Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Updated 4 h ago · first seen 11 Sept 2026
paper_01M294FRGFNJGG0B72ZQ5CK0JQ
- Published
- 11 Sept 2026
- T1 · 4 h ago
- arXiv
- 2609.11807
- T1 · 4 h ago
- Category
- stat.ML
- T1 · 4 h ago
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 $\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 ($\gamma\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.
Authors 4
Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet
Specification
- Official page
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
- Arxiv announce type
- cross
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
- arXiv id
- 2609.11807
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
- Categories
- stat.ML, cs.LG
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
- Primary category
- stat.ML
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
- Published
- 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 4 h agohigh
Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →
Provenance
Attributed facts
9
Source tiers
T19
Freshest observation
4 h ago
Conflicts
None
No models linked to this paper yet.
- Authors
- Corentin Pla, Hugo Richard, Marc Abeille
As of
Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.
Claim history
Official pageofficial_url1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| https://arxiv.org/abs/2609.11807 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Abstractabstract1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 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 ($\gamma\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. | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Arxiv announce typearxiv_announce_type1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| cross | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
arXiv idarxiv_id1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 2609.11807 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Categoriescategories1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| stat.ML, cs.LG | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
PDFpdf_url1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| https://arxiv.org/pdf/2609.11807 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Primary categoryprimary_category1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| stat.ML | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Publishedpublished_at1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 11 Sept 2026 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →
New paper: Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
arxiv
| Source | Document | Type | Tier | Last observed | Snapshots |
|---|---|---|---|---|---|
| arXiv (Atom API + RSS) | rss.arxiv.org/rss/cs.LG | feed | T1· Official | 4 h ago | 1 |
Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.