Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments
Authors: Liyu Chen
Haipeng Luo
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
stochastic shortest path
dynamic regret minimization
non-stationary environments

Abstract: We initiate the study of dynamic regret minimization for goal-oriented reinforcement learning modeled by a non-stationary stochastic shortest path problem with changing cost and transition functions.
We start by establishing a lower bound $\Omega((B_{\star} SAT_{\star}(\Delta_c + B_{\star}^2\Delta_P))^{1/3}K^{2/3})$, where $B_{\star}$ is the maximum expected cost of the optimal policy of any episode starting from any state, $T_{\star}$ is the maximum hitting time of the optimal policy of any episode starting from the initial state, $SA$ is the number of state-action pairs, $\Delta_c$ and $\Delta_P$ are the amount of changes of the cost and transition functions respectively, and $K$ is the number of episodes.
The different roles of $\Delta_c$ and $\Delta_P$ in this lower bound inspire us to design algorithms that estimate costs and transitions separately.
Specifically, assuming the knowledge of $\Delta_c$ and $\Delta_P$, we develop a simple but sub-optimal algorithm and another more involved minimax optimal algorithm (up to logarithmic terms).
These algorithms combine the ideas of finite-horizon approximation [Chen et al., 2021b], special Bernstein-style bonuses of the MVP algorithm [Zhang et al., 2020], adaptive confidence widening [Wei and Luo, 2021], as well as some new techniques such as properly penalizing long-horizon policies.
	Finally, when $\Delta_c$ and $\Delta_P$ are unknown, we develop a variant of the MASTER algorithm [Wei and Luo, 2021] and integrate the aforementioned ideas into it to achieve $\widetilde{O}(\min\{B_{\star} S\sqrt{ALK}, (B_{\star}^2S^2AT_{\star}(\Delta_c+B_{\star}\Delta_P))^{1/3}K^{2/3}\})$ regret, where $L$ is the unknown number of changes of the environment.

Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments
Liyu Chen
Haipeng Luo University of Southern California
University of Southern California liyucOusc.
haipengl@usc..
Abstract
We initiate the study of dynamic regret minimization for goal-oriented reinforce- ment learning modeled by non-stationary stochastic shortest path problem with changing cost and transition functions. We start by establishing lower bound [[BBSSAT.AA) + B) of the optimal policy any episode starting from any state, T, is the maxi- mum hitting time of the optimal policy of any episode starting from the initial state, SA is the number state-action pairs, A. and Ap are the amount changes of the cost and transition functions respectively, and K' is the number episodes. The different roles of A. and Ap in this lower bound inspire us design algorithms that estimate costs and transitions separately. Specifically, assuming the knowledge of A. and Ap, we develop a simple but sub-optimal algorithm and another more involved minimax optimal algorithm (up to loga- rithmic terms). These algorithms combine the ideas of finite-horizon approxi- mation |Chen al., 2022a], special Bernstein-style bonuses of the MVP algo- rithm [Zhang et al., 2020]. adaptive confidence widening [Wei and Luo, 2021], as well as some new techniques such properly penalizing long-horizon policies. Finally, when A. and Ap are unknown, we develop a variant of the MASTER algorithm [Wei and Luo, 2021] ]] and integrate the aforementioned ideas into achieve ( (. B.S SB? AT, (A. B. P)) K2/33) regret, where L is the unknown number of changes of the environment.
where B, is the maximum expected cost
1 Introduction
Goal-oriented reinforcement learning studies how achieve certain goal with minimal total cost in an unknown environment via sequential interactions. It has often been modeled online learning in an episodic Stochastic Shortest Path (SSP) model, where in each episode, starting from fixed initial state, the learner sequentially takes an action, suffers a cost, and transits to the next state, until the goal state reached. The performance of the learner can be measured by her regret, generally defined as the difference between her total cost and that of sequence of benchmark policies (one for each episode).
Despite the recent surge of studies on this problem, all previous works consider minimizing static regret, special case where the benchmark policy the same for every episode. This reasonable only for (near) stationary environments where one single policy performs well over all episodes. In reality, however, the environment is often non-stationary with both the cost function and the transition function changing over episodes, making static regret an unreasonable metric. Instead, the desired objective is to minimize dynamic regret, where the benchmark policy for each episode the optimal policy for that corresponding environment, and the hope is to obtain sublinear dynamic regret whenever the non-stationarity not too large.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Based on this motivation, we initiate the study of dynamic regret minimization for non non- non-stationary SSP and develop the first set of results. Specifically, our contributions are as follows:
To get a sense on the difficulty of the problem, we start by establishing a dynamic regret lower bound in Section 3. Specifically, we prove that (( SAT. (A. + B) K2/3) regret is unavoidable, where B, is the maximum expected cost of the optimal policy of any episode starting from any state, T. is the maximum hitting time of the optimal policy of any episode starting from the initial state, S and A are the number of states and actions respectively, A. and Ap are the amount of changes of the cost and transition functions respectively. and K is the number of episodes. Note the different roles of A. and Ap here the latter is multiplied with extra B, factor, which we find surprising for a technical reason discussed in Section 3. More importantly, this inspires to estimate costs and transitions independently in subsequent algorithm design.
For algorithms, we first present a simple one (Algorithm 2 in Section 5) that achieves sub-optimal regret of ([BB,SATTas ( A + B²Ap)) where Tmax 2 T, is the maximum hitting time of the optimal policy of any episode starting from any state. Except for replacing T. with the larger quantity Tmax, this bound is optimal in all other parameters. Moreover, this also translates to a minimax optimal regret bound the finite-horizon setting (a special case of SSP), making Algorithm the first model- algorithm with the optimal (Sa) dependency.
To improve the T maax dependency to T. in Section 6, we present more involved algorithm (Algorithm 4) that achieves a near minimax optimal regret bound matching the earlier lower bound up to logarithmic terms.
Both algorithms above require the knowledge of A. and Ap. Moreover, for a special kind of non-stationary environments where the cost/transition function only changes L times, they not able to achieve more favorable dynamic regret bound of the form VLK. To overcome these issues altogether, in Section 7, we develop a variant of the MASTER algorithm [Wei and Luo, 2021] and integrate the earlier algorithmic ideas into it, which finally leads to a (sub-optimal) O(min B,.V ALK, (B AT, (A. + (33)))33/////))) regret bound without knowing the non-stationarity A.. Ap, or L.
Techniques All our algorithms are built on top of finite-horizon approximation scheme first proposed by Cohen et al. [2021] and later improved by Chen et al. [2022a]; see Section 4. Both the sub-optimal Algorithm 2 and the optimal Algorithm 4 are then developed based on idcas from the MVP algorithm [Zhang ct al., 2020] (for the finite-horizon setting), which adopts a UCBVI-style update rule [Azar et al., 2017] with special Bernstein-style bonus term. The sub-optimal algorithm further integrates the idea of adaptive confidence widening [Wei and Luo, 2021] | into the UCBV VI-yyle update by subtracting bias from the cost function uniformly over all state-action pairs, which helps control the magnitude of the estimated value function. The minimax optimal algorithm. on the other hand, adds a positive correction term to the cost function to penalize long-horizon policies, which helps improve the Tmax dependency to T.. It also incorporates several non-stationarity tests to ensure that the algorithm resets its knowledge of the environment when the amount of non-stationarity is large. Both algorithms maintain (update and reset) cost and transition estimation independently, which is the key to achieve the correct B, dependency for both the -eerate and Prrrelated terms.
To handle unknown non-stationarity, we adopt the idea of the MASTER algorithm from [Wei and Luo, 2021]. Although the nature of MASTER is blackbox reduction, we cannot apply it directly due to the presence of the correction term that changes continuously and brings extra challenges in tracking the learner's performance. We handle this by redesigning the first non-stationarity test of the MASTER algorithm. Specifically, we maintain multiple running averages of the estimated value function to detect different levels of non-stationarity.
Related Work Static regret minimization in SSP has been heavily studied in recent years, for both stochastic costs [Tarbouriech et al., 2020, Cohen et al., 2020, 2021, Tarbouriech et al., 2021, Chen et al., 2021a, a, Lafarnia-Jahrom et al., 2021, Vial et al., 2021, Min et al., 2021, Chen et al., 2022a] and adversarial costs [Rosenberg and Mansour, 2021, Chen al., 202 Chen and Luo, 2021, Chen et al., 2022b]. To the best of our knowledge, we are the first to study dynamic regret for non-stationary SSP.
There is also a surge of studies on online learning in non-stationary environments, ranging from bandits [Auer et al., 2019, Chen et al., 2019, 2021c, Russac et al., 2020, Faury et al., 2021, Abbasi- Yadkori et al., 2022, Suk and Kpotufe, 2021] to reinforcement learning [Gajane et al., 2018, Ortner

---

et al., 2020, Cheung et al., 2020, Fei et al., 2020, Mao et al., 2021, Zhou et al., 2020, Touati and Vincent, 2020. Domingues et al., 2021, Wei and Luo, 2021, Ding and Lavaci, 2022, Lykouris et al.. 2021, Wei et al., 2022]. Compared to previous work, the model we study is quite general and subsumes multi-armed bandit and finite-horizon reinforcement learning. On the other hand, also introduces extra and unique challenges as we will discuss.
2 Preliminaries
A non-stationary SSP instance consists of state space S, action space A. initial state Sinit E S, goal state & S, a set of cost mean functions {ex [c*] with Ck E [0, 1jx1, and a set of transition functions { P& 1x with Ps- = the simplex over S_, and K is the number of episodes. The set of cost and transition functions unknown to the learner and determined by the environment before learning starts.
and Pk.s.a E As., where S+ = S U (g), As. is
The learning protocol is as follows: the learner interacts with the environment for K episodes. In episode k; starting from the initial state Sinit, the learner sequentially takes an action, incurs a cost, and transits to the next state until reaching the goal state. We denote by (sf of c s the i-th state- www.aaacnnoonntttttiite-
tuple observed in episode k where of is sampled from an unknown distribution with support [0, 1] and mean e& (s af) and s 1 is sampled from Pk.ef.at at We denote by I the total number of steps in episode k; such that st 8 =
Learning Objective Intuitively, in each episode the learner aims at finding policy that minimizes the total cost of reaching the goal state. Formally, a policy æ E A assigns an action ı (s) to each state E S, and its expected cost for episode & starting from a state is denoted as V (s) = where the expectation is with respect the randomness of next states 8141 Pf,ef (x())) and the number of steps T before reaching g. The optimal policy मं.. for episode k is then the policy that minimizes Vi (s) for all s. Using Vi as a shorthand for V we formally define the dynamic regret of the learner as
E|E= le (s( (s+))) Pky of
RK
Vi (7((ia))
When 1 = oc for some k, we let PK= =00.
Remark 1. Note that our learning setting does not fall into the general non-stationary reinforcement learning framework in [Wei and Luo, 2021]. In their framework, they fix policy to play throughout an episode, and the cost incurs by any policy is bounded. While in our case, the learner may follow several different policies within an episode. This is necessary since under unknown and changing transition, the learner may not be able to identify a proper policy (which reaches the goal state with probability 1) at the beginning of an episode, and committing to a single policy within an episode may lead to infinite regret.
Several parameters play a key role in characterizing the difficulty of this problem: B. max Vi (s), the maximum cost of the optimal policy of any episode starting from any state; T. = max; T (smi)) (where Tg (s) is expected number of steps it takes for policy н to reach the goal in episode k starting from state s), the maximum hitting time of the optimal policy of any episode starting from the initial state; Tmax = maxk, T (s), the maximum hitting time of the optimal policy of any episode starting from any state; A. = > K-1
k= ||cx41 - -ellso+ the amount of non-stationarity in the cost functions; and finally Ap = ΣK k=1 max,,a |P - Px.e.alliz the amount of non-stationarity in the transition functions. Throughout the paper we assume the knowledge of B., T., and Tmax, and also B. 2 1 for simplicity. Ae and Ap are assumed to be known for the first two algorithms we develop, but unknown for the last one.
Other Notations For value function V E SS+ and a distribution P over S4, define PV E [V()) (mean) and V(P, V) = (Vs') be the number of states and actions respectively. The notation Ō(-) hides all logarithmic dependency
(variance). Let S = S] and A A= |Al
including In K and for some failure probability 5 E (0, 1). Also define a value function upper bound B = 16B.. For integers and e, we define [s, e] {s, + I,...,e) e) and je] el.
3

---

Algorithm Finite-Horizon Approximation of SSP
Input: Algorithm 2 for finite-horizon MDP M with horizon H 47 47 In(8K). Initialize: interval counter m <
for k 1. K do
1
Set 81 5- Sinit-
while 8 + do
3
Feed initial state "1" to 21 4-
while True do
5
Receive action 0z from 21, play it, and observe cost % and next state sm Feed ch and sh+1 to
$4+1"
6
7
h = or In gg or requests to start a new interval then
Hm. +- h. break.
else h t- +1
Set 8/m+11 H and + 1.
Lower Bound
To better understand the difficulty of learning non-stationary SSP, we first establish the following dynamic regret lower bound.
Theorem 1. In the worst case, the learner's regret is at least (( B
The lower bound construction is similar to that in [Mao et al., 2021], where the environment is piecewise stationary. In each stationary period, the learner is facing a hard SSP instance with slightly better hidden state. Details are deferred to Appendix B.2.
In technical lemma Appendix B.I, we show that for any two episodes k and k2, the change of the optimal value function due to non non-stationarity satisfies V (Smit) - V (smit) S (A. + B, B.Ap) )T., with only one extra B. factor for the A p-related term. We thus find lower bound somewhat surprising since an extra B factor shows up for the Prrrelaeed term. This comes from the fact that constructing the hard instance with perturbed costs requires larger amount of perturbation compared to that with perturbed transitions; see Theorem 7 and Theorem 8 for details.
More importantly, this observation implies that simply treating these types of non-stationarity as a whole and only consider the non-stationarity in value function as done in [Wei and Luo, 2021] [] does give the right B. dependency. This further inspires us consider cost and transition estimation independently in our subsequent algorithm design.
4 Basic Framework: Finite-Horizon Approximation
Our algorithms are all built on top of the finite-horizon approximation scheme of [Cohen et al., 2021 whose analysis is greatly simplified and improved by [Chen et al., 2022a], making it applicable to our non-stationary setting well. This scheme makes of algorithm 2 that deals with special case of SSP where each episode ends within H OTTmax) steps, and applies following Algorithm I. Specifically, call each "mini-episode" 2 is facing an interval. At each step of interval m, the learner receives the decision a% from 21 takes this action, observes the cost oj transits to the next state s and then feed the observation 6% and # to 2 (Line and Line 6). The interval ends whenever one of the following happens (Line 7): the goal state reached, H steps have passed, 2l requests start
the original SSP
interval. In the first case, the initial state sn+1 of the next interval m + will be set to Smm, while in the other two cases, it is naturally set to the learner's current state, which is also sH.. where H. is the length of interval m (see Line 10). At the end of each interval, artificially let 21 suffer terminal cost cy H +1) (sm
where cy(s) 2B,1(s # g).
'This last condition is not present in prior works. We introduce since later our instantiation of I will change its policy in the middle of an interval, and creating a new interval in this case allows us to make sure that the policy in each interval is always fixed, which simplifies the analysis.

---

Algorithm 2 Non-Stationary MVP
Parameters: window sizes We (for costs) and Wr (for transitions), and failure probability 8. Initialize: for all (s, a., C(s, a) + 0, M(s, a) t 0, N(s, + 0. ((s, a, s') + 0.
Initialize: Update (1). for m = 1,..., M do
for h 1...., H do Play action 0% < argmin Qn (5% a). receive cost cj and next state 8/+1-
C(s xx - ch M(s xx ) _ 1, N( ax & 1, N( a% sh+1) E 1.2 M(s 0% = 2 N( ax 2 for some integer I z 0 then if % break (which starts a new interval).
if W. divides then reset C(s, a) + 0 and M(s a) 0 for all (s,a) a). if Wp divides m then reset a(.,a, (,, t- and N(s, a) < 0 for all (8, (8,a,88) Update (m + 1).
Procedure Update (m)
VB+1 (6) 2B, # g). (g) 0 for h H, 2 In (2SAHKm and x mH for all (s,a) do
N (s, a) < max {1, (8, a)), M + max (is ((s, t C(s.a)
M (a,a)
E(s,aju C(s. a) max (, M+ Mt(aaa Ps + N(sa.))
N+(x,))
while True do for h = H do
b, - max V V.P... 49Bv5.
for all (s,a).
[+ Qn(s,a) - max (0, (s, + V.+V ba(s, a) x) for all (8,a).
(=,a
(s( min, Qn (8, a) for s.
if o, (x) - B/4 then break; else x 2x.
This procedure (adaptively) generates a non-stationary finite-horizon Markov Decision Process (MDP) that faces: M (S, A. 9. {cm J Jm= {Pm [Pm)) [m=")m=1000 Im=1.cy. .H.. Here, ct Ck(m) and pm Pk(m) where k(m) is the unique episode that interval belongs to, and M is the total number of intervals over K episodes, random variable determined by the interactions. Note that c and pm always lie in the oblivious sets ] and ( respectively, but e and pm are not oblivious since their values depend on the interaction history. Let V.T. (s) be the expected cost (including the terminal cost) of following policy स starting from state in interval m. Define the regret 2 over
A the first M' intervals in M RM = =mM", 2h cx V/, (m(m)) (sfT) where use cH shorthand for the terminal cost Cy H... +1). Following similar arguments as in [Cohen et al.,
M'
2021, Chen et al., 2022a], the regret in M and M are close in the following sense.
Lemma 1. Algorithm ensures R& < RM + B..
See Appendix C for the proof. Based on this lemma, in following sections focus developing the finite-horizon algorithm 2 and analyzing how large Rı is. Note, however, that while this finite-horizon reduction is very useful, it does not mean that our problem is as easy as learning MDPs and that care still needed when designing 2 order to obtain tight regret bounds as we will show.
non-stationary
directly plug in an existing algorithm as 2. Great
5 A Simple Sub-Optimal Algorithm
this section, we present relatively simple finite-horizon algorithm for M which, combination with the reduction of Algorithm 1, achieves a regret bound that almost matches our lower bound except that T, is replaced by T Tmax- The key steps are shown Algorithm follows the ideas
2 = is shorthand for
5

---

of the MVP algorithm [Zhang et al., 2020] and adopts a UCBVI-style update rule (Line 6) with Bernstein-type bonus term (Line 5) to maintain set of Qn functions, which then determines the action at each step in a greedy manner (Line 1). The two crucial new elements are the following. First, in the update rule Line 6, we subtract positive value z uniformly over all state-action pairs so that | 1Qull is of order O (.)) (recall B- = 1. and we find the (almost) smallest such x via a doubling trick (Line 7). This is similar to the adaptive confidence widening technique of [Wei and Luo, 2021], where they increase the size of the transition confidence set to ensure bounded magnitude on the estimated value function; our approach is an adaptation of their idea to the UCBVI style update rule.
Second, we periodically restart the algorithm (by resetting some counters and statisties) in Line and Line 4. While periodic restart is a standard idea to deal with non-stationarity, the novelty here a two-scale restart schedule: we set one window size We related to costs and another one Wr related to transitions, and restart after every W. intervals or every Wp intervals. As mentioned, this two-scale schedule is inspired by the lower bound in Section 3, which indicates that cost estimation and transition estimation play different roles in the final regret and should be treated separately.
Another small modification is that we start new interval when the visitation to some (s, a) doubles (Line 2), which helps remove Tmax dependency in lower-order terms and is important for following sections. With all these elements, we prove the following regret guarantee of Algorithm 2.
Theorem 2. For any M' S M, with probability at least 1 - 228 Algorithm 2 ensures RM = + t/ww,) + (A.We + B.ApWp) Tmax)
Ö (M ( (BB.A(W/.. + B./ww) + B...A
Thus, with a proper tunning of We and Wp (that is in term of M'), Algorithm 2 ensures Ras Ö(BBSATT max (Ae + BL p)) ////// M 2/33) However, this does not directly imply bound on Ras since M is a random variable (and the tunning above would depend on M). Fortunately, to resolve this it suffices to perform a doubling trick on the number of intervals, that is, first make guess on M, and then double the guess whenever M exceeds it. We summarize this idea in Algorithm 3. Finally, combining it with Algorithm 1, Lemma I, and the simplified analysis of [Chen et al., 2022a] which is able to bound the total number of intervals M in terms of the total number of episodes K (Lemma 16), we obtain the following result (all proof's are deferred to Appendix D).
Theorem 3. With probability at least 1 - 228, applying Algorithm I with A being Algorithm 3 ensures Rg² ((B.,SATmaxll + B)) k22/3) (ignoring lower order terms) for any K" S K.
Note that Theorem actually provides an anytime regret guarantee (that is, holds for any K' S K). which is important in following sections. Compared to our lower bound in Theorem 1, the only sub-optimality is in replacing T. with the larger quantity Tmux. Despite its sub-optimality for SSP, however, as a side result our algorithm in fact implies the first model-based finite-horizon algorithm that achieves the optimal dependency on SA and matches the minimax lower bound of [Mao et al., 2021]. Specifically, in previous works, the optimal SA dependency is only achievable by model-free free algorithms, which unfortunately have sub-optimal dependency on the horizon by the current analysis (see [Mao et al., 2021, Lemma 10)). On the other hand, existing model-based algorithms for finite state-action space all follow the idea of extended value iteration, which gives sub-optimal dependency on S and also brings difficulty in incorporating entry-wise Bernstein confidence sets.? 3 Our approach, however, resolves all these issues. See Appendix D.4 for more discussions.
Technical Highlights The key step of our proof for Theorem 2 is to bound the term EM' E V Pm
"x ag. V.t.m - where Vi is the value of Va+1 at the beginning of interval m, and Vi is the optimal value function of Mt in interval m (formally defined in Ap-
Hm
pendix A). The standard analysis on bounding this term requires (1 (s) - Vi (s) 2 O, which is only true in stationary environment due to optimism. To handle this in non-stationarity envi-
ronments, we carefully choose a set of constants { } so that V (s) + 2%, V (s) 2 0
(Lemma 18), and then apply similar analysis on ΣM MM Hm V(Pm A .ar W++1 - v =
M' Hm ΣM' Em=1& Ch ag. h+1 + 2m. - V. See Lemma 20 for more details. 22
V(pm
'Note that the transition non statiioanon Ap is defined via L, norm. Thus, naively applying entry wise confidence widening Bernstein confidence sets introduces extra dependency on S.

---

Algorithm 3 Non-Stationary MVP with Doubling Trick
for n 1,2,...00 do
Initialize an instance of Algorithm 2 with W [(B_SA)43(">>444 ()ax)) max)) and Wp ((54)))9(2~11/40 (mAppm>>))mmm))))3)) and execute it intervals m -2-11_ ....,, 2 1.
Algorithm 4 MVP with Non-Stationarity Tests
Parameters: window sizes Wa and Wp, coefficients Ct, C2 sample probability p, and failure probability 8.
Initialize: ResetC(), ResetP(), U1)ate for ,,..., M do for h ,...., do
Play action 0% + argmin, Qn a), receive cost cj and next state 8
C(s : _ ch M( a%) $ 1, Ns ax E 1, a% 8%41) E
X E ch -ss 0 ), XP $ ( Por. VA+1-
if mm 9 or M(s oh =2 or N( o%) = 2 for some integer 2 20 then L break (which start a new interval).
2
i Xm (defined in Lemma 24) then ResetC(). (Test 1)
x Xm (defined in Lemma 25) then ResetC() and ResetP(). (Test 2)
vf W. then ResetC().
5
vf -W then ResetC() and ResetP ().
ve = 1, PP $ 1, Update (m +).
V. > / some h (Test 3) then
ResetC(), with probability execute ResetP(), O, and Update (m + 1).
Procedure Update (m)
VB+1(s) 2B.I(s + 9). (g) for all S H, and 21l In (2SAHKm) GL
7
6² + min Vee 25 J. p² + min 02 Vur w 17 + p + Bp".
for all (s, do
(= t max N (, a)), M (s, a) max (1, M a)} ((s,a) +- C(s.a)
M-
(..a()) N(s.a.))
(1.a))) ((s,a) max (() V M (a.a) M (a,a)
E(s.a):
a(s,a) a(sa) 8n.
for /1 = H
(n) < max 7V
V(P. V(Paa 498/5. N+(a.a)
for all (s,a).
(=
(x, max (0,8(s + Pa Vh+ bn(s, a)} all (8,
[s(s)) argmin, (s, for a.l
Procedure ResetC() L vc 1, 0, C(s,a) M(s,a) 0 for all (s,
Procedure (esetP()
p - 1, 8
+ 0, O.N,(,,,,))) + 0, ((s, + 0 for all (8, s').
6 A Minimax Optimal Algorithm
In this section, we present an improved algorithm that achieves the minimax optimal regret bound up logarithmic terms, starting with refined version of Algorithm 2 shown in Algorithm 4. Below, focus on describing the new elements introduced in Algorithm (that is, Lines 1-3 and 6-4).*
The main challenge in replacing Tmax with T, is that the regret due to non-stationarity accumulates along the learner's trajectory, which can be as large as O(A,, + B, B.AP)) since the horizon H
Line 4 and Line 5, althogh written in different form, similar to Line and Line of Algorithm 2.

---

Algorithm 5 A Two-Phase Variant of Algorithm 1
Initialize: Phase 1 algorithm instance 21 and Phase 2 algorithm instance A2. Execute Algorithm with 2 = 21 for every first interval of an episode, and 21 = M2 otherwise.
(recall // O ([Tmax) ). Moreover, bounding the number of steps needed for the learner's policy to reach the goal is highly non-trivial due to the changing transitions. Our main idea to address these issues is to incorporate correction term 1) (computed in Line 7) into the estimated cost (Line 4) to penalize policies that take too long to reach the goal. This correction term is set to be an upper bound of the learner's ' average regret per interval (defined through pa and p" in Line 7). It introduces the effect of canceling the non-stationarity along the learner's 's trajectory when it is not too large. When the con-stationarity is large, on the other hand, we detect it through two stationnyy tests (Line and Line 3), and reset the knowledge of the environment (more details to follow).
However, this correction leads to one issue: we cannot perform adaptive confidence widening (that is, the - bias) anymore as it would cancel out the correction term. To address this, we introduce another test (Line 6, Test 3) to directly check whether the magnitude of the estimated value function is bounded as desired. If not, we reset again since that is also an indication of large non-stationarity.
We now provide some intuitions on the design of Test 1 and Test 2. First, one show that the two quantities X and X" we maintain in Line 1 are such that their sum is roughly an upper bound on the estimated accumulated regret. So directly checking whether X + X² is too large would be similar to the second test of the MASTER algorithm [Wei and Luo, 2021]. Here, however, we again break it into two tests where Test 1 only guards the non-stationarity in cost, and Test 2 mainly guards the non-stationarity in transition. Note that Test 2 also involves cost information through V. but our observation is that we can still achieve the desired regret bound as long as the ratio of the number of resets caused by procedures ResetCO) and ResetPO) is of order ((B)). ). This inspires us to reset both the cost and the transition estimation when Test 2 fails, but reset the transition estimation only with some probability p (cventually set to B/B.) when Test 3 fails.
For analysis, we first establish a regret guarantee of Algorithm 4 in an ideal situation where the first state of each interval is always Siitt. (Proofs of this section are deferred to Appendix E.)
Theorem 4. Lei e1 = vB.SA/T.. C2 VSA/T., W. = [(SA))/((K /TT((A)T..))///33 and = B/ Suppose 8 = Simit for all m S K, then Algorithm 4 B.AP))) (333/33 (ignoring lower order terms) with probability
WP
ensures Rx = O((...AT)
at least 408.
The reason that we only analyze this ideal case that, if the initial state not Sints then even the optimal policy does not guarantee T, hitting time by definition. This also inspires us to eventually deploy a two-phase algorithm slightly modifying Algorithm I: feed the first interval of each episode into instance of Algorithm 4, and the rest of intervals into an instance of Algorithm 3 (see Algorithm 5). Thanks to the large terminal cost, we are able to show that the regret in the second phase is upper bounded by constant, leading to the following final result.
Theorem 5. Algorithum 5 with 2, being Algorithm 4 and M2 being Algorithm 3 ensures Rx ((B,SAT,,A, + B/ K2/3) (ignoring lower order terms) with probubility at least 1 - 648.
Ignoring logarithmic and lower-order terms, our bound is minimax optimal. Also note that the bound sub-linear (in K) as long as A. and A p are sub-linear (that is, not the worst case).
7 Learning without Knowing A. and AP
To handle unknown -tatstation,rity, we combine our algorithmic ideas in previous sections with a new variant of the MASTER algorithm [Wei and Luo, 2021]. The original MASTER algorithm is a blackbox reduction that takes base algorithm for (near) stationary environments as input, and turns it into another algorithm for non-stationarity environments. For many problems (including multi-armed bandits, contextual bandits, linear bandits, finite-horizon or infinite- Wei and I Luo [2021] show that the final algorithm achieves optimal regret without knowing the non-stationarity. While powerful, MASTER can not be directly used in our problem to achieve the
MDPs),
8

---

same strong result. As we will discuss, some modification is needed, and even with this modification, some extra difficulty unique SSP still prevents us from eventually obtaining the optimal regret.
Specifically, in order to obtain T. dependency, we again follow the two-phase procedure Algorithm 5 and instantiate MASTER algorithm with a different base algorithm in each phase. In Phase 1, since it is unclear how to update cost and transition estimation independently under the framework of MASTER, we adopt a simpler version of Algorithm as the base algorithm, which performs synchronized cost and transition estimation and a simpler non-stationarity test; see Algorithm 6 (all algorithms/proofs in this section are deferred Appendix F due space limit). In Phase 2, we use Algorithm 2 as the base algorithm.
Our version of the MASTER algorithm (Algorithm 8) requires different Test 1 compared to that in [Wei and Luo, 2021], which is essential due to the presence of the correction terms in Algorithm 6. Specifically, it no longer makes sense simply maintain the maximum of estimated value functions over the past intervals, since the cost function combined with the correction term is changing adaptively, and a large correction term will interfere with the detection of small amount of non-stationarity. Our key observation is that for base algorithm scheduled on a given range by MASTER, the average of its correction terms within the same range is of the desired order that does not interfere with non-stationarity detection. This inspires us to maintain multiple running averages of the estimated value functions with different scales (see Line 2 of Algorithm 8). Then, to detect a certain level of non-stationarity. we refer to the running average with the matching scale (see Line 3).
We show that the algorithm described above achieves the following regret guarantee without knowl- edge of the non-stationarity.
Theorem 6. Let 21 be an instance of Algorithm with Algorithu 6 as the buse algorithm and Un be an instance of Algorithm 8 with Algorithum 2 as the base algorithm. Then Algorithm 5 with 2 and 22 ensures with high probability (ignoring lower order terms):
Rx = = (min
{ (B.SVALK, B.SVAK + +BBS + B.AD)..)
K-1 I4Px+1 & Ps or ck+1 # ck is the number changes of the environment (plus one). Moreover, this is achieved without the knowledge of Do Ap, or L.
where L L= -
The advantage of this result compared to Theorem is two-fold. First, it adapts to different levels of non-stationarity (Ae, Ap, and L) automatically. Second, it additionally achieves bound of order Ö(B.Sv AALK), which could be much better than that in Theorem 5; for example, when L = O(), the former is a -o-order bound while the latter is of order 22233, As discussed in [Wei and Luo, 2021], this is a unique benefit brought by the MASTER algorithm and is not achieved by any other algorithms even with the knowledge of L.
The disadvantage of Theorem 6, on the other hand, is its sub- auboontimality in the B, dependency for the -rllated term and the S dependency for both terms. The extra B, dependency is due to the synchronized cost and transition estimation. As mentioned, it is unclear how to update cost and we do in Algorithm 4 under the framework of MASTER, which we leave as an important future direction. On the other hand, the extra S dependency comes from the fact that the lower-order term in the regret bound of the base algorithm affects the final regret bound (see the statement of Theorem 13). Specifically, the lower-order term is B.S² B.S A instead of B.SA, which eventually leads to extra S dependency. How to remove the extra S factor in the base algorithm, or eliminate the undesirable lower-order term effect brought by the MASTER algorithm, is another important future direction.
transition estimation independently
8 Conclusion
In this work, we develop the first set of results for dynamic regret minimization in non- mon--stttonary SSP, including a (near) minimax optimal algorithm and two others that are either simpler or advantageous in some other cases. Besides the immediate next step such as improving our results when the non- stationarity is unknown, our work also opens up many other possible future directions on this topic, such as extension to more general settings with function approximation. It would also be interesting to study more adaptive dynamic regret bounds in this setting. For example, our R, and T, are defined as the maximum optimal expected cost and hitting time over all episodes, which is undesirable if only
9

---

few episodes admit a large optimal expected cost or hitting time. Ideally, some kind of (weighted) average would be more reasonable measure in these cases.
Acknowledgments and Disclosure of Funding
The authors thank Aviv Rosenberg and Chen- Yu Wei for many helpful discussions. HL is supported by NSF Award IIS-1943607 and a Google Research Scholar Award.
References
Yasin Yadkor,, Andras Gyorgy, and Nevena Lazic new look at dynamic regret for non-stationary stochastic bandits. arXiv preprint arXIv:2201.065322 2022.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with unknown number of distribution changes. In Conference on Learning Theory, pages 138-158.
PMLR, 2019.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pages 263-272. PMLR,
2017.
Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. In International Conference on Machine Learning, 2021.
Liyu Chen, Mehdi Jafarnia-Jahoon Rahul Jain, and Haipeng Luo. Implicit finite-horizon approxima- tion and efficient optimal algorithms for stochastic shortest path. Advances in Neural Information Processing Systems, 2021a.
Liyu Chen, Haipeng Luo, and Chen-Yo Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference Learning Theory, pages 1180-1215.
PMLR, 2021b.
Liyu Chen, Rahul Jain, and Haipeng Luo. Improved no-regret algorithms for stochastic shortest path with linear MDP. International Conference on Machine Learning, 2022a.
Liyu Chen, Haipeng Luo, and Aviv Rosenberg. Policy optimization for stochastic shortest path. Conference Learning Theory, 2022b.
Wei Chen, Liwei Wang. Haoyu Zhao, and Kai Zheng. Combinatorial semi-bandit in the non-stationary environment. In Uncertainty in Artificial Intelligence, pages 865-875. PMLR, 2021c
Yifang Chen, Chung-Wer Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pages 696-726. PMLR, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary Markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pages
PMLR, 2020.
Alon Cohen, Haim Kaplan, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. In Proceedings of the 37th International Conference on Machine Learning. volume 119, pages 2210-8219 PMLR, 2020.
Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. Advances in Neural Information Processing Systems, 2021.
Yuhao Ding and Javad Lavaci. Provably efficient primal-dual reinforcement learning for CMDPs with non-stationary objectives and constraints. arXiv preprint arXiv:2201.1196. 2022.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. A kernel-based approach non-stationary reinforcement learning in metric spaces. International Conference Artificial Intelligence and Statistics, pages 3538-3546. PMLR, 2021.
10

---

Louis Faury, Yoan Russac, Mare Abeille, and Clément Calauzènes. Regret bounds for generalized linear bandits under parameter drift. arXiv preprint arXiv:2103.05750 2021.
Yingjie Fei, Zhuoran Yang. Zhaoran Wang. and Qiaomin Xie. Dynamic regret of policy optimization in non-stationary environments. Advances in Neural Information Processing Systems, 33:6743- 6754, 2020.
Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805 1006. 2018.
Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. Advances in Neural Information Processing Systems, 29, 2016.
Mehdi infarnia-Jarroma Liyu Chen, Rahul Jain, and Haipeng Luo. Online learning for stochastic shortest path model via posterior sampling. arXiv preprint arXiv:2106.05335, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robus exploration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242-3245. PMLR, 2021.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi- Levi, and Tamer Basar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In International Conference on Machine Learning, pages 7447-7458, PMLR, 2021.
Yifei Min, Jiafan He, Tianhao Wang. and Quanquan Gu. Learning stochastic shortest path with linear function approximation. arXiv preprint arXiv:2110.12727 2021.
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 81-90. PMLR, 22-25 Jul 2020.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, 2021.
Yoan Russac, Olivier Cappé, and Aurélien Garivier. Algorithms for non-stationary generalized linear bandits. arXiv preprint arXiv:2003. 13, 2020.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the 37th International Conference on Machine Learning, pages 8604-8613, 2020.
Joe Suk and Samory Kpotufe. Tracking most severe arm changes in bandits. arXiv preprint 1r218:2112.13838, 2021.
Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference on Machine Learning, pages 9428-9437. PMLR, 2020.
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret. Advances in Neural Information Processing Systems, 2021.
Ahmed Touati and Pascal Vincent. Efficient learning in non-stationary linear Markov decision processes. arXiv preprint arXiv: 2020.
Daniel Vial, Advait Parulekar, Sanjay Shakkottai, and R Srikant. Regret bounds for stochastic shortest path problems with linear function approximation. arXiv preprint arXiv:2105.0159) 2021.
Chen-Yr Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal box approach. In Conference on Learning Theory, pages 4300-4354, PMLR, 2021.
11

---

Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
Zihan Zhang, Xiangyang Ji, and Simon S Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse horizon. Conference On Learning Theory, 2020.
Huozhi Zhou, Jinglin Chen, Lav Varshney, and Ashish Jagmohan. Nonstationary reinforcement learning with linear function approximation. arXiv preprint arX1v:2010.04224,, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] After each main theorem.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Pure theoretical work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "orJZ55mCh2E", "reviewer": "Reviewer_DAsW", "summary": "This paper studies dynamic regret minimization for goal-oriented reinforcement learning modeled by a non-stationary stochastic shortest path problem with changing cost and transition functions. They propose several algorithms, with corresponding upper bounds, and lower bounds for this setting.", "questions": "Can the results be applied to more general settings, for example linear MDP?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem this paper studies is novel and of great significance for RL theory. And the theoretical results and analysis are sound and complete. Overall, this is a good paper for RL theory.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "edBTIdWvw56", "reviewer": "Reviewer_rKHa", "summary": "This paper studies dynamic regret minimization for goal-oriented reinforcement learning modeled by a non-stationary stochastic shortest path problem with changing cost and transition functions.", "questions": "Please see above. ", "limitations": "Please see above. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper extends the results of [Wei et al., 2021], with dynamism in amount of changes of the cost and transition functions. \n\nThe key weakness is that the model difference as compared to [Wei et al., 2021] is not explained, and the novelty as compared to [Wei et al., 2021] is not explained. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RTGcYFyftsV", "reviewer": "Reviewer_Cqin", "summary": "This paper initiates the study of learning stochastic shortest path in the nonstationary tabular setting. Specifically, this paper assumes the cost function and the transition kernel vary with respect to the time. It considers the case where the magnitudes of the total change in the cost and transition functions are bounded. Under such a setting, this paper proves several results. First, a lower bound that depends on the magnitudes of the total change of the cost and transition functions. Then it proposed an algorithm that is nearly optimal. \n", "questions": "I have one high level question: Do you think there is any fundamental difference between using finite-horizon approximation and using infinite-horizon-discounted approximation (e.g. [1] ) to solve SSP? \nIt would be good if the authors can give some thoughts. \n\n[1]: Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret\n", "limitations": "No special concerns.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: As far as I know, this paper is the first to consider the nonstationary SSP problem and gives a regret lower bound and regret upper bound. The main algorithm borrows ideas from some well-known existing RL algorithms, but also faces several unique challenges. Still I think t\n\nQuality: The quality is high. The problem is well-defined, and the mathematics looks solid to me.\n\nClarity: The writing is good. Despite being a very technical paper, the main text is easy to follow. \n\nSignificance: SSP has been a quite important problem in RL in these two years. This paper makes a solid contribution to this area by considering a new problem setting (non-stationary change in cost and transition with bounded magnitude) and gives both a lower and upper bounds. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept