Regret Bounds for Reinforcement Learning via Markov Chain Concentration
Not on the map. Why?
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.
Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Aug 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 3; 2023: 3; 2024: 5; 2025: 2; 2026: 1.
19 papers.
Sort:
- 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
- 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
- 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
- 2021Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methodscited by 7
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
- 2024Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inferencecited by 7
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
- 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gapcited by 2
7 more
- 2025Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectivenesscited by 2
- 2021Curious Explorer: a provable exploration strategy in Policy Learningcited by 1
- 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
- 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
- 2023Markov Chain Concentration with an Application in Reinforcement Learningcited by 0
- 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning7 Aug 2026
- 2025Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness10 Nov 2025
- 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model30 Jul 2025
- 2024Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference18 Dec 2024
- 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games9 Nov 2024
- 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces25 Oct 2024
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May 2024
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation19 Apr 2024
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes28 Jun 2023
- 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap20 Jun 2023
- 2023Markov Chain Concentration with an Application in Reinforcement Learning7 Jan 2023
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs18 May 2022
7 more
- 2022Finite-Time Analysis of Natural Actor-Critic for POMDPs20 Feb 2022
- 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints31 Jan 2022
- 2021Dueling RL: Reinforcement Learning with Trajectory Preferences8 Nov 2021
- 2021Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods13 Sep 2021
- 2021Curious Explorer: a provable exploration strategy in Policy Learning29 Jun 2021
- 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPs13 Jun 2021
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation15 Feb 2021
- 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
- 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
- 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
- 2021Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methodscited by 7
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
- 2024Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inferencecited by 7
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
- 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gapcited by 2
12 most cited of 19 All 19 (JSON)
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning7 Aug 2026
- 2025Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness10 Nov 2025
- 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model30 Jul 2025
- 2024Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference18 Dec 2024
- 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games9 Nov 2024
- 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces25 Oct 2024
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May 2024
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation19 Apr 2024
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes28 Jun 2023
- 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap20 Jun 2023
- 2023Markov Chain Concentration with an Application in Reinforcement Learning7 Jan 2023
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs18 May 2022
12 newest of 19 All 19 (JSON)