The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
82,642 characters
Risk and optimal policies in bandit experiments
\title{Risk and optimal policies in bandit experiments}
\author{Karun Adusumilli$^\dagger$ }
\begin{abstract}
We provide a decision theoretic analysis of bandit experiments under
local asymptotics. Working within the framework of diffusion processes,
we define suitable notions of asymptotic Bayes and minimax risk for
these experiments. For normally distributed rewards, the minimal Bayes
risk can be characterized as the solution to a second-order partial
differential equation (PDE). Using a limit of experiments approach,
we show that this PDE characterization also holds asymptotically under
both parametric and non-parametric distributions of the rewards. The
approach further describes the state variables it is asymptotically
sufficient to restrict attention to, and thereby suggests a practical
strategy for dimension reduction. The PDEs characterizing minimal
Bayes risk can be solved efficiently using sparse matrix routines
or Monte-Carlo methods. We derive the optimal Bayes and minimax policies
from their numerical solutions. These optimal policies substantially
dominate existing methods such as Thompson sampling; the risk of the
latter is often twice as high.
\end{abstract}
\thanks{\textit{This version}: \today{}\\
\thispagestyle{empty}I would like to thank two anonymous referees
for valuable suggestions that substantially improved the paper. Thanks
also to Xiaohong Chen, David Childers, Keisuke Hirano, Hiroaki Kaido,
Jonas Lieber, Ulrich M{\"u}ller, Frank Schorfheide, Stefan Wager
and seminar participants at multiple universities and conferences
for helpful comments.\\
$^\dagger$Department of Economics, University of Pennsylvania}
\maketitle
\section{Introduction \label{sec:Introduction}}
The multi-armed bandit problem describes an agent who seeks to maximize
the welfare, i.e., the cumulative returns (aka rewards), generated
by sequentially selecting among various actions (aka arms), the effects
of which are initially unknown.\textcolor{blue}{{} }Compared to static
experiments, adaptive experiments such as bandit algorithms enable
fast learning and implementation of optimal actions, while minimizing
welfare-lowering experimentation. Due to this promise of large welfare
gains, they have been extensively studied in recent years and applied
in areas such as online advertising \citep{russo2017tutorial}, dynamic
pricing \citep{ferreira2018online}, public health \citep{athey2021shared}
and economics \citep{kasy2019adaptive,caria2020adaptive}.
The bandit problem can be formulated as a dynamic programming one,
but solving this exactly is typically infeasible. Instead, heuristic
solutions are commonly used, such as Thompson sampling (TS; see \citealp{russo2017tutorial}
and references therein) and Upper Confidence Bound (UCB; \citealp{lai1985asymptotically})
algorithms. There is by now a large theoretical literature on the
regret properties of stochastic bandit algorithms.\footnote{There is also an important, and parallel, literature on adversarial
bandits that this paper does not contribute to, see, e.g., \citealp{hazan2016introduction}.} Here, regret is the difference in welfare from pulling the best arm
and the agent's actual welfare. Existing results on lower bounds for
regret come in two forms. The first set of results, `instance dependent
bounds' (\citealp{lai1985asymptotically}), provide lower bounds on
rates of regret for `consistent' algorithms under a given set of reward
distributions for each arm. These results are of a large deviations
flavor. The second set of results specify the minimax rates of regret,
when nature is allowed to adversarially change the reward distributions
depending on $n$, the number of periods of experimentation allowed.
This rate is of the order $n^{-1/2}$ \citep[Ch.\ 9]{lattimore2020bandit}.
Despite these advances, a number of questions still remain. Many algorithms,
including TS and UCB, attain the rate bounds described above, but
existing results are silent on selecting between them. Decision theory
under ambiguity suggests two common measures, Bayes and minimax risk,
for ranking algorithms. The importance of these measures is well recognized
in the literature, see \citet[Chs.\ 13, 35]{lattimore2020bandit},
but their characterization, and the subsequent derivation of optimal
algorithms, remain open questions (in fact, a common, but incorrect,
view is that these are intractable). We seek to answer these questions.
The first contribution of this paper is to define notions of asymptotic
Bayes and minimax risk for bandit experiments under diffusion asymptotics
(\citealp{wager2021diffusion,fan2021diffusion}). These asymptotics
consider the regime where the difference in expected rewards between
the arms scales at the minimax, $n^{-1/2}$, rate. This defines the
hardest instance of the bandit problem: if the reward gap scales at
a faster rate, identifying the optimal arm is straightforward, whereas
if it scales at a slower rate, there is too little difference between
the arms, so the asymptotic risk is trivially 0 in either case. The
$n^{-1/2}$ scaling thus provides a good approximation to the finite
sample properties of bandit algorithms. The same scaling occurs in
the analysis of treatment assignment rules by \citet{hirano2009asymptotics}.
\citet{wager2021diffusion} and \citet{fan2021diffusion} study the
properties of TS under diffusion asymptotics, but do not address the
question of optimal policies under Bayes and minimax risk, as we do
here. We define Bayes risk using `non-negligible' priors, i.e., priors
applied on the mean rewards \textit{after} scaling them by the minimax,
$n^{-1/2}$, rate (see Section \ref{subsec:Bayes-risk}). This a major
departure from the existing literature that, starting from \citet{lai1987adaptive},
employs a fixed prior, but which leads to a trivial Bayes risk of
$0$ under the $n^{-1/2}$ scaling. This literature instead analyzes
Bayes risk using large-deviation methods without scaling the rewards,
but as it is based on analysis of tail probabilities and not distributional
approximations, the results are not sharp enough to select between
various policies, e.g., both TS and UCB attain the large-deviation
lower bound. By contrast, we characterize the minimal Bayes risk under
the $n^{-1/2}$ scaling as the solution to a $2^{\textrm{nd}}$-order
partial differential equation (PDE).
We first demonstrate this characterization for Gaussian rewards, using
the theory of viscosity solutions to PDEs \citep{crandall1992user}.
The PDE machinery is indispensable because existing results (\citealp{wager2021diffusion,fan2021diffusion})
only apply to continuous policies, whereas the optimal Bayes policy
is generically deterministic, and hence discontinuous. Next, using
a limit of experiments approach, we show that the same PDE characterization
also holds asymptotically under both parametric and non-parametric
distributions of the rewards. Thus, any bandit problem can be asymptotically
reduced to one with Gaussian rewards. As part of this reduction, we
find that it is sufficient to restrict attention to just two state
variables per arm, apart from time: these are the number of times
the arm has been pulled in the past, and either the score process
(for parametric models) or the cumulative rewards from pulling the
arm (for nonparametric models). This reduction in dimension is perhaps
the main practical insight of this paper since the state space otherwise
grows linearly with $n$ (see Section \ref{subsec:Heuristics}).
We demonstrate the equivalence of experiments by extending the posterior
approximation method of \citet[Section 6.4]{le2000asymptotics} to
sequential experiments. The proof makes use of novel arguments involving
uniform approximation of log-likelihoods and posteriors in sequential
settings. It also differs from the standard approach based on asymptotic
representations; the latter is difficult to implement under diffusion
asymptotics as it requires the construction of couplings between continuous
time processes. The techniques introduced here are thus of independent
interest for analyzing other types of sequential experiments.
The PDE characterizing minimal Bayes risk is essentially a limit case
of the dynamic programming problem (DP) associated with the bandit
experiment. While it is infeasible to solve the DP problem directly,
we present ways to efficiently solve the PDE using finite-difference
and Monte-Carlo methods. This enables us to identify the Bayes optimal
policies. Compared to the latter, we find TS to be provably sub-optimal
as it over-explores; empirical illustrations drawn from real-world
examples find its Bayes risk to be twice as high in some cases. Conversely,
under independent Gaussian priors, the form of the optimal policy
is broadly similar to UCB (for one-armed bandits, this even holds
under any prior). In such cases, we show that MOSS (Minimax Optimal
policy in Stochastic Setting), a minimax-rate optimal version of UCB,
can effectively mimic the optimal policy after optimally tuning it
to the given prior. This is borne out by our empirical illustrations
and we thus recommend it over TS. Incidentally, such a tuned version
of MOSS, while natural, does not appear to have been considered before;
in fact, the standard implementation of MOSS performs even worse than
TS. It should be noted, however, that the similarity between the optimal
policy and UCB/MOSS fails for correlated and non-Gaussian priors.
As an alternative to Bayes risk, we can use minimax risk. This is
simply Bayes risk under a least-favorable prior, and we numerically
compute both this prior and the minimax optimal policy. Intriguingly,
we find that optimally tuned MOSS (as proposed here) is close to minimax
optimal for one-armed bandits, even as an optimally tuned TS performs
much worse. This highlights the usefulness of our theory since it
would not have been possible to know the above without computing the
minimax lower bound; existing results give no reason to favor MOSS
over TS.
Our framework easily accommodates various generalizations and modifications
to the bandit problem such as time discounting and best arm identification
(\citealp{russo2016simple}; \citealp{kasy2019adaptive}). The discounted
bandit problem has a rich history in economic applications, ranging
from market pricing \citep{rothschild1974two} to decision making
in labor markets \citep{mortensen1986job}. For discounted problems,
the optimal Bayes policy can be characterized using Gittins indices
(\citealp{gittins1979bandit}). However, except in simple instances,
e.g., discrete state spaces, computing the Gittins index is difficult
(see, \citealp[Section 35.5]{lattimore2020bandit}). Also, it does
not apply beyond the discounted setting; the optimal Bayes policy
in finite horizon settings is not an index policy (\citealp[Chapter 6]{berry1985bandit}).
Here, we take a different route and characterize the optimal Bayes
policy using PDEs.
\section{Diffusion asymptotics and statistical risk\label{sec:Diffusion-asymptotics-and}}
In this section, we provide a heuristic derivation of the PDE characterizing
minimal Bayes risk in the Multi-Armed Bandit (MAB) problem.
In the MAB problem, there are $K$ arms, and at each period $j$,
a decision maker (DM) chooses which arm $k\in\{0,\dots,K-1\}$ to
pull. Each pull generates a reward with an unknown mean $\mu_{k}$
that is specific to the arm. Suppose the experiment concludes after
$n$ periods, where $n$ is pre-specified. Knowledge of $n$ is reasonable
if it is the population size; indeed, the bandit setting blurs any
distinction between sample and population. In other cases, it might
be more reasonable to assume the DM employs discounting and allows
the experiment to continue indefinitely. The decision theoretic analysis
employed here requires modeling all aspects of decision making including
when to stop or how to discount, but our results are otherwise very
broadly applicable. We focus on the known $n$ case to avoid duplication
of effort, but see Appendix \ref{subsec:Discounting} for discounted
bandits. When $n$ is known, the number of periods that have elapsed
is a state variable, and after dividing by $n$ will be termed `time'.
Thus, time $t$ proceeds from 0 and 1, and is incremented by $1/n$
between successive periods.
Let $A_{j}$ denote the action in period $j$, where $A_{j}=k$ if
arm $k$ is pulled. Suppose each time an arm $k$ is pulled, a reward,
$Y^{(k)}$, is drawn from the normal distribution $\mathcal{N}(\mu_{k,n},\sigma_{k}^{2})$,
where $\mu_{k,n}:=\mu_{k}/\sqrt{n}$. The scaling of the mean reward
by $\sqrt{n}$ follows \citet{wager2021diffusion} and \citet{fan2021diffusion}
and ensures the signal decays with sample size. The variances, $\sigma_{k}^{2}$,
are assumed to be known. Taking variances to be known is common practice
when working under local asymptotics as replacing unknown variances
with consistent estimates has no effect on asymptotic risk (see Section
\ref{sec:Conclusion}). In this section and the next, we provide a
detailed description of the MAB problem under such normally distributed
rewards. The utility of this analysis stems from the fact that more
general models - that assume either a parametric or non-parametric
distribution of rewards - reduce asymptotically to the normal setting
under the limit of experiments approach, see Sections \ref{sec:General-parametric-models}
and \ref{sec:The-nonparametric-setting}.
In what follows, we represent rewards using the so-called `stack-of-rewards
model' (\citealp[Section 4.6]{lattimore2020bandit}). This entails
the following: We exclusively use $j$ to refer to the periods of
experimentation, and $i$ to refer to the number of pulls of an arm.
$Y_{i}^{(k)}$ denotes the reward at the $i$-th pull of arm $k$,
and ${\bf y}_{i}^{(k)}:=\{Y_{i^{\prime}}^{(k)}\}_{i^{\prime}=1}^{i}$
denotes the sequence of rewards after $i$ pulls of that arm. We can
imagine that prior to the experiment, nature draws a stack of outcomes,
$\{Y_{i}^{(k)}\}_{i=1}^{n}$, corresponding to each arm $k$, and
at each period $j$, if $A_{j}=k$, the agent observes the outcome
at the top of the stack (this outcome is then removed from the stack).
Note that $\{Y_{i}^{(k)}\}_{i=1}^{n}$ are iid conditional on the
unknown parameters $\mu_{k}$.
Due to normality of the rewards, the only relevant state variables
are the number of times the arm was pulled, $q_{k}(t):=n^{-1}\sum_{j=1}^{\left\lfloor nt\right\rfloor }\mathbb{I}(A_{j}=k)$,
the cumulative rewards, $x_{k}(t):=n^{-1/2}\sum_{i=1}^{\left\lfloor nq_{k}(t)\right\rfloor }Y_{i}^{(k)}$,
and time $t$ (see Section \ref{sec:General-parametric-models} for
a formal argument about the sufficiency of these variables). The scaling
on $x_{k}(t)$ follows \citet{wager2021diffusion} and is equivalent
to rescaling the rewards $Y_{i}^{(k)}$ by the factor $1/\sqrt{n}$.
The DM chooses a policy rule $\pi(\cdot)\equiv\{\pi_{k}(\cdot)\}_{k}:\mathcal{S}\rightarrow[0,1]^{K+1}$
that determines the probability of pulling each arm $k$ given the
current state $s:=\{\{x_{k},q_{k}\}_{k},t\}$.
For Lipschitz continuous $\pi$, \citet{wager2021diffusion} show
that $\{x_{k}(\cdot),q_{k}(\cdot)\}_{k}$ evolve in the large $n$
limit according to the stochastic differential equations (SDEs)
\begin{align}
dq_{k}(t)=\pi_{k}(s_{t})dt;\quad dx_{k}(t) & =\pi_{k}(s_{t})\mu_{k}dt+\sigma_{k}\sqrt{\pi_{k}(s_{t})}dW_{k}(t),\label{eq:diffusion limit}
\end{align}
where $\{W_{k}(\cdot)\}_{k}$ are independent one-dimensional Brownian
motions, and $\pi_{k}(s_{t}):=\pi_{k}(s(t))$. While (\ref{eq:diffusion limit})
is convenient for heuristics, there is in fact no guarantee that the
optimal policy possesses the requisite regularity properties for (\ref{eq:diffusion limit})
to formally hold. As it turns out, our formal results, in Section
3, do not rely on (\ref{eq:diffusion limit}).
\subsection{Payoff and loss functions}
We take the loss function to be cumulative payoffs, where the payoff
is $0$ when the experiment concludes at $t=1$. We focus on the regret
payoff
\begin{equation}
R(A,\mu)=n^{-1/2}\left\{ Y^{(k^{*})}-\sum_{k}Y^{(k)}\mathbb{I}(A=k)\right\} ,\label{eq:regret payoff defn}
\end{equation}
where $k^{*}=\arg\max_{k}\mu_{k}$. It is the difference in rewards
between the optimal action, $A^{*}=k^{*}$, and the action $A$. Clearly,
regret is just a rescaling of the welfare payoff $W(A,\mu)=-\sum_{k}Y^{(k)}\mathbb{I}(A=k)/\sqrt{n}$.
While these payoffs are equivalent under Bayes risk, their behavior
under minimax risk is very different. Under the welfare payoff, the
minimax policy is trivial and excessively pessimistic: the DM should
never pull the arm. By contrast, the minimax risk under regret payoff
is non trivial. For this reason, we focus exclusively on regret (as
does most of the bandit literature).
Our theory easily extends to other loss criteria, e.g., best arm identification
(\citealp{kasy2019adaptive}). The latter is discussed in Appendix
\ref{subsec:Best-arm-identification}.
\subsection{Bayes risk\label{subsec:Bayes-risk}}
Here we introduce asymptotic Bayes risk for bandit experiments.
\subsubsection{Priors and posteriors\label{subsec:Priors-and-posteriors}}
Suppose the DM places a prior, $m_{0}$, over $\bm{\mu}:=(\mu_{0},\dots,\mu_{K-1})$.
When the current state is $s\equiv\{\{x_{k},q_{k}\}_{k},t\}$, the
posterior density of $\bm{\mu}$ is\footnote{Here, and in the sequel, $\propto$ denotes `proportional to', i.e.,
equality up to a normalizing constant.}
\begin{equation}
p(\bm{\mu}\vert s)\propto\prod_{k}p_{q_{k}}(x_{k}\vert\mu_{k};\sigma_{k}^{2})\cdot m_{0}(\bm{\mu});\quad p_{q}(\cdot\vert\mu;\sigma^{2})\equiv\mathcal{N}(\cdot\vert q\mu,q\sigma^{2}),\label{eq:posterior}
\end{equation}
where $\mathcal{N}(\cdot\vert\mu,\sigma^{2})$ is the normal density
with mean $\mu$ and variance $\sigma^{2}$. Importantly, the posterior
depends only on the $\left\lfloor nq_{k}\right\rfloor $ realizations
of the rewards, $\{{\bf y}_{nq_{k}}^{(k)}\}_{k}$, from each arm $k$
and is not affected by the past values of the actions (nor by past
values of $q_{k}$). Lemma \ref{Lemma 1} in Appendix \ref{subsec:Supporting-lemmas-for}
shows that this property holds generally, and is not limited to Gaussian
rewards.
Since the prior is placed on the local parameter $\bm{\mu}$, it is
asymptotically `non-negligible'. In this regard, our approach differs
fundamentally from the previous literature (e.g., \citealp{lai1987adaptive})
on Bayesian bandits which employs a fixed prior. The rationale for
non-negligible priors is two-fold: First, it provides a better approximation
to finite sample properties. Indeed, any prior applied on the actual
mean, $\bm{\mu}/\sqrt{n}$, would be flat asymptotically, and its
Bayes risk simply $0$ under the $\sqrt{n}$ scaling of mean rewards.
Second, it enables us to characterize minimax risk as Bayes risk under
a least favorable prior (see Section \ref{subsec:Minimax-risk}).
The least favorable prior is non-negligible.
In practice, we are typically provided with a prior, $\rho_{0}$,
on the unscaled mean $\bm{\mu}_{n}=\bm{\mu}/\sqrt{n}$. To apply the
methods here, one needs to convert this to a prior, $m_{0}(\cdot)=\rho_{0}(\cdot/\sqrt{n})$,
on $\bm{\mu}$. To illustrate, suppose the DM places a Gaussian prior
$\mu_{k,n}\sim\mathcal{N}\left(\bar{\mu}_{k,0},\bar{\nu}_{k}^{2}\right)$
that is independent across $k$. We calibrate the scaled prior mean
and variance as $\mu_{k,0}=\sqrt{n}\bar{\mu}_{k,0}$ and $\nu_{k}^{2}=n\bar{\nu}_{k}^{2}$,
so $\mu_{k}:=\mu_{k,n}/\sqrt{n}\sim\mathcal{N}(\mu_{k,0},\nu_{k}^{2})$.
Then, if the current state is $s\equiv\{\{x_{k},q_{k}\}_{k},t\}$,
the posterior distribution of $\mu_{k}$ is
\begin{equation}
\mu_{k}\vert s\sim\mathcal{N}\left(\frac{\sigma_{k}^{-2}x_{k}+\nu_{k}^{-2}\mu_{k,0}}{\sigma_{k}^{-2}q_{k}+\nu_{k}^{-2}},\frac{1}{\sigma_{k}^{-2}q_{k}+\nu_{k}^{-2}}\right).\label{eq:posterior distribution normal}
\end{equation}
\subsubsection{PDE characterization of Bayes and minimal Bayes risk\label{subsec:PDE-characterization-of}}
For a policy $\pi$, we define asymptotic Bayes risk, $V_{\pi}(s)$,
as the expected cumulative regret in the diffusion regime, where the
expectation is taken conditional on all information until state $s$.
We now informally derive a PDE characterization of $V_{\pi}(s)$.
Consider the evolution of cumulative regret in a short time period,
$\Delta t$, following state $s$. The expected regret accrued within
this time period is approximately
\[
\mathbb{E}_{\bm{\mu}\vert s}\left[\mu_{k^{*}}-\sum_{k}\mu_{k}\pi_{k}\right]\cdot\Delta t=\left(\mu^{\max}(s)-\sum_{k}\mu_{k}(s)\pi_{k}\right)\cdot\Delta t,
\]
where $\mu^{\max}(s):=\mathbb{E}_{\bm{\mu}\vert s}[\max_{k}\mu_{k}]$
and $\mu_{k}(s):=\mathbb{E}_{\mu_{k}\vert s}[\mu_{k}]$ are the posterior
means of $\max_{k}\mu_{k}$ and $\mu_{k}$. At the same time, by (\ref{eq:diffusion limit}),
the change to $q_{k}$ and $x_{k}$ over this time period is approximately
(henceforth we use $\pi_{k}$ as a shorthand for $\pi_{k}(s)$)
\begin{align*}
\Delta q_{k} & \approx\pi_{k}\Delta t;\quad\Delta x_{k}\approx\pi_{k}\mu_{k}\Delta t+\sigma_{k}\sqrt{\pi_{k}}\Delta W(t).
\end{align*}
Hence, up to a first order approximation, $V_{\pi}(s)$ satisfies
the recursion
\begin{equation}
V_{\pi}(s)\approx\mathbb{E}\left[\left.\left(\mu^{\max}(s)-\sum_{k}\mu_{k}(s)\pi_{k}\right)\cdot\Delta t+V_{\pi}\left(\{x_{k}+\Delta x_{k},q_{k}+\Delta q_{k}\}_{k},t+\Delta t\right)\right|s\right],\label{eq:recursion for V_pi}
\end{equation}
with the terminal condition $V_{\pi}(s)=0$ if $t=1$.
Now, Ito's lemma implies that
\begin{align*}
& \mathbb{E}\left[\left.V_{\pi}\left(\{x_{k}+\Delta x_{k},q_{k}+\Delta q_{k}\}_{k},t+\Delta t\right)-V_{\pi}(s)\right|s\right]\\
& \approx\left(\partial_{t}V_{\pi}+\sum_{k}\left\{ \pi_{k}\partial_{q_{k}}V_{\pi}+\pi_{k}\mu_{k}(s)\partial_{x_{k}}V_{\pi}+\frac{1}{2}\pi_{k}\sigma_{k}^{2}\partial_{x_{k}}^{2}V_{\pi}\right\} \right)\Delta t.
\end{align*}
Thus, subtracting $V_{\pi}(s)$ from both sides of the recursion (\ref{eq:recursion for V_pi})
and dividing by $\Delta t$, we find that $V_{\pi}(\cdot)$ solves
the PDE
\begin{align}
\partial_{t}V_{\pi}+\mu^{\max}(s)+\sum_{k}\pi_{k}(s)\left\{ -\mu_{k}(s)+L_{k}[V_{\pi}](s)\right\} & =0\ \textrm{if }t<1,\label{eq:PDE- bayes risk}
\end{align}
with the terminal condition $V_{\pi}(s)=0$ if $t=1$. Here,
\[
L_{k}[f]:=\partial_{q_{k}}f+\mu_{k}(s)\partial_{x_{k}}f+\frac{1}{2}\sigma_{k}^{2}\partial_{x_{k}}^{2}f.
\]
denotes the infinitesimal generator of $\{x_{k}(\cdot),q_{k}(\cdot)\}$
for each $k$. It is the continuous time counterpart of the transition
density matrix for these state variables.
We can derive a similar characterization of the minimal Bayes risk,
$V_{\pi}^{*}(s):=\inf_{\pi(\cdot)\in\Pi}V_{\pi}(s)$, where $\Pi$
denotes the class of all possible policy rules. By the dynamic programming
principle, and in analogy with (\ref{eq:recursion for V_pi}), we
should have
\[
V^{*}(s)\approx\inf_{\pi\in[0,1]}\mathbb{E}\left[\left.\left(\mu^{\max}(s)-\sum_{k}\mu_{k}(s)\pi_{k}\right)\cdot\Delta t+V^{*}\left(\{x_{k}+\Delta x_{k},q_{k}+\Delta q_{k}\}_{k},t+\Delta t\right)\right|s\right],
\]
for any small time increment $\Delta t$, with the terminal condition
$V^{*}(s)=0$ if $t=1$. Then, by similar heuristic arguments as those
leading to (\ref{eq:PDE- bayes risk}), we obtain
\begin{align}
\partial_{t}V^{*}+\mu^{\max}(s)+\min_{k}\left\{ -\mu_{k}(s)+L_{k}[V^{*}](s)\right\} & =0\ \textrm{if }t<1,\label{eq:PDE_optimal_bayes_risk_General}\\
V^{*}(s) & =0\ \textrm{if }t=1.\nonumber
\end{align}
As with PDE (\ref{eq:PDE- bayes risk}), PDE (\ref{eq:PDE_optimal_bayes_risk_General})
can be solved using knowledge only of $\{\sigma_{k}^{2}\}_{k}$. We
can thus characterize the minimal ex-ante Bayes risk as $V^{*}(0):=V^{*}(s_{0})$,
where $s_{0}:=\{\{x_{k}=0,q_{k}=0\}_{k},t=0\}$ is the initial state.
\subsubsection*{Discussion}
In the context of PDE (\ref{eq:PDE_optimal_bayes_risk_General}),
we can interpret $\mu_{k}(s)$ as the `exploitation-value' of arm
$k$, and $-L_{k}[V^{*}](s)$ as its `exploration-value' (the marginal
reduction to future regret from pulling arm $k$), so the `overall-value'
from pulling arm $k$ is $\mu_{k}(s)-L_{k}[V^{*}](s)$. Hence, (\ref{eq:PDE_optimal_bayes_risk_General})
describes an exploration-exploitation tradeoff: the regret payoffs
are one of $\{\mu^{\max}(s)-\mu_{k}(s)\}_{k}$ and always greater
than $0$, but as $\{q_{k}\}_{k}$ increase, the posterior collapses
to a point, in which case one chooses the optimal arm with certainty
and the instantaneous regret $\varpi(s):=\min_{k}\{\mu^{\max}(s)-\mu_{k}(s)\}$
becomes $0$. The DM thus faces a tradeoff between exploration, i.e,
pulling the arm enough times to increase $q_{k}$ and thereby reduce
$\varpi(s)$ in the future, and exploitation, i.e., choosing the best
action, $\operatorname*{arg\,max}_{k}\mu_{k}(s)$, at the present.
If a classical, i.e., twice continuously differentiable, solution,
$V^{*}(\cdot)$, to PDE (\ref{eq:PDE_optimal_bayes_risk_General})
exists, the optimal Bayes policy is $\pi^{*}(s)=\operatorname*{arg\,min}_{k}\{L_{k}[V^{*}](s)-\mu_{k}(s)\}$,
i.e., it pulls the arm with the highest `overall-value'. While a classical
solution to (\ref{eq:PDE_optimal_bayes_risk_General}) is generally
impossible, one can always construct measurable policies whose Bayes
risk is arbitrarily close to $V^{*}(\cdot)$. One such construction
is provided in Section \ref{subsec:Optimal-and-approximately}.
\subsubsection{A special case: one-armed bandits\label{subsec:A-special-case:}}
The one-armed bandit is a special case of the MAB problem with two
arms and with arm $0$ corresponding to a known outside option. We
normalize the reward from the outside option to $0$, i.e., $\mu_{0}=0$
and $\sigma_{0}=0$. The set of sufficient statistics can then be
reduced to $s\equiv\{x(t):=x_{1}(t),q(t):=q_{1}(t),t\}$. Let $\mu:=\mu_{1}$
and $\sigma^{2}:=\sigma_{1}$ denote the mean and variance of arm
1. For Bayesian analysis, we place a prior $m_{0}$ on the unknown
$\mu$. The PDE characterization of minimal Bayes risk, $V^{*}$,
then simplifies to
\begin{align}
\partial_{t}V^{*}+\mu^{+}(s)+\min\left\{ -\mu(s)+L[V^{*}](s),0\right\} & =0\ \textrm{if }t<1,\label{eq:PDE optimal bayes risk}
\end{align}
with the terminal condition $V^{*}(s)=0$ if $t=1$, where $\mu^{+}(s):=\mathbb{E}_{\mu\vert s}[\max\{\mu,0\}]$,
$\mu(s):=\mathbb{E}_{\mu\vert s}[\mu]$ and $L[f]:=\partial_{q}f+\mu(s)\partial_{x}f+\frac{1}{2}\sigma^{2}\partial_{x}^{2}f$.
We make frequent reference to one-armed bandits in what follows as
the reduced state space enables us to describe our theoretical results
with minimal notational overhead while still preserving the essential
conceptual features of the MAB problem.
For one-armed bandits, it is easily verified that the optimal policy
is a retirement policy, i.e., if the DM did not pull the arm at some
time $t$, she will not do so at any other time in the future.\footnote{This because the posterior remains unchanged while the arm is not
being pulled.} Also, it needs to be non-decreasing in $x$. These properties imply
$\pi^{*}(s)$ is of the form $\mathbb{I}\left\{ x>f(q,t)\right\} $.
\subsection{Comparison with existing methods\label{subsec:Comparison-with-existing}}
Perhaps the two most commonly used algorithms for MAB problems are
Thompson Sampling (TS) and UCB. The TS rule is $\pi_{k}^{\textrm{ts}}(s)=\mathbb{P}\left(\mu_{k}\ge\max_{k^{\prime}}\mu_{k^{\prime}}\vert s\right)$
and its asymptotic Bayes risk can be obtained by solving (\ref{eq:PDE- bayes risk}).
Figure \ref{fig:Policy plots-1-1} compares this with the corresponding
minimal Bayes risk for one-armed bandits under Gaussian priors, obtained
by solving PDE (\ref{eq:PDE optimal bayes risk}). For the numerical
comparison, we set the prior mean to $0$ and vary the prior and error
variances, $\nu^{2}$ and $\sigma^{2}$. To interpret the ranges of
$\nu^{2},\sigma^{2}$, note that the unscaled prior variance is $\nu^{2}/n$
(which is why $\nu>\sigma$) and all the policies considered here
are invariant to $\nu/\sigma$; for reference, our empirical application
in Section \ref{subsec:Two-armed-bandits} uses $\nu/\sigma\approx15$.
TS is inferior to the optimal Bayes policy across all parameter values
and substantially so - its Bayes risk is generally twice as high.
\begin{figure}
\includegraphics[height=5cm]{Code/Comparison_plots}\\
\begin{raggedright}
{\scriptsize Note: The default parameter values are $\mu_{0}=0$, $\nu=50$
and $\sigma=5$. Modified TS refers to the Thompson sampling rule
modified so that $\pi=1$ whenever $x\ge0$. }{\scriptsize\par}
\par\end{raggedright}
\caption{Asymptotic risk of various policies under one-armed bandits\label{fig:Policy plots-1-1}}
\end{figure}
Figure \ref{fig:Policy plots-2} plots the associated optimal policy
rule, under the parameter values $(\nu=50,\sigma=5)$, as a function
of $x,q$ at a few different snapshots in time. As conjectured earlier,
it is of the form $\pi^{*}(s)=\mathbb{I}\{x\ge f(q,t)\}$ with\textcolor{blue}{{}
$f(\cdot)$ }increasing in $t$ and decreasing in $q$. The policy
recommends pulling the arm for some $x<0$, even though this indicates
negative expected rewards, $\mu(s)$. This is an example of exploration.
The extent of exploration, i.e., the values of $x$ for which $\pi^{*}(s)=1$,
declines over time. The figure also plots a heat-map of, $\pi^{\textrm{ts}}(\cdot)$,
the TS rule. The reason why $\pi^{\textrm{ts}}(\cdot)$ is inferior
is simple: it over-explores. TS continuously attempts to trade-off
exploration and exploitation against each other, but these motives
are not always at odds. Indeed, when $x\ge0$, pulling the arm is
optimal for both exploitation (since the posterior mean is positive)
\textit{and} exploration. A simple modification to the TS rule, that
sets $\pi=1$ whenever $x\ge0$ but is otherwise equivalent to TS,
thus delivers 15-20\% lower Bayes risk under our one-armed bandit
setups, as Figure \ref{fig:Policy plots-1-1} illustrates. More generally,
for MABs, we can improve the Bayes risk of TS by modifying it as follows:
whenever there exist arms $k,k^{\prime}$ such that $\mu_{k}(s)<\mu_{k^{\prime}}(s)$
and $\textrm{Var}[\mu_{k}\vert s]\le\textrm{Var}[\mu_{k^{\prime}}\vert s]$,
we should transfer all the probability that TS assigns to $k$ to
$k^{\prime}$ (this can be repeated for all $k,k^{\prime}$).
\begin{figure}
\includegraphics[height=4cm]{Code/heatmap_t20}~\includegraphics[height=4cm]{Code/heatmap_t50}~\includegraphics[height=4cm]{Code/heatmap_t80}
\vspace*{0.2cm}$\quad$\includegraphics[height=4cm]{Code/heatmap_MOSS}$\ $\includegraphics[height=4cm]{Code/heatmap_thompson}\\
\begin{raggedright}
{\scriptsize Note: The parameter values are $\mu_{0}=0$, $\nu=50$
and $\sigma=5$. Blue corresponds to pulling the arm while red corresponds
to not pulling it. The TS and MOSS policies do not change over time.
In comparing the optimal policy with the others, note that the regions
where $Q\ge T$ are not actually attainable (though the optimal policy,
as plotted, remains well-defined). }{\scriptsize\par}
\par\end{raggedright}
\caption{Policy maps for a one-armed bandit\label{fig:Policy plots-2}}
\end{figure}
On the other hand, the optimal policy shares a number of similarities
with UCB algorithms. Note that $\hat{\mu}:=x/q\sqrt{n}$ is the MLE
estimator of the sample mean $\mu/\sqrt{n}$. Then, defining $F(q,t)=-f(q,t)/q$,
we find that the optimal policy for one-armed bandits has the form
$\pi^{*}=\mathbb{I}\left\{ \hat{\mu}+F(q,t)/\sqrt{n}\ge0\right\} $.
We can thus interpret $F(q,t)/\sqrt{n}$ as the optimal confidence
width in that setting. More generally, for the MAB problem, if the
prior is normal and independent across arms, $\mu_{k}(s)$ is a function
only of $x_{k},q_{k}$ and monotonically increasing in $\hat{\mu}_{k}=x_{k}/q_{k}\sqrt{n}$.
We can then rewrite the optimal policy in the UCB form $\pi^{*}=\operatorname*{arg\,max}_{k}\{\hat{\mu}_{k}+F_{k}(s)/\sqrt{n}\}$,
even if, unlike a typical UCB, $F_{k}(\cdot)$ depends on all of $s$
instead of just $x_{k},q_{k}$.
For correlated priors, however, the optimism principle fails and the
optimal policy may be very different from UCB. Indeed, it can then
even be optimal to pull an arm with a lower UCB than the others if
it is highly informative about the common parameter. The reason for
this difference is that while uncertainty over $\mu_{k}$ is just
one of many factors that determine the exploration-value, $-L_{k}[V^{*}](\cdot)$,
of an arm $k$, the confidence width used in UCBs is determined solely
by it.
The vanilla UCB policy uses the confidence width $\sqrt{2\sigma^{2}\ln(1/\delta)/nq_{k}}$
for each $k$, where $\delta$ is a tuning parameter. But this is
far from optimal. For two-armed bandits, \citet{kalvit2021closer}
show that it converges (under diffusion asymptotics) to a fixed (i.e.,
non-adaptive) allocation rule that is independent of $\delta,\mu_{1},\mu_{0}$.
Thus, this class of UCBs over-explore, and their minimax rate of regret
is $O(\sqrt{\log n/n})$.
The minimax optimal rate, $O(n^{-1/2})$, can be regained with a more
refined confidence width, as evidenced by the MOSS algorithm which
uses $\sqrt{2\sigma^{2}g(q_{k})/nq_{k}}$, where $g(q)\propto\ln(Kq)^{-1}$.
In fact, by \citet{lai1987adaptive}, this is an approximation, as
$q\to0$, of the optimal width, $F(q,t)/\sqrt{n}$, in the one-armed
setting under a flat prior (i.e., when $\nu^{2}\to\infty$). More
generally, with multiple arms and independent Gaussian priors, Section
\ref{sec:Computation-and-simulations} shows that while the standard
implementation of MOSS performs a lot worse than the optimal policy,
an optimally tuned MOSS, that uses the confidence width $\sqrt{\gamma\sigma^{2}g(q_{k})/nq_{k}}$,
comes close to attaining the risk lower bound. Our proposal for the
optimal $\gamma$ here is to choose the value that minimizes the local
asymptotic Bayes risk of MOSS under the given prior. Such an optimal
$\gamma$ is, however, highly sensitive to the prior parameters. Figure
\ref{fig:Policy plots-2} shows that the optimally tuned MOSS $(\gamma^{*}\approx1.72$)
under the parameter values $(\nu=50,\sigma=5)$ shares broad similarities
with the optimal policy, albeit being independent of time.
\subsection{Minimax risk\label{subsec:Minimax-risk}}
Following \citet{wald1945statistical}, we define minimax risk as
the value of a two player zero-sum game played between nature and
the DM. Nature's action consists of choosing a prior, $m_{0}\in\mathcal{P}$,
over $\bm{\mu}$, while the DM chooses the policy rule $\pi$. The
minimax risk $\bar{V}^{*}$ is defined as
\begin{equation}
\bar{V}^{*}=\sup_{m_{0}\in\mathcal{P}}V^{*}(0;m_{0})=\sup_{m_{0}\in\mathcal{P}}\inf_{\pi\in\Pi}V_{\pi}(0;m_{0}),\label{eq:def of minimax risk}
\end{equation}
where $V_{\pi}(0;m_{0})$ and $V^{*}(0;m_{0})$ denote the ex-ante
Bayes risk under a policy $\pi$, and the minimal Bayes risk, when
the prior is $m_{0}$. The equilibrium action of nature is termed
the least-favorable prior, and that of the DM, the minimax policy.
Under a minimax theorem, which holds if there is a Nash equilibrium
to the game (with proper priors), the $\sup$ and $\inf$ operations
in (\ref{eq:def of minimax risk}) can be interchanged, so that
\begin{equation}
\sup_{m_{0}\in\mathcal{P}}\inf_{\pi\in\Pi}V_{\pi}(0;m_{0})=\inf_{\pi\in\Pi}\sup_{m_{0}\in\mathcal{P}}V_{\pi}(0;m_{0})=\inf_{\pi\in\Pi}\sup_{\bm{\mu}}V_{\pi}(0;\bm{\mu}).\label{eq:game equivalence}
\end{equation}
Here, $V_{\pi}(0;\bm{\mu})$ denotes the frequentist risk of a policy
$\pi$ when the local parameter is $\bm{\mu}$. The last term, $\inf_{\pi\in\Pi}\sup_{\bm{\mu}}V_{\pi}(0;\bm{\mu})$,
is perhaps the more common definition of minimax risk. Thus, by (\ref{eq:game equivalence}),
the problem of computing minimax risk reduces to that of computing
Bayes risk under the least favorable prior.
For one-armed bandits, we conjecture, and verify numerically by solving
the two player game, that the least favorable prior, $m_{0}^{*}$,
involves only two support points at $\{\text{\underbar{\ensuremath{\mu}}},\bar{\mu}\}$,
with $\text{\underbar{\ensuremath{\mu}}}<0$ and $\bar{\mu}>0$. This
is because both low and high values of $\vert\mu\vert$ are associated
with low risk, the former by definition, and the latter because the
DM quickly learns to always pull or never pull the arm. Indeed, for
$\sigma=1$, it turns out $m_{0}^{*}$ has a two point support at
$\text{\underbar{\ensuremath{\mu}} \ensuremath{\approx} -2.5 }$ and
$\bar{\mu}\approx1.7$ with $m_{0}^{*}(\bar{\mu})\approx0.415$. In
fact, it suffices to solve the game under $\sigma=1$ as we can always
rescale the rewards to have unit variance (the risk comparisons are
invariant to scale transformations).
Based on the above analysis, we find that the sharp lower bound on
the (unscaled) minimax risk of any one-armed bandit algorithm is given
by $0.373\sigma\sqrt{n}$. By contrast, existing theoretical results
only demonstrate a $\sigma\sqrt{n}$ rate.
Computing the least favorable prior when there are more than two arms
is a lot more demanding. We conjecture, however, that it has a discrete
support.
\section{Formal properties under gaussian rewards\label{sec:Formal-properties} }
For simplicity, the results in this section are stated for the one-armed
bandit problem. However, all our results extend to the general MAB
problem with straightforward adjustments to the proofs, see Appendix
\ref{subsec:Multi-armed-bandits}.
\subsection{Existence and uniqueness of PDE solutions}
Equation (\ref{eq:PDE optimal bayes risk}) describes a nonlinear
$2^{\textrm{nd}}$-order PDE. It is well known that such PDEs do not
admit classical, i.e., twice continuously differentiable, solutions.
Instead, the relevant weak solution concept is that of a viscosity
solution (\citealt{crandall1992user}).
\begin{thm}\label{theorem 1} \textbf{\textit{\citep[Theorem A.1]{barles2007error}}}
Suppose $\mu^{+}(\cdot),\mu(\cdot)$ are $\gamma$-H{\"o}lder continuous
for some $\gamma>0$. Then there exists a unique, $\gamma$-H{\"o}lder
continuous viscosity solution to PDE (\ref{eq:PDE optimal bayes risk}).
\end{thm}
\subsection{Convergence to the PDE solution\label{subsec:Convergence-to-PDE}}
In Section 2, we provided a heuristic derivation of PDE (\ref{eq:PDE optimal bayes risk}).
For a formal result, one would need to prove that a discrete analogue,
$V_{n}^{*}(\cdot)$, of $V^{*}(\cdot)$, defined for a fixed $n$,
converges to $V^{*}(\cdot)$ as $n\to\infty$. Define $\mathbb{I}_{n}=\mathbb{I}\{t\le1-1/n\}$
and $Y_{i}$ as the $i$-th realization of the rewards (corresponding
to the $i$-th pull of the arm). Let $V_{n}^{*}(\cdot)$ denote the
solution to the recursive equation
\begin{align}
V_{n}^{*}\left(x,q,t\right) & =\min_{\pi\in[0,1]}\mathbb{E}\left[\left.\frac{\mu^{+}(s)-\pi\mu(s)}{n}+\mathbb{I}_{n}\cdot V_{n}^{*}\left(x+\frac{A_{\pi}Y_{nq+1}}{\sqrt{n}},q+\frac{A_{\pi}}{n},t+\frac{1}{n}\right)\right|s\right];\nonumber \\
& \quad\textrm{if }t<1,\nonumber \\
V_{n}^{*}\left(x,q,t\right) & =0\quad\textrm{if }t=1.\label{eq:discrete approximation}
\end{align}
In (\ref{eq:discrete approximation}), $A_{\pi}\sim\textrm{Bernoulli}(\pi)$,
and the expectation is a joint one over $(Y_{nq+1},A_{\pi})$ given
$s$. Existence of a unique $V_{n}^{*}(\cdot)$ follows by backward
induction. Clearly, $V_{n}^{*}(\cdot)$ is the minimal Bayes risk
in the fixed $n$ setting under Gaussian rewards. We can thus interpret
(\ref{eq:discrete approximation}) as a discrete approximation to
PDE (\ref{eq:PDE optimal bayes risk}). As such, it falls under the
abstract framework of \citet{barles1991convergence} for showing convergence
to viscosity solutions. An application of their techniques proves
the following result (the proof is in Appendix \ref{subsec:Proof-of-Theorem-2}):
Denote $\varpi(s):=\min\left\{ \mu^{+}(s)-\mu(s),\mu^{+}(s)\right\} $.
\begin{thm}\label{Thm: Convergence to minimal PDE} Suppose $\mu^{+}(\cdot),\mu(\cdot)$
are $\gamma$-H{\"o}lder continuous, $\sup_{s}\varpi(s)<\infty$
and the prior $m_{0}$ is such that $\mathbb{E}[\vert\mu\vert^{3}\vert s]<\infty$
at each $s$. Then, as $n\to\infty$, $V_{n}^{*}(\cdot)$ converges
locally uniformly to $V^{*}(\cdot)$, the unique viscosity solution
of PDE (\ref{eq:PDE optimal bayes risk}). \end{thm}
The assumptions are satisfied for Gaussian priors. Note also that
the theorem is proved without appealing to (\ref{eq:diffusion limit}).
In Appendix \ref{subsec:Rates-of-convergence} we derive a coarse
upper bound on the rate of convergence of $V_{n}^{*}(\cdot)$ to $V^{*}(\cdot)$
and provide simulation evidence suggesting that the quality of the
approximation is quite good in practice.
\subsection{Piece-wise constant policies and batched bandits\label{subsec:Optimal-and-approximately}}
While we are not able to characterize the optimal Bayes policy in
closed form, it is possible to construct (Lebesgue) measurable policies
whose Bayes risk is arbitrarily close to $V^{*}(\cdot)$. One way
to do so is using piece-wise constant policies. In fact, a bandit
experiment with such a policy is equivalent to a batched bandit experiment,
where the data is forced to be considered in batches. The results
in this section thus give an upper bound on the welfare loss due to
batching.
Let $\Delta t$ denote a small time increment, and $\mathcal{T}_{\Delta t}:=\{t_{1},\dots,t_{L}\}$
a set of grid points for time, where $t_{1}=0$, $t_{L}=1$ and $t_{l}-t_{l-1}=\Delta t$
for all $l$. The optimal piece-wise constant policy, $\pi_{\Delta t}^{*}:\mathcal{X}\times\mathcal{Q}\times\mathcal{T}_{\Delta t}\mapsto\{0,1\}$,
is allowed to change only at the time points on the grid $\mathcal{T}_{\Delta t}$.
In particular, suppose that $x=x_{l}$ and $q=q_{l}$ at the grid
point $t=t_{l}$. Then one computes $\pi_{\Delta t}^{*}(x_{l},q_{l},t_{l})\in\{0,1\}$
and holds this policy value fixed until the next time point $t_{l+1}$.
Define $V_{\Delta t,l}^{*}(x,q)$ as the Bayes risk, in the diffusion
regime, at state $(x,q,t_{L-l})$ under $\pi_{\Delta t}^{*}(\cdot).$
We then have the following recursion for $V_{\Delta t,l}^{*}(x,q)$:
\begin{align}
V_{\Delta t,l+1}^{*}(x,q) & =\min\left\{ S_{\Delta t}\left[V_{\Delta t,l}^{*}\right](x,q),V_{\Delta t,l}^{*}(x,q)+\Delta t\cdot\mu^{+}(x,q)\right\} ,\ l=0,\dots,L-1,\nonumber \\
V_{\Delta t,0}^{*}(x,q) & =0,\label{eq:piecewise-constant policy}
\end{align}
where the operator $S_{\Delta t}[\phi](x,q)$ denotes the solution
at $(x,q,\Delta t)$ of the linear second order PDE
\begin{align}
-\partial_{t}f(s)+\mu^{+}(s)-\mu(s)+L[f](s) & =0,\ \textrm{if }t>0;\quad f=\phi,\ \textrm{if }t=0.\label{eq:linear PDE}
\end{align}
The following theorem assures that $V_{\Delta t,l}^{*}(\cdot)$ can
be made arbitrarily close to $V^{*}(\cdot,\cdot,t_{L-l})$ by letting
$\Delta t\to0$.
\begin{thm}\label{Thm: Approximate control}\textbf{\textit{\citep[Theorem 2.1]{jakobsen2019improved}}}
Suppose $\mu^{+}(\cdot),\mu(\cdot)$ are Lipschitz continuous. Then,
there exists $C<\infty$ that depends only on the Lipschitz constants
of $\mu^{+}(\cdot),\mu(\cdot)$ such that $0\le\max_{l}\left\{ V_{\Delta t,l}^{*}(\cdot)-V^{*}(\cdot,t_{L-l})\right\} \le C(\Delta t)^{1/4}$
uniformly over $\mathcal{X}\times\mathcal{Q}$.\end{thm}
Note that $\pi_{\Delta t}^{*}(\cdot)$ is not required to converge
to some measurable $\pi^{*}(\cdot)$ as $\Delta t\to0$. Still, we
can employ $\pi_{\Delta t}^{*}(\cdot)$ in the fixed $n$ setting:
to apply, one simply sets $t=\left\lfloor i/n\right\rfloor $, where
$i$ is the current period. The following theorem asserts that employing
$\pi_{\Delta t}^{*}(\cdot)$ in this manner results in a Bayes risk
that is arbitrarily close to $V^{*}(0)$.
\begin{thm}\label{Thm: Approximate control-2}Suppose $\mu^{+}(\cdot),\mu(\cdot)$
are Lipschitz continuous and $\sup_{s}\mu^{+}(s)<\infty$. Then, for
any fixed $\Delta t$, $\lim_{n\to\infty}\left|V_{\pi_{\Delta t}^{*},n}(0)-V^{*}(0)\right|\le C(\Delta t)^{1/4}$
. \end{thm}
\section{Algorithms and empirical illustrations\label{sec:Computation-and-simulations}}
\subsection{Algorithms}
We provide two empirical illustrations of bandit experiments to show
how our methods translate to real world practice. The first application
solves PDE (\ref{eq:PDE_optimal_bayes_risk_General}) using a finite-difference
(FD) scheme, which is very accurate but scales poorly with the number
of arms, while the second uses a Monte-Carlo method, which is less
accurate but scales linearly with the number of arms. The FD algorithm
is discussed in Appendix \ref{sec:Details-on-computation}. Here we
focus on the Monte-Carlo algorithm as it is arguably more useful in
practice with multiple arms.
Algorithm 1 provides the pseudo-code for the Monte-Carlo method. The
basic elements of this approach are well-known and widely used for
solving PDEs of the HJB kind; our specific implementation is similar
to Approximate Value Iteration (\citealp{munos2008finite}). The general
steps are the following: (1) we discretize time into periods of length
$\Delta t$, (2) at each period $j$, we randomly draw a vector of
state variables, (3) starting from $j=T-1$ and going backwards, and
using the random draw of state variables at period $j$ as input,
we use forward simulation and prediction methods to obtain an estimate
of the action-value function, $V_{k,j}(\cdot)$, at period $j$ given
the (previously obtained) estimate of the value function, $\min_{k}V_{k,j+1}(\cdot)$,
in period $j+1$.\textcolor{blue}{{} }Care must be taken to ensure that
the distribution of state variables drawn is close to what would have
been observed under the optimal policy; as prediction methods minimize
expected MSE, we would like this expectation to be close to that induced
by the optimal policy. Hence, we draw the state variables using a
pilot policy, typically Thompson Sampling, and then run the algorithm
once again with the updated policy.\footnote{In principle, one could iterate this, but we found it to be unnecessary
in practice.}
\noindent\begin{minipage}{\textwidth}
\begin{algorithm}[H]
\caption{Monte-Carlo algorithm for solving PDE (\ref{eq:PDE_optimal_bayes_risk_General})}\label{alg:Monte-Carlo alg}
\footnotesize
\begin{algorithmic}[1]
\Require{$K$ ($\#$ arms), $\Delta t$ (step size), $B$, $M$ (simulation draws), $T := 1/\Delta t$, $\pi^{\textrm{init}}$ (pilot policy)}
\vspace{0.3em}
\State Simulate $b=1,\dots,B$ sample paths $s^{(b)}(\cdot):= \{ x_{k}^{(b)}(\cdot),q_{k}^{(b)}(\cdot): k = 1,\dots ,K \}$ from $\pi^{\textrm{init}}$
\State Save values at discrete time points:
\[
(\forall j=1,\dots,T):\ s_{j}^{(b)} =s^{(b)}( j\Delta t),\ x_{k,j}^{(b)}=x_{k}^{(b)}( j\Delta t),\ q_{k,j}^{(b)}=q_{k}^{(b)}(j\Delta t)
\]
\State Initialize period $T-1$ action-value and value functions:
\begin{align*}
(\forall k):\ V_{k,T-1}(\cdot) & = \mu^{\textrm{max}}(\cdot)-\mu_{k}(\cdot)\\
V_{T-1}^{*}(\cdot) & = \min_{k}V_{k,T-1}(\cdot)
\end{align*}
\For{$j=T-2,T-3,\dots,1$:}
\State{$(\forall b,k)$: Compute $z_{k}^{(b)}$ as sample mean of $M$ simulation draws of
\begin{align*}
& V_{k,j+1}^{*}\left(\left\{ x_{l,j}^{(b)}+ \mathbb{I}\{l=k\} \cdot e_{k,j}^{(b)}, \ q_{l,j}^{(b)}+ \mathbb{I}\{l=k\} \cdot \Delta t \right\} _{l=0}^{K-1}\right),\ \textrm{where }\\
& e_{k,j}^{(b)} \sim \mathcal{N} \left(\mu_k \left(s_{j}^{(b)}\right) \cdot \Delta t, \sigma_{k} \cdot \Delta t \right)
\end{align*}
}
\State{$(\forall k)$: Run prediction model of $\{z_{k}^{(b)}\}_{b=1}^{B}$ on $\{s_{j}^{(b)}\}_{b=1}^{B}$, output prediction function $\hat{f}_{k,j}(\cdot)$}
\State{$(\forall k)$: Return as function
\begin{align*}
V_{k,j}(\cdot) & =\mu^{\textrm{max}}(\cdot)-\mu_k(\cdot)+\hat{f}_{k,j}(\cdot)\\
V_{j}^{*}(\cdot) & =\min_{k}V_{k,j}(\cdot)
\end{align*}
}
\EndFor
\State Return policy function $\pi(\cdot, t)=\operatorname*{arg\,min}_{k}V_{k,\left\lfloor t/\Delta t\right\rfloor }(\cdot)$
\State \textbf{Repeat:} steps 1-9 with new pilot policy $\pi^{\textrm{init}}=\pi$
\end{algorithmic}
\footnotetext{Notes: Step 6 requires a prediction method, e.g., Random Forest. The algorithm assumes oracle knowledge of $\mu_k(\cdot), \mu^\textrm{max}(\cdot)$, which are policy independent and computed from the posterior (\ref{eq:posterior}). For Gaussian priors, closed-form expressions exist; otherwise, they can be computed numerically via MCMC/Laplace approximations, akin to the procedure for TS (which employs similar terms).}
\end{algorithm}
\end{minipage}
\vspace{1.7em}Computation is generally fast; for the second empirical
illustration with 2 arms and Gaussian priors, it takes about 40 minutes.
As for the minimax policy under one-armed bandits, used in our first
application, it only needs to be computed once, as we already did
here. In future applications it can be employed straightaway after
simply rescaling the rewards to have unit variance.\footnote{Even with multiple arms, game-theoretic reasoning and the scale invariance
of Brownian motion suggests the minimax policy only needs to be computed
once under the case $\sigma_{k}=1\ \forall\ k$.}
\subsection{A one-armed bandit\label{subsec:A-one-armed-bandit}}
This illustration is based on a Google Analytics blog example on website
optimization.\footnote{The webpage describing the simulation study can be accessed \href{https://analytics.googleblog.com/2013/01/multi-armed-bandit-experiments.html\#:~:text=Google\%20Analytics\%20uses\%20a\%20multi,updated\%20as\%20the\%20experiment\%20progresses}{here}.}
Suppose that we currently have a website with a known conversion rate
of $p_{0}=0.05$.\footnote{The conversion rate is defined as the percentage of users who have
completed a desired action, e.g., clicking an ad.} We would like to experiment with a new version of the website whose
conversion rate, $p$, is unknown. Let $\tilde{Y}_{i}\sim\textrm{Bernoulli}(p)$
denote the outcome variable under the new website. As our setup normalizes
the reward from the known option to $0$, we redefine the outcomes
as $Y_{i}=(\tilde{Y}_{i}-p_{0})/\sqrt{p_{0}(1-p_{0})}$.\textcolor{blue}{{}
}Though $Y_{i}$ is not normally distributed, Section \ref{sec:General-parametric-models}
shows that the asymptotically sufficient statistics, $x(t),q(t)$,
are the same as in the normal setting with $\sigma^{2}=1$, and the
optimal policies also remain unchanged.\textcolor{blue}{{} }We report
results for different sample sizes $n$. For comparison, the blog
example used $n=6600$.
For this illustration, we apply the minimax risk criterion, and compare
the minimax optimal estimator with Thompson sampling (TS) and MOSS
(see Section \ref{subsec:Comparison-with-existing}). For TS we employ
a beta-prior centered at $p_{0}$, with the prior variance optimally
tuned to minimize max risk.\footnote{The Google Analytics example employed TS updated every 100 observations.}
For MOSS, we employ two versions: the first, a textbook implementation
as in \citet{lattimore2020bandit}, and the second, an optimally tuned
version as described in Section \ref{subsec:Comparison-with-existing},
with $\gamma$ chosen to minimize max-risk. Figure \ref{fig:Illustration 1},
Panel A displays the frequentist risk profiles of the different policies,
for various values of rescaled mean rewards $\mu=(p-p_{0})\cdot\sqrt{p_{0}(1-p_{0})/n}$,
when $n=5000$ (this equivalent to a range of $[0.027,0.073]$ for
$p$). By way of comparison, the Google Analytics example set $p=0.4$,
which corresponds to $\mu=-3$ in the plot. Compared to the optimal
policy, the minimax risks of TS and the standard MOSS algorithm are
substantially higher, by about 80\% and 110\% respectively. On the
other hand, the optimally tuned MOSS comes within 7-10\% of the minimax
lower bound. These relationships are stable over $n$ as Panel B of
same figure illustrates.
\begin{figure}
\includegraphics[height=5cm]{Code/minimax_risk_bernoulli_N5000_p05}~\includegraphics[height=5cm]{Code/Minimax_risk_vs_N_Bernoulli_p05}~
\begin{tabular}{>{\centering}p{7.5cm}>{\centering}p{7.5cm}}
{\scriptsize$\ $A: Risk profiles of various policies} & {\scriptsize$\ \ $B: Minimax risk vs n}\tabularnewline
\end{tabular}
\begin{raggedright}
{\scriptsize Note: Panel A shows the frequentist risk profiles of various
policies under $n=5000$. The x-axis represents the scaled mean $\mu=(p-p_{0})\cdot\sqrt{p_{0}(1-p_{0})/n}$
with $p_{0}=0.05$. Panel B shows how the minimax risk of the various
policies changes with $n$. For reference, the minimax lower bound
is $0.373$.}{\scriptsize\par}
\par\end{raggedright}
\caption{Empirical illustration - one-armed bandit\label{fig:Illustration 1}}
\end{figure}
\subsection{Two-armed bandits\label{subsec:Two-armed-bandits}}
The second illustration is based on experiments conducted by The Washington
Post for selecting between two different images for the headline of
a news article. The goal was to choose the one with the highest click-through
rate (CTR).\footnote{More information on the experiments can be found \href{https://web.archive.org/web/20161013134841/https://developer.washingtonpost.com/pb/blog/post/2016/02/08/bandito-a-multi-armed-bandit-tool-for-content-testing/}{here}.}
Let $p_{0},p_{1}$ denote the CTRs for the two proposals. For this
illustration we employ a Bayesian approach with an independent Gaussian
prior $p_{k}\sim\mathcal{N}(p_{\textrm{ref}},\sigma_{\textrm{ref}}^{2}\nu^{2}/n)$
for $k\in\{0,1\}$, where $\sigma_{\textrm{ref}}:=p_{\textrm{ref}}(1-p_{\textrm{ref}})$
and $n$ is the number of periods of experimentation. In practice,
one would like to set $p_{\textrm{ref}}$ and $\nu^{2}$ based on
prior knowledge of the distribution of CTRs across all the news articles.
In the absence of this information, we set $p_{\textrm{ref}}=0.175$,
which is a typical CTR for media websites, along with $\nu=5$, and
vary $n$ between $1000$ and $5000$. When $n=2500$, our choice
implies that the 95\% range for the prior is $[0.1,0.25]$. For comparison,
in the Washington Post study, the actual CTRs turned out to be $0.117$
and $0.246$. Let $\tilde{Y}^{(k)}\sim\textrm{Bernoulli}(p_{k})$
denote the outcomes (i.e., clicks) under the options $k\in\{0,1\}$;
we rescale them to $Y^{(k)}=(\tilde{Y}^{(k)}-p_{\textrm{ref}})/\sigma_{\textrm{ref}}$.
Section \ref{sec:General-parametric-models} shows that the asymptotically
sufficient statistics $\{x_{k}(t),q_{k}(t)\}_{k=0,1}$ are then the
same as in the normal setting with $\sigma_{k}^{2}=1$, and the optimal
policies also remain unchanged.
The set of algorithms considered are the optimal Bayes algorithm,
TS (with the Gaussian prior) and MOSS with both the textbook and tuned
implementations. For the tuned version, we set the tuning parameter
to the value that minimizes Bayes risk. Figure \ref{fig:Illustration 1-1},
Panel A plots the Bayes risk of these policies under different $n$.
As in the first illustration, while the risk of TS and the standard
MOSS algorithm is substantially worse that that of the optimal Bayes
policy, the optimally tuned MOSS comes within $15\%$ of the lower
bound on risk. The actual Washington Post study employed a standard
UCB algorithm without any tuning; this performs even worse than MOSS.
Panel B of the same figure plots the frequentist risk profiles of
these policies under $(p_{0},p_{1})=(p_{\textrm{ref}}-\mu\sigma_{\textrm{ref}}/\sqrt{n},p_{\textrm{ref}}+\mu\sigma_{\textrm{ref}}/\sqrt{n})$,
with $n=3000$, and as we vary $\mu$ between 0 and $10$. Setting
$\mu=10$ gives a value of $(p_{0},p_{1})$ that is roughly the same
as that actually observed in the Washington Post study. Atleast for
this class of mean reward values, it is seen that the optimal Bayes
policy uniformly dominates all the existing algorithms.
\begin{figure}
\includegraphics[height=5cm]{Code/Bayes_risk_vs_N_2_arms}~\includegraphics[height=5cm]{Code/risk_profile_2_arms}~
\begin{tabular}{>{\centering}p{7.5cm}>{\centering}p{7.5cm}}
{\scriptsize$\ $A: Bayes risk vs n} & {\scriptsize$\ \ $B: Frequentist risk profiles}\tabularnewline
\end{tabular}
\begin{raggedright}
{\scriptsize Note: Panel A shows the Bayes risk of the different algorithms
under various values of $n$. Panel B shows the risk profiles of the
various policies under $(p_{0},p_{1})\equiv(p_{\textrm{ref}}-\mu\sigma_{\textrm{ref}}/\sqrt{n},p_{\textrm{ref}}+\mu\sigma_{\textrm{ref}}/\sqrt{n})$
when $n=3000$, and we we vary $\mu$ between $0$ and $10$.}{\scriptsize\par}
\par\end{raggedright}
\caption{Empirical illustration - two-armed bandits\label{fig:Illustration 1-1}}
\end{figure}
\subsubsection{Implementation details}
We employ Algorithm 1 with $\Delta t=0.01$, $B=2000$ and $M=50$.\footnote{Setting $M=1$ is also fine and does not make much of a difference
in practice.} For the prediction model, we employ Random Forest (RF) as it is relatively
insensitive to tuning parameter selection.\footnote{We use 250 trees and left $\textrm{mtry}$ at the default value, but
changing these did not change the results.} As an alternative, MARS (multivariate adaptive regression splines)
delivers essentially the same results, but requires more fine-tuning.
In running the RF algorithm, we find that better predictive performance
(in terms of achieving lower prediction error with fewer $B$) could
be achieved by using $\{\mu_{k}(\cdot),q_{k}(\cdot)\}_{k},\mu^{\max}(\cdot)$
as inputs instead of $\{x_{k}(\cdot),q_{k}(\cdot)\}_{k}$; the former
is of course just a nonlinear transformation of the latter.
\section{General parametric models\label{sec:General-parametric-models}}
We now relax the Gaussian assumption, and suppose that rewards are
distributed according to some parametric model $P_{\theta}$, with
$\theta$ unknown. In this setting, a dynamic-programming solution
to the optimal Bayes policy generally involves a state space of dimension
$O(n)$. However, we show that it is possible to reduce this asymptotically
to just two state variables per arm (apart from time): the number
of times the arm has been pulled, and the score process, i.e., the
cumulative sum of scores scaled by $n^{-1/2}$, corresponding to the
distribution of rewards for that arm. All our results previously derived
for Gaussian models then continue to apply after simply reinterpreting
$x_{k}(t)$ from before as the score process. Underlying these claims
is a posterior approximation result that states that the posterior
density of the parametric model can be uniformly approximated, at
every point in time, by that from a Gaussian model.
For the rest of this section, we focus on the one-armed bandit for
simplicity. We start by assuming $\theta$ to be scalar to simplify
notation, but the vector case (discussed in Section \ref{subsec:Vector-valued})
does not otherwise present any new conceptual difficulties. The mean
rewards are denoted by $\mu(\theta)\equiv\mathbb{E}_{P_{\theta}}[X]$.
As in \citet{hirano2009asymptotics}, we focus on local perturbations
of the form $\{\theta_{n,h}\equiv\theta_{0}+h/\sqrt{n}:h\in\mathbb{R}\}$,
where $\theta_{0}$ is a reference parameter, chosen such that $\mu(\theta_{0})=0$.
This induces diffusion asymptotics. Indeed, under these perturbations,
$\mu_{n}(h):=\mu(\theta_{n,h})\approx\dot{\mu}_{0}h/\sqrt{n}$, where
$\dot{\mu}_{0}:=\mu^{\prime}(0)$. If instead, $\mu(\theta_{0})\neq0$,
the asymptotic risk is $0$ under all the policies considered here,
including TS, UCB and our PDE based proposals. Focusing on $\mu(\theta_{0})=0$
thus ensures that we are comparing policies under the hardest instances
of the bandit problem. For Bayesian analysis, we place a `non-negligible'
prior, $M_{0}$, on the local parameter $h$. In practice, this simply
involves translating a given prior on $\theta$ to one around $h$.
Let $\nu:=\nu_{1}\times\nu_{2}$, where $\nu_{1}$ is a dominating
measure for $\{P_{\theta}:\theta\in\mathbb{R}\}$ and $\nu_{2}$ is
a dominating measure for the prior $M_{0}$ on $h$. Define $p_{\theta}=dP_{\theta}/d\nu$,
$m_{0}=dM_{0}/d\nu$ (in the sequel, we shorten the Radon-Nikodym
derivative $dP/d\nu$ to just $dP$). Also, let $P_{n,h}$ denote
the joint probability measure over the stacked rewards $\bm{y}_{n}:=\{Y_{i}\}_{i=1}^{n}$.
We assume $\{P_{\theta}:\theta\in\mathbb{R}\}$ is quadratic mean
differentiable (qmd), i.e., there exists a score $\psi(\cdot)\in L^{2}(P_{\theta_{0}})$
such that
\begin{equation}
\int\left[\sqrt{p_{\theta_{0}+h}}-\sqrt{p_{\theta_{0}}}-\frac{1}{2}h\psi\sqrt{p_{\theta_{0}}}\right]^{2}d\nu=o(\vert h\vert^{2}).\label{eq:QMD}
\end{equation}
Among the many examples of qmd families are the Gaussian, Poisson,
and Bernoulli distributions, along with their shifted versions.\footnote{As we set the mean rewards from the known arm to $0$, many of these
distributions, including the Bernoulli, have to be shifted by a constant.
See Section \ref{sec:Computation-and-simulations} for an illustration.} The information matrix is $I:=\mathbb{E}_{P_{\theta_{0}}}\left[\psi^{2}\right]$
and we set $\sigma^{2}:=I^{-1}$. In addition, for $q\in[0,1]$, define
\[
x_{nq}:=\frac{\sigma^{2}}{\sqrt{n}}\sum_{i=1}^{\left\lfloor nq\right\rfloor }\psi(Y_{i})
\]
as the (normalized) score process over $q$.
\subsection{Heuristics\label{subsec:Heuristics}}
Our key assertion is that the posterior density of $h$ at time $t$
can be approximately characterized using just 2 state variables: the
number of times the arm has been pulled, $q(t):=n^{-1}\sum_{j=1}^{\left\lfloor nt\right\rfloor }\mathbb{I}(A_{j}=1)$,
and the score process over $t$, $x(t):=x_{nq(t)}$. We now provide
some intuition behind this. The ideas introduced here are applicable
more broadly to any sequential experiment.
In the one-armed bandit setting, if the arm is pulled $q$ times we
will have observed the first $q$ elements of the stack $\bm{y}_{n}$,
denoted ${\bf y}_{nq}:=\{Y_{i}\}_{i=1}^{\left\lfloor nq\right\rfloor }$.
After $q$ pulls, the log-likelihood ratio process under the local
alternative $h$ is
\begin{align*}
\hat{\varphi}(h;q) & =\ln\frac{dP_{\theta_{0}+h^ {}/\sqrt{n}}}{dP_{\theta_{0}^ {}}}\left({\bf y}_{nq}\right):=\sum_{i=1}^{\left\lfloor nq\right\rfloor }\ln\frac{dP_{\theta_{0}+h/\sqrt{n}}}{dP_{\theta_{0}^ {}}}\left(Y_{i}\right).
\end{align*}
It may appear odd that the likelihood-ratio does not feature the past
actions, which are random, nor does it depend on the policy rule.
Note, however, that given any (possibly randomized) policy, the probability
of choosing an action depends only on the past outcomes, and is therefore
independent of $h$. Hence, these probabilities drop out of the likelihood-ratio.\footnote{We can also interpret this as a consequence of the strong likelihood
principle (see, e.g., \citealp[Chapter 7]{berger2013statistical}):
the likelihood-ratio of the data following $q$ pulls of the arm depends
solely on ${\bf y}_{nq}$, and the exact procedure taken to reach
it is immaterial.} In Appendix \ref{subsec:Supporting-lemmas-for}, we show that (\ref{eq:QMD})
implies the important Sequential Local Asymptotic Normality (SLAN)
property: for any given $h\in\mathbb{R}$,
\begin{equation}
\hat{\varphi}(\bm{h};q)=\frac{h}{\sigma^{2}}x_{nq}-\frac{q}{2\sigma^{2}}h^{2}+o_{P_{n,\theta_{0}}}(1),\ \textrm{uniformly over }q.\label{eq:LAN}
\end{equation}
The SLAN property, which appears to be new in its current form, extends
the usual Local Asymptotic Normality (LAN) to sequential data.\footnote{Previously, an abstract version of it was stated as an assumption
for analyzing sequential experiments of the optimal stopping kind
in \citet[Chapter 13]{le1986asymptotic}.}
The DM employs a sampling rule $\{\pi_{j}\}_{j}\equiv\{\pi_{\left\lfloor nt\right\rfloor }\}_{t}$
that prescribes the probability of pulling the arm at period $t$,
given the information set, $\mathcal{F}_{t}$, consisting of all the
actions and rewards until that time; formally, $\mathcal{F}_{t}$
is the $\sigma$-algebra generated by $\xi_{t}\equiv\{\{A_{j}\}_{j=1}^{\left\lfloor nt\right\rfloor },\{Y_{i}\}_{i=1}^{\left\lfloor nq(t)\right\rfloor }\}$.
Clearly, $\textrm{dim}(\mathcal{F}_{t})=n(t+q(t))$, so it is very
large and increasing in $n,t$. However, (\ref{eq:LAN}) suggests
a way to reduce this. Observe that if the rewards were Gaussian, the
log-likelihood ratio would have been exactly
\[
\tilde{\varphi}(h;q):=\frac{h}{\sigma^{2}}x_{nq}-\frac{q}{2\sigma^{2}}h^{2},
\]
and the sufficient statistics would just be $x_{nq},q,t$. But by
(\ref{eq:LAN}), the true likelihood-ratio is close to that obtained
under Gaussian rewards anyway as $n\to\infty$.
The precise argument relies on the posterior. By Lemma \ref{Lemma 1}
in Appendix \ref{subsec:Supporting-lemmas-for}, the posterior density,
$p_{}(\cdot\vert\mathcal{F}_{t})$, of $h$ depends only on ${\bf y}_{nq(t)}$,
and is given by
\begin{align}
p_{n}(h\vert\mathcal{F}_{t})=p_{n}(h\vert{\bf y}_{nq(t)}) & \propto\left[\prod_{i=1}^{\left\lfloor nq(t)\right\rfloor }p_{\theta_{0}+h/\sqrt{n}}(Y_{i})\right]\cdot m_{0}(h)\nonumber \\
& \equiv\left[\exp\left\{ \hat{\varphi}(h;q(t))\right\} dP_{nq(t),\theta_{0}}({\bf y}_{nq(t)})\right]\cdot m_{0}(h),\label{eq:True posterior}
\end{align}
where $dP_{nq,\theta_{0}}({\bf y}_{nq}):=\prod_{i=1}^{\left\lfloor nq\right\rfloor }p_{\theta_{0}}(Y_{i})\ \forall\ q\in[0,1]$.
Replacing $\hat{\varphi}(\cdot;\cdot)$ with $\tilde{\varphi}(\cdot;\cdot)$,
the SLAN property (\ref{eq:LAN}) suggests that the likelihood at
time $t$ - i.e.\! the term within $[\cdot]$ brackets in (\ref{eq:True posterior})
- can be uniformly approximated over all possible realizations of
$q(t)$ by a new likelihood, the density of the `tilted' measure $\Lambda_{nq(t),h}({\bf y}_{nq(t)})$,
defined as
\begin{equation}
d\Lambda_{nq,h}({\bf y}_{nq})=\exp\left\{ \tilde{\varphi}(h;q)\right\} dP_{nq,\theta_{0}}({\bf y}_{nq})\ \forall\ q\in[0,1].\label{eq:tilted measure}
\end{equation}
Replacing the actual likelihood in (\ref{eq:True posterior}) with
this approximation, we obtain an approximate posterior density $\tilde{p}_{n}(h\vert{\bf y}_{nq(t)})$,
where for any $q\in[0,1]$,\footnote{Formally, $\tilde{p}_{n}(h\vert{\bf y}_{nq})$ is defined via disintegration
of the product measure $d\Lambda_{nq,h}({\bf y}_{nq})\cdot m_{0}(h)$;
see the proof of Lemma \ref{Lem: approximation of posteriors} in
Appendix \ref{subsec:Supporting-lemmas-for}.}
\begin{align}
\tilde{p}_{n}(h\vert{\bf y}_{nq})\equiv\tilde{p}_{n}(h\vert x_{nq},q) & \propto d\Lambda_{nq,h}({\bf y}_{nq})\cdot m_{0}(h)\nonumber \\
& \propto\tilde{p}_{q}(x_{nq}\vert h)\cdot m_{0}(h);\quad\tilde{p}_{q}(\cdot\vert h)\equiv\mathcal{N}(\cdot\vert qh,q\sigma^{2}).\label{eq:posterior - general parametric models}
\end{align}
In Appendix \ref{subsec:Supporting-lemmas-for}, we show that the
total variation distance between $p_{n}(\cdot\vert{\bf y}_{nq})$
and $\tilde{p}_{n}(\cdot\vert{\bf y}_{nq})$ converges to $0$ uniformly
over $q\in[0,1]$. Hence, the true posterior can be approximated arbitrarily
well by one that is obtained under Gaussian rewards.
\subsection{Formal results\label{subsec:Formal-results}}
Define $s:=(x,q,t)$, $\mu^{+}(s):=\dot{\mu}_{0}\tilde{\mathbb{E}}\left[\left.h\mathbb{I}(\dot{\mu}_{0}h\ge0)\right|s\right]$,
$\mu(s):=\dot{\mu}_{0}h(s)$ and $h(s):=\tilde{\mathbb{E}}\left[\left.h\right|s\right]$,
where $\tilde{\mathbb{E}}[\cdot\vert{\bf y}_{nq}]\equiv\tilde{\mathbb{E}}[\cdot\vert s]$
is the expectation corresponding to the approximate posterior density
$\tilde{p}_{n}(\cdot\vert{\bf y}_{nq})\equiv\tilde{p}_{n}(\cdot\vert x_{nq},q)$.
It will be shown that the minimal asymptotic Bayes risk in the parametric
regime is again characterized by (\ref{eq:PDE optimal bayes risk}),
but the infinitesimal generator is now modified slightly to\footnote{The difference is that $\partial_{x}f$ is multiplied by $h(s)$ as
opposed to $\mu(s)=\dot{\mu}_{0}h(s)$.}
\begin{equation}
L[f]:=\partial_{q}f+h(s)\partial_{x}f+\frac{1}{2}\sigma^{2}\partial_{x}^{2}f.\label{eq:infinitesimal generator - parametric}
\end{equation}
We impose the following assumptions:
\begin{asm1} (i) The class $\{P_{\theta}\}$ is differentiable in
quadratic mean as in (\ref{eq:QMD}). (ii) $\mathbb{E}_{P_{\theta_{0}}}[\exp\vert\psi(Y)\vert]<\infty$.
(iii) There exists $\dot{\mu}_{0}<\infty$ and $\delta_{n}\to0$ such
that $\sqrt{n}\mu_{n}(h)=\dot{\mu}_{0}h+\delta_{n}\vert h\vert^{2}\ \forall\ h$.
(iv) The support of $m_{0}(\cdot)$ is a compact set $\{h:\vert h\vert\le\Gamma\}$
for some $\Gamma<\infty$. (v) $\mu(\cdot)$ and $\mu^{+}(\cdot)$
are H{\"o}lder continuous. Additionally, $\sup_{s}\varpi(s)\le C<\infty$.
\end{asm1}
Assumptions 1(i), (iii) and (v) are standard. Assumption 1(ii) is
restrictive, but is related to the fact $\Lambda_{nq,h}$ approximates
the true likelihood rather coarsely when $h$ is large. One could
consider replacing $\exp\left\{ \tilde{\varphi}(h;q)\right\} $ in
its definition with $g(\tilde{\varphi}(h;q))$, where $g(z)=\exp(z)+o(z^{3})$
for small $z$ and bounded for large $z$, e.g., $g(z)=\min\{2,\max\{1+z+z^{2}/2,0\}\}$.
We conjecture that Assumption 1(ii) could then be weakened to $\mathbb{E}_{P_{\theta_{0}}}\left[\vert\psi(Y)\vert^{3}\right]<\infty$.
Assumption 1(iv), which is also employed in \citet[Proposition 6.4.4]{le2000asymptotics},
requires the prior to have a compact support. It is possible to drop
this assumption under some additional conditions, e.g., if the prior
has finite $1+\alpha$ moments, $\alpha>0$, and Assumption 1(iii)
is strengthened to $\vert\mu(P_{\theta_{0}+h})\vert\le C\vert h\vert\ \forall\ h$.
Assumptions 1(ii) \& (iv) are therefore not the most general possible,
but they lead to relatively transparent proofs.
For the theorem below, let $\Pi$ denote the class of all policies
sequentially measurable wrt $\{\mathcal{F}_{j}\}_{j}$, and $\Pi^{\mathcal{S}}\subset\Pi$
the subset of it consisting of policies that depend only on $s=(x,q,t)$.
For a fixed $n$ and $\pi\in\Pi$, the ex-ante Bayes risk is $V_{\pi,n}(0)=\mathbb{E}_{({\bf y}_{n},h)}\left[\sum_{j=1}^{n}R(Y_{j},\pi_{j},h)\right]$,
where $\mathbb{E}_{({\bf y}_{n},h})[\cdot]$ is the expectation under
the joint density $\left\{ \prod_{i=1}^{n}p_{\theta_{0}+h/\sqrt{n}}(Y_{i})\right\} \cdot m_{0}(h).$
The minimal ex-ante Bayes risk is $V_{n}^{*}(0)=\inf_{\pi\in\Pi_{\mathcal{}}}V_{\pi,n}(0)$,
and we also define $V_{n}^{\mathcal{S}*}(0):=\inf_{\pi\in\Pi_{\mathcal{}}^{\mathcal{S}}}V_{\pi,n}(0)$.
Lastly, $\pi_{\Delta t}^{*}$ is the optimal piece-wise constant policy
with $\Delta t$ increments as in Section \ref{subsec:Optimal-and-approximately}.
\begin{thm} \label{Thm: General parametric families}Suppose Assumption
1 holds. Then: (i) $\lim_{n\to\infty}\left|V_{n}^{*}(0)-V_{n}^{\mathcal{S}*}(0)\right|=0$.
(ii) $\textrm{\ensuremath{\lim}}_{n\to\infty}V_{n}^{*}(0)=V^{*}(0)$,
where $V^{*}(\cdot)$ solves PDE (\ref{eq:PDE optimal bayes risk})
with the infinitesimal generator (\ref{eq:infinitesimal generator - parametric}).
(iii) If, further, $\mu(\cdot)$, $\mu^{+}(\cdot)$ are Lipschitz
continuous, $\lim_{n\to\infty}\vert V_{\pi_{\Delta t}^{*},n}(0)-V^{*}(0)\vert\lesssim\Delta t{}^{1/4}$
for any fixed $\Delta t$.\end{thm}
Part (i) states that it is sufficient to restrict attention to just
3 state variables $s=(x,q,t)$. Part (ii) asserts that the minimal
Bayes risk is characterized by PDE (\ref{eq:PDE optimal bayes risk}),
while part (iii) implies piece-wise constant policies can attain this
bound.
\subsection{Vector valued $\theta$\label{subsec:Vector-valued}}
The vector case can be analyzed in the same manner as the scalar setting,
so we only describe the results. Let $\psi(\cdot)$ denote the score
function, $\Sigma^{-1}=\mathbb{E}_{P_{\theta_{0}}}\left[\psi\psi^{\intercal}\right]$
the information matrix, and $x(t)=n^{-1/2}\sum_{i=1}^{\left\lfloor nq(t)\right\rfloor }\Sigma\psi(Y_{i})$,
the normalized score process. The asymptotically sufficient state
variables are still $s(t)=(x(t),q(t),t)$. Given a prior $m_{0}(\cdot)$
on $h$, the approximate posterior density is $\tilde{p}_{n}(h\vert x,q)\propto\mathcal{N}(x\vert qh,q\Sigma)\cdot m_{0}(h)$.
Define $h(s)=\tilde{\mathbb{E}}\left[\left.h\right|s\right]$, $\mu^{+}(s)=\mathbb{\tilde{E}}\left[\left.\dot{\mu}_{0}^{\intercal}h\mathbb{I}(\dot{\mu}_{0}^{\intercal}h\ge0)\right|s\right]$
and $\mu(s)=\dot{\mu}_{0}^{\intercal}h(s)$, where $\tilde{\mathbb{E}}[\cdot\vert s]$
is the expectation corresponding to $\tilde{p}_{n}(\cdot\vert x,q)$
and $\dot{\mu}_{0}:=\nabla\mu(\theta_{0})$. With these definitions,
the minimal Bayes risk is still characterized by PDE (\ref{eq:PDE optimal bayes risk}),
but with the infinitesimal generator now being
\begin{equation}
L[f]:=\partial_{q}f+h(s)^{\intercal}D_{x}f+\frac{1}{2}\textrm{Tr}\left[\Sigma\cdot D_{x}^{2}f\right].\label{eq:vector infinitesimal generator}
\end{equation}
\subsection{Lower bound on minimax risk\label{subsec:Lower-bound-on}}
Let $V_{n,\pi}(0;h)$ denote the fixed-$n$ frequentist risk of policy
$\pi$ when the local parameter is $h$, and write $V^{*}(0)$ as
$V^{*}(0;m_{0})$ to make explicit its dependence on the prior $m_{0}$.
In Appendix \ref{sec:lower bounds on minimax risk}, we use Theorem
\ref{Thm: General parametric families} to derive a lower bound on
asymptotic minimax risk as
\begin{equation}
\lim_{n\to\infty}\inf_{\pi\in\Pi}\sup_{\vert h\vert\le\Gamma}V_{n,\pi}(0;h)\ge\sup_{m_{0}\in\mathcal{P}}V^{*}(0;m_{0})=\bar{V}^{*},\label{eq:minimax result - parametrics}
\end{equation}
where $\mathcal{P}$ is the set of all compactly supported distributions,
and $\bar{V}^{*}$ is just the asymptotic minimax risk in the Gaussian
setting as in (\ref{eq:def of minimax risk}). Proving the sharpness
of the lower bound (\ref{eq:minimax result - parametrics}) is more
involved, however, and left for future research.
\section{The non-parametric setting\label{sec:The-nonparametric-setting}}
Very often we do not have any a-priori information about the distribution
of the rewards. In this section, we show that our characterization
of Bayes and minimax risk also applies in such a non-parametric regime
after we replace the score process with the cumulative sum process
of the rewards. In short, there is no loss in simply pretending that
the outcomes are Gaussian.
Our formal analysis of the non-parametric regime follows \citet{van2000asymptotic}.
Let $\mathcal{P}$ denote the class of probability distributions with
bounded variance and dominated by some measure $\nu$. We then fix
a reference $P_{0}\in\mathcal{P}$, and surround it with various smooth
one-dimensional parametric sub-models, $\{P_{t,\bm{h}}:t\le\eta\}$,
whose score function is $\hm{h}$ and that pass through $P_{0}$ at
$t=0$ (i.e., $P_{0,\bm{h}}=P_{0}$). To obtain non-trivial risk bounds,
we suppose $\mu(P_{0})=0$, where $\mu(P):=\int xdP(x)$ denotes the
mean rewards under $P$. The rationale is akin to setting $\mu(\theta_{0})=0$
in the parametric setting: it focuses attention on the hardest instances
of the bandit problem. The formal definition of $\{P_{t,\bm{h}}:t\le\eta\}$
is given in Appendix \ref{subsec:Additional details for non-parametric},
we just note here that the only requirements on $\bm{h}$ are $\int\bm{h}dP_{0}=0$
and $\int\bm{h}^{2}dP_{0}<\infty$. The set of all such functions
$\bm{h}$ is termed the tangent space $T(P_{0})$.
Denote $\left\langle f_{1},f_{2}\right\rangle =\int f_{1}f_{2}dP_{0}$.
For any regular functional $\mu(\cdot)$ on $\mathcal{P}$ (and not
just the mean), we say that $\psi(\cdot)$ is the efficient influence
function corresponding to it if
\begin{equation}
\frac{\mu(P_{t,\bm{h}})-\mu(P_{0})}{t}-\left\langle \psi,\bm{h}\right\rangle =\frac{\mu(P_{t,\bm{h}})}{t}-\left\langle \psi,\bm{h}\right\rangle =o(t)\ \forall\ \bm{h}\in T(P_{0}).\label{eq:influence function}
\end{equation}
For mean-estimation, $\psi(x)=x$. Now, (\ref{eq:influence function})
implies $\mu(P_{1/\sqrt{n},\bm{h}})\approx\left\langle \psi,\bm{h}\right\rangle /\sqrt{n}$.
This suggests that for non-trivial notions of Bayes and minimax risk
under a $n^{-1/2}$ scaling of mean rewards, we should place `non-negligible'
priors on the set of probability distributions $\mathcal{P}_{n}:=\{P_{1/\sqrt{n},\bm{h}}:\bm{h}\in T(P_{0})\}$.\footnote{Note that priors in the non-parametric regime are probability distributions
over the space of candidate distributions for the rewards.} This is in turn equivalent to a prior, $\rho_{0}$ (say), on $T(P_{0})$.
We impose two restrictions on $\rho_{0}$. First, while $T(P_{0})$
is infinite dimensional, $\rho_{0}$ should be supported on a finite
dimensional sub-space of it (i.e., on a sub-space spanned by a finite
number of basis functions from $T(P_{0})$). Second, it should be
possible to decompose $\rho_{0}=m_{0}\times\lambda$, where $m_{0}$
is a prior on $h_{0}:=\left\langle \psi,\bm{h}\right\rangle $ and
$\lambda$ is a prior over the part of $T(P_{0})$ that is orthogonal
to $\psi$.
The first restriction on $\rho_{0}$ is for mathematical convenience,
but also follows the standard approach of defining minimax risk through
finite dimensional sub-models \citep[Chapter 25]{van2000asymptotic}.
As for the second restriction, the rationale behind product priors
is two-fold: First, they suffice for obtaining a lower bound on minimax
risk. Second, and more importantly, our welfare criterion depends
on $\hm{h}$ only through $h_{0}$, which determines the mean reward.
Invariance considerations would then suggest restricting attention
to policies that deliver the same frequentist risk for any $\bm{h}_{1},\bm{h}_{2}\in T(P_{0})$
such that $\mu(\bm{h}_{1})=\mu(\bm{h}_{2})$. Product priors achieve
this as they ensure the posterior of $h_{0}$ is independent of $\lambda$,
the component of the prior placing beliefs over the part of $\bm{h}$
that is orthogonal to mean-estimation. Incidentally, the above considerations
also apply to parametric models with vector $\theta$. Using product
priors there then leads to a further dimension reduction\textcolor{blue}{:
}we can replace the score process, $x(t)$, with its univariate projection
$\dot{\mu}_{0}^{\intercal}\Sigma^{-1}x(t)$. See Appendix \ref{subsec:Heuristics-non-parametrics}
for the intuition.
While the focus in this paper is on mean rewards, the theory itself
is more general and applies to any regular functional $\mu(\cdot)$
of $\mathcal{P}$. For instance, $\mu(\cdot)$ could be the median,
in which case the risk criterion would be the cumulative sum of median
outcomes. All our results go through unchanged after simply reinterpreting
$\psi(\cdot)$ as the efficient influence function corresponding to
$\mu(\cdot)$.
Let $V_{n}^{*}(0;\rho_{0})$ denote the minimal Bayes risk in the
one-armed bandit setting, when the prior is $\rho_{0}=m_{0}\times\lambda$.
We show that $V_{n}^{*}(0;\rho_{0})$ converges to $V^{*}(0;m_{0})$,
where $V^{*}(\cdot;m_{0})$ solves PDE (\ref{eq:PDE optimal bayes risk})
under the prior $m_{0}$. The asymptotically sufficient state variables
are still $(x_{nq},q,t)$ as before, but $x_{nq}=n^{-1/2}\sigma^{2}\sum_{i=1}^{\left\lfloor nq\right\rfloor }\psi(Y_{i})$
is now the efficient influence function process, with $\sigma^{2}:=\textrm{Var}[P_{0}]$.
The intuition behind this result, and the assumptions required for
it, are described in Appendix \ref{subsec:Additional details for non-parametric}.
\begin{thm} \label{Thm: Non-parametric models}Suppose Assumption
2 in Appendix \ref{subsec:Additional details for non-parametric}
holds. Then:
(i) $\textrm{\ensuremath{\lim}}_{n\to\infty}V_{n}^{*}(0;\rho_{0})=V^{*}(0;m_{0})$.
(ii) If, further, $\mu(\cdot)$, $\mu^{+}(\cdot)$ are Lipschitz continuous,
$\lim_{n\to\infty}\vert V_{\pi_{\Delta t}^{*},n}(0;\rho_{0})-V^{*}(0;m_{0})\vert\lesssim\Delta t{}^{1/4}$
for any fixed $\Delta t$, where $V_{\pi_{\Delta t}^{*},n}(0;\rho_{0})$
is defined in Section \ref{subsec:Optimal-and-approximately}.\end{thm}
As with parametric models, Theorem \ref{Thm: Non-parametric models}
can be used to derive a lower bound on minimax risk. Let $V_{n,\pi}(0;\bm{h})$
denote the fixed $n$ (ex-ante) frequentist risk of a policy $\pi$
under $P_{1/\sqrt{n},\bm{h}}$. Suppose that $\mathbb{E}[\exp\vert Y\vert]<\infty$
and $\mathcal{P}$ is the set of all compactly supported $m_{0}$.
Then, Theorem \ref{Thm: Non-parametric models} implies
\begin{equation}
\sup_{I\in\mathbb{N}}\lim_{n\to\infty}\inf_{\pi\in\Pi}\sup_{\bm{h}\in\mathcal{H}_{I}}V_{n,\pi}(0;\bm{h})\ge\sup_{m_{0}\in\mathcal{P}}V^{*}(0;m_{0})=\bar{V}^{*},\label{eq:minimax result - non-parametrics}
\end{equation}
where $\sup_{\bm{h}\in\mathcal{H}_{I}}$ denotes the supremum over
all finite, $I$-dimensional subspaces, $H_{I}$, of the tangent space
$T(P_{0})$, with $I\in\mathbb{N}$. By \citet[Theorem 25.21]{van2000asymptotic},
the left hand side of (\ref{eq:minimax result - non-parametrics})
is the value of minimax risk. The right hand side of (\ref{eq:minimax result - non-parametrics})
is simply the lower bound on minimax risk under Gaussian rewards,
as in (\ref{eq:def of minimax risk}).
\section{Conclusion\label{sec:Conclusion}}
In this article, we derive sharp lower bounds for Bayes and minimax
risk of bandit algorithms under diffusion asymptotics and suggest
ways to numerically compute the corresponding optimal policies. Our
local asymptotic analysis of Bayes risk is substantially different
from existing approaches and is arguably more powerful, as it enables
us to rank various policies which were previously were indistinguishable
on the basis of their large-deviation regret properties. We show that
all bandit problems, be they parametric or non-parametric, are asymptotically
equivalent to Gaussian bandits. Furthermore, it is asymptotically
sufficient to restrict attention to just two state variables per arm.
For minimax risk, the paper only proves a lower bound. While we believe
the bound is tight, further work is needed to show this. The work
also raises a number of additional avenues for future research, a
few of which are discussed below:
\textit{Unknown $\sigma$.} A drawback of diffusion asymptotics, and
of first-order efficiency criteria more generally, is that replacing
unknown variances with consistent estimates has no effect on asymptotic
risk. One could in principle achieve optimal risk by (say) sampling
all arms equally for $\bar{n}:=n^{\rho}$ periods, $\rho\in(0,1)$,
obtaining estimates of $\sigma$, and applying the optimal policies
based on those estimates from $\bar{n}$ onwards. But in finite samples,
the choice of $\rho$ will matter and further work is needed to choose
this efficiently.
\textit{Other sequential experiments.} \citet{adusumilli2022minimax}
applies insights from this paper to derive the minimax optimal policy
for best-arm identification with two arms, while \citet{adusumilli2022Wald}
does the same for the problem of costly sampling.
\bibliographystyle{IEEEtranSN}
\bibliography{Optimal_sequential_policies}