Online Episodic Convex Reinforcement Learning

We thank the reviewer for their long and detailed review. We address below the raised concerns.

• References:

  • Rosenberg and Mansour (2019): Their setting differs from ours; in fact, our setting generalizes theirs. In our notation, they consider a sequence of adversarial losses $(\ell^t)_t$ with $\ell^t : \mathcal{X} \times \mathcal{A} \to \mathbb{R}$, where the learner's loss is given by $F(\langle \mu, \ell^t \rangle)$. Here, $F$ is a fixed and known beforehand convex function, $\mu$ is the state-action distribution, and $\langle \mu, \ell^t \rangle$ is the expected loss. In contrast, our online convex RL setting is a generalization, as it does not assume linearity in the distribution within $F$, and the convex function itself is adversarial, meaning that the learner's loss in episode $t$ is given by $F^t(\mu)$. Thus, we introduce a method that achieves the same $\sqrt{T}$ regret bound as Rosenberg and Mansour, but in a more general setting.

  • Jin et al. (2020): This work does not use exploration bonuses. Their approach is model-optimistic: in each episode, they solve an OMD iteration over the set of all MDPs induced by a probability kernel within the confidence set around the estimate $\hat{p}^t$. This is their exploration mechanism. In contrast, our method solves an instance of OMD over a single MDP in each episode, the one induced by the estimate $\hat{p}^t$. This is crucial for obtaining a closed-form solution, but eliminates the exploration mechanism in Jin et al (2020). As shown in Section 3, without an exploration mechanism, this approach would fail to achieve low regret. To address this while maintaining a closed-form solution, we add an exploration bonus to the sub-gradient in each OMD iteration, a step not taken by Jin et al. (2020), requiring a new type of analysis.

  • Neu et al (2012/2013): These two works do not use bandit convex optimization (BCO) approaches. They adopt online convex optimization methods to solve RL problems with a standard linear objective (sum of rewards). The same applies for many subsequent works such as Jin et al. (2020). Some of these works address bandit feedback, but it is not appropriate to place them in the BCO category as they only consider linear losses. Instead, BCO refers to online problems with bandit feedback and more general families of convex loss functions (such as the family of convex Lipschitz functions we consider).

• Motivation: We list some motivation applications below that we will add to the final version of the paper.

  • 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) to better match a target consumption. The task involves daily control, with the target consumption varying daily due to fluctuations in energy production. To protect user privacy, the energy provider has limited access to individual trajectories, but receives the average consumption of the whole population at the end of each day. The loss is usually quadratic on the state-action distribution. This problem can be framed as our CURL formulation. See Coffman et al. 2023, or Moreno et al. 2024.

  • Mean-field games (MFG) with potential reward: As shown by Geist et al. (2022), a MFG with potential reward can be framed as a CURL problem. Therefore, any sequential decision problem with a large population of anonymous agents with symmetric interests and potential rewards, such as epidemic spreading, crowd motion control, etc, can be cast as CURL.

• Questions:

  • Computational complexity: See question 1 of reviewer vsjZ.

  • Self-concordant regularization with unknown MDP: A main challenge in adapting the approach of Alg. 4 to the unknown MDP case is that the adoption of the log barrier regularizer introduces some technical difficulties in the analysis of OMD with changing decision sets. Hence, at the moment, the only workaround we see is the adoption of a (generally less efficient) model-optimistic approach to handle the uncertainty regarding the transition kernel.

  • Improved regret bound for bandit CURL: Please see our response to Reviewer 5Sqt regarding bandit feedback.

  • In our practical experiments, we observed that the key factor in the bonus vector is its inverse proportionality to $N_n^t(x, a)$. However, we did not compare the performance of different decay rates other than the one discussed in Section 3.

  • Other experiments: We also applied our algorithm to the pure exploration task within the same grid world environment, whose goal is to maximize the entropy. Since this objective inherently drives exploration, we found that adding a bonus had no impact on performance in this case.

Coffman et al. 2023, A unified framework for coordination of thermostatically controlled loads, Automatica

We thank the reviewer for their time and comments. We address the raised concerns below.

• Claims (papers): We discuss Zahavy et al. (2021) as an offline approach, as they consider a fixed and known loss function aiming to minimize the optimization error (see their Eq. 5). In the final version, we will expand the discussion over works on trajectory-based CURL, see also Formulation below. The work of Moreno et al. (2024) is extensively discussed in the paper.

• Claims (near-optimality): We use the term near-optimal to refer to optimality with respect to $T$. In the final version, we will add a clarification. For the $\sqrt{|\mathcal{X}|}$ term, our intention was to point that it is a consequence of our CURL approach, this too will be clarified.

• References: Thank you for pointing out the works on submodular RL. We will add them to our related work, as well as expand on the discussion regarding trajectory-based CURL.

• Formulation: The feedback related to the loss of the learner is indeed independent of the trajectory of the agent. The trajectory-based formulation of Mutti et al. (2023) is an interesting alternative. However, they show that non-Markovian policies can be necessary to optimize this objective, which entails an increased computational burden. On the other hand, the occupancy-measure-based formulation that we study can be solved efficiently, and allows direct comparison with methods from the CURL literature such as Moreno et al. (2024). Moreover, in application scenarios with many homogeneous agents, a mean-field approach can justify this choice. We give a motivating example in our response to reviewer 1pSC.

• New techniques: We emphasize that, although our algorithm is based on the OMD framework proposed by Moreno et al. (2024), we introduce new technical tools that may be useful to the CURL and RL community. To address unknown probability kernels while preserving their closed-form solution, we introduce the exploration bonuses. Although the use of bonuses for exploration in RL is not new, algorithms with closed-form solutions and adversarial losses with bonuses initially achieved only sub-optimal regret in $T$ (Efroni et al. 2020). Luo et al. (2021) addressed this limitation by constructing a dilated bonus equation satisfying a dilated Bellman equation. However, this technique is not applicable to CURL, as its objective is convex, not linear over the distribution. To overcome this, we develop a novel additive exploration bonus which offers a new solution to this challenge. As demonstrated, this also achieves optimal regret in $T$ for bandit RL through a mechanism and analysis distinct from prior methods. In addition, we address, for the first time, bandit feedback in CURL for general convex Lipschitz functions.

• Questions:

  • 1. In the full-feedback setting, the bandit RL setting, and the first approach in the bandit CURL setting, the algorithm has a closed-form solution for the policy. In each episode, it performs $O(N \times |\mathcal{X}| \times |\mathcal{A}|)$ operations to compute the policy. Whereas for the second approach in the last setting, computing the policy at every step requires solving a convex program.

  • 2. The algorithm of Hazan et al. is designed for a different objective than ours. Firstly, they focus on entropy maximization, while we deal with the CURL problem for any convex function. Secondly, our algorithm is made for an online episodic environment with adversarial losses, while their method works only with a fixed reward function, and they do not prove regret bounds. Finally, they assume access to an approximate planning oracle and a state distribution estimation oracle, which eliminates the need for an explicit exploration tool, unlike our approach, where the bonus plays an essential role in guaranteeing sufficient exploration.

       An idea to take home for practice is that OMD in the space of occupancy-measures handles adversarial losses and, with a well-designed bonus, ensures sufficient exploration while still enjoying a closed-form solution.

  • 3. One example of stochastic losses is when $F_t(\mu) = (\mu - \gamma_t)^2$ where $\gamma_t$ is sampled i.i.d. from some distribution. In our case, we consider adversarial losses, meaning we make no statistical assumptions about the loss sequence, which can follow any pattern.
  • 4. Yes. Since our bandit CURL approaches achieve a regret of $T^{3/4}$, we demonstrate that when $F$ is linear, the problem is simpler, allowing us to achieve a regret of $\sqrt{T}$. Another point is to show a novel approach to adversarial online RL that matches the existing bounds, while introducing a new algorithm based on different tools and analysis that could be of interest to the community.
  • 5. The policy $\pi$ is the comparator strategy in the regret (see Eq.(5)).
  • 6. We agree with the reviewer and leave this question for future work (see also answer to Question 1 of reviewer 5Sqt).

We thank the reviewer for their time and comments. We address the raised concerns below.

• Regret: In our experiments, we compare our approach with the oracle optimal policy, which can be well approximated when the dynamics are fully known. We will specify it in the final version of the paper.

• Failure of Moreno et al. (2024): To succeed in the constrained MDP task of Figure 3, the agent must explore sufficiently to arrive at the rewarding final state. However, without an explicit exploration incentive, the agent remains static to avoid the constraints that induce negative rewards. Since Greedy-MD-CURL does not have an explicit exploration mechanism, it fails to converge within 1000 iterations. Could the reviewer clarify why they believe Greedy-MD-CURL would not fail in this scenario?

• Assumption for sub-linearity: In the full-information case, and the bandit RL case, the two assumptions needed for sub-linear regret are convexity and Lipschitzness of the objective function, which are both stated in the introduction and the setting. For bandit feedback in the CURL setting, in addition to these two hypothesis, we state in the introduction (page 2, line 84-86, column 1) that one of the presented algorithms requires the MDP to be known and that the other requires an assumption on the structure of the MDP, which is then precisely detailed and motivated in Section 4.2.1. In the final version, we will add more details in the introduction.

• Questions:

  • Assumptions Alg. 4: Yes, we assume the MDP is known for this algorithm. We mention this assumption in the introduction (page 2, lines 84-85, column 1) and before the first reference to the algorithm (page 7, lines 370-371, column 2). Additionally, the first input argument in the definition of the algorithm is the set of occupancy measures under the true MDP.
  • Definition of $\xi$: $\xi_n^t(x,a) := \|p_n(\cdot|x,a) - \hat{p}^t_n(\cdot|x,a) \|_1$. We define it in the paragraph before Eq.(9) (see page 4, line 218, column 2).
  • Fig.2: The regret plot represents the cumulative loss over time against the loss of the optimal policy. The loss plot indicates that Greedy-MD-CURL (Moreno et al. 2024) does not converge to the minimum value, justifying why the regret increases linearly. Note that the loss plot is in loglog scale while the regret plot is not.

• Comments: Could the reviewer specify which parts of the paper could benefit from reformatting? We would appreciate more detailed feedback to improve the paper's presentation. Regarding the exploration bonuses, we would like to emphasize that the entire analysis in Section 3, which introduces an additive bonus in mirror descent, is an original contribution, see also New techniques in our response to Reviewer vsjZ. Additionally, we will include a conclusion section and comment more on the experimental results.

We thank the reviewer for their time and comments. We address the raised concerns below.

• Tabular RL: We agree with the reviewer that both the linear MDP case and the case with function approximation are interesting directions for future work. However, since the adversarial convex reinforcement learning setting with an unknown probability kernel had not been addressed even in the tabular case, we believe that developing a foundational algorithm like ours is a necessary step towards adapting to these more general scenarios in the future.

• Bandit feedback: The adversarial convex RL setting is not equivalent to adversarial MDPs with the standard (linear) RL objective. Under bandit feedback, we indeed show that in the latter setting (standard linear RL), our method achieves $\sqrt{T}$ regret (see Thm. 4.1). On the other hand, addressing bandit feedback in convex RL is a more challenging problem, please refer to the second paragraph in Section 4.2 (page 6, line 285, column 2). In short, the adoption of general convex objectives places this problem in the more challenging Bandit Convex Optimization (BCO) field, as opposed to bandit (or semi-bandit) linear optimization, where one can generally categorize standard RL problems with bandit feedback.

  As we discuss in the beginning of Subsection 4.2.1, achieving $\sqrt{T}$ regret (still an active research area) has been shown to be possible in plain BCO problems with Lipschitz objectives via significantly involved algorithmic techniques and analyses (Hazan and Li, 2016; Bubeck et al., 2021; Fokkema et al., 2024). On the contrary, we adopt more common and foundational techniques (building upon works such as Flaxman et al., 2005 and Saha and Tewari, 2011) that though only capable of achieving $T^{3/4}$ regret in our setting (Hu et al., 2016), are arguably more practical, less complicated, and enjoy better dimension dependence. This allows us to better isolate the difficulties posed by the specific structure of this new problem (BCO in MDPs) as we discuss in much detail throughout Section 4.2. Finally, we note that when the dynamics of the MDP are not known (as is the case in Subsection 4.2.1), a new and significant difficulty is added to the BCO formulation of the problem (namely, uncertainty over the decision set), hence it is not clear in that case whether $\sqrt{T}$ is still achievable.

• MDP setting: Applying online learning algorithms to the MDP setting is challenging and demands the development of new tools. Numerous studies in the literature have focused on adapting online learning methods (such as FTRL, or OMD) to MDPs within the reinforcement learning framework, ranging from early works addressing the basic case with known transition dynamics (Even-Dar et al., 2009; Neu et al., 2010) to more recent approaches handling unknown transitions (see references in Section 2). In our paper, dealing with adversarial convex RL is not a straightforward application of OMD because of the need for exploration (which we handle with our bonuses technique), the changing decision sets (due to uncertainty over the transition kernel), and the bandit feedback.

• Question: As outlined in Section 3, Eq.(8), the analysis of the regret can be divided into two main components: one concerning the quality of the MDP estimation under the executed policy, $R_T^{\text{MDP}}$, and the other related to the online algorithm that computes the executed policy, $R_T^{\text{policy}}$. Indeed, the term related to the online algorithm could be improved by assuming curvature in the loss function, but it is unclear if the term related to estimating the MDP can be improved because it is not strongly tied to the structure of the loss function.

Neu et al., 2010, Online Markov decision processes under bandit feedback, NeurIPS