mlsanityData to 7 Oct 2026

Randomized Exploration for Reinforcement Learning with General Value Function Approximation

arXiv 2106.07841 ↗First posted 15 Jun 2021cs.LG stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm as well as the optimism principle. Unlike existing upper-confidence-bound (UCB) based approaches, which are often computationally intractable, our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. To attain optimistic value function estimation without resorting to a UCB-style bonus, we introduce an optimistic reward sampling procedure. When the value functions can be represented by a function class F, our algorithm achieves a worst-case regret bound of widetildeO(poly(dEH)√T) where T is the time elapsed, H is the planning horizon and dE is the textiteluder dimension of F. In the linear setting, our algorithm reduces to LSVI-PHE, a variant of RLSVI, that enjoys an widetildeO(√d3H3T) regret. We complement the theory with an empirical evaluation across known difficult exploration tasks.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). Builds on 23 of its 39 references that are in the map. First posted on arXiv 15 Jun 2021.

Builds on

23 of 39 references.

References · 23

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016OpenAI Gymcited by 1,684
  3. 2016Deep Exploration via Bootstrapped DQNcited by 518
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  8. 2017Noisy Networks for Explorationcited by 262
  9. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  10. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  12. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
11 more
  1. 2017Deep Exploration via Randomized Value Functionscited by 155
  2. 2020SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learningcited by 150
  3. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  4. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  8. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  9. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  10. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  11. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 5; 2023: 10; 2024: 11; 2025: 14; 2026: 5.

49 papers.

Sort:

By area:

  1. 2025Reasoning with Exploration: An Entropy Perspectivecited by 277
  2. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  3. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  4. 2023Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Criticcited by 20
  5. 2023ENOTO: Improving Offline-to-Online Reinforcement Learning with Q-Ensemblescited by 20
  6. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  7. 2025Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learningcited by 17
  8. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  9. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  10. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  11. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  12. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
37 more
  1. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  2. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  3. 2025Revisiting Entropy Regularization: Adaptive Coefficient Unlocks Its Potential for LLM Reinforcement Learningcited by 10
  4. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  5. 2025ReDit: Reward Dithering for Improved LLM Policy Optimizationcited by 8
  6. 2021Anti-Concentrated Confidence Bonuses for Scalable Explorationcited by 7
  7. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  8. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  9. 2024The Curse of Diversity in Ensemble-Based Explorationcited by 6
  10. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  11. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  12. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRiticcited by 5
  13. 2026Emergence of Exploration in Policy Gradient Reinforcement Learning via Retryingcited by 5
  14. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  15. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  16. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  17. 2023Pitfall of Optimism: Distributional Reinforcement Learning by Randomizing Risk Criterioncited by 3
  18. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  19. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  20. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximationcited by 2
  21. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  22. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  23. 2024Training on Irrelevant States Implies Data Augmentation: Generalization in Contextual MDPscited by 1
  24. 2025CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learningcited by 1
  25. 2025Universal Value-Function Uncertaintiescited by 1
  26. 2025Exploration by Random Reward Perturbationcited by 1
  27. 2023Exploration in Model-based Reinforcement Learning with Randomized Rewardcited by 0
  28. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximationcited by 0
  29. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  30. 2025Approximation to Deep Q-Network by Stochastic Delay Differential Equationscited by 0
  31. 2025Thompson Sampling in Online RLHF with General Function Approximationcited by 0
  32. 2025An Arbitration Control for an Ensemble of Diversified DQN variants in Continual Reinforcement Learningcited by 0
  33. 2025Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processescited by 0
  34. 2026Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distributioncited by 0
  35. 2026On the Equivalence of Random Network Distillation, Deep Ensembles, and Bayesian Inferencecited by 0
  36. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  37. 2026Deep Epistemic Value Functions for Optimistic Explorationcited by 0