Tempo Adaptation in Non-stationary Reinforcement Learning
Authors: Hyunin Lee
Yuhao Ding
Jongmin Lee
Ming Jin
Javad Lavaei
Somayeh Sojoudi
Venue: NeurIPS 2023 poster (2023)
Keywords: Non-stationary RL
Reinforcement Learning
TL;DR: We first raise and tackle a ``time synchronization'' issue in non-stationary reinforcement learning. To solve this, we propose a Proactively Synchronizing Tempo (ProST) framework that computes an optimal agent tempo.

Abstract: We first raise and tackle a ``time synchronization'' issue between the agent and the environment in non-stationary reinforcement learning (RL), a crucial factor hindering its real-world applications. In reality, environmental changes occur over wall-clock time ($t$) rather than episode progress ($k$), where wall-clock time signifies the actual elapsed time within the fixed duration $t \in [0, T]$. In existing works, at episode $k$, the agent rolls a trajectory and trains a policy before transitioning to episode $k+1$. In the context of the time-desynchronized environment, however, the agent at time $t_{k}$ allocates $\Delta t$ for trajectory generation and training, subsequently moves to the next episode at $t_{k+1}=t_{k}+\Delta t$. Despite a fixed total number of episodes ($K$), the agent accumulates different trajectories influenced by the choice of interaction times ($t_1,t_2,...,t_K$), significantly impacting the suboptimality gap of the policy. We propose a Proactively Synchronizing Tempo ($\texttt{ProST}$) framework that computes a suboptimal sequence {$t_1,t_2,...,t_K$} (= { $t_{1:K}$}) by minimizing an upper bound on its performance measure, i.e., the dynamic regret. Our main contribution is that we show that a suboptimal {$t_{1:K}$} trades-off between the policy training time (agent tempo) and how fast the environment changes (environment tempo). Theoretically, this work develops a suboptimal {$t_{1:K}$} as a function of the degree of the environment's non-stationarity while also achieving a sublinear dynamic regret. Our experimental evaluation on various high-dimensional non-stationary environments shows that the $\texttt{ProST}$ framework achieves a higher online return at suboptimal {$t_{1:K}$} than the existing methods.

Tempo Adaptation in Non-stationary Reinforcement
Learning
Hyunin Lee
Yuhao Ding' Jongmin Lee'
Ming Jin
Javad Lavaei*
Somayeh Sojoudi l UC Berkeley, Berkeley, CA 94709
Virginia Tech, Blacksburg. VA 24061
Chyunin, yuhao_ yuhao __iiondiinng___o Jongmin lee, lavaei, sooooodd edu
jinmingdvt.edi
Abstract
We first raise and tackle a "time synchronization" issue between the agent and the environment non-stationary reinforcement learning (RL), crucial factor hindering its real-world applications. In reality, environmental changes occur over wall-clock time (t) rather than episode progress (k), where wall-clock time signifies the actual elapsed time within the fixed duration t e [O, In existing works, at episode k, the agent rolls a trajectory and trains a policy before transitioning episode k+ 1. In the context of the -enedeesyncrooizee environment, however, the agent at time & allocates At for trajectory generation and training, subsequently moves to the next episode at t.+1 & + Åt. Despite fixed total number of episodes (K), the agent accumulates different trajectories influenced by the choice of interaction times (4,, (2, .... tx), significantly impacting the suboptimality gap the policy. We propose a Proactively Synchronizing Tempo (ProST) framework that computes suboptimal sequence {t1, ...... tx (= (t):k) by minimizing an upper bound on its performance measure, i.e., the dynamic regret. Our main contribution is that show that suboptimal {t]..K trades-off between the policy training time (agent tempo) and how fast the environment changes (environment tempo). Theoretically, this work develops suboptimal {1) function of the degree of the environment's non-stationarity while also achieving sublinear dynamic regret. Our experimental evaluation various high-dimensional non- stationary environments shows that the ProST framework achieves higher online return suboptimal {{) L:K than the existing methods.
Introduction
The prevailing reinforcement learning (RL) paradigm gathers past data, trains models in the present, and deploys them in the future. This approach has proven successful for stationary Markov decision processes (MDPs), where the reward and transition functions remain constant (1-3). However, challenges arise when the environments undergo significant changes, particularly when the reward and transition functions are dependent on time or latent factors 64, in non-stationary MDPs. Managing non-stationarity in environments is crucial for real-world RL applications. Thus, adapting changing environments pivotal in non-stationary RL.
This paper addresses a practical concern that has inadvertently been overlooked within traditional non- stationary RL. environments, namely, the time synchronization between the agent and the environment. We raise the impracticality of utilizing episode-varying environments in existing non-stationary RL
Corresoondigg authors. This work supported grants from ARO, ONR, AFOSR, NST, and the UC Noyae Initiative.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

000
10
Rewards
2000
2000
5000
Episodes
(a)
(b)
(c)
Figure I: (a) 2D goal reacher in a time-desynchronizee environment for one policy update, where the agent learns an inaccurate policy on an accurate model; (b) For three policy updates, the agent learns a near-optimal policy on an inaccurate model; (c) Rewards per episode in 2D goal reacher with four model-free baselines, where ProST-T" is one of our proposed methods.
research, as such environments do not align with the real-world scenario where changes occur regardless of the agent's behavior. In an episode-varying environment, the agent has complete control over determining the time to execute the episode kt, the duration of policy training between the episodes & and k + 1, and the transition time to the episode k + 1. The issue stems from the premise that the environment undergoes dynamic changes throughout the course of each episode, with the rate of non-stationarity contingent upon the behavior exhibited by the agent. However, an independent wall-clock time (t) exists in real-world environment, thereby the above three events now recognized as wall-clock time 4. training time At, and f2-1- The selection of interaction times (ta, 1x+1) has notable impact on the collected trajectories. while the interval t - ta establishes an upper limit on the duration of training (At). This interval profoundly influences the suboptimality gap of the policy. In the context of dinehdesynchronizeed environment, achieving optimal policy requires addressing previously unexplored question: the determination of the optimal time sequence (l, .2. (= (1).k) at which the agent should interact with the environment.
We elucidate the significance of the aforementioned research question through an example. Consider robot with the goal of reaching inside gray-shaded non-fixed target box, known the goal reacher (Appendix[A.] Note that the reward changes as the position of the box changes over time (Figure (a)). We begin by considering scenario in which the wall-clock time and episode synchronized, wherein the environment evolves alongside the episode. During each episode k, the agent rollouts trajectory and iteratively updates the policy N times, with the assumption that one policy update requires one second, and then the agent transitions to the subsequent episode k + 1. In conventional non-stationary RL environments, it evident that a larger value of N provides an advantage in terms of faster adaptation to achieve a near-optimal policy. However, regardless of the chosen value of N, the agent will consistently encounter the same environment in the subsequent episode. Now, consider a scenario in which the wall-clock time and episode are desynchronized. In this context, given fixed wall-clock time duration È [0, 10]. the agent is faced with the additional task of determining both the total number of interactions (denoted as the total episode K) and the specific time instances for these interactions 1:K. where 4s E [0, 10], 4-11 < 4 for 4k E [K]. Figure I shows an agent that interacts with the environment ten times, that is. [t) = {1, 2, ..., 10), and spends the time interval (te, 1 to train the policy, which consumes one second (K = 10, N 1). The high frequency of interaction (K = 10) provides adequate data for precise future box position learning (t 11), yet single policy update (N = 1) may not approximate the optimal policy. Now, if the agent interacts with the environment four times, i.c. {f1K== = {1, 4, 7, 10} (see Figure [b)) it becomes feasible to train the policy over a duration of three seconds (K = 4, N 3). A longer period of policy training (N = 3) helps the agent in obtaining near-optimal policy. However, limited observation data (K 4) and large time intervals (t E (11, 12, 13)) may lead to less accurate box predictions. This example underscores the practical importance of aligning the interaction time of the agent with the environment in non-stationary RL. Determining the optimal sequence {{) l:k involves a trade-off between achieving an optimal model and optimal policy.
Based on the previous example, our key insight is that, in non-stationary environments, the new factor tempo emerges. Informally, tempo refers to the pace of processes occurring in non-stationary

---

environment. We define environment tempo as how fast the environment changes and agent tempo as how frequently it updates the policy. Despite the importance of considering the tempo find the optimal It), the existing formulations and methods for non-stationarity RI. are insufficient. None of the existing works has adequately addressed this crucial aspect.
Our framework, ProST, provides solution to finding the optimal {t) F: by computing a minimum solution to an upper bound on its performance measure. It proactively optimizes the time sequence by leveraging the agent tempo and the environment tempo. The ProST framework is divided into two components: futurre policy optimizer (OPT,) and time optimizer (OPT,), and characterized by three key features: 1) it is proactive in nature as it forecasts the future MDP model; 2) it is model-bases as it optimizes the policy in the created MDP; and 3) it a synchronizing tempo framework as it finds a suboptimal training time by adjusting how many times the agent needs to update the policy (agent tempo) relative to how fast the environment changes (environment tempo). Our framework is general in the sense that it can be equipped with any common algorithm for policy update. Compared to the existing works 779, our approach achieves higher rewards and a more stable performance over time (see Figure (c) and Section 5).
We analyze the statistical and computational properties of ProST in a tabular MDP, which is named ProST-T. Our framework learns in a novel MDP, namely elapsed time-varying MDP, and quantifies its non-stationarity with novel metric, namely ame-elapsing variation budget, where both consider wall-clock time taken. We analyze the dynamic regret of ProST-T (Theorem I into two components: dynamic regret of o that learns future MDP model (Proposition [ and dynamic regret of OPT, that computes near-optimal policy in that model (Theorem 2 Proposition 2). We show that both regrets satisfy a sublinear rate with respect to the total number of episodes regardless of the agent tempo. More importantly, we obtain suboptimal training time by minimizing an objective that strikes a balance between the upper bounds of those two dynamic regrets, which reflect the tempos of the agent and the environment (Theorem 3. We find an interesting property that the future MDP model error of , serves as a common factor on both regrets and show that the upper bound on the dynamic regret of ProST-T can be improved by joint optimization problem of learning both different weights on observed data and a model (Theorem 4 Remark D
Finally, we introduce ProST-G. which is an adaptable learning algorithm for high- -igh-dimnssioall tasks achieved through a practical approximation of ProST. Empirically, ProST-G provides solid evidence on different reward returns depending on policy training time and the significance of learning the future MDP model. ProST-G also consistently finds a near-optimal policy, outperforming four popular RL baselines that are used in non-stationary environments on three different Mujoco tasks.
Notation
The sets of natural, real, and non- non-negative real numbers are denoted by N. R. and R., respectively. For finite set Z. the notation [Z] denotes its cardinality and the notation A(Z) denotes the probability simplex over Z. For X e N, we define [X]:=1,,,,--. X). For variable X, denote X as forecasted (or predictedd variable the current time, and X as the observed value in the past. Also, for any time variable t > O and A E N. we denote the time sequence {tl, 12,,,, t as (t) and variable X at time 4 as Xi. We use the shorthand notation X(a)(or X (k)) for Xt, (or X We use the notation {xhes to denote a sequence of variables (Ia, Ta+l ..... 22), and (#) to represent a sequence of variables {II,, Dta.ey.... Lt,). }. Given two variables x and y, let æ V y denote max( x y). and æ A y denote min(x, y). Given two complex numbers 21 and 22,
write 22 W(a1) if =2e = 21, where W is the Lambert function. Given a variable x. the notation a = O(b(x) means that C b(x) for some constant C > 0 that is independent of x, and the notation ((b(2:)) means that a 2 C b(x) for some constant C' > O that is independent of x. We have described the specific details in Appendix C.I
2 Problem statement: Desynchronizing timelines
2.1 Time-elapsing Markov Decision Process
In this paper, we study a non-stationary Markov Decision Process (MDP) for which the transition probability and the reward change over time. We begin by clarifying that the term episode is agent- centric, not environment-centric Prior solutions for episode-varying (or step-varying) MDPs operate
3

---

under the assumption that the timing of MDP changes aligns with the agent commencing new episode (or step). We introduce the new concept of time-elapsing MDP. starts from the wall-clock time t == 0 to t T. where T is fixed. The time-elapsing MDP at time É E [0. 7] is defined as M, AS H, Pt, Rt:7) where S is the state space, A is the action space, H is the number of steps, Pi:Sx - A(S) is the transition probability, R4 S x A - IR is the reward function, and y is a discounting factor. Prior to executing the first episode, the agent determines the total number of interactions with the environment (denoted as the number of total episode K) and subsequently computes the sequence of interaction times (t) I:K through an optimization problem. We denote ta as the wall-clock time of the environment when the agent starts the episode k. Similar to the existing non non-stationary RL framework, the agent's 's objective to learn a policy π tx :S + A(AA for all k. This is achieved through engaging in a total of K episode interactions, namely
M.. J. where the agent dedicates the time interval (te, tx+1) ) for policy training and then obtains a sequence of suboptimal policies { n p- *<K) to maximize non-stationary policy evaluation metric, dynamic regret.
Dealing with time-elapsing MDP instead of conventional MDP raises an important question that should be addressed: within the time duration [0, T.. what time sequence (t) I-K yields favorable trajectory samples to obtain an optimal policy? This question is also related to the following: what is optimal value of K, ie. the total number of episode that encompasses a satisfactory balance between the amount of observed trajectories and the accuracy of policy training? These interwined questions are concerned with an important aspect of RL, which is the computation of the optimal policy for given 4g- In Section 4 propose the ProST framework that computes suboptimal K* and its corresponding suboptimal time sequence (t*) 1:k- based on the information of the environment's rate of change. In Section 3 we compute near-optimal policy for (:k'.. Before proceeding with the above results, we introduce a new metric quantifying the environment's 's pace of change, referred as time-elapsing variation budget.
2.2 Time-elapsing variation budget
Variation budget [2 is a metric to quantify the speed with which the environment changes. Driven by our motivations, introduce new metric imbued with real-time considerations, named time-elapsing variation budget (ttt). Unlike the existing variation budget, which quantifies the environment's non-stationarity across episodes {1, 2, K), our definition accesses it across (ti, t2.,, ) where the interval At = 4 - & remains constant regardless of I E [K - 1]. For further analysis, define two time-elapsing variation budgets, one for transition probability and another for reward function.
Definition (Time- elapsing variation budgets). For a given sequence (1,, f2,.. } assume that the interval At is equal to the policy training time A.. We define two time- time-elapsing variation budgets (Ax))) and (Az)) as
K-1
K-1
Bx(A)) = Σ
sup supl|
Hupl|Ptnn (1)8,)) (1,,),,,,,,, B, = 8,0
Σ
sup Run (s,a) Reg (8, 8.a
To enhance the representation of real-world system using the time-elapsing variation budgets, we make the following assumption.
Assumption 1 (Drifting constants). There exist constants 1 and Or, Or 2 0 such that (cAr)))((*B (Ax) and (cAr))sc (,r))). We call Opp and or the dristing constants.
2.3 Suboptimal training time
Aside from the formal MDP framework, the agent can be informed of varying time-clapsing variation budgets based on the training time A, < (0, T) even within the same time-elapsing MDP. Intuitively, a short time A is inadequate to obtain near-optimal policy, yet it facilitates frequent interactions with the environment, leading
reduction in empirical model error due a larger volume of data, On the contrary, a long time A, may ensure obtaining a optrmoptimal policy but also introduces greater uncertainty in learning the environment. This motivates us to find suboptimal training time A E (0, 7) that strikes a balance between the sub-optimal gap of the policy and the empirical model error. If it exists, then A provides suboptimal K* = [T/A]] J. and suboptimal time sequence where f A (k- 1) for all & [K*]. Our ProST framework computes the parameter A;
4

---

then sets {tr tik and finally finds fituree near-optimal policy for time 1+1 at time G. In the next section, we first study how to approximate the one-episode-ahead suboptimal policy x 2..4 at time ls when {1) i is given.
Future policy optimizer
Future policy optimizer (OPT
Time Optimizer (OPT,)
Forecaster
Model Predicter
Agent Tempo
Env. Tempo
(()) E
9(kk) C g
018-w+1
01--1
Oic)
RL algorithm
Agent #o+1
M(k-w+1)
M(k-1)
M(k)
M M(++1)
M (K+1))
A K*
[
K+1
Elapsed time
Figure 2: ProST framework
For given tu and f.+1. the future policy optimizer (OPTx), as a module of the ProST framework (Figure _ computes near-optimal policy for the future time t&+1 time &a via two procedures: (i) it first forecasts the future MDP model of time f++1 at time & utilizing the MDP forecaster function, (ii) it then utilizes an arbitrary policy optimization algorithm within the forecasted MDP model OPT, to obtain future near-optimal policy -*14
3.1
MDP forecaster
Our ProST framework applicable an environment that meets the following assumption.
Assumption (Observable non-stationary set O). Assume that the non-stationarity of My, is fully charucterized by non-stationary parameter ou, O. Assume also that the agent observes noisy non-stationary parameter Oτ2 the end of episode e [K] (at time (x)-
It is worth noting that Assumption is mild, prior research in non-stationary RL has proposed techniques to estimate (1k) through latent factor identification methods [3) and our framework accommodates the incorporation of those works for the estimation of ((K)- Based Assumption 2 we define the MDP forecaster function g below.
Definition (MDP forecaster g f), Consider two function classes F and 9 such that O + O
and G S A O R (SS), where N. Then, for f(x) F and 9(k) G. define MDP forecaster time t& as (g ()) O x S x A R x A(S).
The function f(x). acting as a non-stationarity forecaster, predicts a non-stationary parameter ((k=1) at time lx+1 based on the last w observations given by the set (o) i.e., o(k+1) = ((())()-++,,)). The agent can determine the number of used historical observations, denoted as w, by leveraging information from the environment (Section 4). Then, the function 9()). acting
model predictor, predicts a reward (s a) and a transition probability P(k+1) a) for time (K01 i.e., (R<(+)): P((+1))+ (00),,, a, ŌR+1). 1). Finally, the OPT, generates the estimated future MDP M(K-1) (S,A, H, P ((K+1) R(x+1)=)) associated with time t.+1-
3.2 Finding future optimal policy
Now, consider arbitrary RL algorithm provided by the user to obtain optimal policy from the model M For given time sequence {t] the OPT, finds near-optimal future policy as follows: (1) observe and forecast, (2) optimize using the future MDP model.
(1) Observe and forecast. At time f., the agent executes an episode k in the environment M(x).
completes its trajectory T(k), and observes the noisy non-stationary parameter O(K) (Assumption
2h. The algorithm then updates the function f()) based the last observed parameters, and the
5

---

function 9(k) with input from all previous trajectories. Following these updates, the MDP forecaster time l predicts P(K+1) and R(b+1). thus creating the MDP model M(K-1) for time fg+1-
(2) Optimize using the future MDP model. Up until time 4++1, the agent continually updates the policy within the estimated future MDP M(K+1) for a given duration A,. Specifically, the agent rollouts synthetic trajectories 1(K+1) in M(++1). and utilizes any policy update algorithm to obtain policy ((--1)- Following the duration An. the agent stops the training by the time 44+1 and moves to the next episode ( with policy T()=1)-
We elaborate on the above procedure in Algorithm givee in Appendix F1
4
Time optimizer
4.1 Theoretical analysis
We now present our main theoretical contribution, which regarding the time optimizer (OPT)): computing a suboptimal policy training time A (the agent tempo). Our theoretical analysis starts with specifying the components of the OPT, optimizer, which we refer to as ProST-T (note that -T stands for instance in the tabular setting). We employ the Natural Policy Gradient (NPG) with entropy regularization [17] as a policy update algorithm in OPT,, We denote the entropy regularization coefficient as т, the learning rate 1). the policy evaluation approximation gap arising due to finite samples as 6, and the past reference length for forecaster f as w. Without loss second. The theoretical analysis is
of generality, we assume that each policy iteration takes conducted within a tabular environment, allowing us to relax Assumption [ which means that one can estimate non-stationary parameters by counting visitation of state and action pairs at time tg, denoted as m((e (8, a), rather than observing them. Additionally, we incorporate the exploration bonus term at time t into R(s=-)). denoted as (+)) as, which is proportional to Σ Σ (n(+) (s,a))-1/ and aims promote the exploration of states and actions that are visited infrequently.
We compute A by minimizing an upper bound on the ProST-T's dynamic regret. The dynamic regret of ProST-T is characterized by the model prediction error that measures the MDP forecaster's error by defining the difference between M(K+1) and M(K+1) through Bellman equation.
Definition 3 (Model prediction error). At time te. the MDP forecaster predicts a model M(++1) and then we obtain near-optimal policy z(k-1) based M(++1). For each pair (s,a), we denote the state value function and the state action value function of ((+1)) M(s+1) at step h [H] as ((())) (s) and (((++)) as, respectively. We also denote the model prediction error associated with time t.+1 calculated at time to as 4
(k+1) a), which is defined
(k+ (s, (R)))=(((A)))) (R(k+1) + (((t))) (K++)) - -(htt1) (s, 4
We now derive an upper bound on the ProST-T dynamic regret. We expect the upper bound to be likely controlled by two factors: the error of the MDP forecaster's prediction of the future MDP model and the error of the NPG algorithm due to approximating the optimal policy within an estimated future MDP model. This insight is clearly articulated in the next theorem.
Theorem 1 (ProST-T dynamic regret R). Let CH = EK- I
H-1 (I--1)
'n (s/ (1=11)(s( (k+1)
((+1)) and Th == .a _ap
EK- | where E K is a data-dependent error. For a given p (0, 1), the dynamic regret of the forecasted policies (K=11) J of ProST-TT - upper bounded with probability least 1 p/2 as follows:
R A ( 1, s RR + Rı1
where Ri r 7) - +C c V K 1,, Ri = -mn=Cn[44 Cn[AA]] (K - 1), and Cp, CH[[Ax] are some functions of p. Ag. respectively.
Specifically, the upper bound is composed of two terms: Ry that originates from the MDP forecaster error between M(K-1) and M( and Ry that arises due to the suboptimality gap between n (k++1) and 2(8+1), Theorem | clearly demonstrates that prudent construction of the MDP

---

forecaster that controls the model prediction errors and the selection of the agent tempo A. is significant in guaranteeing sublinear rates for R, and Ry,. To understand the role of the environment tempo in Ry, we observe that the MDP forecaster utilizes w previous observations, which inherently encapsulates the environment tempo. We expect the model prediction errors, at least in part, to be controlled by the environment tempo B A. so that a trade-off between two tempos can be framed as the trade-off between Ry and Rys. Hence, it is desirable to somehow minimize the upper bound with respect to An to obtain solution, denoted as A which strikes balance between Ry and Rtz.
4.1.1 Analysis of Ryr
A direct analysis of the upper bound Ry R2z is difficult since its dependence on K' is not explicit. To address this issue, we recall that an optimal A should be natural number that guarantees the sublinearity of both R, and Ryr with respect to the total number of episodes K. We first compute a set Nrr c N that includes those values of A that guarantee the sublinearity of Ri,, and then compute a set N, c N that guarantees the sublinearity of R, Finally, we solve for A in the common set N 1 n 11I.
Proposition 1 (Ar bounds for sublinear RTd). A total step H is given by MDP. For a number 0 such that H = 2 (log (FTmax )c), we choose 8, T, to satisfy 8 (c), T = Q (e/ log (Al) and n7 s (1 (1-7) /T, where Tmax and mmax the maximum reward of the forecasted model and the maximum reward of the environment, respectively. Define N1i==(1 | n>
1 log C1(x+2) n E N),
where C1 a constant. Then Ryr S 44eKK for all AT Nir-
As by-product of Proposition the sublinearity of Rn can be realized by choosing < O( 1)a-1) for any a [0, 1), which suggests that tighter upper bound on Rir requires a smaller and subsequently a larger Ar E Nrr. The hyperparameter conditions in Proposition I can be found in Lemma T and 2 in Appendix D.3
4.1.2 Analysis of Ry
We now relate R, to the environment tempo B(A,) using the well-established -tnsstationayy adaptation technique of Sliding Window regularized Least-Squares Estimator (SW-LSE) as the MDP forecaster [08 The tractability of the SW-LSE algorithm allows to upper-bound the model predictions errors 'H and i by the environment tempo extracted from the past w observed trajectories, leading to a sublinear R, as demonstrated in the following theorem.
K
Theorem 2 (Dynamic regret R, with f SW-LSE). For given e (0, if the exploration bonus constant and regularization parameter À satisfy = Q(SS) (H/p)) and X 2 1, then Ry is bounded with probability at least 1 - as follows:
H + Cp. VK
R, S. [rss(B(An))] )-
w C.
log 1 X
where C][B(A,)]= (1/(1-7) H) - (A+)) + (1 Hf (armaa)/(/ / ()) Bp(Ax), and Cj is constant on the order of (K).
For a brief sketch of how SW-LSE makes the environment tempo appear in the upper bound, we outline that the model prediction enrors upper-bounded by two forecaster errors, namely P(k+1) P(k-1) and R(x-1)- - RI)+), along with the visitation count (s, a). Then, the SW-LSE algorithm provides solution (P(R+1), R(k=1)) as closed form of linear combinations of past estimated values [P, R) (k-w+1ww) Finally, employing the Cauchy inequality and triangle inequality, we derive two forecasting errors that are upper- bouuded by the environment tempo. For the final step before obtaining a suboptimal A;, we compute N, that guarantees the sublinearity of Ry.
Proposition 2 (A, bounds for sublinear Rt). Denote B(1) the environment tempo when A = 1, which is a summation over all time steps. Assume that the environment satisfies (1) + B,(1))maxs(( -7) = o(K) and we choose w = O(KK - (C, Define the set Nj to be {n
K, e N). Then Ry is upper-bounded as Ri O (())(B(),)] (K (K-12 1)2/3 Vlog ((K ())CC((((((())) and also satisfies a sublinear upper bound, provided that A e Nr.
7

---

The upper bound on the environment tempo B(1) in proposition i aligned with our expectation that dedicating an excessively long time to a single iteration may not allow for an effective policy approximation, thereby hindering the achievement of sublinear dynamic regret. Furthermore, our insight that a larger environment tempo prompts the MDP forecaster to consider a shorter past reference length, aiming to mitigate forecasting uncertainty, is consistent with the condition involving w stated in Proposition]
4.1.3 Suboptimal tempo A
So far, we have shown that upper bound the ProST dynamic regret is composed of two terms Hy and Ry, which are characterized by the environment tempo and the agent tempo, respectively. Now, we claim that suboptimal tempo that minimizes ProST's dynamic regret could be obtained by the optimal solution A = arg min e (RT + -y7"", where R7 and Ryr denote the upper bounds Ri and F We show that A strikes balance between the environment tempo and the agent tempo since R7 is a non-decreasing function of A and R7 a non-increasing function of A.. Theorem 3 shows that the optimal tempo A depends the environment's drifting constants introduced in Assumption []
Theorem 3 (Suboptimal tempo AT). Let Kenv
(a,, va,) C;[B(1]] kagens
log - (K(l-)r)))((K-1))))) 11)(++))++))))) 2). Consider three cases: casel: Or V Op = 0, case2: Or V Vp 1,
case3: 0 a,,," v 0p or or V Vap > 1. Then A depends the environment's drifting constants as follows:
Casel: A T.
Case2: A log1-17 (ki kigens))
Case3: A = exp (-w[-
log (1g()))))))))))))))))()) max (am.aaa)
provided that the parameters are chosen so that
kAgent T7T )igar
4.2 Improving MDP forecaster
Determining suboptimal tempo by minimizing upper bound on Ry + Ryz can be improved by using a tighter upper bound. In Proposition] [ we focused on the Q approximation gap 5 to provide a justifiable upper bound on R, + Rt It is important to note that the factor 5 arises not only from the finite sample trajectories as discussed in (21. but also from the forecasting error between M(K+1)
and M(K+1)- It is clear that the MDP forecaster establishes lower bound å denoted 8min- which in turn sets a lower bound on and consequently on R, This inspection highlights that the MDP forecaster serves a common factor that controls both Ry and R,,, and further investigation to improve the accuracy of the forecaster is necessary for a better bounding on Ry + R1
Our approach to devising precise MDP forecaster is that, instead of selecting the past reference length w as indicated Proposition 2 we set w = k. implying the utilization of all past obser- additional optimization problem, resulting in
vations. However, we address this by solving a tighter bound on Ry. We propose a method that adaptively assigns different weights e RŞ to the previously observed non-stationary parameters up to time tg. which reduces the burden of choosing w. Hence, we further analyze Ry through the utilization of the Weighted regularized Least-Squares Estimator (W-LSE) 22 Unlike SW-LSE, W-LSE does not necessitate a predefined selection of w, but it instead engages in a joint optimization procedure involving the data weights and the future model (P(s-1): R(u To this end, we define the forecasting reward model error (s a) [((())1) R(x1)) (s,a) and the forecasting transition probability model error as (x, =1 (1((()+1) P(K+1)) (-1 +.a)
Theorem 4 (Ht, upper bound with f-W-LSE). By setting the exploration bonus (s))(s,)) (s) + yf
2(17) (f(s,a) a), it holds that
Ri 4H
27
H))
)
K-1
(s
mam K-1
Σ A)(3,)))
7 1 1-7
2(1 - k=1
8

---

Remark 1 (Tighter Ry upper bound with f W-LSE). If the optimization problem of H-LSE is feasible, then the optimal data weight q' provides tighter bounds for Di and A comparison to SW-LSE, consequently leading to tighter upper bound for Ry. We prove in Lemmas and in Appendix D.3 D.3that that ih and -iy are upper-boundee terms of Di and A..
4.3 ProST-G
The theoretical analysis outlined above serves motivation to empirically investigate two key points: firstly, the existence of an optimal training time; secondly, the role of the MDP forecaster's contribution to the ProST framework's overall performance. To address these questions, a practical instance, named ProST-G, which particularly extends the investigation in Section 4.2 ProST-G optimizes policy with the soft actor-critic (SAC) algorithm (23], utilizes the integrated autoregressive integrated moving average (ARIMA) model for the proactive forecaster f. and uses a bootstrap ensemble of dynamic models where each model is probabilistic neural network for the model predictor We further discuss specific details of ProST-G in Appendix F.3 and in Algorithm
propose
3
Experiments
We evaluate ProST-G with four baselines in three Mujoco environments each with five different non-stationary speeds and two non-stationary datasets.
(1) Enviromments: Non-stationary desired posture. We make the rewards in the three environments non-stationary by altering the agent's desired directions. The forward reward R/ changes R or R where R is the original reward from the Mujoco environment. The non-stationary parameter is generated from the sine function with five different speeds and from the real data A and B. K-
We then measure the time-elapsing variation budget by _x=1 [ok+1 environment settings can be found Appendix D.I.I
-ol-- Further details of the
(2) Benchmark methods. Four baselines are chosen to empirically support our second question: the significance the forecaster. MBPO the state-of-the the-art model-based policy optimization 24 Pro-OLS is policy gradient algorithm that predicts the future performance and optimizes the predicted performance of the future episode [7]. ONPG is an adaptive algorithm that performs purely online optimization by fine-tuning the existing policy using only the trajectory observed online (8) FTRL is an adaptive algorithm that performs gellow-the-regularin leader optimization by maximizing the performance on all previous trajectories (
6 Discussions
6.1 Performance compare
The outcomes of the experimental results are presented in Table The table summarizes the average return over the last 10 episodes during the training procedure. We have illustrated the complete training results in Appendix E.3 most cases, ProST-G outperforms MBPO in terms of rewards, highlighting the adaptability of the ProST framework to dynamic environments. Furthermore, except for data A and B, ProST-G consistently outperforms the other three baselines. This supports our motivation of using the proactive model-based method for higher adaptability in non-stationary environments compared to state-of-the-art model-free algorithms (Pro-OLS, ONPG, FTRL). We elaborate the training details in Appendix E.2
Table 1: Average reward returns
Speed B(G)
Swimmer-12
Halfchetth--2
Hopper-12
Pre-OLS
ONPG
FIML
MBPO
Pre87-0
Pro-ULS
ONPG
FTML
MIPP
ProST-G
Pre-OLS
ONPG
FTML
MBPO
F:48T.0
47.56
-55.27
-86.26
-31.65
108.42
63.14
2111
-3.99
-56.7
-21.40
-19.55
98.89
97.83
97.94
97.86
109.48
77.38
-0.23
-0.42
-0.27
0.10
2.11
-84.3 73
-85.42
-57.02
-30.50
-20.52
97.63
99.64
99:40
96.86
$n2.48
x:14
1.46
2.10
2,37
-018
0.57
-76
385 14
381 K3
-11.67
83.74
106.72
118.97
115.21
100125
111:10
B
4.88
1.79
4072
-1.20
0.19
0.30
-91.45
-95 96
385
-70.7%
76.56
80.8%
131.23
110.00
100.99
129.36

---

6.2 Ablation study
An ablation study was conducted on the two aforementioned questions. The following results support our inspection of Section 4.2 and provide strong grounds for Theorem
1 onde
ISA (yed)
2.5
6.5A paul
G-114
2.0
(-50
Rewards
G-122
Rewardg
HARRAA
Model erro
1.5
MARIMA
0.5
0.0
50
50
(a)
(b)
(c)
Figure 3: (a) Optimal ; (b) Different forecaster f (ARIMA, SA); (c) The Mean squared Error (MSE) model loss of ProST-G with four different forecasters (ARIMA and three SA) and the MBPO. The z-axis in each figure shows the episodes.
Suboptimal A" The experiments are performed over five different policy training times A e 2,, 4, 4,5). aligned with SAC's number of gradient steps G E {38, 76, 114, 152, 190). under fixed environment speed. Different from our theoretical analysis, we set A, = 1 with G = 38. We generate O₁ sin( (2m: A k/37), which satisfies Assumption (see Appendix E. The shaded areas of Figures 3 (a), (b) and (c) are 95 confidence area among three different noise bounds 0.01,0.02 and 0.03 in og. Figure
shows A, is close to the optimal G among five different choices.
Functions f.g. We investigate the effect of the forecaster I's accuracy on the framework using two distinct functions: ARIMA and simple average (SA) model, each tested with three different the values of w. Figure 3 3(b) shows the average rewards of the SA model with w (3, 5, 7] and ARIMA model (four solid line). The shaded area is 95 % the confidence area among 4 different speeds (1,2,3, 4). Figure 3 c) shows the corresponding model error. Also, we investigate the effect of the different model predictor g by comparing MBPO (reactive-model) and ProST-G with f =ARIMA (proactive-mode!) in Figure those from MBPO, empirically support that the forecasting component of the ProST framework can provide a satisfactory adaptability to the baseline algorithm that equipped with. Also, FiguresBibb and provide empirical evidence that the accuracy of f is contingent on the sliding window size, thereby impacting the model accuracy and subsequently influencing the agent's 's performance.
The high returns from ProST-G with f = ARIMA, compared to
7
Conclusion
This work offers the first study on the important issue of time synchronization for non-stationary RL. To this end, we introduce the concept of the tempo of adaptation in a non-stationary RL, and obtain suboptimal training time. We propose a Proactively Synchronizing Tempo (ProST) framework, together with two specific instances ProST-T and ProST-G. The proposed method adjusts an agent's tempo to match the tempo of the environment to handle non-stationarity through both theoretical analysis and empirical evidence. The ProST framework provides new avenue to implement reinforcement learning in the real world by incorporating the concept of adaptation tempo.
As a future work, it is important to generalize the proposed framework to learn safe guarantee policy in non-stationary RL by considering the adaptation tempo of constraint violations [25] 26 Another generalization is to introduce an alternative dynamic regret metric, enabling a fair performance comparison among agents, even when they have varying numbers of total episodes. Another future work to find an optimal tempo of the distribution correction in offline non-stationary RI., specifically how to adjust the relabeling function offline data in time-varying environment that is dependent on the tempo of the environment 27 28).
References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Toannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint
10

---

arXiv:1312.5602, 2013.
[2] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, L. Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484- 489, 2016.
[3] Gabriel Dulac-Arnold, Daniel Mankowitz, and Todd Hester. Challenges real-world reinforce- ment learning. In International Conference Machine Learning, 2019.
[4] Luisa Zintgraf, Sebastian Schulze, Cong Lu, Leo Feng, Maximilian Igl, Kyriacos Shiarlis, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: Variational -ayativ deep rl via meta-learning. Journal of Machine Learning Research, 22(289):1-39, 2021.
[5] Zhuangdi Zhu, Kaixiang Lin, Anil K. Jain, and Jiayu Zhou Transfer learning in deep reinforce- ment learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45 (11):13344-1333 13362, 2023.
[6] Sindhu Padakandla. A survey of reinforcement learning algorithms for dynamically varying environments. ACM Computing Surveys (CSUR), 54(6):1-25, 2021.
[7] Yash Chandak, Georgios Theocharous, Shiv Shankar, Martha White, Sridhar Mahadevan, and Philip Thomas. Optimizing for the future in non-stationary mdps. In International Conference on Machine Learning, pages 1414-144 1425. PMLR, 2020.
[8] Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In International Conference Learning Representations, 2018.
[9] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference on Machine Learning, pages 1920-1930. PMLR, 2019.
[10] Yuhao Ding, Ming Jin, and Javad Lavaei. Non-stationary risk-sensitive reinforcement learning: Near-optimal dynamic regret, adaptive detection, and separation design. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6):7405-7413, 2022.
[11] STEVEN BRADTKE.
Linear least-squares algorithms for temporal difference learning.
Machine Learning, 22:33-57, 1996.
[12] Yonatan Gur, Assaf J. Zeevi. and Omar Besbes. Stochastic non-stationary rewards. In NIPS, 2014.
problem with
[13] Xiaoyu Chen, Xiangming Zhu, Yufeng Zheng, Pushi Zhang, Li Zhao, Wenxue Cheng, Peng CHENG, Yongqiang Xiong, Tao Qin, Jianyu Chen, and Tie- Yan Liu. An adaptive deep rl method for non-stationary environments with piecewise stable context. In Advances in Neural Information Processing Systems, volume 35, pages 35449-35461, 2022.
[14] Biwei Huang, Fan Feng, Chaochao Lu, Sara Magliacane, and Kun Zhang. Adarl: What, where, and how to adapt in transfer reinforcement learning. In International Conference on Learning Representations, 2022.
[15] Fan Feng, Biwei Huang, Kun Zhang, and Sara Magliacane. Factored adaptation for non- stationary reinforcement learning. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors. Advances Neural Information Processing Systems, volume 35, pages 31957-31971, 2022.
[16] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34:24523-24534 2021.
[17] Sham M Kakade, natural policy gradient. Advances neural information processing systems, 14, 2001.

---

[18] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non- stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMIR, 2019.
[19] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 68(3):669-177) 1713, 2022.
[20] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pages 1843-1854, PMLR, 2020.
[21] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4): 2563-2578, 2022.
[22] Vitaly Kuznetsov and Mehryar Mohri. Theory and algorithms for forecasting time series. arXiv preprint arXiv: 05814, 2018.
[23] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[24] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
[25] Ming Jin and Javad Lavaci. Stability-certified reinforcement learning: A control-thcoretic perspective. IEEE Access, 8:229086-2299 2020.
[26] Samuel Pfrommer, Tanmay Gautam, Alec Zhou, and Somayeh Sojoudi. Safe reinforcement learning with chance-constrained model predictive control. In Learning for Dynamics and Control Conference, pages 291-303, PMLR, 2022.
[27] Jongmin Lee, Cosmin Paduraru, Daniel J Mankowitz, Nicolas Heess, Doina Precup, Kee-Fung Kim, and Arthur Guez. Coptidice: Offline constrained reinforcement learning via stationary distribution correction estimation. International Conference on Learning Representations, 2022.
[28] Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning. PMIR, 2021.
[29] Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse domains through world models. arXiv preprint arXiv:2301 0.11114414444 2023.
[30] Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi. and Tamer Başar. Model-free non-stationary rl: Near-optimal regret and applications in multi-agent and inventory control. arXiv preprint arXiv:2010.03161, 2020.
[31] Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for cmdps with non-stationary objectives and constraints. AAAI23/AAA23/AMM12 AAAI Press, 2023. ISBN 978-1-57335--880000
[32] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Kirkeby Fidjeland, Georg Ostrovski, Stig Petersen, Charlie Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Ku- maran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015.
[33] Timothy P Lillierap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. International Conference on Learning Representations, 2016.
[34] Wen Sun, Geoffrey Gordon, Byron Boots, and Bagnell. Dual policy iteration, Advances in Neural Information Processing Systems, 31, 2018.
12

---

[35] Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algo- rithmic framework for model-basee deep reinforcement learning with theoretical guarantees. International Conference on Learning Representations, 2019.
[36] Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie. Dynamic regret of policy optimization in non-stationary environments. Advances Neural Information Processing Systems, 33:6743-677555 6754, 2020.
[37] Yash Chandak, Scott Jordan, Georgios Theocharous, Martha White, and Philip S Thomas. Towards safe policy improvement for non-stationary mdps. Advances in Neural Information Processing Systems, 33:9156-9168, 2020.
[38] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 4506, 2021.
[39] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learming Theory, pages 2137- 2143. PMLR, 2020.
13


Reviews:
[{"review_id": "vFsZ5YNltg", "reviewer": "Reviewer_4AXz", "summary": "This paper proposes to look at non-stationarity in reinforcement learning (RL) from a new point of view. While previous approaches did not generally consider the practical implications of the time elapsed while learning a policy, the idea of the current paper is to consider exactly these implications. \n\nA trade-off is posed between spending time learning a stronger policy versus collecting more samples and learning a better model. After defining the problem, a practical solution is proposed. A forecaster fits a model of the process driving the non-stationarity, as well as the set a model of Markov decision processes (MDP) conditioned on it. An Rl algorithm, potentially any algorithm, is then plugged to the forecasted MDP and is optimised for several iterations. \n\nA theoretical analysis is conducted to demonstrate that, as anticipated, the regret drastically depends on the number of policy iterations. Fortunately, under certain conditions on the MDP and the algorithm, it is shown that a sub-linear regret can be obtained in the proposed framework. It results that there exists an optimal number of iterations which depends on the MDP itself. \n\nFinally, an empirical study demonstrates that a practical algorithm, based on the previous theory, is able to compete and outperform several baselines, in a range of non-stationary problems. Furthermore, an ablation study is proposed to illustrate the theoretical results.", "questions": "- Why is the framework considering non-stationarity inter-episode and not intra-episode? \n - Proposition 1 offers a sublinear regret with a condition that binds H and epsilon, this doesn't seem great for applications where H is fixed beforehand. What do the authors think about it? \n - What does \\Delta_t=1 correspond to in the experiments?  \n - Is there a simple way to compute a regret that compares to the best algorithm given a fixed time elapsed instead of number of episodes (K) fixed?\n - What would be the optimal number of iterations in that case? \n - In the experiments, why is the performance compared over the last 10 episodes only? What about the regret throughout learning?", "limitations": "Extra: \n - the text in figures 1.c) and 1.d) i9s too small \n - type line 302: \"the state-of-the-art model-based model-free algorithm\"", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Despite my rating in \"contribution\", this paper comes with an interesting idea. \nIn a practical problem, the time spent while learning a policy may be time not spent to sample new data.  It is an interesting theoretical perspective. As expected, the authors demonstrate that it is critical to take this time into account. I believe that this theory could have great implications and am not aware of previous works going in the exact same direction.\n\nThe practical algorithm follows a simple idea, which I like. It comes with both theoretical and empirical achievements. \n\nThe theoretical analysis is helpful and and well conducted. I have not checked demonstrations in detail, but many proof steps are classic in the literature.  The conclusion of the theoretical analysis is great: \"tempo\" in the MDP and in the algorithms should be in harmony. \n\nThe experimental section is concise but holds enough value to underline the validity of the framework.", "weaknesses": "My rating for the \"contribution\" results from my doubts about the definition of the framework. Despite originating from an interesting idea, I question the following points:\n - The non-stationarity is not defined clearly enough. An agent is placed in an MDP where it can either sample a trajectory or train its policy. Why wouldn't the MDP change during the trajectory? If the agent can choose when to sample data in a stationary MDP, and that the non-stationarity is bounded as in line 119, it seems that too much control over the non-stationarity is offered to the agent.\n - The terms B_p(G) and B_r(G) are not given more details in the main paper. I understand that they satisfies the equation of line 119, but what is the meaning of Delta_t=1? This is also important to understand the experiments, is a step of non-stationarity corresponding to Delta_t=1 and therefore to an iteration of NPG? \n - I am concerned about the result of Theorem 2. I understand that, for a fixed K, there should be an optimal tempo for the policy iteration. But I miss a result for an agent that would have a budget in terms of time. How does a well trained agent sampling less trajectories compare to a poorly trained agent sampling more trajectories in the same time? The optimal tempo could be impacted by these considerations. \n - A related comment about the regret. In the regret formula, the reference is the optimal value function in MDP k, that is, at sampling times synchronised with the algorithm. What if the algorithm is compared to an optimal policy at different tempo ? \n - These two previous comments can be gathered as follow: what if the agent is compared to any agent acting in the same amount of time? \n - I expect that the training takes more time as more data is collected. Delta_t could refer to the longest time of them all, but how can the agent be sure that Delta_t has elapsed always before sampling? This is related to my comment on the agent having an impact on the non-stationarity of the environment. \n - When the agent optimises its policy, as explained in 3.2, paragraph 2), a synthetic trajectory is rolled out. What if the rollout has a comparable time with respect to sampling a trajectory. Shouldn't the number of rollouts add to the time elapsed? In expectation it is irrelevant but it becomes necessary for a high-probability results. Similarly, why is the result of Proposition 3, case 1, suggesting G=\\infty? Only a single trajectory is needed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments and the followings are our answers to the weakness, questions that the reviewer raised.\n\n$\\textbf{1-1) W1,Q1:  validity of inter-episode changing MDP}$\n\nWe have defined the non-stationary as changing across the episode and keeping stationary during the episode (line 99). We have two reasons why we think episode-varying MDP is still reasonable for our paper. First, episode-varying MDP could be regarded as a discrete change for a certain interval for an infinite Horizon case, which supports our work still solves non-stationary environments. Second, most related theoretical works assumed step-varying MDP, but a lot of related empirical works on complex non-stationary environments assumed MDP changes across the episode. For more details, please refer to recent non-stationary RL papers that change inter-episode : [9,11,13,18].\n\n$\\textbf{1-2) W1 : Issue of $B_p(c\\Delta_t)=c^{\\alpha_p}B_p(\\Delta_t)$ provides too much control on the agent}$ \n\nThe environment property (line 119) is the assumption that is given as prior, not a property that the agent can control ($c, \\alpha_p$ is given ,not choosen by agent). The only parameter that the agent choose is $\\Delta_t$, which represents a real-world sceniro that the agent learns the environment model based on observations only from $K$ interaction times $[t_1,t_2,..,t_K]$ where $\\Delta_t = t_{k}-t_{k-1}, \\forall k \\in [K]$. Different interaction times yields different observations, which leads to different learned model. \n\n$\\textbf{2) W2,Q3 : lack of details on time elapsing variation budget, meaning of $\\Delta_t=1$}$\n\n$\\Delta_t=1$ means the agent executes an episode for every one second, which means (k)th episode and (k+1)th episode’s interval is a second.In Figure 3-(a),  $\\Delta_t = [1,2,3,4,5]$ means how much the agent skips the environment’s episode (we have added additional information in line 325~326). Also $\\Delta_t$ means training time which is proportional to gradient steps of NPG, we set $\\Delta_t=1$ corresponds to $38$ iterations.\n\n$\\textbf{3) W 3,4,5 : the clarity of theroem2}$\n\nBefore, we emphasize our work’s main contribution is interpreting the non-stationary MDP as “wall-clock time” goes by, not as “episode” goes by, and shifting the perspective from episode to time is a more realistic setting that matches with non-stationary RL’s motivation: RL for real-world application. Raising this issue recalls our new problem setting stated in the introduction (line 2 $\\sim$ 5). This new setting requires to solve an additional problem: how to choose the optimal K-length time sequence that the agent interacts with the environment?”. With this respect, our main theoretical result is determining the optimal $K-$ time sequence by optimal training time, and we propose a PTM framework to find optimal training time.\n\nNow, we answer your understanding of “fixed K, the optimal tempo exists”. Yes, the optimal tempo exists, but it's not for the fixed episode(K), but for fixed “time duration”. For better understanding, recall the example of the introduction. Let’s say for fixed time duration 0[s]$\\sim$15[s], robot A executes episodes for every 1 second, [0,1,..,15], and between time $t,t+1$, the agent trains the policy. Robot B executes episodes every 2 seconds [0,2,..,14] and between time $t,t+2$, the agent trains the policy. Let’s assume one policy update takes 1 second. Then, robot A can update one time, and robot B can update two times. Robot A interacts with the environment for 15 episodes and updates policy one time, which has more information about the environment but has an uncertain approximate optimal policy. Robot B interacts with the environment for 7 episodes and updates the policy two times, which has less information about the environment but has a better approximate optimal policy than robot A. \n\n$\\textbf{4) W 6: relationship between training time and the amount of data}$\n\nWe want to answer data amount in Buffer does affect training time. We have defined training time as the time that takes one iteration of training, and in theoretical analysis, one iteration of policy update is same as one gradient step of the NPG algorithm. We partially admit that the batch size of the trajectory data could affect the “policy update for one gradient step”, which is same as B_p(1) and B_r(1), but “G” policy iteration does not change if we fix the batch size of the trajectories for policy update.  \n\n$\\textbf{5) W7: including rollout time to traning time, the meaning of $G=\\infty$}$\n\nWe have included the sample complexity (in Appendix: Lemma3) and the approximation gap $\\delta$ due to a finite data sample. Line 216 $\\sim$ 217 shows how Lemma3 interleaves with our Propositoin1. Small $\\epsilon$ enables tighter upperbound for $R_{Alg_\\tau}$, but also requires the approximation gap $\\delta$ to be small. Small approximation gap $\\delta$ requires large sample complexity by Lemma3. This supports the point that you raised: “In $\\sim$ results.”. However, we have not included “data collection time” in the training time, but want to claim that it does not harm our works since we have defined the training time as the time that consumes one policy iteration. \n\nAlso, note that $G=\\infty$ for the case of max(alpha_r, alpha_p) =0 matches with our intuition, since max(alpha_r, alpha_p) =0  corresponds to “stationary environment” (line 120 $\\sim$ 121: typo on the paper, \\alpha_p=\\alpha_r=0 is stationary environment) and within the stationary environment, large policy iteration guarantees closer optimal policy. \n\n$\\textbf{6) Q2}$\n\nIn proposition 1, we think word “given” in line 213 makes misunderstanding, What we meant by was “we choose \\epsilon >0 that satisfies H > (terms)”. Therefore, H is fixed ever since the MDP is given, and for given H, we choose \\epsilon. \n\n$\\textbf{7) Q4,5}$\n\nDefinition of dynamic regret requires obtaining the optimal policy at each episode. In complex environment, it is hard to define what is “optimal policy”.\n"}, {"review_id": "4iAS1pPeSQ", "reviewer": "Reviewer_2jp7", "summary": "This paper presents a solution to nonstationary RL issues through a model-based framework called Tempo-Control (PTM). Specifically, the authors identify a new trade-off in nonstationary RL problems: the trade-off between learning an accurate model and learning an optimal policy. Based on this, a new framework is designed to allow the agent to find an appropriate tempo for adaptation. The authors provide theoretical analysis for the tabular version of the framework and a strategy for complex RL scenarios. Empirical evaluation results confirm the effectiveness of the scheme as well as its theoretical optimality properties. Overall, this paper offers insightful analysis on nonstationary RL problems and rigorous theoretical study on the method. I am inclined to give an \"accept\" rating.", "questions": "I have included the questions in the above section. ", "limitations": "The authors have given a detailed analysis of the limitations in the paper. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "[**About the framework's motivation**] The author's analysis of the trade-off between adaptation tempo and environment tempo is quite insightful. Additionally, the critique of the existing three research lines in nonstationary RL could provide inspiration to the field of nonstationary RL or RL in general.\n\n[**About the theoretical analysis**] The paper offers rigorous theoretical analysis for the tabular version, providing solid theoretical guarantees for subsequent applications.\n\n[**About method design**] The modeling method for adaptation tempo and environment tempo is clear and simple, offering strong reproducibility and portability.\n\n[**About experiments**] The experiments use common nonstationary (deep) RL benchmarks, and the results are quite good, with a significant margin over the baselines. Furthermore, the ablation studies also confirm the previous theories on optimality.", "weaknesses": "Note: Most of the weaknesses listed below are more like questions, discussion points, or suggestions, rather than outright flaws. Any clarifications provided by the authors would be very welcome and appreciated. Given the limited time for rebuttal, it is not necessary to fully supplement experiments for comparison with these papers. Some clarifications and discussions on these methods would be greatly appreciated.\n\n[**About the latent variable**] The authors assume that the non-stationary variable $\\hat{o}_k$ is observable, but in real complex scenarios, it is challenging to observe the non-stationary variable. Additionally, certain specific assumptions are required about this latent variable (such as the function of the latent variable's change with time, dimensions, etc.). Could the authors provide more clarification on this point?\n\n[**About the presentation**]The authors might consider placing PTM-G after the third section and moving Algorithm 3 from the appendix to the main text. This could help readers better understand the overall framework design and flow.\n\n[**About the experiment**] In Fig. 3 (b-2), it seems that convergence has not been reached at the end; consider providing a longer range for the x-axis. Also, the x-axis is not labeled in Fig. 3.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{[About the latent variables : assumption validity]}$ \n\nThanks for pointing out the validity of the assumption. \n\nFirst, we would like to mention the biggest reason for the observable $\\mathcal{O}$ assumption is not to increase the gap between theoretical analysis (PTM-T framework) and solid experiment results (PTM-G framework). Please note that most relevant existing works train a probabilistic network that encodes the $1 \\sim k$ episodes’ trajectories  (which represents the $1 \\sim k$ episodes’ environment)  into the latent space (which represents the non-stationary variables), and learn network parameters by bayesian method, then infer the future non-stationary variable from the latent space [9-12]. The problem with Bayesian inference is that its posterior distribution is intractable. Within this sense, We have not used the existing method since the intractability of the practical algorithm makes the gap between the theoretical analysis and the practical algorithm larger.\n\nAlso, we would like to recall that assumption 1 is not necessary for the PTM-T framework, which means we $\\textit{estimate}$ the non-stationary variables, then predict the future variables.  (please refer to line 186 $\\sim$ 187). The practical algorithm, PTM-G framework, exploits the advantage of assumption 1 to forecast the future variables (future MDP model) to fully support the ablation study. Throughout the paper, we stated the theoretical analysis on “improving forecaster accuracy”(section 4.1.2) to emphasize that “MDP forecaster” serves a significant role in PTM-framework, and have done experiments to support its theoretical importance (Figure 3-(b-1), (b-2)). We have thought inferring the non-stationary variables makes the ablation study that checks the performance of the MDP forecaster to be unclear (Figure 3-(b-1), (b-2)) since it takes $w$ past observations.    \n \n$\\textbf{[About the presentation]}$ \n\nThanks for pointing out the location of the PTM-G algorithm. We will modify it later on if we get accepted. \n\n$\\textbf{[About the experiment : Figure 3-(b-2) issue]}$\n\nThanks for pointing out the issue of convergence. Does to the limited time of the rebuttal, we have not attempted to do additional experiments. However, we can certainly claim that we have rolled 200 episodes, and the model error except f=ARIMA increases as the episode goes by.\n"}, {"review_id": "g63PTkIzJd", "reviewer": "Reviewer_EXsm", "summary": "This work introduces the tempo of adaptation in a non-stationary RL problem. The authors provide Proactive Tempo control Model-based (PTM) framework, and two specific instances PTM-T and PTM-G. By adjusting the tempo of the algorithms, the proposed algorithm can match the tempo of the environment to address non-stationarity. This claimed property is demonstrated by both theoretical analysis and empirical results. The proposed PTM framework helps the RL algorithm to be implemented in real-world settings. The authors show that the PTM framework achieves a higher online return than the existing methods and provides empirical evidence of the existence of an optimal algorithm tempo with the comprehensive experimental evaluation of various Mujoco tasks.", "questions": " ", "limitations": "The authors adequately addressed the limitations", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "(1) Interesting topic for real-world applications: This paper focuses on a practical setting for non-stationary RL by introducing a “time-elapsing variation budget”, which not only measures non-stationarity but also considers actual time taken. This setting is common and has great potential in real-world applications, and this work will encourage more interest in this direction.\n\n(2) Solid theoretical analysis: This paper provides a dedicated mathematical formulation for the tasks and provides a detailed theoretical analysis and discussion of the proposed methods under the tabular settings. They also provide a discussion on more general cases in the supplementary material.\n\n(3) Comprehensive experimental evaluation: This work provides comprehensive experimental results both with sufficient baseline methods and testing tasks to demonstrate the strength of their work.\n", "weaknesses": "(1) Complicated symbolic notation: The author uses too many fancy symbols for notations that are hard to identify, write, pronounce, and memorize. I would be more than happy to see a simplified version, and I believe by reducing the symbolic complexity, this paper will be much easier to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{1) W1: complicated symbolic notation}$\n\nThanks for pointing out that the paper contains too many notations and those make readers follow up the paper hard. We will reduce notations and make theorems much more straightforward in the camera-ready version if we get accepted. \n\n$\\textbf{2) Regarding with low-confidence score: clarification of main contribution}$\n\nBesides your constructive comments, we also appreciate your low-confidence score and we understand the score since the message of our paper is not fully clear to the reviewer. Within this sense, we would like to clarify the motivation, main contribution and how our theoretical analysis is related, and how our experiments support those.\n\nFirst, We would like to emphasize that our work’s $\\textbf{main contribution}$ is interpreting the non-stationary MDP as “$\\textit{wall-clock time}$” goes by, not as “$\\textit{episode}$” goes by, and we claim shifting the perspective from episode to time is a more realistic setting that matches with non-stationary RL’s motivation: RL for real-world application. Raising this issue recalls our new problem setting stated in the introduction (line 2 $\\sim$ 5). This new setting gives rise to solving an additional problem: how to choose the optimal $K-$length time sequence that the agent interacts with the environment?”. With this respect, our $\\textbf{main theoretical result}$ is that we determine the optimal K-length interaction time sequence by finding an optimal training time of the agent. Within this sense, we propose the PTM framework to 1) find optimal training time by forecasting model-based method and 2) claim our method yields a better online return, which 1) is supported by Fig 3-(a) and 2) is supported by Table 1. \n\nTherefore, we claim  $\\textbf{we unearth a hidden assumption}$ that the agent and the environment should have independent timelines, and our proposed method finds how to adapt two timelines theoretically and also proves empirically, which supports we have different problem-setting and different purpose of the algorithm aside from existing the non-stationary RL methods.\n\nWe also brought up our motivation and main contribution on “global response” \n"}, {"review_id": "ZEsnagISLb", "reviewer": "Reviewer_WHPE", "summary": "The paper introduces a novel framework for handling non-stationary environments in reinforcement learning (RL) called Proactive Tempo-control Model-based (PTM) framework. The authors argue that in non-stationary environments, an additional factor emerges alongside the classical exploration-exploitation trade-off: the tempo of adaptation. The PTM framework is designed to adjust the policy-update tempo (algorithm tempo) to match the environment tempo. The authors propose two instances of the PTM framework, PTM-T and PTM-G, and provide theoretical analysis and empirical evidence to support their claims.", "questions": "- In proposition 3, how are the different cases of environment tempos reflected in the experimental setting?\n- In Figure b-2, the learning curves of the algorithms seem to be in their early stages. Why not plot the complete curve until convergence?", "limitations": "- The writing and logic of this paper is not good enough, making it hard for readers to follow. \n- There is a gap between theory and practice, and there are no detailed experimental demonstrations for theoretical conclusions.\n- Additionally, there is a lack of experiments comparing with the recent SOTA baselines. \n- Although the author proposes an interesting perspective on \"adapt to adapt,\" fundamentally it does not differ from works on actively learning changes in MDPs. \n\nI suggest that the author reorganize the use of math symbols and consider simplifying unnecessary theoretical analysis in the main text. Furthermore, provide a more detailed explanation of the PTM-G algorithm in Section 4.2 and supplement with additional experiments as mentioned above.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The concept of tempo adaptation in non-stationary RL environments is an interesting approach.\n- The proposed PTM framework could have implications for the field of RL, particularly in real-world applications where environments are often non-stationary.\n- The paper provides theoretical analysis for the proposed method.", "weaknesses": "- Although the author tells an interesting story about \"adapt to adapt,\" the proposed PTM algorithm essentially attempts to learn a gradually changing MDP, which does not seem to have any fundamental difference from some previous works like [1][2].\n- There is a significant gap between the theoretical results of the paper and the practical methods. Although the author has used a considerable amount of theoretical analysis in the main text to try to demonstrate that PTM method can achieve smaller dynamic regret with sublinear iterations, only simple performance curves are shown in the experimental section without further demonstrating the relationship between dynamic regret and iterations, which should explain the principle of improvement in the PTM algorithm.\n- As cited and discussed by the author (line 29-30), some previous works have also been able to effectively address non-stationarity. However, in the selected baseline, MBPO is just a standard model-based RL algorithm without specific optimization for non-stationarity. Additionally, other baselines seem to be relatively outdated. Why not compare with newer references like [3], etc?\n- This paper uses a lot of complex and scattered math symbols, making it confusing for readers when reading the theoretical part. For example, in line 207, the author uses an icon symbol to represent \"Alg\". In line 264, the author uses diamond and square symbols to represent $r$, $p$ and $\\mathcal{P}$, etc. Why not simply use the letters or with some subscriptions directly? In some contextual formulas (e.g. formula 4.2, 4.3, 4.4, 4.6 and line 271-276), the author interchangeably uses these icon symbols and original letters. When readers read through this paper, they may need to repeatedly recall what these complex symbols actually represent.\n\n[1] Deep reinforcement learning amidst continual structured non-stationarity. Xie, et al. (ICML 2021)\n\n[2] Meta-reinforcement learning by tracking task non-stationarity. Poiani, et al. (IJCAI 2021)\n\n[3]Factored adaptation for non-stationary reinforcement learning. Feng, et al. (NeurIPS 2022)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive comments and the followings are our answers to weakness, question that the reviewer has raised.\n\n$\\textbf{1) W1: clarity of contribution and difference from related works}$ \n\nFirst, We would like to emphasize that our work’s $\\textbf{main contribution}$ is interpreting the non-stationary MDP as “wall-clock time” goes by, not as “episode” goes by, and shifting the perspective from episode to time is a more realistic setting that matches with non-stationary RL(NSRL)’s motivation: RL for real-world application. Raising this issue recalls our new problem setting stated in the introduction (line 2 $\\sim$ 5). This new setting gives rise to solving an additional problem: how to choose the optimal $K-$length time sequence that the agent interacts with the environment?”. With this respect, our $\\textbf{main theoretical result}$ is that we determine the optimal K-length interaction time sequence by finding an optimal training time of the agent. Within this sense, we propose the PTM framework to 1) find optimal training time by forecasting model-based method and 2) claim our method yields a better online return, which 1) is supported by Fig 3-(a) and 2) is supported by Table 1. \n\nTherefore, we claim  $\\textbf{we unearth a hidden assumption}$ that the agent and the environment should have independent timelines, and our method finds how to synchronize two timelines theoretically with empirical results, which supports we have 1) different problem-setting and 2) different purposes of the algorithm aside from existing the non-stationary RL methods.\n\nAlso, please note that the fundamental goal of NSRL methods is to learn gradually changing MDP [p1]. So if your understanding of our proposed method well matches with learning a gradually changing MDP, then it means the proposed method has solved the standard NSRL goal, which support the credibility of our work. \n\n[p1] Milano et al, 2021, State of the Art on: Non-Stationary Reinforcement Learning\n\n$\\textbf{2) W2: gap between theoretical results and a practical method}$ \n\nWe would like to provide two points that how theoretical results (PTM-T) are closely related to the practical algorithm (PTM-G). \n\nBefore, we would like to recommend interpreting theoretical analysis not as “theoretical justification or theoretical proof” of the practical algorithm, but rather as “theoretical grounds or insights”, and experiment on ablation study (subsection [6.2]) supports this. Our theoretical analysis can be grouped into two main contributions: 1) the subsection[4.1.1] highlights the existence of optimal tempo, 2) subsection [4.1.2] highlights improving forecaster accuracy is important in PTM framework. \n\nFirst, the motivation of theoretical analysis on “the existence of optimal tempo” is to support our new problem-setting: additional factors, tempo, arise in a non-stationary environment, and how to adapt the policy-update tempo to the environment tempo is significant. (line 55 $\\sim$ line 61). This “optimal tempo existence” is supported by the experiment result in Figure 3-(a) and line 323 $\\sim$ line 329. \n\nAlso, the motivation of theoretical analysis on “improving forecaster accuracy” is to emphasize “MDP forecaster” serves a significant role in obtaining accurate optimal interaction time sequence. To be specific, finding the optimal tempo by taking minimum of the upperbound of $\\mathfrak{R}_\\mathcal{I} + \\mathfrak{R}_A$ still leave room for an improvement that tighter upperbound provides a much more accurate optimal tempo. \n\nIn proposition 1, let's focus on the factor $\\delta$ to provide a compact representation of the dynamic regret of PTM-T (Theorem 1). We emphasize that the approximation gap $\\delta$ emerges not only due to finite sample trajectories (Lemma 3) , but also the forecasting error between $\\mathcal{M}^{k+1}$ and $\\widehat{\\mathcal{M}}^{k+1}$. It's straightforward since MDP forecaster yields a lowerbound of $\\delta$ as $\\delta_{\\text{min}}$ and $\\delta_{\\text{min}}$ provides a lowerbound on $\\epsilon$ and subsequently a lowerbound on $\\mathfrak{R}_\\mathcal{I}$. This shows MDP forecaster serves as a common factor that controls both $\\mathfrak{R}_I$ and $\\mathfrak{R}_{A}$.\n\nSecond, the experiment results of PTM-T which exactly match the setting of theoretical analysis are stated in the introduction (in Figure 1-(c)) to utilize its results for motivation.  \n\n$\\textbf{3) W3 : appropriateness of baseline algorithms}$ \n\nFirst, we would like to claim that we used MBPO as baseline to compare the result between MBPO and PTM-G. (line 335 $\\sim$ 338). PTM-G is a model-based policy optimization framework. The difference is that MBPO predicts stationary model and PTM-G predicts the non-stationary model by MDP forecaster. This structure difference clearly supports that comparing MBPO and PTM-G can highlight the forecaster performance of the PTM-G. Please note that the role of the forecaster is significant as we mentioned in section [4.1.2], and we have come up with theoretical soundness (Theorem3, Remark1) and experimental soundness (Figure 3-(b-1),(b-2)) to support its significance.\n\nSecond, We provide $\\textbf{why} we have selected the three baseline algorithms: ProOLS, FTML, ONPG. We claim those are appropriate baselines to compare the effectiveness of PTM-G. To be specific, ProOLS predicts future policy evaluation based on past observation data but it is a model-free method. ProOLS and PTM-G both shares the “forecasting” component but ProOLS is a model-free method and PTM-G  is a model-based method. Comparing ProOLS and PTM-G can highlight the effect of the \"model-based” approach of PTM-G. Other two were also baselines in the non-stationary RL works [13] \n\n$\\textbf{4) Q1}$ : The environment tempo's corresponding scenarios are in line 120 $\\sim$ 121.  $\\alpha_r=\\alpha_p=0$ is a stationary environment (typo on main paper)\n\n$\\textbf{5) Q2}$ : we rolled 200 episodes. The model error except f=ARIMA increases as episode goes by.  \n"}, {"review_id": "WVtAuYcJC0", "reviewer": "Reviewer_3oD2", "summary": "This paper studies reinforcement learning in non-stationary environments. The authors propose a proactive tempo-control model-based (PTM) framework to adjust how often the learning agent to adjust its policy to the environment tempo. Two different variants of PTM are considered: The PTM-T variant uses natural policy gradient as the base algorithm and achieves sublinear dynamic regret. The regret bound is further improved when the forecaster assigns different weights to the observed data. The second variant PTM-G is more empirical and is shown to outperform four existing baselines on three different Mujoco tasks.", "questions": "Please consider first answering my questions in the “Weaknesses” section. The additional questions listed below are comparably not major. \n\n1.\tHow does the environment tempo formulation deal with the difference between the frequency of environment non-stationarity (i.e., frequent, slow, gradual variations) and the magnitude of non-stationarity (i.e., abrupt variations). \n\n2.\tIn Eq (2.1), the authors measure the transition variations in terms of the infinity-norm, which is different from the more popular metric of 1-norm in existing non-stationary RL works (e.g., Cheung et al., 2020). I wonder why such a difference occurs.\n\n3.\tSince the authors mentioned the word “meta-algorithm”, I wonder how the proposed method is related to meta-learning?", "limitations": "The limitations are briefly discussed in the conclusions section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper studies an interesting and important problem in reinforcement learning: The quick adaptation of the learning algorithm to a non-stationary environment. The proposed solution of proactive tempo-control is interesting and novel as far as I know. The theoretical derivations look solid and convincing. This paper also includes a decent amount of numerical results with ablation studies in addition to the theoretical contributions, which also looks encouraging.", "weaknesses": "1.\tWhile I am sure that the authors have a lot of interesting results to share, the writing of the paper fails to convey some of the important ideas, which prevents me from fully appreciating the contributions of the work. The presentations of the methodology and results in the paper are somewhat unclear and sometimes can be confusing. There are a few things that are unclear to me and can certainly be improved:\n\na. The main theoretical results are not clearly stated. The authors build up the theoretical results through a series of theorems and propositions, but it is hard to keep track of what the strongest results are, given that there are numerous results presented. The reader needs to combine a few theorems to see the exact form of the dynamic regret bound, which is not reader-friendly. The authors could consider providing the strongest, take-home results of the work in one theorem. \n\nb. The main text of the paper is not very self-contained, which adds to the confusion. The definitions of some notations and even algorithm descriptions (e.g., Algorithms 1 and 2) are deferred to appendices, which really should have been included in the main text. My suggestion is that some of the intermediate results in Section 4 can be moved to the appendices to allow more space for many other sections. \n\n2.\tThe main setup of the problem formulation is a bit unclear to me. The authors mentioned the main “trade-off” between interacting with the environment more often to gather data vs. performing more policy optimization using collected samples. Why is it even a trade-off and why can’t we do both of them at the same time? The only reason that I can think of is computation complexity, which is less critical and was not even discussed in the paper. \n\n3.\tIt is unclear to me how the problem formulation is related to the standard setup in non-stationary RL, e.g., [Cheung et al., 2020]. The definition of the time elapsing variation budget is a bit ad hoc and should be better explained. It is also quite confusing that the formulation considers both a finite-horizon $H$ and a reward discounting factor $\\gamma$, while usually people only choose one of the two. The definitions of the values functions are also missing (which are included in the appendix but should definitely have been included in the main text).\n\n4.\tThe assumption that $B_p(\\Delta_t) = c^{\\alpha_p} B_p(\\Delta_t)$ seems a bit ad hoc to me and probably needs more justification. Similarly, it is also unclear what Assumption 1 means and the authors could provide some examples on how it is satisfied. \n\n5.\tIn the simulations, it seems that some of the selected comparison baselines are originally designed for the stationary environment. It would be unfair to compare with these algorithms in non-stationary environments. I wonder how the proposed method compares to some existing solutions specifically designed for non-stationary RL (e.g., some simple sliding-window or restarting-based algorithms). \n\n6.\tA related work section is missing (and again is included in the appendix but should have been included in the main text to be self-contained). There are also a few important closely related works that are not discussed in the references. Just to name a few that I am aware of:\n\na.\tWei, Chen-Yu, and Haipeng Luo. \"Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.\" Conference on learning theory, 2021.\n\nb.\tMao, Weichao, et al. \"Near-optimal model-free reinforcement learning in non-stationary episodic mdps.\" International Conference on Machine Learning, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{1)  W 1,2: clairty of main contribution and meaning of tradeoff}$\n\nThanks for pointing out the clarity of the main theoretical results and corresponding contribution and the meaning of the “trade-off”.  We would like to emphasize our work’s main contribution is interpreting the non-stationary MDP as “$\\textit{wall-clock time}$” goes by, not as “$\\textit{episode}$” goes by, and shifting the perspective from episode to time is a more realistic setting that matches with non-stationary RL’s motivation: RL for real-world application. Raising this issue recalls our new problem setting stated in the introduction (line 2 $\\sim$ 5). This new setting gives rise to solving an additional problem: how to choose the optimal $K-$length time sequence that the agent interacts with the environment?”. With this respect, our main theoretical result is that we determine the optimal K-lenght time sequence by optimal training time, and we propose a PTM framework to find optimal training time.\n\nNow, we would like to address the “tradeoff”. Yes, the tradeoff exists between the agent’s training time and how fast the environment changes, but it's not for the fixed episode(K), but for fixed “time duration”. For better understanding, we would like to remind the example of an introduction with a detailed explanation. Let’s say for a fixed time duration 0[s]$\\sim$15[s], robot A executes episodes for every 1 second, [0,1,..,15], and between time $t,t+1$, the agent trains the policy. Robot B executes episodes every 2 seconds [0,2,..,14] and between time $t,t+2$, the agent trains the policy. Let’s assume one policy update takes 1 second. Then, the robot A can update one time, and the robot B can update two times. The robot A interacts with the environment for 15 episodes and updates policy one time, which has more information about the environment but has an uncertain approximate optimal policy. Robot B interacts with the environment for 8 episodes and updates policy two times, which has less information about the environment but has a better approximate optimal policy than robot A. \n\nThe above results clearly show the existence of tradeoff (line53~54) and support our main contribution that how to choose optimal training time is significant that should be addressed.\n\n$\\textbf{2) W3: necessity of defining time elasping variation budget}$\n\nThanks for pointing out the necessity of defining time elapsing variation budget compared to the standard variation budget [Cheung et al. 2020]. Aside from the standard definition of variation budget, we need a new definition since the time of the environment and the episode of the agent are not synchronized anymore. Standard setup [Cheung et al. 2020] defines the variation budget as the difference between two consecutive MDP and takes summation over the total K episodes. However, in our setting, how the agent chooses the interaction time $[t_1,t_2,...,t_K]$ brings about different variation budgets even though executing total K episodes (K interaction time instances) since the environment changes as time goes by. Therefore, two different agents that execute with the same K episodes, but different interaction time sequence experience different variation budgets. This is the reason why we need to define variation budget with respect to the environment’s time, which we named “time-elapsing variation budget”.\n\n$\\textbf{3) W4: Necessity of the property$B_p(\\Delta_t) = c^{\\alpha_p} B_p(\\Delta_t)$}$\n\nThe main reason why we added this assumption is to justify our new definition, time-elapsing variation budget, covers and can represent standard MDPs, so utilizing our practical setting can be compatible with previous non-stationary RL methods. (line 118 $\\sim$ line121). $\\alpha_p = \\alpha_r =0$ represents a stationary environment (typo on the main paper line 120 $\\sim$ 121) and $\\alpha_p = \\alpha_r=1$ is a linear drifiting environment. This validness of our assumption is well-supported by the result of our main theorem, Theorem 3. In theorem 3, as case1: $max(\\alpha_r, \\alpha_p) =0$ , the $G^*$ is infinity. This makes sense, since in a stationary environment, a large number of NPG gradient steps (iteration numbers of policy updates) guarantee policy closer to the optimal policy. \n\n$\\textbf{4) W5: appropriateness of the baseline algorithms}$\n\nWe admit MBPO algorithm is built upon a stationary environment. The main reason why we added the MBPO algorithm is to compare the result between MBPO and PTM-G framework. (line 335 $\\sim$ 338). Note that the PTM-G framework is a model-based policy optimization framework, but the big deviation from MBPO occurs PTM-G framework predicts the future non-stationary model using the MDP forecaster and the MBPO predicts the stationary-model by past observed trajectories. This structure difference clearly shows comparing MBPO and PTM-G framework can shed light on the forecaster performance of the PTM-G framework. We also have selected left three algorithms as a baseline, since those are algorithms that were proposed to deal with non-stationarity and have been utilized as a baseline algorithm [13].\n\n$\\textbf{5) Q1}$ : The environment tempo, which is a time-elapsing variation budget, can capture both properties of the non-stationarity since it’s s a definition that captures the non-stationarity with respect to time, not respect to episode.\n\n$\\textbf{6) Q2}$ : We apologize for the typo. The variations of the transition probability should $\\sum_{k=1}^{K-1} \\sup_{s,a} || P^{t_{k+1}} ( \\cdot | s,a) - P^{t_{k}} ( \\cdot | s,a) ||$.\n\n$\\textbf{ 7) Q3}$ : We first note that our PTM framework is not related to meta-learning. We use the term “meta-algorithm” since the PTM framework 1) first provides an MDP forecaster that creates a future MDP 2) then obtains optimal policy in that model.  The term “meta-algorithm” represents we can use any existing RL algorithms that obtain an optimal policy for a given model in process 2) (line120 $\\sim$ line 151).\n"}]

Author rebuttal:
We appreciate constructive comments from all reviewers. 

We would like to organize our $\textbf{motivation and main contribution}$ on this global response to help reviewers to better understand our paper. We also have elaborated more details on each reviewer's responses.


$\textbf{1. Motivation}$

$\textbf{We unearth a hidden assumption of non-stationary reinforcement learning (RL)}$ that critically holds back its fundamental motivation: real-world applications of RL. We call it a $\textit{time synchronization}$ issue between the agent and the environment. In the real-world, the environment changes as a $\textit{wall-clock time}$ goes by, not as an $\textit{episode}$ goes by, where the $\textit{wall-clock time}$ should independently flow from the episode which is controllable by the agent. The $\textit{time}$ (wall-clock time) of the environment should be uncontrollable by any instances including the agent, training algorithm.

To solve this issue, we consider a $\textbf{practical setting}$ for non-stationary RL where the agent chooses a time sequence when to interact with the environment and fully spends the time interval(the time between $k^{th}$ and $k+1^{th}$ interaction time instance) to train its policy. 


$\textbf{2. Main contribution}$

Our main contribution is that finding the optimal time sequence entails an additional factor, $\textbf{tempo}$, and an additional trade-off that should be addressed in addition to the traditional exploration-exploitation trade-off, that is $\textbf{the trade-off between the environment tempo and the agent tempo}$.  We propose a $\texttt{PTM}$ framework that finds optimal training time by leveraging how long the agent should train its policy (agent tempo) and how fast the environment changes (environment tempo). Theoretically, this work establishes an optimal training time as a function of the degree of the environment's non-stationarity and achieves a sublinear dynamic regret at the same time. Our experimental evaluation on Mujoco non-stationary environments shows that the \texttt{PTM} framework achieves a higher online return than the existing methods, and it provides empirical evidence of the existence of an optimal algorithm tempo. 


Meta-review: This paper introduces a new reinforcement learning framework to deal with non-stationary environments.
Although the reviewers raised many concerns about the presentation, the gap between theory and practice, and the experimental evaluation, the authors' rebuttals effectively solved most of these concerns.
Even if the reviewers did not reach a consensus, there is quite a strong support for acceptance.
The authors need to be aware that there were many problems with the presentation that induced a lot of misunderstandings and prevented some reviewers from properly evaluating their work.
To avoid the same problems with future readers of this paper, the authors have to deeply revise the presentation of their paper and fix the issues raised in the reviews.
Decision: Accept (poster)