Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
82,642 characters · 26 sections · 50 citation commands
Risk and optimal policies in bandit experiments
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 russo2017tutorial, dynamic pricing ferreira2018online, public health athey2021shared and economics 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 russo2017tutorial and references therein) and Upper Confidence Bound (UCB; 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., 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' (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}$ 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 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 (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 hirano2009asymptotics.
wager2021diffusion and 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 after scaling them by the minimax, $n^{-1/2}$, rate (see Section (ref)). This a major departure from the existing literature that, starting from 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 crandall1992user. The PDE machinery is indispensable because existing results (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)).
We demonstrate the equivalence of experiments by extending the posterior approximation method of 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 (russo2016simple; kasy2019adaptive). The discounted bandit problem has a rich history in economic applications, ranging from market pricing rothschild1974two to decision making in labor markets mortensen1986job. For discounted problems, the optimal Bayes policy can be characterized using Gittins indices (gittins1979bandit). However, except in simple instances, e.g., discrete state spaces, computing the Gittins index is difficult (see, lattimore2020bandit). Also, it does not apply beyond the discounted setting; the optimal Bayes policy in finite horizon settings is not an index policy (berry1985bandit). Here, we take a different route and characterize the optimal Bayes policy using PDEs.
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) 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 wager2021diffusion and 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)). 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) and (ref).
In what follows, we represent rewards using the so-called `stack-of-rewards model' (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) for a formal argument about the sufficiency of these variables). The scaling on $x_{k}(t)$ follows 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$, wager2021diffusion show that $\{x_{k}(\cdot),q_{k}(\cdot)\}_{k}$ evolve in the large $n$ limit according to the stochastic differential equations (SDEs)
where $\{W_{k}(\cdot)\}_{k}$ are independent one-dimensional Brownian motions, and $\pi_{k}(s_{t}):=\pi_{k}(s(t))$. While ((ref)) is convenient for heuristics, there is in fact no guarantee that the optimal policy possesses the requisite regularity properties for ((ref)) to formally hold. As it turns out, our formal results, in Section 3, do not rely on ((ref)).
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
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 (kasy2019adaptive). The latter is discussed in Appendix (ref).
Here we introduce asymptotic Bayes risk for bandit experiments.
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.}
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) in Appendix (ref) 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., 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)). 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
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)), 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)$)
Hence, up to a first order approximation, $V_{\pi}(s)$ satisfies the recursion
with the terminal condition $V_{\pi}(s)=0$ if $t=1$.
Now, Ito's lemma implies that
Thus, subtracting $V_{\pi}(s)$ from both sides of the recursion ((ref)) and dividing by $\Delta t$, we find that $V_{\pi}(\cdot)$ solves the PDE
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)), 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)), we obtain
As with PDE ((ref)), PDE ((ref)) 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.
In the context of PDE ((ref)), 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)) 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)) 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)) 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).
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
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\} $.
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)). Figure (ref) compares this with the corresponding minimal Bayes risk for one-armed bandits under Gaussian priors, obtained by solving PDE ((ref)). 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) 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.
Figure (ref) 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) 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) 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}$).
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, 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 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) 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) 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.
Following 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
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)) can be interchanged, so that
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)), 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.
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).
Equation ((ref)) 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 (crandall1992user).
In Section 2, we provided a heuristic derivation of PDE ((ref)). 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
In ((ref)), $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)) as a discrete approximation to PDE ((ref)). As such, it falls under the abstract framework of barles1991convergence for showing convergence to viscosity solutions. An application of their techniques proves the following result (the proof is in Appendix (ref)): Denote $\varpi(s):=\min\left\{ \mu^{+}(s)-\mu(s),\mu^{+}(s)\right\} $.
The assumptions are satisfied for Gaussian priors. Note also that the theorem is proved without appealing to ((ref)). In Appendix (ref) 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.
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)$:
where the operator $S_{\Delta t}[\phi](x,q)$ denotes the solution at $(x,q,\Delta t)$ of the linear second order PDE
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$.
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)$.
We provide two empirical illustrations of bandit experiments to show how our methods translate to real world practice. The first application solves PDE ((ref)) 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). 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 (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.}
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$.}
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) 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)). 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 lattimore2020bandit, and the second, an optimally tuned version as described in Section (ref), with $\gamma$ chosen to minimize max-risk. Figure (ref), 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.
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) 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), 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.
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.
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)) does not otherwise present any new conceptual difficulties. The mean rewards are denoted by $\mu(\theta)\equiv\mathbb{E}_{P_{\theta}}[X]$. As in 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
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) 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$.
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
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., 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), we show that ((ref)) implies the important Sequential Local Asymptotic Normality (SLAN) property: for any given $h\in\mathbb{R}$,
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 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)) 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)), 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) in Appendix (ref), the posterior density, $p_{}(\cdot\vert\mathcal{F}_{t})$, of $h$ depends only on ${\bf y}_{nq(t)}$, and is given by
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)) suggests that the likelihood at time $t$ - i.e.\! the term within $[\cdot]$ brackets in ((ref)) - 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
Replacing the actual likelihood in ((ref)) 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) in Appendix (ref).}
In Appendix (ref), 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.
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)), 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)$.}
We impose the following assumptions:
\begin{asm1} (i) The class $\{P_{\theta}\}$ is differentiable in quadratic mean as in ((ref)). (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 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).
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)), while part (iii) implies piece-wise constant policies can attain this bound.
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)), but with the infinitesimal generator now being
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), we use Theorem (ref) to derive a lower bound on asymptotic minimax risk as
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)). Proving the sharpness of the lower bound ((ref)) is more involved, however, and left for future research.
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 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), 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
For mean-estimation, $\psi(x)=x$. Now, ((ref)) 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 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) 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)) 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).
As with parametric models, Theorem (ref) 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) implies
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 van2000asymptotic, the left hand side of ((ref)) is the value of minimax risk. The right hand side of ((ref)) is simply the lower bound on minimax risk under Gaussian rewards, as in ((ref)).
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:
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.
Other sequential experiments. adusumilli2022minimax applies insights from this paper to derive the minimax optimal policy for best-arm identification with two arms, while adusumilli2022Wald does the same for the problem of costly sampling.