# Optimal allocation of finite sampling capacity in accumulator models of
multi-alternative decision making

Jorge Ramírez-Ruiz  Center for Brain and Cognition, and Department of
Information and Communication Technologies, Universitat Pompeu Fabra,
Barcelona, Spain  Rubén Moreno-Bote  Center for Brain and Cognition, and
Department of Information and Communication Technologies, Universitat Pompeu
Fabra, Barcelona, Spain  Serra Húnter Fellow Programme, Universitat Pompeu
Fabra, Barcelona, Spain

## Abstract

When facing many options, we narrow down our focus to very few of them.
Although behaviors like this can be a sign of heuristics, they can actually be
optimal under limited cognitive resources. Here we study the problem of how to
optimally allocate limited sampling time to multiple options, modelled as
accumulators of noisy evidence, to determine the most profitable one. We show
that the effective sampling capacity of an agent increases with both available
time and the discriminability of the options, and optimal policies undergo a
sharp transition as a function of it. For small capacity, it is best to
allocate time evenly to exactly five options and to ignore all the others,
regardless of the prior distribution of rewards. For large capacities, the
optimal number of sampled accumulators grows sub-linearly, closely following a
power law for a wide variety of priors. We find that allocating equal times to
the sampled accumulators is better than using uneven time allocations. Our
work highlights that multi-alternative decisions are endowed with breadth-
depth tradeoffs, demonstrates how their optimal solutions depend on the amount
of limited resources and the variability of the environment, and shows that
narrowing down to a handful of options is always optimal for small capacities.

##  1 Introduction

The problem of allocating finite resources to determine the best of several
options is common in decision making, from deciding which vaccine candidates
to fund for further research to choosing a movie for Saturday night. In these
cases, planning, and thus resource allocation, needs to be made in advance,
well before feedback about the success of the choice is observed.
Consequently, two important questions arise: How many options should we
examine? And, for how long? When resources are limited, such as number of
participants or weekend free time, a decision maker should balance breadth,
how many options to sample, and depth, how much to sample each. This
ubiquitous decision making problem under constrained resources is what has
been called the breadth-depth (BD) dilemma [1, 2, 3].

In the face of many alternatives, humans quickly narrow down the number of
considered options to around two to five [4, 5, 6, 7, 8], and, when presented
with more than 6 options, experienced overload produces suboptimal choices in
certain conditions [9, 10]. Models describe this behavior by assuming that
considering more options incurs search or mental costs [8, 11, 12], but why
people consider small sets in a wide range of environments is still a matter
of debate. While this could be explained by strict small capacity limits in
attention or working memory [13, 14], the nature of this small capacity would
still need to be addressed [15]. Another possibility is that capacity is not
necessarily small, but rather that sampling few options and ignoring the vast
majority is actually an optimal policy that favors depth over breadth [3].
This possibility is supported by the fact that neuronal resources devoted to
decision making are not precisely low, as dozens of brain areas and several
billions of neurons are involved in even simple decision making tasks [16, 17,
18, 19]. Thus, processing bottlenecks could be reflections of close-to-optimal
policies.

Bounded rationality accounts [20, 21, 22, 23] surmise that many features of
cognition arise from the finite limits of the nervous system. This must also
be the case for the nature of the policies chosen by people in decision
making, but oftentimes the constraints imposed by the limited resources are
not made explicit. Indeed, choices between two or three options have been
typically modelled as optimal stopping problems [24, 25, 26, 27, 28, 29, 30],
where agents should optimally balance the prospect of learning the value of
the options with the costs of sampling them, but they do so without
computational or capacity constraints. The effect of resource limitations on
decision making might not be important when there are only two or three
available options, but it might be critical when going beyond those low
numbers. In that case, the allocation of resources might be governed by two-
stage processes [8, 11, 31, 32], instead of purely sequential processes, where
the first decision is about the subset of options that will be considered for
further processing.

Here we study whether narrowing attention to a few options results from
optimally allocating finite resources. To this end, we consider an infinitely
divisible sampling resource (e.g. time), such that there are no bounds in the
number of alternatives that can be considered. In our model, an agent can
first allocate finite sampling time over an arbitrarily large number of
options, modelled as accumulators of noisy evidence, with the only restriction
that the total sampling time is fixed. Accumulation of evidence runs in
parallel and independently for each accumulator, and only their final states
are observed. Based on the observations, the agent picks up the one with the
highest expected drift rate, which defines the utility of the choice. The goal
of the agent is to optimize the allocation of sampling time such that expected
utility is maximized. We identify a critical variable in the problem, that we
simply call _capacity_ , that increases with the actual size of the resources
of the agent as well as with the discriminability between options, and we find
that this capacity separates two distinct regimes of optimal allocation. When
sampling capacity is small, the optimal policy is to sample exactly five
options, regardless of the prior. In contrast, when capacity is large, the
number of options to sample grows with capacity in a sub-linear fashion that
depends on the prior. We find a duality between allocated time and allocated
precision to the options, such that all our results generalize to allocating
precision while keeping fixed sampling time. Finally, we show that even
allocations are optimal, and thus better than more complex asymmetric time
allocations over the considered options. Overall, our results suggest that
decisional bottlenecks can be a byproduct of optimal policies in the face of
uncertainty.

##  2 Results

### Multi-accumulator model

We consider an environment that generates many options ($N\gg 1$) from which
to choose (Fig. 1, top), each one characterized by a ‘drift’ parameter
$\mu_{i}$ ($i=1,\ldots,N$), unknown to the agent. All drifts $\mu_{i}$ are
drawn identically and independently from a prior probability distribution
$p_{\theta}(\mu)$, known to the agent and assumed to have finite mean and
variance.

The agent learns about the options, in order to choose between them, by
allocating sampling time $t_{i}$ to each (Fig. 1, bottom). The critical aspect
of our model is that sampling times $t_{i}\geq 0$ need to be allocated before
feedback about the drifts is received, and with the constraint that the total
sampling time equals a finite available time $T$,

$\sum_{i=1}^{N}t_{i}=T.$ (1)

In practice, the agent needs to decide on the number of options $M\leq N$ to
be sampled and their corresponding sampling times $t_{i}>0$ for $i\leq M$,
while the remaining options $i>M$ are ignored by giving them no sampling time,
$t_{i}=0$. The ordering of the options is irrelevant, as they are initially
indistinguishable, and thus we take the first $M$ as those that are sampled.
We assume that non-sampled options cannot be chosen, although a ‘default’
option can be added to our framework with no change of our main results.

Once total sampling time is allocated, noisy evidence about the drift
$\mu_{i}$ of each of the sampled options $i\leq M$ is integrated by
independent accumulators (Fig. 1, middle) according to the drift-diffusion
process

$\frac{dx_{i}(t)}{dt}=\mu_{i}+\eta_{i}\left(t\right),$ (2)

where $x_{i}(t)$ is the accumulated evidence up to time $t$ with initial
condition $x_{i}(0)=0$, and $\eta_{i}\left(t\right)$ is a Gaussian white noise
with zero mean and fixed variance $\sigma^{2}$, independent and identical for
all the accumulators.

Figure 1: A multi-accumulator model with finite sampling resources. The
environment produces a large number of options, each characterized by a drift
$\mu_{i}$, unknown to the agent and drawn from a prior distribution
characterized by hyperparameters $\theta$, which is known to the agent. The
agent has a finite resource $T$, that they divide and allocate across options,
$\sum_{i}t_{i}=T$, in order to sample them. In practice, the agent allocates
finite sampling time to a finite number $M$ of accumulators to infer their
unknown drifts. After allocation, evidence (red lines) is optimally integrated
by the accumulators. The agent observes the integrated evidence $x_{i}$ at the
allocated time $t_{i}$, infers the drifts for each of the accumulators and
chooses the one that is deemed to have the highest drift (in this case,
$\mu_{M}$; green box).

The result of the accumulation is the total evidence $x_{i}$ at time $t_{i}$,
both of which are observed by the agent and constitute the sufficient
statistics for the unknown drift $\mu_{i}$ [33]. With these observations, the
agent builds the posterior distribution of the drifts by using Bayes rule as

$p(\mu_{i}|x_{i},t_{i},\sigma,\theta)=\frac{\mathcal{L}(\mu_{i}|x_{i},t_{i},\sigma)p_{\theta}(\mu)}{p(x_{i}|t_{i},\sigma,\theta)},\vspace{5pt}$
(3)

where
$\mathcal{L}(\mu_{i}|x_{i},t_{i},\sigma)=\mathcal{N}(x_{i}|\mu_{i}t_{i},\sigma^{2}t_{i})$
is the likelihood function for the drift, $p_{\theta}(\mu)$ is the prior
distribution and
$p(x_{i}|t_{i},\sigma,\theta)=\int\differential{\mu}\mathcal{N}(x_{i}|\mu
t_{i},\sigma^{2}t_{i})p_{\theta}(\mu)$ is the marginal distribution of the
evidence, which serves as a normalization constant. The posterior mean of the
drift becomes
$\hat{\mu}_{i}\equiv\hat{\mu}_{i}\left(x_{i},t_{i},\sigma,\theta\right)\equiv\int\differential{\mu}\mu\,p(\mu|x_{i},t_{i},\sigma,\theta)$,
which is finally used by the agent to choose the option with the highest
inferred drift (Fig. 1, middle, green box), to optimize utility,
$U\left(M,\mathbf{x},\mathbf{t},\sigma,\theta\right)=\max_{i\leq
M}\hat{\mu}_{i}\left(x_{i},t_{i},\sigma,\theta\right)$, where
$\mathbf{x}=(x_{1},...,x_{M})$ is the vector of observations for the $M$
accumulators with allocated times $\mathbf{t}=(t_{1},...,t_{M})$. To avoid
notation clutter, from now on we will stop writing the dependence on $\sigma$
and $\theta$ of the various functions and leave it implicit.

The last expression is the utility of the choice of accumulator, which depends
on the observations and allocation times. However, before time is allocated,
the observations $\mathbf{x}$ themselves will be unknown to the agent.
Therefore, the expected utility of a given allocation $\mathbf{t}$ is given by
taking the expectation of the above utility over all possible observations as

$\hat{U}(M,\mathbf{t})\equiv\mathbb{E}\left[\max_{i\leq
M}\hat{\mu}_{i}|\mathbf{t}\right]=\int\differential{x_{1}}...\differential{x_{M}}p(x_{1},...,x_{M}|\mathbf{t})\max_{i}\hat{\mu}_{i}\left(x_{i},t_{i}\right),$
(4)

where, using the independence of the accumulators,
$p(x_{1},...,x_{M}|\mathbf{t})=\prod_{k\leq M}p(x_{k}|t_{k})$ is the product
of the marginal distribution of the evidences.

Optimally inferring the drifts from observations is readily accessible through
Bayesian inference as shown above. Thus, the main, and harder, objective of
the agent is to optimize the allocation policy, i.e. to select both the number
of sampled accumulators $M\leq N$ and the time $t_{i}$ allocated to each, in
order to maximize expected reward, while satisfying the total sampling time
constraint in Eq. (1). This is accomplished by optimizing the utility with
respect to $M$ and $\mathbf{t}=(t_{1},...,t_{M})$ as

$(M^{*},\mathbf{t}^{*})=\arg\max_{M,\;\mathbf{t}}\hat{U}(M,\mathbf{t}).$ (5)

### Capacity and time-precision duality

While time is the resource that the agent allocates, we found a dimensionless
scale that expresses their actual sampling capacity, i.e. their ability to
sample and differentiate between drifts, which we call capacity $C$ (Fig. 2).
As the agent integrates noisy evidence through Eq. (2), the likelihood of the
drift $\mu_{i}$ for accumulator $i$ is proportional to a Gaussian (Fig. 2a,
orange curve) with mean $x_{i}/t_{i}$ and variance $\sigma^{2}/t_{i}$,
$\mathcal{L}(\mu_{i}|x_{i},t_{i},\sigma)\propto\mathcal{N}(\mu_{i}|\frac{x_{i}}{t_{i}}\frac{\sigma^{2}}{t_{i}})$
[33]. Its variance $\sigma^{2}/t_{i}$ shows how the sampling time and the
variance of the sampling noise are related when inferring the drift $\mu_{i}$,
since the Gaussian gets broader with increasing $\sigma$ or decreasing time
$t_{i}$. In fact, the sampling capacity of the agent should capture this
duality. Thus, having a fixed capacity could be interpreted as having a fixed
noise variance $\sigma^{2}$ for all accumulators and allocating time $T$
between them (Fig. 2b, left) or as having a fixed sampling time $T$ for each
of the accumulators and allocating precision $1/\sigma^{2}$ between them (Fig.
2b, right).

Figure 2: Time/precision duality and the notion of capacity. (a) The
likelihood of the drift $\mu$ (in orange) given the evidence has variance
$\sigma^{2}/t_{i}$ and the prior distribution of the drifts (in cyan) has
variance $\sigma_{0}^{2}$. These quantities determine capacity as in Eq. (6).
(b) Time and sampling noise are intricately related (see text). In this
example, allocating time $T/3$ to each accumulator under fixed precision
$1/\sigma^{2}$ (left) is equivalent to allocating precision $1/3\sigma^{2}$ to
each accumulator under fixed sampling time $T$ (right). (c) Small capacity
means that the variance of the observation is much larger than the variance of
the prior, indicating that it is difficult to confidently identify the best
drift from the observations. (d) In the large capacity limit, it is easier to
differentiate the good drifts from the poor ones.

Moreover, the posterior in Eq. (3) depends on the prior as well (Fig. 2a, cyan
curve). For fixed evidence, the broader the prior is, the easier it is to
differentiate between sampled drifts, since the expected squared distance
between two drifts drawn from the same distribution is twice its variance
${\rm Var}[p_{\theta}(\mu)]$. Therefore, we define the capacity allocated to
option $i$ as the ratio between the precision of the observation and the
precision of the prior,

$c_{i}=\frac{{\rm Var}[p_{\theta}(\mu)]}{{\rm
Var}[\mathcal{N}(\mu_{i}|\frac{x_{i}}{t_{i}},\frac{\sigma^{2}}{t_{i}})]}=\frac{\sigma_{0}^{2}}{\sigma^{2}}t_{i}.$
(6)

Adding the individual capacities results in the total sampling capacity of the
agent,

$C=\sum_{i}c_{i}=\frac{\sigma_{0}^{2}}{\sigma^{2}}T.$ (7)

For the rest of this article, we stick to the interpretation of allocating
capacity as dividing the total time $T$ while fixing the accumulation noise
$\sigma$, such that the variable we can control is the sampling time allocated
to each option, keeping in mind that all the results presented below can be
readily reinterpreted as dividing precision while giving to all options the
same sampling time.

### Even sampling

Optimally dividing sampling capacity $C$ into options is an a priori hard
problem due to its high dimensionality. However, we show in a section below
through numerical simulations and for Gaussian priors that the optimal
allocation lies within the family of even allocations, where $M$ options
receive equal sampling time $t_{i}=t\equiv T/M$, while the remaining others
are given no time. Thus, finding the optimal policy reduces to finding the
optimal number $M$ of accumulators to sample.

In this section, we exploit the structure of even sampling. First, the
posterior mean of the drift $\hat{\mu}_{i}(x_{i},t)$, computed from Eq. (3),
is a monotonously increasing function of the evidence $x_{i}$ for any prior
(see proof in Sec. 4.1 of the Methods). Therefore, the option that maximizes
the posterior mean $\hat{\mu}_{i}$ is the one that has the highest evidence
$x_{i}(t)$, as all $M$ sampled options are given the same sampling time $t$.
This allows us to work by maximizing evidence instead of maximizing the
posterior means of the drifts in Eq. (4). Secondly, by changing variables
$y\equiv\max_{i}x_{i}$, and using the probability distribution of the maximum
$y$, denoted $p_{{\rm max}}(y|t,\sigma,\theta)$, the expected utility in Eq.
(4) can be recast in the one-dimensional integral

$\hat{U}(M,t)=\int\differential{y}\,p_{{\rm max}}(y|t)\hat{\mu}(y,t).$

Finally, given that the $M$ options are sampled evenly, the probability
distribution of the maximum can be simplified by using the cumulative
distribution of the evidence $x$ for an arbitrary accumulator,
$F_{x}(y|t)=\int_{-\infty}^{y}\differential{x^{\prime}}p(x^{\prime}|t)$, where
$p(x|t)$ is the marginal of the evidence $x$ of the accumulator, as

$p_{\rm max}(y|t)=\derivative{y}\left[F_{x}(y|t)\right]^{M}.$ (8)

With all the above, the expected utility in Eq. (4) can thus be written as

$\hat{U}(M,t)=M\int\differential{y}\,\left[F_{x}(y|t)\right]^{M-1}p(y|t)\,\hat{\mu}(y,t).$
(9)

When the prior distribution is a Gaussian with mean $\mu_{0}$ and variance
$\sigma_{0}^{2}$, it is possible to identify the total capacity
$C=\frac{\sigma_{0}^{2}}{\sigma^{2}}T$ explicitly and Eq. (9) simplifies to

$\hat{U}(M,C)=\mu_{0}+\frac{M\sigma_{0}}{\sqrt{1+\frac{M}{C}}}\int_{-\infty}^{\infty}\differential{y}\left[\Phi(y)\right]^{M-1}\mathcal{N}(y|0,1)\,y,$
(10)

where $\Phi(y)=\frac{1}{2}\left[1+\erf\left(\frac{y}{\sqrt{2}}\right)\right]$
is the cumulative distribution function of a normal distribution.

Plotting the utility in Eq. (10) as a function of the number of sampled
accumulators $M$ reveals a clear breadth-depth tradeoff (Fig. 3). At the depth
limit, $M=1$, only one accumulator is sampled and it is given all sampling
time $T$. In this case, the expected utility will simply be the expected value
of the prior, $\mu_{0}$ (Fig. 3, left point), since there is no choice to be
made between accumulators. At the breadth extreme, $M/C\rightarrow\infty$, the
evidence gathered for each accumulator is very noisy because each has been
allocated a very short sampling time, and thus choosing any will amount to an
expected utility again equal to the prior mean (rightmost points). Therefore,
for all capacities, there is an intermediate optimal value for the number of
accumulators to sample, $M^{*}$.

Figure 3:  Expected utility as a function of sampled accumulators exhibits the
breadth-depth tradeoff. Results for the Gaussian prior case
($\mu_{0}=0.5,\sigma_{0}^{2}=1$), for three different capacities. Blue points
denote the maxima. Note log horizontal scale (points, Monte Carlo simulations;
lines, theoretical predictions, Eq. 10).

### Sharp transition between the small and large capacity regimes

Our main result is that the optimal allocation policies are qualitatively
different at small and large capacity, and that there is a abrupt transition
between the two regimes. We provide useful asymptotic analytical expressions
for the utility in Eq. (9) and the optimal $M^{*}$ in both limits and describe
their characteristic features.

The limit $C\ll 1$ corresponds to the case where the uncertainty in the
observation $\sigma^{2}/T$ is much larger than the variance of the prior
$\sigma_{0}^{2}$, i.e. the Gaussian likelihood is much wider than the prior
(Fig. 2c). In this limit, we find that the utility in Eq. (9) can be expanded
a series in powers of $\sqrt{C}$, which at first order is given by (see Sec.
4.2)

$\hat{U}(M,C)=\mu_{0}+\sigma_{0}\sqrt{\frac{C}{2\pi}}\left[\sqrt{M}\int_{-\infty}^{\infty}\differential{z}z\exp(-\frac{z^{2}}{2})\left(\frac{1}{2}+\frac{1}{2}\erf\left(\frac{z}{\sqrt{2}}\right)\right)^{M-1}\right]+\mathcal{O}(C).$
(11)

Remarkably, this expression holds for any prior distribution as long as
capacity is small enough. Using Extreme Value Theory (see Sec. 4.4) and noting
that the only depencence of $M$ is in the quantity in the square brackets, we
find that utility decreases with $M$ for large $M$. On the other hand, it is
easy to see that expected utility attains its lowest value when $M=1$. Thus,
as utility is positive, the optimal $M$ should be attained at some
intermediate value. We find numerically that the optimum happens when

$M^{*}(C\ll 1)=5.$

In summary, at small capacity the optimal number of sampled accumulators is
constant and equal to five, regardless of the prior and the value of capacity.
We have confirmed this strong prediction by direct numerical integration of
Eq. (9) using different prior distributions, including Gaussian, uniform and
bimodal (Fig. 4), which also holds even when a non-sampled, default, option
can be chosen (diamond markers).

Figure 4:  The optimal number of sampled accumulators undergoes qualitatively
different behaviors at small and large capacity values. Results come from
searching the maximum expected utility via Monte Carlo simulations (points)
and numerical integration (lines) for a Gaussian (Eq. 10), uniform (Eq. 20)
and a bimodal (Eq. 21) priors (illustrated in inset). In addition, diamond
markers indicate simulations with a ‘default’ option. We used $\mu_{0}=0.5$
for all priors and $\sigma_{0}^{2}=1/12$ for the Gaussian prior to match the
uniform distribution. For the bimodal prior, the variance of each mode equals
$\sigma_{0}^{2}$. Dashed red line corresponds to the asymptotic limit in the
Gaussian prior case, Eq. (13). Dashed gray line is the best power law fit for
the uniform prior case.

The opposite limit $C\gg 1$ corresponds to the case where the precision of the
observation is much greater than the one of the prior (Fig. 2d). Intuitively,
this means that the quality of the observations is good enough to likely
differentiate the drifts between two randomly chosen accumulators, and thus we
expect that the optimal number of accumulators to increase with increasing
capacity, giving a qualitatively different behaviour than the small capacity
limit. To study this limit, we assume that the optimal number of sampled
options $M^{*}$ increases with $C$, an assumption that is consistent with the
results shown below, and thus we study the behaviour of Eq. (9) for large $M$.
In this limit, we can find an analytical expression for the expected utility
in Eq. (10), when the prior distribution is Gaussian,

$\hat{U}(M,C)\rightarrow\mu_{0}+\sigma_{0}\frac{b_{M}}{\sqrt{1+\frac{M}{C}}},$
(12)

where $b_{M}=\left(2\log(M)-\log(\log(M))-\log(4\pi)\right)^{1/2}$ (see Sec.
4.4). By relaxing $M$ to be continuous, we can maximize expected utility, and
we find that the optimal number of sampled options for large capacity
satisfies, up to leading order, the implicit equation $M^{*}\log(M^{*})=C$.
After inverting it, the optimal number of sampled options is

$M^{*}(C\gg 1)=\frac{C}{W(C)},$ (13)

where $W(C)$ is the Lambert function. This asymptotic limit provides a very
good approximation to the optimal $M^{*}$ at large $C$ obtained from direct
numerical integration of Eq. (10) (Fig. 4; red dashed line, theory; blue
points, simulations). For prior distributions other than the Gaussian, we rely
on numerical integration of Eq. (9) (see Secs. 4.5 and 4.6 for analytical
expressions). For a uniform prior, the optimal number of sampled options
increases as a power law with an exponent close to $1/3$ (Fig. 4, pink), while
for a bimodal prior the optimal number increases in a similar fashion to the
Gaussian prior case (green). While differences of asymptotic limits are due to
the presence of bounded or unbounded drifts in the priors, in all cases the
increase is sub-linear, indicating that increasingly longer times are
allocated to each of the sampled accumulators as capacity increases.

The above results show that there are two distinct regimes, one at small and
another at large capacities, characterized by qualitatively different optimal
allocations: while at small capacity the optimal number of sampled options
should be five regardless of the prior, at large capacity the optimal number
of sampled options grows sublinearly regardless of the tested prior. Further,
we observe that there is an abrupt transition between the two regimes as
capacity grows, with a bump being observed at intermediate capacity values.

### Even allocation is optimal

Above we have assumed that we could find the optimal time allocation within
the subset of even allocations, such that, given finite total time $T$, an
agent just needs to determine how many options will be sampled and split equal
time to all of them. Conveniently, this set is discrete and thus amenable to
effective search of the optimum. However, in general, the set of allocation
policies is the infinite-dimensional simplex $\sum_{i}t_{i}=T$, $t_{i}\geq 0$
for all $i$, as a priori the agent could unevenly split time to options in any
arbitrary way. Despite its infinite-dimensionality, we have seen in the case
of even sampling that it is optimal to ignore (infinitely) many options, such
that $t_{i}>0$ only for $i\in\\{1,...,M\\}$, with finite $M$, and then we say
that there are $M$ active dimensions.

To address the most general case, using the above intuitions we first
generalize the expected utility, Eq. (9), to the case when allocated time is
unevenly distributed among $M$ accumulators, as

$\hat{U}(M,\mathbf{t})=\int_{-\infty}^{\infty}\differential{y}\derivative{y}\left[\prod_{i=1}^{M}F_{x}(y|t_{i})\right]\hat{\mu}(y,t_{i}),$
(14)

where $F_{x}(y|t_{i})$ is the cumulative distribution function of the
posterior when using $t_{i}$ sampling time. Our goal is then, for every $M$,
to find the allocation $\mathbf{t}$ that maximizes Eq. (14) under the capacity
equality constraint and the inequalities $t_{i}\geq 0$ for all $i$, and then
select the optimal $M$, the one that achieves the highest utility.

Figure 5: Even allocations correspond to critical points of utility lying at
the center of $M$-simplices. (a) In one dimension, there is only one point
that complies with the constraint. (b) For $M=2$ dimensions, constraints
define a line segment or 1-simplex. The circle depicts the symmetric critical
point $\mathbf{t}_{2}^{e}$. (c) For $M=3$, constraints form a triangle or
2-simplex. The black triangle is the symmetric critical point
$\mathbf{t}_{3}^{e}$. The colors at the extremes reflect the minimum and
maximum utility reached in this simplex, which was computed with Monte Carlo
simulations of Eq. (4) for the Gaussian prior with $T=0.1$, $\sigma=1$,
$\sigma_{0}=1$, $\mu_{0}=0.5$. (d) Expected utility computed along directions
that go orthogonally from $\mathbf{t}_{M}^{e}$ to $\mathbf{t}_{M+1}^{e}$ (as
illustrated with orange arrows in panel c, same parameters). The red dot shows
the maximum occurring at $\mathbf{t}_{5}^{e}$. (e) Using the stochastic
projected gradient ascent detailed in Sec. 4.7, we initialized the algorithm
at random points (ten shown here) in a high-dimensional simplex and measured
the coefficient of variation (CV) of the allocation vector at every step of
the algorithm until convergence, for various values of capacity. Zero CV
implies even allocation.

In this more general setup, an even allocation corresponds to the symmetrical
point in $M$ active dimensions given by $\mathbf{t}^{e}_{M}$, where
$t^{e}_{M,i}=T/M$ for $i=1,...,M$ (superscript reflects ‘even’ allocation). As
the expected utility in Eq. (14) is symmetric under any permutation
$t_{j}\leftrightarrow t_{k}$ for any $j$ and $k$, all its partial derivatives
have to be equal at $\mathbf{t}_{M}^{e}$. Therefore, every even allocation for
each $M$ corresponds to a critical point of the constrained optimization
problem (see Sec. 4.7).

We still need to characterize these critical points in order to show that the
global maximum is indeed an even allocation. We first remember that the
optimal number of active dimensions $M$ needs to be found, and thus it is
useful to see how expected utility varies as a function of $M$. To do this, we
note that any $M$-dimensional simplex is in fact the border of an
($M-1$)-dimensional simplex. For example, for $M=2$, the constraints describe
a line segment, or 1-simplex, where we have the symmetric critical point
$\mathbf{t}^{e}_{2}=(T/2,T/2)$ (Fig. 5b, black circle). However, the line
$t_{1}+t_{2}=T$ is one of the 3 edges of the triangle, or 2-simplex (Fig. 5c:
pink lines are the edges of triangle), where in fact we have another symmetric
critical point in its interior (black triangle). With this, we can ‘visualize’
the infinite-dimensional nature of this problem, since all critical points of
the utility lie at the edges of a higher dimensional simplex.

To asses the landscape of expected utility in high-dimensional simplices, we
can evaluate it at all symmetric critical points $\mathbf{t}^{e}_{M}$ and
along directions that go orthogonally between them (Fig. 5c, orange arrows).
Thus, we devised a one-dimensional path that allows to continuously connect
all symmetrical critical points, and applied it to the small capacity limit
$C\ll 1$. As we move from the 1-simplex to higher dimensional simplices (as in
Fig. 5c), we find that first utility increases, reaching a maximum at the even
allocation in $M=5$ dimensions, and then decreases (Fig. 5d). Therefore,
critical points $\mathbf{t}^{e}_{2}$, $\mathbf{t}^{e}_{3}$ and
$\mathbf{t}^{e}_{4}$ are ‘saddle’-like points, as they are maxima in the
interior of their corresponding simplex, and minima as one moves to the
interior of the higher dimensional simplex.

Although the above analysis suggests that the optimum lies at an even
allocation point, it is still unclear whether there are other critical points
that are asymmetrical and have a larger utility. To argue that the presence of
non-symmetrical local optima is unlikely, we used a stochastic gradient
projection method [34] that maximizes expected utility subject to the
constraints, and applied it to the Gaussian prior case (see Sec. 4.7 in
Methods for details). Indeed, we find for various capacities that, regardless
of the initial condition, i.e. random initial allocations, a maximum utility
is attained when time is evenly divided (Fig. 5e), and the global maxima
coincide with the ones found in the previous sections.

##  3 Discussion

We have studied a model of multi-alternative decision making where an agent
can allocate finite sampling resources to options and choose the best one
amongst them. We found that the capacity of the agent depends on both the
amount of sampling resources, i.e. time or precision, as well as on the
discriminability of the options in the environment. As a function of capacity,
optimal policies undergo an abrupt transition: at small capacity, allocating
time to a handful of options is optimal; at large capacity, the number of
options grows sub-linearly, well below the actual sampling capacity of the
agent. Our results show that decision bottlenecks, such as option-narrowing,
can arise from optimal policies in the face of uncertainty, and provide so far
untested predictions on choice behaviors in multi-alternative decision making
as a function of capacity.

Seemingly strict limits pervade cognition, from the so-called attentional
bottleneck [35, 36, 37], over working memory [13, 14, 38, 39, 40], to
executive control [41, 42, 43]. These limits might result from using scarce
neuronal resources or from using them inefficiently. However, a likely
alternative is that bottlenecks reflect strategies that make optimal use of
limited but large resources. Indeed, past work has recognized that some
apparent limits, most notably dual tasking bottlenecks [44, 45], could be the
result of optimal allocation of finite resources to avoid overlap and
interference between the different representations needed to solve the two
tasks [45, 46, 47]. Further, it has been recognized that the narrow focus of
attention could be at the heart of solution to the the binding problem by
integrating separate features into a coherent object [48], and thus its
narrowness might reflect a function more than a limitation. Our work follows
this line of argument and provides for the first time a quantitative account
for why it is optimal for an agent to consider a handful of options in the
face of uncertainty, well above two but well below 10. In addition, our
results shed light on why people might ignore hundreds of accessible options
and focus resources to a very small number of options [8, 9, 10]. Thus, some
of the seemingly strict limits in decision making can be the result of optimal
policies that favour depth versus breadth processing of the options.

It has been long recognized that people often consider a small set of options
while ignoring many others [12, 8, 11, 4]. In the ‘consumer’ literature this
is explained by arguing that small consideration sets are favored because they
optimally balance the probability of finding a good option in the set with the
search and mental costs incurred in adding new options to that set. These
models thus assume that resources are not limited, but are costly. In
contrast, the assumptions in our work do not explicitly tune the cost of
sampling, but rather an implicit cost arises naturally from the strict
capacity constraint, which depends intrinsically on the agent as well as
extrinsically on the environment. A more fundamental distinction is that
previous work did not focus on allocating resources intensively into the
options, such that the only decision was whether to include an option into the
set or not, without considering the amount of resources allocated to it. This
distinction makes that problem drastically different than the tradeoffs of the
BD dilemma considered here. This can explain why transitions of optimal
policies as a function of agent’s parameters have not been reported before.

Previous work has characterized optimal BD tradeoffs in multi-alternative
choices like the ones studied here, but by assuming that agents have a finite
‘discrete’ capacity [3]. Our assumption of a continuous resource (e.g. time)
that can be infinitely divided has allowed us to uncover qualitatively novel
optimal policies at small capacity. This is because a discrete small capacity
can never produce numbers of sampled options above that capacity. Our modeling
assumptions are also different and more in line with current theories of
decision making based on accumulators of evidence [25, 27, 33, 49] that trade
accuracy over time. Here we have not considered, however, a sequential process
where accumulation of evidence can be stopped at any time, a topic that should
be addressed in the future. In any event, any agent with finite capacity
cannot avoid the problem of first deciding how many options to allocate
capacity to, as dividing resources up to too small portions is clearly
suboptimal, and thus BD tradeoffs as described above will be generally at
play. Secondly, a sequential decision process can ensue after the first
decision of how many options to sample, while we have assumed that allocated
times cannot be reallocated on the fly. Although this will be as well a very
relevant extension of our work, it is important to note that in many decisions
it is actually hard, if not impossible, to reallocate already assigned
resources, being neuronal, temporal or economical, and thus our framework more
closely applies to those circumstances.

Bounded rationality accounts [20, 21, 22, 23] propose that cognition results
from the finite limits of the nervous system from where it emerges. Our work
follows this line of research in two ways. First, we propose that agents
indeed have a finite sampling capacity that can be arbitrarily allocated to
the available options. However, an important assumption in our work is that
while the intrinsic resources of an agent might seem large, the interaction of
the agent with the environment might render their effective decision-making
capacity small. Therefore, capacity is not an absolute quantity that describes
an agent, but a relative quantity that contextualizes the agents and
characterizes how well they are suited to solve a given task in the world. An
important contribution of our work is to show that optimal policies depend on
effective capacity in a highly non-linear way, such that small-capacity agents
would behave qualitatively different than large-capacity agents (or even the
behavior of the same agent operating in different environments could be
qualitatively different). This is clearly a prediction that can be tested with
humans where time or other resources are constrained and varied on a trial by
trial basis. Secondly, agents perform the allocation before feedback is
received, which relates to a bounded-optimal agent that is optimized at
‘design’-time, which eliminates the paradox of perfect rationality by not
letting the agent optimize their decisions at run-time [50], an argument that
further supports the validity and relevance of two-stage decisions.

Another important result of our work is that evenly dividing time to a small
set of options is optimal when they are initially indistinguishable. This
optimal division of resources coincides with the $1/N$ heuristic rule [51] or
equality heuristic [52], which has proven to be implemented in human decision
making and highly efficient as a portfolio strategy [53]. In our case, the
fact that options are drawn from the same prior (known to the agent)
contributes to the optimality of the even allocation. Although the optimal
allocation of non-identically distributed options is not addressed here, this
heuristic can be efficient in such situations [54]. It is important to realize
that the optimal low numbers of considered options have been found in the case
where their values are not known in advance and come from the same
distribution. If agents have strong preferences or have additional information
about the expected values of the options, then the number of considered
alternatives will be further reduced. This shows once again that a low number
of considered options can hardly be taken as evidence of a decisional
bottleneck and is more in line with an optimal tradeoff between breadth and
depth.

Finally, our results can have important implications for the optimal wiring of
neural networks in the brain [16, 17, 18, 19]. First, as just few options
should be considered at the same time, it is expected that only those would be
encoded in different, albeit possibly overlapping, pools of neurons. Thus,
although models consisting of two or three pools that compete for dominance
through mutual inhibition can be a sensible idea for binary and ternary
decision making [25, 55, 56, 57, 58, 59, 60], extrapolating this to many more
options (e.g., larger than 10) by splitting neurons into corresponding pools
of neurons would be hardly optimal. Our results are, in contrast, consistent
with the opposite view that posits that a single pool of neurons is sufficient
for decision making [61]. In this framework, a single pool encodes just one of
the available options, the one that is under the focus of attention.
Previously attended options produce a background activity against which the
current option is compared to, and other options fall outside the
representation of the neural network [61, 62, 63, 64, 65]. Thus, comparison
and selection between options occurs through a temporal contrast, rather than
through mutual inhibition between simultaneously encoded options. This model
can be readily extrapolated to multiple many options, with the only dilemma of
dividing time or precision into few or many options (like in Fig. 1), thus
addressing the associated BD tradeoffs. The debate of the one-pool versus
several-pools models remains open [61, 66], but electrophysiology experiments
with many options should be able to arbitrate between the two hypotheses under
the new computational constraints that we have identified here.

## Acknowledgments

This work is supported by the Howard Hughes Medical Institute (HHMI, ref
55008742), MINECO (Spain; BFU2017-85936-P) and ICREA Academia (2016) to
R.M.-B, and MINECO/ESF (Spain; PRE2018-084757) to J.R.-R. J.R.-R. would like
to thank Fred Callaway for helpful suggestions at early stages of this work.

## Code availability

All the numerical work performed to generate the various figures is available
as documented Julia code along with a guided notebook at this public GitHub
repository.

## References

  * [1] Dwight P Miller.  The depth/breadth tradeoff in hierarchical computer menus.  In Proceedings of the Human Factors Society Annual Meeting, volume 25, pages 296–300. SAGE Publications Sage CA: Los Angeles, CA, 1981.
  * [2] Ellis Horowitz and Sartaj Sahni.  Fundamentals of computer algorithms.  Computer Science Press, 1978.
  * [3] Rubén Moreno-Bote, Jorge Ramírez-Ruiz, Jan Drugowitsch, and Benjamin Y Hayden.  Heuristics and optimal solutions to the breadth–depth dilemma.  Proceedings of the National Academy of Sciences, 117(33):19799–19808, 2020.
  * [4] John W Payne.  Task complexity and contingent processing in decision making: An information search and protocol analysis.  Organizational behavior and human performance, 16(2):366–387, 1976\.
  * [5] Richard W Olshavsky.  Task complexity and contingent processing in decision making: A replication and extension.  Organizational behavior and human performance, 24(3):300–316, 1979\.
  * [6] Lee Roy Beach.  Broadening the definition of decision making: The role of prechoice screening of options.  Psychological science, 4(4):215–220, 1993.
  * [7] Irwin P Levin, JD Jasper, and Wendy S Forbes.  Choosing versus rejecting options at different stages of decision making.  Journal of Behavioral Decision Making, 11(3):193–210, 1998.
  * [8] John R Hauser and Birger Wernerfelt.  An evaluation cost model of consideration sets.  Journal of consumer research, 16(4):393–408, 1990.
  * [9] Sheena S Iyengar and Mark R Lepper.  When choice is demotivating: Can one desire too much of a good thing?  Journal of personality and social psychology, 79(6):995, 2000.
  * [10] Benjamin Scheibehenne, Rainer Greifeneder, and Peter M Todd.  Can there ever be too many options? a meta-analytic review of choice overload.  Journal of consumer research, 37(3):409–425, 2010.
  * [11] Nitin Mehta, Surendra Rajiv, and Kannan Srinivasan.  Price uncertainty and consumer search: A structural model of consideration set formation.  Marketing science, 22(1):58–84, 2003.
  * [12] George J Stigler.  The economics of information.  Journal of political economy, 69(3):213–225, 1961.
  * [13] George A Miller.  The magical number seven, plus or minus two: Some limits on our capacity for processing information.  Psychological review, 63(2):81, 1956.
  * [14] Nelson Cowan, Emily M Elliott, J Scott Saults, Candice C Morey, Sam Mattox, Anna Hismjatullina, and Andrew RA Conway.  On the capacity of attention: Its estimation and its role in working memory and cognitive aptitudes.  Cognitive psychology, 51(1):42–100, 2005.
  * [15] Timothy F Brady, Viola S Störmer, and George A Alvarez.  Working memory is not fixed-capacity: More active storage capacity for real-world objects than for simple stimuli.  Proceedings of the National Academy of Sciences, 113(27):7459–7464, 2016.
  * [16] Matthew FS Rushworth, MaryAnn P Noonan, Erie D Boorman, Mark E Walton, and Timothy E Behrens.  Frontal cortex and reward-guided learning and decision-making.  Neuron, 70(6):1054–1069, 2011.
  * [17] Markus Siegel, Timothy J Buschman, and Earl K Miller.  Cortical information flow during flexible sensorimotor decisions.  Science, 348(6241):1352–1355, 2015.
  * [18] Timothy J Vickery, Marvin M Chun, and Daeyeol Lee.  Ubiquity and specificity of reinforcement signals throughout the human brain.  Neuron, 72(1):166–177, 2011.
  * [19] Seng Bum Michael Yoo and Benjamin Yost Hayden.  Economic choice as an untangling of options into actions.  Neuron, 99(3):434–447, 2018.
  * [20] Herbert A Simon.  Theories of bounded rationality.  Decision and organization, 1(1):161–176, 1972.
  * [21] Stuart Russell and Eric Wefald.  Principles of metareasoning.  Artificial intelligence, 49(1-3):361–395, 1991.
  * [22] Samuel J Gershman, Eric J Horvitz, and Joshua B Tenenbaum.  Computational rationality: A converging paradigm for intelligence in brains, minds, and machines.  Science, 349(6245):273–278, 2015.
  * [23] Thomas L Griffiths, Falk Lieder, and Noah D Goodman.  Rational use of cognitive resources: Levels of analysis between the computational and the algorithmic.  Topics in cognitive science, 7(2):217–229, 2015.
  * [24] Roger Ratcliff and Bennet B Murdock.  Retrieval processes in recognition memory.  Psychological review, 83(3):190, 1976.
  * [25] Joshua I Gold and Michael N Shadlen.  The neural basis of decision making.  Annual review of neuroscience, 30, 2007.
  * [26] Ian Krajbich and Antonio Rangel.  Multialternative drift-diffusion model predicts the relationship between visual fixations and choice in value-based decisions.  Proceedings of the National Academy of Sciences, 108(33):13852–13857, 2011.
  * [27] Jan Drugowitsch, Rubén Moreno-Bote, Anne K Churchland, Michael N Shadlen, and Alexandre Pouget.  The cost of accumulating evidence in perceptual decision making.  Journal of Neuroscience, 32(11):3612–3628, 2012.
  * [28] Satohiro Tajima, Jan Drugowitsch, Nisheet Patel, and Alexandre Pouget.  Optimal policy for multi-alternative decisions.  Nature neuroscience, 22(9):1503–1511, 2019.
  * [29] Anthony I Jang, Ravi Sharma, and Jan Drugowitsch.  Optimal policy for attention-modulated decisions explains human fixation behavior.  bioRxiv, 2020.
  * [30] Frederick Callaway, Antonio Rangel, and Thomas L Griffiths.  Fixation patterns in simple choice are consistent with optimal use of cognitive resources.  PsyArXiv preprint PsyArXiv: https://doi. org/10.31234/osf. io/57v6k, 2020.
  * [31] Allan D Shocker, Moshe Ben-Akiva, Bruno Boccara, and Prakash Nedungadi.  Consideration set influences on consumer decision-making and choice: Issues, models, and suggestions.  Marketing letters, 2(3):181–197, 1991.
  * [32] John H Roberts and James M Lattin.  Development and testing of a model of consideration set composition.  Journal of Marketing Research, 28(4):429–440, 1991.
  * [33] Rubén Moreno-Bote.  Decision confidence and uncertainty in diffusion models with partially correlated neuronal integrators.  Neural computation, 22(7):1786–1811, 2010.
  * [34] Roger Fletcher.  Practical methods of optimization.  John Wiley & Sons, 2013.
  * [35] J Anthony Deutsch and Diana Deutsch.  Attention: Some theoretical considerations.  Psychological review, 70(1):80, 1963.
  * [36] Anne M Treisman.  Strategies and models of selective attention.  Psychological review, 76(3):282, 1969.
  * [37] Steven Yantis and James C Johnston.  On the locus of visual selection: Evidence from focused attention tasks.  Journal of experimental psychology: Human perception and performance, 16(1):135, 1990.
  * [38] Steven J Luck and Edward K Vogel.  Visual working memory capacity: from psychophysics and neurobiology to individual differences.  Trends in cognitive sciences, 17(8):391–400, 2013.
  * [39] Wei Ji Ma, Masud Husain, and Paul M Bays.  Changing concepts of working memory.  Nature neuroscience, 17(3):347, 2014.
  * [40] Timothy F Brady, Talia Konkle, and George A Alvarez.  A review of visual memory capacity: Beyond individual items and toward structured representations.  Journal of vision, 11(5):4–4, 2011.
  * [41] Amitai Shenhav, Sebastian Musslick, Falk Lieder, Wouter Kool, Thomas L Griffiths, Jonathan D Cohen, and Matthew M Botvinick.  Toward a rational and mechanistic account of mental effort.  Annual review of neuroscience, 40:99–124, 2017.
  * [42] DA Norman and T Shallice.  Attention to action [w:] rj davidson, ge schwartz, d. shapiro (red.).  Consciousness and Self-Regulation, pages 1–18, 1986.
  * [43] Brianna J Sleezer, Meghan D Castagno, and Benjamin Y Hayden.  Rule encoding in orbitofrontal cortex and striatum guides selection.  Journal of Neuroscience, 36(44):11223–11237, 2016.
  * [44] Rico Fischer and Franziska Plessow.  Efficient multitasking: parallel versus serial processing of multiple tasks.  Frontiers in psychology, 6:1366, 2015.
  * [45] David E Meyer and David E Kieras.  A computational theory of executive cognitive processes and multiple-task performance: Part i. basic mechanisms.  Psychological review, 104(1):3, 1997.
  * [46] Samuel F Feng, Michael Schwemmer, Samuel J Gershman, and Jonathan D Cohen.  Multitasking versus multiplexing: Toward a normative account of limitations in the simultaneous execution of control-demanding behaviors.  Cognitive, Affective, & Behavioral Neuroscience, 14(1):129–146, 2014.
  * [47] Ariel Zylberberg, Stanislas Dehaene, Pieter R Roelfsema, and Mariano Sigman.  The human turing machine: a neural framework for mental programs.  Trends in cognitive sciences, 15(7):293–300, 2011.
  * [48] Anne Treisman.  Feature binding, attention and object perception.  Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences, 353(1373):1295–1306, 1998.
  * [49] Roger Ratcliff and Philip L Smith.  A comparison of sequential sampling models for two-choice reaction time.  Psychological review, 111(2):333, 2004.
  * [50] Stuart J Russell and Devika Subramanian.  Provably bounded-optimal agents.  Journal of Artificial Intelligence Research, 2:575–609, 1994.
  * [51] Gerd Gigerenzer and Wolfgang Gaissmaier.  Heuristic decision making.  Annual review of psychology, 62:451–482, 2011.
  * [52] David M Messick.  Equality as a decision heuristic.  Psychological perspectives on justice: Theory and applications, pages 11–31, 1993.
  * [53] Victor DeMiguel, Lorenzo Garlappi, and Raman Uppal.  Optimal versus naive diversification: How inefficient is the 1/n portfolio strategy?  The review of Financial studies, 22(5):1915–1953, 2009.
  * [54] Warren Thorngate.  Efficient decision heuristics.  Behavioral Science, 25(3):219–225, 1980.
  * [55] Paul Cisek and John F Kalaska.  Neural mechanisms for interacting with a world full of action choices.  Annual review of neuroscience, 33:269–298, 2010.
  * [56] Robert M Roe, Jermone R Busemeyer, and James T Townsend.  Multialternative decision field theory: A dynamic connectionst model of decision making.  Psychological review, 108(2):370, 2001.
  * [57] Marius Usher and James L McClelland.  The time course of perceptual choice: the leaky, competing accumulator model.  Psychological review, 108(3):550, 2001.
  * [58] Rubén Moreno-Bote, John Rinzel, and Nava Rubin.  Noise-induced alternations in an attractor network model of perceptual bistability.  Journal of neurophysiology, 98(3):1125–1139, 2007.
  * [59] Anne K Churchland, Roozbeh Kiani, and Michael N Shadlen.  Decision-making with multiple alternatives.  Nature neuroscience, 11(6):693–702, 2008.
  * [60] Xiao-Jing Wang.  Decision making in recurrent neuronal circuits.  Neuron, 60(2):215–234, 2008.
  * [61] Benjamin Y Hayden and Rubén Moreno-Bote.  A neuronal theory of sequential economic choice.  Brain and Neuroscience Advances, 2:2398212818766675, 2018.
  * [62] Ian Krajbich, Carrie Armel, and Antonio Rangel.  Visual fixations and the computation and comparison of value in simple choice.  Nature neuroscience, 13(10):1292–1298, 2010.
  * [63] Seung-Lark Lim, John P O’Doherty, and Antonio Rangel.  The decision value computations in the vmpfc and striatum use a relative value code that is guided by visual attention.  Journal of Neuroscience, 31(37):13214–13223, 2011.
  * [64] A David Redish.  Vicarious trial and error.  Nature Reviews Neuroscience, 17(3):147, 2016.
  * [65] Erin L Rich and Jonathan D Wallis.  Decoding subjective decisions from orbitofrontal cortex.  Nature neuroscience, 19(7):973–980, 2016.
  * [66] Sébastien Ballesta and Camillo Padoa-Schioppa.  Economic decisions through circuit inhibition.  Current Biology, 29(22):3814–3824, 2019.
  * [67] Laurens De Haan and Ana Ferreira.  Extreme value theory: an introduction.  Springer Science & Business Media, 2007.
  * [68] Christopher M Bishop.  Pattern recognition and machine learning.  springer, 2006.

##  4 Methods

Comments and mathematical proofs supporting claims in the manuscript.

###  4.1 Posterior mean of drift is a monotonously increasing function of
accumulated evidence

Here we prove that the posterior mean of the drift, which is a random variable
with probability distribution defined by Bayes’ rule, Eq. (3), is a
monotonously increasing function of evidence $x$. We have seen that the
expected value of a drift $\mu$ given the accumulated evidence $x$, for any
option (and thus here dropping indices) is given by

$\hat{\mu}(x,t,\sigma,\theta)=\frac{\int\differential{\mu}\mu\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)}{p(x|t,\sigma,\theta)},$ (15)

where $p_{\theta}(\mu)$ is the prior probability of the drifts, with
hyperparameters $\theta$ and $p(x|t,\sigma,\theta)$ is the marginalized
probability distribution of the evidence. To know if
$\hat{\mu}(x,t,\sigma,\theta)$ is an increasing function of $x$, we simply
derive, and we expect the derivative to be always positive,

$\displaystyle\derivative{\hat{\mu}}{x}=$
$\displaystyle\,\frac{p(x|t,\sigma,\theta)\int\differential{\mu}\mu\left(-\frac{x-\mu
t}{\sigma^{2}t}\right)\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)}{p(x|t,\sigma,\theta)^{2}}$
$\displaystyle-\frac{\int\differential{\mu}\mu\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)\int\differential{\mu}\left(-\frac{x-\mu
t}{\sigma^{2}t}\right)\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)}{p(x|t,\sigma,\theta)^{2}}>0$
$\displaystyle\iff$
$\displaystyle\frac{1}{\sigma^{2}}\left(\mathbb{E}\left[\mu^{2}|x,t,\sigma,\theta\right]-\mathbb{E}\left[\mu|x,t,\sigma,\theta\right]^{2}\right)=\frac{{\rm
Var}\left[p(\mu|x,t,\sigma,\theta)\right]}{\sigma^{2}}>0,$

where

$\mathbb{E}\left[\mu^{n}|x,t,\sigma,\theta\right]=\frac{\int\differential{\mu}\mu^{n}\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)}{\int\differential{\mu}\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu)}.$

Since the variance is the expected value of a positive quantity, then we
conclude that the expected value of the drift is a monotonously increasing
function of the observed accumulated evidence $x$ for any prior.

###  4.2 Expected value of the drift in the small capacity limit

Here we show that in the small capacity limit, the utility in Eq. (9) can be
written as in Eq. (11) for any regular prior distribution. Our strategy is to
study the limiting behaviors of the cumulative density function (described
below in Sec. 4.3) and the posterior mean of the drift (detailed in this
section) that appear in Eq. (9) as $C=\frac{\sigma_{0}^{2}}{\sigma^{2}}T$ goes
to zero.

From Bayes’s rule, Eq. (3), the posterior mean of the drift is given by

$\hat{\mu}(x,t,\sigma,\theta)=\frac{1}{\sqrt{2\pi\sigma^{2}t}}\frac{\int\differential{\mu}\mu\,\exp(-\frac{1}{2\sigma^{2}t}(\mu
t-x)^{2})p_{\theta}(\mu|\theta)}{p(x|t,\sigma,\theta)}.$ (16)

Let us focus on the numerator, which we will interpret as the expectation
value of $\mu\,\exp(-\frac{1}{2\sigma^{2}t}(\mu t-x)^{2})$ with respect to the
prior. We assume the prior to be such that this expectation is finite for all
$x$ and that all its moments are finite (e.g, Gaussian and uniform
distributions). We define $z\equiv
z(x)\equiv\frac{1}{\sqrt{\sigma^{2}t}}(x-\mu_{0}t)$ and
$\mu_{s}\equiv\frac{1}{\sqrt{\sigma^{2}t}}(\mu t-\mu_{0}t)$, and by adding and
subtracting $\mu_{0}t$ at the exponent, we can write the numerator in the
above equation as

$\displaystyle\mathbb{E}_{\theta}\left[\mu\,\exp(-\frac{1}{2\sigma^{2}t}(\mu
t-x)^{2})\right]$
$\displaystyle=\mathbb{E}_{\theta}\left[\mu\,\exp(-\frac{1}{2\sigma^{2}t}(\mu
t-\mu_{0}t+\mu_{0}t-x)^{2})\right]$
$\displaystyle=\exp(-\frac{z^{2}}{2})\mathbb{E}_{\theta}\left[\mu\,\exp\left(z\mu_{s}-\frac{1}{2}\mu_{s}^{2}\right)\right]$
$\displaystyle=\exp(-\frac{z^{2}}{2})\Big{\\{}\mathbb{E}_{\theta}\left[\mu_{0}\,\exp\left(z\mu_{s}-\frac{1}{2}\mu_{s}^{2}\right)\right]$
$\displaystyle+\mathbb{E}_{\theta}\left[\sqrt{\frac{\sigma^{2}}{t}}\mu_{s}\,\exp\left(z\mu_{s}-\frac{1}{2}\mu_{s}^{2}\right)\right]\Big{\\}}.$

Next, we note that the exponential in the expectations is the generating
function of the Hermite polynomials, and thus

$\exp(z\mu_{s}-\frac{1}{2}\mu_{s}^{2})=\sum_{n=0}^{\infty}{\rm
He}_{n}(z)\frac{\mu_{s}^{n}}{n!}.$

By replacing the exponential with the infinite series in the above
expectation, Eq. (16), we obtain

$\displaystyle p(x|t,\sigma,\theta)\hat{\mu}(x,t,\sigma,\theta)=$
$\displaystyle\frac{\exp(-\frac{z^{2}}{2})}{\sqrt{2\pi\sigma^{2}t}}\left\\{\mathbb{E}_{\theta}\left[\mu_{0}\,\sum_{n=0}^{\infty}{\rm
He}_{n}(z)\frac{\mu_{s}^{n}}{n!}\right]+\mathbb{E}_{\theta}\left[\sqrt{\frac{\sigma^{2}}{t}}\mu_{s}\,\sum_{n=0}^{\infty}{\rm
He}_{n}(z)\frac{\mu_{s}^{n}}{n!}\right]\right\\}$ $\displaystyle=$
$\displaystyle\frac{\mathcal{N}(z|0,1)}{\sqrt{\sigma^{2}t}}\left\\{\sum_{n=0}^{\infty}\frac{1}{n!}\mathbb{E}_{\theta}\left[\mu_{s}^{n}\right]\mu_{0}{\rm
He}_{n}(z)+\sum_{n=0}^{\infty}\frac{1}{n!}\mathbb{E}_{\theta}\left[\mu_{s}^{n+1}\right]\sqrt{\frac{\sigma^{2}}{t}}{\rm
He}_{n}(z)\right\\}$ $\displaystyle=$
$\displaystyle\frac{\mathcal{N}(z|0,1)}{\sqrt{\sigma^{2}t}}\left\\{\sum_{n=0}^{\infty}\frac{1}{n!}\mathbb{E}_{\theta}\left[\frac{(\mu-\mu_{0})^{n}}{\sqrt{\sigma^{2}/t}^{n}}\right]\left(\mu_{0}{\rm
He}_{n}(z)+\sqrt{\frac{\sigma^{2}}{t}}n{\rm He}_{n-1}(z)\right)\right\\}$
$\displaystyle=$
$\displaystyle\frac{\mathcal{N}(z|0,1)}{\sqrt{\sigma^{2}t}}\Bigg{\\{}\sum_{n=0}^{\infty}\frac{1}{n!}\sqrt{\frac{C}{M}}^{\,n-1}\mathbb{E}_{\theta}\left[\frac{(\mu-\mu_{0})^{n}}{\sigma_{0}^{n}}\right]$
$\displaystyle\quad\quad\quad\quad\quad\times\left(\sqrt{\frac{C}{M}}\mu_{0}{\rm
He}_{n}(z)+\sigma_{0}n{\rm He}_{n-1}(z)\right)\Bigg{\\}},$

where we have used that all the moments of the prior are finite and the sum is
well defined. Note that to obtain the third line we have shifted the second
index $n+1\rightarrow n$ and used that the term $n{\rm He}_{n-1}(z)$ is zero
for $n=0$.

We now insert the above series into the expression of utility in Eq. (9) to
obtain

$\displaystyle\hat{U}(t,\sigma,\theta)=$
$\displaystyle\int\differential{x}\,\derivative{x}\left\\{\left[F_{x}(x|t,\sigma,\theta)\right]^{M}\right\\}\hat{\mu}(x,t,\sigma,\theta)$
$\displaystyle=$
$\displaystyle\int\differential{x}\,M\left[F_{x}(x|t,\sigma,\theta)\right]^{M-1}\frac{\mathcal{N}(z|0,1)}{\sqrt{\sigma^{2}t}}$
$\displaystyle\times\left\\{\sum_{n=0}^{\infty}\frac{1}{n!}\sqrt{\frac{C}{M}}^{\,n-1}\mathbb{E}_{\theta}\left[\frac{(\mu-\mu_{0})^{n}}{\sigma_{0}^{n}}\right]\left(\sqrt{\frac{C}{M}}\mu_{0}{\rm
He}_{n}(z)+\sigma_{0}n{\rm He}_{n-1}(z)\right)\right\\}$ $\displaystyle=$
$\displaystyle\int\differential{z}\,M\left[F_{z}(z|t,\sigma,\theta)\right]^{M-1}\mathcal{N}(z|0,1)\left[\mu_{0}+\sqrt{\frac{C}{M}}\sigma_{0}z\right]+\mathcal{O}(C),$

where in the second line it is implicit that $z$ depends on $x$, and in the
last line we have made a linear transformation of variables from $x$ to
$z=z(x)$. We also note that as the integral in the last line only involves
polynomials in $z$ that are weighted by the standard normal (and by a
cumulative, which is bounded to be in the range $[0,1]$), their integrals are
finite, and thus we can truncate the series at the first leading order, which
is order $\sqrt{C}$. It remains to see whether the cumulative density function
$F_{z}(z|t,\sigma,\theta)$ contributes order $\sqrt{C}$ or larger, and we show
below in Sec. (4.3) that the former is actually true, such that
$F_{z}(z|t,\sigma,\theta)=\frac{1}{2}\left[1+\erf\left(\frac{z}{\sqrt{2}}\right)\right]+\mathcal{O}(C)$.
With all this, we can approximate the utility up to order $\sqrt{C}$ as

$\hat{U}(C,M,\mu_{0})=\mu_{0}+\sigma_{0}\sqrt{C}\sqrt{M}\int_{-\infty}^{\infty}\differential{z}\left[\frac{1}{2}\left(1+\erf\left(\frac{z}{\sqrt{2}}\right)\right)\right]^{M-1}\mathcal{N}(z|0,1)\,z+\mathcal{O}(C),$
(17)

which is identical to Eq. (11).

###  4.3 Distribution of evidence at small capacity limit

Here, we find an approximation to the marginalized probability distribution of
the evidence at small capacity. From Bayes’ rule and the law of the
unconscious statistician,

$p(x|t,\sigma,\theta)=\int\differential{\mu}\mathcal{N}(x|\mu
t,\sigma^{2}t)p_{\theta}(\mu|\theta)=\mathbb{E}_{\theta}\left[\mathcal{N}(x|\mu
t,\sigma^{2}t)\right].$

To compute this expectation, we follow the same procedure as in Sec. 4.2. We
define $z\equiv\frac{1}{\sqrt{\sigma^{2}t}}(x-\mu_{0}t)$ and
$\mu_{s}\equiv\frac{1}{\sqrt{\sigma^{2}t}}(\mu t-\mu_{0}t)$ and add and
subtract $\mu_{0}t$ at the exponent, to obtain

$\displaystyle p(x|t,\sigma,\theta)$
$\displaystyle=\mathbb{E}_{\theta}\left[\exp(-\frac{1}{2\sigma^{2}t}(x-\mu
t)^{2})\right]$
$\displaystyle=\mathbb{E}_{\theta}\left[\exp(-\frac{1}{2\sigma^{2}t}(x-\mu_{0}t+\mu_{0}t-\mu
t)^{2})\right]$
$\displaystyle=\exp(-\frac{z^{2}}{2})\mathbb{E}_{\theta}\left[\exp\left(z\mu_{s}-\frac{1}{2}\mu_{s}^{2}\right)\right].$

Next, we again identify the exponential generating function of the Hermite
polynomials,

$\exp(z\mu_{s}-\frac{1}{2}\mu_{s}^{2})=\sum_{n=0}^{\infty}{\rm
He}_{n}(z)\frac{\mu_{s}^{n}}{n!},$

and thus we obtain a series for the probability distribution of the evidence,

$\displaystyle p(x|t,\sigma,\theta)=$
$\displaystyle\frac{1}{\sqrt{2\pi\sigma^{2}t}}\exp(-\frac{z^{2}}{2})\mathbb{E}_{\theta}\left[\sum_{n=0}^{\infty}{\rm
He}_{n}(z)\frac{\mu_{s}^{n}}{n!}\right]$ $\displaystyle=$
$\displaystyle\frac{\exp(-\frac{z^{2}}{2})}{\sqrt{2\pi\sigma^{2}t}}\sum_{n=0}^{\infty}\frac{1}{n!}\mathbb{E}_{\theta}\left[\mu_{s}^{n}\right]{\rm
He}_{n}(z)$ $\displaystyle=$
$\displaystyle\frac{\exp(-\frac{z^{2}}{2})}{\sqrt{2\pi\sigma^{2}t}}\sum_{n=0}^{\infty}\frac{1}{n!}\mathbb{E}_{\theta}\left[\frac{(\mu-\mu_{0})^{n}}{\sqrt{\sigma^{2}/t}^{n}}\right]{\rm
He}_{n}(z)$ $\displaystyle=$
$\displaystyle\frac{\exp(-\frac{z^{2}}{2})}{\sqrt{2\pi\sigma^{2}t}}\sum_{n=0}^{\infty}\frac{1}{n!}\sqrt{\frac{C}{M}}^{\,n}\mathbb{E}_{\theta}\left[\frac{(\mu-\mu_{0})^{n}}{\sigma_{0}^{n}}\right]{\rm
He}_{n}(z).$

We see that the leading order the distribution of the evidence is a normal
distribution, while the order $\sqrt{C}$ is zero. Therefore, its cumulative in
the variable $z=z(x)$ is, exactly, up to order $\sqrt{C}$,
$F_{z}(z|t,\sigma,\theta)=\frac{1}{2}\left[1+\erf\left(\frac{z}{\sqrt{2}}\right)\right]+\mathcal{O}(C)$.
This expression has been used in Sec. (4.2).

###  4.4 Asymptotic limit of relevant integral

In this subsection we want to obtain the asymptotic limit,
$M\rightarrow\infty$, of the integral

$I(M)=\int_{-\infty}^{\infty}\differential{y}y\,\derivative{y}\Phi^{M}(y),$

appearing in Eqs. (11) and (12), where $\Phi(y)$ is the normal cumulative
distribution function,

$\Phi(y)=\left(\frac{1}{2}+\frac{1}{2}\erf\left(\frac{y}{\sqrt{2}}\right)\right).$

Using Extreme Value Theory [67], it can be shown that this cumulative
distribution function $\Phi(y)$ belongs to the Gumbel class of the generalized
extreme value distributions,

$\lim_{M\rightarrow\infty}\Phi^{M}(a_{M}y+b_{M})=G(y),$

where $G(y)=\exp(-\exp(-y))$ and

$b_{M}=\left(2\log(M)-\log(\log(M))-\log(4\pi)\right)^{1/2}\quad\text{and}\quad
a_{M}=1/b_{M}.$

Using this result, then our integral develops quite easily,

$\displaystyle I(M)$
$\displaystyle\rightarrow\int_{-\infty}^{\infty}\differential{y}y\,\derivative{y}G\left(\frac{y-b_{M}}{a_{M}}\right)$
$\displaystyle=\int_{-\infty}^{\infty}\differential{y}\left(\frac{y}{b_{M}}+b_{M}\right)\derivative{y}G(y)$
$\displaystyle=\frac{1}{b_{M}}\int_{-\infty}^{\infty}\differential{y}y\exp(-y)\exp(-\exp(-y))+b_{M}\int_{-\infty}^{\infty}\differential{y}\derivative{y}G(y)$
$\displaystyle I(M\rightarrow\infty)$
$\displaystyle=\frac{\gamma}{b_{M}}+b_{M},$

where $\gamma\approx 0.577$ is Euler’s constant.

###  4.5 Expected utility for uniform prior

For this choice of prior, drifts are all drawn independently and identically
from a uniform probability distribution between zero and one. That is,

$p(\mu_{i})=\Theta(\mu_{i})\Theta(1-\mu_{i}),$

where $\Theta(x)$ is the Heaviside step function. We can substitute this prior
into eq. (3) to obtain the posterior probability distribution for the drifts,

$p(\mu_{i}|x_{i},\sigma,t_{i},\theta)=\begin{cases}\frac{\mathcal{N}\left(\mu_{i}|\frac{x_{i}}{t_{i}},\frac{\sigma^{2}}{t_{i}}\right)}{\int_{0}^{1}\mathcal{N}\left(\mu_{i}|\frac{x_{i}}{t_{i}},\frac{\sigma^{2}}{t_{i}}\right)\differential\mu_{i}}&\mu_{i}\in[0,1]\\\
0&\text{otherwise}.\end{cases}$

This will produce an expectation value for each drift,

$\hat{\mu}_{i}(x_{i},t_{i},\sigma)\equiv\mathbb{E}\left[\mu_{i}|x_{i},t_{i},\sigma\right]=\frac{x_{i}}{t_{i}}+\frac{\sigma}{\sqrt{2\pi
t_{i}}}\frac{\exp\left(-\frac{x_{i}^{2}}{2\sigma^{2}t_{i}}\right)-\exp\left(-\frac{(x_{i}-t_{i})^{2}}{2\sigma^{2}t_{i}}\right)}{\frac{1}{2}\left[\erf\left(\frac{x_{i}}{\sqrt{2\sigma^{2}t_{i}}}\right)-\erf\left(\frac{x_{i}-t_{i}}{\sqrt{2\sigma^{2}t_{i}}}\right)\right]},$
(18)

where the denominator is related to the probability distribution of the
evidence $x_{i}$, which we can find by marginalizing over drifts,

$\displaystyle p(x_{i}|t_{i},\sigma)$
$\displaystyle=\int_{0}^{1}\differential\mu\frac{1}{\sqrt{2\pi\sigma^{2}t_{i}}}\exp\left(-\frac{1}{2\sigma^{2}t_{i}}(x_{i}-\mu_{i}t_{i})^{2}\right)$
$\displaystyle=\frac{1}{2t_{i}}\left[\erf\left(\frac{x_{i}}{\sqrt{2\sigma^{2}t_{i}}}\right)-\erf\left(\frac{x_{i}-t_{i}}{\sqrt{2\sigma^{2}t_{i}}}\right)\right].$
(19)

We will use from now on the assumption of even time allocation,
$t_{i}=t=\frac{T}{M}$ for all $i$. The cumulative probability distribution for
the evidence in eq. (4.5) is, integrating by parts,

$\displaystyle F(x|t,\sigma)=$
$\displaystyle\int_{-\infty}^{x}p(x^{\prime}|t,\sigma)\differential{x^{\prime}}$
$\displaystyle=$
$\displaystyle\,\frac{1}{2}\left(1+\erf\left(\frac{x-t}{\sqrt{2\sigma^{2}t}}\right)\right)+\frac{x}{2t}\left(\erf\left(\frac{x}{\sqrt{2\sigma^{2}t}}\right)-\erf\left(\frac{x-t}{\sqrt{2\sigma^{2}t}}\right)\right)$
$\displaystyle+\sqrt{\frac{\sigma^{2}}{2\pi
t}}\left[\exp(-\frac{x^{2}}{2\sigma^{2}t})-\exp(-\frac{(x-t)^{2}}{2\sigma^{2}t})\right]$
$\displaystyle=\frac{1}{2}\left[1+\erf\left(\frac{x-t}{\sqrt{2\sigma^{2}t}}\right)\right]+tp(x|t,\sigma)\hat{\mu}(x,t,\sigma),$

where in the last equality we have rewritten the solution in a convenient
form. Hence, the product of the expected value with the probability density
can be rewritten in terms of the cumulative function, from the previous
equation,

$\hat{\mu}(x,t,\sigma)p(x|t,\sigma)=\frac{1}{t}F(x|t,\sigma)-\frac{1}{2t}\left[1+\erf\left(\frac{x-t}{\sqrt{2\sigma^{2}t}}\right)\right],$

and using eq. (9) we get the expression for the utility,

$\displaystyle\hat{U}(M,t,\sigma)=$
$\displaystyle\frac{M}{t}\int_{-\infty}^{\infty}\differential
x\left[F(x|t,\sigma)\right]^{M-1}\left\\{F(x|t,\sigma)-\frac{1}{2}\left[1+\erf\left(\frac{x-t}{\sqrt{2\sigma^{2}t}}\right)\right]\right\\}.$
(20)

###  4.6 Expected utility for Gaussian bimodal prior

The expected utility for the bimodal Gaussian prior with modes $\mu_{1}$ and
$\mu_{2}$, each with a variance $\sigma_{0}^{2}$, is quite similar to the
unimodal, Eq. (10), and follows the straightforward application of Eq. (9).
The probability distribution of the evidence marginalized over drifts is
$p(x|t,\sigma,\theta)=\frac{1}{2}\mathcal{N}(x|\mu_{1}t,\sigma^{2}t+\sigma_{0}^{2}t^{2})+\frac{1}{2}\mathcal{N}(x|\mu_{2}t,\sigma^{2}t+\sigma_{0}^{2}t^{2})$.
Therefore the cumulative is

$F(x|t,\sigma,\theta)=\frac{1}{2}\Phi(x|\mu_{1}t,\sigma^{2}t+\sigma_{0}^{2}t^{2})+\frac{1}{2}\Phi(x|\mu_{2}t,\sigma^{2}t+\sigma_{0}^{2}t^{2}),$

where $\Phi(x|\mu_{m},\sigma_{m}^{2})$ is the normal cumulative distribution
for one mode. However, the expected value of the drift is a bit more involved,
since the posterior distribution over drifts takes a different form,

$p(\mu|x,t,\sigma,\theta)=\frac{\sigma_{t}}{\sqrt{2\pi\sigma^{2}t\sigma_{0}^{2}}p(x|t,\sigma,\theta)}\sum_{i}\frac{1}{2}\mathcal{N}(\mu|\hat{\mu}_{i},\sigma_{t}^{2})\exp\left(-\frac{1}{2(\sigma_{0}^{2}t^{2}+\sigma^{2}t)}\left(\mu_{i}t-x\right)^{2}\right),$

where $1/\sigma_{t}^{2}=t/\sigma^{2}+1/\sigma_{0}^{2}$ and

$\hat{\mu}_{i}=\frac{\sigma^{2}_{t}}{\sigma_{0}^{2}}\mu_{i}+\frac{\sigma^{2}_{t}}{\sigma^{2}}x.$

Consequently, the expected value will be

$\hat{\mu}(x,t,\sigma,\theta)=\frac{1}{\sqrt{2\pi(\sigma_{0}^{2}t^{2}+\sigma^{2}t)}}\frac{1}{p(x|t,\sigma,\theta)}\sum_{i}\frac{\hat{\mu}_{i}}{2}\exp\left(-\frac{1}{2(\sigma_{0}^{2}t^{2}+\sigma^{2}t)}\left(\mu_{i}t-x\right)^{2}\right).$

Then, expected utility is

$\hat{U}(M,t,\sigma,\theta)=M\int_{-\infty}^{\infty}\differential{x}F(x|t,\sigma,\theta)^{M-1}\sum_{i}\frac{\hat{\mu}_{i}}{2}\mathcal{N}\left(x|\mu_{i}t,\sigma_{0}^{2}t^{2}+\sigma^{2}t\right).$
(21)

This expression is numerically integrated and used in Fig. 4.

###  4.7 Stochastic gradient ascent method for Gaussian prior

To maximize utility, Eq. (14), under the time constraint, we can make use of
unconstrained optimization through Lagrangian multipliers. We construct the
Lagrangian given by

$L(\mathbf{t},\theta,\lambda)=\hat{U}(\mathbf{t},\sigma,\theta)+\lambda
h(\mathbf{t})+\boldsymbol{\mu}\cdot\mathbf{g}(\mathbf{t}),$ (22)

where $h(\mathbf{t})=\sum_{i=1}^{M}t_{i}-T$ is the equality constraint that
defines the hyperplane and $0\leq g_{i}(\mathbf{t})=t_{i}$ is the inequality
constraint forcing all times $i$ to be non-negative and thus defining the
simplex. The quantities $\lambda$ and $\boldsymbol{\mu}$ are the Lagrangian
multipliers. In other words, maximizing utility, Eq. (14), subject to the
initial constraints can be done by optimizing the Lagrangian, Eq. (22), with
respect to $\mathbf{t}$, $\lambda$ and $\boldsymbol{\mu}$ subject to Karush-
Kuhn-Tucker conditions [68]

$\displaystyle g_{i}(\mathbf{t})$ $\displaystyle\geq 0,\quad\text{for all }i$
(23a) $\displaystyle\mu_{j}$ $\displaystyle\geq 0,\quad\text{for all }j$ (23b)
$\displaystyle\boldsymbol{\mu}\cdot\mathbf{g}(\mathbf{t})$ $\displaystyle=0$
(23c)

We notice that the first two conditions imply that the third can be rewritten
as $\mu_{i}t_{i}=0$ for all $i$. By optimizing the Lagrangian, Eq. (22), we
obtain the following system of equations

$\nabla_{\mathbf{t}}\,\hat{U}(\mathbf{t}^{*},\sigma,\theta)+\lambda^{*}\mathbf{1}+\boldsymbol{\mu}^{*}=\mathbf{0},$
(24)

where $\mathbf{t}^{*},\lambda^{*},\boldsymbol{\mu}^{*}$ denote the critical
points of the Lagrangian. We note that the symmetrical point in $M$ active
dimensions, denoted by $\mathbf{t}^{e}_{M}$, where $t^{e}_{M,i}=T/M$ for
$i=1,...,M$, is a critical point of the Lagrangian. This is because the
partial derivatives with respect to the utility have to be equal at
$\mathbf{t}_{M}^{e}$, and since this point lies in the interior of the
$(M-1)$-simplex, the $\boldsymbol{\mu}^{e}_{i}=0$ for $i=1,\ldots,M$.
Therefore $\mathbf{t}_{M}^{e}$ complies with Eq. (24) and is indeed a critical
point.

Next, we detail the gradient ascent method used to obtain Fig. 5e. As
explained above, we want to optimize utility, Eq. (14), subject to a set of
equality, Eq. (1), and inequality constraints, $t_{i}\geq 0$, as described in
section “Even allocation is optimal” of the Results. As all our constraints
are linear, we can make use of the gradient projection method [34]. In this
case, we want to obtain the gradient of utility in Eq. (10) and project it in
the $(M-1)$-simplex such that the capacity constraint in Eq. (1) is satisfied.
Due to the linear capacity equality constraint, this projection is simply
given by the linear operator

$\Pi=\mathbf{Id}_{M\times M}-\frac{1}{M}\mathbf{1}_{M\times M}$

where $\mathbf{Id}_{M\times M}$ is the $M\times M$ identity matrix and
$\mathbf{1}_{M\times M}$ is an $M\times M$ matrix full of ones. Therefore, we
can maximize utility by updating $\mathbf{t}^{(k)}$ appropriately,

$\mathbf{t}^{(k+1)}=\mathbf{t}^{(k)}+\eta\Pi\left(\nabla_{\mathbf{t}}\,\hat{U}(\mathbf{t},\sigma,\theta)\right),$
(25)

where $\eta=10^{-1}\,T$ is the default step size, $k$ is the iteration number,
and $\theta$ corresponds to the parameters of the Gaussian prior. The utility
for an arbitrary time allocation $\mathbf{t}$ for the Gaussian prior case is,
using Eq. (14),

$\displaystyle\mathbf{\hat{U}}(\mathbf{t},\sigma,\theta)$
$\displaystyle=\mu_{0}+\sigma_{0}\sum_{i=1}^{N}\int_{-\infty}^{\infty}\differential{y}\,y\,\frac{\exp(-\frac{y^{2}}{2\sigma_{i}^{2}})}{\sqrt{2\pi\sigma_{i}^{2}}}\prod_{j\neq
i}\left\\{\frac{1}{2}\left[1+\erf\left(\frac{y}{\sqrt{2}\sigma_{j}}\right)\right]\right\\},$
(26)

where
$\sigma_{i}^{2}=\frac{\sigma_{0}^{2}t_{i}}{\sigma_{0}^{2}t_{i}+\sigma^{2}}$.
We can therefore compute the derivative of the previous equation with respect
to all components $t_{i}$ and numerically integrate the expression that
results.

In addition to the linear capacity constraint, we have to enforce the
inequality constraints as well, i.e. $t_{i}\geq 0$, which we do by utilizing
an active set of constraints. To implement it, we start in a relatively high-
dimensional ($M-1$)-simplex, choosing $M$ to be $2M^{*}$, where $M^{*}$ is the
optimal number of accumulators to sample in the even sampling case (which is
estimated before through exploration, see main text). If and whenever any of
the components of $\mathbf{t}^{k+1}$ derived from Eq. (25) is approaching a
border ($t_{i}^{(k+1)}\approx\tau$ for some $i$ and small $\tau$), the step
size decreases until the component effectively reaches zero. In such a case,
this dimension is added to the active constraints set (we inactivate the
dimension), thus downgrading the simplex to a lower dimension. In this way,
our algorithm only reduces the initial dimension of the simplex and never
extends it. To initially activate the $2M^{*}$ dimensions, for any random
initial condition $\mathbf{t}_{0}$, we make sure that all the components are
greater than our threshold $t_{0,i}>\tau$ for all $i=1,...,2M^{*}$.

Finally, in order to avoid potentially getting trapped in local maxima, we add
noise at every iteration as follows. At every step $k$ of Eq. (25), and with
probability $\epsilon=0.1$, we push the $t^{(k)}_{i}$ of a randomly chosen
dimension $i$ by a magnitude $\delta=10^{-3}T$ and pull the $t^{(k)}_{j}$ of
another random dimension $j$ in the opposite direction with the same amount in
order to stay in the appropriate simplex.