We thank the reviewer for their insightful comments. Below, we address the main concerns:

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

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

  Indeed, 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).

  Finally, 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.

• 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:

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

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

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

• 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).

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

  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.

• Additional references: Thank you for pointing out these interesting new references. We will add them to our related work.

References:

• Neu et. al 2012, The adversarial stochastic shortest path problem with unknown transition probabilities, AISTATS
• Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS
• Efroni et al. 2020a, Optimistic Policy Optimization with Bandit Feedback, ICML
• Efroni et al. 2020b, Exploration-Exploitation in Constrained MDPs
• Agarwal et. al 2016, Corralling a Band of Bandit Algorithms
• Jin et al. 2020, Learning Adversarial MDPs with Bandit Feedback and Unknown Transition, ICML

We thank the reviewer for their comments and for recognizing the new theoretical insights in our paper. We address the questions below:

• 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:

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

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

• 2. Transition dynamics: We address this concern in our general response to all reviewers as well. We open on some details below:

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

    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.

    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.

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

References:

• Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS 2021

Motivational examples:

We agree with the suggestion to provide examples to motivate our setting. We will include these examples in the introduction on the extended version.

Questions about the setting:

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

• 2. No, there are no restrictions on the occupancy measure.

No inconsistent notations:

There is no inconsistency in our notations and we respectfully disagree with the reviewer on this point. We address all the specific concerns below:

• 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]$.

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

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

• 5. round $t$: Round $t$ is the same as episode $t$.

• 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].

Questions about MetaCURL

• 1. and 2. We do not fully understand the question. Could you please provide more details?

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

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

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

• 6.

  • 6.1 The 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^*}$.

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

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

  • 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].

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

References:

• Perrin et. al 2020, Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications, NeurIPS 2020

Still, from my perspective, a theoretical paper should only be accepted at NeurIPS if it clearly demonstrates its motivation, and its assumptions are valid in practice (as mentioned by Reviewer unHu, Reviewer FWrb, Reviewer La9P, Reviewer ZTXg); and the whole RL community can benefit from its insights.

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

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

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

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

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

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

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

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

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

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

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

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

I strongly recommend that the authors directly test their framework on such benchmarks, instead of merely discussing it. This claim remains questionable.

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.

Questions

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

• 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).

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

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

  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.

  For a more detailed discussion on both approaches we refer to the works of [Luo et al. 2021, Efroni et al. 2020a,b].

• How the algorithm changes with $g\_n$ unknown:

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

Comments for improving the paper:

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

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

Regarding 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:

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

References:

• Luo et al. 2021, Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses, NeurIPS 2021
• Efroni et al. 2020a, Optimistic Policy Optimization with Bandit Feedback, ICML 2020
• Efroni et al. 2020b, Exploration-Exploitation in Constrained MDPs

I thank the authors for their replies. I went over them and do not have any further questions. Please include the changes as promised in your revised version, particularly regarding the dynamics assumption and improving readability.

We thank the reviewer for their comments and for recognizing the new theoretical insights in our paper. We address the questions below:

• 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:

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

• 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?

Questions

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

• 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^{\*}}$.

• 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].

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

• Related work: We greatly appreciate the reviewer for pointing us to these related works. We will include them in our citations.

References:

• Neu et al. 2010, Online Markov Decision Processes under Bandit Feedback, NeurIPS
• Neu et al. 2012, The adversarial stochastic shortest path problem with unknown transition probabilities, AISTATS
• Zimin et al. 2013, Online Learning in Episodic Markovian Decision Processes by Relative Entropy Policy Search, NeurIPS
• Rosenberg et al. 2019, Online Convex Optimization in Adversarial Markov Decision Processes, ICML
• Jin et al. 2020, Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition, ICML
• Efroni et al. 2020, Optimistic Policy Optimization with Bandit Feedback, ICML
• Moreno et al. 2024, Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent, AISTATS

Thank you for the update.

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

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

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