mlsanityData to 7 Oct 2026

Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

arXiv 1906.05110 ↗First posted 12 Jun 2019cs.LG stat.MLcited by 43

Not on the map. Why?

Abstract (arXiv)

We present an algorithm based on the Optimism in the Face of Uncertainty (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space efficiently. By evaluating the state-pair difference of the optimal bias function h*, the proposed algorithm achieves a regret bound of tildeO(√SAHT)footnoteThe symbol tildeO means O with log factors ignored. for MDP with S states and A actions, in the case that an upper bound H on the span of h*, i.e., sp(h*) is known. This result outperforms the best previous regret bounds tildeO(S√AHT) citepfruit2019improved by a factor of √S. Furthermore, this regret bound matches the lower bound of Omega(√SAHT) citepjaksch2010near up to a logarithmic factor. As a consequence, we show that there is a near optimal regret bound of tildeO(√SADT) for MDPs with a finite diameter D compared to the lower bound of Omega(√SADT) citepjaksch2010near.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 9; 2023: 5; 2024: 10; 2025: 3; 2026: 4.

43 papers.

Sort:

By area:

  1. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  2. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  3. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  4. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  5. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  6. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  7. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  8. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  9. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  10. 2021Sublinear Regret for Learning POMDPscited by 19
  11. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  12. 2021Online Learning for Unknown Partially Observable MDPscited by 17
31 more
  1. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  2. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  3. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  4. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  5. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  6. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  7. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  8. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  9. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  10. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 9
  11. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  12. 2021Causal Markov Decision Processes: Learning Good Interventions Efficientlycited by 7
  13. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  14. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  15. 2022Provably Efficient Kernelized Q-Learningcited by 4
  16. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  17. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  18. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  19. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  20. 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
  21. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  22. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  23. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  24. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  25. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  26. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  27. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  28. 2024Reinforcement Learning and Regret Bounds for Admission Controlcited by 0
  29. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  30. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0
  31. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0