Near-Optimal Regret Bounds for Model-Free RL in Non-Stationary Episodic MDPs
Authors: Weichao Mao
Kaiqing Zhang
Ruihao Zhu
David Simchi-Levi
Tamer Basar
Venue:  (2021)
Keywords: reinforcement learning
non-stationary environment
model-free approach
regret analysis

Abstract: We consider model-free reinforcement learning (RL) in non-stationary Markov decision processes (MDPs). Both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long as their cumulative variation magnitude does not exceed certain budgets. We propose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. Our algorithm outperforms the state-of-the-art (model-based) solution in terms of dynamic regret. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret of $\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\Delta>0$ is the variation budget, $H$ is the number of steps per episode, and $T$ is the total number of steps. We further show that our algorithm is near-optimal by establishing an information-theoretical lower bound of $\Omega(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H^{\frac{2}{3}} T^{\frac{2}{3}})$, which to the best of our knowledge is the first impossibility result in non-stationary RL in general.

Under review as a conference paper at ICLR 2021
NEAR-OPTIMAL REGRET BOUNDS FOR MODEL-FREE RL IN NON- NON-STATIONARY EPISODIC MDPs
Anonymous authors Paper under double-blind review
ABSTRACT
We consider model-free reinforcement learning (RL) in non-stationary Markov decision processes (MDPs). Both the reward functions and the state transition distributions are allowed to vary over time, either gradually or abruptly, as long their cumulative variation magnitude does not exceed certain budgets. We pro- pose an algorithm, named Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCCB), for this setting, which adopts a simple restarting strategy and an extra optimism term. Our algorithm outperforms the state-of-the-ar (model- based) solution in terms of dynamic regret. Specifically, Restar(Q-UCB with Freedman-type bonus terms achieves dynamic regret of Ö(S A A HT&). where S and A are the numbers of states and actions, respectively, A > 0 is the variation budget, is the number of steps per episode, and T is the total num- ber of steps. We further show that our algorithm is near-optimal by establishing cntommttion-hheorttice lower bound of 12 A A H T which the best of our knowledge is the first impossibility result in non-stationary RL in general.
INTRODUCTION
Reinforcement learning (RL) studies the class of problems where an agent maximizes its cumulative reward through sequential interaction with an unknown but fixed environment, usually modeled by a Markov Decision Process (MDP). At each time step, the agent takes an action, receives a random reward drawn from reward function, and then the environment transitions to new state according to unknown transition kernel. In classical RI problems, the transition kernel and the reward functions are assumed to be time-invariant. This stationary model, however, cannot capture the phenomenon that in many real-world decision-making problems, the environment, including both the transition dynamics and the reward functions, is inherently evolving over time. Non-stationarriy exists in wide range of applications. including online advertisement auctions (Cai et al. 2017; Lu
et al. 2019), dynamic pricing (Board) 2008 Chawla et al. 2016), traffic management ( (Chen et al. 2020
healthcare operations (Shortreed al. 2011), and inventory control (Agrawal & Jia 2019).
Among the many intriguing applications, we specifically emphasize two research areas that can significantly benefit from progress non-stationary RL, yet their connections have been largely overlooked in the literature. The first one is sequential transfer in RI. (Tirinzoni et al., (0200) or multi-task RL Brunskill Li (2013). In this setting, the agent encounters a sequence of tasks over time with different system dynamics and reward functions, and seeks to bootstrap learning by transferring knowledge from previously-solved tasks. The second one is multi-agent reinforce- ment learning (MARL) (Littman, 1994). where a set of agents collaborate or compete in shared environment. In MARL, since the transition and reward functions of the agents are coupled, the en- vironment is non-stationary from each agent's 's own perspective, especially when the agents learn and update policies simultaneouuly. more detailed discussion on how non-stationary RI can benefit sequential transfer, multi-task, and multi-agent RL is given in Appendix A
Learning in a non-stationary MDP is highly non-trivial due to the following challenges. The first one is the exploration vs. exploitation challenge inherited from standard (stationary) RL. An agent needs to explore the uncertain environment efficiently while maximizing its rewards along the way. Classical solutions in stationary RL oftentimes leverage the "optimism in the face of uncertain" principle that adopts an upper confidence bound to guide exploration. These bounds can be either an optimistic estimate of the state transition distributions in model-based solutions (Jaksch al. 2010

---

Under review as a conference paper at ICLR 2021
Setting
Algorithm
Regret
Model-free?
Comment
Jaksch al.
2010
ö(s A T A
X
only abrupt changes
Gajane et al.
2018
X
only abrupt changes
Undis- counted
Ortner et al.
2019
Ö(s A T$)
X
requires local budgets
Cheung et al. 2020
Ō(s T
X
does not require A
Lower bound
((S
Domingues et al.
2020
Ö(s A
X
also metric spaces
Episodic
RestartQ-UCG -UCC
Ō(S T
Lower bound"
Dynamic regret comparisons for RL in non-stationary MDPs. S and A are the numbers of states and actions, the number of abrupt changes, D is the maximum diameter, H is the number of steps per episode, and T' is the total number of steps. Gray cells denote results from this paper.
Table I:
or an optimistic estimate of the Q-values in the model-free ones (Jin et al. 2018: Zhang et al. 2020 An additional challenge in non-stationary RL is the trade-off between remembering and forgetting. Since the system dynamics vary from one episode to another, all the information collected from previous interactions are essentially out-of-date and biased. In fact, it has been shown that a standard RL algorithm might incur a linear regret if the non-stationarity is not handled properly (Ortner et al.) 2019). On the other hand, the agent does need maintain sufficient amount of information from history for future decision making, and learning what to remember becomes a further challenge.
In this paper, we introduce an algorithm, named Restarted Q-Learning with Upper Confi- dence Bounds (Restan(--UBB), to address the aforementioned challenges in non-stationary RL. the standard based bonus in the upper confidence bound, to counteract the non- of the MDP. This additional bonus term guarantees that our optimistic Q- Q-value still an upper bound of the optimal Q'-value even when the environment changes. To address the second challenge, we adopt simple but effective restarting strategy that resets the memory the agent according to a calculated schedule. Similar strategies have also been considered in non-stationary bandits (Besbes) ctt al. 2014) and non-stationary RL in the un-discounted setting (Jaksch et al. 2010; Ortner et al., 2019 The restarting strategy ensures that algorithm only refers to the most up-to-date experi- ence for Decision-making A further advantage of our algorithm is that RestartQ-UCG UCB is model-free. Compared with model-based solutions, our model-free algorithm is more time- and space-efficient, flexible to use, and more compatible with the design of modern deep RL architectures.
Our algorithm utilizes an extra optimism term for exploration, in addition non-stationarity Hoeffding/Bernsiee
Related Work. Dynamic regret of non-stationary RL has been mostly studied using model-based solutions. Jaksch et al. (2010) consider the setting where the MDP is allowed to change abruptly T, times, and achieve a regret of ÖSSALL DT where D is the maximum diameter of the MDP. A sliding window approach is proposed in Gajane et al. (2018) under the same setting. Ortner et al. 2019) generalize the previous setting by allowing the MDP to vary either abruptly or gradually at every step, subject to total variation budget of A. Cheung et al. 2020) consider the same setting and develop a sliding window algorithm with confidence widening. The authors also introduce Bandit-over-BB RL technique that adaptively tunes the algorithm without knowing the variation bud- get. In setting most similar to ours, DDomingues al. (020)) investigate non-stationary RL in the episodic setting. They propose a -ased approach when the state-action set forms a metric space, and their results can be reduced to an ((SAb A 1 H HáTă regret in the tabular case. Fei et al. (2020) also consider the episodic setting. but they assume stationary transition kernels and adver- sarial (subject to some smoothness assumptions) full-information rewards. The authors propose two
"Connections to stationary RL: Results Table hold for > 0. To derive an upper bound for = 0, we only need a simple modification in the proof of Theorem by setting the number of epochs to be 1. This leads to an upper bound of Ö(H /ST)), which matches the results given Zhang et al. (2020). similar modification in the proof of Theorem results in lower bound of 92 22(HV5 (SAT) when A
2

---

Under review as a conference paper at ICLR 2021
policy optimization algorithms. which are also the only model-free solutions that in non-stationary RL. In contrast, we allow both the transition kernel and the reward function to change over time, and deal with bandit-feedbach which makes the setting in |Fi et al. (2020) not directly comparable. Table (Tomparess our regret bounds with existing results that tackle the same setting as ours. Interested readers referred to Padakandla (2020) for a comprehensive survey on RL in non-stationary environments, We would also like to mention another related line of research that studies online/adversarial MDPs (Yu & Mannor 2009; Neu et al.] 2010 Arora al., 2012] Yadkori et al. 2013] Dick et al. 2014, Wang et al. (018/Lkkurrss et al. 2019 Jin et al. 2019). but they mostly only allow variations in reward functions, and use static regret as performance metric. Finally, RL with low switching cost (Bai et al., 2019) also shares a similar spirit as our restarting strategy since it also periodically forgets previous experiences. However, such algorithms do not address the non-stationarity of the environment explicitly, and it is non-trivial to analyze its dynamic regret in terms of the variation budget.
aware of
Non-stationarity has also been considered in bandit problems. Under different non-stationary multi- armed bandit (MAB) settings, various methods have been proposed, including decaying memory Keskin & Zeevi 2017). well restart-
and sliding windows Garrivirr& & Moulines 2011:
strategies (Auer et al. inspired later research in non-stationary RL. A more recent line of work developed methods that do
et al. 2014 Allesiardo et al., 2017). These methods largely
not require prior knowledge of the variation budget (Karnin & Anava
et al.) 2019a) or
the number of abrupt changes (Auer et al. [2019. Other related settings considered in the literature
include Markovian bandits (Tekin & Liu 2010: Ma 2018), 20118) non-stationary contextual bandits (Luo)
al. 2018 Chen et al., 2019p. linear bandits (Cheung al. 20196; Zhao al. 2020), continuous-
armed bandits (Mao et al. 2020), and bandits with slowly changing rewards (Besbes et al.) 2019).
Contributions. First, we propose RestartQ-UCB, the first model-free RL algorithm in the general setting of non-stationary MDPs, where both the transition kernel and reward functions are allowed to vary over time. Second, we provide dynamic regret analysis for RestartQ-UCB,, and show that it outperforms even the model-based state-of-the-arr solution. Third, we establish the first lower bounds in non-stationary RL, which suggest that our algorithm is optimal in all parameter depen- dences except for an H factor, where H is the episode length.
In the main text of this paper, we will present and analyze simpler version of RestartQ-UCC with a Hoeffding style bonus term. Replacing the Hoeffding term with a Freedman-styl. one will lead to tighter regret bound, but the analysis is more involved. For clarity of presentation, we defer the exposition and analysis of the Freedman- algorithm to the appendices. All missing proofs in the paper can also be found in the appendices.
2 PRELIMINARIES
Model: We consider an episodic RL setting where an agent interacts with a non-stationary MDP for M episodes, with each episode containing H steps. We use a pair of integers (m, h) as a time index to denote the h-th step of the m-th episode. The environment can be denoted by a tuple (S, A, H, P. r), where S is the finite set of states with ||| = S, A is the finite set of actions with [A| = A, H is the number of steps in one episode, P = {P Jme[M (NEH) is the set of transition kernels, and r = (r.² [e([M), is the set of mean reward functions. Specifically, when the agent takes action at" E A in state sy E S at the time (m, h). it will receive a random reward Re (sjt , az)') E [0, 1] with expected value rft (s), o%)), and the environment transitions to a next state $ following the distribution P (- s% ag ). It is worth emphasizing that the transition kernel and the mean reward function depend both on m and h, and hence the environment is non- stationary over time. The episode ends when am is reached. We further denote T M H as the total number of steps.
A deterministic policy क : [M] x [H] + A is a mapping from the time index and state space to the action space, and we let (T)(s) denote the action chosen in state at time (m, h). Define m. + I to be the value function under policy π at time (m, h), i.e..
h
H
Vmm del E
Σ
m (SK, TH (sw)) 1 8h = s SW+1 ~ P (: sw, sw))..
h
3

---

Under review as a conference paper at ICLR 2021
Accordingly, the state-action value function Qnt". :8 x A - R is defined as:
(s. @h def (s, + +
Σ
TW (she, Th (str)) | 8h 5,00
Li=hh-1
For simplicity of notation, we let Pr I a) df By- ( Then, the Bellman equation gives VA Vm (s) = = (s, xhh (s)) and have HH+1 (8) = 0, vs E S by definition. Since the state space, the action space, and the length of each episode are all finite, there always exists optimal policy n² that gives the optimal value (*=""()) def V
= (r + PA. (++1) a), and we also
(8) = sup, V/ (s), Vs E S, m E [M], h E [H]. From the Bellman optimality (s, equation, we have VA Vmm (s) maxaEA Q% (s, a), where "T" a)
def (1% + pm (s, a)),
and (*) 0, E
The agent aims maximize the cumulative expected reward over the entire M episodes, by adopting some policy x. We measure the optimality of the policy x in terms of its dynamic regrer (Cheung et al.) 2020 Domingues al. (2020), which compares the agent's policy with the optimal policy of each individual episode in the hindsight:
Dynamic Regret:
M
M)
def
(VTT
(s - ViT (sT)))
m=1
where the initial state sT of each episode is chosen by adversary (and more specifically, by an oblivious adversary (Zhang et al. 2020). Dynamic regret is a stronger measure than the standard (static) regret, which only considers the single policy that is optimal over all episodes combined.
Variation: We measure the non-stationarity of the MDP in terms of its variation in the mean reward function and transition kernels:
M
M
A
def
sup (r a) -/ (s, (s, a)). Ap def
Σ sup P |
s,
P pm (.
a a))l
where ||-I|, is the Lo'nnor. Note that our definition of variation only imposes restrictions on the summation of non-stationarity across two different episodes, and does not put any restriction on the difference between two consecutive steps in the same episode; that is, Px (- 8, a) and P {,,a) allowed to be arbitrarily different. We further let A A. Ap. and assume A 0.
3 ALGORITHM: RESTARTQ-UCB
We present our algorithm Restarted Q-Learning with Hoeffding Upper Confidence Bounds (RestartQ-UCB Hoeffding) in Algorithm[] Replacing the Hoeffding-style upper confidence bound in Algorithm [ with Freedman-style one will lead to tighter regret bound, but for clarity of exposition, the latter version will be deferred to Algorithm 2 in Appendix
RestartQ-UCB breaks the M episodes into D epochs, with each epoch containing K T episodes (except for the last epoch which possibly has less than K episodes). The optimal value of D (and hence K) will be specified later in analysis. RestartQ- a Q-learning algorithm with UCB exploration at the beginning of each epoch, thereby addressing
periodically restarts
the non-stationarity of the environment. For each d [D], define A to be the variation of the
(d)
mean reward function within epoch By definition, we have Eb (d) < Ap. Further, for each d [D] and h [H), define A
h. to be the variation of the mean reward step in epoch d, i.e., A!a by
A (i) def (dK,M)- -1 T. Em=(d- (d-1)K+ sup,,a (s. - m+ (s, a)). also holds that Σ A ddd
definition. Define (d) and A (d)
p.A analogously.
Since our algorithm essentially invokes the same procedure for every epoch, in the following, we focus analysis on what happens inside one epoch only (and without loss of generality, focus on epoch 1, which contains episodes 1, 1,2...., K). At the end our analysis, we will merge the results across all epochs.
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: RestartQ-UCC (Hoeffding)
for epoch 4- to D do
Initialize: (s) f - h h+ 1, (n(ss)) + --- a, fn(s,a) 0, (s, t 0, for all (s. E [H]
for episode t (d 1)K + min/KK, M) do
observe st:
for step h < to H do
Take action / + arg max, (s a), receive H af) and observe shi4i
( a + (s at) + (o a (n af) + on a (o+1(6
(s a (s a + + (sh a (s () +1;
if ( then
H. a E // Reaching the end of the stage
Ha by V Nulsh
V Na ba + A + H
11
Qn ott t min (alohaa))
+ (.
+ + 2bs. (
(x)
((((s)) maxa Qn (nks
13
(n a t O, (s ) + O, on (s ab) 0:
14
For each triple as,a, E x A x [M]. divide the visitations (within epoch 1) to the triple into multiple stages, where the length of the stages increases exponentially at rate of (1 + 7) Specifically, let é = H, and ei+1 = [(1 + }) Jei,, i 2 denote the lengths of the stages. Further, EE e; = 1,2,
let the partial sums We remark that the stages defined for each individual triple (s, h), and for different triples the starting and ending times of their stages do not necessarily align in time.
denote the set of the ending times of the stages.
Recall that the time index (ks, h) represents the h-th step of the k-th episode. At each step (k,h), h), take the optimal action with respect to the optimistic Qu. (s, a) value (Line 6 in Algorithm D. which is designed as an optimistic estimate of the optimal Q k.* (s, a) value of the corresponding episode. For each triple (s, a. ht). we update the optimistic Q (s, a) value at the end of each stage, using samples only from this latest stage that is about to end (Line 12 in Algorithm[]] [T. 'The optimism in optimism
Qs,s, a) comes from two bonus terms bÊ and ba. where 6 is a standard Hoeffding- that is commonly used in upper confidence bounds (Jin al. 2018 Zhang et al., 2020), and ba is the extra optimism (Cheung et al. 2020) that we need to take into account the non-stationarity of the environment. The definition of ba requires knowledge of the local variation budget in each epoch, or at least an upper bound of it. The same assumption has also been made in Ortner et al. (2019). Fortunately, in method, we can show (in Theorem 2 that if we simply replace Equation (+) in Algorithm with the following update rule:
F of) (o (
Cn(s aft). (o at)
(n at)) +- min
+ the (n aft
(1)
then we can achieve the same regret bound without the assumption on the local variation budget. We set log (2). where 5 is the failure probability.
4 ANALYSIS
In this section, present main result- dynamic regret analysis of the RestartQ-UCC algo- rithm. Our first result on RestartQ-UCB with Hoeffding-style bonus terms is summarized in the following theorem. The complete proofs of its supporting lemmas are given in Appendix B
Theorem 1. (Hoeffding) For = (SAAHII' and for any ô E (0, 1), with probability at least 1 --6 8, the dynamic regret of RestariQ-UCB with Hoeffding bonuses (Algorithml 7 is bounded by ÖsS A A (iTT). where Ō(.) hides poly logarithnii factors of and 1/8.
5

---

Under review as a conference paper at ICLR 2021
Recall that focus analysis epoch 1, with episode indices ranging from 1 to K. We start with the following technical lemma, stating that for any triple (s, a, h), the difference of their optimal Q-values at two different episodes S 11 <k² I K is bounded by the variation of this epoch.
Lemma For any triple (s, a, and any 1 = h1 < 22 S
K. it holds that 10th (s. a)
2 0) < A (1) +HAp! (1)
We now define a few notations to facilitate the analysis. Denote by s and af, respectively the state and action taken at step h of episode k. Let N (8, a), (s, a), (x, a) and V (a) denote, respec- tively, the values of (s, a), (N, a), (s,s, a) and Va(s) at the beginning of the k-th episode in Algorithm Further, for the triple (s a% h). let nf. be the total number of episodes that this triple has been visited prior to the current stage, and let 1 denote the index of the episode that this triple was visited the i-th time among the total ni times. Similarly, let n denote the number of visits to the triple (s a li) in the stage right before the current stage, and let 1/,, be the i-th episode among the ii episodes right before the current stage. For simplicity, use 1, and I, denote 1 and ii and á to denote nh, when h and is are clear from the context. We also use (s, a) and ön (s, a) to denote the values of (s af) and ün (5), a)) when updating the Qn (s af) value in Line 12 of Algorithm [
The following lemma states that the optimistic Q-value (s, a) is an upper bound of the optimal Q-value (s, a) with high probability. Note that we only need to show that the event holds with probability 1 - poly(K, H) because we can replace with 8/ s/poly((A) (K, H) in the end to get the desired high probability bound without affecting the polynomial part of the regret bound.
Lemma 2. (Hoeffding) For 8 E 1). with probability at least 1 1 1-2K H6, it holds that Q (s, a) S (s, s (h a), V(s, a, h, k) E S x A x [H] x [K].
We now proceed to analyze the dynamic regret in one epoch, and at the very end of this section, we will see how to combine the dynamic regret over all the epochs to prove Theorem The following analysis will be conditioned on the successful event of Lemma
The dynamic regret of Algorithm in epoch d 1 can hence be expressed as
I
K
K
R(4) (TT, K) = Σ ( (sf) Vi
V (s V (sf)
(2)
From the update rules of the value functions in Algorithm
we have
( a (s ( ag)
+ in att
(5 27 [m = 0] H
by 2b
( at:)
=1 [1 = 0j H
in(s att
1
V (5/ h+1)
)) + bJ + 28g.
For ease of exposition, we define the following notations:
8 del Vi V
hi (sh).
<b 2 vi vit V (st))
(3)
We further define ( at) with high probability that
(s af).
Then by the Hoeffding's inequality, it holds
1
(
k
at)
<
h
ky +
Vn
( at) s by + bba
(4)

---

Under review as a conference paper at ICLR 2021
By the Bellman equation (s*) Qh (sh, (s())) r . + Ph V (5) al),, we have
c <1 0
v4. (5 1 b% 2b + ( att V (5h
<1[n
=
Ph. yl,
h+1
V h+1
( aa)) + 3b 3b
(5)
1 x1
=
0|H
Σ
p
v4l h+1 P
(s
Σ
Ph (vl. v/4
(sh aht
ñ
71
1 ñ h
(s a +36%. + 3ba
where 5 is by the Azuma-Hoeffdine Hocffding inequality and by 4 In the following, we bound each term in separately. First, by Hölder's 's incquality, we have
i
( - h)) bb.
Let ey denote standard basis vector of proper dimensions that has 1 the j-th entry and Os the others, in the form of (0,...,,,.4 O, ... 0). Recall the definition of 8% in (3). and have
ph
2/ )
(v/4, h+t v2lii)
(5
a
1
Σ
Bht + Sh+1 (8)
1=
ch
Finally, recalling the definition of ck in we have that
1
(vlut(st
v (sitt))))))
Σ
pk
(vl+t
v*+tt)
(s att)
e, c.ht1)
ñ
1
(1/ V -V (sh+a))))) shi 8% + oh
<bs + ch++1 sh+1 + oh+1
(9)
where inequality 9 is by Lemma T Combining ( 1). and
leads to
ch < n 0 H
n Σ
1
dl
ch+ sh 5h
oh+1 + 3b + 5bs.
(10)
To find an upper bound of >
1 Sh we proceed to upper bound each term on the RHS of 10) sep-
arately. First, notice that Σ k= 1 [nt 0] < SAH, because each fixed triple (s, h) contributes
at most 1 to Σk| 1 [n = 0j. The second term in 10P can be upper bounded by the following
lemma:
Lemma 3. ΣK n
Σnh h+ 5 1 D 1+1
7

---

Under review as a conference paper at ICLR 2021
Combining (10)
and Lemma
now have that
K
SSAH
(cht1 + Sh+z1 + + + 3bb +5ba)
H
1+1
k=1
SSAH² + (1
Sh+1 +
(sh+1 + the1 + +0 + 5ba).
(I1)
H
A
where
11 we have used the fact that 0htt1 I Sh+1, which in turn is due to the optimality that
h (sf)
Vil. (s% Notice that we have Sh the LHS of III and Sh the RHS. By
iterating
over H, 1,...,1, we conclude that
K
H K
Σ k=
ct SO
SAH +
DE A=
(M-IAh Ah.1
(12)
H
We bound Σ Σ + # 1 +1 in the proposition below. Its proof relies on series of lemmas Appendix B
that upper bound each term in A/411 separately.
Proposition 1. With probability at least 1 (KH + 2)ō, it holds that
K
h+1 Sō (VSAKH + KHAP * + H
Now we are ready to prove Theorem
Proof. (of Theorem 1 By 2 and [1).. and by replacing å with ズम in Proposition know that the dynamic regret in epoch d
be upper bounded with probability at least 8 by:
(T, δ (SAH² VSAKH + KHA + KH
and this holds for every epoch d [D]. Suppose T ((SAAH3); summing up the dynamic
regret over all the D epochs gives us an upper bound of O(DVSAKHF + ΣD + KHA +
Ed K 2 (d)). Recall the definition that Ede A Ap. El A S A A = Ap.
and that K = e (TT) ). By setting D = -- A - the dynamic regret over the entire T steps is bounded by R(T, M) & Õ(s A H8T3) which completes the proof.
Algorithm relies on the assumption that the local budgets ba are known priori, which hardly holds in practice. the following theorem, we will show that this assumption can be safely removed without affecting the regret bound. The only modification to the algorithm is to replace the Q-value update rule in Equation (+) Algorithm T with the new update rule in Equation (T.
Theorem 2. (Hoeffding, no local budgets) For T = ((AAH²) and for any 5 E (0,1), with probability at least 8, the dynamic regret of Restart UCB with Hoeffding bonuses and no knowledge of local budgets is bounded by ÓSS A where Ö(-) hides poly-togarithmic factors T and 1/5.
To understand why this simple modification works, notice that in (+) we are adding exactly the same value 2ba to the upper confidence bounds of all (s,a) a) pairs in the same epoch. Subtracting the same value from all optimistic Q-values simultaneously should not change the choice of actions in future steps. The only difference that the new "optimistic" (, a) values would no longer be strict upper bounds of the optimal Of (s, a) anymore, but only an "upper bound" subject to some error term of the order ba. This further requires slightly different analysis on how this error term propagates over time, which is presented as a variant of Lemma 2 as follows.
8

---

Under review as a conference paper at ICLR 2021
Lemma 4. (Hoeffding, no local budgets) Suppose have knowledge of the local variation
budgets and replace the update rule (+) in Algorithm | with Equation ① For E (0,1), with
probability at least 1 - HŌ it holds that 0% (s,a) - 2(11 - h + 1)62 S Q (3, S Qh, a), V(s a, h. E Ax H x [K].
The casy removal of the local budget assumption is non-trivial in the design of the algorithm, and does not exist in the non sta-ioatio RL literature with restarts. In fact, it has been shown in concurrent work (Zhou et al. 2020) that removing this assumption would lead to a much worse regret bound (cf. Corollary 2 and Corollary 3 therein).
Remark 1.
will lead tighter regret bound, summarized Theorem 3 below. The proof of the theorem follows a simi- lar procedure as in the proof of Theorem ! and is given in Appendix D It relies on reference- advantage decomposition technique for variance reduction as coined in Zhang et al. (2020). The in- tuition to first learn a reference value function yref that serves as roughly accurate estimate of the optimal value function V*, The goal of learning the optimal value function V = V + (V* -ver) can hence be decomposed into estimating two terms /ree and V Viet- each of which can be ac- curately estimated due to the reduced variance. For ease of exposition, we proceed again with the assumption that the local variation budgets are known. The reader should bear in mind that this assumption can be easily removed using similar technique in Theorem 2
Replacing the Hoeffding- based upper confidence bound with Freedman-style
Theorem 3. (Freedman) For T greater than some polynomial of S. A, A and H, and for any E 1), with probability at least 5, the dynamic regret of RestartQ-UCB with Freedman bonuses (Algorithm 2 is bounded by Ö(S HT&) where O()) hides poly-logarithiic factors.
LOWER BOUNDS
In this section, we provide cnlormationn-hhoreiiiene lower bounds of the dynamic regret character- ize the best achievable performance of any algorithm for solving non-stationary MDPs.
Theorem 4. For any algorithm, there exists an episodic non-stationary MDP such that the dynamic regret of the algorithm at least (( 3 A 3
Proof sketch. The proof of our lower bound relies on the construction of "hard instance" of non- stationary MDPs. The instance we construct is essentially a switching-MDP: an MDP with piece- wise constant dynamics on each segment of the horizon, and its dynamics experience abrupt change at the beginning of each new segment. More specifically, we divide the horizon T into L segments where each segment has To def | steps and contains Mo def [ episodes, each episode having a length of H. Within each such segment, the system dynamics of the MDP do not vary, and we construct the dynamics for each segment in way such that the instance is a hard instance of stationary MDPs on its own. The MDP within each segment is essentially similar to the hard instances constructed in stationary RL problems (Osband & Van Roy [016] Jin et al. 2018). Between two consecutive segments, the dynamics of the MDP change abruptly, and we let the dy- namics vary in a way such that no information learned from previous interactions with the MDP can be used in the new segment. In this sense, the agent needs to learn new hard stationary MDP in each segment. Finally, optimizing the value of L and the variation magnitude between consecutive segments (subject the constraints of the total variation budget) leads to our lower bound.
A useful side result of our proof is the following lower bound for non-stationary RL in the un- discounted setting, which is the same setting as studied in Cheung et al. (2020). Gajane et al. (2018) and Ortner et al.) (2019).
Proposition 2. Consider a reinforcement learning problem in un-discounted non-stationary MDPs with horizon length T, total variation budget A, and maximum MDP diameter D (Cheung et al. 2020). For any learning algorithm, there exists a non-stationary MDP such that the dynamic regret of the algorithm is at least (2S$3 A T).. T
'The definition of segments is irrelevant to, and should not be confused with, the notion of epochs we previously defined.

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Abel, Yuu Jinnai, Sophie Yue Guo, George Konidaris, and Michael Littman. Policy and value transfer in lifelong reinforcement learning. In International Conference on Machine Learning, pp. 20-29, 2018.
Shipra Agrawal and Randy Jia. Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management. In ACM Conference on Economics and Computation, pp. 743-744, 2019.
Robin Allesiardo, Raphaël Féraud, and Odalrie-Ambrym Maillard. The non-stationary stochastic multi-armed bandit problem. International Journal of Data Science and Analytics, 3(4):267-283, 2017.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Deterministic MDPs with adversarial rewards and bandit feedback. In Conference Uncertainty in Artificial Intelligence, pp. 93-101, 2012.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pp. 138-158, 2019.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference Machine Learning, pp. 263-272, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, pp. 8004-8015 2019.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bant bandit problem with non- stationary rewards. Advances in Neural Information Processing Systems, pp. 199-207, 2014.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration-exploiaatin in a multi-armed bandit problem with non-stationary rewards. Stochastic Systems, 944)3119-337, 2019.
Simon Board, Durable-goods monopoly with varying demand. The Review of Economic Studies, 75 (2):391-413, 2008.
Michael Bowling and Manuela Veloso. Rational and convergent learning in stochastic games. In International Joint Conference on Artificial Intelligence, volume 17, pp. 1021-1026. Lawrence Erlbaum Associates Ltd, 2001.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. In Un- certainty in Artificial Intelligence, pp. 122, 2013.
Lucian Busomiu, Robert Babuska, and Bart De Schutter, A comprehensive survey of multiagent rein- forcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), (2():156-172. 2008
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 International Conference on 2017.
Web Search and Data Mining, pp.
Shuchi Chawla, Nikhil R Devanur, Anna R Karlin, and Balasubramanian Sivan. Simple pricing schemes for consumers with evolving values. In ACM-SIAM Symposium Discrete Algorithms, pp. 1476-1490, 2016.
Chacha Chen, Hua Wei, Nan Xu, Guanjie Zheng, Ming Yang, Yuanhao Xiong, Kai Xu, and Zhenhui Li. Toward thousand lights: Decentralized deep reinforcement learning for large-scale traffic signal control. In AAAI Conference Artificial Intelligence, pp. 3414-3421, 2020.
Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal, and parameter-free. arXiv preprint 1902 00980, 2019.
10

---

Under review as a conference paper at ICLR 2021
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under con-stationarity. arXiv preprint S.G::19033.1161,, 2019a.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non- stationarity. In International Conference Artificial Intelligence and Statistics, pp. 1079-1087, 2019b.
Wang Chi Cheung,
David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary Markov decision processes: The blessing of (more) optimism. arXiv preprint arXiv:2006. 14389, 2020.
Trevor Davis, Neil Burch, and Michael Bowling. Using response functions to measure strategy strength. In AAAI Conference on Artificial Intelligence, 2014.
Travis Dick, Andras Gyorgy, and Csaba Szepesvari. Online learning in Markov decision processes with changing cost sequences. In International Conference on Machine Learning, pp. 512-520, 2014.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. A kernel-based approach to non-stationary reinforcement learning in metric spaces, arXiv preprint arXiv:2007.05078. 2020.
Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie. Dynamic regret policy optimization in non-stationary environments. arXiv preprint (xXi::0077.00148, 2020.
David A Freedman. On tail probabilities for martingales. The Annals of Probability, pp. 100-118, 1975.
Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-wint window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805. 10066 2018.
Aurelien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, pp. 174-188, 2011.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-larrning provably effi- cient? In Advances Neural Information Processing Systems, pp. 4863-4873, 2018
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learnnng adversarial MDPs with bandit feedback and unknown transition. arXiv preprint arXiv:1912.01 2019.
Christos Kaplanis, Murray Shanahan, and Claudia Clopath. Continual reinforcement learning with complex synapses. In International Conference on Machine Learning, pp. 2497-2506, 2018.
Zohar S Karnin and Oren Anava. Multi-armed bandits: Competing with optimal sequences. In Advances in Neural Information Processing Systems, pp. 199-207, 2016.
N Bora Keskin and Assaf Zeevi. Chasing demand: Learning and earning in changing environment. Mathematics of Operations Research, 42(2):277-307, 2017.
Chung-Wei Lee, Haipeng Luo, Chen-Y Wei, and Mengxiao Zhang. Linear last-iterate convergence for matrix games and stochastic games. arXiv preprint vrXiv:2006.095/1 2020.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 157-163. 1994.
Junwei Lu, Chaoqi Yang, Xiaofeng Gao, Liubin Wang, Changeheng Li, and Guihai Chen. Rein- forcement learning with sequential information clustering in real-time bidding. In International Conference on Information and Knowledge Management, pp. 1633-1641, 2019.
Haipeng Luo, Chen Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pp. 1739-1776, 2018.

---

Under review as a conference paper at ICLR 2021
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust explo- ration in episodic reinforcement learning. arXiv preprint arXiv:1911.08653 2019.
Will Ma. Improvements and generalizations of stochastic knapsack and Markovian bandits approx- imation algorithms. Mathematics of Operations Research, 43(3):789-812, 2018.
Weichao Mao, Kaiqing Zhang, Qiaomin Xie, and Tamer Başar. POLY-HOOT: Monte-Carlo plan- ning in continuous space MDPs with non-asymptotic analysis. arXiv preprint arXiv:2006.06672, 2020.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online Markov decision pro- cesses under bandit feedback. In Advances in Neural Information Processing Systems, pp. 1804 2010.
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Uncertainty Artificial Intelligence, pp. 81-90, 2019.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv: 2016.
Sindhu Padakandla. A survey of reinforcement learning algorithms for dynamically varying envi- ronments. arXiv preprint arXiv:2005. 10619, 2020.
Susan M Shortreed, Eric Laber, Daniel Lizotte, T Scott Stroup, Joelle Pineau, and Susan A Mur- phy. Informing sequential clinical decision-making through reinforcement learning: An empirical study. Machine learning,
2011.
Yanchao Sun, Xiangyu Yin, and Furong Huang. Temple: Learning template of transitions for sample efficient multi-task RL. arXiv preprint #xXv:20002.06659, 2020.
Cem Tekin and Mingyan Liu. Online algorithms for the multi-armed bandit problem with Marko- vian rewards. In 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1675-1682, 2010.
Andrea Tirinzoni, Riccardo Poiani, and Marcello Restelli. Sequential transfer in reinforcement learning with generative model. arXiv preprint 2XXi:2007.00722, 2020.
Jingkang Wang, Yang Liu, and Li. Reinforcement learning with perturbed rewards. arXiv 2018.
preprint arXiv:
Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. Online learning in Markov decision processes with adversarially chosen transition probability distributions. In Advances in Neural Information Processing Systems, pp.
2013.
Jia Yuan Yu and Shie Mannor. Online learning in Markov decision processes with arbitrarily chang- ing rewards and transitions. In International Conference on Game Theory for Networks, pp- 314 312. IEEE, 2009.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. arXiv preprint arXiv:2004.10019, 2020.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In International Conference on Artificial Intelligence and Statistics, volume 2020, 2020.
Huozhi Zhou, Jinglin Chen, Lav R Varshney, and Ashish Jagmohan. Nonstationary reinforcement learning with linear function approximation. arXiv preprint 4rX1v:2010.04244, 2020.
12

---

Under review as a conference paper at ICLR 2021
A APPLICATIONS TO SEQUENTIAL TRANSFER, MULTI-TASK, AND MULTI-AGENT RL
One area that could benefit from -tatioatinaay RL is sequential transfer in RL Tirinzoni et al, 2020) or multi-task RL (Brunskill & Lij 2013), which itself is conceptually related to contin- ual RL (Kaplanis et al., 2018) and life-long RL (Abel et al., 2018). In the setting of sequential transfer/multi-task RL, the agent encounters sequence of tasks over time with different system dynamics, and seeks to bootstrap learning by transferring knowledge from previously-solve
tasks. Typical solutions in this area (Brunskill & Li 2013 Tirinzoni et al. 2020: Sun et al.] (020) need to assume that there are finitely many candidate tasks, and every task should be sufficiently different from the others Only under this assumption can the agent quickly identify the current task it is operating on, by essentially comparing the system dynamics it observes with the dynamics it has memorized for each candidate task. After identifying the current task with high confidence, the agent then invokes the policy that it learned through previous interactions with this specific task. This transfer learning paradigm in turn causes another problem- it "cold switches" between poli- cies that are most likely very different, which might lead to unstable and inconsistent behaviors of the agent over time. Fortunately, non-stationary RL can help alleviate both the finite-task assump- tion and the cold-switching problem. First, non-stationary RI. algorithms do not need the candidate tasks to be sufficiently different in order to correctly identify each of them, because the algorithm itself can tolerate some variations in the task environment. There will also be no need to assume the finiteness of the candidate task set anymore, and the candidate tasks can be drawn from a continuous space. Second, since are running the same non-stationary RL algorithm for series of tasks, it improves its policy gradually over time, instead of cold-switching to a completely independent policy for each task. This could largely help with the unstable behavior issues.
Multi-agent reinforcement learning (MARL) (Littman] 1994) studies the problem where a set of agents collaborate or compete in shared environment. In MARI., since the transition and ward functions of the agents are coupled, the environment is non-stationary from each agent's 's own perspective, especially when the agents learn and update their policies simultancously. The non- stationarity in MARL is a setting where non- non-stationary RL can play a role. As advocated earlier in Bowling & Veloso (000T): Busoniu al. 2008), good MARL algorithm should be both rational and convergent, where the former means that the algorithm converges to its opponent's 's best response its opponent converges to a stationary policy, and the latter means that if all agents use the same algorithm, the algorithm converges to a stationary policy. As such, non-stationary RL algorithm can be viewed as a rational MARL algorithm, thanks to its dynamic regret guarantees, although its convergence property in MARL settings is still worth further investigation. In fact, developing algorithms that are both rational and convergent in general MARL settings is still relatively open. In addition, non-stationary RL algorithms also apply to the MARL setting achieve low regret against slowly-changing opponents (see (Lee et al. 2020 Sec. 5.2) for the setting) but we consider a more challenging measure of dynamic regret (as opposed to the static regret Lee al. (2020)). Finally, dynamic regret is also pertinent to the notion of exploitability of strategies in two-player zero-sum games Davis et al. 2014).
B PROOFS OF THE TECHNICAL LEMMAS
B. PROOF OF LEMMA
Proof. In fact, in the following, we will prove a stronger statement: |Q /Q.. (s, a) Q
k2. (s, 2 S (1)
Ei' (1)
W/ + H Ei=m A (1)
p. which implics the statement of the lemma because Σm'h r/ S
and Σ = A pkh I A by definition. Our proof relies on backward induction on h. First,
NNedlesss to say, this assumption itself also to some extent contradicts the primary motivation of transfer learning. After all, only want transfer knowledge among tasks that are essentially similar each other.
13

---

Under review as a conference paper at ICLR 2021
the statement holds for h H because for any (s, by definition
(*,0 2 (s. = + (s,, a)
H (s, a)
- Σ
(s,a) r (s,
k=
r (s, - (s, a) s A
(13)
k=1
where we have used the triangle inequality. Now suppose the statement holds for h + 1; by the Bellman optimality equation,
t (s, (s,a) a) - t (s,a)
-P 1+1 (s) Ph Vitt + r (s. r/ (s)
pla h+1 V - Ph h+l (s, + 4
(14)
Σ Phi (s' (s.aa) Σp s.a) 4
SES
*ES
EE (pf (s' 8 a)) = p (s' 8, Q (s', (x41)s))) + 1 S'ES
r.b (15)
(1)
where inequality (14) holds due to a similar reasoning as in (3). and in the optimal policy in episode k and 22. respectively. Then by our induction hypothesis on h + 1, for any s' E
15) n h and A2. denote
"aiils.=<4400 1 (b)) +
Σ M=h+1
(1)
+H
Σ
(1)
p.h
M==l+1
H
<Q - (s))+ +
Σ
+
H
(1)
(16)
p,b
M+
W=h+1
where inequality (16) is due the optimality of the policy h in episode k2 over h Then,
2 k1 (s, a) - Q k2 +s,aa
H
H
< Σ (p (s' s,,a) - (s s. a)) (ar((s)))) +
Σ
(1)
+ H
Σ
(1)
r.
D.
s'ES
k==h
R'=h+1
<
ph (-18, a) - (1s, (
Σ M=
A
(1)
+ H
Σ
A (I)
(17)
p.h
M=k+1
H
<A (2) (H- h) + Σ p.h
A W
H
Σ h==
p.M
(18)
W=
H
H
H
p.hss
W=h
M=hh
p.h and by the definition of optimal Q-values that Q (s, a) S H h V(s a) E A. Repeating similar process gives us kes (s,a) - thi " a) S Σ#= (D) + = (l)) This completes our proof.
where (17 is by Hölder's inequality, and (18) is by the definition of A (1)
B.2 PROOF OF LEMMA 2
Proof. It should be clear from the way we update Qn a) that (h a) is monotonically decreasing
in kt. We now prove Qx (s, a) s 1 (s,a) a) for all h, k by induction on k. First, it holds for
k = by our initialization of ()) For k now suppose 03 (s, a) S Q (s, s
14

---

Under review as a conference paper at ICLR 2021
(%, a) for all a, h and 1 s k. For fixed triple (s, a. h), consider the following two cases.
Case 1: (s) is updated in episode k. Then with probability at least 1 28
Fn(s, a)
(1) a)
0 (s,
+ b + 2ha
as)
(s) a)
())
1
H²
1
h+1 (5+1) + à it V "
2b
(19)
as)
1
pl v (5, a) + /// +bb
+V
(20)
(n(
0h - ()) - (3())))) + V 1 2bb
+
Σ
(21)
2 20 (s, + ba.
(22)
Inequality 19) is by the induction hypothesis that o (5) a) 2 Qief ( Va E A.
and hence V (s/+1) 2 V Inequality (20) follows from the Azuma-Hoeffiee in-
equality.
21 uses the Bellman optimality equation. Inequality (22) is by the Hoeffding's
1 á (Eark((s,a) F)) I Vá with high probability, and by Lemma
equality that
that o (s, a) + Pb as) According to the monotonicity of (s, we know that 2f (s,a)
(s," S (s, S (s, fact, we have proved the stronger statement + (s, 2
Q (s, a) = ba that will be useful in Case 2 below.
Case 2: Qn a) is not updated in episode k. Then there are two possibilities:
1. If (s a) has never been updated from episode 1 to episode k: It is easy to see that @h+ (s,a) (x
(h(s, a) = H h + 2hiit (s, holds.
2. If Qn. has been updated at least once from episode 1 to episode A: Let j be the index of the latest episode that (s, a) was updated. Then, from our induction hypothesis and Case 1, we know that // (s, a) 2 Qi (s. ba- Since (s, a) has not been updated from episode j + to episode k we know that Q (s.a) = as) = =.... 0% +1 (s.u) a) > Q (s, + bba 2 "s, where the last inequality holds because of Lemma
A union bound over all time steps completes our proof.
B.3 PROOF OF LEMMA 3
Proof. It holds that
K
K K
[ = =
Tk = 5] (23)
h++
k=11=1
1=1
k=1
i=1
For fixed episode j. notice that E 1 177 -] < 1, and that Σ [7Th j] = 1 happens and only if (sft aft) = (sh, a)) and (j. h) lies in the previous stage of (k, h) with respect to the
triple (sft at, h). Let IC {k E [K] E 117 = -] = 1}: then, we know that every element k IC has the same value of nit i.e., there exists an integer N₂ 0. such that n N2, vk E K. Further, by our definition of the stages, we know that [C] S (1 + N because the current stage
15

---

Under review as a conference paper at ICLR 2021
is most (1 + #)
times longer than the previous stage. Therefore, for every j. we know that
Σ I - 1 1 H
Σ
(24)
h
Combining 23 and (24) completes the proof of
K ckml Ri
siml Oh4 S
#)
> o h+1
B.4 PROOF OF PROPOSITION I
In the following, we will bound each term in A separately in series of lemmas. Lemma 5. With probability 1, have that
K (1 ΣE h=1k-1
1 1 133, +ba)) K ( H
Proof. First, by the definition of ba. it is easy to see that Σ Σ Ek K ((A (1) + HA S O(KHA!) (1) + KH2 ) Recall our definition that e1 H
3 11 5
and ei+1 (1 )e i 1. For fixed h E [M], since H²2
k
K Σ
H
E (1+ +
1-133
1 12
H
H
No at)
k=1
1=1
112 V
1 (b) (s, ( (sh, = eg]
j21
k=1
1
12H
(1+
H )) w(s, a.
w
ej
8,0 j21
K where w(s,a,) def ン k= We then know that Σ., w(s K. For a fixed (s, a). let us now find an upper bound of j. denoted as J. Since each stage is (1+ H times longer than the previous stage, we know for
((st xt) (s, (s at) ez]. and w(s,a) _ EE>ز w(s, a,
1 1 j S J, a) ΣK [ss a = as) (s) at) = e,] = [(1+ )) From Σ a(s,a,j) w(s, a), we get I (1+ - I
10 w(a.a) Therefore,
I+ H
I I 0
Σa- -0-30,00)))))) ej
Σ
Jej
so 30(Vu(s,a))
J21
Finally, by the Cauchy-Schward -chwwrtzz inequality, we have
H 1 1- 0 H2 IIV w(s w(s a.
S V VSKKH
H
j21
Combining the bounds for by, and ba completes the proof.
Lemma 6. With probability at least - 5, it holds that
H K
Σ (1+
h- Sha1 - < 5O KHA KH
H
A= k=
16

---

Under review as a conference paper at ICLR 2021
Proof. We have that
1h+1
h= Am11
H
h- x
ph e .) (vi+t V/si1) (sh aB)
(1+
71 i=1
H
1
1
Ph
ex ) (viys -v + V - v (0% at)
h= 1=1
i=1
| |h- Pp) - (vitt v (0% af);
(1+
2b
1=1
h= k=1
where the last inequality follows from Lemma and the definition of ba- From the proof of Lemma 5 we know that the first term can be bounded as
H K
ΣΣ
(1+
1 +
1 S O(KHA, + KH)
A=1k=1 km
Further, the second term is bounded by the Aruma-Hoefiding inequality as
H
K
Ph - t ) (vaut - V2441) (5 a S {((KHH))
h=1k=1
Combining the two terms completes the proof.
Lemma 7. With probability at least (KH 1)6, it holds that
K
ΣΣ
1 -
ch+ S OVVSAKH'* KH A
H
Proof. We have that
H
1
ck
H
Sh+1
H
K
1
A
) (vi++ - v/iit) (s att)
(L+
pk
e
11
ñ ==1
int1
h=1
H K
1
1
à
pkc
ph
ph: - e ) ) (vi++, - -v/+t) (ohi agt)
H
h=1k=1
i=1
H
1 H
ph. - e e ) (vita viltt) (shsat) (25)
<O(KHA
where the last step is by the fact that V ax) 2 Vlui (s/) at) from Lemma 2 and then by Hölder's 's inequality and the triangle inequality. The following proof is analogous to the proof of Lemma 15 in Zhang et al. (2020). For completeness we reproduce it here. We have
#
K
pl.
e (v/4, v (shs att
1=1k=1
1=1
K K
a
1
1 LTh =i] (PH) e ) (Vit+ - -Vh41) (sf
# Σ
K
K
4-1
Th
= (p).
oxfmn) ) (Vitz - -V/+t) (5% at) (26)
H
k=
17

---

Under review as a conference paper at ICLR 2021
where (26 holds because (s. a j if and only if is in the previous stage of l and (s alp) (s/== ).) For simplicity of notations, we define 0 = (1+ } 1 Then we further have (note that we have swapped the notation of j and k))
2 i=
1
h k)
K
oh+1 (Ph- - - (Vi-1 - V (s a.).
26
For hk E [K] X [H], let á denote the number of occurrences of the triple (s ah h) in the current stage. Define 0ht11 def (1 ) [1+ 3 )=k
S 3. Define K. def {(k. 0 0% )
and K h) E [K]
[H] 0%+ + 1 Then, we have that
26
8
-ook..) (Vi - -v/t1) (s ah)
11 K
Σ
Σ
(0h+1 - 0h+t) (Pf (Ph-est -ett..) (Vi+ - Va41) (s at).
h=1k=1
Since 0% 0,+ is independent of sht1. by the Azuma-Hooffding inequality, it holds with probability at least 1 - ò that
ΣΣ 0h+t Pht - (Vi+1 Vitii (5% at) S <O(VKH3)
(27)
It is easy to see that if &s is in a stage that is before the second last stage of the triple (sh at h). then (ks, h) E K. For triple (s, a, h), define (s, del fk E [K] k is in the second last stage of the triple (s, h), (sh ax) (s,a)}. We have that
H
10 oht1) (Ph -e- est (Vi= - vi+tt) (sh ah)
EE
Σ
11 [(stt ah) = as) (0h+11 - 0ltta) (Ph o (Vitz - V (s,
h, ki(k,
=
-E - (s)1(s,a))
Σ
(ph (ph-e -0oott))) (Vitt - h+1 (s,
(28)
8,0,h
(s,a(
where for a fixed triple (s, h), we have defined (n+1(s, oht for any k E Kr (s, Note that (1, a) is well-defined, because 0 0% Vki, ka E (s, Similarly, let 0 (1, a) del 0 for any k (s, a), and (s a) is also well-defined. By the Azuma- Hoeffding inequality and a union bound, it holds with probability at least 1 - KH8 that
Σo 8,a.h
(
H? |C (6, (s.)))
Σo
o
V H2NNk+ (s.
s.a.h
SAH3,
N-K+ (s, N a)
(29)
s,ahh
<0 SAKH3
(30)
where N a) is defined to be the total number of visitations to the triple (s, a, h) over the inequality. (30) holds because by the way stages defined, for each triple (s, a, h), the length of its last two stages is at most an O(1/H) H) fraction of the total number of visitations.
entire K episodes. (29) is by the
Combining
25
27 and (30) completes the proof.
18

---

Under review as a conference paper at ICLR 2021
B.5 PROOF OF LEMMA 4
Proof. This proof follows a similar structure as the proof of Lemma 2 It should be clear from the way we update Qa a) that 2% (s, a) is monotonically decreasing in k. We now prove 0% (s, a) 2(H - h + 1)6a I 0% (s, a) for all s, a, h, k by induction on k. First, it holds for k: = 1 by our (s,
+ 1)61 S 2 a) S (s, a) for all s, h and 1 I j S k. For a fixed triple (s, 0, h), we consider the following two cases.
initialization of (s, a). For l 2 2, now suppose Q (s,a) 2(H
Case 1: Qn a) is updated in episode k. Then with probability at least 26 (1,s,a)) a)
(s,
Oht
+
+ 6%
())
())
V -2(1 2-122((1100) 11)ba +
H²
+
L
(31)
P h+1
(8, + -V -2(H-- - -hybs
(32)
à
==1
a) 1
(Ql. (s, (s, - (3..a) + V/ - -2(H hibb
(33)
á
20 (s, a) - b& - hibbs.
(34)
Inequality 331 is by the induction hypothesis that Q (5) (9/+1: a) 2 Q 0/41 a)
2(H
h)ba, Va E A, and hence V (5% 2 (o 2(H - h)b2, Incquality (3) follows from
the Azuma- Hoeffding inequality.
33
uses the Bellman optimality equation. Inequality 34 is by
the Hoeffding's 's inequality that
(s, (s(,a)) S V with high probability, and by
n
Lemma that di (s,a) 2 0 (s, a) - ba- According to the monotonicity of Q (s, a), we know that h (s,a) 2(H h+ 1)6a I 1 a) S Qf a). In fact, we have proved the stronger g++1 (s, a) 2 2ft a) - 6 2(H - 6))6 that will be useful in Case 2 below. statement 2
Case 2: Qn a) is not updated in episode k. Then there are two possibilities:
1. If Qr (s, a) has never been updated from episode 1 to episode k: It is casy to see that p (s. a) = (f = ... = (), = H - h + 1 2 Q holds.
k. (s,a) 2(H - h + 1)6s
2. If Qn,s,a a) has been updated least once from episode to episode k: Let j be the index of the latest episode that Qu a) was updated. Then, from our induction hypothesis and (s,
Case we know that 1 a) 2 Q a) ba 2(H h)ba- Since Qu a) has
not been updated from episode j + 1 to episode k, we know that Q/+11 (s, a) Q (s, a)
... 0 (s, a) 2 2 (s. a) ba 2(H h)bb 2 0 (x, - 2(H - h + 1)ba, where the last inequality holds because of Lemma [
A union bound over all time steps completes our proof.
B.6 PROOF SKETCH OF THEOREM 2
Proof sketch. We only sketch the difference with respect to the proof of Theorem I in the main text. The reader should have no difficulty recovering the complete proof by following the same routine as Theorem |
Specifically, it suffices to investigate the steps that are involved with Lemma 2
The dynamic regret of the new algorithm in epoch d = now can be expressed as
K
K
R (d) (T, K) = Σ
(v (s*)
b. (s+)
v (st)
viki"* (of) + 2KHbb, (35)
S
19

---

Under review as a conference paper at ICLR 2021
where we applied the results of Lemma 4 instead of Lemma 2 from the new update rules of the value functions, we now have
The reader should bear in mind that
(5% of) (s af))
(sh. oft No a
(+ S 1 - H H+
+
- U%
(36)
where the RHS no longer has the additional bonus term ba. we define çh: 1 and oh+ in the same way as before, the author can easily verify that all the derivations until Equation (12 still holds,
although the value of A should be re-defined as A def ch +0/+1+ 3b + 3bb due to the
new upper bound in (36) that is independent of ba. Proposition also follows analogously though
some additional attention should be paid to the proof of Lemma 7 where the results of Lemma 2
have been utilized. Finally, we obtain the dynamic regret upper bound in epoch d = 1 as follows:
R (TT, K) S Ō (SAH* + SSKHH + KHAP + KH + 2kKbba
where the additional term HKH comes from 35 From our definition of ba, we can easily see that 2K Hba S O(KH,," k upper bound in one epoch remains the same order, which leaves the dynamic regret over the entire horizon also unchanged.
Therefore, we can conclude that the dynamic regret
C ALGORITHM: RESTARTQ-UCB (FREEDMAN)
The algorithm Restarted Q-Learning with Freedman Upper Confidence Bounds (RestanQ-UUCB Freedman) is presented in Algorithm For ease of exposition, we use i, j,, U, o, nt and n, and denote in (s,a), inn (sh af),, én [s af),, ön ( k a ph (sh af), ofd (s at), (s a and (s af)) respectively, when the values of (s, a, h, k) are clear from the context.
Compared with Algorithm D there are two major improvements in Algorithm 2 The first one is to replace the Hoeffding-baane bradingg-asedd bonus term by with tighter term by- The latter term takes into account the second moment information of the random variables, which allows sharper tail bounds that rely on second moments to come into use (in our case, the Freedman'ss 's inequality). The second improve- decomposition
ment is a variance reduction technique, or more specifically, the snffeence-advanteen as coined in Zhang et al. (2020). The intuition is to first learn a reference value function V that serves as a roughly accurate estimate of the optimal value function V The goal of learning the optimal value function V V (V* - Vier) can hence be decomposed into estimating two terms Veel and V Viet. The reference value yzel is a fixed term, and can be accurately estimated using a large number of samples (in Algorithm 2 we estimate V only when we have cS cSAH"t samples for a large constant c). The advantage term V - Vief can also be accurately estimated due to the reduced variance.
D PROOF OF THEOREM
Similar to the proof of Theorem I we start with the dynamic regret in one epoch, and then extend to all epochs in the end. The proof follows the same routine as in the proof of Theorem [ Given that
rigorous analysis on the Freedman-basee bonus with variance reduction is present in Zhang al.
(2020). one should not find it difficult to extend our Hoeffding based algorithm to Algorithm 2 Therefore, rather than providing a complete proof of Theorem 3 in the following, we sketch the differences and highlight the additional analysis needed that is not covered by the proof of Theorem and Zhang et (2020).
To facilitate the analysis, first recall few notations NA NA, (h,s,, a), (s), Nh.s: T 4
and 1, that we have defined in Section 4 In addition, when (h, k) is clear from the context, we drop the time indices and simply use μ, o. ef re denote their corresponding values in the computa- tion of the (s
. a value in Line 15 of Algorithm
We start with the following lemma, which an analogue of Lemma but requires a more careful treatment of variations accumulated in / and tun It states that the optimistic Q (s, a) is an upper bound of the optimal 2 (s, a) with high probability.
20

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Restar(Q-UCB (Freedman)
for epoch 6 to D do
2 Initialize: (s((s) + - h h 1, + 1- 0, (( + O,
an(s,a) + 0, (s, a) t 0, (s) + -0, +
+ 0.,0%
0, (s) - H, for all (s, a, h) E S x Ax [H];
for episode k + (d 1)K + 1 to min M) do
observe si;
for step f to H do
Take action at, arg max, ( a), receive ( ak). and observe +h+1i
i マ + (5 a,), + + Vh+1 (oh+z))
7
+ ja 1 Vh+41sh441
- (sh 1), t + (Vh+1(5h++1) (sh+(s)+11) ($)+1),000 o + jte + (
1 + 1 + V (st
10
n n + 1, 1 1
if E L // Reaching the end of the stage then
12
H2
V + L ba + A. (d) + HA (d);
13
V
14
by < 2// 0rd jon/nn (prd /n)² 2+2 (e/n-(p/a)
L+5
( He 3,/4 H.14
23/4 +
43/4 2t Va
n
n
n
(s ab t min
{ c +
/ + +b, 4bs On (sh at;
15
(s f max, a):
16
(N ai),nn(( (o
(60% ax),, én (5 a a a + 0:
17
if E. (s a) = -S(SAHH)) /// Learn the reference value
18
19
then
Vie (5h) (o()):
Lemma 8. (Freedman) For d E 10, with probability at least 1 - 2KHH. it holds that Qu (s, a) S
O (s,a) S (%, V(s, a, h, k) S A [H] [K].
Proof. It should be clear from the way we update Qu a) that (s, a) is monotonically decreasing in k. We now prove Qh:² a) < Q (s, a) for all a, h, & by induction on k. First, it holds for k by our initialization of Qn a). For k > now suppose Q% (s, S Q (s, a) for all s, a,
and 1 < j < k. For a fixed triple (s, a, h), we consider the following two cases.
Case 1: Qu a) is updated in episode k. Notice that it suffices analyze the case where (s a) updated using by, because the other case of by, would be exactly the same as in Lemma 2 With probability at least 1 6.
an(s,a)
( a)
+ a))
+ 2b + 4bs
(s, a)
(s,
(s,
(s) a)
prefd (ole (s/it)) - ple vrofll (s)
h+1
h+1
m
1
Viita (8/112) - ( (6ht+2) - (pl.v/ Pllv (s)a)
+
1 11
pla refid h+1
1
pli pii
Pf. v+t1 P (s, a) +26 + +b4 (37)
+
12
ñ
X3
21

---

Under review as a conference paper at ICLR 2021
In the following, will bound each term in (37) separately. First, we have that
+ 20I
Ph 1+1
PR (s, + b
(38)
1=1
1
pla h+1
Pht (s, + ba
(39)
91
1
Vi (s, a)
1 Σ Σ Ph Phy () + ñ
pliv ( (8,
(40)
71
1
ph h (s.a),
(41)
where 38 > 0 and
39
0 by Hölder's inequality and the definition of ba. 440). we have that
EELPP v.yil (s,a)
1/4 Σ PK h+1 (s, a) 2 0, because V (s) is non- non-increasing in k.
h+1
Following a similar procedure as in Lemma 10, Lemma 12, and Lemma 13 in Zhang et al. 2020). we can further bound |x1l and |xal as follows:
yeet
5H
2/1
2H.
1x
2
(42)
n
Tn
11
5
2/i
2Hc
Ixel S
+
(43)
ñ
n
Th
These are the steps where Freedman's 's inequal- ity Freedman (1975) come into use, and we omit these steps since they are essentially the same as the derivations in Zhang et al. (2020). We can see from 42 (43). and the definition of by. that Ixal + |x2l s uh
where ye def
and def
n
Substituting the results on X1, X2 and X3 back to (37 holds that with probability least 1 5,
in a)
2x+1(s,a)
+ X1 + X2 + X3 + +bb + 4bb
ñ
(1 a)
plyl
(8,0) + + + 2b h+
(44)
n
F (x,
(8,a) a) + + + 2b vl h+1
(45)
n
i=1
(s,
1
(s.. -1)(s,a)) + th 26
ñ
a
Q (s, a) 2ba 2 Q (s,a) a) + bba
(46)
where in 44 used 441
43 and the definition of by in Algorithm 2 445 is by the
induction hypothesis that Q (st41aa)) 2 ofe (sl a). Va E A,1 4,154 < k. The second to last
inequality holds due to the Hofdding's inequality that à (EL (s, a) as) S Va s by
with high probability. Finally, the last inequality follows from Lemma
According to the monotonicity of (s,s,a), we can conclude from (6)) that Q k.t (s.a) S Ok+t (s, a) S (s, a). In fact, we have proved the stronger statement + a) 2:: + ba that will be useful in Case 2 below.
Case 2: Qn(8, a) is not updated in episode k. Then, there two possibilities:
22

---

Under review as a conference paper at ICLR 2021
1. If Qn a) has never been updated from episode 1 to episode k: It is easy to that Oh (s,a) (5, a)
(s, H h+12 2 (s,a) holds.
2. If Qu(s,a) a) has been updated least once from episode 1 to episode Let j the index of the latest episode that (s(8 a) was updated. Then, from our induction hypothesis know that ( (s,a) a) (s, ba- Since Qs(s,a) has not been
and Case updated from episode j ++ episode k, we know that + (s.a) (,, a)
0h+ (s.a) 2 (s, + ba 2 (s, where the last inequality holds because of Lemma
A union bound over all time steps completes our proof.
Conditional on the successful event of Lemma 8 the dynamic regret of Algorithm 2 in epoch d = can hence be expressed
( (T. K) Σ (V (sf) V (s (st)
V (s V. (st)
(47)
From the update rules of the value functions in Algorithm have
(s a
ref,k Hb
V (sh) - 1 [m = 0] H
+
2b + 4bs
n
n
n
in ( )
=1 [m = 0] H
vesfl (sh 1)+
(v/ h+ (sli
h+t (5h 1) +bbs
If again define Sh Theorem [ (details can be found in Zhang et al. (2020) and obtain
V/ (st)
Vola (s))
follow similar routine in the proof of
K Σ ct S0
H K
SAH +
ΣΣ (M-IAR
1=1
A=
where 1/41 1h+1
+ + oh+1 +bb + 8ba with the following definitions:
nk
hh+1
def
Ph
Phvvrot h+1
Ph PXViotk+1) (5% ali),
-e e/it ) (v -V at).
def
ph
del
(v -iiit--iie -V/ts) (s att..
14+1
An upper bound on the first four terms in A is derived in the proof of Lemma 7 in Zhang et al. 2020) (There is an extra term of v f our defnition of LA compared to theirs, but does not affect the leading term in the upper bound). By further recalling the definition of ba. we can obtain the following lemma.
Lemma 9, (Lemma in Zhang et al. (2020)) With probability least (1 - O(H2T4))), holds that
/ -0 -AAT--/AAAATTTTTTTTTTTTAAAAAAAAA
ΣΣ (1
1=1
Combined with 47 and the definition of ch, we obtain the dynamic regret bound in a single epoch:
R(d) (T, K) 0
0 [VSAHPT.++ + HoTolog(T) + S H KHA KH²AA)) Vil E [D].
23

---

segment. More specifically, we divide the horizon T into L segment: where def Under review as a conference paper at ICLR 2021
Finally, suppose T is greater than a polynomial of S, A, A and H. VSAHTT would be the leading term of the dynamic regret in a single epoch. In this case, summing up the dynamic regret over all the epochs gives us an upper bound of Ô (DVSAHT + Eod KHA
KHA, (d) EL KH (d)
Recall that > d==
( I Ar Eb=1 A (4) I Ap. A A. + Ap. and that K = O T DH
By setting
D= S A A3T the dynamic regret over the entire T steps is bounded by
R(T, M) s δ ( A
This completes the proof of Theorem 3
E PROOF OF THEOREM 4
The proof of our lower bound relies on the construction of a "hard instance" of non-stationary MDPs. The instance we construct is essentially switching-MDP: an MDP with piecewise constant dynamics on each segment of the horizon, and its dynamics experience an abrupt change at the beginning of each
each segment has To def [ steps and contains My = I. episodes, each episode having a length
of H. Within each such segment, the system dynamics of the MDP do not vary, and construct the dynamics for each segment in a way such that the instance a hard instance of stationary MDPs on its own. The MDP within each segment is essentially similar to the hard instances constructed in stationary RL problems (Osband & Van Royl 2016; Jin et al. 2018). Between two consecutive segments, the dynamics of the MDP change abruptly, and we let the dynamics vary in a way such that no information learned from previous interactions with the MDP can be used in the new segment. In this sense, the agent needs to learn a new hard stationary MDP in each segment. Finally, optimizing the value of L and the variation magnitude between consecutive segments (subject to the constraints of the total variation budget) leads to our lower bound.
We start with a simplified episodic setting where the transition kernels and reward functions are held constant within each episode, i.e., pT
PAr = =... P and r [M. This is a popular but less challenging episodic setting, and its stationary counterpart has been studied in Azar et al. (2017). We further require that when the environment varies due to the non- stationarity, all steps one episode should vary simultaneously in the same way. This simplified setting is easier to analyze, and its analysis conveniently leads to a lower bound for the un- un-discounted setting as side result along the way. Later we will show how the analysis can be naturally extended to the more general setting we introduced in Section 2 using techniques that have also been utilized in Jin al. 2018). For simplicity of notations, temporarily drop the indices and use pm and p to denote the transition kernel and reward function whenever there is no ambiguity.
= r TH Vm E
1
8
So
c+ 8
SI
1-8
8
1 4-8 8
The "JAO MDP" constructed in Jaksch et al. (2010). Dashed lines denote transitions related to the good action a'.
Figure 1:
Consider a two-state MDP as depicted in Figure I This MDP was initially proposed in Jaksch et al. (2010) as a hard instance of stationary MDPs, and following Ji et al. (2018) we will refer to this construction as the "JAO MDP". This MDP has states S { sif and SA actions (1, ..., SA). The reward does not depend on actions: state always gives reward 1 whatever action is taken, and state s, always gives reward O. Any action taken state 8, takes the agent to state so with probability 8, and to state s, with probability 1 6. At state so, for all but a single
'The definition of segments is irrelevant to, and should not be confused with, the notion of epochs previously defined.
24

---

Under review as a conference paper at ICLR 2021
"good" action a", the agent is taken to state s, with probability 6, and for the good action a", the agent is taken to state & with probability 8 + E for some 0 < E < 6. The exact values of 8 and e will be chosen later. Note that this is not an MDP with S states and A actions as we desire, but the extension to an MDP with S states and A actions is routine (Jaksch et al. 2010), and is hence omitted here.
1-E-ô
1 1-8-6
1 E 8
8
1
8
So
E + 6
So
S
E + 8
S
+ 6
8
6
8
8
6
8
S
S
S
-
1 1 5
1 8
Figure 2: A chain with H copies of JAO MDPs correlated in time. At the end of an episode, the state should deterninistically transition from any state in the last copy to the 8, state in the first copy of the chain, the arrows of which are not shown in the figure. Also, the i state in the first copy is actually never reached and hence is redundant.
To apply the JAO MDP to the simplified episodic setting, we ''cocctenate"" H copies of exactly the same JAO MDP into a chain as depicted in Figure denoting the H steps in episode. The initial state of this MDP is the 8, state in the first copy of the chain, and after each episode the state is "reset" to the initial state. In the following, we first show that the constructed MDP is hard instance of stationary MDPs, without worrying about the evolution of the system dynamics. The techniques that we will be using are essentially the same as in the proofs of the lower bound in the multi-armed bandit problem (Auer et al. 2002) or the reinforcement learning problem in the un-discounted setting (Jaksch al., 2010).
The good action a' is chosen uniformly at random from the action space A. and we use E.I-1 to denote the expectation with respect to the random choice of a". We write [-] for the expectation conditioned on action a being the good action a". Finally, we use Eunit[-] to denote the expectation when there is no good action in the MDP, i.e., every action in A takes the agent from state so to s with probability 8. Define the probability notations P. P.)...a()) and F Funir(-) analogously.
Consider running a reinforcement learning algorithm on the constructed MDP for To steps, where To M.Hl. It has been shown in Auer et al. (2002) and Jaksch al. (2010) that it is sufficient to consider deterministic policies. Therefore, we assume that the algorithm maps deterministically from sequence of observations to action a at time t. Define the random variables N, N. and N to be the total number of visits to state s, the total number of visits to Se, and the total number of times that is taken at state 8a, respectively. Let 8, denote the state observed time and a, the action taken at time I. When there is no chance of ambiguity, we sometimes also use 8y to denote the state step of episode m, which should be interpreted as the state 8; observed at time t = (m 1) x H + h. The notation aj is used analogously. Since so is assumed to be the initial state, we have that
To Ps: 8)
Mn
EA. [M]
Pa ==m=8 8)
1=1
m= h=2
M
H
(P (P = (o) PP m s s = so) + Po 8)) Pa(s)) s, s// s))
2
Me
H
(0P, (sp = Sc 0/ fa)) + (8 +
So, a0 = a²) + (5) - =))
m= 1=2
<SE,
[No No. + (8 E, No. + (1- 5)
25

---

Under review as a conference paper at ICLR 2021
and rearranging the last inequality gives us [M[ & - - - [.
For this proof only, define the random variable (To) to be the total reward of the algorithm over the horizon To. and define G(T)) to be the (static) regret with respect to the optimal policy. Since for any algorithm, the probability of staying state s, under IP, (-) is no larger than under Pumit()): it follows that
Ba Ba(W((b)) < [M] < [N NO. + (1 ),a.
=Ba + Ral No S Bunit No. [n
- 5 [N.].
=To - Eunir [M]
(48)
Let To denote the first step that the state transits from state so to in the m-th episode, then
Ma
H
Ma
Hf
Eumit [N]
unar'
Tm
Eunit
[ Tm
8)m-118 5 [N, T
172m
17
Mo
Σ (1 1 8)
H
Mo
1
(1
5)
2
2
26
20
m=1
h=1
m==
To Mo
(49)
2 26
Since the algorithm is deterministic mapping from the observation sequence action, the random variable No is also a function the observations up to time T. In addition, since the immediate reward only depends on the current state, Ng can further be considered just the state sequence up to T. Therefore, the following lemma from Jaksch et al. (2010), which in turn was adapted from Lemma A.1 in Auer et al. (2002). also applies in our setting.
function of
Lemma 10. (Lemma 13 in Juksch al. (2010)) For any finite constant B, let f {s,, 8) Too + [0, B) be any function defined on the state sequence s E (8a; 8,o,8]]ott Tot1, Then, for any 0 < 8 S 2.2 any
0 < < 1 - 26, and any E A, it holds that
B
Eg [x]) S Eamig (s))
21 [Nt].
2
V8
Since No itself is a function from the state sequence to [0, To), we can apply Lemma 10 and arrive
To
E [N[ < Eunir [No]
+
/
2E
[N+]-
(50)
2 V8
From (49
we have that SA Ennit [N+]] = To
Exnit
[N]
To S
+
Ma. 24
By the Cauchy- -chwwaz
2
inequality, we further have that > /2Euni obtain
[N:]
S SA(To
Me). Therefore, from 50
SA
To
Mo
To
Mo 8
R
<
+
SA(To +
2
28
2
v8
Together with 488 and
449
holds that
SA [To]]
E. [.(W <
E.
SA
==1
Tb
Mo
E 1
To
Mo
To
E
Mo, 8
+
SA
+
(51)
28
8 SA
2
28
2
V8
E. UN-DISCOUNTED SETTING
Let us now momentarily deviate from the episodic setting and consider the un-discounted setting (with Mo 1). This is the case of the JAO MDP in Figure where there is not reset. We could
26

---

Under review as a conference paper at ICLR 2021
calculate the stationary distribution and find that the optimal average reward for the JAO MDP is S+t. It is also easy to calculate that the diameter of the JAO MDP is D = 3/- Therefore, the expected (static) regret with respect to the randomness of a can be lower bounded by
26+g-
6+E
[.[
To B..[W
20 +
ETo
D(To + D)
TDDDD
(Vo+
46 + 28
2
2SA
2VSA
By assuming To 2 DSA (which in turn suggests D we further have that
S V
'Tn SA
and setting & CV ToD
SA for 3
E. [. 2
cD
c²
D
VSAT.D-
D 2
2SA
2SAT.
2
To
3
1
c
SAT
v SATDD.
20
200
1600
It is easy to verify that our choice of d and satisfies our assumption that 0 < E < 6. So far, we have recovered the (static) regret lower bound of (VVAAT) in the un-discounted setting, which was originally proved in Jaksch et al. (210)..
Based on this result, let us now incorporate the sssssiottiiattt of the MDP and derive a lower bound for the dynamic regret RT)). Recall that we are constructing the non con-stationary environment For each segment of length To. the environment held constant, and the regret lower bound for each segment is S (V At the beginning of each new segment, we uniformly sample new action a" at random from the action space to be the good action for the new segment. In this case, the learning algorithm cannot use the information it learned during its previous interactions with the environment, even it knows the switching structure of the environment. Therefore, the algorithm needs to learn new (static) MDP in each segment, which leads to dynamic regret lower bound of ((LTAA that is the number of segments. Every time the good action a varies, will cause a variation of magnitude 2x in the transition kernel. The constraint of the overall variation budget requires that
as a switching-
O ((VSATLD), where let recall
2=L
3
SA L A, which in turn requires L D A--3, Finally, by assigning T.
20
the largest possible value to subject to the variation budget, we obtain a dynamic regret lower bound of Ω (st A A This completes the proof of Proposition
E.2 EPISODIC SETTINGS
Now let us go back to simplified episodic setting, as depicted in Figure 2 One major difference with the previous un-discounted setting is that we might not have time to mix between sa and s, in H steps. (Note that we only need reach the stationary distribution over the (8,, pair in each step h, rather than the stationary distribution over the entire MDP. In fact, the latter case is never possible because the entire MDP this MDP has a mixing time of O (+) (Jin et al. 2018), and hence we can choose to be slightly larger than O H to guarantee sufficient time to mix. All the analysis up to inequality (1 carries set d to be θ (() to get (static) regret lower bound of ((VSATHH) in each segment. Another difference with the previous setting lies in the usage of the variation budget. Since we require that all the steps in the same episode should vary simultaneously, it now takes a variation budget of 2 each time we switch to a new action a" at the beginning of a new segment. Therefore, the overall variation budget now puts a constraint
aperiodic.) It can be shown that the optimal policy on
over to the episodic setting, and essentially
of 2 < O(A) on the magnitude of each switch. Again, by choosing = θ optimizing over possible values of subject to the budget constraint, we obtain a dynamic regret lower bound of Ω ( A in the simplified episodic setting.
SA
and
Taff
Finally, we consider the standard episodic setting as introduced in Section 2 In this setting, we essentially will be concatenating H distinct JAO MDPs, each with an independent good action a".
27

---

Under review as a conference paper at ICLR 2021
into chain like Figure 2 The transition kernels in these JAO MDPs are also allowed to vary asynchronously in each step h, although our construction of the lower bound does not make use of this property. As argued similarly in Jin al. (2018), the number of observations for each specific JAO MDP only To/ H. instead of 7-- Therefore, we can assign slightly larger value to and the learning algorithm would still not be able identify the good action given the fewer observations.
leads to (static) regret lower bound of (H in the stationary RL problem. Again, the transition kernels in all the H JAO MDPs vary simultaneously the beginning of each segment. By optimizing L subject the overall budget constraint
Setting å = θ ( } and θ
(
SA
To
L 2 ( we obtain dynamic regret lower bound of Ω (s A # in the episodic setting. This completes our proof Theorem
28


Reviews:
[{"review_id": "t1j-j9xCOE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies efficient model-free reinforcement learning in non-stationary Markov Decision process. They propose an algorithm with efficient dynamic regret bounds. Besides, they also propose matching lower bounds. \n\npros:\n- The theoretical results are solid since they achieve minimax regret bounds.\n\ncons:\n- The algorithm follows the similar algorithmic framework of [1], which studies provably efficient reinforcement learning with low switching condition. The algorithm of [1] suits non-stationary setting well since it periodically forgets the previous experience and only uses data collected recently. I guess this is the reason why this idea works for non-stationary environment. Maybe more discussion is needed in the paper.\n\n- The assumption about prior knowledge of the variation budget in each epoch is a bit strong. Restart-UCB algorithm require this knowledge to construct the confidence bonus $b_{\\Delta}$. However, in real applications, it is almost impossible to know the variation budget beforehand (If we know this, we can almost directly know the reward and transition in each step.) For theoretical analysis, I remember that many previous results don't need this assumptions, including papers about non-stationary MDP and non-stationary bandit. Since the reasonability of this assumption is important to quantify the contribution of the paper, I suggest that the authors should discuss in detail about this issue during the rebuttal period, including whether this assumption is common in the previous literature, and whether it is possible to remove the assumption.  \n\n[1] Provably Efficient Q-Learning with Low Switching Cost\n\n\n-------Post Rebuttal-------\n\nThanks for the feedback from the authors. I am glad to see that the new theorem (Theorem 2) has successfully tackle the problem about the prior knowledge of the variation budget. I have updated the score accordingly.", "extra_scores": {}, "extra_text": {}}, {"review_id": "q9c-iEekiQI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper derives a low-regret algorithm to control non-stationary MDPs. By non-stationary, the authors mean that the transition matrix and reward function can vary over time. The sum of all changes is bounded by a variation budget \\Delta (known by the controller). This algorithm combines two ingredients:\n1. The learning horizon is decomposed into epochs whose lengths depends on \\Delta.\n2. Within an epoch, the algorithm uses an unmodified Q-learning UCB.\n\nThe authors derive an upper bound on the regret of the algorithm that is obtained by carefully choosing the epoch lengths.\n\nI found the paper reasonably well written (although the technical part are not easy to understand, see below). The algorithm is clearly defined and the results are easy to understand.  The problem of learning in non-stationary environment is quite challenging and hence the result is appealing. The proof approach is quite classical for this kind of problems and looks reasonable (apart from a term of Proposition 1, see below).\n\nThat being said, I found that the paper has a number of shortcomings that prevent me from seeing its contributions as remarkable. In particular:\n\n1. What is the main originality of the paper? The idea of restarting for non-stationary environment is not new (Jaksch et al. 2010). The use of Q-learning UCB is not new (Jin et al. 2018). The combination of the two and its analysis is probably new.  Yet, I fail to see it as a real contributions. In particular, I have the impression that the approach taken by the authors could be easily adapted by replacing Q-learning UCB by any other algorithm (UCRL2, PSRL,...).  The usual approach to obtain a regret bound is to view the regret as a term of opportunism + a term of concentration. Here, the only addition is to add a term of \"error\" due to \\Delta and then to tune the epoch lengths. This approach seems algorithm-independent.\n\n2. I do not understand why *model-free* is so important here. The fact that there is no analysis of model-free non-stationary algorithms in the literature might just be because model model-based algorithms perform better? The authors do not compare their algorithms to existing solutions. Some numerical experiments could be useful.\n\n3. On page 8: where did the SAH^3 go? Naively replacing D by its value and T by SA\\Delta H^2 leads to a term TH which grows in T. Where is the catch?\n\n4. The heavy notations make the technical parts hard to follow. Also, on the beginning of page 6, the notations \\v{n}^k_h are then transformed in \\v{n} while being similar to N and \\v{N}. I would hope that some simplification are doable.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "dArp-4-46zT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an algorithm called RestartedQ-UCB for nonstationary episodic MDP. The setting studied is when the transition kernels and reward functions are both possibly changing with iterations. I think the setting is not quite novel, similar settings have appeared in several earlier papers, including Ortner et al. (2020) and Cheung et al. (2020).\n\nThe method proposed uses a simple restarting strategy on top of an existing algorithm with known stationary regret, for example, the Q-learning methods (Jin et al., 2018; Zhang et al., 2020). The idea of restarting strategy for nonstationary stochastic optimization or decision-making (even MDP, see reference below) is not new, which clearly diminishes the novelty of this paper. As far as I know,\n1. stochastic optimization or online convex optimization. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 2015.\n2. multi-armed bandits. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with nonstationary rewards. In NeurIPS, 2014. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration–exploitation in a multi-armed bandit problem with non-stationary rewards. Stochastic Systems, 9(4):319–337, 2019.\n3. stochastic linear bandits. Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In AISTATS, 2020.\n4.contextual bandits. Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In COLT, 2018.\n5. MDP. Ronald Ortner, Pratik Gajane, and Peter Auer. Variational Regret Bounds for Reinforcement Learning. In UAI 2019. [NOTICE: this paper is published at UAI 2019 venue, while in the submission authors mistakenly cite as UAI 2020. This should be corrected.] A similar idea also appears for the tracking case (when the nonstationary setting reduces to the piecewise stationary) in UCRL2 paper (Jaksch et al. 2010, Section 7 Regret Bounds for Changing MDPs)\n\nSome of the references are not well placed: \"We measure the optimality of the policy π in terms of its dynamic regret (Cheung et al., 2020; Domingues et al., 2020)\" I do not think the originality of dynamic regret (even for nonstationary MDPs) should be credited to these two papers.\n\nAs far as the extra optimism, this has also appeared in the recent work for studying nonstationary MDP (Cheung et al. 2020). \n\nThe main results (Theorem 1 and Theorem 2) are interesting, didn't the algorithm require the variation quantities Delta_r and Delate_p as input? I think this is not fully overcome in previous studies, even the most recent papers (Cheung et al., 2020; Domingues et al., 2020; Fei et al. 2020). The issue should be highlighted in the theorem and the setting of input parameters in the statement of algorithms, explicitly.\n\nThe lower bound for nonstationary MDP is not surprising by constructing a piecewise stationary hard instance and further taking a reduction to the lower bound for stationary MDP (Jin et al., 2018). Similar constructions have appeared in earlier studies of dynamic regret, to name a few, online convex optimization (https://arxiv.org/pdf/1810.10815.pdf), linear bandits (https://arxiv.org/pdf/1810.03024.pdf), etc.\n\nOverall, the paper fails to provide much technical contribution and novelty to the community since most techniques and ideas were published previously, and unfortunately falls below the bar of ICLR. Please correct me if I missed non-trivial technical contributions.\n\nThe final issue is that in the introduction section the authors provide several practical intriguing applications with modeling by nonstationary RL/MDP, and also claim that \"our model-free algorithm is more time- and space-efficient, flexible to use, and more compatible with the design of modern deep RL architectures\" but no experiments are offered especially in a conference like ICLR, while the theoretical contributions seem to be unable to stand it alone. The authors should implement the algorithm in practical nonstationary RL tasks to show its strength, a number of references can be found at the survey https://arxiv.org/abs/1905.03970", "extra_scores": {}, "extra_text": {}}, {"review_id": "SoFJee22U5", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the first model-free RL algorithm (RestartQ-UCB) for the non-stationary episodic RL problems, where the model parameters are determined by an oblivious adversary and change with time with a certain budget on the total variation. Moreover, the authors provide a rigorous analysis of RestartQ-UCB and establish a near-optimal regret upper bound as well as the first lower bound on the dynamic regret in non-stationary RL.\n\nThe paper is a novel and rigorous theoretical contribution to non-stationary RL. Overall the paper is well-written and easy to follow. I have done a careful check of the proof of Theorem 1 (including the technical lemmas) and a high-level check of the rest of the analysis, and they all look sound. Overall I do not find any particular weakness in this paper. My only concern is that RestartQ-UCB requires the knowledge of the variation budget in each epoch. While this assumption has been considered in (Ortner et al., 2020), it would be helpful to provide more justification for this assumption.\n\nAdditional comments:\n\n-While I could follow the proofs step by step in a mechanistic way, it would be helpful to first outline the high-level idea of the proofs at the beginning of Section 4.\n\n-It is not totally clear to me why stages are necessary for the analysis. Could the authors provide some intuition behind this design?\n\n-While the proofs of Theorem 1 and 2 are similar, it would be helpful to at least highlight the main differences in the main text.\n\n-In Appendix B.2: In the second sentence of the first paragraph, shall the goal be proving $Q_h^{k,*}(s,a)\\leq Q_{h}^{k+1}(s,a)$ instead?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows (nearly) matching upper and lower bounds on dynamic regret for non-stationary finite-horizon reinforcement learning problems. The paper studies an important problem and the results are interesting. Some reviewers are concerned that there is not enough algorithmic and theoretical innovations in light of prior results. Authors need to improve the presentation and add a more detailed discussion on related works, the novelty and the originality of the paper, and the new algorithmic and theoretical contributions. Finally, authors can improve the submission by implementing the proposed method and adding experiments.
Decision: Reject