>1|m #1 mm #2#1 #1 | #2

# A Convex Relaxation Approach to
Bayesian Regret Minimization in Offline Bandits

Mohammad Ghavamzadeh
Google Research
Mountain View, CA
<EMAIL_ADDRESS>&Marek Petrik
Google Research
Mountain View, CA
<EMAIL_ADDRESS>
&Guy Tenneholtz
Google Research
Mountain View, CA
<EMAIL_ADDRESS>
###### Abstract

Algorithms for offline bandits must optimize decisions in uncertain
environments using only offline data. A compelling and increasingly popular
objective in offline bandits is to learn a policy which achieves low Bayesian
regret with high confidence. An appealing approach to this problem, inspired
by recent offline reinforcement learning results, is to maximize a form of
_lower confidence bound_ (LCB). This paper proposes a new approach that
directly minimizes upper bounds on Bayesian regret using efficient conic
optimization solvers. Our bounds build on connections among Bayesian regret,
Value-at-Risk (VaR), and chance-constrained optimization. Compared to prior
work, our algorithm attains superior theoretical offline regret bounds and
better results in numerical simulations. Finally, we provide some evidence
that popular LCB-style algorithms may be unsuitable for minimizing Bayesian
regret in offline bandits.

##  1 Introduction

Offline reinforcement learning (RL) aims to learn reliable policies for
sequential decision-making problems from fixed datasets [25, 35]. The interest
in this area has been steadily growing in many critical domains. For example,
one cannot easily explore or collect data using a suboptimal policy in health
care and similar fields. Despite recent progress in offline RL, designing
effective algorithms remains a challenge. Offline bandit is a special case of
offline RL that targets problems that consist of a single state and, thus,
have no state transition [19]. Offline bandit represents an important model
that can be a foundation for theoretical analysis and various practical
problems alike.

This paper studies the problem of minimizing the _Bayesian regret_ in the
offline linear bandit setting. The high-confidence Bayesian objective has
received limited attention in the literature. Most prior work in offline RL
and bandit targets the _frequentist regret_ , which assumes a fixed true model
and studies the behavior of algorithms with a random dataset. In contrast,
Bayesian regret assumes a fixed dataset and studies the behavior of policies
with respect to a random true model. A discussion on the merits of the two
approaches is beyond the scope of our paper and has been covered elsewhere
[26, 14, 41].

The predominant approach to offline RL and bandit, regardless of being
Bayesian or frequentist, is a form of pessimism that usually aims to choose
actions with the highest lower confidence bounds (LCBs). These LCB-style
algorithms compute a policy with the largest expected return (or reward),
penalized by its uncertainty. In frequentist algorithms, these penalties are
typically computed from concentration inequalities [45, 35, 24, 15, 9],
whereas in Bayesian methods, they are usually derived in one form or another
from credible regions111A credible region is the Bayesian version of a
confidence region. derived from the posterior distribution [11, 19, 7], and
often give rise to some form of robust optimization [4, 33].

In this paper, we provide evidence that pessimistic LCB-style algorithms could
be unsuitable for computing a policy with a small Bayesian regret. In fact in
some situations, they may even maximize the Bayesian regret. To address this,
we propose an algorithm, BRMOB, that directly minimizes new tractable bounds
on the Bayesian regret. BRBOM leverages approaches studied in the context of
chance-constrained optimization, robust optimization, and monetary risk
measures [11, 33], and introduces only a small computational overhead in
comparison with the existing LCB-style methods [19].

To minimize the Bayesian regret, we reformulate the objective as a risk-averse
optimization problem with respect to epistemic uncertainty. In particular, the
usual high-confidence objective can be framed as a Value-at-Risk (VaR) of the
epistemic uncertainty. We then bound the VaR of the regret by combining
techniques from robust optimization and Chernoff-style upper bounds on the VaR
of Gaussian or sub-Gaussian posterior distributions of the (latent) reward
parameter. Using these bounds, we derive convex, conic optimization problems
that can be solved using modern solvers. Moreover, we show that our bounds can
be used to derive new offline regret bounds that tighten previous work [19].

Our BRMOB algorithm improves the state-of-the-art in Bayesian offline bandits
as follows. The only other algorithm for minimizing Bayesian regret in offline
linear bandits that we are aware of is FlatOPO [19] that returns a
_deterministic_ policy by maximizing LCBs. In contrast, we compute
_randomized_ policies that directly minimize bounds on the Bayesian regret.
This results in significantly lower regret bounds, both theoretically and in
numerical simulations. Another work in offline Bayesian bandits is by Uehara
and Sun [40] that targets average regret, which reduces to computing the best
action for the mean latent reward parameter. While there has been a
significant amount of work focusing on general high-confidence policies in
Bayesian offline RL (e.g., [33, 4, 12, 11, 28, 39, 2, 18]), the methods
primarily focus on maximizing the Bayesian return, rather than the regret, and
invariably obtain LCB-style algorithms. Exceptions include algorithms for
obtaining Bayesian regret guarantees in inverse RL, which employ scenario-
based algorithms for minimizing a specific form of regret [22, 7].

Bayesian regret minimization in offline bandits can also be framed as a
chance-constrained optimization problem [5]. The recent chance-constrained
optimization literature is mostly focused on chance constraints in which the
function is concave or linear in the uncertain parameter [16, 6]. However, the
chance constraint in the regret minimization problem is convex, preventing us
from using these methods. Another approach to non-concave chance-constrained
optimization is to resort to scenario-based or sample-based methods (e.g., [8,
31, 30, 7]). We briefly discuss these methods in Section 4 and outline two
possible scenario-based formulations for the regret minimization problem in
Appendix E. Such sample-based formulations are very general, simple to
implement and work well in practice. However, they scale poorly to larger
problems and cannot be used to derive new theoretical insights. The closest
result to our work is the Bernstein technique for bounding linear chance-
constrained programs [32, 34], which is a special case of one of our bounds.

The remainder of the paper is organized as follows. Section 3 describes the
offline linear bandit framework and the high-confidence Bayesian regret
objective. We summarize the basic properties of risk measures and illustrate
how they can be used to model our objective. Then, in Section 4, we introduce
new Bayesian regret bounds, derive corresponding convex optimization
solutions, and present our BRMOB algorithm. In Section 5, we derive regret
bounds for BRMOB in terms of problem parameters and argue that it compares
favorably with LCB-type approaches, such as FlatOPO [19]. Finally, the
numerical comparison in Section 6 provides additional evidence that minimizing
Bayesian regret is preferable to LCB-style algorithms in various problems.

##  2 Preliminaries

We begin by defining the notations we use throughout the paper. We use lower
and upper case bold letters to denote vectors and matrices, such as
$\bm{x}\in\mathbb{R}^{N}$ and $\bm{A}\in\mathbb{R}^{n\times n}$, and normal
font for the elements of vectors and matrices, e.g., $x_{i}$. We define the
weighted $\ell_{2}$-norm for any vector $\bm{x}\in\mathbb{R}^{d}$ and positive
definite matrix $\bm{A}\in\mathbb{R}^{d\times d}$ as
$\|\bm{x}\|_{\bm{A}}=\sqrt{\bm{x}^{\mathsf{T}}\bm{A}\bm{x}}$. We denote by
$\Delta_{k},\forall k\in\mathbb{N}$ the $k$-dimensional probability simplex,
and by $\bm{I}$, $\bm{0}$, $\bm{1}$, and $\bm{1}_{a}$ the identity matrix, the
zero vector, the one vector, and the one-hot vector all with appropriate
dimensions. Random variables are adorned with a tilde and are not capitalized.
For example, $\bm{\tilde{x}}$ represents a vector-valued random variable.
Finally, we denote by $\Omega$ the probability space of a random variable.

Suppose that $\tilde{x}\colon\Omega\rightarrow\mathbb{R}$ is a random variable
that represents costs. Then, its _value-at-risk_ (VaR) at a risk level
$\alpha\in[0,1)$ is usually defined as the largest lower-bound on its
$\alpha$-quantile (e.g., [13, definition 4.45, remark A.20]):222The precise
definition of VaR in the literature depends on whether $\tilde{x}$ represents
cost or reward [18]. If it represents _rewards_ , then its risk can be
controlled by maximizing $-\operatorname{VaR}_{\alpha}\left[-\tilde{x}\right]$
instead of minimizing $\operatorname{VaR}_{\alpha}\left[\tilde{x}\right]$.

$\operatorname{VaR}_{\alpha}\left[\tilde{x}\right]=\inf\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}>t\right]\leq
1-\alpha\right\\}=\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}\geq
t\right]>1-\alpha\right\\}.$ (1)

For Gaussian random variables, $\tilde{x}\sim\mathcal{N}(\mu,\sigma^{2})$, VaR
has the following analytical form [13]:

$\operatorname{VaR}_{\alpha}\left[\tilde{x}\right]\;=\;\mu+\sigma\cdot
z_{\alpha}\,,$ (2)

where $z_{\alpha}$ is the $\alpha$-quantile of the standard normal
distribution $\mathcal{N}(0,1)$.

##  3 Bayesian Offline Bandits

Consider a stochastic linear bandit problem with $k\in\mathbb{N}$ arms
(actions) from the set $\mathcal{A}=\\{1,\ldots,k\\}$. Each arm
$a\in\mathcal{A}$ is associated with a $d$-dimensional feature vector
$\bm{\phi}_{a}\in\mathbb{R}^{d}$ and its reward distribution has a mean
$r(a;\bm{\theta})=\bm{\phi}_{a}^{\mathsf{T}}\bm{\theta}$ for some unknown
parameter $\bm{\theta}\in\mathbb{R}^{d}$. We define the feature matrix
$\bm{\Phi}\in\mathbb{R}^{d\times k}$ as
$\bm{\Phi}=(\bm{\phi}_{a})_{a\in\mathcal{A}}$. The goal of the agent is to
learn a (possibly randomized) policy $\bm{\pi}\in\Delta_{k}$ to choose its
actions accordingly. We denote by $\pi_{a}$ the probability according to which
policy $\bm{\pi}$ selects an action $a\in\mathcal{A}$. The mean reward, or
value, of a policy $\bm{\pi}$ is defined as

$r(\bm{\pi};\bm{\theta})=\mathbb{E}_{#1}\left[\setargs{r(\tilde{a};\bm{\theta})\mid\tilde{a}\sim\bm{\pi}}\right]=\sum_{a\in\mathcal{A}}\pi_{a}\cdot
r(a;\bm{\theta})=\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\theta}\,.$
(3)

The optimal policy $\bm{\pi}^{\star}(\bm{\theta})$ is a policy which attains
the maximum in (3).

In the offline bandit setting, the agent only has access to a logged dataset
$\tilde{\mathcal{D}}=\\{(\tilde{a}_{i},\tilde{y}_{i})\\}_{i=1}^{n}$, and is
not capable of interacting further with the environment. Each pair
$(\tilde{a}_{i},\tilde{y}_{i})$ in $\tilde{\mathcal{D}}$ consists of an action
$\tilde{a}_{i}$ selected according to some arbitrary logging policy and a
sampled reward $\tilde{y}_{i}$ from the reward distribution of action
$\tilde{a}_{i}$. We use $D$ to refer to an instantiation of the random dataset
$\tilde{\mathcal{D}}$.

We take the Bayesian perspective in this paper and model our uncertainty about
the reward parameter $\bm{\tilde{\theta}}\colon\Omega\to\mathbb{R}^{d}$ by
assuming it is a random variable with a known prior
$P_{\bm{\tilde{\theta}}}(\bm{\theta})$. Therefore, all quantities that depend
on $\bm{\tilde{\theta}}$ are also random. The logged dataset $D$ is used to
derive the posterior density $P_{\bm{\tilde{\theta}}|D}(\bm{\theta})$ over the
reward parameter. To streamline the notation, we denote by
$\bm{\tilde{\theta}}_{D}:=(\bm{\tilde{\theta}}\mid\tilde{\mathcal{D}}=D)$ the
random variable distributed according to this posterior distribution
$P_{\bm{\tilde{\theta}}|D}$. The derivation of the posterior is standard and
does not play a role in the design of our algorithms, hence, we defer
discussing it to Section 5.

As described above, in the Bayesian offline bandit setting we assume that the
logged data $\tilde{\mathcal{D}}$ is fixed to some $D$ and the uncertainty is
over the reward parameter $\bm{\tilde{\theta}}$. This is different than the
frequentist offline setting in which the reward parameter is fixed,
$\bm{\tilde{\theta}}=\bm{\theta}^{\star}$, and the randomness is over
different datasets generated by the logging policy.

Our goal is to compute a policy $\bm{\pi}\in\Delta_{k}$ which minimizes the
_high-confidence Bayesian regret_
$\mathcal{R}_{\delta}\colon\Delta_{k}\to\mathbb{R}_{+}$, where
$\delta\in(0,1)$ is the tolerance parameter ($1-\delta$ is the confidence),
that is,

$\mathfrak{R}_{\delta}(\bm{\pi}):=\min\Big{\\{}\epsilon\mid\mathbb{P}\big{[}\max_{a\in\mathcal{A}}\;r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\leq\epsilon\big{]}\geq
1-\delta\Big{\\}}\;.$ (4)

This objective was also used in [19]. Note that in (4), we compare the value
of a fixed policy $\bm{\pi}$ with the reward of an action (max action) that
depends on the posterior random variable $\bm{\tilde{\theta}}_{D}$. Thus, one
cannot expect to achieve a regret of zero. By taking a close look at the
definition of regret in (4) and using the definition of VaR in (1), we may
equivalently write our objective in (4) as

$\mathfrak{R}_{\delta}(\bm{\pi})=\operatorname{VaR}_{1-\delta}\left[\max_{a\in\mathcal{A}}\;r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right]\,.$
(5)

Finally, we note that one could optimize other objectives besides the high-
confidence regret in (4) and (5), e.g., minimizing the expected regret, or
alternatively, maximizing VaR of the reward. We refer the reader to Appendix F
for further discussion on this, and related results/proofs.

##  4 Minimizing Analytical Upper Bounds on the Bayesian Regret

In this section, we propose our method for computing a policy which minimizes
the high-confidence Bayesian regret in (5):
$\min_{\bm{\pi}\in\Delta_{k}}\mathfrak{R}_{\delta}(\bm{\pi})$. All proofs for
this section can be found in Appendix B.

Perhaps the simplest way to minimize $\mathfrak{R}_{\delta}(\bm{\pi})$ is to
approximate it using samples from the posterior $\bm{\tilde{\theta}}_{D}$, and
return the policy $\bm{\pi}$ with the smallest (estimated) regret. This
approach, referred to as scenario-based optimization, has been studied
extensively in the context of chance-constrained optimization [8, 31, 30]. We
outline how it can be used in our setting in Appendix E. Despite the
generality and simplicity of this approach, it has several drawbacks,
including: requirement to sample from the posterior, and its computational
complexity scales poorly with $d$ (the dimension of $\bm{\tilde{\theta}}_{D}$)
and with the confidence level $1-\delta$. Moreover, obtaining theoretical
insight into the behavior of the regret from this approach is non-trivial.

In the rest of this section, we propose an analytical approach for minimizing
$\mathfrak{R}_{\delta}(\bm{\pi})$. To do this, we derive analytical upper-
bounds on $\mathfrak{R}_{\delta}(\bm{\pi})$ which can be minimized (over the
policy space) using tractable convex optimization techniques. For clarity, we
assume the posterior distribution over the reward parameter is Gaussian with
mean $\bm{\mu}\in\mathbb{R}^{d}$ and a _positive definite_ covariance matrix
$\bm{\Sigma}\in\mathbb{R}^{d\times d}$:
$\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$. Nevertheless,
our results can be easily extended to the sub-Gaussian case, as we show in
Appendix D.

We begin by showing that the Bayesian regret can be reduced to computing the
VaR of a maximum of normally distributed random variables.

######  Lemma 4.1.

Suppose that $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$
and $\bm{\tilde{x}}^{\bm{\pi}}\colon\Omega\to\mathbb{R}^{k}$ be a multivariate
Gaussian random variable
$\bm{\tilde{x}}^{\bm{\pi}}\sim\mathcal{N}\big{(}\bm{F}_{\bm{\pi}}^{\mathsf{T}}\bm{\mu}\;,\;\bm{F}_{\bm{\pi}}^{\mathsf{T}}\bm{\Sigma}\bm{F}_{\bm{\pi}}\big{)}$,
where $\bm{F}_{\bm{\pi}}=\bm{\Phi}(\bm{I}-\bm{\pi}\bm{1}^{\mathsf{T}})$ for
any policy $\bm{\pi}\in\Delta_{k}$. Then, the Bayesian regret in (5) can be
written as

$\mathfrak{R}_{\delta}(\bm{\pi})\;=\;\operatorname{VaR}_{1-\delta}\left[\max_{a\in\mathcal{A}}\;\tilde{x}_{a}^{\bm{\pi}}\right]\,,$
(6)

where
$\bm{\tilde{x}}^{\bm{\pi}}=\left(\bm{I}-\bm{1}\bm{\pi}^{\mathsf{T}}\right)\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}$.

Lemma 4.1 points to the main challenge in deriving tight bounds on
$\mathfrak{R}_{\delta}(\bm{\pi})$. Even when $\bm{\tilde{\theta}}_{D}$ is
normally distributed, the random variable
$\max_{a\in\mathcal{A}}\;\tilde{x}_{a}^{\bm{\pi}}$ is unlikely to be normally
distributed. The lack of normality prevents us from deriving an _exact_
analytical expression for $\mathfrak{R}_{\delta}(\bm{\pi})$ using the
expression in (2). In the remainder of the section, we derive two separate
techniques for upper-bounding the VaR of the maximum of random variables in
(6), thereby also bounding the regret $\mathfrak{R}_{\delta}(\bm{\pi})$.

#### 1) Action-set bound.

Our first upper-bound on $\mathfrak{R}_{\delta}(\bm{\pi})$ expresses the
regret as a maximum over regrets with respect to individual actions. We refer
to this bound as an action-set bound because it involves a coefficient
$z_{1-\delta\xi_{a}}$ which grows with the number of actions $k$.

######  Theorem 4.2.

Suppose that $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$.
Then the regret for each $\bm{\pi}\in\Delta_{k}$ satisfies

$\displaystyle\mathfrak{R}_{\delta}(\bm{\pi})$
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{VaR}_{1-\delta\xi_{a}}\left[r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right]$
(7)
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot
z_{1-\delta\xi_{a}}$

where $z_{1-\delta\xi_{a}}$ is the $(1-\delta\xi_{a})$-th standard normal
quantile and
$z_{1-\delta\xi_{a}}\leq\sqrt{2\log\nicefrac{{1}}{{\delta\xi_{a}}}}$.

###### Proof sketch.

We decompose the expression in (6) using the _union bound_ as

$\displaystyle\operatorname{VaR}_{1-\delta}\left[\max_{a\in\mathcal{A}}\;\tilde{x}_{a}^{\bm{\pi}}\right]$
$\displaystyle=\sup\Big{\\{}t\in\mathbb{R}\mid\mathbb{P}\big{[}\max_{a\in\mathcal{A}}\;\tilde{x}_{a}^{\bm{\pi}}\geq
t\big{]}>\delta\Big{\\}}\leq\sup\Big{\\{}t\in\mathbb{R}\mid\sum_{a\in\mathcal{A}}\mathbb{P}\left[\tilde{x}_{a}^{\bm{\pi}}\geq
t\right]>\delta\Big{\\}}$
$\displaystyle\leq\min_{\bm{\xi}\in\Delta_{k}}\sup\Big{\\{}t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}^{\bm{\pi}}\geq
t\right]>\delta\xi_{a},\,\forall
a\in\mathcal{A}\Big{\\}}=\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{VaR}_{1-\delta\xi_{a}}\left[\tilde{x}_{a}^{\bm{\pi}}\right].$

∎

Similar bounding techniques to Theorem 4.2 have been used in risk-averse and
chance-constrained literature previously. For example, the Bernstein bound in
Nemirovski and Shapiro [32] uses a similar decomposition, but is applied to
EVaR rather than VaR. Also, Hau et al. [17] uses a similar technique when
constructing a dynamic decomposition of VaR in the context of dynamic
programming.

To better understand Theorem 4.2, let $\bm{\xi}=1/k\cdot\bm{1}$ be uniform, in
which case the regret is bounded as

$\mathfrak{R}_{\delta}(\bm{\pi})\;\leq\;\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot
z_{1-\nicefrac{{\delta}}{{k}}}\,.$ (8)

Note that $z_{1-\nicefrac{{\delta}}{{k}}}\leq\sqrt{2\log(k/\delta)}$ as stated
in Theorem 4.2. A notable strength of this bound is that the coefficient
$z_{1-\nicefrac{{\delta}}{{k}}}$ grows sub-logarithmically with the number of
actions. We use this fact in Section 5 to derive new tighter regret bounds.
However, when the number of actions $k$ is very large the bound does not take
advantage of a potentially small dimension $d$ of the parameter $\bm{\theta}$.
Our next bound accounts for this.

#### 2) Parameter-space bound.

Our second regret bound improves on Theorem 4.2 when $d$ is much smaller than
$k$. We derive this bound using the standard robust representation of VaR [5].
We first construct a standard $(1-\delta)$-credible region
$\mathcal{P}_{\delta}\subseteq\mathbb{R}^{d}$ for the random variable
$\bm{\tilde{\theta}}_{D}$ as

$\mathcal{P}_{\delta}\;=\;\left\\{\bm{\theta}\in\mathbb{R}^{d}\mid\|\bm{\theta}-\bm{\mu}\|^{2}_{\bm{\Sigma}^{-1}}\leq\chi^{2}_{d}(1-\delta)\right\\}\,,$
(9)

where $\chi^{2}_{d}(1-\delta)$ is the $(1-\delta)$-th quantile of the
$\chi^{2}$ distribution with $d$ degrees of freedom. We then obtain the
following regret bound.

######  Theorem 4.3.

Suppose that $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$.
Then the regret for each $\bm{\pi}\in\Delta_{k}$ satisfies

$\displaystyle\mathfrak{R}_{\delta}(\bm{\pi})$
$\displaystyle\;\leq\;\max_{\bm{\theta}\in\mathcal{P}_{\delta}}\max_{a\in\mathcal{A}}\;\left(r(a;\bm{\theta})-r(\bm{\pi};\bm{\theta})\right)$
$\displaystyle\;\leq\;\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\sqrt{\chi^{2}_{d}(1-\delta)}\,,$
(10)

where $\mathcal{P}_{\delta}$ is defined in (9) and
$\sqrt{\chi^{2}_{d}(1-\delta)}\leq\sqrt{5d\log(1/\delta)}$.

###### Proof sketch.

Because $\|\bm{\theta}-\bm{\mu}\|^{2}_{\Sigma^{-1}}$ is a sum of $d$
independent squared random variables, it is distributed according to the
$\chi^{2}$ distribution with $d$ degrees of freedom. Then we show that
$\mathcal{P}_{\delta}$ is a $(1-\delta)$-credible region to upper-bound the
regret using the inequality
$\operatorname{VaR}_{\alpha}\left[\tilde{x}\right]\leq\max\left\\{x\in\mathcal{X}\right\\}$
when $\mathbb{P}\left[\tilde{x}\in\mathcal{X}\right]\geq\alpha$ for any set
$\mathcal{X}\subseteq\mathbb{R}$. ∎

One may wonder whether using a credible region to obtain the bound in Theorem
4.3 is an appropriate approach. A growing body of literature argues that using
credible regions in constructing robust approximations of VaR is overly
conservative when used with linear or concave functions [16, 6, 33]. These
results do not apply to our setting because the maximum in (6) is a _non-
concave_.

Input: Dataset $D$, prior $P_{\bm{\tilde{\theta}}}$, tolerance
$\delta\in(0,\nicefrac{{1}}{{2}})$, feature matrix
$\bm{\Phi}\in\mathbb{R}^{d\times k}$, # of iterations $m$

Output: Randomized policy $\bm{\pi}^{\star}\in\Delta_{\Delta}$ and regret
upper bound $\rho^{\star}$

1 Compute posterior distribution of $\bm{\tilde{\theta}}_{D}$ and the prior as
described in (13) ;

/* First phase: main minimization */

2 Set
$\;\nu^{0}_{a}\leftarrow\min\left\\{\sqrt{\chi^{2}_{d}(1-\delta)},z_{1-\nicefrac{{\delta}}{{k}}}\right\\}\;$
for each $a\in\mathcal{A}$ ;

3 Solve (11) with $\bm{\nu}=\bm{\nu}^{0}$ and let $\rho^{0}$ and
$\bm{\pi}^{0}$ be optimal objective and a minimizer respectively ;

/* Second phase: optional tightening step */

4 for  _$i=1,\ldots,m$_ do

5 Solve (12) with $\bm{\pi}=\bm{\pi}^{i-1}$ and let $\;\bm{\xi}^{i}$ be a
minimizer ;

6 Solve (11) with $\nu_{a}=z_{1-\delta\xi^{i}_{a}},\forall a\in\mathcal{A}$
and let $\rho^{i}$ and $\bm{\pi}^{i}$ be optimal value and a minimizer
respectively ;

7

/* Select the best policy from both phases */

8 $i^{\star}\leftarrow\arg\min_{i=0,\dots,m}\rho^{i}$ ;

9 return _$\;\bm{\pi}^{i^{\star}},\;\rho^{i^{\star}}$_ ;

Algorithm 1 BRMOB: Bayesian Regret Minimization for Offline Bandits

#### Optimization algorithm.

We now describe our main algorithm, _Bayesian Regret Minimization for Offline
Bandits_ (BRMOB), whose pseudo-code is reported in Algorithm 1. The goal is to
find a policy $\bm{\pi}$ that minimizes the regret bounds proposed in Theorems
4.2 and 4.3, simultaneously. The algorithm runs in two phases. In the first
phase, it minimizes a simplified bound on the regret which can be formulated
as a tractable optimization problem. In the second phase, it runs a sequence
of heuristic steps that can tighten the bounds and improve the computed
policy.

The algorithm proceeds as follows. In the first phase, Algorithm 1 computes
$\bm{\pi}^{0}$, which jointly minimizes the parameter-space bound in Theorem
4.3 and an upper-bound on the action-set bound in Theorem 4.2 as given in (8).
Recall that the bound in (8) simplifies the one in (7) by replacing the
minimization over $\bm{\xi}$ by assuming a fixed uniform
$\xi_{a}=1/k,\;\forall a\in\mathcal{A}$, and as a result is an upper-bound on
it. Note that the bounds in (8) and (10) only differ in the coefficient
associated with $\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}$. Because
the coefficients in (8) and (10) are independent of $a\in\mathcal{A}$, the two
bounds can be combined into a single one with a coefficient
$\nu_{a}=\min\\{\sqrt{\chi^{2}_{d}(1-\delta)},z_{1-\nicefrac{{\delta}}{{k}}}\\},\;\forall
a\in\mathcal{A}$ and minimized by solving

$\min_{\bm{\pi},\;\bm{s}\in\mathbb{R}^{k}_{+},\;t\in\mathbb{R}}\left\\{t\mid\bm{1}^{\mathsf{T}}\bm{\pi}=1,\;t\geq(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\mu}+s_{a}\cdot\nu_{a},\;s_{a}^{2}\geq\norm{\bm{\phi}_{a}-\bm{\pi}}_{\bm{\Sigma}}^{2},\,\forall
a\in\mathcal{A}\right\\}.$ (11)

The optimization in (11) is a second-order conic optimization (SOCP), which
can be solved efficiently when $\bm{\nu}>\bm{0}$ with the similar time
complexity as a linear program [3, 29].

In the second phase, Algorithm 1 repeatedly computes policies
$\bm{\pi}^{1},\dots,\bm{\pi}^{m}$ by optimizing a sequence of bounds in
Theorem 4.2 tightened by optimizing the parameter $\bm{\xi}$. In particular,
Algorithm 1 alternates between optimizing over $\bm{\pi}$ and $\bm{\xi}$. For
a fixed $\bm{\xi}$, it optimizes over $\bm{\pi}$ using the optimization
program (11), and for an incumbent policy $\bm{\pi}$, it uses the following
optimization to compute $\bm{\xi}$ that minimizes an upper-bound on the regret
(when $\delta\leq\nicefrac{{1}}{{2}}$):

$\min_{\bm{\xi},\,\bm{s}\in\mathbb{R}^{k}_{+},\,\bm{l}\in\mathbb{R}^{k},\;t\in\mathbb{R}}\left\\{t\mid\bm{1}^{\mathsf{T}}\bm{\xi}=\delta,\;t\geq\mu^{\bm{\pi}}_{a}+\sigma^{\bm{\pi}}_{a}\cdot
s_{a},\;s_{a}^{2}\geq-2l_{a},\;l_{a}\leq\log\xi_{a},\,\forall
a\in\mathcal{A}\right\\},$ (12)

where $\mu_{a}^{\bm{\pi}}=\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})$
and
$\sigma_{a}^{\bm{\pi}}=\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}$
for each $a\in\mathcal{A}$. The optimization in (12) upper-bounds the standard
normal quantiles
$z_{1-\delta\xi_{a}}\leq\sqrt{2\log(\nicefrac{{1}}{{\delta\xi_{a}}})}$, as
stated in Theorem 4.2, and can be solved efficiently as a conic optimization
problem that involves both exponential and second order cones [3, 29]. This
phase, which we also refer to as the tightening step, can also be seen as a
coordinate descent approach to minimize the regret bound in Theorem 4.2 in
(7).

It is important to emphasize that the second phase is a heuristic. It would be
preferable to optimize the regret bound in (7) simultaneously over $\bm{\pi}$
and $\bm{\xi}$, but unfortunately such optimization is non-convex and
intractable. However, this heuristic phase does not increase the regret in
comparison to the first phase because the final policy it returns is the one
with minimum regret among the $m$ computed policies (see Line 1). Therefore,
our regret analysis of Algorithm 1 in the next section holds regardless of
this tightening step.

A somewhat unusual characteristic of BRMOB is that it may compute a
_randomized_ policy. Unlike online bandits, the goal of the randomization
among the actions is not to explore, but rather reduce the risk of achieving
high regret. As we discuss in Section 5, the ability to randomize among
multiple actions may help to significantly reduce the Bayesian regret.

In the remainder of the paper, we focus on the theoretical analysis of the
first phase of the algorithm (when $m=0$). We can immediately establish the
following guarantee on the regret of its policy.

######  Corollary 4.4.

Suppose that $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$
and Algorithm 1 returns a policy $\bm{\hat{\pi}}$ and a regret bound
$\hat{\rho}$. Then, we can bound the regret of $\bm{\hat{\pi}}$ as

$\mathfrak{R}_{\delta}(\bm{\hat{\pi}})\leq\hat{\rho}\leq\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\min\left\\{\sqrt{2\log(k/\delta)},\sqrt{5d\log(1/\delta)}\right\\}\,.$

In the next section, we use Corollary 4.4 to bound the regret of Algorithm 1.

##  5 Theoretical Analysis

This section analyses the regret of BRMOB (Algorithm 1) with respect to $k$,
$d$, and $n$ (the size of the dataset $D$) and compares it with an LCB-based
algorithm for offline bandits [19]. Proofs for the claims in this section can
be found in Appendix C.

Similar to prior work [19], we assume a normal prior distribution over the
reward parameter:
$P_{\bm{\tilde{\theta}}}=\mathcal{N}(\bm{\mu}_{0},\bm{\Sigma}_{0})$ with an
invertible $\bm{\Sigma}_{0}$, and normal reward
$\tilde{y}\sim\mathcal{N}\big{(}r(a;\bm{\tilde{\theta}})=\bm{\phi}_{a}^{\mathsf{T}}\bm{\tilde{\theta}},\bar{\sigma}^{2}\big{)}$
for each action $a\in\mathcal{A}$. After observing the logged dataset
$D=\\{(a_{i},y_{i})\\}_{i=1}^{n}$, we can use _Bayesian linear regression
algorithms_ [36, 10] and compute the following posterior distribution over
$\bm{\tilde{\theta}}_{D}$:

$\bm{\Sigma}_{n}=(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\bm{G}_{n})^{-1},\qquad\bm{\mu}_{n}=\bm{\Sigma}_{n}(\bm{\Sigma}_{0}^{-1}\bm{\mu}_{0}+\bar{\sigma}^{-2}\bm{B}_{n}\bm{y}_{n}),$
(13)

where $\bm{B}_{n}=(\phi_{a_{i}})_{i=1}^{n}$ is the matrix with observed
features in its columns, $\bm{y}_{n}=(y_{i})_{i=1}^{n}$ is the vector of
observed rewards, and $\bm{G}_{n}=\bm{B}_{n}^{\mathsf{T}}\bm{B}_{n}$ is the
data covariance matrix.

We make the following standard assumption about the quality of data [19].

######  Assumption 5.1.

The feature vector satisfies that $\|\bm{\phi}_{a}\|_{2}\leq 1$ for each
$a\in\mathcal{A}$ and there exists a $\gamma>0$ such that the data covariance
matrix $\bm{G}_{n}$ satisfies

$\bm{G}_{n}\;\succeq\;\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}},\qquad\forall
a\in\mathcal{A},\;\forall n\geq 1\,.$

5.1 plays a key role in understanding how the Bayesian regret scales as a
function of the problem’s parameters. The intuition behind 5.1 is that the
dataset provides sufficient information such that the norm of the covariance
matrix $\bm{\Sigma}_{n}$ of the posterior distribution over
$\bm{\tilde{\theta}}_{D}$ decreases linearly with $n$. From a frequentist
perspective, this assumption holds with high probability by the Bernstein-Von-
Mises theorem under mild conditions (e.g., [41]). Using this assumption, we
are ready to bound the Bayesian regret of BRMOB, as shown by the following
result.

######  Theorem 5.2 (BRMOB regret bound).

Let 5.1 holds and
$\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu}_{n},\bm{\Sigma}_{n})$ with
$\bm{\mu}_{n}$ and $\bm{\Sigma}_{n}$ given in (13). Then, the regret of the
policy $\bm{\hat{\pi}}$ returned by Algorithm 1 can be bounded as

$\mathfrak{R}_{\delta}(\bm{\hat{\pi}})\;\leq\;2\sqrt{\frac{\min\left\\{2\log(\nicefrac{{k}}{{\delta}}),5d\log(\nicefrac{{1}}{{\delta}})\right\\}}{\lambda_{\max}(\bm{\Sigma}_{0})^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n}}.$ (14)

###### Proof sketch.

Letting
$\bm{\pi^{\prime}}\in\arg\max_{\bm{\pi}\in\Delta_{k}}\bm{\mu}^{\mathsf{T}}\bm{\Phi}\bm{\pi}$,
we bound the regret of $\bm{\hat{\pi}}$ from Corollary 4.4 as

$\mathfrak{R}_{\delta}(\bm{\hat{\pi}})\;\leq\;\max_{a\in\mathcal{A}}\,\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi^{\prime}})}_{\bm{\Sigma}_{n}}\cdot\min\left\\{\sqrt{2\log(\nicefrac{{k}}{{\delta}})},\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\right\\}.$

Then, the Cauchy-Schwartz inequality and algebraic manipulation show that

$\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi^{\prime}})}_{\bm{\Sigma}_{n}}^{2}=\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{1}_{a}+{\bm{\pi^{\prime}}}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\pi^{\prime}}-2\cdot\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\pi^{\prime}}\leq
4\max_{a^{\prime}\in\mathcal{A}}\bm{\phi}_{a^{\prime}}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a^{\prime}}\,.$

From 5.1 and matrix identities, we bound the covariance term for each
$a\in\mathcal{A}$ as

$\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a}\;\leq\;\bm{\phi}_{a}^{\mathsf{T}}(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}})^{-1}\bm{\phi}_{a}\;.$

Finally, we obtain the desired bound by applying the Sherman-Morrison-Woodbury
formula as

$\bm{\phi}_{a}^{\mathsf{T}}\left(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}}\right)^{-1}\bm{\phi}_{a}\;=\;\left(\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{0}^{-1}\bm{\phi}_{a}+\bar{\sigma}^{-2}\cdot\gamma
n\right)^{-1}.$

∎

#### Comparison to Hong et al. [19].

As discussed in the introduction, previous work has proposed to solve Bayesian
offline bandits by choosing a policy that maximizes a lower confidence bound
(LCB) on the mean reward of each action [4, 33, 19]. One particular
instantiation of this principle is FlatOPO [19], which computes its action
deterministically as

$\hat{a}\;\in\;\arg\max_{a\in\mathcal{A}}\,\left(\bm{\mu}_{n}^{\mathsf{T}}\bm{\phi}_{a}-\beta\cdot\sqrt{\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a}}\right)\,,$
(15)

where $\beta=\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}$. The optimization in
(15) can be derived as a minimization of a relaxed version of our bound in
Theorem 4.3 as

$\displaystyle\mathfrak{R}_{\delta}(\bm{\pi})\;\leq\;\max_{\bm{\theta}\in\mathcal{P}_{\delta}}\;\max_{a\in\mathcal{A}}\left(r(a;\bm{\theta})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right)\;\leq\;\max_{a\in\mathcal{A}}\;\max_{\bm{\theta}_{1}\in\mathcal{P}_{\delta}}r(a;\bm{\theta}_{1})-\min_{\bm{\theta}_{2}\in\mathcal{P}_{\delta}}r(\bm{\pi};\bm{\theta}_{2})$
(16)
$\displaystyle\;\leq\;\left(\max_{a\in\mathcal{A}}\,\bm{\mu}_{n}^{\mathsf{T}}\bm{\phi}_{a}+\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\cdot\sqrt{\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a}}\right)-\left(\bm{\mu}_{n}^{\mathsf{T}}\bm{\Phi}\bm{\pi}-\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\cdot\sqrt{\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\pi}}\right)\,.$

Since the first term in the above bound is independent of $\bm{\pi}$, it is
sufficient to maximize the second term in order to minimize the regret bound,
which corresponds to (15). Under 5.1, Hong et al. [19] derive the following
bound on the Bayesian regret of the policy $\bm{\hat{\pi}}$ returned by
FlatOPO:

$\mathfrak{R}_{\delta}(\bm{\hat{\pi}})\;\leq\;2\sqrt{\frac{5d^{2}\log(\nicefrac{{1}}{{\delta}})}{\lambda_{\max}(\bm{\Sigma}_{0})^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n}}\;.$ (17)

Comparing our regret bound for BRMOB in (14) with FlatOPO in (17) we notice
two main improvements. The first one is that the regret of BRMOB is bounded by
$\sqrt{\log k}$. When the number of actions $k$ satisfies $k\ll\exp d$, the
regret guarantee of BRMOB can be dramatically lower than that achieved by
FlatOPO. It is unclear how one could extend the existing analysis in Hong et
al. [19] to bound its regret in terms of $k$. Its design and analysis rely on
constructing a robust set (see in (16)), which seems to be difficult to
restrict it using the number of actions $k$.

The second main improvement is that the BRMOB’s regret bound grows $\sqrt{d}$
slower than FlatOPO’s. This is a significant reduction in regret, but we
believe that it is a consequence of our tighter analysis and not originated
from better algorithmic design. The analysis in Hong et al. [19] uses a
general upper-bound on the trace of a rank one matrix, which introduces an
unnecessary $\sqrt{d}$ term.

Figure 1: Visualization of BRMOB and LCB solutions in two bandit problems
illustrating a failure _(left)_ and a success _(right)_ of LCB. The radius of
each dashed circle corresponds to the upper-bound
$\|\bm{h}_{a}-\bm{H}\bm{\pi}\|_{2}$ on the regret of each policy $\bm{\pi}$.

#### On the LCB approach to regret in Bayesian offline bandits.

We now argue that the LCB approach is unsuitable for minimizing high-
confidence _regret_ in offline bandits. The intuition behind the LCB approach
is that one should prefer actions with low uncertainty, and thus, limited
downside. When the goal is to maximize VaR of _reward_ , this intuition is
correct and we show in Section F.1 that the LCB approach computes the optimal
policy. However, this intuition is wrong when the goal is to minimize the
high-confidence _regret_. Actions with low uncertainty also have limited
upside, and thus, can have high regret. In this case, a good policy needs to
hedge, or randomize, among actions with low and high uncertainty to achieve
low regret. BRMOB computes precisely such a policy. A tighter regret bound on
BRMOB in Corollary C.1 and our numerical results in Section 6 support this
fact.

In the following scenario, any LCB approach computes an incorrect action.
Consider a bandit problem where the actions’ means are identical, (such as
$\bm{\mu}_{n}=\bm{0}$). Then, BRMOB solves

$\arg\min_{\bm{\pi}\in\Delta_{k}}\,\|\bm{h}_{a}-\bm{H}\bm{\pi}\|_{2}\;,$ (18)

where $\bm{h}_{a}=\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a}$ and
$\bm{H}=(\bm{h}_{a})_{a\in\mathcal{A}}$. The optimization in (18) corresponds
to finding the _Chebyshev center_ [43] of the set
$\left\\{\bm{h}_{a}\right\\}_{a\in\mathcal{A}}$. In contrast, any LCB
objective in (15) finds a (deterministic) policy that solves
$\arg\min_{\bm{\pi}}\,\|\bm{0}-\bm{H}\bm{\pi}\|_{2}$, which corresponds to
selecting an action $a$ whose projection $\bm{h}_{a}$ is closest to the
origin. The distance of the policy from the origin is an arbitrary objective
and a bad proxy for the regret. To illustrate this point, Figure 1 depicts
$\bm{h}_{a}$ and $\bm{H}\bm{\pi}$ projections for two bandit problems: one in
which LCB selects an action that _maximizes_ the Bayesian regret (left) and
one that shows LCB works well because the origin is near the Chebyshev center
of $\bm{h}_{a}$ (right).

##  6 Numerical Results

In this section, we compare BRMOB to several baselines on synthetic domains.
Particularly, we compare it to (i) FlatOPO [19] that is based on the LCB
principle, (ii) Greedy method which selects an action $a$ with the largest
value of $\bm{\mu}_{n}\bm{1}_{a}$, and finally, (iii) ScenarioR, the scenario-
based method which upper-bounds the VaR using CVaR and then approximates it
using samples. We expect ScenarioR to perform the best as it approximates a
tight upper-bound on the Bayesian regret $\mathfrak{R}_{\delta}$.
Nevertheless, as we note in Section 5, this sampling-based algorithm has high
computational complexity. We compare our method to ScenarioR to emphasize that
it achieves comparable regret.

Figure 2:  Bayesian regret with $k=d=5$ (left), $k=d=50$ (middle and right).
The prior mean is $\bm{\mu}_{0}=\bm{0}$ (left and middle) and
$(\bm{\mu}_{0})_{a}=\sqrt{a}\;$ for $a=1,\dots 50$ _(right)_.

Figure 3:  Bayesian regret with $d=4$ and $k=10$ (left), $k=50$ (middle), and
$k=100$ (right).

Our experiments use synthetic domains, each defined by a normal prior
$(\bm{\mu}_{0},\bm{I})$ and a feature matrix $\bm{\Phi}$. To evaluate the
Bayesian regret as a function of data size, we first sample a single large
dataset and then vary the number of data-points $n$ from this set used to
estimate the posterior distributions. The regret for each policy is computed
by a scenario-based algorithm that samples from the posterior and computes the
empirical VaR. We use error tolerance of $\delta=0.1$ throughout. Results are
averaged over $100$ runs of this process to reduce variance. As confidence
intervals were negligible for all algorithms except FlatOPO, to avoid clutter,
we do not plot them here, and refer the reader to Appendix G for additional
details.

We evaluate the algorithms on three domains. The first one uses $k=d$ actions,
an identity matrix as the features: $\bm{\Phi}=\bm{I}$, and
$\bm{\mu}_{0}=\bm{0}$. The second one is the same, except
$(\bm{\mu}_{0})_{a}=\sqrt{a}$ to simulate varying rewards for actions.
Finally, the third one uses a fixed dimension $d=4$ and varies the number of
actions using randomly-generated features from the $L_{\infty}$ ball.

Figures 2 and 3 summarize our numerical results. They consistently show across
all domains that BRMOB significantly outperforms FlatOPO. FlatOPO’s
performance is noisy because the $\beta$ coefficient in (15) is relatively
large when the action count is high. A common practice is to tune $\beta$, but
we did not find any value of $\beta$ for which FlatOPO performs better than
Greedy. Greedy performs surprisingly well, which provides additional evidence
that the LCB approach is unsuitable for computing policies that minimize the
Bayesian regret. We provide additional results, including runtime, in Appendix
G.

##  7 Discussion and Conclusion

We proposed BRMOB, a new approach for minimizing Bayesian regret in offline
bandits, by minimizing analytical upper bounds on the Bayesian regret. This
approach facilitates tractable algorithms and new theoretical analysis. We
also provided theoretical and numerical evidence indicating that minimizing
Bayesian regret is superior to LCB-style algorithms.

Our approach can be extended to several more general settings. The algorithm
and bounds can be generalize to sub-Gaussian posterior distributions as
described in Appendix D. The algorithm can also be extended to contextual
linear bandits by computing a separate policy $\pi$ for each context
individually. One could also consider optimizing expected regret for a random
context, which would lead to similar optimization problems as we study in the
paper. Finally, our approach also applies to linear and general Markov
decision processes, but such a setting introduces additional computational
complexities that are beyond the scope of this paper and we leave it for
future work.

Another important future direction is understanding the implications of our
results to frequentist settings where similar concerns about the value of the
LCB approach have been raised previously [46, 44]. However, Bayesian and
frequentist regret differ fundamentally in their definitions and their
relationship is poorly understood in offline settings.

## References

  * Ahmadi-Javid [2012] A. Ahmadi-Javid.  Entropic Value-at-Risk: A new coherent risk measure.  _Journal of Optimization Theory and Applications_ , 155(3):1105–1123, 2012.
  * Angelotti et al. [2021] Giorgio Angelotti, Nicolas Drougard, and Caroline Ponzoni Carvalho Chanel.  Exploitation vs caution: Risk-sensitive policies for offline learning.  _arXiv:2105.13431 [cs, eess]_ , 2021.
  * ApS [2022] MOSEK ApS.  _The MOSEK optimization toolbox for MATLAB manual. Version 10.0._ , 2022.
  * Behzadian et al. [2021] Bahram Behzadian, Reazul Russel, Chin Pang Ho, and Marek Petrik.  Optimizing percentile criterion using robust MDPs.  In _International Conference on Artificial Intelligence and Statistics (AIStats)_ , 2021.
  * Ben-Tal et al. [2009] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.  _Robust Optimization_.  Princeton University Press, 2009.
  * Bertsimas et al. [2021] Dimitris Bertsimas, Dick den Hertog, and Jean Pauphilet.  Probabilistic Guarantees in Robust Optimization.  _SIAM Journal on Optimization_ , 31(4):2893–2920, 2021.
  * Brown et al. [2020] Daniel S. Brown, Scott Niekum, and Marek Petrik.  Bayesian robust optimization for imitation learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Calafiore and Campi [2005] Guiuseppe Calafiore and M C Campi.  Uncertain convex programs: Randomized solutions and confidence levels.  _Mathematical Programming, Series A_ , 102:25–46, 2005\.
  * Cheng et al. [2022] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal.  Adversarially trained actor critic for offline reinforcement learning, 2022.
  * Deisenroth et al. [2021] Marc Peter Deisenroth, A Aldo Faisal, and Cheng Soon Ong.  _Mathematics for Machine Learning_.  2021\.
  * Delage and Mannor [2010] E. Delage and S. Mannor.  Percentile optimization for Markov decision processes with parameter uncertainty.  _Operations Research_ , 58(1):203–213, 2010.
  * Derman et al. [2018] Esther Derman, Daniel Mankowitz, Timothy A Mann, and Shie Mannor.  Soft-robust actor-critic policy-gradient.  In _Uncertainty in Artificial Intelligence (UAI)_ , 2018.
  * Follmer and Schied [2016] Hans Follmer and Alexander Schied.  _Stochastic Finance: Introduction in Discrete Time_.  De Gruyter Graduate, fourth edition, 2016.
  * Gelman et al. [2014] Andrew Gelman, John B Carlin, Hal S Stern, and Donald B Rubin.  _Bayesian Data Analysis_.  Chapman and Hall/CRC, 3rd edition, 2014.
  * Ghosh et al. [2022] Dibya Ghosh, Anurag Ajay, Pulkit Agrawal, and Sergey Levine.  Offline RL policies should be trained to be adaptive, 2022.
  * Gupta [2019] Vishal Gupta.  Near-optimal bayesian ambiguity sets for distributionally robust optimization.  _Management Science_ , 65(9):4242–4260, 2019\.
  * Hau et al. [2023a] Jia Lin Hau, Erick Delage, Mohammad Ghavamzadeh, and Marek Petrik.  On dynamic programming decompositions of static risk measures in Markov decision processes, 2023a.
  * Hau et al. [2023b] Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh.  Entropic risk optimization in discounted MDPs.  In _Artificial Intelligence and Statistics (AISTATS)_ , 2023b.
  * Hong et al. [2023] Joey Hong, Branislav Kveton, Sumeet Katariya, Manzil Zaheer, and Mohammad Ghavamzadeh.  Multi-task off-policy learning from bandit feedback.  In _International Conference on Machine Learning_ , 2023.
  * Horn and Johnson [2013] Roger A. Horn and Charles A Johnson.  _Matrix Analysis_.  Cambridge University Press, second edition, 2013.
  * Hsu et al. [2012] Daniel Hsu, Sham Kakade, and Tong Zhang.  A tail inequality for quadratic forms of subgaussian random vectors.  2012\.
  * Javed et al. [2021] Zaynah Javed, Daniel Brown, Satvik Sharma, Jerry Zhu, Ashwin Balakrishna, Marek Petrik, Anca Dragan, and Ken Goldberg.  Policy gradient Bayesian robust optimization for imitation learning.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Jin et al. [2019] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan.  A short note on concentration inequalities for random vectors with subgaussian norm.  _arXiv preprint arXiv:1902.03736_ , 2019.
  * Jin et al. [2022] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline RL?, 2022.
  * Lange et al. [2012] Sasche Lange, Thomas Gabel, and Martin Riedmiller.  Batch reinforcement learning.  In _Reinforcement Learning_ , pages 45–73. 2012.
  * Lattimore and Szepesvari [2018] Tor Lattimore and Csaba Szepesvari.  _Bandit Algorithms_.  2018\.
  * Laurent and Massart [2000] B. Laurent and P. Massart.  Adaptive estimation of a quadratic functional by model selection.  _The Annals of Statistics_ , 28(5):1302–1338, 2000.
  * Lobo et al. [2020] Elita A. Lobo, Mohammad Ghavamzadeh, and Marek Petrik.  Soft-Robust Algorithms for Handling Model Misspecification, 2020\.
  * Lubin et al. [2023] Miles Lubin, Oscar Dowson, Joaquim Dias Garcia, Joey Huchette, Benoît Legat, and Juan Pablo Vielma.  Jump 1.0: Recent improvements to a modeling language for mathematical optimization.  _Mathematical Programming Computation_ , 2023.
  * Luedtke and Ahmed [2008] James Luedtke and Shabbir Ahmed.  A sample approximation approach for optimization with probabilistic constraints.  _SIAM Journal on Optimization_ , 19(2):674–699, 2008.
  * Nemirovski and Shapiro [2006] Arkadi Nemirovski and Alexander Shapiro.  Scenario Approximations of Chance Constraints.  In Giuseppe Calafiore and Fabrizio Dabbene, editors, _Probabilistic and Randomized Methods for Design under Uncertainty_ , pages 3–47. Springer, 2006.
  * Nemirovski and Shapiro [2007] Arkadi Nemirovski and Alexander Shapiro.  Convex approximations of chance constrained programs.  _SIAM Journal on Optimization_ , 17(4):969–996, 2007.
  * Petrik and Russel [2019] Marek Petrik and Reazul Hasan Russel.  Beyond confidence regions: Tight Bayesian ambiguity sets for robust MDPs.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Pintér [1989] J. Pintér.  Deterministic approximations of probability inequalities.  _Zeitschrift für Operations-Research_ , 33(4):219–239, 1989.
  * Rashidinejad et al. [2022] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _IEEE Transactions on Information Theory_ , 68(12):8156–8196, 2022.
  * Rasmussen and Williams [2006] Carl Edward Rasmussen and Christopher Williams.  _Gaussian Processes for Machine Learning._ 2006\.
  * Rockafellar and Wets [2009] R. Tyrrell Rockafellar and Roger JB Wets.  _Variational Analysis_.  2009\.
  * Shapiro et al. [2014] A. Shapiro, D. Dentcheva, and A. Ruszczynski.  _Lectures on Stochastic Programming: Modeling and Theory_.  SIAM, 2014.
  * Steimle et al. [2021] Lauren N Steimle, David L Kaufman, and Brian T Denton.  Multi-model Markov decision processes.  _IISE Transactions_ , 53, 2021.
  * Uehara and Sun [2023] Masatoshi Uehara and Wen Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  In _International Conference on Learning Representations (ICLR)_ , 2023.
  * Vaart [2000] A. W. Van Der Vaart.  _Asymptotic Statistics_.  Cambridge University Press, 2000.
  * Vershynin [2010] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  _arXiv preprint arXiv:1011.3027_ , 2010.
  * Xia et al. [2019] Yong Xia, Meijia Yang, and Shu Wang.  Chebyshev center of the intersection of balls: Complexity, relaxation and approximation, 2019.
  * Xiao et al. [2021] Chenjun Xiao, Yifan Wu, Tor Littlemore, Bo Dai, Jincheng Mei, Lihong Li, Csaba Szepesvari, and Dale Schuurmans.  On the optimality of batch policy optimization algorithms.  In _International Conference of Machine Learning (ICML)_ , 2021.
  * Xie et al. [2021] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 6683–6694, 2021.
  * Xie et al. [2022] Tengyang Xie, Mohak Bhardwaj, Nan Jiang, and Ching-An Cheng.  ARMOR: A model-based framework for improving arbitrary baseline policies with offline data, 2022.

##  Appendix A Technical Background and Lemmas

#### Sub-Gaussian random variable.

A scalar random variable $\tilde{x}\colon\Omega\to\mathbb{R}$ with mean
$\mu=\mathbb{E}_{#1}\left[\setargs{\tilde{x}}\right]$ is sub-Gaussian with a
variance factor $\sigma^{2}\geq 0$ when

$\mathbb{E}\big{[}\exp\big{(}\lambda(\tilde{x}-\mu)\big{)}\big{]}\;\leq\;\exp\big{(}\lambda^{2}\sigma^{2}/2\big{)},\qquad\forall\lambda\in\mathbb{R}\,.$
(19)

A multivariate random variable $\bm{\tilde{x}}\colon\Omega\to\mathbb{R}^{d}$
with a mean $\bm{\mu}=\mathbb{E}_{#1}\left[\setargs{\bm{\tilde{x}}}\right]$ is
_sub-Gaussian_ with a covariance factor $\bm{\Sigma}\in\mathbb{R}^{d\times d}$
when [42, 21, 23]

$\mathbb{E}\big{[}\exp\big{(}\lambda\bm{w}^{\mathsf{T}}(\bm{\tilde{x}}-\bm{\mu})\big{)}\big{]}\;\leq\;\exp\big{(}\lambda^{2}\bm{w}^{\mathsf{T}}\bm{\Sigma}\bm{w}/2\big{)},\qquad\forall\lambda\in\mathbb{R},\;\forall\bm{w}\in\Delta_{d}\,.$
(20)

#### Entropic Value-at-Risk (EVaR).

The EVaR is a risk measure related to VaR, defined as [1]

$\operatorname{EVaR}_{\alpha}\left[\tilde{x}\right]\;=\;\inf_{\beta>0}\,\beta^{-1}\big{(}\mathbb{E}[\exp(\beta\tilde{x})]-\log(1-\alpha)\big{)}\,,\qquad\forall\alpha\in[0,1).$
(21)

#### EVaR properties:

The following lemma shows that EVaR is an upper-bound on VaR. This is a
property that will be useful in our proofs later on.

######  Lemma A.1.

For any random variable $\tilde{x}\colon\Omega\to\mathbb{R}$, we have that

$\operatorname{VaR}_{\alpha}\left[\tilde{x}\right]\;\leq\;\operatorname{EVaR}_{\alpha}\left[\tilde{x}\right],\qquad\forall\alpha\in[0,1).$

###### Proof.

This is a consequence of Proposition 3.2 in Ahmadi-Javid [1] and the fact that
CVaR upper bounds VaR. ∎

Similar to (2) for VaR, we can show that for Gaussian random variables,
$\tilde{x}\sim\mathcal{N}(\mu,\sigma^{2})$, EVaR has the following analytical
form [1]:

$\operatorname{EVaR}_{\alpha}\left[\tilde{x}\right]\;=\;\mu+\sigma\cdot\sqrt{-2\log(1-\alpha)}.$
(22)

One advantage of EVaR over VaR is that we can bound it in the more general
case of sub-Gaussian random variables by the same bound as for a normal random
variable in (22) (see the following lemma).

######  Lemma A.2.

Let $\tilde{x}\colon\Omega\to\mathbb{R}$ be a sub-Gaussian random variable
defined according to (19). Then, we have

$\operatorname{EVaR}_{\alpha}\left[\tilde{x}\right]\;\leq\;\mu+\sigma\cdot\sqrt{-2\log(1-\alpha)}\,,\qquad\forall\alpha\in[0,1)\;.$

###### Proof.

From the translation invariance of EVaR [1, Theorem 3.1] and the definitions
in (19) and (21), we have

$\displaystyle\operatorname{EVaR}_{\alpha}\left[\tilde{x}\right]$
$\displaystyle=\mu+\operatorname{EVaR}_{\alpha}\left[\tilde{x}-\mu\right]=\mu+\inf_{\beta>0}\,\beta^{-1}\cdot\Big{(}\mathbb{E}_{#1}\left[\setargs{\exp\big{(}\beta\cdot(\tilde{x}-\mu)\big{)}}\right]-\log(1-\alpha)\Big{)}$
$\displaystyle\leq\mu+\inf_{\beta>0}\,\beta^{-1}\cdot\left(\frac{\beta^{2}\sigma^{2}}{2}-\log(1-\alpha)\right)=\mu+\sigma\cdot\sqrt{-2\log(1-\alpha)}\,.$

The last step follows by solving for the optimal
$\beta^{\star}=\sigma^{-1}\sqrt{-2\log(1-\alpha)}$ from the first-order
optimality conditions of the convex objective function. ∎

##  Appendix B Proofs of Section 4

###### Proof of Lemma 4.1.

We obtain by algebraic manipulation that

$\displaystyle\max_{a\in\mathcal{A}}\;r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})$
$\displaystyle=\max_{a\in\mathcal{A}}\;\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}-\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}=\max_{a\in\mathcal{A}}\;\bm{1}_{a}^{\mathsf{T}}\left(\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}-\bm{1}\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\right)$
$\displaystyle=\max_{a\in\mathcal{A}}\;\bm{1}_{a}^{\mathsf{T}}\left(\bm{I}-\bm{1}\bm{\pi}^{\mathsf{T}}\right)\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\,.$

Let
$\bm{\tilde{x}}^{\bm{\pi}}=\left(\bm{I}-\bm{1}\bm{\pi}^{\mathsf{T}}\right)\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}$,
which is a linear transformation of the normal random variable
$\bm{\tilde{\theta}}_{D}$. The result follows because linear transformations
preserve normality [10]. ∎

###  B.1 Proof of Theorem 4.2

We first report a result in the following lemma which we later use to prove
Theorem 4.2.

######  Lemma B.1.

Suppose $\bm{\tilde{x}}\colon\Omega\to\mathbb{R}^{k}$ is a random variable
such that all $\alpha$-quantiles, $\forall\alpha\in[0,1)$, for each
$\tilde{x}_{a},a\in\mathcal{A}$ are unique. Then, the following inequality
holds for each $\alpha\in[0,1)$:

$\operatorname{VaR}_{\alpha}\left[\max_{a\in\mathcal{A}}\tilde{x}_{a}\right]\;\leq\;\inf\left\\{\max_{a\in\mathcal{A}}\operatorname{VaR}_{1-\xi_{a}}\left[\tilde{x}_{a}\right]\mid\bm{\xi}\in\mathbb{R}^{k}_{+},\,\bm{1}^{\mathsf{T}}\bm{\xi}=1-\alpha\right\\}\,.$

We interpret the maximum of all $-\infty$ as $-\infty$.

###### Proof.

The result develops as

$\displaystyle\operatorname{VaR}_{\alpha}\left[\max_{a\in\mathcal{A}}\tilde{x}_{a}\right]$
$\displaystyle\overset{\text{(a)}}{=}\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\max_{a\in\mathcal{A}}\tilde{x}_{a}\geq
t\right]>1-\alpha\right\\}$
$\displaystyle\overset{\text{(b)}}{\leq}\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\max_{a\in\mathcal{A}}\tilde{x}_{a}\geq
t\right]\geq 1-\alpha\right\\}$
$\displaystyle\overset{\text{(c)}}{\leq}\sup\left\\{t\in\mathbb{R}\mid\sum_{a\in\mathcal{A}}\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq 1-\alpha\right\\}$
$\displaystyle\overset{\text{(d)}}{=}\inf\left\\{\sup\left\\{t\in\mathbb{R}\mid\sum_{a\in\mathcal{A}}\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\sum_{a\in\mathcal{A}}\xi_{a}\right\\}\mid\bm{\xi}\in\mathbb{R}_{+}^{k},\bm{1}^{\mathsf{T}}\bm{\xi}=1-\alpha\right\\}$
$\displaystyle\overset{\text{(e)}}{\leq}\inf\left\\{\max_{a\in\mathcal{A}}\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\xi_{a}\right\\}\mid\bm{\xi}\in\mathbb{R}_{+}^{k},\bm{1}^{\mathsf{T}}\bm{\xi}=1-\alpha\right\\}$
$\displaystyle\overset{\text{(f)}}{\leq}\inf\left\\{\max_{a\in\mathcal{A}}\operatorname{VaR}_{1-\xi_{a}}\left[\tilde{x}_{a}\right]\mid\bm{\xi}\in\mathbb{R}_{+}^{k},\bm{1}^{\mathsf{T}}\bm{\xi}=1-\alpha\right\\}.$

(a) is from the definition of VaR. (b) follows by relaxing the set by
replacing the strict inequality by a non-strict one. (c) follows by relaxing
the constraint further using the union bound. (d) follows from algebraic
manipulation because the objective is constant in the choice of $\bm{\xi}$.
(e) holds by relaxing the sum constraints and then representing the supremum
over a union of sets by a maximum of the suprema of the sets as

$\displaystyle\sup\left\\{t\in\mathbb{R}\mid\sum_{a\in\mathcal{A}}\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\sum_{a\in\mathcal{A}}\xi_{a}\right\\}$
$\displaystyle\leq\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\xi_{a},\,\exists a\in\mathcal{A}\right\\}$
$\displaystyle=\max_{a\in\mathcal{A}}\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\xi_{a}\right\\}\,.$

Finally, (f) follows from the definition of VaR and because then the quantiles
are unique [13]

$\operatorname{VaR}_{1-\xi_{a}}\left[\tilde{x}_{a}\right]=\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]\geq\xi_{a}\right\\}=\sup\left\\{t\in\mathbb{R}\mid\mathbb{P}\left[\tilde{x}_{a}\geq
t\right]>\xi_{a}\right\\}\,.$

The first equality is the definition of the upper quantile $q^{+}$ and the
second equality is the definition of the lower quantile $q^{-}$, which are
equal by the uniqueness assumption. ∎

We are now ready to prove Theorem 4.2.

###### Proof of Theorem 4.2.

The first inequality in (7) follows from Lemma 4.1 and Lemma B.1 by some
algebraic manipulation. The second inequality in (7) follows from upper-
bounding the VaR of a Gaussian random variable using (2) and the fact that
$\tilde{x}^{\pi}_{a}$ is a Gaussian random variable with mean
$\bm{\tilde{\mu}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})$ and variuance
$\|\bm{\Phi}(\bm{1}_{a}-\bm{\pi})\|_{\bm{\Sigma}}$.

The inequality
$z_{1-\delta\xi_{a}}\leq\sqrt{2\log\nicefrac{{1}}{{\delta\xi_{a}}}}$ holds
because for a standard normal random variable $\tilde{y}$, we have that

$z_{1-\delta\xi_{a}}=\operatorname{VaR}_{1-\delta\xi_{a}}\left[\tilde{y}\right]\overset{\text{(a)}}{\leq}\operatorname{EVaR}_{1-\delta\xi_{a}}\left[\tilde{y}\right]\overset{\text{(b)}}{=}\sqrt{2\log(1/\delta\xi_{a})}\,.$

(a) follows from Lemma A.1 and (b) is by (22). ∎

###  B.2 Proof of Theorem 4.3

This result follows from techniques that are standard in robust optimization
(e.g., [16, 33]) as well as bandit analysis. In fact, similar or perhaps
almost identical analysis has been used to analyze the regret of FlatOPO in
Hong et al. [19]. We provide an independent proof for the sake of
completeness.

The following two auxiliary lemmas are used to show that a robust optimization
over a credible region can be used to upper-bound the VaR of any random
variable. The first auxiliary lemma establishes a sufficient condition for a
robust optimization being an overestimate of VaR.

######  Lemma B.2.

Suppose that we are given an ambiguity set $\mathcal{P}\subseteq\mathcal{X}$,
a function $g\colon\mathcal{X}\to\mathbb{R}$, and a random variable
$\bm{\tilde{x}}:\Omega\to\mathcal{X}$. If
$\mathcal{P}\cap\mathcal{Z}\neq\emptyset$ for
$\mathcal{Z}=\big{\\{}\bm{x}\in\mathcal{X}\mid
g(\bm{x})\geq\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]\big{\\}}$,
then

$\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]\;\leq\;\sup_{\bm{x}\in\mathcal{P}}\;g(\bm{x})\,.$

###### Proof.

By the hopothesis, there exists some
$\bm{\hat{x}}\in\mathcal{P}\cap\mathcal{Z}$. Then, we have
$\sup_{\bm{x}\in\mathcal{P}}g(\bm{x})\;\geq\;g(\bm{\hat{x}})\;\geq\;\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]$
that concludes the proof, where the first inequality is by definition and the
second one is from the definition of the set $\mathcal{Z}$. ∎

The second auxiliary lemma shows that a credible region is sufficient to
upper-bound VaR using a robust optimization problem.

######  Lemma B.3.

Suppose that we are given an ambiguity set $\mathcal{P}\subseteq\mathcal{X}$,
a function $g\colon\mathcal{X}\to\mathbb{R}$, and a random variable
$\bm{\tilde{x}}:\Omega\to\mathcal{X}$. Then, we have

$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}}\right]\geq\alpha\qquad\Longrightarrow\qquad\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]\;\leq\;\sup_{\bm{x}\in\mathcal{P}}g(\bm{x})\,.$

###### Proof.

Our proof is by contradiction using Lemma B.2. We start by assuming that
$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}}\right]$. Define
$\mathcal{Z}=\big{\\{}\bm{x}\in\mathcal{X}\mid
g(\bm{x})\geq\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]\big{\\}}$
as in Lemma B.2. From Lemma B.2, we know that if
$\sup_{\bm{x}\in\mathcal{P}}g(\bm{x})\;\geq\;\operatorname{VaR}_{\alpha}\left[g(\bm{\tilde{x}})\right]$
is false, then we should have $\mathcal{P}\cap\mathcal{Z}=\emptyset$. By the
definition of VaR, we have that
$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{Z}}\right]>1-\alpha$.
Then, we get a contradiction with $\mathcal{P}\cap\mathcal{Z}=\emptyset$ as
follows

$1\geq\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}\cup\mathcal{Z}}\right]=\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}}\right]+\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{Z}}\right]>\alpha+1-\alpha>1\,.$

∎

The following lemma uses a standard technique for constructing a credible
region for a multivariate normal distribution [19, 16].

######  Lemma B.4.

Suppose that $\bm{\tilde{x}}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$ is a multi-
variate normal random variable with a mean $\bm{\mu}\in\mathbb{R}^{d}$ and a
covariance matrix $\bm{\Sigma}\in\mathbb{R}^{d\times d}$. The set
$\mathcal{P}\subseteq\mathbb{R}^{d}$, defined as

$\mathcal{P}=\left\\{\bm{x}\in\mathbb{R}^{d}\mid\|\bm{x}-\bm{\mu}\|_{\bm{\Sigma}^{-1}}^{2}\leq\chi_{d}^{2}(\alpha)\right\\},$

with $\chi_{d}^{2}(\alpha)$ being the $\alpha$-quantile of the $\chi^{2}_{d}$
distribution, satisfies that
$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}}\right]=\alpha\,.$

###### Proof.

One can readily verify that
$\bm{\Sigma}^{{-\frac{1}{2}}}(\bm{\tilde{x}}-\bm{\mu})\sim\mathcal{N}(\bm{0},\bm{I})$
is a standard multivariate normal distribution. The norm of this value is a
sum of i.i.d. standard normal variables, and thus, is distributed according to
the $\chi^{2}_{d}$ distribution with $d$ degrees of freedom:

$\left(\bm{\Sigma}^{{-\frac{1}{2}}}(\bm{\tilde{x}}-\bm{\mu})\right)^{\mathsf{T}}\left(\bm{\Sigma}^{{-\frac{1}{2}}}(\bm{\tilde{x}}-\bm{\mu})\right)=\|\bm{\tilde{x}}-\bm{\mu}\|_{\bm{\Sigma}^{-1}}^{2}\sim\chi^{2}_{d}\,.$

Therefore, by algebraic manipulation and the definition of a quantile, we
obtain that

$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{x}}\in\mathcal{P}}\right]=\mathbb{P}_{#1}\left[\setargs{\|\bm{\tilde{x}}-\bm{\mu}\|_{\bm{\Sigma}^{-1}}^{2}\leq\chi_{d}^{2}(\alpha)}\right]=\alpha\,.$

∎

Finally, the following lemma derives the optimal solution of the quadratic
optimization problem used in computing the worst case with respect to
$\mathcal{P}_{\delta}$ in (9).

######  Lemma B.5.

The identity

$\max_{\bm{p}\in\mathbb{R}^{d}}\left\\{\bm{x}^{\mathsf{T}}\bm{p}\mid\left\|\bm{p}-\bm{\hat{p}}\right\|_{\bm{C}}^{2}\leq
b,\,\bm{p}\in\mathbb{R}^{k}\right\\}\;=\;\bm{x}^{\mathsf{T}}\bm{\hat{p}}+\sqrt{b}\cdot\|\bm{x}\|_{\bm{C}^{-1}}\,$
(23)

holds for any given vectors $\bm{x},\bm{\hat{p}}\in\mathbb{R}^{d}$ and a
matrix $\bm{C}\in\mathbb{R}^{d\times d}$ that is positive definite
$\bm{C}\succ\bm{0}$.

###### Proof.

From the convexity of the optimization problem (23), we can construct the
optimizer $\bm{p}^{\star}$ using KKT conditions as

$\bm{p}^{\star}=\bm{\hat{p}}+\sqrt{b}\cdot\|\bm{x}\|_{\bm{C}^{-1}}\cdot\bm{C}^{-1}\bm{x}\,.$

The result then follows by substituting $\bm{p}^{\star}$ into the maximization
problem in the lemma. ∎

We are now ready to prove the main theorem.

###### Proof of Theorem 4.3.

Using Lemma B.4 and the definition of $\mathcal{P}_{\delta}$ in (9), we can
see that $\mathcal{P}_{\delta}$ is indeed a credible region:

$\mathbb{P}_{#1}\left[\setargs{\bm{\tilde{\theta}}\in\mathcal{P}_{\delta}}\right]=1-\delta\,.$

Then, Lemma B.3 gives us the first inequality in (10):

$\mathfrak{R}_{\delta}(\bm{\pi})\leq\max_{\bm{\theta}\in\mathcal{P}_{\delta}}\max_{a\in\mathcal{A}}\left(r(a;\bm{\theta})-r(\bm{\pi};\bm{\theta})\right)\,.$

The second inequality in (10) is a consequence of Lemma B.5 with
$\bm{x}=\bm{\Phi}(\bm{1}_{a}-\bm{\pi})$, $\bm{\hat{p}}=\bm{\mu}$,
$\bm{p}=\bm{\theta}$, $\bm{C}=\bm{\Sigma}^{-1}$, and
$b=\sqrt{\chi^{2}(1-\delta)}$.

Finally, the inequality
$\sqrt{\chi^{2}_{d}(1-\delta)}\leq\sqrt{5d\log(1/\delta)}$ follows from Lemma
1 in Laurent and Massart [27] as in the proof of Lemma 3 in Hong et al. [19].
∎

###  B.3 Proof of Corollary 4.4

The corollary is an immediate consequence of Theorems 4.2 and 4.3 and the
construction of Algorithm 1. By construction, $\bm{\pi}^{0}$ is the solution
to

$\bm{\pi}^{0}\in\arg\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\nu_{a}^{0}\,,$

where $\nu_{a}^{0}$ is defined in Algorithm 1. Therefore, using Theorems 4.2
and 4.3 to upper-bound $\nu_{a}$, we obtain

$\mathfrak{R}_{\delta}(\bm{\pi}^{0})\leq\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\min\left\\{\sqrt{2\log(k/\delta)},\sqrt{5d\log(1/\delta)}\right\\}\,.$

This proves the corollary when $i^{\star}=0$ in Algorithm 1. Then, using
Theorem 4.2 with general $\bm{\xi}$, we observe that the algorithm selects
$i^{\star}>0$ only when
$\mathfrak{R}_{\delta}(\bm{\pi}^{i^{\star}})\leq\rho^{i^{\star}}\leq\rho^{0}$,
which means that the corollary also holds. ∎

##  Appendix C Proofs of Section 5

###### Proof of Theorem 5.2.

Let $\bm{\bar{\pi}}$ be a policy that minimizes the linear component of the
regret:

$\bm{\bar{\pi}}\in\arg\min_{\bm{\pi}\in\Delta_{k}}\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})\,.$

Note that the minimum above is upper-bounded by 0. Next we use Corollary 4.4
to bound the regret:

$\displaystyle\mathfrak{R}_{\delta}(\bm{\hat{\pi}})$
$\displaystyle\leq\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}_{n}}\cdot\min\left\\{\sqrt{2\log(\nicefrac{{k}}{{\delta}})},\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\right\\}$
$\displaystyle\leq\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})}_{\bm{\Sigma}_{n}}\cdot\min\left\\{\sqrt{2\log(\nicefrac{{k}}{{\delta}})},\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\right\\}$
$\displaystyle\leq\max_{a\in\mathcal{A}}\,\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})}_{\bm{\Sigma}_{n}}\cdot\min\left\\{\sqrt{2\log(\nicefrac{{k}}{{\delta}})},\sqrt{5d\log(\nicefrac{{1}}{{\delta}})}\right\\}.$

Now, we bound the term
$\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})}_{\bm{\Sigma}_{n}}$. Recall that
$\|\bm{\bar{\pi}}\|_{2}\leq\|\bm{\bar{\pi}}\|_{1}\leq 1$, since
$\bm{\bar{\pi}}\in\Delta_{k}$. Then, for each $a\in\mathcal{A}$, we have by
algebraic manipulation that

$\displaystyle\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})}_{\bm{\Sigma}_{n}}^{2}$
$\displaystyle\;=\;(\bm{1}_{a}-\bm{\bar{\pi}})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}(\bm{1}_{a}-\bm{\bar{\pi}})$
$\displaystyle\;=\;\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{1}_{a}+\bm{\bar{\pi}}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\bar{\pi}}-2\cdot\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\bar{\pi}}$
$\displaystyle\;\overset{\text{(a)}}{\leq}\;4\max_{a^{\prime}\in\mathcal{A}}\bm{1}_{a^{\prime}}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{1}_{a^{\prime}}\;=\;4\max_{a^{\prime}\in\mathcal{A}}\bm{\phi}_{a^{\prime}}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a^{\prime}}\,.$

(a) holds by the Cauchy-Schwartz inequality because

$-\bm{1}_{a}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\bar{\pi}}\;\leq\;\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{1}_{a}\|_{2}\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\bar{\pi}}\|_{2}\;\leq\;\max_{a^{\prime}\in\mathcal{A}}\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{1}_{a^{\prime}}\|_{2}^{2}\,.$

The last inequality in the above equation is satisfied because
$\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\bar{\pi}}\|_{2}\leq\sum_{a^{\prime}\in\mathcal{A}}\bar{\pi}_{a^{\prime}}\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{1}_{a^{\prime}}\|_{2}\leq\max_{a^{\prime}\in\mathcal{A}}\|\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{1}_{a^{\prime}}\|_{2}$,
which in turn follows by Jensen’s inequality from the convexity of the
$\ell_{2}$-norm and the fact that $\bm{\bar{\pi}}\in\Delta_{k}$. The term
$\bm{\bar{\pi}}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\Phi}\bm{\bar{\pi}}$
is upper bounded by an analogous argument.

Now 5.1 implies the following for each $a\in\mathcal{A}$:

$\displaystyle\bm{G}_{n}$ $\displaystyle\quad\succeq\quad\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}}$
$\displaystyle\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\bm{G}_{n}$
$\displaystyle\quad\succeq\quad\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}}\quad\succ\quad\bm{0}$
$\displaystyle(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\bm{G}_{n})^{-1}$
$\displaystyle\quad\preceq\quad(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}})^{-1}$
$\displaystyle\bm{\phi}_{a}^{\mathsf{T}}(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\bm{G}_{n})^{-1}\bm{\phi}_{a}$
$\displaystyle\quad\leq\quad\bm{\phi}_{a}^{\mathsf{T}}(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}})^{-1}\bm{\phi}_{a}$
$\displaystyle\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a}$
$\displaystyle\quad\leq\quad\bm{\phi}_{a}^{\mathsf{T}}(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}})^{-1}\bm{\phi}_{a}.$ (24)

The second line holds because we assumed $\bm{\Sigma}_{0}\succ 0$, and thus,
$\bm{\Sigma}_{0}^{-1}\succ 0$, and adding a positive-definite matrix preserves
definiteness. The third line holds from the definiteness in the second line
and Horn and Johnson [20, corollary 7.7.4(a)]. Finally, the fourth line holds
from the definition of positive semi-definiteness.

We continue by applying the Woodbury matrix identity to (24), which will give
us the following inequality for each $a\in\mathcal{A}$:

$\displaystyle\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{n}\bm{\phi}_{a}$
$\displaystyle\quad\leq\quad\bm{\phi}_{a}^{\mathsf{T}}(\bm{\Sigma}_{0}^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n\cdot\bm{\phi}_{a}\bm{\phi}_{a}^{\mathsf{T}})^{-1}\bm{\phi}_{a}\quad=\quad\frac{1}{\bm{\phi}_{a}^{\mathsf{T}}\bm{\Sigma}_{0}^{-1}\bm{\phi}_{a}+\bar{\sigma}^{-2}\cdot\gamma
n}$
$\displaystyle\quad\leq\quad\frac{1}{\lambda_{\min}(\bm{\Sigma}_{0}^{-1})+\bar{\sigma}^{-2}\cdot\gamma
n}\quad\leq\quad\frac{1}{\lambda_{\max}(\bm{\Sigma}_{0})^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n}\,,$

where $\lambda_{\min}$ and $\lambda_{\max}$ are the minimum and maximum
eigenvalues. Substituting the inequality above proves the theorem. ∎

We can tighten the regret bound when the mean rewards of all actions are the
same. To streamline the argument, we assume that $\bm{\mu}_{n}=\bm{0}$ without
loss of generality.

######  Corollary C.1.

Suppose that $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{0},\bm{\Sigma}_{n})$
with $\bm{\Sigma}_{n}\in\mathbb{R}^{d\times d}$ estimated from (13) with a
logging dataset $D$ that satisfies 5.1. Then, the regret of the policy
$\bm{\hat{\pi}}$ returned by Algorithm 1 satisfies

$\mathfrak{R}_{\delta}(\bm{\hat{\pi}})\quad\leq\quad
2\left(1-\max_{a^{\prime}\in\mathcal{A}}\hat{\pi}_{a^{\prime}}\right)\sqrt{\frac{\min\left\\{2\log(\nicefrac{{k}}{{\delta}}),5d\log\nicefrac{{1}}{{\delta}}\right\\}}{\lambda_{\max}(\bm{\Sigma}_{0})^{-1}+\bar{\sigma}^{-2}\cdot\gamma
n}}.$

Moreover, there exists $\bm{\hat{\pi}}$ such that
$\max_{a^{\prime}\in\mathcal{A}}\hat{\pi}_{a^{\prime}}\geq\nicefrac{{1}}{{d+1}}$.

###### Proof.

Let $\bm{\pi}^{0}$ be the solution in the first iteration of Algorithm 1 and
recall that the subsequent iterations can only improve the regret as we argue
in the proof of Corollary 4.4. Given the posterior distribution of
$\bm{\tilde{\theta}}_{D}$, the policy $\bm{\pi}^{0}$ is chosen as

$\displaystyle\bm{\pi}^{0}$
$\displaystyle\in\arg\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\;\bm{0}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\nu_{a}^{0}$
$\displaystyle=\arg\min_{\bm{\pi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\;\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\,.$

The square of this minimization problem can be formulated as a convex
quadratic program

$\min_{t\in\mathbb{R},\;\bm{\pi}\in\Delta_{k}}\left\\{t\mid
t\geq\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a}-\bm{\Sigma}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\pi}}_{2}^{2}\;,\,\forall
a\in\mathcal{A}\right\\}\,.$ (25)

Because $\bm{\Sigma}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\pi}\in\mathbb{R}^{d}$
and is a convex combination of points in $\mathbb{R}^{d}$, there exists an
optimal $\bm{\pi}^{0}$ such that
$l=|\left\\{a\in\mathcal{A}\mid\pi^{0}_{a}>0\right\\}|\leq d+1$ [37]. Then,
let $\hat{a}\in\arg\max_{a^{\prime}\in\mathcal{A}}\pi^{0}_{a^{\prime}}$. We
have that $\pi^{0}_{\hat{a}}\geq\frac{1}{l}$ because $l$ actions are positive,
and the constraint
$t\geq\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a}-\bm{\Sigma}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\pi}}_{2}^{2}$
is active (holds with equality). If the constraint were not active, this would
be a contradiction with the optimality of $\bm{\pi}^{0}$ because decreasing
$\pi_{\hat{a}}^{0}$ would reduce the objective. Then, using the inequalities
above and the triangle inequality, we get that the optimal $t^{\star}$ in (25)
satisfies

$\displaystyle\sqrt{t^{\star}}$
$\displaystyle=\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{\hat{a}}-\bm{\Sigma}^{\nicefrac{{1}}{{2}}}\bm{\Phi}\bm{\pi}^{0}}_{2}=\left(1-\max_{a^{\prime\prime}\in\mathcal{A}}\pi^{0}_{a^{\prime\prime}}\right)\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{\hat{a}}-\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a^{\prime}}}_{2}$
$\displaystyle\leq\left(1-\max_{a^{\prime\prime}\in\mathcal{A}}\pi^{0}_{a^{\prime\prime}}\right)\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{\hat{a}}-\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a^{\prime}}}_{2}\leq
2\left(1-\max_{a^{\prime\prime}\in\mathcal{A}}\pi^{0}_{a^{\prime\prime}}\right)\norm{\bm{\Sigma}_{n}^{\nicefrac{{1}}{{2}}}\bm{\phi}_{a^{\prime}}}_{2}.$

The remainder of the proof follows by the same steps as the proof of Theorem
5.2. The lower bound on
$\max_{a^{\prime}\in\mathcal{A}}\hat{\pi}_{a^{\prime}}$ holds from the
existence of $\pi^{0}$ with at most $d+1$ positive elements, as discussed
above. ∎

##  Appendix D Sub-Gaussian Posterior

We discuss here how our results can extend to $\bm{\tilde{\theta}}_{D}$ with
sub-Gaussian distributions. The modifications necessary are quite minor. The
key to the approach is to generalize Theorem 4.2 to a sub-Gaussian
distribution as the following theorem states.

######  Theorem D.1.

Suppose that $\bm{\tilde{\theta}}_{D}$ is a random variable with an atomless
distribution that is sub-Gaussian with mean $\bm{\mu}$ and covariance factor
$\bm{\Sigma}$. Then the regret for each $\bm{\pi}\in\Delta_{k}$ satisfies that

$\displaystyle\mathfrak{R}_{\delta}(\bm{\pi})$
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{VaR}_{1-\delta\xi_{a}}\left[r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right]$
(26)
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\sqrt{2\log(\nicefrac{{1}}{{\delta\xi_{a}}})}.$

###### Proof.

The first inequality in (26) holds by Theorem 4.2 since this inequality does
not require that the posterior is normal. That is, we have that

$\displaystyle\mathfrak{R}_{\delta}(\bm{\pi})$
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{VaR}_{1-\delta\xi_{a}}\left[r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right]$
$\displaystyle\;=\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{VaR}_{1-\delta\xi_{a}}\left[(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\right]$
$\displaystyle\;\leq\;\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{EVaR}_{1-\delta\xi_{a}}\left[(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\right]\,.$

The last inequality follows from Lemma A.1. For each $a\in\mathcal{A}$, the
definition of a multi-variate sub-Gaussian random variable in (20) with
$\bm{w}^{\mathsf{T}}=(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}$
implies that that
$(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}$
is sub-Gaussian with mean
$\mu=(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\mu}$ and a
variance factor
$\sigma^{2}=(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})$.
Therefore, from Lemma A.2 we have

$\min_{\bm{\xi}\in\Delta_{k}}\max_{a\in\mathcal{A}}\,\operatorname{EVaR}_{1-\delta\xi_{a}}\left[(\bm{1}_{a}-\bm{\pi})^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\right]\leq\bm{\mu}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi})+\norm{\bm{\Phi}(\bm{1}_{a}-\bm{\pi})}_{\bm{\Sigma}}\cdot\sqrt{2\log(\nicefrac{{1}}{{\delta\xi_{a}}})}\;,$

which proves the result. ∎

Theorem 4.3 can also be extended to the sub-Gaussian setting, but seems to
require an additional assumption that
$\|\bm{\tilde{\theta}}-\bm{\mu}\|^{2}_{\bm{\Sigma}^{-1}}$ is a sub-gamma
random variable, and we leave it for future work.

Armed with Theorem D.1, we can adapt Algorithm 1 to the sub-Gaussian setting
simply by setting $\nu^{0}_{a}=\sqrt{2\log(\nicefrac{{k}}{{\delta}})}$. Note
that (12) already uses the correct inequality for a sub-Gaussian distribution.

##  Appendix E Scenario-based Algorithms

The scenario-based algorithms for chance-constrained optimization problems
typically work by approximating the posterior distribution over
$\bm{\tilde{\theta}}_{D}$ using a discrete distribution.

We are aware of three general scenario-based approaches to minimizing regret
in (5). The first one is to construct a _discrete_ random variable
$\bm{\tilde{q}}$ that approximate $\bm{\tilde{\theta}}$. The random variable
$\bm{\tilde{q}}$ is typically constructed by sampling from
$\bm{\tilde{\theta}}_{D}$. The algorithm then computes a _deterministic_
policy by solving the optimization problem:

$\arg\min_{\hat{a}\in\mathcal{A}}\operatorname{VaR}_{1-\delta}\left[\max_{a\in\mathcal{A}}r(a;\bm{\tilde{q}})-r(\hat{a};\bm{\tilde{q}})\right]\,.$

This optimization problem can be solved relatively easily by enumerating all
actions and computing the VaR of the discrete random variable. The important
question of the number of samples needed to obtain a solution with a good
confidence has been studied extensively; see for example [32, 31] and
references therein. Computing a randomized policy using this technique is
challenging because it requires solving a non-convex optimization problem,
such as a mixed integer linear program.

The second approach computes a _randomized_ policy by solving

$\arg\min_{\bm{\pi}\in\mathcal{A}}\max\left[\max_{a\in\mathcal{A}}r(a;\bm{\tilde{q}})-r(\bm{\pi};\bm{\tilde{q}})\right]\,,$

where $\bm{\tilde{q}}$ is the same discretized distribution approximating
$\bm{\tilde{\theta}}_{D}$. The advantage of this method is that it can compute
a randomized policy using a tractable optimization problem. However, one needs
to be careful about how many samples are used to construct $\bm{\tilde{q}}$.
Because this approach approximates VaR by the worst-case, sampling too many
points from $\bm{\tilde{\theta}}_{D}$ will lead to an overly pessimistic
solution [8].

The third approach computes a _randomized_ policy by approximating the VaR by
a Conditional-Value-at-Risk (CVaR) as

$\arg\min_{\bm{\pi}\in\mathcal{A}}\operatorname{CVaR}_{1-\delta}\left[\max_{a\in\mathcal{A}}r(a;\bm{\tilde{q}})-r(\bm{\pi};\bm{\tilde{q}})\right]\,.$

CVaR is known to be an upper-bound on VaR [38]. The advantage of this approach
is that it is tractable and increasing the number of samples will not make the
solution overly conservative as the second approach. The optimization problem
can be formulated as follows. Let $\bm{q}_{1},\dots,\bm{q}_{J}$ be values of
$\bm{\tilde{q}}$ with probabilities $\bm{p}=p_{1},\dots,p_{J}$. Then the
linear program that computes optimal CVaR randomized policy is

$\begin{array}[]{>{\displaystyle}c>{\displaystyle}l>{\displaystyle}l>{\displaystyle}l}\operatorname*{minimize}_{\bm{\pi}\in\mathbb{R}^{A},\;z\in\mathbb{R},\;\bm{b}\in\mathbb{R}^{J}}&z+\frac{1}{\delta}\cdot\bm{p}^{\mathsf{T}}\bm{b}\\\\[4.30554pt]
\operatorname{subject\;to}&b_{j}\geq\left(\max_{a\in\mathcal{A}}\bm{\phi}_{a}^{\mathsf{T}}\bm{q}_{j}-\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{q}_{j}^{\mathsf{T}}\right)-z,\qquad\forall
j=1,\dots,J,\\\\[4.30554pt]
\hfil&\bm{1}^{\mathsf{T}}\bm{\pi}=1,\quad\bm{\pi}\geq\bm{0},\quad\bm{b}\geq\bm{0}.\end{array}$

This formulation follows directly from the definition of CVaR [38] and more
details can be found in Brown et al. [7], for example.

##  Appendix F Other Objectives

We now briefly discuss two other related objectives as alternatives to
minimizing the high-confidence Bayesian regret, defined in (4) and (5). These
objectives may be preferable in some settings because they can be solved
optimally using simple and tractable techniques.

###  F.1 Expected Bayes Regret

The first objective we discuss is expected Bayes regret, which is obtained by
simply replacing the VaR by expectation in (5). In this case, the goal of the
agent is to minimizes the expected regret, defined as

$\min_{\bm{\pi}\in\Delta_{k}}\mathbb{E}_{#1}\left[\setargs{\max_{a\in\mathcal{A}}\;r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})}\right]\,.$

Using the linearity property of the expectation operator and the reward
function $r$, we have

$\arg\min_{\bm{\pi}\in\Delta_{k}}\mathbb{E}_{#1}\left[\setargs{\max_{a\in\mathcal{A}}\;r(a;\bm{\tilde{\theta}}_{D})-r(\bm{\pi};\bm{\tilde{\theta}}_{D})}\right]=\arg\max_{\bm{\pi}\in\Delta_{k}}\mathbb{E}_{#1}\left[\setargs{r(\bm{\pi};\bm{\tilde{\theta}}_{D})}\right]=\arg\max_{\bm{\pi}\in\Delta_{k}}r\left(\bm{\pi};\mathbb{E}_{#1}\left[\setargs{\bm{\tilde{\theta}}_{D}}\right]\right).$

This means it is sufficient to maximize the return for the mean posterior
parameter value. In most case, such as when the posterior over
$\bm{\tilde{\theta}}_{D}$ is normal, this is an easy optimization problem to
solve optimally.

###  F.2 High-confidence Return

The second objective we discuss is high-confidence return, which is obtained
by simply replacing the regret with return in (5). In this case, the goal of
the agent is to minimizes the VaR of the return random variable as

$\min_{\bm{\pi}\in\Delta_{k}}\operatorname{VaR}_{1-\delta}\left[-r(\bm{\pi};\bm{\tilde{\theta}}_{D})\right]=\min_{\bm{\pi}\in\Delta_{k}}\operatorname{VaR}_{1-\delta}\left[-\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D})\right]\,.$
(27)

One may think of this objective as minimizing the regret with respect to $0$.
The reward inside is negated because we use VaR that measures costs rather
that rewards. Note that
$-\operatorname{VaR}_{1-\delta}\left[-\tilde{x}\right]\approx\operatorname{VaR}_{\delta}\left[\tilde{x}\right]$
with an equality for atomless (continuous) distributions.

When $\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$, the
optimization in (27) can be solved _optimally_ using a LCB-style algorithm.
Then, using the properties of linear transformation of normal distributions,
for each $\bm{\pi}\in\Delta_{k}$, we obtain

$\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\tilde{\theta}}_{D}\sim\mathcal{N}(\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\mu},\,\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}\bm{\Phi}\bm{\pi})\,.$

Combining the objective in (27) with (2), we end up solving

$\max_{\bm{\pi}\in\Delta_{k}}\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\mu}-\sqrt{\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}\bm{\Phi}\bm{\pi}}\cdot
z_{1-\delta}\,.$ (28)

Recall that $z_{1-\delta}$ is the $1-\delta$-th quantile of the standard
normal distribution. We can reformulate (28) as the following SOCP
optimization problem (for $\delta\leq\nicefrac{{1}}{{2}}$)

$\begin{array}[]{>{\displaystyle}c>{\displaystyle}l>{\displaystyle}l>{\displaystyle}l}\operatorname*{maximize}_{\bm{\pi}\in\mathbb{R}^{k},\;s\in\mathbb{R}}&\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\mu}-z_{1-\delta}\cdot
s\\\\[4.30554pt]
\operatorname{subject\;to}&s^{2}\leq\bm{\pi}^{\mathsf{T}}\bm{\Phi}^{\mathsf{T}}\bm{\Sigma}\bm{\Phi}\bm{\pi},\\\\[4.30554pt]
\hfil&\bm{1}^{\mathsf{T}}\bm{\pi}=1,\quad\bm{\pi}\geq\bm{0}\,.\end{array}$

When restricted to deterministic policies, the optimization in (28) reduces to
a plain deterministic LCB algorithm. The FlatOPO algorithm can, in fact, be
seen as an approximation of (28) in which $z_{1-\delta}$ is replaced by its
upper bound.

##  Appendix G Additional Experimental Details

Figure 4:  Bayesian regret with $k=d=5$ (left), $k=d=50$ (middle and right).
The prior mean is $\bm{\mu}_{0}=\bm{0}$ (left and middle) and
$(\bm{\mu}_{0})_{a}=\sqrt{a}\;$ for $a=1,\dots 50$ _(right)_.

Figure 5:  Bayesian regret with $d=4$ and $k=10$ (left), $k=50$ (middle), and
$k=100$ (right).

Figure 6: Regret bounds in Theorem 4.2 for different choices of $\bm{\xi}$ as
a function of $k$. The posterior distribution of $\bm{\tilde{x}}$ is normal
with $\bm{\mu}=\bm{0},\,\bm{\Sigma}=\bm{I}$ _(left)_ ,
$\bm{\mu}=\bm{0},\,\Sigma_{aa}=a^{2}/k$ _(middle)_ , and
$\mu_{a}=a/k,\,\Sigma_{aa}=a^{2}/k$ _(right)_ with $a=1,\dots,k$.

In this section, we provide some additional experimental results. First,
Figures 4 and 5 report the same results as Figures 2 and 3 but also report the
95% confidence interval for the average regret over the 100 runs. Second, we
report the effect of the tightening step on the quality of the bounds in
Figure 6 compared to a scenario-based estimation. In this simplified example,
we fix some policy $\bm{\pi}$ and _assume_ the particular parameters of the
distribution of
$\tilde{x}_{a}=\bm{\tilde{\theta}}_{D}^{\mathsf{T}}\bm{\Phi}(\bm{1}_{a}-\bm{\pi}),a\in\mathcal{A}$,
which is normal by Lemma 4.1. The results in the figure show that when the
distribution $\bm{\tilde{x}}$ is close to i.i.d. the tightening step does not
improve the bound. This is expected since the optimal $\bm{\xi}$ in (12) is
nearly uniform. However, when the means or variances of the $\tilde{x}_{a}$
vary across actions $a\in\mathcal{A}$, then the tightening step can
significantly reduce the error bound.