mlsanityData to 7 Oct 2026

Worst-Case Regret Bounds for Exploration via Randomized Value Functions

arXiv 1906.02870 ↗First posted 7 Jun 2019cs.LG cs.AI cs.SYcited by 57

Not on the map. Why?

Abstract (arXiv)

This paper studies a recent proposal to use randomized value functions to drive exploration in reinforcement learning. These randomized value functions are generated by injecting random noise into the training data, making the approach compatible with many popular methods for estimating parameterized value functions. By providing a worst-case regret bound for tabular finite-horizon Markov decision processes, we show that planning with respect to these randomized value functions can induce provably efficient exploration.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

57 papers.

Sort:

By area:

  1. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  2. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  3. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  4. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  5. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  6. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  7. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  8. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  9. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  10. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  11. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  12. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
38 more
  1. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  2. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  3. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  4. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  5. 2025Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learningcited by 17
  6. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  7. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  8. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  9. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited 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. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  13. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  14. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  15. 2025Posterior Behavioral Cloning: Pretraining BC Policies for Efficient RL Finetuningcited by 8
  16. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  17. 2022Neural Design for Genetic Perturbation Experimentscited by 6
  18. 2021Exponential Family Model-Based Reinforcement Learning via Score Matchingcited by 5
  19. 2022Data-pooling Reinforcement Learning for Personalized Healthcare Interventioncited by 5
  20. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  21. 2026Learning to Explore with Parameter-Space Noise: A Deep Dive into Parameter-Space Noise for Reinforcement Learning with Verifiable Rewardscited by 5
  22. 2021Random Effect Banditscited by 4
  23. 2022Provably Efficient Kernelized Q-Learningcited by 4
  24. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  25. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  26. 2023Fair Active Learning in Low-Data Regimescited by 2
  27. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  28. 2023Dyadic Reinforcement Learningcited by 1
  29. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  30. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  31. 2025Universal Value-Function Uncertaintiescited by 1
  32. 2025Q-learning with Posterior Samplingcited by 1
  33. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  34. 2023Exploration in Model-based Reinforcement Learning with Randomized Rewardcited by 0
  35. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  36. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  37. 2025Thompson Sampling in Online RLHF with General Function Approximationcited by 0
  38. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachcited by 0

50 most cited of 57 All 57 (JSON)