Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
Authors: Chenbei Lu
Zaiwei Chen
Tongxin Li
Chenye Wu
Adam Wierman
Venue: NeurIPS 2025 spotlight ()
Keywords: Reinforcement Learning
Markov Decision Processes
Transition Prediction
Bellman-Jensen Gap
Sample Complexity
Primary area: theory
TL;DR: We introduce a Bayesian value framework and a Bellman–Jensen Gap analysis to rigorously quantify and exploit imperfect multi‐step transition predictions, and present BOLA, the first provable sample‐efficient algorithm for RL with predictions.

Abstract: Traditional reinforcement learning (RL) assumes the agents make decisions based on Markov decision processes (MDPs) with one-step transition models. In many real-world applications, such as energy management and stock investment, agents can access multi-step predictions of future states, which provide additional advantages for decision making. However, multi-step predictions are inherently high-dimensional: naively embedding these predictions into an MDP leads to an exponential blow-up in state space and the curse of dimensionality. Moreover, existing RL theory provides few tools to analyze prediction-augmented MDPs, as it typically works on one-step transition kernels and cannot accommodate multi-step predictions with errors or partial action-coverage. We address these challenges with three key innovations: First, we propose the \emph{Bayesian value function} to characterize the optimal prediction-aware policy tractably. Second, we develop a novel \emph{Bellman–Jensen Gap} analysis on the Bayesian value function, which enables characterizing the value of imperfect predictions. Third, we introduce BOLA (Bayesian Offline Learning with Online Adaptation), a two-stage model-based RL algorithm that separates offline Bayesian value learning from lightweight online adaptation to real-time predictions. We prove that BOLA remains sample-efficient even under imperfect predictions. We validate our theory and algorithm on synthetic MDPs and a real-world wind energy storage control problem.

Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
Chenbei Lu
Institute for Interdisciplinary Information Sciences Tsinghua University
Zaiwei Chen
Edwardson School of Industrial Engineering Purdue University
Tongxin Li
School of Data Science
The Chinese University of Hong Kong (Shenzhen)
Chenye Wu
Adam Wierman
School of Science and Engineering
Computing Mathematical Sciences Caltech
The Chinese University of Hong Kong (Shenzhen)
Abstract
Traditional reinforcement learning (RL) assumes the agents make decisions based on Markov decision processes (MDPs) with one-step transition models. many real-world applications, such energy management and stock investment, agents can access multi-step predictions future states, which provide additional ad- vantages for decision making. However, multi-step predictions high-dimg high-dimensional: naively embedding these predictions into an MDP leads to an exponential blow-up in state space and the curse of dimensionality. Morcover, existing RL theory provides few tools to analyze prediction -aatriionn-mmmneeeddd MDPs, as it typically works one-step transition kernels and cannot accommodate multi-step predictions with errors or partial action-coverage. We address these challenges with three key innovations: First, propose the Bayesian value function to char- acterize the optimal prediction-awarc policy tractably. Second, we develop novel BellmanJensen Gap analysis the Bayesian value function, which enables charac- terizing the value of imperfect predictions. Third, we introduce BOLA (Bayesian Offline Learning with Online Adaptation), two-stage model-basee based RL algorithm that separates offline Bayesian value learning from lightweight online adaptation to real-time predictions. We prove that BOLA remains sample-efficient even under imperfect predictions. We validate our theory and algorithm on synthetic MDPs and real-world wind energy storage control problem.
inherently
1 Introduction
Reinforcement Learning (RL) 1 has emerged powerful framework for sequential decision- making, achieving remarkable success across diverse domains [2H5]. Classical RL formulates
"Corresponding author, chenyewu@yeah.ne net
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

socision-making as a Markov Decision Process (MDP), where an agent seeks to maximize expected cumulative rewards in a stochastic environment. A central premise of this framework that once the agent has accurately captured the environment model (e.g., the transition dynamics), it can, in principle, compute an optimal policy. In model-based RI., this involves explicitly learning the transition kernel and reward function to solve the optimal policy [6]. Even in model-free RI., agents implicitly learn the environment through value function or policy learning 77.
However, in many real-world applications, agents can access even richer information: the prediction of future transition realizations. Rather than relying solely on expected transition dynamics, these realization-lewe predictions specify exact future states, which can reduce or even eliminate the environments inherent stochasticity and enable more effective recision-makinng For example, in financial markets, accurate multi-step price forecasts can substantially improve trading strategies 8 while in energy systems, reliable predictions of renewable energy generation allow the system operators to schedule the power generation sources more efficiently [9]
Despite their potential, incorporating multi-step transition predictions into MDPs faces three key challenges. First, the predictions over a multi-step horizon are inherently high-dimensional: augment- ing the state with these predictions expands the state space exponentially, making standard solutions computationally intractable (see Section 3 for more details). Second, even if the augmented MDP can be solved, existing theory lacks formal tools to quantify the benefits of multi-step transition predictions, particularly when they are inaccurate or only cover a subset of actions. Third, in the absence of strong assumptions on function approximation [T [3 RL's sample complexity scales at least linearly with the size of the stateaction space [14] 15 and the exponential state expansion also induces an exponential blow-up the required samples [6] Addressing these challenges is
essential for the rigorous integration of transition predictions into RL. See Appendix A a detailed
literature review.
To overcome these challenges, our contributions can be summarized as follows:
Tractable Optimal Policy for MDPs with Transition Predictions. We introduce low- wiw-dimensional Bayesian value function that integrates multi-step transition predictions into the value evaluation, which enables a tractable characterization of the optimal prediction aware policy.
Characterization of the Value of Imperfect Predictions using Bellman-Jensen Gap. We introduce the Bellman-Jensen Gap framework, a novel analytical tool that decomposes the advantage of multi- step predictions into recursive sum of local Jensen gaps in the Bayesian value function. Building on this framework, we characterize the value of imperfect predictions and show how it can close the performance gap to the offline optimal policy in Theorem 4.1
Prediction-Aware Algorithm with Improved Sample Complexity. We propose BOLA, a two-stage masel-based RL algorithm that combines offline Bayesian value estimation with online integration of real-time predictions. We prove that BOLA avoids the exponential sample complexity and, given high-quality predictions, is more sample efficient than classical model-based RL [4 [5] Our analysis relies on tailored decopposioon and telescoping bounds to control multi-step transition errors.
The remainder of this paper proceeds as follows. Section 2 formalizes the regiittion-aummente MDP framework. Based on this formulation, Section 3 introduces a tractable Bayesian value function to characterize the optimal policy, circumventing the curse of dimensionality. Subsequently, Section 4 establishes the Bellman-Jensen Gap theoretically quantify the value of imperfect predictions. This analysis directly motivates Section 5, where we present the BOLA algorithm with provable sample efficiency guarantees. Section 6 then provides empirical validation on a wind energy storage problem. Finally, Section 7 concludes with discussion of limitations and future work. Complete proofs and additional details are included in the appendices.
2 Markov Decision Processes with Transition Predictions
In this section, we formally introduce the framework for MDPs augmented with transition predictions.
We begin by introducing the definition of discounted infinite-horizon MDP, which is specified by the tuple A AS P. rr,7), 7). Here, S and are the finite state and action spaces, respectively; P is the transition kernel, i.c., P(: s, a) denotes the distribution of the next state given that action

---

is taken at state s; r. S x A - [0, 1..1]a is the reward function; and E (0, 1) is the discount factor. Since we focus on finite MDPs, assuming bounded rewards without loss of generality. The model parameters of the MDP (i.e., the transition kernel P and the reward function r)) are unknown to the agent, but the agent can interact with the environment by observing the current state, selecting actions, and receiving the resulting next state and reward.
2.1 MDPs with Transition Predictions
We extend the classical MDP framework by incorporating imperfect predictions of future transition dynamics. Formally, consider an MDP with transition predictions characterized by the tuple Md = A, P, A,,,,,,,, where (K, AK,A),e) ,)) capture the prediction structure. Specifically, K denotes the finite prediction horizon; A S A specifies the subset actions for which transition outcomes can be predicted; and quantifies the associated prediction errors.
We first consider an ideal case that the prediction is accurate. At discrete time steps t 0, K, SK,2K,... the agent receives batch of predicted transitions for the next K steps, denoted as a² (oi, .2....... ok), and each of a binary matrix of size (S||A_| x |S], where each row corresponds to a (s, a) pair with E A and is a one-hot vector indicating the predicted next state.
Given an accurate one-step transition prediction og the conditional transition probabilities depend on whether the action taken falls within the predictable action subset A This subset captures actions for which reliable prediction models are available, allowing the agent exploit future information. In contrast, actions outside A must rely solely on the underlying transition dynamics P(s||s, a) of the environment. Accordingly, the conditional transition model with predictions
[oi((s,a), P(s' s,a);
Va E ,8, E ES,
P(s (k),
(I)
Va A 8,8' E.
To preserve the Markov property of the underlying MDP, we impose two natural conditions on each onestep prediction matrix of within the K K-step forecast:
Independence and stationarity. Each of is drawn i.i.d. from a fixed distribution. This ensures that every predicted transition remains stationary with respect the transition kernel. Also, the prediction depends only on the current stateaction pair and not on any prior history.
Consistency, In expectation, the accurate prediction exactly recovers the true transition kernel:
Bog-P, [ot((s, s')] P(s' s,a),
4 K, AT 88 E.
However, exact prediction is not always attainable in practice. Thus, we assume the agent only receives inaccurate predictions denoted as o (0), 02. ..,,, oK) E QK. where QK denotes the space of inaccurate prediction σr, and each o E [0, 1 |S|AA |x|S| predicted transition probabilities for the state-action pairs at step i: in the future. Each prediction may differ from the true future transition of due prediction error. We model this discrepancy as 0% = og + k- = 1,..., K, where E is a random eтror matrix drawn from a distribution fra int
stochastic matrix indicating
This formulation captures a broad class of imperfect predictions, allowing us to study how finite- horizon, partial, and inaccurate forecasts can be leveraged for improved decision-making in MDPs.
which treats predictions as noisy estimates of the transition kernel and aims only to match standard MDP performance. In contrast, we model ideal predictions as concrete, one-hot realizations with certain consistency property in Eq. (2). enabling us to leverage realization-leww information to surpass classic MDP performance, Furthermore, unlike these methods, we explicitly address partial action predictability, an open challenge identified in [7
Remark:
Our model differs fundamentally from prior work such 17 18
2.2 Decision-Making and Optimization Objectives
We adopt fixed-horizon planning protocol 19 where the agent makes decisions at discrete time points 0, K, T,2KK.... At each decision point, after observing the current state 8, and receiving the prediction batch σr, the agent selects action sequence Boo....,ak-. E AK according to
3

---

policy т S QK - A(A"), where Qx denotes the prediction space and ((A*) denotes the prob- ability simplex over K -ttpp action sequences. This setting models how agents dynamically plan deci- sions over a finite prediction horizon. The agent seeks to maximize the expected cumulative reward by selecting an optimal policy, defined as π = arg max R o 7 ( 8t, a+) 80 = 8, 0o = a) for all 8 S. a QK-
3 Bayesian Value Function and Prediction-Aware Optimal Policy
In this section, we develop a tractable formulation for Eecision-mmainn with multi-step imperfect transition predictions.
Motivation: A straightforward strategy for using predictions is to treat (s, or) as the new state and solve a standard MDP over this extended state space. However, this approach quickly becomes intractable. K Ktstep prediction (0I..... ok) consists of K transition matrices, each of size [S|||] x [S], resulting an exponentially large state space size of at least |S| (S]K]S]IAA, Moreover, since a is typically noisy and continuous, its support can be uncountably infinite. As result, the augmented value function must satisfy an infiniteddimensional Bellman equation, making classical solutions impractical even for K =
In summary, while predictions have the potential to improve performance, naively augmenting the state space with raw prediction vectors leads to intractable computation. To address this issue, we next introduce Bayesian value function that enables tractable, prediction-aware characterization of the optimal policy.
3.1 Bayesian Value Function and Optimal Policy Structure
To avoid explicit state augmentation,
instead formulate Bayesian value function defined over the original state space. The key idea is to take an expectation over the prediction distribution, thereby shifting the complexity into outer integral while preserving tractable structure. Formally, define the Bayesian value function as:
Bayess K.A (s) = E. Er 2'm so ooo=
This Bayesian value function represents the expected cumulative reward when each decision is made after drawing K -sstep prediction a.. We call Bayesian because we marginalize over the distribution of a, thereby accounting for forecast uncertainty in the value estimate. Importantly, the policy can condition the realized or, yet the value function itself remains defined solely over the original state space. This preserves tractability by avoiding an explicit statespace augmentation. The optimal Bayesian value is then:
K.A
Bayes.* (s)
max 37
V- K.A
Bayes.
(s):
E S.
By constructing an auxiliary MDP that incorporates the predictions and linking it with the optimal Bayesian value function, we derive the corresponding Bellman optimality equation (see Appendix for the proof).
Theorem 3.1 (Bellman Optimality Equation for Bayesian Value Function). The optimal Bayesian value function v Bayes,, is the unique solution to the following fixed-point equation: K,A-
V Bayes, K.A 1 (s)
Eg max EEe
K-1 7dt (E,, P(sels, 00--1, 10
Bayes, (<k))(())))))))))))))))) VSES. +7 K Σ P(sk|s, a, σ) V
(5)
Here in Eq. 5. aoit1 (ao.... (ao..... 11-1) and o (0), (01,..., .,) denote the sequences of actions and predictions, respectively, and P(st|so, 00 is the multi-step transition probability from initial state so state st after i steps under the sequences of actions and predictions ao.t-1 and iit which satisfies the following recursive relation:
P(selSu, 00:--1, = =E
a1-1, 01) 0 201-2-014-1) (6)

---

The recursive form in Eq. ( captures how predictions guide near-term planning over horizon K, with long-term value rolled into Vi (sx) Importantly, the corresponding Bellman operator is contraction mapping with parameter y under the infinity norm, which guarantees the existence and uniqueness of the solution and enables efficcint fixed-point computation.
The optimal Bayesian value function directly yields the optimal policy, as characterized below. The proof is provided in Appendix [
Corollary 3.1 (Optimal Policy with Bayesian Value Function and Transition Predictions). The optimal policy x:(: (: a) with K-step transition predictions satisfies:
{a E A ( (a s, >0}
K-1
S arg max aEAs
Σ r Σ
P(sels, ao--11 a..-1. n
Bayes, P(s K.A (s
aK
V Qk.
This result shows that the optimal prediction-aware policy can be computed via a finite-horizon planning over followed by terminal reward using the Bayesian value function V-Bayes, K In effect,
we have reduced the original infinite-horizon problem with high-dimensional predictions to a special form of fixedhorizon planning [9], which tractable without explicitly augmenting the state space.
4 Analyzing the Value of Predictions
In this section, we examine how access to transition predictions improves decision-making in MDPs. Classical MDPs face structural limitation: their value functions involve deeply nested max-over-Rt operations, which force agents to commit to fixed policies based expected dynamics. We show that transition predictions alleviate this limitation by enabling a localized reordering of the max and E operators, allowing actions to adapt to realized transitions. We use Bellman-Jensen Gap analysis on the Bayesian value function to characterize the value predictions.
4.1 Bellman-Jensen Gap
We introduce the Bellman-Jensen Gap by comparing the following value functions.
Bellman Expansion of Optimal Value Function. By recursively applying the Bellman optimality equation for classical discounted MDPs, the value function can be expressed in the following nested form 20
I]]] (8)
VMDP (sp) = max r(so; ao) + 7Bo max r(s1, a1) + ylang max[r( a2) +
where of denotes the transition realization of s; at time f. Each expectation EE;; is equivalent to taking the expectation over the next state 8, P( 8t-1, 0t-1; corresponding to the transition dynamics governed by of- This formulation results in a deeply nested max-over-E structure, where the agent must choose action that optimal in expectation, without the ability to anticipate and adapt to future information.
In contrast, if the agent had access perfect predictions of future transitions, it could defer action selection until those transitions are known, which allows a localized reordering of the max and operators. We one-step prediction case to illustrate it:
Operator Reordering with One-Step Prediction. Recall the Bayesian value function with which can be expanded into the following recursive form:
.11
Bayes, K=1,A.0 (36) Eg; max r(sp, an) +7 max(r(s1,
Observe that, with one-step prediction, each E,, operator is moved to the outer side of the neigh- borhood max operator. Intuitively, it provides the agent the ability to make decisions according to the transition prediction of at time t. Mathematically, this localized reordering creates local
5

---

Jensen gap by exploiting Jensen's ' inequality due to E, [max, f(s, a)) 2 max, Eo a: g),, where discrete maximization a convex function, and f(s, a; a; o) denotes the expected return under state 8 with action a and prediction a. Since the Bayesian value function contains infinitely many such operator reordering in a recursive manner, we term it as the Bellman-Jensen Gap.
Maximal Bellman-Jensen Gap with Infinite-Step Prediction. Such Bellman-Jenser Gaps reach the maximum when the prediction horizon is infinite. Formally, let offf V-Bayes, E. |R| denote the offline optimal Bayesian value function, where the agent has exact knowledge of all future transitions:
+ =Il
Bayes, (su) =Eo; off
max ag
r(su, ao) +y max 61
r(s1, +7 max [r(s2, + 02
Σ 7(((1), an) 00:k-1
lim 100
Eoi
max
(10)
where iis is the sequence of realized transition kernels and do-k-1 the action sequence over horizon k. The existence of the limit is shown in Appendix D
Observe that, with infinitely long accurate prediction, all E. operators appear outside of any maN. operator, which indicates that the agent can make the decision with full information of all future information, yielding the maximal Belsman-Jensen Gap defined follows:
Definition 4.1 (Maximal Bellman-Jensen Gap). For any state E S, we define the Maximal Bellman- Jensen Gap as (ss) VB (s), which quantifies the greatest possible performance gromfrom knowing exact future transitions.
The maximal Gellman-Jensen Gap characterizes the fundamental benefit that predictive information can offer in MDPs. It upper-bounds the value of any prediction by capturing the intrinsic benefits of operator reordering in the value function. Note that, this analytical framework naturally extends to other types of predictions. For example, by redefining a to represent the prediction on reward realizations, the same Bellman-Jensen Gap analysis applies.
4.2 Closing the Bellman.Jensen Gap with Imperfect Predictions
We now leverage the BellmanJensen gap framework to analyze how imperfect predictions narrow the performance gap to the offline oracle. In particular, derive explicit bounds the suboptimality of a policy that uses finite-houe horizon,, inaccurate, and partial action-coverage predictions.
The following theorem provides finite-horizon performance bound that decomposes the suboptimal- ity into three interpretable components, each capturing a distinct structural limitation. The proof provided in Appendix|] E.
Theorem 4.1 (Bellman-Jensen Performance Bound), Given any prediction with horizon K > 1. predictable action set A A and prediction errors e, the performance gap between the prediction- aware policy and the offline optimal policy satisfies:
CiT K A
(v (BByes, (8) off
V. BBayes,*
"KA--e(1 (5)
m0xx SES
(1 (1
71 kKys
As closs due to finite prediction window
Agtsoss due to prediction ervor
C2 Σ
|A- [+] -I
1)02 maxx
Ag:loss due to partial action predictability
where Ci and C2 are absolute constants, Cj denotes the prediction error at step j. defined as the Wasserstein-I I distance between the predicted and true transition distributions; parameter 02 max, .t 0² (r((s, ac|sa = s, a.:)) captures the variability of the reward, and a(-) denotes the Sab-Gaussian parameter.
Interpretation. Theorem 4.1 shows that the performance gap decomposes into three terms. The first term A₁ quantifies the performance loss due to the finite prediction horizon K. The factor 7 reflects that the benefit of predictions decreases exponentially with the horizon length, implying that even short-term predictions can capture significant potential improvement. When K - cc, this loss term

---

diminishes. The (1 -/)0/// exponent arises from a refined dyadic horizon decomposition argument controlling the dependence on the discount factor (see Lemmas E.2 and E.3 for details). The term vlog | shows the number of actions slightly increases this gap, as a larger action space makes statistically harder to identify the optimal action under uncertainty.
The second term A2 captures the impact prediction errors and disappears the predicted transitions become accurate. Notably, it highlights that errors in subsequent steps have progressively smaller effects on overall performance, aligning with practical intuition. When e for all j. we have A2 ((e/(1 2) which is independent of K, indicating that this term is primarily governed by the average prediction error, rather than the length of the prediction horizon.
The third term A3 arises from partial action predictability and vanishes when all actions are pre- dictable (i.e., A A). It is scaled by / indicating that greater reward uncertainty am- plifies the Bellman-Jensen Gap. When A = 0, this term will not blow up and simplifies to O(Vlog A| -))
Corollary 4.1. Given any prediction horizon K 2 if the predictions are perfectly accurate with Ej = 0 for all 1 S j & K, and all actions are predictable with A = A. then the maximal BuBus,, (s)) O K VK).
performance gap satisfies max,es( (V-Kess,, -
This result demonstrates that sufficiently accurate predictive informationeven over finite horizoncan dramatically reduce the fundamental Bellman-Jensen Gap, bringing the agents performance signif- icantly closer to the offline oracle benchmark. It characterizes the theoretical upper bound on the improvement that predictive signals can offer, revealing an exponential decay in the gap with horizon length K, up to a sublinear K correction term.
5 BOLA: Bayesian Offline Learning with Online Adaptation
Building the theoretical understanding of the prediction-awant policy, in this section, present practical model-based algorithm for implementing the prediction-aware optimal policy.
The key insight from Theorem 3.1 and Corollary 3.1 is that optimal decisions can be achieved by combining short-horizon planning with a precomputed Bayesian value as the terminal function, which can effectively leverage predictive information without explicitly expanding the state space. This motivates the design of BOLA, a two-stage approach that cleanly separates offline learning from online adaptation to predictions.
5.1 BOLA Algorithm Overview
We propose BOLA (Bayesian Offline Learning with Online Adaptation), model-based reinforcement learning algorithm designed to exploit transition predictions for efficient decision-making. BOLA decomposes learning and planning into two stages: (1) Offline Stage: Estimate the Bayesian value y-Bayes.* function "KA-- (s) from samples by solving the Bellman equation in Eq. (5). and (2) Online Stage: At each decision point, observe real-time transition predictions o and compute the optimal short-horizon action sequence using Eq.
Offline Bayesian Value Function Learning. To implement the prediction-aware Bellman operator from Eq. (5). we adopt a model-basse learning approach inspired by classical MDPs. Specifically, we estimate the key quantities required compute the Bayesian value function / "KA- (s) via value iteration. These include: (1) the reward function r(s, a), (2) the distribution over K -stepp transition predictions P(o), and (3) the multi-step transition kernel ((s' s,a,
yBBayss.
Importantly, the recursive structure in Eq. (6) allows us to avoid estimating the full K K-step transition model directly. Instead, it suffices to estimate one-step transition probabilities P(s' a) for predictable actions a E A and standard MDP transitions P(s' s, a) for actions & A
We assume access to generative model (21, For each state-action pair (s, a) with & A the generative model allows us to generate N, independent next-state samples, denoted by [s)
N.
7

---

For estimating the prediction distribution, we assume there exists prediction oracle defined as follows:
Assumption 5.1 (Prediction Oracle). The agent has access to a prediction oracle D pred that, upon query, returns independent sumples a' P(a), where o' = (oi (oi..... o'k) represents K K-step transition prediction vector drawn from the underlying distribution P(ar).
Under this assumption, we draw N2 independent prediction samples from the oracle, denoted by for = ))) ) which are then used to estimate P(a) via empirical frequencies.
Using these samples, we estimate the relevant probabilities by empirical frequency:
P(6' 8,
1
Σ Ni
16( = =s), Va E AAEA,
(11)
N1
P(o) - 2₂
Σ 1= 1(o' o), Vo Qk.
(12)
The reward function r(s,a) a) is obtained by sampling from each state-action pair (8, a) once.
With all model components estimated, we apply value iteration on the prediction-augmeette Bellman operator in Eq. to compute approximate Bayesian value function Bayes,, property of the Bellman operator ensures that this fixed-point iteration converges.
K,A--c"" The contraction
Online Adaptation. At each decision point, BOLA receives K K-step transition prediction vector (oI...., σK). Given the current state BOLA first evaluates the multi-step transition probabilities by incorporating the prediction σ, and then solves the optimal action sequence through Eq. 7 using precomputed Bayesian value function Bayes,
K.A-,e"
This scheme enables real-time adaptation without solving high nigh-dimensional value functions online. By combining offline long-term terminal value estimation with short-horizon prediction-aware planning 23 BOLA avoids state space augmentation and maintains computational tractability. Algorithm summarizes the BOLA procedure.
Algorithm BOLA: Bayesian Offline Learning with Online Adaptation
Sample N₁ times from each (s, E S x A A and get samples (
M
2: Sample N2 empirical predictions {a Ji=1 from the prediction oracle 2 predi
3: Estimate transition model P(s' s, a) and distribution P(ar) according to Eq. 12
4: Solve the estimated Bayesian value function Bayes.* using value iteration;
K.A--
5: for each decision timestep do
6: Observe the current state and the transition prediction o;
7: for ł = 1 to K do
8:
Compute the transition probabilities P(s s, do:-11, I.)) using Eq. (6;
9: end for
10: Determine the optimal policy x² 88 .)) by solving Eq. 7
11:
end for
5.2 Sample Complexity Guarantees
This section presents the sample complexity guarantees of Algorithm | more specifically, the learning of the Bayesian value function. The proof of the following theorem is presented in Appendix F Theorem 5.1. For any given MDP, any confidence level 5 (0, 1), any desired accuracy level E (0, } a tradeoff parameter a E (0, 1), and prediction horizon K 2 1, let D be the number of samples drawn from the generative model, and D2 be the number of samples drawn from the prediction oracle Pred. If
D C1SA((AA) (A- log S[AI - 1A-1)/8) +1S||A),
71 1001-a)26 2.2
Co log (415)/5)
D2 = (1 - (1 - 2
8

---

where C1 C2 are absolute constants, then with probability at least 1 - 6, the learned Bayesian value function satisfies
max
Bayes, K.A
(s)
V-Baves,
K.A T
(s) e.
(13)
Theorem 5.1 quantifies the sample complexity of BOLA, explicitly capturing the interplay between environment sampling and predictive adaptation. In particular, BOLAs total sample requirements decompose into two distinct regimes:
Environmentintrracioon samples Dj. The first requirement D1, arising from direct environment interactions, scales with |A| |, the number of unpredictable actions. This leads to sample complexity which is strictly smaller than the classical dependence of O(S)) [4] 24], since increased predictability reduces the enviromment sampling burden. In the extreme case where all actions in the prediction horizon are predictable (A- A), the dominant term of D, vanishes altogether (except for the reward function learning cost |S][A],, as the predictive model fully specifies the transition dynamics within the prediction horizon.
The second term D2 represents the samples required from the predictive model, which exhibits a distinct scaling behavior: as the prediction horizon K grows, the required number of samples decreases due to the stronger contraction factor y in the Bayesian Bellman equation. When K 2 (log((,, (,) )), this term improves (1 - ?) -2, which lower than that in model-based RL [3]. This highlights that when predictions are both comprehensive and with long enough horizon, BOLA can achieve lower sample complexity than classical MDP approaches.
Prediction Oracle Samples D2.
Trade-off between the Two Sample Sources. Together, these two sampling regimes reveal a trade- off parameterized by a: increasing a (more environment interaction) raises the environment sample requirement Dj to O((1 a) 2), while reducing the required number of samples D2 from the prediction oracle. One can choose a reasonable a to trade off the sample requirements.
6 Numerical Studies
Although our emphasis is on theory and finitesample guarantees, we provide a small-scale empirical case study to demonstrate practical relevance. Specifically, we evaluate BOLA on a windfarm storage control task, where the operator minimizes energy imbalance penalties by charging or discharging a battery based on wind mismatch, price signals, and current state of charge (see Figure I for the setup, Appendix G for more details, and Appendix H for additional experiments).
Specifically, Figure 2(a) illustrates the cumulative cost reduction achieved by BOLA under different prediction horizons, compared against baseline MDP policy without prediction. As the prediction horizon K increases from 1 to 4, the cost reduction consistently improves, confirming that longer foresight enables the agent better anticipate upcoming mismatches and price fluctuations. Notably, the largest marginal improvement occurs at K = 1. indicating that even a short look-ahead can significantly enhance decision-making performance. Figure 26) illustraas the robustness of BOLA under increasing levels of relative prediction error. As the prediction error increases, the performance of all methods declines approximately linearly, which aligns with our theoretical analysis. Notably, longer prediction horizons yield greater cost savings under perfect or low-noise forecasts but also exhibit greater sensitivity to prediction errors. In contrast, shorter horizons are more stable and
Required Power
Genernted
Power
We
W+ V2
Power Supply
1r
Power Grid
Wind Farm
Energy Storage System
Figure 1: Wind Farm Storage Control

---

4000
Horzon
Prodiction Horizon K=3
Reduction (4)
3000
Prediction Horizon 2
Prediction Horizon K=
Cost Reduction
No Precictions
2000
2000
Prediction Horizon
Prediction Horizon K=3
Prediction Horizon
1080
1000
Prddction Horizon K-1
No Prediction Baseline
0
1000
15000
2500
Error (56
(a) Cost Reduction with Predictions
(b) Robustness Prediction Errors
Figure 2: Storage Control Performance. (a) Cumulative cost reduction for different prediction
horizons: longer prediction horizon yields greater savings over the no-prediction baseline. (b) Robustness prediction noise: cost savings decline roughly linearly with error, yet all predictive policies outperform the baseline even 30% noise.
degrade more gradually noise increases. Nevertheless, all prediction- based policies consistently outperform the no- no-prediction baseline, even when the relative error reaches 30%.
Conclusion
In this work, study the theoretical value of transition predictions in sequential decision-making. We propose a prediction-augmentee MDP framework, characterize the benefit of predictions via the Bellman-Jensen Gap, and develop tractable model-based RL algorithm with sample complexity guarantees. A natural future direction is to extend our results to the model-free setting.
Limitations and Future Directions. In prediction-augmente MDP, we consider fixed-horizon planning where the agent receives a K K-step prediction and plans a K-step sequence of actions. For sequential decision decision-making problems with predictions, another popular framework is called the sereding-horizong control, where the agent receives K-step prediction but only plans a single-step action instead of sequence of K actions. Intuitively, using receding-horizon horizon control could be more beneficial to the agent than fixed-horizon planning, since the agent does not have to commit to sequence of actions and can adaptively choose actions based the realizations of the states and the predictions. Further investigating the advantage of receding-horizon control among the future directions of this work. On the theoretical side, we have established the first upper bounds on BOLAs sample complexity, but it remains open whether these be tightened matched by lower bounds. In particular, refined variance-based techniques (e.g.. refined concentration for the multi-step Bayesian operator) may yield stronger guarantees.
MDPs with
Acknowledgments
We sincerely thank anonymous area chair and reviewers for their insightful feedback. We are grateful to Hongyu Yi for proofreading the paper and to Laixi Shi for helpful discussions.
C. Wu's work was supported in part by the National Natural Science Foundation of China under Grant
72271213, the Shenzhen Science and Technology Program under Grant RCYX20221088092227700
A. Wierman's work was supported in part by NSF grants CNS-2146814, CPS-2136197, CNS-
2 2106403, and NGSDI-2105648.
10

---

References
[1] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[2] Lukasz Kaiser, Mohammad Babacizadch, Piotr Milos, Blažej Osiáski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model- based reinforcement learning for Atari. In International Conference on Learning Representa- tions.
[3] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: survey. The International Journal of Robotics Research, 32(11): 2013.
[4] Ammar Haydari and Yasin Yilmaz. Deep reinforcement learning for intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(1):11-33) 2020.
[5] Xin Chen, Guannan Qu, Yujie Tang, Steven Low, and Na Li. Reinforcement learning for selective key applications power systems: Recent advances and future challenges. IEEE Transactions on Smart Grid, 13(4):2935-2958, 2022.
[6] Thomas M Moerland, Joost Broekens, Aske Plaat, Catholijn M Jonker, al. Model-based reinforcement learning: A survey. Foundations and Trendso in Machine Learning, 16(1):1-118, 2023.
[7] Leslie Pack Kaelbling, Michael Littman, and Andrew W Moore. Reinforcement learning: A survey, Journal of artificial intelligence research, 4:237-285, 1996.
[8] Arthur Charpentier, Romuald Elie, and Carl Remlinger. Reinforcement learning economics and finance. Computational Economics, pages 1-38, 2021.
[9] Adil Ahmed and Muhammad Khalid. A review on the selected applications of forecasting models in renewable power systems. Renewable and Sustainable Energy Reviews, 100:9-21, 2019.
[10] John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-difference learning with function approximation. Advances neural information processing systems, 9, 1996.
[11] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal differ- ence learning with linear function approximation. In Conference on learning theory, pages 1691-1692. PMLR, 2018
[12] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD-lcarning In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[13] Zaiwei Chen, John-Paul Clarke, and Siva Theja Maguluri. Target network and truncation overcome the deadly triad in Q-learning. SIAM Journal on Mathematics of Data Science, 5(4): 1078-1101, 2023.
[14] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. On the sample complexity of reinforcement learning with a generative model. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1707-1714, 2012.
[15) Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. Advances in neural information processing systems, 33: 1281--211772 2020.
[16] Chenbei Lu, Laixi Shi, Zaiwei Chen, Chenye Wu, and Adam Wierman. Overcoming the curse of dimensionality in reinforcement learning through approximate factorization. In Forty-second International Conference Machine Learning (ICML. 2025), 2025.
[17) Ziyi Zhang, Guannan Qu, et al. Predictive control and regret analysis of non-stationary MDP with look-aheas information. Transactions on Machine Learning Research.

---

[18] Lixing Lyu, Jiashuo Jiang, and Wang Chi Cheung. Efficiently solving discounted MDPs with predictions on transition matrices. Preprint 1111:2500.15345. 2025.
[19] Carlos E Garcia, David M Prett, and Manfred Morari. Model predictive control: Theory and practicea survey. Automatica, 25(3):335- -388,,5--,. 1989.
[20] EN Barron and H Ishii. The bellman equation for minimizing the maximum cost. Nonlinear Anal. Theory Methods Applic., 13()):1067-1090, 1989.
[21] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near- optimal planning in large Markov decision processes. Machine learning, 49:193-20 208, 2002.
[22] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[23] Philip Allmendinger. Planning theory. Bloomsbury Publishing, 2017.
[24] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34: 1772--77777 2021.
[25] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
[26] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning. 91:325-349, 2013.
[27] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31, 2018
[28] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[29] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforce- ment learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
[30] Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward MDPs, In International Conference on Machine Learning. pages 5055-5064. PMLR, 2021.
[31] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. Advances in Neural Information Processing Systems, 35:31 10-31220 2022.
[32] Pascal Poupart and Nikos Vlassis. Model-based bayesian reinforcement learning in partially observable domains. In Proc Int. Symp. on Artificial Intelligence and Mathematics, pages 1-2, 2008.
[33] Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. Advances in Neural Information Processing Systems, 35:578 592, 2022.
[34] Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle: A generic model-based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 963-376, 2023.
[35] Michael O' Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptis Markov decision processes. University of Massachusetts Amherst, 2002.
[36] Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptive pomdps. Advances in neural information processing systems, 20, 2007.
12

---

[37] Arthur Guez. David Silver, and Peter Dayan. Efficient bayes- adaptive reinforcement learning using sample-based search. Advances in neural information processing systems, 25, 2012.
[38]
Ibrahim El Shar and Daniel Jiang. Lookahead-bounded Q-learning. International Conference on Machine Learning, pages 1665-8675 PMLR, 2020.
[39] Anna Winnicki, Joseph Lubars, Michael Livesay, and Srikant. The role of lookahead and ap- proximate policy evaluation in reinforcement learning with linear value function approximation. Operations Research, 73(1):139-155) 139-156, 2025.
[40] Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Beyond the one-step greedy approach in reinforcement learning. In International Conference on Machine Learning, pages 1387-1396. PMI.,, 2018.
[41] Aviy Rosenberg, Assaf Hallak, Shie Mannor, Gal Chechik, and Gal Dalal. Planning and learning with adaptive lookahead. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9606-9613, 2023.
[42] Yonathan Efroni, Mohammad Ghavamzadeh, and Shic Mannor. Online planning with lookahead policies. Advances in Neural Information Processing Systems, 33:14024-14033 2020.
[43] Noah Golowich and Ankur Moitra. Can Q-learning be improved with advice? In Conference on Learning Theory, pages 4548-4619. PMLR, 2022.
[44] Tongxin Li, Yiheng Lin, Shaolei Ren, and Adam Wierman. Beyond black-box advice: Learning- augmented algorithms for MDPs with Q-value predictions. Advances in Neural Information Processing Systems, 36, 2024.
[45] Yingying Li and Na Li. Leveraging predictions in smoothed online convex optimization via gradee algorithms. Advances in Neural Information Processing Systems, 33: 14520-14531, 2020.
[46] Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66(10) 4761-4768 2020.
[47] Niangjun Chen, Anish Agarwal, Adam Wierman, Siddharth Barman, and Lachlan LH Andrew. Online convex optimization using predictions. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 191-204, 2015.
[48] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-32, 2020.
[49] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, 33: 1994-2004, 2020.
[50] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online LQR control with predictions. In 2021 American Control Conference (ACC), pages 697-703 IEEE, 2021.
[51] Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guamnan Qu, and Adam Wierman. Perturbation-base regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 14:5174-5185 2021.
[52] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret MPC via perturbation analysis: Prediction error, constraints, and nonlinearity. Advances in Neural Information Processing Systems, 35:36174-361877 2022.
[53] Luc Mercier and Pascal Van Hentenryck. Performance analysis of online anticipatory algorithms for large multistage stochastic integer programs. In IJCAI, pages 1979-1984, 2007.
[54] Martin I. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
13

---

[55] Dimitri Bertsekas and John N Tsitsiklis. Neuro-Dynamte Programming. Athena Scientific, 1996.
[56] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math, 3(1):133-111, 1922.
[57] Walter Rudin et al. Principles of Mathematical Analysis, volume 3. McGraw-hill New York, 1964.
[58] Roman Vershynin. High-DDienssiona Probability: An Introduction with Applications in Data Science, volume 47. Cambridge University Press, 2018.
[59] Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends@ in Machine Learning,
2019.
[60] California ISO. Electricity Price Data. httpps//www.eerrggoonneeeee/oo//
2021.
Online; accessed on 20 December 2022.
[61] Chenbei Lu, Hongyu Yi, Jiahao Zhang, and Chenye Wu. Self-improving online storage control for stable wind power commitment. IEEE Transactions Smart Grid, 2024.
[62] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored MDPs. Advances in Neural Information Processing Systems, 27, 2014.
[63] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded Eluder dimension. Advances in Neural Information Processing Systems,
2020.
[64] William Koch, Renato Mancuso, Richard West, and Azer Bestavros. for UAV attitude control. ACM Trunsactions on Cyber-Physical Systems, 3(2):1-21, 2019.
Reinforcement learning
[65] Gaoyuan Xu, Jian Shi, Jiaman Wu, Chenbei Lu, Chenye Wu, Dan Wang, and Zhu Han. An optimal celuutions-uuidee deep reinforcement learning approach for online energy storage control. 2024.
Applied Energy,
[66] Chenbei Lu, Nan Gu, Wenqian Jiang, and Chenye Wu. Sample-adaptive robust economic dispatch with statistically feasible guarantees. IEEE Transactions on Power Systems, 39(1): 779-793, 2023.
[67] Lin Lin, Xin Guan, Yu Peng, Ning Wang. Sabita Maharjan, and Tomoaki Ohtsuki. Deep reinforcement learning for economic dispatch of virtual power plant internet of energy. IEEE Internet of Things Journal, 7(7):6288-665 6601, 2020.
[68] Giancarlo Mantovani and Luca Ferrarini. Temperature control of commercial building with model predictive control techniques. IEEE transactions on industrial electronics, 62(4): 2651-2660, 2014.
[69] Shiying Huang, Peng Li, Ming Yang, Yuan Gao, Jiangyang Yun, and Changhang Zhang. A control strategy hased on deep reinforcement learning under the combined wind-solar storage system. IEEE Transactions on Industry Applications, 5766)6647--6588 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction reflect the papers contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals motivation long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We provide the limitations in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide them in the Appendix
Guidelines:
15

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We have provided detailed parameters and settings in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture. describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-souse source models, it may be that access to the model is limited in some way (e.g.. to registered users). but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We included code and data in supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
16

---

Please see the NeurIPS code and data submission guidelines (https://nips.co//) Sondde//oooeSuumissiiiooooooe
for more details.
While we encourage the release code and data, we understand that this might not be possible, No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
guides//CoeeSumiise ssissiiin ssionPolicyy for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reprodueible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided all the experimental settings in experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: They are correctly defined.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
17

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
They are included in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e-g.. preliminary or failed experiments that didn't make into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:://tutrrrte http://arr.p.rro/aaaa//////aaaaa
Answer: [Yes]
Justification:
We confirm this issue
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We justify the practical relevance and socictal impacts in the introduction part.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
18

---

11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This work does involve releasing pretrained models or sensitive datasets, and thus no additional safeguards for high-risk model or data release are applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We mentioned the source of data.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g,, website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information creators.
available online, the authors encouraged reach out the asset's
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provided the code and data.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification:
We use LLMs to polish some writings.
Guidelines:
The answer NA means that the method development in this research does not involve LLMMs as any important, original, or non-standard components.
Please refer to our LLM policy httppe/r/baurrrecccc///orrrrrrrr for what should or should not be described.
20

---

Appendices
A Related Literature
Classical Model-Based RL and Sample Complexity. Our work builds on the modelbased RL paradigm, which separates learning into model estimation and policy planning. Classical model- based RL for finite MDPs has been extensively studied and achieves minimax-optimal sample complexity guarantees [4 25 Recent extensions of sample complexity analyses cover broader classes of problems, including average-reward MDPs [30], constrained MDPs BT, and partially observable MDPs (POMDPs) 34 In contrast, we tackle new settingMDPs augmented with multistep transition predictionsand establish the first finitesample guarantees (Theorem (51)) under both environment and prediction sampling. Notably, when the prediction horizon satisfies K (loog(1 ([log(1/7)) 1/7)), the stronger contraction factor 7K leads to a strictly lower sample complexity than the classical bound [14 15), highlighting how predictive information can fundamentally accelerate learning.
RL with Look-ahead Prediction and Planning. Integrating multi-step look-ahead forecasts into reinforcement learning has driven strong empirical gains. Related work ranges from Bayes- Adaptive methods [35 and look-ahead Q-learning [38 [9] to policy-iteration variants 440 4] and real- time dynamic programming 42 However, these methods focus primarily on empirical gains and offer little theoretical support on some key points: they neither quantify the value added by multi-step predictions nor guarantee robustness when forecasts are noisy or partial, and they do not address the sample complexity of learning with such predictions. We fill these gaps by introducing the BellmanJensen framework, which is the first to deliver rigorous performance and robustness guarantees for multi-step, imperfect transition predictions in RL. We also propose BOLA, which comes with finite-sample complexity bounds for RL with transition predictions.
MDPs with Predictions. Recent work has explored integrating predictions into MDPs in several ways. Some methods leverage Q-value predictions to to speed up learning or refine suboptimal policies 4 44
There are also some more related work focusing on incorporating estimates of the transition kernel to boost performance in nonstationary environment [17] or improve sample efficiency [8]. However, these approaches target matching the performance of an idealized MDP with perfect models. By contrast, we use realizationbased, multistep transition forecasts to surpass the inherent limits of classical online MDP solutions, driving performance closer to the offlineoptimal benchmark even under imperfect and partial predictions (Theorem
Online Optimization and Control with Predictions. Leveraging predictive information is com- mon strategy in broader online optimization and control contexts, notably within Online Convex Optimization (OCO) and Model Predictive Control (MPC). For example, recent studies 45 demonstrate exponentially decaying regret when leveraging predictions Smoothed Online Convex Optimization (SOCO). Lin al. [48) have identified conditions under which predictions significantly enhance performance in general online optimization settings. Similarly, prediction -driiiiiionnriennnnneie improve- ments have been established in linear-quadratic control frameworks, yielding exponential regret reduction 44 50). and have been successfully extended to MPC settings, even with time-varying (53) investigate prediction in general online optimization setting, offering useful insights, while leaving open questions on the formal analysis on the value of prediction and on broader prediction settings. Compared to this extensive literature on deterministic or structured linear settings, irediction-augmente attention due to their inherent complexity and lack of closed-form solutions. Our work addresses this gap by providing rigorous theoretical foundations, clear sample complexity characterizations, and practical algorithms that effectively integrate predictive realizations into sequential stochastic Docision-making
constraints 51 52) Mercier el al.
stochastic models such as MDPs have received relatively limited
21

---

B Proof of Theorem 3.1
The proof is divided into 3 steps. First, we construct an auxiliary MDP M and show that its optimal policy X* is the same as the optimal policy x of the prediction-uummente MDP. Then, we show that the optimal value function satisfies our proposed Bellman equation of the prediction-augmen -aagmtion-augmenteed MDP. Finally, we show that the Bellman operator associated with our Bellman equation is a contraction mapping, which implies that it has unique fixed point solution.
Step 1: Construction of the Auxiliary MDP M. In prediction-augiie -ugmented MDP, the agent essentially makes decisions based on both the current state s and the received prediction o. Therefore, can incorporate the prediction into the state and define auxiliary MDP based it. Specifically, let M = (S, A, i, P.5) be an MDP with state space S, action space A, reward function i; transition kernel P, and discount factor ? The state space S is the product space of the state space of the original MDP and the domain of the prediction o, i.e.,
(s, E S == S Q, where (01, 02 TK). The action space A is the K K-product space of the action space of the original MDP, i.e., a = (ao, "1."....p ak-1) E Á AA For any E S and a E A, the reward function F(.,)) is defined to be the K K-step expected discounted reward of the original MDP, that is,
K Σ
1- (r((s)aa))
7(8, a) E
any where sp = and 8, P( s, doa-l ta) for all 2 1. For any (5 (8, and = (s',o'), the transition probability P(3 3, a) is defined as
P( a) = P(s', o' = P(s))s,..0))((())
Finally, the discount factor of the auxiliary MDP satisfies 7 = >
For the policy क S Ā A(Ā) (where A(Ā) denotes the probability simplex on A). The corresponding value function v the auxiliary MDP is defined as
VT (8) Ex Σ 7-7(3,, a.) 50 =] V
The auxiliary MDP is with infinite state space and finite action space. The Bellman optimality equation remains valid provided the bounded rewards, the measurable transition kernel, and a discount factor 5 E [0, 1). These conditions ensure the Bellman operator is 7-contraction the space of bounded measurable functions (54 55
Therefore, the optimal value function V is the unique solution to the following Bellman optimality cquation:
(=(3) max aεA ((3,a)+T* / Jses (()5)3.a)('88))
(14)
In addition, any policy म* satisfying
(F(5,a)+/) +2k / Jses P(d3'ss
{a E (a 8) > 0} C arg max
(15)
for all 5 (s, σ)) an optimal policy.
Since the auxiliary MDP has the same problem structure (state, action, transition, reward) as the prediction-augmentedd MDP, an optimal policy #* of the auxiliary MDP is also optimal policy n² of the prediction-augmented MDP.
Step 2: Establishing the Bellman Equation. Recall from Section 3.1 that we defined the Bayesian
value function Bayess, (s) (V (s, E. (V= (5)), where = (8) Using the
previous identity in Eq. 14 we have that under the optimal policy n².
V Bayes,
K.A-
(8)
Er
max LaEA
F(3,a) + +
Jse
[ P(d3')s, (()3"),
K-1 Σ === 7 ( P(sels, Plelss.onn--.0nddree...
=Ea
max aEA
22

---

+ J s s. a.
(16)
JEB
For the term Jies P(dø' 5, a. we use the independence between prediction and state and get:
J 348
a)) Eves [ D'EQ
P(lls...oo))(ddd))
Eves P(5ll,,,,0))
d'eQ P(do')V" /
Eves (i.
= Eves (ayer. Eves a K.A_. K.A-
o o')l
(17)
Combining the previous two equations, we finally have:
V Bayes, (8) Eo
Σ K-1
P(sels, (is1s,,0
max LaE
1=
+7 Σ
P(s is, a. V (e
(18)
for all 8 E S. This leads to the Bellman optimality equation in Eq. (
Step 3: The Uniqueness of the Solution to the Bayesian Bellman Equation. It is easy verify that our Bellman equation is a fixed-point equation with a contractive fixed-point operator, where the contraction factor is , Therefore, by the Banach fixed-point theorem [56), the solution to Bellman equation is unique.
C Proof of the Corollary 3.1
This is a direct corollary of Theorem 3.1 Recall that, the optimal policy π is consistent with the optimal policy of the auxiliary MDP M defined in Section B Hence, combining Eq. (55 and Eq. (17) yields the optimal policy:
K-1 Σn
(a E AK (a| > 0} S arg max aEAR
Σ sx
P(skls; V K.A
(sk) (sk)) (sK))
Bayes,
D Proof of the Existence of V BBayes, (ayyes.(s) off
For any state E S and 2 1, we define the following truncated optimal value function with k-step accurate transition prediction o ii
Σ 8-1
(r oittt))
(s)
Eoi
max 0pok-1
We now show the sequence ( is (1) monotonically increasing with & and (2) bounded.
For monotonically increasing, since Vi Voft,+((()) (8) can be represented by:
Voll (s) = Eoiue
max ag.k
Σ
y y'r(s,, = (..01141))
2 Eo
max
Σ 1=0
yrr s, . +min 7 *r = s00
aook-1
23

---

k-1
(rrs =s, s
Boix. 11
max aa.k-1 1
vft (s);
where the last inequality is due to r(s, a) 2 0 for any state-action pair (8,a).
For the bounded property, it is clear that V z Σ X S - for any k. Hence, the sequence (V off (+)) Ha is monotonically increasing and bounded, implying Vist (8) lim Voft (eft,e(b) exists for any s. This concludes our proof.
Bayees
E Proof of Theorem
Let V VBBayes,
Baress (8) for all S. The following lemma verifies that oo, o (s) lim K.A- BBayes,+
V "oo-A_ (0()) is indeed well-defined.
Lemma E.1 (Proof in Appendix
E. limg-
K.A- (s)
(s) exists and is unique.
To bound the difference between Vo tion:
Bayes, and V Bayes, (s), we perform the following decomposi- K,A-
V Bayees.*ss (s) - V Bayess,
'Kd- (s) V Bayes, - .0 (s)
V Bayes, (s) +
Bayess
(())
V V-Bayess *
off
off
.0
Ti
12
Bayes,, K.A (())
Bayee, (s), VsE. K.A
(19)
T3
Here, Ti denotes the loss incurred by the finite prediction window K, T2 captures the loss stemming from partial action predictability, and T's accounts for the error introduced by prediction errors. We bound these three terms as follows.
Step 1: Bounding the Term Ti using Dyadic Horizon Decomposition. We begin by analyzing the Bellman-Jense Gap due to the finite prediction horizon K. Since the value function sequence (V Bayes. (s)} converges as k - co, any subsequence must also converge to the same limit. There- fore, for any s E S, we make dyadic horizon decomposition as follows:
B-Bayes ( (s) V V-Bayes,+
K.A- (s)
lim k+000
TyBayes.+ (s) K
V- Bayess, KAA-,00 (s)
lim k
Bayes, K-2h,A (s)
Bayes,
K,A (0(())
lim A-
Σ
k-1
K-24+1 A (s)
Bayes,
VK-2 oo (8)) (
(20)
Based this decomposition, only need to provide upper bound to the value function gap when doubling the prediction window, which is stated in the following lemma.
Lemma E.2 (Proof in Appendix E.2 For any prediction window K we have
max V Bayes,* (s) - (BBa)ss. I 2 /CK log IAI K.A (s))
(21)
2K.A
(1 (1-) (11)22k)
where C is absolute constant.
By repeatedly using Lemma we have the following lemma that bounds the term Ti in Eq. [19
Lemma E.3 (Proof in Appendix E.3 There exists an absolute constant Co 0 such that the following inequality holds for all K Co::
Ci,K K / /logg A
(1 (1-7) 2
where C₁ is an absolute constant.
24

---

Step 2: Bounding the term T2. For any E S, Viaayess and V (o) are based on full
prediction o² and partial one o with predictable action a E AT, satisfying:
V
Bayos, (s) lim Bojs
Σ 1-
rr(s aelso = =s oist1) ii0
off
max
8-000
0o,A _0
Bayes, (s)
lim Boi
max Guok-1
Σ 1=0
7'r(s ael00 = 01411)
k0000
Therefore, have
V y-Bayes,* Bayes, 00.A-00
off
lim k0000
Foix
max dosk-1
Σ x- a000=
= ii41)
k-1 En ("r(se, as|s0 (ma+z))
The following lemma further bounds the Bellman-Jensen Gap due to partial action-coverage. Lemma E.4 (Proof Appendix E.4 For any predictable action set
C A, we have:
max (VBayess (s) - co.A- (s) S C2 EnE 7'Vlog(
A (
A [+] + 1)6 max
where O2 is an absolute constant, 6 max,,am..! 0² (r(st, as|so = ao:a), where a(-) denotes the sub- Gaussian parameter. Parameler Orax then captures the variability of the reward.
Step 3: Bounding the Term Tg. T3 captures the value decay due to prediction errors. We
Lemma E.5 (Proof in Appendix E.5). For any prediction horizon K and predictable action set A have:
3 V. Bayes, (s)) S 7) - -1- Ej K.A- a
max Bayes,* SES
(s)
(22)
K.A
where e == (P7 denotes the Wassersteinl distance between the distributions Pj. P3 of the j-step predictive model under accurate and inaccurate prediction o3 and o, respectively, measured with respect to the base metric d(o o.)) = Wi(a,, oz),, i.e., the Wassersteinl distance between single-step predictive distributions.
Step 4: Putting pieces together. Our last step is to combine the bounds we obtained for the terms Ti, T2 and T's get the final results:
max (v) (+)( < C17 / K log A
K
2
(1 3) 2
71
7kys
j=1
+ C2 E 7/ Vog(
A 1+1 |A- [+1
--1(+11
1)0
This concludes the proof.
E.1 Proof of Lemma E.
First of all, since we work with bounded rewards, it is easy to see that K.A- B (s) S 1/(1 - -7) for any k 2 0 and E S. Next, we show that (V.Bayes (s) is Cauchy sequence, which implies its convergence [57].
Recall the Bellman equation for y- Bayes,, k+I.A ,0'
y Bayes,+ -+1, (s) Eor
max Σ nd Σ
P Plaalss.o.r.....wrrraa.a.
+ + k+1 Σ P(s o) v Bayes,
k+1.A-,00 (8
8k+1
25

---

for any s E S and & 2 0. Therefore, we can truncate the tail term and have
xkl
Ba (5) I E
max Σ
Σ
P(suls, au--1, oud
In addition, since the residual positive, we have V-Bayes,+ imply
-+I,A-,000 -0(())
V Bayes.. ,0(s) 0. Together, they
B B 7t ++1,A--00 - Rid ( -
(23)
1 1-7
Similarly, we have
V. Bayes.*
R. 0 (s)
E
max
7
Σ
P(sils, au.-1, ou) + +1*h ((oxlssa, (
a
1=0
< Eg
max Σn
aus, aus, aus (us)))((s
1-7
1=0
BB Bayes,*
7
K.A K.A--0(8) +
1-7
and (ayess - -V Bayes,
",A-, (8)
k.A (s) 2 - Together, they imply
nk Vs E S.
Bayaye, v K.A- .0 (s)
Bayes,
A.d .n (s) S
(24)
1-
Combining Eq. (23 and 244. we have by triangle inequality that
Bayes,,
(s)
1.
Bayes,*
(s)
Bayea,* 1+1.A-
(s) - V k. ( +
Bayes,* Bayes. k.A-.o(s)) (s)
*+1,A=
R.A
0
R.A 0
27
1
Now, for any > O, choosing such that of generality that 2 n),, we have
27 [-ン)e
S then, for any m, 2 k (assuming without loss
172
V-Bayes. (5)
Bayess. A.A-
Σ
Bayes.
n+itA-,00 (s)
ati+1.1-
m7 1-1
27
1
2
7)²
S.
Therefore, for any e S, (s) is Cauchy sequence.
E.2 Proof of Lemma E.2
To bound the value improvement from doubling the prediction window, we use a sub-Gaussian moment-generatte function bound combined with tailored Jensen-based analysis. For simplicity of presentation, define auxiliary Q-function, denoted by (5 a, or). Specifically, for all E S. AK, and E Qk.
(3)0,00)
Σ 7' Σ P (1slss, + +7 >>>E
/) Bayea, K.A K.A-.0% 1 (5k).
8K
26

---

Thus, for any 8 E S and K 2 I, we have
V- (0(s) - (BBayes. 2KK
K,A KAA-,0
20 [max Q2 (8; 00:2K-1,
Eo [max (8, 10:
=/o max 00.
122)
eix
max
Qx
! max ((00
JaI JaKI122KERx
-J max (0 P(do
eex
JonKERx (J (max Q2x 00:2k-1, 01:k)
max (xx- P(daxttxa))))) P P(do
(25)
This treatment allows us to focus on the value improvement from additional transition predic- tion of K+1:2K For any 0:2K E 22K, we bound the term max, Q2x (s, 00.2K 012kk maxa (8, 10:K-1, as follows:
max V2x 00:2k-1. (12K) max Q7 an:K -1
2K-1
Σ Σ P(sels, P(alss-an +y2k 2K
P(22k (s 00:2K-1, 0122 V.
2K,A ($2x)
Bayes,
00:2K
Σ
Bayes * 11 Byyee (sx))))
max ao.K
ax
2K-1
P(sels, [issssaaa..,,,o::rreeaaa)))) +y
2K
P(s2k a0:K,, 2K .0 (82k)
Bayes,
00:2K-1 -1
2K-1
01s1:s,00:tt110001)r...00.0 +g 2K
Σ 00:2k11 K
Bayes, Bayes K.A- (82K)
max
00:2K
82K
Σ P(si an--) 01 + 2 Σ P(sak|s, 00:2K11, 0
V Bayes, K.A- (82k)
0o:2k
K Σ 7
max do:K-
Σ P(7 ao1- 01a
+
Σ
Bayes, K.A- (sk))
1=
SK
(26)
Applying the max-difference inequality on Eq. 26), we can conclude:
max Qik 00:2k -1 11 1122k) max Q 00.--1,
292K 2K max V Bayes,*
2K.A . (s) (s))
Σ K-K
max
20 -1
27

---

+7k Σ
P(s2k 10
V K.A (
Bayes.
Σ ox
P(skls, 1, Bayes,
(((k)
K,A
2IK
(27)
Combining Eq. 25 and 27 and take the maximal on states both sides, have simplified
bound in a trajectory-wist reward form:
7K
max Bayee,,
V Bavess. K.A (0))
2-2
max E
K4122
(Pa(0
- -
aK:2K
(28)
where V E ((IISIA))* is trajectory-wise reward vector, defined as:
-1
V2(*K+1,8K+2, 82K, ak "KK, 02K 1)
Σ t=k
/- K ((s), at) + +g vy K,A- (82k).
The matrix P RIAI ((S)AAA)* with each entry denote the probability of visiting a state-action trajectory ($K+1, SK-2 ... 82K ag, a..... Q2K-1) given initial state s, the action vector 0K:2K-1 and transition 0 K-2K- The matrix Px(0K+1:2K) = F (o(o
Let X 1 = (P.(0k+1.2) - P.)Villaaas 1 which denotes the 0K22K-1tth entry of the vector (P ((2(k - P.)V We can verify that Xs.0k4122 04122 is the cu- mulative discounted reward, whose absolute value is bounded by 1-y. For simplicity, we denote X X, 1. by X X..a.o Therefore, Nx... is lub-Gaussian random variable, which implies
Eo(cNN) I 22.8
Va E A
Where 0 Ka denotes the sub Gau-sassiinn parameter ity and the monotonicity of exponential functions, we have for all A:
158 of X Therefore, using Jensen's 'ss inequal-
(max BEAR Xa,a,)) < Eg (maxae AK e (Xaa S Σ E(eXsaa) S Σ
aEAR
GEAR
Taking the logarithm on both sides of the previous inequality, we have
o2 2aa,x
EaEaKe
log
Eg
max Xs,a,
X
x
aEAR
mano sia A
log
|A|K
maxa 82 x.a.x 22
K log
[Al +
(29)
By choosing
2K log [A]
Eq.
29
we have
V
maxa 0² 0...K
82
LAA
a.a.K make u2 2.e.K
K log [A|
E EOK+IK max axiaK-1
(Po(oKH12K)- -P.JV
2K log (A). max. 6",a,
2K max 02 02,,K K log (A].
(30)
Substituting Eq. (30 into Eq. (28 yields:
K 2K max 0 02. log [A]
max 2K ( (s) - V. KKA-
<
VsES,K2 (31)
22
28

---

Due to the boundedness of the reward function, the sub- Gabb-Gassiin max,, 0 s.a.K of trajectory can be upper bounded by:
max 8,0
2,,,x S CC ?)
(32)
where C' is an absolute constant. Combining
32 and
31 yields our result.
E.3
Proof of Lemma D
Using Lemma B.2 in Eq. 20 and, have:
Bayes, (8) 00,A-,0
V Bayes,
(8)
lim
(V V K-24+1,A-.0 ,- K-2' AA- (0)
K.A-
k
i=
7 K.2' VCK 22 log AA
lim k
=0= (1 7) - 22)
Σ. 7 K22 v VCK 24 log A
(1 - -1 - 2)
< VCK (CKlog// |A|
(3 22
(33)
7)(1 - 222
Next, we focus on bounding the term Ei= ( (n' (2))) Denote a; 2k-2 V2a. Consider the index
20 log2( ( ) ). for any i 2 i", we notice that:
Kk22 = -172) & (7 I. KK
1 :/ (71-))
I
E 1). S 07-7/00
Hence, for any i 2 i", we have:
0,+1 = =2 k2 /
K. og K:2
2 S 57-20
-2n
K:2 2
997
1000 0,.
Summing a; from i = [i0] to infinity yields that:
Σ Enpn < ==f=]
997
1000
1000
1000 K
a.
5
a.
S
1000
3
3
3(1 - 7) T0
For the sum of az from i= ==0 to [ir]
1, we have:
Σ F1-1 -
== a
[81-1 7
K-2'
/2i
117-1
V2i
<
8
K
2/2
8
(1 - 7
Then the desired sum satisfies:
Σ a
Σ
1---1 1=0
aj + > 00
a; S 1024~
S
1=
3(1 7) 20
Hence, we can conclude that:
< Ci.cK / K Klog A
& Cia"K / K Klogg/ A (1- (1 (1 - 722
max (Vi V=x()))
(1 - 7) 15
(1 (1- 2K)
where C1 is an absolute constant.
29

---

E.4 Proof of Lemma E.4
The desired gap satisfies:
B- - V Bayes, off
oo,A (s)
lim Boi is
max
Σn 1=0
k-1 2r1 = =
k-000
Σ c=
>'r 00l00 = -,, =10
max
En X (r(s) - -s5, arlo
lim Boi k-900
max ago
lim
Boia
max (rx," agloia) r(s, 1a)
k=000
1=0
where the last inequality follows by exchanging the limit and expectation with the finite summation. Then we only need to bound each Qs separately. Specifically, for each Qe, can be rewritten into:
Q: = =ooi.
max > (r(s, ailo r(st, a 11))
-y/Boi.
max( 1arr-r(spp
r(st((())))) 0((0:))
-y'Boi,
Σ (P(s)) (..s:l))......11))) - P(s aux (o)-
max
P PRoond)).
-y -y'Boi,
max
P ii
(34)
an::
where RIS|IA denotes the reward vector, with the (s, a)-th entry equal r(s,a); Ps.ai. and P P..o.. E BBAA x|S||A| denote the random transition probability matrices from the initial state s to the state-action pair (st, az) under the action sequence do:t, specified by the transition predictions oie and 1 respectively.
RIA 1I x|S|IAI *|(s(AA
Note that P.. differs from Parii.. only due partial predictability. We can observe that the form in Eq. (34 is with the similar form as Eq. (28) in Appendix E.2 We can follow the same routine in the proof to Lemma B.. in Appendix E. to handle Eq. (34 We verify that for any action
sequence Qu. E (AT)
the corresponding rows of P s.a and P Pe.oi are identical. Formally,
for all oi we have
[Pa.o P..on.) an.t =0, Vagi E (
(35)
Hence, under any fixed I, the two 1-step kernels Port, and P+,1 agree on every row corresponding to an action sequence (AA ) Since there are |A-| such sequences, the number remaining mismatched rows is [A[ [A 1+1, Adding the trivial all-zero case yields at most |||
[A-|(+1 + 1 distinct nonzero differences between the two kernels.
Applying Lemma
E.2 to each such mismatched row, we obtain for all t 2 1:
Q. S 72 C2 v 02 In(1A[++ LA ++1
(36)
where C2 an absolute constant and 82 2 max,, ( ag Sq = s, ao:)), where (-)) denotes the sub-Gaussian parameter. Parameter 02 aax indicates the maximal variance of the reward.
Summing over 1, .. for Eq. (36) then gives
max
Bayes, (s)
Bayee, oo.A (s)) S C2 Σ
02 max In([A[++] |A-|e+1 +
SES
This completes the proof.
30

---

E,5
Proof of Lemma E.5
For clarity of presentation, for any Bayesian value function Bayes R|S| and K-step transition prediction E QK, we define:
k-1 n'
R(s, V Bayes .0) = =max
1=0
?
K Σ
do:k-1 Po o) Bayres (sk)
P(skls
(37)
#K
Applying the Bayesian Bellman equation on T3. we have:
BB V V-Bayes
(s) E
Eo~Pie
R(s, V Bayes,
K.A-.0:07 o)
E P
R(s, Bayes,
K.A-ee σ))
BowPiR
R(s, V Bayes,
K.A,00 .0: 07)
EE PNPPiN
R(s, V Bayas, K,A- K,A-00: .0: 07) R(s,, V Bayes, K.A .e
E
[(ss, V Bayes, K.A .0
EL B
where Pi.k and Pi.k denote the distributions of accurate and inaccurate K-step transition prediction a.
Taking the absolute value on both sides and selecting the state that maximizes it yields:
max I Bayess. K.A-,0 (o)
K.A- e (s)l S max
E EawPiN
R(s, V Bayes,+
0) E
R(s, V Bayes,
K σr)
K.A- .0:
(ayes, K,A ()() - K,A
BBaees,+ (s))
+ max
max,
E EaNpE
R(s, K K.A- 0 0r]
Bayes,
E BomPIN
R(s. V Bayes, K.A o
Now focus on Ee~Pix R[ss, V. Bayes,
K.A .0 o The difference in this term comes from the prediction errors, which we use the Kantorovich-Rubinsee inequality to bound:
K.A . .
EE oN R(s, V Bayes,
Inequality (59). Let (X, d) be a Polish metric space, and let μ. v be two probability measures over X. Let f X + R a measurable function that is L-Lipschitz with respect d, i.e.
Lemma E.6 (Kantorovich-Rubinsee
If(x) - f(v) < L d(x,y), Ve,yEX
Then the difference in expectations satisfies
|f - F L- LL
where Wi (J,, is the Wasserstein-1 distance defined by
[ d(x, y) d)(x,v),
Wi ()
inf geM((aa) xxxx
and I(J, v) denotes the of all couplings (joint distributions) with marginals and v.
We first show the perturbation sensitivity. A perturbation in σy changes only the terms involving {
for 2 j. Its impact on the reward-sum Σxn 7t r(s,, ar) is bounded by Σ nt 5 2'-7
1-7
x while its impact on the terminal term K Ky Bayes. (sx) is 2 max, Iy-Bayss each j.
K.A- (s) S 1-7." Hence, for
7 (i((o,)'')
R(s, V Bayes,+ K.A .0:07 o)-R(s, v Bayes,
o')l
5
Wilo,,o
K.A 00:
1=1 1 1-7
1-
1
31

---

Hence, we introduce the distance metric d( inequality simply says [R(s, V Bayes, K.A- 00 σ) - R(s, V Bayes,
Σ ) Under d, the above 1-7
K,A- 0 o') S dio σ'), and iss I-Lipschitz.
By the KantonovichhRubinseinn inequality in Lemma E.6 for two measures Pi.k Pi:k on the product space,
Eg PorPP P.,x
R(s, V
Bayes, K,A- .0 σ)] Pix R(s, V
Bayes, K,A- .0: oi] S ( PurK)
Py, where Pj and P, denote the distribution of oj when prediction is accurate and inaccurate, respectively. One checks:
Since Pi.k- 0 j=1 Pj and Pl.k
K
7
(Pix, PI:x) - Σ
w(1h (P). = Σ
Cj.
1-7 j=1
j=1
Thus, we have:
( V Bayes,
KKA-,c
(s)
5
(1 7) R3 Cj-
(38)
F
Proof of Theorem 5.1
Based on the proposed algorithm, the required sample amounts D1 and D2 satisfy:
D1 N₁ ((AA)
|AT + [S|AA, D2 N2-
(39)
The first term D1 represents the sample complexity of estimating the environment model. The term Ni []|A]( - | )) denotes the learning cost transition kernel P[s'|s, a) for s E S and a E A \ A where |S (1.4] (A-)) denotes the number of sampled entries, and N, denotes the number of times each entry is sampled. Learning the cost function only requires to sample each state action pair with |A| samples. The second term Dj directly equals the number of samples N₂ from the prediction oracle.
We need to determine appropriate values for N1 and N2 to ensure that the estimation error of V Bayes, smaller than 6.
K.A
Let's first analyze the structure of the error. For any state S, the estimate Bayesian value function Bayes, K.A-,s .
(s) satisfies:
K-1
1 (s))
P(do max
Σn 7/
Σ P(sils oox-i..
K.A
JoLKKERK
a)
Buyes:
(40)
where the estimated multi-step transition kernel P(sels, condition: P(si|s, 0u:1-1,01:)) =
(15es,,000-11 a0: 1 satisfies the following recursive
satisfies
Σ Poile
K.
And P(s((5t-1. ((1,0 satisfies:
P(s((s-- = o AT, P(o)))
(41)
We can see that, any term (s a0:-1, (aa) presents finite-sample error only caused by the estimation error of ((s -1 -1- with t' t. And the Bayesian value function estimation
32

---

Bayes, (s) is influenced by the estimation enrors of both P( and P(ar). To highlight K.A-
such dependence, we define an auxiliary value function V(Po: P(e,a), BBayes ,8) as
V(Po, P(s,a)) Bayes,
K-1
max (o(oo max
Σ
?
Σ
Plaa)(stls, a 10))
Jo
K
Σ Pes.a)(xk(l,,, or) B (sx))
,80
(42)
Bayess, Hence, Bayyes, (s) can be denoted by Bayes, (s) v(P(o), P(s' s, a). K.A- s) to show the K.AA
K.A- dependence on estimated probabilities and Bayesian value function. So the true Bayesian value function V Bayess, K.A- (s) V(P(o),, P(s'|s, a). V Bayes,
K.A-.e: s).
Hence, for any state E S, the maximal estimation error can be decomposed by:
max 1 Bayes,+
K. ( (s) V
(s)]
Bayes, KKA-,
=max ((P(ar), P(s'(s,a),
K.A-.e:8). Bayos, -)))))(())) P(s'(s,,)) a), V Bayes, k,))
V(P(o), (s,a),) Bayes, 8) (PP( a), V Bayes, K.d
max
T21
((P()),Pss11s) a), V Bayes.+ K,A- . 8) ((5()),, K.A
Bayes, K.A
+ max
T2a
V(P(o), P(s'|s, ((8)s), V Bayes. 8) (VP()) V Bayes, K.A-
max
T23
Here, T2: captures the bias the estimated Bayesian value function, T22 quantifies the error from imperfect predictiondistribttion estimation, and T23 reflects the error in onestep transition kernel estimation.
The remaining hurdle is to bound the terms T21, Tee and T23, respectively. Lemmas F.I provide the desired bounds as follows:
and
F3
Lemma F.1 (Proof in Appendix F.I). For any state the term T21 satisfies:
Te 7tt max A Bayyess, (s) V-Bayes,* KuA-,
(s)).
(43)
K.A
Lemma F2 (Proof in Appendix
F2
With probability at least - 6, the term T22 satisfies:
log (2/5)/6)
T22 S
(44)
2N₂
Lemma E3 (Proof in Appendix
F.3
With probability at least 6, the term Te3 satisfies:
7(1 ))) (1 7)
log (2K2)S]((AA) - 1/66)
Te3 <
(45)
2N1
Combining the results in Eq. 43
45
yields that, with probability at least -
log log (1()
2012"
Tog(1 M 1 (P (LA 1/8)
Bayes,, (s)= V- Bayaess
(s)
2N2
2N.
KKA-,
K.A
log(4) /8)
log aM((14423155 [S LA 1/8)
2N2
2N
7) - k)
(1-7)²
33

---

74
1ox 1ul214k2|510.4 LA (4-D/0)
Letting
282
are and
2Ng
(1 a)e yields that:
7
(1-1)²
Ni 2log (1 + 4K2|S| |A 1)/6)
(46)
(1 (1 a)?e²
2 2og (4|51/5)
N₂
(47)
(1
Injecting Eq. (46 and 47
into Eq.
(39) and combining the constants yields our result.
F.1
Proof of Lemma
For any fixed state s, the only difference between the two expressions in T21 lies in their terminal Bayesian value function. Hence, by the 7 contraction property of the Bayesian Bellman operator, immediately obtain:
V (P(()), P()lss,), K.A 2,, V(P(o), P(s'(s, V V
max
R-1
P(do 1:K) max a
Σ 7
Σ
max 8o
oLKKEkK
Σ
P(sx (axlssa.. a, V Bayes,
KM- (sx))
8K
P(do (.K) max Σ nd
Σ
1IK EQK
Bayes, +g Σ (
K.A- (sk))
Sx
P(do max
K Σ
P(sx(1, a, (V Bayes, K,A-, (( (ox) - Bayos,
KKA- (sk))
AK
Sx K max
Bayrs,
K,A (s) V Baycs
This concludes proof.
F22 Proof of Lemma F2
We denote X(a,, 8) as the cumulative reward from state with K-step transition prediction o::
K -1
X(a, 5) = max
Σ
P(ssls, a..- + Σ
P(sk(s, a, or) K.A (sx))
SKK
where 5g = 5. Note that, for any state s, P(s ss, a0:-1101:1 and B-Bayes.
KR, (sk), X(or, (or, 8) is bounded
with x(a,s) - Hence, for any state E S, have:
v(P(o), y Bayea,* 3) ((P())) a), v Bayes, K.A .
K.A k. 5)
[ J P(o
1(do
JOLKERK
(P(doi.)) P(d
(48)
Janxeex
To bound the distribution estimation error. We reformulate Eq. 48 into finite-sample Hoeffding form. Specifically, we define X(s) = = Sor 1(d ( and X =X(o', s). Then,
34

---

have:
J (P(do -
Σx (()s).
N2
JoLKEQK
where Eg (x) = (s) for all
Applying the Hoeffding's inequality yields:
No N2 2 - (s) - X(s) )=) 2exp (- 2N
P
2 exp (-2(1 - 7))
(1-7)
where the first inequality holds because 0 v X'(s) S (1-7) for all Letting the RHS probability term
1
& 137 we apply the union bound across all different states E S yields:
T22 max
Σ i- X'(x)
No
xx())xX(s)
X(s)
S
log (2/S1/6)
2(1 7)2
F.3 Proof of Lemma
This proof focuses on bounding how errors from inaccurate single-step transition kernels propagate to the long-term cumulative reward. The key idea is to decompose the total cumulative error into multiple deeeddeendentt components and bound each individually.
Step Decompose the estimation error of P(s doa-1, 11:))
For any estimation P(sels, do:--1, I:)), the term Tes upper bounded by:
K-1
T23 S
max
max
Σ
7
10:1l,,,00-1,0001)0).000 +7 K Σ a
a. ) Bayes,
K,A-, (sx)
Σ
P(sclss Plaals.eorr...0001000..0... +
Σ
V. P(skls, K.A- (sk)
max
8x
K-
< max
P(sels, 1101ls,00
K t7
v K.A- (
Bayes,
*x
K-1
P(stls, P(slls 0101 +7
1 Bayes,
K.A- K.
8K
K-1
Σ 7'
Σ ((ssls,
max
Σ -
K
Σ (P(stls, 001111)002--1,0a))) - -
max 8,0,a
+
max
Σ (P(skls,a, -
K.A (sk)
8,0,a
Ax
Now have
K-1 To3
A'Ar +2 AKK.
(49)
1=1
35

---

Specifically, for any t, initial state the action sequence do:k-1 and prediction 01:K A can be represented as the following product form:
A (Po Po.1 Pi-1:e- Po Po:1 Pt-1a) max:
(50)
where vector Po E |x|S] denotes the initial state with the s-th entry equals and the other entries equal O, max E [R|5]x1 x1 denotes the vector of reward with the s-th entry equals max, r(8, a).
Matrices Pai+1 E R [| and Pas+1 E IR [||ss denote the estimated and real state transition probabilities from state s; state 8141 with given action d;.
Hence, A can be further decomposed by one-step errors as follows:
A (Po Poa
Pi--i:t Po Po:1 Pt-1:t) max
Po (Paa ..... Pi- - Po Poa .... Pt-1:t)
max
Σ i=1
Po
Po
Prs++
k=i PRAA-I 1=0
Pos+i II
Pk,
max
==0
Po
Pas+i
(P:-1a - Pa-
PRAK+1
.V mmax
(51)
i=
j=0
Similarly, the terminal value error Ax k can be decomposed
K = (Po Po.1
PP-11 - Po Po.1 Pt-1::)
V Bayes;+ (s
K.A
Σ (Po.
(II 1-2 Priti (P.-
P1-1
II
k= Phicet)
V
Bayes, K.A
(52)
Ak.i
Combining Eq. 51
52 with Eq.
550
we can decompase total error T23 into:
K
Σ i=1 A K.
T23
+
(53)
Step 2: Bound individual error terms A and Ax:
We can show the concentration behavior of Ar as follows
i-2 Pist1(PP11) P.- II Iike Pkckt1 rmmax)
Po
(II]
1-2 Postt
(Pi-1a Pi-1a)
Po
k=z PE.t max
|=0
(P Pi-1:s)
PKA+1
ret max
(Pi-1- Pa-1st
PRA++ rmaxx satisfies 1 for any t.
where 8 1-1
[R| denotes the expected reward vector from state 8t, which
With N1 samples on each substate-action pair as,a), a), we can directly bound (Pi- - Po-11s) miaa by the Hoeffding's inequality:
P P(A 2 <) < 2xxp (expp-2NM) (-2N1e²),
We need to ensure A 2 for any (s, a) with E and A A thus, take 2 exp
2r
N.
IS MIAAi-A-1 and yields that, with probability least 5,
log (2) [A -1-- ()/5))
A
Vt,
(54)
2N
36

---

Following exactly the same routine, since Bayes,
E [0, I-yb we have that, with probability at
K,A
least 1 - 6, Ax satisfies:
log - - 11/6)
K
S 1 1
Vt,
(55)
2N1
Step 3: Combine the pieces: Now it is enough to bound A. Let the probability 8 in Eq. 54 55 be
K², we have that, with probability at least 1 5,
R
And + +7 Σ im1 K,il
A S
log (2K ( - IA-1)/6)
2N1
log (2K S((A 1A-1)
K
2N1
log (2K?)) (S)((A | 13/5)
Σ K-1
Kg
2N1
1 1-7
$ 71 ))) 7)2
log (2K2)S)(
(A-1)/0)
2N1
This concludes our proof.
G Detailed Model of Wind-Farm Storage Control
We consider windfarm operator that must deliver precommitted power schedule to the grid while managing the uncertainty of realtime wind generation. To avoid costly imbalances, the farm uses a battery storage system: when actual output exceeds the commitment, excess energy is stored; when output falls short, the storage discharges to make up the difference. The operators goal is to minimize cumulative penalty costs for over underdelivery by choosing charge/discharge actions based observed prices, the current stateofcharge, and shortterm forecasts of wind generation.
Below, we formalize this sequential decision problem an MDP.
G.1 MDP Formulation for WindFarm Storage Control
model sequential storage control as an MDP (S,A,,, with:
s; (Pr, A., SoCr), where Pt is the (identical) penalty price, A, is the generation mismatch between generated wind power wi and required wind power w., and SoC, is the storages state of charge.
State:
Action: 0, = (vzt v, denoting charge/discharge amounts subject to of of = O, capacity, and generation constraints.
Transition:
the state transition probabilities satisfy:
P(s++1 st, a.) P(p++1 p.) P(A++1 A.) 1[SoC441 SoC, + + n }.
Reward: the reward function is the negative penalty defined as:
r(0e, 0:) - [pr max(Ax +²,0) ) max("; - -,,
The dynamics of the storage control problem is visualized in Figure
37

---

Required
Generated
Power
Power
We E
We
Power Supply
12
Power Grid
Wind Farm
1
Energy Storage System
Figure 3: Wind Farm Storage Control
5.1
Wish Predictions
5.7
With Predictioas
Expected Rocara
Wishout Predictione
Expected Return
Without Prodictions
5.0
5.6
Imprevment 5.A8%
5.5
2.75%
Predicsion Window Size K
Prediction Window Size K
(a) Performance at Low-Value State
(b) Performance at High-Value Value State
Figure 4: Prediction Helps More in Low- Value States. (a): The expected return at a low-value state increases significantly with prediction horizon K (b): The return a high-value state also improves with K, but the marginal gain much smaller.
G.2 Parameter Settings
In the numerical study, utilized the California aggregate wind power generation dataset from CAISO (60) containing predicted and real wind power generation data with a 5-minute resolution spanning from January 2020 December 2020. The penalty price equals the average electricity price of CASIO [60] with the matching resolution and periods. We set C = 10 kWh, = 0.95. The discretization levels of p, Aw and SoC' are set to be 10, 10, 21, respectively, The action includes 9 discretized choices ranging from charging 2 KW to discharging 2 KWh. The other parameters
follow [6]
H Additional Experiments
In this section, we conduct experiments to validate our theoretical findings. In particular, we demonstrate the advantage of Algorithm for MDPs with transition predictions, compared with model-based RL for classical MDPs. For each experiment, we randomly generate 20 MDPs with [S] and |A| = 5, and present the average performance of both approaches.
We first verify how predictions improve expected returns over standard MDPs, as predicted by our theoretical analysis Section 4.2, Specifically, examine two representative statesone with the lowest value and one with the highest value under the standard MDP value function. Figure ((a) illustrates how incorporating transition predictions enhances the value functions of these two states. Even with a short prediction horizon K 1, we observe notable improvements over the MDP baseline. As K increases, the improvements also increase and tend to converge, which aligns with our theoretical findings. Interestingly, we find that low-value states benefit more from predictions than high-value states. particular, the low-value state, the expected return improves by 5.43% with K = 4. In contrast, the corresponding gain for the high-value state is 2. 2.75%. This is intuitive because predictions help guide the agent toward transitions that reach higher- value regions, offering more substantial gains for states with lower initial value.
38

---

5.5
With Predictions (BOLA)
Value Essitssioon Earor
0.8
Withous Prodictions (Model-based RI.)
Exported Roturn
5.4
0.6
5.3
0.4
6.2-
With Predictions (BOLA)
0.2
5.1
Without Predictions (Optimal))
Without Predictions (Model-boed RI)
20000
4000
5000
1000
2000
3000
5000
Number Samples D
Namber Somples D
(a) Rate of Convergence
(b) Policy Performance
Figure 5: Sample Efficiency of Learning with Predictions. (a): Convergence of (Bayesian) value function estimation error; (b): Policy performance measured by expected return. BOLA with predictions achieves similar convergence and consistently higher performance across varying sample sizes compared to classical model-based RL.
Figure compares the learning efficiency of BOLA with K and standard model-based RL. In with fewer environment samples, indicating its sample efficiency is no worse than vanilla MDPs even with K = 1. In Figure 5(b). observe that BOLA consistently outperforms the model-based RL baseline. Notably, once the number of samples exceeds a small threshold 500, the policy learned via BOLA yields higher expected return than what maximally achievable by any MDP policy without predictive information. This highlights the fundamental advantage of incorporating predictions, which enables agents to surpass the conventional performance ceiling imposed by standard MDP frameworks.
Figure 5()). BOLA exhibits faster decay in the value estimation
I Extension to Splitable State Modeling
Our model can be extended to Markov Decision Processes (MDPs) with splittable states, which naturally generalize settings with predictable trajectories. A key feature of this extension is the decomposition (s )²), where sth E S is the Markovian substate, and s E Sd is the dependent substate, with S 5t x Sd
each state 8 E S into two independent components, represented as a pair
This modeling approach provides natural way to incorporate exogenous or independently fore- castable time seriessuch as demand, weather, or price signalsinto the decision-makee makiing process. Specifically, these predictable sequences can be encoded in the Markovian substate s" allowing the agent to plan adaptively using trajectory-level predictions without enlarging the core Markov state space. The two substates are formally defined below.
Markovian Substates. The first type of substates, denoted by s" is used capture externally evolving states that do not depend on the agent's 's action, with several important real-world examples be discussed in Section I.] State transitions with respect to s" are Markovian such that they only depend on the previous substate. Formally, its transition kernel satisfies
P(s St, az) = ([s""11s")) Vs E S, and E A.
(56)
Dependent Substates. The transition of this substate, denoted by sd, depends on both past substate and action (like in classical MDPs). The state transitions with respect to are
P ( 82, st,02) P (sL+) sf, 1s4+1, E S, and A.
(57)
The Markovian substate and the dependent substate are assumed to have independent transitions, i... for any 8; = (s²" st) E S, A, the overall transition probability P(s++1 8t, az) satisfies P(st+1 St, 0z) = P(s
s."" P( sff az [ Unlike Markovian substates, a dependent sub-
state depends on both past action and substate, making harder to predict. Next, we introduce the MDPs considered in this work.
prediction model of the prediction-augmente
WWithout the predictive model P, the MDP model with Markovian and dependent substates is essentially special case of the factored MDP 62
39

---

Let P = AK,A", ..) denote the prediction model that provides the predictions to the future states, where is the length of the prediction window, A S A is a predictable action set, and denotes the transition prediction. Specifically, given 1 = 0, K, 2K, ..... let 8, (s," sg) be the current state of the environment. Before taking actions, the agent receives a probablistic prediction of the transition o = (0 , .K) for the next K steps, where different Ø% s are independent and sampled from an unknown probability distribution P(ox). For each & 21, K}. on captures the transitions from state Sc+k-1 state St+K, and is of the form 0g (o og),, where o% E [0, |||š|x[š] is an [S] x |S|-dimensional matrix representing the transition prediction of the Markovian substate and of [0, 1|| is [S] AA by [S] matrix representing the transition prediction of the dependent substate. Given a prediction o = (o" " o²). the transition probabilities
satisfy the following.
Fully Predictable Markovian Substates. For Markovian substates, we have
P (st41 88"" 0+41) o't1 (sy" $142),
(58)
where T' 16+1) is the (s.", 1 entry of the matrix o²
Partially Predictable Dependent Substates. We consider general setting that allows for partially predictable states and actions. In particular, given set of predictable actions AT, we have
P 16 ar o441) { (0ft1l(9,,a)) s(+1);
if A
(59)
(st (..
if & AT.
where of ((5), a.), 1) denotes the entry located in the (s a -tth row and the 1 column of the matrix 0f+1-
L11 Illustrative Examples
Extending classic MDPs, the prediction-augmentee MDP model introduced in Section 2.1 naturally fits real-world scenarios with Markovian states. Examples include stock prices in stock market trading [8] outdoor temperatures building thermal control [63] wind speeds in unmanned aerial vehicle (UAV) control [64], electricity prices in storage control 665 and grid electricity demands in power system economic dispatch [66].
Table 1: Real- examples that instantiate the prediction-auggmentt MDP model (see Section
Markovian Substate
Dependent Substate
Action
predictable
partially predictable
Stock Investment
Buy/sell stocks
Stock price
N/A
VPP Operation
Energy consumption
Renewable generation N/A
Electricity price Indoor/outside temperature Battery SoC UAV position/attitude
Building HVAC Control
Hcating/cooling
Storage Control
Charge/discharge
Energy mismatch
UAV Control
DC motor force
Wind direction/speed
Stock Investment. Consider the stock investment problem for a retail investor [ The market stock prices action-independen unknown time series if the trading volume is high. With relatively accurate stock price predictions, the revenue from the investment can be significantly improved.
Virtual Power Plant operation. Another example is the virtual power plant (VPP) operation problem [67], where the agent sequentially decides the energy consumption of large-scale VPP to minimize total electricity costs. In this scenario, the renewable generation within the VPP depends solely on its previous state and can be effectively predicted. Conversely, the real-time electricity price in the electricity market depends on both its previous state and the VPP's energy consumption actions. The electricity price is partially predictable: when the VPP's energy consumption is low, its impact on market prices is minimal and predictable. However, when energy consumption is very high, the VPP becomes a market price-maked maker, causing market prices to fluctuate wildly and become unpredictable.
Building HVAC Control. Besides, many online decision-making problems related to sustainability exhibit predictable structures aligning with our model. For example, the control of heating, ventila- tion, and air conditioning (HVAC) systems relies temperature predictions (68), battery storage
40

---

management depends on energy predictions 699. Similar predictable components exist for the task of controlling battery storage systems.
In Table | we summarize the key features of real-world scenarios with Markovian substates and partially predictable dependent substates, which present challenges for modeling with classic MDPs.
41


Reviews:
[{"review_id": "PeUCjMTQCZ", "reviewer": "Reviewer_DyeW", "summary": "The authors study the setting of RL in MDPs where additional (imperfect) predictions of multi-step predictions are given. They formalize a setting for MDPs with multi-step transition predictions. They define the *Bayesian value function* for prediction-aware decision-making, and work out the Bellman optimality equations for this value function. Towards analyzing the *value* of imperfect predictions, they give a bound on the difference between the Bayesian (imperfect) value function and the value function given perfect information. They lastly introduce a tabular model-based algorithm (BOLA) that estimates a model and incorporates predictions to compute the optimal Bayesian policy, with sample complexity guarantees. Experiments are run.", "questions": "See above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This is an interesting paper on incorporating imperfect predictions into the RL problem. The formalism is clean, and the Bayesian value function approach feels like the correct solution concept. The theoretical results, while restricted to the tabular setting, are clean and neatly demonstrate the value of imperfect predictions. I am not aware of related work that overlaps too closely with this one. The writing is polished and brings out the key intuitions. I have skimmed the proofs and they seem correct. The experimental results on wind-farm storage are cool. \n\nI have no major complaints, and just some minor points of confusion that I would appreciate some clarification on:\n1. Equation 1 should be $P(s' \\mid s,a,\\sigma^\\star_k)$?\n2. What does it mean to condition on $\\sigma$ when $\\sigma = \\sigma^\\star + \\varepsilon$ is imperfect (for example, in the expression of Equation 5.) Do we treat $\\sigma$ here as $\\sigma^\\star$, ignoring the imperfection? In general it's not crystal clear what it means to condition on $\\sigma$  (e.g. even in the value function definition of Equation 3). Can the authors be more formal about the probability kernels involved?\n3. The current algorithm 1 samples transitions and predictions and does a plug-in estimator to learn \\hat{V}^{Bayes}_{\\varepsilon} that approximates V^{Bayes}_{\\varpesilon}. Intuition suggests that sampling more $\\sigma$ variables could eventually give us a good approximation to $\\sigma^\\star$ (by concentration and since $\\sigma = \\sigma^\\star + \\varepsilon$) and we should thus be learning V^{Bayes}_0. What is happening here?\n\nTwo additional questions:\n1. It feels like the BOLA algorithm can be extended to settings beyond the tabular one. At a high level the two components involve: estimating $P(\\sigma)$, and estimating the rest of the model ($r$ and $P(s' | s,a)$). Can we indeed say that this methodology works in any setting where the above quantities are learnable?\n2. There is a trade-off here between the statistical and computational costs of learning transitions over $K$ steps (which gets more expensive due to an exponential scaling in $K$) and the quality of the learned policy (since more steps gives a better policy). Is there any interesting way to adaptively choose $K$ to balance these considerations?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive and thoughtful review of our paper. We greatly appreciate your recognition regarding our novelty, theoretical results, experiments, and writing. Below, we address your minor points of confusion:\n\n**Q1. Equation 1 should be $P(s'|s,a,\\sigma_k^*)$?**\n\n**Response:** Yes, that is correct. Thank you for catching this typo!\n\n**Q2. What does it mean to condition on $\\sigma$ when $\\sigma = {\\sigma}^* +\\epsilon$ is imperfect (for example, in the expression of Equation 5.) Do we treat $\\sigma$ here as $\\sigma^*$, ignoring the imperfection? In general it's not crystal clear what it means to condition on $\\sigma$ (e.g. even in the value function definition of Equation 3). Can the authors be more formal about the probability kernels involved?**\n\n**Response:** Thank you for raising this point. In our framework, we condition on the imperfect transition prediction $\\sigma$, not the perfect one ${\\sigma}^* $. Specifically, throughout the paper (including in Equations 3 and 5), we use the imperfect transition probabilities defined as $P(s'|s,a,\\sigma_k) = \\sigma_k((s,a),s')$. This ensures that the agent makes decisions based solely on the imperfect predictions available to it (the agent never observes the perfect transitions $\\sigma^*$). We agree that the confusion may have arisen due to the typo in Equation 1.\n\n**Q3. The current algorithm 1 samples transitions and predictions and does a plug-in estimator to learn hat{V}^{Bayes}_epsilon that approximates V^{Bayes}_epsilon. Intuition suggests that sampling more variables could eventually give us a good approximation to accurate transition prediction, because by concentration, $\\sigma = \\sigma^{*} + \\epsilon$, and we should thus be learning unbiased value function. What is happening here?**\n\n**Response:**  Thank you for the question. In our approach, we sample imperfect transition predictions $\\sigma$ to approximate their distribution $f_{\\sigma}$. This distribution reflects forecast errors of size $\\epsilon$, and is different from the true distribution $f_*$ over accurate transitions $\\sigma^*$. \n\nImportantly, any accurate prediction $\\sigma^*$ is a deterministic (binary) transition matrix, where each row is a one-hot vector. In contrast, the noisy forecasts $\\sigma$ may contain non-binary probabilities (like 0.1, 0.9) due to errors. Thus, even with many samples from $f_{\\sigma}$, we do not recover the distribution of accurate predictions. Hence, the learned Bayesian value function will converge, but to a biased solution. This is different from using transition samples to recover the accurate transition kernel using empirical average.\n\n**Two additional questions:**\n\n\n**Q4. It feels like the BOLA algorithm can be extended to settings beyond the tabular one. At a high level the two components involve: estimating $P(\\sigma)$, and estimating the rest of the model (r and $P(\\sigma)$). Can we indeed say that this methodology works in any setting where the above quantities are learnable?**\n\n**Response:**  Yes, the two-stage BOLA algorithm can indeed be extended beyond the tabular setting, as long as $P(\\sigma)$ and other relevant system models (such as $r$ and $P(\\sigma)$) are learnable. To extend to continuous state settings, we can use function approximation (e.g., neural networks) to learn the continuous Bayesian value function $V^{\\text{Bayes}}(s)$. This can be done via fitted value iteration, leveraging the structural similarity between our Bayesian Bellman equation and that of standard MDPs. \n\nAt a high level, BOLA remains applicable in more general settings because it preserves the fundamental notions of value functions and optimal policies shared with classical MDPs.\n\n**Q5. There is a trade-off here between the statistical and computational costs of learning transitions over K steps (which gets more expensive due to an exponential scaling in K) and the quality of the learned policy (since more steps gives a better policy). Is there any interesting way to adaptively choose K to balance these considerations?**\n\n**Response:**  This is an excellent question. As shown by both Theorem 4.1 and our experiments, the marginal benefit of extending the prediction horizon $K$ decreases exponentially, while the computational cost increases exponentially. To handle this trade-off, a simple yet effective strategy is to incrementally increase $K$ (e.g., starting from $K=1$) until the computational budget is met. Since the total trial cost $\\sum_{k=1}^{K} D^k \\approx D^K$ (where $D^k$ is the computational cost with prediction window $k$), this approach naturally identifies the optimal $K$ that balances reward performance and computational cost, and is nearly optimal in terms of total trial cost. In practice, this greedy search often achieves a good performance."}, {"review_id": "6keoh2wEAC", "reviewer": "Reviewer_6EBS", "summary": "The paper studies the problem where the RL agent is provided with a K-length sequence of forecasts about the future evolution of the state (dynamics). To deal with the tractability of state augmentation, a Bayesian value function approach called BOLA is derived, which marginalizes out the forecast, avoiding the exponential blowup in compute. Analysis of the Bellman-Jensen gap provides an interpretable performance gap of BOLA in terms of horizon K, prediction error of the forecast, and partial action predictability, and sample complexity bounds are also derived. Analysis of the method on wind farm storage control show significant cost savings with longer forecasts, and some robustness to imprecise forecasting.", "questions": "1. Can other assumptions on forecasts, like parametric transition distributions, be accommodated within the current framework, perhaps as part of a broad spectrum of assumptions with parametric model on one extreme and full transition matrix forecast on the other?\n\n2. Does the framework support continuous or large state spaces (perhaps connected to question 1 above)? What modifications to BOLA will be needed to avoid the blowup in compute with value iteration?", "limitations": "I think more discussion should be provided about scalability and how to avoid the blowup in compute for larger state/action spaces. Additional experimentation would be quite useful to assess how well BOLA works across different types of problems.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. The approach of embedding forecasts into the dynamic programming framework is quite elegant, and the Bellman equation shows how the forecast is utilized in downstream calculation. \n2. The paper presents strong theoretical results in terms of performance gaps and sample efficiency.\n3. The empirical evaluation is simple but demonstrates the use case and advantages quite clearly.\n\nWeaknesses and suggestions: \n\n1. In many practical settings, it may not be ideal to forecast each component of the transition matrix independently as described by sigma_k. Instead, many domain-specific models, such as the financial forecasting example mentioned in the preamble as well as many OR-specific problems like inventory control, queueing, etc. could often be parametric (i.e. Black-Scholes model). Other forecasts could perhaps be extrapolated from data using a neural network or other parametric model. It is not clear whether the current framework supports such use cases or how to adapt it.\n\n2. The analysis on the Bellman-Jensen gap is quite similar to the work of Mercier et. al. [1] on anticipatory sampling, which has been widely known in stochastic planning. It might be good to cite this (and related) work, and ideally discuss the main limitations of their analysis on the so-called \"anticipatory gap\" and why it is difficult to apply directly towards forecasts.\n\n3. (10)-(11) and value iteration might work well for small state/action/forecast spaces, but I don't think this will scale to problems of significant size. While I understand the core of the paper is theory-focused, an experiment on a larger version of the current problem with function approximation could significantly strengthen the paper's empirical evaluation. I understand that (6) might be applied within an existing model-based (deep) RL algorithm, but it might be good to discuss any practical limitations or necessary modifications to the current algorithm to scale up the current approach.\n\n[1] Mercier, Luc, and Pascal Van Hentenryck. \"Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Integer Programs.\" IJCAI. 2007.", "was_revised": true, "final_justification": "- Most of my concerns were centred on addressing the generality and necessary assumptions of the proposed framework. These issues have been clarified with examples in the rebuttal.\n- Another aspect was clarification of the novelty of the theory in relation to prior work which was addressed well by the authors.\n- The error regarding sample efficiency mentioned by another reviewer was also clarified.\n- I have therefore decided to maintain my current score of Accept because the paper is technically strong and innovative.", "rebuttal": "We thank the reviewer for the detailed and thoughtful review. We're encouraged by your positive evaluation of our theoretical contributions and the clarity of our framework. We also appreciate your constructive suggestions. We address each of these points below.\n\n\n**Q1. Can other assumptions on forecasts, like parametric transition distributions, be accommodated within the current framework, perhaps as part of a broad spectrum of assumptions with parametric model on one extreme and full transition matrix forecast on the other?**\n\n\n**Response:**  Thank you for raising this insightful point. Our framework is flexible enough to accommodate a wide range of forecasting assumptions from full transition matrices to **parametric models**. As long as the forecast can be expressed in terms of (or mapped to) some transition probabilities, either explicitly or via a compact parameterization, it can be seamlessly integrated into our approach.\n\n* As the reviewer suggests, many real-world systems such as queueing and inventory control exhibit structured dynamics that can be characterized using only a few parameters. For example, in the classic discrete-time M/M/1 queue, the entire transition matrix can be fully determined by forecasting just two parameters: the arrival probability $\\lambda$ and the service probability $\\mu$. This allows us to compute all probabilities like $P(s_{t+1} = j+1 \\mid s_t = j) = \\lambda(1 - \\mu)$ (i.e., an arrival occurs but no service), without needing to explicitly give the full matrix.\n\n* Moreover, the required forecast model can be incomplete. our framework also supports **partial forecasts** with predictable action set $\\mathcal{A}^-$, where only a subset of transitions can be predicted. \n\n**Q2. Does the framework support continuous or large state spaces (perhaps connected to question 1 above)? What modifications to BOLA will be needed to avoid the blowup in compute with value iteration?**\n\n\n**Response:**   Yes, our framework can indeed be extended to large or even continuous state settings. The key is to learn the high-dimensional Bayesian value function $V^{{Bayes}}(s)$. To achieve this, we can use function approximation (e.g., neural networks) to learn $V^{Bayes}(s)$ via fitted value iteration. It is achievable because the Bayesian value function $V^{\\text{Bayes}}(s)$ has the same dimensionality and quite similar definition (only different in prediction $\\sigma$) of value function in standard MDPs. With the learned Bayesian value function, we can calculate the optimal policy follow a similar routine.\n\nAt a high level, our method remains applicable in more general settings because it preserves similar fundamental notions of Bellman optimality condition and optimal policies shared with classical MDPs.\n\n**Q3. The analysis on the Bellman-Jensen gap seems similar to the work of Mercier et. al. [1] on anticipatory sampling, which has been widely known in stochastic planning. It might be good to cite this (and related) work, and ideally discuss the main limitations of their analysis on the so-called \"anticipatory gap\" and why it is difficult to apply directly towards forecasts.**\n\n**Response:** Thank you for the helpful suggestion. The anticipatory gap studied by Mercier et al. [1] is indeed closely related to our Bellman-Jensen gap when the prediction window is limited to $K=1$. However, our setting is significantly more general and challenging, in several key ways:\n\n* We allow arbitrary prediction windows $K \\geq 1$;\n* We consider maximizing infinite-horizon cumulative reward objectives, not just terminal rewards;\n* We allow for incomplete predictions regarding subset $\\mathcal{A}^-$ and prediction errors.\n\nMoreover, the analysis of the gap in [1] is primarily **case-based and lacks general theoretical characterization**. As acknowledged by the authors themselves, “We are currently applying this method on more complex problems but proofs quickly become very cumbersome. As an alternative, we discuss another, empirical way to argue that the GAG of a problem is small”, they resort to empirical justification rather than formal analysis.\n\n\nIn contrast, our work provides a **general, explicit bound on the Bellman-Jensen gap for arbitrary MDPs and any prediction window $K$**. A key technical challenge lies in characterizing the recursive sum of coupled Jensen gaps across multi-step transitions. To address this, we introduce a novel dyadic horizon decomposition and a variance-based analysis (both in Appendix E) that enables us to decouple the multi-step dependencies in the Bellman operator.\n\nAnalytically quantifying the value of prediction is a long-standing challenge, especially for unstructured problems. Most existing results rely on strong assumptions—e.g., linear dynamics as in LQR settings [2]. To our knowledge, our work provides the first general theoretical analysis of the value of prediction in MDPs with arbitrary forecast lengths and incomplete information.\n\n>[1] Mercier, Luc, and Pascal Van Hentenryck. \"Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Integer Programs.\" IJCAI. 2007.  \n>[2] Yu, C., Shi, G., Chung, S.-J., Yue, Y., and Wierman, A. (2021). The power of predictions in online control. Advances in Neural Information Processing Systems, 33:1994–2004"}, {"review_id": "0Qxu7aobmX", "reviewer": "Reviewer_jBsU", "summary": "This paper studies a reinforcement learning setting where the agent has access to an oracle of imperfect predictions. The text introduces the framework of Bayesian value functions and the prediction-aware optimal policy as well as a corresponding Bellman operator. Then, it provides a theoretical analysis of the effects of perfect predictions before a tabular algorithm BOLA for prediction-aware RL is presented. A theoretical analysis on the sample complexity is provided as well as a set of numerical studies.", "questions": "Q1: In the numerical study, can you elaborate on what happens in the case of no predictions? Does the Bayes Bellman operator not capture the regular Bellman operator?\n\nQ2: Can you elaborate why the sample complexity of the algorithm would not have an O(|S||A|) dependence?", "limitations": "The limitations are outlined in section 7, however I do think it would be beneficiall to add a discussion of the oracle assumption and what challenges it adds.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n**Motivation**\n* Finding new frameworks that allow us to leverage future forecasts and predictions is quite relevant in current times where foundational models exist. As such, I find this a very interesting problem to study.\n\n**Clarity**  \n* The text is well written, well structured and easy to follow\n* The theoretical statements have in-depth intuitive explanations that make it easy to understand the relevant parts of the resulting bounds.\n* The structure of results has a nice build-up that starts with intuition relating the framework to traditional MDPs, to studying perfect predictions before the final result is presented. This makes is quite easy to follow what results are being presented and why.\n\n**Related Work**\n* I’m not very familiar with the Bayesian side of RL but the treatment of related work is relatively extensive\n\n**Novelty**  \n* I’m not aware of any work that attempts to provide similar results and I believe this may be an interesting novel contribution for the community.\n\n**Claims and Evidence**\n* The first claim is that a new low-dimensional value Bayesian value function that leverages multi-step predictions is introduced which is supported by section 3.\n* The second claim is the novel decomposition into local Jensen gaps that allows to learn a policy in the proposed setting without much overhead. This claim is also \n* The claim that BOLA circumvents the exponential blow-up from state augmentation is supported by the algorithms sample complexity.\n\n**Experimental Design and Analyses**\n* The experimental study highlights that the theoretical results hold in practice.\n\n__________ \n**Neutral Points**\n\n**Minor points**\n* It might make sense for clarity purposes to rename the sub-gaussian variable since it shares notation with the predictions.\n__________ \n\n**Weaknesses**\n\n**Experimental Design and Analyses**\n\n**Claims and Evidence**\n* I’m a bit confused about the sample complexity D1. D1 is a function of |S|(|A| - |A-|) but also from what the text states |S||A|. The classical O(|S||A|) state dependence is still in D1. Even if the first term vanishes, the second term still exists. Thus I’m unsure if the claim that BOLA provides better sample complexity guarantees than regular model-based RL algorithms is correct. I will ask for clarification. Maybe this is meant to say there is no epsilon scaling on that part of the dependence?\n\n**Theoretical Results**\n* A fundamental question is whether or not these algorithms provide any benefits over traditional RL algorithms. I think this answer could be a bit stronger. In the end, the upper bound in the worst case must still depend on the state-action space size which in practice is quite limiting.\n* The analysis and limitations ignore the cost of obtaining the prediction oracle. In the worst case, it seems one may have to learn a full model of the transition dynamics to obtain such a model before the algorithm can be run. In this case, it seems this type of algorithm would be more expensive than a traditional RL algorithm.\n\n__________ \n\n**Summary**\n\nOverall, I think this is a nice paper. While there are some drawbacks to the theoretical assumptions, I understand that this is a first result on this type of algorithm. These initial results follow the structure of many initial results in the RL community that later led to interesting practical findings. I’m a bit worried about the sample complexity statement but if my questions can be answered, I am happy to recommend acceptance.", "was_revised": true, "final_justification": "This paper presents an interesting view on combining RL with forecasts and I think the community will likely benefit from learning about this contribution.", "rebuttal": "Thank you for the thoughtful and encouraging review. We appreciate your positive comments on the motivation, clarity, novelty, and theoretical contributions of the work. Below, we address your questions in detail.\n\n**Q1. I’m a bit confused about the sample complexity D1. D1 is a function of |S|(|A| - |A-|) but also from what the text states |S||A|. The classical O(|S| |A|) state dependence is still in D1. Even if the first term vanishes, the second term still exists. Thus I’m unsure if the claim that BOLA provides better sample complexity guarantees than regular model-based RL algorithms is correct. I will ask for clarification. Maybe this is meant to say there is no epsilon scaling on that part of the dependence?**\n\n\n**Response:** Thank you for pointing this out, and we appreciate the opportunity to clarify. You are absolutely right: our claim refers specifically to the $\\epsilon$ scaling in the sample complexity. The classical minimax sample complexity for model-based RL is $\\mathcal{O}(|S||A|\\epsilon^{-2})$ [1], with model-free methods typically requiring even more samples. In contrast, our term $D_1$ has a lower complexity $\\mathcal{O}(|S|(|A| - |A^{-}|)\\epsilon^{-2} + |S||A|)$. The key distinction is that only the first term in $D_1$ depends on $\\epsilon^{-2}$, while the second term, $\\mathcal{O}(|S||A|)$, does not scale with $\\epsilon$ and is often negligible. \nWe will make this clarification explicit in the revision to avoid any confusion.\n\n>[1] Azar, M. G., Munos, R., & Kappen, H. (2012). On the Sample Complexity of Reinforcement Learning with a Generative Model. In International Conference on Machine Learning.\n\n**Q2. A fundamental question is whether or not these algorithms provide any benefits over traditional RL algorithms. I think this answer could be a bit stronger. In the end, the upper bound in the worst case must still depend on the state-action space size which in practice is quite limiting.**\n\n**Response:**  Yes, our algorithm can be more sample-efficient, especially when predictions are available (as discussed in our response to Q1). \n\n* **Theoretically, our sample complexity is $\\mathcal{O}(|\\mathcal{S}|(|\\mathcal{A}| - |\\mathcal{A}^-|)\\epsilon^{-2})$, which is lower than the minimax sample complexity $\\mathcal{O}(|\\mathcal{S}||\\mathcal{A}|\\epsilon^{-2})$ in tabular MDPs [1]**. Intuitively, for actions $a \\in \\mathcal{A}^-$, transition dynamics are directly obtained from predictions $\\sigma$, so increasing $|\\mathcal{A}^-|$ leads to improved efficiency. The $|\\mathcal{S}||\\mathcal{A}|$ scaling can not be avoided in statistical theory (because we at least need to sample all the reward function $r(s,a)$), but our framework can avoid the $|\\mathcal{S}||\\mathcal{A}|\\epsilon^{-2}$ scaling of standard MDPs.\n\n>[1] Azar, M. G., Munos, R., & Kappen, H. (2012). On the Sample Complexity of Reinforcement Learning with a Generative Model. In International Conference on Machine Learning.\n\n* **Empirically, our framework scales naturally to large or continuous state spaces using function approximation, similar to how standard MDPs overcome the sample complexity dependence on state-action space size.** The key idea is to approximate the Bayesian value function $V^{\\text{Bayes}}(s)$ using function approximation (e.g., neural networks), trained via fitted value iteration. This is feasible because $V^{\\text{Bayes}}(s)$ shares the same dimensionality and Bellman structure as the standard value function, with the only difference being the use of prediction $\\sigma$. Once $V^{\\text{Bayes}}(s)$ is learned, the optimal policy can be extracted via standard planning techniques.  We provide an example of realizing the algorithm in our setting as follows:\n\n\nConsider the case where the forecast horizon $K=1$. Given a dataset of transitions $\\mathcal{D} = {(s_i, a_i, r_i, s_i')}$ and a dataset of one-step predictions $\\mathcal{D}\\sigma$, we aim to learn a Bayesian value function $\\hat{V}^{\\text{Bayes}}_\\theta(s)$ using fitted value iteration:\n\n* Step1: Sample a batch of states $s$ from $\\mathcal{D}$\n* Step 2: For each $s$, compute the Bellman target:\n$y(s) = \\mathbb{E}{\\sigma \\sim \\mathcal{D}\\sigma} \\left[ \\max_{a \\in \\mathcal{A}} \\left( r(s, a) + \\gamma \\cdot \\frac{1}{M} \\sum_{m=1}^M V_\\theta(s^{(m,\\sigma)}) \\right) \\right]$,\n\nwhere $s^{(m,\\sigma)} \\sim \\hat{P}\\phi(\\cdot \\mid s, a, \\sigma)$ are next states sampled from a learned transition model $\\hat{P}\\phi$ using forecast $\\sigma$.\n* Step 3: Update parameter $\\theta$ of the value function by minimizing the squared error $\\min_\\theta \\sum_{s \\in \\text{batch}} \\left(V_\\theta(s) - y(s)\\right)^2$\n* Step 4: Repeat from Steps 2-3 until convergence.\n\n\n\n\n**Q3. The analysis and limitations ignore the cost of obtaining the prediction oracle. In the worst case, it seems one may have to learn a full model of the transition dynamics to obtain such a model before the algorithm can be run. In this case, it seems this type of algorithm would be more expensive than a traditional RL algorithm.**\n\n\n**Response:**  Thank you for raising this important point. In our analysis, we do not assume that prediction oracles are free; rather, we treat querying the oracle as incurring the same per-sample cost as interacting with the environment (e.g., one sample for each $\\sigma$). \n\n* In many practical settings, such as electricity markets, weather systems, or queueing networks, forecast information is externally available through domain-specific models and does not need to be learned by the RL agent. Moreover, generating such forecasts is often much less costly than estimating full transition dynamics via trial-based exploration. For instance, in a discrete-time M/M/1 queue, forecasting only the arrival probability $\\lambda$ and service probability $\\mu$ is sufficient to compute all transition probabilities analytically, such as $P(s_{t+1} = j+1 \\mid s_t = j) = \\lambda(1 - \\mu)$ (i.e., an arrival occurs but no service).\n\n* Our framework is also designed to flexibly support **partial prediction** (see Section 2.1), where only a subset of actions $\\mathcal{A}^-$ are associated with transition forecasts. In this case, the agent only needs to learn the dynamics for the remaining actions $\\mathcal{A} \\setminus \\mathcal{A}^-$, and we provide corresponding sample complexity guarantees.\n\n* Even under the most conservative assumption where the prediction $\\sigma$ must be queried for each transition entry (e.g., $|S||\\mathcal{A}^-|$ samples for each $\\sigma$), the total cost including both oracle queries ($D_2 = \\mathcal{O}(|\\mathcal{S}||\\mathcal{A}^-|\\epsilon^{-2})$) and environment samples ($D_1 = \\mathcal{O}(|\\mathcal{S}|(|\\mathcal{A}| - |\\mathcal{A}^-|)\\epsilon^{-2})$) still matches the standard minimax sample complexity of model-based RL: $\\mathcal{O}(|\\mathcal{S}||\\mathcal{A}|\\epsilon^{-2})$. Thus, our framework is never worse than classical MDPs in theory, and it can provide substantial benefits when more forecasts are available in practice.\n\n\n\n**Minor: It might make sense for clarity purposes to rename the sub-gaussian variable since it shares notation with the predictions.**\n\n**Response:**  Thanks for the suggestion, we will change the notation for clarity.\n\n\n**Again, thank you for your thoughtful review. We would be happy to further clarify any points if there are remaining questions during the discussion.**"}]

Author rebuttal:

Meta-review: The paper studies whether (and how) future-state multistep predictions can be integrated into an RL process and how this impacts the overall performance. 

The question studied in the paper is fundamental in nature and particularly significant in domains where (multi-step) world models are available. The contribution of the paper is shading light on this question is extensive: from the formalization of the question, to development of an algorithm and its theoretical properties, all the way to empirical validation in a small-scale but practically relevant problem (wind-farm storage control task). While the reviewers pointed out some weaknesses (e.g., validity of assumptions, limitation to tabular MDPs for the theory, comparison with existing literature, and small-scale experiments), these were clearly out-weighted by the significance of the topic and the novelty of the results, which position the paper to have the potential to inspire further developments in this direction. Based on this, there was a clear consensus towards acceptance.

I would still encourage the authors to properly integrate the rebuttal (e.g., comparison to Mercier et. al., clarification of the theoretical results) and expand as much as possible on the path towards practical algorithms based on BOLA.
Decision: Accept (spotlight)