Learning to Optimize via Posterior Sampling

By Daniel Russo, Benjamin Van Roy. 2013

780 citations recorded by the source corpus.

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 multiarmed bandit problems. The algorithm, also known as Thompson Sampling and as probability matching, 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...

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

In Probabilistic & Bayesian Methods

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “Let Φ( X ) denote the n × J matrix where [Φ( X )] i,j = φ j ( x i ) ; then the posterior is as in Bayesian linear regression, substituting Φ( X ) for the design matrix X .”
Balanced Linear Contextual Bandits (2018, background): “The existing literature has provided regret bounds (e.g., the general bounds of (Russo and Van Roy 2014), the bounds of (Rigollet and Zeevi 2010), (Perchet and Rigollet 2013), (Slivkins 2014) in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.g.,…”
Estimation Considerations in Contextual Bandits (2017, neutral): “, the general bounds of [51], the bounds of [50, 49, 56] in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.”
Learning to Learn for Global Optimization of Black Box Functions (2016, background): “Here again we encounter a huge variety of strategies, including Thompson sampling [Thompson, 1933, Scott, 2010, Chapelle and Li, 2011, Agrawal and Goyal, 2013], information gain [Villemonteix et al., 2009, Hennig and Schuler, 2012, Russo and Van Roy, 2014, Shahriari et al., 2014, Hern ´ andez-Lobato”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “Proposition 3 of [22], translated to our current context, establishes that for our maximal-reward path problem, the expected regret of PSRL satisﬁes One can design an OFU-based algorithm that obeys the same bound, as established in [7].”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “In this case it can be shown that the regret increases by a multiplicative factor related to the Radon-Nikodym derivative of the true prior with respect to the assumed prior [48, § 3.1].”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, neutral): “Our results suggest this method has great potential in reinforcement learning as well.”
Generalization and Exploration via Randomized Value Functions (2014, background): “Then, in period h = 0, 1, · · · , H−1, if the state is xh and an action ah is selected then a subsequent state xh+1 is sampled from P (·|xh, ah) and a reward rh is sampled from R (·|xh, ah, xh+1).”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “In multi-arm bandit, there are compelling empirical pieces of evidence that Thompson Sampling can provide better results than optimism-under-uncertainty approaches [22], while the state of the art performance bounds are preserved [23], [24].”
A Tutorial on Thompson Sampling (2017, background): “A more formal link between the two approaches is established in [42].”
Deep Exploration via Randomized Value Functions (2017, background): “Further, the theory suggests that “well-designed” upper-confidence-bound-based approaches, which appropriately couple uncertainties across state-action pairs, but are often computationally intractable, are similarly near-optimal (statistically) and competitive with Thompson sampling in such contexts”
Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “M L ] 1 5 M ar 2 Any learning algorithm over Markov decision processes (MDPs) will have worst-case regret Ω( √”
Bandit Algorithms (2020, background): “We should mention there is a recent book on bandits by Slivkins [2018] that is currently in progress and freely available on-line.”
Provable Optimal Algorithms for Generalized Linear Contextual Bandits (2017, methodology): “Recently developed techniques for analyzing Bayes regret in BLM ban-dits (Russo & Van Roy, 2014) may be useful to analyze the cumulative regret considered here.”
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (2022, background): “…Long Beach, CA, USA. attractive empirical performance [Chapelle and Li, 2011, Kaufmann et al., 2012], as well as provably optimal performance bounds that have been recently obtained for many variations of MAB [Agrawal and Goyal, 2012, 2013b,a, Russo and Van Roy, 2015, 2014, Bubeck and Liu, 2013].”