# Quantum and classical ergotropy from relative entropies

Akira Sone<EMAIL_ADDRESS>Aliro Technologies, Inc. Boston,
Massachusetts 02135, USA  Theoretical Division, Los Alamos National
Laboratory, Los Alamos, New Mexico 87545,USA  Center for Nonlinear Studies,
Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA  Sebastian
Deffner<EMAIL_ADDRESS>Department of Physics, University of Maryland,
Baltimore County, Baltimore, Maryland 21250, USA  Instituto de Física ‘Gleb
Wataghin’, Universidade Estadual de Campinas, 13083-859, Campinas, São Paulo,
Brazil

###### Abstract

The quantum ergotropy quantifies the maximal amount of work that can be
extracted from a quantum state without changing its entropy. We prove that the
ergotropy can be expressed as the difference of quantum and classical relative
entropies of the quantum state with respect to the thermal state. This insight
is exploited to define the classical ergotropy, which quantifies how much work
can be extracted from distributions that are inhomogeneous on the energy
surfaces. A unified approach to treat both, quantum as well as classical
scenarios, is provided by geometric quantum mechanics, for which we define the
geometric relative entropy. The analysis is concluded with an application of
the conceptual insight to conditional thermal states, and the correspondingly
tightened maximum work theorem.

According to its definition, the adjective _ergotropic_ refers to the
physiological mechanisms of a nervous system to favor an organism’s capacity
to expend energy Gellhorn (1970). Generalizing this notion to physical
systems, _quantum ergotropy_ was then coined to denote the maximal amount of
work that can be extracted by isentropic transformations Allahverdyan  _et
al._ (2004). In particular, the quantum ergotropy quantifies the amount of
energy that is stored in _active_ quantum states, and which can be extracted
by making the state _passive_ Pusz and Woronowicz (1978); Koukoulekidis  _et
al._ (2021). In simple terms, a passive state is diagonal in the energy basis,
and its eigenstates are ordered in descending magnitude of its eigenvalues.
Gibbs states are then called _completely passive_ Pusz and Woronowicz (1978).

The quantum ergotropy plays a prominent role in quantum thermodynamics Deffner
and Campbell (2019). In particular, when assessing the _thermodynamic value_
of genuine quantum properties Goold  _et al._ (2016); Perarnau-Llobet  _et
al._ (2017); Levy and Lostaglio (2020); Santos  _et al._ (2019) such as
squeezed and nonequilibrium reservoirs Niedenzu  _et al._ (2018); Cherubim
_et al._ (2019), coherence Francica  _et al._ (2020); Çakmak (2020), or
quantum correlations Francica  _et al._ (2017); Touil  _et al._ (2021), it has
proven powerful. However, if the quantum system is not in contact with a heat
reservoir, computing the quantum ergotropy is far from trivial. This is due to
the fact that the ergotropy is determined by a maximum over all unitaries that
can act upon the system Allahverdyan  _et al._ (2004). Thus, it appears
desirable to have an expression for the ergotropy that is independent of the
maximization.

In this letter, we prove that the quantum ergotropy can be written as the
difference of quantum and classical relative entropies. Here, the classical
relative entropy is the Kullback-Leibler divergence of the eigenvalue
distributions. This motivates the definition of a _classical ergotropy_ ,
which quantifies the maximal amount of work that can be extracted from
inhomogeneities on the energy surfaces, which have been shown to be analogous
to quantum coherences Smith (2019); Smith  _et al._ .

In a second part of the analysis, we turn to a unified framework, namely
geometric quantum mechanics. Exploiting this approach Anza and Crutchfield
(2020a, b, c), we define the _geometric relative entropy_. With this it
becomes particularly transparent to characterize the one-time measurement
approach to quantum work Deffner  _et al._ (2016); Beyer  _et al._ (2020);
Sone  _et al._ (2020); Sone and Deffner (2020). In this paradigm, work is
determined by first measuring the energy of the system, and then letting it
evolve under a time-dependent dynamics. In contrast to the two-time
measurement approach Kurchan (2001); Tasaki (2000); Talkner  _et al._ (2007);
Huber  _et al._ (2008); Campisi  _et al._ (2011); Deffner and Lutz (2011);
Kafri and Deffner (2012); Mazzola  _et al._ (2013); Dorner  _et al._ (2013);
Roncaglia  _et al._ (2014); Batalhão  _et al._ (2014); An  _et al._ (2015);
Deffner and Saxena (2015a, b); Talkner and Hänggi (2016); Gardas  _et al._
(2016); Bartolotta and Deffner (2018); Gardas and Deffner (2018); Touil and
Deffner (2021), no projective measurement is taken at the end of the process.
Hence, the work probability distribution is entirely determined by the
statistics _conditioned_ on the initial energy. Here, we identify the distinct
contributions to the thermodynamic cost of projective measurements by
separating out the coherent and incoherent ergotropies, and the population
mismatch in the conditional statistics.

Hence, by re-writing the quantum ergotropy in a form independent of the
maximization over all unitaries, we are able to (i) generalize the notion to
classical scenarios, and to (ii) elucidate the thermodynamics of projective
measurements. This analysis further cements the ergotropy as one of the
salient pillars of quantum thermodynamics.

## Quantum ergotropy

We begin by deriving a simple expression for the quantum ergotropy, which does
not explicitly depend on the optimization over unitary maps. To this end,
consider a quantum system with Hamiltonian $H$ and quantum state $\rho$. Then,
the ergotropy is defined as Allahverdyan  _et al._ (2004)

$\mathcal{E}\left(\rho\right)\equiv\mathrm{tr}\left\\{\rho\,H\right\\}-\min_{U\in\mathcal{U}}\left[\mathrm{tr}\left\\{U\rho
U^{\dagger}\,H\right\\}\right]\,,$ (1)

where $\mathcal{U}$ is the unitary group.

Our goal is now to express Eq. (1) as a difference of relative entropies. To
this end, we write the quantum state $\rho$ in its “ordered” eigenbasis,

$\rho=\operatorname*{\mathchoice{\ooalign{$\displaystyle\sum$\cr$\displaystyle\int$\cr}}{\ooalign{\raisebox{0.14pt}{\scalebox{0.7}{$\textstyle\sum$}}\cr$\textstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}}_{i}p_{i}\left|p_{i}\right\rangle\left\langle
p_{i}\right|\quad\text{with}\quad p_{i}\geq p_{i+1}\,.$ (2)

Let $\sigma$ be a second quantum state, which we write as

$\sigma=\operatorname*{\mathchoice{\ooalign{$\displaystyle\sum$\cr$\displaystyle\int$\cr}}{\ooalign{\raisebox{0.14pt}{\scalebox{0.7}{$\textstyle\sum$}}\cr$\textstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}}_{i}s_{i}\left|s_{i}\right\rangle\left\langle
s_{i}\right|\quad\text{with}\quad s_{i}\geq s_{i+1}\,.$ (3)

In principle, $\rho$ and $\sigma$ can be vastly different quantum states. To
better compare $\rho$ and $\sigma$, it is then interesting to identify the
unitary operation that takes $\rho$ as close as possible to $\sigma$. Hence,
considering the quantum relative entropy Nielsen and Chuang (2011),

$S(U\rho
U^{\dagger}||\sigma)\equiv\mathrm{tr}\left\\{\rho\ln{\left(\rho\right)}\right\\}-\mathrm{tr}\left\\{U\rho
U^{\dagger}\ln{\left(\sigma\right)}\right\\}\,,$ (4)

we now need to identify the specific $U$ such that $S(U\rho
U^{\dagger}||\sigma)$ is minimal. To this end, we parametrize a variation as
$\delta U=(\delta X)U$, where $\delta X$ is an arbitrary infinitesimal, anti-
Hermitian operator, i.e., $(\delta X)^{\dagger}=-\delta X$, and we have

$\delta S(U\rho U^{\dagger}||\sigma)=-\mathrm{tr}\left\\{\delta X\,\left[U\rho
U^{\dagger},\,\ln{\left(\sigma\right)}\right]\right\\}=0\,.$ (5)

It is then easy to see that a solution to Eq. (5) is given by

$\tilde{U}\equiv\operatorname*{\mathchoice{\ooalign{$\displaystyle\sum$\cr$\displaystyle\int$\cr}}{\ooalign{\raisebox{0.14pt}{\scalebox{0.7}{$\textstyle\sum$}}\cr$\textstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}}_{i}\left|s_{i}\right\rangle\left\langle
p_{i}\right|\,,$ (6)

for which we immediately obtain

$S(\tilde{U}\rho\tilde{U}^{\dagger}||\sigma)=\operatorname*{\mathchoice{\ooalign{$\displaystyle\sum$\cr$\displaystyle\int$\cr}}{\ooalign{\raisebox{0.14pt}{\scalebox{0.7}{$\textstyle\sum$}}\cr$\textstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}{\ooalign{\raisebox{0.2pt}{\scalebox{0.6}{$\scriptstyle\sum$}}\cr$\scriptstyle\int$\cr}}}_{i}p_{i}\ln{\left(p_{i}/s_{i}\right)}\equiv
D(\rho||\sigma)\,.$ (7)

Therefore, we conclude that the minimum of the quantum relative entropy under
all unitary transformations of $\rho$ is nothing but the classical relative
entropy of its distribution of eigenvalues,

$\min_{U\in\mathcal{U}}\left[S(U\rho
U^{\dagger}||\sigma)\right]=D(\rho||\sigma)\,.$ (8)

Using Eq. (8), we now re-write the quantum ergotropy (1). To this end, we
choose $\sigma$ as the Gibbs state,,
$\sigma=\rho^{\mathrm{eq}}=\exp{\left(-\beta H\right)}/Z$. For the sake of
simplicity, we further assume that the eigenenergies are ordered in ascending
magnitude, $E_{i}\leq E_{i+1}$. It is then easy to show that 222Note that
$\beta^{-1}\left(S(\rho||\rho^{\mathrm{eq}})-D(\rho||\rho^{\mathrm{eq}})\right)$
makes $\mathcal{E}(\rho)$ independent of $\beta$.

$\beta\,\mathcal{E}(\rho)=S(\rho||\rho^{\mathrm{eq}})-D(\rho||\rho^{\mathrm{eq}})\,.$
(9)

In conclusion, the quantum ergotropy is written as the difference of the
quantum and classical relative entropies of the quantum state $\rho$ with
respect to $\rho^{\mathrm{eq}}$. Note that Eq. (9) is entirely determined by
$\rho$ and $\rho^{\mathrm{eq}}$, and independent of any optimization.

## Ergotropy from quantum coherence

It has recently been recognized Francica  _et al._ (2020); Çakmak (2020);
Touil  _et al._ (2021) that the quantum ergotropy (1) can be separated into
two fundamentally different contributions,
$\mathcal{E}(\rho)=\mathcal{E}_{i}(\rho)+\mathcal{E}_{c}(\rho)$. The
_incoherent ergotropy_ $\mathcal{E}_{i}(\rho)$ denotes the maximal work that
can be extracted from $\rho$ without changing its coherence. Thus, the
_coherent ergotropy_ $\mathcal{E}_{c}(\rho)$ is the work that is exclusively
stored in the coherences. These can be quantified by the relative entropy of
coherence Baumgratz  _et al._ (2014)

$\mathcal{C}(\rho)=\mathcal{H}\left(\mathcal{L}(\rho)\right)-\mathcal{H}(\rho)\,,$
(10)

where
$\mathcal{H}(\rho)\equiv-\mathrm{tr}\left\\{\rho\ln{\left(\rho\right)}\right\\}$
and $\mathcal{L}$ is the purely dephasing map, i.e., the map that removes all
coherences, but leaves the diagonal elements in energy basis invariant. It is
then a simple exercise to show that we have

$\beta\,\mathcal{E}_{c}(\rho)=\mathcal{C}(\rho)+S(\mathcal{L}(\rho)||\rho^{\mathrm{eq}})-D(\rho||\rho^{\mathrm{eq}})\,.$
(11)

Hence, we conclude that there are three distinct contributions to the coherent
ergotropy. Namely, work can be extracted not only from the coherences
directly, but also from the population mismatch between the completely
decohered state and the corresponding thermal state. However, the total,
extractable work is lowered by the fact that generally $\rho$ is not diagonal
in energy, and hence the classical relative entropy is different from the
quantum relative entropy of the completely decohered state.

## Classical ergotropy from inhomogeneity

Remarkably, the above discussion can be generalized to purely classical
scenarios. It has recently been recognized that distributions that are
inhomogeneous on the energy surfaces can be considered as classical equivalent
of quantum states with coherences Smith (2019); Smith  _et al._ . Therefore,
we proceed by defining the _classical ergotropy_ , which quantifies the
maximal work that can be extracted from inhomogeneous distributions under
Hamiltonian dynamics, i.e., under the classical equivalent of unitary maps.

We start with the classical distribution, $p(\Gamma)$, that measures how
likely it is to find a system at a point in phase space $\Gamma$. Now consider
a situation in which $\Gamma$ is sampled microcanonically from an (initial)
energy surface $A$, and we then let $p_{A}(\Gamma)$ evolve under Liouville’s
equation. We are interest in assessing how close to equilibrium the system is
driven. To this end, consider the joint probability of finding
$\Gamma^{\prime}$ on energy surface $B$, given that $\Gamma$ was sampled from
energy surface $A$,

$p_{B|A}(\Gamma,\Gamma^{\prime})=p(\Gamma^{\prime}|\Gamma)\,p_{A}(\Gamma)\,,$
(12)

where $p(\Gamma^{\prime}|\Gamma)$ is the classical transition probability. We
have

$\int d\Gamma\,p(\Gamma^{\prime}|\Gamma)=\int
d\Gamma^{\prime}\,p(\Gamma^{\prime}|\Gamma)=1\,,$ (13)

which follows from Liouville’s theorem and normalization.

In complete analogy to the quantum case we now consider the relative entropy
of $p_{B|A}(\Gamma,\Gamma^{\prime})$ with respect to the thermal distribution
on energy surface $B$, $p_{B}^{\mathrm{eq}}(\Gamma)=\exp{\left(-\beta
E_{B}(\Gamma)\right)}/Z$. We can write

$\begin{split}&D(p_{B|A}||p_{B}^{\mathrm{eq}})\\\ &\quad=\int d\Gamma\int
d\Gamma^{\prime}\,p_{B|A}(\Gamma,\Gamma^{\prime})\ln{\left(p_{B|A}(\Gamma,\Gamma^{\prime})\right)}\\\
&\quad-\int d\Gamma\int
d\Gamma^{\prime}\,p_{B|A}(\Gamma,\Gamma^{\prime})\ln{\left(p^{\mathrm{eq}}_{B}(\Gamma)\right)}\,.\end{split}$
(14)

Note that the normalization of the transition probabilities (13) is essential
to guarantee that the classical distributions, $p_{B|A}$ and
$p_{B}^{\mathrm{eq}}$, have the same support. As before, we then seek a
“transformed” joint distribution $\mathscr{Q}_{B|A}$ for which the relative
entropy $D(\mathscr{Q}_{B|A}||p_{B})$ becomes minimal. This
$\mathscr{Q}_{B|A}$ can be written as

$\mathscr{Q}_{B|A}(\Gamma^{\prime\prime},\Gamma)\equiv\int
d\Gamma^{\prime}\,q(\Gamma^{\prime\prime}|\Gamma^{\prime})p(\Gamma^{\prime}|\Gamma)p_{A}(\Gamma)\,,$
(15)

and we need to minimize Eq. (14) as a function of the transition probability
$q(\Gamma^{\prime\prime}|\Gamma^{\prime})$.

We start by recognizing that the convolution of two transition probabilities
is also a transition probability

$\xi(\Gamma^{\prime\prime}|\Gamma)\equiv\int
d\Gamma^{\prime}\,q(\Gamma^{\prime\prime}|\Gamma^{\prime})p(\Gamma^{\prime}|\Gamma)\,.$
(16)

We have

$\mathscr{Q}_{B|A}(\Gamma^{\prime\prime},\Gamma)=\xi(\Gamma^{\prime\prime}|\Gamma)\,p_{A}(\Gamma)\,.$
(17)

Therefore, we now minimize $D(\mathscr{Q}_{B|A}||p_{B})$ as a function $\xi$.
In particular, a variation in $\xi$ can be written as

$\delta\xi\equiv\delta\Gamma^{\prime}\cdot\nabla_{\Gamma^{\prime}}\xi+\delta\Gamma\cdot\nabla_{\Gamma}\xi\,,$
(18)

where we replaced $\Gamma^{\prime\prime}$ with $\Gamma^{\prime}$ without loss
of generality. After a few straight forward manipulations, we obtain

$\delta D\left(\mathscr{Q}_{B|A}||p_{B}^{\text{eq}}\right)\\!=\\!\beta\int
d\Gamma\int d\Gamma^{\prime}p_{A}(\Gamma)E_{B}(\Gamma^{\prime})\,\delta\xi\,,$
(19)

where we used the explicit expression for $p_{B}^{\text{eq}}$. It is easy to
see that the variation of the relative entropy vanishes, $\delta
D\left(\mathscr{Q}_{B|A}||p_{B}^{\text{eq}}\right)=0$, for
$\xi(\Gamma^{\prime}|\Gamma)=\delta(\Gamma^{\prime}-\Gamma)$.

In conclusion, and in complete analogy to the quantum case, we obtain

$\min_{\xi}\left[D\left(\mathscr{Q}_{B|A}||p_{B}^{\text{eq}}\right)\right]=D(p_{A}||p_{B}^{\text{eq}})\,.$
(20)

Accordingly, we define the classical ergotropy as

$\beta\,\mathcal{E}_{\mathrm{class}}(p_{B|A})\equiv
D\left(p_{B|A}||p_{B}^{\text{eq}}\right)-D\left(p_{A}||p_{B}^{\text{eq}}\right)\,.$
(21)

which quantifies the maximal amount of work that can be extracted from the
joint distribution $p_{B|A}$ under Liouvillian maps. Remarkably, both the
quantum (9) as well as the classical (21) ergotropy comprise the classical
relative entropy with respect to a thermal state.

Equation (21) can also be re-written to resemble more closely the established
expression of the quantum ergotropy (1). We have

$\mathcal{E}_{\mathrm{class}}(p_{B|A})=\int
d\Gamma^{\prime}\,\varphi_{B}(\Gamma^{\prime})E_{B}(\Gamma^{\prime})$ (22)

where we introduced

$\varphi_{B}(\Gamma^{\prime})=\int
d\Gamma\,p_{B|A}(\Gamma^{\prime},\Gamma)-p_{A}(\Gamma^{\prime})\,.$ (23)

In this form, it becomes apparent that the classical ergotropy quantifies the
maximal amount of work stored in inhomogeneities. Notice that $\varphi_{B}$ is
not an explicit function of the Hamiltonian of the system, which has been
shown to be a classical equivalent of quantum coherences Smith (2019); Smith
_et al._ .

## Ergotropy in geometric quantum mechanics

Thus far we have seen that in quantum as well as in classical systems, work
can be extracted by “reshaping” the states in phase space without changing
their entropy. Remarkably, in either case the ergotropy is given by a
difference of relative entropies (see Eqs. (9) and (21)). The natural question
arises whether the quantum-to-classical limit can be taken systematically, or
rather whether the seemingly independent results can be derived within a
unifying framework.

Only very recently, Anza and Crutchfield Anza and Crutchfield (2020a, b, c)
recognized that for such thermodynamic considerations so-called geometric
quantum mechanics Ashtekar and Schilling (1999); Bengtsson and Zyczkowski
(2017); Cariñena  _et al._ (2007) is a uniquely suited paradigm. In standard
quantum theory, a quantum state is described by a density operator $\rho$,
which can be expanded in many different decompositions of pure states.
However, an often overlooked consequence is that, thus, the probabilistic
interpretation of quantum states is not unique. To remedy this issue,
_geometric quantum states_ Ashtekar and Schilling (1999); Bengtsson and
Zyczkowski (2017); Cariñena  _et al._ (2007) have been introduced, which are
probability distributions on the manifold spanned by the quantum states. In
this sense, classical and quantum mechanics only differ in the geometric
properties of the underlying manifold.

We proceed by briefly outlining the main notions of geometric quantum
mechanics. For a more complete exposition we refer to the literature Ashtekar
and Schilling (1999); Bengtsson and Zyczkowski (2017); Cariñena  _et al._
(2007); Anza and Crutchfield (2020a, b, c). In the geometric approach, a pure
quantum state $\left|\psi\right\rangle$ is described as a point in a complex
projective space $\mathcal{V}_{d}\equiv\mathbb{C}P^{d-1}$ Bengtsson and
Zyczkowski (2017), where $d$ is the dimension of the Hilbert space 111Note
that $d$ can also be infinite Ashtekar and Schilling (1999). Here, $\bm{z}$ is
the set of complex homogeneous coordinates in $\mathcal{V}_{d}$, and
$\bm{z^{*}}$ is the complex conjugate.

Hence, any pure state $\left|\psi\right\rangle$ can be written as

$\left|\psi(\bm{z})\right\rangle=\sum_{\alpha=0}^{d-1}z_{\alpha}\left|e_{\alpha}\right\rangle$
(24)

where $\\{e_{\alpha}\\}_{\alpha=0}^{d-1}$ is an arbitrary basis. The geometry
of the manifold is determined by the Fubini-Study metric Bengtsson and
Zyczkowski (2017),

$ds^{2}=2g_{\alpha\gamma^{*}}\,dz_{\alpha}dz^{*}_{\gamma}\equiv\frac{1}{2}\,\partial_{z_{\alpha}}\partial_{z^{*}_{\gamma}}\ln\left(\bm{z}\cdot\bm{z^{*}}\right)dz_{\alpha}dz^{*}_{\gamma},$
(25)

which allows to define a unique, unitarily invariant volume element,
$dV\equiv\sqrt{\det(g)}\,d\bm{z}d\bm{z^{*}}$.

It is easy to recognize that pure state are represented as generalized delta-
functions on the projective space. In particular, for
$\left|\psi_{0}\right\rangle\equiv\left|\psi(\bm{z}_{0})\right\rangle$ the
corresponding geometric quantum state becomes

$\mathcal{P}(\bm{z})=\widetilde{\delta}(\bm{z}-\bm{z}_{0})\equiv\delta(\bm{z}-\bm{z}_{0})/\sqrt{\det(g)}\,,$
(26)

where we introduced the coordinate-covariant Dirac-delta. Any (mixed) quantum
state can then be written as

$\rho=\int_{\mathcal{V}_{d}}dV\,\mathcal{P}(\bm{z})\,\left|\psi(\bm{z})\right\rangle\left\langle\psi(\bm{z})\right|\,,$
(27)

where the geometric quantum states are given by

$\mathcal{P}(\bm{z})=\sum_{j=1}^{d}p_{j}\,\widetilde{\delta}\left(\bm{z}-\bm{z}_{j}^{p}\right)\,,$
(28)

and $p_{j}$ are again the eigenvalues of $\rho$, and
$\bm{z}_{j}^{p}\equiv\bm{z}(\left|p_{j}\right\rangle)$.

We are now equipped to return to the expressions for the quantum and classical
ergotropies, Eqs. (9) and (21), respectively. We immediately recognize that to
proceed, we have to consider a generalization of the relative entropy to
geometric quantum states. In complete analogy to the classical case, we need
to guarantee that the geometric quantum states have the same support Anza and
Crutchfield . Hence, we introduce a geometric quantum generalization of the
conditional distribution to include a generalized transition probability. To
this end, consider

$\widetilde{\mathcal{P}}(\bm{z})\equiv\sum_{j=1}^{d}p_{j}\,\widetilde{\delta}\left(\bm{z}-\bm{z}_{j}^{s}\right)\,,$
(29)

where now $\bm{z}_{j}^{s}\equiv\bm{z}(\left|s_{j}\right\rangle)$, and
$\left|s_{j}\right\rangle$ is an eigenstate of a density operator $\sigma$.
The density operator, $\widetilde{\rho}$, corresponding to
$\widetilde{\mathcal{P}}(\bm{z})$ reads,
$\widetilde{\rho}=\widetilde{U}\,\rho\,\widetilde{U}^{\dagger}=\sum_{j}p_{j}\,\left|s_{j}\right\rangle\left\langle
s_{j}\right|$, where $\widetilde{U}$ are the “optimal” unitary maps (6).

The _geometric relative entropy_ is then defined as

$\mathcal{D}\left(\widetilde{\mathcal{P}}||\mathcal{S}\right)\equiv\int_{\mathcal{V}_{d}}dV\,\widetilde{\mathcal{P}}(\bm{z})\ln{\left(\widetilde{\mathcal{P}}(\bm{z})/\mathcal{S}(\bm{z})\right)}\,,$
(30)

where $\mathcal{S}$ is the geometric quantum state corresponding to $\sigma$
(same as before). Moreover, we have by construction
$\mathcal{D}\left(\widetilde{\mathcal{P}}||\mathcal{S}\right)=S\left(\widetilde{\rho}||\sigma\right)=D(\rho||\sigma)$,
and we conclude that the geometric relative entropy is identical in value to
the classical relative entropy (8). Therefore, we can write the quantum
ergotropy (9) as

$\beta\,\mathcal{E}(\rho)=S(\rho||\rho^{\mathrm{eq}})-\mathcal{D}\left(\widetilde{\mathcal{P}}||\mathcal{P}^{\mathrm{eq}}\right)\,,$
(31)

where $\mathcal{P}^{\mathrm{eq}}$ is the geometric quantum state corresponding
to $\rho^{\mathrm{eq}}$. In other words, the quantum ergotropy is the
difference of the relative entropies of the density operator and the geometric
quantum state with respect to $\rho^{\mathrm{eq}}$.

Remarkably, also the classical case can be fully treated within the geometric
approach. To this end, note that for any classical distribution we can
construct the corresponding geometric quantum state. Therefore, it now becomes
a fair comparison to consider the difference of quantum and classical
ergotropy,

$\Delta\mathcal{E}\equiv\mathcal{E}(\rho)-\mathcal{E}_{\mathrm{class}}(\rho)\,.$
(32)

It is not far-fetched to realize that $\Delta\mathcal{E}$ is the genuinely
quantum contribution to the extractable work. A more careful analysis of this
contribution may be related to quantum correlations (see also Ref. Touil  _et
al._ (2021)), yet a thorough analysis is beyond the scope of the present
discussion. Rather the remainder of this analysis is dedicated to an
application of the gained insight to quantum work relations.

## Ergotropy from conditional thermal states

To this end, imagine a closed system that is driven by the variation of some
external control parameter. We denote the initial Hamiltonian by $H_{A}$ and
the final Hamiltonian by $H_{B}$, and the average work is simply given by
$\left\langle W\right\rangle=\left\langle H_{B}\right\rangle-\left\langle
H_{A}\right\rangle$. The maximum work theorem predicts that $\left\langle
W\right\rangle$ is always larger than the work performed for quasistastic
driving Deffner and Campbell (2019). If the system was initially prepared in a
thermal state, the quasistatic work is nothing but the difference in Helmholtz
free energy $\Delta F$ Deffner and Lutz (2010). The difference of total work
and free energy difference is called _irreversible work_ , and we have
$\left\langle W_{\mathrm{irr}}\right\rangle=\left\langle W\right\rangle-\Delta
F\geq 0$ Deffner and Lutz (2010). Only rather recently, it has been recognized
that a sharper inequality can be derived, for both quantum Deffner  _et al._
(2016) as well as classical Sone and Deffner (2020) systems, if the quantum
work statistics are conditioned on the initial state. Note that this
corresponds to the one-time measurement approach, where only one projective
measurement is taken at the beginning of the process.

In particular it has been shown that Deffner  _et al._ (2016); Sone and
Deffner (2020)

$\beta\left\langle W_{\text{irr}}\right\rangle\geq
S(\varrho_{B}||\rho_{B}^{\text{eq}})\,,$ (33)

where $\rho_{B}^{\text{eq}}=\exp{\left(-\beta H_{B}\right)}/Z_{B}$, and
$\varrho_{B}$ has been called conditional thermal state Sone and Deffner
(2020). It reads Deffner  _et al._ (2016)

$\varrho_{B}\equiv\sum_{j}\frac{\exp{\left(-\beta\,h_{B}(j_{A})\right)}}{\mathcal{Z}(B|A)}\,U_{\tau}\left|j_{A}\right\rangle\left\langle
j_{A}\right|U_{\tau}^{\dagger}\,,$ (34)

where $\left|j_{A}\right\rangle$ is an eigenstate of the initial Hamiltonian
$H_{A}$. Further, $U_{\tau}$ is the unitary evolution operator corresponding
to driving the system from $H_{A}$ to $H_{B}$, and
$h_{B}(j_{A})\equiv\left\langle
j_{A}\right|U_{\tau}^{\dagger}H_{B}U_{\tau}\left|j_{A}\right\rangle$. Finally,
$\mathcal{Z}(B|A)$ is the conditional partition function of $\varrho_{B}$.
Since the discovery of Eq. (33), the significance of the conditional thermal
state has been somewhat obscure. In Ref. Deffner  _et al._ (2016); Sone  _et
al._ (2020) the lower bound in Eq. (33) was understood as some contribution to
the usable work that would have been destroyed by a second projective
measurement. Yet, a transparent interpretation has been lacking.

Remarkably, it is not hard to see that $\varrho_{B}$ is a representation of
the _geometric canonical ensemble_ as proposed by Anza and Crutchfield Anza
and Crutchfield (2020a, c). The geometric canonical ensemble is defined as the
geometric state that maximizes the corresponding Shannon entropy under the
usual boundary conditions Jaynes (1957). Specifically, we have Anza and
Crutchfield (2020a, c).

$\mathfrak{P}(\bm{z})\equiv\exp{\left(-\beta\,h(\bm{z})\right)}/\mathcal{Z}\,,$
(35)

where
$h(\bm{z})\equiv\left\langle\psi(\bm{z})\right|H\left|\psi(\bm{z})\right\rangle$
and the geometric partition function
$\mathcal{Z}\equiv\int_{\mathcal{V}_{d}}dV\exp{\left(-\beta\,h(\bm{z})\right)}$.
Now, consider the geometric representation of $\varrho_{B}$,

$\varrho_{B}=\int_{\mathcal{V}_{d}}dV\mathfrak{P}_{B}\,(\bm{z})\,\left|\psi(\bm{z})\right\rangle\left\langle\psi(\bm{z})\right|\
$ (36)

and we have

$\mathfrak{P}_{B}(\bm{z})=\sum_{j}\frac{\exp{\left(-\beta\,h_{B}(\bm{z})\right)}}{\mathcal{Z}(B|A)}\,\widetilde{\delta}\left(\bm{z}-\bm{z}_{j}\right)\,,$
(37)

where as before
$h_{B}(\bm{z})\equiv\left\langle\psi(\bm{z})\right|H_{B}\left|\psi(\bm{z})\right\rangle$
and the covariant Dirac-delta is evaluated at
$\left|\psi(\bm{z}_{j})\right\rangle\equiv U_{\tau}\left|j_{A}\right\rangle$.
Comparing Eqs. (35) and (37) we immediately recognize that the
$\mathfrak{P}_{B}(\bm{z})$ is nothing but the geometric canonical state
evaluated on the quantum manifold.

The natural question arises if any work can be extracted from the geometric
ensemble. To this end, consider the corresponding ergotropy (31)

$\beta\,\mathcal{E}(\varrho_{B})=S\left(\varrho_{B}||\rho_{B}^{\text{eq}}\right)-\mathcal{D}\left(\widetilde{\mathfrak{P}}_{B}||\mathfrak{P}_{B}^{\text{eq}}\right)\,,$
(38)

where in complete analogy to above $\widetilde{\mathfrak{P}}_{B}$ is given by

$\widetilde{\mathfrak{P}}_{B}(\bm{z})\equiv\sum_{j}\frac{\exp{\left(-\beta
h_{B}(j_{A})\right)}}{\mathcal{Z}(B|A)}\,\widetilde{\delta}\left(\bm{z}-\bm{z}_{j}^{\text{eq}}\right)\,,$
(39)

and now
$\bm{z}_{j}^{\text{eq}}\equiv\bm{z}\left(\left|j_{B}\right\rangle\right)$,
where $\left|j_{B}\right\rangle$ is the eigenstate of the final Hamiltonian
$H_{B}$. Thus, exploiting Eq. (11) we can write the sharpened maximum work
theorem (33) as

$\beta\left\langle
W_{\text{irr}}\right\rangle\geq\beta\mathcal{E}_{i}(\varrho_{B})+\mathcal{C}(\varrho_{B})+S(\mathcal{L}(\varrho_{B})||\rho_{B}^{\text{eq}})\,.$
(40)

In conclusion, realizing that the conditional thermal state (34) is nothing
but a representation of the geometric canonical ensemble the physical
interpretation of the sharpened maximum work theorem (33) becomes apparent.
The lower bound on the irreversible work has three contributions, namely the
incoherent ergotropy and the quantum coherences stored in the conditional
thermal state, and the population mismatch between $\varrho_{B}$ and
$\rho_{B}^{\text{eq}}$.

## Concluding remarks

Motivated by the desire to express the maximally extractable work in a form
independent of the optimization over unitary operations, we have obtained
several results: First, we expressed the quantum ergotropy as the difference
of quantum and classical relative entropies. This separation of terms allowed
to identify the three distinct contributions to the coherent ergotropy, for
which the relative entropy of coherence and the population mismatch between
thermal state and fully decohered state are the most important. This insight
was extended to classical systems, in which inhomogeneities in the energy
distribution play the role of quantum coherences. To quantify how much work
can be extracted from classical states, we introduced the classical ergotropy,
and we postulated that the genuine quantum contribution to the ergotropy is
given by the difference of quantum and classical expressions. This was
solidified by exploiting the geometric approach to quantum mechanics, in which
quantum and classical states can be treated in a unified framework. As an
application, we demonstrated that a recently introduced notion of “conditional
thermal state” actually belongs to the family of geometric canonical
ensembles, and that, hence, the corresponding sharpened maximum work theorem
becomes easy to interpret. This demonstrates that understanding quantum as
well as classical ergotropies is an essential pillar of modern thermodynamics
with a myriad of potential applications.

###### Acknowledgements.

We would like to thank Fabio Anza, Christopher Jarzynski, and Kanupriya Sinha
for insightful discussions. A.S. was supported by the U.S. Department of
Energy, the Laboratory Directed Research and Development (LDRD) program and
the Center for Nonlinear Studies at LANL. He is now supported by the internal
R&D from Aliro Technologies, Inc. S.D. acknowledges support from the U.S.
National Science Foundation under Grant No. DMR-2010127.

## References

  * Gellhorn (1970) E. Gellhorn, “The emotions and the ergotropic and trophotropic systems,” Psychol. Forsch. 34, 67–94 (1970).
  * Allahverdyan  _et al._ (2004) A. E. Allahverdyan, R. Balian, and Th. M. Nieuwenhuizen, “Maximal work extraction from finite quantum systems,” EPL (Europhys. Lett.) 67, 565 (2004).
  * Pusz and Woronowicz (1978) W. Pusz and S. L. Woronowicz, “Passive states and KMS states for general quantum systems,” Commun. Math. Phys. 58, 273–290 (1978).
  * Koukoulekidis  _et al._ (2021) Nikolaos Koukoulekidis, Rhea Alexander, Thomas Hebdige, and David Jennings, “The geometry of passivity for quantum systems and a novel elementary derivation of the Gibbs state,” Quantum 5, 411 (2021).
  * Deffner and Campbell (2019) S. Deffner and S. Campbell,  _Quantum Thermodynamics_ (Morgan and Claypool Publishers, San Rafael, 2019).
  * Goold  _et al._ (2016) John Goold, Marcus Huber, Arnau Riera, Lídia del Rio, and Paul Skrzypczyk, “The role of quantum information in thermodynamics—a topical review,” J. Phys. A: Math. Theor. 49, 143001 (2016).
  * Perarnau-Llobet  _et al._ (2017) Martĺ Perarnau-Llobet, Elisa Bäumer, Karen V. Hovhannisyan, Marcus Huber, and Antonio Acin, “No-go theorem for the characterization of work fluctuations in coherent quantum systems,” Phys. Rev. Lett. 118, 070601 (2017).
  * Levy and Lostaglio (2020) Amikam Levy and Matteo Lostaglio, “A quasiprobability distribution for heat fluctuations in the quantum regime,” Phys. Rev. X Quantum 1, 010309 (2020).
  * Santos  _et al._ (2019) Jader P. Santos, Lucas C. Céleri, Gabriel T. Landi, and Mauro Paternostro, “The role of quantum coherence in non-equilibrium entropy production,” npj Quantum Inf. 5, 23 (2019).
  * Niedenzu  _et al._ (2018) Wolfgang Niedenzu, Victor Mukherjee, Arnab Ghosh, Abraham G. Kofman, and Gershon Kurizki, “Quantum engine efficiency bound beyond the second law of thermodynamics,” Nat. Commun. 9, 165 (2018).
  * Cherubim  _et al._ (2019) Cleverson Cherubim, Frederico Brito, and Sebastian Deffner, “Non-thermal quantum engine in transmon qubits,” Entropy 21, 545 (2019).
  * Francica  _et al._ (2020) G. Francica, F.C. Binder, G. Guarnieri, M.T. Mitchison, J. Goold, and F. Plastina, “Quantum coherence and ergotropy,” Phys. Rev. Lett. 125, 180603 (2020).
  * Çakmak (2020) B. Çakmak, “Ergotropy from coherences in an open quantum system,” Phys. Rev. E 102, 042111 (2020).
  * Francica  _et al._ (2017) Gianluca Francica, John Goold, Francesco Plastina, and Mauro Paternostro, “Daemonic ergotropy: enhanced work extraction from quantum correlations,” npj Quantum Inf. 3, 12 (2017).
  * Touil  _et al._ (2021) Akram Touil, Barış Çakmak, and Sebastian Deffner, “Second law of thermodynamics for quantum correlations,” arXiv preprint arXiv:2102.13606 (2021).
  * Smith (2019) Andrew Maven Smith,  _Studies in Nonequilibrium Quantum Thermodynamics_ , Ph.D. thesis, University of Maryland, College Park (2019).
  * (17) A. Smith, K. Sinha, and C. Jarzynski, (to be published).
  * Anza and Crutchfield (2020a) Fabio Anza and James P. Crutchfield, “Geometric quantum state estimation,” arXiv:2008.08679 (2020a).
  * Anza and Crutchfield (2020b) Fabio Anza and James P. Crutchfield, “Beyond density matrices: Geometric quantum states,” arXiv:2008.08682 (2020b).
  * Anza and Crutchfield (2020c) Fabio Anza and James P. Crutchfield, “Geometric quantum thermodynamics,” arXiv:2008.08683 (2020c).
  * Deffner  _et al._ (2016) Sebastian Deffner, Juan Pablo Paz, and Wojciech H. Zurek, “Quantum work and the thermodynamic cost of quantum measurements,” Phys. Rev. E 94, 010103(R) (2016).
  * Beyer  _et al._ (2020) Konstantin Beyer, Kimmo Luoma, and Walter T. Strunz, “Work as an external quantum observable and an operational quantum work fluctuation theorem,” Phys. Rev. Research 2, 033508 (2020).
  * Sone  _et al._ (2020) Akira Sone, Yi-Xiang Liu, and Paola Cappellaro, “Quantum Jarzynski equality in open quantum systems from the one-time measurement scheme,” Phys. Rev. Lett. 125, 060602 (2020).
  * Sone and Deffner (2020) Akira Sone and Sebastian Deffner, “Jarzynski equality for stochastic conditional work,” arXiv:2010.05835 (2020).
  * Kurchan (2001) Jorge Kurchan, “A quantum fluctuation theorem,” arXiv:cond-mat/0007360 (2001).
  * Tasaki (2000) Hal Tasaki, “Jarzynski relations for quantum systems and some applications,” arXiv:cond-mat/0009244 (2000).
  * Talkner  _et al._ (2007) Peter Talkner, Eric Lutz, and Peter Hänggi, “Fluctuation theorems: Work is not an observable,” Phys. Rev. E 75, 050102(R) (2007).
  * Huber  _et al._ (2008) Gerhard Huber, Ferdinand Schmidt-Kaler, Sebastian Deffner, and Eric Lutz, “Employing trapped cold ions to verify the quantum jarzynski equality,” Phys. Rev. Lett. 101, 070403 (2008).
  * Campisi  _et al._ (2011) Michele Campisi, Peter Hänggi, and Peter Talkner, “Colloquium: Quantum fluctuation relations: Foundations and applications,” Rev. Mod. Phys. 83, 771 (2011).
  * Deffner and Lutz (2011) Sebastian Deffner and Eric Lutz, “Nonequilibrium entropy production for open quantum systems,” Phys. Rev. Lett. 107, 140404 (2011).
  * Kafri and Deffner (2012) Dvir Kafri and Sebastian Deffner, “Holevo’s bound from a general quantum fluctuation theorem,” Phys. Rev. A 86, 044302 (2012).
  * Mazzola  _et al._ (2013) L. Mazzola, G. De Chiara, and M. Paternostro, “Measuring the characteristic function of the work distribution,” Phys. Rev. Lett. 110, 230602 (2013).
  * Dorner  _et al._ (2013) R. Dorner, S. R. Clark, L. Heaney, R. Fazio, J. Goold, and V. Vedral, “Extracting quantum work statistics and fluctuation theorems by single-qubit interferometry,” Phys. Rev. Lett. 110, 230601 (2013).
  * Roncaglia  _et al._ (2014) Augusto J. Roncaglia, Federico Cerisola, and Juan Pablo Paz, “Work measurement as a generalized quantum measurement,” Phys. Rev. Lett. 113, 250601 (2014).
  * Batalhão  _et al._ (2014) Tiago B. Batalhão, Alexandre M. Souza, Laura Mazzola, Ruben Auccaise, Roberto S. Sarthour, Ivan S. Oliveira, John Goold, Gabriele De Chiara, Mauro Paternostro, and Roberto M. Serra, “Experimental reconstruction of work distribution and study of fluctuation relations in a closed quantum system,” Phys. Rev. Lett. 113, 140601 (2014).
  * An  _et al._ (2015) Shuoming An, Jing-Ning Zhang, Mark Um, Dingshun Lv, Yao Lu, Junhua Zhang, Zhang-Qi Yin, H. T. Quan, and Kihwan Kim, “Experimental test of the quantum jarzynski equality with a trapped-ion system,” Nature Physics 11, 193–199 (2015).
  * Deffner and Saxena (2015a) Sebastian Deffner and Avadh Saxena, “Jarzynski equality in $\mathcal{P}\mathcal{T}$-symmetric quantum mechanics,” Phys. Rev. Lett. 114, 150601 (2015a).
  * Deffner and Saxena (2015b) Sebastian Deffner and Avadh Saxena, “Quantum work statistics of charged dirac particles in time-dependent fields,” Phys. Rev. E 92, 032137 (2015b).
  * Talkner and Hänggi (2016) Peter Talkner and Peter Hänggi, “Aspects of quantum work,” Phys. Rev. E 93, 022131 (2016).
  * Gardas  _et al._ (2016) Bartłomiej Gardas, Sebastian Deffner, and Avadh Saxena, “Non-hermitian quantum thermodynamics,” Scientific Reports 6, 23408 (2016).
  * Bartolotta and Deffner (2018) Anthony Bartolotta and Sebastian Deffner, “Jarzynski equality for driven quantum field theories,” Phys. Rev. X 8, 011033 (2018).
  * Gardas and Deffner (2018) Bartłomiej Gardas and Sebastian Deffner, “Quantum fluctuation theorem for error diagnostics in quantum annealers,” Scientific Reports 8, 17191 (2018).
  * Touil and Deffner (2021) Akram Touil and Sebastian Deffner, “Information scrambling versus decoherence—two competing sinks for entropy,” PRX Quantum 2, 010306 (2021).
  * Nielsen and Chuang (2011) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_, 10th ed. (Cambridge University Press, New York, NY, USA, 2011).
  * Note (2) Note that $\beta^{-1}\left(S(\rho||\rho^{\mathrm{eq}})-D(\rho||\rho^{\mathrm{eq}})\right)$ makes $\mathcal{E}(\rho)$ independent of $\beta$.
  * Baumgratz  _et al._ (2014) T. Baumgratz, M. Cramer, and M.B. Plenio, “Quantifying coherence,” Phys. Rev. Lett. 113, 140401 (2014).
  * Ashtekar and Schilling (1999) Abhay Ashtekar and Troy A. Schilling,  _“Geometrical Formulation of Quantum Mechanics” in “On Einstein’s Path” (pp. 23-65)_ (Springer, New York, NY, USA, 1999).
  * Bengtsson and Zyczkowski (2017) I. Bengtsson and K. Zyczkowski,  _Geometry of Quantum States_ (Cambridge University Press, 2017).
  * Cariñena  _et al._ (2007) J. F. Cariñena, J. Clemente-Gallardo, and G. Marmo, “Geometrization of quantum mechanics,” Theor. Math. Phys. 152, 894 (2007).
  * Note (1) Note that $d$ can also be infinite Ashtekar and Schilling (1999).
  * (51) Fabio Anza and James Crutchfield, in preparation .
  * Deffner and Lutz (2010) Sebastian Deffner and Eric Lutz, “Generalized clausius inequality for nonequilibrium quantum processes,” Phys. Rev. Lett. 105, 170402 (2010).
  * Jaynes (1957) E. T. Jaynes, “Information theory and statistical mechanics,” Phys. Rev. 106, 620 (1957).


# Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit
Approach

Arman Rahbar∗
Department of Computer Science and Engineering
Chalmers University of Technology
Gothenburg, Sweden
<EMAIL_ADDRESS>
& Niklas Åkerblom∗
Volvo Car Corporation
Gothenburg, Sweden
Department of Computer Science and Engineering
Chalmers University of Technology
Gothenburg, Sweden
<EMAIL_ADDRESS>
Morteza Haghir Chehreghani
Department of Computer Science and Engineering
Chalmers University of Technology
Gothenburg, Sweden
<EMAIL_ADDRESS>

###### Abstract

Online decision making plays a crucial role in numerous real-world
applications. In many scenarios, the decision is made based on performing a
sequence of tests on the incoming data points. However, performing all tests
can be expensive and is not always possible. In this paper, we provide a novel
formulation of the online decision making problem based on combinatorial
multi-armed bandits and take the (possibly stochastic) cost of performing
tests into account. Based on this formulation, we provide a new framework for
cost-efficient online decision making which can utilize posterior sampling or
BayesUCB for exploration. We provide a theoretical analysis of Thompson
Sampling for cost-efficient online decision making, and present various
experimental results that demonstrate the applicability of our framework to
real-world problems.

**footnotetext: These authors contributed equally to this work.

##  1 Introduction

Online decision making (ODM) is concerned with interactions of an agent with
an environment through a series of sequential tests in order to acquire
sufficient information about the environment and successively learn how to
make better decisions. Each such test and decision can be associated with
either a reward or a cost. Here, we focus on problem settings where tests may
incur stochastic costs.

One such example is medical diagnosis. A patient arrives at a hospital with an
unknown affliction. In order to determine an appropriate treatment for the
patient, a number of medical tests need to be performed. Since each of these
tests might take time (which can differ depending on the test result and the
underlying affliction), be expensive or cause discomfort to the patient, it is
desirable to limit the set of tests to the most informative ones. On the other
hand, it is apparent that misdiagnosing the patient can have severe
consequences, so performing too few tests is also undesirable.

Another example is adaptive identification of driver preferences for in-car
navigation systems. Consider the selection of charging stations during long-
distance trips with battery-electric vehicles (BEVs). Since the duration of a
single charging stop can be as long as 40 minutes, it may be desirable to
select a charging station with additional amenities in close proximity, such
as restaurants, shops, or public restrooms. While it is possible to ask
questions through the vehicle user interface of drivers to learn their
charging location preferences, such questions should be kept few, short, and
simple. We note that in both of these examples, the problem instances (e.g.,
diagnosis of patients and identification of driver preferences) arrive
incrementally in an _online_ manner and should be processed accordingly.

We take a novel view of the online decision making problem described above,
where we cast it as a combinatorial multi-armed bandit problem (CMAB) (Cesa-
Bianchi and Lugosi, 2012), an extension of the classical multi-armed bandit
problem (MAB). The standard MAB problem is a common way of representing the
trade-off inherent to decision making problems between exploring an
environment by performing successive actions (playing arms, in bandit
nomenclature) to gain more knowledge and exploiting that knowledge to reach a
long-term objective. In a CMAB problem, an agent interacts with the
environment in each time step by performing a set of actions (a super arm),
where the set may be subject to combinatorial constraints. Each individual
action (base arm) in that set may result in some observed feedback (so-called
semi-bandit feedback), and the agent also receives a reward associated with
the complete super arm.

In this work, we view the combined choice of tests to perform and the selected
decision as a super arm in a CMAB problem where the underlying cost
distribution parameters are initially unknown, which allows us to leverage
effective MAB exploration strategies like Thompson Sampling (TS) (Thompson,
1933) and Upper Confidence Bound (UCB) (Auer et al., 2002) together with cost-
efficient (active) information acquisition methods, such as Equivalent Class
Edge Cutting (EC2) (Golovin et al., 2010) and Information Gain (IG) (Dasgupta,
2005). We summarize our contributions as follows.

  1. 1.

We study the problem of cost-efficient online decision making, where costs may
be stochastic and depend on both test and decision outcomes. For this, we
propose a novel combinatorial semi-bandit framework, providing a new
perspective on cost-efficient information acquisition.

  2. 2.

We adapt a number of bandit methods to this framework, namely Thompson
Sampling and Upper Confidence Bound, combined with novel extensions of EC2 and
IG which can handle tests with different and stochastic costs, which we call
W-EC2 and W-IG, respectively. Thereby, in addition to Thompson Sampling, we
develop W-EC2 and W-IG oracles utilizing a Bayesian variant of UCB (called
BayesUCB by Kaufmann et al. 2012) that is well adapted to our framework and
enables the UCB method to effectively employ prior knowledge in the form of a
prior distribution.

  3. 3.

We demonstrate the effectiveness of our framework via several experimental
studies performed on data sets from a variety of important domains. We find
that Thompson Sampling yields the best performance in most of the experiments
we perform.

  4. 4.

We theoretically analyze the performance of Thompson Sampling within our
framework for cost-efficient online decision making and establish an upper
bound on its Bayesian regret.

##  2 Related Work

#### Cost-efficient information acquisition.

The primary goal of cost-efficient information acquisition algorithms is to
sequentially select from a number of available costly tests to make a decision
(such as making a prediction about a label) with a minimal cost. To minimize
cost, these tests are performed until a sufficient level of confidence in the
decision is reached. Prominent algorithms for cost-efficient information
acquisition are Information Gain (IG) (Zheng et al., 2012), EC2 (Golovin et
al., 2010), and Uncertainty Sampling (US). Among them, EC2 has been proved to
enjoy adaptive submodularity (Golovin et al., 2010), and thus yields near-
optimal cost. The works of Rahbar et al. (2023); Chen et al. (2017) consider
active information acquisition in an online setting. The regret bounds in
these works are based on formulating the problem as a Partially Observable
Markov Decision Process (POMDP) and are _exponential_ in the total number of
possible tests. In this work, we consider a CMAB formulation of the problem
and derive a regret bound that is _linear_ in the number of tests (and
_sublinear_ w.r.t. the horizon $T$). In addition, unlike Rahbar et al. (2023);
Chen et al. (2017), our framework supports variability in the cost of the
tests depending on the outcomes of the tests and the decisions.

#### Combinatorial semi-bandit algorithms.

CMAB methods have been utilized to address online learning problems in various
settings but often without considering cost-efficient information acquisition.
Durand and Gagné (2014) adapt a combinatorial variant of Thompson Sampling for
_online feature selection_ where the agent has a fixed budget for tests and
the reward is a linear function of the test outcomes. Both assumptions are
used in later works studying the problem from a CMAB perspective (Bouneffouf
et al., 2017, 2021), but differ from the setting considered in this work
(e.g., the budget for information acquisition is fixed with no concept of
achieving a decision, and the costs are independent of the outcomes of the
tests and the decisions). Åkerblom et al. (2023) analyze the Bayesian regret
of combinatorial Thompson Sampling using a similar technique as this work
(originally developed by Russo and Van Roy (2014) for standard and linear
MAB), but for a very different super arm reward function and setting (for the
online minimax path problem, which does not consider cost-efficient
information acquisition and decision making).

##  3 Problem Formulation

In this section, we propose a new formulation of the online decision making
problem which incorporates the cost of acquiring test outcomes. In each time
step $t$, we receive the problem instance (e.g., data point)
$\mathbf{x}^{(t)}$ with $n$ tests
$\\{x_{1}^{(t)},x_{2}^{(t)},\dots,x_{n}^{(t)}\\}$. Here, we assume that all
test outcomes (unknown until after each test is performed) are binary (i.e.,
$x_{i}^{(t)}\in\\{0,1\\}$ for all $i$), but our methods can easily be extended
to other test values (see Section 6). The goal is to make an accurate decision
$y^{(t)}\in[m]$ for that problem instance with a minimal cost of performing
tests ($m$ represents the total number of options for the decision, or
_outcomes_ if the correct decision is viewed as a random variable), where we
denote the correct decision by $y^{*}$.

Consistent with the common Naïve Bayes assumption, we let all tests
$x_{i}^{(t)}$ be mutually independent and Bernoulli-distributed conditional on
the decision $y^{(t)}$. We also let $y^{*}$ be known given a full realization
of $\mathbf{x}^{(t)}$. This implies that upon performing all available tests,
we know the correct decision for the problem instance. This is realistic and
consistent with the settings of Golovin et al. (2010); Chen et al. (2017);
Rahbar et al. (2023), though they do not follow a CMAB formulation. As an
example, consider a medical diagnosis problem. This property means that if we
perform all available medical tests, we can determine the correct diagnosis.

Regarding the costs, we assume that they directly depend on the outcomes of
the tests and the decisions. As motivation, consider, for example, a medical
test to confirm the presence of some indicator for a particular disease. If
such an indicator is found, the test can be terminated immediately with a
positive outcome, whereas establishing the non-presence of an indicator (for a
negative test outcome) may require more time and be more invasive.

We model the problem described above by an elegant design of a stochastic
combinatorial multi-armed bandit (CMAB) problem (Cesa-Bianchi and Lugosi,
2012) with semi-bandit feedback. Briefly, CMAB corresponds to a reward
maximization problem with a set of base arms. In each time step, the agent
selects a subset of base arms. After playing this subset of base arms, called
a _super arm_ , the agent receives a reward from the environment. The
objective is to maximize the expected sum of rewards within a time horizon
$T$, which is typically formulated as a regret minimization task.

In our problem, since the costs of tests depend on both test and decision
outcomes, we need to consider a set of base arms that reflect both. Therefore,
we define the set $\mathcal{A}$ of $n\times m$ base arms $a_{ij}$ ($i\in[n]$
and $j\in[m]$). In each time step $t$, the agent selects a super arm
$S^{(t)}\in 2^{\mathcal{A}}$ and receives the reward $R(S^{(t)})=R^{(t)}$. A
base arm $a_{ij}$ in $S^{(t)}$ indicates that the test with index $i$ is
performed for making decision $y^{(t)}=j$. We define
$\mathcal{I}^{(t)}\subseteq 2^{\mathcal{A}}$ as the set of _feasible_ super
arms at time $t$ which yield a decision, i.e., each feasible super arm
consists of tests and a single decision (concretely, if $a_{ij},a_{lk}\in
S\in\mathcal{I}^{(t)}$, then $j=k$). The feedback at time $t$ of a base arm
$a_{ij}\in\mathcal{A}$ (observable by the agent if $a_{ij}\in S^{(t)}$) is the
corresponding outcome of test $x_{i}^{(t)}$, which given a decision
$y^{(t)}=j$ is Bernoulli-distributed with an unknown (to the agent) parameter
$\theta_{ij}\triangleq Pr(x_{i}=1|y=j)$, for all $i,j$. While tests may, in
practice, be selected sequentially, the super arm (and base arms) are only
known _in hindsight_ after the decision has been made. This is intentional and
allows us to analyze the problem as a CMAB.

We let the cost (assumed to be fixed and known) of each base arm $a_{ij}$ be
$\mu_{ij}^{(0)}\in[0,1]$ and $\mu_{ij}^{(1)}\in[0,1]$ (given test outcomes $0$
and $1$, respectively). Then, we define the expected reward of the selected
feasible super arm $S^{(t)}$ as the negative sum of expected base arm costs,
such that $\mathbb{E}[R(S^{(t)})]=-\sum_{ij\in S}\mu_{ij}$, where

$\mu_{ij}\triangleq\mu_{ij}^{(1)}\times\theta_{ij}+\mu_{ij}^{(0)}\times(1-\theta_{ij}),$
(1)

with the vector of all $\mu_{ij}$’s denoted by $\boldsymbol{\mu}$ and the
vector of all $\theta_{ij}$’s denoted by $\boldsymbol{\theta}$. We let
$\boldsymbol{\mu}^{*}$ be the true underlying mean cost vector, with
corresponding parameter vector $\boldsymbol{\theta}^{*}$. We define the
suboptimality gap at time $t$ of a feasible super arm $S$ as

$\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S)\triangleq
f_{\boldsymbol{\mu}^{*}}(S^{*,(t)})-f_{\boldsymbol{\mu}^{*}}(S),$ (2)

where $f_{\boldsymbol{\gamma}}(M)\triangleq(-\sum_{ij\in M}\gamma_{ij})$
denotes the expected reward of super arm $M$ given an arbitrary mean cost
vector $\boldsymbol{\gamma}$, and
$S^{*,(t)}\triangleq\operatorname*{argmax}_{S\in\mathcal{I}^{(t)}}f_{\boldsymbol{\mu}^{*}}(S)$
is the optimal super arm found by the oracle applied on the feasible set
$\mathcal{I}^{(t)}$. Then, the _regret_ (which the agent should minimize) for
a time horizon $T$ is defined as

$\text{Regret}_{\boldsymbol{\mu}^{*}}(T)\triangleq\sum_{t\in[T]}\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S^{(t)}).$
(3)

##  4 CMAB Methods for ODM

In our framework, we utilize _oracles_ (i.e., optimization algorithms) which,
given a parameter vector $\boldsymbol{\theta}$, output super arms with maximum
expected reward (or approximately, in the case of approximate oracles), such
that

$Oracle(\boldsymbol{\theta})\triangleq\operatorname*{argmax}_{S\in\mathcal{I}^{(t)}}\mathbb{E}\left[R(S)\right|\boldsymbol{\theta}].$
(4)

The $\theta_{ij}^{*}$ values of the true parameter vector
$\boldsymbol{\theta}^{*}$ are initially unknown, but to be able to employ
prior knowledge, we consider a prior distribution over $\theta_{ij}^{*}$’s.
Formally, we assume that each $\theta_{ij}^{*}$ follows a Beta distribution,
$\mathrm{Beta}(\alpha_{ij}^{(0)},\beta_{ij}^{(0)})$. We also assume a fixed
and known distribution over decision outcomes, denoted by $P(y)$ (i.e., the
learning agent knows the marginal distribution _a priori_). However, even if
the oracle is assumed to always be able to find the correct decision (i.e., it
only needs to minimize the number of tests), the optimization problem is NP-
hard, and thus in practice, we use approximate oracles (introduced in Section
4.1).

A _greedy_ method to address the problem defined in Section 3 is that in each
time step $t$, we use an oracle with the current (MAP) estimate of
$\boldsymbol{\theta}^{*}$. However, this greedy method may converge to a sub-
optimal super arm due to lack of exploration. To balance exploration and
exploitation, we adapt Thompson Sampling and BayesUCB to our problem.

#### Thompson Sampling.

Algorithm 1 summarizes our framework, with Thompson Sampling used as
exploration method. In each time step $t$, we sample the parameters from the
current posterior distribution (line 2). We then (in lines 3-4) use the
_oracle_ to get a super arm based on the sampled parameters, and perform the
tests sequentially. Finally, we use Algorithm 2 to update the posterior
distribution of the parameters. Algorithm 2 uses the fact that Beta
distribution is conjugate prior to the Bernoulli distribution111Since test
outcomes are binary, then, given decision $y=j$, each test $x_{i}$ follows a
Bernoulli distribution with parameter $\theta_{ij}$.

#### BayesUCB.

To utilize BayesUCB for exploration instead of Thompson Sampling, we have to
modify lines 2-3 of Algorithm 1 such that instead of sampling parameters from
the posterior distribution, we retrieve _optimistic_ parameter estimates. Like
Kaufmann et al. (2012) (done for classical bandits), we achieve this by
utilizing quantiles of the posterior distribution. However, since neither gain
function (Eq. 7 or Eq. 11) of the approximate oracles introduced in this
section is monotonically increasing w.r.t. the provided parameter vector
$\boldsymbol{\theta}$, a high value of a base arm parameter $\theta_{ij}$ does
not necessarily mean that test $i$ is more likely to be selected. Hence, with
$Q_{\lambda}(\eta)$ denoting the quantile function (such that under the
distribution $\lambda$, $\text{Pr}\left(X\leq Q_{\lambda}(\eta)\right)=\eta$),
we compute both an upper confidence bound
$\overline{\theta}^{(t)}_{ij}=Q_{\text{Beta}(\alpha_{ij}^{(t)},\beta_{ij}^{(t)})}(1-1/t)$
and a lower confidence bound
$\underline{\theta}^{(t)}_{ij}=Q_{\text{Beta}(\alpha_{ij}^{(t)},\beta_{ij}^{(t)})}(1/t)$
for each base arm $a_{ij}$, which we pass to the oracles. Then, while
computing Eq. 7 and Eq. 11, whenever a high value for a term involving
$\theta_{ij}$ makes the algorithm _more_ likely to select test $i$, we use
$\overline{\theta}^{(t)}_{ij}$ as an optimistic estimate, and correspondingly,
$\underline{\theta}^{(t)}_{ij}$ for terms making $i$ _less_ likely to be
selected.

Algorithm 1 Cost-efficient online decision making

0: $P(y)$; $\boldsymbol{\mu}$; prior parameters
$(\alpha_{ij}^{(0)},\beta_{ij}^{(0)}$)’s

1: for t = 1, 2, …, T do

2: Sample $\theta_{ij}^{(t)}$ from
$\mathrm{Beta}(\alpha_{ij}^{(t-1)},\beta_{ij}^{(t-1)})$ for all $i,j$.

3: $S^{(t)}\leftarrow Oracle(\boldsymbol{\theta}^{(t)})$ (e.g., Algorithm 3).

4: Make decision based on $S^{(t)}$, and observe $x_{i}^{(t)}$ for all $i$
such that $a_{ij}\in S^{(t)}$.

5: Observe correct decision $y^{(t)}$.

6: Call Algorithm 2 and obtain
$\mathrm{Beta}(\alpha_{ij}^{(t)},\beta_{ij}^{(t)})$ for all $i,j$.

7: end for

Algorithm 2 Posterior update

0: $S^{(t)}$; $x_{i}^{(t)}$ for all $i$ such that $a_{ij}\in S^{(t)}$;
$y^{(t)}=k$; $\alpha_{ij}^{(t-1)}$’s and $\beta_{ij}^{(t-1)}$’s

1: for each $x_{i}^{(t)}$ do

2: if $x_{i}^{(t)}=1$ then

3: $\alpha_{ik}^{(t)}$ $\leftarrow$ $\alpha_{ik}^{(t-1)}+1$

4: else

5: $\beta_{ik}^{(t)}$ $\leftarrow$ $\beta_{ik}^{(t-1)}+1$

6: end if

7: end for

###  4.1 Cost-Efficient Approximate Oracles

Solving the optimization problem in Eq. 4 is intractable in general (see,
e.g., Golovin et al. 2010; Chakaravarthy et al. 2007). Therefore, to implement
line 3 of Algorithm 1, we propose two different _approximate oracles_ using
algorithms that greedily select tests to optimize a surrogate objective
function, _Information Gain_ (IG) (Zheng et al., 2012) and EC2 (Golovin et
al., 2010). We introduce extensions of IG and EC2 to handle tests with
stochastic costs, which we call _Weighted IG_ (W-IG) and _Weighted EC 2_
(W-EC2) respectively. In both of these, all probabilities involved are
computed using the fixed and known decision distribution $P(y)$ and the
conditional distribution over test outcomes $P(\mathbf{x}|y)$ (determined by a
given parameter vector $\boldsymbol{\theta}$, see line 3 in Algorithm 1). In
particular, the dependence on $\boldsymbol{\theta}$ is omitted in the
following section to simplify notation.

Before introducing W-IG and W-EC2, we need to define the notions of
_hypothesis_ and _decision region_. We call a full realization of test
outcomes (i.e., of all possible tests) a hypothesis. Therefore, with $n$
binary tests, we have $2^{n}$ different possible hypotheses. Let
$\mathcal{H}\triangleq\\{0,1\\}^{n}$ be the set of all possible hypotheses for
$n$ tests. We can partition $\mathcal{H}$ into $m$ disjoint sets. We call each
of these disjoint sets a _decision region_. Each decision region corresponds
to a decision $y\in[m]$. So our objective will be finding the correct decision
region, for which the cost of performing tests is low. We want to emphasize
that one important difference between these oracles and standard CMAB oracles
is that they are _interactive_. In other words, during a single time step,
they sequentially perform tests and observe outcomes to select subsequent
tests and make a decision.

#### Weighted IG algorithm (W-IG).

In the standard IG algorithm, based on a set of previously observed test
outcomes, we select the test that maximizes the reduction of entropy in the
decision regions. Formally, the gain of a test $i$ in the IG algorithm is
defined as:

$\displaystyle\Delta_{\text{IG}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)\triangleq\mathbb{H}(y|\mathbf{x}_{\mathcal{P}})-\mathbb{E}_{x_{i}|\mathbf{x}_{\mathcal{P}}}[\mathbb{H}(y|\mathbf{x}_{\mathcal{P}\cup\\{i\\}})],$
(5)

where $\mathcal{P}$ is the set of previously performed tests, and
$\mathbf{x}_{\mathcal{P}}$ is the vector of results of tests in $\mathcal{P}$.
The random variable for decision regions is denoted $y$, and $\mathbb{H}(z)$
is the Shannon entropy of a random variable $z$. In the W-IG algorithm, we
sequentially perform tests that maximize
$\Delta_{\text{IG}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)$ divided with
the expected cost of test $i$ given the previously performed tests. In other
words, after performing and observing the outcomes of the tests in
$\mathcal{P}$, the next test to perform will be

$i^{*}=\operatorname*{argmax}_{i\in([n]\setminus\mathcal{P})}\Delta_{\text{W-IG}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right),$
(6)

where

$\Delta_{\text{W-IG}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)\triangleq\frac{\Delta_{\text{IG}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)}{\text{Cost($i$)}},$
(7)

and

$\text{Cost($i$)}\triangleq\sum_{j\in[m]}\sum_{q\in\\{0,1\\}}\mu_{ij}^{(q)}\times
Pr\left(x_{i}=q,y=j\mid\mathbf{x}_{\mathcal{P}}\right),$ (8)

given test outcome costs $\mu_{ij}^{(0)}$ and $\mu_{ij}^{(1)}$ for all $i,j$.
We call the set of hypotheses $\mathcal{H}_{i}=\\{h|P(x_{i}|h)>0\\}$
_consistent_ with the outcome of test $i$. We continue performing tests until
all hypotheses in $\bigcap\limits_{i\in\mathcal{P}}\mathcal{H}_{i}$ belong to
the same decision region, i.e., there is only one decision region remaining.

#### Weighted EC2 algorithm (W-EC2).

The standard EC2 algorithm starts with a graph with $\mathcal{H}$ as the set
of nodes. We have an edge $(h,h^{\prime})$ between two hypotheses $h$ and
$h^{\prime}$ if and only if they do not belong to the same decision region.
The weight of an edge $(h,h^{\prime})$ is set to
$w_{hh^{\prime}}=P(h\mid\mathbf{x}_{\mathcal{P}})\times
P(h^{\prime}\mid\mathbf{x}_{\mathcal{P}})$ where
$P(\cdot\mid\mathbf{x}_{\mathcal{P}})$ is the posterior distribution of a
hypotheses after performing tests. Naturally, the weight of a set of edges
$\mathcal{E}$ is defined as the sum of weights of edges in $\mathcal{E}$,
i.e.,
$w(\mathcal{E})\triangleq\sum_{(h,h^{\prime})\in\mathcal{E}}w_{hh^{\prime}}$.
We say that performing a test $i$ _cuts_ an edge $(h,h^{\prime})$ if
$h\notin\mathcal{H}_{i}$ or $h^{\prime}\notin\mathcal{H}_{i}$. We denote the
set of edges cut by test $i$ with $K(i)$.

We now define the objective function for the EC2 algorithm as

$f_{\text{EC}^{2}}\left(\mathcal{P}\right)\triangleq
w\left(\bigcup_{i\in\mathcal{P}}K(i)\right).$ (9)

Based on the objective function above, we define the EC2 gain of a test $i$ as

$\Delta_{\text{EC}^{2}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)\triangleq\mathbb{E}_{x_{i}|\mathbf{x}_{\mathcal{P}}}\left[f_{\text{EC}^{2}}\left(\mathcal{P}\cup\\{i\\}\right)-f_{\text{EC}^{2}}\left(\mathcal{P}\right)\right],$
(10)

and, similar to W-IG, the W-EC2 gain as

$\Delta_{\text{W-EC}^{2}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)\triangleq\frac{\Delta_{\text{EC}^{2}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)}{\text{Cost($i$)}},$
(11)

with $\text{Cost}(i)$ defined as in Eq. 8.

Also like with W-IG, in the W-EC2 algorithm, we sequentially perform tests
that maximize
$\Delta_{\text{W-EC}^{2}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)$. We stop
performing tests when all edges are cut, meaning that there is only one
decision region left.

To be able to implement W-IG and W-EC2 (calculate $\Delta_{\text{W-IG}}$ and
$\Delta_{\text{W-EC}\textsuperscript{2}}$), similar to standard IG and EC2, we
assume that the outcomes of the tests are conditionally independent given the
decision. We show the test selection process in W-IG and W-EC2 algorithms in
Algorithm 3.

Algorithm 3 Cost-efficient approximate oracle

0: $\text{Alg}\in\\{\text{W-IG},\text{W-EC}^{2}\\}$; $P(y)$;
$\boldsymbol{\mu}$; $\boldsymbol{\theta}$

1: Enumerate hypotheses in $\mathcal{H}$

2: $\mathcal{P}=\\{\\}$

3: while more than one decision region left do

4: Select next test (with $\Delta_{\text{Alg}}(\cdot)$ computed w.r.t.
$\boldsymbol{\theta}$)
$i^{*}=\operatorname*{argmax}\limits_{i\in([n]\setminus\mathcal{P})}\Delta_{\text{Alg}}\left(i\mid\mathbf{x}_{\mathcal{P}}\right)$.

5: Perform test $i^{*}$ and observe $x_{i^{*}}$.

6: Update $P(h\mid\mathbf{x}_{\mathcal{P}})$ based on results of tests in
$\mathcal{P}$.

7: end while

8: Select the decision associated to the remaining decision region.

##  5 Theoretical Analysis

In this section, we theoretically analyze the framework proposed in Section 4.
Specifically, we provide an upper bound on the Bayesian regret (defined below)
of the online decision making procedure in Algorithm 1.

In our problem setting, the set of feasible super arms $\mathcal{I}^{(t)}$ is
restricted such that $y^{(t)}=y^{*}$ (i.e., we study the setting where correct
decisions are guaranteed, and the objective is to minimize the cost of tests),
and we assume that we have access to a perfect _oracle_ which can solve the
optimization problem Eq. 4.

The Bayesian regret is defined as the expected value of $\text{Regret}(T)$
(see Eq. 3), with the expectation taken over the prior distribution of
$\boldsymbol{\mu}^{*}$ and other random variables (e.g., randomness in the
rewards and the policy of the agent).

$\text{Bayesian
Regret}(T)\triangleq\mathbb{E}\left[\sum_{t\in[T]}\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S^{(t)})\right].$
(12)

We then prove the following theorem which establishes an upper bound on the
Bayesian regret of Thompson Sampling applied to our framework.

######  Theorem 5.1.

The Bayesian Regret of Algorithm 1 is $\mathcal{O}(mn\sqrt{T\log T})$.

###### Proof.

We begin our regret analysis by presenting a decomposition of
$\mathbb{E}[\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S^{(t)})]$ in the following
lemma.

######  Lemma 5.2.

For any upper confidence bound
$U^{(t)}:\mathcal{I}^{(t)}\rightarrow\mathbb{R}$ and lower confidence bound
$L^{(t)}:\mathcal{I}^{(t)}\rightarrow\mathbb{R}$ we have

$\mathbb{E}[\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S^{(t)})]=\mathbb{E}[U^{(t)}(S^{(t)})-L^{(t)}(S^{(t)})]+\mathbb{E}[L^{(t)}(S^{(t)})-f_{\boldsymbol{\mu}^{*}}(S^{(t)})]+\mathbb{E}[f_{\boldsymbol{\mu}^{*}}(S^{*,(t)})-U^{(t)}(S^{*,(t)})].$
(13)

###### Proof.

We give the full proof, which is based on Proposition 1 of Russo and Van Roy
(2014), in Appendix A. ∎

Additionally, we define lower and upper confidence bounds as follows:

$L^{(t)}(S)\triangleq f_{\hat{\boldsymbol{\mu}}^{(t-1)}}(S)-\sum_{ij\in
S}\sqrt{\frac{2\log T}{N^{(t-1)}(ij)}}$ (14)

$U^{(t)}(S)\triangleq f_{\hat{\boldsymbol{\mu}}^{(t-1)}}(S)+\sum_{ij\in
S}\sqrt{\frac{2\log T}{N^{(t-1)}(ij)}}$ (15)

where $\hat{\mu}^{(t)}_{ij}$ is the average cost of base arm $a_{ij}$ till
time $t$, and $N^{(t)}(ij)$ is the number of times base arm $a_{ij}$ has been
played till time $t$. We continue by bounding each term in Eq. 13.

$\mathbb{E}[L^{(t)}(S^{(t)})-f_{\boldsymbol{\mu}^{*}}(S^{(t)})]$
$=\mathbb{E}\Bigg{[}-\sum_{ij\in S^{(t)}}\hat{\mu}^{(t-1)}_{ij}-\sum_{ij\in
S^{(t)}}\sqrt{\frac{2\log T}{N^{(t-1)}(ij)}}+\sum_{ij\in
S^{(t)}}\mu^{*}_{ij}\Bigg{]}$

$=\sum_{ij\in
S^{(t)}}\mathbb{E}\Bigg{[}-\hat{\mu}^{(t-1)}_{ij}-\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}+\mu^{*}_{ij}\Bigg{]}$

$\leq\sum_{ij\in
S^{(t)}}\mathbb{E}\Bigg{[}\Big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\Big{|}-\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{]}$

($[z]^{+}=\max\\{0,z\\}$)

$\leq\sum_{ij\in\mathcal{A}}\mathbb{E}\Bigg{[}\Bigg{[}\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}-\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{]}^{+}\Bigg{]}$

$\begin{split}=\sum_{ij\in\mathcal{A}}\Bigg{(}\mathbb{E}\Bigg{[}\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}-\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{|}\text{``bad event''}\Bigg{]}\times Pr\\{\text{``bad
event''}\\}\Bigg{)},\end{split}$ (16)

where “bad event” is
$\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}>\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}$.

The last equality comes from the fact that
$\Big{[}|\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}|-\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\text{ }\Big{]}^{+}=0$ if
$\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}\leq\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}$. We continue with the following lemma.

######  Lemma 5.3.

$Pr\Bigg{\\{}\exists t\in[T]\;\exists
ij\in\mathcal{A},|\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}>\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{\\}}\leq\frac{2}{T}$.

###### Proof.

To prove Lemma 5.3, we use Eq. 1 which implies that
$|\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}=|\mu_{ij}^{(1)}-\mu_{ij}^{(0)}||\theta_{ij}^{*}-\hat{\theta}_{ij}^{(t-1)}|$
together with the fact that $|\mu_{ij}^{(1)}-\mu_{ij}^{(0)}|\leq 1$, as well
as Hoeffding’s inequality. The full proof is given in Appendix A. ∎

Continuing from Eq. 16, using Lemma 5.3, and noting that
$\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}\leq 1$ we have

$\mathbb{E}[L^{(t)}(S^{(t)})-f_{\boldsymbol{\mu}^{*}}(S^{(t)})]\leq\sum_{ij\in\mathcal{A}}\frac{2}{T}=\frac{2mn}{T}.$
(17)

We can similarly show that

$\mathbb{E}[f_{\boldsymbol{\mu}^{*}}(S^{*,(t)})-U^{(t)}(S^{*,(t)})]\leq\frac{2mn}{T}.$
(18)

In order to bound the last term of the regret decomposition, we utilize the
following lemma.

######  Lemma 5.4.

$\sum_{t\in[T]}\mathbb{E}[U^{(t)}(S^{(t)})-L^{(t)}(S^{(t)})]\leq
2mn\sqrt{8T\log T}.$

###### Proof.

We prove Lemma 5.4 using a similar technique as Lemma 8 by Åkerblom et al.
(2023) for the combinatorial batched feedback setting (with batch size 1). See
Appendix A for the full proof. ∎

Now, based on Eq. 17, Eq. 18, Eq. 13, and Lemma 5.4 we have

$\text{Bayesian Regret}(T)\leq 4mn+2mn\sqrt{8T\log
T}=\mathcal{O}(mn\sqrt{T\log T}).$ (19)

∎

We utilize the structure of the problem in our analysis and thereby, the bound
derived in Theorem 5.1 is significantly tighter than the ones by Rahbar et al.
(2023); Chen et al. (2017) which take a different perspective than our CMAB
formulation. Our bound is also consistent with Bayesian upper bounds for
combinatorial semi-bandit methods developed in other settings.

Table 1: Average cost ($\pm$ standard deviation) of decision making in a time
step (over the entire learning period).

Data set \Algorithm | W-EC2-TS | W-EC2-BUCB | W-IG-TS | W-IG-BUCB | Random | All | DPP
---|---|---|---|---|---|---|---
Navigation | 1.746 $\pm$ 0.030 | 1.746 $\pm$ 0.030 | 1.859 $\pm$ 0.020 | 1.867 $\pm$ 0.023 | 1.975 $\pm$ 0.008 | 2.305 $\pm$ 0.000 | 2.300 $\pm$ 0.002
LED | 2.032 $\pm$ 0.053 | 2.061 $\pm$ 0.059 | 2.418 $\pm$ 0.015 | 2.438 $\pm$ 0.019 | 2.644 $\pm$ 0.025 | 3.147 $\pm$ 0.000 | 3.137 $\pm$ 0.002
Fico | 1.159 $\pm$ 0.003 | 1.101 $\pm$ 0.002 | 1.935 $\pm$ 0.075 | 2.067 $\pm$ 0.064 | 3.078 $\pm$ 0.005 | 8.353 $\pm$ 0.000 | 8.249 $\pm$ 0.056
Compas | 3.056 $\pm$ 0.009 | 3.090 $\pm$ 0.017 | 4.197 $\pm$ 0.039 | 4.034 $\pm$ 0.028 | 4.719 $\pm$ 0.006 | 6.101 $\pm$ 0.000 | 5.923 $\pm$ 0.049
Breast cancer | 1.437 $\pm$ 0.019 | 1.554 $\pm$ 0.032 | 2.091 $\pm$ 0.048 | 2.213 $\pm$ 0.136 | 6.376 $\pm$ 0.087 | 14.181 $\pm$ 0.000 | 9.286 $\pm$ 0.077
Troubleshooting | 6.207 $\pm$ 0.013 | 7.615 $\pm$ 0.034 | 12.010 $\pm$ 0.078 | 12.563 $\pm$ 0.117 | 23.236 $\pm$ 0.072 | 38.113 $\pm$ 0.000 | 24.538 $\pm$ 0.309

Figure 1: Decision making costs of our framework applied to four different
data sets.

##  6 Experiments

In this section, we empirically validate our cost-efficient online decision
making framework via various experiments. Unless otherwise specified, we
consider Beta(2,2) as the prior distribution of all $\theta_{ij}^{*}$’s. We
employ both of the cost-efficient approximate oracles introduced in Section
4.1 (W-IG and W-EC2) as the oracle in Algorithm 1. We also employ the
hypothesis enumeration procedure proposed in Chen et al. (2017) to generate
the most likely hypotheses for each decision region. In Appendix B, we
demonstrate the applicability of our framework in the setting where the
decision regions for the set of hypotheses are not known. Moreover, in Section
6.2, we provide an extension of our framework to real-valued non-binary test
outcomes. We run each experiment with 5 different random seeds.

#### Data sets.

We apply our framework to the LED display domain data set from the UCI
repository (Breiman et al., 1988). Additionally, we use the ProPublica
recidivism (Compas) data set (Larson et al., 2016) and the Fair Isaac (Fico)
credit risk data set (FICO et al., 2018), which both are preprocessed in the
same way as by Hu et al. (2019). The aforementioned data sets contain
relatively large numbers of tests and few decision outcomes, which correspond
well to, e.g., the medical diagnosis example in Section 1. In applications
like the charging station selection example, it might instead be reasonable to
expect a large number of decision outcomes (individual charging stations or
groups sharing certain characteristics) and relatively few tests (questions).
Hence, in order to thoroughly evaluate the latter type of setting, we create a
synthetic data set (called Navigation) with the desired characteristics. With
$n=5$ tests and $m=20$ decision outcomes, we sample parameters
$\theta_{ij}^{*}$ from the prior distribution Beta(2,2) for each $i\in[n]$ and
$j\in[m]$, which subsequently use to generate the data set. Moreover, to
demonstrate the applicability of our methods to real-valued test outcomes, we
investigate the Breast Cancer Wisconsin data set (Street et al., 1993)
(Section 6.2). Finally, in Section 6.3, we present the application of our
framework to a real-world troubleshooting case study.

#### Algorithms.

In our experiments, we investigate the cost of decision making using both W-IG
and W-EC2 algorithms embedded in our framework (Algorithm 1). For each
algorithm, we investigate both Thompson Sampling and BayesUCB for exploration.
In addition to Thompson Sampling (TS) and BayesUCB (BUCB), we consider the
following baselines for selecting tests in each time step:

  * •

Random Information Acquisition. Within our framework, we can use a random
subset of tests decision making. This baseline continues performing random
tests until only one decision region is left (similar to W-IG and W-EC2).

  * •

All. This baseline always performs all available tests, and does not consider
the cost.

  * •

DPP. Determinantal Point Process (DPP) provides a way to select diverse sets.
With this method, we use exact sampling (Derezinski et al., 2019) (finite DPP
with likelihood kernel) to subsample columns (tests). We use the
implementation of Gautier et al. (2019). To perform the sampling, in each time
step $t$, we provide all data points (all test results for all data points)
until time $t-1$ to the sampler. The number of tests selected by the sampler
is related to the number of eigenvectors of the kernel matrix.

###  6.1 Experimental Results

We first investigate the four data sets Navigation, LED, Fico, and Compas. As
mentioned, to guarantee accurate decision regions for all hypotheses, we
implement the algorithm outlined by Chen et al. (2017) for enumeration of
hypotheses. In short, this algorithm produces the most probable hypotheses
based on a decision and the conditional probabilities of test outcomes
associated with that decision. To assign the correct decisions to hypotheses,
we extract the parameter vector $\boldsymbol{\theta}$ from the entire data set
and subsequently utilize the enumeration procedure to generate the most likely
hypotheses for each decision. However, the parameters are not known to the
agent after the enumeration of hypotheses. We assign fixed costs
$\mu_{ij}^{(0)}\in[0,1]$ and $\mu_{ij}^{(1)}\in[0,1]$ (randomly sampled from a
uniform distribution) for each data set before performing our experiments.

In Figure 1, we illustrate the cost of performing tests (i.e.,
$-\mathbb{E}[R(S^{(t)})]$) during online learning for different algorithms.
The cost of each test is calculated based on Eq. 1, where the parameter
$\theta_{ij}$ is derived from the data. Our results in Figure 1 show that our
framework yields the lowest information acquisition cost for all data sets.
DPP has a low cost initially since it only uses a few data points to perform
sampling, but after a few time steps its cost becomes as high as ‘All’.
Additionally, we observe that the W-EC2 algorithm always has the lowest cost.
This result is consistent with the theoretical results of Golovin et al.
(2010) for the cost of the original EC2 algorithm in the offline setting. We
also observe that the exploration methods (TS and BayesUCB) exhibit very
similar performances in terms of cost.

During online learning, it is observed that the cost of the random algorithm
remains relatively constant, whereas the costs associated with the W-IG and
W-EC2 algorithms decrease until they converge to a low value. This behavior is
attributed to the utilization of parameter estimates by the W-IG and W-EC2
algorithms when selecting tests. As the knowledge of the agent about these
parameters improves over the course of learning, the associated costs decline.

Furthermore, in Table 1, we report the average cost of decision making in a
single time step for different data sets. It is obvious that our framework
incurs significantly lower costs for performing tests.

###  6.2 Extension to Real-Valued Test Outcomes

In this section, we extend our experimental results to real-valued (non-
binary) test outcomes. For this purpose, we adapt the discretization method
proposed by Rahbar et al. (2023). Specifically, for each test, we consider
different thresholds for “binarization”. Then, in each time step, we can
calculate the gain ($\Delta_{\text{W-IG}}$ or $\Delta_{\text{W-EC}^{2}}$) for
the tests using different binarization thresholds and choose the one with a
maximal gain. We employ this method on the Breast Cancer Wisconsin data set.
In this data set, we predict the diagnosis from 30 real-valued medical tests
computed from an image of a fine needle aspirate. Figure 2 illustrates the
decision making cost incurred by our framework when applied to this data set.
Similar to the results depicted in Figure 1, our framework consistently
achieves the lowest cost, demonstrating its effectiveness in this setting. In
particular, we observe that W-EC2-TS yields the best results, and W-IG-TS,
W-EC2-BUCB, and W-IG-BUCB are other suitable methods for this task.

Figure 2: Decision making costs of our framework extended to real-valued test
outcomes in the Breast Cancer Wisconsin data set.

###  6.3 Application to Online Troubleshooting

In this section, we study the application of our decision making framework for
online troubleshooting. The data set for this _real-world_ application is
collected from contact center agents. The agents solve problems from mobile
devices. We use a subset of this data set with 15 possible decisions and 74
tests. Each test corresponds to a symptom that a customer may or may not see
on the device.

We experiment on approximately 1500 different scenarios (i.e., roughly 100
scenarios for each decision). A scenario starts with a customer entering the
system. Then the online learning agent aims at finding the correct decision by
asking a sequence of multiple questions of the customer (performing tests).
The goal for the agent is to ask the most informative questions in a cost-
efficient manner.

Figure 3 shows the cost of making decisions for different time steps (i.e.,
scenarios) in the same setting as Section 6.1. The results show that our
framework enables the agent to find the correct decisions for troubleshooting
in mobile devices with a significantly lower cost compared to other methods.
Similar to previous observations, the W-EC2 algorithm remains the most cost-
effective method within our framework.

Figure 3: Decision making costs of our framework when applied to online
troubleshooting.

##  7 Conclusion

We propose a novel framework for online decision making based on an elegant
design of a combinatorial multi-armed bandit problem, which incorporates the
cost of performing tests, and where the costs may be stochastic and depend on
both test and decision outcomes. Within this framework, we develop various
cost-efficient online decision making methods such as W-EC2 and W-IG. We also
adapt Thompson Sampling and BayesUCB, methods that are commonly used for
exploration. In particular, we provide a theoretical upper bound for the
Bayesian regret of Thompson Sampling. We finally demonstrate the performance
of the framework on a number of data sets from different domains.

## Acknowledgments

The work of Arman Rahbar and Morteza Haghir Chehreghani was partially
supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP)
funded by the Knut and Alice Wallenberg Foundation. The work of Niklas
Åkerblom was partially funded by the Strategic Vehicle Research and Innovation
Programme (FFI) of Sweden, through the project EENE (reference number:
2018-01937).

## References

  * Cesa-Bianchi and Lugosi [2012] Nicolo Cesa-Bianchi and Gábor Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404–1422, 2012.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47:235–256, 2002.
  * Golovin et al. [2010] Daniel Golovin, Andreas Krause, and Debajyoti Ray.  Near-optimal bayesian active learning with noisy observations.  _Advances in Neural Information Processing Systems_ , 23, 2010.
  * Dasgupta [2005] Sanjoy Dasgupta.  Analysis of a greedy active learning strategy.  _Advances in neural information processing systems_ , 17:337–344, 2005.
  * Kaufmann et al. [2012] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On bayesian upper confidence bounds for bandit problems.  In _Artificial intelligence and statistics_ , pages 592–600. PMLR, 2012.
  * Zheng et al. [2012] Alice X Zheng, Irina Rish, and Alina Beygelzimer.  Efficient test selection in active diagnosis via entropy approximation.  _arXiv preprint arXiv:1207.1418_ , 2012.
  * Rahbar et al. [2023] Arman Rahbar, Ziyu Ye, Yuxin Chen, and Morteza Haghir Chehreghani.  Efficient online decision tree learning with active feature acquisition.  _International Joint Conference on Artificial Intelligence (IJCAI)_ , 32, 2023.
  * Chen et al. [2017] Yuxin Chen, Jean-Michel Renders, Morteza Haghir Chehreghani, and Andreas Krause.  Efficient online learning for optimizing value of information: Theory and application to interactive troubleshooting.  In _Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI 2017)_ , 2017.
  * Durand and Gagné [2014] Audrey Durand and Christian Gagné.  Thompson sampling for combinatorial bandits and its application to online feature selection.  In _Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence_ , 2014.
  * Bouneffouf et al. [2017] Djallel Bouneffouf, Irina Rish, Guillermo A. Cecchi, and Raphaël Féraud.  Context attentive bandits: Contextual bandit with restricted context.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , IJCAI’17, page 1468–1475. AAAI Press, 2017.  ISBN 9780999241103.
  * Bouneffouf et al. [2021] Djallel Bouneffouf, Raphael Feraud, Sohini Upadhyay, Irina Rish, and Yasaman Khazaeni.  Toward optimal solution for the context-attentive bandit problem.  In Zhi-Hua Zhou, editor, _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pages 3493–3500. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  doi:10.24963/ijcai.2021/481.  URL https://doi.org/10.24963/ijcai.2021/481.  Main Track.
  * Åkerblom et al. [2023] Niklas Åkerblom, Fazeleh Sadat Hoseini, and Morteza Haghir Chehreghani.  Online learning of network bottlenecks via minimax paths.  _Machine Learning_ , 112(1):131–150, 2023.
  * Russo and Van Roy [2014] Daniel Russo and Benjamin Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Chakaravarthy et al. [2007] Venkatesan T Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania.  Decision trees for entity identification: Approximation algorithms and hardness results.  In _Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 53–62, 2007.
  * Breiman et al. [1988] L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone.  LED Display Domain.  UCI Machine Learning Repository, 1988.
  * Larson et al. [2016] J. Larson, S. Mattu, L. Kirchner, and J. Angwin.  How we analyzed the compas recidivism algorithm.  _SIAM journal on computing_ , 2016.
  * FICO et al. [2018] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berkeley.  Explainable machine learning challenge, 2018.  URL https://community.fico.com/s/explainable-machine-learning-challenge.
  * Hu et al. [2019] Xiyang Hu, Cynthia Rudin, and Margo Seltzer.  Optimal sparse decision trees.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Street et al. [1993] W Nick Street, William H Wolberg, and Olvi L Mangasarian.  Nuclear feature extraction for breast tumor diagnosis.  In _Biomedical image processing and biomedical visualization_ , volume 1905, pages 861–870. SPIE, 1993.
  * Derezinski et al. [2019] Michal Derezinski, Daniele Calandriello, and Michal Valko.  Exact sampling of determinantal point processes with sublinear time preprocessing.  _Advances in neural information processing systems_ , 32, 2019.
  * Gautier et al. [2019] Guillaume Gautier, Guillermo Polito, Rémi Bardenet, and Michal Valko.  DPPy: DPP Sampling with Python.  _Journal of Machine Learning Research - Machine Learning Open Source Software (JMLR-MLOSS)_ , 2019.  URL http://jmlr.org/papers/v20/19-179.html.  Code at http://github.com/guilgautier/DPPy/ Documentation at http://dppy.readthedocs.io/.
  * Slivkins et al. [2019] Aleksandrs Slivkins et al.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ , 12(1-2):1–286, 2019.

##  Appendix A Additional Proofs

###  A.1 Proof of Lemma 5.2

###### Proof.

This lemma is based on Proposition 1 of Russo and Van Roy [2014]. Given the
history of played super arms (and base arms) and their rewards, we know that
in Thompson Sampling the optimal super arm $S^{*,(t)}$ and the played super
arm $S^{(t)}$ follow the same distribution. Since $U^{(t)}(\cdot)$ is a
deterministic function, we conclude that given the history, the expected
values of $U^{(t)}(S^{(t)})$ and $U^{(t)}(S^{*,(t)})$ are equal, and we have:

$\mathbb{E}[\Delta^{(t)}_{\boldsymbol{\mu}^{*}}(S^{(t)})]=\mathbb{E}[U^{(t)}(S^{(t)})-f_{\boldsymbol{\mu}^{*}}(S^{(t)})]+\mathbb{E}[f_{\boldsymbol{\mu}^{*}}(S^{*,(t)})-U^{(t)}(S^{*,(t)})],$

and by adding and subtracting $\mathbb{E}[L^{(t)}(S^{(t)})]$ we prove 13. ∎

###  A.2 Proof of Lemma 5.3

###### Proof.

Let $\bar{x}_{ij}^{(\tau)}$ be the average of first $\tau$ observations of
$x_{i}$ under the decision region $y=j$. We have:

$Pr\Bigg{\\{}\exists t\in[T]\;\exists
ij\in\mathcal{A},\big{|}\mu^{*}_{ij}-\hat{\mu}^{(t-1)}_{ij}\big{|}>\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{\\}}$

$\begin{split}\stackrel{{\scriptstyle Eq.6}}{{=}}Pr\Bigg{\\{}\exists
t\in[T]\;\exists
ij\in\mathcal{A},\big{|}\mu_{ij}^{(1)}-\mu_{ij}^{(0)}\big{|}\big{|}\theta_{ij}^{*}-\hat{\theta}_{ij}^{(t-1)}\big{|}>\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{\\}}\end{split}$

(since $\big{|}\mu_{ij}^{(1)}-\mu_{ij}^{(0)}\big{|}\leq 1$)

$\leq Pr\Bigg{\\{}\exists t\in[T]\;\exists
ij\in\mathcal{A},\big{|}\theta_{ij}^{*}-\hat{\theta}_{ij}^{(t-1)}\big{|}>\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{\\}}$

(Union bound)

$\leq\sum_{t\in[T]}\sum_{ij\in\mathcal{A}}\sum_{\tau=1}^{(t-1)}Pr\Bigg{\\{}\big{|}\theta_{ij}^{*}-\bar{x}_{ij}^{(\tau)}\big{|}>\sqrt{\frac{2\log
T}{\tau}}\Bigg{\\}}$

(assuming $T\geq|\mathcal{A}|$)

$\leq T^{3}\times 2T^{-4}=\frac{2}{T}.$

The last inequality is due to Hoeffding’s inequality (e.g., Theorem A.1 of
Slivkins et al. [2019] with $\alpha=2$).

∎

###  A.3 Proof of Lemma 5.4

###### Proof.

$\sum_{t\in[T]}\mathbb{E}[U^{(t)}(S^{(t)})-L^{(t)}(S^{(t)})]$

$=\sum_{t\in[T]}\mathbb{E}\Bigg{[}2\sum_{ij\in S^{(t)}}\sqrt{\frac{2\log
T}{N^{(t-1)}(ij)}}\Bigg{]}$

$\leq\sqrt{8\log T}\sum_{t\in[T]}\mathbb{E}\Bigg{[}\sum_{ij\in
S^{(t)}}\frac{1}{\sqrt{N^{(t-1)}(ij)}}\Bigg{]}$

$=\sqrt{8\log T}\sum_{ij\in\mathcal{A}}\mathbb{E}\Bigg{[}\sum_{t:ij\in
S^{(t)}}\frac{1}{\sqrt{N^{(t-1)}(ij)}}\Bigg{]}$

$=\sqrt{8\log
T}\sum_{ij\in\mathcal{A}}\mathbb{E}\Bigg{[}\sum_{l\in[N^{(T)}(ij)]}\frac{1}{\sqrt{l}}\Bigg{]}$

(Lemma 1 of Russo and Van Roy 2014)

$\leq 2\sqrt{8\log
T}\sum_{ij\in\mathcal{A}}\mathbb{E}\Bigg{[}\sqrt{N^{(T)}(ij)}\Bigg{]}$

(Cauchy–Schwarz inequality)

$\leq 2\sqrt{8\log
T}\;\mathbb{E}\Bigg{[}\sqrt{mn\sum_{ij\in\mathcal{A}}N^{(T)}(ij)}\Bigg{]}$

$\leq 2\sqrt{8\log T}\;\mathbb{E}\Bigg{[}\sqrt{(mn)(mn)T}\Bigg{]}$

$=2mn\sqrt{8T\log T}.$

∎

##  Appendix B Additional Experimental Results

In this section, to demonstrate the generality of our framework, we examine
the setting where the decision regions for the enumerated hypotheses are not
known. This situation may lead to incorrect decisions by the agent.
Specifically, in the context of online learning, our objectives are: i) to
achieve highly accurate decisions, and ii) to minimize the cost of performing
tests. To quantify the accuracy of the decisions, we employ a utility
function. Specifically, we assign a utility of $2$ for a correct decision and
$-1$ for an incorrect one. Additionally, we consider an “unknown" decision
when the correct hypothesis is assigned to multiple decision regions. We
define the utility of such decisions as 0.

The upper row in Figure 4 shows the cost of making decisions for different
data sets (when the correct decisions of the hypotheses are not known).
Similar to the findings in Figure 1, we observe that our framework (with both
W-IG and W-EC2) yields a final decision with significantly lower cost than
other algorithms. Again, we observe that EC2 (with both Thompson Sampling and
BayesUCB) has the lowest cost of performing tests. The IG algorithm results in
the second lowest cost, and the random algorithm for picking tests is the
third option.

As previously mentioned, when faced with unknown decision regions, our goal is
to enhance the accuracy of our decisions during online learning. The lower row
in Figure 4 illustrates the utility achieved by various information
acquisition algorithms. Notably, our framework demonstrates comparable
performance to both All and DPP in the early stages of learning. Therefore,
our approach proves capable of making precise decisions with a significantly
reduced cost. We note that DPP yields very low costs in the early time steps,
but the corresponding utility is also very low.

Figure 4: Decision making cost (upper row) and utility (lower row) of our
framework applied to the setting that the decision regions are not known
beforehand.