# Regret Bounds for Reinforcement Learning via Markov Chain Concentration

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2018.

## Built on by (most cited first, 19 of 19)

- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods](https://mlsanity.com/paper/2109.06362/) (2021)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference](https://mlsanity.com/paper/2412.14355/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap](https://mlsanity.com/paper/2306.11271/) (2023)
- [Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness](https://mlsanity.com/paper/2511.07604/) (2025)
- [Curious Explorer: a provable exploration strategy in Policy Learning](https://mlsanity.com/paper/2106.15503/) (2021)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Markov Chain Concentration with an Application in Reinforcement Learning](https://mlsanity.com/paper/2301.02926/) (2023)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)
- [Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2608.07725/) (2026)

## Abstract (arXiv)

We give a simple optimistic algorithm for which it is easy to derive regret bounds of tildeO(√trm mix SAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter trm mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.