MetaCURL: Non-stationary Concave Utility Reinforcement Learning

Authors: bianca  marin
moreno  inria
edf  r&d
margaux  brégère
sorbonne  université
pierre  gaillard inria
nadia  oudjane
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 10:28:05

Abstract: We explore online learning in episodic loop-free Markov decision processes on non-stationary environments (changing losses and probability transitions). Our focus is on the Concave Utility Reinforcement Learning problem (CURL), an extension of classical RL for handling convex performance criteria in state-action distributions induced by agent policies. While various machine learning problems can be written as CURL, its non-linearity invalidates traditional Bellman equations. Despite recent solutions to classical CURL, none address non-stationary MDPs. This paper introduces MetaCURL, the first CURL algorithm for non-stationary MDPs. It employs a meta-algorithm running multiple black-box algorithms instances over different intervals, aggregating outputs via a sleeping expert framework. The key hurdle is partial information due to MDP uncertainty. Under partial information on the probability transitions (uncertainty and non-stationarity coming only from external noise, independent of agent state-action pairs), we achieve optimal dynamic regret without prior knowledge of MDP changes. Unlike approaches for RL, MetaCURL handles full adversarial losses, not just stochastic ones. We believe our approach for managing non-stationarity with experts can be of interest to the RL community.

Main paper: 
 introduction: 
 We consider the task of learning in an episodic Markov decision process (MDP) with a finite state space X , a finite action space A, episodes of length N , and a probability transition kernel p := (p n ) n∈ [N ] such that for all (x, a) ∈ X × A, p n (•|x, a) ∈ S X . For any finite set B, we denote by S B the simplex induced by this set, and by |B| its cardinality. For all d ∈ N we let [d] := {1, . . . , d}. At each time step n, an agent in state x n chooses an action a n ∼ π n (•|x n ) by means of a policy, and moves to the next state x n+1 ∼ p n+1 (•|x n , a n ), inducing a state-action distribution sequence µ π,p := (µ π,p n ) n∈ [N ] , where µ π,p n ∈ S X ×A for all n ∈ [N ]. In many applications of learning in episodic MDPs, an agent aims at finding an optimal policy π maximizing/minimizing a concave/convex function F of its state-action distribution, known as the Concave Utility Reinforcement Learning (CURL) problem: min π∈(S A ) X ×N F (µ π,p ).(EQUATIONdivergence induced by a function g and µ * being a behavior to be imitated; certain instances of meanfield control [7] , where F (µ π,p ) = ⟨ℓ(µ π,p ), µ π,p ⟩; mean-field games with potential rewards [34] ; among others. The CURL problem alters the additive structure inherent in standard RL, invalidating the classical Bellman equations, requiring the development of new algorithms.Most of existing works on CURL focus on stationary environments [28, 57, 58, 5, 56, 25, 12, 11] , where both the objective function F and the probability transition kernel p remain the same across episodes. However, in practical scenarios, environments are rarely stationary. The work of [39] is the first to address online CURL with objective functions that can change arbitrarily between episodes, also known as adversarial losses [19] . However, their work assumes stationary probability kernels and presents results in terms of static regret (performance comparable to an optimal policy).In non-stationary scenarios, it is more relevant to minimize dynamic regret-the gap between the learner's total loss and that of any policy sequence (see Eq. ( 5) for formal definition). In this work we address this problem by introducing the first algorithm for CURL handling adversarial objective functions and non-stationary probability transitions, achieving near-optimal dynamic regret.High-level idea. Our approach, called MetaCURL, draws inspiration from the online learning literature. In online learning [9] , non-stationarity is often managed by running multiple black-box algorithm instances from various starting points and dynamically selecting the best performer using an "expert" algorithm. This strategy has demonstrated effectiveness in settings with complete information [29, 59, 47, 33] . With MetaCURL, we extend this concept to decision-making in MDPs. Unlike classical online learning, the main challenge faced is uncertainty. We assume that the probability transition kernel in each episode has a known deterministic structure but is affected by an external noise with unknown distribution, placing us in a setting with only partial information (see Section 2 for more details). The learner is then unable to observe the agent's loss under policies other than the one played.MetaCURL is a general algorithm that can be applied with any black-box algorithm with low dynamic regret in near-stationary environments. CURL approaches suitable as black-boxes rely on parametric algorithms that would require prior knowledge of the MDP changes to tune their learning rate. MetaCURL also addresses this challenge by simultaneously running multiple learning rates and weighting them in direct proportion to their empirical performance. MetaCURL achieves optimal regret of order Õ √ ∆ π * T + min { √ ∆ p ∞ T , T 2/3 (∆ p ) 1/3 } , where ∆ p ∞ and ∆ p represent the frequency and magnitude of changes of the probability transition kernel respectively, and ∆ π * is the magnitude of changes of the policy sequence we compare ourselves with in dynamic regret (see Eqs. (6) and (7) for formal definitions). MetaCURL does not require previous knowledge of the degree of non-stationarity of the environment, and can handle adversarial losses. To ensure completeness, we show that Greedy MD-CURL from [39] fulfills the requirements to serve as a black-box algorithm. This is the first dynamic regret analysis for a CURL approach.Comparisons. Without literature on non-stationary CURL, we review non-stationary RL approaches. Most methods [24, 13, 45, 17, 20, 40, 21] typically rely on prior knowledge of the MDP's nonstationarity degree, while MetaCURL does not. Let ∆ l ∞ and ∆ l represent the frequency and magnitude of change in the RL loss function, respectively 1 . Recently, [54] achieved a regret of Õ min { (∆ p ∞ + ∆ l ∞ )T , T 2/3 (∆ p + ∆ l ) 1/3 } , a near-optimal result as demonstrated by [40] , without requiring prior knowledge of the environment's variation. However, this regret bound is tied to changes in loss functions, making it ineffective against adversarial losses. In contrast, rather than Table 1 : Comparisons of our results with the state-of-the-art in non-stationary RL. Here, ∆ p ∞ , ∆ p and ∆ π * are defined in ( 6) and (7) ; and ∆ l ∞ and ∆ l measure the RL loss function variations 1 . We introduce D T (∆ ∞ , ∆) := min { √ ∆ ∞ T , T 2/3 ∆ 1/3 }.RL CURL Adv. lossesExploration MetaCURL (ours)D T (∆ p ∞ , ∆ p ) + √ ∆ π * T ✓ ✓ ✓ ✓ ✗ SoTA in RL [54] D T (∆ p ∞ + ∆ l ∞ , ∆ p + ∆ l ) ✓ ✗ ✗ ✓ ✓ 1 ∆ l := 1 + T -1 t=1 ∆ l t and ∆ l ∞ := 1 + T -1 t=1 1{∆ l t ̸ = ∆ l t+1 }, where ∆ l t := N n=1 maxx,a |ℓ t n (x, a)ℓ t+1 n (x, a)| and ℓ t n (x, a) is the expected loss suffered by choosing action a in state x at step n of round t.depending on the magnitude of variation of the loss function, MetaCURL's bound depends on the magnitude of variation of the policy sequence we use for comparison in dynamic regret. This allows it to handle adversarial losses, and to compare against policies with a more favorable bias-variance trade-off, which may not align with the optimal policies for each loss. In addition, we improve this dependency by paying it as √ ∆ π * T instead of (∆ π * ) 1/3 T 2/3 . We summarize comparisons in Table 1 .Other related works. The studies by [43, 42] examine the difference between optimizing the objective over infinite trials and the expectation of the objective over a single trial, challenging the traditional CURL formulation in Eq. ( 1). Here, we retain the classic formulation to align with existing CURL research. Other works on RL with nonlinear objective functions are [46, 16] focusing on rewards over trajectories rather than individual states. In addition to non-stationarity, there is a series of works on RL with adversarial losses but stationary probability transitions, with results only on static regret [48, 30, 18, 50, 32, 14] . Another line of research is known as corruption-robust RL. It differs from non-stationary MDPs in that it assumes a ground-truth MDP and measures adversary malice by the degree of ground-truth corruption [31, 38, 10, 60, 53] .Contributions. We resume our main contributions below:• We introduce MetaCURL, the first algorithm for non-stationary CURL. Under the framework described in Section 2, MetaCURL achieves the optimal dynamic regret bound of orderÕ √ ∆ π * T + min { √ ∆ p ∞ T , T 2/3 (∆ p ) 1/3} , without requiring previous knowledge of the degree of non-stationarity of the MDP. MetaCURL handles full adversarial losses and improves the dependency of the regret on the total variation of policies. MetaCURL is the first adaptation of Learning with Expert Advice (LEA) to deal with uncertainty in non-stationary MDPs.• We also establish the first dynamic regret upper bound for an online CURL algorithm in a nearly stationary environment, which can serve as a black-box routine for MetaCURL.Notations. Let ∥ • ∥ 1 be the L 1 norm, and for all v:= (v n ) n∈[N ] , such that v n ∈ R X ×A we define ∥v∥ ∞,1 := sup 1≤n≤N ∥v n ∥ 1 .2 General framework: non-stationary CURLWhen an agent plays a policy π := (π n ) n∈[N ] in an episodic MDP with probability transition p, it induces a state-action distribution sequence (also called the occupancy-measure [61] ), which we denote by µ π,p := (µ π,p n ) n∈[N ] , with µ π,p n ∈ S X ×A . It can be calculated recursively for all (x, a) ∈ X and n ∈ [N ] by taking µ π,p 0 (x, a) = µ 0 (x, a) fixed, andEQUATIONOffline CURL. The classic CURL optimization problem in Eq. ( 1) considers minimizing a function F : (S X ×A ) N → R, here defined as F (µ) := N n=1 f n (µ n ) with f n a convex function over µ n with values in [0, 1], across all policies that induce µ π,p . Note that F is not convex on the policy π. To convexify the problem, we define the set of state-action distributions satisfying the Bellman flow of a MDP with transition kernel p asEQUATIONFor any µ ∈ M p µ0 , there exists a strategy π such that µ π,p = µ. It suffices to take π n (a|x) ∝ µ n (x, a) when the normalization factor is non-zero, and arbitrarily defined otherwise. There is thus an equivalence between the CURL problem (optimization on policies) and a convex optimization problem on state-action distributions satisfying the Bellman flow:EQUATIONOnline CURL. In this paper we consider the online CURL problem in a non-stationary setting. We assume a finite-horizon scenario with T episodes. An oblivious adversary generates a sequence of changing objective functions (F t ) t∈[T ] , with F t being fully communicated to the learner only at the end of episode t. We assume F t is L F -Lipschitz with respect to the ∥ • ∥ ∞,1 norm for all t. The probability transition kernel is also allowed to evolve over time and is denoted by p t at episode t. The learner's objective is then to calculate a sequence of strategies (π t ) t∈[T ] minimizing a total loss L T := T t=1 F t (µ π t ,p t ), while dealing with adversarial objective functions F t and changing probability transition kernels p t . To measure the learner's performance, we use the notion of dynamic regret (the difference between the learner's total loss and that of any policy sequence (π t, * ) t∈[T ] ):EQUATIONNon-stationarity measures. We consider the following two non-stationary measures ∆ p ∞ and ∆ p on the probability transition kernels that respectively measure abrupt and smooth variations:EQUATIONEQUATIONRegarding dynamic regret, we define for any sequence of policies (π t, * ) t∈[T ] , its non-stationarity measure asEQUATIONMoreover, for any interval I ⊆ [T ], we write ∆ p I := t∈I ∆ p t and ∆ π * I := t∈I ∆ π * t . Dynamic's hypothesis. For each episode t, let (x t 0 , a t 0 ) ∼ µ 0 (•), and for all time steps n ∈ [N ],EQUATIONwhere g n represents the deterministic part of the dynamics, and(ϵ t n ) n∈[N ] is a sequence of independent external noises such that ϵ t n ∼ h t n (•), where h t n is any centered distribution. Note that these dynamics imply that the probability transition kernel can be written as p t n+1 (x ′ |x, a) = P g n (x, a, ϵ t n ) = x ′ . Different variants of this problem can be considered, depending on the prior information available about the dynamics in Eq. (8) . In this article we consider the case where g n is fixed and known by the learner, but h t n is unknown and can change (hence the source of uncertainty and non-stationarity of the transitions). To the best of our knowledge, there are no black-box algorithms in the literature that achieve sublinear regret for online CURL with adversarial losses without relying on model assumptions. In using RL methods to CURL, we believe model-optimistic approaches like UCRL (Upper Confidence RL [4] ) could be adapted. However, these methods are computationally expensive, as they require solving an additional optimization problem in every episode. The black-box algorithm for CURL we consider from [39] provides closed-form solutions, which is more computationally efficient, but requires the same dynamic assumption as in Eq. (8) . Another class of RL methods is policy optimization (PO), which directly optimizes the policy and often yields closed-form solutions, leading to faster performance. Recent theoretical work [37] has shown that PO methods can achieve near-optimal regret without model assumptions. However, these methods rely on RL's Bellman equations, which do not apply to CURL due to its non-linear nature. We believe that the MetaCURL analysis could potentially be extended to the case where g n is unknown but belongs to a parametric family. We leave this extension for future work. This particular dynamic is also motivated by many real-world applications:• Controlling a fleet of drones in a known environment, subject to external influences due to weather conditions or human interventions. • Addressing data center power management aiming to cut energy expenses while maintaining service quality. Workload fluctuations cause dynamic job queue transitions, and volatile electricity prices lead to varying operational costs. The probabilities of task processing by each server are predetermined, but the probabilities of task arrival are uncertain [6] . • As renewable energy use increases and energy demand grows, balancing production and consumption becomes harder. Certain devices, like electric vehicle batteries and water heaters, can serve as flexible energy storage options. However, this requires electric grids to establish policies regulating when these devices turn on or off to match a desired consumption profile. These profiles can fluctuate daily due to changes in energy production levels. Despite knowing the devices' physical dynamics, household consumption habits remain unpredictable and constantly changing [51, 41] .Outline. In this paper, we propose a novel approach to handle non-stationarity in MDPs, being the first to propose a solution to CURL within this context. We begin in Section 3 by discussing the idea behind our algorithm's construction and the key challenges within our framework. Section 4 introduces MetaCURL, while Section 5 presents the main results of our regret analysis. The proofs' specifics are provided in the appendix. 
main idea: 
 A hypothetical learner who achieves optimal regret. Let m > 1. Assume a hypothetical learner that could compute a sequence of restart times 1 = t 1 < . . . < t m+1 = T + 1, where for each i ∈ [m] we letEQUATIONConsider any algorithm that, when computing (π t ) t∈I with learning rate λ for any interval I ⊆ [T ], attains a dynamic regret relative to any sequence of policies (π t, * ) t∈I upper bounded byEQUATIONwhere (c j ) j∈ [3] are constants that may depend on the MDP parameters, and on the interval size only in logarithmic terms. This kind of regret bound holds for Greedy MD-CURL from [39] as we show in Appendix G. Suppose the hypothetical learner could also access ∆ π * to calculate the optimal learning rate. Hence, playing such an algorithm for all horizon T with the optimal learning rate, the learner would have a dynamic regret upper bounded byR [T ] (π t, * ) t∈[T ] ≤ 2 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m -1 .Optimizing over m, the learner would obtain the optimal regret of order Õ √ ∆ π * T + (∆ p ) 1/3 T 2/3 . In the case where the MDP is piece-wise stationary, if the learner takes I i such that ∆ p Ii = 0, it obtains a regret of order O( A meta algorithm to learn restart times. In reality, the restart times of Eq. ( 9), and the optimal learning rate, are unknown to the learner. Hence, we propose to build a meta aggregation algorithm to learn both. Let E represent a parametric black-box algorithm with dynamic regret as in Eq. (10) . We introduce a meta algorithm M that, takes as input a finite set of learning rates Λ, and at each episode t, initializes |Λ| instances of E, denoted as E t,λ for each λ ∈ Λ. Each E t,λ operates independently within the interval [t, T ]. At time t, M combines the decisions from the active runs {E s,λ } s≤t,λ∈Λ by weighted average. The idea is that at time t, some of the outputs of {E s,λ } s≤t,λ∈Λ are not based on data prior to t ′ < t, so if the environment changes at time t ′ , these outputs can be given a greater weight by the meta algorithm, enabling it to adapt more quickly to the change. At the same time, we expect a larger weight will be given to the empirically best learning rate. Let M(E, Λ) be the complete algorithm. Remark 3.1. The meta-algorithm increases the computational complexity of the parametric blackbox algorithm by a factor of T × |Λ|, as it requires updating t × |Λ| instances at each episode t. By strategically designing intervals to run the black-box algorithms, previous works on online learning have reduced computational complexity to O(log(T )) [15, 29, 27] . Extending our analysis to these intervals is straightforward, but it would complicate the presentation of the paper. Thus, we decided to present our results using the naive choice of intervals. Also, in Section 5, we show that a learning rate grid with |Λ| = log(T ) is sufficient to obtain the optimal regret. Regret decomposition. Denote by π t,s,λ the policy output from E s,λ at episode t, for learning rate λ, for all s ≤ t, and by π t the policy output by the meta algorithm M(E, Λ) to be played by the learner. The regret of M(E, Λ) can be decomposed as the sum of the regret suffered by the meta algorithm aggregation scheme, M, and the regret from the black-box algorithm, E, played with any learning rate λ ∈ Λ. The dynamic regret, defined in Eq. ( 5), can be decomposed, for any set of intervals I i = [t i , t i+1 -1], with 1 = t 1 < . . . < t m+1 = T + 1, and for any learning rate λ ∈ Λ, as√ ∆ π * T + √ ∆ p ∞ T ),EQUATIONThe black-box regret on I i is exactly the standard regret for T = |I i | with a learning rate of λ. Hence, in order to prove low dynamic regret for M(E, Λ) we have to: show that M incurs a low dynamic regret in each interval I i ; find a black-box algorithm E for CURL that has dynamic regret as in Eq. (10) , and build a learning rate grid Λ allowing us to perform nearly as well as the optimal learning rate. 
metacurl algorithm: 
 We call our meta-algorithm M MetaCURL. It is based on sleeping experts, is parameter-free, and achieves optimal regret. Its construction is described below.General setting. In Learning with Expert Advice (LEA), a learner makes sequential online predictions u 1 , . . . , u T in a decision space U, over a series of T episodes, with the help of K experts [22, 36, 9] . For each round t, each expert k makes a prediction u t,k , and the learner combines the experts' predictions by computing a vector v t := (v t,1 , . . . , v t,K ) ∈ S K , and predicting the convex combination of experts' prediction u t := K k=1 v t,k u t,k . The environment then reveals a convex loss function ℓ t : U → R. Each expert suffers a loss ℓ t,k := ℓ t (u t,k ), and the learner suffers a loss lt := ℓ t (u t ). The learner's objective is to keep the cumulative regret with respect to each expert as low as possible. For each expert k, this quantity is defined as Reg[T ] (k) := T t=1 lt -ℓ t,k .Sleeping experts. In our case, each black-box algorithm is an expert that does not produce solutions outside its active interval. This problem can be reduced to the sleeping expert problem [8, 23] , where experts are not required to provide solutions at every time step. Let I t,k ∈ {0, 1} define a signal equal to 1 if expert k is active at episode t and 0 otherwise. The algorithm knows (I t,k ) k∈[K] and assigns a zero weight to sleeping experts (I t,k = 0 implies v t,k = 0). We would like to have a guarantee with respect to expert k ∈ [K] but only when it is active. Hence, we now aim to bound a cumulative regret that depends on the signalI t,k : Reg sleep [T ] (k) := T t=1 I t,k ( lt -ℓ t,k ).There is a generic reduction from the sleeping expert framework to the general LEA setting [3, 2] (see Appendix A.1).In every episode t, for every learning rate λ ∈ Λ and s ≤ t, an instance E s,λ of the black-box algorithm acts as an expert computing a policy π t,s,λ . The meta algorithm aims to aggregate these predictions using a sleeping expert approach based on the expert's losses. However, within CURL's framework, the meta algorithm faces two challenges: Uncertainty. At the episode's end, the learner has full information about the objective function F t . If the learner also knew p t , they could recursively calculate the corresponding state-action distribution µ π t,s,λ ,p t using Eq. ( 2) and observe the actual loss of each expert, denoted as F t (µ π t,s,λ ,p t ). However, given that p t is unknown to the learner, the true loss remains unobservable. Consequently, the metaalgorithm needs to create an estimator pt for p t and utilize it to estimate the losses. We propose a method to compute an estimator pt in Subsection 4.3.Convexity. As discussed in Section 2, the objective functions F t are not convex over the space of polices. However, CURL is equivalent to a convex problem over the state-action distributions satisfying the Bellman's flow as shown in Eq. ( 4). Therefore, instead of aggregating policies, the meta algorithm aggregates the associated state-action distributions using the probability estimator pt and the recursive scheme at Eq. ( 2). We detail MetaCURL in Alg. 1 when employed with the Exponentially Weighted Average forecaster (EWA) as the sleeping expert subroutine (we detail EWA in Appendix A.2).As discussed earlier, applying the learning with experts framework requires estimating the loss of non-played expert policies, which depends on estimating the non-stationary transition probabilities pt . Standard RL techniques for bounding the L 1 norm between the empirical estimator pt and the true Algorithm 1 MetaCURL with EWA 1: Input: number of episodes T , finite set of learning rates Λ, black-box algo. E, EWA learning rate η = 8 log(T )T 2: Initialization:p1 n (•|x, a) := 1 |X | for all n ∈ [N ], (x, a) ∈ X × A 3: for t = 1, . . . , T do 4:Start |Λ| new instances of E denoted by E t,λ for all λ ∈ Λ, assign each of them a new weight v t,t,λ = 1 |Λ|t , and normalize weight vectors v t,s,λ for s ∈ [t-1] such that v t := (v t,s,λ ) s≤t,λ∈Λ is a probability vector in R t×ΛFor s ≤ t and λ ∈ Λ, E s,λ outputs π t,s,λ 6:Compute recursively µ π t,s,λ , pt using Eq. ( 2) for all s ≤ t and λ ∈ Λ 7:Aggregate the state-action distributions:µ t := t s=1 λ∈Λ µ π t,s,λ , pt v t,s,λ 8:Retrieve π t from µ t : for all n, (x, a),π t n (a|x) = µ t n (x,a) a ′ ∈A µn(x,a ′ ) , if µ t n (x, a) ̸ = 0 1 |A| , if µ t n (x, a) = 0 9:Learner plays π t : Agent starts at (x t 0 , a t 0 ) ∼ µ 0 (•)10:for n = 1, . . . , N do 11:Environment draws new statex t n ∼ p t n (•|x t n-1 , a t n-1 ) 12:Learner observes agent's external noise ε t n 13:Agent chooses an actiona t n ∼ π t n (•|x t n ) 14:end for 15:Objective function F t is exposed 16:Compute experts' losses ℓ t,s,λ := F t (µ π t,s,λ , pt ), for all s ≤ t and λ ∈ Λ 17:Compute the new weight vector v t+1 : for all s ≤ t and λ ∈ Λ,v t+1,s,λ = v t,s,λ exp (-ηℓ t,s,λ ) t s ′ =1 λ ′ ∈Λ v t,s ′ ,λ ′ exp (-ηℓ t,s ′ ,λ ′ ) (EWA update) 18:Use agent's external noise trajectory (ε t n ) n∈[N ] to compute pt+1 as in Subsection 4.3 19: end for dynamics p t [44, 49] are not applicable here due to non-stationarity. To address this, we introduce a second layer of sleeping experts for each (n, x, a) ∈ [N ] × X × A, where each expert provides an empirical estimate of p t based on different intervals. We then propose a new loss function in Eq. ( 12) and conduct a novel regret analysis in Prop. 5.2 to achieve the optimal regret rate.In each episode t, the learner calculates independent samples x t n,x,a ∼ p t n (•|x, a) utilizing the external noise sequence(ε t n ) n∈[N ] observed (just let x t n,x,a = g n-1 (x, a, ε t n-1), see Eq. ( 8)). Each expert outputs an empirical estimator of p t n (•|x, a) using samples across different intervals. We assume T experts, with expert s active in interval [s, T ]. Expert s at episode t > s outputs:pt,s n (x ′ |x, a) = N s:t-1 n,x,a (x ′ ) (t -s) , with N s:t-1 n,x,a (x ′ ) := t-1 q=s 1 {x q n,x,a =x ′ } .We let pt n (•|x, a) be the result of employing sleeping EWA with experts pt,s n (•|x, a), for s < t. Typically, in density estimation with EWA, a logarithmic loss -log(•) is used. However, in this case -log(•) can be unbounded, so we opt here for a smoothed logarithmic loss, given by, for all q ∈ S X ,EQUATION)The definition of this non-standard loss is further clarified during the regret analysis in Section 5. This loss function is  
regret analysis: 
 This section presents the main result concerning MetaCURL's regret analysis. Subsection 5.1 shows an upper bound for R meta when MetaCURL is played with EWA and pt is computed as in Subsection. 4.3. Subsection 5.2 introduces a learning rate grid for MetaCURL when the black-box algorithm meets the dynamic regret criteria in Eq. ( 10), providing an upper bound for R black-box . Given the dynamic regret decomposition of Eq. ( 11), we see that the combination of these results leads to our main result, the full proof of which can be found in appendix (F) : Theorem 5.1 (Main result). Let δ ∈ (0, 1). Playing MetaCURL, with a parametric black-box algorithm E with dynamic regret as in Eq. (10) , with a learning rate grid Λ := 2 -j |j = 0, 1, 2, . . . , ⌈log 2 (T )/2⌉ , and with EWA as the sleeping expert subroutine, we obtain, with probability at least 1 -2δ, for any sequence of policies(π t, * ) t∈[T ] , R [T ] (π t, * ) t∈[T ] ≤ Õ √ ∆ π * T + min T ∆ p ∞ , T 2/3 (∆ p ) 1/3 .Given the uncertainty in the probability transition, the meta regret term can be decomposed as follows:EQUATIONSleeping LEA regret. Referring to Thm. A.1 in Appendix A, using sleeping EWA as the sleeping expert subroutine of MetaCURL, with signals I t,s = 1 for active experts (s ≤ t), experts' convex losses ℓ t,s,λ := F t (µ π t,s,λ , pt ), and learner loss lt := F t (µ π t , pt ), yields, for any m ∈ [T ] and for any set of intervalsEQUATIONpt Estimation regret. In a scenario without uncertainty in the MDP's probability transitions, the meta-algorithm's regret would simply be bounded by Eq. ( 14), the sleeping expert regret used as a subroutine. However, given the presence of uncertainty, the main challenge in analyzing the meta-regret comes from the regret terms associated with the estimator pt . We outline this analysis in Prop. 5.2.Proposition 5.2. Let δ ∈ (0, 1), C := 1 2 log N |X ||A|2 |X | T δ, and L F be the Lipschitz constant of F t , with respect to the norm ∥• ∥ ∞,1 , for all t ∈ [T ]. With a probability of at least 1 -δ, MetaCURL obtains R p [T ] (π t ) := T t=1 F t (µ π t ,p t ) -F t (µ π t , pt ) ≤ 2L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 T 2/3 (∆ p ) 1/3 .For any m ∈ [T ] and for any set of intervalsI i = [t i , t i+1 -1], with 1 = t 1 < . . . < t m+1 = T + 1, the same bound is valid for m i=1 t∈Ii R p Ii (π t,ti,λ ).Proof. The proof idea is based mainly on the formulation of pt described in Subsection 4.3. We start by using the convexity of F t to linearize the expression, then we apply Holder's inequality and exploit the L F -Lipschitz property of F t to establish an upper bound based on the L 1 norm difference of the state-action distributions induced by the true probability transition and the estimator. Using Lemma C.5 in Appendix C, we then obtain thatR p [T ] ≤ L F T t=1 N n=1 n j=1 x,a µ π t ,p t j-1 (x, a)∥p t j (•|x, a) -pt j (•|x, a)∥ 1 .To use the results from Subsection 4.3, we first regularize p t and pt , for each (n, x, a), by averaging each with the uniform distribution over X , that we denote by p 0 := 1/|X |. As both probabilities are now lower bounded, we can employ Pinsker's inequality to convert the L 1 norm into a KL divergence.The sum over t ∈ [T ] of the KL divergence can then be decomposed as follows:T t=1 KL p t j (•|x, a) + p 0 2 pt j (•|x, a) + p 0 2 = m i=1 t∈Ii KL p t j (•|x, a) + p 0 2 pt,ti j (•|x, a) + p 0 2 + m i=1 t∈Ii E xt j,x,a log pt,ti j (x t j,x,a |x, a) + p 0 -log pt j (x t j,x,a |x, a) + p 0 ,where pt,ti j (•|x, a) is the empirical estimate of p t j (•|x, a) calculated with the observed data from t i to t -1, and the expectation is over xt j,x,a ∼ (p t j (•|x, a) + p 0 )/2. The second term is the cumulative regret of computing pt using EWA with loss as in Eq. ( 12), and is bounded by m log(T ). We finish and give more details of the proof in Appendix D. Prop. 5.2 together with Eq. ( 14) yields the main result of this subsection: R meta [T ] ≤ 4L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 T 2/3 (∆ p ) 1/3 + mT 2 log(T |Λ|).Assuming E is a parametric black-box algorithm with dynamic regret satisfying Eq. ( 10) for any learning rate λ > 0, we only need to address the selection of the λs grid and optimize across λ to achieve our final bound on R black-box[T ].Learning rate grid. The dynamic regret of Eq. ( 10) implies that any two λ that are a constant factor of each other will guarantee the same upper-bound up to essentially the same constant factor. We therefore choose an exponentially spaced gridEQUATION)The meta-algorithm aggregation scheme guarantees that the learner performs as well as the best empirical learning rate. We thus obtain a bound on R black-box[T ], with its proof in Appendix E:Proposition 5.4 (Black-box regret bound). Assume MetaCURL is played with a black-box algorithm satisfying dynamic regret as in Eq. (10) , with learning rate grid as in Eq. (15) . Hence, for any sequence of policies(π t, * ) t∈[T ] , R black-box [T ] (π t, * ) t∈[T ] ≤ N c 2 ∆ π * + c 3 c 1 + c 1 √ T + 3 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m .Greedy MD-CURL. Greedy MD-CURL, developed by [39] , is a computationally efficient policyoptimization algorithm known for achieving sublinear static regret in online CURL with adversarial objective functions within a stationary MDP. In Thm. G.3 of Appendix G, we extend this analysis showing that Greedy MD-CURL also achieves dynamic regret as in Eq. (10) . To our knowledge, this is the first dynamic regret result for a CURL algorithm. Hence, Greedy MD-CURL can be used as a black-box for MetaCURL. We detail Greedy MD-CURL in Alg. 4 in Appendix G.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: This is a theoretical paper, with no experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion, discussion, and future work: 
 In this paper, we present MetaCURL, the first algorithm for dealing with non-stationarity in CURL, a setting covering many problems in the literature that modifies the standard linear RL configuration, making typical RL techniques difficult to use. We also employ a novel approach to deal with nonstationarity in MDPs using the learning with expert advice framework from the online learning literature. The main difficulty in analyzing this method arises from uncertainty about probability transitions. We overcome this problem by employing a second expert scheme, and show that MetaCURL achieves near-optimal regret.Compared to the RL literature, our approach is more efficient, deals with adversarial losses, and has a better regret dependency concerning the varying losses, but to do so, we need to simplify the assumptions about the dynamics (all uncertainty comes only from the external noise, that is independent of the agent's state-action). There seems to be a trade-off in RL: all algorithms dealing with both non-stationarity and full exploration use UCRL-type approaches, and are thus computationally expensive. We thus leave a question for future work: How can we effectively manage non-stationarity and adversarial losses using efficient algorithms, all while addressing full exploration?A Learning with expert adviceIn this section, we take a closer look at the Learning with Expert Advice (LEA) framework. We start by presenting, in Subsection A.1, a general reduction of the sleeping experts framework to the standard framework. Thus, any LEA algorithm can be used as a sub-routine for MetaCURL.In Section 5 of the main paper, we show a regret bound for MetaCURL using the Exponentially Weighted Average Forecaster (EWA) algorithm [9] , also known as Hedge. In Subsection A.2 we present the main results of playing EWA with convex and exp-concave losses.Setting. We recall the general setting of learning with expert advice (LEA) as presented in the main paper: a learner makes sequential online predictions u 1 , . . . , u T in a decision space U, over a series of T episodes, with the help of K experts. For each round t, each expert k makes a prediction u t,k , and the learner combines the experts' predictions by computing a vector v t := (v t,1 , . . . , v t,K ) ∈ S K , and predicting u t := K k=1 v t,k u t,k . The environment then reveals a convex loss function ℓ t : U → R. Each expert suffers a loss ℓ t,k := ℓ t (u t,k ), and the learner suffers a loss lt := ℓ t (u t ). The learner's objective is to keep the cumulative regret with respect to each expert as low as possible. For each expert k, this quantity is defined as Reg[T ] (k) := T t=1 lt -ℓ t,k .Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: This is a theoretical paper, with no 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 a 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. 
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, with no 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, confidence 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.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• 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). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The results presented in this paper are largely theoretical. The framework provided in this paper is very general and could be applied to any reinforcement learning or concave utility reinforcement learning problem in a tabular MDP. Therefore, as with any reinforcement learning algorithm, it is possible that the algorithms developed from the ideas presented in this paper could be applied in contexts that have negative societal impacts, or in contexts where the reward function has a negative negative societal impacts.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). 
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 paper poses no such risks.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 paper 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators.  
 
 Appendix: The sleeping expert problem [8, 23] is a LEA framework where experts are not required to provide solutions at every time step. Let I t,k ∈ {0, 1} define a binary signal that equals 1 if expert k is active at episode t and 0 otherwise. The algorithm knows (I t,k ) k∈[K] and assigns a zero weight to sleeping experts. We would like to have a guarantee with respect to expert k ∈ [K] but only when it is active. Hence, we now aim to bound a cumulative regret that depends on the signalI t,k : Reg sleep [T ] (k) := T t=1 I t,k ( lt -ℓ t,k). We present a generic reduction from the sleeping expert framework to the standard LEA framework [3, 2] :Let, for all episodes t ∈ [T ], ût := K k=1 I t,k v t,k u t,k K k=1 I t,k v t,k .We play a standard LEA algorithm with modified outputs where, at episode t, expert k outputs ũt,k := u t,k , if k is active at episode t ût , if not.A standard LEA algorithm gives an upper bound on the regret Reg T (k) with respect to each expert k.Using thatK k=1ũt,k v t,k = ût , we obtain thatReg [T ] (k) := T t=1 ℓ t K k=1 ũt,k v t,k -ℓ t (ũ t,k ) = T t=1 ℓ t (û t ) -ℓ t (ũ t,k ) = T t=1 I t,k ℓ t (û t ) -ℓ t (u t,k ) =: Reg sleep [T ] (k).Consequently, the cumulative regret with respect to each expert during the times it is active is upper bounded by the standard regret of playing a LEA algorithm with the modified outputs.The exponentially weighted average forecaster (EWA), also called Hedge, is a LEA algorithm that chooses a weight that decreases exponentially fast with past errors. We present EWA in Alg. 2.Algorithm 2 EWA (Exponentially Weighted Average) Input: [K] := {1, . . . , K} a finite set of experts, v 0 a prior over [K], a learning rate η > 0 for t ∈ {1, . . . , T } do Observe loss function ℓ t , compute the loss suffered by each expert ℓ t,k := ℓ t (u t,k ) and sufferloss lt := ℓ K k=1 v t,k u t,k Update for all k ∈ [K] : v t+1,k = v t,k exp (-ηℓ t,k ) K k ′ =1 v t,k ′ exp (-ηℓ t,k ′ ) end forWe recall two results of playing EWA with convex losses, and with exp-concave losses, used in the main paper: Theorem A.1 (EWA with convex losses: Corollary 2.2 from [9] ). If the ℓ t losses are convex and take value in [0, 1], then the regret of the learner playing EWA with any η > 0 satisfies, for any k ∈ [K],Reg [T ] (k) ≤ log(K) η + T η 8 .In particular, with η = 8 log(K)/T , the upper bound becomes (T /2) log(K).Theorem A.2 (EWA with exp-concave losses: Thm. 3.2 from [9] ). If the ℓ t losses are η-exp concave, then the regret of the learner playing EWA (with the same value of η) satisfies, for any k ∈ [K],Reg [T ] (k) ≤ log(K) η .B Algorithm for the online estimation of the probability kernel (p t estimator) for (n, x, a) ∈ [N ] × X × A do 4: Compute x t n,x,a = g n-1 (x, a, ε t n-1 ) 5:Update the empirical estimations for s < t and x ′ ∈ X :pt,s n (x ′ |x, a) = 1 {x t n,x,a =x ′ } t-s + (t-1-s) t-s pt-1,s n (x ′ |x, a) 6:Initialize a new estimator, pt,t n (x ′ |x, a) = 1 {x t n,x,a =x ′ } for all x ′ ∈ X ,We start with some auxiliary results. For t ∈ I := [t s + 1, t e ] ⊆ [T ], we define the average probability distribution for all n and (x, a) asp t (x ′ |x, a) = 1 t -t s t-1 s=ts p s n (x ′ |x, a).Lemma C.1. Let pt,ts be the empirical probability transition kernel computed with data from episodes [t s , t -1]. For any δ ∈ (0, 1), with probability 1 -δ,∥p t,ts n (•|x, a) -p t n (•|x, a)∥ 1 ≤ 1 2(t -t s ) log N |X ||A|2 |X | T δ , simultaneously for all n ∈ [N ], (x, a) ∈ X × A, t s ∈ [T -1], and t ∈ [t s + 1, T ].Proof. For a fixed n ∈ [N ], (x, a) ∈ X × A, and θ ∈ {-1, 1} |X | , we define for all s ∈ I, Y s n,x,a,θ :=x ′ ∈X θ(x ′ )1 {gn(x,a,ε s n )=x ′ } ,a Bernoulli random variable with mean value given by x ′ ∈X θ(x ′ )p s n (x ′ |x, a).The sequence of random variables given by Y s n,x,a,θ s∈I is independent, as we assume that the external noises observed at each episode are all independent. Hence, by Hoeffding's inequality we get that, for all ξ > 0,P t-1 s=ts Y s n,x,a,θ -E t-1 s=ts Y s n,x,a,θ ≥ ξ ≤ exp -2ξ 2 t -t s .Therefore, we have thatP x ′ ∈X θ(x ′ ) pt,ts n (x ′ |x, a) -p t n (x ′ |x, a) ≥ ξ = P 1 t -t s t-1 s=ts x ′ ∈X θ(x ′ )1 {gn(x,a,ε s n )=x ′ } - t-1 s=ts θ(x ′ )p s n (x ′ |x, a) ≥ ξ = P 1 t -t s t-1 s=ts Y s n,x,a,θ -E t-1 s=ts Y s n,x,a,θ ≥ ξ ≤ exp -2ξ 2 (t -t s ) .By applying an union bound on all n ∈ [N ], (x, a) ∈ X × A, and θ ∈ {-1, 1} |X | and noting that, for any two probability distributions p, q ∈ ∆ X , we have that∥p -q∥ 1 = max θ∈{-1,1} |X | x∈X θ(x)(p(x) -q(x)),we arrive at the final result.Lemma C.2. Let t ∈ I := [t s + 1, t e ] ⊆ [T ]. For all n ∈ [N ], and (x, a) ∈ X × A, ∥p t n (•|x, a) -p t n (•|x, a)∥ 1 ≤ t-1 j=ts ∆ p j ,Proof. For t ∈ I, and for all n and (x, a) we have that∥p t n (•|x, a) -p t n (•|x, a)∥ 1 = x ′ ∈X p t n (x ′ |x, a) - 1 t -t s t-1 s=ts p s n (x ′ |x, a) = x ′ ∈X 1 t -t s t-1 s=ts p t n (x ′ |x, a) -p s n (x ′ |x, a) ≤ 1 t -t s t-1 s=ts t j=s+1 ∥p j n (•|x, a) -p j-1 n (•|x, a)∥ 1 = 1 t -t s t-1 j=ts (j -t s )∥p j n (•|x, a) -p j-1 (•|x, a)∥ 1 ≤ t-1 j=ts ∆ p j ,where recall that we define ∆ p j := max n,s,a ∥p j+1 n (•|x, a) -p j n (•|x, a)∥ 1 .Lemma C.3. Let pt,ts be the empirical probability transition kernel computed with data from episodes [t s , t -1]. For any δ ∈ (0, 1), with probability 1 -δ,∥p t n (•|x, a) -pt,ts n (•|x, a)∥ 1 ≤ 1 2(t -t s ) log N |X ||A|2 |X | T δ + t-1 j=ts ∆ p j , simultaneously for all n ∈ [N ], (x, a) ∈ X × A, t s ∈ [T -1], and t ∈ [t s + 1, T ].Proof. The result follows immediately from the triangular inequality and Lemmas C.1 and C.2.Let p ′ , q ′ be any distributions over S X . DefineEQUATION, and q :=q ′ + 1 |X | 2 .Therefore,KL(p | q) ≤ 2|X |∥p -q∥ 2 1 .Proof. First, note that q is lower bounded by 1 2|X | , hence KL(p | q) is well defined. Also, by convexity of the simplex, p, q ∈ S X , thereforeKL(p | q) = x∈X p(x) log p(x) q(x) = x∈X p(x) log 1 + p(x) q(x) -1 ≤ x∈X p(x) p(x) q(x) -1 = x∈X p(x) q(x) p(x) -q(x) + x∈X q(x) -p(x) = x∈X p(x) -q(x) 2 q(x) ≤ 1 min x∈X q(x) ∥p -q∥ 2 ≤ 2|X |∥p -q∥ 2 1 .Lemma C.5. For any strategy π ∈ (S A ) X ×N , for any two probability kernels p = (p n ) n∈[N ] and q = (q n ) n∈[N ] such that p n , q n : X × A × X → [0, 1], and for all n ∈ [N ],∥µ π,p n -µ π,q n ∥ 1 ≤ n-1 i=0 x,a µ π,p i (x, a)∥p i+1 (•|x, a) -q i+1 (•|x, a)∥ 1 .Proof. From the definition of a state-action distribution sequence induced by a policy π in a MDP with probability kernel p in Eq. ( 2), we have that for all (x, a) ∈ X × A and n ∈ [N ],µ π,p n (x, a) = x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )p n (x|x ′ , a ′ )π n (a|x).Thus,∥µ π,p n -µ π,q n ∥ 1 = x,a µ π,p n (x, a) -µ π,q n (x, a) = x,a x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )p n (x|x ′ , a ′ ) -µ π,q n-1 (x ′ , a ′ )q n (x|x ′ , a ′ ) π n (a|x) = x x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )p n (x|x ′ , a ′ ) -µ π,q n-1 (x ′ , a ′ )q n (x|x ′ , a ′ ) = x x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )p n (x|x ′ , a ) -µ π,p n-1 (x ′ , a ′ )q n (x|x ′ , a ′ ) + µ π,p n-1 (x ′ , a ′ )q n (x|x ′ , a ′ ) -µ π,q n-1 (x ′ , a ′ )q n (x|x ′ , a ′ ) ≤ x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )∥p n (•|x ′ , a ′ ) -q n (•|x ′ , a ′ )∥ 1 + x ′ ,a ′ µ π,p n-1 (x ′ , a ′ ) -µ π,q n-1 (x ′ , a ′ ) = x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )∥p n (•|x ′ , a ′ ) -q n (•|x ′ , a ′ )∥ 1 + ∥µ π,p n-1 -µ π,q n-1 ∥ 1 .Since for n = 0, ∥µ π,p 0 -µ π,q 0 ∥ 1 = 0, by induction we get that∥µ π,p n -µ π,q n ∥ 1 ≤ n-1 i=0 x ′ ,a ′ µ π,p i (x ′ , a ′ )∥p i+1 (•|x ′ , a ′ ) -q i+1 (•|x ′ , a ′ )∥ 1 .Lemma C.6. For any pair of strategies π, π ′ ∈ (∆ A ) X ×N , for any probability kernel p = (p n ) n∈[N ] such that p n : X × A × X → [0, 1], and for all n ∈ [N ],∥µ π,p n -µ π ′ ,p n ∥ 1 ≤ n i=1 x∈X ρ π,p i (x)∥π i (•|x) -π ′ i (•|x)∥ 1 ,where ρ π,p i (x) := a∈A µ π,p i (x, a) for all x ∈ X and i ∈ [N ].Proof. Using the recursive relation from Eq. ( 2) of a state-action distribution induced by a policy π in a MDP with probability transition p we have that∥µ π,p n -µ π ′ ,p n ∥ 1 = x,a µ π,p n (x, a) -µ π ′ ,p n (x, a) ≤ x,a x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )π n (a|x) -µ π ′ ,p n-1 (x ′ , a ′ )π ′ n (a|x) p n (x|x ′ , a ′ ) ≤ x,a x ′ ,a ′ µ π,p n-1 (x ′ , a ′ )p n (x|x ′ , a ′ ) π n (a|x) -π ′ n (a|x) + x,a x ′ ,a ′ π ′ n (a|x)p n (x|x ′ , a ′ ) µ π,p n-1 (x ′ , a ′ ) -µ π ′ ,p n-1 (x ′ , a ′ ) = x ρ π,p n (x)∥π n (•|x) -π ′ n (•|x)∥ 1 + ∥µ π,p n-1 -µ π ′ ,p n-1 ∥ 1 .Since µ 0 is fixed for each state-action distribution sequence, by induction we obtain that∥µ π,p n -µ π ′ ,p n ∥ 1 ≤ n i=1 x ρ π,q i (x)∥π t i (•|x) -π t-1 i (•|x)∥ 1 ,completing the proof.Proof. Here, we set an upper bound on the term R p [T ] where we pay for errors in estimating p t by pt .R p [T ] := T t=1 F t (µ π t ,p t ) -F t (µ π t , pt ) ≤ T t=1 ⟨∇F t (µ π t ,p t ), µ π t ,p t -µ π t , pt ⟩ ≤ L F T t=1 N n=1 ∥µ π t ,p t n -µ π t , pt n ∥ 1 ≤ L F T t=1 N n=1 n j=1 x,a µ π t ,p t j-1 a)∥p t j (•|x, a) -pt j (•|x, a)∥ 1 .To obtain the first inequality, we use the convexity of F t for all t ∈ [T ], then we use Holder's inequality and the fact that F t is L F -Lipschitz, and for the last inequality we use Lemma C.5.The difficulty in analyzing the L 1 difference between p t and pt arises from the non-stationarity of p t .To overcome this we want to use the scheme presented in Subsection 4.3. By Cauchy-Schwartz, we get thatEQUATION)Analysis of the L 1 norm. We start by analysing the sum over t ∈ [T ] of the L 1 norm in term ( * ).For each n ∈ [N ], j ∈ [n] and (x, a) ∈ X × A, T t=1 ∥p t j (•|x, a) -pt j (•|x, a)∥ 2 1 = 4 T t=1 p t j (•|x, a) + 1 |X | 2 - pt j (•|x, a) + 1 |X | 2 2 1 ≤ 8 T t=1 KL p t j (•|x, a) + 1 |X | 2 pt j (•|x, a) + 1 |X | 2 ,where we apply Pinsker's inequality.Consider a sequence of episodes 1 = t 1 < t 2 < . . . < t m+1 = T + 1, withI i := [t i , t i+1 -1], such that ∆ p Ii ≤ ∆ p /m for all i ∈ [m].Decomposing the KL sum over t ∈ [T ] as a sum on the intervals I i , we obtain thatT t=1 KL p t j (•|x, a) + 1 |X | 2 pt j (•|x, a) + 1 |X | 2 = m i=1 t∈Ii KL p t j (•|x, a) + 1 |X | 2 pt,ti j (•|x, a) + 1 |X | 2 (i) + m i=1 t∈Ii E xt j,x,a log pt,ti j (x t j,x,a |x, a) + 1 |X | 2 -log pt j (x t j,x,a |x, a) + 1 |X | 2 (ii), where the expectation of the second term is with respect to xt j,x,a ∼ p t j (•|x, a) + 1 |X | /2. We analyse each term separately: First, note that (ii) is the expectation over xt j,x,a of the cumulative regret of sleeping EWA on interval I i with respect to the expert t i using the loss function ℓ t defined in Eq. ( 12). This term is upper bounded by log(T ) (see Subection 4.3 of the main paper). From it we deduce that(ii) ≤ m i=1 log(T ) = m log(T ).Regarding term (i), we start by using the inverse of Pinsker's inequality presented in Lemma C.4,(i) ≤ m i=1 t∈Ii 2|X | p t j (•|x, a) + 1 |X | 2 - pt,ti j (•|x, a) + 1 |X | 2 2 1 = m i=1 t∈Ii |X | 2 ∥p t j (•|x, a) -pt,ti j (•|x, a)∥ 2 1 .To simplify notations, from now on we letC := 1 2 log N |X ||A|2 |X | T δ . Applying Lemma C.3, we obtain that m i=1 t∈Ii |X | 2 ∥p t j (•|x, a) -pt,ti j (•|x, a)∥ 2 1 ≤ |X | 2 m i=1 t∈Ii C 2 t -t i + 1 + 2C √ t -t i + 1 t-1 k=ti ∆ p k + t-1 k=ti ∆ p k 2 ≤ |X | 2 m i=1 C 2 log(|I i |) + 2C |I i |∆ p Ii + |I i |(∆ p Ii ) 2 ≤ |X | 2 C 2 m log(T ) + 2C √ T ∆ p √ m + T (∆ p ) 2 m 2 .Joining the upper bounds of (i) and (ii) we conclude thatT t=1 ∥p t j (•|x, a) -pt j (•|x, a)∥ 2 1 ≤ 8 (i) + (ii) ≤ 8 (C 2 |X | 2 + 1)m log(T ) + 2 |X | 2 C √ T ∆ p √ m + T |X | 2 (∆ p ) 2 m 2 .Thus, for m =EQUATION)Back to the analysis of R p [T ] . Using the inequality in Eq. ( 17) to bound the L 1 norm of ( * ) on Eq. ( 16), we obtain thatR p [T ] ≤ L F N √ T N n=1 n-1 j=1 x,a 12|X |C 4/3 log(T ) 2/3 T 1/3 (∆ p ) 2/3 ≤ 2L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 T 2/3 (∆ p ) 1/3 , concluding the proof.Note that for m i=1 t∈Ii R p Ii (π t,ti,λ ) (the third term of the meta-regret decomposition of Eq. ( 13)), following the same procedure as above, we obtain that m i=1 t∈IiF t (µ π t,t i , pt ) -F t (µ π t,t i ,p t ) ≤ m i=1 t∈Ii ⟨∇F t (µ π t,t i , pt ), µ π t,t i , pt -µ π t,t i ,p t ⟩ ≤ L F m i=1 t∈Ii ∥µ π t,t i , pt n -µ π t,t i ,p t n ∥ 1 ≤ L F m i=1 t∈Ii N n=1 n j=1 x,a µ π t,t i ,p t j-1 (x, a)∥p t j (•|x, a) -pt j (•|x, a)∥ 1 ≤ L F m i=1 t∈Ii N n=1 n j=1 x,a (µ π t,t i ,p t j-1 (x, a)) 2 ≤T N 2 T t=1 N n=1 n j=1 x,a ∥p t j (•|x, a) -pt j (•|x, a)∥ 2 1 independent of π t,t i .Since the second term is independent of π t,ti , the analysis is the same as before and we obtain the same upper bound as for R p [T ] (π t ).E Proof of Prop. 5.4: R black-box[T ]Proof. Assume a Black-box algorithm satisfying the dynamic regret bound of Eq. ( 10), i.e., for any interval I ⊆ [T ], with respect to any sequence of policies (π t, * ) t∈I , and for any learning rate λ,EQUATION)Consider any sequence of episodes 1 = t 1 < t 2 < . . . < t m+1 = T + 1, forming intervalsI i := [t i , t i+1 -1] for all i ∈ [m].We can decompose the black-box regret over [T ] asR black-box [T ] (π t, * ) t∈[T ] = m i=1 t∈Ii F t (µ π t,t i ,λ ,p t ) -F t (µ π t, * ,p t ) ≤ m i=1 c 1 λ|I i | + c 2 ∆ π * Ii + c 3 λ + |I i |∆ p I ≤ c 1 λT + c 2 ∆ π * + c 3 λ + T ∆ p m .In principle, we would like to select the optimal λ that optimizes this dynamic regret. However, as ∆ π * may be unknown in advance, this is not possible. We show here that running MetaCURL with the learning rate set Λ := {2 -j |j = 0, 1, 2, . . . , ⌈[log 2 (T )/2⌉} ensures that the optimal empirical learning rate is close to the true optimal one by a factor of 2 and that the learner always plays as well as the optimal empirical learning rate.Denote by λ * the optimal learning rate and λ * the empirical optimal learning rate in Λ. Note thatλ * = c 2 ∆ π * + c 3 c 1 T .We consider three different cases:If λ * ≥ 1: this implies that c2∆ π * +c3 c1T ≥ 1. Therefore, we have that T ≤ c2∆ π * +c3 c1. As we assume f t n ∈ [0, 1] for all time steps n ∈ [N ] and episodes t ∈ [T ], thenR black-box [T ] (π t, * ) t∈[T ] ≤ N T + T ∆ p m ≤ N c 2 ∆ π * + c 3 c 1 + T ∆ p m . If λ * ≤ 1/ √ T : this implies that c2∆ π * +c3 c1 ≤ 1. Therefore, taking λ * = 1/ √ T ∈ Λ, we have that R black-box [T ] (π t, * ) t∈[T ] ≤ λc 1 T + c 1 λ + T ∆ p m ≤ c 1 √ T + T ∆ p m If λ * ∈ [1/ √ T , 1]: in this case, given the construction of Λ, there is a λ * ∈ Λ such that λ * ≤ λ * ≤ 2λ * . Hence, R black-box [T ] (π t, * ) t∈[T ] ≤ 3 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m .Therefore, by taking λ = λ * in the analysis, we can ensure thatR black-box [T ] (π t, * ) t∈[T ] = m i=1 t∈Ii F t (µ π t,t i ,λ ,p t ) -F t (µ π t, * ,p t ) ≤ N c 2 ∆ π * + c 3 c 1 + c 1 √ T + 3 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m .F Proof of Thm. 5.1: Main resultJoining the results from the meta-regret bound and the black-box regret bound, we get the main result of the paper: Theorem (Main result). Let δ ∈ (0, 1). Playing MetaCURL, with black-box algorithm with dynamic regret as in Eq. ( 10), with a learning rate grid Λ := 2 -j |j = 0, 1, 2, . . . , ⌈1/2 log 2 (T )⌉ , and with EWA as the sleeping expert subroutine, we obtain, with probability at least 1 -2δ, for any sequence of policies (π t, * ) t∈[T ] ,R [T ] (π t, * ) t∈[T ] ≤ Õ √ ∆ π * T + min T ∆ p ∞ , T 2/3 (∆ p ) 1/3 .Proof. Define a sequence of episodes 1 = t 1 < t 2 < . . . < t m+1 = T + 1, withI i := [t i , t i+1 -1], such that ∆ p Ii ≤ ∆ p /m for all i ∈ [m]. The dynamic regret of M(E, Λ) with respect to any sequence of policies (π t, * ) t∈[T ] , and any λ ∈ Λ, can be decomposed asR [T ] (π t, * ) t∈[T ] = m i=1 t∈Ii F t (µ π t ,p t ) -F t (µ π t,t i ,λ ,p t ) Meta algorithm regret + m i=1 t∈Ii F t (µ π t,t i ,λ ,p t ) -F t (µ π t, * ,p t ) Black-box regret on Ii . := R meta [T ] + R black-box [T ] (π t, * ) t∈[T ] .From Prop. 5.3, we have that with probability at least 1 -2δ, andC := 1 2 log N |X ||A|2 |X | T δ , R meta [T ] ≤ 4L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 T 2/3 (∆ p ) 1/3 + mT 2 log(T |Λ|).In addition, for Λ := 2 -j |j = 0, 1, 2, . . . , ⌈1/2 log 2 (T )⌉ , and λ equal the best empirical learning rate in Λ, Prop. 5.4 yields that, if the black-box algorithm has dynamic regret as in Eq. ( 10) for any interval in T , thenR black-box [T ] (π t, * ) t∈[T ] ≤ N c 2 ∆ π * + c 3 c 1 + c 1 √ T + 3 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m .Therefore, joining both results, we get that,R [T ] (π t, * ) t∈[T ] ≤ 4L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 T 2/3 (∆ p ) 1/3 + mT 2 log(T log 2 (T )) + N c 2 ∆ π * + c 3 c 1 + c 1 √ T + 3 c 1 (c 2 ∆ π * + c 3 m)T + T ∆ p m .Thus, for m = 2√ T ∆ p γ 2/3, with γ := log(T log 2 (T ))2+ 3 √ c 1 c 3 , we have that R [T ] (π t, * ) t∈[T ] ≤ T 2/3 ∆ 1/3 4L F N 2 |X | 3|A|C 2/3 log(T ) 1/3 + 2γ 2/3 + N c 2 ∆ π * + c 3 c 1 + c 1 √ T + 3 c 1 c 2 ∆ π * T = Õ √ ∆ π * T + min T ∆ p ∞ , T 2/3 (∆ p ) 1/3 .Here we introduce Greedy MD-CURL developed by [39] , a computationally efficient policyoptimization algorithm known for achieving sublinear static regret in online CURL with adversarial objective functions within a stationary MDP. We begin by detailing Greedy MD-CURL as presented in [39] in Alg. 4. We then provide a new analysis upper bounding the dynamic regret of Greedy MD-CURL in a quasi-stationary interval valid for any learning rate λ. Hence, Greedy MD-CURL can be used as a black-box for MetaCURL. This is the first dynamic regret analysis for a CURL approach.Let M p, * µ0 denote the subset of M p µ0 where the corresponding policies π are such that π n (a|x) ̸ = 0 for all (x, a) ∈ X × A, n ∈ [N ]. For any probability transition p, Γ : M p µ0 × M p, * µ0 → R such that, for all µ ∈ M p µ0 with its associated policy π, and µ ′ ∈ M p, * µ0 with its associated policy π ′ , we haveEQUATIONThis divergence Γ is a Bregman divergence (see Proposition 4.3 of [39] ). Problem (20) implemented with this Bregman divergence Γ has a closed form solution, as showed in [39] .Algorithm 4 Greedy MD-CURL 1: Input: number of episodes T , initial sequence of policies π 1 ∈ (S A ) X ×N , initial state-action distribution µ 0 , learning rate λ > 0, sequence of parameters (α t ) t∈[T ] .2: Initialization: ∀(x, a), p1 (•|x, a) = 1 |X | and µ 1 = μ1 := µ π 1 , p1 3: for t = 1, . . . , T do 4:Agent starts at (x t 0 , a t 0 ) ∼ µ 0 (•)5:for n = 1, . . . , N doEnvironment draws new statex t n ∼ p n (•|x t n-1 , a t n-1 ) 7:Learner observes agent's external noise ε t n 8:Agent chooses an actiona t n ∼ π t n (•|x t n ) 9:end for 10:Update probability kernel estimate for all (x, a):11: pt+1 n (•|x, a) := 1 t δ gn(x,a,ϵ t n ) + t -1 t pt n (•|x, a) 12:Compute policy for the next episode:13:EQUATIONfor all n ∈ [N ], (x, a) ∈ X × A,π t+1 n (a|x) = µ t+1 n (x, a) a ′ ∈A µ t+1 n (x, a ′ ) 15: Compute πt+1 := (1 -α t+1 )π t+1 + α t+1 /|A| 16: Compute μt+1 := µ πt+1 , pt+1as in Eq. (2) 17: end for 18: return (π t ) t∈[T ]Let us assume we analyze our regret in an interval I := [t s , t e ] ⊆ [T ]. We denote by R I the dynamic regret of an instance of Greedy MD-CURL started at episode t s until the end of interval I at episode t e . We denote by π t the policy produced by this instance of Greedy MD-CURL at episode t ∈ I, p t the true probability transition kernel, andpt n (x ′ |x, a) = 1 t -t s t-1 s=ts 1 {gn(x,a,ε s n )=x ′ } ,the empirical estimate of the probability kernel at episode t, with data from the beginning of the interval I.We define and decompose the dynamic regret R I with respect to any sequence of policies (π t, * ) t∈I into three terms as follows:EQUATION)The terms R MDP I (π t ) and R MDP I (π t, * ) pay for our lack of knowledge of the true MDP, forcing us to use its empirical estimate. The term R policy I corresponds to the loss incurred in calculating the policy by solving the optimization problem given in Eq. (20) . Below, we present the first analysis of the dynamic regret for a CURL algorithm. We consider each term separately.In Section 2 we assume that the deterministic part of the dynamics, given by g n in equation ( 8) for each time step n, is known in advance. The source of uncertainty and non-stationarity in the MDP comes only from the external noise dynamics, that is independent of the agent's state-action pair. Therefore, we do not need to explore in this setting, so the analysis of the two terms R MDP Proof. We start by using the convexity of F t , Holder's inequality, that F t is L F -Lipschitz, and Lemma C.5 to obtain thatEQUATIONApplying Lemmas C.1 and C.2, we have that for any δ ∈ (0, 1), with probability 1 -δ,∥p t j (•|x, a) -pt j (•|x, a)∥ 1 ≤ ∥p t j (•|x, a) -p t j (•|x, a)∥ 1 + ∥p t j (•|x, a) -pt j (•|x, a)∥ 1 ≤ 1 2(t -t s ) log N |X ||A|2 |X | T δ + t-1 k=ts ∆ p k .Using this to continue the upper bound of Eq. ( 22), we conclude our proof: Then, Greedy MD-CURL obtains, for any sequence of policies (π t, * ) t∈I , and for any learning rate λ > 0,R MDP I (π t ) ≤ L F N 2 te t=ts 1 2(t -t s ) log N |X ||A|2 |X | T δ + t-1 k=ts ∆ p k ≤ L F N 2 1 2 log N |X ||A|2 |X | T δ |I| + |I|∆ p I .R policy I (π t, * ) t∈I ≤ λL 2 F |I| + N 2 λ ∆ π * I + b 1 λ .Proof. We adapt the proof of Prop. 5.7 of [39] that upper bounds the static regret incurred when solving the optimization Problem (20) , for a proof that upper bounds the dynamic regret. The main difference is that, in the case of static regret, we compare ourselves to the same policy throughout the interval, whereas in the case of dynamic regret, at each episode we compare ourselves to a different policy given by π t, * . Consequently, the analysis remains the same as in [39] for all terms that do not depend on π t, * , but requires a new analysis in terms that do depend on it.To simplify notation, we take ℓ t := ∇F t (µ π t , pt ) and µ t := µ π t , pt . We can use the same reasoning as in appendix D.5 of [39] to show thatR policy I ≤ 1 λ t∈I λ⟨ℓ t , µ t -µ t+1 ⟩ -Γ(µ t+1 , μt ) A + 1 λ t∈I Γ(µ π t, * , pt+1 , μt ) -Γ(µ π t, * , pt+1 , µ t+1 ) B .Since the A term does not depend on π t, * , its analysis follows directly from [39] , and is given byEQUATIONwhere L F is the Lipschitz constant of F t and α t is an input parameter of Greedy MD-CURL.We then proceed to analyze term B. Again, following the procedure of appendix D.5 of [39] , we obtain thatEQUATIONEQUATION.Let ψ : (S X ×A ) N → R denote the function inducing the Bregman divergence Γ of Eq. ( 19). [39] further shows that:• (i) ≤ -ψ(µ π t i -1, * , pt i ) + N t∈I log |A| αt ∥µ π t-1, * , pt -µ π t, * , pt+1 ∥ ∞,1• (ii) ≤ 2N t∈I α t , and this upper bound is found independently of π t, *• (iii) ≤ Γ(µ π t-1, * , pt , µ t ).Lemma D.6 of [39] shows that, -ψ(µ π t i -1, * , pt i ) + Γ(µ π t i -1, * , pt i , µ ti ) ≤ N log(|A|).Only term (i), which involves ∥µ π * ,t-1 , pt -µ π * ,t , pt+1 ∥ ∞,1 , depends on the sequence (π t, * ) t∈[T ] , requiring then a new analysis. For this purpose, we rely on the following two results:• From Lemma 5.6 of [39] , we have that, for all strategies π,∥µ π, pt -µ π, pt+1 ∥ ∞,1 ≤ 2N t -t s .• From auxiliary Lemma C.6 proved in Appendix C we have that∥µ π * ,t-1 , pt+1 n -µ π t, * , pt+1 n ∥ 1 ≤ n i=1 x∈X ρ π t-1, * i (x)∥π t, * i (•|x) -π t-1, * i ∥ 1 ≤ N ∆ π * t .Therefore, using the triangular inequality and the two results above, we obtain that∥µ π * ,t-1 , pt -µ π t, * , pt+1 ∥ ∞,1 ≤ ∥µ π t-1, * , pt -µ π t-1, * , pt+1 ∥ ∞,1 + ∥µ π t-1, * , pt+1 -µ π t, * , pt+1 ∥ ∞,1 ≤ 2N t + N ∆ π * t .Therefore, the bound on term B is given byEQUATION)Final step: joining all resultsJoining the upper bounds on term A from Eq. ( 23) and on term B from Eq. ( 24), we have thatR policy I (π t, * ) t∈I ≤ A + B ≤ λL 2 F |I| + 1 2λ t∈I 2N t -t s + 2N α t 2 + 1 λ N t∈I log |A| α t 2N t -t s + N ∆ π * t + 2N t∈I α t + N log(|A|) .If we take the learning rate as α t = 1/t, then, for all λ > 0, Let δ ∈ (0, 1). With probability at least 1 -2δ, for any interval I ⊆ [T ], for any sequence of policies (π t, * ) t∈I , for any learning rate λ > 0, and for α t := 1/t, Greedy MD-CURL obtainsR policy I (π t, * )t ∈ I ≤ λL 2 F |I| + N 2 λ ∆ π * I + 1 λ 8N 2 + 2NR I (π t, * ) t∈I ≤ λL 2 F |I| + N 2 ∆ π * I + b λ + 2F N 2 1 2 log N |X ||A|2 |X | T δ |I| + 2|I|∆ p IHence, Greedy MD-CURL meets the requisite dynamic regret bound from Eq. ( 10) to serve as a black-box algorithm for MetaCURL achieving optimal dynamic regret.(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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 be possible for other researchers to have some path to reproducing or verifying the results. 


Decision: This work explores online learning in non-stationary Markov decision processes (MDPs) where losses are non-linear and probability transitions are subject to change. The authors design an algorithm, MetaCURL, that runs multiple black box experts experts. Even though such an approach is relatively standard when studying dynamic regret, the presence of non-linearity together with time-changing transition model makes the setting challenging compared to prior work.

The main concerns reviewers raised are twofold: 1) the additional assumption on the transition model in equation 8 seems limiting, and 2) lack of motivating examples in light of lack of experiments. Regarding 1), the reviewers and I are still in agreement this assumption is restrictive, however, since the setting considered in this work is significantly more challenging there's a merit in making such restrictive assumption as a first step. Regarding 2), the authors elaborated on several examples that motivates the assumption in equation 8 and the setting studied in this work in general.

In light of these I am happy to accept this work. Further, I ask the authors to expand on the motivation in the camera ready version  so the community will benefit from these observations, as well as combine other suggestions from the reviewers.

Reviews: review: paper_summary: paper_summary: This paper addresses online learning in non-stationary episodic loop-free Markov decision processes (MDPs) with changing losses and probability transitions. It extends the Concave Utility Reinforcement Learning (CURL) problem to handle convex performance criteria in state-action distributions, overcoming the non-linearity that invalidates traditional Bellman equations. The introduced MetaCURL algorithm, the first for non-stationary MDPs, runs multiple black-box algorithm instances over different intervals, using a sleeping expert framework to aggregate outputs. MetaCURL achieves optimal dynamic regret under partial information without prior knowledge of MDP changes, handling fully adversarial losses. This approach is expected to be of significant interest to the RL community.
strength_weakness: strength_weakness: My comments on weaknesses are listed below.
questions: questions: Thanks for the opportunity to review this paper. I have some questions as follows. 
[Major issues]

1. Novelty 

- The statement "non-requiring prior knowledge of the environment's variations" (lines 68-69) needs clarification. In Table 1, the dynamic regret of the proposed algorithms still depends on $\Delta^p_\infty$ and $\Delta^p$, which seem to contain information about environmental changes (lines 123-126). How does this align with the claim of not requiring prior knowledge?

2. Dynamic regret representation 

- The use of $\Delta^{\pi^\star}_t$ to represent the upper bound of dynamic regret requires further justification. While it may seem reasonable since the optimal policy is defined given the environment, what happens if the optimal policy is not unique? In such cases, $\Delta^{\pi^\star}_t$ could take multiple values, as there can be multiple optimal policies at times $t$ and $t+1$.

3. Dynamic hypothesis
 
- The dynamic hypothesis presented in line 128 appears to be a strong assumption. Reinforcement learning (RL) is inherently about learning from data, and assuming prior knowledge of how the environment operates seems misaligned with RL's principles. This assumption aligns more with traditional control theory, where the plant dynamics are known. In RL, even in model-based RL, the model is estimated, and the policy is learned simultaneously.

[Minnor issues]
1. Terminology
- The term "loop-free" used in the abstract needs clarification. This term is not commonly used in the context of learning but is more prevalent in control theory. Is "loop-free learning" akin to continual learning with infinite episodes? More precise terminology would help readers understand your contributions better.

2. Regarding with the related works. 
- It seems the paper lacks some recent related works (around 2023,2204)  in theoretical non-stationary RL works. Please include the following to keep the track. 

 [1] Lee, H., Ding, Y., Lee, J., Jin, M., Lavaei, J., & Sojoudi, S. (2024). Tempo adaptation in non-stationary reinforcement learning. Advances in Neural Information Processing Systems, 36.
[2] Feng, S., Yin, M., Huang, R., Wang, Y. X., Yang, J., & Liang, Y. (2023, July). Non-stationary reinforcement learning under general function approximation. In International Conference on Machine Learning (pp. 9976-10007). PMLR.
limitations: limitations: There is no limitations on potential negative societal impact .
paper_summary: paper_summary: This paper presents theoretical results on the CURL algorithm for non-stationary MDPs. The proposed meta CURL models non-stationarity factors using external noise and achieves low dynamic regret in near-stationary environments, with regret only related to the frequency and magnitude of changes. Overall, the work provides solid theoretical results for CURL and non-stationary RL. Although I am not an expert on RL theory (my focus is more on algorithms and applications), I would give an acceptance rating for this initial review and will be engaged in the discussion.
strength_weakness: strength_weakness: Since I am not an expert on RL theory, I have listed most of my questions in this section. 

Q1: In equation (8), the noise captures the non-stationary factors. Will these factors from different parts of the MDP (such as the reward function or state dynamics) separately influence or impact the major theory and regret bound?

Q2: In some non-stationary or meta RL works, the non-stationary or distribution change factors are not only from external noise but also from the agent’s policy itself. How does this affect the major theoretical results? Any comments on this point would be appreciated.
questions: questions: I put the questions in the above section.
limitations: limitations: I do not think this theoretical work could pose any potential negative societal impact.
paper_summary: paper_summary: The authors present a policy learning algorithm for non-stationary (+ uncertain) environments and convex utilities. 
The proposed algorithm is a meta-algorithm which runs multiple black-box algorithms and aggregates outputs with something they call a sleeping expert framework. The algorithm achieves optimal dynamic regret.
strength_weakness: strength_weakness: - The paper considers uncertain/non-stationary noise distribution. However, until 1/3rd of the paper, I got an impression of uncertain dynamics (without any structure assumption).  
- The paper is difficult to follow particularly section 3 from line 175 and section 4
questions: questions: - Are baselines the same as the black-box algorithms? 
- Line 164, what does parametric algorithm mean in this context
- Line 141 why do policy optimization algorithms have lower complexity?
- Any thoughts on how the algorithm changes if g_n is uncertain?

Comments for improving paper:
- line 13: we achieve ---> the algorithm achieves?
- line 15: "full adversarial losses, not just stochastic ones." is ill-posed
- I am familiar with both non-stationarity and uncertainty. However, since the paper builds on these two challenges, I would suggest explaining them (at least in a high-level) early in the introduction. Similarly, for the terms adversarial objectives and learner (line 50).
- Line 133-135: Please include it in the introduction (could be a bit vague) but it's important to note that the structure of MDP is already known and only the noise is uncertain. 
- Maybe write contributions as a paragraph, since points 2,3 are not contributions but explanations of point 1.
limitations: limitations: None
paper_summary: paper_summary: The paper studied the Concave Utility Reinforcement Learning (CURL) problem in non-stationary environments, which extends classical reinforcement learning (RL) to handle convex performance criteria in state-action distributions induced by agent policies. The paper proposed MetaCURL to address the challenges posed by non-stationary Markov Decision Processes (MDPs) with changing losses and probability transitions by using a meta-algorithm that aggregates multiple black-box algorithm instances over different intervals. The algorithm achieves optimal dynamic regret without requiring prior knowledge of the MDP changes, making it suitable for adversarial losses and providing a significant advancement in the RL community.
strength_weakness: strength_weakness: 1. The model falls into the tabular MDPs, where the state-action pairs are finite. I am wondering if similar technique can be applied to the case of function approximation. In addition, there is a missing related work on the non-stationary RL with function approximation [1].
2. The transition dynamics, while there are many suitable applications, is also restrictive for a theoretical work.


Feng et al., Non-stationary Reinforcement Learning under General Function Approximation, ICML, 2023.
questions: questions: Please see the weaknesses part.
limitations: limitations: No further limitations to be addressed
paper_summary: paper_summary: This paper focuses on CURL, i.e., the Concave Utility Reinforcement Learning problem, which can be treated an extension of traditional RL  to deal with convex performance criteria. The authors introduce MetaCURL for non-stationary MDPs. This is a theory heavy paper.
strength_weakness: strength_weakness: Actually, for readers (like me) are not an expert in CURL, some introductory examples are helpful. Additionall, it seems that this paper does not have any experiment.
questions: questions: First of all, I strongly recommend the authors to include at least one or two introductory examples or figures to show the high-level intuition of their settings and motivation. E.g., difference between RL and concave utility RL; a figure showing offline CURL and online CURL; why concave utility RL is important; why do we need to focus on non-stationarity; and so on. Some examples can be within the domains of robotics, medical treatment, and so on.

A good figure example can be found in Fig.1 of [1]. 

[1] Levine, Sergey, et al. "Offline reinforcement learning: Tutorial, review, and perspectives on open problems." arXiv preprint arXiv:2005.01643 (2020).

A good introductory example can be done by setting some parameters equal to low dimensions.

# Specific Questions about the Settings
1. Can your framework handle cases when the state or the action is continuous?
2. Do we need to assume the occupancy measure is non-zero?

# Inconsistent Notations
1. Authors mention that L247-248, "We assume T experts, with expert s active in interval [s, T]". Actually, such notations are very confusion. $t$ refers to the episode, but here $T$ represents the number of experts. Especially in L209, the authors mention "over a series of T episodes". Again, in L127, the authors mention that "for any interval $I \subseteq [T]$", what interval does $[T]$ represent, $[1:T]$ or $[t:T]$? It is extremely hard for readers to understand their paper with inconsistent notations.

2. In L248, the authors mention that "Expert s at episode t > s outputs". $s$ refers to the expert, how it can be compared with $t$? 

3. In L19, authors claim "episodes of length N". Does it mean that each episode has N steps? Do the authors need to assume each episode has the exactly same length?

4. In L248, Why N is treated as a function, $N(x')$? But in L19, authors claim "episodes of length N".

5. In L210, "For each round t". In L225, "In every episode t". Actually, from my perspective, round t is different from episode t.

6. Confusing exponent symbols and notations. In L268, $T^{2/3}$ represents T exponent $2/3$. Is that correct? In your Algorithm 1, symbol $F^{t}$ and $\hat{p}^{t+1}$ represent exponent $t$?

I strongly recommend the authors to introduce a notation table.

# Specific Questions about MetaCURL
As mentioned previously, because the notations are inconsistent, it is really hard for me to fully understand the proposed framework.

1. Learning with Expert Advice (LEA)

    1.1 Do you assume these K experts are optimal? What if there is limited expert knowledge?
    
    1.2 What if two experts contradict to each other? Will your algorithm take the average of these two values? E.g., for the state $s_1$, expert 1 takes $a_1$, expert_2 takes $-a_1$, What should be the expert loss in that case? Could you show some numerical intro examples?

2. The authors mention that "This problem can be reduced to the sleeping expert problem". However, it is still unclear how and why this problem can be reduced?
    2.1 The authors mention that "experts are not required to provide solutions at every time step". What if at certain step there is not any expert providing solutions? Is there a lower bound of the number of experts that have to be awake?

3. Does the agent have access to the "external noise sequence $\left(\varepsilon_{n}^{t}\right)$"? Because $\epsilon_{n}^{t} \sim h_{n}^{t}(\cdot)$, is there any information leakage?

4. Does the algorithm know which expert is active? Is that signal too strong? Can such information be learned?

5. What is the time complexity of algo. 1? 

6. Theorem 5.1
    
    6.1 In Theorem 5.1, why the complexity is determined by $\Delta^{\pi^{*}}$, $\Delta_{\infty}^{p}$ and $\Delta^{p}$ simultanously? What is the intuition of taking the minimum of abrupt and smooth variation? Under the worst case, should we take the maximum of such variations?

    6.2 In [2], their regret bound contains the dimenions for the state space, action space, and the length of each episode. Why in Theorem 5.1, they are not included? Does it mean that your algorithm will not change, when their dimensions are increasing? Still, because of the inconsistent $T$ notation, it is unclear such $T$ represents? (L247-248, "We assume T experts, with expert s active in interval [s, T]". In L209, the authors mention "over a series of T episodes".)

[2] Rosenberg, Aviv, and Yishay Mansour. "Online convex optimization in adversarial markov decision processes." International Conference on Machine Learning. PMLR, 2019.

7. Because there is not any experiment in the current version, I have general concerns over the practicality of the proposed method, e.g., infinite horizon or continuous spaces.
limitations: limitations: This paper does not have any introductory examples, or figures, or experiments. However, as such a notation dense paper, it seems that the notations are not consistent, making readers extremely hard to understand their major contributions. Additionally, the agents are assumed to have special strong information, e.g., experts signal or external noise sequence, which might be missing in real-world.

-----------------Updates

Thanks for the thoughtful discussions. After careful consideration, I have decided to maintain my current rating of 4.

tl&dr: Recommendation for Rejection: **The majority of reviewers (Reviewer unHu, Reviewer FWrb, Reviewer La9P, Reviewer ZTXg) expressed some concerns regarding the assumptions underlying this paper.** Suggesting inclusion of motivating examples and realistic experiments to enhance community-wide benefits from your insights.
paper_summary: paper_summary: This paper addresses concave utility RL in a non-stationary episodic setting, where the transition probabilities as well as the utility function may change from one episode to the other. The paper proposes an algorithm, dubbed MetaCURL, which dynamically select the best performing "expert" within a set of baseline algorithms with different starting points and hyper-parameters. The paper analyses the dynamic regret of MetaCURL as a function of some characteristics of the instance, such as the number of abrupt changes and the magnitude of changes, under a deterministic dynamics plus action-independent noise assumption.
strength_weakness: strength_weakness: - Motivation of the setting (1). The paper does not do much to support why studying non-stationarity in CURL is useful/interesting;
- Motivation of the setting (2). The paper only evaluates the performance of the expected realization rather than the expected performance;
- Restrictive assumptions. The setting presents several challenges but does not require exploration due to an assumption that makes the stochasticity of the transitions independent from the actions;
- Analysis. It is unclear whether the analysis brings some interesting techniques beyond what has been done in prior works.

This paper tackles a setting comprising an eye-popping list of challenges, which include: non-stationarity of transitions, adversarial learning, concave cost functions. However, aside from restrictive assumptions that makes strategic exploration unnecessary, I believe the paper somewhat fails in two aspects: First, to motivate the setting properly, not just as a "patchwork" of other settings considered in the literature but as a problem raising from important application; Second, to highlight what is the value of their results in terms of insights and employed techniques.
To these reasons, I am currently providing a slightly negative evaluation. I would like to hear from the authors on these concerns. More details below.
questions: questions: MOTIVATION: NON-STATIONARY CURL.

Both CURL and non-stationary MDPs are interesting and worth studying, but why the combination of CURL and non-stationarity is interesting? Does the combination brings more challenges than just the sum of its components? Does the algorithm bring novel ideas? Does the analysis bring novel techniques or valuable insights? I feel that the paper shall do more to support why the reported results matter.

MOTIVATION: OCCUPANCY VS SINGLE-TRIAL.

As it is typical in the original formulation, the paper defines the CURL objective as a concave function of the occupancy measure, i.e., the expected state visitations. More recently (see Mutti et al., Challenging common assumptions in convex reinforcement learning, 2022), it has been shown that there is a crucial difference between optimizing the concave objective over the expected visitation and the expected concave objective. Can the authors comment on why the occupancy formulation is relevant in this setting?

MOTIVATION: NO EXPLORATION.

Studying the regret in a setting in which strategic exploration is unnecessary looks a bit odd. Also, the provided motivation is that applying optimism would induce computational issues, which I do not find fully convincing. There exist tractable no-regret algorithms in RL and it shall be shown why it is not the case for CURL. Moreover, plenty of works in RL studies the regret by relying on planning oracles that are intractable to implement. This is a common choice to isolate statistical complexity from computational considerations. I think that considering $g_n$ unknown but belonging to a known function class would make for a significantly more interesting analysis.

NOVELTY OF THE ANALYSIS.

Can the authors highlight what is novel in the analysis? From reading the paper, the main effort seems to reduce the analysis to a combination of EWA and a known rate for the baseline algorithm.

ADDITIONAL REFERENCES.

While the work does a good job of placing the contribution with respect to previous literature in non-stationary RL, there are some missing works that seem relevant. As mentioned above, the papers *(Mutti et al., Challenging common assumptions in convex reinforcement learning, 2022; Mutti et al., Convex reinforcement learning in finite-trials, 2023)* study a so-called "single-trial" variation of the CURL formulation. The works *(Cheung, Regret minimization for reinforcement learning with vectorial feedback and complex objectives, 2019; Cheung, Exploration-exploitation trade-off in reinforcement learning on online markov decision processes with global concave rewards, 2019)* analyse regret-minimization in a problem formulation akin to an infinite-horizon form of CURL. The papers *(Prajapat et al., Submodular reinforcement learning, 2023; De Santi et al., Global reinforcement learning, 2024)* look also closely related.

OTHER COMMENTS.
- Examples of applications: the paper makes an effort of describing a few applications that fulfil the dynamics assumption, not why they are  relevant for CURL.
- Does the analysis need $F_t$ to be fully revealed instead of bandit feedback? If that is the case, can the authors comment on how this assumption may be overcome?
- The considered policies seem to depend only on the current state of the environment (aka Markovian). Can the author discuss why history-based policies are unnecessary in this setting?
limitations: limitations: The paper is mostly upfront in mentioning the limitations introduced by restrictive assumptions.

Comments: title: Recommendation for Rejection: Suggesting Inclusion of Motivating Examples and Realistic Experiments to Enhance Community-Wide Benefits from Your Insights
comment: Thanks for the response. I decide to maintain my score.
Thank you for your response, we are glad to have addressed most of the reviewer concerns. We hope to address  Q2 below, based on reference [1].

In [1], non-stationarity is represented by a probabilistic model. Indeed, the Markov decision process (including both the rewards and the probability transition kernels) is indexed by some latent variable $z$ that evolves according to a hidden Markov model. Our paper does not assume any model for how the non-stationarity arises, making it a robust approach. 

From the perspective of losses, our algorithm is robust to adversarial losses—losses that can change arbitrarily and are unknown to the learner—affecting our regret bound through  $\Delta^{\pi^*}$. 

From the perspective of the probability transition kernel, we do not make any model assumptions about the distribution of the non-stationarity factors, $h_n^t$. The only assumption is that $g_n$ from Equation (8) is known. However, we believe our approach could be extended to the case where $g_n$ belongs to a known family of parametric functions with parameters that are unknown and vary across episodes, also without assuming any specific model for the distribution of these parameter changes.
We would like to thank the reviewer for their prompt response and for recognizing the motivations and novelties in our theoretical analysis. We also appreciate the reviewer's insightful comments and suggestions, and we will incorporate the recommended changes into our paper. Below, we address the reviewer's additional comments.

> The reported application are interesting, but I want to stress that they sometimes fail to answer the question. For instance, you are explaining why the finance domain may be non-stationary (clear), but not why the utility shall be concave (e.g., through risk aversion);

We agree that the objective function was not explicitly stated in some cases. In the inventory management domain, for instance, a multi-objective function can be needed, while in finance, the objective might involve minimizing a convex risk measure (e.g., Conditional Value-at-Risk) while maximizing returns. To clarify our motivation, we will carefully explain in the paper how each example provided fully aligns with our framework.

> “No efficient method that fully explores in CURL exists". What about intractable methods that are statistically efficient? Previous work show that CURL can be solved through a sequence of RL problems, so it is not clear what makes CURL inefficient. Is it the instantiation of the RL problem (aka computing the reward function)?

We acknowledge that statistically efficient methods for online CURL with adversarial losses exist, such as occupancy-measure approaches using Mirror Descent combined with UCRL2 techniques. However, these methods are not computationally efficient, either for RL or CURL, as they require solving an optimization problem over the set of all plausible MDPs within a confidence interval at each iteration. On the other hand, policy optimization algorithms, which are both statistically and computationally efficient for RL, rely on value-based techniques that cannot be applied to CURL due to the invalidation of the classical Bellman equations.

The work that demonstrated that CURL can be solved through a sequence of RL problems [Zahavy et al. (2021)], considers a different setting than ours. They consider the CURL problem in Equation (1) with a fixed convex objective function and unknown dynamics. We focus on the online version with adversarial objective functions, i.e. that change with each episode and are unknown to the learner. As a result, their reduction does not apply to our case.

### References
- *Zahavy et al. 2021, Reward is Enough for Convex MDPs, NeurIPS*
Thank you for your quick response and for recognizing the new contributions of our paper. Yes, that is precisely what "loop-free" signifies in this context. We are pleased to have addressed all of the reviewer's questions, and we appreciate you taking the time to review our work.
Still, from my perspective, a theoretical paper should only be accepted at NeurIPS if it clearly demonstrates its motivation, and its assumptions are valid in practice (as mentioned by Reviewer unHu, Reviewer FWrb, Reviewer La9P, Reviewer ZTXg); and the whole RL community can benefit from its insights.

As the authors mention Robotics and Finance in their global response, here are some open repositories I recommend they test:

[1] https://github.com/openai/gym

[2] https://github.com/google-deepmind/dm_control

[3] https://github.com/AI4Finance-Foundation/FinRL

For example, many existing control and robotics problems involve infinite horizons and continuous actions and states. How can we assume a large number of experts are possible? How can your assumptions make sense in such scenarios? Additionally, in finance, many high-frequency trading problems occur within milliseconds, making it impractical for all your assumptions to be true.

> Moreover, although the reviewer may not fully appreciate it, the CURL framework is significantly more challenging than the classical RL framework, where the loss is linear.

I agree CURL is more challenging. As such, it is more important to clearly on experiments show the proposed method is able to outperform the existing methods.

> This scenario is not possible because the core principle of our meta-algorithm (Alg. 1) is specifically to design $K=T$ experts. Therefore, we can have as many experts as necessary (the number is controlled by the meta-algorithm).

Why is such a scenario considered impossible in your settings? In practice, it's common to encounter extremely long horizons or a high number of episodes, yet with a limited number of experts. Still, your settings appear overly restrictive.

> Including a notation table is a good suggestion that can easily be added to the paper and should not be a reason for rejection.

Actually, I need to ensure your theory is correct. While reading, I still find lots of notations should be better and properly defined. Without clear notation, it is extremely difficult for me to evaluate it. Therefore, I still have some concerns regarding your theoretical contributions.

> The dynamic assumption may appear strong, but it is valid in practical situations. For instance, [34] provides a real-world motivating application that aligns perfectly with our assumption and framework, addressing a significant problem in the context of climate change. We also believe that our algorithm could be extended in a future work to deal with continuous spaces using function approximation approaches. We point out that this extension has nothing to do with the dynamic’s assumption.

I strongly recommend that the authors directly test their framework on such benchmarks, instead of merely discussing it.
This claim remains questionable.
I thank the authors for their replies. I went over them and do not have any further questions. Please include the changes as promised in your revised version, particularly regarding the dynamics assumption and improving readability.
Thank you for your detailed response. My concerns have been mostly addressed. As to the Q2, one reference could be [1] where the non-stationary factors could come from different sources in MDPs. 

[1] Xie, Annie, James Harrison, and Chelsea Finn. "Deep reinforcement learning amidst continual structured non-stationarity." International Conference on Machine Learning. PMLR, 2021.
Thank you for the update.

- **Novelty:** I apologize for the earlier confusion. I now understand what the authors mean. The algorithm does not require any prior information about the environment, and the performance bound is indeed dependent on the environmental changes. This point has been fully addressed.

- **Loop-free:** Thank you for the explanation. This question is now fully addressed. It seems that "loop-free" refers to resetting the agent and starting from the initial stage multiple times. (Please correct me if I am mistaken.)

I also appreciate how the author have written its. contribution in a explicit way and actively engaging in the  discussions. **I have raised my score to 7.** Please revise the paper based on our discussions if the paper get accepted. I will also consider the feedback from other reviewers. Good luck with your paper. Thank you.
We address below the reviewer comments:

> Empirical validation: While it is acceptable for a NeurIPS paper to focus on theoretical contributions without extensive experiments, I share similar concerns with Reviewer 55Y9. It would significantly strengthen the paper if the proposed framework were tested on some empirical baselines. This would not only validate the theoretical claims but also demonstrate their practical relevance.

**Answer:** We respectfully disagree with the reviewer's perspective and believe that the absence of empirical evaluations in a theoretical paper should not be a reason for rejection. Our paper contributes significantly to the theoretical understanding of non-stationary CURL, an area with no prior research. It's important to highlight that many foundational papers on non-stationary RL were published without experiments [38, 25, 15, 40, 27, 12, 11, 36, 16, 44]. We regret that the reviewer may not fully recognize the value of our contributions. 


> Furthermore, as Reviewer ZTXg pointed out, the dynamic hypothesis presented in L128 seems to be a strong assumption. This assumption necessitates empirical evidence to show that it holds in practicem e.g., in infinite horizon or continuous spaces. Although the authors mentioned some real-world applications in their rebuttal, I remain unconvinced. It is particularly important to clarify how your assumptions (e.g., $K=T$, assumptions about experts, etc. ) align with real-world scenarios, such as those in energy grid optimization, robotics, or finance.

**Answer:** The dynamic assumption may appear strong, but it is valid in practical situations. For instance, [34] provides a real-world motivating application that aligns perfectly with our assumption and framework, addressing a significant problem in the context of climate change. We also believe that our algorithm could be extended in a future work to deal with continuous spaces using function approximation approaches. We point out that this extension has nothing to do with the dynamic’s assumption.

Moreover, although the reviewer may not fully appreciate it, the CURL framework is significantly more challenging than the classical RL framework, where the loss is linear. Managing convex loss functions under partial feedback is considerably more complex than dealing with linear ones (*e.g.*, no efficient optimal algorithm exists for convex bandits while the problem is mostly solved for multi-armed bandits), and it necessitates certain assumptions. No existing work on CURL offers theoretical regret guarantees without this dynamic assumption.

The reviewer's concerns about assumptions, such as $K = T$ and expert assumptions, indicate a misunderstanding of how prediction with expert advice algorithms are used as meta-procedures. These are not assumptions but rather the design of meta-algorithms. Meta-algorithms are extensively used in the online learning literature to develop adaptive algorithms, as demonstrated in works such as [13, 22, 24], among others, or

- *Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization. Peng Zhao, Yu-Jie Zhang, Lijun Zhang, Zhi-Hua Zhou, 2024*
- *Metagrad: Multiple learning rates in online learning. T Van Erven, WM Koolen - Advances in Neural Information Processing Systems, 2016*
- *Locally-Adaptive Nonparametric Online Learning. Ilja Kuzborskij, Nicolò Cesa-Bianchi, 2020*


> Furthermore, as an average reader of RL literature, I still found the notations in the paper challenging to follow. Including a notation table and additional clarifications would greatly enhance the readability and accessibility of your work. I still find some of the assumptions in the paper to be unconvincing. The motivation behind these assumptions is not entirely clear, especially in the absence of a motivating example. It is a little difficult to see how the broader RL community could readily apply or benefit from the theoretical insights offered in this paper.

**Answer:** Including a notation table is a good suggestion that can easily be added in the paper and it should not be a reason for rejection. While our notations may seem complex, they are necessary due to the episodic online CURL framework, which involves multiple indices ($t$ for episodes, $n$ for time steps, $x$ for states, $a$ for actions, etc.). We are open to any constructive suggestions from the reviewer to improve our notations.
Dear authors,

Thank you for your thoughtful replies to my comments and the general response above.
I think you are making a compelling enough case for the paper showing why the analysis is interesting and providing some application where the need for models that are non-stationary and concave-utility simultaneously may be reasonable. I am increasing my score towards acceptance. I still believe that sidestepping the exploration problem is not fully motivated and that potential application shall be explored in more details.

Some additional comments:
- The reported application are interesting, but I want to stress that they sometimes fail to answer the question. For instance, you are explaining why the finance domain may be non-stationary (clear), but not why the utility shall be concave (e.g., through risk aversion);
- "No efficient method that fully explores in CURL exists". What about intractable methods that are statistically efficient? Previous work show that CURL can be solved through a sequence of RL problems, so it is not clear what makes CURL inefficient. Is it the instantiation of the RL problem (aka computing the reward function)?
**Empirical validation**: While it is acceptable for a NeurIPS paper to focus on theoretical contributions without extensive experiments, I share similar concerns with Reviewer 55Y9. It would significantly strengthen the paper if the proposed framework were tested on some empirical baselines. This would not only validate the theoretical claims but also demonstrate their practical relevance.

Furthermore, as Reviewer ZTXg pointed out, the dynamic hypothesis presented in L128 seems to be a strong assumption. This assumption necessitates empirical evidence to show that it holds in practicem e.g., in infinite horizon or continuous spaces. Although the authors mentioned some real-world applications in their rebuttal, I remain unconvinced. It is particularly important to clarify how your assumptions (e.g., $K=T$, assumptions about experts, etc. ) align with real-world scenarios, such as those in energy grid optimization, robotics, or finance.

Furthermore, as an average reader of RL literature, I still found the notations in the paper challenging to follow. Including a notation table and additional clarifications would greatly enhance the readability and accessibility of your work. I still find some of the assumptions in the paper to be unconvincing. The motivation behind these assumptions is not entirely clear, especially in the absence of a motivating example. It is a little difficult to see how the broader RL community could readily apply or benefit from the theoretical insights offered in this paper.

Given these concerns, I am unable to raise my score at this time and will maintain my rating of 4.
Thank you for your prompt response. We are pleased that we have addressed most of your questions. The remaining issue appears to stem from a misunderstanding, which we hope to clarify below. We hope that the reviewer will consider this in their final assessment.

> **Question about novelty:** The reviewer acknowledges that the upper bound should be dependent on the environment's changes. [...] However, the statement "Our algorithm runs without needing knowledge of the environment changes as input" seems to imply a rather strong assumption. Does this mean that the algorithm requires exact information about the environment changes, or is it based on estimated information?

**Answer:** There is still a misunderstanding. Our algorithm **does not** require prior-knowledge of the environment changes contrary to most existing works. The fact that it appears in the performance bounds is a strength, not a weakness of our result, and does not mean at all that the algorithm needs it to satisfy the bound. 

As the reviewer acknowledges, it is highly challenging to know the environment's changes with precision in a time-varying setting. Achieving our results without needing this knowledge was thus non-trivial and most existing algorithms loose their practicality contrary to us. This is one of our core contributions. 

Thanks again for pointing us to these related works. We will include them in our citations.

> **Loop free terminology:** Could the authors please be more specific about the term "loop-free"?

**Answer:** The loop-free problem refers to a specific case of episodic MDPs, where an agent must transverse episodes of a fixed length (denoted by $N$ in our case), always starting from the same state or from a state-action pair sampled from the same distribution (denoted by $\mu_0$ in our case), with transition probabilities dependent on the agent's time step $n \in [N]$. We will include these details in the main paper.
We continue below to address each point of the reviewer.

> Providing numerical examples or visual figures that illustrate real-world applications would greatly strengthen your paper. […] in your newly added reference, [Perrin et. al, 2020] have some experiments, and figures clearly showing their results.

**Answer:** We emphasize that this is a paper on theoretical reinforcement learning and online learning. The work by Perrin et al. (2020) addresses an offline scenario in mean field reinforcement learning with fully known dynamics (both $g_n$ and $h_n$ are known) and assumes stationary dynamics and losses, making it relatively straightforward to design experiments for such a setting.

In contrast, our framework is considerably more complex, involving adversarial losses and changing dynamics. Conducting experiments for adversarial and non-stationary MDPs is particularly challenging due to the difficulty of constructing optimal policies across episodes. The existing literature largely lacks experimental validation for such scenarios. Most of the influential papers addressing non-stationarity in reinforcement learning that we cite do not include experiments, such as [38, 25, 15, 40, 27, 12, 11, 36, 16, 44], among others.

> As such, how your algorithm will perform, when their dimensions are increasing?

**Answer:** As previously mentioned, this dependency in each term of the regret is explicitly outlined in Propositions 5.2, 5.3, 5.4 and Appendix F. The final dependency in Theorem 5.1 is influenced by the choice of the black-box algorithm. For the Greedy MD-CURL algorithm we propose, the dependency on the constants is the same as in [38]: $N^2 \mathcal{X} \sqrt{\mathcal{A}}$, multiplied by the dependency on $T$ and the variation budgets as has been outlined in Appendix G.
Thank you for your quick response. We believe there might unfortunately be some misunderstandings. Below, we offer our point-by-point responses to address and clarify these concerns.

> This raises a key question. What if $K \neq T$? 

**Answer:** This scenario is not possible because the core principle of our meta-algorithm (Alg. 1) is specifically to design $K=T$ experts. This approach is a well-established technique in several dynamic online learning studies (see [13, 22, 24] cited in the paper). Additionally, as stated in lines 225-226, an expert is simply an instance of the black-box algorithm launched by the meta-algorithm. Therefore, we can have as many experts as necessary (the number is controlled by the meta-algorithm). 

> […] are all your experts considered optimal? If some experts are not optimal (e.g., expert $k_1$ has a performance of 1, while expert $k_2$ has a performance of 0.9), how does your algorithm accommodate such variability?

**Answer:**  We don't quite understand your point. Naturally, not all experts are optimal. The purpose of the meta-algorithm is to perform as well as the best expert, which aligns with the standard regret objective in Learning with Expert Advice. Regardless of the experts' performance, our theoretical guarantee in Thm. 5.1 remains valid.

>  If the experts propose different actions under similar circumstances ($s_1$, expert 1 takes $a_1$ but expert 2 takes $-a_1$), how does your algorithm resolve these conflicts?

**Answer:** Experts proposing different actions under similar circumstances is not a problem. As is standard in the literature on learning with expert advice (see *Prediction, Learning, and Games* by Cesa-Bianchi and Lugosi, 2006), the experts' advice—represented as different state-action distributions—are combined in line 7 of Alg. 1. The resulting combined state-action distribution is then used to select the action to be taken.


> "this problem can be reduced to the sleeping expert problem." Could you provide further explanation on this point? Specifically: In L218, The authors mention that "experts are not required to provide solutions at every time step". What if, at a certain step, no experts provide solutions? Is there a minimum number of experts that must be "awake" or active for the algorithm to function effectively?

**Answer:** This will never be the case. An expert is simply an instance of the black-box algorithm. By design, we initialize one black-box algorithm at the beginning of each episode, which continues to provide outputs throughout all episodes until $T$. Thus, in every episode, there is always an expert providing solutions. The expert corresponding to the black-box instance initialized in episode $t$ is not active in any earlier episode $t’ < t$. However, all experts initialized in episodes $s < t’$  are active at episode $t$.

	
> $g_n$ known. Is this assumption necessary? What if $g_n$ is not known? How could we validate it in real-world scenarios?

**Answer:** Yes, this assumption is necessary in our framework. We explain the importance of addressing CURL and this assumption in our general response to all reviewers. If $g_n$ is unknown but belongs to a known family of parametric functions, we could extend our analysis. However, if $g_n$ is entirely unknown, it would be more challenging and would require further work, as already mentioned in the Conclusion (line 319) of our paper. We've already provided several examples of real-world scenarios where the dynamics can be modeled under the assumption of $g_n$ being known, with an unknown and non-stationary external noise distribution $h_n^t$ (see lines 142-154 in the paper and our general response).

> This supports my initial observation that your current notation is not very consistent. As such, I strongly recommend including a notation table in the paper to clearly define and distinguish all critical symbols and terms. This would greatly aid in understanding and improve the readability of your work.

**Answer:** The notation is not inconsistent. The function N can easily be distinguished from index N both by its signature and the presence of indices. We find the statement that: "since we accept to modify this notation, it supports the claim of inconsistency of all our notations" to be unjustified. The purpose of the review process is to improve the paper, and using our willingness to make changes to satisfy the reviewer as an argument against the paper is non-constructive and unfair. Nonetheless, we can easily implement this modification in the final version, which we see as a minor issue, and believe it should not be used as a reason to reject the paper. We will include a notation table in the final version.
Thank you for the update.

The reviewer still has a few questions and requires some clarification.

- **Novelty**: The reviewer acknowledges that the upper bound should be dependent on the environment's changes. However, the statement "Our algorithm runs without needing knowledge of the environment changes as input" seems to imply a rather strong assumption. Does this mean that the algorithm requires *exact* information about the environment changes, or is it based on *estimated* information? If it requires exact information, the algorithm might lose its practicality, as it is generally impossible to know the environment's changes with precision in a time-varying setting. If this is the case, could the authors propose an upper bound that accounts for estimation error? I also recommend referring to recent non-stationary reinforcement learning papers [1,2] that incorporate estimation errors in both model-free and model-based approaches.

  [1] Lee, H., Ding, Y., Lee, J., Jin, M., Lavaei, J., & Sojoudi, S. (2024). Tempo adaptation in non-stationary reinforcement learning. Advances in Neural Information Processing Systems, 36. – This work includes estimation error in a model-based approach.

  [2] Lee, H., Jin, M., Lavaei, J., & Sojoudi, S. (2024). Pausing Policy Learning in Non-stationary Reinforcement Learning. In Forty-first International Conference on Machine Learning. – This work incorporates estimation error in a model-free manner.

- **Dynamic Regret Representation**: While the author's response wasn't perfectly aligned with the reviewer's initial query, the clarification provided has fully addressed the concern. The reviewer is now persuaded by the approach of taking $ \min_{\pi^*} \Delta^{\pi^*} $ for the constant upper bound. Thank you.

- **Dynamic Hypothesis**: The reviewer still finds the dynamic hypothesis to be a somewhat strong assumption, even though the system includes noise. This is because noise is an inevitable consideration in any system design. However, based on the prior works referenced, this issue is considered fully addressed. Thank you.

- **Terminology**: Thank you for the clarification. Could the authors please be more specific about the term "loop-free"? What exactly does "loop" refer to, and why is the proposed algorithm described as "loop-free"?

- **Related Work**: Thank you for the consideration. Please include these references if the paper is accepted.
Thank you for your detailed response. While I appreciate the clarifications provided, I remain concerned about certain aspects of your problem settings and their practical applications.

I strongly recommend the authors to add the clarifications above to their paper.

> we introduce the general setting of learning with expert advice, involving $K$ experts and $T$ episodes. In our algorithm, the number of experts equals the number of episodes, i.e., $K = T$. At each episode $s$ we activate an expert that remains active until the finite horizon $T$.

This raises a key question. What if  $K \neq T$? Additionally, regarding my earlier inquiries about Learning with Expert Advice (LEA), are all your experts considered optimal? If some experts are not optimal (e.g., expert $k_1$ has a performance of 1, while expert $k_2$ has a performance of 0.9), how does your algorithm accommodate such variability? 

Furthermore, let me add more details to my previous questions. If the experts propose different actions under similar circumstances ($s_1$, expert 1 takes $a_1$ but expert 2 takes $-a_1$), how does your algorithm resolve these conflicts? Addressing these scenarios would significantly enhance the robustness and applicability of your approach.

The authors mention that "this problem can be reduced to the sleeping expert problem." Could you provide further explanation on this point? Specifically: In L218,  The authors mention that "experts are not required to provide solutions at every time step". What if, at a certain step, no experts provide solutions? Is there a minimum number of experts that must be "awake" or active for the algorithm to function effectively?

Could you clarify what do you mean by "that remains active until the finite horizon $T$"?

> $g_n$ is assumed to be known.

Is this assumption necessary? What if $g_n$ is not known? How could we validate it in real-world scenarios?

> The notation $N(X')$ represents the number of times an agent transitions from the state-action pair. The notation $N$ indicates the length of an episode. To avoid confusion, we will change the letter for one of these notations.

I appreciate your willingness to revise the notation to reduce confusion. This supports my initial observation that your current notation is not very consistent. As such, I strongly recommend including a notation table in the paper to clearly define and distinguish all critical symbols and terms. This would greatly aid in understanding and improve the readability of your work.

> We recognize that experiments are valuable for assessing an algorithm's practical performance, but our paper focuses on developing an algorithm that theoretically achieves the optimal regret bound within a specific framework.

Providing numerical examples or visual figures that illustrate real-world applications would greatly strengthen your paper. Such examples would address concerns raised by other reviewers, including Reviewer unHu, regarding the practicality and applicability of your algorithm. Empirical evidence, even in simplified scenarios, would offer a more comprehensive evaluation of your proposed method. E.g., could you provide an intuitive numerical example based on your global rebuttal (energy grid optimization, or robotics or finance)?

Additionally, in your newly added reference, [Perrin et. al, 2020] have some experiments, and figures clearly showing their results.

> Our regret bound also depends on the state space, the action space, and the episode length. 

As such, how your algorithm will perform, when their dimensions are increasing?