Learning to Optimize Via Posterior Sampling

Introduction.

We consider an optimization problem faced by an agent who is uncertain about how his actions influence performance. The agent selects actions sequentially, and upon each action observes a reward. A reward function governs the mean reward of each action. The agent represents his initial beliefs through a prior distribution over reward functions. As rewards are observed the agent learns about the reward function, and this allows him to improve his behavior. Good performance requires adaptively sampling actions in a way that strikes an effective balance between exploring poorly understood actions and exploiting previously acquired knowledge to attain high rewards. In this paper, we study a simple algorithm for selecting actions and provide finite time performance guarantees that apply across a broad class of models.

The problem we study has attracted a great deal of recent interest and is often referred to as the multi-armed bandit (MAB) problem with dependent arms. We refer to the problem as one of learning to optimize to emphasize its divergence from the classical MAB literature. In the typical MAB framework, there are a finite number of actions that are modeled independently; sampling one action provides no information about the rewards that can be gained through selecting other actions. In contrast, we allow for infinite action spaces and for general forms of model uncertainty, captured by a prior distribution over a set of possible reward functions. Recent papers have addressed this problem in cases where the relationship among action rewards takes a known parametric form. For example, Dani et al. , Abbasi-Yadkori et al. , Rusmevichientong and Tsitsiklis study the case where actions are described by a finite number of features and the reward function is linear in these features. Other authors have studied cases where the reward function is Lipschitz continuous , sampled from a Gaussian process , or takes the form of a generalized or sparse linear model.

Each paper cited above studies an upper confidence bound (UCB) algorithm. Such an algorithm forms an optimistic estimate of the mean-reward value for each action, taking it to be the highest statistically plausible value. It then selects an action that maximizes among these optimistic estimates. Optimism encourages selection of poorly-understood actions, which leads to informative observations. As data accumulates, optimistic estimates are adapted, and this process of exploration and learning converges toward optimal behavior.

We study an alternative algorithm that we refer to as posterior sampling. It is also also known as Thompson sampling and as probability matching. The algorithm randomly selects an action according to the probability it is optimal. Although posterior sampling was first proposed almost eighty years ago, it has until recently received little attention in the literature on multi-armed bandits. While its asymptotic convergence has been established in some generality , not much else is known about its theoretical properties in the case of dependent arms, or even in the case of independent arms with general prior distributions. Our work provides some of the first theoretical guarantees.

Our interest in posterior sampling is motivated by several potential advantages over UCB algorithms, which we highlight in Section 4.3. While particular UCB algorithms can be extremely effective, performance and computational tractability depends critically on the confidence sets used by the algorithm. For any given model, there is a great deal of design flexibility in choosing the structure of these sets. Because posterior sampling avoids the need for confidence bounds, its use greatly simplifies the design process and admits practical implementations in cases where UCB algorithms are computationally onerous. In addition, we show through simulations that posterior sampling outperforms various UCB algorithms that have been proposed in the literature.

In this paper, we make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. In particular, we show that while the regret of a UCB algorithm can be bounded in terms of the confidence bounds used by the algorithm, the Bayesian regret of posterior sampling can be bounded in an analogous way by any sequence of confidence bounds. In this sense, posterior sampling preserves many of the appealing theoretical properties of UCB algorithms without requiring explicit, designed, optimism. We show that, due to this connection, existing analysis available for specific UCB algorithms immediately translates to Bayesian regret bounds for posterior sampling.

Our second theoretical contribution is a Bayesian regret bound for posterior sampling that applies broadly and can be specialized to many specific model classes. Our bound depends on a new notion of dimension that measures the degree of dependence among actions. We compare our notion of dimension to the Vapnik-Chervonenkis dimension and explain why that and other measures of dimension used in the supervised learning literature do not suffice when it comes to analyzing posterior sampling.

The remainder of this paper is organized as follows. The next section discusses related literature. Section 3 then provides a formal problem statement. We describe UCB and posterior sampling algorithms in Section 4. We then establish in Section 5 a connection between them, which we apply in Section 6 to convert existing bounds for UCB algorithms to bounds for posterior sampling. Section 7 develops a new notion of dimension and presents Bayesian regret bounds that depend on it. Section 8 presents simulation results. A closing section makes concluding remarks.

Related Literature.

One distinction of results presented in this paper is that they center around Bayesian regret as a measure of performance. In the next subsection, we discuss this choice and how it relates to performance measures used in other work. Following that, we review prior results and their relation to results of this paper.

Several recent papers have established theoretical results on posterior sampling. One difference between this work and ours is that we focus on a different measure of performance. These papers all study the algorithm’s regret, which measures its cumulative loss relative to an algorithm that always selects the optimal action, for some fixed reward function. To derive these bounds, each paper fixes an uninformative prior distribution with a convenient analytic structure, and studies posterior sampling assuming this particular prior is used. With one exception , the focus is on the classical multiarmed bandit problem, where sampling one action provides no information about others.

Posterior sampling can be applied to a much broader class of problems, and one of its greatest strengths is its ability to incorporate prior knowledge in a flexible and coherent way. We therefore aim to develop results that accommodate the use of a wide range of models. Accordingly, most of our results allow for an arbitrary prior distribution over a particular class of mean reward functions. In order to derive meaningful results at this level of generality, we study the algorithm’s expected regret, where the expectation is taken with respect to the prior distribution over reward functions. This quantity is sometimes called the algorithm’s Bayesian regret. We find this to be a practically relevant measure of performance and find this choice allows for more elegant analysis. Further, as we discuss in Section 3, the Bayesian regret bounds we provide in some cases immediately yield regret bounds.

In addition, studying Bayesian regret reveals deep connections between posterior sampling and the principle of optimism in the face of uncertainty, which we feel provides new conceptual insight into the algorithm’s performance. Optimism in the face of uncertainty is a general principle and is not inherently tied to any measure of performance. Indeed, algorithms based on this principle have been shown to be asymptotically efficient in terms of both regret and Bayesian regret , to satisfy order optimal minimax regret bounds , to satisfy order optimal bounds on regret and Bayesian regret when the reward function is linear , and to satisfy strong bounds when the reward function is sampled from a Gaussian process prior . We take a very general view of optimistic algorithms, allowing upper confidence bounds to be constructed in an essentially arbitrary way based on the algorithm’s observations and possibly the prior distribution over reward functions.

2 Related Results.

Though it was first proposed in 1933, posterior sampling has until recently received relatively little attention. Interest in the algorithm grew after empirical studies demonstrated performance exceeding state-of-the-art methods. An asymptotic convergence result was established by May et al. , but finite time guarantees remain limited. The development of further performance bounds was raised as an open problem at the 2012 Conference on Learning Theory .

Three recent papers provide regret bounds for posterior sampling when applied to MAB problems with finitely many independent actions and rewards that follow Bernoulli processes. These results demonstrate that posterior sampling is asymptotically optimal for the class of problems considered. A key feature of the bounds is their dependence on the difference between the optimal and second-best mean-reward values. Such bounds tend not to be meaningful when the number of actions is large or infinite unless they can be converted to bounds that are independent of this gap, which is sometimes the case.

In this paper, we establish distribution-independent bounds. When the action space $\mathcal{A}$ is finite, we establish a finite time Bayesian regret bound of order $\sqrt{\left|\mathcal{A}\right|T\log T}$. This matches what is implied by the analysis of Agrawal and Goyal . However, our bound does not require actions are modeled independently, and our approach also leads to meaningful bounds for problems with large or infinite action sets.

Only one other paper has studied posterior sampling in a context involving dependent actions . That paper considers a contextual bandit model with arms whose mean-reward values are given by a $d$-dimensional linear model. The cumulative $T$-period regret is shown to be of order $\frac{d^{2}}{\epsilon}\sqrt{T^{1+\epsilon}}\ln(Td)\ln\frac{1}{\delta}$ with probability at least $1-\delta$. Here $\epsilon\in(0,1)$ is a parameter used by the algorithm to control how quickly the posterior distribution concentrates. The Bayesian regret bounds we will establish are stronger than those implied by the results of Agrawal and Goyal . In particular, we provide a Bayesian regret bound of order $d\sqrt{T}\ln T$ that holds for any compact set of actions. This is order–optimal up to a factor of $\ln T$ .

We are also the first to establish finite time performance bounds for several other problem classes. One applies to linear models when the vector of coefficients is likely to be sparse; this bound is stronger than the aforementioned one that applies to linear models in the absence of sparsity assumptions. We establish the the first bounds for posterior sampling when applied to generalized linear models and to problems with a general Gaussian prior. Finally, we establish bounds that apply very broadly and depend on a new notion of dimension.

Unlike most of the relevant literature, we study MAB problems in a general framework, allowing for complicated relationships between the rewards generated by different actions. The closest related work is that of Amin et al. , who consider the problem of learning the optimum of a function that lies in a known, but otherwise arbitrary set of functions. They provide bounds based on a new notion of dimension, but unfortunately this notion does not provide a bound for posterior sampling. Other work provides general bounds for contextual bandit problems where the context space is allowed to be infinite, but the action space is small (see, e.g., ). Our model captures contextual bandits as a special case, but we emphasize problem instances with large or infinite action sets, and where the goal is to learn without sampling every possible action.

A focus of our paper is the connection between posterior sampling and UCB approaches. We discuss UCB algorithms in some detail in Section 4. UCB algorithms have been the primary approach considered in the segment of the stochastic MAB literature that treats models with dependent arms. Other approaches are the knowledge gradient algorithm , forced exploration schemes for linear bandits , and exponential-weighting schemes .

There is an immense and rapidly growing literature on bandits with independent arms and on adversarial bandits. Theoretical work on stochastic bandits with independent arms often focuses on UCB algorithms or on the Gittin’s index approach . Bubeck and Cesa-Bianchi provide a review of work on UCB algorithms and on adversarial bandits. Gittins et al. cover work on Gittin’s indices and related extensions.

Since an initial version of this paper was made publicly available, the literature on the analysis of posterior sampling has rapidly grown. Korda et al. extend their earlier work to the case where reward distributions lie in the 1–dimensional exponential family. Bubeck and Liu combine the regret decomposition we derive in Section 5 with the confidence bound analysis of Audibert and Bubeck to tighten the bound provided in Section 6.1, and also consider a problem setting where the regret of posterior sampling is bounded uniformly over time. Li explores a connection between posterior sampling and exponential weighting schemes, and Gopalan et al. study the asymptotic growth rate of regret in problems with dependent arms.

Problem Formulation.

The $T$-period regret of a policy $\pi$ is the random variable defined by

This quantity is also called Bayes risk, or simply expected regret.

Measurability assumptions are required for the above expectations to be well-defined. In order to avoid technicalities that do not present fundamental obstacles in the contexts we consider, we will not explicitly address measurability issues in this paper and instead simply assume that functions under consideration satisfy conditions that ensure relevant expectations are well-defined.

All equalities between random variables in this paper hold almost surely with respect to the underlying probability space.

2 On Changing Action Sets.

Our stochastic model of action sets $\mathcal{A}_{t}$ is distinct relative to most of the multi-armed bandit literature, which assumes that $\mathcal{A}_{t}=\mathcal{A}$. This construct allows our formulation to address a variety of practical issues that are usually viewed as beyond the scope of standard multi-armed bandit formulations. Let us provide three examples.

Contextual Models. The contextual multi-armed bandit model is a special case of the formulation presented above. In such a model, an exogenous Markov process $X_{t}$ taking values in a set $\mathcal{X}$ influences rewards. In particular, the expected reward at time $t$ is given by $f_{\theta}(a,X_{t})$. However, this is mathematically equivalent to a problem with stochastic time-varying decision sets $\mathcal{A}_{t}$. In particular, one can define the set of actions to be the set of state-action pairs $\mathcal{A}:=\left\{\left(x,\,a\right):\,x\in\mathcal{A},\,a\in\mathcal{A}(x)\right\}$, and the set of available actions to be $\mathcal{A}_{t}=\left\{\left(X_{t},\,a\right):\,a\in\mathcal{A}(X_{t})\right\}$.

Cautious Actions. In some applications, one may want to explore without risking terrible performance. This can be accomplished by restricting the set $\mathcal{A}_{t}$ to conservative actions. Then, the instantaneous regret in our framework is the gap between the reward from the chosen action and the reward from the best conservative action. In many settings, the Bayesian regret bounds we will establish for posterior sampling imply that the algorithm either attains near-optimal performance or converges to a point where any better decision is unacceptably risky.

for some scalar constant $\alpha>0$, we can then select an optimal cautious action given $\theta$ by solving $\max_{a\in\mathcal{A}_{t}}\left\langle a,\theta\right\rangle$, which is equivalent to

This problem is computationally tractable, which accommodates efficient implementation of posterior sampling.

Adaptive Adversaries. Consider a model in which rewards are influenced by the choices of an adaptive adversary. At each time period, the adversary selects an action $A^{-}_{t}$ from some set $\mathcal{A}^{-}$ based on past observations. The agent observes this action, responds with an action $A^{+}_{t}$ selected from a set $\mathcal{A}^{+}$, and receives a reward that depends on the pair of actions $(A_{t}^{+},A_{t}^{-})$. This fits our framework if the action $A_{t}$ is taken to be the pair $(A^{+}_{t},A^{-}_{t})$, and the set of actions available to the agent is $\mathcal{A}_{t}=\{(a,A^{-}_{t})|a\in\mathcal{A}^{+}\}$.

Algorithms.

We will establish finite time performance bounds for posterior sampling by leveraging prior results pertaining to UCB algorithms and a connection we will develop between the two classes of algorithms. To set the stage for our analysis, we discuss the algorithms in this section.

As a concrete example, consider Algorithm 1, proposed by Auer et al. to address MAB problems with a finite number of independent actions. For such problems, $\mathcal{A}_{t}=\mathcal{A}$, $\theta$ is a vector with one independent component per action, and the reward function is given by $f_{\theta}(a)=\theta_{a}$. The algorithm begins by selecting each action once. Then, for each subsequent time $t>|\mathcal{A}|$, the algorithm generates point estimates of action rewards, defines upper confidence bounds based on them, and selects actions accordingly. For each action $a$, the point estimate $\hat{\theta}_{t}(a)$ is taken to be the average reward obtained from samples of action $a$ taken prior to time $t$. The upper confidence bound is produced by adding an “uncertainty bonus” $\beta\sqrt{\log t/N_{t}(a)}$ to the point estimate, where $N_{t}(a)$ is the number of times action $a$ was selected prior to time $t$ and $\beta$ is an algorithm parameter generally selected based on reward variances. This uncertainty bonus leads to an optimistic assessment of expected reward when there is uncertainty, and it is this optimism that encourages exploration that reduces uncertainty. As $N_{t}(a)$ increases, uncertainty about action $a$ diminishes and so does the uncertainty bonus. The $\log t$ term ensures that the agent does not permanently rule out any action, which is important as there is always some chance of obtaining an overly pessimistic estimate by observing an unlikely sequence of rewards.

Our second example treats a linear bandit problem. Here we assume $\theta$ is drawn from a normal distribution $N(\mu_{0},\Sigma_{0})$ but without assuming that the covariance matrix is diagonal. We consider a linear reward function $f_{\theta}(a)=\langle\phi(a),\theta\rangle$ and assume the reward noise $R_{t}-f_{\theta}(A_{t})$ is normally distributed and independent from $(H_{t},A_{t},\theta)$. One can show that, conditioned on the history $H_{t}$, $\theta$ remains normally distributed. Algorithm 2 presents an implementation of UCB algorithm for this problem. The expectations can be computed efficiently via Kalman filtering. The algorithm employs upper confidence bound $\left\langle\phi(a),\,\mu_{t}\right\rangle+\beta\log(t)\left\|\phi(a)\right\|_{\Sigma_{t}}$. The term $\left\|\phi(a)\right\|_{\Sigma_{t}}$ captures the posterior variance of $\theta$ in the direction $\phi(a)$, and, as with the case of independent arms, causes the uncertainty bonus $\beta\log(t)\left\|\phi(a)\right\|_{\Sigma_{t}}$ to diminish as the number of observations increases.

2 Posterior Sampling.

Our first example involves a model with independent arms. In particular, suppose $\theta$ is drawn from a normal distribution $N(\mu_{0},\Sigma_{0})$ with a diagonal covariance matrix $\Sigma_{0}$, the reward function is given by $f_{\theta}(a)=\theta_{a}$, and the reward noise $R_{t}-f_{\theta}(A_{t})$ is normally distributed and independent from $(H_{t},A_{t},\theta)$. It then follows that, conditioned on the history $H_{t}$, $\theta$ remains normally distributed with independent components. Algorithm 3 presents an implementation of posterior sampling for this problem. The expectations are easy to compute and can also be computed recursively.

Our second example treats a linear bandit problem. Algorithm 4 presents a posterior sampling analogue to Algorithm 2. As before, we assume $\theta$ is drawn from a normal distribution $N(\mu_{0},\Sigma_{0})$. We consider a linear reward function $f_{\theta}(a)=\langle\phi(a),\theta\rangle$ and assume the reward noise $R_{t}-f_{\theta}(A_{t})$ is normally distributed and independent from $(H_{t},A_{t},\theta)$.

3 Potential Advantages of Posterior Sampling.

Well designed optimistic algorithms can be extremely effective. When simple and efficient UCB algorithms are available, they may be preferable to posterior sampling. Our work is primarily motivated by the challenges in designing optimistic algorithms to address very complicated problems, and the important advantages posterior sampling sometimes offers in such cases.

Posterior sampling can also offer critical computational advantages over UCB algorithms when the action space is intractably large. Consider the problem of learning to solve a linear program, where the action set $\mathcal{A}$ is a polytope encoded in terms of linear inequalities, and $f_{\theta}(a):=\langle\phi(a),\theta\rangle$ is a linear function. Algorithm 2 becomes impractical, because, as observed by Dani et al. , the action selection step entails solving a problem equivalent to linearly constrained negative definite quadratic optimization, which is NP hard .Dani et al. studies a slightly different UCB algorithm, but the optimization step shares the same structure. By contrast, the action selection step of Algorithm 4 only requires solving a linear program. The figure below displays the level sets of the linear objective $\langle\phi(a),\hat{\theta}\rangle$ and of the upper confidence bounds used by Algorithm 2. While posterior sampling preserves the linear structure of the functions $f_{\theta}(a)$, it is challenging to maximize the upper confidence bounds of Algorithm 2, which are strictly convex.

It is worth mentioning that because posterior sampling requires specifying a fully probabilistic model of the underlying system, it may not be ideally suited for every practical setting. In particular, when dealing with some complex classes of functions, specifying an appropriate prior can be a challenge while there may be alternative algorithms that address the problem in an elegant and practically effective way.

Confidence Bounds and Regret Decompositions.

Unlike UCB algorithms, posterior sampling does not make use of upper confidence bounds to encourage exploration and instead relies on randomization. As such, the two classes of algorithm seem very different. However, we will establish in this section a connection that will enable us in Section 6 to derive performance bounds for posterior sampling from those that apply to UCB algorithms. Since UCB algorithms have received much more attention, this leads to a number of new results about posterior sampling. Further, the relationship yields insight into the performance advantages of posterior sampling.

The inequality follows from the fact that $\bar{A_{t}}$ is chosen to maximize $U_{t}$. If the upper confidence bound is an upper bound with high probability, as one would expect from a UCB algorithm, then the first term is negative with high probability. The second term, $U_{t}(\bar{A_{t}})-f_{\theta}\left(\bar{A_{t}}\right)$, penalizes for the width of the confidence interval. As actions are sampled $U_{t}$ should diminish and converge on $f_{\theta}$. As such, both terms of the decomposition should eventually vanish. An important feature of this decomposition is that, so long as the first term is negative, it bounds regret in terms of uncertainty about the current action $\bar{A}_{t}$.

Taking the expectation of (1) establishes that the $T$-period Bayesian regret of a UCB algorithm satisfies

where $\pi^{U}$ is the policy derived from $U$.

2 Posterior Sampling Regret Decomposition.

Summing over $t$ gives the result. \Halmos

To compare (2) and (3) consider the case where $f_{\theta}$ takes values in $[0,\,C]$. Then,

An important difference to take note of is that the Bayesian regret bound of $\pi^{U}$ depends on the specific upper confidence bound sequence $U$ used by the UCB algorithm in question whereas the bound of $\pi^{\rm PS}$ applies simultaneously for all upper confidence bound sequences. This suggests that, while the Bayesian regret of a UCB algorithm depends critically on the specific choice of confidence sets, posterior sampling depends on the best possible choice of confidence sets. This is a crucial advantage when there are complicated dependencies among actions, as designing and computing with appropriate confidence sets presents significant challenges. This difficulty is likely the main reason that posterior sampling significantly outperforms recently proposed UCB algorithms in the simulations presented in Section 8.

We have shown how upper confidence bounds characterize Bayesian regret bounds for posterior sampling. We will leverage this concept in the next two sections. Let us emphasize, though, that while our analysis of posterior sampling will make use of upper confidence bounds, the actual performance of posterior sampling does not depend on upper confidence bounds used in the analysis.

From UCB to Posterior Sampling Regret Bounds.

We consider in this section a problem with $|\mathcal{A}|<\infty$ actions and rewards satisfying $R_{t}\in$ for all $t$ almost surely. We note, however, that the results we discuss can be extended to cases where $R_{t}$ is not bounded but where instead its distribution is “light-tailed.” It is also worth noting that we make no further assumptions on the class of reward functions $\mathcal{F}$ or on the prior distribution over $\theta$.

In this setting, Algorithm 1, which was proposed by Auer et al. , is known to satisfy a problem-independent regret bound of order $\sqrt{|\mathcal{A}|T\log T}$. Under an additional assumption that action rewards are independent and take values in $\{0,1\}$, an order $\sqrt{|\mathcal{A}|T\log T}$ regret bound for posterior sampling is also available .

Here we provide a Bayesian regret bound that is also of order $\sqrt{|\mathcal{A}|T\log T}$ but does not require that action rewards are independent or binary. Our analysis, like that of Auer et al. , makes use of confidence sets that are Cartesian products of action-specific confidence intervals. The regret decomposition (3) lets us use such confidence sets to produce bounds for posterior sampling even when the algorithm itself may exploit dependencies among actions.

Proof. Let $N_{t}(a)=\sum_{l=1}^{t}\mathbf{1}(A_{t}=a)$ denote the number of times $a$ is sampled over the first $t$ periods, and $\hat{\mu}_{t}(a)=N_{t}(a)^{-1}\sum_{l=1}^{t}\mathbf{1}(A_{t}=a)R_{t}$ denote the empirical average reward from these samples. Define upper and lower confidence bounds as follows:

The next lemma, which is a consequence of analysis in Abbasi-Yadkori et al. , shows these hold with high probability. Were actions sampled in an iid fashion, this lemma would follow immediately from the Hoeffding inequality. For more details, see Appendix 10.

We now turn to bounding $\sum_{t=1}^{T}(U_{t}-L_{t})(A_{t})$. Let $\mathcal{T}_{a}=\left\{t\leq T:A_{t}=a\right\}$ denote the periods in which $a$ is selected. Then, $\sum_{t=1}^{T}(U_{t}-L_{t})(A_{t})=\sum_{a\in\mathcal{A}}\sum_{t\in\mathcal{T}_{a}}(U_{t}-L_{t})(a)$. We show,

Summing over actions and applying the cauchy-shwartz inequality yields,

where (a) follows from the cauchy-shwartz inequality and (b) follows from the assumption that $T>K$. \Halmos

2 Linear and Generalized Linear Models.

We now consider function classes that represent linear and generalized linear models. The bound of Proposition 6.1 applies so long as the number of actions is finite, but we will establish alternative bounds that depend on the dimension of the function class rather than the number of actions. Such bounds accommodate problems with infinite action sets and can be much stronger than the bound of Proposition 6.1 if there are many actions.

The Bayesian regret bounds we provide in this section derive from regret bounds of the UCB literature. In Section 7, we will establish a Bayesian regret bound that is as strong for the case of linear models and stronger for the case of generalized linear models. Since the results of Section 7 to a large extent supersede those we present here, we aim to be brief and avoid formal proofs in this section’s discussion of the bounds and how they follow from results in the literature.

If $f_{\theta}$ takes values in $[-C,\,C]$ then (3) implies

2.2 Generalized Linear Models

In a generalized linear model, the reward function takes the form $f_{\theta}(a):=g\left(\left\langle\phi(a),\theta\ \right\rangle\right)$ where the inverse link function $g$ is strictly increasing and continuously differentiable. The analysis of can be applied to establish a Bayesian regret bound for posterior sampling, but with one caveat. The algorithm considered in begins by selecting a sequence of actions $a_{1},..,a_{d}$ with linearly independent feature vectors $\phi(a_{1}),\ldots,\phi(a_{d})$. Until now, we haven’t even assumed such actions exist or that they are guaranteed to be feasible over the first $d$ time periods. After this period of designed exploration, the algorithm selects at each time an action that maximizes an upper confidence bound. What we will establish using the results from is a bound on a similarly modified version of posterior sampling, in which the first $d$ actions taken are $a_{1},\ldots,a_{d}$, while subsequent actions are selected by posterior sampling. Note that the posterior distribution employed at time $d+1$ is conditioned on observations made over the first $d$ time periods. We denote this modified posterior sampling algorithm by $\pi^{\rm IPS}_{a_{1},\ldots,a_{d}}$. It is worth mentioning here that in Section 7 we present a result with a stronger bound that applies to the standard version of posterior sampling, which does not include a designed exploration period.

where $r=\sup_{\rho,a}g^{\prime}(\langle\phi(a),\rho\rangle)/\inf_{\rho,a}g^{\prime}(\langle\phi(a),\rho\rangle)$.

Like the analyses of and , which apply to linear models, the analysis of follows two steps that together bound both terms of our regret decomposition (6). First, an ellipsoidal confidence set $\Theta_{t}$ is constructed, centered around a quasi-maximum likelihood estimator. This confidence set is designed to contain $\theta$ with high probability. Given confidence bounds $U_{t}(a):=\max\{C,\max_{\rho\in\Theta_{t}}g(\langle\phi(a),\rho\rangle)\}$ and $L_{t}(a):=\min\{0,\min_{\rho\in\Theta_{t}}g(\langle\phi(a),\rho\rangle)\}$, a worst case bound on $\sum_{1}^{T}(U_{t}-L_{t})(a_{t})$ is established. The bound is similar to those established for the linear case, but there is an added dependence on the the slope of $g$.

3 Gaussian Processes.

In this section we consider the case where the reward function $f_{\theta}$ is sampled from a Gaussian process. That is, the stochastic process $\left(f_{\theta}(a):a\in\mathcal{A}\right)$ is such that for any $a_{1},..,a_{k}\in\mathcal{A}$ the collection $f_{\theta}(a_{1}),..,f_{\theta}(a_{k})$ follows a multivariate Gaussain distribution. Srinivas et al. study a UCB algorithm designed for such problems and provide general regret bounds. Again, through the regret decomposition (3) their analysis provides a Bayesian regret bound for posterior sampling.

For simplicity, we focus our discussion on the case where $\mathcal{A}$ is finite, so that $\left(f_{\theta}(a):a\in\mathcal{A}\right)$ follows a multivariate Gaussian distribution. As shown by Srinivas et al. , the results extend to infinite action sets through a discretization argument as long as certain smoothness conditions are satisfied.

When confidence bounds hold, a UCB algorithm incurs high regret from sampling an action only when the confidence bound at that action is loose. In that case, one would expect the algorithm to learn a lot about $f_{\theta}$ based on the observed reward. This suggests the algorithm’s cumulative regret may be bounded in an appropriate sense by the total amount it is expected to learn. Leveraging the structure of the Gaussian distribution, Srinivas et al. formalize this idea. They bound the regret of their UCB algorithm in terms of the maximum amount that any algorithm could learn about $f_{\theta}$. They use an information theoretic measure of learning: the information gain. This is defined to be the difference between the entropy of the prior distribution of $\left(f_{\theta}(a):a\in\mathcal{A}\right)$ and the entropy of the posterior. The maximum possible information gain is denoted $\gamma_{T}$, where the maximum is taken over all sequences $a_{1},..,a_{T}$.An important property of the Gaussian distribution is that the information gain does not depend on the observed rewards. This is because the posterior covariance of a multivariate Gaussian is a deterministic function of the points that were sampled. For this reason, this maximum is well defined. Their analysis also supports the following result on posterior sampling.

Srinivas et al. also provide bounds on $\gamma_{T}$ for kernels commonly used in Gaussian process regression, including the linear kernel, radial basis kernel, and Matérn kernel. Combined with the above proposition, this yields explicit Bayesian regret bounds in these cases.

We will briefly comment on their analysis and how it provides a bound for posterior sampling. First, note that the posterior distribution is Gaussian, which suggests an upper confidence bound of the form $U_{t}(a):=\mu_{t-1}(a)+\sqrt{\beta_{t}}\sigma_{t-1}(a)$, where $\mu_{t-1}(a)$ is the posterior mean, $\sigma_{t-1}(a)$ is the posterior standard deviation of $f_{\theta}(a)$, and $\beta_{t}$ is a confidence parameter. We can provide a Bayesian regret bound by bounding both terms of (3). The next lemma, which follows, bounds the second term. Some new analysis is required since the Gaussian distribution is unbounded, and we study Bayesian regret whereas Srinivas et al. bound regret with high probability under the prior.

Then since the posterior distribution of $f_{\theta}(a)-U_{t}(a)$ is normal with mean $-\sqrt{\beta_{t}}\sigma_{t-1}(a)$ and variance $\sigma^{2}_{t-1}(a)$

The final inequality above follows from the assumption that $\sigma_{0}(a)\leq 1$. The claim follows from (7) since

Now, consider the first term of (3), which is:

Here the second equality follows by the tower property of conditional expectation, and the final step follows from the Cauchy-Schwartz inequality. Therefore, to establish a Bayesian regret bound it is sufficient to provide a bound on the sum of posterior variances $\sum_{t=1}^{T}{\sigma^{2}_{t-1}(a_{t})}$ that holds for any $a_{1},..,a_{T}$. Under the assumption that $\sigma_{0}(a)\leq 1$, the proof of Lemma 5.4 of Srinivas et al. shows that $\sigma^{2}_{t-1}(a_{t})\leq\alpha^{-1}\log\left(1+\sigma^{-2}\sigma_{t-1}^{2}(a_{t})\right)$, where $\alpha=\left(1+\sigma^{-2}\right)$. At the same time, Lemma 5.3 of Srinivas et al. shows the information gain from selecting $a_{1},...a_{T}$ is equal to $\frac{1}{2}\sum_{t=1}^{T}\log\left(1+\sigma^{-2}\sigma_{t-1}^{2}(a_{t})\right)$. This shows that for any actions $a_{1},..,a_{T}$ the the sum of posterior variances $\sum_{t=1}^{T}{\sigma^{2}_{t-1}(a_{t})}$ can be bounded in terms of the information gain from selecting $a_{1},..,a_{T}$. Therefore $\sum_{t=1}^{T}{\sigma^{2}_{t-1}(A_{t})}$ can be bounded in terms of the largest possible information gain $\gamma_{T}$.

Bounds for General Function Classes.

The previous section treated models in which the relationship among action rewards takes a simple and tractable form. Indeed, nearly all of the multi-armed bandit literature focuses on such problems. Posterior sampling can be applied to a much broader class of models. As such, more general results that hold beyond restrictive cases are of particular interest. In this section, we provide a Bayesian regret bound that applies when the reward function lies in a known, but otherwise arbitrary class of uniformly bounded real-valued functions $\mathcal{F}$. Our analysis of this abstract framework yields a more general result that applies beyond the scope of specific problems that have been studied in the literature, and also identifies factors that unify more specialized prior results. Further, our more general result when specialized to linear models recovers the strongest known Bayesian regret bound and in the case of generalized linear models yields a bound stronger than that established in prior literature.

If $\mathcal{F}$ is not appropriately restricted, it is impossible to guarantee any reasonably attractive level of Bayesian regret. For example, in a case where $\mathcal{A}=$, $f_{\theta}(a)={\bf 1}(\theta=a)$, $\mathcal{F}=\{f_{\theta}|\theta\in\}$, and $\theta$ is uniformly distributed over $$, it is easy to see that the Bayesian regret of any algorithm over$T$periods is$T$, which is no different from the worst level of performance an agent can experience.

This example highlights the fact that Bayesian regret bounds must depend on the function class $\mathcal{F}$. The bound we develop in this section depends on $\mathcal{F}$ through two measures of complexity. The first is the Kolmogorov dimension, which measures the growth rate of the covering numbers of $\mathcal{F}$ and is closely related to measures of complexity that are common in the supervised learning literature. It roughly captures the sensitivity of $\mathcal{F}$ to statistical over-fitting. The second measure is a new notion we introduce, which we refer to as the eluder dimension. This captures how effectively the value of unobserved actions can be inferred from observed samples. We highlight in Section 7.3 why notions of dimension common to the supervised learning literature are insufficient for our purposes.

Our analysis in some ways parallels those found in the literature on UCB algorithms. In the next section we provide a method for constructing a set $\mathcal{F}_{t}\subset\mathcal{F}$ of functions that are statistically plausible at time $t$. Let $w_{\mathcal{F}}(a):=\sup_{\overline{f}\in\mathcal{F}}\overline{f}(a)-\inf_{\underline{f}\in\mathcal{F}}\underline{f}(a)$ denote the width of $\mathcal{F}$ at $a$. Based on these confidence sets, and using the regret decomposition (3), one can bound Bayesian regret in terms of $\sum_{1}^{T}w_{\mathcal{F}_{t}}(A_{t})$. In Section 7.2, we establish a bound on this sum in terms of the Kolmogorov and eluder dimensions of $\mathcal{F}$.

The construction of tight confidence sets for specific classes of functions presents technical challenges. Even for the relatively simple case of linear bandit problems, significant analysis is required. It is therefore perhaps surprising that, as we show in this section, one can construct strong confidence sets for an arbitrary class of functions without much additional sophistication. While the focus of our work is on providing a Bayesian regret bound for posterior sampling, the techniques we introduce for constructing confidence sets may find broader use.

The confidence sets constructed here are centered around least squares estimates $\hat{f}_{t}^{LS}\in\arg\min_{f\in\mathcal{F}}L_{2,t}(f)$ where $L_{2,t}(f)=\sum_{1}^{t-1}(f(A_{t})-R_{t})^{2}$ is the cumulative squared prediction error.The results can be extended to the case where the infimum of $L_{2,t}(f)$ is unattainable by selecting a function with squared prediction error sufficiently close to the infimum. The sets take the form $\mathcal{F}_{t}:=\{f\in\mathcal{F}:\|f-\hat{f}_{t}^{LS}\|_{2,E_{t}}\leq\sqrt{\beta_{t}}\}$ where $\beta_{t}$ is an appropriately chosen confidence parameter, and the empirical 2-norm $\left\|\cdot\right\|_{2,E_{t}}$ is defined by $\left\|g\right\|_{2,E_{t}}^{2}=\sum_{1}^{t-1}g^{2}(A_{k})$. Hence $\left\|f-f_{\theta}\right\|_{2,E_{t}}^{2}$ measures the cumulative discrepancy between the previous predictions of $f$ and $f_{\theta}$.

By Lemma 7.1, with high probability, $f$ can enjoy lower squared error than $f_{\theta}$ only if its empirical deviation $\left\|f-f_{\theta}\right\|_{2,E_{t}}^{2}$ from $f_{\theta}$ is less than $8\sigma^{2}\log(1/\delta)$. Through a union bound, this property holds uniformly for all functions in a finite subset of $\mathcal{F}$. Using this fact and a discretization argument, together with the observation that $L_{2,t}(\hat{f}_{t}^{LS})\leq L_{2,t}(f_{\theta})$, we can establish the following result, which is proved in the appendix. Let $N(\mathcal{F},\,\alpha,\,\left\|\cdot\right\|_{\infty})$ denote the $\alpha$-covering number of $\mathcal{F}$ in the sup-norm $\|\cdot\|_{\infty}$, and let

While the expression (8) defining the confidence parameter is complicated, it can be bounded by simple expressions in important cases. We provide three examples.

Finite function classes: When $\mathcal{F}$ is finite, $\beta^{*}_{t}(\mathcal{F},\delta,0)=8\sigma^{2}\log(\left|\mathcal{F}\right|/\delta)$.

Generalized Linear Models: Consider the case of a $d$-dimensional generalized linear model $f_{\theta}(a):=g\left(\left\langle\phi(a),\,\theta\right\rangle\right)$ where $g$ is an increasing Lipschitz continuous function. Fix $g$, $\gamma=\sup_{a\in\mathcal{A}}\|\phi(a)\|$, and $s=\sup_{\rho\in\Theta}\|\rho\|$. Then, the previous argument shows $\log N(\mathcal{F},\,\alpha,\,\left\|\cdot\right\|_{\infty})=O(d\log(1/\alpha))$. Again, choosing $\alpha=1/t^{2}$ yields a confidence parameter $\beta_{t}^{*}(\mathcal{F},\delta,1/t^{2})=O(d\log(t/\delta))$.

The confidence parameter $\beta^{*}_{t}(\mathcal{F},1/t^{2},1/t^{2})$ is closely related to the following concept.

The Kolmogorov dimension of a function class $\mathcal{F}$ is given by

In particular, we have the following result.

For any fixed class of functions $\mathcal{F}$,

The result follows from the fact that $\underset{t\rightarrow\infty}{\lim\sup}\log\left(N\left(\mathcal{F},\,1/t^{2},\,\left\|\cdot\right\|_{\infty}\right)\right)/\log\left(t^{2}\right)={\rm dim}_{K}(\mathcal{F})$. \Halmos

2 Bayesian Regret Bounds.

We can use the confidence sets constructed in the previous section to guarantee that the conditions of this lemma hold. In particular, choosing $\delta=1/2T$ in (8) guarantees that $f_{\theta}\in\bigcap_{t=1}^{\infty}\mathcal{F}_{t}$ with probability at least $1-1/T$.

The $\epsilon$-eluder dimension ${\rm dim}_{E}(\mathcal{F},\epsilon)$ is the length $d$ of the longest sequence of elements in $\mathcal{A}$ such that, for some $\epsilon^{\prime}\geq\epsilon$, every element is $\epsilon^{\prime}$-independent of its predecessors.

Recall that a vector space has dimension $d$ if and only if $d$ is the length of the longest sequence of elements such that each element is linearly independent or equivalently, -independent of its predecessors. Definition 7.11 replaces the requirement of linear independence with $\epsilon$-independence. This extension is advantageous as it captures both nonlinear dependence and approximate dependence. The following result uses our new notion of dimension to bound the number of times the width of the confidence interval for a selected action $A_{t}$ can exceed a threshold.

Proof. We begin by showing that if $w_{t}(A_{t})>\epsilon$ then $A_{t}$ is $\epsilon$-dependent on fewer than $4\beta_{T}/\epsilon^{2}$ disjoint subsequences of $(A_{1},..,A_{t-1})$, for $T>t$. To see this, note that if $w_{\mathcal{F}_{t}}(A_{t})>\epsilon$ there are $\bar{f},\,\underline{f}\,\in\mathcal{F}_{t}$ such that $\overline{f}(A_{t})-\underline{f}(A_{t})>\epsilon$. By definition, since $\overline{f}(A_{t})-\underline{f}(A_{t})>\epsilon$, if $A_{t}$ is $\epsilon$-dependent on a subsequence $(A_{i_{1}},..,\,A_{i_{k}})$ of $(A_{1},..,A_{t-1})$ then $\sum_{j=1}^{k}(\overline{f}(A_{i_{j}})-\underline{f}(A_{i_{j}}))^{2}>\epsilon^{2}$. It follows that, if $A_{t}$ is $\epsilon$-dependent on $K$ disjoint subsequences of $(A_{1},..,A_{t-1})$ then $\|\overline{f}-\underline{f}\|_{2,E_{t}}^{2}>K\epsilon^{2}$. By the triangle inequality, we have

and it follows that $K<4\beta_{T}/\epsilon^{2}$.

Next, we show that in any action sequence $(a_{1},..,a_{\tau})$, there is some element $a_{j}$ that is $\epsilon$-dependent on at least $\tau/d-1$ disjoint subsequences of $\left(a_{1},..,a_{j-1}\right)$, where $d:={\rm dim}_{E}(\mathcal{F},\epsilon)$. To show this, for an integer $K$ satisfying $Kd+1\leq\tau\leq Kd+d$, we will construct $K$ disjoint subsequences $B_{1},\ldots,B_{K}$. First let $B_{i}=\left(a_{i}\right)$ for $i=1,..,K$. If $a_{K+1}$ is $\epsilon$-dependent on each subsequence $B_{1},..,B_{K}$, our claim is established. Otherwise, select a subsequence $B_{i}$ such that $a_{K+1}$ is $\epsilon$-independent and append $a_{K+1}$ to $B_{i}$. Repeat this process for elements with indices $j>K+1$ until $a_{j}$ is $\epsilon$-dependent on each subsequence or $j=\tau$. In the latter scenario $\sum|B_{i}|\geq Kd$, and since each element of a subsequence $B_{i}$ is $\epsilon$-independent of its predecessors, $|B_{i}|=d$. In this case, $a_{\tau}$ must be $\epsilon$–dependent on each subsequence.

Now consider taking $(a_{1},..,a_{\tau})$ to be the subsequence $(A_{t_{1}},\ldots,A_{t_{\tau}})$ of $(A_{1},\ldots,A_{T})$ consisting of elements $A_{t}$ for which $w_{\mathcal{F}_{t}}(A_{t})>\epsilon$. As we have established, each $A_{t_{j}}$ is $\epsilon$-dependent on fewer than $4\beta_{T}/\epsilon^{2}$ disjoint subsequences of $(A_{1},..,A_{t_{j}-1})$. It follows that each $a_{j}$ is $\epsilon$-dependent on fewer than $4\beta_{T}/\epsilon^{2}$ disjoint subsequences of $(a_{1},..,a_{j-1})$. Combining this with the fact we have established that there is some $a_{j}$ that is $\epsilon$-dependent on at least $\tau/d-1$ disjoint subsequences of $\left(a_{1},..,a_{j-1}\right)$, we have $\tau/d-1\leq 4\beta_{T}/\epsilon^{2}$. It follows that $\tau\leq(4\beta_{T}/\epsilon^{2}+1)d$, which is our desired result. \Halmos

Using Proposition 7.12, one can bound the sum $\sum_{t=1}^{T}w_{\mathcal{F}_{t}}(A_{t})$, as established by the following lemma.

Proof. To reduce notation, write $d=\dim_{E}\left(\mathcal{F},T^{-1}\right)$ and $w_{t}=w_{t}(A_{t})$. Reorder the sequence $\left(w_{1},...,w_{T}\right)\rightarrow\left(w_{i_{1}},...,w_{i_{T}}\right)$ where $w_{i_{1}}\geq w_{i_{2}}\geq...\geq w_{i_{T}}$. We have

We know $w_{i_{t}}\leq C$. In addition, $w_{i_{t}}>\epsilon\iff\sum_{k=1}^{T}\mathbf{1}\left(w_{\mathcal{F}_{k}}\left(A_{k}\right)>\epsilon\right)\geq t$. By Proposition 7.12, this can only occur if $t<\left(\frac{4\beta_{T}}{\epsilon^{2}}+1\right)\dim_{E}(\mathcal{F},\epsilon)$. For $\epsilon\geq T^{-1}$, $\dim_{E}(\mathcal{F},\epsilon)\leq\dim_{E}(\mathcal{F},T^{-1})=d$, since $\dim_{E}\left(\mathcal{F},\epsilon^{\prime}\right)$ is nonincreasing in $\epsilon^{\prime}$. Therefore, when $w_{i_{t}}>\epsilon\geq T^{-1}$, $t<\left(\frac{4\beta_{T}}{\epsilon^{2}}+1\right)d$ which implies $\epsilon<\sqrt{\frac{4\beta_{T}d}{t-d}}$. This shows that if $w_{i_{t}}>T^{-1}$, then $w_{i_{t}}\leq\min\left\{C,\sqrt{\frac{4\beta_{T}d}{t-d}}\right\}$. Therefore,

Our next result, which follows from Lemma 7.9, Lemma 7.14, and Proposition 7.2, establishes a Bayesian regret bound.

Using bounds on $\beta_{t}^{*}$ provided in the previous section together with Proposition 7.16 yields Bayesian regret bounds that depend on $\mathcal{F}$ only through the eluder dimension and either the cardinality or Kolmogorov dimension. The following proposition provides such bounds.

For any fixed class of functions $\mathcal{F}$,

The next two examples show how the first Bayesian regret bound of Proposition 7.17 specializes to $d$-dimensional linear and generalized linear models. For each of these examples, a bound on ${\rm dim}_{E}\left(\mathcal{F},\epsilon\right)$ is provided in the appendix.

Linear Models: Consider the case of a $d$-dimensional linear model $f_{\rho}(a):=\left\langle\phi(a),\,\rho\right\rangle$. Fix $\gamma=\sup_{a\in\mathcal{A}}\|\phi(a)\|$ and $s=\sup_{\rho\in\Theta}\|\rho\|$. Then, ${\rm dim}_{E}(\mathcal{F},\epsilon)=O(d\log(1/\epsilon))$ and ${\rm dim}_{K}(\mathcal{F})=O(d)$. Proposition 7.17 therefore yields an $O(d\sqrt{T}\log(T))$ Bayesian regret bound. This is tight to within a factor of $\log T$ , and matches the best available bound for a linear UCB algorithm .

One advantage of studying posterior sampling in a general framework is that it allows bounds to be obtained for specific classes of models by specializing more general results. This advantage is highlighted by the ease of developing a performance guarantee for generalized linear models. The problem is reduced to one of bounding the eluder dimension, and such a bound follows almost immediately from the analysis of linear models. In prior literature, extending results from linear to generalized linear models required significant technical developments, as presented in Filippi et al. .

3 Relation to the Vapnik-Chervonenkis Dimension.

To close our section on general bounds, we discuss important differences between our new notion of eluder dimension and complexity measures used in the analysis of supervised learning problems. We begin with an example that illustrates how a class of functions that is learnable in constant time in a supervised learning context may require an arbitrarily long duration when learning to optimize.

Consider a finite class of binary-valued functions $\mathcal{F}=\left\{f_{\rho}:\mathcal{A}\mapsto\{0,1\}\ |\ \rho\in\{1,\ldots,n\}\right\}$ over a finite action set $\mathcal{A}=\{1,\ldots,n\}$. Let $f_{\rho}(a)={\bf 1}(\rho=a)$, so that each function is an indicator for an action. To keep things simple, assume that $R_{t}=f_{\theta}(A_{t})$, so that there is no noise. If $\theta$ is uniformly distributed over $\{1,\ldots,n\}$, it is easy to see that the Bayesian regret of posterior sampling grows linearly with $n$. For large $n$, until $\theta$ is discovered, each sampled action is unlikely to reveal much about $\theta$ and learning therefore takes very long.

In the preceding example, the $\epsilon$-eluder dimension is $n$ for $\epsilon\in(0,1)$. On the other hand, the Vapnik-Chervonenkis (VC) dimension, which characterizes the sample complexity of supervised learning, is $1$. To highlight conceptual differences between the eluder dimension and the VC dimension, we will now define VC dimension in a way analogous to how we defined eluder dimension. We begin with a notion of independence.

In the above example, any two actions are VC-dependent because knowing the label of one action could completely determine the value of the other action. However, this only happens if the sampled action has label 1. If it has label 0, one cannot infer anything about the value of the other action. Instead of capturing the fact that one could gain useful information about the reward function through exploration, we need a stronger requirement that guarantees one will gain useful information through exploration. Such a requirement is captured by the following concept.

Simulation Results.

In this section, we compare the performance in simulation of posterior sampling to that of UCB algorithms that have been proposed in the recent literature. Our results demonstrate that posterior sampling significantly outperforms these algorithms. Moreover, we identify a clear cause for the large discrepancy: confidence sets proposed in the literature are too loose to attain good performance.

Several UCB algoriths are suitable for such problems, including those of . While the confidence bound of is stronger than that of , it is still too loose and the resulting linear UCB algorithm hardly improves its performance over the 1000 period time horizon. We display the results only of the more competitive UCB algorithms. The line labeled “linear UCB” displays the results of the algorithm proposed in , which incurred average regret of 339.7. The algorithm of is labeled “Gaussian UCB,” and incurred average regret 198.7. Posterior sampling, on the other hand, incurred average regret of only 97.5.

Each of these UCB algorithms uses a confidence bound that was derived through stochastic analysis. The Gaussian linear model has a clear structure, however, which suggests upper confidence bounds should take the form $U_{t}(a)=\mu_{t-1}(a)+\sqrt{\beta}\sigma_{t-1}(a)$ where $\mu_{t-1}(a)$ and $\sigma_{t-1}(a)$ are the posterior mean and standard deviation at $a$. The final algorithm we consider ignores theoretical considerations, and tunes the parameter $\beta$ to minimize the average regret over the first 1000 periods. The average regret of the algorithm was only 68.9, a dramatic improvement over , and , and even outperforming posterior sampling. On the plot shown below, these results are labeled “Gaussian UCB - Tuned Heuristic.” Note such tuning requires the time horizon to be fixed and known.

In this setting, the problem of choosing upper-confidence bounds reduces to choosing a single confidence parameter $\beta$. For more complicated problems, however, significant analysis may be required to choose a structural form for confidence sets. The results in this section suggest that it can be quite challenging to use such analysis to derive confidence bounds that lead to strong empirical performance. In particular, this is challenging even for linear models. For example, the paper uses sophisticated tools from the study of multivariate self-normalized martingales to derive a confidence bound that is stronger than those of or , but their algorithm still incurs about three and a half times the regret of posterior sampling. This highlights a crucial advantage of posterior sampling that we have emphasized throughout this paper; it effectively separates confidence bound analysis from algorithm design.

Finally, it should be noted that the algorithms of have free parameters that must be chosen by the user. We have attempted to set these values in a way that minimizes average regret over the 1000 period time horizon. Both algorithms construct confidence bounds that hold with a pre-specified probability $1-\delta\in$. Higher levels of $\delta$ lead to lower upper-confidence bounds, which we find improves performance. We set $\delta=1$ to minimize the average regret of the algorithms. The algorithm of requires two other choices. We used a line search to set the algorithm’s regularization parameter to the level $\lambda=.025$, which minimizes cumulative regret. The algorithm of also requires a uniform upper bound on $\left\|\theta\right\|$, but the Gaussian distribution is unbounded. We avoid this issue by providing the actual realized value $\left\|\theta\right\|$ as an input to algorithm.

Conclusion.

This paper has considered the use of a simple posterior sampling algorithm for learning to optimize actions when the decision maker is uncertain about how his actions influence performance. We believe that, particularly for difficult problem instances, this algorithm offers significant potential advantages because of its design simplicity and computational tractability. Despite its great potential, not much is known about posterior sampling when there are dependencies between actions. Our work has taken a significant step toward remedying this gap. We showed that the Bayesian regret of posterior sampling can be decomposed in terms of confidence sets, which allowed us to establish a number of new results on posterior sampling by leveraging prior work on UCB algorithms. We then used this regret decomposition to analyze posterior sampling in a very general framework, and developed Bayesian regret bounds that depend on a new notion of dimension.

In constructing these bounds, we have identified two factors that control the hardness of a particular multi-armed bandit problem. First, an agent’s ability to quickly attain near-optimal performance depends on the extent to which the reward value at one action can be inferred by sampling other actions. However, in order to select an action the agent must make inferences about many possible actions, and an error in its evaluation of any one could result in large regret. Our second measure of complexity controls for the difficulty of maintaining appropriate confidence sets simultaneously at every action. While our bounds are nearly tight in some cases, further analysis is likely to yield stronger results in other cases. We hope, however, that our work provides a conceptual foundation for the study of such problems, and inspires further investigation.

Details Regarding Lemma 6.3.

Lemma 6.3 follows as a special case of Theorem 1 of Abbasi-Yadkori et al. , which is much more general. Note that because reward noise $R_{t}-f_{\theta}(A_{t})$ is bounded in , it is 1-subgaussian. Equation 12 in Abbasi-Yadkori et al. gives a specialization of Theorem 1 to the problem we consider. It states that for any $\delta>0$, with probability at least $1-\delta$,

We choose $\delta=1/T$ and use that for $t\leq T$, $N_{t}(a)\leq T-1$ to show that with probability at least $1/T$,

Since $1+N_{t}(a)\leq 2N_{t}(a)$ whenever $a$ has been played at least once, with probability at least $1/T$,

Proof of Confidence bound.

We note that the event $\left\{M_{\tau_{x}\wedge n}\left(\lambda\right)\geq x\right\}=\bigcup_{k=1}^{n}\left\{M_{k}(\lambda)\geq x\right\}$. So we have shown that for all $x\geq 0$ and $n\geq 1$

2 Proof of Lemma 7.1.

Proof. By definition $\sum_{1}^{T}Z_{t}=L_{2,T+1}(f_{\theta})-L_{2,T+1}(f)$. Some calculation shows that $Z_{t}=-\left(f(A_{t})-f_{\theta}(A_{t})\right)^{2}+2\left(f\left(A_{t}\right)-f_{\theta}\left(A_{t}\right)\right)\epsilon_{t}$. Therefore, the conditional mean and conditional cumulant generating function satisfy:

Applying Lemma 11.3 shows that for all $x\geq 0$, $\lambda\geq 0$

Choosing $\lambda=\frac{1}{4\sigma^{2}}$, $x=\log\frac{1}{\delta}$, and using the definition of $\sum_{1}^{t}Z_{k}$ implies

3 Least Squares Bound - Proof of Proposition 7.2.

Proof. Let $\mathcal{F}^{\alpha}\subset\mathcal{F}$ be an $\alpha$–cover of $\mathcal{F}$ in the sup-norm in the sense that for any $f\in\mathcal{F}$ there is an $f^{\alpha}\in\mathcal{F}^{\alpha}$ such that $\left\|f^{\alpha}-f\right\|_{\infty}\leq\epsilon$. By a union bound, with probability at least $1-\delta$,

Lemma 11.7, which we establish in the next section, asserts that with probability at least $1-\delta$ the discretization error is bounded for all $t$ by $\alpha\eta_{t}$ where $\eta_{t}:=t\left[8C+\sqrt{8\sigma^{2}\ln(4t^{2}/\delta)}\right]$. Since the least squares estimate $\hat{f}_{t}^{LS}$ has lower squared error than $f_{\theta}$ by definition, we find with probability at least $1-2\delta$

Taking the infimum over the size of $\alpha$ covers implies:

4 Discretization Error.

If $f^{\alpha}$ satisfies $\left\|f-f^{\alpha}\right\|_{\infty}\leq\alpha$, then with probability at least $1-\delta$,

Proof. Since any two functions in $f,f^{\alpha}\in\mathcal{F}$ satisfy $\left\|f-f^{\alpha}\right\|_{\infty}\leq C$, it is enough to consider $\alpha\leq C$. We find

Summing over $t$, we find that the left hand side of (9) is bounded by

Since $\left|R_{k}\right|\leq C+\left|\epsilon_{k}\right|$ this shows that with probability at least $1-\delta$ the discretization error is bounded for all $t$ by $\alpha\eta_{t}$ where $\eta_{t}:=t\left[8C+2\sqrt{2\sigma^{2}\ln(4t^{2}/\delta)}\right]$. \Halmos

Bounds on Eluder Dimension for Common Function Classes.

Definition 7.11, which defines the eluder dimension of a class of functions, can be equivalently written as follows. The $\epsilon$-eluder dimension of a class of functions $\mathcal{F}$ is the length of the longest sequence $a_{1},..,a_{\tau}$ such that for some $\epsilon^{\prime}\geq\epsilon$

Any action is $\epsilon^{\prime}$–dependent on itself since

Therefore, for all $\epsilon>0$, the $\epsilon$-eluder dimension of $\mathcal{A}$ is bounded by $|\mathcal{A}|$.

2 Linear Case.

To simplify the notation, define $w_{k}$ as in (10), $\phi_{k}=\phi\left(a_{k}\right)$, $\rho=\rho_{1}-\rho_{2}$, and $\Phi_{k}=\sum_{i=1}^{k-1}\phi_{i}\phi_{i}^{T}$. In this case, $\sum_{i=1}^{k-1}\left(f_{\rho_{1}}-f_{\rho_{2}}\right)^{2}\left(a_{i}\right)=\rho^{T}\Phi_{k}\rho$, and by the triangle inequality $\left\|\rho\right\|_{2}\leq 2S$. The proof follows by bounding the number of times $w_{k}>\epsilon^{\prime}$ can occur.

Step 1: If $w_{k}\geq\epsilon^{\prime}$ then $\phi_{k}^{T}V_{k}^{-1}\phi_{k}\geq\frac{1}{2}$ where $V_{k}:=\Phi_{k}+\lambda I$ and $\lambda=\left(\frac{\epsilon^{\prime}}{2S}\right)^{2}$.

Proof. We find $w_{k}\leq\max\left\{\rho^{T}\phi_{k}:\,\rho^{T}\Phi_{k}\rho\leq(\epsilon^{\prime})^{2},\,\,\rho^{T}I\rho\leq(2S)^{2}\right\}\leq\max\left\{\rho^{T}\phi_{k}:\,\rho^{T}V_{k}\rho_{k}\leq 2(\epsilon^{\prime})^{2}\right\}=\sqrt{2(\epsilon^{\prime})^{2}}\left\|\phi_{k}\right\|_{V_{k}^{-1}}$. The second inequality follows because any $\rho$ that is feasible for the first maximization problem must satisfy $\rho^{T}V_{k}\rho\leq(\epsilon^{\prime})^{2}+\lambda(2S)^{2}=2(\epsilon^{\prime})^{2}$. By this result, $w_{k}\geq\epsilon^{\prime}$ implies $\left\|\phi_{k}\right\|_{V_{k}^{-1}}^{2}\geq 1/2$. \Halmos

Step 2: If $w_{i}\geq\epsilon^{\prime}$ for each $i<k$ then $\det V_{k}\geq\lambda^{d}\left(\frac{3}{2}\right)^{k-1}$ and $\det V_{k}\leq\left(\frac{\gamma^{2}\left(k-1\right)}{d}+\lambda\right)^{d}$.

Proof. Since $V_{k}=V_{k-1}+\phi_{k}\phi_{k}^{T}$, using the Matrix Determinant Lemma,

Recall that $\det V_{k}$ is the product of the eigenvalues of $V_{k}$, whereas $\text{trace}\left[V_{k}\right]$ is the sum. As noted in , $\det V_{k}$ is maximized when all eigenvalues are equal. This implies: $\det V_{k}\leq\left(\frac{\text{trace}\left[V_{k}\right]}{d}\right)^{d}\leq\left(\frac{\gamma^{2}\left(t-1\right)}{d}+\lambda\right)^{d}$. \Halmos

Proof. Manipulating the result of Step 2 shows $k$ must satisfy the inequality: $\left(\frac{3}{2}\right)^{\frac{k-1}{d}}\leq\alpha_{0}\left[\frac{k-1}{d}\right]+1$ where $\alpha_{0}=\left(\frac{\gamma^{2}}{\lambda}\right)=\left(\frac{2S\gamma}{\epsilon^{\prime}}\right)^{2}$. Let $B(x,\alpha)=\max\left\{B:\,\left(1+x\right)^{B}\leq\alpha B+1\right\}$. The number of times $w_{k}>\epsilon^{\prime}$ can occur is bounded by $dB(1/2,\alpha_{0})+1$.

We now derive an explicit bound on $B(x,\alpha)$ for any $x\leq 1$. Note that any $B\geq 1$ must satisfy the inequality: $\ln\left\{1+x\right\}B\leq\ln\left\{1+\alpha\right\}+\ln B$. Since $\ln\left\{1+x\right\}\geq x/(1+x)$, using the transformation of variables $y=B\left[x/(1+x)\right]$ gives:

This implies $B(x,\alpha)\leq\frac{1+x}{x}\frac{e}{e-1}\left(\ln\left\{1+\alpha\right\}+\ln\frac{1+x}{x}\right)$. The claim follows by plugging in $\alpha=\alpha_{0}$ and $x=1/2$. \Halmos

3 Generalized Linear Models.

The proof follows three steps which closely mirror those used to prove Proposition 12.1.

Step 1: If $w_{k}\geq\epsilon^{\prime}$ then $\phi_{k}^{T}V_{k}^{-1}\phi_{k}\geq\frac{1}{2r^{2}}$ where $V_{k}:=\Phi_{k}+\lambda I$ and $\lambda=\left(\frac{\epsilon^{\prime}}{2S\underline{h}}\right)^{2}$.

Proof. By definition $w_{k}\leq\max\left\{g\left(\rho^{T}\phi_{k}\right):\,\sum_{i=1}^{k-1}g\left(\rho^{T}\phi(a_{i})\right)^{2}\leq(\epsilon^{\prime})^{2},\,\,\rho^{T}I\rho\leq(2S)^{2}\right\}$. By the uniform bound on $g^{\prime}(\cdot)$ this is less than $\max\left\{\overline{h}\rho^{T}\phi_{k}:\,\underline{h}^{2}\rho^{T}\Phi_{k}\rho\leq(\epsilon^{\prime})^{2},\rho^{T}I\rho\leq(2S)^{2}\right\}\leq\max\left\{\overline{h}\rho^{T}\phi_{k}:\,\underline{h}^{2}\rho^{T}V_{k}\rho\leq 2(\epsilon^{\prime})^{2}\right\}=\sqrt{2(\epsilon^{\prime})^{2}/r^{2}}\left\|\phi_{k}\right\|_{V_{k}^{-1}}$.\Halmos

Step 2: If $w_{i}\geq\epsilon^{\prime}$ for each $i<k$ then $\det V_{k}\geq\lambda^{d}\left(\frac{3}{2}\right)^{k-1}$ and $\det V_{k}\leq\left(\frac{\gamma^{2}\left(k-1\right)}{d}+\lambda\right)^{d}$.

Proof. The above inequalities imply $k$ must satisfy: $\left(1+\frac{1}{2r^{2}}\right)^{\frac{k-1}{d}}\leq\alpha_{0}\left[\frac{k-1}{d}\right]$ where $\alpha_{0}=\gamma^{2}/\lambda$. Therefore, as in the linear case, the number of times $w_{k}>\epsilon^{\prime}$ can occur is bounded by $dB(\frac{1}{2r^{2}},\alpha_{0})+1$. Plugging these constants into the earlier bound $B(x,\alpha)\leq\frac{1+x}{x}\frac{e}{e-1}\left(\ln\left\{1+\alpha\right\}+\ln\frac{1+x}{x}\right)$ and using $1+x\leq 3/2$ yields the result. \Halmos

References