mlsanityData to 14 Oct 2026

Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning

arXiv 2110.00871 ↗First posted 2 Oct 2021cs.LG math.ST stat.MLcited by 66

Not on the map. Why?

Abstract (arXiv)

Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this paper, we present a theoretical analysis of Thompson Sampling, with a focus on frequentist regret bounds. In this setting, we show that the standard Thompson Sampling is not aggressive enough in exploring new actions, leading to suboptimality in some pessimistic situations. A simple modification called Feel-Good Thompson Sampling, which favors high reward models more aggressively than the standard Thompson Sampling, is proposed to remedy this problem. We show that the theoretical framework can be used to derive Bayesian regret bounds for standard Thompson Sampling, and frequentist regret bounds for Feel-Good Thompson Sampling. It is shown that in both cases, we can reduce the bandit regret problem to online least squares regression estimation. For the frequentist analysis, the online least squares regression bound can be directly obtained using online aggregation techniques which have been well studied. The resulting bandit regret bound matches the minimax lower bound in the finite action case. Moreover, the analysis can be generalized to handle a class of linearly embeddable contextual bandit problems (which generalizes the popular linear contextual bandit model). The obtained result again matches the minimax lower bound. Finally we illustrate that the analysis can be extended to handle some MDP problems.

Key facts. Cited by 66 papers in the map (data through 14 Oct 2026). Builds on 15 of its 38 references that are in the map. First posted on arXiv 2 Oct 2021.

Builds on

15 of 38 references.

References · 15

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2013Learning to Optimize Via Posterior Samplingcited by 256
  4. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  5. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  6. 2017Deep Exploration via Randomized Value Functionscited by 156
  7. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  9. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  10. 2021Adapting to Misspecification in Contextual Banditscited by 81
  11. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  12. 2020Latent Bandits Revisitedcited by 44
3 more
  1. 2020Mirror Descent and the Information Ratiocited by 40
  2. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  3. 2014Bounded Regret for Finite-Armed Structured Banditscited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 14; 2023: 13; 2024: 16; 2025: 11; 2026: 12.

66 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  2. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  3. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  4. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  5. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  6. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  7. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 31
  8. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  9. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  10. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  11. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 27
  12. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
38 more
  1. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  2. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  3. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  4. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  5. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  6. 2024From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systemscited by 17
  7. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 16
  8. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  9. 2023Leveraging Demonstrations to Improve Online Learning: Quality Matterscited by 13
  10. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  11. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  12. 2022Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditscited by 11
  13. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  14. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  15. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  16. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  17. 2025When and why randomised exploration works (in linear bandits)cited by 8
  18. 2024Optimistic Information Directed Samplingcited by 7
  19. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  20. 2025LLM Routing with Dueling Feedbackcited by 7
  21. 2023VITS : Variational Inference Thompson Sampling for contextual banditscited by 6
  22. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  23. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  24. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  25. 2023Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewardscited by 5
  26. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  27. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  28. 2023Online Learning in Contextual Second-Price Pay-Per-Click Auctionscited by 4
  29. 2024Contextual Multinomial Logit Bandits with General Value Functionscited by 4
  30. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdowncited by 4
  31. 2026Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Banditscited by 4
  32. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  33. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  34. 2022Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimizationcited by 2
  35. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  36. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximationcited by 2
  37. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  38. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2

50 most cited of 66 All 66 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis
  2. 2023The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models
  3. 2023Thompson Sampling for Linear Bandit Problems with Normal-Gamma Priors
  4. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
  5. 2023Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits
  6. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
  7. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
  8. 2026RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits