mlsanityData to 7 Oct 2026

Near-Optimal Randomized Exploration for Tabular Markov Decision Processes

arXiv 2102.09703 ↗First posted 19 Feb 2021cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case widetildeOleft(H√SATright) regret bound for episodic time-inhomogeneous Markov Decision Process where S is the size of state space, A is the size of action space, H is the planning horizon and T is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the Omegaleft(H√SATright) lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 35 of its 64 references that are in the map. First posted on arXiv 19 Feb 2021.

Builds on

35 of 64 references.

References · 35

  1. 2018Exploration by Random Network Distillationcited by 966
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2017Noisy Networks for Explorationcited by 262
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 218
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2017Deep Exploration via Randomized Value Functionscited by 155
  12. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
23 more
  1. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  2. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  3. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2020Q-learning with Logarithmic Regretcited by 59
  10. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  11. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  12. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  13. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  14. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  15. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  16. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  17. 2020MOTS: Minimax Optimal Thompson Samplingcited by 28
  18. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  19. 2013Prior-free and prior-dependent regret bounds for Thompson Samplingcited by 25
  20. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  21. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  22. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  23. 2019Parameterized Indexed Value Function for Efficient Exploration in Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 3; 2025: 4; 2026: 5.

14 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  3. 2025Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learningcited by 17
  4. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  5. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  6. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  7. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  8. 2025Q-learning with Posterior Samplingcited by 1
  9. 2025Thompson Sampling in Online RLHF with General Function Approximationcited by 0
  10. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
  11. 2026Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Banditscited by 0
  12. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0
2 more
  1. 2026Mathematical methods of reinforcement learningcited by 0
  2. 2026ForgetMimic: Motion Unlearning for Reinforcement Learning Humanoid Controlcited by 0