Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs

Authors: long-fei  li
peng  zhao
zhi-hua  zhou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:54:07

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.

Main paper: 
 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 et 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 be broadly divided into two lines based 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 a fixed distribution. In many real-world scenarios, 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] .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 (NeurIPS 2024).Table 1 : Comparisons of dynamic regret guarantees with previous works studying adversarial linear mixture MDPs with the unknown transition and full-information feedback. Here, d is the feature mapping dimension, H is the episode length, K is the number of episodes, P K and PK are two kinds of non-stationarity measure defined in (3) satisfying PK ≤ HP K [Zhao et al., 2022, Lemma 6] .Dynamic Regret P K or PK Zhong et al. [2021] O dH 7/4 K 3/4 + H 2 K 2/3 P 1/3 K Known Li et al. [2023] O d √ H 3 K + H 2 (K + P K )(1 + P K ) Known Li et al. [2024b] O dHS √ K + HK(H + PK ) UnknownUpper Bound (Theorem 1) O d √ H 3 K + HK(H + PK ) UnknownLower Bound (Theorem 2) Ω d √ H 3 K + HK(H + PK ) / learner's policies π 1 , . . . , π K against the best-fixed policy in hindsight, namely,EQUATIONwhere V π k,1 (s k,1 ) is the expected cumulative reward of policy π starting from initial state s k,1 at episode k and Π is the policy set. While static regret is a natural choice for online MDPs, the bestfixed policy may perform poorly when the rewards change adversarially. To this end, an enhanced measure called dynamic regret is proposed in the literature [Zhao et al., 2022 , Li et al., 2023] , which benchmarks the learner's policies against a sequence of changing policies. This measure is defined asEQUATIONwhere π c 1 , . . . , π c K 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 π c 1:K ∈ arg max π∈Π K k=1 V π k,1 (s k,1 ). An ideal dynamic regret bound should scale with a certain variation quantity of compared policies denoted by P K (π c 1 , . . . , π c K ) or PK (π c 1 , . . . , π c K ) 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 is still understudied. With the prior knowledge of the non-stationarity measure, Zhong et al. [2021] proposed a policy optimization algorithm with the restart strategy [Zhao et al., 2020] , achieving a result with suboptimal dependence in H, K and P K . Later, Li et al. [2023] significantly improved their results by designing an algorithm with the optimal dynamic regret in K and P K , 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-based algorithm with two-layer structure that achieves optimal dynamic regret in K and PK . However, their result incurs a 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 PK simultaneously for adversarial linear mixture MDPs with the unknown transition, without prior knowledge of the non-stationarity measure. We begin with in-depth analyses of the strengths and limitations of two most popular methods: occupancy-measure-based and policy-based methods. We find that while the occupancy-measure-based method is effective in addressing the non-stationary 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 nonstationary environments. To this end, we propose a novel algorithm that combines the benefits of both methods. Specifically, our algorithm employs (i) an occupancy-measure-based 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 a novel conversion. We show our algorithm achieves an O(d √ H 3 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 occupancy-measure-based component is used to provide a horizon-free (independent of horizon length H) 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-measure-based component and thus expensive compared to policy-based method. This issue is the inherent challenge for occupancy-measure-based method and also appears in several studies [Zhao et al., 2023 , Ji et al., 2024] . Nevertheless, our analyses suggest that the occupancy-measure-based method offers unique advantages in handling non-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.Organization. We review the related work in Section 2 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 proofs to the appendices.Notations. We denote by [n] the set {1, . . . , n} and define[x] [a,b] = min{max{x, a}, b}. For vector x ∈ R d and positive semi-definite matrix Σ ∈ R d×d , define ∥x∥ Σ = √ x ⊤ Σx. For policies π and π ′ , define ∥π -π ′ ∥ 1,∞ = max s ∥π(•|s) -π ′ (•|s)∥ 1 . The notation O(•) hides all polylogarithmic factors. 
related work: 
 In this section, we review related works on the dynamic regret of MDPs in non-stationary environments. 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 transitions 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 infinitehorizon MDPs, the seminal work of Jaksch et 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 at every step. Subsequently, Cheung et al. [2020] introduce the Bandit-over-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] and episodic non-stationary linear MDPs [Touati and Vincent, 2020, Zhou et al., 2022] . A breakthrough is the black-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 adversarial 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-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 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 is still understudied. With the prior knowledge about the non-stationarity measure, Zhong et al. [2021] proposed a policy optimization algorithm with restart strategy [Zhao et al., 2020] , achieving a result with suboptimal dependence in H, K and P K . Later, Li et al. [2023] significantly improved their results by designing an algorithm with optimal dynamic regret in terms of K and P K , 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-based algorithm with two-layer structure [Zhang et al., 2018 , Yan et al., 2023 , Zhao et al., 2024] that achieves optimal dynamic regret in K and PK . However, their dynamic regret incurs a polynomial dependence on the state space size S, which is undesirable. In this work, we propose an 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. 
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 a tupleM = {S, A, H, {P h } h∈[H] , {r k,h } k∈[K],h∈[H] },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,P h (•|•, •) : S × A × S → [0, 1]is the transition with P h (s ′ |s, a) denoting the probability of transiting to state s ′ given the state s and action a at stage h, and r k,h : S × A → [0, 1] is the reward function for episode k at stage h chosen by the adversary. A policy π = {π h } H h=1 is a collection of h functions, where each π h : S → ∆(A) maps a state s to a distribution over action space A. For any (s, a) ∈ S × A, the state-action value function Q π k,h (s, a) and value function V π k,h (s) are defined as:Q π k,h (s, a) = E π H h ′ =h r k,h ′ (s h ′ , a h ′ ) s h = s, a h = a , V π k,h (s) = E a∼π h (•|s) [Q π k,h (s, a)],where the expectation is taken over the randomness of π and P. For any function V : S → R, we define[P h V ](s, a) = E s ′ ∼P h (•|s,a) [V (s ′ )] and [V h V ](s) = [P h V 2 ](s, a) -([P h V ](s, a)) 2 .The interaction protocol is given as follows. 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 = {S, A, H, {P h } h∈[H] , {r k,h } k∈[K],h∈[H]} is called an inhomogeneous, episode B-bounded linear mixture MDP, if there exist a known feature mapping ϕ(s ′ |s, a) : S × A × S → R d and an unknown vectorθ * h ∈ R d with ∥θ * h ∥ 2 ≤ B, ∀h ∈ [H], such that (i) P h (s ′ |s, a) = ϕ(s ′ |s, a) ⊤ θ * h , (ii) ∥ϕ V (s, a)∥ 2 ≜ ∥ s ′ ∈S ϕ(s ′ |s, a)V (s ′ )∥ 2 ≤ 1 for any (s, a) ∈ S × A and any bounded function V : S → [0, 1].Occupancy Measure. We introduce the concept of occupancy measure [Altman, 1998, Zimin and Neu, 2013] . Given a policy π and a transition P, the occupancy measure q is defined as the probability of visiting state-action-state triple (s, a, s ′ ) under transition P and policy π, that is,q P,π h (s, a, s ′ ) = Pr[s h = s, a h = a, s h+1 = s ′ | P, π].A valid occupancy measure q = {q h } H h=1 satisfies the following properties. First, each stage is visited exactly once and thus ∀h ∈ [H], s∈S a∈A s ′ ∈S q h (s, a, s ′ ) = 1. Second, the probability of entering a state when coming from the previous stage equals to the probability of leaving from that state to the next stage, i.e., ∀s ∈ S, a∈A s ′ ∈S q 1 (s, a, s ′ ) = 1{s = s 1 } and ∀h ∈ [2, H], a∈A s ′ ∈S q h (s, a, s ′ ) = s ′′ ∈S a∈A q h-1 (s ′′ , a, s). For any occupancy measure q satisfying the above two properties, it induces a transition P q = {P q h } H h=1 and a policy π q = {π q h } such thatP q h (s ′ |s, a) = q h (s, a, s ′ ) s ′′ q h (s, a, s ′′ ) , π q h (a|s) = s ′ q h (s, a, s ′ ) a ′ ,s ′ q h (s, a ′ , s ′ ) , ∀(s, a, s ′ , h) ∈ S × A × S × [H].We denote by ∆ the set of all occupancy measures satisfying the above two properties. For a transition P, denote by ∆(P) ∈ ∆ the set of occupancy measures whose induced transition P q is exactly P. For a collection of transitions P, denote by ∆(P) ∈ ∆ the set of occupancy measures whose induced transition P q is in the transition set P. We use q k = q P,π k , q c k = q P,π c k 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 non-stationarity measures widely used in the literature:EQUATIONThey quantify the difference between the compared policies and the compared occupancy measures, respectively. Zhao et al. [2022, Lemma 6] show it holds that PK ≤ HP K . Thus, we focus on the PK -type upper bound in this work as it implies an upper bound in terms of HP K directly. 
the proposed algorithm: 
 In this section, we first analyze the strengths and limitations of two most popular methods for adversarial MDPs. Then we propose a novel algorithm that combines the benefits of both approaches.Occupancy-measure-based and policy-based methods are the two most popular approaches for 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.The first line of work [Zimin and Neu, 2013 , Rosenberg and Mansour, 2019 , Jin et al., 2020a] employed the occupancy-measure-based method for adversarial MDPs. This method use the occupancy measure as a proxy for the policy, optimizing over the occupancy measure rather than the policy directly. 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 asD-Reg K (π c 1:K ) = K k=1 V π c k k,1 (s k,1 ) - K k=1 V π k k,1 (s k,1 ) = K k=1 ⟨q c k -q k , r k ⟩.By this conversion, the online MDP problem is 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, a general idea is to construct a confidence set P k at episode k that contains the true transition with high probability then replace the decision set by ∆(P k ). Then the dynamic regret can be decomposed into:EQUATION)where qk is an occupancy measure in the decision set ∆(P k ). The first term is the dynamic regret of online linear optimization over the decision set ∆(P k ), which has been explored in the known transition setting [Zhao et al., 2022] . This term can be well controlled by a two-layer structure, as demonstrated in the online learning literature [Zhang et al., 2018 , Yan et al., 2023 , Zhao et al., 2024] .The second term reflects the approximation error introduced by using the confidence set P k as a surrogate for the true transition P, 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 k=1 ∥q k -q k ∥ 1 , leveraging Hölder's inequality:⟨q k -q k , r k ⟩ ≤ ∥q k -q k ∥ 1 ∥r k ∥ ∞ and r k ∈ [0, 1] SA .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 a complex recursive form, as highlighted in Zhao et 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. Occupancy-measure-based method optimizes a 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.Policy-based method directly optimizes the policy, making it easier to implement and computationally more efficient than occupancy-measure-based method. More importantly, it shows advantages in handling unknown transitions, as it only requires estimating the value function, bypassing the need to estimate the transition kernel explicitly. However, due to 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.By the performance difference lemma [Kakade and Langford, 2002, Cai et al., 2020] , the dynamic regret in (2) can be rewritten as the following formulation:EQUATIONwhere the expectation is taken over the changing policy sequence π c 1 , . . . , π c K . For each state s h , the termK k=1 H h=1 ⟨Q π k,h (s h , •), π c k,h (•|s h ) -π k,h (•|s h )⟩ is exactly the regret of a A-armed bandit problem, with Q π k k,h (s h ,•) 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 π c 1 , . . . , π c K . Since the transition is unknown, the policy-based method need to estimate the value function Q π k k,h at each state. By the definition of linear mixture MDPs in Definition 1, for any V k,h (•), it holds that[P h V k,h+1 ](s, a) = ⟨ϕ V k,h+1 (s, a), θ * h ⟩.Therefore, learning the underlying transition parameters θ * h can be regarded as solving a "linear bandit" problem where the context is ϕV k,h+1 (s k,h , a k,h ) and the noise is V k,h+1 (s k,h , a k,h ) -[P h V k,h+1 ](s k,h , a k,h). This observation enables the application of "linear bandits" techniques to learn the value function effectively for the policy-based method.The key challenge for the policy-based method lies in handling the non-stationarity of environment.Even with accurate estimates of Q π k k,h 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, Cesa-Bianchi et al., 2012] , forcing uniform exploration to deal with non-stationary environments. They update policies byπ ′ k,h (•|s) ∝ π k-1,h (•|s) exp η • Q π k-1 k-1,h (s, •) , π k,h (•|s) = (1 -γ)π ′ k,h (•|s) + γπ u (•|s), where η is the step size, π u (•|s) is uniform distribution, and γ is the fixed-share parameter. They show it ensures D-Reg K (π c 1:K ) ≤ O(ηKH 3 + H(1 + P K )/η). To achieve a favorable dynamic regret, the step size η needs to be set as η ≈ (1 + P K )/(KH 2 ), which is impractical as the non-stationarity measure P K is unknown. The standard approach to 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 in (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 = {η 1 , . . . , η N } (N = O(log K)) to discretize the range of the optimal step size.Subsequently, multiple base-learners B 1 , . . . , B N are maintained, with each associated with a step size η i ∈ H. Finally, a 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,K k=1 E π c k H h=1 ⟨Q π k k,h (s h , •), π c k,h (•|s h ) -π i k,h (•|s h )⟩ base-regret + K k=1 E π c k H h=1 ⟨Q π k k,h (s h , •), π i k,h (•|s h ) -π k,h (•|s h )⟩ meta-regret .Key Difficulties. Though the base-regret above involves the expectation of changing policies, it can be effectively controlled as the decomposition holds for any base-learner B i , 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 method is independent of the state number S, offering a notable advantage. However, due to 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-stationary environments. This reveals a significant trade-off between computational efficiency and the ability to manage non-stationary environments.By the analysis in Section 4.1, we observe that the occupancy-measure-based method is proficient in addressing non-stationary environments but shows limited compatibility with unknown transitions. In contrast, the policy-based method can deal with unknown transitions efficiently but faces challenges in handling non-stationary environments. To this end, we propose a new algorithm named Occupancymeasure-based Optimization with Policy-based Estimation (OOPE), which combines the benefits of both methods. At a high level, OOPE algorithm consists of two components: (i) an occupancymeasure-based 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 a novel analysis that converts the occupancy-measure-based approximation error into the policy-based estimation error. We elaborate on the details below.The occupancy-measure-based optimization follows Li et al. [2024b] , using online mirror descent for updating the occupancy measure and a two-layer structure to manage non-stationary environments.We first construct a step size pool H = {η 1 , . . . , η N } to discretize the range of the optimal step size, then maintain multiple base-learners B 1 , . . . , B N , each of which is associated with a step size η i ∈ H. Finally, we use a meta-algorithm to track the best base-learner. At each episode k, we construct a confidence set C k such that θ * h ∈ C k,h with high probability. The details of the construction of confidence set will be introduced later. Then, the base-learner B i updates the occupancy measure byEQUATIONwhere D ψ (q∥q ′ ) = s,a,s ′ q(s, a, s ′ ) ln q(s,a,s ′ ) q ′ (s,a,s ′ ) is the KL-divergence and the decision set is set as∆(C k , α) = {q h ∈ [α, 1] S 2 A , ∀h ∈ [H] | q satisfies constraints (C1) and (C2)} where (C1) : a,s ′ q1(s, a, s ′ ) = 1{s = s k,1 }, ∀s ∈ S; a,s ′ q h s, a, s ′ = a,s ′ q h-1 s ′ , a, s ∀(s, h) ∈ S × [2, H]; (C2) : ∀(s, a, h) ∈ S × A × [H], ∃θ ∈ C k,h , q h (s, a, •) s ′ q h (s, a, s ′ ) = ⟨ϕ(• | s, a), θ⟩.The meta-algorithm updates weights byEQUATIONwhere ε > 0 is the learning rate, ⟨q i k-1 , r k-1 ⟩ evaluates the performance of the base-learner B i at episode k -1. The final occupancy measure is given by qk = N i=1 p i k qi k and the learner plays the policy π qk . Algorithm 1 summarizes the details. We show it enjoys the following guarantee.Algorithm 1 OOPE Input: step size pool H, learning rate ε, and clipping parameter α.1: Set qi 1,h (s, a, s ′ ) = 1/(SAS), ∀i ∈ [N ]. 2: Set p i 1 = 1/N, ∀i ∈ [N ]. 3: for k = 1 to K do 4:Receive qi k by (6) from B i for i ∈ [N ].Receive p k from meta-algorithm by (7).6:Compute qk = N i=1 p i k qi k . 7:Play policy π k = π qk .8:Observe reward r k and trajectory U k . 9:C k+1 ← CompConfSet (π k , U k , r k ). 10: end for Algorithm 2 CompConfSet Input: Policy π k , trajectory U k , and reward r k . 1: for h = H, H -1, • • • , 1 do 2: Set Q k,h (•, •) and V k,h (•) as in (9). 3: Σ k+1,h ← Σ k,h + σ-2 k,h ϕ k,h,0 ϕ ⊤ k,h,0 . 4: b k+1,h ← b k,h + σ-2 k,h ϕ k,h,0 V k,h+1 (s k,h+1).5:Σ k+1,h ← Σ k,h + ϕ k,h,1 ϕ ⊤ k,h,1 . 6: b k+1,h ← b k,h + ϕ k,h,1 V 2 k,h+1 (s k,h+1).7:θ k+1,h ← Σ -1 k+1,h b k+1,h . 8: θ k+1,h ← Σ -1 k+1,h b k+1,h . 9:Compute confidence set C k+1 by (10). 10: end forLemma 1. Suppose θ * h ∈ C k,h , ∀k ∈ [K], h ∈ [H].Set the clipping parameter α = 1/T 2 , the step size pool asH = {η i = 2 i-1 K -1 log(S 2 A/H) | i ∈ [N ]}, where N = ⌈ 1 2 log(1+ 4K log T log(S 2 A/H))⌉+ 1, and the learning rate ε = (log N )/(HT ). Algorithm 1 ensures the following guarantee:K k=1 ⟨q c k -qk , r k ⟩ ≤ O T (H log (S 2 A) + PK log T ) .Remark 3. By the occupancy-measure-based optimization with a two-layer structure, we can handle the first term in (4) well. It remains to bound the approximation-error term K k=1 ⟨q k -q k , r k ⟩, which arises from employing the confidence set C k as a surrogate for true transition parameter θ * .Implementation Details of Algorithm 1. The main computation complexity arises from the online mirror descent step of (6) in Line 4. This step can be divided into into an unconstrained optimization problem and a projection problem. The unconstrained optimization problem can be 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 be efficiently solved by the Dysktra's algorithm as the decision set is an intersection of convex sets of explicit linear or quadratic forms. We refer the readers to Appendix D of Ji et al. [2024] for more details.As discussed in Section 4.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 K k=1 ∥q k -q k ∥ 1 . However, though the transition P admits a linear structure, the occupancy measure does not and retains a complex recursive form, which introduces an 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, we propose to learn value functions as a whole instead of directly controlling the occupancy measure discrepancies. This strategy diverges from traditional methods that bound ⟨q k -q k , r k ⟩ by the transition discrepanciesH h=1 s,a ∥P h (•|s, a) -Pk,h (•|s, a)∥ 1 ,where Pk is the estimated transition in episode k. Instead, we opt to constrain ⟨q k -q k , r k ⟩ through the value difference, which effectively integrates reward information. We introduce the details below.Denote by V k,1 (s k,1 ) = h,s,a,s ′ qk,h (s, a, s ′ )r k,h (s, a) the expected reward given the occupancy measure qk,h . Then, the approximation error can be rewritten asEQUATIONwhere V k,1 is an intermediate value we define later. Our key idea is building an optimistic estimator V k,1 to ensure the first term is non-positive while controlling the second term. This bypasses the need to bound occupancy measure discrepancies, allowing us to focus solely on the value estimation error.It remains to build the value function to ensure V k,h ≤ V k,h . A key observation is that the occupancy measure qk induces a new MDP whose transition lies in the confidence set C k with high probability. Thus, it suffices to ensure that V k,h is an overestimate of the true value function in the confidence set.By the definition of linear mixture MDPs, for anyEQUATIONs, a), θ * h ⟩. Thus, we compute the optimistic estimation as follows:EQUATION)where C k,h is 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 θ * h by the weighted ridge regression to utilize the variance information. Denote byϕ k,h,0 = ϕ V k,h+1 (s k,h , a k,h ) and ϕ k,h,1 = ϕ V 2 k,h+1 (s k,h , a k,h). We construct the estimator θ k,h asθ k,h = arg min θ∈R d k-1 j=1 [⟨ϕ j,h,0 , θ⟩ -V j,h+1 (s j,h+1 )] 2 σ2 j,h + λ∥θ∥ 2 2 ,where σ2 j,h is the upper confidence bound of the variance [V h V j,h+1 ](s j,h , a j,h ) and is set asσ2 k,h = max{H 2 /d, [ Vk,h V k,h+1 ] (s k,h , a k,h )+E k,h }, where [ Vk,h V k,h+1 ](s k,h , a k,h) is an estimate for the variance of value function V k,h+1 under the transition P h (•|s k , a k ), and E k,h is the bonus term to guarantee the true variance[V k,h V k,h+1 ](s k,h , a k,h ) is upper bounded by [ Vk,h V k,h+1 ](s k,h , a k,h )+E k,h with high probability. By definition, we have [V h V k,h+1 ](s k,h , a k,h ) = ⟨ϕ k,h,1 , θ * h ⟩ -[⟨ϕ k,h,0 , θ * h ⟩] 2 . Thus, we set [ Vk,h V k,h+1 ] (s k,h , a k,h ) = [⟨ϕ k,h,1 , θ k,h ⟩] [0,H 2 ] -[⟨ϕ k,h,0 , θ k,h ⟩] 2 [0,H], where θ k,h is used to estimate the second-order moment and is constructed as:θ k,h = arg min θ∈R d k-1 j=1 [⟨ϕ j,h,1 , θ⟩ -V 2 j,h+1 (s j,h+1 )] 2 + λ∥θ∥ 2 2 .The confidence set for the parameter θ * h is constructed asEQUATION)where Σ k,h is a covariance matrix, and β k is 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:β k = 8 d log(1 + k/λ) log (4k 2 H/δ) + 4 √ d log 4k 2 H/δ + √ λB. βk = 8d log(1 + k/λ) log (4k 2 H/δ) + 4 √ d log 4k 2 H/δ + √ λB, β k = 8H 2 d log (1 + kH 4 /(dλ)) log (4k 2 H/δ) + 4H 2 log 4k 2 H/δ + √ λB. E k,h = min H 2 , 2H βk Σ -1/2 k,h ϕ k,h,0 2 + min H 2 , β k Σ -1/2 k,h ϕ k,h,1 2 .Algorithm 2 ensures with probability at least 1 -δ, it holds thatK k=1 ⟨q k -q k , r k ⟩ ≤ O √ d 2 H 3 K + √ dH 4 K .Remark 4. This bound can be further simplified as O( √ d 2 H 3 K) when d ≥ H, which is a mild assumption. Following previous work [Zhou et al., 2021] , we only discuss the case d ≥ H below. 
theoretical guarantees: 
 In this section, we present the dynamic regret upper bound and the lower bound for this problem.The dynamic regret upper bound of our algorithm is guaranteed by the following theorem. Theorem 1. Set the parameters as in Lemma 1 and Lemma 2. Algorithm 1 with Algorithm 2 as the subroutine ensures with probability at least 1 -δ, the dynamic regret is upper bounded byD-Reg K (π c 1:K ) ≤ O √ d 2 H 3 K + HK(H + PK ) .Remark 5. Compared with the dynamic regret of O √ d 2 H 3 K + H 2 (K + P K )(1 + P K ) for known non-stationarity measure cases in Li et al. [2023] , our bound has a better dependence on H. Compared with the dynamic regret of O dHS √ K + HK(H + PK ) for unknown non-stationarity measure cases in Li et al. [2024b] , our bound removes the dependence on the state number S.Then, we establish the dynamic regret lower bound for this problem. Theorem 2. Suppose B ≥ 2, d ≥ 4, H ≥ 3, K ≥ (d -1) 2 H/2, for any algorithm and any constant Γ ∈ [0, 2KH], there exists an adversarial inhomogeneous linear mixture MDP and a policy sequenceπ c 1 , . . . , π c K such that PK ≤ Γ and D-Reg K (π c 1:K ) ≥ Ω( √ d 2 H 3 K + HK(H + Γ)). Remark 6. Combining Theorem 1 and Theorem 2, our algorithm achieves the minimax optimal dynamic regret in terms of d, H, K and PK simultaneously up to logarithmic factors.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-Reg K (π c 1:K ) = K k=1 ⟨q c k -qi k , r k ⟩ base-regret + K k=1 ⟨q i k -qk , r k ⟩ meta-regret + K k=1 V k,1 -V k,1occupancy-policy-gap+ K k=1 V k,1 -V π k k,1estimation-error .• base-regret. By the analysis of OMD, it can be upper bounded by O η i KH + (H + PK )/η i .Choosing the base-learner with the best step size leads to an upper bound of O( KH(H + PK )).• meta-regret. This term is the static regret of the expert-tracking problem. As our meta-algorithm is the Hedge algorithm, by the standard analysis, this term can be upper bounded by O(H √ K). • occupancy-policy-gap. As the value functions are optimistic estimators over the confidence set C k , the value gap between the occupancy measure and the policy is guaranteed to be non-positive.• estimation-error. Let ϵ Q k,h = Q k,h -Q π k k,h and ϵ V k,h = V k,h -V π k k,h , then define policy noise M k,h,1 = E a∼π k (•|s k,h ) [ϵ Q k,h (s k,h , a)] -ϵ Q k,h (s k,h , a k,h ), transition noise M k,h,2 = [P h (ϵ V k,h )](s k,h , a k,h ) - ϵ V k,h (s k,h+1 ) and bonus ι k,h = Q k,h -(r k,h + P h V k,h+1). The estimation error can be decomposed into transition noises, policy noises, and bonuses, i.e.,K k=1 H h=1 (M k,h,1 + M k,h,2 + ι k,h ).The transition and policy noises can be bounded by O( √ KH 3 ) using Azuma-Hoeffding's inequalities. The bonus term can be bounded by O(√ d 2 H 3 K + √ dH 4 K) according to Lemma 2. ■ 
conclusion and future work: 
 In this work, we study the dynamic regret of adversarial linear mixture MDPs with the unknown transition. We observe the occupancy-measure-based method is effective in addressing non-stationary environments but struggles with unknown transitions. In 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 of both methods, achieving an O( √ d 2 H 3 K + HK(H + PK )) dynamic regret without prior knowledge of the non-stationarity measure. We show it is optimal up to logarithmic factors by establishing a matching lower bound.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 et al., 2021] and multinomial logit function approximation [Li et al., 2024a] , is an interesting direction. 
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 a theoretical paper and does not release any data or models that have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a 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 a theoretical paper and does not use 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Proof. Without loss of generality, we assume that all states are reachable with positive probability under the uniform policy π u (a|s) = 1/A, ∀s ∈ S, a ∈ A. Otherwise, we can simply remove the unreachable states from the state space. Assume K is large enough such that the occupancy measure of q P,π u ∈ ∆(P, 1/T ). We define u k = (1 -1 T )q c k + 1 T q P,π u ∈ ∆(P, 1/T 2 ). Then, we can decompose the first term asEQUATION)which the first inequality follows from Holder's inequality, the second holds by ∥q c k -q P,π u ∥ 1 ≤ 2H, and the last holds for any i ∈ [N ]. Next, we bound base-regret and meta-regret separately.Upper bound of base-regret. Since the true transition parameter θ * is contained in the confidence set C k by condition, we ensure thatu k ∈ ∆(P, 1/T 2 ) ∈ ∆(C k , 1/T 2 ). By the update rule of qi k in (6), we ensure that qi k ∈ ∆(C k , 1/T 2 ), ∀i ∈ [K].The update rule in (6) can be rewritten as:qi k+1 = arg max q∈R HSAS η i ⟨q, r k ⟩ -D ψ (q∥q i k ), qi k+1 = arg min q∈∆(C k ,α) D ψ (q∥q i k+1 ),or equivalently,qi k+1,h (s, a, s) = qi k,h (s, a, s) exp(η i r k (s, a)), qi k+1 = arg min q∈∆(C k ,α) D ψ (q∥q i k+1 ).By the three-point identity in Lemma 9, we haveEQUATION)where the inequality is due to the Pythagorean theorem.For the last term of ( 12), summing over k, we haveEQUATION)where the first inequality is due to the fact ex -x -1 ≤ x 2 for x ∈ [0, 1].For the first two terms of ( 12), by the definition of KL-divergence, we haveK k=1 D ψ (u k ∥q i k ) -D ψ (u k ∥q i k+1 ) = D ψ (u 1 ∥q i 1 ) + K k=2 D ψ (u k ∥q i k ) -D ψ (u k-1 ∥q i k ) = D ψ (u 1 ∥q i 1 ) + K k=2 H h=1 s,a,s ′ u k,h (s, a, s ′ ) log u k,h (s, a, s ′ ) qi k,h (s, a, s ′ ) -u k-1,h (s, a, s ′ ) log u k-1,h (s, a, s ′ ) qi k,h (s, a, s ′ ) = D ψ (u 1 ∥q i 1 ) + ψ(u K ) -ψ(u 1 ) + K k=2 H h=1 s,a,s ′ (u k,h (s, a, s ′ ) -u k-1,h (s, a, s ′ )) log 1 qi k,h (s, a, s ′ ) ≤ D ψ (u 1 ∥q i 1 ) + ψ(u K ) -ψ(u 1 ) I1 +2 log T K k=2 H h=1 s,a,s ′ |u k,h (s, a, s ′ ) -u k-1,h (s, a, s ′ )| I2where the inequality holds by qi k ∈ ∆(P k , 1/T 2 ). It remains to bound I 1 and I 2 separately. For term I 1 , since qi 1 minimize ψ over ∆(P 1 , 1/T 2 ), we have ⟨∇ψ(q i 1 ), u 1 -qi 1 ⟩ ≥ 0, thus,EQUATIONFor term I 2 , for any (s, a), we haves ′ |u k,h (s, a, s ′ ) -u k-1,h (s, a, s ′ )| = s ′ |u k,h (s, a)P h (s ′ |s, a) -u k-1,h (s, a, s ′ )P h (s ′ |s, a)| = s ′ |u k,h (s, a) -u k-1,h (s, a)|P h (s ′ |s, a) = |u k,h (s, a) -u k-1,h (s, a)|.Thus, we haveEQUATIONCombining ( 12), ( 13), ( 14) and ( 15), we havebase-regret ≤ 1 η i K k=1 D ψ (u k ∥q i k ) -D ψ (u k ∥q i k+1 ) + D ψ (q i k ∥q i k+1 ) ≤ η i T + 1 η i (H log(S 2 A) + 2 PK log T ).It is easy to verify that the optimal step size is η * = (H log(S 2 A) + 2 PK log T )/T . Since 0 ≤ PK ≤ 2T , we ensure thatH log(S 2 A) T ≤ η * ≤ H log(S 2 A) + 4T log T T .By the construction of the step size poolH = {η i = 2 i-1 K -1 log(S 2 A) | i ∈ [N ]} with N = 1 + ⌈ 1 2 log(1 + 4K log T log(S 2 A))⌉, we know that the step size therein is monotonically increasing withη 1 = H log(S 2 A) T , η N ≥ H log(S 2 A) + 4T log T T .Thus, we ensure there exists an index i * such that η i * ≤ η * ≤ 2η i * = η i * +1 . Since the decomposition in (11) holds for any B i , we choose B i * to analyze the regret bound. By the definition of η * , we have base-regretEQUATIONwhere the last equality holds by substituting η * = (H log(S 2 A) + 2 PK log T )/T .Upper bound of meta-regret. Denote byh i k = ⟨q i k , r k ⟩ ∈ [0, H], we have meta-regret = K k=1 ⟨q i k - N i=1 p i k qi k , r k ⟩ = K k=1 ⟨e i -p k , h k ⟩,where e i is the i-th standard basis vector in R N . 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-Bianchi and Lugosi, 2006, Theorem 2 .2], we haveEQUATIONwhere the equality holds by setting ε = (log N /HT ).Combining ( 11), ( 16) and ( 17), we haveK k=1 ⟨q c k -qk , r k ⟩ ≤ 3 T (H log(S 2 A) + 2 PK log T ) + 2.This finishes the proof. ■In this section, we first provide the main proof of Lemma 2, and then present the proofs of the auxiliary lemmas used in the main proof.Proof. To prove Lemma 2, we first introduce the following lemma which shows the true parameter θ * h is contained in the confidence set C k,h with high probability by such configuration. Lemma 3 (Zhou et al. [2021, Lemma 5] ). Let C k,h be defined in (10) and set parameters as in Lemma 2. Then, we haveθ * h ∈ C k,h for all h ∈ [H] and k ∈ [K] with probability at least 1 -3δ.Denote by E the event when Lemma 3 holds, then Pr(E) ≥ 1 -3δ. We are ready to prove Lemma 2.First, we can rewrite the termK k=1 ⟨q k -q k , r k ⟩ as K k=1 ⟨q k -q k , r k ⟩ = K k=1 V k,1 (s k,1 ) -V π k k,1 (s k,1 ) = K k=1 V k,1 (s k,1 ) -V k,1 (s k,1 )occupancy-policy-gapEQUATIONNext, we bound these two terms separately.Upper bound of occupancy-iteration-gap. This term is the gap between the value function computed by the occupancy measure {q k } K k=1 and the optimistic value function computed by backward iteration defined in (9). Similar to Ji et al. [2024, Lemma 6 .1], we show this term is non-positive.Lemma 4. For any episode k ∈[K], define V k,1 (s k,1 ) = h,s,a,s ′ qk,h (s, a, s ′ )r k,h (s, a) and V k,1 (s k,1 ) the value function computed in (9), on the event E, it holds that V k,1 (s k,1 ) ≤ V k,1 (s k,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 ∈ [K], h ∈ [H], it holds that V k,h (s k,h ) -V π k k,h (s k,h ) = H h ′ =h M k,h ′ ,1 + M k,h ′ ,2 -ι k,h ′ (s k,h ′ , a k,h ′ ) , with M k,h,1 = E a∼π k (• | s k,h ) [Q k,h (s k,h , a) -Q π k k,h (s k,h , a)] -(Q k,h (s k,h , a k,h ) -Q π k k,h (s k,h , a k,h )), M k,h,2 = [P h (V k,h+1 -V π k k,h+1 )](s k,h , a k,h ) -(V k,h+1 (s k,h+1 ) -V π k k,h+1 (s k,h+1 )) ι k,h (•, •) = Q k,h (•, •) -(r k,h (•, •) + P h V k,h+1 (•, •)).Note M k,h,1 is the noise from the stochastic policy and M k,h,2 is the noise from the state transition,Let M k,h = M k,h,1 + M k,h,2 , ∀k ∈ [K], h ∈ [H],we define two following high probability events:E 1 = ∀h ∈ [H], K k=1 H h ′ =h M k,h ′ ≤ 4 H 3 K log H δ , E 2 = K k=1 H h=1 M k,h,2 ≤ 8H 3 K log 1 δ .According to the Azuma-Hoeffding inequality, we have Pr(E 1 ) ≥ 1 -δ and Pr(E 2 ) ≥ 1 -δ. It remains to bound the model prediction error ι k,h .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ι k,h = Q k,h -(r k,h + P h V k,h+1), on the event E, it holds thatK k=1 H h=1 ι k,h (s k,h , a k,h ) ≤ 2 β K K k=1 H h=1 σ2 k,h 2Hd log(1 + K/λ).Here, σ2 k,h is the estimated variance, for the total true varianceK k=1 H h=1 [V h V π k h+1 ](s k,h , a k h ), we introduce the high probability event E 3 :E 3 = K k=1 H h=1 [V h V π k h+1 ](s k,h , a k h ) ≤ 3(HK + H 3 log(1/δ)) .Lemma C.5 in Jin et al. [2018] suggests that Pr(E 3 ) ≥ 1 -δ. Based on the events E ∩ E 1 ∩ E 2 ∩ E 3 , 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 eventsE ∩ E 1 ∩ E 2 ∩ E 3 , it holds that K k=1 H h=1 σ2 k,h ≤ 2H 3 K d + 179H 2 K + (165d 3 H 4 + 2062d 2 H 5 ) log 2 4K 2 H δ log 2 1 + KH 4 λ .Combining Lemma 5, Lemma 6 and Lemma 7, we can bound the estimation-error as follows.Lemma 8. On the eventsE ∩ E 1 ∩ E 2 ∩ E 3 , for any h ∈ [H], it holds that K k=1 V k,h (s k,h ) - K k=1 V π k k,h (s k,h ) ≤ O √ dH 4 K + √ d 2 H 3 K .Finally, we finish the proof of Lemma 2 by combining Lemma 4 and Lemma 8. ■In this section, we proof the auxiliary lemmas used in the proof of Lemma 2 in Appendix B.1.Proof. The proof is similar to that of Ji et al. [2024, Lemma 6.1] . The only difference is that qk is a weighted combination rather than a single occupancy measure in the decision set. For k ∈ [K], the occupancy measure qk is given by qk =N i=1 p i k qi k . Since qi k ∈ ∆(P k , α), we ensure that qk ∈ ∆(P k , α). Thus, for occupancy measure qk , there exist θ such thatP k,h (s ′ |s, a) = q k,h (s, a, s ′ ) s ′ q k,h (s, a, s ′ ) = ⟨ϕ(s ′ |s, a), θk,h (s, a)⟩, ∀(s, a, h) ∈ S × A × [H].It is easy to verify that the update rule V k,1 (s k,1 ) = h,s,a,a ′ qk,h (s, a, s ′ )r k,h (s, a) computed by the occupancy measure is the same as the following backward iteration:Q k,h (s, a) = r h (s, a) + ⟨ϕ V k,h+1 (s ′ |s, a), θk,h (s, a)⟩, V k,h (s) = E a∼π k (•|s) Q k,h (s, a), V k,H+1 (s) = 0.Then, we can 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)∈ S × A, since Q k,h (s, a) ≤ H, so if Q k,h (s, a)= H, then it holds directly. Otherwise, we haveQ k,h (s, a) -Q k,h (s, a) = ⟨ϕ V k,h+1 (s, a), θ k,h ⟩ + β∥ϕ V k,h+1 (s, a)∥ Σ -1 k,h -⟨ϕ V k,h+1 (s ′ |s, a), θk,h (s, a)⟩ ≥ ⟨ϕ V k,h+1 (s, a), θ k,h ⟩ + β∥ϕ V k,h+1 (s, a)∥ Σ -1 k,h -⟨ϕ V k,h+1 (s ′ |s, a), θk,h (s, a)⟩ = ⟨ϕ V k,h+1 (s, a), θ k,h -θk,h (s, a)⟩ + β∥ϕ V k,h+1 (s, a)∥ Σ -1 k,h ≥ β∥ϕ V k,h+1 (s, a)∥ Σ -1 k,h -∥ θ k,h -θk,h (s, a)∥ Σ k,h ∥ϕ V k,h+1 (s, a)∥ Σ -1 k,h ≥ 0,where the first inequality holds by the inductive hypothesis, the second holds due to Holder's inequality, and the last holds due to θk,h (s, a) ∈ C k,h . By induction, we finish the proof. ■Proof. By the definitionV k,h (s k,h ) = E a∼π k (• | s k,h ) [Q k,h (s k,h , a)], we have V k,h (s k,h ) -V π k k,h (s k,h ) = E a∼π k (• | s k,h ) Q k,h (s k,h , a) -Q π k k,h (s k,h , a) = E a∼π k (• | s k,h ) Q k,h (s k,h , a) -Q π k k,h (s k,h , a) -Q k,h (s k,h , a k,h ) -Q π k k,h (s k,h , a k,h ) + Q k,h (s k,h , a k,h ) -Q π k k,h (s k,h , a k,h ) = E a∼π k (• | s k,h ) Q k,h (s k,h , a) -Q π k k,h (s k,h , a) -Q k,h (s k,h , a k,h ) -Q π k k,h (s k,h , a k,h ) + [P h (V k,h+1 -V π k k,h+1 )](s k,h , a k,h ) + ι k,h (s k,h , a k,h ) = E a∼π k (• | s k,h ) Q k,h (s k,h , a) -Q π k k,h (s k,h , a) -Q k,h (s k,h , a k,h ) -Q π k k,h (s k,h , a k,h ) ≜M k,h,1 + [P h (V k,h+1 -V π k k,h+1 )](s k,h , a k,h ) -V k,h+1 (s k,h+1 ) -V π k k,h+1 (s k,h+1 ) ≜M k,h,2 + V k,h+1 (s k,h+1 ) -V π k k,h+1 (s k,h+1 ) + ι k,h (s k,h , a k,h) where the third equality holds by the fact Q k,h = r k,h +P h V k,h+1 +ι k,h and Q π k k,h = r k,h +P h V π k k,h+1k,h = Q k,h -(r k,h + P h V k,h+1 ), we have ι k,h (s, a) = Q k,h (s, a) -(r k,h + P h V k,h+1 )(s, a) = r k,h (s, a) + θ k,h , ϕ V k,h+1 (s, a) + β k Σ -1/2 k,h ϕ V k,h+1 (s, a) 2 -(r k,h + P h V k,h+1 )(s, a) = θ k,h -θ * h , ϕ V k,h+1 (s, a) + β k Σ -1/2 k,h ϕ V k,h+1 (s, a) 2 ≤ 2 β k Σ -1/2 k,h ϕ V k,h+1 (s, a) 2 ,where the first inequality holds by the configuration of Q k,h in (9), the second inequality holds by the definition of linear mixture MDP such that [P h V k,h+1 ](s, a) = ⟨ϕ V k,h+1 (s, a), θ * h ⟩ and the last inequality holds by the construction of the confidence set in Lemma 3.Then, we haveK k=1 H h=1 ι k,h (s k,h , a k,h ) ≤ K k=1 H h=1 2 min{ β k Σ -1/2 k,h ϕ V k,h+1 (s k,h , a k,h ) 2 , H} ≤ K k=1 H h=1 2 β k σk,h min Σ -1/2 k,h ϕ V k,h+1 (s k,h , a k,h ) /σ k,h 2 , 1 ≤ 2 β K K k=1 H h=1 σ2 k,h K k=1 H h=1 min Σ -1/2 k,h ϕ V k,h+1 (s k,h , a k,h ) /σ k,h 2 , 1 ≤ 2 β K K k=1 H h=1 σ2 k,h 2Hd log(1 + K/λ),where the first inequality holds by Q k,h ∈ [0, H], the second holds by 2 β k σk,h ≥ √ dH/ √ d = H, the third inequality is by Cauchy-Schwarz inequality and the last inequality holds by the elliptical potential lemma in Lemma 10. This finishes the proof. ■Proof. The proof can be obtained by combining Lemma 5, 6 and 7. Specifically, we haveK k=1 V k,h (s k,h ) - K k=1 V π k k,h (s k,h ) ≤2 β K K k=1 H h=1 σ2 k,h 2Hd log(1 + K/λ) + 4 H 3 K log H δ + 8H 3 K log 1 δ ≤ O √ dH 4 K + √ d 2 H 3 K .where the first inequality holds by Lemma 5 and Lemma 6 and the last inequality holds by Lemma 7. This finishes the proof. ■Proof. Combining Lemma 1 and Lemma 2, we haveD-Reg K (π c 1:K ) ≤ O T (H log (S 2 A) + PK log T ) + O √ dH 4 K + √ d 2 H 3 K .This finishes the proof. ■Proof. Our proof is similar to that of Li et al. [2023, Theorem 4] . At a high level, we prove this lower bound by noting that optimizing the dynamic regret of linear mixture MDPs is harder than (i) optimizing the static regret of linear mixture MDPs with the unknown transition, (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:EQUATIONThen, 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 Ω(H K log (SA)). 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 an expanded state space S ′ = S × [H]. Thus, Ω(H K log (SA)) is also a lower bound of the static regret for the MDP in our work. We consider the following two cases:Case 1: Γ ≤ 2H. In this case, we can directly utilize the lower bound of static regret as a lower bound of dynamic regret, i.e.,EQUATIONCase 2: Γ > 2H. Without loss of generality, we assume L = ⌈Γ/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 -1 ≤ Γ/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 Γ. As a result, we have 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 K (π c 1:K ) ≥ LH K/L log (SA) = H KL log (SA) ≥ Ω( KHΓ log (SA)).D-Reg K (π c 1:K ) ≥ Ω max{ √ d 2 H 3 K, KH(H + Γ) log(SA)} ≥ Ω √ d 2 H 3 K + KH(H + Γ) log(SA). This finishes the proof. ■In this section, we introduce the supporting lemmas used in the proofs. Lemma 9 (Three-point identity). Let X be a closed and convex set. For any x ∈ X and y, z ∈ int X , it holds that D ψ (x, y) + D ψ (y, z) -D ψ (x, z) = ⟨∇ψ(z) -∇ψ(y), x -y⟩.Lemma 10 (Abbasi-Yadkori et al. [2011, Lemma 11] ). Let {x t } ∞ t=1 be a sequence in R d space, V 0 = λI and define Guidelines:V t = V 0 + t i=1 x i x ⊤ i . If ∥x i ∥ 2 ≤ L, ∀i ∈ Z + , then for each t ∈ Z + , t i=1 min 1, ∥x i ∥ V -1 i-1 ≤ 2d log dλ +• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 of RL, none societal impacts we feel must be specifically highlighted here. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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.

Reviews: review: paper_summary: paper_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.

This 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.
strength_weakness: strength_weakness: 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? 
2. 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. 
3. 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.

Minor: typos noted below

Line 243: The formula for KL-divergence

Line 326: “Combinin”
questions: 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.

Can you comment on the intuition of why it is possible to remove the dependence on S in the upper bound?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

[1] Nonstationary Reinforcement Learning with Linear Function Approximation
questions: 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}$.

2. 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: None.
limitations: limitations: The authors discussed limitations of the work.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: All techniques used in this paper are existed in previous works. Apart from this, I don't see significant drawbacks in this paper.
questions: questions: I have the following questions for the authors:

1. Does the algorithm apply to other type of non-stationary measures, e.g. switching cost, etc?

2. 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: limitations: Yes. The authors addressed all the limitations listed in the guidelines.

Comments: title: Thanks for the review! Have we properly addressed your concerns?
Thank you!
comment: We sincerely appreciate your constructive feedback and are especially grateful for bringing the paper [1] to our attention. We will revise the paper to cite [1] and incorporate the above discussions in the next version.

Given that the author-reviewer discussion period is soon coming to an end, please let us know if our response has properly addressed the concerns. We will be happy to provide clarification if you have any further questions. Thanks!

Best,

Authors
Thank you very much for your response. I do not have further questions.
Thank you for your re-evaluation and the revised score. We are happy to discuss work with you.
Thank you for providing the clarifications. I have increased the score accordingly.
I appreciate the authors' response, which is reasonable. I will keep my score unchanged.