The polynomial-time algorithm matches contextual-bandit lower bounds.
Users are excited about the new algorithm achieving horizon-free asymptotically optimal regret in tabular RL because they see it as great work.
No Digg Deeper questions have been answered for this story yet.
Asymptotically optimal regret for tabular reinforcement learning, with no dependence whatsoever on the horizon. http://arxiv.org/abs/2607.19854
🚨 New paper: “Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence.” We give the first polynomial-time algorithm for time-homogeneous tabular MDPs whose regret term is both: • completely independent of the horizon H, and • asymptotically optimal in S, A, and K. Our regret bound is Õ(√SAK + S⁸A³) matching the contextual-bandit lower bound Ω(√SAK) in the leading term. Technically, we introduce: • an S-dimensional discretization of the monotone optimal value sequence; • a new cutting bonus for horizon-free optimism; • a total-deviation bound controlling clipped variance independently of H; and • a horizon-truncation framework enabling reward-aware exploration. 📄 https://arxiv.org/abs/2607.19854 Greatly thankful to collaborators Zihan Zhang, Maryam Fazel, @SimonShaoleiDu
🚨 New paper: “Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence.” We give the first polynomial-time algorithm for time-homogeneous tabular MDPs whose regret term is both: • completely independent of the horizon H, and • asymptotically optimal in S, A, and K. Our regret bound is Õ(√SAK + S⁸A³) matching the contextual-bandit lower bound Ω(√SAK) in the leading term. Technically, we introduce: • an S-dimensional discretization of the monotone optimal value sequence; • a new cutting bonus for horizon-free optimism; • a total-deviation bound controlling clipped variance independently of H; and • a horizon-truncation framework enabling reward-aware exploration. 📄 https://arxiv.org/abs/2607.19854 Greatly thankful to collaborators Zihan Zhang, Maryam Fazel, @SimonShaoleiDu
[1/7] Why is removing H difficult? Even when the transition kernel is time-homogeneous, the optimal value functions {V₁⋆, V₂⋆, …, Vₕ⋆} are time-inhomogeneous. For each state-action pair, the learner must estimate one transition distribution accurately against a potentially enormous sequence of value functions. Previous concentration methods introduce a min{log H, S} factor. The main challenge is therefore not merely estimating the transition model. It is controlling its error uniformly over a long, structured, time-varying sequence of value functions.
[2/7] Our first key observation is structural. Because rewards are nonnegative, the optimal values are monotone in the remaining horizon. For every state s: V₁⋆(s) ≥ V₂⋆(s) ≥ … ≥ Vₕ⋆(s). This means the sequence {Vₕ⋆}ₕ₌₁ᴴ is far less complex than an arbitrary collection of H vectors in [0,1]ˢ. We exploit this monotonicity by projecting the value sequence onto a carefully constructed S-dimensional grid. The number of relevant projected vectors can then be bounded independently of H. The projection alone, however, is not sufficient: naive discretization can artificially increase variance. This motivates our second idea.
[4/7] The third ingredient is a new horizon-free total-deviation bound for time-homogeneous MDPs which bounds total clipped-variance. For a transition distribution p, value vector v, and cutoff x ≥ 0, define the x-clipped variance as: 𝕍ₓ(p,v) = ∑ₛ p(s) min{(v(s) − p·v)², x²}. We prove that for any deterministic Markov policy π and initial state s: 𝔼π[∑ₕ₌₁ᴴ 𝕍ₓ(Pₛₕ,ₐₕ, Vₕ₊₁⋆) | s₁ = s] ≤ x·2S. Crucially, this bound has no dependence on H and we can use x to control the scale. The proof uses a new potential function. Monotonicity of the optimal value sequence lets us relate each one-step deviation to an expected decrease in this potential. Because the potential is bounded by 2S, the total deviation, and therefore the clipped variance, remains horizon-free. This is what allows the residual part of the cutting bonus to be summed at the scale required for the √SAK leading term. The total-deviation bound may also be useful beyond this particular regret analysis.
[3/7] We introduce a cut projection and a corresponding cutting bonus. The basic idea is to treat coordinates differently depending on how far they are from the mean value under a transition distribution: • Coordinates with large deviations are discretized and retained in the cut component • Coordinates close to the mean remain in a residual component Why is this useful? Large deviations dominate the ordinary variance and can be handled using concentration over a finite, horizon-independent function class. The residual contains only local fluctuations around the mean, so its contribution can be controlled through a clipped-variance quantity. The resulting bonus preserves both optimism and the monotonicity needed for dynamic programming. Although the cutting operation is discontinuous, we prove a relaxed monotonicity property, up to a universal constant, which is sufficient to propagate optimism through backward induction.
[5/7] Our fourth ingredient is horizon truncation with reward-aware exploration. Previous horizon-free algorithms rely on a largely reward-free sample-collection phase, which can be expensive. Instead, our algorithm first follows an optimistic policy for the actual reward function. Reward-free exploration is invoked only when this policy reaches an insufficiently learned state-action pair. A difficulty is that such a pair might be reached very late in the episode, leaving too little time to collect useful samples. We therefore plan on a slightly truncated horizon and reserve a short suffix of every episode for exploration. Choosing the truncation carefully makes the total approximation cost O(√SAK), while ensuring that enough steps remain for effective exploration whenever an unlearned pair is encountered.
@VectorZhou WoW. Great work!
[7/7] Conceptually, our result implies that in asympotitc sense, long-horizon RL is no more difficult than a contextual bandit problem. The main open question is whether the S⁸A³ burn-in term can be substantially reduced to SA. A positive answer would suggest that time-homogeneous tabular RL is no harder than contextual bandits even at the finite-sample level. A lower bound on the burn-in, on the other hand, would reveal a genuine separation between learning actions and learning state-transition dynamics.
[6/7] How does this compare with prior work? Zhang et al. (2021) obtained: Õ(√SAK log H + S²A log H), which has an optimal leading dependence on S, A, and K, but still depends logarithmically on H. Li et al. (2021) showed that completely horizon-free learning is information-theoretically possible, but with exponential dependence on S. Zhang et al. (2022) gave the first polynomial-time horizon-free algorithm, with regret: Õ(√(S⁹A³K)). Our result is both completely horizon-free and tight in leading term.