Organizations: Duffield College of Engineering, Cornell University · Edwardson School of Industrial Engineering, Purdue University · School of Data Science, The Chinese University of Hong Kong (Shenzhen) · School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen) · Computing & Mathematical Sciences, Caltech
Multi-step predictions of future transition realizations can improve reinforcement learning, but their value remains difficult to quantify. Directly including these predictions in the state can lead to exponential state-space growth, making direct dynamic programming computationally expensive. We study discounted finite MDPs under a block-feedback protocol: at the start of each K-period block, the decision maker observes K-step probabilistic transition predictions for a subset of actions and adapts decisions to observed states within the block. We show that the optimal value satisfies a Bayesian Bellman equation on the original state space. This representation reveals that predictive information creates value by recursively changing the local order of maximization and expectation in the Bellman expansion. We formalize this effect through a Bellman--Jensen analysis and quantify the effects of prediction horizon, error, action coverage, and within-block feedback. We propose block-feedback Bayesian offline learning with online adaptation (BF--BOLA), a model-based algorithm for learning near-optimal policies, and establish upper and lower sample-complexity bounds that match up to logarithmic factors in the stated regimes. The results show that predictions can reduce transition learning to uncovered rows and that learning a near-optimal policy can require fewer prediction samples than estimating the Bayesian value function.
Figures & tables
Protocol
Information timing
Value representation
Exact computation or storage bottleneck
FH
One prediction per block; open-loop block actions
Block-start value on S
NP-hard in worst case
BF
One prediction per block; state-adaptive block actions
Block-start value on S
O(K∣S∣2∣A∣) within-block DP per realized prediction
RH
Prediction refreshed every period
Augmented value on S×QK
NP-hard for K≥2 ( Pla et al., 2026a )
Table 1: Comparison of prediction protocols. The last column reports the cost of exact planning or tabular value storage.
Target
Environment samples D1
Prediction samples D2
Near-optimal policy
Θ((1−γ)3εpol2∣S∣(∣A∣−∣A−∣))
Θ(1+(1−γ)2(1−γK)εpol2γ2K)
Bayesian value estimation
Θ((1−γ)3εest2∣S∣(∣A∣−∣A−∣))
Θ((1−γ)2(1−γK)εest21)
Table 2: Statistical rates under block feedback, up to logarithmic factors, in the matching regimes of Theorems 5.3 and 5.4 . The D1 rates omit the additive ∣S∣∣A∣ reward observations.
Figure 1: Value of transition predictions in the production MDP. The two noise levels in (a) are 0 and 0.15 . In (b), solid curves have full coverage and dashed curves predict type 0 only. We use K=3 in (a), (c), and (d), and channel noise 0.15 in (b) and (d). Each gain is measured against its baseline in the same MDP. Error bars and bands are 1.96 standard errors across 24 MDP instances.
Figure 2: Two-source learning in the production MDP. The top row varies D2 under full coverage. The bottom row varies D1 under type-0 coverage or no prediction, with the prediction law provided. The budget D1 includes 12 reward observations. Policy success means loss at most 10−3 . Each budget uses 12 training runs on each of 10 MDP instances. Error bars and bands are 1.96 standard errors across instance means.
Figure 3: Optimal control in the data-calibrated wind-storage MDP, with capacity 4, per-period charge/discharge limit 1.5, and γ=0.95 . Panel (a) shows exact expected discounted partial sums under the infinite-horizon optimal policies. Panels (b,c) show paired percentage savings over the no-prediction policy for feedback protocols, including a one-step BF reference. Panels (a,b) use K=3 , except for that reference. Panels (a,c,d) use η=0.15 . Panel (d) times the model-specific Bellman solvers at the same value tolerance. Curves show means across 12 MDPs fitted to day-level bootstrap resamples. Bands and error bars show their 2.5th–97.5th percentiles.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
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
We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions {r1,r2,…,rM}. The goal is to output an ε-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error V0∗,m−V0πm,m where m∈[M] represents the reward function and V0∗,m=Es1∼μ[V1∗,m(s1)]. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of O(ε2SAH3logMpolylog(min{ε,1}δSAHlogM)) episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of polylog(SAHlogM/(min{ε,1}δ)). Our method combines three technical ingredients. First, we adapt MVP to reward-switching learning to construct optimistic value estimates. Second, we use fresh replay samples to conservatively evaluate the candidate policies. Third, gap-based multiplicative weights updates adjust the reward-sampling distribution using the differences between these estimates, converting weighted learning progress into simultaneous guarantees for all rewards.
Zijun Chen, Zihan Zhang
Department of Computer Science and Engineering Hong Kong University of Science and Technology
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying linear Bellman completeness -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with deterministic transitions, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an ε-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and 1/ε.