mlsanityData to 7 Oct 2026

Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning

arXiv 1802.04020 ↗First posted 12 Feb 2018cs.LG stat.MLcited by 65

Not on the map. Why?

Abstract (arXiv)

We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound c on the span of the optimal bias function is known. For an MDP with S states, A actions and Gamma ≤ S possible next states, we prove a regret bound of widetildeO(c√Gamma SAT), which significantly improves over existing algorithms (e.g., UCRL and PSRL), whose regret scales linearly with the MDP diameter D. In fact, the optimal bias span is finite and often much smaller than D (e.g., D=∞ in non-communicating MDPs). A similar result was originally derived by Bartlett and Tewari (2009) for REGAL.C, for which no tractable algorithm is available. In this paper, we relax the optimization problem at the core of REGAL.C, we carefully analyze its properties, and we provide the first computationally efficient algorithm to solve it. Finally, we report numerical simulations supporting our theoretical findings and showing how SCAL significantly outperforms UCRL in MDPs with large diameter and small span.

Key facts. Cited by 65 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 9; 2023: 15; 2024: 13; 2025: 7; 2026: 6.

65 papers.

Sort:

By area:

  1. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  2. 2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
  3. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  4. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  5. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  6. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  8. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  9. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  10. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  11. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  12. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
38 more
  1. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  2. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  3. 2023Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Criticcited by 20
  4. 2023A Study of Global and Episodic Bonuses for Exploration in Contextual MDPscited by 19
  5. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  6. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  7. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  8. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  9. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  10. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  11. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  12. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  13. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  14. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  15. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  16. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  17. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 9
  18. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  19. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  20. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  21. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  22. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7
  23. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  24. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  25. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  26. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  27. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  28. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  29. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  30. 2021Bad-Policy Density: A Measure of Reinforcement Learning Hardnesscited by 2
  31. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  32. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  33. 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
  34. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  35. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  36. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  37. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  38. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1

50 most cited of 65 All 65 (JSON)