mlsanityData to 7 Oct 2026

Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent

arXiv 2402.10228 ↗First posted 5 Feb 2024cs.LG cs.AI stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We propose HyperAgent, a reinforcement learning (RL) algorithm based on the hypermodel framework for exploration in RL. HyperAgent allows for the efficient incremental approximation of posteriors associated with an optimal action-value function (Q^star) without the need for conjugacy and follows the greedy policies w.r.t. these approximate posterior samples. We demonstrate that HyperAgent offers robust performance in large-scale deep RL benchmarks. It can solve Deep Sea hard exploration problems with episodes that optimally scale with problem size and exhibits significant efficiency gains in the Atari suite. Implementing HyperAgent requires minimal code addition to well-established deep RL frameworks like DQN. We theoretically prove that, under tabular assumptions, HyperAgent achieves logarithmic per-step computational complexity while attaining sublinear regret, matching the best known randomized tabular RL algorithm.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 46 of its 72 references that are in the map. First posted on arXiv 5 Feb 2024.

Builds on

46 of 72 references.

References · 46

  1. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  3. 2021Deep Reinforcement Learning at the Edge of the Statistical Precipicecited by 781
  4. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 774
  5. 2015Dueling Network Architectures for Deep Reinforcement Learningcited by 769
  6. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  7. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  8. 2016Deep Exploration via Bootstrapped DQNcited by 518
  9. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  10. 2017A Tutorial on Thompson Samplingcited by 420
  11. 2020Data-Efficient Reinforcement Learning with Self-Predictive Representationscited by 309
  12. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
34 more
  1. 2017Noisy Networks for Explorationcited by 262
  2. 2022The Primacy Bias in Deep Reinforcement Learningcited by 242
  3. 2021Mastering Atari Games with Limited Datacited by 235
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 218
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  7. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  8. 2017Parameter Space Noise for Explorationcited by 158
  9. 2017Deep Exploration via Randomized Value Functionscited by 155
  10. 2023Bigger, Better, Faster: Human-level Atari with human-level efficiencycited by 145
  11. 2019Behaviour Suite for Reinforcement Learningcited by 129
  12. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 125
  13. 2021Epistemic Neural Networkscited by 120
  14. 2019When to use parametric models in reinforcement learning?cited by 118
  15. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  16. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  17. 2021APS: Active Pretraining with Successor Featurescited by 109
  18. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  19. 2021Reinforcement Learning, Bit by Bitcited by 59
  20. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
  21. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  22. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  23. 2015Bootstrapped Thompson Sampling and Deep Explorationcited by 40
  24. 2020Hypermodels for Explorationcited by 37
  25. 2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
  26. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  27. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  28. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  29. 2022An Analysis of Ensemble Samplingcited by 23
  30. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  31. 2022Langevin Monte Carlo for Contextual Banditscited by 22
  32. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  33. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  34. 2021State-Aware Variational Thompson Sampling for Deep Q-Networkscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 2.

6 papers.

  1. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  2. 2025Contextual Thompson Sampling via Generation of Missing Datacited by 5
  3. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximationcited by 2
  4. 2024Simple, unified analysis of Johnson-Lindenstrauss with applicationscited by 1
  5. 2024Probability Tools for Sequential Random Projectioncited by 1
  6. 2025Robust Search with Uncertainty-Aware Value Models for Language Model Reasoningcited by 1