# Trotterization in Quantum Theory

Grant Kluber

## Abstract

Trotterization in quantum mechanics is an important theoretical concept in
handling the exponential of noncommutative operators. In this communication,
we give a mathematical formulation of the Trotter Product Formula, and apply
it to basic examples in which the utility of Trotterization is evident.
Originally, this article was completed in December 2020 as a report under the
mentorship of Esteban Cárdenas for the University of Texas at Austin
Mathematics Directed Reading Program (DRP). However, the relevance of
Trotterization in reducing quantum circuit complexity has warranted the
release of a revised and more formal version of the original. Thus, we present
a mathematical perspective on Trotterization, including a detailed sketch of a
formal proof of the Trotter Product Formula.

###### Contents

  1. 1 Introduction
  2. 2 The Trotter Product Formula
  3. 3 Applications and Implications
  4. 4 Conclusion

##  1 Introduction

One of the major goals of quantum mechanics is finding solutions, called
wavefunctions/eigenfunctions, to the time-independent Schrödinger wave
equation. For a given time-independent Hamiltonian operator $\hat{H}$ on a
Hilbert space $\mathcal{H}$, the Schrödinger equation is given by

$\hat{H}\ket{\Psi}=E\ket{\Psi}$ (1)

where $\ket{\Psi}\in\mathcal{H}$ is an eigenfunction and $E\in\mathbb{R}$ is
an energy eigenvalue. Alone, this equation only yields the energy values and
the stationary states of the physical system. To get the time-dependent
eigenvector $\ket{\Psi(t)}$, one needs the unitary operator $U(t)$:

$\displaystyle U(t)=e^{-i\hat{H}t/\hbar},$ (2)
$\displaystyle\ket{\Psi(t)}=U(t)\ket{\Psi}=e^{-i\hat{H}t/\hbar}\ket{\Psi},$
(3)

where $\hbar=h/2\pi$ is Planck’s reduced constant.

In practice, it can be hard to compute this operator exponential, so let us
focus on the simplest example: When the (finite-dimensional in this case)
Hamiltonian operator $\hat{H}$ is given by the diagonal matrix

$\hat{H}=\begin{pmatrix}E_{1}&0&\cdots&0\\\ 0&E_{2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&E_{n}\end{pmatrix}.$ (4)

Substituting this into Equation 1, the eigenfunctions are given by the
standard basis

$\ket{\psi_{1}}=\begin{pmatrix}1\\\ 0\\\ \vdots\\\
0\end{pmatrix},\quad\ket{\psi_{2}}=\begin{pmatrix}0\\\ 1\\\ \vdots\\\
0\end{pmatrix},\quad\cdots,\quad\ket{\psi_{n}}=\begin{pmatrix}0\\\ 0\\\
\vdots\\\ 1\end{pmatrix}$ (5)

with corresponding eigenvalues $E_{1},\cdots,E_{n}$, respectively. From this,
an arbitrary stationary state $\ket{\Psi}$ of the entire quantum system is
simply a complex ($c_{i}\in\mathbb{C}$) linear combination:

$\ket{\Psi}=\sum_{i=1}^{n}c_{i}\ket{\psi_{i}},\quad\sum_{i=1}^{n}\left\lvert
c_{i}\right\rvert^{2}=1.$ (6)

This is the time-independent solution. To get to the full time-dependent
solution $\ket{\Psi(t)}$, we simply need to compute $U(t)$. This is made easy
by the fact that the exponential of a diagonal matrix is just the diagonal
matrix of element exponentials. Concretely,

$\displaystyle U(t)$
$\displaystyle=\exp\left[\begin{pmatrix}-iE_{1}t/\hbar&0&\cdots&0\\\
0&-iE_{2}t/\hbar&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&-iE_{n}t/\hbar\end{pmatrix}\right]$
$\displaystyle=\begin{pmatrix}e^{-iE_{1}t/\hbar}&0&\cdots&0\\\
0&e^{-iE_{2}t/\hbar}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&e^{-iE_{n}t/\hbar}\end{pmatrix}.$ (7)

Therefore, the time-dependent state $\ket{\Psi(t)}$ is given by

$\displaystyle\ket{\Psi(t)}$ $\displaystyle=U(t)\ket{\Psi}$
$\displaystyle=\begin{pmatrix}e^{-iE_{1}t/\hbar}&0&\cdots&0\\\
0&e^{-iE_{2}t/\hbar}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&e^{-iE_{n}t/\hbar}\end{pmatrix}\left(\sum_{i=1}^{n}c_{i}\ket{\psi_{i}}\right)$
$\displaystyle=\sum_{i=1}^{n}c_{i}e^{-iE_{i}t/\hbar}\ket{\psi_{i}}.$ (8)

This calculation was simple because the Hamiltonian $\hat{H}$ was diagonal,
but for the general case we need to use the series definition of
exponentiation. Given a (potentially infinite-dimensional) self-adjoint
(Hermitian) operator $S$ defined on $\mathcal{H}$, its exponential is defined
by

$e^{S}=\sum_{n=0}^{\infty}\frac{S^{n}}{n!}.$ (9)

When $S$ is finite-dimensional, simply diagonalizing the matrix is sufficient
to compute $e^{S}$, and therefore solve the eigenvalue problem. However, when
$S$ is infinite dimensional, the problem becomes much more complicated. To
help reduce this complexity, we can consider decomposing an operator into a
sum.

If we have another self-adjoint operator $T$ defined on $\mathcal{H}$ such
that $[S,T]=0$ (i.e., $ST=TS$), then the exponential of the sum splits:

$e^{S+T}\xi=e^{S}e^{T}\xi,\quad\forall\xi\in\mathcal{H}$ (10)

We can actually prove this in a relatively straight-forward manner from the
definition of the operator exponential by applying the Binomial Theorem:

$\displaystyle e^{S+T}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{(S+T)^{n}}{n!}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{n!}\binom{n}{k}S^{n-k}T^{k}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{n!}\frac{n!}{(n-k)!k!}S^{n-k}T^{k}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{(n-k)!k!}S^{n-k}T^{k}.$

With this result, notice that every possible product of $S^{m}$ with $T^{n}$
occurs for $m,n\in\mathbb{Z}^{+}\cap\\{0\\}$. Thus, rewrite the sum as
follows:

$\displaystyle\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{(n-k)!k!}S^{n-k}T^{k}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}\frac{1}{m!n!}S^{m}T^{n}$
$\displaystyle=\left(\sum_{m=0}^{\infty}\frac{1}{m!}S^{m}\right)\left(\sum_{n=0}^{\infty}\frac{1}{n!}T^{n}\right)$
$\displaystyle=e^{S}e^{T}.$

In the case where $S$ and $T$ do not commute, this argument fails because the
Binomial Theorem no longer applies. It seems like there’s no way to generalize
this argument for the noncommutative case. For example, in the binomial
expansion of $(S+T)^{3}$ with $[S,T]\neq 0$, $STS\neq S^{2}T$, and so it’s
impossible to collect terms on the left and right sides of the overall sum. A
somewhat surprising result called the Trotter Product Formula is needed for
noncommutative operators, which in a strong sense approximates the above
splitting of the exponential (Equation 10). This is what we explore for the
remainder of this communication.

Before the next section, it’s important to bring up one prerequisite: unitary
evolution groups. Put simply, a unitary evolution group is a group of unitary
operators $G(t)$ for $t\in\mathbb{R}$ given by a homomorphism of
$(\mathbb{R},+)$ (i.e., for all $s,t\in\mathbb{R}$, $G(s+t)=G(s)G(t)$). An
important notion is the infinitesimal generator $T$ of a unitary evolution
group, given pointwise by

$T\xi=i\lim_{h\xrightarrow{}0}\frac{G(h)-I}{h}\xi.$ (11)

It turns out that (with some technical regularity of the mapping $t\to G(t)$,
namely weak measurability) $T$ is self-adjoint (by Stone’s Theorem on one-
parameter unitary groups). Furthermore, it also turns out that any self-
adjoint operator $T$ corresponds to the (strongly/pointwise continuous)
unitary evolution group $U_{T}(t)=e^{-itT}$. This correspondence will be
useful in formally proving the Trotter Product Formula.

Furthermore, note that the domain for $S$ and $T$ was always taken to be the
entire Hilbert space. This is because if an operator $S$ is bounded and self-
adjoint, then its dense domain $D(S)$ can be extended to all of $\mathcal{H}$
by constructing a new unique extended operator $\overline{S}$ from $S$ for
which $\overline{S}=S$ on $D(S)$. In general, domains only matter for
unbounded operators, which we consider in the next section in the statement of
the Trotter Product Formula proof.

##  2 The Trotter Product Formula

The following proof is adapted from de Oliveria’s textbook presentation [1].

######  Claim.

Let $S$ and $T$ be (potentially unbounded) self-adjoint operators on
$\mathcal{H}$. Then, for every $t\in\mathbb{R}$ and for all $\xi\in
D(S+T)=D(S)\cap D(T)=\mathcal{D}$,

$\lim_{n\xrightarrow{}\infty}\left\lVert
e^{-it(S+T)}\xi-\left(e^{-i\frac{t}{n}S}e^{-i\frac{t}{n}T}\right)^{n}\xi\right\rVert=0.$
(12)

In other words, the following strong (pointwise) operator limit holds:

$\smashoperator[]{\operatorname{s-lim}_{}^{}}\limits_{n\to\infty}\left(e^{-i\frac{t}{n}S}e^{-i\frac{t}{n}T}\right)^{n}=e^{-it(S+T)}.$

###### Proof.

Let $h\in\mathbb{R}$ such that $h\neq 0$ and $\xi\in\mathcal{D}$; then, define
$u_{h}(\xi)$ as

$u_{h}(\xi)=\frac{1}{h}\left(e^{-ihS}e^{-ihT}-e^{-it(S+T)}\right).$

Now, this can be rewritten as

$u_{h}(\xi)=\frac{e^{-ihS}-I}{h}\xi+e^{-ihS}\frac{e^{-ihT}-I}{h}\xi-\frac{e^{-ih(S+T)}-I}{h}\xi$

where $I$ is the identity operator on $\mathcal{H}$. Now, we can use the fact
that these resemble unitary evolution group generators (Equation 11). Taking
the limit $h\xrightarrow{}0$ for the first and third terms yields $S\xi$ and
$-(S+T)\xi$, respectively. For the second term, the Dominated Convergence
Theorem [2] applies, so that it yields $T\xi$ as $h\xrightarrow{}0$. Thus,
$\lim_{h\xrightarrow{}0}u_{h}(\xi)=0$.

Since $u_{h}$ is linear and bounded, and since the operator $S+T$ is closed
(because the sum of two self-adjoint operators is self-adjoint and every self-
adjoint operator is closed), one can show through the Uniform Boundedness
Principle, as in de Oliveria’s work [1], that

$\lim_{h\xrightarrow{}0}\sup_{\left\lvert s\right\rvert<\left\lvert
t\right\rvert}\left\lVert u_{h}(\xi_{s})\right\rVert=0,$ (13)

where $\xi_{s}$ is given by the unitary evolution group
$\xi_{s}=e^{-is(S+T)}$. Because the unitary evolution group is strongly
continuous, it follows that $J_{\xi,t}=\set{\xi_{s}}{\left\lvert
s\right\rvert\leq\left\lvert t\right\rvert}$ is compact and totally bounded in
$J_{\xi,t}$ under the graph norm of $S+T$. Because $J_{\xi,t}$ is totally
bounded, it can be covered by a finite number of open balls. This leads to an
interpolation argument: any $\xi_{s}\in J_{\xi,t}$ lies inside one of those
balls, and from that we can upper bound the graph norm with a distance term
that vanishes as $h\xrightarrow{}0$. Thus, since $\xi_{s}\in J_{\xi,t}$ is
arbitrary, this bound also applies to the $\xi_{s}$ that maximizes
$\left\lVert u_{h}(\xi_{s})\right\rVert$.

Now that we have shown this, we need to relate $u_{h}(\xi)$ with the
difference in Equation 12. For bounded operators $A,B$ and any
$n\in\mathbb{Z}^{+}$, one can show that

$A^{n}-B^{n}=\sum_{j=0}^{n-1}A^{j}(A-B)B^{n-1-j}.$

Substituting $A=e^{-it(S+T)/n}$ (so that $A^{n}=e^{-it(S+T)}$) and similarly
with $B=e^{-i\frac{t}{n}S}e^{-i\frac{t}{n}T}$,

$\displaystyle\left(e^{-it(S+T)/n}\right)^{n}-\left(e^{-itS/n}e^{-itT/n}\right)^{n}$
$\displaystyle=\sum_{j=0}^{n-1}\left(e^{-itS/n}e^{-itT/n}\right)^{j}\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\left(e^{-it(S+T)/n}\right)^{n-1-j}$

Therefore, we can take the norm and apply it to an arbitrary
$\xi\in\mathcal{D}$. Applying the triangle inequality along with the fact that
the norm of unitary operators is unity,

$\displaystyle\left\lVert\sum_{j=0}^{n-1}\left(e^{-itS/n}e^{-itT/n}\right)^{j}\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\left(e^{-it(S+T)/n}\right)^{n-1-j}\xi\right\rVert$
$\displaystyle\leq\sum_{j=0}^{n-1}\left\lVert\left(e^{-itS/n}e^{-itT/n}\right)^{j}\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\left(e^{-it(S+T)/n}\right)^{n-1-j}\xi\right\rVert$
$\displaystyle\leq\sum_{j=0}^{n-1}\left\lVert\left(e^{-itS/n}e^{-itT/n}\right)^{j}\right\rVert\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\left(e^{-it(S+T)/n}\right)^{n-1-j}\xi\right\rVert$
$\displaystyle=\sum_{j=0}^{n-1}\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\left(e^{-it(S+T)/n}\right)^{n-1-j}\xi\right\rVert$

Now, the only dependence we have on $j$ is in the last term of the product. If
we define $s_{j}=t(n-1-j)/n$, then that term becomes $e^{-is_{j}(S+T)}$.
Because $\left\lvert s_{j}\right\rvert<\left\lvert t\right\rvert$,
$\\{s_{j}\\}$ is a subset of the interval $[-\left\lvert
t\right\rvert,\left\lvert t\right\rvert]$. Therefore, we upper bound the
previous expression with a supremum over the entire interval:

$\displaystyle\sum_{j=0}^{n-1}\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)e^{-is_{j}(S+T)}\xi\right\rVert$
$\displaystyle\leq n\sup_{\left\lvert s\right\rvert<\left\lvert
t\right\rvert}\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)e^{-is(S+T)}\xi\right\rVert$
$\displaystyle=n\sup_{\left\lvert s\right\rvert<\left\lvert
t\right\rvert}\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\xi_{s}\right\rVert$

If we let $h=\left\lvert t\right\rvert/n$, then the last expression becomes

$\displaystyle\frac{\left\lvert t\right\rvert}{h}\sup_{\left\lvert
s\right\rvert<\left\lvert
t\right\rvert}\left\lVert\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\xi_{s}\right\rVert$
$\displaystyle=\left\lvert t\right\rvert\sup_{\left\lvert
s\right\rvert<\left\lvert
t\right\rvert}\left\lVert\frac{1}{h}\left(e^{-it(S+T)/n}-e^{-itS/n}e^{-itT/n}\right)\xi_{s}\right\rVert$
$\displaystyle=\left\lvert t\right\rvert\sup_{\left\lvert
s\right\rvert<\left\lvert t\right\rvert}\left\lVert
u_{h}(\xi_{s})\right\rVert.$

Therefore, as $n\xrightarrow{}\infty$, $h\xrightarrow{}0$ so that

$\left(e^{-i\frac{t}{n}S}e^{-i\frac{t}{n}T}\right)^{n}\xi\xrightarrow{}e^{-it(S+T)}\xi,\quad\xi\in\mathcal{D}.$

∎

##  3 Applications and Implications

Given a finite-dimensional $n\times n$ (complex) Hermitian matrix $A$, its
matrix exponential can be computed exactly by diagonalizing. By the complex
spectral theorem for finite-dimensional matrices, $A$ can be decomposed as
$A=UDU^{\dagger}$, where $U$ is a unitary matrix, $D$ is a diagonal matrix,
and $\left(\cdot\right)^{\dagger}$ denotes the conjugate transpose. Using the
fact that $A^{m}=(UDU^{\dagger})^{m}=UD^{m}U^{\dagger}$ for any
$m\in\mathbb{Z}^{+}$, it turns out that $e^{A}$ is given by

$e^{A}=Ue^{D}U^{\dagger}.$ (14)

However, when the dimensionality $n$ is very large, diagonalizing $A$ can be
computationally difficult. Therefore, an approximation is needed to compute
matrix exponentials in general instead of using Equation 14 directly.

As a very simple example, we can approximate the matrix exponential $e^{A+B}$
by Trotterization for noncommuting matrices $A$ and $B$. Using the series
definition of the matrix exponential for sufficiently large $N$,

$e^{A/N}\approx I+\frac{A}{N},\quad e^{B/N}\approx I+\frac{B}{N}.$

As a consequence of the Trotter Product Formula,

$\displaystyle e^{A+B}$ $\displaystyle\approx\left(e^{A/N}e^{B/N}\right)^{N}$
$\displaystyle\approx\left[\left(I+\frac{A}{N}\right)\left(I+\frac{B}{N}\right)\right]^{N}$
$\displaystyle=\left[I+\frac{A}{N}+\frac{B}{N}+\frac{AB}{N^{2}}\right]^{N}$
$\displaystyle\approx\left[I+\frac{A+B}{N}\right]^{N}.$

Matrix multiplication is still $O(n^{3})$, but it is generally faster and more
parallelizable than diagonalization. Furthermore, this can be implemented for
large $N=2^{m}$ using a repeated squaring algorithm [3]. Another interesting
observation is that the approximation is commutative with respect to the
inputs $A$ and $B$. As a final thought, note the similarities between this
equation and the limit definition for $e^{x}$ for $x\in\mathbb{R}$:

$e^{x}=\lim_{n\xrightarrow{}\infty}\left(1+\frac{x}{n}\right)^{n}.$

For a more practical example of this principle applied, specifically a
Trotterized Hamiltonian equation, see Whitfield et al. (2012) [4].

Trotterization is also useful for analyzing operators that individually have
”nice” operator exponentials, but when summed together have a complicated
operator exponential. A good example of this is the unitary evolution group
$e^{it(\hat{p}^{2}/2m+\hat{x})}$ corresponding to the Hamiltonian operator
$\hat{H}=\frac{\hat{p}^{2}}{2m}+\hat{x}$ (i.e., $V(x)=x$). It is difficult to
compute this exponential directly, but the exponential of $it\hat{p}^{2}/2m$
individually corresponds to the free Schrödinger kernel (which is well-
understood mathematically), and the exponential of $it\hat{x}$ individually
corresponds to a momentum translation. Thus, the exponential of the sum can be
reduced to terms much easier to analyze.

##  4 Conclusion

Thus, we have proved the Trotter Product Formula in its full generality.
Additionally, we have discussed its motivations from a practical perspective
within quantum mechanics. This combination is powerful because it means that
Trotterization can both be applied to practical quantum mechanics challenges,
such as computing quantum circuits, and theoretical challenges, such as
reducing quantum circuit complexity.

In some cases, the Trotter Product Formula admits a simpler form. When
operators $A,B$ (on some $\mathcal{H}$) are anti-commutative, such that
$AB=-BA$, then $e^{A+B}$ can be calculated using a generalization of the
Binomial Theorem to q-commutative ($q=-1$) algebras. A detailed reference and
derivation for this can be found in Scurlock (2020) [5]. This can be
practically applied to, for example, Pauli gate operations. A detailed work is
utilizing this result is Zhao & Yuan (2021) [6].

range

pages16 rangepages1

## References

  * [1] Oliveira César R. “Intermediate spectral theory and quantum dynamics” Birkhäuser, 2009
  * [2] Elias M. Stein and Rami Shakarchi “Real Analysis: Measure Theory, Integration, and Hilbert Spaces” Princeton University Press, 2005 URL: http://www.jstor.org/stable/j.ctvd58v18
  * [3] “Repeated squaring” In _Algorithmist_ URL: https://algorithmist.com/wiki/Repeated_squaring
  * [4] Jacob Biamonte James D. and Alán Aspuru-Guzik “Simulation of electronic structure Hamiltonians using quantum computers” In _Molecular Physics_ 109.5 Taylor & Francis, 2011, pp. 735–750 DOI: 10.1080/00268976.2011.552441
  * [5] Ashley Scurlock “Anticommutative Associative Algebras And The Binomial Theorem” In _Student Research Submissions_ 328, 2020 URL: https://scholar.umw.edu/student_research/328
  * [6] Qi Zhao and Xiao Yuan “Exploiting anticommutation in Hamiltonian simulation” In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 534 DOI: 10.22331/q-2021-08-31-534


easily prove that if $n_{\alpha}$ is the first index satisfying
$\sum_{i=1}^{n_{\alpha}}p_{i}\geq\alpha$, then the supremum is achieved in
$n_{\alpha}$ and

$\displaystyle\text{CVaR}_{\alpha}(\nu)$
$\displaystyle=x_{n_{\alpha}}-\frac{1}{\alpha}\sum_{i=1}^{n_{\alpha}-1}p_{i}(x_{n_{\alpha}}-x_{i})$
$\displaystyle=\frac{1}{\alpha}\left(\sum_{i=1}^{n_{\alpha}-1}p_{i}x_{i}+\left(\alpha-\sum_{i=1}^{n_{\alpha}-1}p_{i}\right)x_{n_{\alpha}}\right)\;.$

Hence in that case the CVaR can also be seen as an average when we consider
the lower part of the distribution before reaching a total mass $\alpha$.

From the general definition (1), one can also observe that for $\alpha=1$,
$\text{CVaR}_{\alpha}(\nu)=\mathbb{E}_{X\sim\nu}(X)$. Moreover, the mapping
$\alpha\mapsto\text{CVaR}_{\alpha}(\nu)$ is continuous on $(0,1]$. Thus,
considering CVaR bandits allows to smoothly interpolate between classical
bandits (that correspond to $\alpha=1$) and risk-averse problems.

We also prove in this section a technical result needed in the proof of
Theorem 2 that relates the CVaR of two distributions that are close in terms
of the $L^{\infty}$ distance defined in Appendix A.

######  Lemma 7 (CVaR of two discrete distributions in a $L^{\infty}$ ball).

Let $p$ and $q$ be the probability vectors of two discrete distribution of
with shared support $\mathcal{X}=\\{x_{1},\dots,x_{M}\\}$, then for any
$\alpha\in(0,1]$ and any $\operatorname{\varepsilon}>0$:

$C_{\alpha}(\mathcal{X},p)-\frac{M||p-q||_{\infty}}{\alpha}x_{M}\leq
C_{\alpha}(\mathcal{X},q)\leq
C_{\alpha}(\mathcal{X},p)+\frac{M||p-q||_{\infty}}{\alpha}x_{M}\,.$

###### Proof.

For any $p\in\mathcal{P}^{M}$ and $q\in\mathcal{P}^{M}$ we write for
simplicity
$\operatorname{\varepsilon}=\sup_{i\in\\{0,1,\dots,M\\}}|p_{i}-q_{i}|=||p-q||_{\infty}$,
so $\forall i$: $q_{i}-\operatorname{\varepsilon}\leq p_{i}\leq
q_{i}+\operatorname{\varepsilon}$. Let’s consider the optimisation problem
used to compute the CVaR, $\forall x$:

$\displaystyle x-\frac{1}{\alpha}\sum_{i=0}^{M}p_{i}\left(x-x_{m}\right)^{+}$
$\displaystyle\leq
x-\frac{1}{\alpha}\sum_{i=0}^{M}(q_{i}-\operatorname{\varepsilon})\left(x-x_{m}\right)^{+}$
$\displaystyle=x-\frac{1}{\alpha}\sum_{i=0}^{M}q_{i}\left(x-x_{m}\right)^{+}+\frac{\operatorname{\varepsilon}}{\alpha}\sum_{i=0}^{M}\left(x-x_{m}\right)^{+}$
$\displaystyle\leq
x-\frac{1}{\alpha}\sum_{i=0}^{M}q_{i}\left(x-x_{m}\right)^{+}+\frac{\operatorname{\varepsilon}}{\alpha}(M+1)x_{M}\,.$

Taking the supremum on all possible values $x$ on the left side of the
inequality and then on the right side ensures the result. Then, replacing $p$
by $q$ proves the other inequality. ∎

###  E.2 Proof of Lemma 1

In this section we prove Lemma 1, introduced in Section 3.

See 1

We recall that the set $\mathcal{Q}_{n}^{M}$ is defined as

$\mathcal{Q}_{n}^{M}=\left\\{(\beta,p)\in\mathbb{N}^{*n}\times\mathcal{P}^{M}:p=\frac{\beta}{n}\right\\}\;.$

The proof relies on Lemma 13 of [Riou and Honda, 2020] that we re-state below
for completeness.

######  Lemma 8 (Lemma 13 in [Riou and Honda, 2020]).

Assume $w\sim\mathrm{Dir}(\beta)$ a Dirichlet distribution over the
probability simplex $\mathcal{P}^{M}$. We assume that $\beta^{T}1=n$ and
$\forall j\in\\{1,\dots,M\\},\beta_{j}\geq 0$. We denote by
$p=\frac{1}{n}\beta$ the mean of the Dirichlet distribution. Let
$S\subset\mathcal{P}^{M+1}$ a closed convex set included in the probability
simplex. The following bound holds:

$\mathbb{P}_{w\sim\mathrm{Dir}(\beta)}\left(w\in S\right)\leq
C_{1}n^{\frac{M}{2}}\exp\left(-n\mathrm{KL}\left(p,p^{*}\right)\right)\,,$

where $p^{*}=\text{argmin}_{x\in S}\mathrm{KL}(p,x)$.

Using the notation of Section 3, for any $w\in\mathcal{P}^{M}$,
$\mathbb{P}(w\in\mathcal{S}_{\mathcal{X}}^{\alpha}(c))\leq\sum_{m=1}^{M}\mathbb{P}(w\in\mathcal{S}_{m,\mathcal{X}}^{\alpha}(c))$.
Then, using Lemma 8 for each subset $\mathcal{S}_{m,\mathcal{X}}^{\alpha}(c)$,
which is closed and convex, we have

$\mathbb{P}(w\in\mathcal{S}_{\mathcal{X}}^{\alpha}(c))\leq
C_{1}n^{M/2}\sum_{m=1}^{M}\exp\left(-n\mathrm{KL}\left(\frac{\beta}{n},p_{m}^{*}\right)\right)\;,$

where
$p_{m}^{*}=\text{argmin}_{x\in\mathcal{S}_{m,\mathcal{X}}^{\alpha}(c)}\mathrm{KL}\left(\frac{\beta}{n},x\right)$.

We conclude by using that there exists some $i\in\\{1,\dots,M\\}$ such that
$\mathcal{K}_{\inf}^{\alpha,\mathcal{X}}\left(\frac{\beta}{n},c\right)=\mathrm{KL}\left(\frac{\beta}{n},p_{i}^{*}\right)$,
and for all $m\neq i$ $\mathrm{KL}(q,p_{m}^{*})\geq\mathrm{KL}(q,p_{i}^{*})$.

###  E.3 Proof of Lemma 2

We prove the Lemma 2 presented in Section 3. See 2

We follow the sketch of the proof of Lemma 14 of [Riou and Honda, 2020] using
Equation (8). We start by stating that there exists some $p^{*}$ such that
$\mathcal{K}_{\inf}^{\alpha,\mathcal{X}}\left(\frac{\beta}{n},c\right)=\mathrm{KL}\left(\frac{\beta}{n},p^{*}\right)$.
The existence of $p^{*}$ is ensured by the fact that the function
$\mathcal{K}_{\inf}^{\alpha,\mathcal{X}}$ is the solution of the minimization
of a continuous function on a compact set. We consider the set

$\mathcal{S}_{2}=\\{w\in\mathcal{P}^{M+1}:w_{i}\in[0,p_{i}^{*}],\forall j\leq
M-1,w_{M}\geq p_{M}^{*}\\}.$

Let us remark that $\forall p\in\mathcal{S}_{2},C_{\alpha}(\mathcal{X},p)\geq
C_{\alpha}(\mathcal{X},p^{*})\geq c$. Indeed, if we transfer some of the mass
from some items of the support to largest items we can only increase the CVaR.
It then holds that

$\displaystyle\mathbb{P}_{w\sim Dir(\beta)}\left(C_{\alpha}(\mathcal{X},w)\geq
c\right)$ $\displaystyle\geq\mathbb{P}_{{w\sim
Dir(\beta)}}\left(w\in\mathcal{S}_{2}\right)$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\int_{x\in
S_{2}}\prod_{i=1}^{M}x_{i}^{\beta_{i}-1}dx$
$\displaystyle\geq\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}(p_{M}^{*})^{\beta_{M}-1}\prod_{j=1}^{M-1}\int_{x_{j}=0}^{p_{j}^{*}}x_{j}^{\beta_{j}-1}dx_{j}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}(p_{M}^{*})^{\beta_{M}-1}\prod_{j=1}^{M-1}\frac{(p_{j}^{*})^{\beta_{j}}}{\beta_{j}}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\frac{\beta_{M}}{p_{M}^{\star}}\prod_{j=1}^{M}\frac{(p_{j}^{*})^{\beta_{j}}}{\beta_{j}}\;,$

which proves the first inequality. We then exhibit the KL-divergence between
two multinomial distributions using

$\displaystyle\mathbb{P}_{{w\sim Dir(\beta)}}\left(w\in\mathcal{S}_{2}\right)$
$\displaystyle\geq\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\frac{(p_{j}^{*})^{\beta_{j}}}{\beta_{j}}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i})}\prod_{j=1}^{M}\left(\frac{p_{j}^{*}}{\beta_{j}}\right)^{\beta_{j}}\times\prod_{j=1}^{M}\beta_{j}^{\beta_{j}-1}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i}+1)}\prod_{j=1}^{M}\left(\frac{p_{j}^{*}}{\beta_{j}/n}\right)^{\beta_{j}}\times\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}}$
$\displaystyle=\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i}+1)}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}}\exp\left(-n\mathrm{KL}\left(\frac{\beta}{n},p^{\star}\right)\right)\;.$

This corresponds to the second inequality in the lemma, as we can remark that
the terms before the exponential correspond to the desired multinomial
distributions, up to a factor $1/n$. We finally provide a lower bound of this
quantity using Stirling formula (similarly to the proof scheme of [Riou and
Honda, 2020]),

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\leq n!\leq\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}\left(1+C(n)\right)\;,$

with $C(n)=\frac{1}{12n}+\frac{1}{288n^{2}}$. We then obtain that

$\displaystyle\frac{\Gamma(n)}{\prod_{i=1}^{M}\Gamma(\beta_{i}+1)}\prod_{j=1}^{M}\left(\frac{\beta_{j}}{n}\right)^{\beta_{j}}$
$\displaystyle=\frac{1}{n}\frac{n!}{n^{n}}\prod_{j=1}^{M}\frac{\beta_{j}^{\beta_{j}}}{\beta_{j}!}$
$\displaystyle\geq\sqrt{\frac{2\pi}{n}}e^{-n}\times\prod_{j=1}^{M}\frac{1}{1+C(\beta_{j})}\frac{e^{\beta_{j}}}{\sqrt{2\pi\beta_{j}}}$
$\displaystyle=\sqrt{\frac{2\pi}{n}}\prod_{j=1}^{M}\frac{1}{(1+C(\beta_{j}))\sqrt{2\pi\beta_{j}}}$
$\displaystyle\geq\sqrt{\frac{2\pi}{n}}e^{\frac{-M}{12}}\prod_{j=1}^{M}\frac{1}{(1+C(\beta_{j}))\sqrt{2\pi\beta_{j}}}$
$\displaystyle\geq\sqrt{\frac{2\pi}{n}}e^{\frac{-M}{12}}\frac{1}{\sqrt{2\pi}^{M}}\times\left(\frac{M}{n}\right)^{\frac{M}{2}}$
$\displaystyle\geq\frac{e^{-\frac{M}{12}}M^{\frac{M}{2}}}{\sqrt{2\pi}^{M-1}}n^{-\frac{M+1}{2}}$
$\displaystyle\geq\sqrt{2\pi}\left(\frac{M}{2.13}\right)^{\frac{M}{2}}\times
n^{-\frac{M+1}{2}}$ $\displaystyle=C_{M}n^{-\frac{M+1}{2}}\;,$

where we used that $C(n)$ is maximum when $n=1$ and that
$1/12\geq\log(25/288)$, and on the other hand that $\prod_{j=1}^{M}\beta_{j}$
is minimized when all $\beta_{j}$ are equal to $n/M$ (if we allow continuous
values).

###  E.4 Proof of Lemma 3

We prove Lemma 3 that is introduced in Section 3.

See 3

###### Proof.

We first use that $\\{q:C_{\alpha}(\mathcal{X},q)\geq
c\\}=\cup_{y\in[c,B]}\left\\{q\in\mathcal{P}^{n+1}:y-\frac{1}{\alpha}\mathbb{E}_{X\sim
q}\left((X-y)^{+}\right)\geq c\right\\}$ to write

$\displaystyle\mathbb{P}_{w}\left(C_{\alpha}(\mathcal{X},w)\geq c\right)\leq$
$\displaystyle\mathbb{P}_{w}\left(\sup_{y\in[c,B]}\left\\{y-\frac{1}{\alpha}\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\right\\}\geq
c\right)$
$\displaystyle\leq\int_{c}^{B}\mathbb{P}_{w}\left(y-\frac{1}{\alpha}\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\geq
c\right)\mathbb{P}_{w}\left(y=\text{argsup}_{y\in[c,B]}\left\\{y-\frac{1}{\alpha}\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\right\\}\right)dy$

The second term can have an arbitrarily complicated form, but we use the fact
that the support is bounded, which enables to uniformly bound it by $1$. We
bound the first term by its supremum on $[0,B]$, hence

$\displaystyle\mathbb{P}_{w}\left(C_{\alpha}(\mathcal{X},w)\geq c\right)\leq$
$\displaystyle
B\sup_{y\in[c,B]}\mathbb{P}_{w}\left(y-\frac{1}{\alpha}\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\geq
c\right)$ $\displaystyle\leq
B\sup_{y\in[c,B]}\mathbb{P}_{w}\left(\alpha(y-c)-\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\geq
0\right)\;.$

We then handle
$\mathbb{P}\left(\alpha(y-c)-\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\geq 0\right)$
for a fixed value of $y$. We here follow the path of Riou and Honda [2020],
using that a Dirichlet random variable $w=(w_{0},\dots,w_{n})$ can be written
in terms of $n+1$ independent random variables $R_{0},\dots,R_{n}$ following
an exponential distribution, as $w_{i}=\frac{R_{i}}{\sum_{j=0}^{n}R_{j}}$.
Using this property and multiplying by $\sum_{j=0}^{n}R_{j}$ we obtain

$\displaystyle\mathbb{P}\left(\alpha(y-c)-\sum_{i=0}^{n}w_{i}(y-x_{i})^{+}\geq
0\right)\leq$
$\displaystyle\mathbb{P}\left(\sum_{i=0}^{n}R_{i}\left(\alpha(y-c)-(y-x_{i})^{+}\right)\geq
0\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\exp\left(t\sum_{i=0}^{n}R_{i}\left(\alpha(y-c)-(y-x_{i})^{+}\right)\right)\right]\;,$

where we used Markov’s inequality for some
$t\in\left[0,\frac{1}{(y-c)\alpha}\right)$. We then isolate the first term,
writing

$\displaystyle\leq$
$\displaystyle\prod_{i=0}^{n}\mathbb{E}\left[\exp\left(R_{i}t\left(\alpha(y-c)-(y-x_{i})^{+}\right)\right)\right]$
$\displaystyle\leq$
$\displaystyle\exp\left(-\sum_{i=0}^{n}\log\left(1-t\left(\alpha(y-c)-(y-x_{i})^{+}\right)\right)\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-t\alpha(y-c)}\exp\left(-\sum_{i=1}^{n}\log\left(1-t\left(\alpha(y-c)-(y-x_{i})^{+}\right)\right)\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-t\alpha(y-c)}\left\\{\exp\left(-N\mathbb{E}_{\widehat{F}}\left[\log\left(1-t\left(\alpha(y-c)-(y-X)^{+}\right)\right)\right]\right)\right\\}\;.$

Since the term $1-t\alpha(y-c)$ can be arbitrarily small, we have to control
the values of $t$ in order to ensure that the constant before the exponential
is not too large. Hence, we choose some constant $\eta>0$, and write that for
any $t\in[0,\frac{1-\eta}{\alpha(y-c)}]$ we have

$\mathbb{P}_{w}\left(C_{\alpha}(\mathcal{X},w)\geq
c\right)\leq\frac{B}{\eta}\exp\left(-N\mathbb{E}_{\widehat{F}}\left[\log\left(1-t\left(\alpha(y-c)-(y-X)^{+}\right)\right)\right]\right)\;,$

which leads to

$\displaystyle\mathbb{P}_{w}\left(C_{\alpha}(\mathcal{X},w)\geq c\right)\leq$
$\displaystyle\frac{B}{\eta}\inf_{t\in\left[0,\frac{1-\eta}{(y-c)\alpha}\right]}\exp\left(-N\mathbb{E}_{\widehat{F}}\left[\log\left(1-t\left(\alpha(y-c)-(y-X)^{+}\right)\right)\right]\right)$
$\displaystyle\leq$
$\displaystyle\frac{B}{\eta}\exp\left(-N\sup_{t\in\left[0,\frac{1-\eta}{(y-c)\alpha}\right]}\mathbb{E}_{\widehat{F}}\left[\log\left(1-t\left(\alpha(y-c)-(y-X)^{+}\right)\right)\right]\right)\,.$

At this step the dual form of the function
$\mathcal{K}_{\inf}^{\alpha,\mathcal{X}}(\widehat{F})$ start to appear,
however, we have to handle the interval on which the supremum is taken is
$\left[0,\frac{1-\eta}{\alpha(y-c)}\right]$ instead of
$\left[0,\frac{1}{\alpha(y-c)}\right]$. As in [Riou and Honda, 2020] we will
use the concavity and the regularity of the function in the expectation in
order to conclude. We write

$\phi(t)=\frac{1}{n}\sum_{i=1}^{n}\log\left(1-t(\alpha(y-c)-(y-x_{i})^{+})\right)\;.$

As $\phi$ is concave it holds that for any
$t\in\left[\frac{1-\eta}{(y-c)\alpha},\frac{1}{(y-c)\alpha}\right)$ we have

$\phi(t)\leq\phi\left(\frac{1-\eta}{\alpha(y-c)}\right)+\frac{\eta}{\alpha(y-c)}\phi^{\prime}\left(\frac{1-\eta}{\alpha(y-c)}\right)\;.$

At this step we only need to upper bound
$\phi^{\prime}\left(\frac{1-\eta}{\alpha(y-c)}\right)$ by a constant that
would not depend on the values of $x_{1},\dots,x_{n}$ and $y$. To do so, we
use that all variables are bounded, and for any
$t\in\left[\frac{1-\eta}{(y-c)\alpha},\frac{1}{(y-c)\alpha}\right)$,

$\displaystyle\phi^{\prime}\left(t\right)$
$\displaystyle=-\mathbb{E}_{\widehat{F}}\left[\frac{(y-c)\alpha-(y-X)^{+}}{1-t\left[(y-c)\alpha-(y-X)^{+}\right]}\right]$
$\displaystyle\leq-\mathbb{E}_{\widehat{F}}\left[\frac{(y-c)\alpha-y}{1-t\left[(y-c)\alpha-y\right]}\right]$
$\displaystyle=\frac{(1-\alpha)y+\alpha c}{1-t(1-\alpha)y-t\alpha c}\;.$

We then replace $t$ by $\frac{1-\eta}{(y-c)\alpha}$, which gives

$\frac{\eta}{\alpha(y-c)}\phi^{\prime}\left(\frac{1-\eta}{(y-c)\alpha}\right)\leq\eta\frac{(1-\alpha)y+\alpha
c}{\eta\alpha(y-c)+(1-\eta)y}\;.$

Then, we use that $(1-\alpha)y+\alpha c\leq B$, and that
$\eta\alpha(y-c)+(1-\eta)y\geq(1-\eta)c\geq c$, so finally

$\frac{\eta}{\alpha(y-c)}\phi^{\prime}\left(\frac{1-\eta}{(y-c)\alpha}\right)\leq\eta\frac{(1-\alpha)B+\alpha
c}{c}\;.$

Summarizing these steps, we obtain

$\sup_{t\in\left[0,\frac{1-\eta}{(y-c)\alpha}\right]}\phi(t)\leq\sup_{t\in\left[0,\frac{1}{(y-c)\alpha}\right]}\phi(t)+\eta\frac{(1-\alpha)B+\alpha
c}{c}\;.$

Hence, we finally conclude the proof using Lemma 4, to obtain

$\mathbb{P}_{w}\left(C_{\alpha}(\mathcal{X},w)\geq
c\right)\leq\frac{B}{\eta}\exp\left(-n\left(\mathcal{K}_{\inf}^{\alpha,\mathcal{X}}(\widehat{F},c)-\eta\frac{(1-\alpha)B+\alpha
c}{c}\right)\right)\;.$

∎

###  E.5 Proof of Lemma 5

In this section we prove Lemma 5 introduced in Section 3. See 5

###### Proof.

We assume that $\mathcal{X}$ is known and ordered, i.e $x_{1}\leq
x_{2}\leq\dots\leq x_{n}$. We then write

$A=\mathbb{P}_{w\sim\mathcal{D}_{n}}\left(C_{\alpha}(\mathcal{X},w)\geq
C_{\alpha}(\mathcal{X})\right)\;.$

Thanks to the definition of the CVaR provided by Equation (1) it holds that

$A=\mathbb{P}_{w}\left(\sup_{y\in\mathcal{X}}\\{y-\frac{1}{\alpha}\sum_{i=1}^{n}w_{i}(y-x_{i})^{+}\\}\geq\sup_{z\in\mathcal{X}}\\{z-\frac{1}{\alpha
n}\sum_{i=1}^{n}(z-x_{i})^{+}\\}\right)\;.$

First, if we know $x_{1},\dots,x_{n}$ then the second term is deterministic
and the sup is actually achieved in $x_{\lceil n\alpha\rceil}$. Secondly, the
inequality is true if at least one term in the left element satisfies it, so
we can write

$\displaystyle A=$
$\displaystyle\mathbb{P}\left(\sup_{z\in\mathcal{X}}\left\\{z-\frac{1}{\alpha}\sum_{i=1}^{n}w_{i}(z-x_{i})^{+}\right\\}\geq
x_{\lceil n\alpha\rceil}-\frac{1}{\alpha n}\sum_{i=1}^{n}(x_{\lceil
n\alpha\rceil}-x_{i})^{+}\right)$ $\displaystyle\geq$
$\displaystyle\mathbb{P}\left(x_{\lceil
n\alpha\rceil}-\frac{1}{\alpha}\sum_{i=1}^{n}w_{i}(x_{\lceil
n\alpha\rceil}-x_{i})^{+}\geq x_{\lceil n\alpha\rceil}-\frac{1}{\alpha
n}\sum_{i=1}^{n}(x_{\lceil n\alpha\rceil}-x_{i})^{+}\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}w_{i}(x_{\lceil
n\alpha\rceil}-x_{i})^{+}\leq\frac{1}{n}\sum_{i=1}^{n}(x_{\lceil
n\alpha\rceil}-x_{i})^{+}\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}w_{i}\frac{B-(x_{\lceil
n\alpha\rceil}-x_{i})^{+}}{B}\geq\frac{1}{n}\sum_{i=1}^{n}\frac{B-(x_{\lceil
n\alpha\rceil}-x_{i})^{+}}{B}\right)\;.$

As the variable $\frac{B-(x_{\lceil n\alpha\rceil}-x_{i})^{+}}{B}$ belongs to
$[0,1]$ we can apply the lemma 17 of Riou & Honda and get

$A\geq\frac{1}{25n^{2}B}\left(B-\frac{1}{n}\sum_{i=1}^{n}(B-(x_{\lceil
n\alpha\rceil}-x_{i})^{+})\right)=\frac{1}{25n^{3}B}\sum_{i=1}^{n}(x_{\lceil
n\alpha\rceil}-x_{i})^{+}\;.$

We conclude by simply omitting all the terms except $(x_{\lceil
n\alpha\rceil}-x_{1})$ in the sum. ∎

##  Appendix F Brown-UCB a.k.a U-UCB

In this section, we present the instanciation of the U-UCB algorithm of
[Cassel et al., 2018] for CVaR bandits, and discuss its links with the Brown-
UCB idea proposed by [Tamkin et al., 2020], which propose to build a UCB
strategy based on concentration inequalities proposed by [Brown, 2007].

###  F.1 Explicit form of U-UCB

The U-UCB bonus is written as $f\left(\frac{C\log t}{N_{k}(t-1)}\right)$ for
some constant $C$ and some function $f$ defined as

$f(x)=\max\left\\{2b\left(\frac{x}{a}\right)^{1/2},2b\left(\frac{x}{a}\right)^{q/2}\right\\}.$

Following the Definition 3 in [Cassel et al., 2018] we can find the values of
the constants $a$, $b$ and $q$. The DKW inequality gives $a=1$, while $b$ and
$q$ are found as the smallest parameters satisfying the following inequality:

$|\text{CVaR}_{\alpha}(F)-\text{CVaR}_{\alpha}(G)|\leq
b(||F-G||_{\infty}+||F-G||_{\infty}^{q})$

If the distributions are upper bounded by some constant $U$ then we have from
[Tamkin et al., 2020] that it is sufficient to choose $b=\frac{U}{2\alpha}$
and $q=1$. This yields the following explicit form for the U-UCB stratey:

$A_{t+1}^{\text{U-UCB}}=\underset{k\in[K]}{\text{argmax}}\left[\text{CVaR}_{\alpha}(\widehat{\nu}_{k})+\frac{U}{\alpha}\sqrt{\frac{C\log
t}{2N_{k}(t)}}\;\right].$

In our experimental study, with use the constant $C=2$ in the index of U-UCB
(and $U=1$ as we consider distributions that are bounded in $[0,1]$). This
choice is motivated by the fact that [Cassel et al., 2018] show that for
$C>2$, U-UCB has a logarithmic _proxy regret_. As explained by [Tamkin et al.,
2020], the proxy regret is an upper bound on the CVaR regret, hence U-UCB is
guaranteed to have logarithmic CVaR regret in our setting.

Interestingly, by following an approach suggest by [Tamkin et al., 2020], we
can recover the exact same algorithm as U-UCB, an propose a simple analysis of
this algorithm directly in terms of CVaR regret.

###  F.2 Brown-UCB and its analysis

The authors of [Tamkin et al., 2020] propose to build on concentration
inequalities for the empirical CVaR given by [Brown, 2007] to derive a UCB
strategy in which the index of each arm adds a confidence bonus to the CVaR of
its empirical distribution. However, their derivation of this Brown-UCB
algorithm is not correct as they use the concentration inequalities originally
given by [Brown, 2007] for the _loss_ version of the CVaR. We propose a fix in
this section, which consists in adapting the Brown inequalities to the
_reward_ version of the CVaR which we consider in this paper.

For bounded distributions there is a clear symmetry between the the two
definitions of CVaR. In particular, for any distribution $\nu$ supported in
$[0,B]$

$\text{CVaR}_{\alpha}(\nu)=B-\text{CVaR}_{\alpha}^{\text{loss}}(B-\nu)\;,$

where $1-\nu$ denotes the distribution of $1-X$ with $X\sim\nu$ and we write
respectively CVaR and $\text{\text{CVaR}}^{\text{loss}}$ the reward and loss
version of CVaR.

###### Proof.

$\displaystyle\text{CVaR}_{\alpha}(\nu)$
$\displaystyle=\sup_{x\in[0,B]}\left\\{x-\frac{1}{\alpha}\mathbb{E}\left((x-X)^{+}\right)\right\\}$
$\displaystyle=\sup_{x\in[0,B]}\left\\{x-\frac{1}{\alpha}\mathbb{E}\left((B-X-(B-x))^{+}\right)\right\\}$
$\displaystyle=\sup_{y\in[0,1]}\left\\{B-y-\frac{1}{\alpha}\mathbb{E}\left((B-X-y)^{+}\right)\right\\}$
$\displaystyle=B-\inf_{y\in[0,1]}\left\\{y+\frac{1}{\alpha}\mathbb{E}\left((B-X-y)^{+}\right)\right\\}$
$\displaystyle=1-\text{CVaR}_{\alpha}^{\text{loss}}(B-\nu)$

∎

######  Remark 4.

Applying the same trick to $Y=-X$ provide that for a real random variable $X$
then $\text{CVaR}_{\alpha}(X)=-\text{CVaR}_{\alpha}^{\text{loss}}(-X)$.

This observation easily yield the following concentration inequalities, which
are the counterpart of the Brown inequalities for the reward version of the
CVaR.

######  Lemma 9 (Brown’s inequalities for $\text{CVaR}_{\alpha}$).

If we write $\widehat{c}_{n}^{\alpha}$ the CVAR of an empirical distribution
from $n$ variables drawn from a distribution $\nu$ supported in $[0,B]$ and
$\emph{CVAR}_{\alpha}(\nu)=c^{\alpha}$, we have:

$\displaystyle\mathbb{P}(\widehat{c}_{n}^{\alpha}\geq
c^{\alpha}+\operatorname{\varepsilon})\leq
3\exp\left(-\frac{\alpha}{5}\left(\frac{\operatorname{\varepsilon}}{B}\right)^{2}n\right)$
$\displaystyle\mathbb{P}(\widehat{c}_{n}^{\alpha}\leq
c^{\alpha}-\operatorname{\varepsilon})\leq\exp\left(-2\left(\frac{\alpha\operatorname{\varepsilon}}{B}\right)^{2}n\right)$

We note that the upper and lower deviation have their probability bounded by a
term whose scaling in $\alpha$ is different. By interverting the two
inequalities, [Tamkin et al., 2020] proposed a “Brown-UCB” algorithm with an
confidence bonus scaling in $1/\sqrt{\alpha}$ instead of $1/\alpha$ and
obtained a regret bound that was actually contradicting the lower bound of
Theorem 1.

##### Expression of Brown-UCB

The inequalities in Lemma 9 permit to propose a UCB algorithm of the form

$A_{t+1}^{\text{Brown-UCB}}=\underset{k\in[K]}{\text{argmax}}\
\mathrm{UCB}_{k}(N_{k}(t),t)$

where
$\mathrm{UCB}_{k}(n,t)=\widehat{c}_{k,n}^{\alpha}+\frac{U}{\alpha}\sqrt{\frac{f(t)}{2n}}$,
where $\widehat{c}_{k,n}^{\alpha}$ is the CVaR of level $\alpha$ of the
empirical distribution of the $n$ first observations from arm $k$ and $f(t)$
is an increasing function of $t$ that will be specified later in the analysis.
Indeed, one can easily check that

$\mathbb{P}(\mathrm{UCB}_{k}(t,n)\leq
c^{\alpha})=\mathbb{P}\left(\widehat{c}_{k,n}^{\alpha}\leq
c_{k}^{\alpha}-\frac{U}{\alpha}\sqrt{\frac{f(t)}{2n}}\right)\leq e^{-f(t)},$

which justifies that fact that $\mathrm{UCB}_{k}(t,n)$ is an upper confidence
bound on the CVaR of arm $k$.

Interestingly, we observe that for the choice $f(t)=C\log(t)$, Brown-UCB
coincides with the U-UCB algorithm. We upper bound below the CVaR regret of
Brown-UCB (or U-UCB) for $C>2$, and recover that this regret is indeed
logarithmic.

We analyze Brown-UCB for distributions supported in $[0,U]$ and a threshold
function $f(t)=(2+\varepsilon)\log(t)$ for some $\varepsilon>0$. For every
sub-optimal arm $k$, we start with the classical decomposition

$\displaystyle\mathbb{E}\left[N_{k}(T)\right]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k)]$
$\displaystyle=1+\sum_{t=K}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{1}(N_{1}(t),t)\leq
c_{1}^{\alpha})]+\sum_{t=K}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{k}(N_{k}(t),t)\geq
c_{1}^{\alpha})]\;.$

We analyze separately these two terms. We use a union bound on the values of
$N_{1}(t)$ and the second inequality in Lemma 9 to handle the first term:

$\displaystyle\sum_{t=K}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{1}(t)\leq
c_{1}^{\alpha})]$
$\displaystyle\leq\sum_{t=K}^{T}\sum_{n=1}^{t}\mathbb{P}\left(N_{1}(t)=n,\mathrm{UCB}_{1}(n,t)\leq
c_{1}^{\alpha}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{n=1}^{t}\mathbb{P}\left(\widehat{c}_{1,n}^{\alpha}\leq
c_{1}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(t)}{2n}}\right)$
$\displaystyle\leq\sum_{t=1}^{T}t\exp(-f(t))\;.$

With the choice $f(t)=(2+\varepsilon)\log(t)$, we get
$\sum_{t=K}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{1}(t)\leq
c_{1}^{\alpha})]=O(1)$.

To handle the second term, we write the following:

$\displaystyle\sum_{t=K}^{T-1}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{k}(t)\geq
c_{1}^{\alpha})]$
$\displaystyle\leq\sum_{t=K}^{T-1}\sum_{n=1}^{t}\mathbb{E}[\mathds{1}(A_{t+1}=k,N_{k}(t)=n,\mathrm{UCB}_{k}(N_{k}(t),t)\geq
c_{1}^{\alpha})]$
$\displaystyle\leq\sum_{t=K}^{T-1}\sum_{n=1}^{t}\mathbb{E}\left[\mathds{1}\left(A_{t+1}=k,N_{k}(t)=n,\widehat{c}_{k,n}^{\alpha}\geq
c_{1}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(t)}{2n}}\right)\right]$
$\displaystyle\leq\sum_{t=K}^{T-1}\sum_{n=1}^{t}\mathbb{E}\left[\mathds{1}\left(A_{t+1}=k,N_{k}(t)=n,\widehat{c}_{k,n}^{\alpha}\geq
c_{1}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(T)}{2n}}\right)\right]$
$\displaystyle\leq\sum_{n=1}^{T}\mathbb{E}\left[\mathds{1}\left(\widehat{c}_{k,n}^{\alpha}\geq
c_{1}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(T)}{2n}}\right)\sum_{t=K}^{T-1}\mathds{1}\left(A_{t+1}=k,N_{k}(t)=n\right)\right]$
$\displaystyle\leq\sum_{n=1}^{T}\mathbb{E}\left[\mathds{1}\left(\widehat{c}_{k,n}^{\alpha}\geq
c_{1}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(T)}{2n}}\right)\right]$
$\displaystyle=\sum_{n=1}^{T}\mathbb{P}\left(\widehat{c}_{k,n}^{\alpha}\geq
c_{k}^{\alpha}+\left(\Delta_{k}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(T)}{2n}}\right)\right)$

Let $\beta>0$ to be chosen later. Letting
$n_{0}(T)=\left\lceil\frac{f(T)}{2\alpha^{2}(1-\beta)^{2}(\Delta_{k}^{\alpha})^{2}}\right\rceil$,
we have that for all $n\geq n_{0}(T)$,

$\left(\Delta_{k}^{\alpha}-\frac{1}{\alpha}\sqrt{\frac{f(T)}{2n}}\right)\geq\beta\Delta_{k}^{\alpha}.$

Therefore, using the first inequality in Lemma 9,

$\displaystyle\sum_{t=1}^{T}\mathbb{E}[\mathds{1}(A_{t+1}=k,\mathrm{UCB}_{k}(t)\geq
c_{1}^{\alpha})]$ $\displaystyle\leq
n_{0}(T)+\sum_{n=n_{0}(T)+1}^{T}\mathbb{P}\left(\widehat{c}_{k,n}^{\alpha}\geq
c_{k}^{\alpha}+\beta\Delta_{k}^{\alpha}\right)$ $\displaystyle\leq
n_{0}(T)+\sum_{n=1}^{T}3\exp\left(-\frac{\alpha}{5}\beta^{2}(\Delta_{k}^{\alpha})^{2}n\right)$
$\displaystyle=n_{0}(T)+O(1).$

Choosing for example $\beta=1-\sqrt{1/2}$ yields that Brown-UCB with
$f(t)=(2+\varepsilon)\log(T)$ satisfies

$\mathbb{E}[N_{k}(T)]\leq\frac{(2+\varepsilon)\log(T)}{\alpha^{2}(\Delta_{k}^{\alpha})^{2}}+O_{\varepsilon}(1).$

This permits to prove that Brown-UCB has a regret of the same order of
magnitude as the CVaR-UCB algorithm proposed by [Tamkin et al., 2020].

##  Appendix G Complementary Experiments

In this section we provide a more complete overview of the results of our
experiments introduced but not detailed in Section 4. The first part of this
section contains a comprehensive set of experiments on synthetic data in order
to illustrate particular properties of the M-CVTS and B-CVTS algorithms. The
second part provides additional experiments performed with the DSSAT crop-
simulator, that complete the first set of experiments provided in Section 4.

###  G.1 Experiments on synthetic examples

Before testing the algorithms on a real-world use-case we performed
experiments on simulated data in order to illustrate their empirical
properties compared to existing UCB-like algorithms. For all the experiments
we generally consider $\alpha$ ranging in $\\{10\%,50\%,90\%\\}$.

####  G.1.1 Experiments on Multinomial arms

We first introduce some experiments with multinomial arms in order to check
the empirical performance of the M-CVTS algorithm. We ackowledge that M-CVTS
has some advantage over its competitors as it is aware of the full support of
the multinomial distribution while the UCBs only know an upper bound. For this
reason we do not comment extensively on the performance gaps between the
algorithms, but we are more interested in checking the asymptotic optimality
of M-CVTS. Indeed, for multinomial distribution we implemented the lower bound
described in Section 3 and illustrated it in Figures 7 and 8 for one of our
experiments.

##### Multinomial Experiments 1 to 4: Choice of the distributions

We run M-CVTS on different multinomial bandit problems in which all arms have
the common support $(x_{0},x_{1},\dots,x_{10})=\\{0,0.1,\dots,0.9,1\\}$. In
this setting we consider 5 multinomial distributions, that we write
$(q_{i})_{i\in\\{1,\dots,5\\}}$, and visually represent in Figure 3. Those
arms provide different distributions with interesting shapes and properties,
using simple formulas to generate the probabilities.

As the order of arms’ CVaR varies substantially depending on the value of
$\alpha$, a bandit algorithm aiming at minimizing the CVaR regret is
necessary. For instance $q_{1}$ is the best arm for $\alpha\leq 20\%$, $q_{3}$
for $\alpha\in[30\%,55\%]$, and $q_{5}$ for $\alpha\geq 55\%$. Furthermore,
$q_{5}$ is typically a distribution that a risk-averse practitioner would like
to avoid as its expectation is large at the cost of potential high losses,
while $q_{1}$ is not satisfying for someone maximizing the expected reward due
to the high concentration around $0.5$. Interestingly, despite different
shapes $q_{2}$ and $q_{4}$ are actually close in terms of CVaR, hence a bandit
problem defined over these two distributions only is hard to solve. We
illustrate the CVaRs of these different arms as a function of $\alpha$ in
Figure 4.

We implemented four experiments with different subsets of these arms, for
$\alpha$ in $\\{10\%,50\%,90\%\\}$:

  * •

Experiment $1$, $Q_{1}=[q_{1},q_{2},q_{3},q_{4},q_{5}]$

  * •

Experiment $2$ (Hard for risk-averse learner), $Q_{1}=[q_{4},q_{5}]$

  * •

Experiment $3$ (Large gaps), $Q_{1}=[q_{1},q_{2},q_{3}]$

  * •

Experiment $4$ (Small gaps), $Q_{1}=[q_{2},q_{4}]$

##### Experimental setup

Each experiment consists in $N=5000$ runs of each algorithm (namely U-UCB,
CVaR-UCB and M-CVTS) up to a horizon $T=10000$. We report the results in
Tables 8, 8, 8 and 8.

##### Analysis of the results

The results reveal that M-CVTS clearly outperforms the baselines for any level
of $\alpha$ in all experiments. Experiment $4$ is the only one for which the
gap is not very large, because this CVaR bandit problem is a hard instance,
and no algorithm reaches its asymptotic regime after $10^{4}$ time steps.
However, it is interesting to notice that M-CVTS can be better than the
baselines even when it is not in this asymptotic regime.

For Experiment $1$ and $\alpha\in\\{10\%,90\%\\}$ we display the regret curves
of both M-CVTS, CVaR-UCB and U-UCB in Figure 5 and Figure 6. We also add a
$5\%-95\%$ confidence bound around each curve. We see that the regret of U-UCB
is linear for this time horizon with $\alpha=10\%$, while the regrets of CVaR-
UCB and M-CVTS have similar shapes and confidence intervals for the two values
of $\alpha$, hence they appear to be more robust to the parameter $\alpha$
than U-UCB in this setting. Nonetheless, in both cases M-CVTS largely
outperforms CVaR-UCB. It is also interesting to remark that M-CVTS becomes
clearly better than its competitors very early in the competition, which shows
that M-CVTS can be a good choice for practitioners who would consider shorter
horizons.

##### Optimality of M-CVTS

Still on Experiment $1$, we illustrate in Figures 7 and 8 the asymptotic
optimality of M-CVTS by representing its regret (in logarithmic scale on the
$x$ axis) along with the asymptotic lower bound described in Section 3, again
for $\alpha\in\\{10\%,90\%\\}$. The fact that M-CVTS matches the asymptotic
lower bound is verified in this experiment, as the regret of M-CVTS converges
to a straight line which is parallel to the lower bound (still in logarithmic
scale on the $x$ axis). The small difference of slopes in Figure 7 might be
due to the fact that we used a solver to solve the optimization problem
involved in the lower bound, and we noticed that this solver was less precise
for small values of $\alpha$.

Figure 3: Visual representation of multinomial distributions
$q_{1},q_{2},q_{3},q_{4},q_{5}$

Figure 4: CVaR of the distributions $(q_{i})_{i\in\\{1,\dots,5\\}}$ as a
function of $\alpha$

vertical lines are the thresholds $\alpha=\\{5\%,50\%,90\%\\}$.

Table 5: Results for Multinomial Experiment 1 at $T=10000$ for 5000 replications. Standard deviations in parenthesis. $Q=[q_{1},q_{2},q_{3},q_{4},q_{5}]$ $\alpha$ | U-UCB | CVaR-UCB | M-CVTS
---|---|---|---
$10\%$ | 549.4 (3.3) | 235.9 (19.6) | 35.1 (14.7)
$50\%$ | 283.6 (16.3) | 181.5 (17.9) | 65.4 (30.6)
$90\%$ | 221.1 (23.7) | 220.5 (23.7) | 43.7 (36.3)

Table 6: Results for Multinomial Experiment 2 at $T=10000$ for 5000 replications. for 5000 replications. $Q=[q_{4},q_{5}]$ $\alpha$ | U-UCB | CVaR-UCB | M-CVTS
---|---|---|---
$10\%$ | 44.5 (0.4) | 26.7 (5.0) | 11.9 (7.8)
$50\%$ | 137.5 (18.9) | 55.4 (13.6) | 17.7 (23.8)
$90\%$ | 53.3 (11.0) | 54.3 (11.4) | 8.0 (5.6)

Table 7: Results for Multinomial Experiment 3 at
$T=10000$ for 5000 replications. $Q=[q_{1},q_{2},q_{3}]$ $\alpha$ | U-UCB | CVaR-UCB | M-CVTS
---|---|---|---
$10\%$ | 360.1 (3.9) | 149 (16.8) | 23.0 (13.8)
$50\%$ | 217.2 (17) | 117.6 (18.7) | 29.0 (25.6)
$90\%$ | 124.2 (16.5) | 116.6 (16.0) | 17.3 (10.8)

Table 8: Results for Multinomial Experiment 4 at
$T=10000$ for 5000 replications. $Q=[q_{2},q_{4}]$ $\alpha$ | U-UCB | CVaR-UCB | M-CVTS
---|---|---|---
$10\%$ | 17.7 (0.2) | 16.4 (2.2) | 13.6 (8.6)
$50\%$ | 79 (7.8) | 68.3 (14.4) | 27.8 (26.4)
$90\%$ | 27.1 (4.4) | 26.0 (4.3) | 21.3 (15.6)

Figure 5: Experiment 1 with Multinomial arms,
all algorithms, $\alpha=10\%$ Figure 6: Experiment 1 with Multinomial arms,
all algorithms, $\alpha=90\%$

Figure 7: Experiment 1 with Multinomial arms,
regret of M-CVTS and lower bound (abscissa log scale),
$\alpha=10\%$ Figure 8: Experiment 1 with Multinomial arms,
regret of M-CVTS and lower bound (abscissa log scale)
$\alpha=90\%$

####  G.1.2 Experiments on general Bounded distributions: Truncated Gaussian
Mixtures

In this section we consider bounded multi-modal distributions, built by
truncated Gaussian Mixture models in $[0,1]$. We simply call these
distributions Truncated Gaussian Mixtures (TGM for short). We first remark
that these distributions are not continuous because they can have a positive
mass in $0$ and $1$, but it is still a good illustrative example to check the
performance of B-CVTS. Indeed, we also performed the same exact experiments
making the distributions continuous (instead of truncating, we re-sampled
observations until they lied in $[0,1]$) and the results were deemed to be
exactly the same.

##### Continuous Experiments 1 to 4: Bi-modal Gaussian mixtures

We first consider experiments with two modes, each mode being equiprobable and
having the same variance for simplicity ($\sigma=0.1$) in all experiments. It
is interesting to compare settings where some arms have modes that are both
close to $0.5$, and where other arms have a large mass of probability close to
the two support bounds (one mode close to $1$ and one close to $0$).

We experiment 4 possible configurations of the modes, given by:

  * •

$\mu_{1}=(0.2,0.5)$

  * •

$\mu_{2}=(0,1)$

  * •

$\mu_{3}=(0.3,0.6)$

  * •

$\mu_{4}=(0.1,0.65)$

We indifferently call the arms by their means (saying arm $\mu_{1}$ for the
TGM arm with the parameter $\mu_{1}$ along with the parameters we fixed).

As for the discrete setup in the previous section, we highlight some basic
properties of their CVaRs: the distribution with parameter $\mu_{2}$ has a
larger mean than the one with $\mu_{1}$, but the $50\%$ CVaR of $\mu_{1}$ is
larger. We represented the CVaR for each parameter for different values of
$\alpha\in(0,1]$ in Figure 9, with the thresholds
$\alpha\in\\{0\%,10\%,90\%\\}$ represented by the vertical lines.
Interestingly, with these arms the most difficult problems are not necessarily
those with smallest values of $\alpha$. Indeed, for $\alpha=80\%$ it may be
particularly difficult to choose between $\mu_{2}$ and $\mu_{3}$, or between
$\mu_{1}$ and $\mu_{4}$, while $\mu_{3}$ is the clear winner for $\alpha=10\%$
due to the distribution being very concentrated around $0.5$. Furthermore, the
distribution $\mu_{2}$ is very concentrated around the bounds of the support
but has a larger mean than the others, hence it becomes the best arm for
values of $\alpha$ that are close to $1$.

Figure 9: CVaR of each TGM distribution $\nu_{i}$ (with centers $\mu_{i}$),
$i=1,\dots,4$ for different values of $\alpha$

We run the algorithms for $\alpha=10\%,50\%$ and $90\%$ on four bandit
problems with the following respective distributions:

  * •

$\nu_{1}=(\mu_{1},\mu_{2})$

  * •

$\nu_{2}=(\mu_{1},\mu_{3})$

  * •

$\nu_{3}=(\mu_{1},\mu_{4})$

  * •

$\nu_{4}=(\mu_{i})_{i\in\\{1,2,3,4\\}}$

##### Results

In Tables 9, 10, 11 and 12 we report the results for the four considered
problems (mean regret and standard deviation at $T=10000$). We also provide
the regret curves, as for multinomial distributions, in order to check the
logarithmic order of the regret of B-CVTS and its rate when $T$ is large.

Table 9: Results for TGM Experiment 1 at $T=10000$ for 5000 replications. Standard deviations in parenthesis.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$10\%$ | 274.9 (1.8) | 5.3 (1.5) | 1.1 (0.5)
$50\%$ | 127.0 (19.3) | 135.3 (41.1) | 29.8 (17.2)
$90\%$ | 80.5 (10.4) | 53.5 (6.7) | 10.2 (17.9)

Table 10: Results for TGM Experiment 2 at $T=10000$ for 5000 replications.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$10\%$ | 373.7 (4.1) | 72.8 (9.6) | 4.1 (2.3)
$50\%$ | 135.8 (8.9) | 37.9 (7.5) | 5.5 (2.7)
$90\%$ | 62.6 (7.1) | 43.9 (5.1) | 5.0 (1.8)

Table 11: Results for TGM Experiment 3 at $T=10000$ for 5000 replications.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$10\%$ | 269.4 (1.8) | 23.2 (4.8) | 2.8 (1.5)
$50\%$ | 138.5 (12.4) | 71.8 (19.0) | 14.7 (8.3)
$90\%$ | 53.1 (6.6) | 34.5 (6.6) | 20.2 (22.4)

Table 12: Results for TGM Experiment 4 at $T=10000$ for 5000 replications.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$10\%$ | 958.9 (4.8) | 230.5 (25.3) | 10.4 (3.2)
$50\%$ | 318.4 (12.2) | 147.7 (17.9) | 21.2 (6.4)
$90\%$ | 154.3 (11.9) | 119.5 (11.7) | 25.1 (14.1)

Again, the TS approach significantly outperforms the two UCB algorithms, which
is a very interesting result: contrarily to the multinomial case, this time
the three algorithms had the same level of information on arms’ distributions.
B-CVTS is consistently the best for all four problems we implemented and for
all $\alpha$ levels.

##### Continuous Experiment 5: Robustness to small $\alpha$

We then check the robustness of B-CVTS to a smaller value of the parameter
$\alpha$ by setting $\alpha=1\%$, referred as Experiment 5. The bandit of
Experiment 5 has six TGM arms with respective mean and variance parameters
$\mu_{135}=(0.3,0.6)$, $\mu_{246}=(0.25,0.65)$, $\sigma_{12}=0.05$,
$\sigma_{34}=0.06$, $\sigma_{56}=0.07$. This experiment allows to additionally
check if adding different variances to the arms affects the performance of the
algorithms. However, we keep the probability of each mode to $0.5$. This
problem provides the following CVaR values for each arm at level $1\%$,
respectively: $c^{0.01}_{1:6}=[0.18,0.13,0.15,0.10,0.13,0.08]$. The results
are reported in Table 13, in which we observe a very large performance gap
between B-CVTS and UCB algorithms. This is particularly interesting because it
shows that the UCB algorithms are not really able to learn for very small
values of $\alpha$ (indeed $\alpha=1\%$ is very small when drawing only a
total number of $10^{4}$ observations) before the horizon becomes extremely
large. We already observed this behavior for CVaR-UCB in previous experiments,
but this time we can see as well that its average regret is even higher than
the one of U-UCB, and its variance spiked. On the other hand, B-CVTS seems to
learn smoothly even for $\alpha=1\%$, as its average regret only doubles
between $T=1000$ and $T=5000$, and increases even less between $T=5000$ and
$T=10000$.

Table 13: Results for TGM Experiment 5 ($\alpha=1\%$) at $T=10000$ for 5000 replications. T | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
1000 | 49.1 (0.3) | 53.2 (5.6) | 18 (37)
5000 | 245 (1.1) | 263.2 (24.7) | 35.5 (51)
10000 | 489.1 (2.2) | 518.4 (45.0) | 41 (66)
Table 14: Results for TGM Experiment 6, at $T=10000$ averaged over 400 random instances with $K=30$ truncated Gaussian mixtures with 10 modes. T | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
10000 | 2149.9 (263) | 2016.0 (265) | 210.9 (6.4)
20000 | 4276.4 (538) | 3781.3 (521) | 237.1 (15.4)
40000 | 8493.4 (1085) | 6894.1 (985) | 263.5 (17.9)

##### Continuous Experiment 6: Random Problems with more modes and more arms

Finally, we further check the robustness of B-CVTS to more arms and more
diverse distribution profiles by increasing the number of possible modes. To
do so, we implement an experiment with $K=30$ arms, with TGM distributions
with 10 modes exhibiting different means and variances, which covers a large
variety of shapes of distributions. All of those parameters are drawn
uniformly at random, and we summarize their distributions as
$(\mu,\sigma)\sim\mathcal{U}([0.25,1]^{10}\times[0,0.1]^{10})$, and
$p\sim\mathcal{D}_{10}$ (uniform distribution on the simplex, presented in
Section 3). We name this setting TGM Experiment 6. The results of this
experiment are reported in Table 14 for a parameter $\alpha=0.05$ averaged
over 400 random instances. Again, we choose a smaller value for $\alpha$ than
in the previous extensive sets of experiments because problems with small
$\alpha$ seem to be more challenging. The results highlight that best
performances are obtained by B-CVTS.

##### Conclusions

We preliminary evaluated the CVaR bandit algorithms on synthetic problems
before testing them on realistic-world bandit environment in the next section.
These experiments seem to highlight a greater robustness of B-CVTS to many
different settings regarding different parameters: $\alpha$ level, the number
of arms $K$ and the different possible shapes of the distributions (symbolized
by the number of modes in our synthetic experiments). In particular, B-CVTS is
the only algorithm that has not shown to be affected by the value of $\alpha$,
as the two UCB algorithms had their respective performances degraded in some
extent depending on $\alpha$ values.

###  G.2 Experiments with DSSAT crop-model

In this section we keep comparing B-CVTS with U-UCB and CVaR-UCB for
$\alpha\in\\{5\%,10\%,80\%\\}$ as described in section 4. DSSAT is still
parameterized with the same challenging conditions, but we generate two
different problems thanks to the crop-simulator. For both presented
experiments we consider $N=1040$ runs of each algorithm up to a time horizon
$T=10000$. As explained in section 4, all DSSAT arms’ distributions are
empirically estimated from $10^{6}$ samples in both experiments.

#####  DSSAT Experiment 1: 7 armed planting date bandit

We consider a bandit instance that consists of 7 arms, each arm corresponds to
a planting date spaced of 15 days from the previous one. An illustration of
the underlying distributions is given in Figure 10. In this case, the best arm
is consistent with all values of $\alpha$, as shown in Table 16. Nevertheless,
arms exhibit different gaps when considering different values of $\alpha$.
This experiment intends to evaluate B-CVTS robustness for a greater number of
real-world alike arms with a diversity of reward distribution shapes.

The results of this experiment are reported in Table 18. The regret curves for
the three algorithms, with considered values of $\alpha$ parameter are
illustrated in Figures 12, 14, and 16.

In this experiment, by exhibiting superior performances B-CVTS appears to be
more robust than the UCB CVaR bandit algorithms relative to an increase in the
number of arms. In practice for the planting-date problem, a global, few
months planting-window is known but needs further refinements e.g. to identify
the best two-week time slot for planting. That is to say, the number of arms
is unlikely to be greater that what has been tested in this experiment, making
B-CVTS a particularly fit-for-purpose candidate in this setup.

#####  DSSAT Experiment 2: Impact of support upper bound over-estimation

This configuration is the same than the one presented in Section 4, but here
we largely over-estimate the yield upper-bound to 30 t/ha, when a close to
reality yield upper bound is about 10 t/ha. From an agronomic point of view,
this yield value is a very unlikely over-estimation in the given conditions.
This experiment intends to empirically evaluate how a rough arms’ upper-bound
estimation affects algorithms’ performances, when little expert knowledge is
available. An illustration of the underlying distributions and how the upper-
bound estimation is exaggerated is given in Figure 11 and corresponding
metrics are reported in Table 16.

We provide the results of this experiment in Table 18, and display the regret
curves in Figures 13, 15, and 17.

Experiment 2 addresses one possible concern for practitioners: the
prerequisite of rewards’ support upper bound. We empirically demonstrate that
with realistic simulations, when a highly over-estimated, unrealistic support
upper-bound is given – triple of expert’s estimation –, B-CVTS keeps
outperforming UCB-like CVaR bandit algorithms. We shown that this over-
estimation did not affect B-CVTS performances compared to the situation of
correct support upper-bound identification as presented in Section 4. In
particular, it even slightly improved its performance for $\alpha=80\%$. This
result is counter-intuitive, but it can be explained by the fact that the
extra exploration induced by the larger upper bound may have sped up learning
in this particular case, improving overall performances. On the other hand,
CVaR-UCB seems much more impacted by this over-estimation (regret is
respectively increased by about $150\%$, $75\%$ and $78\%$ for
$\alpha\in\\{5\%,20\%,80\%\\}$). Similarly U-UCB shown altered performances,
despite its already unsatisfying results when considering the true upper
bound.

##### Conclusions

B-CVTS appeared to be a satisfying candidate for real-world alike problems, as
shown with the planting date bandits. We empirically showed the B-CVTS was
best able to deal with a greater number of planting date arms than its UCB
counterparts. We showed as well that B-CVTS remained the best performer
despite considering a very unlikely support upper-bound estimation. We think
that in many physical resource-based problems, this should be reassuring for
practitioners, in particular when compared with UCB algorithms’ sensibility to
the input upper bound.

Figure 10: Experiment 1, 7 armed DSSAT environment empirical distributions ;
$10^{6}$ samples.  Figure 11: Experiment 2, 4 armed DSSAT environment
empirical distributions with over-estimated support ; $10^{6}$ samples.

Table 15: DSSAT Experiment 1 distribution metrics in kg/ha estimated from $10^{6}$ samples..  day (action) |  |  | $\text{CVaR}_{\alpha}$ |
---|---|---|---|---
| $5\%$ | $20\%$ | $80\%$ |  $100\%$ (mean)
057 | 0 | 448 | 2238 | 3016
072 | 46 | 627 | 2570 | 3273
087 | 287 | 1059 | 3074 | 3629
102 | 538 | 1515 | 3120 | 3586
117 | 808 | 1832 | 3299 | 3716
132 | 929 | 1955 | 3464 | 3850
147 | 1122 | 2203 | 3745 | 4112

Table 16: DSSAT Experiment 2 distribution metrics in kg/ha estimated from $10^{6}$ samples. day (action) |  |  | $\text{CVaR}_{\alpha}$ |
---|---|---|---|---
| $5\%$ | $20\%$ | $80\%$ |  $100\%$ (mean)
057 | 0 | 448 | 2238 | 3016
072 | 46 | 627 | 2570 | 3273
087 | 287 | 1059 | 3074 | 3629
102 | 538 | 1515 | 3120 | 3586

Table 17: Results for DSSAT Experiment 1, empirical regret at $T=10000$ in t/ha for 1040 replications. Standard deviations in parenthesis.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$5\%$ | 5687 (5) | 1891 (18) | 700 (22)
$20\%$ | 6445 (10) | 1795 (19) | 489 (17)
$80\%$ | 3367 (14) | 1580 (15) | 293 (8)

Table 18: Results for DSSAT Experiment 2, empirical regret at $T=10000$ in t/ha for 1040 replications.  $\alpha$ | U-UCB | CVaR-UCB | B-CVTS
---|---|---|---
$5\%$ | 3179 (2) | 759 (14) | 195 (11)
$20\%$ | 5644 (6) | 1020 (17) | 202 (10)
$80\%$ | 2642 (10) | 888 (13) | 284 (12)

Figure 12: DSSAT Experiment 1, 7 armed bandit
all algorithms, $\alpha=5\%$ ; 1040 replications.  Figure 13: DSSAT Experiment
2,
4 armed over-estimated support upper bound,
all algorithms, $\alpha=5\%$ ; 1040 replications.

Figure 14: DSSAT Experiment 1,
all algorithms, $\alpha=20\%$ Figure 15: DSSAT Experiment 2,
all algorithms, $\alpha=20\%$

Figure 16: DSSAT Experiment 1,
all algorithms, $\alpha=80\%$ Figure 17: DSSAT Experiment 2,
all algorithms, $\alpha=80\%$