Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Equipping reinforcement learning agents with multi-step transition lookahead can significantly boost performance, yet exact planning remains NP-hard across any fixed rational discount factor. Resolving this computational barrier, this work develops a randomized polynomial-time approximation scheme for fixed lookahead depths. By incorporating optimism and variance-adaptive confidence bounds to handle unknown transitions and stochastic rewards, the resulting algorithm yields a cumulative regret bound whose leading term matches classical tabular discounted reinforcement learning up to logarithmic factors. It confirms that while exact optimization is computationally intractable, efficient near-optimal learning is attainable.