# Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

arXiv: https://arxiv.org/abs/2601.10418 · HTML: https://mlsanity.com/paper/2601.10418/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 23 of 23)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [The Power of Predictions in Online Control](https://mlsanity.com/paper/2006.07569/) (2020)
- [Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems](https://mlsanity.com/paper/2106.10497/) (2021)
- [On the Regret Analysis of Online LQR Control with Predictions](https://mlsanity.com/paper/2102.01309/) (2021)
- [Learning from the Hindsight Plan -- Episodic MPC Improvement](https://mlsanity.com/paper/1609.09001/) (2016)
- [Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity](https://mlsanity.com/paper/2210.12312/) (2022)
- [Thinker: Learning to Plan and Act](https://mlsanity.com/paper/2307.14993/) (2023)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [Reinforcement Learning with Lookahead Information](https://mlsanity.com/paper/2406.02258/) (2024)
- [The Value of Reward Lookahead in Reinforcement Learning](https://mlsanity.com/paper/2403.11637/) (2024)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)

## 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.