PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

arXiv:2609.11807v1stat.MLcs.LG

TL;DR

Multi-step transition look-ahead may improve decisions, but exact planning is computationally hard, raising the question of whether efficient approximation and learning remain possible. The paper proves fixed-discount NP-hardness, develops a randomized polynomial-time approximation scheme, and extends it to unknown transitions with regret matching classical tabular discounted reinforcement learning up to logarithmic factors.

  • Problem

    It was unknown whether multi-step transition look-ahead remains NP-hard for fixed discount factors and whether near-optimal planning can be performed efficiently.

  • Method

    The paper samples complete transition tables to build a finite empirical planning problem and extends the approach to unknown transitions and stochastic rewards using optimism.

  • Results

    Exact planning remains NP-hard for every fixed rational γ ∈(0, 1), while fixed-depth near-optimal planning is achievable in randomized polynomial time.

  • Takeaways & Limitations

    Despite exact-planning hardness, efficient near-optimal planning and learning remain possible with transition look-ahead.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies reinforcement learning with multi-step transition look-ahead, where extra predictive information may improve decisions but complicates planning. It proves fixed-discount hardness while developing efficient near-optimal planning and learning methods.

  • Motivation: Transition look-ahead reveals states reachable after action sequences before acting, as in navigation, simulation, and supply-chain applications.
  • Related work: The approximation approach has polynomial dependence on (1 −γ)^−1 for fixed ℓ, unlike sparse sampling’s exponential dependence on the effective horizon.
  • Contributions: For every fixed rational γ ∈(0, 1), exact planning with look-ahead depth ℓ≥2 remains NP-hard.This removes the earlier requirement that the discount factor be arbitrarily close to one.
  • Contributions: For every fixed look-ahead depth, a randomized polynomial-time approximation scheme constructs a uniformly near-optimal policy with high probability.
  • Contributions: The paper extends the planning approach to unknown transitions and stochastic rewards using an optimism-based regret learning algorithm.

2 SETTING AND OBJECTIVES

The paper models transition look-ahead by exposing future transition tables and embedding the resulting information structure into an augmented discounted MDP. Policies therefore act on the current state together with the observed look-ahead window.

  • 2.1 MARKOV DECISION PROCESSES: An MDP consists of finite states, actions, transition probabilities, and rewards, with policies selecting actions based on the current state.
  • 2.2.1 LOOK-AHEAD AND STATE OBSERVABILITY: Transition look-ahead reveals future transition tables before action selection, so every action sequence of length at most ℓ has a determined trajectory.
  • 2.2.1 LOOK-AHEAD AND STATE OBSERVABILITY: After each transition, the oldest table is discarded and an independent fresh table is revealed, preserving a Markov evolution on state-window pairs.
  • 2.2.1 LOOK-AHEAD AND STATE OBSERVABILITY: The look-ahead problem becomes a standard discounted MDP on the augmented space S × Ω^ℓ, with policies mapping state-window pairs to actions.
  • 2.2.1 LOOK-AHEAD AND STATE OBSERVABILITY: Its optimal policy is characterized by a Bellman optimality operator over the current state and the observed transition-table window.

3 HARDNESS OF EXACT PLANNING

Exact planning remains computationally hard even when the discount factor is fixed away from one. The reduction creates a gap between committing to ordinary candidate subsets and waiting for a favorable one to appear.

  • 3 HARDNESS OF EXACT PLANNING: For every fixed ℓ≥2 and rational γ ∈(0, 1), deciding whether a policy reaches a threshold under perfect look-ahead is NP-hard.
  • 3 HARDNESS OF EXACT PLANNING: The reduction exposes random candidate subsets at the root, letting the agent either commit immediately or wait for a fresh candidate.
  • 3 HARDNESS OF EXACT PLANNING: If every candidate subset has expected maximum at most U, commitment yields value at most T := γ^(ℓ+1)U.
  • 3 HARDNESS OF EXACT PLANNING: If a favorable subset has expected maximum at least U + ∆, repeated waiting preserves a strictly positive surplus above T for every fixed γ ∈(0, 1).

4 NEAR OPTIMAL PLANNING

The paper makes near-optimal planning tractable by sampling complete transition tables, solving a finite empirical MDP, and recursively incorporating the actual look-ahead window online. For fixed depth, the resulting policy and representation have polynomial computational and memory requirements.

  • 4 NEAR OPTIMAL PLANNING: Offline, the method samples a dictionary of transition tables, builds C_N := S × [N]^ℓ, and runs value iteration once on this finite state space.
  • 4 NEAR OPTIMAL PLANNING: Online, backward recursion processes the observed tables exactly while averaging only over the next unseen table from the offline dictionary.
  • 4 NEAR OPTIMAL PLANNING: For every fixed look-ahead depth, a randomized polynomial-time approximation scheme constructs a uniformly near-optimal policy with high probability.
  • 4.2 THEORETICAL GUARANTEES: For fixed ℓ, computing and storing the policy and selecting each action require time and memory polynomial in n, m, ε^−1, log(1/δ), and (1 −γ)^−1.
  • 4.2 THEORETICAL GUARANTEES: Sampling complete transition tables yields a uniform approximation bound simultaneously over every possible look-ahead window.

5 REGRET MINIMIZATION

DLA-UCB learns with unknown transitions and stochastic rewards by combining optimistic confidence bounds with dictionary-based approximate planning. Its leading regret dependence matches classical tabular discounted RL up to logarithmic factors, despite the exponentially large augmented state space.

  • Algorithm: DLA-UCB estimates the transition law, constructs optimistic reward estimates, samples a fresh dictionary, and solves a finite MDP with optimistic Bellman backups.At decision time, it uses the observed look-ahead window in the same backward recursion.
  • Approximation strategy: The finite planning problem runs optimistic value iteration on S × [M_N]^ℓ, replacing empirical successor averages with variance-adaptive optimistic estimates.The bonus combines a Bernstein-type variance term, continuation-value control, and a quadratic term preserving monotonicity.
  • Online implementation: The online algorithm updates its planner on doubling schedules for transition samples and reward counts, while reusing the fixed dictionary and value array between updates.There are at most O(nm log T) recomputations, and for fixed ℓ the costs are polynomial in n, m, T, and (1 −γ)^−1.
  • Regret guarantee: The leading regret term matches classical tabular discounted MDPs up to logarithmic factors in n, m, T, and (1 −γ)^−1.The remaining lower-order term comes from the uniform transition confidence bound needed for data-dependent optimistic value functions.
  • Approximation strategy: The planner approximates the transition law in two stages: marginal estimation produces bQ_N, then Monte Carlo sampling produces a finite dictionary of complete transition tables.The first stage is statistical estimation error; the second is computational sampling error.

6 CONCLUSION

The paper establishes both hardness and tractability boundaries for discounted planning with multi-step transition look-ahead. Exact planning remains hard, but finite-dictionary approximation yields efficient near-optimal control, while broader look-ahead settings remain open.

  • 6 CONCLUSION: Exact planning is NP-hard for every fixed rational discount factor and every fixed look-ahead horizon ℓ≥2.The result shows that the hardness persists without requiring discount factors arbitrarily close to one.
  • 6 CONCLUSION: For every fixed ℓ, a randomized approximation scheme constructs a uniformly near-optimal policy in polynomial time and memory with high probability.The method replaces transition realizations with a finite dictionary, solves an empirical Bellman problem, and extends the value function to observed look-ahead windows.
  • 6 CONCLUSION: The exponentially large augmented state space does not by itself preclude efficient approximate control under transition look-ahead.
  • 6 CONCLUSION: Whether similar guarantees hold when look-ahead depth is part of the input or predictions are imperfect, dependent, or partially observed remains open.

A.1 PROOF OF THEOREM 1

For every fixed rational γ∈(0,1) and ℓ≥2, the reduction establishes NP-hardness of exact planning with ℓ-step transition look-ahead. It converts an expected-maximum gap into an MDP where look-ahead reveals candidate subsets, while discounting is controlled through waiting and reward shifts.

  • Hardness reduction: For every fixed rational γ∈(0,1) and ℓ≥2, a polynomial-time reduction from INDEPENDENT SET proves exact ℓ-step look-ahead planning is NP-hard.The reduction maps graph instances to ℓ-DVDP instances.
  • Hardness reduction: The reduction starts from independent nonnegative random variables whose expected maximum separates graph instances with and without an independent set of size k.All variables have equal expectation, polynomial encoding length, and a gap between the two cases.
  • MDP construction: Reward shifting ensures the constructed rewards are nonnegative without changing the reduction’s essential gap.The shifted variables are used to define finite-support payoff states and bounded nonnegative rewards.
  • MDP construction: At the root, look-ahead reveals a candidate tuple of vertices; committing yields a discounted expected maximum, while waiting produces a fresh candidate tuple.The construction uses the distinction between commitment and repeated waiting to encode the gap problem.
  • MDP construction: After the deterministic delay chain, the selector state exposes each candidate’s payoff before the agent chooses, so the agent can select the largest revealed payoff.The payoff realization remains outside the root look-ahead window and is sampled independently conditional on the candidate tuple.

A.2 PROOF OF THEOREM 2

The planning algorithm approximates the augmented MDP by sampling a finite dictionary of transition tables and solving the resulting finite state space. Exact restriction and extension identities show that observed arbitrary look-ahead windows can be incorporated without additional approximation, yielding polynomial complexity for fixed ℓ.

  • Dictionary planner: Sampling N transition tables creates the finite state space C_N=S×[N]^ℓ, on which value iteration computes an approximate empirical fixed point.The dictionary avoids enumerating the full transition-table space.
  • Approximation analysis: Uniform concentration controls the empirical-versus-true Bellman discrepancy because, for fixed ℓ, the relevant function class has logarithmic size polynomial in n and m.The resulting value error is amplified by the discounted contraction factor rather than by enumerating all look-ahead suffixes.
  • Dictionary planner: The empirical augmented MDP and the finite dictionary MDP have identical Bellman dynamics because the next dictionary table is sampled uniformly.This identifies the finite MDP’s fixed point with the empirical model’s value function on dictionary windows.
  • Backward extension: The exact extension identity reintroduces the observed tables backward from the dictionary fixed point and recovers empirical action scores on arbitrary look-ahead windows.The stability bound shows the extension contracts errors by γ^ℓ.
  • Computational guarantee: For fixed ℓ, the dictionary planner has preprocessing time, representation size, and per-decision computation polynomial in n, m, ε^-1, log(1/δ), and (1−γ)^-1.The guarantee follows after finite value iteration and backward extension from dictionary windows.

A.3 PROOF OF THEOREM 3

The unknown-transition extension combines empirical transition estimates, optimistic rewards, and variance-adaptive confidence bounds in an optimistic Bellman planner. Product-estimator concentration and dictionary sampling transfer the resulting guarantees to efficient online planning.

  • Dictionary sampling: A fresh dictionary sampled by independent coordinate permutations supplies i.i.d. transition tables conditional on past observations.This makes concentration applicable to the dictionary-dependent planner through the ideal fixed point.
  • Confidence bounds: Although the look-ahead suffix space is exponential, its contribution to the confidence radius is only logarithmic.The bound exploits uniform control over the relevant continuation-value functions for fixed ℓ.
  • Confidence bounds: The planner’s optimistic expectation combines a Bernstein variance bonus with a Hellinger-based uniform correction for data-dependent continuation values.The construction also clips estimates and adds a term preserving monotonicity.
  • Optimistic planning: The optimistic Bellman operator is a monotone γ-contraction and dominates the true Bellman operator when reward estimates are optimistic.Contraction gives a unique optimistic fixed point and supports the planner’s analysis.
  • Planner accuracy: The dictionary planner’s approximation error combines finite value-iteration error with sampling error, while restriction and backward extension add no further approximation.The stated sampling condition controls the dictionary approximation during planner updates.

B EXPERIMENTS

The paper extends DLA-UCB to locally corrupted transition look-ahead by modeling noisy tables and comparing the learner with an oracle that observes the same noisy windows. Bayesian posterior averaging replaces deterministic successor transitions in the planner.

  • Extension: The noisy-look-ahead extension changes the observation model while keeping the reward-confidence construction unchanged.The section specifies a noisy-table comparator, algorithm, and regret analysis.
  • Posterior model: Conditioning on a noisy transition entry replaces the true successor law with a Bayes posterior over latent successors.The posterior combines the original transition probability with the corruption distribution.
  • Posterior model: The noisy augmented Bellman operator remains a monotone γ-contraction with a well-defined fixed point and action scores.Posterior averaging is incorporated directly into the Bellman updates.
  • Observation model: The oracle observes the same noisy windows as the learner rather than the latent transition tables.Regret is therefore measured against a comparator with the same corrupted information.

C.2 NEAR-OPTIMAL PLANNING

The near-optimal planner samples transition tables to construct a finite empirical MDP, then applies value iteration and backward extension to obtain approximately greedy actions. For fixed look-ahead depth, its policy computation and action selection are polynomial in the problem parameters.

  • C.2 NEAR-OPTIMAL PLANNING: Value iteration applies the empirical Bellman update on dictionary states, while backward extension transfers the resulting scores to arbitrary observed look-ahead windows.The returned policy is greedy with respect to the approximate action scores.
  • C.2 NEAR-OPTIMAL PLANNING: For fixed ℓ, computing, storing, and deploying the policy require time and memory polynomial in n, m, ε^-1, log(1/δ), and (1 −γ)^−1.The approximation scheme therefore avoids the exact planner’s computational barrier at fixed look-ahead depth.
  • C.2 NEAR-OPTIMAL PLANNING: The empirical planner’s one-sweep cost is O(n(nm + 1)N^ℓ), and backward extension costs O(ℓn(nm + 1)N^ℓ).Posterior averaging adds only one factor n relative to the perfect-look-ahead planner.

C.3 THE NOISY VERSION OF DLA-UCB

The noisy-look-ahead algorithm models each synthetic dictionary element with both a noisy transition table and sampled physical successors. It combines these objects with optimistic Bellman backups and maintains polynomial update, representation, and per-decision costs for fixed look-ahead depth.

  • C.3 THE NOISY VERSION OF DLA-UCB: Theorem 5 gives NOISY-DLA-UCB a high-probability regret guarantee under noisy transition look-ahead and stochastic rewards.The algorithm uses optimism and confidence estimates for the noisy setting.
  • C.3 THE NOISY VERSION OF DLA-UCB: For fixed ℓ, the noisy algorithm has polynomial update time, representation size, and per-decision computation.The number of planner updates is O(n^2m log T), and each update uses a dictionary built from the expired tables.
  • C.3 THE NOISY VERSION OF DLA-UCB: Each synthetic dictionary element contains a noisy table and a physical successor sampled from the estimated conditional law given the local state, action, and noisy entry.This replaces the deterministic successor used by the perfect-look-ahead algorithm.
  • C.3 THE NOISY VERSION OF DLA-UCB: NOISY-DLA-UCB estimates the noisy-table distribution from expired tables and uses a uniform successor law when a local context has no observations.The unvisited-context choice is immaterial because the continuation estimate is clipped at Vmax.
  • C.3 THE NOISY VERSION OF DLA-UCB: At decision time, the algorithm performs optimistic dictionary value iteration followed by backward extension to the observed noisy window, without an additional online exploration step.The update is triggered initially, at powers of two, or when reward or local-transition counts double.

C.3.1 PROOF OF THEOREM 5

The proof controls noisy planning on a finite computation graph rather than uniformly over all possible noisy suffixes. It combines concentration for posterior successors and noisy-table laws with contraction and stability arguments to extend optimism to deployed decisions.

  • C.3.1 PROOF OF THEOREM 5: The proof avoids a uniform bound over all noisy suffixes by restricting concentration to a finite graph containing observed, dictionary, and hybrid windows.This preserves the intended dimension dependence while covering every window used by backward extension.
  • C.3.1 PROOF OF THEOREM 5: Conditioned on the noisy-table sequence, successors observed on repeated visits to a fixed local context are independent with a common conditional law.Optional skipping preserves this i.i.d. posterior-sample stream, including after independent synthetic noisy tables are introduced.
  • C.3.1 PROOF OF THEOREM 5: The analysis separately controls estimation of physical-successor laws and noisy-table laws, then combines their errors through product-law comparisons and concentration inequalities.The proof uses scalar Bernstein bounds, Hellinger control, and union bounds over contexts, sample counts, and graph continuations.
  • C.3.1 PROOF OF THEOREM 5: The compound-dictionary operator is monotone and a γ-contraction, so its fixed point is stable and finite value iteration yields approximately greedy deployed actions.After K_N iterations, the action selected is 2γ^K_N Vmax-greedy for the exact dictionary scores.
Loading 2609.11807v1…