Nonstationary Reinforcement Learning with Linear Function Approximation
Authors: Huozhi Zhou
Jinglin Chen
Lav R. Varshney
Ashish Jagmohan
Venue: Accepted by TMLR ()

Abstract: We consider reinforcement learning (RL) in episodic Markov decision processes (MDPs) with linear function approximation under drifting environment. Specifically, both the reward and state transition functions can evolve over time but their total variations do not exceed a \textit{variation budget}. We first develop $\texttt{LSVI-UCB-Restart}$ algorithm, an optimistic modification of least-squares value iteration with periodic restart, and bound its dynamic regret when variation budgets are known. Then we propose a parameter-free algorithm \texttt{Ada-LSVI-UCB-Restart} that extends to unknown variation budgets. We also derive the first minimax dynamic regret lower bound for nonstationary linear MDPs and as a byproduct establish a minimax regret lower bound for linear MDPs unsolved by Jin et al. (2020). Finally, we provide numerical experiments to demonstrate the effectiveness of our proposed algorithms. 

Published in Transactions on Machine Learning Research (10/2022)
Nonstationary Reinforcement Learning with Linear Function Approximation
Huozhi Zhou
hahou85@rllinoiseeie
Deportment of Electrical and Computer Engineering University of Illmois Urbona- Champaign
Jinglin Chen
jinglincthllinois.ccc edu
Department Computer Science University of Blinois Urbena- Chaaa--n
Lav R. Varshney
worshaney@Wllnnoiss edu
Department of Electrical and Computer Engineering University of Ilinois Urbana- Urbana-Champae Champoign
Ashish Jagmohan
oshishja@us. ibm. com
IBM Research
Reviewed OpenReview: https: openreviee. net/ forum? id= id=nS849p0rqp
Abstract
We consider reinforcement lcarning (RL) in episodic Markov decision processes (MDPs) with linear function approximation under drifting environment. Specifically, both the re- ward and state transition functions can evolve over time but their total variations do not exceed a variation budget. We first develop LSVI-UCB-Restee modification of least-squares value iteration with periodic restart, and bound its dynamic regret. when variation budgets known. Then propose parameter-free algorithm kda-IsVI-UCB-Restarr that extends to unknown variation budgets. We also derive the first minimax dynamic regret lower bound for nonstationary linear MDPs and as byprod- uet establish a minimax regret lower bound for linear MDPs unsolved by Jin et al. (2020). Finally, we provide numerical experiments to demonstrate the offectiveness of our proposed algorithms.
algorithm, an optimistic
1 Introduction
Reinforcement learning (RI.) is a core control problem in which an agent sequentially interacts with an unknown environment to maximize its cumulative reward (Sutton & Barto, 2018). RL finds enormous applications in real-time bidding in advertisement auctions (Cai et al., 2017), autonomous driving (Shalev- Shwartz et al., 2016), gaming-AI (Silver et al., 2018), and inventory control (Agrawal Jia, 2019), among others. Due the large dimension of sequential decision-making problems that are of growing interest, classical RL algorithmms designed for finite state space such as tabular Q-learning (Watkins & Dayan, 1992) no longer yield satisfactory performance. Recent advances in RL rely function approximators such deep neural nets to overcome the curse of dimensionality, i.e., the value function is approximated by function which is able to predict the value function for unseen statc-action pairs given few training samples. This function approximation technique has achieved remarkable success in various large-scale decision- decision-making problems such as playing video games (Mnih et al., 2015), the game Go (Silver et al., 2017), and robot control (Akkaya et al., 2019). Motivated by the empirical success of RI. algorithms with function approximation, there is growing interest in developing RL algorithms with function approximation that statistically efficient (Yang & Wang, 2019; Cai et al., 2020; Jin al., 2020; Modi et al., 2020; Wang

---

Published in Transactions on Machine Learning Research (10/2022)
et al., 2020; Wei et al., 2021; Neu & Olkhovskaya, 2021; Jiang et al., 2017; Wang et al., 2020; Jin et al., 2021; Du et al., 2021). The focus of this line of work is to develop statistically efficient algorithms with function approsimation for RL in terms of either regret or sample complexity. Such efficiency is especially crucial in data-sparse applications such as medical trials (Zhao et al., 2009).
However, all of the aforementioned empirical and theoretical works on RL with function approximation assume the environment is stationary, which is insufficient to model problems with time-varying dynamics. For example, consider online advertising. The instantancous reward is the payoff when viewers are redirected to advertiser, and the state is defined as the the details of the advertisement and user contexts. If the target users' preferences are time-varying, time-invariant reward and transition function are unable to capture the dynamics. In general nonstationary random processes naturally occur in many settings and are able to characterize larger classes of problems of interest (Cover & Pombra, 1989). Can one design a theoretically sound algorithm for large-scale nonstationary MDPs? In general is impossible to design algorithm to achieve sublinear regret for MDPs with non-oblivious adversarial reward and transition functions in the worst case (Yu al., 2009). Then what is the maximum nonstalionarity learner can tolerate to adapt to the time-varying dynamics of an MDP with potentially infinite number of states? This paper addresses these two questions.
We consider the setting of episodic RL with constationary reward and transition functions. To measure the performance of an algorithm, we use the notion of dynamic regret, the performance difference between an algorithm and the set of policies optimal for individual episodes in hindsight. For nonstationary RL, dynamic regret is a stronger and more appropriate notion of performance measure than static regret, but is also more challenging for algorithm design and analysis. To incorporate function approximation, we focus subclass of MDPs in which the reward and transition dynamics are linear in known feature map (Melo & Ribeiro, 2007), termed linear MDP. For any linear MDP, the value function of any policy is linear in the known feature map since the Bellman equation is linear in reward and transition dynamics (Jin et al., 2020). Since the optimal policy is groedy with respect to the optimal value function, lincar function approximation sullices to learn the optimal policy. For nonstationary linear MDPs, we show that one can design a near- optimal statistically--efiiie algorithm to achieve sublinear dynamic regret as long as the total variation of reward and transition dynamics is sublincar. Let T be the total number of time steps, B be the total variation of reward and transition function thronghout the entire time horizion, d be the ambient dimension of the features, and H be the planning horizon.
The contribution of our work is summarized as follows.
We prove a /33 1/3T2/33 minimax regret lower bound for nonstationary lincar MDP, which shows that it is impossible for any algorithm to achieve sublinear regret on any nonstationary linear MDP with total variation linear in T. As byproduct, we also derive the minimax regret lower bound for stationary linear MDP on the order of (RddHH)) which is unsolved in Jin et al. (2020).
We develop the LSVI-UCB-Restart algorithm and analyze the dynamic regret bound for both cases that local variations are known or unknown, assuming the total variations are known. We define local variations (Eq. (2)) as the change in the environment between two consecutive epochs instead of the total changes over the entire time horizon. When local variations are known, SEII-UCB-Restan achieves 3/3/3,4////4////// dynamic regret, which matches the lower bound in and T, up to polylogarithin factors. When local variations are unknown, SWV--UC-RRestan achieves Ö(B²/4 /4 (5//11//4//// dynamic regret.
We propose a parameter-fie free algorithm called Ada-LSWI-UCB-Restee an adaptive version of LSVI-UCB-Restard and prove that it can achieve the total variations.
dynamic regret without knowing
We conduct mumerical experiments on synthetic nonstationary linear MDPs demonstrate the effective- ness of our proposed algorithms.
2

---

Published in Transactions on Machine Learning Research (10/2022)
1.1 Related Works
Nonstationary bandits Bandit problems can be viewed as a special case of MDP problems with unit planning horizon. It is the simplest model that captures the exploration-cxpllottttonn tradcoff, unique feature of sequential decision-making problems. There are several ways to define nonstationarity in the bandit literature. The first one is piecevvse-stationary (Garivier & Moulines, 2011), which assumes the expected rewards of arms change in a piecewise manner, i.e. stay fixed for a time period and abruptly change at unknown time stops. The second one is to quantify the total variations of expected rewards of arms (Besbes et al., 2014). The general strategy to adapt to nonstationarity for bandit problems is the forgetting principle: run the algorithm designed for stationary bandits either on a sliding window or in small epochs. This scemingly simple strategy is successful in developing near-optimal algorithms for many variants of nonstationary bandits, such as cascading bandits (Wang et al., 2019), combinatorial semi-bandits (Zhon et al., 2020) and linear contextual bandits (Cheung et al., 2019; Zhao et al., 2020; Russac et al., 2019). Other nonstationary bandit models include the nonstationary rested bandit, where the reward of each arm changes only when that arm is pulled (Cortes et al., 2017), and online learning with expert advice (Mohri & Yang, 2017a;b), where the qualities of experts are time-varying. However, reinforcement learning is much more intricate than bandits. Note that naively adapting existing nonstationary bandit algorithms to nonstationary RL leads to regret bounds with exponential dependence on the planing horizon H.
RL with function approximation Motivated by empirical success of deep RL, there is recent line of work analyzing the theoretical performance of RL algorithms with function approximation (Yang & Wang, 2019; Cai et al., 2020; Jin et al., 2020; Modi ct al., 2020; Ayoub et al., 2020; Wang et al., 2020; Zhou et al., 2021; Wei et al., 2021; Neu & Olkhovskaya, 2021; Huang el al., 2021; Modi et al., 2021; Jiang el al., 2017; Agarwal et al., 2020; Dong et al., 2020; Jin et al., 2021; Du et al., 2021; Foster et al., 2021a; Chen et al,, 2022). Recent work also studies the instance-dependent sample complexity bound for RL with function approximation, which adapts to the complexity of the specific MDP instance (Foster et al., 2021b; Dong & Ma, 2022). All of these works assume that the learner is interacting with a stationary environment. In sharp contrast, this paper considers learning in nonstationary environment. As we will show later, if we do not properly adapt to the nonstationarity, linear regret is incurred.
Nonstationary RL The last relevant line of work on dynamic regret analysis of nonstationary MDPs mostly without function approximation (Auer et al., 2010; Ortner et al., 2020; Cheung et al., 2019; Fei et al., 2020; Cheung et al., 2020). The work of Auer et al. (2010) considers the setting in which the MDP is piecewise- stationary and allowed to change in 1 times for the reward and transition functions. They show that UCRL2 with restart achieves (((1/312/33 dynamic regret, where T is the time horizon. Later works (Ortner et al., 2020; Choung ct al., 2020; Fei et al., 2020) generalize the nonstationary setting to allow reward and transition functions vary for any number of time steps, as long as the total variation is bounded. Specifically, the work of (Ortner et al., 2020) proves that UCRL with restart achieves Ö((B, + 1/332/33333 dynamic regret (when the variation in each epoch is known), where B, and B, denote the total variation of reward and transition functions over all time steps. Cheung et al. (2020) proposes an algorithm based on UCRL2 by combining sliding windows and confidence widening technique. Their algorithm has slightly worse dynamic regret. bound (B) without knowing the local variations. Further, Fei et al. (2020) develops an algorithm which directly optimizes the policy and enjoys near-optimal regret in the low-variation regime. A different model of nonstationary MDP is proposed by Lykouris et al. (2021), which smoothly interpolates between stationary and adversarial environments, by assuming that most episodes are stationary except for a small number of adversarial episodes. Note that Lykouris et al. (2021) considers linear function approximation, but their nonstationarity assumption is different from ours. In this paper, we assume the variation budget for reward and transition function is bounded, which is similar to the settings in Ortner et al. (2020); Cheung et al. (2020); Mao et al. (2021). Concurrently to our work, Tonati & Vincent (2020) propose an algorithm combining weighted least-squares value ileration and the optimistic principle, achieving the same O(B1/4 (3/////33/ regret as we do with knowledge of the total variation B. They do not have a dynamic regret bound when the knowledge of local variations is available. Their proposed algorithm uses exponential weights to smoothly forget data that are far in the past. By contrast, our algorithm periodically restarts the LSVI-UCB algorithm from scratch to handle the non-stationarity and is much more computationally
3

---

Published in Transactions on Machine Learning Research (10/2022)
efficient. Another concurrent work by Wei & Luo (2021) follows substantially different approach to achieve the optimal 72/3 regret. The key idea of their algorithm is to run multiple base algorithms for stationary instances with different duration simultaneously, under a carefully designed random schedule. Compared with them, our algorithm has a slightly worse rate, but a much better computational complexity, since we only require to maintain one instance of the base algorithm. Both of these two concurrent works do not have empirical results, and we are also the first one to conduct numerical experiments on online exploration for non-stationary MDPs (Section 6). Other related and concurrent works investigate online exploration in different classes of non-stationary MDPs, including linear kernal MDP (Zhong et al., 2021), constrained tabular MDP (Ding & Lavaei, 2022), and stochastic shorted path problem (Chen & Luo, 2022).
The rest of the paper is organized as follows. Section 2 presents our problem definition. Section 3 establishes the minimax regret lower bound for nonstationary linear MDPs. Section and Section 5 present our algorithms LSVI-UCB-Restard
Ada-LSVI-UCB-Restanl and their dynamic regret bounds. Section 6 shows our experiment results. Soction concludes the paper and discusscs some future dircctions. All detailed proofs can be found in Appendices.
Notation We use (5 to denote inner products in Euclidean space, ||0||| to denote the L2 norm of vector v, and || to denote the For an integer N, we denote the set of positive integers 2 N] as [N].
norm induced by a positive definite matrix A for vector w, i.c., || = V Av.
2 Preliminaries
We consider the setting of a nonstationary finite-hriizon episodic Markov decision process (MDP), specified by a tuple (S, A, H, K, K. {P%) ( = (r%) [e(),))))))) where the set S is the collection of states, A is the collection of actions, H is the length of each episode, K is the total number of episodes, and IP and are the transition kernel and deterministic reward functions respectively. Moreover, PK (+ls,, a) denotes the transition kernel over the next states if the action is taken for state 8 at step h in the k-th episode, and r : S x A + [0, is the deterministic reward function at step h in the k-th episode. Note that we are considering a nonstationary setting, thus we assume the transition kernel P and reward function r may change in different episodes. We will explicitly quantify the nonstationarity later.
The learning protocol proceeds as follows. In episode k the initial state sf is chosen by an adversary. Then at each step h E [H) the agent observes the current state 8). E S, takes an action Oд A, receives instantaneous reward rf,,,, an), then transitions ( (1|ss, on). This process terminates at step H and then the next episode begins. The agent interacts with the environment for K episodes, which yields T = KH time steps in total.
the next state 81+1 according to the distribution
A policy π is a collection of functions Th : S + A, Vh E [H]. We define the value function at step h in the k-th episode for policy æ as the expected value of the cumulative rewards received under policy æ when starting from an arbitrary state s:
11 Σ
(s) = ExT
(swr, an as V [H],k k E [K].
Note that the value function also depends the episode le since the Markov decision process is nonstationary. Similarly, we can also define the action-value function (a.k.a. Q function) for policy æ at step h in the k-th episode, which gives the expected cumulative reward starting from an arbitrary state-action pair:
A Σ A+1
(n)))s))))s 8, = a
- + E,
A [M], [K].
We define the optimal value function and optimal action-value function for step h in k-th episode (s) = sup, (s) and Qi = sup, (s, respectively, which always exist (Puterman, 2014).
For simplicity, we denote E. (o) (PP)) Va]a a). Using this notation, we can write down the
4

---

Published in Transactions on Machine Learning Research (10/2022)
Bellman equation for any policy n, (s, (r% + PK (KV,,,)))ss (s) ( -. [K].
Similarly, the Bellman optimality equation is
(n, = (r + P a), (s) = max (h, a), (,) = 0, E xx [K]. aEA
This implies that the optimal policy n' greedy with respect to the optimal action-value function (;))).
Thus in order learn the optimal policy it suffices estimate the optimal action-value function.
Recall that the agent is learning the optimal policy via interactions with the environment, despite the uncertainty of r and P. In the k-th episode, the adversary chooses the initial state sf, then the agent decides its policy x² for this episode based on historical interactions. To measure the convergence to optimality, we consider an equivalent objective of minimizing the dynamic regret (Cheung et al., 2020),
Dyn-Reg( K)
Σ
Vin( ViT(
(1)
2.1 Linear Markov Decision Process
We consider special class of MDPs called linear Markov decision process (Melo & Ribciro, 2007; Bradtke & Barto, 1996; Jin al., 2020), which assumes both transition function IP and reward function are linear in known feature map (). The formal definition is follows.
Definition 1. (Linear MDP). The MDP (S, H, K, Pr) is a linear MDP with the feature map & : SS A + Rd, if for any (h, k) E [H] x [K], there erist d unknown measures PA,k = - ph,x) on S and a vector On Rdd such that.
( ()) (t)),')), rl(s,a) (8(,aa)
Without loss of generality, we assume [ S for all (8, E S A,,, and Vd for all (h, E [H] x [K].
| s
Note that the transition function and reward function r are determined by the unknown measures { heeet,,ee and latent vectors {0 (e[ The quantities Pa,k and On, vary across time in general, which leads to change in transition function P and reward function (2014); Cheung et al. (2019; 2020), we quantify the total variation on a and in terms of their respective variation budget Bg and Bp,, and define the total variation budget B as the summation of these two variation budgets:
Following Besbes et al.
Bg
1 0n.-1ll2 By
[I (1)6-1 B Bg + Bus
where ().,(() is the concatenation of (s) for all states.
Remark 1. One may find the definition of By to be restrictive, since Bμ sums over all possible states and the number of states the dependency of Bp in the worst case. It is possible to define nonstationarity measure that does not linear MDPs. For example, can add some
be infinite in linear MDPs. However, indicated by Theorem 1, we cannot remove
depend all states if we impose additional construinls reachability construints on the state space to avoid the dependency on all states to some extent. But such reaching probability in general would also change in the nonstationary environment; therefore, it is hard to define and capture this. Fature work may define new envirovment change measure.
3 Minimax Regret Lower Bound
In this section, we derive minimax regret lower bounds for nonstationary linear MDP' in both inhomogeneous and homogeneous settings, which quantify the fundamental difficulty when measured by the dynamic regret
5

---

Published in Transactions on Machine Learning Research (10/2022)
in nonstationary linear MDPs. More specifically, we consider inhomogeneous setting in this paper, where the transition function P (as introduced in Section 1) can be different for different h. In contrast, for the homogeneous setting, the transition function P% will be the same within an episode, iee, for any k PA = pk for any = (1..... :.......) H). All of the detailed proofs for this section are in Appendix A.
For the homogeneous setting, the minimax dynamic regret lower bound is the following. Theorem 1. For any algorithm, the dynamic regret is at least 0(B1/382/3H//// for one nonstationary homogeneous linear MDP instance, if z 4, 64(d 3)ad-
Sketch of Proof. The construction of the lower bound instance is based on the construction used in Theorem 8 in Appendix A. Nature divides the whole time horizon into [ intervals of equal length N episodes (the last episode may be shorter). For each interval, nature initiates new stationary linear MDP parametrized by which is drawn from a set (=vd 3/ 3/vN] VN) Note that nature chooses the parameters for the linear MDP for each interval only depending on the learner's policy, and the worst-case regret for each interval is at least (idvH2N) Since there are at least K - intervals, the total regret at least (2 (ad/H=K 1/2). By checking the total variation budget B, we can obtain the lower bound for N, which is QB 2/3 d2/3 K2/3). Then we can obtain the desired regret lower bound. For the detailed proof, please refer to Appendix A. J
For the inhomogencous sctting, the minimax dynamic regret lower bound the following. Theorem 2. For any algorithm, the dynamic regret is at least /2BB1/3 ( HT/////33) for one nonstationary inhomogenous linear MDP instance, if 2 4, > 3, T 2 (d - 1
Sketch of Proof. The proof idea is similar to that of Theorem 1. The only difference is that within each pictoviso-ttttionary segment,
the hard instance constructed by Zhou et al. (2021); Hu et al. (2022) for inhomogenous linear MDPs. Optinizing the length of each piecewise-stationary segment N and the variation magnitude between consecutive segments (subject to the constraints of the total variation budget) leads to our lower bound.
Comparing these lower bounds, we can see that learning in inhomogencous scttings is indcod harder since there is more freedom in the transition function.
4 LSVI-UCB-Restare Algorithm
In this section, we describe our proposed algorithm LSVI-UCB-Restare and discuss how to tune the hyper- parameters for cases when local variation is known or unknown. For both cases, we present their respective regret bounds. Detailed proofs are deferred to Appendix B. Note that our algorithuns are all designed for inhomogeneous setting.
4.1 Algorithm Description
Our proposed algorithm LSVI-uce-Restart has two key ingredients: least-squares value iteration with upper confidence bound to properly handle the exploration-expllitattii trade-off (Jin et al., 2020), and restart strategy to adapt to the unknown nonstationarity. Our algorithm is summarized in Algorithm 1. From a high-level point of view, our algorithm runs in epochs. At each epoch, we first estimate the action- value function by solving regularized least-squares problem from historical data, then construct the upper confidence bound for the action-value function, and update the policy greedily w.r.t. action-valut function plus the upper confidence bound. Finally, we periodically restart our algorithm to adapt to the nonstationary nature of the environment.
Next, we delve into more details of the algorithm design. Note that in a linear MDP, for any policy x, the Q-function lincar in the feature embedding ((--)). As a preliminary, we briefly introduce least-squares value iteration (Bradtke & Barto, 1996; Osband et al., 2016), which the key tool estimate w, the latent vector used to form the optimal action-value function, Q (((s)); w). Least-squares value iteration

---

Published in Transactions on Machine Learning Research (10/2022)
is natural extension of classical value iteration algorithm (Sutton & Barto, 2018), which finds the optimal action-value function by recursively applying Bellman optimality equation,
(s,((s,) = [ma, PK max Q1+11x-((.d')ss..0 d'EA
In practice, the transition function P is unknown, and the state space might be so large that it is impossible for the learner to fully explore all states. If we parametrize the action-value function in a linear form as ()(:),, w)) , it is natural to solve a regularized least-squares problems using collected data inspired by classical value iteration. Specifically, the update formula of wf, in Algorithm 1 (line 8) is the analytic solution of the following regularized least-squares problem:
R-1
wh arg min Eina air + max ( (b(5) a,),, w)l? + 120122- aeA
One might be skeptical since simply applying least-squares method to solve does not take the distribution drift in I and into account and hence, may lead to non-trivial estimation error. However, we show that the estimation error can gracefully adapt to the nonstationarity, and it suffices to restart the estimation periodically to achieve good dynamic regret.
In addition to least-squares value iteration, the inner loop of Algorithm also adds an additional quadratic bonus term [| ()((a))) (line 9) to encourage exploration, where 3 is scalar and A is the Gram matrix of the regularized least-squares problem. Intuitively, 1/|| is the effective sample nunber of the agent observed so far in the direction of Φ, thus the quadratic bonus term can quantify the uncertainty of estimation. We will show later if we tune 3g properly, then our action-value function estimate Q% can be an optimistic upper bound or an approximately optimistic upper bound of the optimal action-value function, so we can adapt the principle of optimism the face uncertainty (Auer et al., 2002a) to explore.
Finally, we use epoch restart strategy to adapt the drifting environment, which achieves near-optimal dynamic regret nofwithstanding its simplicity. Specifically, we restart. the estimation of after W episodes, all illustrated in the outer loop of Algorithm 1. Note that in general epoch size W can vary for different epochs, but we find that a fixed length is sufficient to achieve near-optimal performance.
To sum up, our hm follows the algorithmic principles of LSVI-UCB (Jin et al., 2020). The key differ- ence and challenge to set the confidence parameter properly and use periodic restart strategy to handle nonstationarity.
Algorithm LSVI-UCB- Algorithm Require: time horizon T, epoch size W
1: Set epoch counter j = 1.
2: while <
T do
W
3: sel 7 1
for all k -, I,..., mi..,, W K, do Receive the initial state st.
6: for all step h H...,, do
A + k- ((s)/ a (ish,, T +
7:
wf + (AA) EL= ((5) Mrn, a + max, 1 (s) (s)
9:
() + (wn)( ((.,)) + 3e ( )1aag)= H
10:
end for
11: for all step h = 1,.... H do
12: lake action at + arg max, Q ( a), and observe sh+1
13:
end for
14: end for
15: set j j jj+1 +1
16: end while

---

Published in Transactions on Machine Learning Research (10/2022)
4.2 Regret Analysis
Now we derive the dynamic regret bounds for SSVI--UCBRRestary first introducing additional notation for local variations.
We let
H ΣΣ KEEh=1
H 10 - 02,x-1l12 and Bu, ΣΣ
B
(M,((S) - p
(2)
KEE h=1
be the local variation for 0 and μ in epoch E. To derive the dynamic regret lower bounds, we need the following lemma to control the fluctuation of least-squares value itcration.
Lemma 1. (Modified from Jin et al. (2020)) Denote T to be the first episode in the epoch which contains episode k. There erists an absolute constant C such that the following event E,
Σ V (h
I CdH V /ogg[((c + L)dW/pl. V(k,h) e E [H].
(A()
happens with probability at least p/2.
Next we proceed to derive the dynamic regret bounds for two cases: (1) local variations are known, and (2) local variations are unknown.
4.2.1 Known Local Variations
For the case of known local variations, under event E' defined in Lemma 1, the estimation error of least-squares estimation scales with the quadratic bonus (|ø(;, "l(y)) uniformly for any policy which is detailed in the following lemma.
Lemma 2. Under event E defined in Lemma I, we have for any policy n, Vs,a, k E Ax [M] X
l(o(s, w/) - Qh, -P% (V/4+ - (i+,,,) Br 10( (
+)+ Bu, d(k T) and the first episode the current where Bk CidH /lgg(2lW//WW))ppo Bo, d(k d(k epoch.
The proof of Lemma is included in Appendix В. Based on Lemma we can show that if we set Ba properly with knowledge of local variations Ba,g and By&,, the action-value function estimate maintained in Algorithm 1 is upper bound of the optimal action-value function under event E.
Lemma 3. Under event defined in Lemma 1, for episode k, if we 3x odH /log(2dW/p) + Bo. d(k - r) + B / /d(k - T), we have
()) 2 Qh,
Sketch of Proof. For the last step H in each episode, the results hold due to Lemma 2 since after step H there is no reward and the episode terminates. We then prove Q is indeed the upper bound for the optimal action-value function i for remaining E [H 1] by induction. Please see Appendix B for details.
After showing the action-valie function estimate is the optimistic upper bound of the optimal action-value function, we can derive the dynamic regret bound within epoch via recursive regret decomposition. The dynamic regret within one epoch for Algorithm with the knowledge of Ba, and B, is follows, and the proof is deferred to Appendix B.
Theorem 3. For each epoch with epoch size W, set B in the k-th episode BB edHl / /loo(222// + Bo. d(k d(k T) + B d(k - T), where e is an absolute constant and p (0. Then the dynamic regret within that epoch is 3//2///11111// Bo.edW + BHHH) with probability at least p-
8

---

Published in Transactions on Machine Learning Research (10/2022)
By summing over all epochs and applying the union bound, can obtain the dynamic regret upper bound for LSVI-UCB-Restard for the whole time horizon.
Theorem 4. If we set BE = cdH /log(2dT/p)- Bo.E /o.evd(k- d)) Bp..HH ((kk-)) the dynamic regret of LSVI-UCB-Restart is 0(H3/228/21)) 1/2 BedW + BBddHW), with probability at least 1 - p.
By properly tuning the epoch size W, we can obtain tight dynamic regret upper bound.
Corollary 1. Let W [B-2/$72/3 - H, and 3x cdH L /ll//o/g///W/// + Bo, v d(k- - 7) + By.eH H /d(k - T) for each epoch. LSVI-UCB- -ee--eettarr achieves 1/3 probability at least p.
dynamic regret, with
Remark 2. Corollary 1 shows that if local variations are known, we achieve near-optimal dependency on the the total variation Bg. By and time horizon T compared to the lower bound provided in Theorem 1. However, the dependency on d and H is worse. The dependency on d is unlikely to improve unless there is an improvement to LSVI-UCB
Remark 3. The definition of total variation B is related to the misspecification error defined by Jin et al. (2020). One can apply the Cauchy--Shuae
inequality to show that our total variation bound implies that misspecification in Eq. (4) of Jin et al. is also bounded (but not vice versa). However, the regret analysis in the misspecified linear MDP of Jin et al. (2020) is restricted to stotic regret, so we cannot directly borrow their analysis for the misspecified setting (Jin et al., 2020) to handle our dynamic regret (as defined in Eq. (1)).
Remark 4. For the case when the encironment changes abruplly L låmes, our algorithm enjoys 011//37//3) dynamic regret bound, which is sub-optimal compared to Wei & Luo (2021). The reason is that periodic restort is not a suitable strategy to handle abrupt changes since the passive nature indicates that we cannot guarantee detecting the abrupt encironment change within a reasonably short delay. Wei & Luo (2021) overcome this issue by running two tests on top of multiple base instances with different scales to detect the environmental change. Similar ideas have also been used in the pieceuise-stationary bondit liter- alure (Besson & Kaufmann, 2019), where a change delection subroutine is run to detect the environmental change, so the regret incurred by the environmental drift can be better controlled.
4.2.2 Unknown Local Variation
If the local variations are unknown, the proof is similar to the case of known local variations. We only highlight the differences compared to the previous case. The key difference is that without knowledge of local variations Be and Bμ, we set the hyper-parameter 8 edHl /lol///og2dd//p value function estimate Qf, maintained in Algorithm I is no longer the optimistic upper bound of the optinal action-value function, but only approximately, up to some error, proportional to the local variation. The rigorous statement is as follows.
As result, the action-
Lemma 4. Under event E defined in Lemma 1, if we set B = edH /og(2dW//)) we have
V(s,a, k) E
[H] x E, Q+(ss 2 Qh. (H h () + Bu..H Hd
Sketch of Proof. For the case when local variations are unknown, the least -squares estimation crror have some additional terms that are linear in the local variations Ba. and B,, (See Lemma 10 in Appendix B). Then we can prove that Q is an approximate upper bound of Qi, via induction. For details, please see Appendix B.
By applying a similar proof technique as Theorem 3, we can derive the dynamic regret within one epoch when local variations are unknown.
Theorem 5. For each epoch E with epoch size W, if we set Br = cdH /lgg(222)))))) where e is an absolute constant and E 10, then the dynamic regret within that epoch is 0(Vd + Ba /d/Hw3/2 + Bu.vvdHWe Ba.VV/333/2 with probability at least 1 -p, p, where Bo,g and B,, are the total variation within that epoch.
9

---

Published in Transactions on Machine Learning Research (10/2022)
By summing regret over epochs and applying union bound over all epochs, we obtain the dynamic regret of SOVI-UCB-Restary for the whole time horizon.
Theorem 6. If we set 3 edH / Tog(2dT) then the dynamic vegret of LSVI-UCB- is 0(d//213/271) 11/22 + 12
+ Bnd (/23)) with probability at least 1 p.
By properly tuning the epoch size W, we can obtain tight regret bound for the case of unknown local variations as follows.
Corollary 2. Let W = (B- 1/21 H and 5g = cdH /1o((2dW/p). Then ASVI-UCB-Restenn dynamic regret, with probability at least p.
achieves Ó
Remark 5. Our algorithmm has a slightly worse vegret bound compared with Wei Luoo (2021). However, our algorithm has a much better better computational complerity, since we only require to maintain one instance the base algorillen. We are also the first one to conduct numerical experiments on online exploration for non con-stationory MDPs (Section 6). How to achieve the ((T2/3) dynomic regret bound without prior knowledge and with only one base instance is still on open problem.
5 Ada-LSWI-UCB-Restaree a Parameter-free Algorithm
In practice, the total variations Bo and Bμ are unknown. To mitigate this issue, we present a parameter-free algorithm L---LLSV-UUB--Rsttae and its dynamic regret bound.
5.1 Algorithm Description
Inspired by bandit-over-bandit mechanism (Cheung et al., 2019), we develop a new parameter-fre algorithm. The key idea is to use LSVI-UCB-Resttae as a subroutine (set B = edH /log(2d// since we assume total variations are unknown), and periodically update the epoch size based on the historical data under the time- varying PP and (potentially adversarial). More specifically, Mta-LsVI-UCB-RRstaae the whole time horizon into 7 blocks of equal length A episodes (the length of the last block can be smaller than M episodes), and specifics a set Jw from which epoch size is drawn. For each block E [f HM 1]. with W
(Algorithm 2) divides
Ada-LSVI-UCB runs master algorithm to select. the epoch size W; and runs for the current block. After the end of this block, the total reward of this block fed back to the master algorithm, and the posteriors of the parameters are updated accordingly.
For the detailed master algorithm, select EXP3-P (Bubeck & Cesa-Bianchi, 2012) since it is able to deal with non-oblivious adversary. Now we present the details of Sta-LsVV--UBB-Rstaar We set the length of each block M and the feasible set of epoch size Jw as follows:
M = 122 111/221111111111 Jw (H, 2H 4H. ,.. MH..
The intuition of designing the feasible set for epoch size Jw is to guarantee it well-aprroximate the optimal epoch size with the knowledge of total variations while on the other hand make it as small possible, so the learner do not lose much by adaptively selecting the epoch size from Jw. This intuition is more clear when we derive the dynamic regret bound of -dda-Lsv--CC--Restart. Denoting |/w|= A, the master algorithm EXP3-P treats each element Jw as an arm and updates the probabilities selecting each feasible epoch size based on the reward collected in the past. It begins by initializing
I
I ATT/MH
In A TT/M 0t,1 0, 1E [A].
0.95,
7= 1.05,
A
where a, 8. are parameters used in EXP3-P and q E [A] are the initialization of the estimated total reward of running different epoch lengths. At the beginning of the block i, the agent first. sees the initial state s/ (i-1)H and updates the probability of selecting different epoch lengths for block i as
Exexxeex((aqn.) + 7
exp(aq::)
W1 = (1 ΣlE exp(agn.))
77)
(4)
10

---

Published in Transactions on Machine Learning Research (10/2022)
Then the master algorithm samples 4 E [A] according to the updated distribution (ul,) the epoch size W; for the block chosen as 4,tth element Jw, |M In MJ After sclecting the epoch size W,, Ada-LSVI-UCB runs new copy of LSVI-UCB-Restad Ada-LLvI-UUS-RRetartt observes the total reward of the current block, denoted as R,,,,, 81 "f- then the algorithm updates the estimated total reward of rumning different epoch sizes (divide (,,,, s MH to normalize):
with that epoch size. By the end of each block,
((-1) by
8 8+ (111-4]..0 4.R.
)/ J/MH
gl1++ = q1 +
(5)
U1
Algorithm 2 ADA-LSVI-UCB-ResEEE
Algorithm
Require: time horizon T, block length M, feasible set of epoch size Ju 1: Initialize a, 8, 7 and {qi, hE(A) according to Eq. 3.
2: for all i = 1,2, [T/HM]] do
Receive the initial state (((1))H
Update the epoch size selection distribution (u,cheta) according to Eq.
5: Sample 4 E [A] from the updated distribution {uI,) then set the epoch size for block i
W; [M4/imMM] JH.
for all t (i 1)MH L,.... min(iMH, do Run LSVI-UCB-Restart algorithm with epoch size W;
8: end for
9: After observing the total reward for block i, R,W,, 11 1) update the estimated total reward of running different epoch sizes {9,44))E according to Eq. 5
10: end for
5.2 Regret Analysis
Now we present the dynamic regret bound achieved by Ada-LSWI-UCB-Resttann Theorem 7. The dynamic regret of Ada-LSVZ-UCB-Restaen 0(B\/4
Sketch of Proof. To analyze the dynamic regret of SALLSVIIUCB-RRttaae we decompose the dynamic regret into two terms. The first term is regret incurred by always selecting the best Wt from Jw, and the second term regret incurred by adaptively selecting the epoch size from Jw via EXP3-P rather than always selecting W1. For the second term,, reduce to adversarial bandit problem and directly use the regret bound of EXP3-P (Bubeck & Cesa-Bianchi, 2012; Auer et al., 2002b). For the first term, show that Wi can well-approximate the optimal epoch size with the knowledge of B₁ and Be, up to constant factors. Thus we can use Theorem to bound the first term. For details, see Appendix C.
Remark 6. Using the master algorithm to select the window size is reminiscent of model selection approaches to online RL (Agarwal et al., 2017; Pacchiano et al., 2020; Lee et al., 2021; Abbasi- Yadkori et al., 2020). Typically model selection approaches achieve worse rates compared to the best base algorithm. However, in our setting we can discretize the feasible set for epoch size Jw proper gramularrty, so we can control the additional regret incurred by the master algorithm with respect to the best epoch size in Jw to be reasonably smoll. That is, have more freedom to choose the base algorithms compared to some problem settings in the model selection literature. As result, the regret bound does not lose much compared to the case where we have knowledge of total variation B.
6 Experiments
In this soction, we perform empirical experiments on synthetic datascts to illustrate the effectiveness of ESVI-UCB-Restade and M--LLSSI-UCC-Restaatr We compare the cumulative rewards of the pro- posed algorithms with five baseline algorithms: Epsilon-Greedy (Watkins, 1989), Randon-Exploratiion
11

---

Published in Transactions on Machine Learning Research (10/2022)
LSVI-UCB (Jin et al., 2020), OPT-WLSVI (Touati & Vincent, 2020), and MASTER (Wei & Luo, 2021). As dis- cussed before, we are the first one to perform numerical experiments on online exploration for non-stationary MDPs and demonstrate the effectiveness of proposed algorithms.
The agent takes actions uniformly in Random-Expe Exploro-xploootion.. In Epsilon-Greedy instead of adding a bonus term as in LSVI-UCB, the agent takes the greedy action according to the current estimate of Q function with probability 1 e, and takes the action uniformly at random with probability e, where we set 0.05. For LSVI-UCB and -eestatt we set B 0.001cdH /log(200dT). In addi- we test the performance of two cases: (1) known global variation, where we H; (2) unknown global variation (denoted LSVI-UCB-Unknomn) where
tion, for set W- = [ (the dynamic regret bound is 0(Bd//1155/4///4) for this case). For we set the length of each block M =
we set W MUA-LSVI-UGB-Rettan
Note that the tuning of hyperparameters is different from our thcoretical derivations by some constant factors. The reason is that the worst-case analysis is pessimistic and we ignore the constant factor in the derivation.
Settings We consider an MDP with S= 15 states, A actions, H = 10, d 10, and T = 20000. In the abruptty-changing environment, the linear MDP changes abruptly every 100 episodes to another linear MDP with different transition function and reward function. The changes happen periodically by cycling through different linear MDPs; we have 5 different linear MDPs in total. In the praduall-channgin environment, we consider the same set of 5 linear MDPs, {Mo. ...... Ma]. The environment changes smoothly from M; to M(++1) mod over every 100 episodes. To be more specific, at episode 100i (i is a non-negative integer), the MDP model is M; mud 5 parameterized by latent vectors {0), mod ") and {ui mod mod ((S) hh=1- The latent vectors of the MDP from episode 100i to 100(i + 1) are the linear interpolations of those of M; mod & and M(++1) mod 5 i.e., at episode (100i S S 100 Og = (1 k=100x )01 mod 5 k-100t (i+1)) mod 5 Vh e 100
100
100 44 (5+1) mod (8), wh [H]. To make the environment [H], (S))(S)) (1- --10==) Ja mod (SS + E-100:
100
challenging for exploration, our construction falls into the category of combination lock (Koenig & Simmons, 1993). For each of these 5 linear MDPs, there is only one good (and different) chain that contains a huge reward at the end, but 0 reward for the rest of the chain. Further, any sub-optimal action has small positive rewards that would attract the agent to depart from the optimal route. Therefore, the agent must perform "deep exploration" " (Osband al., 2019) to obtain near-optimal policy. The details of the constructions are in Appendix E. Here we report the cumulative rewards and the running time of all algorithms averaged over 10 trials.
From Figure 1, we see LSVI-UCB-Restead with the knowledge of global variation drastically outperforms all other methods designed for stationary environments. in both abruptly-changing and gradually-changinn environments, since restarts the ostimation of the Q function with knowledge of the total variations. Ada-LLVV--OCB-Restart also outperforms the baselines because it also takes the nonstationarity into ac- count. by periodically updating the epoch size for restart. Tn addition, huge gain compared to LSVI-UGB-Unknonn, which agrees with our theoretical analysis. This suggests that MLA-LLVI-UCB-Restare works well when the knowledge of global variation is unavailable. Our proposed algorithms not only perform systemic exploration, but also adapt to the environment change.
MA-LLSVI-UCB-Rettare has a
Compared to OPT-WLSVI and MASTER, our proposed algorithmss achieve comparable empirical performance. More specifically, MASTER outperforms our proposed algorithm which agrees with its dynamic regret upper bound. However, the variance of MASTER is larger due to the random scheduling of multiple base algorithms. Our algorithm outperforms OPT-WLSVI in the abrupt change sotting, but has worse performance in the gradual change setting, which agrees with the empirical findings in the nonstationary contextual bandit literature (Zhao et al., 2020). The main advantage of our algorithm compared to OPT-WLSVI and MASTER is its computational efficiency, as demonstrated by Figure 1. The reason is that our algorithm only requires the most recent data to estimate the Q-function, while the other two require the entire history. MASTER additionally requires maintaining multiple base instances at different scales, which further increases the computational burden.
From Figure 1, we find that the restart strategy works better under abrupt changes than under gradual changes, since the gap between our algorithms and the baseline algorithms designed for stationary environ-
12

---

Published in Transactions on Machine Learning Research (10/2022)
Abrupt change
Gradual change
2000
Epsilon-Greedy
3500
Epsilon-Greedy
Random-Exploraton
Random-Exploration
1750
LSVI-UCB
3000
LSVI-UB
LSVI-UCB-Restal
LSVI-CB-R
Cumuuativ lalve reward
MDD-LSVI-UCB-Retta
Cumulativv reward
25.00
ADA-LSVI-UCB-Rettan
1250
LSVI UCB Unknown
LSVI-UCB Unknown
MASTER
2000
MASTER
1000
OPT-WLSVI
OPT-WLSVI
1500
750
500
250
500
2500
5000 7500 10000 12500 15000 17500 20000 Total timestep
2500 5000
7500 10000
Total timestep
Figure Comparisons of different methods on cumulative reward under two different environments. The results are averaged over trials and the error bars show the standard deviations. The environment changes abruptly in the left subfigure, whereas the environment changes gradually in the right subfigure.
ments is larger in this setting. The reason is that the algorithms designed explore in stationary MDPs are generally insensitive to abrupt change in the environment. For example, UCB-type exploration does not have incentive to take actions other than the one with the largest upper confidence bound of Q-value, and if it has collected sufficiett number of samples, it very likely never explores the new optimal action thereby taking the former optimal action forever. On the other hand, in gradually-changing environment, LSVI-UCB and Epeilon-Greedy can perform well the beginning when the drift of environment is small. However, when the change of environment is greater, they no longer yield satisfactory performance since their Q function estimate is quite off. This also explains why LSVI-UCE and Epsilon-Greedy outperform ADA-LSVI-UCB the beginning in the gradually-changing environment, as shown in Figure
Figure 2 shows that the rumning times of COy--UCB-Restat and LSA-LSVI-UCB- -esttrtt are roughly the same. They are much less compared with MASTER, OPT-NLSVI, LSVI-UCE, Segiloon-Greedi This is because WUHIUCB-Restaae and Mta-LsvI-UCB-Retaal can automatically restart according to the variation of the environment and thus have much smaller computational burden since it does not need to use the entire history to compute the current policy each time step. The rumning time of ASWI-UCB-Unkn than LSVI-UCB- since the epoch larger is larger due the lack of the knowlege of total variation B, but it still does not use the entire history to compute its policy. Although Random-Exy Exttom--Epporation takes the least time, it cannot find the near-optimal policy. This result further demonstrates that our algorithms are not only sample-eficciet, but also computationally tractable.
is larger
7 Conclusion and Future Work
In this paper, we studied nonstationary RL with time-varying reward and transition functions. We focused on the class nonstationary linear MDPs such that linear function approximation is sufficient to realize any value function. We first incorporated the epoch start strategy into LSVI-UCB algorithm (Jin et al., 2020) to propose the LSVI-UCB-Restart algorithm with low dynamic regret when the total variations are known. We then designed parameter-free algorithm Ada-LSVI-UCB-Resse dynamic regret bound without knowing the total variations. We derived minimax regret lower bound for nonstationary linear MDPs to demonstrate that our proposed algorithms are near-optimal. Specifically, is near order-optimal except for the dependency
that enjoys slightly worse
when the local variations are known, LSVI-UCB-Restan on feature dimension d, planning horizon H, and some poly-logarithmic factors. Numerical experiments demonstrates the effectiveness of our algorithms.
A number of future directions are of interest. An immediate step to investigate whether the dependence the dimension d and planning horizon H in our bounds be improved, and whether the minimax regret
13

---

Published in Transactions on Machine Learning Research (10/2022)
Comparison of running time
1400
1373.9
MASTER
1281.1
OPT-WLSVI
LSVI-UCB
1200
Opsilonn-Greed
LSVI-UCB-Unknowin
ADA-LSVI-UCBRRsstar
1000
LSVI-UCB- Random-Exploration
Time (seconds)
800
600
400
282.9 -
213.
213.5
177.945.2
202
200
162.2
44.8 8.2 1.1
59.8
10.1 11.31.3
Abrupt Change
Gradual Change
Figure 2: Comparisons of different methods on rumning time for two different environments. The results are averaged over 10 trials and the error bars show the standard deviations. See Appendix E.2 for details on hardware.
lower bound can also be improved. It would also be interesting to investigate the setting of nonstationary RL under general function approximation (Wang et al., 2020; Du et al., 2021; Jin et al., 2021), which is closer to modern RT. algorithms in practice. Recall that our algorithm more computationally efficient than other works. Another closely related and interesting direction is to study the low-switching cost (Gao al,, 2021) or deployment efficient (Huang et al., 2021) algorithm in the nonstationary RL setting. Finally, our algorithm is based the Optimism in Face of Uncertainty. There is another broad category of algorithms called Thompson Sampling (TS) (Agrawal & Jia, 2017: Russo, 2019; Agrawal et al., 2021; Xiong et al., 2021; Ishfaq et al., 2021; Dann et al., 2021; Zhang, 2022). It would be an interesting avenue to see whether empirically appealing TS algorithms are also suitable in nonstationary RL settings.
References
Yasin Abbasi-Yadkont Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lincar stochastic bandits. In Proc. 25th Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), pp. 2312 -2200, December 2011.
Yasin Abbasi- Ybdksi- Aldo Pacchiano, and My Phan. Regret balancing for bandit and rl model selection. arXiv preprint ar arXix:2006.05.4 2020.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. In Conference on Learning Theory, pp. 12 38. PMLR, 2017.
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural complexity and representation learning of low rank MDPs. In Proc. 34th Annu. Conf. Newral Inf. Process. Syst. (NeurIPS), December 2020.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-caso regret bounds for randomized least- squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1566-6573 2021.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194 2017.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Shipra Agrawal and Randy Jia. Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management. In Proc. 20th ACM Conf. Electron. Commer. (EC'19), pp. 743-744 744, June 2019.
1lge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng, Qiming Yuan, Wojeiech Zaremba, and Lei Zhang. Solving rubik's cube with a robot hand. arXiv:1910.07113 [cs.I.G],, October 2019.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finile-time analysis of the multiarmed bandit problem. Machine Learning, 27(223))235-222 256, May 2002a.
Peter Auer, Nicolo Desa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48 77, 2002b.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-1600 2010.
Alex Ayoub, Zeyu Jia, Csaba. Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, 2020.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non-stationary rewards. In Proc. 28th Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), pp. 199 207, December 2014.
Lilian Besson and Emilie Kaufmann. The generalized likelihood ratio test meets klueb: an improved al- gorithm for picco-wisc non-stationary bandits. Proceedings of Machine Learning Research vol XX, 1:35, 2019.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1-3):33-55 57, March 1996.
J Bretagnolle and C Huber. Estimation des densités: risque minimax. Zeilschrift für Wahrscheimlickkeit theorie und verwandte Gebiete, 47(2):119-133 1371 1979.
Sébastien Bubeck and Nicolo
Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122 2012.
Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo. Real-time bidding by reinforcement learning in display advertising. In Proc. 10th ACM Int. Conf. Web Search Data Min. (WSDM 17), pp. 661 670, February 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization.
In Proc. 37th Int. Conf. Mach. Learn. (ICML 2020), July 2020.
Jinglin Chen and Nan Jiang. Information-theeorttic considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alckh Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. aix preprint arxi::220..11 10770, 2022.
Liyu Chen and Haipeng Luo. Near-optimal goal-oriented reinforcement learning in non-stationary environ- ments. arXie preprinl arXiv:2205.1300 2022.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non-stationarity, In Proc. 22nd Int. Conf. Artif. Intell. Stat. (AISTATS 2019), pp. 1079-1087, April 2019.
Wang Chi Cheung, David Simchi- Levi, and Ruihao Zhu. Non-stationary reinforcement learning: The blessing of (more) optimism. In Proc. 37th Int. Conf. Mach. Learn. (ICML 2020), July 2020.
Corinna Cortes, Giulia DeSalvo, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Discrepancy- based algorithms for non-stationary rested bandits. ar preprint arXiv: 1117011011..77 2017.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Thomas M Cover and Sandeep Pombra. Gaussian feedback capacity. IEEE Transactions Information Theory,
January 1989.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. Proc. 21st Annual Conf. Learning Theory (COLT 2008), pp. 355-366, July 2008.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. provably efficient model-free posterior sampling method for episodic reinforcement learning. Aduances in Neural Information Processing Systems, 34:12040-12055 2021.
Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for cmdps with non- stationary objectives and constraints. arXiv preprint arXiv:2201. 11902001.199,, 2022.
Kefan Dong and Tengyu Ma. Asymptotic instance-optimal algorithms for interactive decision making, arXiv preprint 220: 02326, 2022.
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Vn-regret for learning in Markov decision processes with function approximation and low Bellman rank. In Proc. Conf. Learning Theory (COLT), pp. 1554 1557, July 2020.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In International Conference on Machine Learning, 2021.
Damien Ernst, Picrre Gourts, and Louis Wehenkel. Tree-basod batch mode reinforcement lcarning. Journal of Machine Learning Research, 6:503 556, 2005.
Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie. Dynamic regret of policy optimization in non-stationary environments. In Proc. 33rd Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), December 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprinl arXiv:2112 122.:11111111 13487, 2021a.
Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity contextual bandits and reinforcement learning: disagreement-base based perspective. In Conference on Learning Theory, 2021b.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:8101.00494, 2021.
Aurélien Garivier and Fric Moulines. On upper-confidence bound policies for switching bandit problems. In Proc. Int. Conf. Algorithmic Learning Theory (ALT 2011), pp. 174 188, October 2011.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971 9019. PMLR, 2022.
Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Yan Liu. Towards deployment- reinforcement learning: Lower bound and optimality. In International Conference Learning Represen- tations, 2021.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. International Conference on Machine Learning, pp. 4607-4616. PMLR, 2021.
Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proc. 34th Int. Conf. Mach. Learn. (ICML 2017), pp- 1704-1713, August 2017.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Proc. Conj. Learning Theory (COLT), pp. 2137-2143, July 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and samplo-efficient algorithms. In Advances in Neural Information Processing Systems, 2021.
Sven Koenig and Reid G Simmons. Complexity analysis of real-time reinforcement learning. In Proc. 1 11th Nat. Conf. Artificial Intell. (AAAI), pp. 99 107, 1993.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 8340-3348. PMLR, 2021.
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust exploration in episodic reinforcement learning. Conference on Learning Theory. PMLR, 2021.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Near-optimal regret bounds for model-free rl in non-stationary episodic mdps. In Proc. 38th Int. Conf. Mach. Learn. (ICMI, 2021). 2021.
Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In Proc. Int. Conf. Computational Learning Theory (COLT 2007), pp. 308-322 June 2007.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, (18(7540):529--388 February 2015.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement. learning using linearly combined model ensembles. In Proc. 23rd Int. Conf. Artif. Intell. Stat. (AISTATS 2020), pp. 2010-2020, August 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alckh Agarwal. Model-free representa- tion learning and exploration low-rank mdps. arXiv preprint urXi::2102.000 07035, 2021.
Mehryar Mohri and Scott Yang. Online learning with transductive regret. In Proc. 31st Annu. Conf. Neural Tnf. Process. Syst. (NeurIPS), pp. 5220-5230, 2017a.
Mehryar Mohri and Scott Yang. Online learning with automata-based expert sequences. orXiv preprint
arXiv:1705.00:: 2017b.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value itcration. Journal of Machine Learning Research, 9(5), 2008.
Gergely Neu and Julia Olkhovskaya. Online learning in MDPs with linear function approximation and bandit feedback. In Proc. 34th Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), December 2021.
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Proc. 36th Anna. Conf. Uncertainty in Artificial Intelligence (UAT'20), pp. 81-90, August 2020.
lan Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Proc. 33rd Int. Conf. Mach. Learn. (ICML 2016), pp. 2377-2386, June 2016.
Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 2019.
17

---

Published in Transactions on Machine Learning Research (10/2022)
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit, problems. Advances in Neural Information Processing Systems, 33:10328 10337, 2020.
Martin L Puterman. Markoe Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Hoboken, NJ, USA, 2014.
Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary enviromments. In Proc. 33rd Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), 2019.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Advances in Newrul Information Processing Systems, pp. 14410-14420, 2019.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv:1610.03295 [cs.AI]], October 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Malthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676):354-355, October 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanclot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through sclf-play. Science, 362( December 2018. doi: 10. /02///ciencc.aar6-011..
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, USA, 2018.
Ahmed Touati and Pascal Vincent. Efficient learning in non-stationary linear markov decision processes. arXiv preprint Xim:22000. 12870, 2020.
Lingda Wang, Huozhi Zhou, Bingcong Li, Lav R Varshney, and Zhizhen Zhao. Nearly optimal algorithms for piecewise-stationary cascading bandits, arXiv:1909.05888 005.86vv [cs.LG]., September 2019.
Ruosong Wang, Ruslan Salakhutdinov, and Lin Yang. Provably efficient reinforcement learning with general value function approximation. In Proc. 34th Annu. Conf. Newral Inf. Process. Syst. (NeurIPS), May 2020.
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279-2))) 292, May 1992.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. Combrdge, 1989.
PhD thesis, University of
Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference Learning Theory, pp. 4300-4354. PMLR, 2021.
Chen-Yi Yu Wei, Mchdi Jafarnia-Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite-horizon average- reward MDPs with linear function approximation. In Proc. 24th Inl. Conf. Artif. Intell. Stat. (AISTATS 2021), April 2021.
Zhihan Xiong, Ruoqi Shen, and Simon S Du. Randomized exploration is near-optimal for tabular mdp. arXiv preprint Xrx::22002. 09703, 2021.
Lin F Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In Proc. 36th Int. Conf. Mach. Learn. (ICML 2019), June 2019.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Math. Oper. Res., 34(3):7377777 -757, August 2009.
18

---

Published in Transactions on Machine Learning Research (10/2022)
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathemalics of Dala Science, 4(2):834-85)) 857, 2022.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zui-Hua Zhou. simple approach for non-stationary linear bandits. In Proc. 23rd Int. Conf. Artif. Intell. Stat. (AISTATS 2020), pp. 746-755, August 2020.
Yufan Zhao, Michael R Kosorok, and Donglin Zeng. Reinforcement learning design for cancer clinical trials. Statistics in Medicine, 28(26):3294 3315, November 2009.
Han Zhong, Zhuoran Yang, and Zhaoran Wang Csaba Szepesvári. Optimistic policy optimization is provably efficient in non-stationary mdps. arXiv preprint orXiv:2110. 100.9844, 2021.
Dongruo Zhou, Jiafan Нe, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference Machine Learning, pp. 12802. PMLR, 2021.
Huozhi Zhou, Lingda Wang, Lav R Varshney, and Ee-Peng Lim. near-optimal change-detection based algorithm for piecewise-stationary combinatorial semi-bandils. In Proc. 34th AAAI Conf. Arlif. Intell., pp. 6933 6940, February 2020.
19

---

Published in Transactions on Machine Learning Research (10/2022)
A Proofs in Section 3
To prove the minimax dynamic regret lower bound for the homogeneous setting, we first prove the minimax regret. bound for linear MDP with homogeneous transition function.
Theorem 8. For any algorithm, if 2 4 and T 2 3)3 then there exists at least one stationary linear MDP instance that incurs regret at least (T)
The key step of this proof is to construct the hard-to-learn MDP instances. Inspired by the lower bound construction for stochastic contextual bandits (Dani et al., 2008; Lattimore & Szepesvári, 2020), we construct an ensemble of hard-to-lcarn 3-state linear MDPs, which is illustrated in Figure 3. This construction can be viewed as a generalization of the lower bound construction for linear contextual bandits (Dani el al., 2008; Lattimore & Szepesvári, 2020). The intuition is that the reward distributions under optimal and suboptimal policies for these instances close: thus it is statistically hard for any learner to identify the optimal policy.
8 (at, v)
8 (a'.
so
1 1 8 (a),))
1 - - (a'.v)
82
D
Figure 3: Graphical illustration of the hard-to-learn linear MDP instances with deterministic reward.
Each linear MDP instance in this ensemble has three states 81, 82 (81 and 82 absorbing states), and it is characterized by unique (d - d)-minnnsi vector ( 3) VTJ--3, Specifically, the vector v defines the transition function of the corresponding MDP, as illustrated in Figure 3. Each action a of this MDP instance encoded by (d (d-3) 3) dimensional vector a E (#1/vd-33 d-3 The reward functions for the three states are fixed regardless of the actions, specifically, r(sg, a) r(22, a) 0,,((1, a) 1, Va A. For each episode, the agent starts at so, and ends at step H. The transition functions of the linear MDP parametrized by are defined follows,
|s a) = (a, v), P(82|80; a) =1 1- 5 (a, v), PPs)|/1,, = 1, PP(82 a) = 1,
where = J. Notice that the optimal policy for the MDP instance parametrized by v is taking the action that maximizes the probability to reach $1, which equivalent to taking the action such that its corresponding vector a satisfies (g,) = sgn(æ;), Vi E (d-3). Furthermore, can be verified that the above MDP instance is indeed a lincar MDP, by sctting:
(530, (0, 10,118,))) (b)) o (0,10,,,0)
((s)) ((s)
= (0,1,-1,-
Remark 7. Note that the above parameters violate the normalization assumption in Definition but it is straightforward to normalize them. We ignore the additional rescaling to clarify the presentation.
After constructing the ensemble of hard instances, we can derive the minimax regret lower bound for sta- tionary linear MDP for the homogeneous setting.
20

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Theorem 8. Let Př,v (assume t is multiple of H) be the probability distribution of {at, -x=1 rhe ai, r 1/H Σm= I' j of rumning algorithm π on linear MDP parametrized by First note that by the Markov property of π, we can decompose D (KL(PT (K.(PT,,llPT, as
1/H
4/H Σ
H Σ
H |IP
Σ palay, o' b') A=1
EDKL
P
rlall 0)
Recall that due to hard cases construction, the first step in every episode determines the distribution of the total reward of that episode; thus
H
H Σ rhlldt (Ehlecior)) o1))
Σ (alaio0 Exhldti
DKL
IP
1|l
h=1
ö (a), v) =66 + (a'; 0)) log + (at, v²)
(1 - 8- (al,, 0)) --(08,,,,)) log - ô (aa, 1) - (a),
(6)
We bound the KL divergence in (6) applying the following lemma. Lemma 5. (Auer et al,, 2010) O < 8' S 1/2 and < 1 28', then
8'
1-8 8'
2(e')2
8' log
- (1 8')
8' +e e'
el 8'
To apply Lemma 5, we let v) hold for any a, v, v/:
v) + d = 8 (v- - -', di) = =é' Thus we must ensure the following inequalities
(d 3V
(a, u) + 85
+ 8 $ 1/2
VT
2(d 3)VH
(d 3V (d-3)VH
(u ,' S
+8
s 1--28' 28'.
VT
VT
To guarantee the above incqualities hold, we can set and let (d-3)vB
S 1.4 Now we get back
VT
bounding Eq. 6. Let A (d-3)VII and suppose and uf only differ in coordinate. Then VT
DKL
P
Σ
Ehildh v)
11
|IP Σ Erilch )) < 1=1
"
8A
16A 5(d
64H T
8-A
332
A==
Furthermore, let Eib be the the following event:
H1 E [K] sgn(a))) + sgn(b))12 1
K. 2
Let Qi.r = P(E,, [o], the probability that the agent is taking sub-optimal action for the i-th coordinate for at least half of the episodes given that the underlying linear MDP is parameteriezed by v. We can then lower bound the regret of any algorithm when running on lincar MDP parameterized by as:
H Ri K(H 10--11)) 1)
Reg,
T
i=1
2 (VTH - VK
Σ ki
(7)
since whenever the learner takes sub-optinal action that diflers from the optimal action by one coordinate, it will ineur 2 (H expected regret. Next we take the average over 2d-3 linear MDP instances to
21

---

Published in Transactions on Machine Learning Research (10/2022)
show that average it incurs H(dyHT) regret, thus there exists at least one instance incurring ((d regret. Before that, we need to bound the summation of bad events under two close linear MDP instances. Denote the vector which is only different from v in i-th coordinate as o Then we have
4 + Ni = PP Ei [o] + 1P 10:
= P( |o] + P 100
1
2 exp( exp(-Dxxi -DKL( Pr..=)))
2
1
exp(-64),
(8)
where the inequality is due to Bretagnolle-Huber Huber inequality (Bretagnolle & Huber, 1979). Now we are ready to lower bound the average regret over all linear MDP instances.
VIT
VK
Reg, (T)
2d 3
2d-3
jml
HT VK
d-3
fi.0 + vi
26-3
/HT VK
2d-3 3
04
(d
(d- -3)
2d-3
4
2 ((dVHT)
where the first inequality is due to (7), and the third inequality due to (8).
Based on Theorem 8, we can derive the minimax dynamic regret for nonstationary linear MDP.
Proof of Theorem 1. We construct the hard instance as follows: We first divide the whole time horizon T into K
N intervals, where each interval has K episodes (the last interval might be shorter K is not a multiple
of N). For cach interval, the lincar MDP fixed and paramcterized by a u (= ( which we define when constructing the hard instances in Theorem 8. Note that different intervals are completely decoupled, thus information is not passed across intervals. For each interval, incurs regret at least (ddVIIN by Theorem Thus the total regret is least
VN
K 1)2((NPPN
Dyn-Reg(T T) Z (1
(9)
Intuitively, we would like N to be as small as possible to obtain tight lower bound. However, due to our construction, the total variation for two consecutive blocks is upper-bounded. by
d-3
4(d - 3) 2(d 3) VN
N
Note that the total time variation for the whole time horizon is B and by definition B> 2(d-3) which implies N 2 2/332
(L 1),
VN
2/3 k2/3). Substituting the lower bound of N into (9), we have
Dyn-Reg(TT) 2 S(B1/3 2/3 2/ 2/3 2 S(B-/3 2 1332233
which concludes the proof.
Finally, provide the formal proof for Theorem 2.
22

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Theorem 2. We construct the hard instance follows. We first divide the whole time horizon T into [&] intervals, where each interval has [ episodes (the last interval might be shorter if K is not multiple of N). For each interval, the linear MDP is fixed and parameterized by a v = defined in Lemma E.1 in Hu et al. (2022). Note that different intervals completely decoupled, thus information is not passed across intervals. For each interval, incurs regret least [[dd/H*N) by Lemma E.1 in Hu et al. (2022). Thus the total regret is at least
{+ NH 3d-1,
K 1)D(dVH'N)) Dyn-Reg(T) 2
(10)
Intuitively, we would like N to be small as possible to obtain tight lower bound. However, due to our construction, the total variation for two consccutive blocks is upper-bounded by
Vd-I
32NH 4/2/NH
Note that the total time variation for the whole time horizon is B and by definition B 2 //////KKK///1/111 which implies N 2 12(B22/30) /2/3 Substituting the lower bound of N into Eq. (10), we have
Dyn-Reg(T)) 2 S(B2/3 (0BB//,5//0 //6 HT2
which concludes the proof.
B Proofs in Section 4
Here we provide the proofs in Section 4. We first want to comment that our algorithm builds on LSVI-UCB. LSVI can be seen as a specialization of the regression- basod Fitted Q-Itcration algorithm (Ernst et al., 2005; Munos & Szepesvári, 2008; Chen & Jiang, 2019) to the linear case, and LSVI-UCB (Jin al., 2020) further adds the bonus term top of that to handle exploration.
Now, we introduce some notations we use throughout the proof. We let wh, AA and Q as the parameters and action-value function estimate in episode & for step h. Denote value function estimate as (*(()) = max, (f,ss)) For any policy т, we let WT Q7, be the ground-truth parameter and action-value function for that policy in episode k for step h. We also abbreviate Φ6s), af))) as / for notational simplicity.
We first work on the case when local variation is known and then consider the case when local variation is unknown.
B.1 Case 1: Known Local Variation
Before we prove the regret upper bound within one epoch (Theorem 5), we need some additional lemmas. The first lemma is used to control the fluctuations in least-squares value iteration, when performed on the value function estimate (+)(-) maintained in Algorithm
Proof of Lemma 1. The lemma is slightly different than Jin et al. (2020, Lemma B.3), since they assume PA is fixed for different episodes. It can be verified that the proof for stationary case still holds in our case without any modifications since the results Jin et al. (2020) holds for least-squares value iteration for arbitrary function in the function class of our interest, i.e., (V = ( un) w E Rd). Let us first. restate Lemma B.3 in Jin al. (2020) to compare against our Lemma 1.
23

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma 6. (Lemma. B.3 in Jin et al. (2020)) There erists absolute constant C' that is independent of cp such that for any fixed p E [0, 1), if we let the event E. be the following,
h) E [ x H
Σ
- P (5 d/l1
S CdH log[2(cs + /p)W/p). (A8)-1
then event E happens with probability at least p/2.
To prove Lemma 1, we need the following technical lemmas.
Lemma 7. (Lemma D.4 in Jin et al. (2020)) Let { a stochastic process on state space S with corresponding filtration {Fr 100 Let {Ør]7=1 be a RRd-vel stochastic process where or F and I| < L. Let A₁ = A Σi=1 0, Then for any ô > 0, with probability at least 1 1- ö, for all k > 0, and V so that sup,]V(z)]= H, we have
k+ > log No +
812
Σ o -
BVV
S 4H log(
2 d 5
where N2 is the covering namber for V.
Lemma 8. (Lemma D.6 in Jin et al. (2020)) For function class with the following form,
V() minnmmxx w Φ(.,a) + 8V
satisfying the constraints given by Jin et al. (2020), the log covering number log No for this function class is upper bounded by d logg(1 SHv//e) d log Sd-122 =dd-123//(xe"))
By applying Lemma 7 and Lemma 8, and setting X L, k = CdH log(2dT/p), we prove Lemma 1.
We then proceed to derive the error bound for the action-value function estimate maintained in the algorithm for any policy.
Proof of Lemma 2. Note that (h a) = (o(s, a), w First we can docompose w woijk as
1=1
w/ whi = (A -
Σ
& (s d + 1 - =w
1=7
(A
w Σ 1h (s) 18 V (5) dbl Σ oh oh) r1(5)h ob)
k-1
= -(AR)) -1 Lu + (A Σ
$ Vi h+t (sh+1) - Ph (sh.
+ (A
IM - PAy a/,1 + (A Σ ( - V (,t,, ah)
k-1
+ + Σ
(h - ob
24

---

Published in Transactions on Machine Learning Research (10/2022)
We bound the individual terms right side one by one. For the first term,
(((s, O) = K a),
S I |1 (1((s,)))laa))) =
2H (1 ::
where the last inequality is due to Lemma 12. For the second term, we know that under event E defined in Lemma 1,
(Ø((,,), 2/1 CdH
/ /og(2(cs 1ydw//llld(s 1-
For the third term,
R-1
(Ø(8, 3 ( a) (A%)
&1((P) - P
((s,a) (A (AA)) 2% I[(%/ - PAV ah)1
SBull
SBp
(0(s, 1
Σ ( (A
d(d(k B, H [[ ( a)ll(a)>1
where the first three inequalities are due Cauchy-Schwand inequality and boundedness of P/ IP. and V h++1 and the last inequality is due to Lemma 13. For the fourth term,
(Ø(s,a), a), (0(s, a), (A
H Pi (hh
= (K(s, (At))
(T(rT)T (vhL
= ( / (v V ( - a), / (V V
where
6 (P h+1 ((,, and 7 < 22H/Vll0( a)l due to Cauchy-Schware inequality.
For the fifth term,
(Ø(s.a) 5 (0(s, (AA) Σ shib ah) r/(shh ab))
k-1
10(8, a) - a/h) ((0hh:%))
$ d(k 7) Bo, || a) a)
25

---

Published in Transactions on Machine Learning Research (10/2022)
where the incqualities are derived similarly as bounding the third term. After combining all the upper bounds for these individual terms, we have
((((s,)) a). w - (h, - -PP (Vit+ - v (s,
S4HVa (Io a) Mal + CdH /ogg2((0 /CdlH
1)dW/1) II ()
- Bo v d(k - 7) ())(a)))) + B H d(k |1 ()))
<CodHl /llgl///g///////oooo /l a) (((at))) + Bo, v d(k -)) (1 (l(()))))))) |
BB,,e V d(k 7) (1(3.
The second incquality holds if we choose a sufficiently large absolute constant Co.
Lemma 2 implics that the action-value function estimate we maintainod in Algorithm is always an optimistic upper bound of the optimal action-value function with high confidence, we know the local variation.
Proof of Lemma 3. We prove this by induction. First prove the base case when = H. According to
Lemma 2, we have
a))(s,),, wht (s,(s, 3x (l((s, (1)(,,)))()))--
which implics
(),aa = min((w ((8, a)) + Br (1)(s (1) HJ 2 VH.
Now suppose the statement holds true at step h 1, then for step h, due to Lemma 2, we have
(()(s,a), w - (),(s,a) - (V Vi+ (s, Be (0((,
By the induction hypothesis, we have P1 ((t,,,)(s, 2 20, thus
(h(s min ((,,((,.sss))))) + Ba ( , 2 (s.
Next we derive the bound for the gap between the value function estimate and the ground-truth value function for the executing policy t o = va (st) VT (s in recursive manner.
Lemma 9. Let 6 Vh - V (, shtt E(8h+11 atl 5 Under event E defined in Lemmaa 1, we have for all (k, h) E E x [
_ < sh + sh+z + 23x ||
Proof. By Lemma 2, for any (8, h k) E s A E,
Q)(s,a) Q (s, < (V V (s, 23x (I((
Note that Q (s), att max, ( a) = (s according to Algorithm 1, and Q at) = (it(s by the definition. Thus,
8 s 8h + chi + 23x 1
Now we are ready to derive the regret bound within epoch.
26

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Theorem 3. We denote the dynamic regret within that epoch Dyn-Reg(E). We define o (s - V and Sh+1 = 1 af] - 6/ as in Lemma. 11. We derive the dynamic regret within epoch & (the length of this epoch is W which is equivalent to πf defined in Lemma I which happens with probability at least 1 p/2.
w episodes) conditioned on the event E
Dyn-Reg(E)
Σ
Vite(s)) ViTk
REy
Σ
(f
VI
KEE
Σ 8
KEE
ch +
Σ 8k KEK
> h=1
(
(11)
REE -=1
where the first incquality due to Lemma 3, the third incquality duc to Lemma For the first term the right side, since V is independent of the new observation oh {Gh) is martingale difference sequence. Applying the Azefa-Hogflding inequlity, we have for any >>
H Σ
21 2 exp(-2/ H))
h=1
Hence with probability at least p/2, we have
c 2H W log(2dW/p).
(12)
For the second term, we bound via Schway-Schwarz inequality:
H
H
2 KEE
8k
| [oillaap=
2CodH 2Codd ((dWpp)
O ll (ag))
+2 >
BB,e v
d(k T)
0
1=1
REE h=1
KEE
H T)
+ Σ B,H V d(k -
+ fll (aa))
39y
h=1
< 2nnH v log (ddWp)
W/H
|
1)1/2
1
+ 2
BA.E d(k 1/2
| (AA) 2)2/2
1=1 3Ey
3Ey
Bu H vd(k--)))
| 11 (AA) 2
key
11
< 20ndH / log (pdWpp)
W/H(
h=1
3Ey
W
+2
Ba Vd
| (AA)
(()))))))
+2
Bo /dw
1 ((a))1))
14/2
(13)
P=
KEy
27

---

Published in Transactions on Machine Learning Research (10/2022)
By Lemma 14, have
|1 (M =
W d
+1)
(14)
H
KEE
Finally, by combining Eq. 11-14, we obtain the regret bound within the epoch as:
Dyn-Reg(E) S 0/2 Bo,edW + &B,.ddW)..
By summing over all epochs and applying a union bound, we obtain the regret bound for the whole time horizon.
Theorem 9. If we set B By odl / /og( Be, V dd(k B Vd(k -), the dynamic regret of SSVI-UCBBRestare is 0(H312 1/2 BodW + +BddW)), with probability at least 1 1-p.
Proof. In total there are N w epochs. For cach epoch & we set N: then will incur regret ( H3/2 + Bo,e, dW + B,,,, dHW) with probability at least. - - By summing over all epochs and applying the union bound over them, we can obtain the regret upper bound for the whole time horizon. With probability at least 1 --p,
Dyn-Reg(T)
Σ Dyn-Reg(E.)
E.
2 0 3//22//2/222 + dW. + Bp,, dHW)
8,
2 //23//2//211 1/2 BodW BBddHW.
B.2 Case 2:
Unknown Local Variation
Similar to the case of known local variation, first derive the error bound for the action-value function estimate maintained in the algorithm for any policy, which is the following technical lemma.
Lemma 10. Under event E defined in Lemma 1, we have for any policy n, Vs, a.a,, x Ax [H] x E,
((b(s,) a). w (8, (V h++1 V (s, B 11b(, A)l + Bo, / d(k- + B,, H H d(k T),
where 8 = CodH /log(2dW/p) and T is the first episode in the current epoch.
Proof.
This lemma is looser upper bound implied by Lemma 2. By Lemma 2, we have p2 (V/++ - V (s,
((b(s, w -
sC,dH (ogg(2W/p)))))ooooooooo/// |1 ((( + Ba.8 / d(k (1b(s)
+ + / d(k - (l)
SC,tH
+ Bo v d(k-
+ B,.eH d(k-)),
where the second incquality is due to || a)ll < 1 and Amin (A 2 1, thus (()())))) $1.
Different from Lemma 3, when the local variation unknown, the action-value function estimate we main- tained in Algorithm 1 is no longer an optimistic upper bound of the optimal action-value function, but approximately up to some error proportional to the local variation.
28

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Lemma 4. We prove this by induction. First prove the base case when h H. According to
Lemma 10, we have
( a), - s 5 (lla))))))))))11 + Ba,e Bo -7) + Bu, Vdlk 7),
which implies
(s, = min o(s, a)) + +)1l)(
(H,((s,a) (Be d(k r) Bp d(k r)).
Now suppose the statement holds true at step h + 1, then for step h, due to Lemma 10, we have
((((s, w - Q,, - (V - (s,
<B (((())))))( + Bo, / - Bu, d(k-
By the induction hypothesis, we have [P (i++,)((ssa) 2 -(H + 2) d(k 5) +
Bu.eH ddlk r)), thus
ah( min((1t (ls 3 11 ((()))
2 (s, - (H - 1) (B. d(k T) + B d(k T)).
Similar to Lemma 9, next we derive the bound for the gap between the value function estimate and the ground-truth value function for the executing policy 2², of = (s - V (s in a recursive manner, when the local variation is unknown.
Lemma 11. Let 6% V (st) Vo sh+1 Bi6 1s atl t- Under event E defined in Lemma 1, we have for all (k, h) E x [H],
t h+ + ch+1 + 2B 11 + Ba.
B H H 7).
Proof. By Lemma 10, for any (s, E SS [
(h) Q (s, (h va (s,a) + 23 ||| a)) Ba.5 /dkk + Bn Vd(k: T).
Note that Q ( at) max, (h a) = (s) according to Algorithm 1, and Q7 att (it) by the definition. Thus,
8 < 5/4 + ch+1 + 2/ 281108 + Ba,s / d(k r) + B H Vd(k -)) r).
Now we are ready to prove Theorem 5, which is the regret upper bound within one epoch.
Proof of Theorem 5. We denote the dynamic regret within an epoch Dyn-Reg(E). We define o (st) - (* and sht = 1[ at] 5h as in Lemma 11. We derive the dynamic regret within epoch & (the length of this epoch is W which is equivalent to W episodes) conditioned on the event. E
29

---

Published in Transactions on Machine Learning Research (10/2022)
defined in Lemma 1 which happens with probability at least 1 p/2.
Dyn-Reg(E)
Σ
(it)((+) Vi (ot)
KEE
[iv((s) B H vdlk -) + BB H?2 Vi(k- v(f)
Σ1 1o
Bo,e v
+ B Bugll? /dlk d(k-
H
t + 2
o ( + Σ
BB, V Σ KEE
BusH dd(k->
REE h=1
KEy h=1
REE
H
2/3
| (il)
Bo,e W v W + 1)+ B,, W Wd(W + H)
(15)
KEE -=1
KEE
where the first incquality due to Lemma 4, the third inequality is due to Lemma. 11, and the last inequality is due Jensen's inequality. Now we need bound the first terms in the right side. Note that {sh is martingale difference sequence satisfying K 2H for all h). By Lauma-Hoeffding inequality we have for any t> >>0 0,
H
TP
21
2
FAEE
h=11
Hence with probability at least - p/2, we have
ΣΣ<
ch S 21 / log(2dW/p)) /p).
(16)
KEE
For the sccond term, note that by Lemma 14 for any E [H],
we have
Σ(tt) [O)) + s 2log
det(AA(+) !e
2d
W
H +
+1)
KEE
By Cauchy-Schwaad inequality, we have
1/2
ΣΣ BEE Æ=1
O (AE)-
I Σ
W/H
h=1
LKEE
W
W
<
2d
log
+1
H
H
W
<
H
2d
log 12W/pp.
(17)
H
Finally, combining Eq. 15-17, we have with probability at least 1 p.
Dyn-Rog(E) $ 2H / / Wog((2WW/p) + CodH2 (og(ddd))))))) s/p 2d W
log log(2dW/r)
H
+ Wo. 22((W/H B,,eW 2d H + +
SOV + Ba, / d/ B,G +B dHW3/2).
30

---

Published in Transactions on Machine Learning Research (10/2022)
Now derive the regret bound for the whole time horizon by summing over all epochs and applying union bound. We restate the regret upper bound and provide its detailed proof.
Theorem 10. If we set B = edH / log(2d7) /p), the dynamic regret of LSVI-UCB-Ress Restart algorithm is H812 0(W-1/2T:8/2Fp) H2/2 + 2 + Bad
with probability at least 1 - p.
Proof. In total there are = W epochs. For each epoch & we set = f: then will incur regret H(V Be, Vd..V///W33/ Bu.s, VdHw3/3) with probability at least 1 - N. By summing over all epochs and applying a union bound over them, can obtain the regret upper bound for the whole time horizon. With probability at least 1 --p.
Dyn-Reg(T) = Σ Dyn-Rog(Ei) S ΣO(VBHO + BB. Va/Hw3/2 + Bu VJHW3/2) & x 50
&
2 1/2 + B B 22d //222
C Proofs in Section 5
In this section, we derive the regret bound for Sha-LLyI-UUB-Restaae algorithm.
Proof of Theorem 7. Let R&W,, of ( be the totol reward recieved in i-th block by running proposed LSVI-UCB- Resttrt with window size starting at state sf (1-1)M we can first decompose the regret as follows:
[ТУ Σ
Dyn-Reg(T) = (+t((t))
Ra .1
( +
Σ
(R,(W), of ) ) R& (W ((-1)H))
where term ! is the regret incurred by always selecting the best epoch size for restart in the feasible set Jw, and term ② is the regret incurred by adaptively tuning epoch size by EXP3-P, We denote the optimal epoch size in this case as W [(Ba + + 1/22/22 1 W S MH, thus there exists Wt Jw such that Wt S W S 2W', which vell-approximates the optimal epoch size up to constant factors. Denote the total variation of 0 and μ in block as Bo,; and By, respectively. Now can bound the regret. For the first term, have
It straightforward
verify that
[T/MH] 1 K Σ O(2 1/2 Bo 12 1/2 + id 12 (
010 Bod 1/2 Byd 12 (Wt
$ 0(8/12 0 12 332 + //2 H /2 2 O + B
where the first incquality is due to Theorem 6, and the third inequality is due to W differs from W up to constant factor. For the second term, we can directly apply the regret bound of EXP3-P algorithm (Bubeck & Desa-Bianchi 2012). In this case there are A = In M + 1 arms, number of equivalent time steps MH and loss per equivalent time step bounded within [0, H). Thus we have
S /LMH/AT/MB 0
Combining the bound of I and yields the regret bound of Ada ada-LsvI-UCB-RRstarr Dyn-Reg(T) $ O((B + B, +
31

---

Published in Transactions on Machine Learning Research (10/2022)
D Auxiliary Lemmas
In this section, we present some useful auxiliary lemmas.
Lemma 12. For any fized policy n,, let {Wi kejj be the corresponding weights such that Qh (s,a)
(Ø(s, a), whxx for all (s,a, h. k) E S A x [ x [K]. Then we have
| S 2HVd. V(k, E [ x [M],
Proof. By the Bellman equation, we know that for any (h, E [H] [K],
(s, = (rh + PAV
= (On, + Viriadunass)). ((s,a)
= -wo% ()),
where the second equality holds due to the linear MDP assumption. Under the normalization assumption in Definition 1, we have |00,,xll $ Vd, V+ti S and (s')l s vd. Thus,
wh,k S Vd H 2HHV
Lemma 13. Let A, I +i= 07 di, where Φr E Rdd then
Σ (A) 5 Sd.
Proof. We have Ei_ $. (At)) E Tr(o, (b:) TTr((A)) 2id.). After apply eigen- value decomposition, have Σi=1 Φ Udiag(A1 (A,,..,, and A, Udiag(A) + L,..., Aa 1). Thus E (A,) = Σ d.
Lemma 14. (Abbasi- Yodkori et al., 2011) Let { be a bounded sequence in Ti.d satisfying supr20 || S 1. Lel An E Bdxd be a posilive defonile matria. For any 1 O, we define A, Ao Σj= $3 Φj. Then if the smollest eigenvalue of Ao satisfies Amin(Ap 2 1, we have
det(AA)
ddt(AA) det(AA)
log
Φ A s 2
det
/=1
E Details of the Experiments
E.1
Synthetic Linear MDP Construction
The MDP has 15 states, 7 actions, = 10, d 10, and T 20000, and special chains. The states are denoted .1,...,88 88, and the actions are denoted 01,..., 0A. We first construct the known feature Φ. Intuitively, & represents the transition from S A space to d-dim space. We let the special chains have the correct transition to the d-dim space while other parts have random transition. This special transition will later be connected with Ma,k, (i.e., the transition from d-dim space to S space) to form the chain. A special property of the construction is at any episode k, the transition function only has one connected chain and such chain similar to combination lock. The agent must find this unique chain to achieve good behavior.
We let feature & have "one-hot" form (each (s, a) deterministically transits to a latent state in d-dim space), and satisfy the following:
32

---

Published in Transactions on Machine Learning Research (10/2022)
1. For special chain i = 1,....,,, 5, we have ((s;, = and ((s,, [x] 00 i. For i = 1.....5 and E [A], * i, we have ((8;, az)(m) = and (ss,, az)((] = 0,7 E [5],1 1 o n, where & is uniformly drawn from ,,..., 1, ,....,d.
2. For normal chain i 6, .,..., S and j E [A] we have ((s; az)[n] and ((8 a;) 0, [5].1 # n. where is uniformly drawn from .....dd
Now consider designing Pa,k- As mentioned the main text, we have set of 5 different MDPs, and they have unique but different good chains. The abruptly-changio environment abruptly switches the good chain (or linear MDP) periodically every 100 episodes, whereas the gradually-changing environment switches the good chain (or linear MDP) continuousl from one to another within every 100 episodes. In the following construction, we only design those 5 different MDPs for the Abruptly-changiin environment since we only need to take convex combination of different MDPs in the grudually-changinn case. For each of those 5 linear MDPs, we only let one special chain be connected, and it becomes the good chain. Other special chains are broken in the M part (i.e., the part transits from d-dim space to S space). When the good chain is g E [5] in episode k, let ph,k satisfy the following:
1. For good chain 9, Vh E [H], we have ( = 0.99, ( Mal = 0.01, and ( =
0, n # 9.9+ 1.
2. For other special but not good chain ğ E [5].9 * g, wh [H], we have (s) 0.01, Mh. [ = 0.99, and ph,k (sn, [g] 0, n E [S], + 9.9+1.
3. For all normal chain i .,...,d d, vh [M], we randomly sample two states ny and ng, and let (n, [[]] 0.8, (n.x(5.., M[j] = 0.2, and (s.a(s 0, [S], n # ni, 122
Finally we construct On which is related to the reward function. To ensure g E [5] is a good chain, we place a huge reward at the end of the chain but 0 reward for the rest of the chain. In addition, we put small intermediate rewards on sub-optimal actions. Specifically, when g is the good chain at episode k, On, is follows:
For good chain g, we have 0n, = 0, vh [H - 1], and [=]
2. For all other chains E [d]. i + wh E [H] we let 0n [i] uniformly sample from [0.005, 0.008).
In our construction, straighttorward verify that we have a valid transition function, and the transition function and reward function together satisfy the combination lock type construction. Notice that sometimes refer to the normal chain in the S space and sometimes in the d-dim space. The reason is that special chain must be connected in both parts (S x A space to d-dim space and d-dim space to S space), so we can break any part to make it a normal chain.
E.2 Hardware Details
All experiments are performed on Macbook Pro with 8 cores, 16 GB of RAM.
33


Reviews:
[{"review_id": "yTGWsjxY9r", "reviewer": "Reviewer_Kk4U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nOverall I think this is a good paper.\n\nTo my knowledge, the proposed algorithms and their analyses are new. They are simple and appear to provide fairly strong guarantees for the non-stationary problem. The lower bound also helps paint a comprehensive picture of the hardness of the problem, but it is not totally complete yet. While the algorithms are based on existing techniques (LSVI-UCB + epochs for non-stationarity) they appear to be used in a unique way to address this problem.\n\nThe discussion of related work appears to be thorough, but I cannot be 100% sure. There were a couple of points that were not clear to me mentioned in the next box.\n\nThe proofs generally follow the outline of proofs in Jin et al with some modifications to deal with the non-stationarity. Though the technical novelty of the modifications is small, the simplicity is desirable. I have read all the proofs but not to the degree of checking constants. I think it is sound.\n\nThe experiments are pretty informative, but they are toy experiments designed to fit the problem setting.\n\n**Weaknesses**\n\nIt is clear that there are several things that have gone unaddressed. For example, the adaptive algorithms have worse regret rates than the stated lower bound. So something is not tight, but it is not clear whether it is the lower bound or the algorithm. Nonetheless, this paper has already provided a number of non-trivial contributions, so it makes sense that this could be addressed in future work instead. I don’t think this is a major drawback of the paper and it was discussed by the authors in the conclusion.\n\nWhile the paper is generally well written and easy to understand, there are a few standout places where the clarity could definitely be improved. I suspect that these can be fixed easily, assuming that the authors agree. I have listed these in the next box.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of reinforcement learning in the linear MDP setting where the transition probabilities and rewards are allowed to change over time. In this setting, one aims to prove dynamic regret guarantees that bound the cumulative sub-optimality gaps between the optimal policy and the learned policy (on the round-varying MDP). In settings like this, one expects to have dependence on the total amount of variation in the problem (amid the changes in the transitions and reward). The authors propose a lower bound $O((dT)^{2/3} B^{1/3})$ where $B$ is a bound on the total variation across all the rounds.\n\nAn algorithm based on a restarting version of LSVI-UCB is proposed. The paper first starts with the case where “local variations” or the variation along any particular window/epoch is known. This allows one to choose windows to run LSVI-UCB and tune the optimism and the size of the window based on the budget. The rate nearly matches the lower bound\n\nAnother algorithm is given where the local variations are not known, but this requires inflating the optimism and leads to a slightly worse bound.\n\nA final adaptive algorithm is proposed, which is designed to automatically handle the case where the variations are known. This is done via a meta algorithm that break the full $K$ rounds down into length $M$ chunks. Then, for each chunk, a window size $W$ is selected to run the LSVI-UCB restart algorithm over the length $M$ chunk. The size is selected based on an Exp3 meta algorithm.\n\nToy experiments are provided showing the effectiveness of the algorithms vs stationary methods.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "This paper is already in good shape technically for the most part. My suggested changes and questions are primarily concerning clarity and are here for  the purpose of strengthening the paper.\n\n\n\nI don’t know if the term “local variation” is common in some of the immediate prior works, but I am personally not familiar with it and found it confusing when it was mentioned several times in the introduction without a proper or at least intuitive definition. I recommend clarifying that.\n\n\nThe paper mentions two concurrent works: Touati & Vincent and Wei & Luo. Evidently Wei & Luo, prove a better bound, but the algorithmic differences and computational disadvantages of their algorithm is described in the current paper. However, the method of Touati & Vincent, which gets the same rate as the current paper, is not described. I think it would be helpful to describe the main idea of their result and differentiate it from the current work. It would also be helpful to explicitly state the bounds achieved in these papers.\n\nI’m not sure the result of Theorem 1 _that_ significant, as claimed. From the $d\\sqrt{T}$ already comes up from existing linear bandit literature and this seems to be reframing this an MDP so that one can scale it up by H if I’m not mistaken. The proof of the theorem may be technically interesting, but it’s also a bit of a distraction from the non-stationary setting. I think the paper would be in good shape even without it.\n\nCan the results of Zhong et al be applied to this setting or the other way around? Or do these two problem classes not contain each other?\n\n\nI don’t doubt that Lemma 1 is true but I think the proof is not sufficient. Even if it is a minor modification of Jin et al, I think it’s worth showing explicitly how that happens. I suspect that one can apply their Lemma D.4 directly to do this.\n\nFor Lemma 1, it would be good to state the specific lemma it modifies from Jin et al in the main paper (I see that it’s listed in the appendix already).\nIn Definition 1 should the norm on $\\mu$ be for all $s’$?\n\nI may have missed it but it doesn’t appear the budget $B$ is defined before it’s used in Theorem 2.\n\nIn 4.1 I would recommend including a note that much of this is following the algorithmic principles of UCB or LSVI-UCB. The key difference seems to be setting the confidence parameter and the use of epochs.\n\nI’m skeptical of Remark 3. I am not aware of a particular instance where the $d^{3/2}$ for LSVI-UCB is tight so it is conceivable that an improvement could be possible. Unless the authors can point out a reference to a particular case, it might be better to rephrase this as saying that the $d^{3/2}$ is unlikely to improve unless there is an improvement to LSVI-UCB. \n\nIn the first figure of the experiments, if you run LSVI-UCB-restart-unknown for more time steps, would you expect it to eventually outperform vanilla LSVI-UCB?\n\n**High level questions that I’d like to see addressed in the revision**\n\nI have several additional questions that occurred to me while reviewing this.\n\nThe use of the master algorithm Exp3 to handle selection of the window size is very reminiscent of “corralling” or model selection approaches to online RL [1, 2, 3, 4]. However, each of these requires some sort of “trick” (e.g. stochasticity or some significant forced exploration) and the rates are usually worse. I am wondering: why, fundamentally, is this not an issue in this paper? I hypothesize the reason is that you do not have a “starvation” problem identified in [1] since each chunk is an independent restarted run. However, I believe the authors may be in a better position to provide insights about this relationship.\n\n[1] Agarwal, A., Luo, H., Neyshabur, B. and Schapire, R.E., 2017, June. Corralling a band of bandit algorithms. In Conference on Learning Theory (pp. 12-38). PMLR.\n\n[2] Pacchiano, A., Phan, M., Abbasi Yadkori, Y., Rao, A., Zimmert, J., Lattimore, T. and Szepesvari, C., 2020. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 33, pp.10328-10337.\n\n[3] Lee, J., Pacchiano, A., Muthukumar, V., Kong, W. and Brunskill, E., 2021, March. Online model selection for reinforcement learning with function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 3340-3348). PMLR.\n\n[4] Abbasi-Yadkori, Y., Pacchiano, A. and Phan, M., 2020. Regret balancing for bandit and rl model selection. arXiv preprint arXiv:2006.05491.\n\n\n\nAdditionally, I wonder if it is possible to simply treat the variation as misspecification and simply apply Theorem 3.2 from Jin et al setting the misspecification parameter to the value of the local variation. Probably you would still have to use epochs, but is this significantly different from the proposed algorithm? If such a modification would work, I am curious if it would be possible to then apply results similar to [5] to then adapt the misspecification. It would be nice to include some discussion of the former in the paper, but the latter is just my own curiosity.\n\n[5] Foster, D.J., Gentile, C., Mohri, M. and Zimmert, J., 2020. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33, pp.11478-11489.\n\n", "broader_impact_concerns": "There are no immediate concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yhpDNfAEtE", "reviewer": "Reviewer_4EKk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Both upper bounds and lower bounds are presented.\n2. The parameter-free algorithm is nice. \n2. Numerical experiments are conducted, which is nice to have for a theoretical RL paper.\n\nWeaknesses:\n1. The upper and lower bounds do not match. Furthermore, the upper bound is worse than a prior work by Wei & Luo.\n2. The techniques used are quite standard in the literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies non-stationary linear MDPs with the following contributions:\n1. A minimax lower bound, which also implies a lower bound for standard linear MDP.\n2. A new algorithm with upper bounds in the known variation and unknown variation setting. For the known variation setting, the bound is tight for T and B.\n3. A parameter-free algorithm for the unknown variation setting with the same theoretical guarantee.\n4. Numerical experiments to demonstrate the effectiveness of the proposed algorithms.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I suggest the following two changes:\n1. Improve the bound to T^{2/3}, so as to match the state-of-the-art result.\n2. Use the recent work on minimax linear MDP to improve the dependency on H and d: https://arxiv.org/abs/2206.11489", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KzFwhil95I", "reviewer": "Reviewer_8NKu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is easy to follow and the results are clearly laid out. The algorithms are relatively intuitive. I found the exposition intuitive and compelling, with the authors gradually building up the sophistication of the algorithm as assumptions are relaxed.\n- From what I can tell the results appear technically sound—I read through the proofs and all seem correct.\n- To the best of my knowledge, the lower bound on time-variations in the linear MDP setting is novel. \n- Experimental results demonstrate that the proposed algorithms improve on baselines which do not take into account the time variation. \n- In the case when “local variation” is known, it is shown that the proposed algorithm achieves the optimal $B$ and $T$ dependence of $O(B^{1/3} d^{4/3} H^{4/3} T^{2/3})$. Here known “local variation” means that the learner knows not just the total change over all $T$ steps, but also the change in each individual epoch of the algorithm. While knowing this local variation is a relatively strong and unrealistic assumption, it is interesting that it is possible to obtain the optimal rate with this knowledge.\n\nWeaknesses:\n- The regret bound presented in this work scales as a suboptimal $O(B^{1/4} T^{3/4})$, off the optimal rate of $O(B^{1/3} T^{2/3})$ (ignoring $d$ and $H$ dependence). \n- There is significant overlap between this work and existing work. A paper from 2020, (Touati & Vincent, 2020), achieves an identical regret bound in an identical setting (though it lacks a lower bound and the result in the “local variation” setting). A paper from early 2021, (Wei & Lou, 2021), achieves a tighter regret bound (achieving regret of $O(B^{1/3} d^{4/3} H^{4/3} T^{2/3})$, which has optimal $B$ and $T$ dependence, as well as hitting a regret bound in terms of the total number of switches, $L$) and applies in much more general settings. Both of these works are discussed in related work. \n- The techniques are relatively standard. In particular, the basic algorithm presented, and analysis, are very similar to the LSVI-UCB algorithm of (Jin et al., 2020), and then simply apply the Bandit-over-Bandit strategy of (Cheung et al., 2019) to handle non-stationarity. As such, I am not certain the algorithmic techniques are of significant interest to the community. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies regret minimization in linear (low-rank) MDPs when the environment is non-stationary. The primary contribution is several upper bounds in this setting—first in the case when the amount of non-stationarity is known, and then in the case when it is unknown, both of which scale as $O(B^{1/4} d^{5/4} H^{5/4} T^{3/4})$, for $B$ a measure of how much the environment changes. In addition to the upper bounds, a lower bound scaling as $\\Omega(B^{1/3} d^{2/3} H^{1/3} T^{2/3})$ is shown. Finally, experiments are providing illustrating the proposed algorithm on a simple example.  \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- Is it possible to obtain a regret bound in terms of the total number of environment switches (e.g. the $L$ parameter of (Wei & Lou, 2021))? Even if it is not, I think this should be discussed, and the technical challenges that prevent the proposed approaches from obtaining this guarantee should be described. \n- The experiments do not compare against the algorithms of (Touati & Vincent, 2020) and (Wei & Lou, 2021). I believe it is important that comparisons against these algorithms are presented. \n- The MDP used in the experiments is fairly simple and almost a tabular MDP—the feature vectors are all one-hot encodings, though $d < SA$, so the MDP does still have a non-trivial low-dimensional structure—and the state and action spaces are relatively small (both under 20). It could be interesting to look at more complicated linear MDPs with larger state spaces (for example with feature vectors living in the simplex). I do not think this is a critical change but it would make the experiments section more compelling. \n- The works [1,2] (see blow) both present lower bounds of $\\Omega(d\\sqrt{K})$ in the linear MDP setting and should be cited in relation to the lower bound given here ([2] just appeared at ICML 2022 and is concurrent). \n- The definition of environment change, $B_\\mu$, seems perhaps overly restrictive. Given the nature of the linear MDP setting, where there are potentially an infinite number of states and the probability of reaching any one of them could be 0, one could easily have that $B_\\mu$ is arbitrarily large, but the actual MDP the user interacts with is identical except for on a measure 0 set. In the worst case this is tight, and this is also the definition of environment change considered by (Touati & Vincent, 2020) and (Wei & Lou, 2021), but it seems possible to do better. For example, perhaps one could measure change in a way that takes into account how easily certain states can be reached. This is not an essential change but would strengthen the work. \n\n\nMinor typos:\n- At the top of page 13, “thw” should be “the”.\n- In section 7, I believe the sentence “We derived a minimax regret lower bound is for nonstationary…” should read “We derived a minimax regret lower bound for nonstationary…”.\n\n\n[1] Zanette, Andrea, et al. \"Learning near optimal policies with low inherent bellman error.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Hu, Pihe, Yu Chen, and Longbo Huang. \"Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation.\" International Conference on Machine Learning. PMLR, 2022.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was deemed to be technically sound. The novelty of the contributions was contested by some reviewers, especially in light of some preprints that have been online since as early as 2020. Then again, a detailed look at the submission history of this paper reveals that this paper has been online for just as long, so all other preprints can be regarded as concurrent work. This left the review team with no concerns about novelty or originality. Also, the amount of concurrent preprints clearly indicates that there is sufficient interest in the community about this type of work. Thus, the paper is clearly worthy of acceptance at TMLR.
Decision: Accept (poster)