Data to 14 Oct 2026

Learning to Optimize Via Posterior Sampling

arXiv 1301.2609 ↗First posted 11 Jan 2013cs.LGcited by 256

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 256 papers in the map (data through 14 Oct 2026). First posted on arXiv 11 Jan 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 48; 2022: 43; 2023: 44; 2024: 40; 2025: 38; 2026: 42.

256 papers.

Sort:

By area:

2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
2023Supervised Pretraining Can Learn In-Context Reinforcement Learningcited by 139
2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
2021Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observabilitycited by 109
2022POEM: Out-of-Distribution Detection with Posterior Samplingcited by 108
2025Outcome-based Exploration for LLM Reasoningcited by 83
2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
2021Meta-Thompson Samplingcited by 63
2021Reinforcement Learning, Bit by Bitcited by 59
2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46

38 more

2021MobILE: Model-Based Imitation Learning From Observation Alonecited by 44
2021Fairness of Exposure in Stochastic Banditscited by 43
2022Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterizationcited by 37
2021Hierarchical Bayesian Banditscited by 35
2022On the Complexity of Adversarial Decision Makingcited by 33
2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
2021No Regrets for Learning the Prior in Banditscited by 30
2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
2025Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Rewardcited by 27
2021Metadata-based Multi-Task Bandits with Bayesian Hierarchical Modelscited by 24
2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
2021Online Multi-Armed Bandits with Adaptive Inferencecited by 22
2022Surrogate modeling for Bayesian optimization beyond a single Gaussian processcited by 22
2022How to talk so AI will learn: Instructions, descriptions, and autonomycited by 22
2022Langevin Monte Carlo for Contextual Banditscited by 22
2023Efficient Exploration in Continuous-time Model-based Reinforcement Learningcited by 22
2021Policy Learning with Adaptively Collected Datacited by 21
2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
2021Information Directed Sampling for Sparse Linear Banditscited by 20
2021Parallelizing Thompson Samplingcited by 20
2022Multi-Fidelity Cost-Aware Bayesian Optimizationcited by 20
2021Batched Thompson Samplingcited by 19
2022Deep Hierarchy in Banditscited by 19
2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
2023Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processescited by 19
2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 18
2023Algorithm Selection for Deep Active Learning with Imbalanced Datasetscited by 18
2021Online Learning for Unknown Partially Observable MDPscited by 17
2021Bayesian Optimization over Permutation Spacescited by 17
2025Toward Efficient Exploration by Large Language Model Agentscited by 17
2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
2021Thompson Sampling with a Mixture Priorcited by 16
2021Metalearning Linear Bandits by Prior Updatecited by 16

50 most cited of 256 All 256 (JSON)