Efficient and Interpretable Bandit Algorithms

Subhojyoti Mukherjee Ruihao Zhu Branislav Kveton ECE Department SC Johnson
College of Business AWS AI Labs∗

University of Wisconsin, Madison Cornell University Amazon

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Motivated by the importance of explainability in modern machine learning, we
design bandit algorithms that are _efficient_ and _interpretable_. A bandit
algorithm is interpretable if it explores with the objective of reducing
uncertainty in the unknown model parameter. To quantify the interpretability,
we introduce a novel metric of uncertainty loss, which compares the rate of
the uncertainty reduction to the theoretical optimum. We propose CODE, a
bandit algorithm based on a Constrained Optimal DEsign, that is interpretable
and maximally reduces the uncertainty. The key idea in CODE is to explore
among all plausible actions, determined by a statistical constraint, to
achieve interpretability. We implement CODE efficiently in both multi-armed
and linear bandits and derive near-optimal regret bounds by leveraging the
optimality criteria of the approximate optimal design. CODE can be also viewed
as removing phases in conventional phased elimination, which makes it more
practical and general. We demonstrate the advantage of CODE by numerical
experiments on both synthetic and real-world problems. CODE outperforms other
state-of-the-art interpretable designs while matching the performance of
popular but uninterpretable designs, such as upper confidence bound
algorithms.

##  1 Introduction

A _multi-armed bandit (MAB)_ is a class of sequential decision-making problems
that have gained significant attention in various fields, including machine
learning, economics, and operations research, due to their broad applicability
in real-world scenarios, such as clinical trials (Thompson, 1933; Agrawal and
Goyal, 2012), online advertising (Li et al., 2010; Foster and Krishnamurthy,
2021), and recommender systems (Li et al., 2016; Eide and Zhou, 2018; Bendada
et al., 2020; Mehrotra et al., 2020). In MAB, the goal is to maximize the
cumulative reward by interacting with a set of actions under an initially
unknown model parameter. Therefore, we have to balance exploration (learning
the parameter) and exploitation (reward maximization). Two notable approaches
that efficiently balance exploration and exploitation are an _upper confidence
bound (UCB)_ (Auer et al., 2002; Abbasi-Yadkori et al., 2011) and _Thompson
sampling (TS)_ (Agrawal and Goyal, 2012, 2013). At a high level, UCB is a
frequentist approach that uses the estimated mean reward of each action and
its confidence interval to strike the right balance. TS is a Bayesian approach
that maintains a posterior distribution on the model parameter, and samples
actions accordingly.

11footnotetext: The work was done outside of Amazon.

Perhaps not surprisingly, apart from statistical efficiency, another important
factor in modern machine learning is interpretability (Carvalho et al., 2019;
Molnar, 2020). Interpretability can increase human trust in machine learning
models for certain critical tasks, such as medical diagnoses. Therefore, it is
also critical to study interpretability in MABs (Hüyük et al., 2022). Recall
that in MABs, the goal is to learn the underlying model parameter since its
better estimate could lead to a higher reward. Hence, one of the most
intuitive and explainable policies could be to take actions that maximally
reduce the uncertainty in the model parameter. To further take reward
maximization into account, one should focus exclusively on actions that are
plausible, as the rest are deemed to be sub-optimal already. Although there is
no unified definition of interpretability, we follow conventional machine
learning to define bandit algorithms that satisfy the following as
_interpretable_ :

> A bandit algorithm is interpretable if it takes plausible actions with the
> objective of reducing uncertainty in the model parameter.

In this paper, we study the design of interpretable and efficient bandit
algorithms. To this end, we make the following two observations:

  * •

While both UCB and TS can efficiently maximize the cumulative reward, both
adaptively mix exploration and exploitation to explore at a near-optimal rate.
Therefore, one can hardly tell why a particular action was taken, to explore
or exploit.

  * •

On the other hand, _explore-then commit (EtC)_ algorithms (Langford and Zhang,
2008; Garivier et al., 2016; Jin et al., 2021) are clearly interpretable. This
is because they first explore to minimize model parameter uncertainty, and
then take the empirically optimal action to exploit. However, they are
statistically sub-optimal due to non-adaptivity and thus may incur high
regret.

As a partial remedy, several phased elimination algorithms have been proposed
(Soare et al., 2014; Fiez et al., 2019; Katz-Samuels et al., 2020; Wagenmaker
et al., 2021). These algorithms run in phases and eliminate sub-optimal
actions in between. Within each phase, they rely on an optimal design
(Pukelsheim, 2006) to find a distribution over actions that maximally explore
the unknown parameter, to learn it. As a result, they are more efficient than
EtC as they are more adaptive. In addition, they are interpretable because
their exploration is guided by optimal designs (over plausible actions) that
minimize the uncertainty of the unknown model parameter. However, these
algorithms

  1. 1.

Perform poorly empirically since no sub-optimal actions are removed in the
middle of a phase, even if they are detected early within the phase.

  2. 2.

Do not reuse observations from earlier phases.

  3. 3.

Cannot handle changing action sets, which is often the case in contextual
bandits.

This work tries to bridge the gap between interpretability and efficiency.
Specifically:

  * •

We propose CODE, a bandit algorithm based on a Constrained Optimal DEsign,
that is both efficient and interpretable. In each round, CODE uses an
approximate version of the $D$-optimal design to explore all plausible
actions, determined by a statistical constraint that excludes sub-optimal
actions. This leads to a statistically sound exploration guided by the optimal
design that maximally reduces the uncertainty in the model parameter. Thus we
have an interpretable algorithm. Critically, CODE avoids inefficient phases in
phased elimination algorithms and can deal with time-varying action sets.
Moreover, CODE does not need to solve an optimal design in each round because
it takes a deterministic action from the plausible set of actions that
minimizes the uncertainty of the model parameter.

  * •

Motivated by optimal designs (Pukelsheim, 2006), we propose the first metric
for interpretability in the bandit setting. This metric estimates how the
uncertainty loss decreases due to not acting like a $D$-optimal design over
plausible actions. We call it an _uncertainty loss_.

  * •

Next we instantiate CODE in both multi-armed and linear bandits and show that
it attains near-optimal regret. Unlike in conventional analysis, the regret of
CODE in each round depends on the confidence intervals of both the taken and
optimal actions. We leverage the optimality criteria of the approximate
optimal design problem to control the confidence interval of the optimal
action.

  * •

Finally, we demonstrate empirically that CODE outperforms other state-of-the-
art interpretable bandit algorithms in linear bandits, in both synthetic
problems and simulations based on real-world data.

This paper is organized as follows. In Section 2, we introduce our notation
and problem setting. In Section 3, we outline key ideas in our explainable and
efficient exploration. In Section 4, we apply them to $K$-armed bandits. In
Section 5, we address the more general setting of linear bandits with a
changing action set. Finally, we show numerical experiments in Section 6 and
conclude in Section 7.

##  2 Problem Formulation

We start by introducing our general notation. For any $p\geq 0,$ we define a
$p$-norm $\|\cdot\|_{p}$. We denote by $\mathbf{1}_{k}$ the $k$-dimensional
vector with all entries equal to $1$. We use
$\mathds{1}\\!\left\\{\cdot\right\\}$ to denote the indicator function. For
any positive semi-definite matrix $M$, we let
$\|x\|_{M}\coloneqq\sqrt{x^{\top}Mx}$. A $d\times d$ identity matrix is
denoted by $\mathbf{I}_{d}$. We also define $[m]\coloneqq\\{1,2,\ldots,m\\}$.

The bandit setting is defined as follows. The learning horizon has $n$ rounds
and we index them by $t\in[n]$. The action set is denoted by
$\mathcal{A}\subseteq\mathbb{R}^{d}$. It can change with round $t$ and we
denote by $\mathcal{A}_{t}\subseteq\mathcal{A}$ the action set in round $t$. A
random variable $X$ is $\sigma^{2}$-sub-Gaussian if $\mathbb{E}[X]=0$ and
satisfies $\mathbb{E}[\exp(sX)]\leq\exp(s^{2}\sigma^{2}/2)$ for all
$s\in\mathbb{R}$. The learner interacts with the bandit sequentially. At round
$t$, it takes an action $A_{t}\in\mathcal{A}_{t}$ and obtains a reward
$X_{t}=\langle A_{t},\bm{\theta}_{*}\rangle+\eta_{t},$ where $\eta_{t}$ is
conditionally $1$-sub-Gaussian. The model parameter
$\bm{\theta}_{*}\in\mathbb{R}^{d}$ is unknown to the learner but the features
of the actions in $\mathcal{A}_{t}$ are known. We assume that
$\|\bm{\theta}_{*}\|_{2}\leq S$ and $\|a\|_{2}\leq L$ for any
$a\in\mathcal{A}$. The cardinality of each $\mathcal{A}_{t}$ is at most $K,$
$|\mathcal{A}_{t}|\leq K$.

The goal of the learner is to minimize pseudo-regret

$\displaystyle R_{n}$
$\displaystyle=\mathbb{E}\left[\left(\sum_{t=1}^{n}\left\langle
A_{t}^{*},\bm{\theta}_{*}\right\rangle\right)-\left(\sum_{t=1}^{n}\left\langle
A_{t},\bm{\theta}_{*}\right\rangle\right)\right]\,,$

where $A^{*}_{t}=\mathop{\rm arg\,max}_{a\in\mathcal{A}_{t}}\langle
a,\bm{\theta}_{*}\rangle$ is the optimal action at round $t$.

##  3 Interpretable Exploration via Constrained Optimal Design

We introduce CODE, a bandit algorithm based on a Constrained Optimal DEsign,
that is both efficient and interpretable. The key idea in CODE is to take the
action that maximally reduces the uncertainty in the unknown model parameter
$\bm{\theta}_{*}$ from plausible actions. This is formulated as an
optimization problem, a variant of the $D$-optimal design subject to
constraint. The constraint excludes high-probability sub-optimal actions and
defines the plausible action set. In round $t$, CODE takes a deterministic
action that is computed by solving

$\displaystyle A_{t}=$ $\displaystyle\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\log\det(V_{t}+aa^{\top})$ (1)
$\displaystyle\text{ s.t. }\widetilde{\mathcal{A}}_{t}$
$\displaystyle=\\{a\in\widetilde{\mathcal{A}}_{t}:\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a,\bm{\theta}\rangle\geq\max_{a^{\prime}\in\mathcal{A}_{t}}\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a^{\prime},\bm{\theta}\rangle\\}\,$

where $V_{t}\coloneqq\sum_{s=1}^{t-1}A_{s}A^{\top}_{s}$ is the _design matrix_
up to round $t$ that allows computation of high-probability confidence
intervals in linear and generalized linear models, and $\mathcal{C}_{t}$
represents high-probability confidence set inside which the unknown model
parameter $\bm{\theta}_{*}$ resides. We make the following remarks about CODE:

  * •

Per-Round Elimination Constraint: We introduce a per-round elimination
constraint that excludes high-probability sub-optimal actions. This is
achieved by first building the confidence set $\mathcal{C}_{t}$ at the
beginning of each round $t$. Then we compare the _upper confidence bound
(UCB)_ of each action $a$, given by
$\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle a,\bm{\theta}\rangle$, against
the _lower confidence bound (LCB)_ of any other action $a^{\prime}$, given by
$\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle a^{\prime},\bm{\theta}\rangle$.
The constraint ensures that actions with lower UCBs than any LCB are excluded.
In particular, if $\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a,\bm{\theta}\rangle<\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a^{\prime},\bm{\theta}\rangle$ for any $a^{\prime}$, the constraint can be
only satisfied by not taking action $a$.

  * •

Interpretability: CODE is interpretable by design. Specifically, it excludes
high-probability sub-optimal actions through the constraint. Then it takes the
action, from the remaining plausible actions, that maximally reduces
uncertainty in $\bm{\theta}_{*}$, which also has the highest uncertainty in
its estimated mean reward. To see this, note that

$\displaystyle\mathop{\rm arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}$
$\displaystyle\log\det(V_{t}+aa^{\top})$
$\displaystyle\overset{(a)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\log\det(\mathbf{I}_{d}+V_{t}^{-1/2}aa^{\top}V_{t}^{-1/2})$
$\displaystyle\overset{(b)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\log(1+\|a\|^{2}_{V_{t}^{-1}})\,.$
(2)

Here equality (a) follows from $V_{t}$ being constant at round $t$. Equality
(b) follows from the fact that for any vector $b$, $\mathbf{I}_{d}+bb^{\top}$
has $d-1$ eigenvalues $1$ and one eigenvalue $1+\|b\|_{2}^{2}$. Therefore, its
determinant is $1+\|b\|_{2}^{2}$ and its logarithm is $\log(1+\|b\|_{2}^{2})$.
As we will see later, the identity (2) is an important step in bounding the
regret of CODE.

###  3.1 Explainability Metric

CODE takes the action that maximally reduces uncertainty in the unknown model
parameter. However, since this action is taken greedily, it is unclear if CODE
reduces uncertainty more efficiently than other bandit algorithms. We propose
a metric to quantify this. More specifically, fix round $t\in[n]$ and note
that the $D$-optimal design

$\displaystyle\pi_{t}=\mathop{\rm
arg\,max}_{\pi\in\Delta(\mathcal{A}_{t})}\log\det\bigg{(}V_{t}+\sum_{a\in\mathcal{A}_{t}}\pi_{t}(a)aa^{\top}\bigg{)}$

is an optimal solution to the uncertainty reduction in a single round, where
$\Delta(\mathcal{A}_{t})$ is a simplex over set $\mathcal{A}_{t}$. So one
reasonable way of evaluating the closeness of any bandit policy to $\pi_{t}$
is by

$\displaystyle\log\det\bigg{(}V_{t}+\sum_{a\in\mathcal{A}_{t}}\pi_{t}(a)aa^{\top}\bigg{)}-\log\det(V_{t}+A_{t}A_{t}^{\top})\,.$

This metric has two issues. First, the optimum is not attainable in a single
round unless $\pi_{t}$ is a deterministic policy. This is generally not the
case in linear bandits. Second, bandit algorithms are adaptive. Hence, only
_plausible actions_ $\widetilde{\mathcal{A}}_{t}$, likely to be taken from
round $t$ forward, should be considered in the optimal design. With this in
mind, we define our interpretability metric of _uncertainty loss_ in round $t$
as $\kappa_{t}={}$

$\displaystyle\log\det\bigg{(}V_{t}+\sum_{a\in\widetilde{\mathcal{A}}_{t}}\pi_{t}(a)aa^{\top}\bigg{)}-\log\det(V_{t}+A_{t}A_{t}^{\top})\,.$

###  3.2 Related Optimal Design Works

Now we discuss some related works that connect our optimization problem in (1)
to optimal designs. There is a growing body of literature on optimal designs
for bandits (Pukelsheim, 2006; Lattimore and Szepesvári, 2020). The output of
optimal designs is a distribution over actions. When the learner takes $n$
actions according to this distribution, it minimizes some notion of
uncertainty in the estimate of $\bm{\theta}_{*}$ within a fixed budget of $n$
samples. We note that the optimization in (1) maximizes the log determinant of
the design matrix, which is similar to the $D$-optimal design. By Kiefer-
Wolfowitz theorem (Kiefer and Wolfowitz, 1960), the $D$\- and $G$-optimal
designs have identical solutions in some problem classes.

Several bandits papers considered the $G$-optimal design for regret
minimization to derive their algorithms (Soare et al., 2014; Fiez et al.,
2019; Katz-Samuels et al., 2020; Wagenmaker et al., 2021; Jamieson and Jain,
2022; Zhu and Kveton, 2022b). However, these approaches use optimal designs in
phases of increasing length and eliminate sub-optimal actions at the end of
each phase. The next phase communicates with the earlier one only through non-
eliminated actions and neglects all earlier observations. Therefore, these
algorithms are conservative and need a fixed action set $\mathcal{A}$. In
contrast, CODE does not have phases and can be applied to changing action sets
$\mathcal{A}_{t}$. CODE also does not compute a sampling distribution over
actions at each round $t$, because it takes a plausible deterministic action
that maximally reduces the uncertainty in the estimate of $\bm{\theta}_{*}$.
We outperform the phased elimination algorithms empirically (Section 6).

Finally, optimal designs have been used in pure exploration and related
settings (Soare et al., 2014; Fiez et al., 2019; Katz-Samuels et al., 2020;
Fontaine et al., 2021; Mason et al., 2021; Mukherjee et al., 2022, 2023; Zhu
and Kveton, 2022a). However, in this work, we focus on cumulative regret
minimization.

##  4 $K$-Armed Bandits: A Warm-Up

To gain preliminary insights into CODE, we first study its algorithmic
behavior and performance in the classic $K$-armed bandits. We start by
introducing the $K$-armed bandits terminologies and then discuss how (1) can
be implemented. We represent the $K$-armed bandits as having an action set
$\mathcal{A}=\\{\mathbf{e}_{1},\dots,\mathbf{e}_{K}\\}\subseteq\mathbb{R}^{K}$,
where $\mathbf{e}_{a}$ is the $a$-th vector in the standard Euclidean basis
representing action $a$. Note that now we use $a$ to denote the action index
in $[K]$. We denote by $\mu(a)$ the mean reward of action $a$. The optimal
action is $a^{*}=\mathop{\rm arg\,max}_{a\in\mathcal{A}}\mu(a)$ and the
suboptimality gap of action $a$ is $\Delta(a)\coloneqq\mu(a^{*})-\mu(a)$.

CODE can be implemented as follows. Let

$\displaystyle
T_{t}(a)\coloneqq\sum_{s=1}^{t-1}\mathds{1}\\!\left\\{A_{s}=a\right\\}$

be the number of times that action $a$ is taken up to round $t$. Let the mean
reward estimate of action $a$ in round $t$ be

$\displaystyle\widehat{\mu}_{t}(a)\coloneqq
T_{t}^{-1}(a)\sum_{s=1}^{t-1}\mathds{1}\\!\left\\{A_{s}=a\right\\}Y_{s}\,,$

where $Y_{s}$ is the observed reward at round $s$. Note that the vectors in
$\mathcal{A}$ are orthonormal. Therefore, the constrained optimization in (1)
reduces to

$\displaystyle A_{t}$ $\displaystyle\overset{(a)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\log\det(V_{t}+\mathbf{e}_{a}\mathbf{e}_{a}^{\top})$
$\displaystyle\widetilde{\mathcal{A}}_{t}$
$\displaystyle=\\{a\in[K]:\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle\mathbf{e}_{a},\bm{\theta}\rangle\geq\max_{a^{\prime}\in[K]}\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle\mathbf{e}_{a^{\prime}},\bm{\theta}\rangle\\}\,$

where the equality (a) holds from (2) and that each action is a vector
$\mathbf{e}_{a}$. It follows then that

$\displaystyle A_{t}$ $\displaystyle\overset{(a)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\log(1+\|\mathbf{e}_{a}\|^{2}_{V_{t}^{-1}})$
$\displaystyle\overset{(b)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\|\mathbf{e}_{a}\|^{2}_{V_{t}^{-1}}$
$\displaystyle\overset{(c)}{=}\mathop{\rm
arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\dfrac{1}{T_{t}(a)}\,.$

Equality (a) holds from (2) and that each action is a vector $\mathbf{e}_{a}$.
Equality (b) follows from the monotonicity of the logarithm. Equality (c)
holds because $V_{t}^{-1}$ is a diagonal matrix whose $a$-th diagonal entry is
$T_{t}^{-1}(a)$.

Now recall that $\mathcal{C}_{t}$ in the constraint of (1) is a confidence set
that contains the unknown model parameter with a high probability,
$\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle a,\bm{\theta}\rangle$ can be
viewed as an _upper confidence bound (UCB)_ on the mean reward of action $a$
in round $t$, and $\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a^{\prime},\bm{\theta}\rangle$ can be viewed as a _lower confidence bound
(LCB)_ on the mean reward of action $a^{\prime}$ in round $t$. In our
$K$-armed bandits, these have closed-form solutions

$\displaystyle\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a,\bm{\theta}\rangle$ $\displaystyle=\widehat{\mu}_{t}(a)+c_{t}(a)\,,$
$\displaystyle\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
a^{\prime},\bm{\theta}\rangle$
$\displaystyle=\widehat{\mu}_{t}(a^{\prime})-c_{t}(a)\,,$

where $c_{t}(a)\coloneqq\sqrt{\frac{2\log(1/\delta)}{T_{t}(a)}}$ and
$\delta\in(0,1)$ is the failure probability of the bounds. Let
$U_{t}(a)\coloneqq\widehat{\mu}_{t}(a)+c_{t}(a)$ and
$L_{t}(a)\coloneqq\widehat{\mu}_{t}(a)-c_{t}(a)$. With the above, the
constrained optimization problem in (1) becomes

$\displaystyle A_{t}=\mathop{\rm arg\,max}_{a\in\widetilde{\mathcal{A}}_{t}}\
\dfrac{1}{T_{t}(a)}$ (3) $\displaystyle\mathrm{s.t.}\
\widetilde{\mathcal{A}}_{t}=\\{a\in[K]:U_{t}(a)\geq\max_{a^{\prime}\in[K]}L_{t}(a^{\prime})\\}\,.$

The constraint in (1) reduces to comparing the upper and lower confidence
bounds of actions $a$ and $a^{\prime}$, denoted by $U_{t}(a)$ and
$L_{t}(a^{\prime})$, respectively (Auer et al., 2002; Auer and Ortner, 2010).
If $U_{t}(a)$ is lower than $L_{t}(a^{\prime})$ for any action $a^{\prime}$,
then the action $a$ does not belong to the plausible set of actions and cannot
be taken. Finally, to make the logarithm in the objective well-defined, each
action is initially taken once.

To summarize our approach, CODE solves the optimization in (3) in every round
$t$ and takes a deterministic action. Finally, it updates the parameters of
the taken action $A_{t}$, its empirical mean reward estimate
$\widehat{\mu}_{t}(A_{t})$, and the number of times that the action is taken
$T_{t}(A_{t})$. We analyze the regret of CODE next.

###  4.1 Regret Analysis

In this section, we bound the regret of CODE in $K$-armed bandits. We state
the bound first.

######  Theorem 1.

The regret of CODE in $K$-armed bandits is given by $R_{n}=O\left(\dfrac{K\log
n}{\Delta_{\min}}\right)$, where
$\Delta_{\min}\coloneqq\min_{a\in\mathcal{A}}\Delta(a)$.

The regret bound in 1 scales linearly with the number of actions $K$ and
depends on the minimum gap $\Delta_{\min}$. This is natural in $K$-armed
bandits as actions do not share any information. The factor of $\log n$ is
standard in gap-dependent regret bounds in $K$-armed bandits (Auer et al.,
2002; Lattimore and Szepesvári, 2020). In fact, from Theorem 16.4 of Lattimore
and Szepesvári (2020), our regret bound matches the gap-dependent lower bound
in $K$-armed bandits. This bound also matches that of LinUCB and LinTS.

Gap-independent Bound: Note that the result of 1 is an instance-dependent
bound. We can get an instance-free minimax bound by setting
$\Delta_{\min}=\sqrt{K\log n/n}$. It follows then that

$\displaystyle R_{n}=O\left(\sum_{a\in[K]}\Delta(a)+\dfrac{K\log
n}{\Delta_{\min}}\right)=O(\sqrt{Kn\log n})$

Therefore the gap-independent bound yields a regret of $O(\sqrt{Kn\log n})$.

Proof Sketch of 1: We start by considering the good event $\xi_{n}$ such that
the unknown reward parameters fall into the confidence intervals holds for all
actions $a\in\mathcal{A}$. Let $A_{t}$ be the action selected at round $t$,
the $c_{t}(a)\coloneqq\sqrt{2\log(1/\delta)/T_{t}(a)}$ be the width of the
confidence interval of action $a$, and $a^{*}\coloneqq\mathop{\rm
arg\,max}_{a\in\mathcal{A}}\mu(a)$ be the optimal action. The good
concentration event is shown in the following lemma.

######  Lemma 1.

(Concentration) Let $\xi_{n}$ be a good event, that the confidence intervals
holds jointly over all rounds and actions,

$\displaystyle\xi_{n}\coloneqq\bigcap_{a\in[K]}\bigcap_{t=1}^{n}\left\\{\left|\widehat{\mu}_{t}(a)-\mu(a)\right|\leq
c_{t}(a)\right\\}.$

Then $\mathbb{P}(\xi_{n})\geq 1-2Kn\delta$ for any $\delta\in(0,1)$.

The proof of this lemma is given in Section A.1. From Lemma 1 we know
$\xi_{n}$ holds with probability greater than $(1-2Kn\delta)$. Then, we show
that, under $\xi_{n}$, the per-round regret incurred by choosing action
according to (3) and CODE is upper bounded by $\mu(a^{*})-\mu(A_{t})\leq
2c_{t}(A_{t})+2c_{t}(a^{*})$. This is shown in Lemma 2.

######  Lemma 2.

(Per-Round Regret) Suppose event $\xi_{n}$ occur and $A_{t}$ be the action
taken by CODE in round $t$. Then, $\mu(a^{*})-\mu(A_{t})\leq
2c_{t}(A_{t})+2c_{t}(a^{*})$ holds.

###### Proof.

The regret of round $t$ is

$\displaystyle\mu(a^{*})-\mu(A_{t})$ $\displaystyle=(\mu(a^{*})-L_{t}(a^{*}))$
$\displaystyle+(L_{t}(a^{*})-U_{t}(A_{t}))+(U_{t}(A_{t})-\mu(A_{t}))$
$\displaystyle\leq(\mu(a^{*})-L_{t}(a^{*}))+(U_{t}(A_{t})-\mu(A_{t})),$ (4)

where the inequality follows because according to the constraints in (3): if
$A_{t}$ is chosen, its UCB $U_{t}(A_{t})$ should be no less than any actions’
LCB, and in particular, the optimal action’s (i.e., $L_{t}(a^{*})$).

Under $\xi_{n}$, we have from Lemma 1 that

$\displaystyle\mu(a^{*})-L_{t}(a^{*})$
$\displaystyle=\mu(a^{*})-(\widehat{\mu}_{t}(a^{*})-c_{t}(a^{*}))$
$\displaystyle=(\mu(a^{*})-\widehat{\mu}_{t}(a^{*})+c_{t}(a^{*})\leq
2c_{t}(a^{*})$

and

$\displaystyle U_{t}(A_{t})-\mu(A_{t})$
$\displaystyle=(\widehat{\mu}_{t}(A_{t})+c_{t}(A_{t}))-\mu(A_{t})$
$\displaystyle=(\widehat{\mu}_{t}(A_{t})-\mu(A_{t}))+c_{t}(A_{t})\leq
2c_{t}(A_{t}).$

Plugging the above two into (4.1) concludes the proof of this lemma. ∎

There are two key insights in Lemma 2. First, to arrive at (4.1), we make use
of the constraints in (3) which ensures UCB of $A_{t}$ is at least as large as
the LCB of $a^{*}$. Moreover, one can also observe that the per-round regret
depends not just on the selected action $A_{t}$, but also on the optimal
action $a^{*}$.

######  Lemma 3.

(Optimal Action Confidence Interval) Let event $\xi_{n}$ occur and $A_{t}$ be
the action taken by CODE in round $t$. Then $\mu(a^{*})-\mu(A_{t})\leq
4c_{t}(A_{t})$ holds.

###### Proof.

Now observe from the solution of the constrained optimization in (3) that it
takes those actions that are least taken. This implies that these actions have
higher confidence width than the actions that are taken more. Since the action
$A_{t}$ taken at round $t$ has the highest confidence interval width, we have
that $c_{t}(A_{t})\geq c_{t}(a^{*})$. Following Lemma 2, we have

$\displaystyle\mu(a^{*})-\mu(A_{t})\leq 4c_{t}(A_{t}).$

The claim of the lemma follows. ∎

From Lemma 3 observe that the solution in (3) ensures that $c_{t}(A_{t})\geq
c_{t}(a^{*})$ which leads to the per step regret bound of $4c_{t}(A_{t})$. We
finish the proof of 1 by calling Lemma 1, 2, and 3 and showing that the
optimal action $a^{*}$ eliminates sub-optimal actions and bounding the number
of samples of each sub-optimal action $a$ till horizon $n$. The full proof is
given in Section A.1. $\blacksquare$

##  5 Linear Bandits

Next we study CODE in linear bandits. Recall that actions in linear bandits
are $d$-dimensional vectors $a\in\mathbb{R}^{d}$. In contrast to $K$-armed
bandits, they share the model parameter $\bm{\theta}_{*}$. In round $t$, CODE
first estimates $\bm{\theta}_{*}$ using regularized least squares from all
observations up to round $t$ as

$\displaystyle\widehat{\bm{\theta}}_{t}\coloneqq\mathop{\rm
arg\,min}_{\bm{\theta}\in\mathbb{R}^{d}}\left(\sum_{s=1}^{t-1}\left(Y_{s}-\left\langle\bm{\theta},A_{s}\right\rangle\right)^{2}+\lambda\|\bm{\theta}\|_{2}^{2}\right),$
(5)

where $A_{s}$ is the taken action at round $s$, $Y_{s}$ denotes its reward,
and $\lambda\geq 0$ is a regularizer. Then it uses $\widehat{\bm{\theta}}_{t}$
to construct a high-probability confidence ellipsoid

$\displaystyle\mathcal{C}_{t}\coloneqq\\{\bm{\theta}\in\mathbb{R}^{d}:\|\widehat{\bm{\theta}}_{t}-\bm{\theta}\|_{V_{t}}\leq\sqrt{\beta_{t}(\delta)}\\}\,,$
(6)

where $\delta\in(0,1)$ is its failure probability and
$\sqrt{\beta_{t}(\delta)}=\sqrt{d\log((1+tL^{2}/\lambda)\delta)}+\lambda^{1/2}S$.
Finally, it solves the optimization in (1) to select $A_{t}$ and observes its
reward $Y_{t}$. The pseudo-code is presented in Algorithm 1.

Algorithm 1 CODE for linear bandits.

1:Input: Finite action set $\mathcal{A}\subseteq\mathbb{R}^{d}$, regularizer
$\lambda\geq 0$

2:Set $V_{0}=\lambda\mathbf{I}_{d}$

3:for $t=1,\dots,n$ do

4: Estimate $\widehat{\bm{\theta}}_{t}$ using (5) and $C_{t}$ using (6)

5: Solve the optimization in (1)

6: Select action $A_{t}$ and observe reward $Y_{t}$

###  5.1 Regret Analysis

In this section, we bound the regret of CODE in linear bandits. We state the
bound first.

######  Theorem 2.

The regret of CODE in linear bandits is given by
$R_{n}=\widetilde{O}(d\sqrt{n})$, where $\widetilde{O}$ hides logarithmic
factors.

This rate is standard in linear bandits (Abbasi-Yadkori et al., 2011;
Lattimore and Szepesvári, 2020), and comparable to those of LinUCB and LinTS
with infinitely many actions. From Theorem 24.2 of Lattimore and Szepesvári
(2020), our regret bound matches the gap-free lower bound of
$\Omega(d\sqrt{n})$ in this setting. Finally, we note that one $\sqrt{d}$ in
our bound could be exchanged for $\sqrt{\log K}$ if the confidence ellipsoid
in (6) was designed for finitely many actions.

Proof Sketch of 2: The regret bound proof follows a similar rationale as 1
with a few novel techniques. We start off by considering the good event
$\xi_{n}$ such that $\bm{\theta}_{*}\in\mathcal{C}_{t}$ for all $t\in[n]$ as
follows:
$\xi_{n}\coloneqq\bigcap_{t=1}^{n}\\{\bm{\theta}_{*}\in\mathcal{C}_{t}\\}$. In
the following lemma, we show that the good event $\xi_{n}$ holds with high
probability.

######  Lemma 4.

(Confidence Ellipsoid, Theorem 2 of Abbasi-Yadkori et al. (2011)) Let
$V_{0}=\lambda\mathbf{I}_{d},\lambda>0$. Assume that
$\left\|\bm{\theta}_{*}\right\|_{2}\leq S$ and $\left\|A_{t}\right\|_{2}\leq
L$. Then, for any $\delta>0$, with probability at least $1-\delta$, for all
$t\geq 0,\bm{\theta}_{*}$ lies in the confidence set $\mathcal{C}_{t}$ defined
in (6).

The proof of this lemma is in Abbasi-Yadkori et al. (2011). It follows from
Lemma 4 that $\mathbb{P}(\xi_{n})\geq 1-\delta$. Then we provide a key lemma
that upper bounds the per-step regret.

######  Lemma 5.

(Per-Round Regret) Under the good event $\xi_{n}$ we can show that the
expected regret of round $t$ is bounded from above as

$\displaystyle\langle A_{t}^{*},\bm{\theta}_{*}\rangle-\langle
A_{t},\bm{\theta}_{*}\rangle$ $\displaystyle\leq$ $\displaystyle\left(\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle\right)+\left(\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\langle A_{t},\bm{\theta}_{*}\rangle\right).$

The proof of this lemma is similar to that of Lemma 2, and is deferred to
Appendix B. Following conventional linear bandits analysis, the second term on
the R.H.S. of Lemma 5 can be bounded as

$\displaystyle\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\langle A_{t},\bm{\theta}_{*}\rangle\leq$
$\displaystyle\|A_{t}\|_{V^{-1}_{t}}\max_{\bm{\theta}\in\mathcal{C}_{t}}\|\bm{\theta}-\bm{\theta}_{*}\|_{V_{t}}$
$\displaystyle\leq$
$\displaystyle\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)},$ (7)

where $\beta_{t}(\delta)$ is the width of $\mathcal{C}_{t}$, the confidence
region of $\bm{\theta}$. For the first term of the R.H.S. in Lemma 5, we can
similarly have

$\displaystyle\langle
A^{*}_{t},\bm{\theta}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A^{*}_{t},\bm{\theta}_{*}\rangle\leq$
$\displaystyle\|A_{t}^{*}\|_{V^{-1}_{t}}\max_{\bm{\theta}\in\mathcal{C}_{t}}\|\bm{\theta}-\bm{\theta}_{*}\|_{V_{t}}$
$\displaystyle\leq$
$\displaystyle\|A^{*}_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)}$
$\displaystyle\leq$
$\displaystyle\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)},$ (8)

where the last step holds by definition of CODE.

Combining the above, we have that the per round regret of CODE under the good
event $\xi_{n}$ is at most $2\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)}$.
From here, one can apply the log determinant inequality in Lemma 6 to give us
the desired regret bound. The full proof is given in Section A.2.

##  6 Experiments

We conduct four experiments. In the first experiment, we evaluate CODE on
synthetic linear bandits and compare it to multiple baselines. The remaining
three experiments are conducted on the MovieLens, White Wine Quality, and
Heart Failure datasets. We use these standard public benchmarks to evaluate
the performance of CODE in real-life datasets.

To compute the uncertainty loss $\kappa_{t}$ in Section 3.1, we make two
approximations. First, the plausible actions are actions taken by the
algorithm in the _next_ $w$ rounds,
$\mathcal{P}_{t}=\\{A_{t},\dots,A_{t+w-1}\\}$. We use $w=30$ in our
experiments. Second, to speed up the metric computation, we compute the
optimal design only every $w$ rounds. That $D$-optimal design is

$\displaystyle\hat{\pi}_{t}=\mathop{\rm
arg\,max}_{\pi\in\Delta(\mathcal{P}_{t})}\log\det\bigg{(}V_{t}+w\sum_{a\in\mathcal{P}_{t}}\pi_{t}(a)aa^{\top}\bigg{)}$

and the loss in uncertainty due to not acting like it is approximated by the
average over the next $w$ rounds,

$\displaystyle\hat{\kappa}_{t}={}$
$\displaystyle\frac{1}{w}\log\det\bigg{(}V_{t}+w\sum_{a\in\mathcal{P}_{t}}\hat{\pi}_{t}(a)aa^{\top}\bigg{)}-{}$
$\displaystyle\frac{1}{w}\log\det\bigg{(}V_{t}+\sum_{s=1}^{t+w-1}A_{s}A_{s}^{\top}\bigg{)}\,.$

Note that $\hat{\kappa}_{t}$ can be computed for any linear bandit algorithm,
even a deterministic one, since it only requires access to its taken actions.
We plot $\hat{\kappa}_{t}$ cumulatively in our experiments.

###  6.1 Linear Bandits

We start with $d$-dimensional linear bandits, where $d=5$, the number of
actions is $K=100$, and the horizon is $n=10\,000$ rounds. The model parameter
is generated as $\bm{\theta}_{*}\sim\mathcal{N}(\mathbf{0}_{d},I_{d})$. The
feature vectors of actions are drawn uniformly at random from $[-1,1]^{d}$.
The reward noise is $\mathcal{N}(0,\sigma^{2})$ and $\sigma=0.5$. All results
are averaged over $200$ random runs.

We compare CODE to five baselines. The first two, LinUCB (Dani et al., 2008;
Abbasi-Yadkori et al., 2011) and LinTS (Chapelle and Li, 2012; Agrawal and
Goyal, 2013), are classic adaptive algorithms for linear bandits. They are not
interpretable and show what regret is attainable without demanding
interpretability. Elimination is an elimination algorithm for linear bandits
with quadrupling phase lengths (Section 22 in Lattimore and Szepesvári
(2020)). Like CODE, Elimination uses an optimal design to explore. Unlike
CODE, the design is computed only at the beginning of each phase and kept
fixed throughout it. The $\epsilon$-greedy policy explores in round $t$ with
probability $\varepsilon\sqrt{n/t}/2$. Therefore, it explores more initially
and the number of exploration rounds is roughly $\varepsilon n$. The last
baseline is explore-then-commit (EtC) of Langford and Zhang (2008). EtC
explores in the first $\varepsilon n$ rounds and then acts greedily with
respect to the learned model.

We implement CODE with the confidence interval in (6), where $L=1$, $S=0$,
$\lambda=10^{4}$, and $\delta=0.05$. This setting gives us a comparable
performance to LinUCB. We set $\delta=0.05$ in Elimination, and
$\varepsilon=0.05$ in both the $\epsilon$-greedy policy and EtC.

Figure 1: (a) Regret of CODE and five baselines in linear bandits, reported as
a function of horizon $n$. (b) Interpretability of CODE and the baselines.

In Figure 1a, we plot the regret of all methods as a function of the number of
rounds $n$. We observe that the regret of CODE is comparable to that of
LinUCB, and significantly lower than that of any interpretable baseline.
LinTS, which is a strong but uninterpretable baseline, outperforms all
methods. In Figure 1b, we plot the _uncertainty loss_ due to not acting like
the $D$-optimal design. We observe that CODE has the lowest uncertainty loss
and therefore can be viewed as most interpretable. The next two most
interpretable methods are Elimination and EtC. This experiment clearly
demonstrates the benefit of CODE over other interpretable methods.

###  6.2 MovieLens

We also experiment with the MovieLens 1M dataset (Lam and Herlocker, 2016).
This dataset contains one million ratings given by $6\,040$ users to $3\,952$
movies. We apply low-rank factorization to the rating matrix to obtain
$5$-dimensional representations: $\bm{\theta}_{j}\in\mathbb{R}^{5}$ for user
$j\in[6\,040]$ and $a_{i}\in\mathbb{R}^{5}$ for movie $i\in[3\,952]$. In each
run, we randomly select one user $\bm{\theta}_{j}$ and $100$ movies $a_{i}$,
and they represent the unknown model parameter and actions, respectively. The
reward noise is $\mathcal{N}(0,\sigma^{2})$, where $\sigma=0.811$ is estimated
from data. All results are averaged over $200$ random runs.

The performance of all compared methods is reported in Figure 2. We observe
the same trends as in Figure 1. In Figure 2a, CODE has a comparable regret to
LinUCB and is outperformed only by LinTS. In Figure 2b, CODE attains the
lowest uncertainty loss and thus can be viewed as most interpretable.

Figure 2: (a) Regret of CODE and five baselines on the MovieLens problem,
reported as a function of horizon $n$. (b) Interpretability of CODE and the
baselines.

###  6.3 White Wine Quality

The White Wine Quality dataset (Cortez et al., 2009) contains $4\,500$ samples
of white wine, each associated with a feature vector $a\in\mathbb{R}^{11}$.
The target variable is the rating of wine in range $1$ to $10$. We first fit a
linear model to the dataset and get an estimate of $\bm{\theta}_{*}$. The
reward model is linear, $A_{t}^{\top}\bm{\theta}_{*}+\eta_{t}$, where $A_{t}$
is the action at round $t$ and $\eta_{t}$ is conditional $1$-sub-Gaussian
noise. In each run, we randomly select $100$ wines as actions. Our results are
averaged over $50$ runs.

The performance of all compared methods is reported in Figure 3. We observe
again that LinTS is the only baseline with a significantly lower regret than
CODE (Figure 3a). On the other hand, CODE is most interpretable (Figure 3b).

Figure 3: (a) Regret of CODE and five baselines on the Wine Quality dataset,
shown as a function of horizon $n$. (b) Interpretability of CODE and the
baselines.

###  6.4 Heart Failure

The Heart Failure dataset (mis, 2020) contains $300$ samples of heart failure
records, each associated with a feature vector $a\in\mathbb{R}^{12}$. The
target variable is if the patient lived or died. We again fit a linear model
to the dataset and get an estimate of $\bm{\theta}_{*}$. The reward model is
linear, $A_{t}^{\top}\bm{\theta}_{*}+\eta_{t}$, where $A_{t}$ is the action at
round $t$ and $\eta_{t}$ is conditional $1$-sub-Gaussian noise. All samples
are actions. Our results are averaged over $50$ runs.

The performance of all compared methods is reported in Figure 4. We observe
that LinTS has the lowest regret, followed by all other methods but
Elimination (Figure 4a). On the other hand, CODE is most interpretable by a
large margin (Figure 4b).

Figure 4: (a) Regret of CODE and five baselines on the Heart Failure dataset,
shown as a function of horizon $n$. (b) Interpretability of CODE and the
baselines.

##  7 Conclusions and Future Work

We propose algorithm CODE for linear bandits that is computationally
efficient, statistically efficient, and interpretable. The key idea in CODE is
to take the action that maximally reduces the uncertainty in the unknown model
parameter, from potentially optimal actions. Therefore, CODE is comparably
simple to other interpretable algorithms, such as EtC and $\epsilon$-greedy.
CODE can also be viewed as removing phases in phased elimination algorithms.
It addresses many issues that plagued these designs (Soare et al., 2014; Fiez
et al., 2019) and affected their practical performance. We analyze CODE in
$K$-armed and linear bandits, and prove tight regret bounds. Finally, we
empirically evaluate CODE and compare it to state-of-the-art baselines in
linear bandits. CODE outperforms all interpretable baselines, while matching
the performance of popular but uninterpretable designs like LinUCB. In the
future work, we want to extend this work to a more general class of
reinforcement learning (RL) problems, such as regret minimization in
contextual bandits and linear MDPs.

## References

  * mis (2020) Heart failure clinical records.  UCI Machine Learning Repository, 2020.  DOI: https://doi.org/10.24432/C5Z89R.
  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Agrawal and Goyal (2012) Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * Agrawal and Goyal (2013) Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International conference on machine learning_ , pages 127–135. PMLR, 2013.
  * Auer and Ortner (2010) Peter Auer and Ronald Ortner.  Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  _Periodica Mathematica Hungarica_ , 61(1-2):55–65, 2010.
  * 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.
  * Bendada et al. (2020) Walid Bendada, Guillaume Salha, and Théo Bontempelli.  Carousel personalization in music streaming apps with contextual bandits.  In _Proceedings of the 14th ACM Conference on Recommender Systems_ , pages 420–425, 2020.
  * Carvalho et al. (2019) Diogo V Carvalho, Eduardo M Pereira, and Jaime S Cardoso.  Machine learning interpretability: A survey on methods and metrics.  _Electronics_ , 8(8):832, 2019.
  * Chapelle and Li (2012) Olivier Chapelle and Lihong Li.  An empirical evaluation of Thompson sampling.  In _Advances in Neural Information Processing Systems 24_ , pages 2249–2257, 2012.
  * Cortez et al. (2009) Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis.  Modeling wine preferences by data mining from physicochemical properties.  _Decision support systems_ , 47(4):547–553, 2009\.
  * Dani et al. (2008) Varsha Dani, Thomas Hayes, and Sham Kakade.  Stochastic linear optimization under bandit feedback.  In _Proceedings of the 21st Annual Conference on Learning Theory_ , pages 355–366, 2008.
  * Eide and Zhou (2018) Simen Eide and Ning Zhou.  Deep neural network marketplace recommenders in online experiments.  In _Proceedings of the 12th ACM conference on recommender systems_ , pages 387–391, 2018.
  * Fiez et al. (2019) Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff.  Sequential experimental design for transductive linear bandits.  _Advances in neural information processing systems_ , 32, 2019.
  * Fontaine et al. (2021) Xavier Fontaine, Pierre Perrault, Michal Valko, and Vianney Perchet.  Online a-optimal design and active linear regression.  In _International Conference on Machine Learning_ , pages 3374–3383. PMLR, 2021.
  * Foster and Krishnamurthy (2021) Dylan J Foster and Akshay Krishnamurthy.  Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination.  _Advances in Neural Information Processing Systems_ , 34:18907–18919, 2021.
  * Garivier et al. (2016) Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann.  On explore-then-commit strategies.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Hüyük et al. (2022) Alihan Hüyük, Daniel Jarrett, and Mihaela van der Schaar.  Inverse contextual bandits: Learning how behavior evolves over time.  In _International Conference on Machine Learning_ , pages 9506–9524. PMLR, 2022.
  * Jamieson and Jain (2022) Kevin Jamieson and Lalit Jain.  Interactive machine learning.  2022\.
  * Jin et al. (2021) Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu.  Double explore-then-commit: Asymptotic optimality and beyond.  In _Conference on Learning Theory_ , pages 2584–2633. PMLR, 2021\.
  * Katz-Samuels et al. (2020) Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al.  An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits.  _Advances in Neural Information Processing Systems_ , 33:10371–10382, 2020.
  * Kiefer and Wolfowitz (1960) Jack Kiefer and Jacob Wolfowitz.  The equivalence of two extremum problems.  _Canadian Journal of Mathematics_ , 12:363–366, 1960.
  * Lam and Herlocker (2016) Shyong Lam and Jon Herlocker.  MovieLens Dataset.  http://grouplens.org/datasets/movielens/, 2016.
  * Langford and Zhang (2008) John Langford and Tong Zhang.  The epoch-greedy algorithm for contextual multi-armed bandits.  In _Advances in Neural Information Processing Systems 20_ , pages 817–824, 2008.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile.  Collaborative filtering bandits.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 539–548, 2016.
  * Mason et al. (2021) Blake Mason, Romain Camilleri, Subhojyoti Mukherjee, Kevin Jamieson, Robert Nowak, and Lalit Jain.  Nearly optimal algorithms for level set estimation.  _arXiv preprint arXiv:2111.01768_ , 2021.
  * Mehrotra et al. (2020) Rishabh Mehrotra, Niannan Xue, and Mounia Lalmas.  Bandit based optimization of multiple objectives on a music streaming platform.  In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 3224–3233, 2020.
  * Molnar (2020) Christoph Molnar.  _Interpretable machine learning_.  Lulu. com, 2020.
  * Mukherjee et al. (2022) Subhojyoti Mukherjee, Ardhendu S Tripathy, and Robert Nowak.  Chernoff sampling for active testing and extension to active regression.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7384–7432. PMLR, 2022.
  * Mukherjee et al. (2023) Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, and Robert Nowak.  Speed: Experimental design for policy evaluation in linear heteroscedastic bandits.  _arXiv preprint arXiv:2301.12357_ , 2023.
  * Pukelsheim (2006) Friedrich Pukelsheim.  _Optimal design of experiments_.  SIAM, 2006.
  * Soare et al. (2014) Marta Soare, Alessandro Lazaric, and Remi Munos.  Best-arm identification in linear bandits.  In _Advances in Neural Information Processing Systems 27_ , pages 828–836, 2014.
  * 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.
  * Wagenmaker et al. (2021) Andrew Wagenmaker, Julian Katz-Samuels, and Kevin Jamieson.  Experimental design for regret minimization in linear bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3088–3096. PMLR, 2021.
  * Zhu and Kveton (2022a) Ruihao Zhu and Branislav Kveton.  Safe optimal design with applications in off-policy learning.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , pages 2436–2447. PMLR, 2022a.
  * Zhu and Kveton (2022b) Ruihao Zhu and Branislav Kveton.  Safe data collection for offline and online policy learning.  In _arXiv:2111.04835_ , 2022b.

##  Appendix A Appendix

###  A.1 $K$-armed Bandit Proof

######  Lemma 1.

(Restatement of Concentration lemma) Define the confidence interval for each
action $a\in[K]$ at round $t$ as
$c_{t}(a)=\sqrt{\frac{2\log(1/\delta)}{T_{t}(a)}}$. Let $\xi_{n}$ be the good
event that confidence intervals hold for all $n$ such that

$\displaystyle\xi_{n}\coloneqq\bigcap_{a\in\mathcal{A}}\bigcap_{t=1}^{n}\left\\{\left|\widehat{\mu}_{t}(a)-\mu(a)\right|\leq
c_{t}(a)\right\\}.$

Then the $\mathbb{P}(\xi_{n})\geq 1-2n\delta$ for any $\delta\in(0,1)$.

###### Proof.

We can show that for the action $a$ the event $\xi_{n}(a)$ not happening is
bounded by the probability of the following three bad events

$\displaystyle\bigcup_{t=1}^{n}\\{\xi^{c}_{t}\\}$
$\displaystyle\subseteq\bigcup_{t=1}^{n}\underbrace{\\{\widehat{\mu}_{t}(a)\geq\mu(a)+c_{t}(a)\\}}_{\textbf{action
$a$ is over-
estimated}}\bigcup\underbrace{\\{\widehat{\mu}_{t}(a^{*})\leq\mu(a^{*})-c_{t}(a^{*})\\}}_{\textbf{action
$a^{*}$ is under-estimated}}$
$\displaystyle\qquad\bigcup\underbrace{\\{\mu(a^{*})-\mu(a)\leq
2c_{t}(a)\\}}_{\textbf{Critical number of samples}}$ (9)

where, $t=1,2,\ldots,n$. Then using Hoeffding inequality for bounded rewards
and union bounding over all $t=1,2,\ldots,n$ we can show that

$\displaystyle\mathbb{P}\left(\bigcup_{a\in\mathcal{A}}\bigcup_{t=1}^{n}\\{\widehat{\mu}_{t}(a)\geq\mu(a)+c_{t}(a)\\}\right)$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\sum_{t=1}^{n}\sum_{T_{t}(a)=1}^{t}\mathbb{P}\left(\\{\widehat{\mu}_{t}(a)\geq\mu(a)+c_{t}(a)\\}\right)$
$\displaystyle\overset{(a)}{\leq}\sum_{a\in\mathcal{A}}\exp\left(-\frac{c^{2}_{t}(a)T_{t}(a)}{2}\right)=Kn\delta$
(10)

where, $(a)$ follows from Hoeffding’s inequality and using the $1$-sub-
Gaussian assumption. Similarly for the other event also we can show that

$\displaystyle\mathbb{P}\left(\sum_{a\in\mathcal{A}}\bigcup_{t=1}^{n}\\{\widehat{\mu}_{t}(a^{*})\leq\mu(a^{*})-c_{t}(a^{*})\\}\right)\leq
Kn\delta$ (11)

Finally, for the third bad event, we can show that

$\displaystyle\mu(a^{*})-\mu(a)\leq 2c_{t}(a)\implies T_{t}(a)\leq\dfrac{8\log
n}{\Delta^{2}(a)}$ (12)

Hence, for $T_{t}(a)\geq 1+\frac{8\log n}{\Delta^{2}(a)}$ the third bad event
is controlled. This we call the critical number of samples. Hence, combining
(10), (11), and (12) we can show that $\mathbb{P}(\xi_{n}(a))\geq 1-2Kn\delta$
for $T_{n}(a)\geq 1+\frac{8\log n}{\Delta^{2}(a)}$. ∎

######  Theorem 1.

(Restatement) The regret of the CODE in $K$-actioned bandit is given by
$R_{n}=O\left(\dfrac{K\log n}{\Delta_{\min}}\right)$, where
$\Delta_{\min}=\min_{a}\Delta(a)$.

###### Proof.

Step 1 (Definition): Define the confidence width for an action $a$ at round
$t$ as $c_{t}(a)\coloneqq\sqrt{\frac{2\log(1/\delta)}{T_{t}(a)}}$. Define the
LCB of action $a$ as $L_{t}(a)\coloneqq\widehat{\mu}_{t}(a)-c_{t}(a)$ and the
UCB as $U_{t}(a)\coloneqq\widehat{\mu}_{t}(a)+c_{t}(a)$ at round $t$. Let the
empirical mean for action $a$ till round $t$ be defined as
$\widehat{\mu}_{t}(a)$. Let $\ell_{t}=\mathop{\rm
arg\,max}_{a\in\mathcal{A}}L_{t}(a)$ be the index of the action with the
highest LCB. Define the good event $\xi_{n}$ such that all confidence interval
holds for all actions $a\in\mathcal{A}$ as follows:

$\displaystyle\xi_{n}\coloneqq\bigcap_{a\in[K]}\bigcap_{t=1}^{n}\left\\{\left|\widehat{\mu}_{t}(a)-\mu(a)\right|\leq
c_{t}(a)\right\\}.$

From Lemma 1 we know that the probability of the good event is bounded by at
least $(1-2Kn\delta)$.

Step 2 (Per step concentration): Under the good event $\xi_{n}$ and sampling
according to (3) we can show that the $\mu(a^{*})-\mu(A_{t})\leq
4c_{t}(A_{t})$. This follows from Lemma 2 and Lemma 3.

Step 3 (Bound the samples of sub-optimal actions
$a\in\mathcal{A}\setminus\\{a^{*}\\}$): First recall that under the good event
$\xi_{n}$ an action $a$ can only be taken at round $t$ if

$\displaystyle L_{t}(a^{*})\leq
U_{t}(a)\overset{(a)}{\implies}\mu(a^{*})-\mu(a_{t})\leq 4c_{t}(a_{t})$
$\displaystyle\overset{(b)}{\implies}\Delta(a)\leq\sqrt{\dfrac{2\log(1/\delta)}{T_{t}(a)}}$
$\displaystyle\implies T_{t}(a)\leq\dfrac{2\log(1/\delta)}{\Delta^{2}(a)}$

where, $(a)$ follows from step 4, $(b)$ follows from the definition of the
gap. Now to get the total number of times the action $a$ is taken, we can sum
up $T_{t}(a)$ from $t=1$ to $\frac{2\log(1/\delta)}{\Delta^{2}(a)}$. This
yields

$\displaystyle\sum_{t=1}^{\dfrac{2\log(1/\delta)}{\Delta^{2}(a)}}\sqrt{\dfrac{2\log(1/\delta)}{t}}\leq\sqrt{2\log(1/\delta)}\int_{t=1}^{\dfrac{2\log(1/\delta)}{\Delta^{2}(a)}}\dfrac{1}{\sqrt{t}}$
$\displaystyle\overset{(a)}{\leq}\sqrt{2\log(1/\delta)}\left(2\sqrt{\dfrac{2\log(1/\delta)}{\Delta^{2}(a)}}\right)$
$\displaystyle\leq\dfrac{8\log(1/\delta)}{\Delta(a)}$

where, $(a)$ follows as $\int_{1}^{b}\frac{1}{\sqrt{t}}dt=2\sqrt{b}-2$.

Step 4 (Regret Decomposition): Finally we can decompose the regret till $n$ as
follows:

$\displaystyle R_{n}=\sum_{a=1}^{K}\Delta(a)\mathbb{E}[T_{n}(a)]$
$\displaystyle=\sum_{a=1}^{K}\Delta(a)\mathbb{E}[T_{n}(a)\mathbb{I}\\{\xi_{n}\\}]+\sum_{a=1}^{K}\Delta(a)\mathbb{E}[T_{n}(a)\mathbb{I}\\{\xi^{C}_{n}\\}]$
$\displaystyle\leq\sum_{a=1}^{K}\Delta(a)\mathbb{E}[T_{n}(a)\mathbb{I}\\{\xi_{n}\\}]+\sum_{a=1}^{K}\Delta(a)\mathbb{E}[\mathbb{I}\\{\xi^{C}_{n}\\}]$
$\displaystyle\leq\sum_{a=1}^{K}\Delta(a)\left(1+\frac{8\log
n}{\Delta^{2}(a)}\right)+2\sum_{a=1}^{K}\Delta(a)n\delta$
$\displaystyle=\sum_{a=1}^{K}\Delta(a)+\sum_{a=1}^{K}\frac{8\log(1/\delta)}{\Delta(a)}\
+2\sum_{a=1}^{K}\Delta(a)n\delta$

The claim of the theorem follows by setting $\delta=\frac{1}{n}$.

∎

###  A.2 Linear Bandit Proof

######  Lemma 6.

(Restatement of Lemma 19.4 from Lattimore and Szepesvári (2020) ) Let
$A_{1},\ldots,A_{n}\in\mathbb{R}^{d}$ be a sequence of vectors with
$\left\|A_{t}\right\|_{2}\leq L<\infty$ for all $t\in[n]$,
$V_{t}=\sum_{s=1}^{t-1}A_{s}A^{\top}_{s}+\lambda\mathbf{I}_{d}$ with
$\lambda\geq L^{2}$, then

$\displaystyle\sum_{t=1}^{n}\left\|A_{t}\right\|_{V_{t}^{-1}}^{2}\leq
2\log\left(\frac{\operatorname{det}V_{n+1}}{\operatorname{det}V_{1}}\right)\leq
2d\log\left(\frac{\operatorname{trace}V_{1}+nL^{2}}{d\operatorname{det}\left(V_{1}\right)^{1/d}}\right)=2d\log\left(d+nL^{2}/\lambda\right).$

######  Theorem 2.

(Restatement) The regret of CODE in the linear bandits setting is given by

$\displaystyle R_{n}\leq
4(2+L)\sqrt{(1+LS)nd\log(\lambda+nL/d)}\left(\lambda^{1/2}S+\sqrt{2\log(1/\delta)+d\log(1+nL/(\lambda
d))}\right)$

where, $\left\|a\right\|_{2}\leq L$ for any $a\in\mathcal{A}_{t}$ and
$\|\bm{\theta}_{*}\|_{2}\leq S$.

###### Proof.

Step 1 (Definition): Following the work of Abbasi-Yadkori et al. (2011) we
define the width of the confidence interval as

$\displaystyle\beta_{t}(\delta)\coloneqq
R\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}+\lambda^{1/2}S.$

Then define the confidence set (ellipsoid) at round $t$ as follows:

$\displaystyle\mathcal{C}_{t}\coloneqq\left\\{\bm{\theta}\in\mathbb{R}^{d}:\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}\right\|_{V_{t}}\leq
R\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}+\lambda^{1/2}S\right\\}.$

Finally, define the good event that $\bm{\theta}_{*}\in\mathcal{C}_{t}$ for
all $t\in[n]$ as follows:

$\displaystyle\xi_{n}=\bigcap_{t=1}^{n}\\{\bm{\theta}_{*}\in\mathcal{C}_{t}\\}$

We can show from Lemma 4 that $\mathbb{P}(\xi_{n})\geq 1-\delta$. Finally, for
convenience, we state the algorithm once more as follows:

$\displaystyle A_{t}=$ $\displaystyle\mathop{\rm arg\,max}_{a\in\mathcal{A}}\
\log(1+\|a\|^{2}_{V_{t}^{-1}})$ (13) $\displaystyle\mathrm{s.t.}\
\left[\underbrace{\langle
a^{\prime},\hat{\bm{\theta}}_{t}\rangle+\sqrt{2\|a^{\prime}\|^{2}_{V^{-1}_{t}}\log(\delta^{-1})}}_{U_{t}(a^{\prime})}-\left(\underbrace{\langle
a,\hat{\bm{\theta}}_{t}\rangle-\sqrt{2\|a\|^{2}_{V^{-1}_{t}}\log(\delta^{-1})}}_{L_{t}(a)}\right)\right]\geq
0\quad\forall a,a^{\prime}\in\mathcal{A}\,.$

where $U_{t}(a)$ and $L_{t}(a)$ denote the UCB and LCB of the action $a$. Let
$\ell_{t}=\mathop{\rm arg\,max}_{a}L_{t}(a)$ be the index of the action with
the highest LCB. We also define the confidence width of action $a$ as
$c_{t}(a)=\sqrt{2\|a\|^{2}_{V^{-1}_{t}}\log(\delta^{-1})}$.

Step 2 (Per-step Regret): Using Lemma 5 we can show that the per step regret
of round $t$ is bounded as follows

$\displaystyle\langle A_{t}^{*},\bm{\theta}_{*}\rangle-\langle
A_{t},\bm{\theta}_{*}\rangle\leq\left(\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle\right)+\left(\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\langle A_{t},\bm{\theta}_{*}\rangle\right).$ (14)

Step 3 (First and Second Term of (14)): The second term of (14) can be upper-
bounded as

$\displaystyle\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\langle A_{t},\bm{\theta}_{*}\rangle\leq$
$\displaystyle\|A_{t}\|_{V^{-1}_{t}}\max_{\bm{\theta}\in\mathcal{C}_{t}}\|\bm{\theta}-\bm{\theta}_{*}\|_{V_{t}}$
$\displaystyle\leq$
$\displaystyle\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)},$ (15)

where $\beta_{t}(\delta)$ is the width of $\mathcal{C}_{t}$, the confidence
region of $\bm{\theta}$.

For the first term of (14), we can similarly have

$\displaystyle\langle
A^{*}_{t},\bm{\theta}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A^{*}_{t},\bm{\theta}_{*}\rangle\leq$
$\displaystyle\|A_{t}^{*}\|_{V^{-1}_{t}}\max_{\bm{\theta}\in\mathcal{C}_{t}}\|\bm{\theta}-\bm{\theta}_{*}\|_{V_{t}}$
$\displaystyle\leq$
$\displaystyle\|A^{*}_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)}$
$\displaystyle\leq$
$\displaystyle\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)},$ (16)

where the last step holds by definition of CODE.

Step 4 (Regret Decomposition): Combining the above and putting them back to
(14), we have the expected regret of a round $t$ is at most upper bounded by

$\displaystyle r_{t}\leq 2\|a\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)}.$ (17)

Sum of this over $t=1,\ldots,n$ yields the following:

$2\sum_{t=1}^{n}\|A_{t}\|_{V_{t}^{-1}}\sqrt{\beta_{t}(\delta)}.$

We can apply the log determinant inequality in Lemma 6 from here. Thus,
setting $\lambda>0$, with probability at least $1-\delta$, for all $n\geq 0$

$\displaystyle R_{n}$
$\displaystyle\leq\sqrt{n\sum_{t=1}^{n}r_{t}^{2}}\leq\sqrt{8\beta_{n}(\delta)n\sum_{t=1}^{n}\|A_{t}\|^{2}_{V_{t}^{-1}})}$
$\displaystyle\leq
8\sqrt{\beta_{n}(\delta)n\log\left(\operatorname{det}\left(V_{n}\right)\right)}$
$\displaystyle\leq
8\sqrt{nd\log(\lambda+nL/d)}\left(\lambda^{1/2}S+R\sqrt{2\log(1/\delta)+d\log(1+nL/(\lambda
d))}\right)$

where the last two steps follow from Lemma 6. ∎

##  Appendix B Proof of Lemma 5

###### Proof.

We can show that the expected regret of round $t$ is

$\displaystyle\langle A_{t}^{*},\bm{\theta}_{*}\rangle-\langle
A_{t},\bm{\theta}_{*}\rangle$ $\displaystyle=$ $\displaystyle\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A^{*}_{t},\bm{\theta}\rangle+\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle-\left(\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle+\langle A_{t},\bm{\theta}_{*}\rangle\right)$
$\displaystyle=$ $\displaystyle\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A^{*}_{t},\bm{\theta}\rangle+\underbrace{\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle-\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle}_{\textbf{Constraint}}-\left(-\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle+\langle A_{t},\bm{\theta}_{*}\rangle\right)$
$\displaystyle\leq$ $\displaystyle\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle-\left(-\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle+\langle A_{t},\bm{\theta}_{*}\rangle\right)$
$\displaystyle=$ $\displaystyle\langle
A_{t}^{*},\bm{\theta}_{*}\rangle-\min_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t}^{*},\bm{\theta}\rangle+\left(\max_{\bm{\theta}\in\mathcal{C}_{t}}\langle
A_{t},\bm{\theta}\rangle-\langle A_{t},\bm{\theta}_{*}\rangle\right).$ (18)

The claim of the lemma follows. ∎