PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Optimize Via Posterior Sampling

Daniel Russo, Benjamin Van Roy

arXiv:1301.2609v5cs.LG

TL;DR

The paper asks how to balance exploration and exploitation when optimizing actions under uncertain and potentially dependent rewards. It analyzes posterior sampling, connects it to UCB methods, and derives broad Bayesian regret guarantees. The results extend to multiple model classes and simulations show performance surpassing various UCB algorithms, while confidence-bound and prior specification remain practical scope considerations.

  • Problem

    The paper addresses sequential optimization when an agent must learn an uncertain reward function while balancing exploration and exploitation across dependent or potentially infinite action spaces.

  • Method

    The paper analyzes posterior sampling, connects its Bayesian regret to UCB confidence-bound analyses, and develops a broad bound based on a dimension measuring dependence among action rewards.

  • Results

    Posterior sampling receives finite-time guarantees across several model classes, and simulations show it outperforming various proposed UCB algorithms.

  • Takeaways & Limitations

    Posterior sampling can retain appealing UCB-style theoretical properties without requiring explicitly designed optimism and can be useful for complicated optimization problems.

  • Takeaways & Limitations

    UCB alternatives may be preferable when simple efficient confidence bounds exist, while posterior sampling requires specifying an appropriate probabilistic model and prior.

Abstract

from arXiv · show

This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multi-armed bandit problems. The algorithm, also known as Thompson Sampling, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. This result lets us convert regret bounds developed for UCB algorithms into 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 model classes. This bound depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm Bayesian regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models. Further, our analysis provides insight into performance advantages of posterior sampling, which are highlighted through simulation results that demonstrate performance surpassing recently proposed UCB algorithms.

1. Introduction.

The paper studies posterior sampling as an alternative to UCB for sequential optimization with dependent rewards, infinite action spaces, and general model uncertainty. It develops theoretical links and broad Bayesian regret bounds, complemented by simulations.

  • Problem setting: The setting allows infinite action spaces and general relationships among action rewards represented by a prior over reward functions.This contrasts with classical bandits, which typically use finitely many independently modeled actions.
  • Posterior sampling: Posterior sampling randomly selects an action according to the probability that it is optimal, unlike UCB’s optimistic confidence-bound selection.The algorithm is also known as Thompson sampling or probability matching.
  • Empirical comparison: Simulations show posterior sampling outperforming various UCB algorithms proposed in the literature.The paper also motivates posterior sampling by its simpler design process when confidence-set construction is difficult.
  • Theoretical contributions: The first theoretical contribution connects posterior sampling with UCB algorithms, allowing existing UCB analyses to yield Bayesian regret bounds.Posterior sampling preserves analogous theoretical properties without explicitly designed optimism.
  • Theoretical contributions: The second contribution provides a broad Bayesian regret bound based on a new dimension measuring dependence among action rewards.The bound can be specialized to many model classes and is contrasted with standard supervised-learning dimensions.

2. Related Literature.

Related work establishes the paper’s focus on Bayesian regret, general priors, dependent-action models, and finite-time guarantees across multiple model classes. The paper extends prior results beyond narrower independent-arm or specialized settings.

  • Performance measure: Earlier posterior-sampling studies often analyzed regret under convenient uninformative priors, whereas this paper focuses on Bayesian regret.The paper emphasizes expected performance under a prior distribution.
  • Research gap: Posterior sampling had limited finite-time theory despite prior empirical success, motivating additional performance bounds.Earlier work established asymptotic convergence, while finite-time guarantees remained limited.
  • Scope: Existing bounds covered finite independent Bernoulli arms, while the paper allows complicated relationships among rewards and large or infinite action sets.The paper’s finite-action bound does not require independent action modeling.
  • Finite actions: The paper’s finite-action Bayesian regret bound is of order |A|T log T and matches what is implied by prior analysis.The supplied passage presents the order in a fragmented form; the comparison to Agrawal and Goyal is explicit.
  • Linear models: For compact linear action sets, the paper gives a Bayesian regret bound of order d√(T ln T), order-optimal up to a factor of ln T.The result is stated as stronger than bounds implied by earlier work.
  • Additional model classes: The paper establishes finite-time bounds for sparse linear, generalized linear, Gaussian-prior, and broad function classes.Its broad bounds depend on a new notion of dimension.
  • Formal framework: The formal framework models actions, reward functions indexed by parameters, and observed rewards under a prior over the true reward function.It also accommodates stochastic action sets and contextual, cautious, and adaptive-adversary settings.

3. Problem Formulation.

The formulation defines sequential decision-making with uncertain reward functions, Bayesian regret, and potentially changing action sets. This framework covers contextual and cautious decisions and supports tractable posterior-sampling implementations in some structured settings.

  • Problem Formulation: The agent selects actions from available sets, observes rewards, and acts through a history-dependent policy.The model includes an action set, parameter-indexed reward functions, and a true reward function indexed by θ.
  • On Regret and Bayesian Regret: T-period Bayesian regret is the prior expectation of the policy’s T-period regret and is also called Bayes risk or expected regret.The paper notes that measurability conditions are assumed so the relevant expectations are well-defined.
  • On Regret and Bayesian Regret: Bayesian regret bounds can imply probabilistic regret bounds through Markov’s inequality.The paper states that BayesRegret(T,π)=O(g(T)) implies Regret(T,π,θ)=O_P(g(T)).
  • On Regret and Bayesian Regret: Bayesian regret is robust to prior misspecification in a sense quantified by the density ratio between the true and working priors.The misspecified-prior bound includes Bayesian regret under the working prior without misspecification.
  • On Regret and Bayesian Regret: With a symmetric linear-model instance, posterior sampling’s Bayesian regret equals its worst-case regret because regret is the same across parameter realizations.The paper also notes that least-favorable priors are more suitable for strong minimax bounds than uniform priors.
  • On Changing Action Sets: Stochastic time-varying action sets represent contextual bandits by encoding state-action pairs as actions available in each context.This converts contextual decisions into the paper’s changing-action-set formulation.
  • On Changing Action Sets: Restricting available actions to conservative choices supports exploration while defining regret relative to the best conservative action.The framework is intended to address exploration where very poor performance should be avoided.
  • On Changing Action Sets: For Gaussian linear rewards over polytopes or ellipsoids, posterior sampling can be implemented through tractable optimization problems.The construction uses Gaussian posteriors and cautious action sets based on confidence regions.

4. Algorithms.

The paper contrasts UCB’s optimism and confidence-bound design with posterior sampling’s randomized action selection. Posterior sampling can simplify difficult model and action-selection problems, though UCB may remain preferable when simple efficient confidence bounds exist.

  • UCB algorithms: UCB algorithms construct upper confidence bounds and select actions using the greatest statistically plausible reward values.Their optimism encourages exploration and adapts as observations reduce uncertainty.
  • UCB algorithms: Independent-arm UCB updates sample-average reward estimates and action counts before selecting an optimistic action.The supplied algorithm passages identify initialization, statistics updates, action selection, and iteration.
  • UCB algorithms: Linear-Gaussian UCB updates posterior mean and covariance statistics before selecting an action using its confidence-bound objective.The corresponding linear model uses a Gaussian prior and Gaussian reward noise.
  • Posterior sampling: Posterior sampling samples a model from the posterior and chooses an action maximizing the sampled reward function.For linear models, it maximizes the inner product between action features and the sampled parameter.
  • Design trade-offs: Simple, efficient UCB algorithms may be preferable, while posterior sampling is motivated by complicated problems where optimistic-algorithm design is challenging.Posterior sampling requires a fully probabilistic model, and its practical suitability depends on the setting.
  • Design trade-offs: UCB performance depends critically on designing confidence bounds, and posterior quantiles may require extensive Monte Carlo simulation when no closed form exists.The difficulty includes choosing appropriate bounds for complex models.
  • Design trade-offs: Posterior sampling can offer computational advantages when UCB action selection is intractable over large action spaces.The paper illustrates this with maximizing a linear function versus an upper confidence bound over a polytope.
  • Posterior sampling: Posterior sampling uses randomization rather than upper confidence bounds to encourage exploration.This difference underlies the paper’s connection between the two algorithm classes.

5. Confidence Bounds and Regret Decompositions.

The section decomposes UCB and posterior-sampling regret using confidence bounds, showing that posterior sampling admits an analogous bound that applies across confidence-bound sequences.

  • 5.1. UCB Regret Decomposition: UCB regret decomposes into an optimism error and the confidence-interval width for the selected action.The first term is typically negative when the upper confidence bound is valid, while the second measures uncertainty about the chosen action.
  • 5.1. UCB Regret Decomposition: Taking expectations converts the UCB regret decomposition into a T-period Bayesian-regret bound for the policy induced by the confidence bounds.The policy is denoted πU.
  • 5.2. Posterior Sampling Regret Decomposition: Posterior sampling has an analogous Bayesian-regret decomposition for any real-valued confidence-bound sequence based on the observed history.Conditioned on the history, the optimal action and posterior-sampled action are identically distributed.
  • 5.2. Posterior Sampling Regret Decomposition: Posterior sampling’s bound applies simultaneously to all confidence-bound sequences, unlike a UCB bound tied to the sequence used by its algorithm.This makes posterior sampling depend on the best possible confidence-set choice in the analysis rather than a specifically designed sequence.
  • 5.2. Posterior Sampling Regret Decomposition: The connection allows existing UCB regret analyses to yield Bayesian-regret bounds for posterior sampling without requiring the algorithm itself to use explicit optimism.The analysis uses confidence bounds even though posterior sampling’s actual performance does not depend on them.

6. From UCB to Posterior Sampling Regret Bounds.

The section transfers UCB analyses to posterior sampling and derives bounds for finite-action, linear, generalized-linear, and broader function-class models. The resulting bounds accommodate infinite action sets and, in the general framework, recover the strongest linear-model bound while improving on prior generalized-linear results.

  • From UCB to Posterior Sampling Regret Bounds: Existing UCB analyses specify high-probability lower and upper confidence bounds and control their cumulative widths, enabling corresponding Bayesian-regret bounds for posterior sampling.The regret decomposition supplies the bridge between the UCB confidence-set analysis and posterior sampling.
  • 6.1. Finitely Many Actions: Finite-action bounds assume |A| = K < ∞ and rewards in [0,1], while the broader setup permits light-tailed rewards and otherwise unrestricted reward-function classes.The finite-action proposition provides a bound for any T under these bounded-reward assumptions.
  • 6.2. Structured Models: Dimension-dependent bounds replace dependence on the number of actions, accommodating infinite action sets and potentially improving substantially when many actions are available.The section treats linear and generalized-linear models as examples of this approach.
  • 6.2.1. Linear Models: Linear-model bounds follow from the posterior-sampling regret decomposition combined with prior confidence-set analyses, including a sparsity-sensitive bound depending on E∥θ∥0.The zero-norm counts nonzero components and can be much smaller than d for sparse reward representations.
  • 6.2.2. Generalized Linear Models: Generalized-linear analysis uses an initial designed exploration period of d linearly independent actions before applying posterior sampling, yielding a bound with additional dependence on the slope of g.A later result is stated to provide a stronger bound for standard posterior sampling without designed exploration.
  • 6.3. Gaussian Processes: For uniformly bounded reward functions in an otherwise arbitrary known class, the general analysis identifies dependence among actions through a new dimension notion based on ϵ-independence.The notion captures nonlinear and approximate dependence and bounds how often selected-action confidence widths exceed a threshold.

7. Bounds for General Function Classes.

The section develops Bayesian regret bounds for broad function classes using confidence sets and the new eluder dimension, then specializes them to linear and generalized linear models. It also shows why supervised-learning dimension measures can miss the difficulty of inferring unobserved action rewards.

  • Motivation: Unrestricted function classes can yield Bayesian regret T, so meaningful bounds must depend on the function class F.The example uses A = [0,1], indicator rewards, and a uniformly distributed parameter.
  • Complexity Measures: The analysis measures function-class complexity through Kolmogorov dimension and eluder dimension.Kolmogorov dimension captures covering-number growth, while eluder dimension captures how effectively unobserved rewards can be inferred from observed samples.
  • Confidence Bounds: Confidence sets convert posterior-sampling regret into bounds involving confidence-interval widths over selected actions.The construction uses statistically plausible function sets Ft and width wF(a) = supf∈F f(a) − inff∈F f(a).
  • Eluder Dimension: The ϵ-eluder dimension is the longest sequence of actions in which each action is ϵ′-independent of its predecessors for some ϵ′ ≥ ϵ.Replacing linear independence with ϵ-independence captures nonlinear and approximate dependence.
  • Model Specializations: For d-dimensional linear models, the resulting Bayesian regret bound is O(d√T log(T)), matching the best available linear UCB bound up to a log T factor.The bound follows from dimE(F,ϵ) = O(dlog(1/ϵ)) and dimK(F) = O(d).
  • Model Specializations: For generalized linear models, the bound is O(rd√T log(rT)) and slightly improves the strongest previously available Bayesian regret bound for any algorithm in that setting.Here r bounds the ratio between maximal and minimal slopes of the link function.
  • Why Eluder Dimension: In a finite binary indicator class, eluder dimension is n while VC dimension is 1, even though supervised prediction error reaches 1/n in constant time.This contrast motivates using eluder dimension for sequential optimization with dependent action rewards.
  • Simulation Results: Simulations show posterior sampling significantly outperforms the compared UCB algorithms, with loose confidence sets identified as the cause of the discrepancy.The comparison is described in the simulation section rather than established by the general bound.

8. Simulation Results.

The simulations compare posterior sampling with several UCB methods in a Gaussian linear model and report lower average regret for posterior sampling than the standard UCB algorithms. A tuned heuristic performs best, but requires horizon-specific parameter tuning.

  • Experimental Setting: The simulation uses a 10-dimensional Gaussian linear model with 100 actions and standard Gaussian observation noise.The parameter has mean zero and covariance matrix 10I.
  • Experimental Setting: Figure 1 reports the portion of regret attributable to each time period over the first 1000 periods, averaged across 5000 trials.The plotted quantity is the per-period linear-model regret contribution.
  • Simulation Comparison: In the 1000-period linear-model simulation, posterior sampling incurred average regret 97.5, versus 339.7 for linear UCB and 198.7 for Gaussian UCB.The results compare the algorithms over the same simulation setting.
  • Simulation Comparison: A tuned Gaussian UCB heuristic achieved average regret 68.9, outperforming posterior sampling and the untuned UCB methods.Its parameter was tuned to minimize average regret over the first 1000 periods.
  • Practical Trade-offs: The tuned heuristic requires the time horizon to be fixed and known, whereas posterior sampling avoids confidence-bound design.The paper presents this as a practical distinction in algorithm design.
  • Interpretation: The paper attributes the gap between posterior sampling and the compared UCB methods to confidence sets that are too loose for good performance.Even a UCB method using more sophisticated analysis incurred about three and a half times posterior sampling’s regret.

9. Conclusion.

The conclusion frames posterior sampling as a simple and computationally tractable approach whose Bayesian regret can be analyzed through confidence sets and a new dimension notion. It identifies two factors governing problem difficulty while noting that stronger bounds may remain possible.

  • Problem Complexity: Problem hardness depends on how well rewards at unobserved actions can be inferred from sampled actions and on maintaining confidence sets across actions.An error in evaluating any one possible action can produce large regret.
  • Scope: The bounds are nearly tight in some cases, but the paper expects further analysis to strengthen them in others.The authors present the work as a conceptual foundation for further study.

Appendix B: Proof of Confidence bound.

The appendix establishes a confidence-bound result through conditional cumulant-generating functions and a martingale stopping-time argument. It then controls boundary-crossing probabilities using Markov’s inequality and convergence.

  • Proof Setup: The proof defines adapted variables, conditional means, and conditional cumulant-generating functions for centered observations.These objects organize the concentration argument relative to the filtration.
  • Martingale Argument: The exponential process Mn(λ) is treated as a martingale with expectation one.This property is used at stopped times in the boundary-crossing proof.
  • Boundary Control: A stopping time records the first crossing of a boundary, after which Markov’s inequality bounds the probability of crossing.The proof introduces τx as the first n for which Mn(λ) reaches x.
  • Boundary Control: Taking n to infinity and applying monotone convergence yields the limiting probability bound for the martingale process.The argument transitions from finite-horizon crossing events to the infinite-horizon event.

B.2. Proof of Lemma 3.

The proof transforms the problem so an exponential martingale result applies under conditionally mean-zero, bounded-moment noise. It then selects parameters and invokes the definition of P_t to obtain the desired bound.

  • The proof sets H_{t−1} as the σ-algebra generated by the history, action, and parameter.
  • The noise ϵ_t is conditionally mean-zero and has a bounded conditional moment-generating function.
  • The argument chooses λ = 1/(4σ^2) and x = log(1/δ) before applying the definition of P_t.

B.3. Least Squares Bound - Proof of Proposition 6.

The proof controls least-squares deviations over an infinite function class by covering the class, applying a union bound, and then bounding the resulting discretization error.

  • An α-cover of F in the sup-norm reduces the analysis to finitely many representative functions.
  • A union bound yields a simultaneous high-probability inequality for every representative function and every time t.
  • The finite-cover bound is extended to all functions by controlling the discretization error.
  • Taking the infimum over cover sizes produces the resulting least-squares bound.

B.4. Discretization Error.

The discretization analysis bounds the loss incurred when replacing a function by a uniformly close cover element, and relates the eluder dimension to action-space size.

  • Discretization Error: If ||f − f^α||∞ ≤ α, the discretization error is bounded by αη_t with high probability.
  • Discretization Error: The proof bounds the per-round squared-loss difference using the reward magnitude, function bound, and cover radius.
  • Eluder Dimension: The ε-eluder dimension is the longest action sequence satisfying the stated dependence condition for some ε′ ≥ ε.
  • Eluder Dimension: For finite action spaces, the ε-eluder dimension is bounded by |A| for every ε > 0.

C.2. Linear Case.

The section bounds the eluder dimension for linear and generalized linear function classes using feature geometry and determinant-growth arguments. The generalized linear result assumes a differentiable, strictly increasing link with uniformly bounded derivative.

  • Linear Case: For linear rewards f_θ(a) = θ^Tφ(a), the eluder dimension is bounded under norm bounds on parameters and features.
  • Linear Case: The proof measures dependence through quadratic forms involving feature vectors and a regularized covariance matrix.
  • Linear Case: Repeatedly large dependence widths force determinant growth in the regularized covariance matrix.
  • Generalized Linear Case: For generalized linear rewards f_θ(a) = g(θ^Tφ(a)), the eluder dimension is bounded when g is differentiable and strictly increasing with bounded derivative.
  • Generalized Linear Case: The generalized linear proof follows the same three-step structure as the linear proof and bounds the number of times dependence exceeds ε′.
Loading 1301.2609v5…