mlsanityData to 14 Oct 2026

Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

arXiv 2601.10418 ↗First posted 15 Jan 2026cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study tabular reinforcement learning problems with multiple steps of lookahead information. Before acting, the learner observes ℓ steps of future transition and reward realizations: the exact state the agent would reach and the rewards it would collect under any possible course of action. While it has been shown that such information can drastically boost the value, finding the optimal policy is NP-hard, and it is common to apply one of two tractable heuristics: processing the lookahead in chunks of predefined sizes ('fixed batching policies'), and model predictive control. We first illustrate the problems with these two approaches and propose utilizing the lookahead in adaptive (state-dependent) batches; we refer to such policies as adaptive batching policies (ABPs). We derive the optimal Bellman equations for these strategies and design an optimistic regret-minimizing algorithm that enables learning the optimal ABP when interacting with unknown environments. Our regret bounds are order-optimal up to a potential factor of the lookahead horizon ℓ, which can usually be considered a small constant.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 23 of its 30 references that are in the map. First posted on arXiv 15 Jan 2026.

Builds on

23 of 30 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025On the Hardness of Reinforcement Learning with Transition Look-Ahead22 Oct
  2. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach21 Oct

Other references · 21

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  8. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  9. 2019Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysiscited by 40
  10. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  11. 2020The Power of Predictions in Online Controlcited by 31
  12. 2021Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systemscited by 25
9 more
  1. 2021On the Regret Analysis of Online LQR Control with Predictionscited by 22
  2. 2016Learning from the Hindsight Plan -- Episodic MPC Improvementcited by 16
  3. 2022Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearitycited by 16
  4. 2023Thinker: Learning to Plan and Actcited by 13
  5. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 12
  6. 2022Planning and Learning with Adaptive Lookaheadcited by 8
  7. 2024Reinforcement Learning with Lookahead Informationcited by 8
  8. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  9. 2024Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Informationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
  2. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
  3. 2026A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
  4. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  5. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
  6. 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
  7. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
  8. 2021Continuous Doubly Constrained Batch Reinforcement Learning