# Optimal metabolic strategies for microbial growth in stationary random
environments

Anna Paola Muntoni and Andrea De Martino  Politecnico di Torino, Turin, Italy,
and Italian Institute for Genomic Medicine, Turin, Italy
<EMAIL_ADDRESS>
###### Abstract

In order to grow in any given environment, bacteria need to collect
information about the medium composition and implement suitable growth
strategies by adjusting their regulatory and metabolic degrees of freedom. In
the standard sense, optimal strategy selection is achieved when bacteria grow
at the fastest rate possible in that medium. While this view of optimality is
well suited for cells that have perfect knowledge about their surroundings
(e.g. nutrient levels), things are more involved in uncertain or fluctuating
conditions, especially when changes occur over timescales comparable to (or
faster than) those required to organize a response. Information theory however
provides recipes for how cells can choose the optimal growth strategy under
uncertainty about the stress levels they will face. Here we analyse the
theoretically optimal scenarios for a coarse-grained, experiment-inspired
model of bacterial metabolism for growth in a medium described by the (static)
probability density of a single variable (the ‘stress level’). We show that
heterogeneity in growth rates consistently emerges as the optimal response
when the environment is sufficiently complex and/or when perfect adjustment of
metabolic degrees of freedom is not possible (e.g. due to limited resources).
In addition, outcomes close to those achievable with unlimited resources are
often attained effectively with a modest amount of fine tuning. In other
terms, heterogeneous population structures in complex media may be rather
robust with respect to the resources available to probe the environment and
adjust reaction rates.

##  1 Introduction

The standard theoretical view of bacterial growth posits that, in any growth
medium, cells are capable of adjusting their metabolic degrees of freedom
(i.e. the rates of metabolic reactions) within bounds dictated by
thermodynamic and regulatory constraints (e.g. enzyme expression levels,
reaction free energies, etc.) so as to maximize their growth rate [1]. Besides
evolutionary considerations, such a picture is supported by the fact that the
expression levels of certain metabolic enzymes and of basic macromolecular
machines like ribosomes actually appear to be tuned for growth-rate
maximization in bacterial populations [2, 3]. On the other hand, the
significant cell-to-cell variability in growth rates observed in experiments
[4, 5, 6, 7, 8], together with the fact that constraints arising outside
metabolism suffice to explain a large batch of empirical facts without
assuming any growth-rate optimization [9, 10], appears to call for deeper
insight into the notion of ‘optimality’ for bacterial growth.

Recent work has shown that the relationship between population growth and
cell-to-cell variability is well described by a Maximum Entropy (MaxEnt)
theory leading to a variable trade-off akin to the usual energy-entropy
balance in statistical physics. More specifically, E. coli populations growing
in carbon-limited media realize a close-to-optimal fitness-heterogeneity
trade-off in rich media [11], while they seem to be less variable or slower-
growing than optimal in poorer growth conditions [12]. Metabolic fluxes
likewise appear to be better captured by accounting for such a trade-off than
by a standard optimality assumption [13]. In each case, the balance between
growth and variability is described by a finite (medium-dependent)
‘temperature’, where a zero-temperature (resp. infinite-temperature) limit
corresponds to maximal growth (resp. maximal variability). Save for a few
general ideas derived from broad-brush models [14], what determines the
‘temperature’ (i.e. the fitness-heterogeneity balance) of actual microbial
systems is still unclear.

High variability can naturally arise from unavoidable inter-cellular
differences in gene expression levels or regulatory programs (e.g. cell cycle)
[15]. In models of metabolism, this would lead, at the simplest level, to
cell-dependent changes in the constraints under which growth is optimized. In
this respect, cell-to-cell heterogeneity might be interpreted as ‘optimality
plus noise’, and the ‘temperature’ described above would quantify, in essence,
the noise strength. Importantly, though, there might be an inherent advantage
in maintaining a diverse population, especially in environments that fluctuate
(due e.g. to natural variability) or when cells have imperfect information
about their growth medium (due e.g. to limits in precision caused by the high
costs cells face to maintain and operate a sensing apparatus). These factors
are not usually included in standard models of metabolic networks, which
therefore cannot address the fitness benefits of heterogeneity.

The problem of growth maximization clearly becomes more subtle under
uncertainty about environmental conditions, as the straightforward
optimization that can be carried out in a perfectly known medium is no longer
an option. Recipes for selecting the optimal growth strategy in uncertain
environments are, however, provided by information theory. Theoretical work
aimed at understanding how efficiently populations can harvest, process and
exploit information about variable or unpredictable media has indeed shown
that bet-hedging (i.e. maintaining a fraction of slow-growing cells even in
rich media or sustaining a lower short-term growth to ensure faster long-term
growth) can yield significant fitness gains in a wide variety of situations
[16]. Biological implications of these results have been explored against
several backdrops [17, 18, 19], albeit never specifically in the context of
metabolism.

In this paper, inspired by the above studies as well as by [20] and [21]
(Chapter 6), we look at a minimal, experiment-derived mathematical model to
characterize optimal metabolic strategies for growth in uncertain
environments, focusing for simplicity on static environments defined by the
probability density of a single variable (the ‘stress level’). Optimal
strategies are parametrised by a ‘temperature’ that modulates the amount of
information they encode about the growth medium or, loosely speaking, how
precisely cells can match their phenotype to the external conditions in order
to foster growth. We will show explicitly that, when the medium is
sufficiently complex, optimal populations acquire a non-trivial phenotypic
organization even when the metabolic strategy encodes the maximum possible
amount of information about the external conditions. A broad spectrum of
behaviours is uncovered upon varying the structure of the environment.
Remarkably, however, the emerging scenarios are often robust to changes in the
‘temperature’. This suggests that metabolic networks may yield outcomes close
to globally optimal ones (at least in an information-theoretic sense) even
when resources to probe the environment and adjust metabolic reactions are
limited.

##  2 Results

###  2.1 Model of metabolism and growth

We consider a coarse-grained model of microbial growth metabolism in which
each cell’s metabolic strategy is described by just two quantities, namely the
specific uptake (or inverse growth yield) $q$, quantifying the nutrient intake
required to grow per unit of growth rate, and the biosynthetic expenditure
$\epsilon$, quantifying the proteome mass fraction to be devoted to metabolic
enzymes per unit of growth rate. (In more detailed models of metabolic
networks, the former quantity relates to the rate at which the limiting
nutrient is imported, while the latter is proportional to a weighted sum of
the absolute values of the fluxes through metabolic reactions [22, 20].) For
E. coli growing in carbon-limited media it has been argued that, for given $q$
and $\epsilon$, the growth rate $\mu$ is well described by the formula [20]

$\displaystyle\mu\simeq\frac{\phi}{w+sq+\epsilon}~{}~{},$ (1)

where $s\geq 0$ represents the level of nutritional stress to which the
organism is subject, while $\phi>0$ and $w>0$ are constants representing
respectively the fraction of proteome devoted to constitutively expressed
proteins and the proteome share to be allocated to ribosome-affiliated
proteins per unit of growth rate. (For glucose-limited E. coli growth,
$\phi\simeq 0.48$ and $w\simeq 0.169$ h [9].) For our purposes, $s$ can be
assumed to be inversely proportional to the carbon level as argued in [22] (so
$s\ll 1$ and $s\gg 1$ for carbon-rich and carbon-poor environments,
respectively).

Let us assume that the stress level $s$ in (1) is a homogeneous parameter
whose value is controlled externally. If $\mu$ were to be maximized, the
quantity $sq+\epsilon$ would have to be minimized. In carbon-limited E. coli
growth, however, $q$ and $\epsilon$ are subject to a trade-off such that high
$q$ implies low $\epsilon$ and vice versa [20]. Metabolic states with minimal
biosynthetic expenditure are hence favoured in rich environments (small $s$),
while states of minimal nutritional requirements prevail in poor media (large
$s$). To make a concrete model, we draw inspiration from the
fermentation/respiration duality that again characterizes E. coli growth in
carbon-limited media and assume that the organism can regulate $q$ and
$\epsilon$ between two extreme strategies, denoted by indices $F$ and $R$,
respectively, distinguished by the fact that $q_{F}>q_{R}$ (i.e. the specific
nutrient requirements of $F$ are higher than those of $R$) and
$\epsilon_{R}>\epsilon_{F}$ (i.e. the specific expenditure for $R$ is higher
than for $F$). (Estimated values of the specific nutrient intake and the
specific proteome mass fraction devoted to metabolic enzymes required for
E.coli to grow on lactate under fermentation are $q_{F}\simeq 8$
g${}_{\mathrm{lac}}/$gDW and $\epsilon_{F}\simeq 0.3$ h, respectively; the
corresponding quantities under respiration are instead given by $q_{R}\simeq
5$ g${}_{\mathrm{lac}}/$gDW and $\epsilon_{R}\simeq 0.6$ h [20]. In this work,
we choose the representative values $q_{F}=10$, $\epsilon_{F}=0.1$, $q_{R}=1$,
$\epsilon_{R}=1$, omitting the units as the specifics of the carbon source are
immaterial for us. Nevertheless, with these choices the growth rate $\mu$ can
be interpreted to be measured in $1/$h.) We then describe the trade-off
between $q$ and $\epsilon$ by assuming that both depend on a single variable
$x$ whose value ranges between 0 and 1, such that

$\displaystyle q(x)=q_{R}+(q_{F}-q_{R})(1-x)^{\nu}~{}~{},$ (2)
$\displaystyle\epsilon(x)=\epsilon_{F}+(\epsilon_{R}-\epsilon_{F})x^{\nu}~{}~{},$
(3)

where $\nu>1$ is a constant. The growth rate of the organism will then be
given by

$\displaystyle\mu(x,s)=\frac{\phi}{w+sq(x)+\epsilon(x)}~{}~{}.$ (4)

By taking the derivative of $\mu(x,s)$ over $x$ at fixed $s$, one finds that,
for any given $q(x)$ and $\epsilon(x)$, $\mu$ is maximum when

$\displaystyle s\frac{\partial q}{\partial x}+\frac{\partial\epsilon}{\partial
x}=0~{}~{}.$ (5)

If $q(x)$ and $\epsilon(x)$ are given by (2) and (3), the maximum is achieved
for $x=\widehat{x}(s)$, with

$\displaystyle\widehat{x}(s)=\frac{s^{n}}{s^{n}+s_{c}^{n}}~{}~{}~{}~{}~{},~{}~{}~{}~{}~{}s_{c}=\frac{\epsilon_{R}-\epsilon_{F}}{q_{F}-q_{R}}~{}~{}~{},~{}~{}~{}n=\frac{1}{\nu-1}~{}~{}.$
(6)

This means that media with $s\ll s_{c}$ can be considered to be rich, while
media with $s\gg s_{c}$ are effectively poor. (With our choices for the
parameters, $s_{c}=0.1$.) In turn, if $\mu$ is maximized, strategy $F$ (i.e.
$x=0$) will be used in rich environments (where $\epsilon$ should be as small
as possible) while strategy $R$ (i.e. $x=1$) will be used in poor ones (where
$q$ should be as small as possible), as shown in Figure 1.

Figure 1: Representative scenarios for $q\left(x\right)$ vs
$\epsilon\left(x\right)$ (Equations (2) and (3), left plots in each panel)
with the corresponding fitness landscape $\mu(x,s)$ (right plots), for
$\nu=1.01$ (panel (a)), 2 (b), 4 (c) and 8 (d). The values of $x$ that
maximize $\mu$ for each $s$, i.e. $\widehat{x}(s)$ (Equation (6)), are
represented by a magenta line. The constants characterizing the $R$ and $F$
strategies are set to $q_{F}=10$, $q_{R}=1$, $\epsilon_{F}=0.1$ and
$\epsilon_{R}=1$.

As one modulates the stress level between these two extremes, growth is
maximized by intermediate values of $x$ (i.e. by strategies that use both $F$
and $R$). Other choices generically lead to slower growth.

Notice that the $q-\epsilon$ trade-off gets stronger as $\nu$ approaches $1$,
when the corresponding optimal strategy is a step-like function. Conversely,
it gets weaker and weaker as $\nu$ increases. For sakes of simplicity, in the
following we shall always use the value $\nu=3/2$, which qualitatively
reproduces the trade-off reconstructed from empirical data [20]. A discussion
of how results depend on $\nu$ (including the issue of why a specific value of
$\nu$ may be evolutionarily preferred) is deferred to future work.

###  2.2 Optimizing growth in random environments: theoretical framework

Consider a microbe whose growth rate depends on $x$ and $s$ as in (4). For any
fixed $s$, the cell can maximize $\mu$ by setting $x=\widehat{x}(s)$ (see
(6)). Suppose, however, that $s$ is a random variable with a prescribed
probability density $p(s)$. In this case, cells face an uncertainty about the
exact value of $s$ they will encounter, although they have knowledge of the
ensemble of environmental conditions in which they live (i.e., of $p(s)$).
What is the optimal choice for $x$ in this situation? The most sensible
measure of performance is now arguably given by the mean growth rate

$\displaystyle\left\langle\mu\right\rangle=\int ds\,p(s)\int
dx\,p(x|s)\mu(x,s)~{}~{},$ (7)

whose value depends on the conditional distribution $p(x|s)$ that describes
the stochastic rule used by the cell to select $x$ for any $s$. The question
of optimality therefore concerns the optimal choice of $p(x|s)$. It turns out
that this choice depends on the amount of information about $s$ that is
encoded in $x$. In particular, if

$\displaystyle I=\int ds\,p(s)\int
dx\,p(x|s)\log_{2}\frac{p(x|s)}{p(x)}~{}~{},$ (8)

denotes the mutual information of $x$ and $s$ (in bits), and

$\displaystyle p(x)=\int ds\,p(s)p(x|s)~{}~{},$ (9)

then the optimal $p(x|s)$ is given by the solution of

$\displaystyle\max_{p(x|s)}\left\langle\mu\right\rangle~{}~{}~{}\textrm{subject
to}~{}~{}~{}I=\mathrm{constant}~{}~{},$ (10)

i.e. (see Appendix and [21])

$\displaystyle
p^{\star}(x|s)=\frac{p^{\star}(x)}{N(s,\beta)}\,\,e^{\beta\mu(x,s)}~{}~{},$
(11)

where

$\displaystyle N(s,\beta)=\int dx\,p^{\star}(x)\,e^{\beta\mu(x,s)}~{}~{},$
(12)

while the ‘inverse temperature’ $\beta$ is a Lagrange multiplier and
$p^{\star}(x)$ denotes the probability density of $x$ corresponding to the
optimal choice. Eq. (11) has a rather straightforward interpretation. When
$\beta\to 0$ (‘infinite temperature’), the choice of $x$ becomes independent
of $s$, which implies $I=0$. As $\beta$ increases, $I$ increases (i.e.
cellular responses encode more and more information about the environment) and
$p^{\star}(x|s)$ tends to get more and more sharply peaked around
$\widehat{x}(s)$. For $\beta\to\infty$ (‘zero temperature’), in particular,
one gets $p^{\star}(x|s)\simeq\delta[x-\widehat{x}(s)]$, so that cells respond
to each instance of $s$ by exactly choosing the value of $x$ that maximizes
$\mu$. Such an ‘infinite-precision’ response requires $I$ to be maximal. In
other terms, the higher $I$, the higher $\left\langle\mu\right\rangle$.
(Conversely, as $\beta$ becomes more and more negative, $p^{\star}(x|s)$ tends
to get more and more sharply peaked around the value of $x$ that minimizes
growth for any $s$. For sake of clarity, we shall however limit the following
analysis to the case $\beta>0$.) $\beta$ is therefore a parameter by which one
interpolates between the case of optimal response to any environmental cue and
that in which the cell’s metabolic strategy is completely insensitive to $s$.
Note that, at optimality, the mean growth rate and mutual information given by

$\displaystyle\langle\mu\rangle_{\star}$ $\displaystyle=$ $\displaystyle\int
ds\,p(s)\int dx\,p^{\star}(x|s)\mu(x,s)~{}~{},$ (13) $\displaystyle I^{\star}$
$\displaystyle=$ $\displaystyle\int ds\,p(s)\int
dx\,p^{\star}(x|s)\log_{2}\frac{p^{\star}(x|s)}{p^{\star}(x)}~{}~{},$ (14)

are both functions of $\beta$ and are related by

$I^{\star}=\frac{\beta}{\ln
2}\langle\mu\rangle_{\star}-\langle\log_{2}N(s,\beta)\rangle_{\star}~{}~{}.$
(15)

For different choices of $p(s)$ and $\beta$ one can solve Equations (9), (11)
and (12) numerically by iteration from an initial guess. Starting (iteration
$n=0$) from uniform guesses for $p\left(x\right)$ and $p\left(x|s\right)$, we
iterated Equations (12), (9), and (11) up to numerical convergence, which we
assumed to be achieved when

$\displaystyle\max_{x}|\,p^{(n)}(x)-p^{(n-1)}(x)|<\sigma~{}~{}~{}\mathrm{and}~{}~{}$
(16) $\displaystyle\max_{x}|\,p^{(n)}(x|s)-p^{(n-1)}(x|s)|<\sigma~{}~{},$ (17)

where the index $n$ denotes the iteration step while $\sigma$ a numerical
precision threshold. (A Matlab code implementing the above procedure is
available from https://github.com/anna-pa-m/OptMetStrategy.) Solutions will
clarify how optimal metabolic strategy and population structure change with
$\beta$, i.e. with the amount of information about the environment encoded in
$x$, in any given environmental condition (described by the chosen $p(s)$).

Before moving on, we note that the above setting suggests how an ‘optimal’
value of $\beta$ may arise in this scenario. It is indeed reasonable to think
that $I^{\star}$ is directly related to the quantity of cellular resources
devoted to probing the environment and tuning metabolic reactions, and, in
turn, that higher costs for sensing and metabolism may negatively affect the
fitness if resources are limited. If one assumes for simplicity that such a
cost reduces the growth performance by a constant amount $c$ per bit of
information encoded, the fitness faced by the organism can be written as

${\cal F}=\left\langle\mu\right\rangle_{\star}-cI^{\star}~{}~{}.$ (18)

One easily sees that, contrary to $\left\langle\mu\right\rangle_{\star}$ and
$I^{\star}$ (both of which increase steadily with $\beta$), ${\cal F}$ is
maximum when $c=\partial\left\langle\mu\right\rangle_{\star}/\partial
I^{\star}$, i.e. for

$\beta=\beta^{\star}\equiv\frac{\ln 2}{c}~{}~{}.$ (19)

In other terms, the costs associated with sensing and adjusting metabolism can
lead to the existence of an optimal value of $\beta$, i.e. of an optimal level
of trade-off between $\left\langle\mu\right\rangle$ and $I$, such that
(expectedly) higher values of ${\cal F}$ are possible only if the cost of
encoding information about the environment in metabolic strategies gets
smaller. (A similar idea was discussed in a different context in [13].)

Figure 2: (a) Probability density of the stress level $s$ in a controlled
environment with $s_{0}=0.6>s_{c}$ (top) and corresponding fitness landscape
(bottom). Magenta line: growth-maximizing value of $x$ for each $s$. (b)
Optimal choice for $p^{\star}\left(x|s\right)$ for different values of
$\beta$. Magenta line: growth-maximizing value of $x$ for each $s$. Green
line: mean value of $x$ for the optimal growth strategy as a function of $s$.
(c) Marginal probability density $p^{\star}\left(x\right)$ for different
values of $\beta$. (d) Growth rate distribution at optimality,
$p^{\star}\left(\mu|\beta\right)$, for different values of $\beta$. (e, top)
Several stress distributions centered at different values of $s_{0}$. (e,
bottom) Behavior of the quantity $\left\langle 1-x\right\rangle_{\star}$ as a
function of the fitness for several values of $\beta$ and $s_{0}$ (for fixed
$\beta$, the fitness increases as $s_{0}$ decreases). A value of $\left\langle
1-x\right\rangle_{\star}\simeq 0$ indicates a strong preference for $R$
(respiration); a value of $\left\langle 1-x\right\rangle_{\star}\simeq 1$
points instead towards massive use of $F$ (fermentation).

###  2.3 Tightly controlled stress levels

We start from the simple case where the stress level $s$ is tightly regulated,
as in a lab setting where the nutrient level is externally controlled with
high precision. Specifically, we assume that $p(s)$ is uniform and centered at
a value $s_{0}$, and that $s$ can only vary by 5% with equal probability
around $s_{0}$ (Figure 2a, top panel). The ensuing landscape of $\mu(x,s)$ is
shown in Figure 2a, bottom panel. One sees that, with our choice of $s_{0}$
($s_{0}>s_{c}$, see (6)), growth is maximized for $x\simeq 1$ ($R$ strategy)
for all values of $s$ (magenta line in Fig. 2a). Figure 2b reports the optimal
strategy $p^{\star}(x|s)$ computed numerically for five different values of
$\beta$. As expected, the distribution concentrates around the growth-
maximizing value of $x$ for large enough $\beta$, while it becomes more and
more uniform over the $[0,1]$ interval (with the mean $x$, green dashed line,
getting closer and closer to $1/2$) as $\beta$ approaches zero. This gradual
shift is also clearly visible in the behaviour of $p^{\star}(x)$, representing
the distribution of metabolic strategies at optimality (Figure 2c).
Correspondingly, the growth-rate distribution $p^{\star}(\mu|\beta)$, which
can be obtained numerically as

$\displaystyle p^{\star}(\mu|\beta)$ $\displaystyle=$ $\displaystyle\int
ds\,p(s)\int dx\,p^{\star}(x|s)\,\delta[\mu(x,s)-\mu]~{}~{},$ (20)

is bimodal for small $\beta$ but then tends to get more and more concentrated
around the maximum achievable values of $\mu(x,s)$ as $\beta$ increases
(Figure 2d). The residual variability seen at large $\beta$ reflects the fact
that the stress level can only be known up to a finite precision (see Figure
2a, top panel).

It is instructive to visualize together the results of a series of box-like
environments $p(s)$ with different values of $s_{0}$, from very low to very
high (see Figure 2e, top panel), a setup that mimics an ensemble of
experiments performed at different, exogenously controlled nutrient levels. As
soon as $\beta$ is large enough, the mean response of the system (i.e. the
mean value of $x$) changes from $x\simeq 0$ ($F$ strategy) in lower-stress
media (faster growth) to $x\simeq 1$ ($R$ strategy) in higher-stress media
(slower growth), see Figure 2e, bottom panel. This scenario recapitulates
qualitatively the well-known respiration-fermentation crossover marked by the
onset of acetate excretion that is observed in experimental E. coli
populations [23]. Noticeably, however, it appears already for values $\beta$
well below the reference scale given by $1/\mu_{\max}$ (with $\mu_{\max}$ the
fastest growth rate achievable in this medium, approximately equal to 1/4 in
this case). Only for values of $\beta$ much smaller than this does the
crossover not develop. In other terms, in these simple environments, the
crossover appears to be a feature of the optimal stochastic response
$p^{\star}(x|s)$ that is extremely robust over $\beta$.

Figure 3: (a) Probability density of the stress level $s$ in the ‘exponential
environment’ (top) $p\left(s\right)\propto e^{-s/s_{0}}$ for $s_{0}=0.5$,
$s\in\left[5\cdot 10^{-3},5\cdot 10^{0}\right]$ and corresponding fitness
landscape (bottom). Magenta line: growth-maximizing value of $x$ for each $s$.
(b) Optimal choice for $p^{\star}\left(x|s\right)$ for different values of
$\beta$. Magenta line: growth-maximizing value of $x$ as a function of $s$.
Green line: mean value of $x$ for the optimal choice rule at different values
of $s$. (c) Marginal probability density $p^{\star}\left(x\right)$ for
different values of $\beta$. (d) Growth rate distribution at optimality,
$p^{\star}\left(\mu|\beta\right)$, for different values of $\beta$. (e, top)
Overall fitness $\mathcal{F}$ (Eq. (18)) as a function of $\beta$ for several
values of the information cost-per-bit $c$. (e, bottom) Optimal value of
$\beta$ ($\beta^{\star}$) versus $c$: numerical results (markers) vs
theoretical prediction (Eq. (19), dashed line).

###  2.4 Exponentially distributed stress levels

We now turn to the case in which the stress level is exponentially
distributed. Specifically, we assume that $p(s)\propto\exp(-s/s_{0})$ on the
interval $\left[s_{\rm{min}},\,s_{\rm{max}}\right]$ (Figure 3a, top panel).
The corresponding fitness landscape $\mu(x,s)$ is shown in Figure 3a, bottom
panel, along with the growth-maximizing curve $x=\widehat{x}(s)$ (magenta
line). One sees that $\widehat{x}(s)$ now shifts continuously from 0 ($F$
strategy) to 1 ($R$ strategy) as the stress level increases. Figure 5b shows
instead the optimal growth strategy $p^{\star}(x|s)$ for different values of
$\beta$, with the green line representing the mean value of $x$ at each $s$.
As expected, for small enough $\beta$, $p^{\star}(x|s)$ is roughly uniform
over $[0,1]$. Upon increasing $\beta$, however, the distribution acquires a
structure that more and more closely concentrates around $\widehat{x}(s)$. The
qualitatively correct crossover is however already observed at values of
$\beta$ of the order of $1/\mu_{\max}$. In turn, the distribution of $x$ at
optimality, $p^{\star}(x)$, acquires a very strong bimodal character as
$\beta$ increases (Figure 3c). This clearly indicates that the coexistence of
two sub-populations of fermenters ($x\simeq 0$) and respirators ($x\simeq 1$)
provides the optimal metabolic response even in presence of limited resources
to encode information about the environment into metabolic strategies, giving
a quantitative representation to bet-hedging in the present model.
Correspondingly, the growth-rate distribution (Figure 3d) consistently
displays large variability with a surprisingly weak dependence on $\beta$.
Note that no bimodality is observed in $p^{\star}(\mu|\beta)$ despite the
bimodality of $p^{\star}(x)$.

It is important to remark that large fluctuations persist even in the
$\beta\to\infty$ limit, when the information about the stress levels encoded
in the metabolic strategy is maximal. In other terms, the globally optimal
growth strategy ($\beta\to\infty$) in an exponentially-distributed medium
requires a large degree of heterogeneity in growth rates. To better visualize
the robustness of these outcomes with respect to $\beta$, we display in Figure
3e the re-scaled fitness ${\cal F}$ defined in (18) as a function of the
‘inverse temperature’. As anticipated, ${\cal F}$ has a maximum at
intermediate value of $\beta$, related to the cost-per-bit $c$ of encoding
information as shown in (19) (bottom panel): higher costs imply lower optimal
values of $\beta$. Noticeably, though, with the realistic parameters we used,
the maximum of the fitness function is extremely flat. This suggests that, at
least in principle, metabolic networks could be capable of generating optimal
growth profiles that are robust to the amount of information about the
environment encoded in the growth strategy. In this respect, questions
concerning the fine-tuning of the value of $\beta$ might be less relevant for
this problem than they likely are for the MaxEnt-related growth-heterogeneity
trade-off discussed in [11, 12, 13]: relatively limited environmental cues
could suffice to bias the distribution of metabolic strategies enough to
generate a (stochastic) response close to the globally optimal one, i.e. that
achievable by perfectly matching $x$ to the stress levels.

###  2.5 Power-law distributed stress levels

A yet more complex scenario is that in which the distribution of stress levels
has a power-law behaviour of the type $p\left(s\right)\propto 1/s$ on the
interval $s\in\left[s_{\rm{min}},s_{\rm{max}}\right]$ (Figure 4a, top panel,
with the corresponding growth rate landscape $\mu(x,s)$ reported in the bottom
panel). Results for this case are shown in Figures 4b-e. In brief, the optimal
growth strategy $p^{\star}(x|s)$, which is uniform for sufficiently small
$\beta$, matches the globally optimal one (i.e. $\widehat{x}(s)$, represented
by the magenta line in Figure 4a) more and more closely as $\beta$ increases
(Figure 4b). The distribution of $x$ at optimality (Figure 4c) again
underscores a non-trivial structuring of the population, which separates into
well-defined groups of faster-growing fermenters ($x\simeq 0$) and slower-
growing respiratos ($x\simeq 1$). Remarkably, the separation already occurs
effectively at values of $\beta$ comparable with $1/\mu_{\max}$, with
$\mu_{\max}$ the fastest growth rate achievable in the medium. At odds with
the exponential case, however, the growth-rate distribution now displays
bimodality robustly over $\beta$ (see Figure 4d). Finally, as in the
exponential case, the value of $\beta$ yielding the maximum fitness
$\mathcal{F}$ decreases with the cost-per-bit $c$, and the maximum again
appears to get flatter as $c$ decreases (Figure 4e), suggesting that limited
resources may suffice to fine-tune $\beta$ so as to achieve responses that are
effectively optimal.

Figure 4: (a) Probability density of the stress level $s$ in the ‘power-law
environment’ (top) and corresponding fitness landscape (bottom). Here,
$s_{\min}=3\cdot 10^{-4}$ and $s_{\max}=3\cdot 10^{1}$. Magenta line: growth-
maximizing value of $x$ for each $s$. (b) Optimal choice for
$p^{\star}\left(x|s\right)$ for different values of $\beta$. Magenta line:
growth-maximizing value of $x$ as a function of $s$. Green line: mean value of
$x$ for the optimal choice rule at different values of $s$. (c) Marginal
probability density $p^{\star}\left(x\right)$ for different values of $\beta$.
(d) Growth rate distribution at optimality, $p^{\star}\left(\mu|\beta\right)$,
for different values of $\beta$. (e, top) Overall metabolic objective function
$\mathcal{F}$ (Eq. (18)) as a function of $\beta$ for several value of the
information cost-per-bit $c$. (e, bottom) Optimal value of $\beta$
($\beta^{\star}$) versus $c$: numerical results (markers) vs theoretical
prediction (Eq. (19), dashed line).  Figure 5: (a) Probability density of the
stress level $s$ in a two-state environment (top) and corresponding fitness
landscape (bottom). Magenta line: growth-maximizing value of $x$ for each $s$.
(b) Optimal choice for $p^{\star}\left(x|s\right)$ for different values of
$\beta$. Magenta line: growth-maximizing value of $x$ for each $s$. Green
line: mean value of $x$ for the optimal choice rule at different as a function
of $s$. (c) Marginal probability density $p^{\star}\left(x\right)$ for
different values of $\beta$. (d) Growth rate distribution at optimality,
$p^{\star}\left(\mu|\beta\right)$, for different values of $\beta$. (e)
Alternative bimodal stress distribution with an extended background of stress
levels with non-zero probability. (f) Corresponding growth rate distribution
at optimality, $p^{\star}\left(\mu|\beta\right)$, for different values of
$\beta$.

###  2.6 Two-state environments

Figure 5 displays results obtained for the case of a bimodal environment in
which high-probability favourable conditions coexist with low-probability very
adverse ones (Figure 5a), as e.g. in experiments probing bacterial resistance
to stress via antibiotic cycles [24]. Here, 95 % of the distribution is
concentrated around $s_{0}=0.05<s_{c}$, whereas high stress levels take values
around $s_{1}=0.8>s_{c}$111The low-stress (high-stress) region is obtained by
truncating in the interval $\left[0,\,0.1\right]$ ($\left[0.7,\,0.9\right]$) a
normal density of mean $0.05$ ($0.8$) and standard deviation $10^{-2}$
($10^{-2}$). For $s\in\left(0.1,\,0.7\right)$, $p\left(s\right)=0$. In other
terms, intermediate values of $s$ are strictly prohibited.. According to the
growth-rate landscape (Figure 5a, bottom panel), while the low-cost strategy
($x=0$) is favored in rich conditions, high-yield metabolism ($x=1$) provides
the optimal response under stress (magenta line in Figure 5a, bottom panel).
Optimal adaptation to a strict bimodal environment therefore requires the
ability to neatly separate the two phenotypes. Indeed, as $\beta$ increases,
the optimal strategy selection rule $p^{\star}(x|s)$ reproduces more and more
closely the optimal response (Figure 5b), while the population gradually
acquires a structure in terms of $x$. As in previous cases, as soon as $\beta$
is sufficiently large one observes the formation of two sub-populations
(Figure 5c): one formed by cells that use a mixed strategy with a stronger
fermentative component (smaller $x$), the other formed by a small but robust
group of strict respirators ($x\simeq 1$). This partitioning is reflected in
turn in the distribution of growth rates (Figure 5d), which displays a marked
bimodal character even for large $\beta$, with lower growth rates associated
with respirators. (It should however be noted that, in this environment, the
background growth-rate landscape is effectively bimodal, as seen from the
$\beta\to 0$ limit in Figure 5d.) These results paint a direct metabolic
realization of the bet-hedging scenario, with respirators forming the group of
‘persisters’ [24].

Noticeably, the dependence on $\beta$ in this environment appears to be
stronger than in previous cases, suggesting that optimal adaptation to a two-
state medium requires the encoding of a considerable amount of information
about stress levels in the metabolic strategy. In view of this, it is
reasonable to ask how the presence of a broad, low-probability background of
stress levels along with the two ‘peaks’ at low and high stress would change
optimal adaptation. Remarkably, results shown in Figure 5e suggest that this
scenario mainly affects the faster-growing sub-population222To obtain the
probability density shown in Figure 5e (top panel), we first removed the
truncations used for Figure 5a, then added a uniform distribution in the
interval $\left[0,\,1.0\right]$ multiplied by $0.8$, and finally normalized
the overall $p\left(s\right)$.. Indeed, as $\beta$ grows, the optimal
population tends to exploit intermediate values of $x$ in a more and more
refined way by depleting the sub-population at smaller values of $x$ (Figure
5f, to be compared with Figure 5c). In other terms, the presence of a robust
sub-population of slower-growing respirators is crucial for optimal
adaptation.

Figure 6: Numerical results for the probability densities of the specific
proteome cost $\epsilon$ (left plot in each panel) and the specific uptake $q$
(right plot in each panel) for different values of $\beta$. Panels (a)-(d)
correspond respectively to the cases of a tightly controlled (a), exponential
(b), power-law (c) or strict bimodal (d) stress distribution discussed in
Figures 2-5. The lower and upper bounds for $\epsilon$ and $q$ are fixed to
$\epsilon_{F}=0.1$ and $q_{R}=1$, and to $\epsilon_{R}=1$ and $q_{F}=10$,
respectively.

###  2.7 A closer look at optimal growth strategies

It is finally instructive to revisit the optimal phenotypic distributions
found in the four types of environments discussed above in terms of the
biologically relevant variables, namely the specific intake $q$ and the
specific proteome cost $\epsilon$. The distribution of these quantities can be
obtained numerically from the optimal growth strategy $p^{\star}(x|s)$ and the
definitions (2) and (3) as

$\displaystyle p^{\star}(q|\beta)$ $\displaystyle=$ $\displaystyle\int
ds\,p(s)\int dx\,p^{\star}(x|s)\,\delta[q(x)-q]~{}~{},$ (21) $\displaystyle
p^{\star}(\epsilon|\beta)$ $\displaystyle=$ $\displaystyle\int ds\,p(s)\int
dx\,p^{\star}(x|s)\,\delta[\epsilon(x)-\epsilon]~{}~{}.$ (22)

Results are reported in Figure 6a-d. One clearly sees how, expectedly, optimal
adaptation to a tightly controlled medium gradually concentrates the metabolic
phenotypes around the growth-maximizing one as $\beta$ increases (Figure 6a).
In all other (more complex) cases, however, the distributions of metabolic
phenotypes effectively define clear sub-populations already for values of
$\beta$ comparable with $1/\mu_{\max}$. Based on the previous results, this
process by itself can lead to an outcome close to the globally optimum one
($\beta\to\infty$) in an exponential environment (Figure 6b) as well as in a
power-law environment (Figure 6c). Indeed in both cases phenotypic
distributions do not change substantially as $\beta$ is further increased. The
bimodal environment again appears to be more sensitive to the value of $\beta$
(i.e. to the amounts of resources available), as its corresponding phenotypic
distribution undergoes considerable refinements as $\beta$ gets larger and
larger (Figure 6d). In this respect, it is fair to say that bimodal media pose
an especially complex adaptation problem for cells that strive to optimize
growth.

##  3 Discussion

The standard theoretical framework to describe exponentially growing microbial
populations mostly relies on the assumption that cells aim at maximizing their
growth rate in any given medium. This idea should however be reconciled with
the empirical fact that bacterial populations display remarkable cell-to-cell
diversity even in terms of single-cell growth rates. Such a question is
especially pressing in the context of metabolic networks, where optimality
normally implies a maximal reduction of variability (e.g. as in Flux-Balance-
Analysis and related models). Here we attempt to bridge optimality and
variability in metabolism through the fact that metabolic strategies need to
encode information about the growth medium. More precisely, optimal strategies
for microbial growth in complex (random) media depend on the amount of
information about the environment that can be encoded in the key metabolic
variable(s). By framing this idea within a simple information-theory
perspective, we have studied the optimal growth strategies for a coarse-
grained but experiment-inspired model of growth metabolism subject to random
stress levels. The key parameter $\beta\geq 0$ modulates, in essence, how
precisely metabolic variables can be tuned in response to the stress levels
or, equivalently for our purposes, the amount of cellular resources available
to tune the metabolic response to the environmental conditions. By changing
$\beta$, one passes from optimal strategies that are completely insensitive to
the composition of the medium ($\beta=0$) to strategies that are perfectly
matched to the structure of the environment ($\beta\to\infty$). We have then
analyzed the scenarios generated by these strategies in different types of
environments. The general lesson is that, when cellular resources are limited,
metabolic strategies for optimal growth require some degree of heterogeneity
even in tightly controlled media. In addition, we find that, in realistic
scenarios, outcomes close to those achievable with unlimited resources are
often attained effectively with a modest amount of fine-tuning or,
equivalently, with limited information about the environment. In other terms,
optimal metabolic strategies for growth may be effectively robust with respect
to the amounts of cellular resources available.

From a purely theoretical perspective, models addressing the adaptation of
populations to unpredictable external conditions have been studied for several
decades. In our view, despite lacking an explicit dynamics, our approach is
conceptually related to that of [25], where heterogeneities in the phenotype
distribution emerge as evolutionarily stable strategies to cope with
fluctuating environments. Likewise, the ‘exploration-exploitation’ paradigm
discussed in [17] leads to a similar outcome in terms of growth rate
distributions, albeit in a highly stylized framework. A dynamical counterpart
of the static scenario discussed here indeed shows that optimal adaptation can
be defined even for dynamically varying stress levels (forthcoming). On the
other hand, heterogeneity of growth rates (and indirectly of metabolic
phenotypes) has been repeatedly observed in experiments probing actual cell
populations subject to different stressors. Large variability in growth-rate
distributions characterizes for instance microbial communities in fluctuating
conditions [24, 26, 27], where heterogeneity induced e.g. by changes in
environmental cues coexists with medium-independent phenotypic variability due
to stochasticity in gene expression. By expanding the pool of genotypes
present within a population, the latter plays a key role for its long-term
adaptation [28]. Obtaining a direct quantitative picture of the the metabolic
strategies of individual cells in a live population is instead experimentally
challenging. Recent work integrating high-resolution techniques for local
microenvironment sensing with statistical inference has however allowed to
quantitatively assess the presence of different metabolic phenotypes in a
population of cells that engineers its own environment [29]. Progress along
these lines will hopefully shed more light on the distributions of
biologically relevant variables in phenotypically heterogeneous populations.

The results we presented here suggest that, in any medium, fitness is
maximized by an optimal distribution of phenotypes. To understand how close
bacterial populations come to these optimal strategies, one needs to port our
modeling framework to more realistic models of metabolic networks. It would be
especially interesting, in our view, to compare the predictions based on
optimal growth driven by information encoded about the environment with those
obtained within the fitness-heterogeneity trade-off scenario of [11, 12, 13].
These approaches rely on the MaxEnt principle to characterize optimal
phenotypic distributions in terms of a fitness-variability trade-off, and in
turn provide a route to inferring how close real microbial populations are to
optimality. So far, this issue has only been explored for populations living
in tightly-controlled media [12]. Naturally, however, things may be
environment-dependent. With proper data, and by integrating the current
framework with the MaxEnt models introduced in [11], one could potentially
establish how much of the observed variability is due to adaptation to complex
environments versus stochastic bet-hedging.

A few other generalizations and open issues could be of further interest.
First, we assumed the value of $\nu$ (Equation (3)) to be given, representing
a property of the metabolic and regulatory networks underlying the
$q-\epsilon$ trade-off. Clearly, results depend on the choice of $\nu$, albeit
weakly if $\nu$ varies in a realistic range. Important and potentially
insightful question however relate to (i) whether the value of $\nu$ can, in
some sense, be optimized upon, and to (ii) how close empirical values of $\nu$
are to such optima. An information-theoretic framework similar to that
employed here might be suited to tackle this issue. Second, in our formulation
we have assumed that bacteria have knowledge of the ensemble of conditions in
which they grow, i.e. of $p(s)$. This model can however be generalized to the
case in which bacteria have to learn the ensemble over time. From an
information theory perspective, a dynamical approach is likely to yield yet
more insight into the idea of ‘optimal bacterial growth’. Finally, it may be
noted that our minimal model of growth completely disregards maintenance
costs, namely the fact that cells can only grow when certain basal (and
possibly growth-rate dependent) metabolic requirements are satisfied. While
results presented here can be seen as the low-maintenance limit of this more
general case, optimal strategies and growth rate distributions are bound to be
affected by non-trivial maintenance costs, especially in heterogeneous media.
A detailed study of these aspects would clarify the interplay between optimal
growth, maintenance and stress levels in complex environments.

## Data availability statement

The data that support the findings of this study are openly available at the
following URL https://github.com/anna-pa-m/OptMetStrategy.

## References

## References

  * [1] Bruggeman FJ, Planqué R, et al (2020). Searching for principles of microbial physiology. FEMS Microbiology Reviews, 44(6), 821-844.
  * [2] Jensen PR, Michelsen O, & Westerhoff HV (1993) Control analysis of the dependence of Escherichia coli physiology on the H(+)- ATPase. Proc Natl Acad Sci USA, 90, 8068-72.
  * [3] Bosdriesz E, Molenaar D, et al (2015) How fast-growing bacteria robustly tune their ribosome concentration to approximate growth-rate maximization. FEBS J, 282, 2029-44.
  * [4] Irwin PL, Nguyen LH, Paoli GC, Chen CY (2010) Evidence for a bimodal distribution of Escherichia coli doubling times below a threshold initial cell concentration. BMC Microbiol 10, 1-4.
  * [5] Kiviet DJ, Nghe P, et al (2014) Stochasticity of metabolism and growth at the single-cell level. Nature 514, 376-379.
  * [6] Taheri-Araghi S, Bradde S, et al (2015) Cell-size control and homeostasis in bacteria. Curr. Biol. 25, 385-391.
  * [7] Kennard AS, Osella MJ, et al (2016) Individuality and universality in the growth-division laws of single E. coli cells. Phys. Rev. E 93, 012408.
  * [8] Jun S, Si F, et al (2018) Fundamental principles in bacterial physiology: history, recent progress, and the future with focus on cell size control: a review. Rep Prog Phys 81, 056601.
  * [9] Scott M, Gunderson CW, et al (2010) Interdependence of cell growth and gene expression: origins and consequences. Science 330, 1099-1102.
  * [10] Panlilio M, Grilli J, et al (2021) Threshold accumulation of a constitutive protein explains E. coli cell-division behavior in nutrient upshifts. Proceedings of the National Academy of Sciences, 118, e2016391118.
  * [11] De Martino D, Capuani F, & De Martino A (2016) Growth against entropy in bacterial metabolism: the phenotypic trade-off behind empirical growth rate distributions in E. coli. Phys Biol 13, 036005.
  * [12] Muntoni AP, Braunstein A, et al (2022) Relationship between fitness and heterogeneity in exponentially growing microbial populations. Biophys J 121, 1919-1930.
  * [13] De Martino D, Andersson A et al (2018) Statistical mechanics for metabolic networks during steady state growth. Nat Comm 9, 2988-2989.
  * [14] De Martino D, Capuani F & De Martino A (2017) Quantifying the entropic cost of cellular growth control. Phys Rev E 96, 010401.
  * [15] Keren L, Van Dijk D et al. (2015) Noise in gene expression is coupled to growth rate. Genome Research 25, 1893-1902.
  * [16] Rivoire O & Leibler S (2011) The value of information for populations in varying environments. J Stat Phys 142, 1124-1166.
  * [17] De Martino A, Gueudre T, & Miotto M (2019) Exploration-exploitation tradeoffs dictate the optimal distributions of phenotypes for populations subject to fitness fluctuations. Phys Rev E 99, 012417.
  * [18] Levien E, Min J, et al (2021) Non-genetic variability in microbial populations: survival strategy or nuisance? Rep Prog Phys, 84, 116601.
  * [19] Dinis L, Unterberger J & Lacoste D (2022) Pareto-optimal trade-off for phenotypic switching of populations in a stochastic environment. J Stat Mech 2022, 053503.
  * [20] Mori M, Marinari E, & De Martino A (2019) A yield-cost tradeoff governs Escherichia coli’s decision between fermentation and respiration in carbon-limited growth. npj Sys Biol Appl 5, 1-9.
  * [21] Bialek W (2012) Biophysics: searching for principles (Princeton University Press)
  * [22] Mori M, Hwa T, et al (2016) Constrained allocation flux balance analysis. PLoS Comp Biol 12, e1004913.
  * [23] Basan M, Hui S, et al (2015) Overflow metabolism in Escherichia coli results from efficient proteome allocation. Nature 528, 99-104.
  * [24] Gefen O & Balaban NQ (2009) The importance of being persistent: heterogeneity of bacterial populations under antibiotic stress. FEMS Microbiol Rev 33, 704-717.
  * [25] Sasaki A and Ellner S (1995) The evolutionarily stable phenotype distribution in a random environment. Evolution 49, 337-50.
  * [26] Grimbergen AJ, Siebring J, Solopova A & Kuipers OP (2015) Microbial bet-hedging: the power of being different. Current Opin Microbiol 25, 67-72.
  * [27] Morawska LP, Hernandez‐Valdes JA & Kuipers OP (2022) Diversity of bet‐hedging strategies in microbial communities—Recent cases and insights. WIREs Mechanisms of Disease 14, e1544.
  * [28] Ackermann M (2015) A functional perspective on phenotypic heterogeneity in microorganisms. Nature Rev Microbiol 13, 497-508.
  * [29] Onesto V, Forciniti S, Alemanno F, et al (2023) Probing Single-Cell Fermentation Fluxes and Exchange Networks via pH-Sensing Hybrid Nanofibers. ACS Nano 10.1021/acsnano.2c06114.

##  Appendix A Derivation of the optimal distribution

Our goal is to determine the conditional distribution $p\left(x|s\right)$ that
maximizes the expectation value of the growth rate –computed with respect to
the joint probability density of the degree of freedom $x$ and of the stress
$s$, i.e. $p\left(x,s\right)$– when the mutual information regarding the
stress encoded in the conditional distribution is limited to a constant; that
is, we want to solve

$\displaystyle\max_{p(x|s)}\left\langle\mu\right\rangle~{}~{}~{}\textrm{subject
to}~{}~{}~{}I=\mathrm{constant}~{}~{}.$ (24)

To this end, we introduce, within the formalism of Lagrange multipliers, the
Lagrangian function

$\displaystyle\mathcal{L}\left[p\left(x|s\right)\right]$ $\displaystyle=$
$\displaystyle\int ds\,p\left(s\right)\int
dx\,p\left(x|s\right)\mu\left(x,s\right)$ $\displaystyle+\gamma\left[\int
ds\,p\left(s\right)\int
dx\,p\left(x|s\right)\left[\log_{2}p\left(x|s\right)-\log_{2}p\left(x\right)\right]-I\right]$
$\displaystyle+\int ds\,\left[\lambda\left(s\right)\int
dx\,p\left(x|s\right)-1\right]~{}~{},$

where $\gamma$ is the Lagrange multiplier associated with the constraint on
the mutual information between $s$ and $x$, and $\lambda\left(s\right)$
ensures that for any value of $s$, the conditional distribution
$p\left(x|s\right)$ is normalized to $1$. Computing the functional derivative
one gets

$\displaystyle\frac{\delta\mathcal{L}}{\delta p\left(x|s\right)}$
$\displaystyle=$ $\displaystyle\int ds^{\prime}\int
dx^{\prime}\delta\left(x-x^{\prime}\right)\delta\left(s-s^{\prime}\right)p\left(s^{\prime}\right)\mu\left(x^{\prime},s^{\prime}\right)$
$\displaystyle+\gamma\left[\int ds^{\prime}\int
dx^{\prime}p\left(s^{\prime}\right)\log_{2}\frac{p\left(x^{\prime}|s^{\prime}\right)}{p\left(x^{\prime}\right)}\delta\left(x-x^{\prime}\right)\delta\left(s-s^{\prime}\right)\right]$
$\displaystyle+\gamma\left[\int ds^{\prime}\int
dx^{\prime}p\left(s^{\prime}\right)p\left(x^{\prime}|s^{\prime}\right)\frac{1}{p\left(x^{\prime}|s^{\prime}\right)}\delta\left(x-x^{\prime}\right)\delta\left(s-s^{\prime}\right)\right]$
$\displaystyle-\gamma\left[\int ds^{\prime}\int
dx^{\prime}p\left(s^{\prime}\right)p\left(x^{\prime}|s^{\prime}\right)\frac{1}{p\left(x^{\prime}\right)}\frac{\delta
p\left(x^{\prime}\right)}{\delta p\left(x|s\right)}\right]$
$\displaystyle+\int
ds^{\prime}\,dx^{\prime}\,\lambda\left(s^{\prime}\right)\delta\left(s^{\prime}-s\right)\delta\left(x-x^{\prime}\right)~{}~{}.$

The remaining integrations involving Dirac $\delta$-functions are easily
performed, yielding

$\displaystyle\frac{\delta\mathcal{L}}{\delta p\left(x|s\right)}$
$\displaystyle=$ $\displaystyle
p\left(s\right)\mu\left(x,s\right)+\gamma\left[p\left(s\right)\log_{2}\frac{p\left(x|s\right)}{p\left(x\right)}+p\left(s\right)-I_{0}\right]+\lambda\left(s\right)~{}~{},$
(25)

where

$\displaystyle I_{0}=\int ds^{\prime}\int
dx^{\prime}p\left(s^{\prime}\right)p\left(x^{\prime}|s^{\prime}\right)\frac{1}{p\left(x^{\prime}\right)}\frac{\delta
p\left(x^{\prime}\right)}{\delta p\left(x|s\right)}~{}~{}.$ (26)

Note however that $p\left(x\right)=\int ds\,p\left(x,s\right)=\int
ds\,p\left(x|s\right)p\left(s\right)$. Therefore

$\displaystyle I_{0}$ $\displaystyle=$ $\displaystyle\int ds^{\prime}\,\int
dx^{\prime}\,p\left(s^{\prime}\right)p\left(x^{\prime}|s^{\prime}\right)\frac{1}{p\left(x^{\prime}\right)}\int
ds^{\prime\prime}p\left(s^{\prime\prime}\right)\delta\left(s^{\prime\prime}-s\right)\delta\left(x^{\prime}-x\right)$
$\displaystyle=$ $\displaystyle p\left(s\right)\int
dx^{\prime}\frac{1}{p\left(x^{\prime}\right)}\int
ds^{\prime}\,p\left(s^{\prime}\right)p\left(x^{\prime}|s^{\prime}\right)\delta\left(x-x^{\prime}\right)$
$\displaystyle=$ $\displaystyle p\left(s\right)$

Setting the derivative of the Lagrangian to zero leads to the condition

$\displaystyle
p\left(s\right)\left[\mu\left(x,s\right)+\gamma\log_{2}\frac{p\left(x|s\right)}{p\left(x\right)}+\gamma-\gamma\right]+\lambda\left(s\right)=0~{}~{},$
(27)

from which one immediately gets

$\displaystyle p^{\star}\left(x|s\right)$ $\displaystyle\propto$
$\displaystyle
p^{\star}\left(x\right)e^{\beta\mu\left(x,s\right)+\beta\frac{\lambda\left(s\right)}{p\left(s\right)}}~{}~{},$
(28)

where here we have defined $\beta=-1/\gamma$. Upon imposing the normalization
condition

$\displaystyle\int dx\,p^{\star}\left(x|s\right)$ $\displaystyle=$
$\displaystyle 1\qquad\forall s~{}~{},$ (29)

the value of $\lambda\left(s\right)$ can be straightforwardly determined to be

$\displaystyle\lambda\left(s\right)$ $\displaystyle=$
$\displaystyle\beta^{-1}p\left(s\right)\log\left[\int
dx\,p^{\star}\left(x\right)e^{\beta\mu\left(x,s\right)}\right]^{-1}~{}~{}.$
(30)

Substituting this into (28) one arrives at Equations (11) and (12), where
$N\left(s,\beta\right)=\int
dx\,p^{\star}\left(x\right)e^{\beta\mu\left(x,s\right)}$.


# EgoTV : Egocentric Task Verification
from Natural Language Task Descriptions

Rishi Hazra1 Brian Chen 2 Akshara Rai2 Nitin Kamra 2 Ruta Desai2
1Örebro University, 2Meta
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

To enable progress towards egocentric agents capable of understanding everyday
tasks specified in natural language, we propose a benchmark and a synthetic
dataset called Egocentric Task Verification (EgoTV). EgoTV contains multi-step
tasks with multiple sub-task decompositions, state changes, object
interactions, and sub-task ordering constraints, in addition to abstracted
task descriptions that contain only partial details about ways to accomplish a
task. We also propose a novel Neuro-Symbolic Grounding (NSG) approach to
enable the causal, temporal, and compositional reasoning of such tasks. We
demonstrate NSG’s capability towards task tracking and verification on our
EgoTV dataset and a real-world dataset derived from CrossTask [cross_task]
(CTV). Our contributions include the release of the EgoTV and CTV datasets,
and the NSG model for future research on egocentric assistive agents.

Figure 1: EgoTV benchmark. A positive example [Left] and a negative example
[Right] from the train set along with illustrative examples from the test
splits [Bottom] of EgoTV are shown. The test splits are focused on
generalization to novel compositions of tasks, unseen sub-tasks or steps and
scenes, and abstraction in NL task descriptions. The bounding boxes are solely
for demonstration purposes and are not used during training/inference.

##  1 Introduction

Inspired by recent progress in visual systems [MagicLeap,
ungureanu2020hololens], we consider an assistive egocentric agent capable of
reasoning about daily activities. When invoked via natural language commands,
for e.g., while baking a cake, the agent understands the steps involved in
baking, tracks progress through the various stages of the task, detects and
proactively prevents mistakes by making suggestions. Such an agent would
empower users to learn new skills and accomplish tasks efficiently.

Developing such an egocentric agent capable of tracking and verifying everyday
tasks based on their natural language specification is challenging for
multiple reasons. First, such an agent must reason about various ways of doing
a _multi-step_ task specified in natural language. This entails decomposing
the task into relevant actions, state changes, object interactions as well as
any necessary causal and temporal relationships between these entities.
Secondly, the agent must ground these entities in egocentric observations to
track progress and detect mistakes. Lastly, to truly be useful, such an agent
must support tracking and verification for a combination of tasks and,
ideally, even unseen tasks. These three challenges – causal and temporal
reasoning about task structure from natural language, visual grounding of sub-
tasks, and compositional generalization – form the core goals of our work.

As our first contribution, we propose a benchmark – _Ego centric Task
Verification_ (EgoTV ) – and a corresponding dataset in the AI2-THOR [ai2thor]
simulator. Given a natural language (NL) task description and a corresponding
egocentric video of an agent, the goal of EgoTV is to verify whether the task
was successfully completed in the video or not. EgoTV contains multi-step
tasks with _ordering_ constraints on the steps and _abstracted_ NL task
descriptions with omitted low-level task details inspired by the needs of
real-world assistants. We also provide splits of the dataset focused on
different generalization aspects, e.g., unseen visual contexts, compositions
of steps, and tasks (see Figure 1).

Our second contribution is a novel approach for order-aware visual grounding –
_N euro-Symbolic Grounding_ (NSG), capable of compositional reasoning and
generalizing to unseen tasks owing to its ability to leverage abstract NL
descriptions and compositional structure of tasks (task decomposition,
ordering). In contrast, state-of-the-art vision-language models [coca, clip,
videoclip, clip_hitchiker] struggle to ground NL descriptions in egocentric
videos, and do not generalize to unseen tasks. NSG outperforms these models by
$\mathbf{33.8}\%$ on compositional generalization and $\mathbf{32.8}\%$ on
abstractly described task verification. Finally, to evaluate NSG on real-world
data, we instantiate EgoTV on the CrossTask [cross_task] instructional video
dataset. We find that it also outperforms state-of-the-art models at task
verification on CrossTask. We hope that the EgoTV benchmark and dataset will
enable future research on egocentric agents capable of aiding in everyday
tasks.

##  2 Related Work

Video-based Task Understanding. Understanding tasks from videos has been a
long-standing theme in vision research with focus on recognizing activities
[charades_dataset, epic_kitchens], human-object interactions [action_genome,
ego_4d], and object state changes [change_it, fathi2013modeling] using
egocentric or exocentric videos. But apart from recognizing actions, objects,
and state changes, task verification also requires understanding temporal
orderings between them. Our work is, therefore, closer to research on
understanding instructional tasks [cross_task, tang2019coin], which require
reasoning about multiple, ordered steps. Prior works focus on either learning
the order of steps [bansal2022my, lin2022learning, huang2019neural,
mao2023action] or use step-ordering as a supervisory signal for learning step-
representations or step-segmentation [cross_task, shen2021learning]. Instead,
we are focused on video-based order verification of steps described in NL,
akin to [qian2022svip].

Temporal Video Grounding. Our EgoTV benchmark is also closely related to the
problem of Temporal Video Grounding (TVG) [mexaction2,
human_activity_understanding, regneri2013grounding, change_it]. However, prior
work on TVG predominantly focuses on localizing a single action in the video
[MAD_dataset, jiang2014thumos]. In contrast, EgoTV requires localizing
multiple actions, wherein actions could have partial ordering, i.e., actions
could have more than one valid ordering amongst them.

| ————– Reasoning ————– | —— Dataset Characteristics ——
---|---|---
| compositional | causal | temporal | egocentric |  | real-
---
world
| diagnostic
---
tools
CLEVRER [clevrer] |  ✓ ✓ ✓ |  ✗ ✗ ✓
Next-QA [next_qa_dataset] |  ✗ ✓ ✓ |  ✗ ✓ ✓
ActivityNet-QA [activity_net_dataset] |  ✗ ✗ ✓ |  ✗ ✓ ✗
STAR [star_situated_reasoning] |  ✓ ✓ ✓ |  ✗ ✓ ✓
Causal-VidQA [causal_vid_qa] |  ✗ ✓ ✗ |  ✗ ✓ ✓
EPIC-KITCHENS [epic_kitchens] |  ✓ ✓ ✗ |  ✓ ✓ ✓
Ego-4D [ego_4d] |  ✗ ✓ ✗ |  ✓ ✓ ✓
VIOLIN [violin_dataset] |  ✗ ✓ ✗ |  ✗ ✓ ✗
Cross-Task [cross_task] |  ✓ ✗ ✓ |  ✗ ✓ ✗
EgoTV  |  ✓ ✓ ✓ |  ✓ ✗ ✓
Table 1: EgoTV vs. existing video-language datasets. EgoTV benchmark enables
systematic investigation (diagnostics) on compositional, causal (e.g., effect
of actions), and temporal (e.g., action ordering) reasoning in egocentric
settings. Table LABEL:table:list_of_datasets_full in Appendix provides a more
comprehensive comparison.

Vision-Language Benchmarks. Various benchmark tasks have been proposed for
enabling models that can reason across video and language modalities (see
Table 1). Examples include video question answering [clevrer, next_qa_dataset,
agqa_dataset, activity_net_dataset, star_situated_reasoning, tvqa_dataset,
movie_qa, cater_dataset], video-based entailment [violin_dataset], and
embodied task completion [ALFRED20, teach_alexa, behavior_benchmark]. However,
these benchmarks focus on individual specific aspects of multimodal reasoning,
e.g., compositional reasoning (AGQA [agqa_dataset], ActivityNet-QA
[activity_net_dataset], TVQA [tvqa_dataset], and CATER [cater_dataset]) or
causal reasoning (NExT-QA [next_qa_dataset], CoPhy [cophy_dataset], Causal-
VidQA [causal_vid_qa], EgoTaskQA[jia2022egotaskqa], and VIOLIN
[violin_dataset]). In comparison, EgoTV focuses on both causal and
compositional reasoning and further requires visual grounding of both objects
and actions from text, similar to STAR [star_situated_reasoning] and CLEVRER
[clevrer], albeit in egocentric settings. Unlike embodied instruction
following (ALFRED [ALFRED20], TEACh [teach_alexa]), which requires
interpreting grounded task instructions for task execution, EgoTV focuses on
task verification in egocentric videos from instruction-like descriptions.
Akin to NLP _Entailment_ problem [pascal_text_entailment, snli_ve_dataset], it
can also be viewed as a video-based entailment problem – where a given
“premise” (video) is validated by a “hypothesis” (task description).

Vision-Language Models. Vision-Language Models (VLMs) [clip, videoclip,
luo2022clip4clip, blip, coca] pre-trained on large-scale image-text or video-
language narration pairs have demonstrated enhanced performance on certain
compositional [li2020hero] and causal [change_it] tasks. However, they
generally struggle to handle compositionality and order sensitivity [VLMbag-
of-words, winoground]. Instead, NSG explicitly targets order awareness and
compositionality for generalization in task verification using neuro-symbolic
reasoning.

Neuro-symbolic Models. Neuro-symbolic models combine feature extraction
through deep learning with symbolic reasoning [nesy-survey,
star_situated_reasoning] to capture compositional substructures. These models
either reason on static images to recognize object attributes and relations
(NS-CL [nscl], NS-VQA [nsvqa], CLOSURE [closure], and $\nabla-$FOL [del-fol]),
or on videos to recognize spatio-temporal and causal relations (NS-DR
[clevrer] and DCL [dcl]). We extend this to tracking multi-step actions.

##  3 EgoTV Benchmark and Dataset

We present the _Ego centric Task Verification_ (EgoTV) benchmark and dataset.
To enable task tracking and verification for real-world egocentric agents,
EgoTV contains: 1)  _multi-step_ tasks with _ordering constraints_ to capture
the causal and temporal nature of everyday tasks, 2)  _multimodality_ –
language in addition to the egocentric video to allow language-based human-
agent interaction. EgoTV also provides data for a systematic study of
generalization in task verification (see Table 1). To this end, we create the
EgoTV dataset using a photo-realistic simulator AI2-THOR [ai2thor] – as a rich
testbed for future research on generalizable agents for task tracking and
verification. We also provide a reduced study of EgoTV on real-world data
using the CrossTask dataset [cross_task].

###  3.1 Definitions

Benchmark. The objective is to determine if a task described in natural
language has been correctly executed by the agent in a given egocentric video.

Tasks. Each task in EgoTV consists of multiple _partially-ordered sub-tasks_
or steps. A sub-task corresponds to a single object interaction via one of the
six actions:  _heat, clean, slice, cool, place, pick_ , and is parameterized
by a  _target_ object of interaction111Except the _place_ sub-task, which is
additionally parameterized by a receptacle object, we currently limit our
EgoTV dataset to sub-tasks involving only a single target object.. By using
the “actionable” properties of objects in AI2-THOR [ai2thor], we ensure that
the sub-tasks are parameterized with appropriate target objects in EgoTV,
e.g., _heat(book)_ will never occur.

Real-world tasks consist of sub-tasks with ordering constraints, either due to
physical restrictions (e.g., picking up a knife before slicing) or task
semantics (e.g., slicing vegetables before frying). We allow EgoTV tasks to be
partially ordered, with some steps following strict ordering, e.g.  _pick_
sub-task happens before _place_ sub-task, while others are order-independent.
The ordering constraints between sub-tasks are captured in the task
description using specifiers such as _and_ , _then_ , and _before/after_. For
ease of description, we will refer to a task in the paper using
$\left<\text{\emph{sub-task}}\right>\\_\left<\text{\emph{ordering-
specifier}}\right>(object)$ notation, irrespective of the actual task
description. An example task from EgoTV:  _heat_then_clean(apple)_ is shown in
Fig. 1 with its NL description: “apple is heated, then cleaned in a
sinkbasin”. The task consists of two ordered sub-tasks: heat $\rightarrow$
clean on _target_ : apple.

###  3.2 Dataset

As shown in Fig. 1, EgoTV dataset consists of (task description, video) pairs
with positive or negative task verification labels. By combining the six sub-
tasks  _heat, clean, slice, cool, put, pick_ with different ordering
constraints, we create 82 tasks for EgoTV (see Appendix
LABEL:appendix:dataset_analysis_and_statistics for an exhaustive list). Tasks
are instantiated with 130 target objects (excluding visual variations in
shape, texture, and color) and 24 receptacle objects, totaling 1038 task-
object combinations. These are performed in 30 different kitchen scenes. We
also provide comprehensive annotations for each video, including frame-by-
frame breakdowns for sub-tasks, object bounding boxes, and object state
information (e.g., hot, cold, etc.) to facilitate future research.

####  3.2.1 Generation

Task-video Generation. We generate the videos in our dataset by leveraging the
ALFRED setup [ALFRED20]. ALFRED allows us to specify the EgoTV tasks using
Planning Domain Definition Language (PDDL) and then to generate plans for
achieving these tasks using the Metric-FF planner [metric_ff]. We execute
these plans using the AI2-THOR simulator and obtain their corresponding
videos. Further details on encoding tasks using PDDL and planning are in
Appendix LABEL:appendix:etv_taskvideogen.

Task-description Generation. We convert the plans generated for each task into
positive and negative task descriptions using templates. Appendix
LABEL:appendix:task_templates provides details on the process and example
templates.

Figure 2: EgoTV dataset. Sub-tasks and tasks, including their difficulty
measures (Sec: 3.2.2) are shown per split. Novel Scenes have more tasks since
all the train tasks are repeated in unseen scenes. Likewise, complexity and
ordering are higher in Novel Tasks due to the addition of unseen sub-tasks.

####  3.2.2 Evaluation

Metrics. We use accuracy and F1 to measure the efficacy of models on EgoTV
task verification benchmark. To capture the difficulty of tracking and
verifying tasks, we introduce two measures: (1)  _Complexity_ : measuring the
number of sub-tasks in a task, which impacts the video length and requires
higher action and object grounding, and (2)  _Ordering_ : measuring the number
of ordering constraints in a task and measures the difficulty of temporal
reasoning required to track and verify tasks. We evaluate model scalability by
testing on tasks with varying complexity and ordering.

Generalization. Our synthetic dataset facilitates a systematic exploration of
generalization in task tracking and verification via four test splits that
focus on generalization to novel steps, tasks, visual contexts/scenes, and
abstract task descriptions.

  * •

Novel Tasks: Unseen compositions of seen sub-tasks. For e.g., if train set is
{clean(apple), cool(apple)}, then this test split would contain tasks like:
{clean_and_cool(apple), clean_then_cool(apple),  cool_then_clean(apple)}.

  * •

Novel Steps: Unseen compositions of sub-task actions and target objects. For
e.g., if the train set is {clean(apple), cool(egg), clean_and_cool(tomato)},
then this test split would contain tasks like: {clean(egg), cool(apple),
clean_and_cool(apple)}.

  * •

Novel Scenes: This test split contains the same tasks as in the train set.
However, the tasks are executed in unseen kitchen scenes.

  * •

Abstraction: Abstract task descriptions, which lack the low-level details of
the task in the descriptions. For instance, for a heat_and_clean(apple) task,
the full task description in the train set could be “apple is heated in a
microwave and cleaned in sink basin”, while the abstract task description in
this split could be “apple is heated and cleaned”.

Note that all the test splits and the train set are disjoint from each other.
Novel Steps split tests an EgoTV model’s ability to understand generalizable
object affordances and tool usage. For instance, once a model learns the
_slice_ action on an apple, this split tests if the model can apply it to an
orange. On the other hand, the Novel Tasks split tests the generalization of a
model’s causal reasoning capabilities on unseen compositions and orderings of
known sub-tasks.

####  3.2.3 Statistics

EgoTV dataset consists of 7,673 samples (train set: 5,363 and test set:
2,310). The split-wise division is Novel Tasks: $540$, Novel Steps: $350$,
Novel Scenes: $1082$, Abstraction: $338$. The total duration of the egocentric
videos in the EgoTV dataset is 168 hours, with an average video length of 84
seconds. The task descriptions consist of 9 words on average, with a total
vocabulary size of 72. On average, there are 4.6 sub-tasks per task in the
EgoTV dataset, and each sub-task spans approximately 14 frames. Additionally,
there are 2.4 ways to verify a task. Figure 2 shows a comparison of train and
test splits (more analysis in Appendix
LABEL:appendix:dataset_analysis_and_statistics).

Figure 3: NSG model (a) semantic parser converts NL descriptions into a graph
$G$ of symbolic queries; query encoders $f^{\theta_{\tau}}$ detect queries in
individual video segments $s_{t}$; and a video aligner aligns $G$ with video
segments by computing alignment matrix $\mathrm{Z}$ via a constrained
optimization problem (Eq. 3). (b) The constraints (Eqs. 3a 3b 3c) and the
recursive structure (Eq. 4) enabling use of DP to solve for $\mathrm{Z}$.
Here, the blue box denotes $F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t}^{S-1})$,
the green boxes denote $\log
f^{\theta}(a_{j},s_{t})+F^{\ast}((n_{j})_{j+1}^{N-1},(s_{t})_{t+1}^{S-1})$,
and the red box denotes $F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t+1}^{S-1})$.

##  4 Neuro-Symbolic Grounding (NSG)

EgoTV requires visual grounding of task-relevant entities such as actions,
state changes, etc. extracted from NL task descriptions for verifying tasks in
videos. To enable grounding that generalizes to novel compositions of tasks
and actions, we propose the Neuro-symbolic Grounding (NSG) approach. NSG
consists of three modules: a) semantic parser, which converts task-relevant
states from NL task descriptions into symbolic graphs, b) query encoders,
which generate the probability of a node in the symbolic graph being grounded
in a video segment, and c) video aligner, which uses the query encoders to
align these symbolic graphs with videos. NSG thus uses intermediate symbolic
representations between NL task descriptions and corresponding videos to
achieve compositional generalization.

###  4.1 Queries for Symbolic Operations

To encode tasks, NSG captures task-relevant visual and relational information
in a structured manner via symbolic operators called _queries_. For instance,
the task description _heat an apple_ can be symbolically captured by the
query: StateQuery(apple, hot). Similarly, the task description _place steak on
grill_ can be captured by RelationQuery(steak, grill, on), which represents
the relation (on) between objects steak and grill. Queries are characterized
by types and arguments and are stored in a text format. Table
LABEL:table:QTypes in the appendix shows the various query types and their
arguments. Different query types capture different aspects, e.g., attributes,
relations, etc., thereby enabling a rich symbolic representation of everyday
tasks.

###  4.2 Semantic Parser for Task Descriptions

The symbolic operators, i.e., queries, allow the semantic parser to represent
a task’s partial-ordered steps using a symbolic graph. Specifically, the
parser translates an NL task description into a graph $G(V,E)$, where a vertex
$n_{i}\in V$ represents a query and an edge $e_{ij}:n_{i}\rightarrow n_{j}\in
E$ is an ordering constraint indicating that $n_{i}$ must precede $n_{j}$
(Figure 3a). We experiment with two different methods to parse language
descriptions of tasks to graphs – (i) finetuning language models and (ii) few-
shot prompting of language models. Appendix
LABEL:section:appendix_semantic_parsing describes these approaches in detail.
We perform a topological sort with the graph $G$ and generate all the possible
sequences of queries consistent with the sort. For example, the topological
sorting of the graph in Figure 3(a) yields two ordered sequences:
$(n_{0},n_{1},n_{2},n_{3})$, $(n_{0},n_{2},n_{1},n_{3})$. Note that this does
not include all physically possible ways to complete a task, but a super-set
of all possible sequences of task-relevant queries, including some infeasible
sequences222For instance, in Figure 3a, $n_{1}$ and $n_{2}$ are at the same
topological level, but the sub-task in query $n_{1}$ could invalidate pre-
conditions for $n_{2}$. Hence, a physically plausible task requires $n_{2}$
followed by $n_{1}$ and not vice versa. Note that EgoTV does not have
physically implausible tasks.. However, having this super-set is useful
because a task can be verified as accomplished if any sequence in this set can
be ascertained to occur in the video.

###  4.3 Query Encoders for Grounding

Query Encoders are neural network modules that evaluate whether a query is
satisfied in an input video. Specifically, a query encoder $f^{\theta_{\tau}}$
for a query $n$ of type $\tau$ (e.g., StateQuery, RelationQuery etc.), accepts
NL arguments ($a$) corresponding to objects and relations in $n$ and a video
($v$) to generate the probability $\mathds{P}=f^{\theta_{\tau}}(a,v)$ of the
desired query being true in the video. Learnable parameters corresponding to
different query type encoders in an NSG model are jointly represented as
$\theta=\bigcup_{\tau}\theta_{\tau}$.

Both the text arguments $a$ of the query and the frames of the input video $v$
are encoded using a pre-trained CLIP encoder [clip]. The token-level and
frame-level representations from CLIP are separately aggregated using two
LSTMs [lstm] to obtain aggregated features for $a$ and $v$, respectively.
These features are then fused and passed through the neural network
$f^{\theta_{\tau}}$ to obtain the probability $\mathds{P}$ of the query being
true in the video (see Figure 3a).

###  4.4 Video Aligner for Task Verification

This module of NSG must align the graph representation $G$ of the task
(generated by the semantic parser) with the video. To that end, it first
segments the video, then jointly learns a) the query encoders, which detect
the queries in the video segments and b) the alignment between video segments
and the query sequences obtained from the topological sort on $G$. Such joint
learning is required since the temporal locations of the queries in the video
are unknown a priori requiring simultaneous detection and alignment. If the
video is a positive match for the task encoded in $G$, at least one of the
query sequences from $G$ must temporally align perfectly with the video
segments for successful task verification. Conversely, for negative matches,
no query sequence from $G$ would _completely_ align with the video segments.
Going forward, we use $\langle\rangle$ and $()$ to denote ordered pairs and
sequences, respectively.

Video Segmentation: The video is segmented into non-overlapping
segments333Since pretrained, off-the-shelf video segmentation models are
limited to predefined action classes [escorcia2016daps] or reliant on
background frame change detection [yang2022temporal] and require downstream
finetuning [gao2020accurate], we leave their integration in NSG as future
work. with a moving window of arbitrary but fixed size $k$444If required, the
last segment is zero-padded to $k$ frames.

Joint Optimization: The objective of the optimization is to jointly learn the
_alignment_ $\mathrm{Z}$ between queries and video segments along with the
_query encoders_ $f^{\theta}$. Given: a) the temporal sequence of $S$ segments
$(s_{t})_{t=0}^{S-1}$ with each $s_{t}$ spanning $k$ image frames; and b) a
sequence of $N$ queries $(n_{j})_{j=0}^{N-1}$ from the topological sort on
$G$, the alignment $\mathrm{Z}$ is defined as a matrix
$\mathrm{Z}\in\\{0,1\\}^{N\times S}$, where $Z_{jt}=1$ implies that the
$j^{th}$ query $n_{j}$ is aligned the video segment $s_{t}$. An example
alignment with $N=2$ and $S=3$ is given by the matrix
$\mathrm{Z}=\left[\begin{array}[]{ccc}1&0&0\\\ 0&0&1\end{array}\right]$, where
the rows are ordered queries $(n_{0},n_{1})$, the columns are temporal
segments $(s_{0},s_{1},s_{2})$, and $\langle n_{0},s_{0}\rangle$, $\langle
n_{1},s_{2}\rangle$ are the aligned pairs. Assuming segmentation guarantees
sufficient segments for query alignment: $S\geq N$. Using $\mathrm{Z}$ and
$f^{\theta}$, the task verification probability $p^{\theta}$ can be defined
as:

$\displaystyle
p^{\theta}=\sigma\bigg{(}\max_{\mathrm{Z}\in{\\{0,1\\}}^{N\times
S}}\frac{1}{N}\sum_{j,t}\log f^{\theta}(a_{j},s_{t})Z_{jt}\bigg{)}$ (1)

Here $\sigma$ is the sigmoid function, $f^{\theta}(a_{j},s_{t})$ denotes the
probability of querying segment $s_{t}$ using query $n_{j}$ with arguments
$a_{j}$ (Sec. 4.3), and $\max$ operator is over the best alignment
$\mathrm{Z}$ between $N$ queries and $S$ segments. We use the ground-truth
task verification label $y$ to compute $\mathrm{Z}$ and $f^{\theta}$ by
minimizing the following loss:

$\displaystyle\min_{\theta}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum\mathcal{L}_{\text{BCE}}(p^{\theta},y),$
(2)

here $|\mathcal{D}|$ is the EgoTV dataset size and
$\mathcal{L}_{\text{BCE}}(\cdot)$ is the binary cross entropy loss computed
over $|\mathcal{D}|$ input, output pairs. Given the minimax nature of Eq. 2,
we use a 2-step iterative optimization process: (i) find the best alignment
$\mathrm{Z}$ between queries and segments with fixed query encoder parameters
$\theta$ (optimize Eq. 1 with fixed $f^{\theta}$); (ii) optimize $\theta$
using Eq. 2, given $\mathrm{Z}$.

Dynamic Programming (DP)-based Alignment: Finding the best $\mathrm{Z}$ in Eq.
1 given $\theta$ requires iterating over combinations of $N$ queries and $S$
segments while respecting certain constraints. The constraints, visualized in
Fig. 3b, ensure that a) no two queries are aligned to the same segment555This
ensures that the order of queries can be verified, which cannot be done when
queries belong to the same segment. (Eq. 3a), b) all queries are accounted for
in $S$ (Eq. 3b), and c) the temporal orderings between queries in the query
sequences are respected (Eq. 3c). Specifically, if query $n_{u}$ precedes
$n_{v}$ ($n_{u}\rightarrow n_{v}$), and query $n_{v}$ is paired with segment
$s_{\bar{t}}$ (i.e. $Z_{v\bar{t}}=1$), then query $n_{u}$ cannot be paired
with any segment that lies after $s_{\bar{t}}$ (i.e. $Z_{ut}\neq
1\;\forall\;t\geq\bar{t}$). The resulting optimization problem for
$\mathrm{Z}$, given $\theta$ is:

$\displaystyle\max_{\mathrm{Z}\in{\\{0,1\\}}^{N\times S}}\sum_{j,t}\log
f^{\theta}(a_{j},s_{t})Z_{jt},\quad\text{s.t.}$ (3)
$\displaystyle\sum_{j=0}^{N-1}Z_{jt}\in\\{0,1\\},\quad\forall\;0\leq t\leq
S-1$ (3a) $\displaystyle\sum_{t=0}^{S-1}Z_{jt}=1,\quad\forall\;0\leq j\leq
N-1$ (3b) $\displaystyle n_{u}\rightarrow
n_{v},\;Z_{v\bar{t}}=1\Longrightarrow Z_{ut}\neq 1,\quad\forall\;t\geq\bar{t}$
(3c)

Intuitively, the solution to Eq. 3 gives us the best alignment score (note,
the overlap with Eq. 1). The iterations over $N$ queries and $S$ segments for
solving Eq. 3 are underpinned by an overlapping and optimal substructure. For
instance, to optimally align queries $(n_{j})_{j=0}^{N-1}$ and segments
$(s_{t})_{t=0}^{S-1}$, one could: a) pair $\langle n_{0},s_{0}\rangle$ and
optimally align the remaining queries and segments
$(n_{j})_{j=1}^{N-1},(s_{t})_{t=1}^{S-1}$; or (2) skip $s_{0}$ and still
optimally align _all_ queries, now with the remaining segments
$(n_{j})_{j=0}^{N-1},(s_{t})_{t=1}^{S-1}$ (see Fig. 3b(iv)). This recursive
substructure leads to a DP solution for Eq. 3.

Let, $F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t}^{S-1})$ denote the best alignment
score for queries $(n_{j})_{j}^{N-1}$ and segments $(s_{t})_{t}^{S-1}$ from
Eq. 3. Based on the aforementioned reasoning,
$F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t}^{S-1})$ can be recursively written as:

$F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t}^{S-1})=\text{max}\big{(}\log
f^{\theta}(a_{j},s_{t})\\\
+F^{\ast}((n_{j})_{j+1}^{N-1},(s_{t})_{t+1}^{S-1}),F^{\ast}((n_{j})_{j}^{N-1},(s_{t})_{t+1}^{S-1})\big{)}$
(4)

The base cases for the DP are: (i) $\mathrm{Z}=\mathds{I}\;\text{if}\;N=S$;
(ii) $Z_{jt}=1\;\forall\;t\;\text{if}\;j=N-1$. It is worth noting that the DP
subproblems, together with the base cases, satisfy the constraints in Eq. 3a
3b 3c. Since the video may match any of the sequence in the super-set of query
sequences (from the topological sort on $G$), we repeat this process of
computing $F^{\ast}$ for each sequence and select the maximum value.

Optimizing Query Encoder Parameters $\theta$: After obtaining the best
alignment $\mathrm{Z}$ using DP, we substitute the corresponding value of
$F^{\ast}((n_{j})_{j=0}^{N-1},(s_{t})_{t=0}^{S-1})$ in Eq. 1 and subsequently
Eq. 2. In Eq. 2, we use single mini-batch of training examples and take one
gradient-update step of the Adam optimizer for the query encoder parameters
$\theta$.