Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs
Authors: Long-Fei Li
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
dynamic regret
linear mixture MDPs
function approximation
Primary area: reinforcement_learning
TL;DR: This is the first work that achieves near-optimal dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.

Abstract: We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback, employing *dynamic regret* as the performance measure. We start with in-depth analyses of the strengths and limitations of the two most popular methods: occupancy-measure-based and policy-based methods. We observe that while the occupancy-measure-based method is effective in addressing non-stationary environments, it encounters difficulties with the unknown transition. In contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non-stationary environments. Building on this, we propose a novel algorithm that combines the benefits of both methods. Specifically, it employs (i) an *occupancy-measure-based global optimization* with a two-layer structure to handle non-stationary environments; and (ii) a *policy-based variance-aware value-targeted regression* to tackle the unknown transition. We bridge these two parts by a novel conversion. Our algorithm enjoys an $\widetilde{\mathcal{O}}(d \sqrt{H^3 K} + \sqrt{HK(H + \bar{P}_K)})$ dynamic regret, where $d$ is the feature mapping dimension, $H$ is the episode length, $K$ is the number of episodes, $\bar{P}_K$ is the non-stationarity measure. We show it is minimax optimal up to logarithmic factors by establishing a matching lower bound. To the best of our knowledge, this is the **first** work that achieves **near-optimal** dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.

Near-Optimal Dynamic Regret for 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) [houzh}@landee mondd..ju.. njj.. wjw.edu.com edu.
@lamda.
Abstract
We study episodic linear mixture MDPs with the unknown transition and adver- sarial rewards under full-information feedback, employing dynamic regret as the performance measure. We start with in-depth analyses of the strengths and limita- tions of the two most popular methods: methods. We observe that while the necupancy-measurr--bee mee-suee-baeeee method is effective in addressing non-stationary environments, it encounters difficulties with the un- known transition. contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non-stationary environments. Building on this, we propose novel algorithm that combines the benefits of both methods. Specifically, it employs (i) an gruuancyy-eassure based global optimiza- tion with two-layer structure to handle non non-stationary environments; and (ii) a policy-base variance-aware value-targe targeted regression to tackle the unknown tran- sition. We bridge these two parts by a novel conversion. Our algorithm enjoys an Odv/H*K + H (H + Pk)) dynamic regret, where d the feature dimension, H is the episode length, K is the number of episodes, Px is the non -tattioiionartt measure. We show it is minimax optimal up to logarithmic factors by establishing matching lower bound. To the best of our knowledge, this is the first work that achieves near retrroltimal dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.
maeaaanccccmmaueeeeeeea based and policy-based
Introduction
Reinforcement Learning (RL) studies the problem where a learner interacts with the environments and aims to maximize the cumulative reward [Sutton and Barto, 2018], which has achieved significant success in games [Silver et al., 2016]. robotics [Kober al., 2013], large language model [Ouyang et al., 2022] and so on. The interaction is usually modeled as Markov Decision Processes (MDPs). Research on MDPs can broadly divided into two lines hased on the reward generation mechanism. The first line of work [Jaksch et al., 2010, Azar et al., 2013, 2017, He et al., 2021] considers the stochastic MDPs where the reward is sampled from fixed distribution. however, the assumption of fixed reward distributions may not hold, as rewards can vary over time. This motivates the study on adversarial MDPs [Even-Dar et al., 2009, Yu et al., 2009, Zimin and Neu, 2013, Jin et al., 2020a], where rewards might change in an adversarial manner. To address the challenges of large-scale MDPs, recent studies have extended these two frameworks to incorporate function approximation, allowing RL algorithms to handle large state and action spaces. Two popular models are linear mixture MDPs [Ayoub et al., 2020] and linear MDPs [Jin et al., 2020b].
many real-world scenarios,
In this work, we focus on linear mixture MDPs with adversarial rewards, unknown transition and full-information feedback. Though significant advances have been achieved for this setting [Cai et al., 2020, He et al., 2022], they choose static regret as the performance measure, which benchmarks the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparisons of dynamic regret guarantees with previous works studying adversarial linear mixture MDPs with the unknown transition and uull-informatio feedback. Here, d is the feature mapping dimension, H is the episode length, K is the number of episodes. Px and Pk are two kinds of non-stationarity measure defined in (3) satisfying Px v Hk [Zhao et al., 2022, Lemma 6].
Reference
Dynamic Regret
Px or Pk
Zhong et al. [2021]
O(aHTi* + K2222/5pp
Known
Li et al. [2023]
Odd + H2 VR + PK)(1 + Pk))
Known
Li et al. [2024b]
OdHSVK + /HK(H PR))
Unknown
Upper Bound (Theorem 1)
Ö(dVH*K VHK(H + PK))
Unknown
Lower Bound (Theorem 2)
(dV/HK + VHK(H + PK))
learner's policies ...... Tx against the best-fixed policy in hindsight, namely,
K
K
Regk = mAX REll
(Sk,,)
Σ
V (sw.),
where V ($ is the expected cumulative reward of policy a starting from initial state 8k,1 at episode k and II is the policy set. While static regret is natural choice for online MDPs, the best- fixed policy may perform poorly when the rewards change adversarially. To this end, an enhanced measure called dynamic regret is proposed in the literature [Zhao al., 2022, Li et al., 2023], which benchmarks the learner's s policies against a sequence of changing policies. This measure is defined as
K
K
D-Regk (RRegK(Ti.)
Σ
VR. (SK.1)
E V (sk,1),
(2)
where .f...., T is any sequence of policies in the policy set that can be chosen with complete foreknowledge of online reward functions. The dynamic regret in (2) is a stronger notation as it
recovers the static regret in (1) directly by setting Tf.K arg max, Ek=1 (sx,)) An ideal dynamic regret bound should scale with a certain variation quantity of compared policies denoted by (x x or Px (ff....., xxx that can reflect the degree of environmental non-stationarity.
While the flexibility of dynamic regret makes it well-suited for adversarial settings, it also presents significant challenges. The dynamic regret of tabular MDPs with full-information feedback has been thoroughly studied by Zhao et al. [2022] and Li et al. [2024b], who achieved optimal dependence on K and PK for the known and unknown transition settings, respectively. without requiring prior knowledge of the non-stationarity measure. However, the dynamic regret of adversarial linear mixture MDPs still understudied. With the prior knowledge of the non-stationarity measure, Zhong et al. [2021] proposed policy optimization algorithm with the restart strategy [Zhao et al., 2020], achieving a result with suboptimal dependence in H. K and Px. Later, Li al. [2023] significantly improved their results by designing an algorithm with the optimal dynamic regret in K and Px. though the dependence on H remains suboptimal. For the more challenging scenarios where non-stationarity is unknown, Li et al. [2023] made an initial solution by introducing two-layer policy optimization algorithm, albeit with an additional term in the dynamic regret involving the switching number of the best base-learner. To address this limitation, Li et al. [2024b] developed an occupancy-measurg measure--ased algorithm with two-layer structure that achieves optimal dynamic regret in K and Pk. However, their result incurs polynomial dependence on the state space size S, which is statistically undesirable.
In this work, we propose an algorithm that achieves the near-optimal dynamic regret in d, H, K and Px simultaneously for adversarial linear mixture MDPs with the unknown transition, without prior knowledge of the -to-ssationarity measure. We begin with in-depth analyses of the strengths and limitations of two most popular methods: occupancy wawpney--mauueebiiieee based and posicy-based methods. We find that while the cecupancy-maauureeee environments, it encounter difficulties with the unknown transition. In contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non- stationary environments. To this end, we propose novel algorithm that combines the benefits of both
method effective in addressing the -tationao
2

---

methods. Specifically, our algorithm employs (i) an mecapancy-measure-bane global optimization with a two-layer framework to handle the non-stationary environments; and (ii) a policy-based variance-aware value-targeted regression to handle the unknown transition. We bridge these two parts through novel conversion. We show our algorithm achieves D(dvH*K (HK(H Pk)) ) dynamic regret and prove it is minimax optimal up to logarithmic factors by establishing a matching lower bound. Table 1 presents the comparison between our result and previous works. Our result surpasses all previous results, even those that require prior knowledge of the non-stationarity measure.
We note a similar combination was firstly employed in Ji et al. [2024], but for distinctly different purposes. In their work, the (independent of horizon length Hf static regret whereas our objective is to address non-stationary environments. One limitation of this hybrid approach is the computational complexity, which is dominated by the occupancy sccpancy-measuure bassdd component and thus expensive compared to policy-based method. This issue is the inherent challenge for occupancy-measure- bbasdre-bbadd method and also appears in several studies [Zhao et al., 2023, Ji et al., 2024]. Nevertheless, our analyses suggest that the occupancy- measure- anees method offers unique advantages in handling con-stationary environments. Investigating whether similar results can be attained by other computationally efficient methods is an important future work. We believe our work represents a significant step forward, as it is reasonable to prioritize achieving statistical optimality before focusing on computational efficiency.
maaeey--mmaau--asseeeeee component is used to provide a horizon- free
Organization. We review the related work in Section and formulates the setup in Section 3. We analyze the challenges and introduce our algorithm in Section 4 and present the dynamic regret in Section 5. Section 6 concludes the paper. Due to the page limits, we defer all proof's to the appendices.
Notations. We denote by [n] the set (1..... n and define [2](a.0] = min max(x; a), b}. For vector r E Rdd and positive semi-definite matrix E E RRddd define ||ar||æ: va T Ex. For policies x and n', define || - r'll 1, = max [|(s( x' r-(1ss]] The notation (-)) hides all polylogarithmic factors.
2 Related Work
In this section, we review related works on the dynamic regret of MDPs in non-stationary environ- ments. The studies can be divided into two lines: non-stationary stochastic MDPs and non-stationary adversarial MDPs. These two categories address distinct challenges and are studied separately.
Non-stationary Stochastic MDPs. Non-stationary stochastic MDPs address scenarios where tran- sitions and rewards are stochastically generated from varying distributions. The non-stationarity measure is typically defined as the total variation of the transitions or rewards over time. For infinite- horizon MDPs, the seminal work of Jaksch al. [2010] investigates the piecewise stationary setting where both the transitions and rewards are subject to changes at specific time and remain fixed in between. Ortner et al. [2019] further advance the field by allowing for changes every step. Subse- quently, Cheung et al. [2020] introduce the Bandit-over-RR RL algorithm, which addresses the limitations of earlier works by eliminating the need for prior knowledge about the non-stationarity. Additional advancements have been made in episodic non-stationary MDPs [Mao et al., 2021, Domingues et al., 2021] 1] and episodic non-stationary linear MDPs [Touati and Vincent, 2020, Zhou et al., 2022]. A breakthrough is the black-box box method by Wei and Luo [2021], which can transform any algorithm with the optimal static regret under certain conditions, into another one that achieves optimal dynamic regret without prior knowledge of the non-stationarity. However, this method is inapplicable in adver- sarial settings. The limitation arises from its dependence on an optimistic estimator, constructed via a Upper Confidence Bound (UCB) -based algorithm for environmental change detection, a technique that performs well in stochastic environments but is less effective in adversarial scenarios.
Non-stationary Adversarial MDPs. Non-stationary adversarial MDPs consider settings where the rewards are generated in an adversarial manner. The non-stationarity measure is defined as the variation of arbitrary changing compared policies, allowing the policy to adapt to non- non-stationary environments implicitly. An illustrative difference between non-stationary stochastic and adversarial MDPs is that, in some cases, even if the rewards and transitions change over time, the optimal policy may remain fixed, The dynamic regret of tabular MDPs with full-information feedback has been thoroughly studied by Zhao et al. [2022] and Li et al. [2024b], who achieved optimal dependence on K and Px for the known and unknown transition settings respectively, without requiring prior knowledge of the -tatiioninn measure. However, the dynamic regret of adversarial linear mixture
3

---

MDPs is still understudied. With the prior knowledge about the non -satsioonnartty measure, Zhong et al. [2021] proposed a policy optimization algorithm with restart strategy [Zhao al., 2020], achieving a result with suboptimal dependence in H, K and Px. Later, Li et al. [2023] significantly improved their results by designing an algorithm with optimal dynamic regret in terms of K and Pk. though the dependence on H remains suboptimal. For the more challenging scenarios where non-stationarity is unknown, Li et al. [2023] made an initial solution by introducing a two-layer policy optimization algorithm, albeit with an additional term in the dynamic regret involving the switching number of the best base-learner. To address this limitation, Li et al. [2024b] developed an occupancy-measure-buee basee algorithm with two-layer structure [Zhang et al., 2018, Yan al., 2023, Zhao et al., 2024] that achieves optimal dynamic regret in K and Pk- However, their dynamic regret incurs a polynomial dependence the state space size S, which is undesirable. In this work, we propose algorithm that achieves near-optimal dynamic regret in d, H, K and Pk simultaneously for adversarial linear mixture MDPs with the unknown transition, without prior knowledge of the non-stationarity measure.
3 Problem Setup
We focus on episodic MDPs with the unknown transition and adversarial reward functions in the full-information feedback setting. We introduce the problem formulation in the following.
Inhomogeneous, Episodic Adversarial MDPs. We denote an inhomogeneous, episodic adversarial MDP by tuple .M- = {S, A, H, (Pn) {TK,A keejk) where S is the state space with cardinality |S] = S, A is the action space with cardinality |A| = A, H is the length of each episode, is the transition with (s')ss ss, a) denoting the probability of transiting
Px(+):):: S Ax - [0,
to state s' given the state and action at stage h. and Tk.A S x A + [0, 1] is the reward function for episode k at stage h chosen by the adversary. A policy π = } is collection of h functions, where each nTy : S - ((A) maps a state s to a distribution over action space A. For any (s, a) E S x A, the state-action value function Q7 (s, a) and value function (s) are defined as:
Q (s, a) = E.g Σ TKE (SN, sh s, an. = a a
(1=) a)], (s) B.
where the expectation is taken over the randomness of and P. For any function V : S + R, we define [IP, a)- (.b,a (s')] and ((s) = V3), ((,
The interaction protocol is given as follows. At the beginning of episode k, the environment chooses the reward functions {Fe,A he([M] and decides the initial state sk,1, where the reward function may be chosen in an adversarial manner. Simultancously, the learner decides a policy TT { he(M-- Starting from the initial state 8h,1, the learner chooses an action 0g.h ~ ( obtains the reward A (sk,h, (k,A), and transits to the next state 8k,++1 PA (-]8k,,, (k,A) for h E [H] After the episode k ends, the learner observes the entire reward function {rK, hell]- The goal of the learner is to minimize the dynamic regret in (2). Denote by T = K H the total steps.
Linear Mixture MDPs. We focus on linear mixture MDPs, which was introduced by Ayoub et al. [2020] and has been studied by subsequent works [Cai et al., 2020, Zhou et al., 2021, Li et al., 2024c]. Definition 1 (Linear Mixture MDPs). An MDP M AS H, ( (rR.A)keTK),. (ee(k) 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 + d and an unknown vector 0% Rd with 10 S B, vh [H], such that (i) (s')sss,, |s, a) o(s' |s, a) T (ii) (s a)]ll & 1|Eves 0( s, V) (s)) S 1 for any (s, a) E S x A and any bounded function V S + 10.
Occupancy Measure. We introduce the concept of occupancy measure [Altman, 1998, Zimin and Neu, 2013]. Given policy and a transition IP, the occupancy measure is defined as the probability of visiting state-action-stale triple (s, a, s') under transition and policy π, that is,
(s, a, 5') = Pr(sa- = 5, an = a, sh+1 = 5' P.
valid occupancy measure q = {yn 1 satisfies the following properties. First, each stage is visited exactly once and thus vh. E [H], EEes Exe Eves th (s, 8') 1. Second, the probability of entering state when coming from the previous stage equals to the probability of leaving from
that state to the next stage, i.e., Vs S, E.Ea Eves as, = 1 $1} and 4h E [2, H].
4

---

EAEA Eves (s, EE''s EeEA 0h-1 a, s). For any occupancy measure satisfying the above two properties, induces transition 1 [Pr) and policy лº {mī} such that
Th (s, (s Ene 9n (s a, a.))) T ([((s))
En En' 4n d' Vs,, ES (
We denote by A the set of all occupancy measures satisfying the above two properties. For a transition P. denote by A(P) E the set of occupancy measures whose induced transition PP' is exactly P. For collection of transitions P. denote by A(P) A the set of occupancy measures whose induced transition 1a is in the transition set P. We 9k Th % q th to simplify the notation.
Non-stationarity measure. The non-stationarity measure aims to quantify the non-stationarity of the environments. We introduce two kinds of hon-stationarity measures widely used in the literature:
PK
TA-1o0 PK
Σ> 2=2h=1
qehh 11-1,A
(3)
They quantify the difference between the compared policies and the compared occupancy measures, respectively. Zhao et al. [2022, Lemma 6] show it holds that Pk I HPK. Thus, we focus on the Px-type upper bound in this work as it implies an upper bound in terms of HK directly.
4
The Proposed Algorithm
In this section, we first analyze the strengths and limitations of two most popular methods for adversarial MDPs. Then we propose novel algorithm that combines the benefits of both approaches.
4.1 Analysis of Two Popular Methods
meerrancy-maauue--aae and policy-based methods are the two most popular approaches for solvin solving adversarial MDPs. Both methods have been extensively studied in the literature and shown to enjoy favorable static regret guarantees [Zimin and Neu, 2013, Cai et al., 2020]. However, when it comes to dynamic regret, both methods face significant challenges. We introduce the details below.
4.1.1 Framework I: Occupancy-meeasure--naee Method
The first line of work [Zimin and Neu, 2013, Rosenberg and Mansour, 2019, Jin et al., 2020a] em- ployed the occupancy-mest weeraancc--muuueeeeee based method for adversarial MDPs. This method use the occupancy measure as proxy for the policy, optimizing over the occupancy measure rather than the policy di- rectly. While the value function is not convex in the policy space, it becomes convex in the occupancy measure space, making this approach theoretically more attractive compared to policy-based method. However, this shift introduces new challenges for dynamic regret analysis, as discussed below.
Using the concept of the occupancy measure, the dynamic regret in (2) can be rewritten as D-Regx(TTf.k) Ek= V (sK,1) Σ V (5 Σk Lo Qu, rk). By this conver- sion, the online MDP problem reduced to the standard online linear optimization problem over the occupancy measure set ((P) induced by the true transition P. However, the true transition P is unknown and thus the decision set ((P) is inaccessible. To address this issue, general idea is to construct confidence Pk at episode i that contains the true transition with high probability then replace the decision set by A (P&).. Then the dynamic regret can be decomposed into:
D-Reg (Tī.K) (
Σ l Qk, rk)
Σ
Lo 2k. Tk)
(gk
ak Tk),
D-Ragrat-01.
approximation-ee cn-
where dt is an occupancy measure in the decision set (Px)). The first term is the dynamic regret of online linear optimization over the decision set A ((P.), which has been explored in the known transition setting [Zhao et al., 2022]. This term can be well controlled by two-layer structure, as demonstrated in the online learning literature [Zhang al., 2018, Yan et al., 2023, Zhao et al., 2024].
5

---

The second term reflects the approximation enror introduced by using the confidence set Ps as surrogate for the true transition I., which constitutes the primary challenge of this approach.
Key Difficulties. To control the approximation error in (4), previous works [Rosenberg and Mansour, 2019, Jin et al., 2020a] proposed to bound the term Σ k= 1l [1ll1. leveraging Hölder's inequality: (Āk- 0k, rb) I [ 9s: 9 lr and rи E [0. 10.1] 1154. While this approach is effective for tabular MDPs, it fails to exploit the inherent structure of linear mixture MDPs. Although the transition kernel P exhibit a linear structure, the occupancy measure is not linear and retains complex recursive form, as highlighted in Zhao al. [2023]. Consequently, the regret bound resulting from this method depends on the state space size S, which is undesirable for linear mixture MDPs.
Remark 1. Eccupaney-measurre based method optimizes global object that encodes the entire policy across all states, which sacrifices some computational efficiency to better handle non-stationary environments. Thanks to their global optimization property, these methods offer favorable dynamic regret guarantees. However, they struggle to address the unknown transition in linear mixture MDPs and suffer from an undesirable dependence on the state space size S in the dynamic regret bound.
4.1.2 Framework II: Policy-based Method
Policy-based method directly optimizes the policy, making it easier to implement and computationally more efficient than occupancy-measure handling unknown transitions, as it only requires estimating the value function, bypassing the need to estimate the transition kernel explicitly. However, due their inherent local-search nature, this method faces challenges in adapting to non-stationary environments and providing favorable dynamic regret guarantees. We outline the key challenges below.
method. More importantly, shows advantages in
By the performance difference lemma [Kakade and Langford, 2002, Cai et al., 2020], the dynamic regret in (2) can be rewritten the following formulation:
K >E
D-Reg (Tf:K)
Eag (QEE :), TE T-,h(-1ss))]]]
(5)
where the expectation is taken over the changing policy sequence of, -.., T For each state 8h, the term Ek= Exz (QT, (Sh, TE, (-1x)) problem, with Q (Sh,,) being the "reward vector". Thus, it indicates the dynamic regret of online MDPs can be written as the weighted average of MAB dynamic regret over all states, where the weight for each state is its (unknown and time-varying) probability of being visited by -f,- T
> - T (-1s))) is exactly the regret of a A-armed bandit
Since the transition is unknown, the policy-based method need to estimate the value function QEA at each state. By the definition of lincar mixture MDPs in Definition 1, for any V., it holds that [P,, Ve, a) = (Øve. (s, a), 07)) Therefore, learning the underlying transition parameters 0% can be regarded as solving a "linear bandit" problem where the context is Φv, (Sk.A. ax.h) and the noise is VR.A+1 (Sk,A, a [PA, Vz, (...--)(ss.... ax,h). This observation enables the application of "linear bandits" techniques to learn the value function effectively for the policy- bbssed method.
The key challenge for the policy-based method lies in handling the non-stationarity of environment. Even with accurate estimates of Q at each state, optimizing the dynamic regret remains difficult. To optimize (5), Li et al. [2023] proposed running the Exp3 algorithm [Auer et al., 2002] at each state and employing the fixed-share technique [Herbster and Warmuth, 2001, -asa-Biinchi et al., 2012], forcing uniform exploration to deal with non-stationary environments. They update policies by
The (-Is) & TA exp (1 Qh-I)
(-Is) (1 - --)) (-1s) + +-lss-))),
where 7 is the step size, x (-1s) is uniform distribution, and y the fixed-share parameter. They show it ensures D-Reg (mf.x) S 0 H(1 + Px)/1). To achieve a favorable dynamic regret, the step size 7) needs to be set as v R (1+ Pk) H2), which is impractical as the non-stationarity measure Pk is unknown. The standard approach address this issue in the online learning literature is to adopt the online ensemble framework [Zhao et al., 2024]. However, this approach encounters challenges in online MDPs as the dynamic regret (5) involves the expectation of changing policies, which does not appear in the standard online learning setting. We elaborate on this issue below.
Specifically, the standard procedure of the two-layer framework is as follows. First, we construct a step size pool H. = {T/,..... } (N- = Olog K) )) to discretize the range of the optimal step size.

---

Subsequently, multiple base-learners Bi.... By are maintained, with each associated with step size 74 E H. Finally, meta-algorithm is employed to track the unknown best base-learner. Then, the dynamic regret can be decomposed into two parts: (i) the dynamic regret of the best base-learner, and (ii) the regret of the meta-algorithm to track the best-learner. Formally,
1277 (sh, F. (1sa())))))
Eng.
E02% (shs (ha((1)w) mm,n(-lsa))
baserregeet
ewlaringrat
Key Difficulties. Though the case-regret above involves the expectation of changing policies, it can be effectively controlled as the decomposition holds for any base-learner B,, allowing us to select the one with the optimal step size for analysis. However, controlling the meta-regret remains challenging as it still involves the expectation of changing policies and the optimal tuning is hindered.
Remark 2. By solely optimizing the policy at the visited states, the computational complexity of the policy-based based method is independent of the state number S, offering a notable advantage. However, due the non-stationary environments, more specifically, changing weights of different states, only caring about the visited states without considering their importance is not enough to achieve favorable dynamic regret. Thus, the local-search property enhances computational efficiency but poses difficulties in handling non- sta-ioationary environments. This reveals a significant trade-off between computational efficiency and the ability to manage non-stationary environments.
4.2 Our Method: A Novel Combination
By the analysis in Section 4.1, we observe that the pccupancy-measure- addressing non-stationary environments but shows limited compatibility with unknown transitions. In contrast, the policy-hased method can deal with unknown transitions efficiently but faces challenges in handling non-stationary environments. To this end, we propose a new algorithm named Occupancy- measure-based Optimization with Policy-based Estimation (OOPE), which combines the benefits of both methods. At high level, OOPE algorithm consists of two components: (i) occupancy- measure-bass -bsued global optimization with a two-layer framework to deal with the non-stationarity of environments; and (ii) a policy-based value-targeted regression to handle the unknown transition. We bridge the two components through novel analysis that converts the occupancy- meeppue approximation error into the policy-bast estimation error. We elaborate on the details below.
method is proficient in
4.2.1 Occupancy-measuree based Global Optimization
The saaeaancyymmauur--baaa optimization follows Li et al. [2024b], using online mirror descent for updating the occupancy measure and two-layer structure manage non-stationary environments.
We first construct a step size pool H = {71..... TN } to discretize the range of the optimal step size, then maintain multiple base-learners B Bi.... BN, each of which is associated with a step size m)s H. Finally, we use a meta-algorithm to track the best base-learner. At each episode k. we construct confidence set Cs such that 0% CR.AA with high probability. The details of the construction of confidence set will be introduced later. Then, the base-learner B, updates the occupancy measure by
dh arg max Th (q. rk) (4ll)))
(6)
(EA(Cz.O)
('(a,,,))) the KL-divergence and the decision set set as (CC,, a) = (Th E (a, 1)5a,, vh E [H] satisfies constraints (C1) and (C2)) where
where Delella') = Esa, ((s a, s') In a(s.a.6')
(C1): Σ a')) = 1(s = = V*
(s, Em(s,,,s) Σ @h-1 (s' v(s E S [2, M]:
a,
qn an (n(,a,,)))) = (p(. 1 8).
(C2) : ((E,,,)) E A H 38 E Ca.h:
The meta-algorithm updates weights by ph x ph- (xp(=((i
where E > is the learning rate. ( evaluates the performance of the base-learner B; at episode l - 1. The final occupancy measure is given by ÿe > P and the learner plays the policy th Algorithm I summarizes the details. We show it enjoys the following guarantee.
7

---

Algorithm OOPE
Algorithm 2 CompConfSet
Input: step size pool H. learning rate E, and
Input: Policy kk. trajectory Uk. and reward rk.
clipping parameter
1: for H, H 1, do
1: Set 0j (8, s') = 1/(SAS), (N].
2: Set Qk h (:,:) and V+, in (9).
2: Set pi 1/N,
[N].
3: Ex+1A f En,n + + o
3: for k == 1 K do
4: Det1, - 6y.h + T V (Sk,
4: Receive of. by (6) from B; for i [M]
5:
Σa+1A En, &RR I
5: Receive PkK from meta-algorithm by (7).
6: Compute q = > i= P.
6:
D by. + @k. V2. k (8k,
7: Play policy T = Th
7:
OK+1, Σx 2k+11 bR
8: Observe reward rs and trajectory Uk.
8: 0 < _ bat1,n.
9: C++1 + CompConfSet (Ta, Uk, rk)-
9:
Compute confidence set Cx+1 by (10).
end for
10:
end for
Lemma 1. Suppose 0% E Cr.b, Vk [K] E [H]. Set the clipping parameter a = 1/T2, the step
size pool as H = {m = 2 K- log 5 A/H) i [N]}, where N = [ log( 1+ 4K log 1, and the learning rate & = v Vllg N)/(HT). Algorithm ensures the following guarantee:
(og(S²A/H))
K
Lak qk, rk) < 0 (V log (52 + Px log7)) Σ
eecupancy-measuree measure- measure-based optimization with a two-layer structure, we can handle the first term in (4) well. It remains to bound the approximati mamaainn-eroorr term Σ which arises from employing the confidence set Cs as a surrogate for true transition parameter 0*
Remark By the occupancy
k= (0x Tk Tk),
The main computation complexity arises from the online mirror descent step of (6) in Line 4. This step can be divided into into unconstrained optimization problem and projection problem. The unconstrained optimization problem can solved by the closed-form solution and the main computational cost lies in the projection step. Ji et al. [2024] show that though such a projection can not be formulated as a linear program, they can efficiently solved by the Dysktra's algorithm the decision set is intersection of convex sets of explicit linear or quadratic forms. We refer the readers to Appendix
Implementation Details of Algorithm 1.
et al. [2024] for more details.
4.2.2 Occupancy Measure to Policy Conversion
As discussed in Section 1.1.1, previous works [Rosenberg and Mansour, 2019, Jin et al., 2020a, Li et al., 2024b] propose to control the approximation error by bounding the term Σ 1/ However, though the transition admits a linear structure, the occupancy measure does not and retains complex recursive form, which introduces undesired dependence on the state number S in the final regret. To take advantage of strength of policy-based method in integrating with linear function approximation, the occupancy measure discrepancies. This strategy diverges from traditional methods that bound (áx- 4k. rk) by the transition discrepancies Σ Σ. [+|s, a) Px a) where Iy is the estimated transition in episode k. Instead, we opt to constrain (qr- ạk, rι) through the value difference, which effectively integrates reward information. We introduce the details below.
qu 11
propose to learn value functions whole instead of directly controlling
Denote by (sk,)) Ems.. (s, a, "T (s, a) the expected reward given the occupancy measure Gk.h. Then, the approximation error can be rewritten as
K
Σ (0 ac rk) 1=1
Σ (Ve.(()e)) (o.1()))))
+
(i.I(Sk.)) V (sE,a))
(8)
occopancy-policy-ga
catimationnorrorr
where VA,1 is an intermediate value we define later. Our key idea is building optimistic estimator Vi.1 to ensure the first term is non-positive while controlling the second term. This bypasses the need to bound occupancy measure discrepancies, allowing to focus solely the value estimation error.

---

4.2.3 Policy-based Value-targeted Regression
remains to build the value function to ensure VE,A S Vi.A. A key observation is that the occupancy measure fs induces new MDP whose transition lies in the confidence set Cs with high probability. Thus, it suffices to ensure that Vi, is an overestimate of the true value function in the confidence set.
By the definition of linear mixture MDPs. for any V-)((-), it holds that [IPA V., a) = (Pv (s, 07) Thus, we compute the optimistic estimation as follows:
Qua(()))) - [r,,((s))+ + max (0, V..vv.ni [o.m! V-,a()) - (-doma.(())) DECE,
(9)
where CR.N the confidence set. We introduce the details of constructing the confidence set below.
Following recent advances in linear mixture MDPs [Zhou et al., 2021, He et al., 2022], we estimate the parameter Of by the weighted ridge regression to utilize the variance information. Denote by
DR.A. = ve (8k,,, hx and 0bC,,11 = =ΦV2 @V2 (8k,h, ag,A). We construct the estimator 0g.n as
Koo,n,0 0) VgA++ (8),++1)2 + 211012
bg = arg min BERA
j.
where 07,,, is the upper confidence bound the variance V (5n++1((8s,,. as,1) and set as o2. max /d, Vk. (sk,A, + where & V ( oR.b) is an estimate for the variance of value function Vi,A+1 under the transition (P (s,, ax), and Ex.a is the bonus term to guar- antee the true variance 1 ok upper bounded by [VA. VV.n+1l(ss,A ak.A) ER with high probability. By definition, have V V 1 aN ( 1, 0%) - I 07)
Thus, we set R, Vi. (Sk, ax,n) = [ (0, KO 2n 1k. where 0 is used to estimate the second-order moment and is constructed as:
0RL arg min
KK 0) 1 2l101
BER
The confidence set for the parameter 07 constructed as
CA,A (0 11 02, 3x).
(10)
where Ex, is covariance matrix, and By a radius of the confidence set. The algorithm is summarized in Algorithm 2. We show the approximation error is bounded as below.
Lemma 2. Set the parameters as follows:
a, = 8/ /d + k/A) log (4k2H/5) + 4v log (4R2 + VAB.
3x (tt/log(1++//// k/A) log (4/²H/0) + 4 (4k2 2k2211 11 + VAB,
3 2 / dlog (1 + kH+/(()) log 44k H/0) + 2 log (4k² H + VBB
Σ. min [12 21 | dr no |1, + min { 112 3R k
5-1/2
Φb I, }}
Algorithm 2 ensures with probubility at least - 6. it holds that
K
Σ
(āx Th, Tx) < (V@HH* vdHlk)
Remark 4. This bound can be further simplified as Õ(v Ö(vd² H3) when d 2 H, which is mild assumption. Following previous work [Zhou et al., 2021], we only discuss the case d 2 below.
Theoretical Guarantees
In this section, we present the dynamic regret upper bound and the lower bound for this problem.

---

5.1 Dynamic Regret Upper Bound and Lower Bound
The dynamic regret upper bound of our algorithm is guaranteed by the following theorem. Theorem 1. Set the parameters as in Lemma and Lemma Algorithm with Algorithm 2 as the subroutine ensures with probability at least 1 6. the dynamic regret is upper bounded by
D-Regg (Tix) S (
VHHSK + HKKH (H + Pk))
for known non- -on-staiionartty measure cases in Li et al. [2023], our bound has a better dependence on H. Compared with the dynamic regret of (dHSs V ++ (K 1 Pk)) for unknown non-stationarity measure cases in Li et al. [2024b], our bound removes the dependence on the state number S.
Remark S. Compared with the dynamic regret of ((vd' d + +
Then, we establish the dynamic regret lower bound for this problem.
Theorem 2. Suppose B 2 2, d 2 4, H 2 3, K 2 (d ( H22 for any algorithm and any constant E' [0, 2K HKH,, there exists an adversarial inhomogeneous linear mixture MDP and a policy sequence
-i:...,,T " such that Pk ST [ and D-Regx (πf.x) 2 22 + V /H + T))-
Remark 6. Combining Theorem and Theorem 2, our algorithm achieves the minimax optimal
dynamic regret in terms of d, H, K and Px simultaneously up logarithmie factors.
5.2 Proof Overview
We provide the proof sketch of Theorem 1. The detailed proof can be found in the appendixes. Proof Sketch (of Theorem 1). We can decompose the dynamic regret as the following four terms:
D- D-Regk (Tí:K)
Σ (ak Th rk)+
E ( 9k. Tk)
Vv.1
Ves11
Vi.1 Vili
base-ragrat.
mata-regrat
occupancy-poliey-ee
nat:iattion-arror
base-regret. By the analysis of OMD, can be upper bounded by Ô (n:KH (H pk)/ Choosing the base-learner with the best step size leads to upper bound of (OVKKH(B Pk)).
meta-regret. This term is the static regret of the expert-tracking problem. our meta-algorithm the Hedge algorithm, by the standard analysis, this term can be upper bounded by Ö(HVK) K).
secupancy-policy-een As the value functions are optimistic estimators over the confidence set Cs. the value gap between the occupancy measure and the policy is guaranteed to be non-positive.
estimation-error. Let E = Qu - -, and c = Vv,a VV. then define policy noise M = (+Ba)) (sk,,, a)] (sk,,, a..)), transition noise Ma,K,2 [P' (P) ag,h) V. R. (81,441) and bonus CA.A = Qu,a - (Fw. + IP 11. The estimation error can be decomposed into transition noises, policy noises, and bonuses, i.e., Ek= E + Ms.t.2 + (.,A). The transition and policy noises can be bounded by Ö(VK K3) using Azuma-Hoeffühe inequalities. The bonus term be bounded by Ö(vαHHK VdH*K) according to Lemma 2.
6 Conclusion and Future Work
In this work, we study the dynamic regret of adversarial linear mixture MDPs with the unknown transition. We observe the meeararc-- environments but struggles with unknown transitions. contrast, the policy- based method can deal with unknown transitions effectively but faces challenges in handling non-stationary environments. To this end, we propose a new algorithm that combines the benefits both methods, achieving an H(V + (HK(H + Pk)) dynamic regret without prior knowledge of the -on-stationarity measure. We show it is optimal up to logarithmic factors by establishing matching lower bound.
method is effective in addressing non-stationary
Currently, we achieve this result by employing a hybrid method. Exploring whether similar results can be attained using computationally more efficient methods is an important future work. Furthermore, extending our results to other MDP classes, such as generalized linear function approximation [Wang al., 2021] 1] and multinomial logit function approximation [Li et al., 2024a], is an interesting direction.
10

---

Acknowledgments
This research was supported by National Science and Technology Major Project (09000 and NSFC (62361 146852, 61921006).
References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NIPS), pages 2312-2322
2011.
Eitan Altman, Constrained Markov Decision Processes. Routledge, 1998.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-777 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. Proceedings of the 37th International Conference on Machine Learning (ICML), pages 463-474, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91(3): 325-349, 2013.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning (ICML), pages 2017. 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 1283-1294, 2020.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Nicolò Cesa-Bianchi, 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.
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.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. A kernel-based approach to non-stationary reinforcement learning in metric spaces. In Proceedings of the 24th International Conference Artificial Intelligence and Statistics (AISTATS), pages 3538-3546 2021.
Eyal Even-Dar, Sham. M. Kakade, and Yishay Mansour. Online Markov decision processes. Mathe- matics of Operations Research, pages 726-736. 2009.
Yoav Freund and Robert E. Schapire. A Decision-theorett generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-138) 1997.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted MDPs. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 19288-22308 2021.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Ncar-optimal policy optimization algorithms for learning adversarial linear mixture MDPs. In Proceedings the 25th International Conference Artificial Intelligence and Statistics (AISTATS), pages 4259-4280, 2022.
Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2): 151-178, 1998.
11

---

Mark Herbster and Manfred K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1:281-309, 2001.
Thomas Jaksch, Ronald Ormnr. and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, pages 1563-1600, 2010.
Kaixuan Ji, Qingyue Zhao, Jiafan He, Weitong Zhang, and Quanquan Gu. Horizon-free reinforcement learning in adversarial linear mixture MDPs. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems 31 (NeurfPS), pages 4868-4877 2018.
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 on Machine Learning (ICML), pages 4860-4869, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2137-2143, 2020b.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the 19th International Conference on Machine Learning (ICML), pages 267-274, 2002.
Jens Kober, J. Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. International Journal of Robotics Research, 32(11):1288-1774 2013.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Dynamic regret of adversarial linear mixture MDPs. In
Advances in Neural Information Processing Systems 36 (NeurIPS), pages 60685-60711 2023.
Long-Fei Li, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou, Provably efficient reinforcement learning with multinomial logit function approximation. In Advances in Neural Information Processing Systems 37 (NeurIPS), page to appear, 2024a.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Dynamic regret of adversarial MDPs with unknown transition and linear function approximation. In Proceedings of the 38th AAAI Conference Artificial Intelligence (AAAI), pages 13572-1358, 2024b.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Improved algorithm for adversarial linear mixture MDPs with bandit feedback and unknown transition. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3061-3069, 2024c.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Basar. Near-optimal model-free reinforcement learning in non-stationary episodic MDPs. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 7447-7458, 2021.
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Proceedings of the 35th Conference Uncertainty in Artificial Intelligence (UAI), pages 81-90, 2019.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35 (NeurIPS), pages 27730-27744, 2022.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference on Machine Learning (ICML., pages 3477-5486 2019.
12

---

David Silver. Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam,, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, llya Sutskever, Timothy P. Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, pages 484-489, 2016.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Ahmed Touati and Pascal Vincent. Efficient learning in non-stationary linear Markov decision processes, ArXiv preprint, arXiv:2010.12870 2020.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy, Optimism in rein- forcement learning with generalized linear function approximation. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Chen-Yo 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.
Yu-Hu Yan, Peng Zhao, and Hui-Hua Zhou. Universal online learning with gradient variations: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurlPS), pages 17762233775, 2023.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, pages 737-757, 2009.
Lijun Zhang. Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments, In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1344 1340, 2018.
Canzhe Zhao, Ruofeng Yang. Baoxiang Wang, and Shuai Li. Learning adversarial linear mixture Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 746 755, 2020.
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- 26894, 2022.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zui-Hua Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Han Zhong, Zhuoran Yang, Zhaoran Wang, and Csaba Szepesvári. Optimistic policy optimization is provably efficient in non-stationary MDPs. ArXiv preprint, 10.08944 2021.
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 (COLT), pages 4532-4576, 2021.
Huozhi Zhou, Jinglin Chen, Lav R. Varshney, and Ashish Jagmohan. Nonstationary reinforcement learning with linear function approximation. Transition on Machine Learning Research, 2022.
ISSN 2835-8856.
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

---

A Proof of Lemma 1
Proof. Without loss of generality, we assume that all states are reachable with positive probability under the uniform policy (a)s))) = 1/4, Vs E S.a E A. Otherwise, we can simply remove the unreachable states from the state space. Assume K is large enough such that the occupancy measure of of."" E APP, 1/T). We define v2 = ) of Tn E 1/T2). Then, can decompose the first term as
K
K
K
Σ
Qu, rk)
Σ
uk, Tk)
+
(u tx rk)
k=1
k=1
K
1
S a F.a" rrk) +
(2k
Gk: rk)
k=1
K
1
14A 9 p. "lll"alllllle
+
Σ
(ux
Tm)
T
1=1
k=1
$ 2 +
(uk 9k: T&))
k=1
K
2 +
(un
rk)
iss rk),
(11)
base-regret
nota-rogret
which the first inequality follows from Holder's inequality, the second holds by l1 - ---="" 1|1 S 2H, and the last holds for any [N]. Next, we bound base-regret and meta-regret separately.
Upper bound of base-regret. Since the true transition parameter 0* is contained in the confidence set Cs by condition, we ensure that uy E A (IP, 1/T²) (CCk, 1/T²). By the update rule of d in (6), we ensure that o (CC,, 1/T²), Vi [K]. The update rule in (6) can be rewritten as:
= arg max 77, (9. nk) (glllt)) HERS
Mh+1
arg min De (gll gEA(C,,.)
equivalently,
(s, = ( a, 8) exp(n:r(s,a)),
1 = min Do(allaee1). gEA(Cr,a)
By the three-point identity Lemma 9, we have
mluu gh. rk) (u De (ux (ut + D (o (1l199++1)
S (uv Dux (1) 11+ + De (9 (uxllatt))
(12)
where the inequality due to the Pythagorean theorem. For the last term of (12), summing over k2 we have
K
k=1
(((,,a,)( exp(ni((s,a))
8.0.5'
< HK,
(13)
where the first inequality is due to the fact ex - 1 S x for [0.
14

---

H (S For the first two terms of (12), by the definition of KL-divergence, we have
K
Σ k=1
(ux (8h) - Du Du(uull((+1))
K (us(ullltt) (ux-)=)ll))))
-Do(uilli))
k=2
K
uR, a, log "k,b(s,
2k -4-11(3,,, log "e-In(8,
-D((uil(()
(3,00,
s,0,s'
K H
1
+ (x(x) -D(uull(t)
(21)
- (x,2,((s,, log
Th (s,
Rm hmm s,a,8'
K
< Du(uullāi) + ((xx) - (((1) +2 T
(u,((s,a,s) - up u1,1n
8,0,5'
where the inequality holds by o E A(Px.1/T3) It remains to bound 4 and 17 separately.
For term It, since of minimize vi over A(PI, we have (Vv(H) u1 - Φ 2 0, thus,
4 S ((uk) ((() & Σ Σ
(s,,s, (s, S H log(s A).
(14)
A= sta.s
For term 12, for any (s, a). we have
Σ (u, a') ux 1,1 a, s')l )))= = Σ Uk (PP
s')
Σ (s.n - 4 (s
= (s, - (
Thus, we have
K H1
12 (s,n(s,a) un (1) ) -h-illi = (1 ) s Pk.
8,a
(15)
Combining (12), (13), (14) and (15), we have
K
base-regret S
Σ (Do(uillth
(ux lihh + (at
k=1
S n.T
(H log S2 22P log
is easy to verify that the optimal step size 17" V (H (og((S2 + 2Px log T)/T. Since
0 s Pk I 27, we ensure that
H (Sg(( + 4Tlog
T Snn
S
T
By the construction of the step size pool H (n 2 VK-VVK-Iaa (gg)
1 E [N]} with
1K log N = 1 [ log(1 + log(
)1, we know that the step size therein is monotonically increasing with
11 lS
H1 log( S2 (22A) 47 log
m
VN
T
15

---

Thus, we ensure there exists an index i" such that 7/ In S 217-- 41+ Since the decomposition
in (11) holds for any B, we choose B analyze the regret bound. By the definition of 17", we have
base-regret S 1/-
H log( 2 A) 2Px log
7/3-
2
S TT
H log S A) 2Pk log
3/ log( A) + 2Px log
(16)
where the last equality holds by substituting 1j" V (5 () + 2P log T//T.
Upper bound of meta-regret. Denote by hi = (4k Th) [0, H), we have
meta-regret Σ
Σ Pl rk)
Σ
(e: Pky hk),
where e, is the i-th standard basis vector TR- This is a standard Prediction with Expert Advice (PEA) problem and our algorithm is the well-known Hedge algorithm [Freund and Schapire, 1997, Herbster and Warmuth, 1998]. By the standard analysis of Hedge (Cesa-Biande and Lugosi, 2006, Theorem 2.2], have
log +eH V Ho
meta-regret S
(17)
where the equality holds by setting e = V(logN/HT) Combining (11), (16) and (17), we have
Σ (uh rx) 3 T( (o + 2Px log T) 2.
This finishes the proof.
B Proof of Lemma 2
In this section, we first provide the main proof of Lemma and then present the proofs of the auxiliary lemmas used in the main proof.
B.1
Main Proof
Proof. To prove Lemma 2, we first introduce the following lemma which shows the true parameter 0f is contained in the confidence set Cr.b with high probability by such configuration.
Lemma 3 (Zhou al. [2021, Lemma 5)). Let Ck be defined in (10) and set parameters in Lemma 2. Then, we have 8 E C. all E [H] and E [K] with probability at least 1 - 35.
Denote by & the event when Lemma 3 holds, then Pr(E) 2 1 36. We are ready to prove Lemma 2.
First, can rewrite the term 2k=1 (āx-
Eknn
T2: T4, Tk)
Σ (āu 9ko Tk)
(s,, Vsx.)
((.1(
+
(VoL(SH.1) -V (.
(18)
Next, we bound these two terms separately.
Upper bound of -ecupancy-tteraaioon-aa This term is the gap between the value function computed k- and the optimistic value function computed by backward iteration
by the occupancy measure {âx) } defined in (9). Similar to Ji et al. [2024, Lemma 6], show this term is non-positive.
16

---

Lemma 4. For any episode k E [K], define (1,1(
= Enear I.n a, a, s')rk,a(s,d) a) and (82,)) the value function computed in (9, on the event E, it holds that V2, (5K,1) - Vv, 1 (81,1).
Upper bound of estimation-error. First, we present the following lemma which shows this term can be decomposed into three major terms, transition noise, policy noise and the sum of bonuses.
Lemma 5. For all k E [K], h E [H]. it holds that
(LA Vi.h (sw,h) Σ
(MEN,1 Ma, (.N((
1/=
with
MI...1 Bownel 1 (Sk,h, (i,h( (Qu, Q.a. -K. (sH, ak,h));
Ma,b,2 (PA(Ve, Viaa 1 (5k,) ak.a) (Vi,n+I Re (S k
(.,(-,)) - Qu,((())) (r..(())))) 1
Note MRA,1 is the noise from the stochastic policy and MR, b,2 is the noise from the state transition, Let ME.A = ME.n.1 + Ma,A,, Ak E [K], h E [H], we define two following high probability events:
E
{ 4h E μMI ΣE k=
MaN I $4/ S log
H H 8..82
82
ΣΣ Ma.h. I / 88HHKK log
According to the Aizuma-Hofffuee inequality, we have Pr(Ei) 2 and Pr(E2) 2 1 - remains to bound the model prediction enror 4k,4-
Next, we show the prediction error depends on the width of the confidence set and the cumulative estimate variance by the following lemma.
Lemma 6. Define prediction error Lk.h =Qk,h - (FR.A + P.Va..41) on the event E, it holds that
K
H
K
H
(s ag,) S 23K
L V 2Hdlog( K/A).
Here, 2i, h is the estimated variance, for the total true variance introduce the high probability event Eg:
Σ k=1
VA h+1 (sk,,, at). we
Eg ΣΣ
< 3(H + 11 log(L/00)
k=1A=ı
Lemma C.5 Jin [2018] suggests that Pr(Ea) 2 Based on the events & & n n n we have the following lemma which bounds the estimated variance of the value function.
Lemma 7 (He et al. [2022, Lemma 6.5]). On the events & E n & E it holds that
K
2H*K k.
(4K2H
KH*
+ 179H + (165d H + 2062d H*) log²
log2
1
d
A
1=1
1=1
Combining Lemma 5, Lemma 6 and Lemma 7, we can bound the estimation-ems as follows.
Lemma 8. On the events E E n &s, for any h E [H], it holds that
Σ V..( - Σ (( SŌ(VaH< VOHIK)
Finally, we finish the proof of Lemma 2 by combining Lemma and Lemma 8.
17

---

B.2 Proofs of Auxiliary Lemmas
In this section, we proof the auxiliary lemmas used in the proof of Lemma Appendix B.I.
B.2.1 Proof of Lemma
Proof. The proof is similar to that of Ji et al. [2024, Lemma 6.1]. The only difference is that őu is weighted combination rather than single occupancy measure in the decision set. For k E [K], the occupancy measure ÿR is given by ÿR = Σn Pi Since o E A(Pk: we ensure that iN A(Pk,.)) Thus, for occupancy measure (u. there exist 0 such that
(8,0(8, a, (s Es, = (0(8'1s, a), A a)), M)s [M].
It is easy verify that the update rule (5K,)) Dh.s.. ( a ('),,, a) computed by the occupancy measure is the same the following backward iteration:
Qu, a) = (8) (DrEAn (8' a), (8, (s) = (1)
V =0
Then, we prove this lemma by induction. The conclusion trivially holds for n H 1. Suppose the statement holds for n h + 1, we prove it for n = h. For any (s, a) E S x A. since Qk, a) S 11, so if (s,n a) = H. then it holds directly. Otherwise, have
Qu. a) (s.a)
(s0 0s. + Blovv (8, 0)13 - -(0 (8'18, a). (x,((s,)) (dve. (8, 0r B11ov (s, o)ss (ove.tti (s' s) 02, (,
(dve (8, 0kh (s, a)) + 3l (8, (s,
2 B1lova (s,0)l 110u - 0n, a)ll lloven (s, a)lls
20.
where the first inequality holds by the inductive hypothesis, the second holds due to Holder's inequality, and the last holds due to (8, a) E Cr. By induction, finish the proof.
B.2.2 Proof of Lemma 5
Proof. By the definition (8. = Bawnel (ereeleeeeeeeeeeee (e.a)l a)). we have
(s,n() VAL (SR.))
= =Ep-re | (K. [Q,A a) - (sk, a)]
=EaNTe (- sA,N) (Kk,h a) Q7,, (sk ke a)]
(Qu. Q (sk, ak.h))
+ (QuA (k.h) - QT, (sK.,,
-E (L (Q,, a) Qha (sk, a)] (Qun(sk,h ak, Q (sk,h, ak.h)
+ (VK,
Th h.h (sk,h, akeh) + 4 (sk,h, ak.h)
= Earze(- ax.) 1v. - (sk, a)] (Qu. akN) - (st,, ac.))
SMK...1
+ PA
Vitk (2 (E.)) - (V..44((9R, (88,441) - V.h++ (BR,
AMe,n,
V vi I
1k (SK,,, ak,1)
where the third equality holds by the fact Qk. Tk, +P VA.PPPtttttaa and Q Tk. +PA V Summing up the above equation from h to H recursively finishes the proof.
k
18

---

B.2.3 Proof of Lemma 6
Proof.
By the definition of 44, = Qk, - (rk, + PA Vk,N+1), we have
(n,
= (ra,a + PAVEa+))(s,)))
=rk,h(s,a) (ee, (s..))) + 2
ov,,ti (rk, (s
= =(Ou. 0 15 (s,a)) 3x 1/11/ oVa,at (s, as)a)
S < |5 25 ov
(8.a)
where the first inequality holds by the configuration of Qu in (9), the second incquality holds by the definition of linear mixture MDP such that [P,,, (1).h+1((ss0)) (0Vr (s,a), a), 0%) and the last inequality holds by the construction of the confidence set in Lemma 3.
Then, have
Ukc (5k,h 0z,h)
K
H
2 2mi
1 [3x
1/2 ooann (8k,b, (x.1))12: H}
k= 1=
K
2BRō min {| 1/2
ovent (sk,h, ak.h) /onn
k= h=1
K
H
K
H
< 2βK
ΣΣ
min
| VVanat (8k,tr ak.h) 1 / l
J.h
K
H
S 2βK
Σ
Ze 2Hdlog(1 + K/A),
where the first inequality holds by Qu, [0, H). the second holds by 23 VdH/Va H. the third inequality is by Cauchy-Sehward inequality and the last incquality holds by the elliptical potential lemma in Lemma 10. This finishes the proof.
B.2.4
Proof of Lemma 8
Proof.
The proof can be obtained by combining Lemma 5, 6 and 7. Specifically, we have
(5k,))
VTT (sk.t)
K
H
<23x,
ReA V [ + +4 H*K log + 888K K log
8
1=
<ō(v (dddl + (&H33))
where the first inequality holds by Lemma 5 and Lemma 6 and the last inequality holds by Lemma 7. This finishes the proof.
C Proof of Theorem
Proof. Combining Lemma 1 and Lemma 2, we have
(ooon)=o(///i ( (S2 A) + Px logT)) -Ö(VHH*K VVHHK)
D-Regk (Tf.x) I
This finishes the proof.
19

---

D Proof of Theorem 2
Proof. Our proof is similar to that of Li et al. [2023, Theorem 4]. At a high level, 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, (ii) optimizing the dynamic regret of linear mixture MDPs with the known transition. Thus, we 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.
First, we consider the lower bound of the static regret of adversarial linear mixture MDPs with the unknown transition. From lower bound in He et al. [2022, Theorem 5.3], since the dynamic regret recovers the static regret by choosing the best-fixed policy, we have the following lower bound for dynamic regret in this case:
D-Regx (Ti:)) 2 O(VPHSK).
(19)
Then, we consider the lower bound of the dynamic regret of adversarial linear mixture MDPs with the known transition. Zimin and Neu [2013] show the lower bound of the static regret for adversarial episodic loop-free MDP with known transition is S2 H / K log (S))). We note that though our MDP model is different from the episodic loop-free MDP, we can treat our MDP model to the episodic loop-free MDP with expanded state space S' S x [H]. Thus, Q K log (SA)) is also lower bound of the static regret for the MDP in our work. We consider the following two cases:
Case 1: r < 2H. In this case, we can directly utilize the lower bound of static regret lower bound of dynamic regret, i.e.,
D-Regx(Ti.k) 2 S2(H / K log (SA)).
(20)
Case 2: I' > 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 L S H/2H times and the occupancy measure difference at each change point is at most 2H, the total path length in K episodes does not exceed r. As a result, we have
D-Reg (ffegg(f(.)) 2 LH HH//K/L log (SA) H /VK L log (SA) 2 ((VKHI log (SA)). (21)
Combining (20) and (21), we have the following lower bound for the dynamic regret of adversarial linear mixture MDPs with the known transition kernel,
D-Reg (Tf.K) 2 Ω( max [H / K log (SA), V KHT log (SA)))
Z SOVVKHCCC KH(H + D) (S)), where the last inequality holds by max b} 2 (a + b)/2.
(22)
Combining two lower bounds (19) and (22), we have the lower bound of the dynamic regret of adversarial linear mixture MDPs with the unknown transition kernel,
D-Reg (Ti.K) 2 2( max max(( VVHHK VKH(H- + 1) (og()))))
2 D(VPH'K (K (EHHHH+)))) +1) (SA)).
This finishes the proof.
E Supporting Lemmas
In this section, we introduce the supporting lemmas used in the proofs. Lemma 9 (Three-point identity). Let X be closed and convex set. For any E X and y, 2 E int X,, it holds that
Delx, v) + Delu, 2) Dp(a, =) (VV(2) x v)-
Lemma 10 (Abbasi- Yadkori al. [2011, Lemma 11D. Let {x be sequence in Rd space,
Vo = Al and define V, = Vo + Ei= xxx.T If 1|xxl122 - L, E Lz, then for each t E E.,
dd + AA+)
Σ min { 1, ||x||l < 2d
dA
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction provide a concise overview of the contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of this work in the introduction and conclusion
section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification:
We make no assumptions and provide proofs for all theoretical results in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is a theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
Pibllic/guidee//oeeSSbtmmi iosoo//eeeaamiiiiioooooooiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp..ccc ccppp.ccpppulcc///eecccc/ hwtpliiiiggiie./.ee/ee /CodeSubmia (isoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https htttps://neurre http///eurrrp.eeeee wwwppublcc/tchccsssuueeeeeeeee
Answer: [Yes]
Justification:
This paper adheres fully to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The goal of this paper is to advance the theoretical understanding RL, none societal impacts we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This is theoretical paper and does not release any data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This is theoretical paper and does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is theoretical paper and does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "md7cGRMHgj", "reviewer": "Reviewer_xu5Q", "summary": "Disclaimer: This specific area falls outside my expertise, as indicated by my confidence score. Nevertheless, I have carefully reviewed this paper and the relevant literature to offer the most informed feedback possible.\n\nThis paper studies the dynamic regret for adversarial linear mixture MDPs, with unknown transitions and full-information feedback. It introduces a hybrid algorithm that combines a policy-based variance-aware value target regression method [Zhou 2021] with the occupancy-measure based method [Li et. al. 2024a]. The authors provide the dynamic regret analysis of this hybrid algorithm, demonstrating its near-optimality up to logarithmic factors by showing both upper and lower bound. In particular, it removes dependence on the state number S from the prior result in Li et. al 2024a.", "questions": "In the weakness section, I noted my interpretation of the proposed algorithm. Could you elaborate if any new techniques are developed in this work? It will help me better understand the contributions of the work.\n\nCan you comment on the intuition of why it is possible to remove the dependence on S in the upper bound?", "limitations": "The introduction acknowledges the limitation of lower computational efficiency due to the occupancy measure based component. But I think that the additional assumptions regarding access to the oracle, introduced by algorithm 2, should be explicitly stated as a limitation.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It establishes a near-optimal dynamic regret for the first-time in its setting, improving over the results presented in [Li et al. 2024a],", "weaknesses": "1. I feel that the contributions of this paper could be highlighted better, given that the proposed algorithm involves various components from the literature. I’m not sure if I fully understand, but it seems that the main contribution lies more in the regret analysis rather than the algorithm itself. The proposed algorithm seems to be a combination of existing components from prior works [Li et. al 2024a and Zhou et al. 2021]. In particular, would it be fair to describe the proposed algorithm as Algorithm 1 in Li et. al 2024a, leveraging the techniques from UCRL-VTR+ [Zhou et. al 2021] to compute the confidence set, in place of the EstimateTransition routine in Algorithm 4 of Li et. al 2024a? \n2. The organization and the clarity of Section 3 can be improved to help with better understanding. Although Section 3.1 and 3.2 seem to aim to outline the pros and cons to motivate the proposed hybrid approach in Section 3.3, a more concise presentation could improve readability. Additionally, reordering 3.2 and 3.1 may better align with the flow in Sec. 3.3. \n3. The limitation of the work should explicitly mention the assumptions on access to the oracle in Algorithm 2. It’s a strong assumption and seems crucial in the ability to remove the dependence on the number of states S in the upper bound.\n\nMinor: typos noted below\n\nLine 243: The formula for KL-divergence\n\nLine 326: “Combinin”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful comments. We will address your questions below.\n\n---\n\n**Q1:** \"It seems that the main contribution lies more in the regret analysis rather than the algorithm itself. Could you elaborate if any new techniques are developed in this work?\"\n\n**A1:** Thanks for your question. Both the algorithm and the regret analysis are new and non-trivial. Even though one may feel the high-level algorithmic ideas are similar to previous works, *previous efforts failed to achieve optimal dynamic regret* due to the inherent limitations of two methodologies in dynamic regret analysis, as highlighted in Sec 3.1 and 3.2. Our primary technical contribution lies in **revealing a crucial yet underexplored connection between the two most popular methods**: the occupancy-measure-based approach and the policy-based approach. These two methods are widely used in the literature, but they are typically considered separately. So It was **only** after realizing that the two methodologies could complement each other, as we demonstrate, that the new algorithm and optimal dynamic regret could be achieved. We believe this optimal result is interesting and important for the community. Moreover, our technique for exploring the connection of two methodologies is novel and could be useful for broader problems in RL theory. We will emphasize this point more clearly in the revised version.\n\n---\n\n**Q2:** \"Can you comment on the intuition of why it is possible to remove the dependence on $S$ in the upper bound?\"\n\n**A2:** The key insight is that Li et al. (2024a) focus on the difference in occupancy measures (state-action distributions) between two policies, whereas we concentrate on the difference in their value functions (expected rewards). The value function difference can be much smaller than the difference between state-action distributions (e.g., when the rewards are all zeros, the value function differences are zero while the difference between state-action distributions can be arbitrary). This approach allows us to remove the dependence on $S$ in the upper bound. We will provide more intuition in the revised version. \n\n---\n\n**Q3:** \"Would it be fair to describe the proposed algorithm as ..\"\n\n**A3:** The main component of our algorithm is the occupancy-measure-based global optimization (Algorithm 1 in Li et. al 2024a) and the policy-based value-targeted regression (UCRL-VTR+ [Zhou et. al 2021]). However, the key insight is to combine these two methodologies in a novel way to achieve optimal dynamic regret. We connect the two methodologies by using the occupancy measure to policy conversion in Section 3.3.2, which is non-trivial and requires careful analysis. \n\n---\n\n**Q4:** \"The organization and the clarity of Section 3 can be improved to help with better understanding.\"\n\n**A4:** Thanks for the suggestion. We will reorder 3.2 and 3.1 to better align with the flow in Sec. 3.3 and present Section 3 more concisely.\n\n---\n\n**Q5:** \"The limitation of the work should explicitly mention the assumptions on access to the oracle in Algorithm 2 ...\"\n\n**A5:** We appreciate your observation. This assumption is not the reason for removing the dependence on $S$ in the upper bound. In fact, this is a standard assumption in the literature and has been used in **all** existing works on linear mixture MDPs (e.g., Zhou et al., 2021, He et al., 2022, Li et al., 2023). This assumption is just used to compute the $Q$-function by backward induction. The Oracle can be estimated by Monte Carlo methods in practice. We will clarify this point in the revised version. \n\n---\n\nWe hope our responses clarify the technical contributions and address your concerns. If your concerns have been addressed, we appreciate it if you could consider re-evaluating our work. \n\n**References:**\n\n[1] Zhou, D., Gu, Q., & Szepesvari, C., Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. In COLT'21.\n\n[2] He J., Zhou D., & Gu Q., Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. In AISTATS'22.\n\n[3] Li, L. F., Zhao, P., & Zhou, Z. H., Dynamic Regret of Adversarial Linear Mixture MDPs. In NeurIPS'23.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XLALKOw44t", "reviewer": "Reviewer_QFuD", "summary": "This work studies adversarial Linear Mixture MDPs, where the reward function can vary across different episodes, and aims to analyze the dynamic regret, where the baseline policy can also change across different episodes with respect to the dynamic environment. The authors propose a novel algorithm with a theoretical guarantee of the dynamic regret. In addition, the authors provide a hard-to-learn instance, which suggests that the regret guarantee cannot be improved by any algorithm.", "questions": "1.For the regret guarantee, why does there exist a $\\sqrt{HK \\cdot H}$ term? It is directly dominated by the first term $d\\sqrt{H^3K}$.\n\n2. The baseline policy $\\pi_k^c$ should be chosen with knowledge of the online reward function before episode $k$, , or it can depend on the future reward function until the end of episode $K$.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work provide a algorithm with theoretically guarantee for the dynamic regret with adversarial environment, which is strictly stronger guarantee than the previous static regret analysis.\n\n2. The authors provide a hard-to-learn instance, which suggests that the proposed algorithm has already achieved a near-optimal regret guarantee.\n\n3. This paper is well-written and easy to follow.", "weaknesses": "1. The proposed algorithm is computationally inefficient. Firstly, calculating the feature $\\phi{k,h}$ requires evaluating the value function over all possible next states. Secondly, the performance of the occupancy-measure-based method relies on solving a global optimization problem over all state-action pairs. For methods with linear function approximation, such state/action spaces are usually huge and require high computational costs in the previous two steps. Though this is a common issue in the analysis of linear mixture MDPs and occupancy-measure-based methods, it will still affect the impact of the proposed algorithm.\n\n2. There is a similar setting that also considers the dynamic regret guarantee (e.g., [1]) in a non-stationary environment. This non-stationary MDP setting measures the environment's dynamics by the difference between adjacent reward/transition functions. In contrast, this work measures the dynamics by the difference between adjacent policy/occupancy. It is better to make a comparison with this setting and previous results. Otherwise, it is challenging to compare fairly with previous work or evaluate the bound of the dynamic regret in this study.\n\n[1] Nonstationary Reinforcement Learning with Linear Function Approximation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We will address your questions below.\n\n---\n\n**Q1:** \"Why does there exist a $\\sqrt{HK \\cdot H}$ term in the regret bound? It is directly dominated by the first term $d\\sqrt{H^3K}$\"\n\n**A1:** Thanks for your careful observation. It is indeed directly dominated by the first term $d\\sqrt{H^3K}$. We present the regret bound in this form to highlight the key three terms for this problem: the first term $d\\sqrt{H^3K}$ represents the regret incurred from dealing with the unknown transition kernel, the second term $\\sqrt{HK \\cdot H}$ corresponds to the static regret when the environment is stationary, and the third term $\\sqrt{HK \\cdot P_K}$ captures the regret due to the non-stationarity of the environment. We will provide more intuition in the revised version.\n\n---\n\n**Q2**: \"The chosen of policy $\\pi_k^c$ ...\"\n\n**A2:** Yes, we can choose $\\pi_k^c$ *arbitrarily*, allowing it to depend on the future reward function until the end of episode $K$. Our algorithm does not require the knowledge of the compared policy $\\pi_k^c$ and our results hold universally for any sequence of compared policies. This flexibility enables our measure to adapt automatically to the non-stationary environment.\n\n---\n\n**Q3:** \"The proposed algorithm is computationally inefficient...\"\n\n**A3:** We note that no prior work has achieved optimal dynamic regret, even for computationally inefficient algorithms. Therefore, the most central problem in this area is determining the optimal statistical complexity and how to achieve it. We design an algorithm with optimal dynamic regret for the first time, along with a matching lower bound. This is achieved by revealing a crucial yet underexplored connection between the two most popular methodologies, which is crucial for our results and could be useful for broader problems in RL theory. As the reviewer noted, computational complexity is a common issue for algorithms in this area and thus beyond the scope of this work. Achieving both computational efficiency and statistical optimality is an important and challenging future work. Nevertheless, our work has already made a significant step in this direction.\n\n---\n\n**Q4:** \"There is a similar setting that also considers the dynamic regret guarantee (e.g., [1]) in a non-stationary environment.\"\n\n**A4:** Thanks for pointing out this work, which also addresses the non-stationarity issue in MDPs and is thus related to our research. We will make sure to add a discussion on the connection between our work and [1] in the next version. However, it's crucial to highlight that the setting and results of [1] is fundamentally different from ours:\n- They study non-stationary **stochastic** MDPs, where the reward is assumed to be stochastically generated by parametric models with parameters continuously drifting. For example, the reward function is $r_k(s, a) = \\theta_k^* \\phi(s, a)$, where $\\theta_k^*$ is drifting over time.\n- In contrast, we study non-stationary **adversarial** MDPs, allowing rewards adversarially chosen and do not make any stochastic assumption over the rewards. The objective is to be competitive with a sequence of time-varying compared policies.\n\nThe algorithmic approaches to handle non-stationarity are also significantly different. For stochastic MDPs, methods such as sliding windows, restarts, and weighting are used. For adversarial MDPs, we employ two-layer structures. The optimal dynamic regret results also differ: $O(B^{1/3} K^{2/3})$ for stochastic MDPs and $O(P_K^{1/2} K^{1/2})$ for adversarial MDPs.\n\nAn illustrative example highlighting the difference is when the difference between adjacent rewards scales linearly with time (i.e., $B=\\Theta(K)$) but the optimal policy remains the same ($P_K = 0$). In this case, [1] suffers linear dynamic regret, while our dynamic regret remains sublinear.\n\nTo summarize, the two settings and respective algorithms/results are incomparable. They can be viewed as two distinct models for non-stationary online MDPs.\n\n---\n\nWe hope our responses address your concerns. If your concerns have been addressed, we appreciate it if you could consider re-evaluating our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VABRK8QZIX", "reviewer": "Reviewer_PUu1", "summary": "The paper explores reinforcement learning in linear mixture Markov Decision Processes (MDPs) with adversarial rewards and unknown transitions. It analyzes policy-based and occupancy-measure-based methods, identifying their strengths and weaknesses. The paper introduced an algorithm that merges both approaches to achieve near-optimal dynamic regret, which is the first work that achieves this.", "questions": "None.", "limitations": "The authors discussed limitations of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a novel algorithm that combines the strengths of policy-based and occupancy-measure-based methods\n2. According to the authors, the paper achieves near-optimal dynamic regret for adversarial linear mixture MDPs, and is the first work that does this.\n3. The paper is presented nicely and compared to previous approaches", "weaknesses": "The paper lacks experimental validation, but could be reasonable given it is a theoretical paper. Intuitively it would not scale to complex high dimensional environments empirically if it were implemented into a practical algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We take this opportunity to highlight the key contributions of our work.\n\n---\n\n**Q1:** \"The paper lacks experimental validation, but could be reasonable given it is a theoretical paper...\"\n\n**A1:** The primary goal of this work is to advance the theoretical understanding of adversarial linear mixture MDPs. The optimal dynamic regret of adversarial linear mixture MDPs is a fundamental and open question in RL theory. We design an algorithm that achieves the optimal dynamic regret for the first time, along with a matching lower bound. This accomplishment is made possible by revealing a crucial yet underexplored connection between two popular methodologies. We believe that our work represents a significant step forward in this area and provides valuable insights for the community. Further experimental validation and implementation into practical algorithms is an interesting and important direction for future work, although it is beyond the scope of this paper.\n\n---\n\nWe are happy to provide clarification if you have any further questions. Thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "26ff6Gv4yi", "reviewer": "Reviewer_pW8k", "summary": "This paper studies the adversarial MDPs, which assume unknown (but stochastic) transition models and adversarial rewards. This paper adopts the linear mixture MDP setting, and they aim to study the dynamic regret, where the comparison policy are allowed to be changed along $K$ steps.\n\nThe algorithm this paper proposed is a combination of policy optimization with exponential weights and online mirror descent. In the meantime, the mirror descent constraint set is updated according to the value target regression framework. This algorithm adopts the merits of both policy optimization and online linear optimization, and achieves optimal rate of regret.", "questions": "I have the following questions for the authors:\n\n1. Does the algorithm apply to other type of non-stationary measures, e.g. switching cost, etc?\n\n2. The lower bound presented in this paper is a constructive lower bound. Can you obtain instance dependent lower bound (given any the transition model, to obtain a lower bound adapts to the transition model)?", "limitations": "Yes. The authors addressed all the limitations listed in the guidelines.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is well written. The algorithm, propositions and theorems are presented clearly. \n\nFrom technical side, the algorithm is computationally efficient and very simple. The regret of the algorithm matches the lower bound as well.", "weaknesses": "All techniques used in this paper are existed in previous works. Apart from this, I don't see significant drawbacks in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation of our work! We will address your questions below.\n\n---\n\n**Q1:** \"Does the algorithm apply to other types of non-stationary measures, e.g. switching cost, etc?\"\n\n**A1:** Thanks for your helpful question. Our algorithm can also be adapted to other types of non-stationary measures, such as the generalized path-length described by Hall & Willett (2013). This measure is defined as $P_K^\\prime = \\sum_{k=2}^K \\sum_{h=1}^H \\| q_{k,h}^c - \\Phi_{k,h}(q_{k-1,h}^c) \\|$, where $\\Phi_{k,h}(\\cdot)$ is a known dynamic model. When $\\Phi_{k,h}(\\cdot)$ is an identity function, this measure reduces to the path-length we used. \n\nThe advantage of this generalized path-length measure is that it allows us to incorporate prior knowledge of the environment's non-stationarity into the dynamic model. If the dynamic model can predict the environment perfectly, (e.g., $q_{k,h}^c = \\Phi_{k,h}(q_{k-1,h}^c)$), the generalized path-length $P_K^\\prime$ will be zero, much smaller than the traditional path-length $P_K$. This capability can significantly enhance the performance of our algorithm in environments where the non-stationarity can be accurately modeled.\n\nAs we focus on the basic setting to present our main results more clearly, we did not include this extension in the current version. We will include a discussion of this extension in the revised version to highlight the flexibility and applicability of our algorithm to various non-stationary measures.\n\n---\n\n**Q2:** \"Can you obtain instance dependent lower bound?\"\n\n**A2:** Thank you for your insightful questions. Obtaining an instance-dependent lower bound is indeed an interesting and challenging problem. To the best of our knowledge, there is no existing instance-dependent lower bound that directly depends on the transition kernel, even for static regret. The main difficulty lies in identifying a suitable quantity (such as max/min value, rank, etc.) of the transition kernel that accurately characterizes the problem's hardness. \n\nThere are other types of instance-dependent lower bounds in the literature, such as those that depend on the optimal value function. However, obtaining such a lower bound is more difficult than deriving a worst-case lower bound, which is already a challenging and open problem. We believe that achieving an instance-optimal dynamic regret is an exciting direction for future research, and our work represents a significant step toward this goal.\n\n---\n\n**Q3:** \"All techniques used in this paper exist in previous works.\"\n\n**A3:** Indeed, the high-level algorithmic ideas in our work exist in previous works. However, previous efforts failed to achieve optimal dynamic regret due to the inherent limitations of two methodologies in dynamic regret analysis, as highlighted in Sec 3.1 and 3.2. It was only after realizing that the two methodologies could complement each other, as we demonstrate, that optimal dynamic regret could be achieved. One of our technical contributions lies in revealing this crucial yet underexplored connection between the two most popular methods. We believe this optimal result is interesting and important for the community. Moreover, our technique for exploring the connection of two methodologies could be useful for broader problems in RL theory. \n\n---\nWe hope our responses address your concerns. We are happy to provide further clarification if needed. Thanks!\n\n---\n\n**References:**\n\n[1] Hall, E. C., & Willett, R. M., Dynamical models and tracking regret in online convex programming. In ICML'13.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In the challenging setting of linear-mixture MDPs with adversarial rewards and unknown transitions, this paper presents a new algorithm that combines the advantages of policy-based and occupancy-based approaches. The authors prove that the algorithm is near optimal, the first such result for this setting.

The reviewers agree that the improvement over the state of the art is significant and that the paper is well written. Several points were clarified in the discussion phase, most importantly: the importance of the algorithmic contribution, the role of the assumptions, the main proof idea that led to the theoretical improvement, computational efficiency, and differences w.r.t. previous work studying dynamic regret in a similar setting.

In recommending acceptance, I stress the importance of incorporating the clarifications provided to reviewers in the camera ready version.
Decision: Accept (poster)