# Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

arXiv: https://arxiv.org/abs/1906.05110 · HTML: https://mlsanity.com/paper/1906.05110/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

## Built on by (most cited first, 30 of 44)

- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Understanding Domain Randomization for Sim-to-real Transfer](https://mlsanity.com/paper/2110.03239/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning](https://mlsanity.com/paper/2210.08238/) (2022)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [Causal Markov Decision Processes: Learning Good Interventions Efficiently](https://mlsanity.com/paper/2102.07663/) (2021)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)

## 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.