Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

Nadav Merlis

cs.LGJan 15, 2026

Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

Authors: Nadav Merlis

Organizations: The Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology, Israel

Abstract

We study tabular finite-horizon reinforcement learning problems with multiple steps of lookahead information. Before acting, the learner observes $\ell$ 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 $\ell$ , which can usually be considered a small constant.

Figures & tables

Panel of Figure 1 — Figure 1: The diagnostic environments in Claims 2.1 and 2.2 . Both environments have deterministic transitions, start at state $s_{1}$ , and are of horizon $\ell+1$ . Rewards are zero except at the last step (and at the first step in Figure 1(b) as a tie-breaking mechanism). In both cases, observing Bernoulli rewards $\Ber(A^{-\ell})$ from the root of a full tree exponentially augments their value: to collect a unit reward, only one leaf needs to realize $R=1$ , which happens w.p. $\geq 1-1/e$ . Observing rewards later in the tree, or not leveraging this exponential increase, is what makes fixed-batching and MPC fail.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2

$A$	$\ell$	$S$	$B^{\star}$	$V_{\mathrm{FB}}$	$V_{\mathrm{opt}}$	$V_{\mathrm{FB}}/V_{\mathrm{opt}}$
2	2	5	2	$0.4375$	$0.6836$	$0.64$
2	5	33	3	$0.2243$	$0.6379$	$0.3516$
2	10	1,025	6	$0.03078$	$0.6323$	$0.04868$
5	2	8	2	$0.1846$	$0.6396$	$0.2887$
5	5	783	3	$0.03922$	$0.6322$	$0.06203$
5	10	2,441,408	6	$3.199\cdot 10^{-4}$	$0.6321$	$5.062\times 10^{-4}$

Appendix

Table 1: Exact-value illustration of Claim 2.1 .

$A$	$\ell$	$S$	$\widehat{V}_{\mathrm{Tr}}$	$\widehat{V}_{\mathrm{L}}=V_{\mathrm{L}}=V_{\mathrm{MPC}}$	$V_{\mathrm{Tr}}=V_{\mathrm{opt}}$	$V_{\mathrm{MPC}}/V_{\mathrm{opt}}$
2	2	7	$0.25$	$0.5$	$0.6836$	$0.7314$
2	5	38	$0.03125$	$0.1768$	$0.6379$	$0.2771$
2	10	1,035	$9.766\times 10^{-4}$	$0.03125$	$0.6323$	$0.04942$
5	2	10	$0.04$	$0.2$	$0.6396$	$0.3127$
5	5	788	$0.00032$	$0.01789$	$0.6322$	$0.0283$
5	10	2,441,418	$1.024\times 10^{-7}$	$0.00032$	$0.6321$	$5.062\times 10^{-4}$

Appendix

Table 2: Exact-value illustration of Claim I.1 .

Notation	Meaning
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{R},P,H)$	Episodic tabular MDP.
$\mathcal{S},\mathcal{A}$	State space and action space.
$S,A$	Cardinalities of the state and action spaces, respectively.
$\mathcal{R}_{h}$	Reward distribution at step $h$ . The reward distribution of a state-action is $\mathcal{R}_{h}(s,a)$
$P_{h}$	Transition kernel at step $h$ . The probability of moving to state $s^{\prime}$ from $(s,a)$ is $P_{h}(s^{\prime}\|s,a)$ .
$H$	Episode horizon.

Appendix

Table 5

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,742 papers

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Sep 10, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Reinforcement Learning Approximation Algorithms
CREST, ENSAE · Criteo AI Lab FairPlay Joint Team
Reinforcement Learning with Multi-Step Transition Predictions: A Bellman Theory
Oct 23, 2026Chenbei Lu, Zaiwei Chen, Tongxin Li +2Reinforcement Learning Model-Based RL
Duffield College of Engineering, Cornell University · Edwardson School of Industrial Engineering, Purdue University · School of Data Science, The Chinese University of Hong Kong (Shenzhen) +2
On the Hardness of Reinforcement Learning with Transition Look-Ahead
Oct 22, 2025Corentin Pla, Hugo Richard, Marc Abeille +2Reinforcement Learning Model-Based Planning
CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team +1

Sep 10, 2026J/K move · Enter open · S save

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

CREST, ENSAE · Criteo AI Lab FairPlay Joint Team

Reinforcement Learning Approximation Algorithms Model-Based RL

Open paper AskPDF arXiv

We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of actions before deciding its course of action. Although look-ahead can substantially improve achievable performance, [1] showed that optimal planning with multi-step transition look-ahead is NP-hard. However, this hardness was established using a discount factor close to one. It was therefore unknown whether the problem remains hard for every discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed discount factor, exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. Third, we extend our approach to account for unknown transitions. We empirically validate the soundness of our results on the wind-farm storage-control benchmark of [2], showing that our approach, optimally accounting for -step look-ahead information, offers substantially better performance than existing algorithms. [1] Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet : On the Hardness of Reinforcement Learning with Transition Look-Ahead [2] Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman : Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach

Abstract

Reinforcement Learning

Explore similar work

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Reinforcement Learning with Multi-Step Transition Predictions: A Bellman Theory

On the Hardness of Reinforcement Learning with Transition Look-Ahead