Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Theorists prove multi-step lookahead RL planning is NP-hard for every fixed rational discount factor yet give a randomized polynomial-time approximation scheme.
The paper resolves open questions about reinforcement learning with multi-step transition lookahead. It shows exact planning remains NP-hard for every fixed rational discount factor in (0,1), not just discounts arbitrarily close to one, and introduces a randomized polynomial-time approximation scheme for every fixed lookahead depth. Extending to unknown transitions and stochastic rewards via optimism and variance-adaptive confidence bounds, the algorithm achieves cumulative regret matching classical tabular discounted RL up to logarithmic factors.
- NP-hardness of exact lookahead planning now holds for every fixed rational discount factor.
- Randomized PTAS achieves near-optimal planning for any fixed lookahead depth.
- Optimism and variance-adaptive bounds extend results to unknown transitions and stochastic rewards.
- Regret matches classical tabular discounted RL up to logarithmic factors.
Full article167 words · extracted from arxiv.org · click to collapse
We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of $\ell$ 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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.11807