Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

arXiv:2607.19854v1 Announce Type: new Abstract: 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 [ilde O(sqrt{SAK}+S^8A^3)] with failure probability elta, where K is the number of episodes and ilde O(dot) hides mathsf{poly}log(S,A,K,1/elta). Thus, the regret is H-free and asymptotically optimal, matching the contextual-bandit lower bound Omega(sqrt{SAK}) up to logarithmic factors. This completely removes the log H dependence from the previous ilde O(sqrt{SAKlog H}+S^2Alog H) guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret ilde O(sqrt{S^9A^3K}) of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions {V_h^}_{h=1}^H are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional min{log H,S} factor. We avoid this factor by (i) exploiting the monotonicity of V_h^ 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.

Source: arXiv cs.LG | 2026-07-23