# Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 42 references that are in the map.
- First posted on arXiv 22 Jul 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Towards Tractable Optimism in Model-Based Reinforcement Learning](https://mlsanity.com/paper/2006.11911/) (2020)

## Abstract (arXiv)

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with S states, A actions, horizon H, and per-trajectory total reward bounded by 1. We propose a new algorithm and prove a regret upper bound [tilde O(√SAK+S8A3)] with failure probability δ, where K is the number of episodes and tilde O(·) hides mathsfpolylog(S,A,K,1/δ). Thus, the regret is H-free and asymptotically optimal, matching the contextual-bandit lower bound Omega(√SAK) up to logarithmic factors. This completely removes the log H dependence from the previous tilde O(√SAKlog H+S2Alog H) guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret tilde O(√S9A3K) of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions Vh^*h=1H are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional minlog H,S factor. We avoid this factor by (i) exploiting the monotonicity of Vh^* in h and (ii) non-trivially projecting the value functions onto an S-dimensional grid. Our analysis relies on three additional ingredients. First, we introduce a horizon-truncation argument that enables reward-based exploration and removes the cost of a separate reward-free exploration phase. Second, we design a cutting bonus that preserves both optimism and the monotonicity needed for planning. Third, we prove a new bound on total deviation for time-homogeneous MDPs, which controls the clipped variance terms in the cutting bonus with adjustable polynomial dependence on S and without any dependence on H. Together, these tools yield an asymptotically optimal horizon-free regret guarantee.