Research map / Bandits and online learning / RL theory and MDPs

Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

NeurIPS 2026 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes adaptive batching policies (ABPs) for tabular episodic RL with multi-step lookahead, derives optimal Bellman equations, and an optimistic algorithm AL-UCB with near-optimal regret bounds.

Problem

Reinforcement learning in tabular MDPs where the agent observes multi-step lookahead information (future transitions and rewards) before acting; optimal lookahead planning is NP-hard and common heuristics (fixed batching, MPC) can fail badly.

Approach

Let the agent choose a state-dependent lookahead batch length, observe lookahead only at batch starts, and play greedily within the batch; derive Bellman equations for this class and an optimistic variance-based UCB algorithm whose regret is order-optimal up to a factor of the lookahead horizon.

Key results

• AL-UCB achieves regret O(sqrt(H^3 S K ell ln(SHellK/delta)) + H^3 S^2 ell ln^2(...)) w.p. 1-delta, order-optimal up to a factor of the lookahead horizon ell.
• Fixed batching policies can collect value at most A^{-ell/2+1} in a simple environment where the optimal ell-step lookahead value exceeds 1/2.
• For ell=1, the regret rate sqrt(H^3 S K) removes dependence on action-space size, matching a lower bound of Omega(sqrt(H^3 S K)).

Surprising findings

• Fixed batching policies can be exponentially suboptimal relative to optimal lookahead policies even in very simple environments.
• Backward-induction MPC value calculations can be exponentially suboptimal in some environments.

Limitations

• Regret bounds are not tight in the lookahead horizon ell; gap of factor ell from the lower bound candidate.
• Assumes perfect, noise-free lookahead information and tabular finite state spaces.
• Planning exact optimal lookahead policy is NP-hard, so the approach is limited to ABPs and computing the optimal lookahead values is conjectured hard.

Experimental setup

Metrics: regret

Baselines: fixed batching policies model predictive control

Builds on: UCBVI fixed batching policies model predictive control one-step lookahead RL algorithms

Closest papers by meaning

• Reinforcement Learning with Lookahead Information (NeurIPS 2024 · similarity 0.92)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning (NeurIPS 2022 · similarity 0.89)
• A General Framework for Sequential Decision-Making under Adaptivity Constraints (ICML 2024 · similarity 0.88)
• Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.88)
• Switching the Loss Reduces the Cost in Batch Reinforcement Learning (ICML 2024 · similarity 0.87)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.87)