Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
stat.ML, cs.LG
Submitted: 2026-09-10
Updated: 2026-09-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of actions before deciding its course of action.
Terminology
Abstract
We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of actions before deciding its course of action. Although look-ahead can substantially improve achievable performance, it is known that optimal planning with multi-step transition look-ahead is NP-hard, but this hardness was established using discount factors arbitrarily close to one. It was therefore unknown whether the problem remains hard for any discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed rational discount factor (γ in(0,1)), exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. We then extend our approach to unknown transitions and stochastic rewards using optimism and variance-adaptive confidence bounds. The resulting algorithm achieves cumulative regret whose leading term matches classical tabular discounted RL up to logarithmic factors. Thus, although exact planning with transition look-ahead is NP-hard, efficient near-optimal planning and learning remain possible.
Sources
- On the Complexity of Value Iteration
- Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
- Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
- On the Complexity of Solving Markov Decision Problems
- Learning in Markov Decision Processes with Exogenous Dynamics
- Empirical Bernstein Bounds and Sample Variance Penalization
- The Value of Reward Lookahead in Reinforcement Learning
- Algorithms with Predictions
- Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
- Online Conformal Prediction for Non-Exchangeable Panel Data
- Deep Time-Series Forecasting in 10 Years: A Survey