# Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 51 references that are in the map.
- First posted on arXiv 24 Mar 2022.

## Builds on (most cited first, 29 of 29)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?](https://mlsanity.com/paper/2005.00527/) (2020)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes](https://mlsanity.com/paper/1807.02373/) (2018)
- [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021)

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

- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [VC Theory for Inventory Policies](https://mlsanity.com/paper/2404.11509/) (2024)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [Horizon-Free Regret for Linear Markov Decision Processes](https://mlsanity.com/paper/2403.10738/) (2024)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)
- [Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2305.08359/) (2023)
- [Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2312.04464/) (2023)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [A Unified Algorithm for Stochastic Path Problems](https://mlsanity.com/paper/2210.09255/) (2022)
- [Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation](https://mlsanity.com/paper/2508.02103/) (2025)
- [Utilizing Maximum Mean Discrepancy Barycenter for Propagating the Uncertainty of Value Functions in Reinforcement Learning](https://mlsanity.com/paper/2404.00686/) (2024)
- [The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability](https://mlsanity.com/paper/2506.09940/) (2025)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)

## Abstract (arXiv)

This paper gives the first polynomial-time algorithm for tabular Markov Decision Processes (MDP) that enjoys a regret bound independent on the planning horizon. Specifically, we consider tabular MDP with S states, A actions, a planning horizon H, total reward bounded by 1, and the agent plays for K episodes. We design an algorithm that achieves an Oleft(poly(S,A,log K)√Kright) regret in contrast to existing bounds which either has an additional polylog(H) dependency~citepzhang2020reinforcement or has an exponential dependency on S~citepli2021settling. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies, which can have applications in other problems related to Markov chains.