MetaCURL: Non-stationary Concave Utility Reinforcement Learning
Authors: Bianca Marin Moreno
Margaux Brégère
Pierre Gaillard
Nadia Oudjane
Venue: NeurIPS 2024 poster (2024)
Keywords: Concave utility reinforcement learning
non-stationary MDPs
learning with expert advice
online learning
Primary area: online_learning

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.

MetaCURL: Non-stationary Concave Utility
Reinforcement Learning
Bianca Marin Moreno
Margaux Brégère Sorbonne Université! EDF R&D
Pierre Gaillard Inria"
Nadia Oudjane EDF R&D!
Inria"
EDF R&D!
Abstract
We explore online learning in episodic Markov decision processes on non-stationary environments (changing losses and probability transitions). Our focus is on the Con- cave 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 intro- duces MetaCURI, the first CURL algorithm for ota-itaaionary MDPs. 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 probability transitions (uncertainty and non-stationarity coming only from external noise, independent of agent state-action pairs), the algorithm achieves optimal dynamic regret without prior knowledge of MDP changes. Unlike approaches for RL, MetaCURL handles adversarial losses. We believe approach for managing non-stationarity with experts can be of interest to the RL community.
the
1 Introduction
We consider the task learning in an episodic Markov decision process (MDP) with a finite state space X, finite action space A, episodes of length N, and probability transition kernel p = (Pr)xE[N) such that for all (I, a) E X' x A, (-(-, a) E Sx. For any finite set B, we denote by Sg the simplex induced by this set, and by [B] its cardinality. For all E we let [d] == {l..... d}. action a, (-(x,, by means of policy, and moves to the next state 2n+1 ~ pn-1(-1a,, an). inducing a state-action distribution sequence nT = (ATTP) (mEN)) where n E SxxA for all [N].
At each time step n, agent in state Fn chooses
In many applications learning episodic MDPs, an agent aims at finding an optimal policy æ maximizing/minimizigg concave/convex function F of its action distribution, known as the Concave Utility Reinforcement Learning (CURL) problem:
min (S
F(
(I)
CURL extends reinforcement learning (RL) from linear to convex losses. Many machine learning problems be written in the CURL setting, including: RL, where for loss function E, F(
(t, x.T:) pure RL exploration [28), where F(F=-P) (NTTPP log(u=>))); imitation learning 26 35
and apprenticeship learning [I. where F( (,( μ²) with D, representing Bregman
38th Conference on Neural Information Processing Systems (NeurIPS 2024).
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, IJK, 38000 Grenoble, France. EDD Lab, bd Gaspard Monge, 91120 Palaiseau, France "Srroonne Université LPSM, Paris, France

---

divergence induced by function g and μ= being a behavior to be imitated; certain instances of mean- field control 771. where F)u=-P)= (L(+=*")) ));;;;;; mean-field games with potential rewards [34;; among others. The CURL problem alters the additive structure inherent in standard RI., 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
where both the objective function I' and the probability transition kernel p remain the same across episodes, However, in practical scenarios, environments are rarely stationary. The work of [39] 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 an optimal policy). In son-stationary scenarios, it is more relevant to minimize dynamic regret- 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
With MetaCURL, we extend this concept to decision 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 known deterministic structure but is affected by an external noise with unknown distribution, placing us in setting with only partial information (see Section P for more details). The learner is then unable to observe the agent's loss under policies other than the one played.
[29 159
47 33
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 Ö(VA-TT + min { T. (A) (A)))/3)) where A and A represent the frequency and magnitude of changes of the probability transition kernel respectively, and A= 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- algorithm. This is the first dynamic regret analysis for a CURL approach.
Comparisons. Without literature on non-stationary CURL, we review ota-stationary RL approaches. Most methods (24 13, 45 17 20 40 21 typically rely on prior knowledge of the MDP's non- stationarity degree, while MetaCURE CURL does not. Let A and A' represent the frequency and magnitude of change in the RL loss function, respectively[] Recently, [54] achieved a regret of Ó( min { (VAA% + YT, (A/ + A1)1/83), a near-optimal result as demonstrated by [40], without requiring prior knowledge of the environment's 's variation. However, this regret bound is tied to changes in loss functions, making it ineffective against adversarial losses. contrast, rather than
Table 1: Comparisons of our results with the state-of-the-art in non-stationary RL. Here, AP AP and A are defined in (6) and ( and A and A' measure the RL loss function v We M
introduce (r A) min ( T, 72/3 23/3/1/1 A//33.
Algorithm
Dynamic Regret in Ô
CURL
Ady. losses
No prior knowledge
Explo- ration
MetaCURL (ours)
T Dr(Ak AP)
/
x /
SoTA in RL [54]
Dr(Ak + A A + A')
/
X
' := + ET- al and A'e == 1+ ΣT' 1( * Al+1), where At: := EN max., (2, a) ++ (z, a) and E. (2, a) the expected loss suffered by choosing action in state at step of round
2

---

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 more favorable bias-variance trade-off, which may not align with the optimal policies for each loss. addition, we improve this dependency by paying it as V instead (A*") 11/33//222// We summarize comparisons in Table
43 examine the difference between optimizing the objective over infinite trials and the expectation of the objective over single trial, challenging the traditional CURL formulation in Eq. (T). Here, we retain the classic formulation to align with existing CURL research. Other works on RL with nonlinear objective functions are [46] [6] focusing on rewards over trajectories rather than individual states. In addition to non-stationarity, there is series of works on RL with adversarial losses but stationary probability transitions, with results only on static regret [8 30 18 50 32 14). Another line of research is known as corruption RL. differs from non-stationary MDPs in that it assumes ground-truth MDP and measures adversary
Other related works. The studies by
malice by the degree of ground-truft trrtt corruption 31 38 TO
53
Contributions. We resume our main contributions below:
We introduce MetaCURL, the first algorithm for non-stationary CURL. Under the frame- work described in Section 2 MetaCURI. achieves the optimal dynamic regret bound of order O(VA*" min & T, (AP)1/3)))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 || ||a be the L1 norm, and for all (eN) such that on e R.x. we define || sUPigngN ||e,]]i.
2 General framework: non-stationary CURL
When an agent plays a policy π == (Na)nEIN) in an episodic MDP with probability transition p. it induces state-action distribution sequence (also called the occupancy- meesure (61), which we denote by fT := (HT.))eIIN) with μ.t E SxxA- can be calculated recursively for all (x, a) X and n [N] taking 16 J.8 (xx a) = uo(a, a) fixed, and
P (I,
Σ (xt,a")EXXA
( aaaaa'))paa (a)pal lalll"aa""mm (')Tn(((aa))
Offline CURL. The classic CURL optimizatin problem in Eq. ① considers minimizing a function F: (Sxx)) + R. here defined as F(w) := -' (un) with fn a convex function over na, with values in [0, 1]. across all policies that induce μ -M= Note that F is not convex 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
MP = {M1 No -{M
Palz' (xr a))an- (x) Val E E. E IN]
Σ pn(z',d')= n'EA
Σ ZEX,NEA
(3)
For any / E MM there exists strategy such that n.= = μ.. It suffices to take n, (alar) (2, a) when the normalization factor is non-zero, and arbitrarily defined otherwise. There thus an equivalence between the CURL problem (optimization problem on state-action distributions satisfying the Bellman flow:
policies) and convex optimization
min *E(SA)AXX
P( min F(u).
(4)
WEME
Online CURL. In this paper we consider the online CURL problem in a non-stationary setting. We assume finite-horizon scenario with T episodes. An oblivious adversary generates a sequence of changing objective functions (F²) [e[z]. with Fr being fully communicated to the learner only at the (F))
end of episode t. We assume F* is L Lipsschii with respect the || Ilso.1 norm for all t. The
3

---

probability transition kernel is also allowed to evolve over time and is denoted by p' at episode t. The leamner' objective is then to calculate a sequence of strategies (TT)) minimizing a total loss LT == Ei=1 (" "er''') while dealing with adversarial objective functions Ft and changing probability transition kernels p'. 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 (etfr))
Rir ((TTT""))) == Enemy F F'(n"' 20) - F F""""
(5)
Non-stationarity measures. We consider the following two non-stationary measures A and A" on the probability transition kernels that respectively measure abrupt and smooth variations:
T-1
T-1 Σ AP
D = 1+ Σ 1 11
:
:ax II (+),,) -p (+2,,)) (6) n.z.a
Regarding dynamic regret, we define for any sequence of policies (I*** )eE())) its noa-stationarity measure as
A EA
AT AT
(-,x) m (-(x01--
max nE(N],zEX
1=1
Morcover, for any interval / S [T], write =7 EtEr DE and AT == AF
Dynamic's hypothesis. For each episode I, let (2/z ab) ~ no(+), and for all time steps n E [N]
x = 9n(2nn a; Cn):
88)
where In. represents the deterministic part of the dynamics, and (eE) is sequence of independent external noises such that <, ~ (-), where h4 is any centered distribution. Note that these dynamics imply that the probability transition kernel can be written as pl++ (a' [ar a) IP (gg (1r, a, + = z'). 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 gn is fixed and known by the learner, but h, 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 model assumptions. In using RL methods to CURL, we believe model-optimistie approaches like UCRL (Upper Confidence RL [) 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 RI. methods policy optimization (PO), which directly optimizes the policy and often yields closed-for form solutions, leading to faster performance. Recent thcoretical work (37) has shown that PO methods can achieve near-optimal regret without model assumptions. However, these methods rely 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 In. is unknown but belongs parametric family. We leave this extension for future work.
This particular dynamic is also motivated by many real-world applications:
Controlling fleet of drones in known environment, subject external influences due 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 consump- tion 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, houschold consumption habits remain unpredictable and constantly changing [5] 41

---

Outline. In this paper, we propose a novel approach to handle non-stationarity in MDPs, being the first to propose a solution CURL within this context. We begin in Section by discussing the idea behind our algorithm's s construction and the key challenges within our framework. Section introduces MetaCURI., while Section presents the main results of our regret analysis. The proofs specifics are provided in the appendix.
3 Main idea
A hypothetical learner who achieves optimal regret. Let m > 1. Assume a hypothetical learner that could compute a sequence of restart times i [m] we let I == [4z 44+1 1), such that
= h <... < (m++1 = T + 1, where for each
S4. S.SD' Sp/mm.
Consider any algorithm that, when computing JeE) with learning rate À for any interval I IS [T]. attains dynamic regret relative to any sequence of policies "re" upper bounded by
Ry ((Tr"))))) S A + ca) + |1|
(10)
where (c))ge'T 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 A to calculate the optimal
learning rate. Hence, playing such an algorithm for all horizon T with the optimal learning rate, the learner would have dynamic regret upper bounded by
Rir ((T" )EEMT S <2/ci + +3m)T++ TAPM"
Optimizing over m, the learner would obtain the optimal regret of order ((VA='+((P))111 In the case where the MDP is piece-wist wise stationary. if the learner takes Ij such that A = 0. obtains regret of order A" T + VAC.)), where A the number of times the probability transitions of the MDP change over (7).
A meta algorithm to learn restart times. In reality, the restart times of Eq. ( and the optimal learning rate, are unknown to the learner. Hence, we propose to build a meta aggregation algorithm to learn both. Let & represent a parametric black-box algorithm with dynamic regret in Eq. (IO). We introduce a meta algorithm M that, takes as input a finite set of learning rates A, and at each episode t, initializes |A| instances of E, denoted er. for each X A. Each E operates independently within the interval [1, T). At time I, . combines the decisions from the active runs {E&A Jast,AeA by weighted average. The idea is that at time f, some of the outputs of {E**) JsAt,AEA are not based on data prior to f' < f, 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, A) be the complete algorithm.
Remark 3.1. The meta-algorithm increases the computational complexity of the parametric black- box algorithm by a factor Tf x [A], as it requires updating x |A] instances at each episode t. By strategically designing intervals run the black-box algorithms, previous works on online learning have reduced computational complexity to ((log(T)) A73 29 277. Extending our analysis to these intervals 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 |A| = log(T) is sufficient to obtain the optimal regret.
Regret decomposition. Denote by ,/,s,> the policy output from g*.A at episode I, for learning rate X for all s S t. and by '² the policy output by the meta algorithm M(E, A) to be played by the learner. The regret of M(E, A) can be decomposed as the sum of the regret suffered by the meta algorithm aggregation scheme, M, and the regret from the black-bor algorithm, E, played with any learning rate À E A. The dynamic regret, defined in Eq. (5), can be decomposed, for any set of intervals 1, and for any learning rate À E A, as
I2 = [1,,4441 1). with 1 = 11 < <... < 1m++1
F' DD) - P'
D²) F'
Meta algorithm regret
Black- bookkbbx regret on Ie
pmmeta [[T]
R[]]
pblacc-box box ((T² )
(11)
5

---

The black-box regret on Ij is exactly the standard regret for T = [Zal with a learning rate of X. 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 Z; find black-box algorithm & for CURL that has dynamic regret as in Eq. (TO), and build a learning rate grid A allowing us to perform nearly well as the optimal learning rate.
4 MetaCURL Algorithm
We call our meta-algorithm M MetaCURL. It based on sleeping experts, is parameter-free, and achieves optimal regret. Its construction is described below.
4.1
Learning with expert advice
General setting, In Learning with Expert Advice (LEA), a learner makes sequential online predictions u² R in decision space U, over a series of episodes, with the help of experts [2 36 91.
For each round t, each expert k makes prediction witk, and the learner combines the experts' predictions by computing a vector o² ;= (v
"u'.,...,, v E Sk. and predicting the convex
combination of experts' prediction u' := Ex= uhtk The environment then reveals convex loss function ft U - IR. Each expert suffers a loss ge.k := ("('k),, and the learner suffers a loss é = (u'). The learner's '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 (eg(r) == Ei=
grh
Sleeping experts. In our case, each black-box algorithm is 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* E {0, 1} define signal equal to if expert k is active at episode and 0 otherwise. The algorithm knows (1**) (I**) and assigns zero weight sleeping experts (T O implies y 0). We would like have guarantee with respect to expert & E [K] but only when it is active. Hence, we now aim to bound a cumulative regret that depends the signal jt,k; Reg
sleep (k) E/= (' (t.)). There is generic reduction
from the sleeping expert framework to the general LEA setting (see Appendix A.1
4.2 Meta-aggregation scheme
In every episode I, for every learning rate À E A and < I, an instance & of the black-box algorithm an expert computing policy nd.e.d, The meta algorithm aims 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², the learner also knew p', they could recursively calculate the corresponding state-action distribution u ,pp using Eq. and observe the actual loss of each expert, denoted as F² ("( "" .p') However, given that pf is unknown to the learner, the true loss remains unobservable. Consequently, the meta- algorithm needs to create an estimator g² for p² and utilize it to estimate the losses. We propose method to compute an estimator ş² in Subsection 4.3
Convexity, As discussed in Section 2 the objective functions F are not convex over the space of polices. However, CURL is equivalent to 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 fe and the recursive scheme Eq. (2). We detail MetaCURL in Alg. _ when employed with the Exponentially Weighted Average forecaster (EWA) as the sleeping expert subroutine (we detail EWA in Appendix A.2)
4.3 Building an estimator of p'
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 j². Standard RL techniques for bounding the L1 norm between the empirical estimator ğ and the true

---

Algorithm MetaCURL with EWA
1: Input: number of episodes T, finite set of learning rates A, black-box algo. &, EWA learning rate 77 log
2: Initialization: Ph (-1z, a) == [ for all [NV] (2,a) x
3: fort 1, ,,..., T do
4: Start |A| new instances of & denoted by g for all E A, assign each of them a new weight gf,4, TATE and normalize weight vectors w/.s, for E [t-1] such that v' == (1( JASAAAA
is a probability vector in R*xA
5: For 8 S I. and À E A, & outputs π (...A
6: Compute recursively 1 == using Eq. 22 for all S t and A
7: Aggregate the state-action distributions: n Σ == ExEr u w lt Deiad
8: Retrieve n' from μ²: for all n, (x, ax,
T (a/x)) = =
palza) Ed'ed unlwaay
1f a) #0
T (n, a) 00
9:
Learner plays x": Agent starts at (x6, ob) po(.)
10:
for 71 = 1, I,...,NN do
Environment draws new state zt, ~ ph (+|x) -1
12:
Learner observes agent's external noise s
13:
Agent chooses an action af, ~ (-(xx/))
14:
end for
15:
Objective function F* is exposed
16:
F* F* (1m 8²) for all S t and X A Compute the new weight vector th for all s S t and A A.
Compute experts' losses gt.s.)
17:
ghind exp (-mprisid)
(EWA update)
E ExEA wh.o' . cxp (-npetoo
18:
Use agent's external noise trajectory (E to compute g as in Subsection 4.3
19: end for
are not applicable here due non-stationarity. To address this, introduce second layer of sleeping experts for each (n, x, a) E [N] x X' x A, where each expert provides an empirical estimate of p' based on different intervals. We then propose
dynamics p' 44 49
loss function in Eq. (12)
and conduct novel regret analysis in Prop. 5.2 to achieve the optimal regret rate.
In each episode the learner calculates independent samples ur nn, (-kr,, a) utilizing the external noise sequence (sM))E(N] observed (just let = 9n-1 a, ch see Eq. (8) Each expert outputs empirical estimator of pt, (-lær, a) using samples across different intervals. We assume T
experts, with expert active in interval [8, 7'. Expert s at episode /. > outputs:
Ned-11 (x')
( (x'(0,)) a)
with Nost pystt-14 R. (x') = Σ 9=
(t (t=s)
We let p (-12z, a) be the result of employing sleeping EWA with experts p- a), for t. Typically, in density estimation with EWA, a logarithmic loss - -lo(()) ) is used. However, this case -log(-) can be unbounded, so opt here for smoothed logarithmic loss, given by, for all q Sx.
(g) = Σ -lo (x(x)=
{ 1 (s) (=....=)) where of thza ~ (ph((12, + ) (12)
ZEX
The definition of this non-standard loss further clarified during the regret analysis in Sec- tion 5 This loss function is 1-exp concave (see Lemma 4 of (22), hence the cumulative regret of EWA with respect to each expert s E [T]. for all episodes т E [s, T). satisfies
Reg Reg (s) Ei= (11((12))) a)) ll (-1,2,, a)) < log(T) (for more information on the regret
deep

---

bounds of EWA with exp-cveavee losses, see Appendix A.2 We describe the complete online scheme to compute øf in Alg. at Appendix
5 Regret analysis
This section presents the main result concerning MetaCURL's regret analysis. Subsection 5.1 shows upper bound for Rmeet when MetaCURL is played with EWA and j³ computed as in Subsection, 4.3 Subsection 5.2 introduces learning rate grid for MetaCURL when the black-box algorithm meets the dynamic regret criteria in Eq. (TPp. providing an upper bound for Pblack 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)
showwws an
Theorem 5.1 (Main result). Let ő E 10, Playing MetaCURI, with parametric black-box
algorithm & with dynamic regret as in Eq. (TO), with learning rate grid A := {2 0, 2, [og2 (T) /2]]] and with EWA the sleeping expert subroutine, we obtuin, with probabil- ity at least 26, for any sequence of policies (n*h²) "EE(T)
Rir ((T))))))) S 2
6 (OVA=TT min (VTAL, (233)1))1)))
5.1
Meta-algorithm analysis
Given the uncertainty in the probability transition, the meta regret term can be decomposed follows:
T
pometta [
Σ
Ft (1c x -F FF A
Rez (IT) (8) estimation)
(13)
Ft
F Aiii 16) - Fi F'
EET,
TET,
sleeping LEA regret
Em Exe, Ry (xfiteed) (P' estimation)
Sleeping LEA regret. Referring Thm. A. in Appendix A using sleeping EWA the sleeping expert subroutine of MetaCURL, with signals _t,
for active experts (s S t), experts' convex
losses gb,a,d == ( n ,¹), and learner loss &t = FC F'"n" m H²) yields, for any m E [7] and for any set of intervals I₁ = [t,, t++1 - 1). with 1 = t1 < ... < fm+11 =
m
Σ Σ
(0) F' F gg
Regz.
sleep
i=1 IET,
i=1
(14)
I
mT
log log(T|A)) S log(T|A)).
2
I' Estimation regret. In scenario without uncertainty in the MDP's probability transitions, the meta-algorithm's 's regret would simply be bounded by Eq. {4), the sleeping expert regret used as subroutine. However, given the presence of uncertainty, the main challenge in analyzing the meta-regret comes from the regret terms associated with the estimator f We outline this analysis in Prop. 5.2
NX ) and LF be the Lipschitz constant of F', with respect to the norm || for all / E [T]. With probability of at least 1 8, MetaCURL obtains
Proposition 5.2. Let E 10, C==
V log
(T') = Σ Ft F' F* F' 2 1/3333
For any m E [T] and for any set of intervals I, = lit1 - 11. with 1 = =4.... the same bound is valid for Σm EIST, Rf, (IThitid))
<...... - bm+1 = = T
8

---

Proof. The proof idea is based mainly on the formulation of p described in Subsection 4.3
We
start by using the convexity of F* linearize the expression, then we apply Holder's inequality and exploit the I.p--.ipschizz property of Ft to establish an upper bound based on the I1 norm difference of the state-action distributions induced by the true probability transition and the estimator, Using we then obtain that
Lemma C.5 in Appendix
C
R ΣΣED
N Σ
R [ LF =1 2,0
J (z. (2. -)
To use the results from Subsection 4.3 we first regularize p' and j¹, for each (n, x. a). by averaging
each with the uniform distribution now lower bounded, we can employ Pinsker's inequality to convert the I1 norm into a KI. divergence. The sum over E [T) of the KL divergence can then be decomposed
X, that we denote by po := 1/ As both probabilities
follows:
(] (((1,,0) 0) + Pu (112, 21,00 a) + Pu
PS x. a)
+ Pa Pj
(-120, 0) + Pu
KL.
KI.
2
2
EEI.
Byg Jiria
[log (0) ( (aa a) + po) log (D) (f), + po)]
1= 1EZ.
where 1.
0/.4 (-|ar, a) the empirical estimate of pp (.1x, a) calculated with the observed data from 4 to t -- 1, and the expectation is over 34 j...a (p) (-11r [r. a) + po)/22. The second term is the cumulative regret of computing ø² 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
L
Prop. 5.2 together with Eq. (1) yields the main result of this subsection:
Proposition 5.3 (Meta regret bound). With the same assumptions as Prop. probability at least 26,
5.2 for any m E [T], with
Rmeeta < 4L 1 3/A 1og(T) 1 + [
mT
log(T|Al).
2
5.2 Black-box algorithm analysis
Assuming is parametric black-box algorithm with dynamic regret satisfying Eq. 10 for any learning rate À > O, only need to address the selection of the As grid and optimize across X to achieve our final bound on Rebluk bbl
Learning rate grid. The dynamic regret of Eq. (T) implies that any two that are a constant factor of each other will guarantee the same upper-bound up essentially the same constant factor. We therefore choose an exponentially spaced grid
A = [2 = 0, 0,1,,.... [log2(T)/2]]
(15)
The algo-ihgo aggregation scheme guarantees that the learner performs well as the best empirical learning rate. We thus obtain a bound on phlack box 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 (7*""))e(r))
((T"))e)()) S 12 +00 + + + cgm)T
TAP
Reblact box
C1
m
Greedy MD-CURL. Greedy MD-CURL, developed by [39, is a computationally efficient policy- optimization 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
the first dynamic regret result for a CURL algorithm. Hence, Greedy MD-CURI. can used as
black-box for MetaCURL. We detail Greedy MD-CURL in Alg. 4 in Appendix G

---

Conclusion, discussion, and future work
In this paper, we present MetaCURL, the first algorithm for dealing with non-stationarity in CURL, 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 non- stationarity 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 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 better regret dependency concerning the varying losses, but do so, we need simplify the assumptions about the dynamics (all uncertainty comes only from the external noise, that independent of the agent's state-action). There seems be trade-off in RL: algorithms dealing with both stn-station and full exploration use UCRL-type approaches, and are thus computationally expensive. We thus leave question for future work: How can we effectively manage non-stationurity and adversarial losses using efficient algorithms, all while addressing full exploration?
10

---

References
[1] Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference Machine Learning (ICML), 2004.
[2] D. Adamskiy, W. Koolen, A. Chernov, and V. Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17(23)11-1,, 2016.
[3] D. Adamskiy, M. Warmuth, and W. M. Koolen. Putting bayes to sleep. In Advances in Neural Information Processing Systems (NeurIPS), volume 25, 2012.
[4] Auer, T. Jaksch, and Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 21, 2008.
[5] A. Barakat, Fatkhullin, and N. He. Reinforcement learning with general utilities: simpler variance reduction and large state-action space. In International Conference on Machine Learning (ICML), pages 1753-1800, 2023.
[6] M. Bayati. Power management policy for heterogeneous data center based on histogram and discrete-time mdp. Electronic Notes in Theoretical Computer Science, 337:5-22, 2018. Proceedings of the Ninth International Workshop on the Practical Application of Stochastic Modelling (PASM).
[7] A. Bensoussan, P. Yam, and Frehse. Mean Field Games and Mean Field Type Control Theory. SpringerBriefs in Mathematics. Springer, 2013.
[8] A. Blum. Empirical support for winnow and reighted-majorite based algorithms: results on calendar scheduling domain. In A. Prieditis and S. Russell, editors, Machine Learning Proceedings 1995, pages 64-72, 1995.
[9] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[10] Y. Chen, S. S. Du, and K. Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. In M. Meila and T. Zhang, editors, International Conference on Machine Learning (ICML), volume 139, pages 1561-1570, 2021.
[11] W. C. Cheung. cntiooration-epploiiatiiii trade-off in reinforcement learning online markov decision processes with global concave rewards. ArXiv, abs//905.00 066666666, 2019.
[12] W. C. Cheung. Regret minimization for reinforcement learning with vectorial feedback and com- plex objectives. In Advances in Nearal Information Processing Systems (NeurIPS), volume 32, 2019.
[13] W. C. Cheung. D. Simchi-Levi and R. Zhu. Reinforcement learning for non-stationary Markov decision processes: The blessing of (More) optimism. In International Conference on Machine Learning (ICMI), volume 119, pages 1844-1854, 2020.
[14] A. Cohen, Y. Efroni, Y. Mansour, and A. Rosenberg. Minimax regret for stochastic shortest path. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 28350-28361, 2021.
[15] A. Daniely, A. Gonen, and S. Shalev-Shwarte Strongly adaptive online learning. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning (ICMI), volume 37, pages 1405-1411, 2015.
[16] R. De Santi, M. Prajapat, and A. Krause. Global reinforcement learning Beyond linear and convex rewards via submodular remi-gradient methods. In Proceedings of the 41st International Conference on Machine Learning. volume 235, pages 10235-10266 2024.
[17] O. D. Domingues, P. M' enard, M. Pirotta, E. Kaufmann, and M. Valko. A kernel-based approach to non-stationary reinforcement learning metric spaces. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130, pages 3538-3546, 1021.

---

[18] Y. Efroni, L. Shani, A. Rosenberg, and S. Mannor, Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning (ICML), volume 119, pages 0614,,613, 2020.
[19] E. Even-Dar, S. M. Kakade, and Y. Mansour. Online markov decision processes. Mathematics of Operations Research, 34(3):726 736, 2009.
[20] Y. Fei, Z. Yang. Z. Wang, and Q. Xie. Dynamic regret of policy optimization in non-stationary environments. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 6743-6754, 2020.
[21] S. Feng, M. Yin, R. Huang. Y.-X. Wang, J. Yang, and Y. Liang. Non-stationary reinforcement learning under general function approximation. In International Conference on Machine Learning (ICML), volume 202, pages 9976-10007, 2023.
[22] Y. Freund and R. E. Schapire. A Decision-theoreti generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 199-19,,1,1,,,,,, 1997.
[23] Y. Freund, R. E. Schapire. Y. Singer, and M. K. Warmuth. Using and combining predictors that specialize. In Annual ACM Symposium on Theory of Computing (STOC), page 334-343, 1997.
[24] Gajane, R. Ortner, and Auer. A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. ArXiv, 0011880.00000 2018
[25] M. Geist, J. Pérolat, M. Laurière, R. Elie, S. Perrin, O. Bachem, R. Munos, and O. Pietquin. Concave utility reinforcement learning: The mean-field game viewpoint. In International Conference Autonomous Agents and Multiagent Systems, page 489-497, 2022.
[26] K. S. Ghasemipour, R. Zemel, and S. Gu. A divergence minimization perspective on imitation learning methods. In Proceedings of the Conference on Robot Learning, volume 100, pages 1259-1277 2020.
[27] A. György, T. Linder, and G. Lugosi. Efficient tracking of large classes of experts. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 885-889, 2012.
[28] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning (ICMI.), volume 97, pages 2681-2691 2019.
[29] E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium on Computational Complexity (ECCC), 14, 01 2007.
[30] C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning (ICML), volume 119, pages 4860-4869, 2020.
[31] T. Jin, J. Liu, C. Rouyer, W. Chang, Y. Wei, and H. Luo. No-regret online reinforcement learning with adversarial losses and transitions. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 38520-38585, 2023.
[32] T. Jin and H. Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 16557-16566, 2020.
[33] K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved Strongly Adaptive Online Learn- ing using Coin Betting. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54, pages 943 951, 2017.
[34] Lavigne and L. Pfeiffer. Generalized conditional gradient and learning in potential mean field games. Applied Mathematics & Optimization, 88(3):89, Oct 2023.
[35] J. W. Lavington, S. Vaswani, and M. Schmidt. Improved policy optimization for online imitation learning. In Proceedings of The 1st Conference on Lifelong Learning Agents, volume 199, pages 1146-1173. 2022. 202.
12

---

[36] N. Littlestone and M. Warmuth. The weighted majority algorithm. Information and Computa- tion, 108(2):112261, 1994.
[37] H. Luo, C.-Y. Wei, and C.-W. Lee. Policy optimization in adversarial mdps: Improved explo- ration via dilated bonuses. In Advances Neural Information Processing Systems (NeurIPS), volume 34, pages 22931 -22942 2021.
[38] Lykouris, M. Simchowitz, A. Slivkins, and W. Sun. Corruption-robust exploration in episodic reinforcement learning. In Conference Learning Theory (COLT), volume 134, pages 3242- 3245, 2021.
[39] B. M Moreno, M. Bregere, P. Gaillard, and N. Oudjane. Efficient model-based concave utility reinforcement learning through greedy mirror descent. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 238, pages 2206-2214 2024.
[40] W. Mao, K. Zhang, R. Zhu, D. Simchi-Levi, and T. Basar. Near-optimal model-free rein- forcement learning in non-stationary episodic mdps. In International Conference Machine Learning (ICML), volume 139, pages 7447-7458, 2021.
[41] B. Marin Moreno, M. Brégère, Gaillard, and N. Oudjane. (Online) Convex Optimization for Demand-Side Management: Application to Thermostatically Controlled Loads, Jan. 2023,
[42] M. Mutti, R. De Santi, P. De Bartolomeis, and M. Restelli. Challenging common assumptions in convex reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages
2022.
[43] M. Mutti, R. D. Santi, P. D. Bartolomeis, and M. Restelli. Convex reinforcement learning in finite trials. Journal of Machine Learning Research, 24(250): 42, 2023.
[44] G. Neu, A. Gyorgy, and C. Szepesvari. The adversarial stochastic shortest path problem with unknown transition probabilities. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 805-813. PMLR, 2012.
[45] R. Ortner, P. Gajane, and P. Auer. Variational regret bounds for reinforcement learning. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115, pages 81-90, 2020.
[46] M. Prajapat, M. Mutny, M. Zeilinger, and A. Krause. Submodular reinforcement learning. In International Conference on Learning Representations (ICLR), 2024.
[47] A. Raj, P. Gaillard, and C. Saad. Non-stationary online regression, 2020.
[48] A. Rosenberg and Y. Mansour. Online convex optimization in adversarial Markov decision processes. In International Conference Machine Learning (ICML), volume 97, pages 3478-5486, 2019.
[49] A. Rosenberg and Y. Mansour. Online convex optimization in adversarial Markov decision processes. In International Conference on Machine Learning (ICML), pages 5478-5486, 2019.
[50] A. Rosenberg and Y. Mansour. Stochastic shortest path with adversarially changing costs. In International Joint Conference on Artificial Intelligence (IJCAI), pages 2936-2942, 2021.
[51] A. Séguret, Wan, and Alasseur. A mean field control approach for smart charging with aggregate power demand constraints. In 2021 IEEE PES Innovative Smart Grid Technologies Europe (ISGT Europe), pages 01-05, 2021.
[52] D. van der Hoeven, N. Zhivotovskiy, and N. CisahBianchi. High-probability risk bounds via sequential predictors, 2023.
[53] C.-Y. Wei, C. Dann, and J. Zimmert. A model selection approach for corruption robust reinforcement learning. International Conference on Algorithmic Learning Theory (ALT), volume 167, pages 1043-1096, 2022.
13

---

[54] C.-Y. Wei and H. Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. In Conference on Learning Theory (COLT), volume 134, pages 2021.
[55] T. Zahavy, A. Cohen, H. Kaplan, and Y. Mansour. Apprenticeship learning via frank-wolfe. In AAAI Conference on Artificial Intelligence. 2019.
[56] Zahavy, B. O' Donoghue, G. Desjardins, and S. Singh. Reward is enough for convex mdps. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 25746-25759, 2021.
[57] J. Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 4572 4583, 2020.
(58) J. Zhang, C. Ni, Yu, C. Szepesvari, and M. Wang. On the convergence and sample efficiency of variance-reduced policy gradient method. In Advances Neural Information Processing Systems (NeurIPS), volume 34, pages 2228-22400 2021.
[59] L. Zhang, T. Yang, rong jin, and Z.-H. Zhou. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning (ICML), volume 80, pages 5882-5891, 2018.
[60] X. Zhang, Y. Chen, X. Zhu, and W. Sun. Robust policy gradient against strong data corruption. In International Conference Machine Learning (ICML), volume 139, pages 12391-12401, 2021.
[61] A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in Neural Information Processing Systems (NeurIPS). volume 26, pages 1583-1591, 2013.
14

---

A Learning with expert advice
In this section, we take a closer look at the Learning with Expert Advice (LEA) framework. We start by presenting, in Subsection A.III general reduction of the sleeping experts framework to the standard framework. Thus, any LEA algorithm can be used as sub-routine for MetaCURL. In Section [ of the main paper, we show 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 in a decision space I, over series of
paper: a learner makes sequential online predictions w w',.... w......t u² T' episodes, with the help of K experts. For each round each expert makes a prediction ut-k; and the learner combines the experts' predictions by computing a vector of := (v ..... k) E SK, and predicting u' := -x=1 ud The environment then reveals convex loss function l u R. Each expert suffers a loss gr, := d' (u("")) and the learner suffers loss e := (u").. The learner's objective is to keep the cumulative regret with respect to each expert as low as possible. For each expert this quantity is defined as Reg(r (k) = Σ pr.k
A.1 Sleeping experts
The sleeping expert problem 88 23 is LEA framework where experts are not required to provide solutions every time step. Let Tc,k E {0, 1} define binary signal that equals if expert active episode and 0 otherwise. The algorithm knows (L***)) and assigns a zero weight to sleeping experts. We would like have guarantee with respect to expert & [K] but only when is active. Hence, we now aim to bound a cumulative regret that depends on the signal 1t Reg (k) == Σtz ((* - k. We present generic reduction from the sleeping expert framework to the standard LEA framework 2
Let, for all episodes E [T].
a' = Ek_ u
Ek,, Itkgghh
We play standard LEA algorithm with modified outputs where, at episode t, expert & outputs
( 0t,
if is active episode I
if not.
standard LEA algorithm gives upper bound the regret Regy(k) with respect each expert k. Using that Ekm ottk ât, we obtain that
T.
K
Reg (k) = Σ 86
Σ
k=
((a)) ((ttiit)
Σ - (w(it)
-e
Reg (k).
sleep
Consequently, the cumulative regret with respect to each expert during the times it is active is upper bounded by the standard regret of playing LEA algorithm with the modified outputs.
A.2 Exponentially Weighted Average forecaster
The exponentially weighted average forecaster (EWA), also called Hedge, a L.AA algorithm that chooses weight that decreases exponentially fast with past errors. We present EWA in Alg 2
15

---

Algorithm 2 EWA (Exponentially Weighted Average)
Input: [K] = {l...., } a finite set experts, v a prior over [K]. a learning rate
for / E [1, ,....., 7) do
Observe loss function t" compute the loss suffered by each expert e* == (x( and suffer loss İ = ( E w
Update for all E [K]
w exp (-nperii) M= whth exp (-neeth))
end for
We 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 ()). If the e losses are convex and take
value in [0, 1), then the regret of the learner playing EWA with any O satisfies, for any k E [K],
log
Tn
Regnn (k)
7
8
In particular, with 17 / /o) the upper bound becomes V (2 log(K).
Theorem A.2 (EWA with exp-concave losses: Thm. 3.2 from (9) If the E. losses are npexp concave, then the regret of the learner playing EWA (with the same value of n) satisfies, for any h: E [K],
log( K)
Reg.r [T) (k) <
17
16

---

B Algorithm for the online estimation of the probability kernel (ø' estimator)
Algorithm 3 Online estimation of the probability kernel (fi estimator)
1: for E ;I,..., } do
2: Get agent's s external noise trajectory (EM))E(N)) from MetaCURL
3: for (n, (2, a) E [N] X' x A do
4: Compute x ,,,,, = In- (2. a, 1
5:
Update the empirical estimations for $ < and x' X:: (x'1xx) ro =n'l -11-al 1 1.-11,(1' (1xl1(x
6: Initialize a new estimator, ph. (2'12, [ (xh...==)) for all x' E X, assign new
weight vector wht n,r,a t. and normalize weight vectors whis for It - 1] such that u.zz ( SttAAA is probability vector in R
7: Simulate sample st R, from distribution (v% a) }
=
F Tm with probability 1/2, Uniformly over X, with probability 1/2,
n.2,a
and use it to build the loss function
(4) = E ((()) + [2]
1 fat (ah...._ =
ZEX
8: Update weights using EWA with loss cl: for all S1
an exp ( (- Et (1th
1+1e n,2,0
(EWA update)
E'= Un exp
8l ('h (-1z,)))
9: Compute tht (,12, a) Ei
mnzaa Pn (.12,
10: end for
11: Issue gt+1 to MetaCURL (line
18 of Alg.
12:
end for
C Auxiliary lemmas
We start with some auxiliary results. Fort E I == [t,++111 +1tel S [T], we define the average probability distribution for all and (z, a) as
+-1
(=(100,))== =
Σ
p (x
Lemma C.1. Let piats be the empirical probability transition kernel computed with data from episodes [L 1). For any 8 E (0, 1), with probability - 5,
N|
11 (1,,) S 1/ 2(t - t.) log
simultaneously for all n E [N], (z, a) E x A. to E [T - -1, and f. E [t. + +1
Proof. For a fixed n E [N) (z, a) E X x A, and E (-1, 1-1,1)141 13121, we define for all E 7,
y n
Σ 0(x') (onttaaer)))
Bernoulli random variable with mean value given by Evrxx 0(x' (x'12,
17

---

The sequence of random variables given by (Y a.2 sel is independent, we assume that the external noises observed at each episode are all independent. Hence, by Hoeffding's inequality we get that, for all & > O,
-2 26) <exp (, (- 1,2
IP
Σ
Y
n.000
R
Σ
V a
Therefore, we have that
P Σ (zt)
(2'1a,)) - -P (x((s, 26)
Σ 0(x') (1n((ree)))))
Σ
26)
t
Z'EX
P tg
Y
E
y
2
S exp ( - 2t² (((-tt)) ts)).
By applying an union bound all E [N], (2) E X x A. and 1 E (-1,1) and noting that, for any two probability distributions p. E Ax. we have that
lpp 41l1
max Σ ((z)(((()) q(x)),
0E(-1,1)
SEX
we arrive at the final result.
Lemma C.2. Let f E := [to + 1,tel S [2]. For all n E [N], and (I, E A
(-x, a) - (11x, S 4g
j=L,
Proof. For l E and for all and (xr, a) we have that
ll, (+1 a) Ph, a))11
Σ
1
Σ (2 s=t.
t
x'E
(0(('12z,)) -0) (2
|r/(-1=,)) - - a-1x,
j=+1
( -)) a)ll t.
where recall that we define A3 == maX (-(x,)))a)) - (1)12,)))l1
Lemma C.3. Let frita be the empirical probability transition kernel computed with data from episodes [ts, 11. For any 8 E (0, 1), with probability
11,, - f/ (-1x,)))1 a) -
log
Σ
2(t - t.)
8
f=
simultaneously for all [N], (I E X A T - 11, and t [t + 1,T].
18

---

Proof.
The result follows immediately from the triangular inequality and Lemmas C.1 and C.2
Lemma C.4 (A version of the inverse of Pinsker's ' inequality). Let pl q' be any distributions over Sx. Define
p' + [
and 9: q' + x
p:= 2
2
Therefore.
KL ( S 2 g112-
Proof. First, note that q is lower bounded by convexity of the simplex, p, q Sx, therefore
2| hence KL(P q) is well defined. Also, by
p(æ) g(x))
KL 9)
Σ NEN
p(x) log
Σ p(x) log
1+
(P(z)
1))
q(x))
NEA
(((x)
Σ p(z)
-1)
((x)
NEX
p(z)
Σ
(p(z) q(x)))
+ Σ (g(x) p(x))
Ex ((x)
=EE
(p(x) q(x))
((x)
SEN
1
|lp d/l
min ((x)
< 2|11112 4l.
Lemma C.5. For any strategy π (SA) XXN, for any two probability kernels p (pv) (P))NN and
q= = (an)nE(N) such that pa. In x A x $00, 1), anr all [N].
p T. (x, a))pp(411111,,... q-1(11
Proof. From the definition of state-action distribution sequence induced by policy π in MDP with probability kernel in Eq. (2). we have that for all (x, E X' A and n E [N],
M T-P (x a)
Ep (x) (a)z). x/.a
19

---

Thus,
1 -M 14: 11 Σ
P (2, a) (I,
2,a
| ( a' (2l 1h "f"" (')gn( (a/x)
d'
Σ
z/,a'
Σ> Σ
14 (x', (n u (7', dd (x)
x'
)gn (2l/'' d') - (+', a' )g (x))x')aaa))
1 (r', 1.12/ a²) - (.(, aa))l= +
Σ - (a', a²) - (3', a')
v'.0'
Σ
T (+', a'
an a')) 11 -1
1, 11--1111-
Since for = 0. 1110
140 -9 111 0, by induction we get that
|| 7 111
p ptt_))plppttllaeeo -0-1(111 a')lla
1=0 ar
Lemma C.6. For any pair of strategies n, n' E (AA)xx .orr any probability kernel p = (Pu)nE[N) such that Pn. x A x + 1], and for all n [N],
1 - p 111
P. N.
(+1x))]
where P (x) = EoEA " for all æ e X and [N].
Proof. Using the recursive relation from Eq. 2 of state-action distribution induced by a policy in MDP with probability transition p we have that
| u -111
Σ
T-P (x, a) p (xx Mn
Σ
T.P (a' (alz) - - (aa
p (a', al )pn (xlp (m) - (a(x)
2,a wt al!
(xl d)) n (x, d') ( d')l
2.0 xe
(4) + | 1
Since No fixed for each state-action distribution sequence. by induction we obtain that
S
p x. (+)) - -f (-1x()))
completing the proof.
20

---

D Proof of Prop. 5.2 Ryy regret analysis
Proof. Here, we set an upper bound on the term R where we pay for errors in estimating p' by p².
T
T
Bi = Σ Fd (1="'p') - Fd (11 (1r
S
V
(n
1
1=
LF
n sp" Pp
Mea 1ar $'111
Im mm
$ LF ΣΣΣΣ
" (z, () 03 a)ll
To obtain the first inequality, we use the convexity of Fet for all / [T], then we use Holder's inequality and the fact that 1 is Lip-iipchitz and for the last inequality we use Lemma C.5
The difficulty in analyzing the L1 difference between p' and p¹ arises from the non-stationarity of p'.
To overcome this we want to use the scheme presented in Subsection 4.3 By Cauchy-Schwarte get that
P LF
(ug-1 (z, a))²
(p)(H2,)) (-
(16)
STN2
Analysis of the L1 norm. We start by analysing the sum over E [7' of the L1 norm in term (+).
For each [N],j E [n] and (x, a) X x A.
p3 (-1r, a)
PJ (3) a) + |2
1p)((zz,a) 65 - a|
|X
t=1
T
(-)(11z,)) a)
1
(/ 0) +
[
X
KI.
2
where we apply Pinsker's inequality.
Consider sequence of episodes = 4 < l2 < that A AP /m/m for all E [m]] Decomposing the KL. sum over [T] as on the intervals
<
km T with I; = [4, 44+1 - 1]. such
I, we obtain that
T
p/ (+lar, a) +
(-12, a) +
(1,,, a) +
2.4 (.12, +
X
[
KL
KL
2
2
2
2
1= tET:
(8)
D
1.4 (Tt
1x, a)
Ja aa (2.0) + [
Bgg
log
-log
2
2
i= TET,
where the expectation of the second term is with respect 5t jJ, (p5(112,0) )
We analyse each term separately:
First, note that (ii) is the expectation over at j.z,a of the cumulative regret of sleeping EWA interval Ij with respect to the expert t, using the loss function lt 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) 5
log(T) = m log(T).
21

---

Regarding term (2), we start by using the inverse of Pinsker's inequality presented in Lemma C.4
(- a)
+ [
(
d/ (-1,, a) + [
)
|
(i) -
2|28|
2
2
==1 T
X
(1,r a) - 13/h (-|z,, a)l
2
t= (EZ,
To simplify notations, from now on we let C == / log
Nixx | A
Applying Lemma C,3
we obtain that
(- a)
(1pr,
2
EET
X
m
C
2C
Σ
1-1
4 +
Σ
[-1
4
4-4+1
Vt - t. +
1=1 IEZ,
k=t.
k=tt
X
|Ca logg( + 2C
/I + [Z
2
X
+ T (A')
C C' + 2CVT
2
mm
m²
Joining the upper bounds of (x) and (ii) we conclude that
T
(11,,))
- (3, 8(()) + (ii)
8 (C2 |2|
+ 1 log(T) + +
A
+ T |x| (AP}2
CVT
m
2 m²
AT 1/3
Thus, for
Th (TT]
(1,5(111, - 0,,,, a)ll, < 12/ (
(17)
Back to the analysis of R. Using the inequality Eq. 17 to bound the L, norm of (+) on Eq. (6). we obtain that
N
R & LENVT
12 1o81044)ogg())3387111 (Dz)2/
3.a < 3/A (o
==1
concluding the proof.
22

---

Note that for Ei=1 ELEZ, R2 (T*) (the third term of the meta meta-regret decomposition of Eq. following the same procedure as above, we obtain that
13
F't (1etttt
1=1
rEZ,
VF F (1e ,, pe sp - s
1=1 EET
$ LF
Mn
1=1 TET
N
11
Lp
(2,))llo{(1aa) a) - (11,,)))]
1EL, n=1 j=1 2,0
170
n
Lp
(1j-1
(x,
ΣΣΣ> -1)
1
STN2
independent of xf14
Since the second term is independent of T the analysis is the same as before and we obtain the same upper bound as for ( (x²).
E Proof of Prop. 5.4 Rblack-box regret analysis [T]
Proof. Assume a Black-box algorithm satisfying the dynamic regret bound Eq. (T), i.e., for any
interval 7 S [7], with respect to any sequence of policies (x. ")EE,, and for any learning rate X,
(I(( )ee)) cc AT + C3
(18)
Consider any sequence of episodes 1 = t < t2 < I = [t,, t++1 for all [m]. We can decompose the black-box regret over [T] as
< fm+ = T 1, forming intervals
Rbbock-box (eEm)) =
Fs (1c
Gi x²)
F F"
1=1 EE
2 + c3
C
A
+
C3
TAP
S CT
X
m
In principle, we would like to select the optimal À that optimizes this dynamic regret. However, as A may be unknown in advance, this is not possible. We show here that running MetaCURL with the learning rate set := (2 J 0, 1, ........ [log2 [2] ensures that the optimal empirical learning rate is close to the true optimal one by factor of and that the learner always plays as well as the optimal empirical learning rate.
Denote by X the optimal learning rate and X the empirical optimal learning rate in A. Note that
C2 A='
C3
X
TTT
We consider three different cases:
If A 2 1: this implies that 2 tea 1. Therefore, we have that T' < crd" +os o2 fh E [0 for all time steps n E [N] and episodes E (T), then
As we assume
6
T]
(ITT)*)EE()) & NT
TAP
m I
C2 n"
+
C3
+
TAP
m
23

---

If & 1/vT: this implies that set 1. Therefore, taking X 1/VT E we have that "1
TVP
TAP
He )EmM)) & Aq
S <aVT +
If X E [1/VT, 1]: in this case, given the construction of A, there a X E such that X & X < 2X* Hence,
Rhinck-bong hox (EtTt))))))))))))))))))))))) s 33/e1 + c3m)T + TA"
m
Therefore, by taking À X in the analysis, ensure that
I/black hox ((T"))))
F² F'((tt pl)
1=1 FET
C2 C2 x + +
TA"
S N
ta +QvT+ +3/C022/ + csmm +
Proof of Thm. 5.1 Main result
Joining the results from the meta-regret bound and the black-box regret bound, get the main result of the paper:
Theorem (Main result). Let d E (0, 1). Playing MetaCURL, with black-box algorithm with dynamic regret as Eq. (TO), with learning rate grid A == { 2....... EWA as the sleeping expert subroutine, we obtain, with probability at least 26, for any sequence of policies (x² )E(T))
... [1/2 log, (T)),, and with
Rim ((x (( s =Ó(VAFT
+ min (VTA&, (AP3(1))))3))
Proof. Define sequence of episodes 1 t t2 tmti = =T +1, with I, = [t,, 1]. such that A%, s AP/m for all i [m]]
The dynamic regret of MME,,, A) with respect to any sequence of policies ( (x''")<E(T)) and any A E A, can be decomposed
((r)((+""))erp)) =
Ft (4 F* (' xp
F F (1 D² F F'
TET:
EET
Meta algorithm regret
Black box regret I,
= Reetta
R
pblack-box ((T² )ee(r))-
From Prop. 5.3 we have that with probability at least 25, and C=== log
N|
mT 2
Rmmeu 4L N 2/3 (33/3) (
+
log(T]A[)-
In addition, for A := 22- زز 0, 2, ... 11/2log,(T)) and À equal the best empirical learning rate in A, Prop. 5.4|yields yields that, if the black- box algorithm has dynamic regret as in Eq. (10) for any interval in T', then
boblack-box ((T""" s NN (02 + R
TAP
+ + c3m3T +
m
24

---

Therefore, joining both results, we get that.
mf
(11"(((("))) S (383))
+
log (T log2 (T))
2
+ +N 22 + )
+Qv 33 c1(02 + +cym)T+ + TAP
C1
Thus, for m [2<T>>) 2/3
with 7 = v
[o (T (T)) 3/0103, we have that
Rirl ((x"
S ST2/3 (4 " log(T) 272/33)
+N c2 +03
= 0 =O(VA='++ min (VTA,, (2/3(19)1131)
G Greedy MD-CURL dynamic regret analysis
Here we introduce Greedy MD-CURL developed by [39], a computationally efficient policy- optimization 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 3391 in Alg. 4 We then provide a analysis upper bounding the dynamic regret of Greedy MD-CURL in quasi-stationary interval valid for any learning rate X. Hence, Greedy MD-CURL can be used as black-box for MetaCURL. This is the first dynamic regret analysis for CURL approach.
Let MP denote the subset of MP to
No where the corresponding policies æ are such that n, (afa:) * for all (r,a) E X' x A, n E [N]. For any probability transition p, r M2 M x -MP." - R such that, for all μ E MP, with its associated policy æ, and μí E &MP.* with its associated policy n², we have
(n(a( T (a x
Σ E ((r
log
(19)
This divergence is a Bregman divergence (see Proposition 4.3 of (39]). Problem 20 implemented with this Bregman divergence has closed form solution, showed in [39]
25

---

Algorithm 4 Greedy MD-CURL
1: Input: number of episodes T, initial sequence of policies xt E (SA)*xN, initial state-action distribution μa,, learning rate > O, sequence of parameters (at))
2: Initialization: V(z, a), p¹ (+2z, a) मेे and p² j = nM
3: for L for1=1,,.... 1,..,, do
4: Agent starts at (r), ab) ~ pa(-)
5: for n = .,,.,, .N do
6: Environment draws new state zt, Pm 1 -1
7: Learner observes agent's external noise stt
8: Agent chooses an action a,, ~ n (-12x)
9:
end for
10:
Update probability kernel estimate for all (x, a):
11:
P (- a) = ( + t
Pm (,),)
12:
Compute policy for the next episode:
13:
# 1+1
arg arg min ((VF"((') +I(,
(20)
PEMPO
14:
forall [2, (x, A.
M (1,
क (a/x)
Eves (2,
15: Compute #f41 (1 01411) (+1 + 0141/|Al
Compute f1+1_ / gr+) as in Eq.
17: end for return (eT)))(T)
G.1 Dynamic regret analysis of Greedy MD-CURL
Let us assume we analyze our regret in an interval = [t., te] S [T). We denote by R2 the dynamic regret of instance of Greedy MD-CURL started at episode t, until the end of interval / at episode te. We denote by r' the policy produced by this instance Greedy MD-CURL at episode t 1, p the true probability transition kernel, and
(z = t-
Σ a=t,
1 Car (m:o..)))=))
the empirical estimate of the probability kernel at episode 4, with data from the beginning of the interval L.
We define and decompose the dynamic regret Ry with respect to any sequence of policies ( )eer into three terms as follows:
R₁ ((e)) = FF'( v0) F² F' 'p''
Σ YET
F* FI
'u' x' - F² FI( .5))
IET
RADD
(21)
Σ Ft (1TTT1)) -F YET
F* F"p
F* (1
+
YET
Reshir (eEr)
Reguee (xe1i*)
The terms RMDP (m') and R (I*1*) pay for our lack knowledge of the true MDP, forcing us to use its empirical estimate. The term pepoliiy corresponds to the loss incurred in calculating the policy
26

---

by solving the optimization problem given in Eq. (20). Below, we present the first analysis of the dynamic regret for CURL algorithm. We consider each term separately.
G.1.1
RyD analysis
In Section 2 we assume that the deterministic part of the dynamics, given by 9n, in equation (8) for each time step n, known in advance. The source uncertainty and non-stationarity in the MDP comes only from the external noise dynamies, 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 Ry (x²)) and RMDP (IT**) are the same.
Proposition G.I. With probability least 1 - 8.
|
BMD S LF log
V
for all intervals 1 E (T]. The same result is valid for (TTt).
Proof. We start by using the convexity of Ft, Holder's inequality, that F is Lp-Lipschitz, and Lemma C.5 to obtain that
f
RMDP (T)))
S
LF
(c, (c),))ll(((1)aa) - -5 a)ll
(22)
Applying Lemmas C.I and C.2
we have that for any 8 (0, 1), with probability 8.
[+b) a) D3 (112,))) < (+,r, a) p) a)ll + |1
125 (110,))))) a)
N + Σ 4
1-1
s
log
2(t - 1.)
k=t
Using this to continue the upper bound of Eq.
22 we conclude our proof:
||
1-1
RMDP (T') S 22
V
log
Σ
2(1 - (x)
8
t=1,
k=t.
1
M1211A1222111
< N2 V
log
VITT+ 1
8
G.1.2 Apolicy analysis
Proposition G.2. Let b be a constant defined as
b = 8N2 + 2N Alg()AA) (og( log((1))) + 2N log((4) + N log((AA)
Then, Greedy MD-CURL obtains, for any sequence of policies (n²* )iEr. and for any learning rate >>0 0,
2
pepoliey ((EE")))E)) S AL
+
Proof. We adapt the proof of Prop. 5.7 of that upper bounds the static regret incurred when solving the optimization Problem (20), for proof that upper bounds the dynamic regret. The main difference is that, 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 different policy given by -.* Consequently, the analysis remains the same as in (39 for all terms that do not depend on -' but requires a new analysis in terms that do depend on it.
27

---

To simplify notation, we take := (F # as in appendix D.5 of 39 to show that
and p² = 1 "
We can use the same reasoning
Repllcy
(A(E pe p r(u
T(u
I(p ++ nl
TET
TET
Since the term does not depend on wht its analysis follows directly from
33 and is given by
1
2NV
A X
+2Na
(23)
2A
NET
where LF is the Lipschitz constant of F and a' is an imput parameter of Greedy MD-CURL.
We then proceed analyze term B. Again, following the procedure of appendix D.5 of [39], obtain that
B
P(p 11111
pp
r(p"
r
I( 1. 14)
(6)
T(u
# 11") - l(u
at li++1 :1
(is))
Let th: (Sxxa) + R denote the function inducing the Bregman divergence I' of Eq. further shows that:
19
39
(1) S -- >+ log
([AI) a. ||000
16
+1
bbo,
(ii) 2N ELEr Oit, and this upper bound is found independently of x5.
(iit) s -Tp v.)).
Lemma D.6 [39 shows that,
( ; + I ,p/) < N log([AA).
Only term (i), which involves || " " requiring then a new analysis. For this purpose, we rely on the following two results:
ol depends on the sequence (I*** "()m))
From Lemma 5.6 of (39. we have that, for all strategies n,
2N
4 T 1o0,1 S ( t.
From auxiliary Lemma C.6 proved Appendix C we have that
(x))l (+1=) - n. ---l"1l s NAT"
(=1EE
Therefore, using the triangular inequality and the two results above, we obtain that
I|
1oc,1 I
|||==
1.+ 5tt1
loc, + - b. 5t+1
3/ 51+1
2N
+NA
Therefore, the bound term B is given by
B N
log
[
2N
+
NAT
2N Σ
ar + N log((A1))
(24)
1 1-1.
tel
28

---

Final step: joining all results
Joining the upper bounds term A from Eq.
(23
and on term B from Eq. 24 have that
Epplicy ((T")))E)) 1 B
1
2N
11
2Na
2X
1-12
+
N
log
[AA]
2NV
+ +NA,")
+ 2N Σ
a + NN [lgg((A))
-- to
TET
TET
we take the learning rate as 04 = 1/t, then, for all > 0,
N A7
Ripllyy ((TT*)) E & 1 +
+ 1 8N2 + 2N² log([ log( logg()(())) + 2N 2N log((4)) + N log( (|A|]
N2 +6
1 +
where b = 8N2 + 2N log(1o (IAl) log( (1) log((?))) - 2N logg(())) + N ll)g((AA))
G.2 Final Greedy MD-CURL regret analysis
Replacing the bounds of Prop. G.I and G.2 in Eq. (1 yields the final upper bound of Greedy MD- CURL's dynamic regret for any interval T T with respect to any sequence of policies (x )ee:
Theorem G.3 (Dynamic regret of Greedy MD-CURL... Let b be a conslant defined as
= 8N2 + 2N (lA)) log( + log((/))) + 2N log(( + N log( lo)(
Let 8 E (0, 1). With probability at least 1 for any interval I S [T), for any sequence of policies tee for any learning rate X > and for a, 1/t, Greedy MD-CURL obtains
+ + N
+ +2N
|
RI((T")) &
log
I + 2
Hence, Greedy MD-CURL meets the requisite dynamic regret bound from Eq. 10 to serve black-box algorithm for MetaCURL achieving optimal dynamic regret.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly provide the contributions of our work and our settings in the Introduction. We formally detail our hypothesis in Section We present the new algorithm in Section
All regret results related to the new algorithm claimed in the abstract and introduction are stated in Section and proved in the Appendix.
4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section we formally detail our assumptions and discuss the strong assumption made about probability transitions, justifying it as a means of providing low- complexity methods. We also discuss real-world applications that satisfy these assumptions. In Section 6 we discuss the aspirational goal of addressing this limitation as future work. Remark 3.1 we discuss the complexity of the algorithm.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
30

---

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

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is theoretical paper, with no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
wow.siyyynnioooioioooooooooiiiii for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppcccg.uiiieeaeeec http:///ggideeeeeecuuuuumiibea http:e////ooeeeubeiiiiiimoo
assionPoicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
This is 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 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, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is theoretical paper, with no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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 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 the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is theoretical paper, with no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This work conform with the NeurIPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
33

---

Justification: The results presented in this paper are largely theoretical. The framework provided in this paper very general and could be applied any reinforcement learning or concave utility reinforcement learning problem in tabular MDP. Therefore, as with any reinforcement learning algorithm, 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.
the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
This paper does not existing assets.
Guidelines:
34

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (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, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that 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.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
35

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "VroQmQdy5a", "reviewer": "Reviewer_ZTXg", "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.", "questions": "Thanks for the opportunity to review this paper. I have some questions as follows. \n[Major issues]\n\n1. Novelty \n\n- 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?\n\n2. Dynamic regret representation \n\n- 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$.\n\n3. Dynamic hypothesis\n \n- 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.\n\n[Minnor issues]\n1. Terminology\n- 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.\n\n2. Regarding with the related works. \n- 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. \n\n [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.\n[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": "There is no limitations on potential negative societal impact .", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The novelty is clear. That is expanding CURL in non-stationary MDPs.", "weaknesses": "My comments on weaknesses are listed below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Questions\n- **Novelty:** Our algorithm runs without needing knowledge of the environment changes as input, but the final error guarantee does depend on these variations, specifically through the non-stationarity measures $\\Delta^p$ and $\\Delta^p_\\infty$. This agrees with the lower bound in [33], which we cite in line 68 of the paper. This lower bound is independent of the algorithm and captures the difficulty of the problem as a function of these measures. Note that all previous algorithms in the literature but the one in [44] require knowledge of the environment changes as input, which in practice is often not feasible. This is an advantage of our algorithm.\n\n- **Dynamic regret representation:** Here, $(\\pi^{\\*,t})\\_{t \\in [T]}$ refers to any sequence of policies, not just the optimal ones. The dynamic regret in Equation (5) and the non-stationarity measure $\\Delta\\_t^{\\pi^{*}}$ in Equation (7) are defined for any sequence of policies $(\\pi^{\\*,t})\\_{t \\in [T]}$. Therefore, our regret bound is valid for any sequence of policies. Choosing the optimal sequence of policies to evaluate the regret is natural. The fact that this sequence of policies may not be unique poses no problem in which case we would pay $\\min\\_{\\pi^{\\*}} \\Delta^{\\pi^{\\*}}$. \n    \n\n- **Dynamic Hypothesis:** We further discuss the importance of the dynamics assumption in Eq. (8) in the common response to all reviewers. We want to emphasize that our dynamics still assume that the noise's distribution $h_n^t$ and the cost functions are completely unknown, requiring simultaneous model learning and optimization. This places our problem outside the scope of control literature and into the realm of reinforcement learning. Many existing RL studies address problems other than the exploration-exploitation dilemma, such as the initial work on concave utility RL mentioned in the paper, which typically consider offline settings with fully known dynamics [23, 47, 48, 5, 46, 20].\n\n- **Terminology:** We appreciate the reviewer's comment and agree that the term may be ambiguous. We will provide additional explanations in the paper to clarify its meaning. However, \"loop-free\" is also commonly used in the context of learning in model-based episodic Markov Decision Processes (MDP) to describe online MDP problems with fixed episode lengths and a fixed initial state-action distribution per episode. This term was first introduced by [Neu et al. 2010], and has since been used in several influential works, such as: [Neu et al. 2012, Zimin et al. 2013, Rosenberg et al. 2019, Jin et al. 2020, Efroni et al. 2020, Moreno et al. 2024]; among many others. \n\n- **Related work:** We greatly appreciate the reviewer for pointing us to these related works. We will include them in our citations.\n\n### References:\n- *Neu et al. 2010, Online Markov Decision Processes under Bandit Feedback, NeurIPS*\n- *Neu et al. 2012, The adversarial stochastic shortest path problem with unknown transition probabilities, AISTATS*\n- *Zimin et al. 2013, Online Learning in Episodic Markovian Decision Processes by Relative Entropy Policy Search, NeurIPS*\n- *Rosenberg et al. 2019, Online Convex Optimization in Adversarial Markov Decision Processes, ICML*\n- *Jin et al. 2020, Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition, ICML*\n- *Efroni et al. 2020, Optimistic Policy Optimization with Bandit Feedback, ICML*\n- *Moreno et al. 2024, Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent, AISTATS*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qHznvtPOSo", "reviewer": "Reviewer_kKtv", "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.", "questions": "I put the questions in the above section.", "limitations": "I do not think this theoretical work could pose any potential negative societal impact.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- [**Motivation and Significance**]: The problem of non-stationary MDPs is critical in CURL, and this paper provides valuable theoretical insights and guarantees for the CURL algorithm. While I am not an expert in RL theory, I think in general this work is critical for both RL theory and empirical algorithms design. \n- [**Technical Soundness**]: While I am not an expert in RL theory, the theoretical results and proofs presented in the paper appear to be solid and well-constructed, especially on the regret analysis part (only related to changing frequency and magnitude). \n- [**Presentation**]: The paper is generally well-written and the theoretical analysis is clearly presented (accessible even to readers outside the theory domain)", "weaknesses": "Since I am not an expert on RL theory, I have listed most of my questions in this section. \n\nQ1: 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?\n\nQ2: 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for recognizing the new theoretical insights in our paper. We address the questions below:\n\n- **Q1:** We take into account two types of non-stationarity: on the objective functions and on the dynamics from the external noise distribution $h_n^t$. Each impact the regret in a different way in Theorem 5.1:\n\t- **Non-stationarity factors from the objective functions:** Our regret bound works for adversarial objective functions, i.e. that can change arbitrarily at each episode, and are unknown to the learner. This robustness to non-stationarity in losses affects the regret through the term $\\Delta^{\\pi^*}$. This is a novel aspect of our algorithm. We are the first to present an algorithm that addresses both dynamic non-stationarity and arbitrarily changing losses without requiring prior knowledge of the variation budget.\n\t- **Non-stationarity in dynamics:** In the paper, non-stationarity in the dynamics arises from the unknown distribution of the external noises $ h\\_n^t $. This affects the regret through the terms $\\Delta^p$ and $\\Delta^p\\_\\infty$, as detailed in Theorem 5.1. However, our bounds would still hold if the state dynamics were also non-stationary (i.e., $ g\\_n^t $ in line 128 instead of just $ g\\_n $), provided $ g\\_n^t $ is known to the learner.\n\n- **Q2:** We also account for the non-stationarity of the policies in our work through the term $\\Delta^{\\pi^{\\*}}$, defined in Equation (7). Our algorithm achieves the optimal regret bound for this term as stated in Theorem 5.1. Could you please provide the references to the works you mentioned so that we can offer more details on this?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RHoatKeOkt", "reviewer": "Reviewer_La9P", "summary": "The authors present a policy learning algorithm for non-stationary (+ uncertain) environments and convex utilities. \nThe 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.", "questions": "- Are baselines the same as the black-box algorithms? \n- Line 164, what does parametric algorithm mean in this context\n- Line 141 why do policy optimization algorithms have lower complexity?\n- Any thoughts on how the algorithm changes if g_n is uncertain?\n\nComments for improving paper:\n- line 13: we achieve ---> the algorithm achieves?\n- line 15: \"full adversarial losses, not just stochastic ones.\" is ill-posed\n- 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).\n- 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. \n- Maybe write contributions as a paragraph, since points 2,3 are not contributions but explanations of point 1.", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Proposed an algorithm for non-stationary and uncertain convex utility MDP\n- Achieves optimal dynamic regret", "weaknesses": "- 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).  \n- The paper is difficult to follow particularly section 3 from line 175 and section 4", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and questions. We agree that the paper is notation-heavy and may be difficult to follow in some parts. We welcome any further suggestions on how to improve the readability of the paper.\n\n### Questions\n- **Baselines vs blackbox:** Yes, baselines algorithms are the same as blackbox, we apologize for the confusion caused by using both terms. We will revise this to ensure consistency.\n\n- **Line 164** We apologize for the typo where we incorrectly used the word \"parametric.\" We wanted to say that our approach is applicable to any black-box algorithm that satisfies Equation (10), and specifically it also works if the algorithm depends on a learning rate $\\lambda$, without requiring us to specify the optimal $\\lambda$ as an input (parameter-free).\n    \n- **Line 141** In tabular RL, there are two main approaches for dealing with uncertainty and adversarial losses: policy optimization (PO) and occupancy-measure (or state-action distribution) methods.\n\n\tOccupancy-measure methods leverage the ideas from UCRL2 [4]. They construct a set of plausible MDPs compatible with the observed samples and then play the policy that minimizes the cost over this set of plausible MDPs.\n\n\t PO methods evaluates the value function and uses a mirror descent-like updates directly on the policy, solving the optimization problem through dynamic programming to obtain a closed-form solution for the policy. This approach is more computationally efficient than planning in the space of all plausible MDPs.\n\n\tFor a more detailed discussion on both approaches we refer to the works of [Luo et al. 2021, Efroni et al. 2020a,b]. \n\n- **How the algorithm changes with $g\\_n$ unknown:** \n\t- **MetaCURL analysis:** MetaCURL with a black-box algorithm that explores could be extended to the case where $g_n$ is unknown but belongs to a known parametric family. The  case where $g_n$ is completely unknown would be harder and require further work.\n\t- **Existence of black-box algorithm for CURL that explores:** No closed-form algorithm for exploration in CURL exists. PO methods for RL rely on the value function, making them unsuitable for CURL, as CURL invalidates the classical Bellman equations. The alternative occupancy-measure methods, while applicable, are computationally less efficient and lack a closed-form solution. The algorithm we propose as a black-box is a PO method adapted for CURL and is derived from [35], but it also assumes that $ g_n $ is known.\n\n### Comments for improving the paper: \nThank you for pointing out the typos in lines 13 and 15; we will correct them. We also appreciate the feedback on making our paper more accessible to readers outside the online learning and theoretical reinforcement learning communities. We will provide a clearer explanation of the challenges of non-stationarity, uncertainty, and adversarial losses earlier in the introduction.\n\nWe will clarify our assumptions on the dynamics by moving Equation (8) to the introduction. We just want to highlight that we fully acknowledge the limitations of our restrictive assumptions in the paper. These are addressed in the abstract, introduction, comparison table 1, Section 2, and the conclusion, where we also point it as an important improvement for future work.\n\nRegarding our contributions, we list them as separate points to highlight the distinct novelties of our method. The third point, in particular, stands as an independent contribution:\n- **Point $1$, New algorithm:** MetaCURL is a new-algorithm for online MDPs dealing with non-stationarity, partial uncertainty, adversarial losses, convex losses, achieving optimal dynamic regret, and being efficient to compute.\n- **Point $2$, New analysis:** this is the first application of learning with expert advice theory to Markov Decision Processes, resulting in analyses significantly distinct from existing RL approaches and potentially inspiring new algorithms for RL and CURL.\n- **Point $3$, New black-box algorithm:** Developing the meta algorithm and proving its regret is one aspect (points $1$ and $2$), while demonstrating the existence of a baseline algorithm that meets the regret bound in Equation (10) is another contribution, detailed in Section 5 and Appendix G.\n\n### References:\n- *Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS 2021*\n- *Efroni et al. 2020a, Optimistic Policy Optimization with Bandit Feedback, ICML 2020*\n- *Efroni et al. 2020b, Exploration-Exploitation in Constrained MDPs*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KaXtNtn2pv", "reviewer": "Reviewer_55Y9", "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.", "questions": "Please see the weaknesses part.", "limitations": "No further limitations to be addressed", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The designed algorithm is parameter-free, and does not require the knowledge of variation budget of transitions.\n2. The results are theoretically solid.", "weaknesses": "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].\n2. The transition dynamics, while there are many suitable applications, is also restrictive for a theoretical work.\n\n\nFeng et al., Non-stationary Reinforcement Learning under General Function Approximation, ICML, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for recognizing the new theoretical insights in our paper. We address the questions below:\n\n- **1. tabular MDP:** Thank you for bringing this related work to our attention, we will include a citation in our paper. Thanks for raising this question, we believe this could be an interesting future work of our paper and we will add it to the conclusions. To answer it, we can break the necessary changes to adapt our result to function approximation in two:\n\t\n\t- **The Meta algorithm:** the analysis of the meta-algorithm depends on the method used to estimate $ p^t $. We believe that a parametric estimation could be employed, which would require a new loss function for the second expert algorithm that handles non-stationarity on the estimation of the probability transitions.\n        \n\t- **The Black-Box Algorithm:** We need to select a black-box algorithm for CURL that generalizes well to function approximation scenarios. Just as policy optimization algorithms are known to generalize effectively in such scenarios for RL (e.g., see [Luo et al. 2021]), we believe that the black-box approach we propose from [35] in Appendix G, which adapts policy optimization for CURL, can be extended to this context.\n    \n- **2. Transition dynamics:** We address this concern in our general response to all reviewers as well. We open on some details below:\n\t- **New theoretical analysis:** Addressing the non-stationary CURL scenario is theoretically more challenging than RL, even with restrictive assumptions about the dynamics. To derive a policy using the learning with experts advice framework, we must estimate the losses of non-played expert policies based solely on the observations from the played policy.\n\n         If $ g\\_n $ is known, we can use the external noises observed by the agent and the function $g\\_n $ to simulate the trajectory of any non-played policy in the true environment, thereby defining an empirical state-action distribution $\\hat{\\mu}$ for each expert. In RL, where $ F^t(\\mu) := \\langle \\ell^t, \\mu \\rangle $, estimating the loss of each expert at episode $ t $ by taking $\\langle \\ell^t, \\hat{\\mu} \\rangle$ is sufficient to prove meta-regret convergence due to the linearity of the expression, requiring only common model-based RL techniques. \n\n        In CURL, this approach fails due to its non-linearity convexity. Therefore, we need to address the more challenging task of estimating the non-stationary probability transition $ p^t $ to estimate the losses. This leads to the main theoretical innovation of the paper: the development of the second expert scheme capable of estimating the transition probabilities even in the presence of non-stationarity. The non-linearity of CURL makes it theoretically more challenging than RL.\n         \n\t- **Existence of black-box algorithm for CURL that explores:** No closed-form algorithm for exploration in CURL exists. Policy optimization (PO) methods for RL rely on the value function, making them unsuitable for CURL, as CURL invalidates the classical Bellman equations. The alternative occupancy-measure methods, while applicable, are computationally less efficient and lack a closed-form solution. The algorithm we propose as a black-box is a PO method adapted for CURL and is derived from [35], but it also assumes that $ g_n $ is known.\n\n### References:\n- *Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS 2021*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wVhjkwYbvt", "reviewer": "Reviewer_FWrb", "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.", "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.\n\nA good figure example can be found in Fig.1 of [1]. \n\n[1] Levine, Sergey, et al. \"Offline reinforcement learning: Tutorial, review, and perspectives on open problems.\" arXiv preprint arXiv:2005.01643 (2020).\n\nA good introductory example can be done by setting some parameters equal to low dimensions.\n\n# Specific Questions about the Settings\n1. Can your framework handle cases when the state or the action is continuous?\n2. Do we need to assume the occupancy measure is non-zero?\n\n# Inconsistent Notations\n1. 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.\n\n2. 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$? \n\n3. 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?\n\n4. In L248, Why N is treated as a function, $N(x')$? But in L19, authors claim \"episodes of length N\".\n\n5. In L210, \"For each round t\". In L225, \"In every episode t\". Actually, from my perspective, round t is different from episode t.\n\n6. 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$?\n\nI strongly recommend the authors to introduce a notation table.\n\n# Specific Questions about MetaCURL\nAs mentioned previously, because the notations are inconsistent, it is really hard for me to fully understand the proposed framework.\n\n1. Learning with Expert Advice (LEA)\n\n    1.1 Do you assume these K experts are optimal? What if there is limited expert knowledge?\n    \n    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?\n\n2. 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?\n    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?\n\n3. 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?\n\n4. Does the algorithm know which expert is active? Is that signal too strong? Can such information be learned?\n\n5. What is the time complexity of algo. 1? \n\n6. Theorem 5.1\n    \n    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?\n\n    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\".)\n\n[2] Rosenberg, Aviv, and Yishay Mansour. \"Online convex optimization in adversarial markov decision processes.\" International Conference on Machine Learning. PMLR, 2019.\n\n7. 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": "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.\n\n-----------------Updates\n\nThanks for the thoughtful discussions. After careful consideration, I have decided to maintain my current rating of 4.\n\ntl&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.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "Proofs are provided. It seems that the proposed theorems and propositions are novel.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Motivational examples:\n  We agree with the suggestion to provide examples to motivate our setting. We will include these examples in the introduction on the extended version.  \n\n### Questions about the setting:\n- **1.** We focus on the model-based RL framework commonly used in theoretical works, which does not address continuous states or actions. However, our work can be extended to handle continuous states and actions by using a function approximation algorithm as a baseline and assuming the transition probabilities belong to a known parametric family.\n       \n- **2.** No, there are no restrictions on the occupancy measure.\n\n### No inconsistent notations:\nThere is no inconsistency in our notations and we respectfully disagree with the reviewer on this point. We address all the specific concerns below:\n\n- **1. and 2.** In Section 4.1, 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$. Thus we index each expert by the episode it has been activated at.  We define the notation $[T]$ on line 21 as $[d] := \\{1, \\ldots, d\\}$ for all $d \\in \\mathbb{N}$. This definition is used consistently throughout the paper. For intervals starting from an episode $t \\neq 1$, we explicitly write $[t, T]$.\n\n- **3. Length $N$:** Yes, each episode consists of $N$ steps, a common assumption in episodic MDP. Practical examples include daily tasks where each day is an episode discretised within $N$  time steps. \n\n- **4. Notation $N$:** The notation $ N_{n,x,a}^{s,t}(x') $ represents the number of times an agent transitions from the state-action pair $(x, a)$ to the state $x’$ at time step $n$ between episodes $s$ and $t$. The notation $N$ indicates the length of an episode. To avoid confusion, we will change the letter for one of these notations.\n\n- **5. round $t$:** Round $t$ is the same as episode $t$.\n\n- **6. exponent symbols:**  The $2/3$ in the regret expression at Line 268 is an exponent. The $t$ in $F^t$ or $\\hat{p}^t$ indexes the objective functions or probability estimation at episode $t$, as defined in Lines 115/116 and Line 118, and is used consistently throughout the paper. This is a common notation in the literature used to avoid having all indexes written as subscripts when many indexes are needed, see for example [Perrin et. al, 2020].\n\n### Questions about MetaCURL\n- **1. and 2.** We do not fully understand the question. Could you please provide more details?\n\n- **3.** The distribution $h\\_n^t$ is entirely unknown to the learner. However, since $g\\_n$ is assumed to be known and each agent observes their own state-action trajectory, they can determine their external noise trajectory by simply inverting $g\\_n$, that is commonly an additive or multiplicative function with respect to the noise.\n\n- **4.** There is no need to learn it. If an expert is active at episode $t$, it will output a policy; if not, it will not have an output. This is how the meta-algorithm knows which experts are active.\n\n- **5.** The runtime is determined by the number of experts (i.e., instances of the black-box algorithm) multiplied by the time complexity of the black-box algorithm. Given our choice of naive intervals for running each black-box algorithm, there are $T$ experts, which increases the computational complexity by a factor of $T$. However, as noted in Remark 3.1, there are more sophisticated ways for designing running intervals that can reduce the computational complexity to $\\log(T)$ and can be adapted to our case. \n\n- **6.**\n\t- **6.1**\n\t\tThe algorithm's error is measured by the dynamic regret in Eq. (5), which is the difference between the learner's total loss and that of any policy sequence. In environments with changing objective functions, the regret bound depends on the total variation of the objective functions or the policy sequence, $\\Delta^{\\pi^*}$.\n\t\t\n\t\tFor environments with changing probability transitions, the regret bound depends on either the abrupt variation, $\\Delta^p_\\infty$, or the smooth variation, $\\Delta^p$. A robust algorithm  depends on the minimum of these two metrics. If there are few abrupt changes, $\\Delta^p\\_\\infty$ is smaller, and the algorithm performs at $\\sqrt{\\Delta^p_\\infty T}$. If changes are frequent but minor, $\\Delta^p$ is smaller, and the algorithm performs at $T^{2/3} (\\Delta^p)^{1/3}$. Prior to our work, only [44] had an algorithm demonstrating such robustness.\n\t\t\n\t\tOur algorithm is the first to achieve optimal performance with respect to both $\\Delta^p$ and $\\Delta^p\\_\\infty$ and depends on $\\Delta^{\\pi^*}$ rather than variations in the objective function. This allows our algorithm to excel even when the objective function changes arbitrarily, a capability not offered by previous work.\n\n\t- **6.2** Our regret bound also depends on the state space $\\mathcal{X}$, the action space $\\mathcal{A}$, and the episode length $N$. Due to these dependencies making the regret bound expression cumbersome, we simplify the presentation by expressing the result in the order of the number of episodes $T$ alone. The notation $\\tilde{O}$ signifies that the bound is of the same order as the expression in $T$, disregarding constants and logarithmic factors. Also, in Propositions 5.2, 5.3 and Appendix F we explicitly detail these dependencies. This is common practice in the literature, see for example [44].\n        \n- **7.**\n\tWe 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. \n\n### References:\n- *Perrin et. al 2020, Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications, NeurIPS 2020*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mYCsrntONG", "reviewer": "Reviewer_unHu", "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.", "questions": "MOTIVATION: NON-STATIONARY CURL.\n\nBoth 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.\n\nMOTIVATION: OCCUPANCY VS SINGLE-TRIAL.\n\nAs 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?\n\nMOTIVATION: NO EXPLORATION.\n\nStudying 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.\n\nNOVELTY OF THE ANALYSIS.\n\nCan 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.\n\nADDITIONAL REFERENCES.\n\nWhile 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.\n\nOTHER COMMENTS.\n- 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.\n- 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?\n- 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": "The paper is mostly upfront in mentioning the limitations introduced by restrictive assumptions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Novelty of the setting. Concave utility RL has been studied extensively recently, but I am not aware of any work combining concave utilities and non-stationarity;\n- Simplicity of the approach. The expert-based solution is neat and easy to follow.", "weaknesses": "- Motivation of the setting (1). The paper does not do much to support why studying non-stationarity in CURL is useful/interesting;\n- Motivation of the setting (2). The paper only evaluates the performance of the expected realization rather than the expected performance;\n- 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;\n- Analysis. It is unclear whether the analysis brings some interesting techniques beyond what has been done in prior works.\n\nThis 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.\nTo these reasons, I am currently providing a slightly negative evaluation. I would like to hear from the authors on these concerns. More details below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. Below, we address the main concerns:\n\n- **Motivating the Setting:**  In our common response to all reviewers we further elaborate on how the applications presented in the paper align with CURL. We plan to include them earlier in the introduction for the extended version.\n\n- **Novelty of the analysis:** Our approach goes beyond simply combining RL with EWA. The challenge is that, due to the uncertainty and non-stationarity of the environment, the losses of each expert are unknown.\n\n\tIndeed, to use the learning with experts framework we need to estimate the losses of non-played expert policies based solely on the observations from the played policy, given the incomplete knowledge of dynamics. For that, we must construct an estimate $\\hat{p}^t$ of the non-stationary probability transition. Using the empirical estimator for $\\hat{p}^t$ and standard RL results for bounding the $L_1$ norm between $\\hat{p}^t$ and the true dynamics $p^t$ [Neu et al. 2012; 38] cannot be applied due to non-stationarity. To overcome this, we propose a second sleeping expert scheme to compute $\\hat{p}^t$ (Alg. 3), where each expert is an empirical estimation of $p^t$ using values from different intervals. Obtaining the optimal rate for it was challenging and required new technical approaches, including a new specific loss function (see Eq. (12) and Alg. 3), and a new regret analysis (see Prop. 5.2). \n\n\tFinally, we need to estimate $\\hat{p}^t$ because we are dealing with CURL instead of RL. In RL, the linearity allows us to accurately estimate the loss of each expert's policy, even if the policy is not played, by simulating trajectories with $g\\_n$ using data from the played policy. However, in the convex case, this approach does not work, so we must estimate $\\hat{p}^t$ to determine the losses of non-played policies.\n\n- **No exploration:** We  address the concern about the dynamic hypothesis in our common answer to all reviewers. We believe our work could be extended to cases where $g_n$ belongs to a known family of parametric functions. We address below the question regarding the computational complexity:\n\n\t In tabular RL, there are two approaches for dealing with dynamic’s uncertainty and adversarial losses: policy optimization (PO) and occupancy-measure methods. Occupancy-measure methods use ideas from UCRL2 [4]. They construct a set of plausible MDPs compatible with the observed samples and then play the policy that minimizes the cost over this set of plausible MDPs. PO methods evaluates the value function and uses a mirror descent update directly on the policy, solving the optimization problem through dynamic programming to obtain a closed-form solution. PO is then more computationally efficient than planning in the space of all plausible MDPs [Luo et al. 2021, Efroni et al. 2020a,b]. \n\n\tNo efficient method that fully explores in CURL exists. As PO methods for RL rely on the value function, they are unsuitable for CURL, as CURL invalidates the classical Bellman equations. The occupancy-measure methods can be applied but are computationally less efficient. The algorithm we propose as a black-box is a PO method adapted for CURL from [35], but that also assumes that $ g\\_n $ is known. \n\n- **Occupancy vs. single-trial:** Thank you for pointing out the work by Mutti et al., 2022. It is an interesting question and we will discuss it in our paper. We chose to work with the expected realization setting to complement existing CURL research, also benefiting from the algorithm from [35] as a black-box. In scenarios with many homogeneous agents (like those in Section 2), a mean-field approach could justify this choice. \n\n- **Bandit feedback of $F^t$:** This is an interesting question for a future work. The CURL bandit framework is significantly more difficult, in the same way that the convex bandit framework is more difficult than the multi-armed bandit one in online learning. In addition, it is also harder for the meta-algorithm to combine results from bandit algorithms while maintaining the optimal regret rates (see Agarwal et al., 2016). \n\n- **Markovian policies:** In a non-stationary environment history-based policies can be detrimental, as they rely on outdated information. What was learned about the environment in previous episodes might no longer be accurate in the current one. Since the learner is unaware of the variation budget of the environment, the best approach is to discard past knowledge and restart learning at every major change in the environment.\n\n    Moreover, history-based policies are unnecessary for determining optimal restart times. Our meta-algorithm aggregates active instances of a black-box algorithm, ensuring performance at least as good as the best active instance, likely the longest-running one since the last major change in the environment. Given that the environment is near-stationary since the last major change, any history-based policy can be associated with a Markovian policy with the same state-action distribution [Putterman, 1994]. We can then just work with Markovian policies.\n\n- **Additional references:** Thank you for pointing out these interesting new references. We will add them to our related work.\n\n\n### References:\n- *Neu et. al 2012, The adversarial stochastic shortest path problem with unknown transition probabilities, AISTATS*\n- *Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS*\n- *Efroni et al. 2020a, Optimistic Policy Optimization with Bandit Feedback, ICML*\n- *Efroni et al. 2020b, Exploration-Exploitation in Constrained MDPs*\n- *Agarwal et. al 2016, Corralling a Band of Bandit Algorithms*\n- *Jin et al. 2020, Learning Adversarial MDPs with Bandit Feedback and Unknown Transition, ICML*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time and  feedback in evaluating our paper. While we agree that the assumption in the dynamics of Equation (8) may seem restrictive, we explain below why studying this case is important for CURL. Additionally, we highlight some of the novel contributions of our work. 

- **New algorithm:** This is the first work where the framework of learning with expert advice has been adapted to online MDP to address non-stationarity. Previous RL approaches rely on sliding windows or restarts, which require prior knowledge of the variation budget. The first method to overcome this issue [44] does not handle adversarial losses, where losses can change arbitrarily at each episode and are unknown to the learner. Introducing the use of experts is novel for both RL and CURL, and can open the way for the development of new algorithms.

- **New analysis and need of dynamic assumption (8):**
    We emphasize that CURL (which is a convex objective) is significantly harder than RL (which is a linear objective). A notable example in the online learning literature is the comparison between convex bandits [Lattimore 2024] and multi-armed bandits [Lattimore and Szepesvari, 2020], where the former are highly more challenging. Early studies on more complex problems may need stronger assumptions to enable the development of new methods for general scenarios. Addressing online CURL needs a new theoretical analysis distinct from RL, even with the dynamics assumption in Equation (8). Existing work on online CURL, like [35], also requires this assumption and is limited to stationary environments.
    
    Our work adds the challenge of non-stationarity. In the meta-algorithm constructed using the experts framework, the complexity of working with CURL is addressed through our novel construction of $\hat{p}^t$, the estimator of the probability transition. This approach differs significantly from classic RL methods [Neu et al. 2012] and necessitates a new analysis (see Proposition 5.2).

- **Real world applications satisfying CURL with dynamic assumption (8):** 
    Our setting encompasses many real-world problems outlined in the paper and further detailed below: 
	- **Energy grid optimization.** To balance the energy production with the consumption, an energy provider may want to control the average consumption of electrical appliances (electric vehicles, water heaters, etc), with known physical dynamics but unpredictable and varying consumer behavior. This is a central problem in the context of climate change to introduce renewable energies into the electrical grid. The application paper Moreno et. al 2023 exactly fits into our CURL framework (see Eq. (1) of Moreno et al. 2023). Other related works are [41, Coffman et. al 2023]. 
	- **Robotics.** Controlling a population of drones often involves environments with non-stationary dynamics, such as changing weather conditions and human interventions. One objective might be to reach a certain target while avoiding specific states. This can be formulated as the following convex objective:
       $$F(\mu) := -\langle r, \mu \rangle + (\langle \mu, c \rangle)^2$$
	where $r$ is a reward vector and $c$ is a cost vector. Alternatively, the objective might be to distribute 	the drones uniformly throughout the space, which can be expressed using the entropy function: 
	$$F(\mu) := \langle \mu, \log(\mu) \rangle.$$

	- **Inventory management.** Online resource allocation, where user demand is the unknown external noise independent of stock levels [Lee et al. 2023];

	- **Finance.** Trading tasks, assuming market independence from the trajectory of a single agent [Riva et. al 2022]; among others. 

Since the external noise distribution and the cost function are unknown, we must still simultaneously learn the model and optimize the policy, which keeps us within the realm of reinforcement learning. These points provide enough motivation for addressing this setting, even though exploration is unnecessary.

### References
- *Lattimore 2024, Bandit Convex Optimisation*
- *Lattimore and Szepesvari 2020, Bandit algorithms*
- *Neu et. al 2012, The adversarial stochastic shortest path problem with unknown transition probabilities, AISTATS*
- *Moreno et. al 2023, (Online) Convex Optimization for Demand-Side Management: Application to Thermostatically Controlled Loads*
- *Coffman et. al 2023, A unified framework for coordination of thermostatically controlled loads, Automatica*
- *Lee et al. 2023, Online Resource Allocation in Episodic Markov Decision Processes*
- *Riva et al. 2022, Addressing Non-Stationarity in FX Trading with Online Model Selection of Offline RL Experts, ICAIF*

Meta-review: 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.
Decision: Accept (poster)