Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Summary

This theory paper resolves two open questions in reinforcement learning with multi-step transition look-ahead, where the agent observes, before acting, which states would be visited under any sequence of ℓ actions. First, it proves exact planning is NP-hard for every fixed rational discount factor γ∈(0,1) and every look-ahead depth ℓ≥2 (Theorem 1), extending earlier hardness that required γ close to one; the reduction gives the waiting action reward (1−γ)T so the baseline value survives discounting. Second, it gives a randomized polynomial-time approximation scheme (Theorem 2): an offline dictionary of N sampled transition tables supports value iteration on S×[N]^ℓ, and an online backward recursion inserts the observed window exactly, producing a uniformly εVmax-optimal policy with probability 1−δ in time polynomial in n, m, ε⁻¹, log(1/δ), and (1−γ)⁻¹ for fixed ℓ — polynomial rather than exponential in the effective horizon, unlike sparse sampling. Third, for unknown transitions and stochastic rewards, DLA-UCB combines optimism with variance-adaptive Bernstein bonuses, achieving regret Õ(Rmax√(nmT/(1−γ)) + Rmax·n²m/(1−γ)²) (Theorem 3), whose leading term matches classical tabular discounted RL up to logarithmic factors. A noisy look-ahead extension (Theorems 4–5) degrades the lower-order term to n³m. Main limitations: dictionary memory scales as nN^ℓ with N of order (1−γ)⁻⁴ε⁻², likely prohibitive near γ→1, and the experiments section (Appendix B) describes a wind-farm benchmark setup but reports no numerical results in the provided text.