Thompson Sampling for 1-Dimensional Exponential Family Bandits
Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (through the Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.
This quantity measures the expected performance of algorithm A compared to the expected performance of an optimal algorithm given knowledge of the reward distributions, i.e. sampling always from the distribution with the highest expectation.
Since the early 2000s the "optimisim in the face of uncertainty" heuristic has been a popular approach to this problem, providing both simplicity of implementation and finite-time upper bounds on the regret (e.g. [4,7]). However in the last two years there has been renewed interest in the Thompson Sampling heuristic (TS). While this heuristic was first put forward to solve bandit problems eighty years ago in [15], it was not until recently that theoretical analyses of its performance were achieved [1,2,11,13]. In this paper we take a major step towards generalising these analyses to the same level of generality already achieved for "optimistic" algorithms.
Thompson Sampling Unlike optimistic algorithms which are often based on confidence intervals, the Thompson Sampling algorithm, denoted by A π0 uses Bayesian tools and puts a prior distribution π a,0 = π 0 on each parameter θ a . A posterior distribution, π a,t , is then maintained according to the rewards observed in H t−1 . At each time a sample θ a,t is drawn from each posterior π a,t and then the algorithm chooses to sample a t = arg max a∈{1,...,K} {µ(θ a,t )}. Note that actions are sampled according to their posterior probabilities of being optimal.
Our contributions TS has proved to have impressive empirical performances, very close to those of state of the art algorithms such as DMED and KL-UCB [11,9,7]. Furthermore recent works [11,2] have shown that in the special case where each p a is a Bernoulli distribution B(θ a ), TS using a uniform prior over the arms is asymptotically optimal in the sense that it achieves the asymptotic lower bound on the regret provided by Lai and Robbins in [12] (that holds for univariate parametric bandits). As explained in [1,2], Thompson Sampling with uniform prior for Bernoulli rewards can be slightly adapted to deal with bounded rewards. However, there is no notion of asymptotic optimality for this non-parametric family of rewards. In this paper, we extend the optimality property that holds for Bernoulli distributions to more general families of parametric rewards, namely 1-dimensional exponential families if the algorithm uses the Jeffreys prior: Theorem 1. Suppose that the reward distributions belong to a 1-dimensional canonical exponential family and let π J denote the associated Jeffreys prior. Then,
where K(θ, θ ) := KL(p θ , p θ ) is the Kullback-Leibler divergence between p θ and p θ .
This theorem follows directly from Theorem 2. In the proof of this result we provide in Theorem 4 a finite-time, exponential concentration bound for posterior distributions of exponential family random variables, something that to the best of our knowledge is new to the literature and of interest in its own right. Our proof also exploits the connection between the Jeffreys prior, Fisher information and the Kullback-Leibler divergence in exponential families.
Related Work Another line of recent work has focused on distribution-independent bounds for Thompson Sampling. [2] establishes that R(A π U , T ) = O( KT ln(T )) for Thompson Sampling for bounded rewards (with the classic uniform prior π U on the underlying Bernoulli parameter). [14] go beyond the Bernoulli model, and give an upper bound on the Bayes risk (i.e. the regret averaged over the prior) independent of the prior distribution. For the parametric multi-armed bandit with K arms described above, their result states that the regret of Thompson Sampling using a prior π 0 is not too big when averaged over this same prior:
Building on the same ideas, [6] have improved this upper bound to 14 √ KT . In our paper, we rather see the prior used by Thompson Sampling as a tool, and we want therefore to derive regret bounds for any given problem parametrized by θ that depend on this parameter.
[14] also use Thompson Sampling in more general models, like the linear bandit model. Their result is a bound on the Bayes risk that does not depend on the prior, whereas [3] gives a first bound on the regret in this model. Linear bandits consider a possibly infinite number of arms whose mean rewards are linearly related by a single, unknown coefficient vector. Once again, the analysis in [3] encounters the problem of describing the concentration of posterior distributions. However by using a conjugate normal prior, they can employ explicit concentration bounds available for Normal distributions to complete their argument.
Paper Structure In Section 2 we describe important features of the one-dimensional canonical exponential families we consider, including closed-form expression for KL-divergences and the Jeffreys' prior. Section 3 gives statements of the main results, and provides the proof of the regret bound. Section 4 proves the posterior concentration result used in the proof of the regret bound.
The paper provides a logarithmic regret bound for a 
      known bandit algorithm, Thompson Sampling, in the case of bandit problems 
      with reward distributions being part of the exponential family. The result 
      is novel and generalizes previous work done for the case of Bernoulli 
      bandits. Quality: The paper seems technically sound. The 
      technical results are interesting and the proofs are non-trivial. 
      One key difference with previous work is the change of the prior 
      distribution for Thompson Sampling (from a uniform prior to Jeffreys 
      prior). The authors provide reasons as to why the Jeffreys prior should be 
      used since it helps the theoretical analysis. My first question is though, 
      what would be the motivation in an applied setting to prefer a Jeffreys to 
      a uniform prior? And what would be the practical impact of this change? 
      For example, in the case of a Bernoulli distribution, the Jeffreys prior 
      is Beta(0.5,0.5) which encodes a prior belief that the optimal expected 
      reward is either closer to 0 or closer to 1. This seems unreasonable if no 
      prior knowledge exists about the arms. My second question is about 
      the proof of inequality (6) in Appendix A. At line 517, D_{a,s} is defined 
      to be the complement of the second part of the event E_{a,t} defined in 
      line 219 (equation (5)). But D_{a,s} is not really the complement (as it 
      would require an \forall s' quantifier instead of the existential 
      quantifier). I am assuming the authors skipped some steps, so could you 
      please clarify? Clarity: The paper is relatively difficult to 
      read. One problem is the disproportionate use of mathematical notation at 
      the expense of providing intuitions for the used variables and the 
      results. Here are several examples: - L(\theta) (introduced in 
      line 216), while an important variable for the proof, has no explanation 
      as to why it is defined that way other than it is a "likely realization of 
      arm a". - The superscript 'c' used for the first time in line 244 and 
      used through the proof has no explanation - the reader is forced to infer 
      that the authors mean the complement of the event E_{a,t}. - The 
      quantity t^b introduced in line 247 is not defined and it is only 
      introduced later in the text. - A lot of subscripts and superscripts 
      (like TS, pi_J) could easily be removed with the benefit of improving the 
      readability of the results. Regarding the organization, I like 
      that the authors provide the high level argument "graph" before the 
      proofs, but I think the paper could be improved if this high level 
      description would be more intuitive even at the cost of moving more 
      technical details to the appendix. Another concrete example of 
      what could help the readability is a corollary of Theorem 4 that would 
      make it explicit for a particular distribution class. Originality 
      and Significance: I agree with the authors that Theorem 4, that 
      introduces a new tool for proving concentration bounds for posterior 
      distributions, is new (to the best of my knowledge) and interesting in 
      itself. The high level strategy of the proof for Theorem 2 (the 
      main result of the paper) follows the idea of the proof for the Bernoulli 
      bandit case in Kaufman et al 2012 while being more technically involved 
      and general.