Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information
Authors: Ziyi Zhang
Yorie Nakahira
Guannan Qu
Venue: Accepted by TMLR ()

Abstract: Policy design in non-stationary Markov Decision Processes (MDPs) is inherently challenging due to the complexities introduced by time-varying system transition and reward, which make it difficult for learners to determine the optimal actions for maximizing cumulative future rewards. Fortunately, in many practical applications, such as energy systems, look-ahead predictions are available, including forecasts for renewable energy generation and demand. In this paper, we leverage these look-ahead predictions and propose an algorithm designed to achieve low regret in non-stationary MDPs by incorporating such predictions. Our theoretical analysis demonstrates that, under certain assumptions, the regret decreases exponentially as the look-ahead window expands. When the system prediction is subject to error, the regret does not explode even if the prediction error grows sub-exponentially as a function of the prediction horizon. We validate our approach through simulations and confirm its efficacy in non-stationary environments.

Published in Transactions on Machine Learning Research (07/2025)
Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information
Ziyi Zhang
siyishon Brsirhhoanddd
Deportment of Electrical and Computer Engineering
Carnegie Mellon Universily
Yoric Nakahira
yorie@temaacomm edu
Deportment Electrical and Computer Engineering Carnegie Mellon University
Guannan Qu
gquSandrew. crvu edu
Department of Electrical and Computer Engineering Carnegie Mellon University
Reviewed on OpenReview: https: openreviee. net/ forum? id- 7ub3
Abstract
Policy design in non-stationary Markov Decision Processes (MDPs) is inherently challenging due to the complexities introduced by time-varying system transition and reward, which make it difficult for learners to determine the optimal actions for maximizing cumulative future rewards. Fortunately, in many practical applications, such as energy systems, look- ahead predictions are available, including Torecasts for renewable energy generation and demand. In this paper, we leverage these look-ahead predictions and propose an algorithm designed to achieve low regret in non-stationary MDPs by incorporating such predictions. Our theoretical analysis demonstrates that, under certain assumptions, the regret decreases exponentially as the look-ahead window expands. When the system prediction is subject to error, the regret does not explode even if the prediction error grows sub-exponentially as a function of the prediction horizon. We validate our approach through simulations and confirm ils efficacy in non-stationary environments.
1 Introduction
Policy design of non-stationary Markov Decision Processes (MDPs) has always been challenging due the timo-varying system dynamics and rewards, the learner usually suffers from uncertainties of future rewards and transitions. Fortunately, exogenous predictions are available in many applications. For example, in energy systems, look-ahead information is available in the form of renewable generation forecasts and demand forecasts (Amin et al.) 2019). It is intuitive to design an algorithm that controls the energy system by utilizing that information to concentrate energy usage in the time frame with the lowest energy price and lower the overall energy cost. To give another example, smart servers can make predictions of future internet traffic from historical data (Katris & Daskalaki (015).. Given that the dispatcher trics to minimize the average waiting time of all tasks, if there is only light. traffic, the average waiting time will be most reduced by only using the fastest server. If the dispatcher forecasts that there will be heavy traffic in the future, all servers should work to reduce the length of the queue.
However, although policy adaptation in a Lime-varying environment has been extensively studied (Auer el al. 2008 Richards et al., 2021 Zhang et al.) 2024 Gajane et al.) 2018), they do not typically take advantage of exogenous predictions. One branch of work focuses on adaptation and relics on periodic reset of the controller (Auer et al.) 2008) or prior knowledge of the environment (Richards al. 2021 Zhang et al., 2024). However, prior knowledge of the environment is usually difficult to obtain, and periodically resetting

---

Published in Transactions on Machine Learning Research (07/2025)
the controller generates a linear regret. Another branch of work focuses on predicting the future based on past data. As past data can not accurately reflect. the system in the future, they often need previously specified (small) variation budget (Merlis, 2024 Lee et al.) 2024 Gajane et al. 2018 Padakandla et al.) 2020) to achiove sublinear regret. Overall, cxisting works demonstrate significant challenges in achicving sublinear regret under general non-stationary MDP on a single trajectory without assumptions on sublinear variation budget.
Most of the above algorithms do not utilize exogenous predictions widely available in applications. With the availability of predictions, it is natural to reason that if we could obtain accurate predictions of the entire future, we would casily obtain the optimal policy (thus zero regret). Furthermore, even if accurate predictions of the full future are not possible, it is reasonable to expect that these imperfect predictions can help the decision maker. Given these intuitions, we ask the question: with potentially imperfect prediction of transition kernel and reward function into the future, can we design an algorithm that leverages the prediction obtain a sublinear regret with reasonable length and accuracy of the prediction?
Contribution: We propose an algorithm, Model Predictive Dynamical Programming (MPDP), that utilizes predictions of transitional probability and reward function to minimize the dynamic regret under the setting of single trajectory. We utilize the look-ahead information and the spen semi-norm to show that, under certain assumptions, the regret decays exponentially with the length of the prediction horizon when the prediction is error-less. Specifically, we show that MPDP achieves a regret of O(T)1k//)))) where T is the time horizon, & is the prediction horizon, 7 < 1, and J, D are constants determined by the properties of the MDP. Even when the system prediction is subject to error, we demonstrate that the regret does not explode if the growth rate of error is subexponential as function of the prediction horizon. To the best of our knowledge, this paper is the first paper that explores the use of exogenous predictions in non-stationary MDP without prior knowledge and proposes an algorithm with decaying regret as the prediction horizon increases and the prediction error descreases.
The key technique underlying our result for sublinear regret is the contraction of the Bellman operator under the span semi-norm. We show that the value function of MPDP converges to the optimal value function exponentially in the span semi-norm under certain assumptions, which leads to the overall sublinear regret. Our result serves as the first step towards future applications of model predictive control in non-stationary RL with no prior information.
1.1 Related Works
Non-stationary reinforcement learning Many works have been done for reinforcement learning (RL) in non-stationary environment, in which a learner tries to maximize accumulated reward during its lifetime. For example, Merlis (2024; Lee et al. (022)) both use past data to predict future system dynamics via Temporal Difference (TD) learning. However, the standard TD methods are established on stationary MDP,
so its applications on non-stationary MDP require a limited variation budge on single trajectory (Li el al.,
2019b Lee et al. 2024 Wei & Luo 2021 Chandak et al. 2020 Jali et al., 2025) or among a sequence of
episodes Feng et al. 2023 Moon & Hashemi 2024 Zhao et al. 2022). For example, Jali et al. (2025)
recently achieves a regret of ((SSAA}T)) where S is the size of state space, A is the size of action space, AT is the total variation budget, and T' is the time horizon. Other works reset the controller at the end of each episode (Gajane et al., 2018 Auer et al. 2008) and assume the ground-truth MDP stays the same within each episode. In this line of work, Merlis (2024) also utilizes prediction in policy design and achieves a regret of 52 K (TTSA)))), where K is the number of total episodes. However, this work only allows for changes in either the reward function or the transitional probability while the other stays the same for all episodes, whereas in our setting, we allow for changes in both reward function and transitional probability and achieve an exponentially decaying regret. Another line of work actively detects the switch of MDPs by maintaining an estimate of system dynamics and resetting the controller when a switch is detected (Alami et al.) 2023 Dahlin et al,, 2023). More recently, a new branch of work uses exogenous predictions, but requires pre-trained optimal policies for cach potential MDP the learner encounters, and designs the policy through mixture of those optimal policies (Pourshamsaci & Nobakhti 2024h. Compared with those works, this paper focuses on different setting of policy design on single rollout, which does not
2

---

Published in Transactions on Machine Learning Research (07/)025)
allow reset of system at the end of each episode for traditional non-stationary episodic RL. Furthermore, we utilize exogenous predictions for controlling non-stationary MDP instead of generating those predictions from past data and do not require any prior knowledge about those MDPs.
Model predictive control Traditionally, model predictive control is a branch of control theory that, at each time step, calculates predictive trajectory for the upcoming time steps and then implements the first control action from this trajectory (Lin et al. 2021p. Some of these works seek to achieve guarantees such static regret (Agarwal et al.] 2019 Simchowitz & Foster 2020), dynamic regret (Li et al., 2019a; Yu et al. 2020,, competitive ratio (Shi et al.]
2020). From theoretical perspective, extensive research has been conducted on the asymptotic properties of MPC, including stability and convergence, under broad
assumptions about the system dynamics (Diehl et al. 2011 Angeli et al. 2012). Remarkably, Lin et al. (2021) shows that regret in a seeaa-ttme-varrinne system decays exponentially with the length of the prediction horizon. However, most of those works assume linear and deterministic system dynamics in continuous space in order to obtain thcoretical regret guarantee. In this paper, we focus on an MDP setting with finite stale spaces and stochastic transition kernels, where the tools and algorithm design are very different.
2 Problem Formulation
We start by introducing the discrete non-stationary Markov Decision Process characterized by the tuple (S, T, (P:)T (re) Here S,A denote the discrete state space and action space, respectively. The set of functions {Pi(-Is, (a.ls, is the collection of transition probability measures indexed by the state- action pair (s, a) and time step t. The set of function (re(s.a)) (s.)EEXX is the expected instantaneous reward, where re(s,a) is the deterministic reward function taking value [0, 1] incurred by taking action a at state and time stop t. We denote T as the time horizon. Lastly, we use (T(-I-) to denote a dccision policy al time I that maps 8, de and use denote the collection of (m))
The learner does not have access to the transition probability {P:} and reward functions {rehe. Instead, we consider a setting in which the learner can predict the future and obtain estimates of future transitional probabilities P and rewards f for time steps. More specifically, al any time 4, the learner has reward and transitional probability estimation fete for any E E {L,...,k}. The error of the predictions are characterized in the below definition.
Assumption 1 (prediction error). The reward estimation f(s, a) and transitional probability estimation P has the error bound
(s, a) re+e(s,a) < ce, (- - Pcte(-1s, e < de,
for all f, where II-l denotes the total variation norm.
The fact that the prediction error is a function of the prediction distance is intuitive, as system forecasts are often more accurate in the near future than in the distant future.
The learner implements an algorithm ALG that at time i, observes 8, and is given the prediction Artele Procie for any l kk. It generates a policy at step i, denoted as Te, based on available information. Given the algorithm ALG, its value function is defined by
T
VLL
Σ BALG [r,(s,,)))s = s].
(1)
such that s;+1 ~ P((-|s,, a:) for all i, where is generated by Te.
We also define the offline optimal, which is the optimal value had the learner known all the future transitions and rewards precisely. Formally, the optimal value function is defined by
T Ir, a.)ss =s],
Vi((s)
max E -
where in the expectation, a; (s)))
3

---

Published in Transactions on Machine Learning Research (07/2025)
The learner's objective is to design policy that utilizes the dynamics forecast to maximize the cumulative reward and minimize the dynamic regret
R(ALG) (50) VALLG (so),
(2)
for some fixed initial state 80-
Example 1. A server needs to allocate resources for tasks and minimize the average wait time for cach job. We consider the setting that there are servers, each has service rale Hi; and single queue with time- varying arrival rate de. The system's state space is the length of the queue and whether each server is idle or busy, and its action space is the decision of sending a job in the queue to an available server or not doing anything The transitional probability is determined as follows. At each time, a job arrives at the queue with probability )e/(Ae + E.1.). Then; a dispatcher decides whether to send a job in the queue to one of the idle servers or wait till the next time step. Also, the busy servers will complete the job and become idle with probability (E,
Σ, 14). For detailed explanation of the setup, see Jali et al. (2024). In this example, the job arrival rate d varies in time, and having a prediction of the future arrival rate can help the dispatcher in making the job assignment decision. Existing methods for future Internet traffic forecasting [Katris & Daskalaki 2015) can greatly help with the process and reduce the average wait time.
Example 2. Renewable energy generation heavily influenced by environmental factors, and its prediction is also subject to error with different prediction horizons. We consider discrete-time model for electric vehicle (EV) charging. A list of EV arrives at the charging station from time step 0 to T. The i-th EV arrives at the station at time 0; if the station is already full, it would leave the station without charging. If there is an unused charging stand, it sets a departure time d, and an energy demand e,. Moreover, each charging stand has a charging rate capacity μ, and the station has an overall charging capacity C. The station needs to charge all electric vehicles that arrive by setting charging rate Ts for each vehicle at each time step t. The energy demand of each vehicle has to be satisfied, i.c. Σ Tt, Cs. Moreover, the charging rate has to be below the threshold of each charging stand and the station, i.e. for every 4, r,s E [0, 14], Ei Th, < C. For a detailed explanation of the setup, see Chen et al. (2022). Moreover, the energy price fluctuates with energy supply and demand. Since the energy price fluctuates with time f, the station wants minimize the total cost of energy while still fulfilling the energy demand of all vehicles before their departures. In this sctup, the state space is the energy demand of each EV, the energy price, and the time frame in which those demands have to be met. The action space is the decision of whether to supply the required amount of energy now or to wait for a later time. As both EV parking demands and energy price can be forecasted (Provoost et al., 2020 McHugh et al. 2022
Kapoor et al. 2025). learners can utilize this information to adjust their policies.
3
Preliminary
Before we introduce the algorithm, we introduce a few concepts that play key role in the decay of regret.
3.1
Span Semi-norm and Bellman Operator
First, we introduce the span semi-norm.
Definition 1. For any vector v E Ied, define the span seminorm of denoted as sp(u) by
sp(u) = i u(i) min v(i).
where v(i) is the i'th entry of w.
The propertics of span semi-norm is briefly described in Proposition can be found in Puterman (1994). We use span semi-norm to quantify our approximation of the Q functions. Since we use arg max on the Q function to determine which action the learner should take, shifting the entire Q function by a constant does not affect the policy. Since span semi-norm has this property (sce Proposition A.1 in Appendix A). we use span semi-norm quantify the deviation of our estimated Q function from the ground-truth Q function.
A.1 in Appendix A More description
4

---

Published in Transactions on Machine Learning Research (07 (025)
We also introduce the Bellman operator in the vector format:
Pi(s Pr(s'ss, P
Loc(s) max aeA
r((s,a)+
Σ s'es
(3)
where e E TR|S| is the vector of value function for all states. Similarly, define
Li u(s)) (a)r(s) rı(s,a) + Σ P(((d(ss
(4)
N'8
Furthermore, denote the time-varying nested Bellman operator as follows:
Lae == Le o ..... Le
(5)
= 1.
(6)
where fog := f(g()) is the nested operator. Similarly, use Pe and Pt to denote the transitional probability matrix when using policy or taking action at time t, respectively. We use P and pe to denote the nested product of the transitional probabilities.
We now introduce the J-stage contraction.
Definition 2 (J-stage contraction). We say sequence of operators (Fi)iE(L.... S J-stage span contraction if exists E 1), such that
sp(F: o...o Fi+Ju F...... F(tJV) < <ssp(u v).
for all u E RI E T.....,T--JJ. Assumption 2. There exists J E Z such that for the optimal policy x² (m and any other policy π (Tr)7-o time step t {O..... TT.,.,
((T,, π²) min Σ min p o .... (j(ss,, .... P > 0.
$1.82E8
JES
The above assumption similar to the uniform ergodicity assumption in Yu & Mannor (0099) Li et al. (2019b). To see this, we note that Assumption III.1 of Yu & Mannor (2009) also requires ergodicity among states in a non-stationary environment under any pairs policies. This assumption implies that the effect of any mistake decays exponentially with the number of passing time steps. In episodic non-stationary RT (e.g.. Moon & Hashemi (2024); Zhao et al. (2022)) ), this assumption is automatically satisfied the environment resets at the end of each episode, so the learner can recover any mistake in future episodes. Further, we point out that if Assumption 2 is not satisfied, it would imply that there exist certain situations within the MDP such that, for any & and T, there exists an non-stationary MDP that violates Assumption any algorithm would have expected regret of O(T). We give a counter-example of such non-stationary MDP in Counter-example
2 such that
In the next proposition, we introduce how Assumption 2 establishes contraction, which later use to show the decay of regret.
Proposition 3.1. For any non-stationary MDP satisfying Assumption J staage contraction operator with contraction coefficient
L, defined in equation is
- min ([
The proof of Proposition 3.1 is deferred to Appendix A

---

Published in Transactions on Machine Learning Research (07 2025)
3.2 Diameter
The diameler of MDP is commonly used in reinforcement learning [Gajane el al. 2018 Wu el al. 2022 We extend the definition to non-stationary MDP.
Definition 3. Given non-stationary MDP, time t, state policy π, and family of sets {s C S), define
de(s, n, {:) in :7 81+r E s(t 8t =))
where {=o is generated by policy n, and let T((S() |/7, 8) denote the minimal travel time from to the family of sets {8(1), J starting at any t, i.e.
T(SS suu sup (Bdd {11)
(7)
Let S == arg max, (s) denote the set of states with the maximal value function at time step i. Define the diameter of non-stationary MDP as
D max min (T(S))]|T.))
(8)
"
In this paper, the time horizon T is finite. Therefore, when > T, we have S 8. As the agent will arrive at } immediately after the T-th time step, we always have D < T for any finite horizon MDP. Proposition 3.2. For a stationary MDP, The diameter as defined in Definition 3 is upper bounded by the
conventional diameler definition for stationary MDP as in Wu el al. (2022).
The proof of Proposition 3.2 is straightforward, as the {st+)) h is constant for all t, in time-invariant MDP.
The diameter of non-stationary MDP upper bounds the span semi-norm of the optimal value function, as we present in the following Proposition:
Proposition 3.3. For any non-stationary MDP with diameter D defined in Definition 3 sp(Vt) < D for
all t.
The proof of Proposition 3.3 is deferred to Appendix B
4 Main Results
4.1 Algorithm Design
On high level, at each time step the proposed algorithm Model Predictive Dynamic Programming (MPDP) works by conducting a dynamic programming style planning for the next k steps, and takes the first action. More precisely, we define the Bellman operator i on system dynamics forecast as follows:
aeA Leteje(s) max fetqr(s,0)+ + (p
(9)
where the learner optimize on the forecast of reward and transitional probability, instead of the ground-truth as in equation 3 The learner picks action such that
at = arg max f(s,, a) max (8442, + max aEA
maxE|.... El... max Pet (814 )]
Ro+1
0r42
denk
(10)
= arg max o...o L aεA
where Wo denotes the zero constant vector. Intuitively, the learner undergoes dynamic programming process for the future & steps based on the reward and transitional probability forecasts, and takes the first action of the dynamic programming. Then, the learner obtains new forecast and repeats the process.

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm Model predictive dynamical programming (MPDP)
1: Select v10) E RR, specify <>> O, and set $ = 0.
2: for t= 0, 1..,..... do
3: Forcast Pe...., Pe+ky Pe....,PPett: f.....,f(t4
Select a, according to equation 10
St-1 P((-(s;,a)).
end for
The algorithm is simple and intuitive. line of Algorithm 1 we forecast the system dynamics of the future steps. In line 4, we pick the first action that maximizes the reward in the future & steps. The algorithm design is inspired by model predictive control (Gareía et al.) 1989), and try to optimize the performance of the learner within the prediction horizon and decide the action by dynamic programming style algorithm.
4.2 Regret Guarantee
In this section, introduce our bound on regret defined in equation 2
Theorem 4.1. Por any non-slationary MDP salisfying Assumplion
Algorithm
achieves a regrel of
[6/--11
R(MPDP) ST.LRIJI 27' + 2To. 2T
Σ
Σ CLJ+s
Σ
BostsD)
KJLJ
A%
+ 1T/11
Σ
Σ
11/JJJ45 +
where k%J == [k/JJ-
In the error-free setting (the prediction does not have error), Theorem 4.1 simplifies to the following corollary. Corollary 4.2. If the system dynamics forecast is exact for the future k steps, then
R(MPDP) < LT
We observe that, the error-Tree case (Corollary 4.2 the regret depends linearly on the time horizon T and diameter D and decays exponentially with the prediction horizon &s when Assumption 2 is satisfied. In particular, Algorithm ! with log- predpredittion horizon h Olog T) will obtain regret sublinear in T. This means that predictions, even if a short horizon, powerful in the sense that it leads to sublinear regret without any assumptions on the variation budget.
In the setting of inaceurate prediction (Theorem 4.1 we observe that regret grows linearly with the predic- tion error Ez, dg. is important to note that the sensitivity to Eg, & decays exponentially in E, meaning that the regret more sensitive the prediction error of the near horizon than the long horizon. Therefore, even if the prediction error increases as l increases, long as the increase subexponential, using predictions in the far future with potentially large errors still has positive impact the overall performance.
Lastly, our results also indicate a tradeoff between the error induced by the inaccurate predictions and the additional information it provides. For predictions further into the future, while it may contain valuable information, the potentially large error can also lead to a worse regret. We note that the learner can solve an optimization problem to determine the best & to maximize on the exponential decay property and avoid the large error caused by forecasting too far into the future.
We briefly outline the steps of the proof of Theorem 4.1 in Section
The full proof is deferred to Appendix

---

Published in Transactions on Machine Learning Research (07 (025))
5 Proof Outline
We split the proof outline into three separate steps. In the first step, we show that the estimated value function converges to the ground truth value function in the span semi-norm with increasing prediction horizon. In the second step, we bound the error of the estimated Q function using the step-wise error bound of the Bellman operator. With the error Q function bounded, if the learner makes a mistake using the estimated Q function, the maximal loss caused by that mistake can be bounded. Therefore, we can bound the maximal regret in the last step.
Step 1: One step error bound. As Algorithm | takes greedy approach to optimize the reward within the prediction horizon of length k, we first need to approximate the optimal value function V22 within the k steps.
Let Pe+eje denote the predicted transition probability for (t ( E) -th stop at time stop t, and let î denote the predicted reward function. Let o8 denote the vector of the maximal expected reward at time t for the next k steps,
0. max (fttnc(s, + By ( (8))
1 1+ T or E> k.
(+)
(11)
t t+
Similarly, let w denote the vector of the maximal expected reward with completely accurate forecasts.
-
0,
t T or 8> k t
(5 1 max r1)r(s,0) + By 11
(12)
Since the forecast is different from the true system dynamics, we need bound the difference between of and dy step-wise. First, make simple observation.
Lemma 5.1. For constant vector Wo, J L, ... Wo where t' min + k}. Similarly, 30 = o.... Ly Wo.
Proof: We procoed by induction. If k 0, the equality is trivial. The induction step directly follows from equation and equalion 12
The above lemma implies that, when t 2 T, we have (s) Vs((s) for all s. Furthermore, we point out that V Tu W, Ia o... T. V741- Correspondingly, need to bound the error generated by each layer of the Bellman operators.
Lemma 5.2. For any V, V e ss such that sp(V) < D,sp(V) < D and sp(V - V) I b, have
sp (Luee - D s b + 22g + 28.
The proof of the above lemma is left to Appendix
Step 2: Bounding the error of Q function. We define the optimal Q function as follows
(s, a) rr(s, a) ( s, a = a).
(13)
Since we use and & to estimate the value function V each time step, we can construct estimates of Qi as follows:
(,( = ra(s, a) E Pa ( (s')},
(14)
(s == fr a) E, B ( 20 (s')).
(15)
In order bound the error between v and Qi we need bound two pairs of the difference: the difference between V, and Qi, and the difference between V, and V. The details of those steps are deffered to
8

---

Published in Transactions on Machine Learning Research (07/2025)
Lemma D33 and Lemma D.4 in Appendix D respectively. With an error bound of our approximated Q function, we can upper bound the loss of reward by each mistake made by the algorithm.
Corollary 5.3. Let a be the action picked by Algorithm ! with prediction error defined in Assumption at the t-th time step at state 8, and let a" be the optimal action at time t, then,
[K/]]-1
J
Qi(s,a)) - a)) sy/W/d) sp (Vi+++1) + 2cg + +60 +2
Σ 1=0
Σ 1=1
CJ+J +
Σ 5=1
BwstsD
R%J
R%J
+ 27 1k/J1
Σ
(W/J)/345 + Σ
The proof of Corollary 5.3 is deferred to Appendix D
Step 3: Bounding regret. Since the error of Q function is bounded at every step, we can upper bound the regret R by bounding the telescoping sum of EЛE, (s) - Q7 (s), a:)]. By bounding the error at each step, we obtain Theorem 4.1
6
Simulation
6.1 Queueing system
In the first simulation, we simulate qucucing system based on the sctup provided Example Specifically, we consider a representative example of servers whose service rates (4r3=1,2,3 are 100, 10, 1, respectively, with time horizon T 100 and varying load d, fluctuating from 10 to 100.
In the first part of this simulation, we compare regrets of different lengths of the prediction horizon k and waw.-eeeeeeeeeeeeeeeeeeeeeeeeeee
the Fast Available Server (FAS) (Lin & Kumar 1984), (Özkan & Kharoufeh] 2014). and Non-Stationary Natural Actor-Critic (NS-NAC) (Jali et al. 2025). FAS is a popular algorithm frequently used in practice, which sends any available job immediately to the fastest available server. RSRT is a threshold policy where job is routed the fastest among the available servers only if the queue length exceeds predetermined threshold (Ōzkan & Kharoufeh, 2014 It has been proven to be the optimal policy in the two-scrver setting (Özkan & Kharoufeh] (0144) Notably, typical time-varying RL algorithm, such as NS-NAC, would not work in this example without pretrained initial policy, there are infinitely many states in the queuing problem, and the policy would keep exploring new states with longer queue lengths. For a proper comparison, we set the initial policy similar to RSRT with a small exploration probability for every action. We then compute regret where the optimal policy has full knowledge of the transitional probability. For each E [I....,15] we run 20 trials and record the average regret for each k value. The agent has access to the predicted arrival rate of jobs with some Gaussian additive prediction error 2, = X, +NOO, a) with E {0, 2, The optimal policy compute our regret from is the policy that is computed knowing all future transitional probability and reward functions. The arrival of jobs fluctuates periodically with a sin function with magnitude 110 to simulate periodical change in demand. The queue length of FAS is consistently the longest throughout the time horizon, and RSRT has a queue length similar to that of MPDP with k = 8. MPDP with & = 12 has the shortest queue length throughout most of the time steps. As shown the rest of Figure D the proposed algorithm outperforms both benchmarks with k 2 under noisc-free setting and also outperforms both benchmarks with k 2 with prediction crror. Specifically, we see a decay in log-scale of regret. However, as we have J-stage contraction, the regret does not necessarily decrease monotonically with every increase in k.
(RSRT) algorithm
In the second part of the simulation, we fix k = 10 and examine the relationship between the magnitude of the prediction error and regret more closely. Although the learner can still forecast the system dynamics in the future, the predicted arrival rate of jobs X := X +V or,)). We first hold or, to be constant of t, as in the first part. Therefore, the variance of the prediction error does not increase with the distance of the forecast into the future. As shown in Figure 2a the regret initially remained minimal and increased lincarly
after variance reaches 8, as shown in Theorem 4.1
9

---

Published in Transactions on Machine Learning Research (07/202) 2025)
10.
12"
reg
regret
negred
31-1
2314
oesieeece intanul
confidance strval
49% 60% corfirenc rtavvl
001
R68
RDNT
HIGT
14
10
22
10
(a)
(b) 0=
(c) 0=
Figure 1: Figure la Figure lb and Figure 1c show the regret of MPDP under different additive prediction error ((0,o). The red solid line shows the mean of the regret, and the shaded area shows the confidence interval.
20% and 80% confidence interval
1.0
confidence
50% and 70% confidence interval
20% confidence interval
15.0
confidence
40% and 60% confidence interval
12.5
regret
10.0
regret
7.5
0.-
variance of prediction error
growth rate of prediction error
(a)
(b)
Figure 2: Figure shows the average regret remains almost constant with variance of prediction error below and starts to grow afterward. Figure 2b shows the regret slowly increases with the growth rate of variance of the prodiction error with respect to the prediction horizon.
Most practical forecast are usually more accurate for closer future than distant future. applications like wind power generation, has been shown that the accuracy of forecasts decreases a linear rate with respect the distant in the future (Qu et al. 2013). Therefore, in the third simulation, we fix k 10 and the initial variance of the prediction error to be 1 and examine the relationship between regret and growth rate of variance with respect to the prediction horizon g. More specifically, for each forecast, variance 0za = 1, and ot, to increase with respect to the distance to the future predicted by the forecast. As shown in Figure 2b the regret does increase with growth rate 9, but the increase relatively slow. Even for the case g = 4, which indicates the variance increases by 4 times for every time step, thus reaching times of the initial error the end of the prediction horizon, the average regret merely increased 2 times. Indeed, by the expression in Theorem the regret would never explode if the growth rate of variance is sub-exponential.
fix the L. We are most interested in the case where > 1, as the variance tends
Lastly, we introduce a simplified version of the queueing problem in Example 1 While keeping all other factors identical, we fix X₂ E {30, 130) and switch X every 50 steps. By fixing À to only two potential values, we simplify the setting where a traditional RI. algorithm with context detection might have an advantage. To incorporate more changes in MDP, we also extend the time horizon to 300.
The result of the simulation is shown in Figure 3 We introduce RL-CD proposed in da Silva (2006) new benchmark. For proper comparison, also set the initial policy to be similar RSRT, with small
10

---

Published in Transactions on Machine Learning Research (07 (07/2025)
corfience
dence
condde Innww
35% and 70% cortiance revv
70% cant sence internal
55% and T0% contide enaan
45% and E0h corfiience servvl
45%
90% dence intenval
42% and cons contid tom imars
R5
MO
regret
14
10
22
0
12
(a)
(b)
(c)
Figure 3: Figure 3a Figure 3b and Figure 3c show the regret of MPDP under different additive prediction error (0, or in a setting with a finite number of changes in MDP's. The red solid line shows the mean of the regret, and the shaded area shows the confidence interval.
5
energy usage
regret
20-
NFOP
SLL
10
time
(b)
Figure 4: Figure shows the power usage different time steps. The shaded indicates the time period with energy prices below 8. We see that with & > 7, the most energy usage happens within the area with low energy prices, reducing the total energy cost of the station. Figure 4b demonstrates that the regret of EV charging decays with the prediction horizon. Compared with traditional scheduling policies, the proposed algorithm can lower the total energy cost even with a few prediction steps.
exploration probability for every action. Due to the scarcity of changes, both RL-CD and NS-NAC perform worse than RSRT, which is provably optimal for queueing systems with constant X. However, the proposed algorithm still outperforms RSRT with k 2 9 in all three noise settings with a E {0, 10,1, demonstrating the effectiveness of MPDP when model prediction is available.
6.2 EV charging
In this section, we consider a scenario of EV charging station under the setup of Example with time horizon T 50. The charging station has three charging stands, and the energy price fluctuates between 2 and 18.
We first show the correlation between the change of energy price and energy usage. We compare the regret of our algorithm with the benchmark policy, the smoothed least-laxity-first algorithm (sLLF) proposed in Chen et al. (022),, which prioritizes charging the EV that is the closest. to the departure time. However, given the fluctuating energy price, the optimal policy should charge the EVs at the time steps with the lowest energy price that can still satisfy the energy demand of the EVs before their departure times. As shown Figure dal compared with sLLF, our algorithm selects better time for charging each EV. particular, when k increases, most of the peak of energy demand falls within the shaded area with low energy price.
11

---

Published in Transactions on Machine Learning Research (07/2025)
We then show the decay of regret with respect to the growth in the prediction horizon. Compared with traditional scheduling algorithm proposed in Chen et al. (2022), our algorithm can better handle the fluctu- ation in energy price. As shown in Figure 4b even with only few steps of prediction, the station's 's regret decays exponentially.
7
Conclusion
This paper designs noval algorithm for non-stationary MDP utilizing exogenous prediction. We showed, under the assumption of uniform ergodicity, our algorithm achieves regret of O(T))k/11)) When O(log obtain regret sublinear in T. We also show that even when the prediction error grows subexponentially, the regret does not explode. The future directions of this work includes the application of this framework in partially observable MDPs and the extension of this framework when only part of the transitional probability and reward functions are predictable.
References
Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances Neural Information Processing System, 32, 2019.
Reda Alami, Mohammed Mahfoud, and Eric Moulines. Restarted bayesian online phange-point detection for non-stationary markov decision processes, 2023. CRL
Poojitha Amin, Ludmila Cherkasova, Rob Aitken, and Vikas Kache. Analysis and demand forecasting of residential energy consumption multiple time scales, In 2019 IFIP SIP//EEE Symposium on Integrated Network and Service Management. (IM), pp. 494-499, 2019.
David Angeli, Rishi Amrit, and James B. Rawlings. On average performance and stability of economic model predictive control. IEEE Transactions on Aulomatic Control, 57(7):1615 1626, 2012. doi: 10.1109/TAC. 2011.2179349.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Botton (ods.), Advances in Neural Information Processing Systems, volume 21. Curran Associales, Inc., 2008.
Yash Chandak, Georgios Theocharous, Shiv Shankar, Martha White, Sridhar Mahadevan, and Philip S. Thomas. Optimizing for the future in non-stationary mdps. In Proceedings of the 37th International Conference on Machine Learning, ICML'20 JMLR.org, 2020.
Niangjun Chen, Christian Kurniawan, Yorie Nakahira, Lijun Chen, and Steven H. Low. Smoothed least- laxity-first algorithm for electric vehicle charging: Online decision and performance analysis with re- source augmentation. IEEE Transactions on Smart Grid, 13(3):2209 2217, 2022. doi: 10.1109/TSG.2021. 3138615.
Bruno C. da Silva, Eduardo W. Basso, Ana L. C. Bazzan, and Paulo M. Engel. Dealing with non-stationary environments using context detection. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, pp. 217-224, New York, NY, USA, 2006. Association for Computing Machinery. URL
ISBN 1595933832, doi: 10. 10.1145/114484441114
http:////o....rg110111////////// 114788444.111877 1143872
Nathan Dahlin, Subhonmesh Bose, and Venugopal V. Veeravalli. Controlling a markov decision process with an abrupt change in the transition kernel. In 2023 American Control Conference (ACC), pp. 3401 -400-, 2023. doi: (22999/ACC55779.2000 10156034.
Moritz Dichl, Rishi Amrit, and James B. Rawlings. Iyapunov function for cconomic optimizing model predictive control. IEEE Transactions on Automatic Control, 56(3):703-707, 2011. doi: 10.1109/TAC. 2010.2101291.
12

---

Published in Transactions on Machine Learning Research (07/2025)
Songtao Feng, Ming Yin, Ruiquan Huang, Yu-Xiang Wang, Jing Yang, and Yingbin Liang. Non-stationary reinforcement learning under general function approxination, 2023. https///aaaa wttp://////////////////
00861
Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-window algorithm for markov decision processes with arbilrarily changing rewards and transitions. CoRR, abs/1805. 10066, 2018.
Carlos E. García, David M. Prett, and Manfred Morari. Model predictive control: Theory and practice a survey. Automatica, 25(3):335-344 1989. ISSN 0005-1098. 90002-2.
doi:
(000000001118(8))
Neharika Jali, Guannan Qu, Weina Wang, and Gauri Joshi. Efficient reinforcement learning for routing jobs heterogeneous queucing systems, 2024. URL pttp:://aaaxx...oor///////200..0
Neharika Jali, Eshika Pathak, Pranay Sharma, Guamnan Qu, and Gauri Joshi. Natural policy gradient for average reward non-stationary RL, 2025. URL http:a////paaaaeeeeeeeee//////aa
Gaurav Kapoor, Nuttanan Wichitaksorn, Mengheng Li, and Wenjun Zhang. Forecasting half-hourly electric- ity prices using a mixed-frequency structural var framework. Econometrics, 13(1), 2025. ISSN 2225-1146. doi: 10.3390 (0:3300/ecooomettres1300000 300000omeetriie11100000....
Christos Katris and Sophia Daskalaki. Comparing forecasting approaches for internet traffic. Expert Systems
with Applications, 42(21):8172 8183, 2015. ISSN 0957-4174. doi: http:///oii.orr1.1100000000 w0w.116/....swa.215....... 029.
Hyunin Lee, Ming Jin, Javad Lavaci, and Somaych Sojoudi. Pausing policy learning in non-stationary reinforcement learning, 2024. URL
httg//bb/24055.. 16053
Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predictions: algorithms and regret analysis. Proceedings of the 33rd International Conference on Neural Information Processing Systems, 13, 2019a.
Yingying Li, Aoxiao Zhong, Guannan Qu, and Na. Li. Markov decision processes with time-varying transition probabilitics and rewards. 2019b.
Woei Lin and Kumar. Optimal control of a queueing system with two heterogeneous servers. IEEE Transactions on Automatic Control, 29(8):696-708 -03, 1984. doi: 00.1199/TAC.18841110388
Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation based regret analysis of predictive control in linear time varying systems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 5174-5188 Curran Associates, Inc., 2021.
Catherine McHugh, Sonya Coleman, and Dermot Kerr. Hourly electricity price forecasting with narmax. Machine Learning with Applications, 9:100383, 2022. ISSN 2666-8270. doi: https://@60.org//0..1011
ndlwa2022..10332
Nadav Merlis. Reinforcement learning with lookahead information, 2024. URL https://arxiv.oor abs/
2406. 02258
Sang Bin Moon and Abolfazl Hashemi. Optimistic regret bounds for online learning in adversarial markov decision processes. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL https: http://www...eeeooooo//////////a
Sindhu Padakandla, Prabuchandran K. J., and Shalabh Bhatnagar. Reinforcement lcarning algorithm for
non-stationary environments. Applied Intelligence, 50(11):3550-36666 nov 2020. ISSN 09244-69XX. doi: 1011007774144884000--1778855 URL httpt:://////// /tt..t/tpp////oorooooo////////00
13

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Hossein Pourshamsaei and Amin Nobakhti. Predictive reinforcement learning in non-stationary environments using weighted mixture policy. Applied Soft. Compuling, 153:111305, 2024. ISSN 1568-4946. doi: https: //doi.org/ (ttpi/or//111016////11
Jesper C. Provoost, Andreas Kamilaris, Luc J.J. Wismans, Sander J. van der Drift, and Maurice van Keulen. Predicting parking occupancy via machine learning in the web of things. Internet of Things. ittp://......////...oo.... sciencedirect. cttp://cccccccarccaaaa///////26.
12:100301, 2020. ISSN 2542-6605. doi:
URL htttps://ww/
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
Guannan Qu, Jie Mei, and Dawei He. Short-term wind power forecasting based on numerical weather prediction adjustment. In 2013 11th IEEE International Conference on Industrial Informatics (INDIN), pp. 453-457, 2013. doi: 10.1109/INDLL .119//III...11..66011 2013.6622927.
Spencer M. Richards, Navid Azizan, Jean-Jacques E. Slotine, and Marco Pavone. Adappive-controo-orinntedd meta-learning for nonlinear systems. Roboties: Science and Systems, 2021.
Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with mem- ory and competitive control. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, 2020.
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8937-8948. PMLR, 13-18 Jul 2020.
Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal 054066
black-box approach, 2021. URL
Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning Sinite-hhorioon average-reward mdps with linear function approximation. Gustau Camps-Valll Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3883 3913. PMLR, 28 30-3 Mar 2022.
Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Proceedings of the 94th International Conference on Neural Information Processing Systems, NIPS '20, 2020.
Jia Yuan Yu and Shie Mannor. Online learning in markov decision processes with arbitrarily changing rewards and transitions. In 2009 International Conference on Game Theory for Networks, pp. 314 322, 2009. doi:
Ziyi Zhang, Guannan Qu, and Yorie Nakahira. Fast bandit-based policy adaptation in diverse environments, 03 2024.
Peng Zhao, Longfei Li, and Zhi-Hua Zhou. Dynamic regret of online markov decision processes. In Inter- national Conference on Machine Learning, 2022. URL htttts://app.. htt.::/cccccccoooorroorrorssaaae 250360901
Erhun Özkan and Jeffrey P. Kharoufeh. Optimal control of a two-server queueing system with fail- ures. Probability in the Engineering and Informational Sciences, 28(4):489 527, 2014. doi: 10.1017/
01269964481000111
14

---

Published in Transactions on Machine Learning Research (07 (075))
A Contraction in span semi-norm
In this section, we briefly introduce some properties of span semi-norm, and how it helps to show the contraction properly in Theorem 4.1.
Proposition A.1. The spon has the following properties:
1. sp(u) 2 0, Vu E Rd.
sp(u + u) - sp(u) + sp(v) for all u. Rd.
8. sp(kv) = [k] sp(v) for all k E I2, v EE EE Rd.
4. sp(v ke) = sp(e) for all le E R, where [I..... 1
sp(u) sp(-v).
6. sp(u) - 2 ||1122-
The proof of the above proposition easily follows from Desinition 11 More detailed properties of the span semi-norm can be found in Puterman (1944.. In the following proposition, we show the fundamental step of J-stage contraction.
Proposition A.2. Let E R" and policies Te..., TEtJ, then
sp Po v) S ss((s),
where Pr is the transitional probability at time with action determined by n, P =p ... .P", and (jls), P
==1
min 8NEES
Σ
min T
Ed+J
jES
1 max
Σ
CI (jls) P
(il)]==
max
Σ
P (j(s) - Paintt (ilu)]+
2 S,NES
jES
JES
Furthermore, 7 E [0, 1], and there exists such that sp( (Pt4 t v) 7 sp(v).
Proof: For simplicity, we drop subscript + superscript or dc+J, and use to represent an arbitrary transitional probability matrix. We further define
A(v) min uss), eES
T(v) max uss).
Let b(i,k;;)) P(j1) For any v,
Σ P(ll))(S) Σ P(iR))u())
jES
JES
> (PG()) -(ikk;))oo)) ΣIP(ik) b(i,k;)))v()
JES
JES
> (P())) b(Cb)T)))))))
( b(i
JES
JES
=(1 Σ sp(().
JES
Therefore,
sp
P v) max Patt
Σ
b(i, ((
i.kES
jES
from which the proposition statement immediately follows.
15

---

Published in Transactions on Machine Learning Research (07 (075)
We now ready to prove Proposition 3.1
Proof: [Proof of Proposition 3.1 Let v* denote the optimal value function at time +++++1, and let R denote the value function for an arbitrary policy at time ++J+1. s* arg max (s) and 8, arg min Lea+te" (s) Les+) Further, let 44प; denote the optimal policy according to Lefi o.... Ln-s(v"), and let Thii denote the optimal policy to take according to Lets ....o L++((v) then
TeatJ0"(") - Im(+)0(5") S TettJ u (s*) [1att v(s*)()))))))))))))) = PatJ
P (u" - (s))),
(Ha4J0"(8.) - Ima+su(8.) 2 I Iuayy
1et+J v² (8()) - [ 1 u(8a) = Petts (v" (8.).
Therefore,
sp(La+so0* Ju) S pr u)({") - ( (s. p (u" - u)(s) seS
S max SES
1it+
min
Putt (v" ()
p ht- Pheees
$
(0* (0- -1)
(16)
Applying Proposition A.2
equation
16 immediately leads to the theorem statement.
Diameter
In this section, prove Proposition 3.3 which shows that the span semi-norm of value function V, is upper bounded by diameter D for all t.
Proof: Proof of Proposition 3.3 Let πt' denote the optimal policy and n' denote the policy defined in Definition 3 trying to move fastest to {st+ By Definition 3 under a trajectory generated by n starting from time at 8,, define = inf(r :T:T 7 > 0, 8t+T = str) }. is a stopping time and by Definition E[d <
sp(V))= -V,(s))-VV())))
t+d-1
tid
=F
(s an) + V (i+a((+)))ss =s] Ex
(h(sh, an) Vi Vita(Seta)lss = s.]
A=t
t4d-1 1
t4d
<
(h(sn, an) + Vi = =5¹ ET
(n and + (ita(se4a)ss =sa]
h=t
h=t
++d-1
#dd-1
E
Th (s(s (1) =s] BF
Σ
ra(sn, ((ls,,an)ees an) sal
h=t
E
[Vinass4d)lss =s² Vital Vita(s)+d))
<0
<Ed < D.
Intuitively, if V."((")) > (s.), then better policy will be to move arg max, V Vi+ fast as possible, during which only D reward will be lost in expectation.
16

---

Published in Transactions on Machine Learning Research (07 (07))
C Proof of Lemma 5.2
In this section, we prove Lemma 5.2 which bounds the step-wise error incurred by using the forecast system dynamics, instead of the ground-truth transition and reward functions.
Proof: [Proof of Lemma 5.2 Assume that sp (v-P) 6. Given state s, let à denote the action chosen in Lete((s), and à denote the action chosen in Letere (s). By the construction of Algorithm
we obtain
P14 () + B Benneeelllls (s') 2 Fete)((s E
s (e V(s')
2 rete(8, ū) - e, + E. ((') (Eg (()) ) (BanPiitrrllad P())) 2 reeels ā) - + Ex+ (ss)) Bs-Pitellsa (V(5') - V(5)) DgD
(17)
The first inequality is due to the relative optimality of à for V and the second/ recond/third third inequalities are by Assumption and Holder's incquality. Similarly,
T=+e(8,ā) + Piettt V(s)) 2 r=) + Es (e V(5')
2 frtels,0) a) < + E Pe (s8) Ey-Pate((add) (V('') v(6'))
(18)
2 ))) B (5') Es (((s') - (((s))-((6)) dgD.
Combining equation
17 and equation 18 we obtain
(44e(8,) a) + B (s') - ENrPPt)((E))) (v(s))-((s)) - -e 6gD
Sfite(s, a) E E (( (s')
(19)
Srite(8,a) + Epw (( (ss) Pe ((()))((s))) + + D.D.
Therefore,
-1) Ls)eV(s) =f ( B ( ta - T(+((s;ū) ((s
(20)
Substituting equation 20 into equation
19
obtain
By By-Pite(aa) (V(s') V(s') a 6,D (s) Le -EP-( (V(s') V(s)) teatd.D. (21)
Let 8* arg max, (b (s) L14e (s)) and 8, = arg mig (lrge L44e (s)). Using Definition
and the assumption that sp (v- v) we obtain
sp(Ln-eee - I = D L+teV(s")- - (Inter((ss) - LeteV(ss))
< 1P44e(-s"",0 Ps (), T) sp(V V) + + + + El + 8,D
(22)
< b + 26, + 28.D.
Bounding the error of Q function
In order bound the error of Q function for every t, we must first bound the error of each estimated value function 20. We complete this in two steps. First, we bound the difference between S and v in span semi-norm. Then, we bound the difference between 30 and V.
17

---

Published in Transactions on Machine Learning Research (07 (07/2023) /025)
Proposition D.1.
[6/1-1
A%J
sp 00
1/6
2
Σ
7
Σ
Gi4ts
EdwADDD + +
Σ
[[KJJ]-445 +
1=1
#=1
for all t, where k%J = [k/J] J.
Proof:
We prove the case where I + k S T, the case where + k > T follows the exact same line. By
Lemma
5.1
उ. - Le .... L - Lug .... Lo
(23)
We proceed step-wise on sp(i) + for l going backward from k to 0. For the base case where / = k + 1,
we have sp (w (Jiti- whtt1 Sp( Wo) = 0.
By Proposition 3.3
know (V.) S D. By the monotonicity of Bellman operator, sp(uf) D,sp(vf) < D for all L. Therefore, we obtain
sp 30
v. sp T4 o...0 Ty+ W i, .... o Ww+
1
< dp L1 o...o o.. ( - xi)) + Σ
+ 6,D
_
(24)
1=1
i=1
(5/ Sas S
}/ 2 i=1
+ Σ
6DD
(25)
1=1
18/11-1
A%J
1%6J
2 2
Σ
7
Σ cu+s Σ SW4sD
12/k/J]
QU/J)-J43 +
Σ
(26)
where equation is obtained by Lemma 5.2 and equation 25 is obtained by Proposition 3.1 We repeat
the steps in equation 24 and equation 25 to obtain equation 26
We now ready to bound the difference between w and Vi" in span semi-norm. Lemma D.2. Given k
sp(w Vi*) k/J sp(V)).
I the estimation of Vr is eract, í.e. J/ = Vr.
Proof: The latter equality is clear from the definition of the Bellman operator, so we just need to prove the first incquality.
sp(16 Vi²) = sp (Le o... ..... TAtt a (Wo) L, .... Lutk (Vi+z-1))
I 5 1k/J] sp (Wo- - Vi+++1)
= -////] sp (Vi+++1).
where we applied Proposition 3.1 for [k/J] times. The last equality holds because Wo = 0.
We are now ready to bound the difference between the optimal Q function Q; and the estimated Q function v, Similar to the beginning this section, we divide the proof into two steps. First, we bound the difference between the optimal Q function Q; and the estimated Q function with exact forecast V
18

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Lemma D.3. For any states and t t k T, the Q function of the MDP satisfies
ss(Q] (s, -) - /- 7/1/11 sp(V+++1)) Ift+k2I, the estimation of Qi is exact, i.c. (.(s, (s,
Proof: The latter equality is a direct result of the construction of Vr in equation 14 so only need to prove the first inequality. By the Bellman operator,
sp(Q7 (e(s, :)) max ((ri(s, a) + s, =
(re(s,a) Bly ( 8 a)))
min ((rx(8, B (8141) 8, 0t a))
(m((s, + E (8 -6 8,0 = dl))
max BIV (8 0
(8++1) = a])
min E[ (8(+1) 30 (9 8t s, at = al)
< max (8) - Ve41 (+)]) min B|V (8) - (
=p((V - 3141)
/y/h/J1 sp (V++++))
where we used Lemma D.2 for the last inequality.
Then, bound the difference between the V and the estimated Q function 3 with forecast under As- sumption M
Lemma D.4. For any state s and time t,
[4/J1-1
sp ( < 260 D2+
Σ
Σ G,4
Σ SwetsD
12/11/111
Σ CL/JJ-J-3
Σ 6 وج/
Proof: By triangle incquality in Proposition A.1
we have
sp (s, - (x(,,)) 1) I ssp (re(s,)) Pr (8,, )) sp
E. P (s')] - 9, (100 (8')1
$2e + sp E 112 (5') 30 (
+ +sp 18 E (a (1242
$260 sp
(Br-pi(la,)) 183 (5') 2h (0))
260D
7/
1hJ
2%L
$2co 25 +2
Σ
Σ cu+s Σ SwttDD + 12/11/
Σ
CW/JJ.343 Σ
where we used Proposition D.1 in the last inequality.
We now ready for Proof of Corollary 5.3
Proof: Proof of Corollary 5.3 Fix a state and time t. Let a' denote an optimal action at (t, s), and let a be the action chosen by Algorithm Define the error vector over actions
(a(a) == ( a') (s,a'', a' d'A.
We first relate the suboptimality gap the span of this error:
(i(s,a") (s,s a) (,(ssa") ex(a") (v.(8, -((())
19

---

Published in Transactions on Machine Learning Research (07/2025)
= (Vv((s,a") (.((s,a) + (((()))e(aa))
Since a maximizes (),,,), we have (,(s, 2 a²(( and hence (,(,,aa) (e((, a) S 0. Therefore
- Qi 1 <(a) - c(a"))
S max me - ex(a")) sp(et).
d'.a"
That is,
-7 z sp(ú -(((s))))(((s..))
(27)
Next, use the triangle inequality for the span seminorm (Proposition A.1
sp - i (s, -M,ss)))))))))))) sp (.(,,)) sp
(s,,-))
(28)
The second term in equation 28 is controlled by Lemma D.3
sp( (s.-)) = sp(Q) (s) S 2111/0] sp sp(Vitu+1)-
(29)
The first term in equation 28 is bounded by Lemma D.4
(s, (s,,)) $ Dep + 20
[1/
+
Σ
GJ++ + Σ Detts D)
i=0
A%6J
A.%J
+ 27 1k/J1
E1/JJJ44
(30)
Combining equation 27 equation
28
equation
29
and equation 30 obtain
@i(,,a') (s) k/1l sp(Vi+++) (+++1)
2eg + 26
[4/J-1
J EiJ- + Σ
+2
Σ
84sts D)
==
==1
j=1
A36J
f2fflf41 D).
2- 1K/1|
QU/JJJ45 +
Σ
1=1
Theorem D.5. (s, (s, max (Q)(s,a)) > 7k/JJ sp (Vi+e) for all 1, 8, then the proposed algorithm is equivalent to the optimal policy.
E Proof of Theorem 4.1
We are now ready to prove Theorem
Proof of Theorem 4.1 Let ((5,, ar) denote the sequence of state-action pairs generated by Al- gorithm I with accurate prediction and {&,, a. denote the sequence of state-action pairs generated by Algorithm Let {af} = (arg max. Qi(s,, a)); denote the optimal action at each of those states.
Proof:
(so) - Vo(so) = =(ro(so, ag) ro aq)) + (Es.P(() (s1) - Eo (i)(s)))
+ (E, (s) Vi((s)))
(31)
=Q% 46) (% ao)) + F. (V) [s1)
(32)
20

---

Published in Transactions on Machine Learning Research (07 (025))
T-k-2 Σ
1/41-1
7 [k/J] sp (Vi+++2) + 2Teo 2T + 27
Σ
7"
Σ EJ44 +
DostsD
(33)
W%0J
AJJ
+ 17/11/ [4/1]
1//1 +
Σ
(34)
==1
In equation 31 and equation 32 we expand out the value functions and rearrange the terms. Applying Corol-
lary 5.3 leads to the resulting bound.
F Lower bound of regret for non-stationary MDP not satisfying Assumption
2
In order to show the necessity of Assumption provide the following counter-exant counter-example that generates linear regret for any k. Counter-ezample F.1. For any fixed k, T such that < T, we can generate the following non-stationary MDP with three states { The learner starts at st and must make the decision of going to s² 8 at time step Each of these actions has a reward of 8² 8 are sinks, and the learner can move out after time step 1. Clearly, the above MDP does not satisfy Assumption 2 since for any J > 0, P.te ... ' (s² = O for all policies π. At time step 0, a state s E {82, 83} is chosen at random, such that the learner gets reward of if at 8* for all time steps after k + 1, and a reward of 0 if otherwise. We claim that any algorithm with prediction horizon h would generale a linear regret for the above MDP, as there is a non-zero constant probability for any policy to not choose s" at time step 0.
21


Reviews:
[{"review_id": "zqKmDwFPQQ", "reviewer": "Reviewer_ocKi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The authors present an application of look-ahead prediction in dynamic programming. Theoretically, the authors prove that the look-ahead prediction can help with reducing regret bound. \n\n(2) The authors show effectiveness of the proposed method in two applications.\n\nWeaknesses:\n\n(1) The regret analysis is misleading. The definition (2) is the optimality gap, not usual regret for online MDPs. \n\n(2) The novelty in analysis should be highlighted, for instance how the contraction in span semi-norm works for look-ahead prediction.  \n\n(3) It is hard to interpret the regret bound in Theorem 4.1. It should be made more explicit when the regret bound is meaningful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the look-ahead prediction for dynamic programming in non-stationary MDPs. By leveraging the look-ahead predictions of the model, the authors propose a MPC-style algorithm that takes the first action in a finite-horizon prediction. In theory, the authors prove that the regret bound of the proposed method that depends on the prediction error, time horizon, and the diameter of non-stationary MDPs. Finally, the authors provide an experiment to show improved regret by increasing prediction horizon.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See detailed comments on Weaknesses: the notion of regret, technical challenge, and interpretation of the regret bound should be better explained.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KFhxAhOo1O", "reviewer": "Reviewer_1ych", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The topic seems interesting on using a prediction model for the non-stationary MDPs.\n2. Theoretical analysis is given for the proposed method with regret error bound. \n3. Numerical experiments are conducted for practical problem setups. \nWeaknesses:\n1. The authors emphasize using a single trajectory for learning. But why can't the prior work that resets the controller be used on such scenarios as well? It seems naturally it forms a transfer learning setting where the environment keeps evolving, and the policy continuously use TD to update. Only focusing on a single trajectory seems to limit the scope of this work. Additionally, it does not make sense to me to consider a single trajectory setting with finite-horizon MDPs as each trajectory automatically resets.\n2. It seems the proposed method is too idealistic, in the sense that we already assume having a predictive model which is close to the true transition kernel. From the perspective of model-based RL, I find it hard to distinguish its contribution as literature in model-based learning approaches already explored such methods extensively. What this paper is doing is even easier than model-based RL methods.\n3. For the experiments, the authors did not compare with baselines RL methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a method for non-stationary MDPs with (inexact) prediction models of the transition kernel. The authors showed that even if the prediction model can be wrong (requiring sub-exponential), a sublunar regret is possible. In the error-free case, an exponential-decay bound is given.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I'd like to see more explanation on the techniques using variation budget in comparison with the method proposed. I am not sure I understand the concept very well. The assumption on prediction model having sub-exponential error seems to have strong correlation to that. More detailed comparison is needed. \n2. The assumptions include sub-exponential error w.r.t time horizon. More detail on the applicability of such assumption should be added. \n3. Please elaborate on the difference between MPC works such as Lin et al. 2021 and the method proposed, if there's any, besides the state space and transition model assumptions. \n4. Definition 1 should be renamed to Assumption 1.\n5. Writing in definition 4 should be improved.\n6. The paper misses conclusion section and discussion section on the experiment results.\n7. No references given for the compared baseline methods.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ra0U1spqJJ", "reviewer": "Reviewer_KuNg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A non-stationary MDP is intrinsically hard to solve since we have limited data to learn about the non-stationary process at each time point. Exogenous predictions provide external information that can help in learning optimal policies. The paper rigorously bounds the regret in terms of the diameter of a non-stationary MDP and the $J$-stage contraction coefficient. It is also interesting to see a theoretical demonstration that the regret does not explode under mild conditions, and that numerically the regret grows slowly with the growth rate $g$.\n\nHowever, the assumptions under which the proposed method performs well should be further discussed. For example, in the two examples, it would be useful to explain how Assumption 1 is satisfied with respect to problem-specific parameters like the arrival rate $\\lambda_i$. Besides, how the desired prediction error can be achieved for specific prediction algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies policy learning in non-stationary Markov Decision Processes (MDPs), which are usually hard to solve due to their time-varying transition and reward functions. It proposes to utilize look-ahead predictions in dynamic programming to determine the optimal action. The authors prove theoretically that the regret decreases exponentially as the length of the look-ahead window increases. Moreover, as long as the prediction error grows sub-exponentially with the prediction horizon, the regret does not explode.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- External information like look-ahead predictions can help policy learning in unknown non-stationary MDPs. However, a key problem with this approach is how to obtain the predictions, especially sufficiently accurate ones (e.g., predictions with sub-exponentially growing prediction error). In the first simulation setting regarding queueing systems, the prediction is directly set to the true value plus some Gaussian noise. In the second simulation setting concerning EV charging, the prediction setup is not explicitly discussed (if I did not miss anything). Example 2 only mentions that \"both weather and energy demand can be forecasted.\" In either case, it is unclear how accurately the predictions can be constructed in real-world problems. It would be helpful for the authors to provide a real-world example of the predictions.\n- Could the authors explain why the confidence intervals in Figure 1 are wide? The proposed method does not seem to be significantly better than the baselines, even when $\\sigma = 0$.\n\nSome minor questions:\n- This paper proves that theoretically, when the look-ahead window $k = O(log T)$, the regret is sublinear in $T$. In the related work section, it would be helpful if the authors could discuss the regret bounds in the literature for non-stationary MDPs and under which assumptions they are derived.\n- Why do the arrival rates of jobs fluctuate periodically in Figure 1a? Is it part of the problem setup or a result of the algorithm?\n- What is the total time horizon $T$ in the two examples in Section 6?\n- Does the contraction coefficient $\\gamma$ refer to $\\alpha$ in Definition 3?\n- In Definition 4, should $s'$ in $\\mathcal{T} (s' | \\pi, s)$ be $\\{S^{(i)}\\}_i$?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DQ3Nhme0NG", "reviewer": "Reviewer_vuXT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is interesting and technically strong. However, I still have some questions on the assumptions and intuitions of the algorithm. First, for Definition 1, is there any difference between your assumption and the budget assumption in the previous literature? Intuitively, since the size of data is increasing, we can get more and more accurate estimations. And it is usually equivalent to the case that we have a limited non-stationary budget. For Definition 3, it seems more reasonable for me that $\\alpha$ then $\\gamma$ also depends on $J$. Can you give any example that $\\gamma$ is independent of $J$? For Definition 4, in the worst case, $D$ can be very large, even linear to $T$. Can you add more discussion on $D$? For (10), you only use a greedy algorithm without exploration. This kind of algorithm usually doesn't work unless you have very strong assumptions on parameters, like $D$. At the same time, the computational complexity is exponential to $k$, making it hard to use in practice. For Theorem 4.1, since the assumption on $\\epsilon_0$ should be held for all $t$, considering the case that we don't have enough data at the beginning, $\\epsilon_0$ can be $\\Omega(1)$. It will make the regret bound trivial. In the discussion of Corollary 4.2, in some RL literature, even without predictions, it's feasible to get sublinear regret. What is the unique difficulty of your problem?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider a very interesting topic -- how we can design policy in non-stationary MDP with some forecasts. The results are quite strong as the regret decreases exponentially. Also, they used both simulation and real-world data to show the advantages of their proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add more comparison on your Assumption 1 and other budget assumptions.\n2. Add some discussion on how $D$ depends on $T$ and the reason why you don't need exploration.\n3. Try to find a more delicate assumption on $\\epsilon_l$ and $\\delta_l$.", "broader_impact_concerns": "I don't think it has broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are concerned about the restrictive assumptions, the lack of error analysis in the prediction step, and whether the proposed algorithm outperforms prior art in practice, not just theory, given the restrictive assumption. The work imposes a multi-step contraction, which facilitates the theory and is interesting. However, it is important to note the proposed algorithm has not been shown to outperform works for the stationary setting with off the shelf change detectors employed for restarting, or even methods for the stationary setting that use function approximators that are well-attuned to time-series (such as RNNs or non-stationary kernels in RKHS). Therefore, the I share the concerns of the reviewers and have determined the paper is not publishable as it is.

If the authors can substantially revise the paper to resolve all reviewer concerns, especially with respect to baselining the proposed approach, contrasting notions of convergence/regret with more standard usage in the literature, and demonstrate its performance on stationary and non-stationary settings in experiments, I would consider a revision of this work.
Decision: Accept (poster)