Dynamic Regret of Adversarial Linear Mixture MDPs
Authors: Long-Fei Li
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: dynamic regret
adversarial MDPs
linear mixture MDPs
policy optimization
TL;DR: We study the dynamic regret of adversarial linear mixture MDPs with full-information rewards and the unknown transition kernel.

Abstract: We study reinforcement learning in episodic inhomogeneous MDPs with adversarial full-information rewards and the unknown transition kernel. We consider the linear mixture MDPs whose transition kernel is a linear mixture model and choose the \emph{dynamic regret} as the performance measure. Denote by $d$ the dimension of the feature mapping, $H$ the horizon, $K$ the number of episodes, $P_T$ the non-stationary measure, we propose a novel algorithm that enjoys an $\widetilde{\mathcal{O}}\big(\sqrt{d^2 H^3K} + \sqrt{H^4(K+P_T)(1+P_T)}\big)$ dynamic regret under the condition that $P_T$ is known, which improves previously best-known dynamic regret for adversarial linear mixture MDP and adversarial tabular MDPs. We also establish an $\Omega\big(\sqrt{d^2 H^3 K} + \sqrt{H K (H+P_T)}\big)$ lower bound, indicating our algorithm is \emph{optimal} in $K$ and $P_T$. Furthermore, when the non-stationary measure $P_T$ is unknown, we design an online ensemble algorithm with a meta-base structure, which is proved to achieve an $\widetilde{\mathcal{O}}\big(\sqrt{d^2 H^3K} + \sqrt{H^4(K+P_T)(1+P_T) + H^2 S_T^2}\big)$ dynamic regret and here $S_T$ is the expected switching number of the best base-learner. The result can be optimal under certain regimes.

Dynamic Regret of Adversarial Linear Mixture MDPs
Long-Fei Li, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology, Nanjing University, China School of Artificial Intelligence, Nanjing University, China {lilf, zhaop, zhouzh chouzh)@llmdee @laada..
Abstract
We study reinforcement learning in episodic inhomogeneous MDPs with adver- sarial full-information rewards and the unknown transition kemne.. We consider the linear mixture MDPs whose transition kernel is linear mixture model and choose the dynamic regret as the performance measure. Denote by the dimen- sion of the feature mapping, H the length of each episode, K the number of episodes, Pr the non-stationary measure, we propose a novel algorithm that enjoys an O(V + +V (K - P1 + Pr.)) dynamic regret under the condition that Pr is known, which improves previously best-known dynamic regret for ad- versarial linear mixture MDP and adversarial tabular MDPs. We also establish H K + / (H + Pr)) lower bound, indicating algorithm is optimal in K and Pr. Furthermore, when the non-stationary measure Pr is un- known, we design online ensemble algorithm with meta-base structure, which is proved achieve an H + v HK + P1) + Pr) + H2S dy- namic regret and here Sy is the expected switching number of the best base-learner. The result can be optimal under certain regimes.
K
Introduction
Reinforcement Learning (RL) aims to learn a policy that maximizes the cumulative reward through interacting with the environment, which has achieved tremendous successes in various fields, includ- ing games [1, 2), robotic control [3, 4), and dialogue generation [5, 6). In reinforcement learning, the Markov Decision Process (MDP) [7] is the most widely used model to describe the environment.
Traditional MDPs assume that the reward functions are stochastic and the number of actions and states is small. However, in many real-world applications, the reward functions may be adversarially changing and the state and action spaces are large or even infinite. Previous work studies these two problems separately. To deal with the adversarial reward functions, Even-Dat Dar et al. [8] first consider learning adversarial MDPs with known transition and full-information reward feedback.
They propose the MDP-E algorithm that enjoys Ö(V+TT) regret, where 7 is the mixing time and T is the number of steps. There line of subsequent work studying adversarial MDPs [9, 10, 11, 12, 13, 14, 15, 16), which studies various settings depending on whether the transition kernel is known, and whether the feedback is full-information bandit. To overcome the large state and action space issue, widely used method is linear function approximation, which reparameterizes the value function as a linear function over some feature mapping that maps the state and action to a low-dimensional space. Amongst these work, linear MDPs [17, 18, 19, 20, 21, 22, 23] and linear mixture MDPs [24, 25, 26, 27, 28, 29, 30, 31] are two of the most popular MDP models with linear function approximation. In particular, He et al. [23] and Zhou et al. [31] attain the minimax optimal H( K) regret for linear MDPs and linear mixture MDPs with stochastic rewards respectively.
Recent studies try to combine two lines of work establish the theoretical foundation adversarial MDPs with large state and action space. In particular, Cai et al. [32] study adversarial linear mixture
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

MDPs and propose the OPPO algorithm that enjoys an Ö(vPHHK) regret. He et al. [33] improve the result to O(vd and show it is (nearly) optimal by presenting a matching lower bound. However, these studies choose static regret as the performance measure, defined as the performance difference between the leamnrr' 's policy and that of the best-fixed policy in hindsight, namely,
Regret(K)
max
Σ (SK.)) xell
where V is the value function and II is the set of all stochastic policies. One caveat in (I) is that the best fixed policy may behave poorly in non-stationary environments. To this end, we introduce dynamic regret, which benchmarks the learner's performance with changing policies, defined
K
D-Regret ()
Σ Vi k=1
Σ
VT. (sk,1),
22
where Ti...., T ll compared policies. Define Pr = =k d( T(-1) d( with certain distance
measure d(.,-) .) as the non-stationary measure. A favorable dynamic regret should scale with Pr.
Dynamic regret is more appropriate measure in non-stationary environments, but it is more chal- lenging to optimize such that few studies focus on it in the literature. Zhao et al. [34] investigate the dynamic regret of adversarial tabular MDPs with the known transition kernel and present an algorithm with optimal dynamic regret. Importantly, their algorithm does not require the non-stationarity measure Pr as the algorithmic input ahead of time. For the unknown transition setting, Fei et al. [35] study adversarial tabular MDPs and propose an algorithm with dynamic regret guarantee. Zhong et al. [36] further extend the algorithm of Fei et al. [35] to accommodate non-stationary transition kernels with linear function approximation. Both algorithms of Fei et al. [35] and Zhong et al. [36] require the quantity of Pr as the input. Moreover, their dynamic regret bounds are suboptimal in terms of K and Pr as demonstrated by the lower bound established by our work (see Theorem 4).
This work investigates the dynamic regret of adversarial linear mixture MDPs, with focus on the full-information feedback and the unknown transition. We first propose POWERS-FixShare algorithm when Pr is known, an algorithm combining optimistic policy optimization with a Bernstein bonus and fixed-share mechanism. We show it enjoys an H + + VH*(K+ PT) + Pr)) dynamic regret, where d is the dimension of the feature mapping. H is the length of each episode, K' is the number of episodes, Pr is the non-stationary measure. We also establish dynamic regret lower bound of 2(vd2
V HHKKU (H + Pr)) We stress four remarks regarding our results:
(1) Our result can recover the H(K minimax optimal static regret in He et al. [33].
(2) Our result improves upon the previously best-known O(dH7/4K3/ K3/4 + H2 K2/3 p.,
p, 1/3) dynamic regret for the fixed transition of Zhong et al. [36, Theorem 4.6] in terms of H, K and Pr.
(3) Our result can imply an O(V AK + / + Pr)(1 + Pr.) dynamic regret for ad- versarial tabular MDPs, strictly improving upon the previously best-known O(VH45²AK
112 1f=K2/3pp7 1/3) dynamic regret of Fei et al. [35, Theorem 1], in terms of both K and Pr.
(4) As the lower bound suggests, our result is the first optimal regarding the dependence on d. K and Pr and can be optimal in terms of H under certain regimes (H < d and Pr < d2/H).
Furthermore, we study the case when Pr is unknown and design a novel algorithm equipped with the dynamic regret guarantee by the meta- meta-base two-layer structure. Our algorithm enjoys an σ(V H(K + (K + Pr) + Pr) + H2S)) dynamic regret, where Sy is the expected switching number of the best base-learner. Though ST is a data-dependent quantity, it also reflects the degree of environmental non-stationarity to some extent. Moreover, under specific regimes, the magnitude of ST may be relatively negligible, resulting in our results still being optimal. Indeed, given that ST is a data-dependent quantity, its inclusion in the regret bound is not ideal. Deriving bounds that rely exclusively on problem-dependen dependent quantities, like Pr, remains an open challenge. We discuss the technical difficulty of removing Sy in Section 5 and take this issue for future work.
Finally, we also highlight the main technical challenges and our solutions as follows.
We first show that the dynamic regret depends on the inverse of the minimal probability over the action space of our policies, which can be arbitrarily small. To this end, we propose novel

---

algorithm with the shxed-share mechanism [37]. While this mechanism is proved to enjoy favorable dynamic regret in online convex optimization [38], it suffers an additional term that can be regarded as the weighted sum of the difference between the occupancy measure of the compared policies in online MDPs. To overcome the difficulty, we exploit the multiplicative stability to bound this term, eliminating the need for a restart strategy to handle the environmental non-stationarity as in previous studies [35, 36] and allows us to attain the dynamic regret optimal in terms of K and Pr.
We show the dynamic regret of online MDPs can be written as the weighted average of "multi- armed bandits" problems over all states, where the weight for each state is the unknown and changing probability of being visited by Tf..... "K- For the unknown Pr case, we first show the standard two-layer structure used in non-stationary online learning studies [39, 40, 41] fails to achieve a favorable dynamic regret guarantee, which characterizes the unique difficulty of online MDPs. Then, we present an initial attempt address this issue by a specifically designed two-layer structure. We prove our algorithm enjoys nice dynamic regret guarantees under certain regimes.
Notations. We denote by ((A) the set of probability distributions on a set A and denote the KL- for any p.p' E (A). We define A(A S, H)
divergence by (plp') = E.EA p(a) log p(a)
p(aj
(- 1-)) (- x) E A(A), Vs E S. E [H] for any set S and H E Σạ. Further, for any n, n', TT E A(A] S, H). we define E,, [DRL (T [T'[[="]] E. D DKL (- (t)) [ (+,,))
For any policy pair Th, ThA we define || - - 11 = max.es
- (- ()]l For any
a, b, R with < b, let [x) denote min a), O() omits the logarithmic factors.
2 Related Work
RL with adversarial rewards. There are many studies on learning adversarial MDPs where the reward functions are adversarially chosen, yielding fruitful results that can be categorized into three lines [8, 10, 11, 12, 13, 14, 15, 16]. In particular, the first line of work considers the infinite- -hoiiznn MDPs with uniform mixing assumption. In the known transition and full- hull-informatio setting, the seminal work of Even-Dar et al. [8] proposes MDP-E algorithm that achieves the Ö(Vr3T) regret, where T is the mixing time and T is the number of steps. Another concurrent work of Yu et al. [9] achieves ((T2/3) in the same setting. In the known transition and bandit-feedback setting, Neu et al. [10] propose MDP-EXP3 algorithm that attains ( regret. The second line of work considers the episodic loop-free free MDPs. Neu et al. [11] first study this problem under the known transition setting and propose algorithms that achieve ((V)) and Ō ((VT/a) for full-information and fandbt-feedback respectively, where a is the lower bound of the probability of all states under any policy. Zimin and Neu [12] propose O-REPS algorithm that enjoys Õ(VT) regret both full-information and bandit- feedit--eebbcck setting without any additional assumption. Rosenberg and Mansour [13] and Jin et al. [14] further consider the harder unknown transition and
setting. The last line of work studies the episodic Stochastic Shortest Path (SSP) setting [15, 16]. In this paper, we focus on episodic MDPs with the unknown transition and full-information setting.
RL with linear function approximation. To design RL algorithms in large state and action space scenarios, recent works focus on solving MDPs with linear function approximation. In general. these works can be divided into three lines based on the specific assumption of the underlying MDP. The first line of work considers the low Bellman-rank assumption [42, 43, 44, 45], which assumes the Bellman error matrix has a low-rank factorization. The second line of work is based on the linear MDP assumption [17, 18, 19, 20. 21, 22, 23], where both the transition kernel and reward functions can be parameterized as linear functions of given state-action feature mappings o : S x A + Rd. The last line of work studies the linear mixture MDP [24, 25, 26, 28, 29, 30, 31], where the transition kernel can be parameterized as a linear function of feature mapping Φ S x A x S - Rd but without the linear reward functions assumption. Amongst these works, He et al. [23] and Zhou et al. [31] attain the minimax optimal O(v H3) regret for both episodic linear MDPs and linear mixture MDPs respectively. However, all the above studies consider the stochastic reward setting. In this paper, we study the episodic linear mixture MDP setting but with adversarial reward functions.
Non-stationary RL. Another related line of research is online non-stationary MDPs. In contrast to adversarial MDPs where the reward functions are generated in an adversarial manner, online non-stationary MDPs consider the setting where the reward functions are generated stochastically
3

---

according to some distributions that may vary over time, Jaksch et al. [46] study the piecewise stationary setting where the transitions and rewards are allowed to change certain times and propose UCRL2 with restart technique to deal with the non-stationarity. Later, Ortner et al. [47] consider the generalized setting where the changes are allowed to take place every step. However, the above studies need prior knowledge about the magnitude of non-stationary. To address this issue, Cheung et al. [48] propose the Bandit-over- RL algorithm to remove this requirement. A recent breakthrough by Wei and Luo [49] introduces a black-box method that can convert any algorithm satisfying specific conditions and enjoying optimal static regret in stationary environments into another with optimal dynamic regret in non-stationary environments, without requiring prior knowledge about the degree of non- con-staiionarity However, this approach does not apply to the adversarial setting. Specifically, their reduction requires the base algorithm satisfy certain property enjoyed by typical UCB- -tppe algorithms. When a new instance of the base algorithm surpasses the optimistic estimator, it can be inferred that the environment has changed, prompting a restart of the algorithm to disregard prior information. However, this approach of constructing an optimistic estimator by a UCB-type algorithm can only be applied to stochastic setting. In the adversarial setting, where no model assumptions are made and comparators can be arbitrary, this approach encounters significant difficulties.
Dynamic Regret. Dynamic regret of RL with adversarial rewards is only recently studied in the literature [34, 35, 36]. Zhao et al. [34] investigate the dynamic regret of adversarial tabular MDPs with the known transition kernel and present algorithm with optimal dynamic regret. Importantly, their algorithm does not require the non-stationarity measure Pr as the algorithmic input ahead of time. For the unknown transition setting, Fei et al. [35] study adversarial tabular MDPs and propose an algorithm with dynamic regret guarantees. Zhong et al. [36] further extend the algorithm of Fei et al. [35] to accommodate non-stationary transition kernels with linear function approximation. Both algorithms [35, 36] require the quantity of Py as the input. Moreover, their dynamic regret bounds are suboptimal in K and Pr as shown by the lower bound established in our work. In this work, we first design an optimal algorithm in terms of K and Pr when Pr is known. Further, we develop the first algorithm to handle the unknown Pr issue in adversarial MDPs with unknown transition.
3 Problem Setup
We focus on episodic inhomogeneous MDPs with full-information reward functions and the unknown transition kernel. Denote by M = A, H, (rK.Akk[(K] (e 1 hejHH] } an episodic inhomoge- neous MDP, where S is the state space, A is the action space, K is the number of episodes, H is the horizon, A : S x A + [0. 1] is the reward function, (- -..): S x A x S - [o, 1] is the transition kernel. We assume the rewards are deterministic without loss of generality and extending our results to stochastic rewards is straightforward. Let S = S and A = [.A..
The learner interacts with the MDP through K episodes without knowledge of transition kernel (Thh )<[[)-- In each episode k, the environment chooses the reward function {ra.s) ]E]HH] and decides the initial state 8g,1, where the reward function may be chosen in an adversarial manner and depend on the history of the past (k 1) episodes. Simultancously, the learner decides policy Thk (k hE]M where each Tk. : S + A(A) is a function that maps a state s to a distribution over action space A. In the h stage in episode k. the learner observes current state Sk.h, chooses an action 0g ~ T- sk,K), and transits to the next state $k,++1 (- $k.h, hg.h). Then the learner obtains the reward F.AAA ( (Sk. ak.h) and observes the reward function Tkr as we consider the full-ifformation setting. At stage H + 1. the learner observes the final state $k but does not take any action, and the episode & terminates. Denote by T = K H the total steps throughout K episodes.
special class of MDPs called linear mixture MDPs, a setting initiated by Ayoub et al. [24] and further studied in the subsequent work [32, 31, 33). In this setup, the transition kernel can be parameterized as a linear function of feature mapping à: S x A X S + Rdd The formal definition of linear mixture MDPs is as follows.
Linear Mixture MDPs. In this work, we focus
Definition 1 (Linear Mixture MDPs). An MDP M = (S. A, H, {rk, A h Me(m) (Pe is called an inhomogeneous, episode B-bounded linear mixture MDP, if there exist a known feature
mapping o(s' s,a) S x A x S + He and an unknown vector 0z E Hd with |10]1| < B. vh E [H] such that (i) Pn(s' s,a) = o(s' a, T 0 for all (s, a, s') E S x A S and h E [H), (ii)
[lov(s & IIEres o(s' (s')lla < 1 for any (s) S x A and function V : S - [0.
4

---

Algorithm POWERS-FixShane
Input: step size 7,, exploration parameter and regularization parameter A.
1: Initialize { (To (
E S as uniform distribution, and set ( (Qo,)(::)) (-= as zero function.
2: for k ===1 1.
K do
3: Receive the initial state Sk,1-
4: for h 1, ..... H do
5: For all E [H] E S, updates policy by
T (1) & 16-1M exp (nQR-1,1 TA.A (- (-1 = -1- (1-7)mm.a(-1 7 (-1
6:
Take the action following assd T. s2,A) and transit to the next state 82,++1- Obtain reward (sk,h, a and observe the reward function T'k, -t). end for
7:
8:
9:
Initialize HK.H+1 +1 ) as zero function.
10: for h = H, H 1, 1, do
Set (..)(: -- (tx, + (OR,h ova (s.)) T ov. (1. (0. (0.
12: Set (-) f- Ba --) 10x, (.(
Set the estimated variance VR Vi,h+1 (Sk,h (kch) as (11), bonus Eg,, as in (21).
14:
JR. + / Vmax (H2/d, VEAVEN (SE ax,h) + Bx.
15:
EKTIA SK,, + +og,oovinnts (SK,A, (k,h) @vnntt (8k,ht ak,h)
6RT1A + $R. + TK,i (5k,h) ok,h) Ve,t+1 (sh+1)-
16:
17:
EATLA < Σn.n + @V2,.- (5k,0: (2 ΦVZ (8k ak
DA+LA < DA.A +0v2
(sk h V22 Wihh-1 (sh+1).
0441A - 5-1 k+1 1kt 1
Oxt1n + 5-1 2
19:
20:
end for
21:
end for
Dynamic Regret. For any policy π = | and any (k, h, a) E [K] x [H] x S x A. we define the action-value function QT,,, and value function k,h as
M
QT = E.
The an)) = 8, VV.n(s) E.
Σ
(sW (ax))
The Bellman equation is given by Qh, = TRA + PA E and VV, Bawaut-1 (s) 10 (8, (s)a) with V2, O. For simplicity, for any function
I. we define the operator
V a) = Eg ( (())), [VAV](s, [PA (s,,a) - (ss)),
(3)
As stated in Section 1, dynamic regret is more appropriate measure compared with static regret for the adversarial environments, which is defined in (2) and we rewrite below for clarity:
D- D-Regret(K3) K)
Σ A=1
k. (sk.1)
(sk.1) k,
(4)
where wf...., o any sequence compared policies. define कह = oं to simplify the notation. The non-stationarity measure is defined as Py = Ek
E I.11.ll
Optimal Dynamic Regret with Known Pr
present our proposed algorithm Algorithm Similar to previous studies, the algorithm consists of (i) policy improvement phase, and (ii) policy evaluation phase. We introduce the details below. In Sections 4. we first consider the case when the transition is known to highlight the challenges even under the ideal setting, Then, extend the results to the unknown transition setting in Section 4.2.
5

---

4.1 Policy Improvement Phase
In the policy improvement phase, the algorithm updates TH based on T--1 using the proximal policy optimization (PPO) method [50]. Specifically, at episode k. we define the following linear function:
LA (T- k, (Sk,1) + B
Σ Q 1 1.6 T. (-1 Th 1.
Sh.1
which is the first-order Taylor approximation of V 1,- around πk-1. Then, we update Ta by
arg max TEA(A (,
1 -
Σ
DKL ( SW)I (sn)))
(-
(5)
where 1) > 0 is the stepsize and the KL-divergence encourages Ty to be close to #;-1 so that ( is good approximation of V 1 (5k.1). The update rule in (5) takes the following closed form,
(. 8) x T
exp (17 Q )). wh E [H] e S.
(6)
We show the update rule in (6) ensures the following guarantee and the proof is Appendix C.1. Lemma 1. The update rule in (6) ensures the following dynamic regret guarantee:
D-Regret S 2
KH
Σ 17
1
Bag
[DKL (p)) DKL (T [[TT))))))
(7)
Note that the expectation in the last term in (7) is taken over Te which may change episode k. For static regret, i.c. कं = = - = n², we can control this term by a standard telescoping argument, which is not viable for dynamic regret analysis. Fei et al. [35] propose restart strategy to handle this term. Specifically, they restart the algorithm every certain number of steps and decompose the above expectation into Erg [1] T [1] Exg - [1] where kn k is the episode in which
restart takes place most recently before episode k. For the first expectation Erg, [.]. they apply a customized telescoping argument to each period the expectation is taken over the fixed policy. The second expectation Exg-xc, [-] involves the difference Th. Th and can be bounded by Pr. However, as we will show in Theorem 4, their regret bound is suboptimal in terms of K and Pr.
We introduce approach below. Let first consider taking expectations over any fixed pol- icy и. Denote by the minimal probability over any action at any state for policies TI...., TK. i... minke[k] (a s), Va A, s E S, the last term in (7) can be upper bounded by EK E, [KKL. (+)) DEL (Tg [[)+ < Hog A + Pr log 1. showing that we need to control the minimal value of 8 to obtain favorable dynamic regret bound. To this end, we slightly modify the update rule in (6) and add a uniform distribution π T"(- s) 1. vss E S. That is, the policy =" chooses each action with equal probability at any state. Thus, the update rule in (6) is modified as:
T 8) x Th T.-1,A 1 s) exp(n QF (s,-)), )), (
- s) = (1-7)11mmmm T s) + (- |s) (8)
for any s S.h E [H], where 2 0 is the exploration parameter. This update is called the fixed-share mechanism in online learning literature [37]. While the fixed-share mechanism is standard to obtain dynamic regret in modern online learning [38], several important new challenges arise in online MDPs due to taking expectations over the policy sequence changing policies of...., - In partieular, prove that performing (8) ensures the following dynamic regret.
Lemma 2. Set क as uniform distribution on A for any state E S. The update rule in (8) ensures
nKH3
1
A + KH log
1 1 1
D-Regret(K)) <
+
Pr Pr
2
7
7
Th (h)) log 1 (a 9p)) s.))
]
Σ
Th Th-
8x)
log
(9)
T (a sh)
LOEAA
The proof can be found in Appendix C.2. In the dynamic regret analysis in online learning, the last term in (9) is usually canceled out through telescoping since we do not need to take expectations [38].

---

However, this is not the case in online MDPs. Since the expectation is taken over the policy sequence of changing policies .i...., kk. this term cannot be canceled out, which requires a more refined analysis. To address this issue, we decompose one step of the expectation in (9) as follows.
)
Σ LaEA
Th - log k
- Eng Σ TR log
Tk+1A
1
Bu 12-1
22-1
Σ LacA
- I. log
With this decomposition, the first term can be canceled out through telescoping, yet it remains to control the second term - the weighted difference between the state-action occupancy measures of policy q and - with weight 1,, it, we need (i) ensure the weight is upper bounded by some universal constant, and (ii) bound the unweighted difference between the state-action occupancy measures, which are new challenges that arose in online MDPs compared with standard online learning.
(a s/,) log A 5%) for state-action (5%, a). To control
For the first challenge, note that the weight - (a sn) log T (a sh.) can be large or even infinite since " is the policy before uniform exploration and T (a 8%) can be arbitrarily small. Fortunately, T A is obtained by one-step descent from Tk-1,h- which is the policy after uniform exploration and can be lower bounded. We provide the following multiplicative stability lemma for the one-step update, which shows Tk, is not far from TK-1,4 and thus is also lower bounded.
Lemma 3 (Multiplicative Stability). For any distributions p E A(A) with p(a) > 0. for all a E A, and any function Q : S x A + 00, H). it holds for p' E (AA) with pl (a) x p(a) exp(1 Q(s,)) and 1) S I/H that pf (a) [p(a)/4, 4p(a)), for all A.
For the second challenge, we show the unweighted difference between the state-action occupancy measures can be bounded by the path length of policies. In particular, we have the following lemma. Lemma 4, For any policy sequence of,
T. it holds that
K
H Σ
H
Σ (Erg ((Eng
1EAg .)
1(sh) 91 kk
T6-1,111,00 = HPr.
Remark 1. We note that a similar argument is also used in Fei et al. [35, Appendix B.2.2]. How- ever, they prove this lemma by imposing additional smooth visitation measures assumption [35, Assumption IJ. which is not required in our analysis.
The proof' for Lemmas 3 and 4 can be found in Appendices C.3 and C.4 respectively. Combining Lemmas 2, and 4, we can prove the guarantee for update rule (8). The proof in Appendix C.5.
Theorem 1. Set Tı uniform distribution on for any state E S. The update rule in (8) ensures
D-Regret(K)) S MKH3 1
4A
Pr + KH log 1
log + (1 + H) log
2
7
Considering the static regret where γं = = T = T., we can recover the O( O(VH*K H*K that is, without uniform exploration. However, when 7 = O, the dynamic regret not bounded as there lacks upper bound for - log showing the necessity of the fixed-share mechanism.
Remark 2.
log A) static regret in Cai et al. [32] under the stationary scenario by setting 7 0.
4.2 Policy Evaluation Phase
Sections 4.1 focus the simplified scenario where the transition is known. In this subsection, further consider the unknown transition setting such that it is necessary to evaluate the policy based on the (k-1) 1) historical trajectories. To see how the model estimation error enters the dynamic regret, we decompose the dynamic regret in the following lemma.
Lemma 5 (Fei et al. [35, Lemma 1J). Define the model prediction error Lk Tke + VK,
QR the dynamic regret D-Regret(KK) = EK V - Σ VE,1 (8K,1) can be written as
Σ [1Qe, Th 8n) Te,a sw)a + MM Σ (Eng [u (sh, an)] ( ak,))
R.A
where МK.H- = E EIL Mx, is martingale that satisfies Ma S 4H, Vk E [b]] E [H].
With slight abuse of notations, omit (-Isn) sn) for simplicity.
7

---

Remark 3. Lemma 5 is independent of the structure of MDPs. The first term in Lemma 5 is the dynamic regret over the estimated action-value function QK. which can be upper bounded by Theorem 5. The second term is martingale, which can be bounded by Azuma-Hoeffdiin inequality. The third term the model estimation error, which the main focus of this section. Note the model prediction eтrоr '2, b (&p; (s)) can be large for the state-action pairs that are less visited or even unseen. The general approach is incorporating the bonus function into the estimated Q-function such that (sh, as) O for all E S,a E A (i.e., lEng (s,, as)] I 0) and we only need to control -kk, ( dg which is the model estimation error at the visited state-action pair (Sk,, (k.A).
When applied to linear mixture MDPs, the key idea learning the unknown parameter 0g of the linear mixture MDP and using the learned parameter 0R.s to build an optimistic estimator Qu. (., such that the model prediction error is non-positive, which is more less standard. From the definition of linear mixture MDP, for the learned value function V we have [PA, V&, 1 a) Ex d(s' a a)) 07)). Inspired by recent advances in policy evaluation for linear
aaVa..VV VK (s'), ) mixture MDPs [31], we adopt the weighted ridge regression to estimate the parameter f% that is, we
construct the estimator Ou. by solving the following weighted ridge regression problem:
R = arg min BER
j= j=1 [(dv),041 (5,.). B) V3 (s),4+1)}² 10j, + 21101
Here, J3, is the upper confidence bound of the variance [VA [VaKgn+ll(ss,n a3,1), and we set as O V max max(112/4 /d, VV,,nV (SK,A, (R.A) + Eu,a where (V V (s., is scalar-valued empirical estimate for the variance of the value function Vi,++1 under the tran- sition probability (- Sk, Ox), and Ek,A is the bonus term guarantee that the true variance [Va, Ve,N+1 as.h) is upper bounded by [V Vi,.+11(5s..... ok,,)) + Eg,, with high probability. Then, the confidence set Cr,b is constructed as follows:
Ex, {0 11 02l) S 3x).
(10)
where Ei,, is a covariance matrix based on the observed data, and 3r is a radius of the confidence set. Given ČR,.. we estimate the Q-function following the principle of "optimism in the face of
uncertainty" [51] and set it as QR, [r,,,((s-)) + max (0) Φv. ()oo H-++1-
remains to estimate the variance [V.. ak.K). By the definition of linear mixture MDPs, we have [Va VK, axlx) = (ovg (SK, ax,n), 0g) - KóvE (Sk,bs o), 0;) Therefore, we estimate [VA.A VinN+1] (Sk,kr ak,h) by the expression below
[ddvenn (SK,N, 0x. 0.H²) [[dvia (8k, 0n,))) 0w [o.H]'
(11)
where 0e.n = arg mingeR Dov sh (3j,n. azn), 0) - 2 ( + Al10 The details
summarized in Lines 10-20 of Algorithm I and we provide the following guarantee.
Theorem 2. Set the parameters as Lemma 8, with probability least - ō, we have
K
K H
Σ 1=1
Vi.1 (sf) - Viri (st) MK.H- - ΣΣ
(x...)..x.))) ax. 2 (V + d2H*K
k=1k=1
The proof is given in Appendix C.6. Theorem 2 shows the model estimation error can be bounded. Combining Theorems 1, 2 and Lemma 5, we present the dynamic regret bound in the next section.
4.3 Regret Guarantee: Upper and Lower Bounds
In this section, we provide the regret bound for our algorithm and present a lower bound of the dynamic regret for any algorithm for adversarial linear mixture MDPs with the unknown transition.
Theorem 3. Set n= min (Pr + log A)/K, 1)/K,1) 1)/H, = 1/(KH) and Br as in Lemma 8, then with probability at least 1
holds
D-Regret K) < ō (VaHA ( K HH HHA(K- + P+)(1 + (Pr)
(12)
where Pr EK_ EI 12111111.00 is the path length of the compared policies.
8

---

Remark 4 (recovering static regret), Since static regret is a special case with Th = T², vk, our result can recover the optimal O(Vd"133) static regret when I/ S d, same as the result in He et al. [33]. Remark 5 (improving linear mixture case). Our result improves upon the previously best-known O(dH + H² K2/33pp Pr" (/8) dynamic regret for adversarial linear mixture MDPs of Zhong et al. [36, Theorem 4.6] in terms of the dependence on H, K and Pr.
Remark 6 (improving tabular case). For the adversarial tabular MDPs, our result implies an O(v A(K + H2 V(K + Pr)(1 + Pr)) dynamic regret. This improves upon the best-known O(VH'S*AK + H2K2//p 1/3) result of Fei et al. [35, Theorem IJ. The details are in Appendix B.
We finally establish the lower bound this problem. The proof can be found in Appendix C.8. Theorem Suppose B 2 2, 2 4, H 3, K 2 (d- 1 H/, for any algorithm and any constant E [0, 2KH), there exists an episodic B-bounded adversarial linear mixture MDP and compared policies oi, "i...., Tk such that Pr S T, and D D-Regret(K) 2 HVV@H3K + VHK(H +T))
When S d, the upper bound is Ö(V@H*K + ++) PT)). Combining with Theorem 4, we discuss the optimality of our result. We consider the following three regimes.
H3)) and the lower bound is Ō(Vd2H²)), hence our result is optimal in terms of d, H and K.
Small Pr: when 0 - Pr < HH/H, the upper bound (12) be simplified
Moderate Pr: when d 9/H HHH S Pr < K, the upper bound (12) can be simplified as (VV +
VH*K(1+ +1++144 Pr)), and it is minimax optimal in d, K and Pr but looses factor of H
Large Py: when Pr 2 K, any algorithm suffers at most ((HK) dynamic regret, while the lower bound is ((KVH] H). So our result is minimax optimal in K but looses factor of VH.
5 Towards Optimal Dynamic Regret with Unknown Pr
This section further considers the case when the non-stationarity measure Pr is unknown. By Theorem I, we need to tune the step size 7 optimally to balance the number of episodes K and Pr to achieve a favorable dynamic regret. To address the difficulty of not knowing Pr ahead of time, develop online ensemble method to handle this uncertainty, in which two-layer meta-base structure is maintained. While the methodology can be standard in recent non-stationary online learning [52, 39, 40, 41], new challenges arise in online MDPs. We introduce the details below.
By the performance difference lemma in Cai et al. [32, Lemma 3.2] (as restate in Lemma 13), we can rewrite the dynamic regret
K
K
H
Σ R=1
1
k
E
(0% :), Th (.Iss) sN) T..a (s)))))))) Σ
R=1
where the expectation is taken over the randomness of the state trajectory sampled according to TÝ- The dynamic regret of online MDPs can be written as the weighted average of some -mueti-armed bandits" problems over all states, where the weight for each state is the unknown and changing probability of being visited by .f..... T As the optimal step size depends on the unknown non- stationarity measure Pr as shown in Section 4, natural idea is to the two-layer structure to learn the optimal step size as recent online convex optimization literature [52, 39, 40, 41].
The general idea is constructing a step size pool H = {m.... 7//] } to discretize the value range of the optimal step size; and then maintaining multiple base-learners B,, . ... NN. each of which works with specific step size 7/: Finally, a meta-algorithm is used to track the best base-learner and yield the final policy. Then, the dynamic regret can be decomposed as follows (omit (-1 sn) for simplicity):
K
11
K
Σ ERE
<
Q TE - Then)
ENg
Σ
{
Shi The Tu.
A=1
Since the above decomposition holds for any index E [N]. we can always choose the base-learner with optimal step size analyze and the first term is easy control. The challenge is control the

---

second term, which is the regret of the meta- meta-algorithm. Different from the standard "Prediction with Expert Advice" problem, it involves an additional expectation over the randomness of states sampled according to z.- This poses grand challenge compared to conventional online convex optimization where the expectation is not required. Although we can bound this term by Pr again, optimal tuning of the meta-algorithm is hindered as Pr is unknown. Consequently, we opt to upper bound it by the worst-case dynamic regret [53], that is, benchmarking the performance with the best choice of each round, which in turn introduces the dependence on the switching number of the best base-learner.
We introduce our approach as follows. We maintain multiple Base-learners, each of which works with specific step size 7/. All base-learner, update their policies according to the same action-value function Qk 1.-1,,((sp of the combined policy - that is, the base-leamer B; updates policy by
& (-1 |s) x =- |) exp(n=Qx-11(s -)), Ti. (- ()) = (1 (1-7)=k.4 (- (-1s) + y-
(-1 (s),, (13)
Then, the meta-algorithm chooses the base-learner by measuring the quality of each base-learner. In our approach, we choose the best base-learner at the last episode, that is,
- T. s) =kA (- 8) with (s) arg [ (Qu- -), m (-1(,)(()))))))))))))))))))))( (s))))
(14)
The details are summarized in Algorithm 2 of Appendix A and the guarantee is as follows.
Theorem 5. Set 7 = I/(Kf), step size pool H = {m= = (2' ( (log A)/K i [N]] with
N = 1 Llog( Tog )- Algorithm 2 ensures
D-Regret(K) s 66 dH'K + PHOK+ + HHA(K + PT) PT) + H3S9)
where Pf = Ek= Ex 1 Th -,lli,,,,, is the path length of the compared policies, ST
ΣK= Ex=1 Exg 1 1 (vn) # f (, is the expected switching number of best buse-learner.
Combining it with Theorem 3, we discuss the optimality of our result. We consider two regimes.
the term ST can be subsumed by other terms. In this case, the upper bound in Theorem 5 is entirely the same as that in Theorem 3. This implies we maintain the same guarantees without Pr as algorithmic input.
Small Sy: when ST S max HK,, HI Pr)
Large Sy: when Sr > max (dv HK, H V(K + Pr)(11 + Pr)}, our result looses a factor of H.T compared with the result in Theorem for the known Pr setting.
By the above discussion, our result can be optimal in terms of K and Pr under certain regimes when Pr is unknown. In comparison, the regret bounds achieved via the restart mechanism [35, 36] remain sub-optimal across all regimes even Pr is known. Note that we introduce the notation ST in the regret analysis, which also reflects the degree of environmental non-stationarity to some extent. Consider the following two examples: (i) in the stationary environment, Sr could be relatively small as the best base-learner would seldom change, and (ii) in the siectwise-ttationary environment, Sr would align with the frequency of environmental changes. Indeed, given that ST is data-dependent quantity, its inclusion in the regret analysis is not ideal. Deriving bounds that rely exclusively on problem-dependent quantities, like Pr, remains a significant open challenge.
Conclusion and Future Work
In this work, we study the dynamic regret of adversarial linear mixture MDPs with the unknown transition. For the case when Pr is known, we propose a novel policy optimization algorithm that incorporates a ffxed--har mechanism without the need for restarts. We show it enjoys dynamic regret of (Vv ( K + /H P1) Pr) ) strictly improving the previously best-known result of Zhong et al. [36] for the same setting and Fei et al. [35] when specialized to tabular MDPs. We also establish an D0 + / K(H + Pr)) lower bound, indicating that our algorithm optimal regarding d, K and Pr and can be optimal in terms of Ii under certain regimes. Moreover, we explore the more complex scenario where Py is unknown. We show this setting presents unique challenges that distinguish online MDPs from conventional online convex optimization. We introduce a novel two-layer algorithm and show its dynamic regret guarantee is attractive under certain regimes.
There are several important future works to investigate. First, how to remove the dependence on the switching number ST is an important open question. Moreover, we focus on the full-information feedback in this work, it remains an open problem to extend the results to the bandit feedback.
10

---

Acknowledgements
This research was supported by National Key R&D Program of China (2022DD01 14800) and NSFC (62206125, 61921006). Peng Zhao was supported in part by the Xiaomi Foundation.
References
[1] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wienstra, and Martin A. Riedmiller. Playing Atari with deep reinforcement learning. ArXiv preprint, 1312.5609 2013.
[2] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mas- tering the game of Go with deep neural networks and search. Nature, pages 484-489, 2016.
[3] John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1889-1897, 2015.
[4] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In Proceedings of the 33nd International Conference on Muchine Learning (ICML), pages 1329-1338, 2016.
[5] Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep reinforcement learning for dialogue generation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1192-1200 2016.
[6] William Yang Wang, Jiwei Li, and Xiaodong He. Deep reinforcement learning for NLP. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), pages 19-21, 2018.
[7] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
[8] Eyal Even-Dar, Sham. M. Kakade, and Yishay Mansour. Online Markov decision processes. Mathematics of Operations Research, pages 726-736, 2009.
[9] Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, pages 737-757, 2009.
[10] Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online Markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems 24 (NIPS), pages 1804-1812, 2010.
[11] Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest- path problem. Proceedings of 23rd Conference on Learning Theory (COLT), pages 231-243, 2010.
[12] Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26 (NIPS), pages 1583-1591, 2013.
[13] Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference Machine Learning (ICML), pages 5478-5486, 2019.
[14] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 4860-4869, 2020.
11

---

[15] Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI). pages 2936-2942, 2021.
[16] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. Proceedings of the 34th Conference on Learning Theory (COLT), pages 1 1180-1215, 2021.
[17] Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 6995-7004, 2019.
[18] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings the Theory (COLT), pages 2137-2143, 2020.
the 33rd Conference on Learning
[19] Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is good representation sufficient for sample efficient reinforcement Iearning? Proceedings of the 8th International Conference Learning Representations (ICLR), 2020.
[20] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1954-1964, 2020.
[21] Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
[22] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In Proceedings of the 38th International Conference Machine Learning (ICML), pages 4171-4180, 2021.
[23] Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforce- ment learning for linear Markov decision processes. ArXiv preprint, 2212.06132, 2022.
[24] Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 463-474, 2020.
[25] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In Proceedings of the 23th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2010-2020. 2020.
[26] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 10746-10756, 2020.
[27] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 22793-12802 2021
[28] Zihan Zhang, Jiaqi Yang. Xiangyang Ji, and Simon S. Du. Improved variance-aware confidence sets for linear bandits and linear mixture MDP. In Advances Neural Information Processing Systems 34 (NeurIPS), pages 4342-4355, 2021.
[29] Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture MDPs. ArXiv preprint, 2205. 1507, 2022.
[30] Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite-horizon average-reward MDPs with linear function approximation. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3883-3913, 2022.
12

---

[31] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Proceedings of the 34th Conference on Learning Theory (COL.T), pages
2021.
[32] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang, Provably efficient exploration in policy optimization. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 1283-1294, 2020.
[33] Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture MDPs. In Proceedings of the 25th International Conference on Artificial Intelligence and Statisties (AISTATS), pages 2255942800, 2022.
[34] Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online Markov decision processes. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26865, 2022.
[35] Yingjie Fei, Zhuoran Yang. Zhaoran Wang, and Qiaomin Xie. Dynamic regret of policy optimization in non-stationary environments. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 6743-6754, 2020.
[36] Han Zhong, Zhuoran Yang, Zhaoran Wang, and Csaba Szepesvári. Optimistic policy opti- mization is provably efficient in non-stationary MDPs. ArXiv preprint, arXiv:21 10.08984, 2021.
[37] Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2):
151-178, 1998.
[38] Nicolò Cesa-Bianche Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25 (NIPS), pages 989-997, 2012.
[39] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12510-12520, 2020.
[40] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 359-409, 2021.
[41] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. ArXiv preprint, 21 12.44668, 2021.
[42] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1704-1713, 2017.
[43] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model- free approaches. Proceedings of the 32nd Conference on Learning Theory (COLT), pages 2019.
[44] Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1665-1674, 2019.
[45] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 13406-133 13418, 2021.
[46] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, pages 1563-1600, 2010.
[47] Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 81-90, 2019.
13

---

[48] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non- stationary Markov decision processes: The blessing of (more) optimism. Proceedings of the 37th International Conference on Machine Learning (ICML), pages 1843-1854, 2020.
[49] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge:
An optimal black-box approach. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 4300-4354, 2021.
[50] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv preprint, 1707.06347, 2017.
[51] Yasin Abbasi-Yadle Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NIPS), pages 2320, 2011.
[52] Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1340, 2018.
[53] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Conference Learning for Dynamics and Control (L4DC), pages 48-59, 2021.
[54] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Proceedings of the 34th Conference On Learning Theory (COLT), pages 1216-1255 2021.
[55] Chi Jin, Zeyuan Allen-Zhn Zhu, Sébastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 4868- 4878, 2018.
14

---

A Algorithm with Unknown PT
In this part, we present the POWERS-FixShare Pr is unknown. The algorithm is based on the POWERS-FixShars algorithm and we further employ an online ensemble structure to eliminate the algorithmic dependence on Pr. Line 5, each base-learner updates her policy with specific step size y) and the meta-learner selects the best policy among the base-learners Line 6. In the policy evaluation phase (Line 21), we use the same estimator in Algorithm 1 to estimate the parameter 0% and construct the confidence set.
algorithm in Algorithm 2 for the case when
Algorithm 2
Input: step size pool H. exploration parameter "y and regularization parameter X. 1: Initialize ( s) h=1+ Vi E [ E & as uniform distribution on A, (Po. Vs E as uniform distribution on N and set (Qo,a(s))]E as zero function. K do
2: for == 1,
3: Receive the initial state 9g,1-
4: for h = 1. 1.2, .... H do
5: For all [H]. s E S, each base-learner B,, Vi [N] updates policy by
"KA (11s)
x ক 1 exp (n.Qx-1nh )) ( 8) = (1- 7)m (- 8) + 7-" (-1s).
5 (- with i (s) = arg [ (Qx-1,1 (.
6: Set T = *
7:
Take the action following ARAA T..A(- Sk.A) and transit to the next state Sk,++1-
8: Obtain reward T (SK,A, a),A) and observe the reward function (.).
9:
end for
Initialize +I. (.) as zero function.
11: for h = H. 1, ... 1 do
12:
Set (x, +- (:)) + (OK,A, ov (c)))) Ball ov (1. (c.))l2) po.1 -+
13:
Set (.) +- -EENTeN 1-) A ))]
14:
Set the estimated variance VV Ve,441 (SK,N, ( as in (11), bonus Ex, in (21).
V Mmx (H2/d, Ve,+4 (Sk,, an.h) + F
ORA
16:
EETLA < EN, + Dv, (SK, ak Oventt (8k,h, ak.h)
17:
BRT1A + 6N.h + &v (sk ak Ve,t+1 (sh+i).
18:
ΣETLA < Σn,n + VVz,,-, (8k,h ak.h) ΦVR (ok,hs ak.t)
19:
DEHLA bA. + ΦVz (5k hk V/2 Vi,h- (sh
04+1A 5-1 k+1n bk+1, bk O4+1h 5-1 2 b
20:
21: end for
22:
end for
B Recovering Tabular Case
In this part, show the result of our algorithm when specialized to the tabular case. Note in the linear case, we adopt the weighted ridge regression to estimate the parameter 0j that is, we construct the estimator 0k. by solving the following weighted ridge regression problem:
0 = arg min
E [1v5A44 (Gj.h,5..)) 0) Vj (35, /0,, 21101
PER"
In the tabular case, we simply set Jjh 1, and compute @V by taking the sample mean of (Ve.4 ($I,41))))( That is, set it as
OV (85,h, a2.n)) ) = Σ
Na(s),he + Vy.n-1(s',,
s'eS
15

---

of each (s, a), where N₁ counts the number of times each tuple (s, a, s) or (s,a) has been visited up to episode k. Then, construct the estimator dR, by solving the linear regression problem:
k = arg min K (g,)), 0) - VaN+1 (s),++1)]² 2l1l1k
BER
Then, the confidence set Cr. is constructed as follows:
ČA, {0 | 1 02,N) - B).
The remaining part of the algorithm is the same the linear case. The following theorem shows the result of our algorithm the tabular case.
Theorem 6. Set y H)( step size pool H. = {n: - H2 (log A)/K i [N] with N 2 log( log A and B / log(dK with probability at least 1 5, it holds
D-Regret(K)) < 36 Ö(VHHSSAK VH*(K P1) (r)))
where Pr = -E E I Th T2-1.ol1, is the path length of the compared policy sequence.
Proof. By Lemma 5, we decompose the dynamic regret as follows.
D-Regret S
Eag [QQK, )) x 8n) T. sn)) + MR.H
km
H
(Engluch (sc an)
1R (sk,h, ax.)))
Note that the policy evaluation phase is the same as the one in Fei al. [35, Algorithm 3], by the estimator bound in Fei et al. [35, Lemmas 7 and 9], we have
K
H
Bng (1R an) 5..
(Sk, S V
Armn 1 Am1
#= A=
(15)
The remaining proof is the same as the proof of Theorem in Appendix C.7.
C
Proofs
In this section, we provide the proof of the results in this paper.
C.1 Proof of Lemma
Proof. By the definition of dynamic regret, we have
D-Regret(K))
K
K
V
(sx.1)
Σ
(sk.1)
k=1
ΣΣ
Bing (QT (Shr )) T [h) Te,a sz))) si sk.1
1=11
HKH3
K
H
Bng DKt. (TR.a (. (T) (s))) DKI. (TR. ( |[ |ss))
where the equality holds by the performance difference lemma in Lemma 13 and the inequality holds by the one-step descent guarantee in Lemma 14. This finishes the proof.
16

---

C.2 Proof of Lemma
Proof. Note the update rule is
(i T--1,A (-1 8) exp(1 QK- 16-1, (8, }), Tx,((-1)) (1 ( --x"( (11
By Lemma 14, for any 8h S,h E [H] k E [K], we have
QK ") 1 (11))) T (-1 sw))
8h)
1112
DKL. (Thn m (b)) - DKT. ( 8n) (1) a bn))
2
Σ
Ta sp) log a 8h) (a sn) log k+1, (a sh)
(16)
2
aEA
where the equality holds by the definition KL divergence. We decompose the last term as follows:
Σ
T [a]
sh) log
( 8h) log
T sh)
T 111n sn)
aEA
= Σ
(a ( log
Th in 8h) log Ta.n sn)
(17)
k (a sn)
atA
1
1 8n) log
Tk 8h) Ta sn) log
Tk+1 (a sn)
acd
For the first term, we have
Σ
(a sn) log
Ta (s) - a #8-In(alsn)oen (in(alss)
aEA
Σ aed
(Tkn(alsn)
(n) 1 ((1as)))))))))))))())) sh)) log Th (a 8h))
1
Th 8h) + T (n) log TB, (a) 18h)
By the update rule, we have < 1/Tx, sp) S A/y and Then sn)/Tenn 8n) S 1/(1 - 7). Therefore, we have
Ta 8N)
(Thilaa sh) (h)) aEA
Σ
1 (s)))) log T 8h)
2a sn) log
TE, 8h)
sh)ll ( log A log I-7
S || s/h)
(18)
7
Then, the dynamic regret bounded as follows:
D-Rogret(K)
K
K Σ (8k,))
(BL.1)
1=1
1=1
Eng (0 (sn, :), Thin (s) TR.al (85)) 81 sx.1
k= k=
H
H
1
Eng =E (n)) log Te.n(a (8h)
Thin sh) log
2
"1
ma sn)
k= A=1 nEA
H
"
[IT - |sh)l log A + --lg
Bing
2
7
1-
k= 1=1
H
1
EN
Th-1n(a sn) log Tken (a sn)
Thin sh) log
* 8n)
11=1
17

---

nKH1
1
+
Pr log
+ KH log
2
1-71
K
H
1+in (a sh) ]
E
8b) log
T 81) log
*kkn (a 8h)
k=
h=
LaEA
where the first inequality holds by (16), the second inequality is due to (17) and (18), and the last inequality holds by the definition of Pr = -E
Th - It ends the proof.
C.3 Proof of Lemma 3
Proof. Lemma 3 is a simplified version of Chen al. [54, Lemma 17] and we prove it in our notations below for self-containedness. It is easy to verify that the update rule p' (a) oc p(a) exp(7 Q(s, a)) equivalent to the update
p' = arg max n/p Q(8, + DxI,(y'lp)) (p)).))
D'EA(A)
Thus, by the KKT condition, we have for some À and p(a) 2 0. such that
p'(a) Q(s log p(a) + A + u(a) = O, and u(a)p'(a) = V, A.
The above equations give the closed-fore solution p'(a) = p(p))pp(((((((ss (ooopp(((((ss))))) + p(a))) First, we prove that for all a E AA we have p(a) = O. Indeed, when uu(a) & 0. by (1a)p' (a) 0, we have pa(a) p(a) exp(n(Q(s,a)) A + ((a))) = which contradicts with p(a) O.
Then, we now separately discuss two cases.
Case 1: min.ea # m Q(s a). In this case, we first show that minag - Q((s a) < S maxaeA -Q(s, a). We prove by contradiction: If X 2 max.e -Q(s, a). then we have
Er'(a) Σ p(a) exp(n(((sss) rEA
u(a))) 2 Σ p(a) 1
aEAA
aEA
contradicting with p' E A(A). A similar argument holds for the case X minaca(-Q(s,,))) Thus, we have E (min.cx(-Q(ss) a)), max.ea( (-((s,, [))] Then, we have [Q(s, a) + u(a)] < m ((s min.e ((s,a) a) < H. By the condition on n/H 1, we have p' (a) [exp( (exp(- (oo(-1)p(a), (xp())( e (1/(4(())) 4p(a)).
Case 2: millaeA Q(s, a) m Q(s a). In this case, it is clear that À -Q(s, must hold for all a E AA to make p and p' both discussions. Thus p'(a) = p(a) for all a E A.
Combining the above two cases finishes the proof.
C.4 Proof of Lemma
To prove Lemma 4, we first introduce the following two lemmas. Denote by P. (s' s)
EaEA (s' s, (a s) the transition kernel of the MDP in step h under policy gy and re- call that ||TT ||==='111.0 = max.es||x(( s) 7'(- s)]l. The first lemma shows the difference between the state distribution of two policies can be bounded by the path length of the policies.
Lemma 6 (Zhao et al. [34, Lemma 7)). For any state distribution d policy pair a and n', and transition kernel P., we have
|PPTA (1,8) - dP (,+))) S || Thll Vh E {H).
Proof. Consider the case when d is delta function The difference in the next distributions is
| (s,s) P (,,s)la
ΣV
Σ
[P(s' (T) s) ( s))]
S'E
Σ
Σ
P(s a)))) (a s)]1
s'ES aEA
18

---

Σ
T(a
s)
x x'
[|] S || T/111,000
REAA
Linearity of expectation leads to the result for arbitrary distributions. This finishes the proof.
The second lemma shows the difference between the state distribution of the policy starting from the different initial distributions can be bounded by the difference between the initial distributions.
Lemma 7 (Zhao et al. [34, Lemma 8)). For any two initial distributions and d', transition kernel F and policy n, we have
-d'P 11 S l|d of 11, 4h ( d
Proof. Note the relationship that d(s') = E.Es (s)) 5,8' we have
d'PAA
11,
Σ Σ d(s) (5'( 1 (ss) [s)
((s)PTT d'())) [s]
(d(s) d'(s) PTt (s' (s)
Σ Id(s) d'(s) Σ P (s' (8)
Σ Id(s) d'()) = |d Il
This finishes the proof.
Now, we are ready to prove Lemma 4.
Proof of Lemma 4. For any policy and n' and any initial state $1, denote by da the distribution of the MDP in step h under policy wa and d', the distribution of the MDP in step h under policy nh. that (s)) E. [1 (st) 181] and d', (sh) (1))) 81]. We have
[d d2l1, ||d PT d'- PPM ||2
|| 1 dh-11p 1. || + 11oh- Iptn - -
dn d/ 111 + [T oí 1,00
n4 1,00
(E[M]
where the second inequality holds by Lemmas 6 and 7 and the last inequality holds by a recursive calculation. Thus, have
K
H Σ
H
Σ
Eug - Exg
1(sn) 81 8k.1
16-1,111,00 HHr.
km h= t=1
This finishes the proof.
C.5 Proof of Theorem
Proof. By Lemma 2, we have
D-Regret(K) HKH
4A
1
Pr log
+ K Hl log
(19)
1-
17
Eng
Σ
1
Th
sh) log
1
Th (a shh) log
Th (a 8n)
T (a sn)
LaEA
19

---

Then, the last term can be bounded as follows:
1
E
Th 1 1888))0 log
Ti,a(a 8n) 8n) log I (a sb))
*k (a 8b)
k=1
h=
LaEA
K
H
B
Σ LEEA
Th 1, 88) log
B Σ
a on) log
1
Tk (a sh))
Tkt1k (a 8n))
k=1 h=1
LaEd
K
Bag
Σ
Th- 1 log log
kk (a shh)
k= 1=1
LaEd
K
H
< E
Σ
(a (a) I 8n) log
Ii (a 8t,]
+
E
x
Σ
1 - (8) log k (a sh))
LaE
k= h=1
Lad
H
4A
S H log A + log
- [1(sh)
81 88,1
1=1
4A
< H log A log
HPT,
(20)
where the second inequality holds by the telescoping sum and the third inequality holds because
Ti, 1 is the uniform distribution and T (a 8) 2 IΛ by the multiplicative stability lemma in Lemma 3 and the last inequality holds by Lemma 4.
Combining (19) and (20), have
1
4A H Hog A+ (1 H) log Pr + KH log
1
D-Regret K) <
2
+
17
y
1 1-
which finishes the proof.
C.6 Proof of Theorem 2
To prove Theorem 2, we first introduce the following key lemma omitted in the main paper due to the space limit, which shows the guarantec of the confidence set.
Lemma (Zhou et [31, Lemma 5)). Let CR,b be defined in (10) and set Be as
3. = 8 log(1 + k/A) log (4k2H/8) + Aog (4k² H + VBB.
Then, with probability at least 35, we have that simultaneously for all h E [H] and k E [K],
0% {o11E 0v.1))12 - 3x) We,.Ve, (5k,hr ak,h) V..V (5k annn)) s ER
where Ek, is defined as follows:
min { HH,2H
1/2 Ovza,s (SR aktt (+)))) 1/2 @vantt (SK,h, ak.h min (H2, | 1
with
8. Add/log(1 + //) (4K2H/8) + 4V (4R2H/0) + VAB,
8/ 8 dH' (1 kH**/(d)) log (4x2H/0) + lo (4k² H/8) + VAB. (21)
We denote by the event when the result of Lemma holds, we have Pr(E) > 35.
Then we present the following lemma that shows the value function difference can be decomposed into two parts, one is a martingale sequence and the other is the estimation error.
Lemma 9. For all & E [K], h E [H), it holds that
H
(EA() - V.TA (8k.h) = Σ
(MENe + MA (s, ak.))
b'uh
20

---

with
Mg Buniel a) (K,A a) Q
(sk, (8k, (k. (s
Ma,h.2 = [TP (VE,tt - V Vk.h+1) (k,A) (VeNNI(PHA,A-)) - (8
Proof. By the definition (skA)) = Bawtel 1eanee a)}, we have
Vk,A(SAA)) - (Sk.h)
-BoNTs (-1 (9K, a) Q.. (Kk. a)]
= =BaNTi (-1 (-1 (e,a) [K, a) - QK. (5k a)] - (Qu,( ak.h) Q (Sk axk))
(QR,N(FR, 02,h.) 2h (SK,A, ak.h))
= -Eanasl ( [K.A a) - QKA (s a) - (Qu, assh)) Q% (sk. ak.h))
+ PV k.h+1 Ak akah) - C4 (Sk.h, ax.h))
BaNTEl- s Qu,
(5k, a)] (Qn,N(BR,A,aE.)) Qki.A. (SK axkh))
Me.h,1
+ IP - Ve (e++ ( ak,)) - V V (SH
Ms.n2
(8k,h11 V V.h++ (sk,)+1)) 14, (sk,h
where the third equality holds by the fact Qk, TK. - and QR,A. Tk, +PP V Summing up the above equation from h to recursively finishes the proof.
Note ME.1.1 is the noise from the stochastic policy and Ma,d, is the noise from the state transition, Let Ma. = ME.h.1 + MR.n2, Vk E [K], E [H]]. we define two following high probability events:
ε = { 4h E MM.
K
Σ
H
H MR S 4 H3K log 8
&
=
ΣΣ
K H
Ma.n.2
& V8H1kKlog log
1=1 T'=h
k=
According to the Azuma- Hoeua-Hoeffding inequality, we have Pr(Ei) 2 1 1- and Pr(E2) 2 1
Then, show the model prediction error LR,6 can be upper and lower bounded both.
Lemma 10. Define prediction error Uk = TR.A + PA V2,4+1 - Qk on the event E, it holds that
-2
1-2 Vvl. (..-)12 - (..) s 0, 4k E K (H].
Proof. First, we prove the left-hand side inequality. By the definition of 4. we have
-1,(((,a)) a)
=Qu((s,a) (rK,n +
Srk,a(s,a) (0n,A, (s, a)) + ( (re. P(
-OBu. 0h: Aivant (s, 3x 5-112 @ve.ntr (s.
2
|| " (s,
where the first inequality holds by the configuration of Qa, in Algorithm 1, the second equality holds by the definition of linear mixture MDP such that [P, (i,,+1)(ss,) = (Øv, (ov (s, 07)) and the last inequality holds by the configuration of confidence set Lemma
Next, we prove the right-hand side inequality. By the definition of 4.h. we have
(s,((saa) a)
= =(re, + Ps V2 (8, a) (s.
< (FR. + V. a)- (R. a) + (Dv,h,
+ Bell 1/2 ov (8, (2,)) 10.H--+1)
21

---

max { (Bahh oh (s, -
SS lel/Vv..o v (s.a))l2 (Fu.h PAV. PAVan++)(ss.) (H -H
< 0,
where the first inequality holds by the configuration of QK, in Algorithm 1, the second equality holds by the definition of linear mixture MDP such that [P^ Vi, a) = (ov (8, a), 0%) and the last inequality holds by the configuration of confidence set in Lemma 8.
Next, show the prediction emorr can be bounded by the eumulative estimate variance.
Lemma 11. Define prediction error Lk.h TR.h
PA v4, Qk the event E, it holds that
H
K H
( aRAA) < 23k
ΣΣ
1 2/H + K/X).
k=
Proof. By Lemma 10 and the definition of LR,A = ru, + FA V4,++1 - QK. we have
4e as.n)
2 min 13x |
ove (sk ?
on.n)l1: H3
k= h=1
K
H
Σ
OR min {115 &va (SK an. /0on//lll22
<
k=1
<28k
min S aaa.. (5K,0) an,)) /aninll :1
K Σ
< 28K
Σ
T V 22 K/A)),
where the second inequality holds by 23 2 VdH/ H, the third inequality is by Cauchy- Schwarz inequality and the last inequality holds by the elliptical potential lemma in Lemma 16.
Define the event
H
Es EMVRIII < 3(H + 33 log(1/61)
k=1k=1
by the law of total variance in Lemma 15, have Pr(Es) 2 8. Then, we have the following lemma which bounds the estimated variance of the value function.
Lemma 12 (He et al. [33, Lemma 6.5)). On the events & n E & n &g, holds that
h
Σ
S2H + 165 4 log² (4K log (1 KH th
k=
2062d 11 log" (4K² log (1+
Now, we are ready to prove Theorem 2.
Proof of Theorem 2. On the events E E & Ez, for any h E [H). it holds that
Σ (sk.))
A=1
22

---

(MK.A.1 + MK - (s,,, akhh))
1==1
4 Ho +3x
ΣΣ k=1b=1
o K
2 +
<Ō(vaH-K+
& BH²K).
where the first equality holds by Lemma 9, the second inequality holds by Lemma 11, and the last inequality holds by Lemma 12. This finishes the proof.
C.7
Proof of Theorem 3
Proof. By Lemma 5, we can rewrite the dynamic regret as follows.
D-Regret(K)
k. (5k,1)
k. (5k,1)
km
E (Qk, ( (1)))) Tech shh)ll
k= h=1
K
H
E (sh, an)] - -H.A(Skn,, + MK.H.
(22)
By Lemma 10, have 1x, (8,4 a) S for any [K], h [H] E S A. Thus, have
K
H
E an)] S 0.
(23)
Rem Am
By Theorem have
K C ax,))) MK.H S (Ō(V
(24)
remains to bound the first term. Note our algorithm is indeed updated based on the estimated action-vail function Qk By Theorem set 7 1/ KH and note that log(1/(1 (1))) I 7/(11 -7) for all y > O. Then, we have
K
Re (8h. " 8n) - TE,a |8))}]]
k= A=1
H
1
Hlog A 1 (1 H) log A Pr +2)
2
1)
7
It is clear that the optimal step size is 17" (Pr log A)/ Note our step size is set as 7 = min (Pr + log A)/K, 1) H to ensure 7) $ 1/H. We consider the following two cases:
Case 1: 17" < 1/H.
In this case, our step size is set as 1) = ((r log A)/(KH2). We have
+ HKH3
H log A + (1 Ho 4
Pr + <Ō(VKH((1+))
2
Case 2: 17" > 1/H.
this case, our step size is set as 1, = 1/H. Therefore, we have
Tj H
A Pr +2) s S(HPPr))
H log A + (1 H) log ?
2
17
23

---

where the equality holds by Pr 2 K in this case. Combining these two cases, we have
K
Brg ( 1) x (1))))))))---)))))))))) -TR.a- sa)) =())) Pr)(1 + Pr)). (25)
1= h=1
Combining (22), (23), (24) and (25), we obtain
D- D-Regret (K) < δ VVaHAK+ + V Pr)(1 +r))
This finishes the proof.
C.8
Proof of Theorem 4
Proof. At a high level, we prove this lower bound by noting that optimizing the dynamic regret of linear mixture MDPs is harder than (i) optimizing the static regret of linear mixture MDPs with the unknown transition kernel, (ii) optimizing the dynamic regret of linear mixture MDPs with the known transition kernel, both. Thus, can consider the lower bound of these two problems separately and combine them to obtain the lower bound of the dynamic regret of linear mixture MDPs with the unknown transition kernel. We present the details below.
First, we consider the lower bound of optimizing the static regret of adversarial linear mixture MDPs with the unknown transition kemel.. From lower bound in He et al. [33, Theorem 5.3], we have the following lower bound in this case since the dynamic regret is no smaller than the static regret.
D-Regret(K) 2 H(KK.HKK.
(26)
Then, we consider the lower bound of optimizing the dynamic regret of adversarial linear mix- ture MDPs with the known transition kernel. We note that Zimin and Neu [12] show the lower bound of the static regret for adversarial episodic loop-free SSP with known transition kernel is Ω H K log (SA)), we utilize this lower bound to establish our lower bound as the episodic loop- free SSP a special case of linear mixture MDPs with A2A. We consider two cases:
Case 1: r < 2H. In this case, we directly utilize the established lower bound of static regret as a natural lower bound of dynamic regret,
D-Regret(K) 2 2(H / log (SA)).
(27)
Case 2: r > 2H. Without loss of generality, we assume L. [T/2H] divides K and split the whole episodes into L pieces equally. Next, we construct a special policy sequence such that the policy sequence is fixed within each piece and only changes in the split point. Since the sequence changes at most
< T/2H times and the path length of the policy sequence at each change point is at most 2H, the total path length in K episodes does not exceed r. As result, we have
D-Regret K) N LH /
K/ log (SA) = H / KL log (SA) 2 2(v Q(VK(TT)))))) log (SA)). (28)
Combining (27) and (28), we have the following lower bound for the dynamic regret of adversarial linear mixture MDPs with the known transition kernel,
D-Regret K) 2 ② max H / K log (SA), / /HTT log (SA)))
+ [] (SA).
(29)
where the last inequality holds by max b} 2 (a 6)/2.
Combining two lower bounds (26) and (29), we have the lower bound of the dynamic regret of adversarial linear mixture MDPs with the unknown transition kernel,
D-Regret (K) 2 2( max (Vo (KH(H + T) log(SA)))
SOV@HHHK / ( log(
This finishes the proof.
24

---

C.9 Proof of Theorem 5
Proof. By Lemma 5, we can rewrite the dynamic regret as follows.
K
D-Regret(K)
Vil (5
Vil (sx,1)
k=1
Re (Qk, F (118)) - TEA. (8h))]
K
H
Bmgg (sh, ax) -. + MK.H-
1=
h=1
By Lemma 10, we have (,, a)
S 0 for any [K], h E [ E S, E A. Thus, we have
K
H
( an) S O.
1==1
By Theorem 2, we have
K
H
(L (x,))) + MK,H & Ō( + @HOK).
remains bound the first term. We decompose this term follows.
BTg [Q k. (sh, )) (-1 (%) T- | [s)))
Aum P
Eng
(Q (sk ) m sb)) Then |s)))
base-regrat.
Rizg (0 )) m 8h) (-
(30)
neta-rogret
where the decomposition holds for any base-leamer E N. Next, we bound the two terms separately.
Upper bound of base regret. From Theorem 1, we have
base-regret < K3 +
H log A + (1+ H) log Pr KH log 1-
Set 7 1/KH and note that log(1/(1
7))
$ 7/(1 - 7) for all 0. Then, have
17 K3
1
base-regret& <
+
HH log A + (1+ log( +
2
ni
7) K
2H
+
(log A Pr log KHA)).
2
T
It is clear that the optimal learning rate ry" = / 4(llog A Pr log K (KH)) By the definition
Pr Σk Σ [ T. 1.6 1,00. it holds that 0 < Pr 2KH. Therefore, the range of the optimal learning rate is
4 A
and 7max 4log A + 8K log (HA)
Mmin
K
KH²
From the construction of the step size pool H (n: (2/ (log A)/K i E [N]] with
N } log log ).). we know that the step size therein is monotonically increasing, in particular
4log A
M
KH2
and T/
H
In the following, consider two cases:
25

---

Case 1: 1111"" NN.. In this case, we ensure there exists i" E N such that 7/+- <n" < 2n.-. Note the decomposition (30) holds for any base-learner. Therefore, we choose the base-learner whose step size is y/- and have
T/- H
2H
base-regret
+
(log A + Pr log (KH
2
17" H
4H
< 2
+
(log A + Pr. log (K H A))
11"
= 3/ H (log A + Pr log (H))).
where the second inequality holds by the condition that V)-- S n S 21,- and the last equality holds by substituting 17* /4(log A + Pr log( K H (H²).
Case 2: 11" > 7N- In this case, know that 4(log A Pr log((HA))) K. Therefore, choose the base-learner whose step size is v/ and have
IN H3
2H
base-regret 1
+
(log + Pr log (KHA))
2
KH²
+ 2H² (log A + Pog K (HA))
2
- 4H² (logA+ A+ Pr logg KHA)),
where the last inequality holds by the condition that 4(log A + PT log KHA)) K. Summing over the two upper bounds yields
base-regret& 3/ KH (log A + Pr log K HA)) + 2 (log + Pr log (KHA))
S 4v HK(K + log A + Pr log (KH (H) + Prlog(K (KHA))
Õ H P1 (1 Pr)).
(31)
where the inequality holds by Va + vb S v ba, 0.
Upper bound of meta regret. For meta-regret, we have
reta-regret
Bag [(Q Th ( sn) TR,al |n))]]
Bigg (se))))) - (xn) Qun((ons)) ( T [8))]]
k= 1=11
K
Eagg (ethin (SN) pk, (unn()).)) Tha snl)
km 1 km1
BAg (ofti (sn) cla-1a (k. Thaa snns
Rm h=1
Eng [lefhih(ss) - - - (m))ll
H
h=1
2HST,
(32)
where the first inequality holds by the definition that 17,, = arg [ (Qu, -), Th (- sn)). the second inequality holds due ph. a. (sh) e'i-1. (sn). and the last equality holds by the definition
ST E
H - Eng 1 (8h) ) # i 1.1 (s+))-
Combining (31) and (32), by Va + vb /2(a= + Va, b 0, we have
D-Regret(K) s Ō (Vat-KV K213K
((11++++++ P+)+ 11357
This finishes the proof.
26

---

D Supporting Lemmas
In this section, we introduce the supporting lemmas used in the proofs.
First, we introduce the performance difference lemma which connects the difference between two policies the difference between their expected total rewards through the Q-function.
Lemma 13 (Cai et al. [32, Lemma 3.2]). For any policies n,, X E ([A)SHH) it holds that
V (ok,)) Vž. (5K,1)
(shh))))) -==1
m 8N) ma(. (6)) 81 sk.1
Then, we introduce the following lemmas which show the "one-step descent" guarantee. Lemma 14 (Cai et al. [32. Lemma 3.3]). For any distributions p' :p E A(A), state s E S, and function Q: S [0, H.. it holds for p' ((A) with p'(+) p(-) exp(n Q(s,))) that
((.,),,'' p()) S / (DRL. (p" ()ll(()) DEL (p" ()))()))
Next, we introduce the law of total variance, which bounds the variance of the value function.
Lemma 15 (Jin et al. [55, Lemma C.5]). With probability at least 1 - 8, it holds that
K
H
log 5))
Vn h+1
(sh ( 5 3 HK + H 1ogg
k=
#=1b=1
Finally, we introduce the elliptical potential lemma, which is a key lemma in online linear regression. Lemma 16 (Abbasi- Yadkori et al. [51, Lemma 11]). Let {x be sequence in R.d space, Vo Al and define V. = Vo + Ei= x.xT. 1/ l|xxx S L, Vi E Zt, then for each & E Z...
dd d1++
min |xx 2 s 2dlog
d)
27


Reviews:
[{"review_id": "rjslOVp9KT", "reviewer": "Reviewer_Gpzi", "summary": "The paper studies RL in the adversarial episodic inhomogeneous MDP setting with transition kernels. It should be noted that the paper considers full-information feedback & linear mixture MDPs (both are very strong assumptions). The authors propose an algorithm drawing inspiration from policy optimization and prediction with expert advice problems (hence the full-information feedback setting). An upper bound on the dynamic regret is provided. The authors also offer an accompanying lower bound.", "questions": "Could the authors highlight what are the key innovations (either in the algorithms or in the analysis) that lead to this improvement?", "limitations": "The authors discuss some limitations & future works in the conclusion.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written and seems technically sound. An extensive literature review is provided and the authors offer comparison and discussion with closely related works. The regret bound improves upon those in existing works, and is near-optimal.", "weaknesses": "Among the key technical innovations listed in the introduction compared to existing works (Fei et al [2], Cai et al [34]), I feel like the extension from tabular MDPs to linear mixtures MDPs not technically challenging, given the fact that proximal policy optimization can be naturally extended beyond the tabular setting. In that case, the real contribution lies in the improvement of the regret bounds. Could the authors highlight what are the key innovations (either in the algorithms or in the analysis) that lead to this improvement?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments and suggestions. We provide our response to each question below.\n\n----\n\nQ1: \"Could the authors highlight what are the key innovations (either in the algorithms or in the analysis) that lead to this improvement?\"\n\nA1: The key innovations over the prior works (especially the works of Fei et al. [2] and Cai et al. [34]) for non-stationary MDPs lie in the different ways to handle the environmental non-stationarity. \n\nCai et al. [34] focused solely on the static regret of adversarial linear mixture MDPs where a single, fixed policy served as the comparator. Their algorithm and analysis do not support dynamic regret minimization, which requires to compare with a sequence of time-varying comparators. \n\nFei et al. [2] studied the same problem setup as ours, i.e., the dynamic regret of adversarial linear mixture MDPs. Their algorithm follows a **restarting strategy** to handle the non-stationarity. Specifically, the algorithm will periodically restart itself to discard previous information. However, this restart period requires the prior knowledge of the environmental non-stationarity $P_T$ as an algorithmic input, which is unfavorable.\n\nIn contrast, our approach tackles the environmental non-stationarity via the **two-layer meta-base framework**. We first design a policy optimization algorithm which is capable of tracking time-varying compared policies (this is achieved in a non-trivial manner, and see Lemma 1 in the paper), though the optimal step size tuning still requires the prior knowledge of $P_T$. To remove this unpleasant dependence, we introduce a meta-base two-layer structure  that concurrently maintains multiple base-learners. Each base-learner is associated with a candidate step size, ensuring that the optimal step size is well approximated when considering all base learners together. Subsequently, we employ a meta-algorithm to track the optimal base-learner and thus can achieve favorable guarantee without knowing $P_T$ ahead of time.\n\nWhile this framework can be kind of standard in modern online learning, several new technical challenges need to be solved when applied to online MDPs. For example, the standard dynamic regret analysis relies a telescoping argument in online convex optimization, which won't work in online MDPs because regret here is defined on the expectations across changing policies. We address this issue by leveraging a fixed-share mechanism and presenting a novel multiplicative stability lemma, as detailed in Lines 203-208. Furthermore, the standard implementation of the two-layer structure requires us to update and evaluate multiple base-learners simultaneously. However, we can only deploy a single combined policy in the environment. We handle this challenge by a new analysis. More technical highlights can be found in the end of page 2 in our paper. \n\nIn summary, a proper deployment of the meta-base two-layer structure is the key innovation of our proposal method to achieve the improvement.  We appreciate your feedback and will revise the paper to more clearly emphasize these discussions in the next version. Thanks!"}, {"review_id": "5KV3ECu43f", "reviewer": "Reviewer_cWVL", "summary": "This study analyzes the problem of online learning episodic inhomogeneous MDPs with _full-information_ reward functions (changed over episodes $k$ and step $h$) and the unknown transition kernel (unchanged over episodes). The MDPs are linear mixture MDPs and the performance measure is _dynamic_ regret (against _any sequence of policies_ with a non-stationarity measure of $P_T$ which controls how varied the sequence is). The proposed algorithm improves on existing upper bounds while relaxing on the requirement of prior knowledge (that of $P_T$). A lower bound is also provided which suggests optimality of the proposed algorithm on a few problem parameters.\n\nThe presentation is excellent and the proposed algorithm seems interesting. I recommend its acceptance.", "questions": "1. Can you provide some intuition of what the switching number of best base-learner, $S_T$, measures? I found it challenging to grasp due to the presence of the expectation taken over (counterfactual) state distribution generated by $\\pi^c_k$. Are there some regimes for this parameter that are interesting (and provide intuitive connections to existing studies)?", "limitations": "Adequate.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The presentation is excellent and technically substantive. I am not an expert on the exact topic but feel comfortable following most of the discussion.\n1. The proposed algorithm is interesting and uses techniques from other (recent) works (some from adjacent fields).\n", "weaknesses": "1. From the point of view of someone who is not intimately familiar with the exact topic, the problem setting might seem a bit artificial/too restrictive, e.g., full information of reward functions. But it is clear from the cited works that many features of the setup are up-to-date with what the community is actively studying. The authors also acknowledged out some of such limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments! Below we will address your questions. \n\n---\n\nQ1: “Can you provide some intuition of what the switching number of best base-learner, $S_T$, measures? Are there some regimes for this parameter that are interesting (and provide intuitive connections to existing studies)?”\n\nA1: Thanks for the question. The quantity $S_T$ denotes the switching number of the best base-learner for each round, which essentially reflects the degree of environmental non-stationarity. Consider the following two examples. \n\n1. In the stationary environment (i.e., reward function remains unchanged), $S_T$ could be relatively small as the best base-learner would seldom change.\n2. In the piecewise-stationary environment, $S_T$ would align with the frequency of these environmental changes. \n\nIn this regard, $S_T$ can be considered as an additional measure of the level of non-stationarity.\n\nBut admittedly, we acknowledge that $S_T$ is a data-dependent quantity, and one may prefer to obtain bounds that rely solely on the problem-dependent quantity, such as $P_T$. As noted in Remark 3, this would introduce technical challenges that are difficult to address. We take this issue for future research and will emphasize more on this point in the revised version. \n\n---\n\nQ2: \" I found it challenging to grasp due to the presence of the expectation taken over (counterfactual) state distribution generated by $\\pi_k^c$\"\n\nA2: Sorry for the confusion. We define $S_T$ by taking the expectation over the state distribution generated by $\\pi_k^c$ to derive a more refined bound. The expectation can be conveniently replaced by considering the maximum over all states.\n\n---\n\nThank you for raising these questions. We will revise our paper to highlight the points discussed above and further improve the presentation in the next version."}, {"review_id": "Q1phjXWNfa", "reviewer": "Reviewer_yhLY", "summary": "The paper \"Dynamic Regret of Adversarial Linear Mixture MDPs\" studies reinforcement learning in episodic non homogeneous MDPs with adversarial rewards in full information feed back setting. The motivation for this work is that In many applications, reward functions may be picked adversarially, and changing over time. Moreover, the state and action spaces may be huge. Hence, this paper considers adversarial rewards and linear function approximation. Previous work lacks in one of these requirements. The authors analyse that their algorithm enjoys a \"dynamic regret\" which is close to \"optimal\" by deriving a lower bound, and can recover the static setting, and improves the adversarial reward regret for tabular MDPs.", "questions": "Please refer to above section. I appreciate if these are discussed further by the authors.\n\nAnother question is in Remark 2. How do we retrieve the static case from Theorem 1?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "A novel algorithm is proposed that achieves good dynamic regret, under non stationary adversarial regime, without the knowledge of the non-stationarity measure, which poses many challenges for the analysis. \n\nThe analysis in the paper successfully overcame these and obtained upper bound and a matching lower bound.\n\nStatic case can be exactly recovered from these results, and in case of tabular case, it strictly improves the existing bound.", "weaknesses": "Though out of scope for this work, I would like to know the author's perspective on the following (since they also mentioned these in the paper).\n\n1. This work considers full information setting, bandit setting is not considered, and much more complex.\n\n2. The dependence on S is bad in large state space regime, and on H when the non-stationary measure is large. These could not be avoided from the analysis.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the insightful and constructive comments from the reviewer. In the following, we will respond to each of the questions raised.\n\n---\n\nQ1: “This work considers full information setting, bandit setting is not considered, and much more complex.”\n\nA1: It would indeed be very interesting to consider the bandit setting, but as far as we know, this presents significant challenges. Investigating dynamic regret with adversarial rewards and bandit feedback, even within the more simplified online learning setting (like multi-arm bandits),  is not well understood. The high-level challenge here includes how to effectively deploy the meta-base structure given the very limited bandit feedback, and how to ensure a sufficiently small meta regret to avoid ruining the overall bound. We believe that substantial novel ideas are required to develop non-trivial guarantees for the bandit setting. \n\n---\n\nQ2: \"The dependence on $S$ is bad in large state space regime, and on $H$ when the non-stationary measure is large\"\n\nA2: Thank you for your question. We would like to address your concerns as follows.\n\n- The dependency on $S$ is indeed not ideal, particularly in the large state space regime. We have addressed this issue in the supplementary-material version, where we present an alternative and refined analysis for the algorithm. This analysis achieves a dynamic regret bound that is independent of $S$, but at the price of introducing another data-dependent quantity $S_T$, which represents the switching number of the best base-learner for each round and essentially captures the degree of environmental non-stationarity. \n- The dependence on $H$ in our result aligns with the most recent research, such as the works of Fei et al. [2] and Zhao et al. [58]. It is important to note that a gap persists in the dependence of $H$ even when the transition kernel is known, as indicated by Theorem 1 and Theorem 2 of Zhao et al. [58]. Addressing this issue and closing this gap is a crucial issue for future research.\n\nIn summary, while our dynamic regret guarantees are already optimal in some contexts, the limitations pointed out by the reviewer indeed exist. We will take those as future work and try to improve the result further.\n\n---\n\nQ3: \"In Remark 2, how do we retrieve the static case from Theorem 1?\"\n\nA3: For the static regret, the comparators are the same, that is, $\\pi_1^c = \\ldots = \\pi_K^c = \\pi^*$, i.e., $P_T=0$. Set $\\gamma = 0$, the dynamic regret in Theorem 1 becomes $\\text{D-Regret}(K) \\leq \\frac{\\eta KH^3}{2} + \\frac{H \\log A}{\\eta}$. By setting the step size as $\\eta = \\sqrt{\\frac{\\log A}{KH^2}}$, we obtain the $O(\\sqrt{H^4 K \\log A})$ static regret. Thanks for your question, and we will add more explanations in the revised version."}, {"review_id": "oR8ZQKrHnP", "reviewer": "Reviewer_Xpcd", "summary": "This paper explores the problem of reinforcement learning in non-homogeneous MDPs with adversarial full-information reward feedback and unknown transition kernels. The authors propose a new algorithm that has advantages in dynamic regret and does not require prior knowledge as input. The algorithm achieves optimal performance in certain cases. The paper provides a theoretical foundation for reinforcement learning in non-homogeneous MDPs by studying the upper and lower bounds of dynamic regret.", "questions": "- While the fix-share mechanism and multiplicative stability lemma used in this work aim to enhance the regret upper bound, it is important to assess whether these techniques strictly improve upon existing works. The authors should provide a clear analysis or comparison demonstrating how their approach surpasses or builds upon the achievements of previous methods. If the improvements are not strictly superior but rather offer refinements or alternative perspectives, they should be clearly stated to avoid potential misconceptions.\n\n- In addition, offering further explanations on why the reduction-based framework in (Wei and Luo, 2020) is not applicable in adversarial linear mixture MDPs, even with full-information feedback, would add value to the paper. Discussing the specific challenges or characteristics of adversarial linear mixture MDPs that render the reduction-based framework ineffective or impractical will enable readers to grasp the unique complexities of the problem domain. By providing these explanations, the authors can highlight the significance of their proposed approach and its suitability for addressing the specific challenges posed by adversarial linear mixture MDPs.", "limitations": "n/a", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "This work investigates the dynamic regret in linear mixture MDPs with adversarial rewards, which is a problem of great significance and relevance. The authors make notable contributions by offering a precise upper bound on regret as well as a lower bound for this problem. To derive the upper bound, the authors introduce new techniques, including the fix-share mechanism and a multiplicative stability lemma, which hold potential value and may be of independent interest to researchers in related fields. ", "weaknesses": "- The authors have not included a highly related work titled \"Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs,\" which addresses the more challenging setting of linear mixture MDPs with adversarial rewards and non-stationary transitions.\n\n- When comparing this work with both (Fei et al., 2020) and \"Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs,\" it is worth noting that this work demonstrates improvements in terms of the parameters K and P_T. However, it introduces an additional dependency on S_T. Since S_T can be linear in K in the worst-case scenario, the resulting regret bounds may not strictly improve upon the previous findings.\n\n- Considering the omission of the aforementioned related work and the potential limitations of the current results in terms of the additional dependency on S_T, it may be valuable for the authors to discuss these aspects in the paper. This would help readers gain a comprehensive understanding of the work's contributions and its relationship to the existing literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful review. We will answer your questions individually. If your concerns are properly addressed, please consider updating the score. Thanks!\n\n---\n\nFirst, the reviewer may have an important misunderstanding on the two different settings: (i) non-stationary *stochastic* MDPs (other works)  and (ii) non-stationary *adversarial* MDPs (this paper). This confusion could be due to our insufficient discussions. We'd clarify the salient differences below.\n\nQ1: a related work [Zhong et al. 2021], which is more challenging\n\nA1: Thanks for bringing this paper, which also studies the non-stationarity issue in MDPs and thus related to our work. We will undoubtedly cite and discuss it in the next version. However, it’s crucial to point out that the setting of [Zhong et al., 2021] is *fundamentally different* from ours. \n\n- They study non-stationary **stochastic** MDPs, where the reward is assumed to be *stochastically* generated by parametric models with parameters continuously drifting. \n- In contrast, we study non-stationary **adversarial** MDPs, allowing rewards *adversarially* chosen. The objective is to be competitive with a sequence of time-varying compared policies. \n\nSo we respectfully disagree with the comment that setup in [Zhong et al., 2021] is more challenging than ours --  they are actually *incomparable*.  Below we highlight more detailed differences. For simplicity, we consider the fixed transition kernel scenario. \n\n- In non-stationary **stochastic** MDPs, rewards are generated **stochastically** according to some parametric models that may vary over time, for example,  $r_k(s, a) = \\phi(s, a) \\theta_k^* +noise$, and the aim is to optimize regret against the drifting parameter $\\theta_1^*,...,\\theta_K^*$.     \n- Contrarily, non-stationary **adversarial** MDPs  do *not* make any stochastic assumption over the rewards $r_k$. Instead, they compete with *arbitrary* feasible sequence of time-varying compared policies, which could be chosen with hindsight as the oracle comparators that best fit the underlying environments with an optimal balance between bias (due to various factors like sample randomness) and variance. \n\nAlgorithmic ingredients to handle non-stationarity are also significantly different (sliding window/restart/weights for stochastic MDPs; and two-layer structures for adversarial MDPs).  \n\nTo summarize, the two settings and respective algorithms/results are *incomparable*. They can be viewed as two distinct models for non-stationary online learning. Actually, in some cases the adversarial setting would be even harder, see A2 for discussions.\n\nWe will include those discussions in the next version to enhance the literature review. Thanks!\n\n----\n\nQ2: \"why ... framework in (Wei and Luo, 2020) is not applicable in adversarial linear mixture MDPs\"\n\nA2: This framework [Wei and Luo, 2020] can handle non-stationary **stochastic** MDPs, but cannot be applied to our adversarial case. Indeed, their reduction requires the base learner to satisfy a UCB-like property. When a new instance of base algorithm surpasses this optimistic estimator, the MASTER algorithm will suspect environment suffering changes and perform the restart. However, this strategy is challenging to apply in adversarial setting, since the construction of a UCB-type base learner is difficult when there are no statistical model assumptions.\n\nIndeed, non-stationary stochastic/adversarial online learning and decision making are usually examined independently, even in simplified scenarios such as full-information and bandit online learning. Actually, in certain instances, non-stationary adversarial setting can be *more challenging* than the non-stationary stochastic one. Consider the multi-armed bandits problem.\n\n- It is extremely difficult to handle its non-stationary *adversarial* model, and actually achieving an optimal bound without knowing the non-stationarity level is provably *impossible* for adaptive adversaries [Marinov and Zimmert, 2021], and remains open for oblivious adversaries. \n\n- In contrast, it's feasible to derive an optimal strategy for a non-stationary *stochastic* setting without the non-stationarity level using the technique of [Wei and Luo, 2022]. \n\nMore technical discussions can be found in P3 of [Luo et al., 2022]. We will clarify it in the revised version.\n\nT. Marinov and J. Zimmert. The Pareto Frontier of Model Selection for General Contextual Bandits. NeurIPS 2021.\n\nC.-Y. Wei and H. Luo. Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach. COLT 2021.\n\nH. Luo, M. Zhang, P. Zhao, and Z.-H. Zhou. Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits. COLT 2022.\n\n---\n\nQ3: issue on switching number $S_T$\n\nA3: We agree with the comment and acknowledge that involving data-dependent quantity $S_T$ is not fully satisfactory. But we believe our contributions are still interesting enough to the community with reasons below.\n\n- Our result is more attractive than (Fei et al,. 2020) under regimes such as stationary environment where the best base-learner rarely changes, as well as piecewise-stationary environment where the environment only change certain times (then $S_T$ aligns with the change frequency). \n- Importantly, we improve the dependence on $K$ and $P_T$, matching the lower bound established in our paper.\n\nAs noted in Remark 3, the dependence on $S_T$ presents a significant technical challenge, primarily because  meta regret is now a weighted regret across all states, where the weight for each state is determined by **arbitrary** comparators $\\pi_1^c,...,\\pi_K^c$. This is in contrast with existing literature and presents a unique challenge. We take this for future research and will emphasize more in the revised version. \n\n---\n\nWe hope above responses sufficiently address your concerns. We're happy to provide further clarifications to additional questions during the reviewer-author discussion period. Thanks!"}, {"review_id": "x6XCw8NBoC", "reviewer": "Reviewer_BpVE", "summary": "This paper studiess adversarial RL under episodic linear mixture MDPs with adversarial full-information reward and stationary unknown transition kernels. This paper first proposes a new algorithm to deal with the adversarial reward and then provides an upper bound of dynamic regret for the proposed algorithm. Then this paper proposes a lower bound for dynamic regret and claims acheiving optimal in terms of the number of episodes $K$ and the non-stationary measure $P_T$.", "questions": "As listed in weakness.  ", "limitations": "This work does not pose any negative impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a noval algorithm to deal with adversarial RL without prior knowledge. The main steps of the algorithm seem reasonable and the paper provides detailed insight of each steps.\n2. This paper provide an upper bound of dynamic regret and the dependenece of $K$ in upper bound achieves optimal. ", "weaknesses": "1. The algorithm and result of this paper only apply to finite state case, which makes the result less significant. \n\n2. The proof of the lower bound lacks rigor in several aspects. Firstly, the proof of the lower bound is divided into two separate cases, which is not in line with the definition of a lower bound. Ideally, the author should construct one hard instance that encompasses both cases. Secondly, in the proof of the second case (dynamic regret case), the proof merely takes the maximum between the results of the two cases with respect to the range of $\\Gamma$. \n\n3. Due to the existence of numerous studies employing alternative approaches to address non-stationarity and yield diverse results, I think more comprehensive and detialed discussions with non-stationary RL are needed. For example, although line 108 indicates that [1] is not applicable to the adversarial setting when the comparators are arbitrarily chosen. In fact, people are usually concerned about the case where camparators are optimal policy. In this case, does the non-stationary RL discussed in [1] cover the adversarial RL in this paper? It is important to discuss the relationship between the findings of [1] and this paper in such cases. [1] also achieves optimal regret with $K^{2/3}\\Delta^{1/3}+\\sqrt{K}$, where $\\Delta$ denotes another non-stationary measure. Why does the dependence on $K$ differ? From my understanding, this discrepancy seems to arise from distinct non-stationary measures. \n\n\n[1] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 4300–4354, 2021.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments. We will address your concerns and questions below. \n\n---\n\nIn particular, we believe there are some misunderstandings about the distinction between the non-stationary *stochastic* MDPs (studied in other works) and the non-stationary *adversarial* MDPs (this paper), as well as the lower bound argument. Those confusions could potentially be due to our lack of sufficient explanations in the paper. We would take this opportunity to make the clarifications below. If your concerns are appropriately addressed, please consider updating your score. Thanks!\n\n---\n\nQ1: \"The algorithm and result of this paper only apply to finite state case, which makes the result less significant.\"\n\nA1: We clarify that our algorithm can be applied to MDPs with the large state case. In Appendix B, we show that the computational complexity is independent of the number of state $S$. Additionally, our regret bound is also independent of $S$ (please kindly check the supplementary version, in which we have refined the analysis and obtained bounds independent of $S$).\n\n---\n\nQ2: \"The proof of the lower bound lacks rigor in several aspects. Firstly, the proof of the lower bound is divided into two separate cases, which is not in line with the definition of a lower bound. Ideally, the author should construct one hard instance that encompasses both cases. Secondly, in the proof of the second case (dynamic regret case), the proof merely takes the maximum between the results of the two cases with respect to the range of $\\Gamma$.\"\n\nA2: We respectfully disagree with this comment. It’s a typical strategy to divide the entire problem into several distinct cases to establish the lower bound, which allows us to find hard instances more conveniently. This is both reasonable and sound. Let's consider a problem denoted as $A$, which consists of two cases, $A_1$ and $A_2$, where the difficulty of case $A_1$ is represented by $L_{A_1}$ and the difficulty of case $A_2$ by $L_{A_2}$. In this context, it is evident that problem $A$ cannot be easier than either case $A_1$ or case $A_2$, since all the difficult instances of cases $A_1$ and $A_2$ are encompassed within problem $A$. Consequently, the difficulty of problem $A$ is at least equal to the maximum difficulty between cases $A_1$ and $A_2$. Thus, we can assert that the difficulty of problem $A$ is $\\max(L_{A_1}, L_{A_2}) \\geq (L_{A_1} + L_{A_2}) / 2 \\geq \\Omega(L_{A_1} + L_{A_2})$. We will add more explanations in the revised version.\n\n---\n\nQ3: \"more comprehensive and detailed discussions with non-stationary RL are needed. \"\n\nA3: Thank you for the suggestion. We will certainly enrich the discussion on the existing literature. However, it's crucial to emphasize that non-stationary MDPs can be divided into two main threads: (i) non-stationary *stochastic* MDPs, which most previous works are concerned with; and (ii) non-stationary *adversarial* MDPs, which this paper focuses on. The two settings, along with their respective results and algorithmic components, are very different and generally incomparable. They can be viewed as two distinct models for addressing non-stationary online learning and decision-making processes. In fact, these two settings are typically studied independently, even in simplified scenarios such as full-information and bandit online learning. For a more detailed discussion on the significant differences between these two setups, **please refer to A1 for Reviewer Xpcd**.\n\nFurthermore, we note that all the relevant works (to the best of our knowledge) on non-stationary adversarial MDPs are covered in our paper. We will add additional discussions on other related works, including those concerning non-stationary stochastic MDPs, to provide readers with a more comprehensive understanding of the literature. Thank you.\n\n---\n\nQ4: \"does the non-stationary RL discussed in [1] cover the adversarial RL when the comparators are optimal policies in this paper?\"\n\nA4: No, the reduction-based framework in [1] can handle non-stationary **stochastic** MDPs, but it *cannot* be applied to non-stationary **adversarial** MDPs even the comparators are set as optimal policies. \n\nIndeed, Wei and Luo (2020) propose a generic reduction, which requires the base learner to satisfy a certain property enjoyed by typical UCB-type algorithms. When a new instance of the base algorithm surpasses this optimistic estimator, it can be inferred that the environment has undergone changes, prompting a restart of the algorithm to disregard prior information. However, this approach of constructing an optimistic estimator using a UCB-type algorithm can only be applied effectively in a **stochastic** setting. In the **adversarial** setting, where no model assumptions are made and comparators can be *arbitrary*, this approach encounters significant difficulties. \n\nThis difference highlights the significant challenges inherent in handling non-stationary adversarial MDPs. In fact, **as discussed in A2 for Reviewer Xpcd**, non-stationary adversarial online learning can be sometimes much harder than non-stationary stochastic online learning, even for the multi-armed bandit setting.\n\nThanks for your question. We will clarify this point more clearly in the revised version.\n\n---\n\nQ5: \"It is important to discuss the relationship between the findings of [1] and this paper in such cases\"\n\nA5: We clarify that [1] studies the non-stationary stochastic MDPs, which is significantly different from our non-stationary adversarial MDPs as mentioned in A4. Consequently, both our problem setting and corresponding results are not directly comparable. We should have discussed more on this point, and we will revise the paper to make it clear in the next version. Thanks!"}]

Author rebuttal:

Meta-review: The work considers the RL problem was in the adversarial episodic linear mixture MDP setting with transition kernels, and not assumptions on the reward function. Further, in terms of feedback model the authors assume full-information feedback. It is worthwhile to note that the linear mixture MDP (as oppose to general linear MDPs) and full information assumptions are quite strict. For this setting, the authors design a policy optimization algorithm, establish upper bound on its dynamic regret, and establish a lower bound for this problem.

The key issue that was raised by reviewer Xpcd is the relation to the work of Zhong et al., 2021, Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs. Zhong et al., 2021 studied the linear MDP setting with linear reward function and derived a 
 upper bound for the dynamic regret of this setting. Even after a long correspondence between reviewer Xpcd and the authors they did not come to agreement about the novelty of this work. The authors highlighted their reward function is adversarial (yet with full information access) whereas in Zhong et al., 2021 the authors made an assumption on its parametric form (that its linear in the features). Another different, that I do find interesting, is the fact the authors obtained an upper bound, as oppose to the upper bound on the authors of Zhong et al., 2021 derived. That being said, the fact in this work the authors assume the full information setting, makes their setting substantially "simpler" than the one of Zhong et al., 2021.

Nevertheless, besides of Xpcd, all other reviewers were positive and in consensus about the quality of this paper. They found the results sufficiently interesting and praised the quality of writing (for example, the literature review on the topic was positively mentioned). In light of these, I currently recommend on the acceptance of this paper: it seems to me the setting studied in this work and in Zhong et al., 2021 is sufficiently different. That being said, much resemblance exist between the settings, and for this reason the authors must cite this work and elaborate on the differences. Further, since Zhong et al., 2021 already studied dynamic regret in RL setting, I believe this work does not deserve to be accepted as a spotlight paper, but only as a poster.
Decision: Accept (poster)