Online Episodic Convex Reinforcement Learning
Authors: Bianca Marin Moreno
Khaled Eldowa
Pierre Gaillard
Margaux Brégère
Nadia Oudjane
Venue: ICML 2025 poster (2025)
Keywords: Online learning
convex reinforcement learning
markov decision processes
bandits
Primary area: theory->online_learning_and_bandits

Abstract: We study online learning in episodic finite-horizon Markov decision processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. This setting generalizes RL from linear to convex losses on the state-action distribution induced by the agent’s policy. The non-linearity of CURL invalidates classical Bellman equations and requires new algorithmic approaches. We introduce the first algorithm achieving near-optimal regret bounds for online CURL without any prior knowledge on the transition function. To achieve this, we use a novel online mirror descent algorithm with variable constraint sets and a carefully designed exploration bonus. We then address for the first time a bandit version of CURL, where the only feedback is the value of the objective function on the state-action distribution induced by the agent's policy. We achieve a sub-linear regret bound for this more challenging problem by adapting techniques from bandit convex optimization to the MDP setting.

Online Episodic Convex Reinforcement Learning
Bianca Marin Moreno 123 Khaled Eldowa 445
Pierre Gaillard Margaux Brégère 26 Nadia Oudjane
Abstract
sequence of probability transition kernels p p= (Pn) (Pn))et[N) [e[] such that for each (z, a) X x A, (-(-, a) Axx the sim- plex over the state space. Formally, the RL problem involves finding policy π that, under a transition kernel induces a state-action distribution sequence j=' E (Axxx.) mini- mizing the inner product with a loss vector := (en)NE(N) with En E R*xAA, i.e.: m)) (f, ,C=P). A large body of literature is devoted to solving the RL problem effi- ciently and with theoretical guarantees in many challenging environments (Bertsekas, 2019; Sutton & Barto, 2018).
We study online learning in episodic finite- horizon Markov decision processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. This setting generalizes RL from linear to convex losses on the state-action distribution induced by the agent's policy. The non-linearity of CURL invalidates classical Bellman equations and re- quires new algorithmic approaches. We introduce the first algorithm achieving near-optimal regret bounds for online CURL without any prior knowl- edge the transition function. To achieve this, we use online mirror descent algorithm with varying constraint sets and a carefully designed exploration bonus. We then address for the first time a bandit version of CURL, where the only feedback is the value of the objective function on the state-action distribution induced by the agent's s policy. We achieve sub-linear regret bound for this more challenging problem by adapting tech- niques from bandit convex optimization to the MDP setting.
However, numerous practical problems entail more intricate objectives, such as those encountered within the Concave Utility Reinforcement Learning (CURL) framework (Hazan et al., 2019; Zahavy et al., 2021) (also known as convex RL). The CURL problem consists in minimizing a convex function (or maximizing a concave function) on the state- action distributions induced by an agent's policy:
min F(47.)).
(1)
In addition to RL, other examples of machine learning problems that can be written as CURL are pure explo- ration (Hazan et al., 2019; Mutti et al., 2021; 2022b), where F(IT*P) <n=TP, log(1==))) imitation learning (Ghasemipour et al., 2020; Lavington et al., 2022) and apprenticeship learning (Zahavy et al., 2019; Abbeel & Ng. 2004), where F(u* = D,(1 ,,**,, with D, rep- resenting a Bregman divergence induced by a function and μ being a behavior to be imitated; certain instances of mean-field control (Bensoussan et al., 2013), where F(u*P) = (E(H=""") "<T mean-field games with poten- tial rewards (Lavigne & Pfeiffer, 2023); risk-averse RL. (Gareıa & Fernández, 2015; Pan et al., 2019; Greenberg et al., 2022), among others. The non-linearity of CURL al- ters the additive structure inherent in standard RL, invalidat- ing the classical Bellman equations. Consequently, dynamic programming approaches become infeasible, necessitating the development of novel methodologies.
1. Introduction
Reinforcement learning (RL) studies the problem where an agent interacts with an environment over time, adhering to a prohabilistic policy that maps states to actions and aiming to minimize the cumulative expected losses. The environ- ment's dynamics are represented by Markov decision pro- cess (MDP), assumed here to be episodic, with episodes of length N, finite state space X,, finite action space A, and
"Equal contribution Unniv. Grenoble Alpes, Inria, CNRS, Grenoble INP, IJK, 38000 Grenoble, France. 'EDF Lab, bd Gaspard Monge, 91120 Palaiscau, France 'FiME (Laboratoire de Finance des Marchés de l'Energie- Dauphine, CREST. EDF R&D) "Università degli Studi di Milano, Milan, Italy 'Politecnico di Milano, Milan, Italy SSobonne Université LPSM. Paris, France. Correspondence to: Bianca Marin Moreno <bianca.mar marin- moreno@inria.fr>.
A natural extension of CURL the online scenario, wherein sequence of policies (T') is computed over T episodes, aimed at minimizing a cumulative loss Lr := F' where the objective F* can change arbi- trarily (known as the adversarial scenario (Even-Dar et al., 2009)), and the MDP probability kernel p is unknown. Most existing approaches to CURL fail to address the challenges
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Episodic Convex Reinforcement Learning
of the online setting (adversarial losses and unknown dynam- ics). The few methods that attempt to tackle this problem rely on strong assumptions about the probability transition kernel (Moreno et al., 2024), which can be overly restric- tive in real-world scenarios. To overcome this, we need an approach capable of optimizing the objective function while simultaneously learning the environment, effectively balancing the exploration-exploottiion dilemma.
induced by the agent's policy, i.e., F'(n" P). We propose two algorithms for this setting and show that they achieve sub-linear regret. One algorithm requires that the MDP is known, while the other, under the assumption that the probability transition kernel is lower bounded by a positive constant, operates in the setting where the MDP is esti- mated progressively from observed trajectories. We rely on gradient estimation techniques from the bandit convex optimization literature, even as the peculiar structure of our constraint set and uncertainty regarding the true transition kernel present some unique challenges.
Motivations. The CURL framework presented in this paper is motivated by variety of application scenarios, some of which we outline below. Energy grid optimization: To bal- ance 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 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 usu- ally quadratic on the state-action distribution. This problem can be framed as our CURL formulation. See (Coffman al., 2023; Moreno et al., 2025). Mean-field games (MFG) with potential reward: As shown by (Barakat et al., 2023), a MFG with potential reward can be framed as 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.
1.1. Related Work
Offline CURL. An extensive line of work focus on the of- fline version of CURL (Problem (1)), where the objective function is known and fixed. The methodologies proposed by (Zhang et al., 2020; 2021; Barakat et al., 2023) rely on policy gradient techniques, requiring the estimation of F's gradient concerning the policy т, a task often complex. Taking different approach, Zahavy et al. (2021) cast the CURL problem as min-max max game using Fenchel dual- ity, demonstrating that conventional RL algorithms can be tailored to fit the CURL framework. Recently, Geist et al. (2022) established that CURL is a specific instance of mean- field games. Moreover, Moreno et al. (2024) undertake a convexification of Problem (1) and propose a mirror de- scent algorithm with non-standard Bregman divergence. Mutti et al. (2022a; 2023) study the gap between evaluating agent performance over infinite realizations versus finite trials and question the classic CURL formulation in Eq. (1), However, they show that non-Markovian policies can be necessary to optimize the finite trials objective, which en- tails an increased computational burden. On the other hand, the occupancy-meant beasur-bbeed 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 ho- mogeneous agents, a mean-field approach can justify this choice, as we discuss in Sec. 1.
Contribution 1. In the full-information feedback setting, where the objective function Fe is fully revealed to the learner at the end of episode f, we propose the first method achieving sub-linear regret for online CURL with adversar- ial losses and unknown transition kernels, without relying on additional model assumptions. Our algorithm uses an Online Mirror Descent (OMD) variant incorporating well- designed exploration bonuses into the sub-grat gradient of the objective function to handle the exploration-explotaaiee trade-off. It achieves a regret of Ö(VT), matching the state- of-the-art (SoTA) in more restricted settings (Moreno et al., 2024), while obtaining a closed-fon form solution.
Online CURL. To the best of our knowledge, Greedy MD- CURL from (Moreno al., 2024) is the only regret min- imization algorithm designed for online CURL. However, it only achieves sublinear regret when the system dynam- ics follow the form In+1 = [n an, En), where In is a known deterministic function, and En is an external noise with an unknown distribution independent of (z,,, a,)), which significantly limits its applicability, as we empirically show in Sec. 5. This assumption simplifies the problem, as the algorithm only needs to learn the noise distribution, which can be done independently of the policy, eliminating the need for exploration. In contrast, our approach does not assume any specific form for the dynamics, which intro- duces the challenge of developing a policy that minimizes
We extend our approach to incorporate bandit feedback on the objective function. We first consider the RL case where F' == (E', p)) Bandit feedback in this setting means that the agent only observes the loss func- tion in the state-action pairs they visit during each episode, i.e. (et, (1/ df)))=[[N) where (xi, mejN is the agent's trajectory. We obtain the optimal regret of Ö(VT) in this setting. We then address for the first time the general CURL problem under more strict bandit feedback. In this setting, the learner only has access to the value of the objective function evaluated on the state-action distribution sequence
Contribution 2.
2

---

Online Episodic Convex Reinforcement Learning
Table Comparisons of SoTA finite-horizon tabular MDPs methads. MD stands for Mirror Descent, KI. for Kullback- Leihler divergence and I'is is defined in Eq. (4). MD+ + (.) indicates the regularization added to the MD iteration. MD indicates a policy optimization
approach in which MD iterations are performed on policies instead of state- action distributions (occupancy measures).
Optimal regret in T
Closed- form
Explo-
No model
Adversarial Losses
Bandit
Algorithm
CURL
ration
assumption
feedback
(Jin et al., 2020) (Moreno al., 2024)
MD KL.
X
x
UCRL
MD r
/
V
V
None
X
4
X
(ours)
MD +1 r
/
V
V
Bonus
/
(Luo et al., 2021)
MD on
V
X
V
Bonus
/
total loss while simultaneously enabling sufficient explo- ration to improve estimates of the transition kernels. The technical novelty we introduce to overcome this challenge are well-designed exploration bonuses detailed in Sec. 3.
is more computationally efficient than model-optimistic ap- proaches and addresses the exploration issues in previous online CURL methods. We believe our analysis is of in- dependent interest, as it also offers new way to study RI approaches over occupancy measures, while providing closed-form solutions. See Table for comparisons.
The work of (Rosenberg & Mansour, 2019b) also studies convex performance criteria in adversarial MDPs, but under different setup. They use fixed, known convex functions applied to linear losses, i.e., F((u, ())) In contrast, our setting generalizes this by allowing the convex function F itself to be adversarial and applied directly to the occupancy measure, i.c., (u)).
2. Problem Formulation
2.1. Setting
For a finite set S, |S] represents its cardinality, while As denotes the |S]-dimensional simplex. For all d E N we denote [d] = (1.....d]. We let || 1I be the L1 norm, and for all :: (Un)ne[N]- such that on E R x we de- fine 20,,,, == supisngN ||u, We denote by |- |I,, its dual. Let II == [A4)=xN denote the set of policies. We consider an episodic MDP as introduced in Sec. 1. We assume that the initial state atatenaction pair of an agent is sam- pled from a fixed distribution po E x at the beginning of cach episode. At time step n [N], the agent moves to a state In ~ Pr--1 an-1), and chooses an action On (-,(11x,,, by means of a policy T, : X' A When the agent follows policy æ (#n)ne[N]] for an episode in environment described by the MDP with transition kernel p, this induces a state-action distribution, which we denote by == := (p Iee[N) that can be calculated re- cursively for all (n, a) [N] x X x A, by
RL approaches. Model-optimise methods construct a set of plausible MDPs by forming confidence bounds around the empirical transition kernels, then select the policy that maximizes the expected reward in the best feasible MDP. A key example of this approach is UCRL (Upper Confidence RL. methods (Jaksch et al., 2008; Zimin & Neu, 2013; Rosenberg & Mansour, 2019b; Jin et al., 2020). While these methods offer strong theoretical guarantees, they are often difficult to implement due to the complexity of optimizing over all plausible MDPs. While believe these approaches could be generalized to CURL, their computational com- plexity has led us to propose an alternative method. Value- optimistic methods are value-based approaches that compute optimistic value functions, rather than optimistic models, using dynamic programming. An example UCB-VI VI (Azar al., 2017). However, these methods are limited to stochas- tie losses. Policy-optimizatton (PO) methods directly op- timize the policy and are widely used in RL due to their faster performance and closed-form solutions. Recently, Luo et al. (2021) achieved SoTA regret for PO methods with adversarial losses and bandit feedback by introducing dilated bonuses, which satisfy dilated Bellman equation and are added to the Q-function. However, their approach cannot be applied here due to CURL's non-linearity (the expectation of the trajectory appears inside the objective function) which invalidates the Bellman's 's equations.
TZ, a) = (o(z,a)
1 (x, a)= Σ (x', a (')an' ad)) (2) (a',a')
We define the set of all state-action distribution sequences satisfying the dynamics of the MDP
Mr = (MEXAXX)) Σ (n(''aa')
(3)
a'EA
Σ pa(="(2,a)nn Val e Vn IM] xEX
We achieve our results by computing local bonuses and adding them to the juudienradient of the objective func- tion in each OMD instance as exploration bonuses. This
For any E M there is a strategy & such that -= = μ. It suffices to take n, (a a) when the normal-
3

---

Online Episodic Convex Reinforcement Learning
ization factor is non-zero, and arbitrarily defined other- wise. Let MP* be the subset of Mi where the cor- responding policies satisfy (a]ax) 0 for all (æt, a). For any two probability transition kernels p. 9. we define : MM x M2** - IR such that, for all u. E MP x de Mg with policies n. n',
mizes over the state-action distributions induced by the esti- mated MDP as if it was the true model. This approach dif- fers from the model-optimistic methods for RL discussed in Sec. 1.1 where each iteration is performed over the union of all state-action distribution sets induced by MDPs within a confidence set around the estimated model, which results in computationally expensive optimization problem per itera- tion. Lemma 2.1 presents an auxiliary result concerning the quality of the state-action distribution sequence (f²)) [=)) when je is the solution of Eq. (6), an OMD instance on the set of state-action distributions induced by transition kernel g². It extends the upper bound result from (Moreno et al., 2024) for OMD with smoothly varying constraint sets to any sequence of bounded vectors (z") and any sequence of smoothhy varying transitions (q (d))ee
no
I(,, - Σ aaaa)) () log
] T.
Tn (a(aa
(4)
In the online extension of CURL, the objective fune- tion for episode L is denoted F :- Σm_1 Sh. where fa : AxxA - IR is convex and L-Lipschitz with respect to the I. 11 norm (hence Ft is Lp-Lipschitz with respect to the norm Ilo.1 with Lp=- == LN). The objective function Ft is unknown to the learner in the start of episode t. In this paper, we examine three types of objective function feedback: Full-information: In this case, F is fully dis- closed to the learner at the end of episode i, and is treated in Sec. 3.2. Bandit in RL: Here, (1) := (e", ni). and the learner observes the loss function only for the state-action pairs visited, i.c.. (f,, (x/ [e(]. which is covered in Sec. 4.1, Bandit in CURL: In this scenario, the learner only has access to the objective function evaluated on the state- action distribution sequence induced by the agent's 's policy, i.e., F² (nT .P). and is treated in Sec. 4.2.
Lemma 2.1. Let (d')=e(T) be a sequence of probability transition kernels and (z* )EETTY sequence of vectors in XI such that max4e[1]] |2$111,00 & <. Initialize -
Th = 1/| Fort E [T], let मt := T +' F+T I be smoothed version of the policy and compute iteratively
1+ aarg min ( Pb) .)) + I' pEM
argmin
(6)
Then, there is a T >> such that, for any sequence (v") (e)))) with v² == vmnn for a common policy n,
The learner's ' goal is to compute a sequence of strategies (r')ee[T). where T represents the total number of episodes, that minimizes their total loss LT := VIT F²t F' :P). The learner's 's performance is evaluated by comparing to any policy क E (AA) ) using the static regret:
E (2 (2,, ,1, v²> & O(SN Vy (oNN///////
where Vr 2 14 max (n,2,a)
11,(), - gh (-|2r, a)ll
Rr(() : EJ I E F' -F'(ATP).
(5)
This lemma is proved in App. C. It is known (Moreno et al., 2024) that for the divergence I defined in Eq. (4), Eq. (6) has a closed-form solution for the policy (see App. A.2).
We assume the probability transition kernel p is unknown to the learner. Hence, to minimize its total loss, the learner must optimize the objective function while simultaneously learn the environment dynamics, facing exploration- exploitation dilemma. The interaction between the learner and the environment proceeds in episodes. At each episode t, the learner selects a policy ,F. sends it to the agent, and observes its trajectory of := (z). .g.... xyy, a.y). The learner uses this observation to compute an estimation of the probability transition kernel g At the end of episode the learner receives one of the three feedbacks described above for the objective function F², and then calculates the policy for the next episode, -+1,, based on n², 1 1 and the feedback on Ft.
Learning the model. Since the learner does not know the probability transition kernel, it must estimate p from the agents' trajectories. Below we present the empirical way for estimating the transition and a well-known re- sult (Lem. 2.2) on its quality using Hoeffding's 's inequal- ity. Let (2 - 1 (x;=0,00; Σ=1 (x;_,)=- - -z,at, -a3- The learner's estimate for the transition kernel at the end of episode t 1, to be used in episode ł, is as follows
M,, (2'[ar, [z,
Pr (2 1I, (x,a)== = (2
Lemma 2.2 (Lem. 17 of Jaksch et al., 2008). For any
2.2. Preliminary Results
0 8 < 1, with a probability of at least 5.
The results in this section are either known or extensions of existing results needed for the analysis.
2| log
X
- (1, &
5
max (1, (1,NL N (x. R)}
Since the probability transition kernel is unknown, we pro- pose an online mirror descent (OMD) instance that opti-
holds simultaneously for all (t, n, N, a) E x [N]xxX]XX'X
4

---

Online Episodic Convex Reinforcement Learning
These results suffice for analyzing CURL with full- information feedback (Sec. 3). For bandit feedback, more refined tools are needed. In bandit RL, we need Bernstein's inequality to bound the L1 distance (Lem. D.2). In bandit CURI, we also need bound on the Kullhack-Leibler (KI.) divergence (Lem. E.3), which requires the Laplace (add- one) estimator (Eqq. (51)), as the KL of the empirical one can be unbounded.
exploration. We decompose this regret term follows:
T
Hpplicy Rt
(
(n"
1 v 12 2..00)
T
V VF (p" 51 2 -00000
3. Exploration Bonus in CURL
Ryy
Assume the learner computes its policy sequence (T* (T'))=[1 by solving Eq. (6) with q++1 = pr+ and x' = VF )²). Hence, from Lem. 2.1, 187 HPpllcyyM Ō (T (Lemmas A.3 and A.4 in the Appendix demonstrate that Σ (' a) f0(,1,, a)ll1 & log((T). By hy- pothesis, VF Ø M1, & Lp. Hence, we meet all the assumptions from Lem. 2.1). But the term R RpolicyMD poses a challenge. It can be decomposed as TeyDe in Eq. (9). How- ever, the state-action distribution multiplying E (z, a) would either be μ
We now present our novel approach for online CURL with adversarial losses and unknown dynamics.
3.1. Limitations of previous approaches
The performance measure of a learner playing sequence of strategies (7")<e(T) is given by the static regret defined in Eq. (5). Using the estimate the probability transition kernel p² computed by the learner, the static regret can be further decomposed as follows
7 (xx a) or 1u, 7.8" (x, a), and neither is a). Consequently, we do not have the same convergence effect RMDPP In fact, this term become prohibitively large. Without exploration, previous work us- ing similar analysis (Moreno et al., 2024) only achieved optimal regret under strong model assumptions, limiting its applicability in realistic scenarios.
related (z, (z.
RT(T) = Σ F' F'( -F
+ Σ Fr (1t x' (00) ) -F-(
F (n= th ()) ;), 1 1 xt
(8)
3.2. CURL with full-information feedback
We outline our idea to overcome previous limitations pre- sented in Subsec. 3.1. Let :- (6g))e[]] be a sequence of vectors, to be properly defined later, such that 69, E xxA, We assume that n' is the policy inducing ja computed as in Eq, (6) with o² := p', but instead of considering zf VF (pT" 56 as the (sub-)gradient of MD to be used in episode + 1, we let FF .²) bb, i.e.
T
LVP 10) p -1 ;
where the inequality comes from the convexity of FL, Let St. (z; a) := [pm.(-1r,, a) - P (-12,))))) The term RMDP accounts for the error in estimating the MDP, and satisfies RYDP = Õ(VT) with high probability. This is a classic result (see Neu et al., 2012). We first show that
arg min ( 1 bb) r(u, (1,,")) x²)3. M #+
If we assume that D' is such that, for all t E [T] and for some ( > 0, VF (n='(') B1 & Ç. then by Lem. 2.1 and by adding and subtracting the bonus vector, we would have that Ro is bounded by
N
RMDP &
T.
Σ [=1
Σ
Σ
Σ
x' & p
"x, (z.
(9)
2,0
ppolicyMDP (10) Õ(VT) + ΣT (b', p= 55 - -=--00 + R
Then, using Lem. 2.2 and that (1, a) increases with the empirical version of the state-action distribution 14, "(x, a) we achieve the final bound (see App. B.2). The second term, Reolicy, depends on the algorithm used to derive the poli- cies. As mentioned in Sec. 1.1, model-optimistic approaches could be adapted to CURL, but they are computationally expensive. To achieve low complexity, we explore poten- tial problems that might arise from the absence of explicit
Let Cs /2 ())(NN))))
and for all
n (0, [N]), (I,, a) E X' A. let
(z, = L(N - n)
(1))
v max {1, (4( a))
Note that | & LNCs, ensuring that the hypothesis of Lem. 2.1 remains valid for this sequence. Decomposing
5

---

Online Episodic Convex Reinforcement Learning
RepoliyyDD we do for Re in Eq. (9), and then applying Lem. 2.2, get that for any ōe (0, 1), with probability at least 1 prolecy/DDP bounded by
Algorithm Bonus O-MD-CURL. (Full-information)
1: Input: number of episodes T. initial policy x E II,
5, R
initial state-action distribution p4o, and state-action distri- bution sequence μ¹ = -i²² = p² .6' with P,,()a,,) =
LC3
T N-1
Σ
(N
n)
Σ
19 (x, a)
1/|x|, learning rate T > 0.
max (1, N (x)
2: Init.: V(n, 2, a, x'), N (z, a) = (1(x'
1==0
2,0
(12)
3: for t .,.... T do
T Ku .B.
agent starts at (any, ag)) Ho(-)
5: for .,..., NN do
6: Env. draws new state xn1 Pol Pal-11 11 dn-1)
By replacing Eq. (12) in Eq. (10), the additive prop- erty in the decomposition allows us to cancel out the problematic regret term ReplicyyMD As a result, we ob- tain that Riplicy < O(VT)) + ET (b, mains is analyze the new term due to the added bonus, LI (b', 1et "i) which we do in Prop. 3.1.
7: Update counts
N an- = N Nn-1( a an- +1
" All that re-
M (2" 1- 11-1)) No (a's inn an-1)
Agent chooses an action a² T (-12/h) end for
Proposition 3.1. Let (b)) (TT) be the bonus vector in Eg. (11). For any 8' E (0, 1), with probability 1 - -3',
10: Compute bonus sequence in Eq. (11)
11:
Observe objective function Fed
EL nt き =
12:
Compute n²' . as in Eq. (2)
13:
Update transition estimate as in Eq. (7)
With all the ingredients in place, we introduce our new method, Bonus O-MD-CURI, in Alg. 1. The main result is in Thm. 3.2 and its proof is in App. B.2. In terms of T and [A],, our result matches the optimal one in RL from (Jin et al., 2020), but we have additional factors of N and v|x that are due to using bonuses and to our approach deal with adversarial convex RL.
14:
Compute the n'-1 associated to the solution of Eq. 6
with 2 := VVF " )+ + b' and g 1 3+
Compute #++1 (Lem. 2.1), and jttt1 == 1 g0
15:
16:
end for
We define Alg. 2 in App. D, version of Bonus O-MD- CURL where for each OMD update we take 2' :- Z b², with & an aepprtance-weighree estimator of le defined in Eq. (40) and b' the bonus vector defined in Eq. (11).
Theorem 3.2. Running Alg. 1 for online CURL with un- known transition kernel, full-information feedback, where F': En Sh is convex and each fh is T--Lipschitz under -| It, ensures that, with probability at least 1 -- 66 for any 5 E (0, 1), the optimal choice of 5 achieves, for any x e II,
Thm. 4.1 states that Alg. achieves the regret bound of
Õ(VT) known to be the optimal for RL with bandit feed- back (Jin et al., 2020). For the proof and for an overview of approaches for bandit RL see App. D.
R = Ö(LN*1X10 V
Theorem 4.1. Playing Alg. for RL with adversarial losses (C' (aatt unknown transition kernel, and bandit feedback, obtains with high probability for any policy π E IT,
4. Bandit Feedback
4.1. Bandit feedback with bonus in RL
RT(T) = = VATT + N3/2 X
We generalize Alg. 1 to handle the RL case with bandit feedback. Our aim is not to improve the existing algorithms for bandit RL; rather, we show that our new methodology and analysis for CURL achieves comparable results to the SoTA in bandit RI. In this case, an adversary selects sequence of loss functions (E)) (e() with et := ne))neN)) where P X x A - [0, 1]. and the objective function is given by Fx (*)))) := (C.p)) p) " pn). Note that now the gradient of F" with respect μ is always equal to Ll due to the linearity of the objective function. Bandit feedback in this setting implies that the learner observes the loss function only for the aate-action pairs visited by the agent during each episode, i.c., (2 m())))(()))) where (nrt, ne]] the agent's trajectory.
4.2. CURL with bandit feedback
Returning back to the CURL framework, we now assume that F²: A - [o, N] can be any convex, I-Liipchitz function with respect to 1 In contrast to Sec. 3, we assume here that after executing a policy n² we observe F²t ("( -P) instead of VF*("="7) P). We will consider both the case when the MDP is known in advance and when it needs (as in previous sections) to be estimated progressively from observed trajectories.
Main challenges. This problem can be broadly catego- rized as a bandit convex optimization (BCO) problem. This places us in more challenging domain compared to the
6

---

Online Episodic Convex Reinforcement Learning
bandit feedback setting in the standard RL problem, where the gradient of the loss function is identical for any point in (AxxA)* and is easier to estimate. Moreover, as BCO problem, the present setting still exhibits distinctive challenges. One being the peculiar nature of our decision set Mi and how it impedes the efficacy of some stan- dard gradient estimation techniques as we explain below. Another issue arises when the MDP is not known as that in- duces uncertainty over the true set of permissible occupancy measures. This incomplete knowledge of the decision set is atypical in the BCO literature and introduces multiple sources of bias for any adopted method.
xB- (MPy)) For any v B-
define ÇuiP: Ap(1sT N(X1(11)-1) + KD)). Motivated by the preceding discussion, we use (a simple transformation of)
1- [ - 1)F d) + =5(
as a surrogate for (p*),, where u' is sampled uniformly from S What remains is to address the issue that the true kernel y is unknown. Similarly to the full infor- mation case, we compute an estimate f at each round to be used in place of the true kernel, and we employ bonuses to explore. One difference is that we rely on a slightly altered transition kernel estimator (see App. E.2.2) to ensure that fo too satisfies the condition of Asm. 4.2. Another discrepancy to be accounted for in the analysis is that although we com- pute n' relying on g (in particular, x'' is the policy induced we observe F' .P), the
4.2.1. ENTROPIC REGULARIZATION METHOD
Our first approach is to extend our MD-based algorithm from Sec. 3, supposing still that the MDP is not known. Since the algorithm required knowledge of the gradient VF"( we propose to estimate it by querying F at a random perturbation of 1 -P a standard approach in the convex bandit literature popularized by Flaxman et al. (2005). This method yields 7 regret under con- vex and Lipschitz conditions, and is incapable of doing better (Hu et al., 2016). Although more advanced algo- rithms and analyses achieve VT regret (Hazan & Li, 2016; Bubeck et al., 2021; Fokkema et al., 2024), they are ar- guably less practical, more complicated, and have worse dimension dependence. For d e Z,. we denote by B' and gd the unit ball and sphere respectively in Rd, and by 12 I& the vector with all entries equal to one. Let k: S - IR be a convex function, where S S IRd is a con- vex set satisfying Bd s S. Fix some 8 E (0. 1). The approach of Flaxman et al. (2005) relies on the observation that [1-5]d Buess [&([1 - 5)x + ōu)u] R Vk(z). Hence, (1-5)d k((1 - 8)r + Su)u (for some u uniformly sampled from ( can be used as a one-point stochastic surrogate for the gradient. Applying this idea to our problem presents several challenges. Mainly, MP, has empty interior in NIAIAAI This can be addressed, assuming for the mo- ment that the kernel p known, by defining a bijection Ap: (Mp)) ) ME po where (Mp. s -M) is representation of the constraint set in a diwer-dimensional space where it is possible for its interior to be non-empty, see App. E.1 for more details. Next, we need to specify a (hyper)sphere that is contained in (MM,, which would allow us to use the aforementioned spherical estimation tech- nique while remaining inside the feasible set of occupancy measures. To guarantee the existence of such an object, we rely on the following assumption (discussed further below).
by (1 (11-5) 5)μ² + 8ç" .F' e .M evaluation of n² in the true environment. This induces an extra source of bias in the gradient estimator. We summa- rize our approach in Alg. in App. E.2.3, and prove the following result in App. E.2.5:
Theorem 4.3. Under Asm. 4.2, Alg. 3 with a suitable tuning of T, 6, and (ax)t(T) satisfies for any policy E II that
E [ = = (0LLL11//((7") ****)
The main shortcoming of this method is its reliance on the restrictive Asm. 4.2, which also affects the regret guarantee through its dependence on E. This assumption is not neces- sary to guarantee that (Mp..) ) has a non-empty interior; it suffices instead to assume that every state is reachable at ev- ery step, as we do later. Enforcing Asm. 4.2 only serves as a simple way enable the construction of a sampling sphere with certain radius. One can construct a different sampling sphere (or ellipsoid) without this assumption; nevertheless, the magnitude of the gradient estimator (which is featured in the current regret bound) would still scale with the re- ciprocal of the radius of that sphere, the permissible values for which depend on the structure of the MDP and can be arbitrarily small. It seems then that the current approach leads to inevitable degradation of the bound subject to the structure of the MDP.
4.2.2. SELF-CONCORDANT REGULARIZATION METHOD
Fortunately, we can adopt a more principled approach via the use of self-concordant regularization, which is a com- mon technique in bandit convex (and linear) optimization (see, e.g., Abernethy et al., 2008; Saha & Tewari, 201 I; Hazan & Levy, 2014), and has been used for online learn- ing in MDPs in different (linear) settings (Lee et al., 2020; Cohen et al., 2021; Van der Hoeven et al., 2023). We show in App. E.3 that (MP poo ) is a convex polytope speci- fied as the intersection of N|| half-spaces. We define thbb (MP, - RK as the standard logarithmic barrier for
Assumption 4.2. There exists value > 0 such that (x [a. a) د a for all x x' E X²2 a E A, and n e [N].
Under this assumption, we show in App. E.2.1 that for = < 1+ VIA - 1)), it holds that A1 1) +
7

---

Online Episodic Convex Reinforcement Learning
(MPg)) (see Nemirovski, 2004, Cor. 3.1.1) which is a 0- self-concordant barrier (see Nemirovski, 2004, Def. 3.1.1)
+
for (My. with 0= = N || The second approach we adopt here is to run mirror descent directly on (Mpt) )
as the decision set and take 4/th as the regularizer in place of the entropic regularizer that induces I'. Let ç belong to the interior of (MPpg) which we assume is not empty. Property in (Nemirovski, 2004, Sec. 2.2) implies that _ (MK..) Hence, we can
Figure I. [left] Initial agent distribution; [middle] The three targets from mulri-objectives; Iright] The constrained MDP (reward in yellow, constraints in blue).
E + EV ()) ( construct an ellipsoid-entiree contained in (M > around any point in int(M)%)) Let 5¹ be the output of mirror descent at round t and U, == (V²)))(Ee))) ///a We
5. Experiments
can then use the following as a surrogate for the gradient of F o Ap at Et (see also Saha & Tewari, 2011):
We evaluate Bonus O-MD-CURL on the multi-objective and constrained MDP tasks from (Geist et al., 2022), which use fixed objective functions and fixed probability kernels across time steps. Adversarial and bandit MDPs are harder to implement due to challenges in finding optimal stationary policies, and there is a a lack of experimental validation in the literature. We focus on evaluating how well the additive bonus helps the algorithm to learn the environment. We also compare it Greedy MD-CURL from (Moreno et al., 2024). The state space is an 11 11 four-room grid world, with a single door connecting adjacent rooms. The agent can choose to stay still or move right, left, up. or down, as long as there are no walls blocking the path: 1n+1 = In + a, + En. The external noise En is a perturbation that can move the agent to neighboring state with some probability. The initial distribution is a Dirac delta the upper left corner of the grid, as in Fig. I [left]. We take N 40, 7 0.01, and 5 repetitions per experiment."
-) + 8U,,))) un'
with u' again sampled uniformly from S The eigenvalues of U, correspond to the lengths of the semi-axes of the ellipsoid used at round t, which could be arbitrarily small and lead again to the gradient surrogate having large magnitude. However, thanks to the relationship between g and U,. a local norm analysis of mirror descent (see, e.g., Lem. 6.16 in Orabona, 2019) absolves the regret of any dependence on the properties of Ug. Unfortunately, due to technical barriers, this log-barrier-based approach is not readily extendable to the setting where the decision set can change over time (in particular, it is not clear whether an analogue for Lem. 2.1 can hold in this case). Hence, we restrict its application only the case when the MDP is known, see Alg. 4 in App. E.3. We state next regret bound for this algorithm (proved in App. E.3.2), which requires the following less restrictive assumption in place of Asm. 4.2.
Multi-objectives: The goal is to concentrate the distribu- tion on three targets by the final step N, as in Fig. 1 [mid- dle]. The objective function is defined as (n(())) := >x-n(1 - <p e where e E R| is a vec- tor with a 1 at the target state and 0 elsewhere. Con- strained MDPs: The goal is to concentrate the state dis- tribution the yellow target in Fig. 1 [right] while avoid- ing the constraint states in blue. The objective function is defined as fn (1) r, C E IR | at the target and constraint states respectively.
Assumption 4.4. For every state x E X' and step n E [N], there exists a policy æ such that ΣaeA 14:- (x, a) > 0.
Note that this can be imposed without loss of generality since the MDP is known; defining X₂ S X' as the subset of states reachable at step n. one can represent occupancy measures sequences of distributions in (Ax, A)nENN]
P) + (4U7, c)) where LAI Here, r and e are zero everywhere except
-r, u
Theorem 4.5, Under Asm. 4.4, Alg. 4 with a suitable tuning T and 5 satisfies for any policy x II that
To compute the regret, we compare against the oracle op- timal policy, which can be closely approximated when the dynamics are known. For the Multi-objective task, Fig. 2 displays the state distribution at the final time step after 50 iterations for Bonus O-MD-CURL [up, left], and Greedy MD-CURL [up.right], and plot the log-loss [down, and regret [down.right] after 1000 iterations. We see that Bonus O-MD-CURL reaches the targets much faster than Greedy MD-CURL. As for the Constrained MDP task, Fig. dis-
E [[[T(T)]= (1811111)))))))**
Though holding only for the known MDP case, this bound maintains the % rate of Thm. 4.3 while eliminating its reliance on Asm. 4.2 and its undesirable dependence on the MDP's s structure. We leave extending this result to un- known MDPs and designing practical approaches enjoying the optimal T rate for future work.
'The code to reproduce the empirical results are available at: https: /i thub, com/b bi ancammo reno/Convex,
8

---

Online Episodic Convex Reinforcement Learning
References
Abbeel, P. and Ng. A. Y. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty- First International Conference on Machine Learning, PP.
641
1, 2004.
Abernethy. J., Hazan, E., and Rakhlin, A. Competing in the dark: An efficient algorithm for bandit linear optimization. In 2t Anmual Conference on Learning Theory, volume 3, pp. 263-274, 2008.
-01
10
CURL
Greedy MD-CURL Bonus CURL
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pp.
07-
Bonus MD CURL
200
263-272, 2017.
Figure 2. Multi-objective: distribution N 40 after 50 iters. for Bonus O-MD-CURL [up.left), Greedy MD-CURL [up.right]; log-loss [dfwn.left] and regret [down.right] for 10 iters.
Barakat, A., Fatkhullin, I,, and He, N. Reinforcement learn- ing with general utilities: simpler variance reduction and large state-action space. In Proceedings of the 40th In- ternational Conference Machine Learning, pp. 1753- 1800, 2023.
+
>B
Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3):667-175, 2003.
6101
Gaeody MD-CURL 0-MD-CURR
Bensoussan, A., Yam, P., and Frehse. J. Mean Field Games and Mean Field Type Control Theory. Springer, 2013.
1012
Bertsekas, D. Reinforcement learning and optimal control, volume 1. Athena Scientific, 2019.
0p4
Creedy
07
0-
Bubeck, S. Convex optimization: Algorithms and complex- ity. Foundations and Trends in Machine Learning, 8(3-4): 231-357, 2015.
1.00
613
000
500
1,000
Iacation
Figure 3. Constrained MDP after 10th iters.: sum distributions over all time steps n [10] at [up.left]: distribution the last time step N 40 for Bonus O-MD-CURL. [up.eenter), and Greedy MD- CURL [up.right]; the log-loss [down, left] and regret (dght.
Bubeck, S., Eldan, R., and Lee, Y. T. Kernel-based methods for bandit convex optimization. Journal of the ACM (JACM), 68(4):1-35, 2021.
Cammardella, N., Bušić, A., and Meyn, S. P. Kullback- cübler-quudraan optimal control. SIAM Journal on Con- trol and Optimization, 61(5):3234-3258 2023.
plays the log-sum of all state distributions for all time steps E [40] at iteration 1000 for Bonus O-MD-CURL [up.left]: the state distribution the last time step n 40 after 1000 iterations for Bonus O-MD-CURL [up.center], and Greedy MD-CURL [up.right]; and the log-loss [dfwn,left] and re- gret [dgwn, In this case, Greedy MD-CURI. fails to reach the target state even after 1000 iterations, while Bonus O-MD-CURL successfully reaches the target state avoiding constrained states to minimize cost thanks the additive bonuses. These examples empirically demonstrate the value of the additive bonus in tasks requiring exploration.
Canonne, C. L., Sun, Z., and Suresh, A. T. Concentration bounds for discrete distribution estimation in kl diver- gence, 2023.
Coffman, A., Bušić, A., and Barooah, P. A unified frame- work for coordination of thermostatically controlled loads. Automatica, 152:1 1002, 2023.
Cohen, A., Kaplan, H., Koren, T., and Mansour, Y. Online Markov decision processes with aggregate bandit feed- back. In Conference on Learning Theory, pp. 1301-1329. PMLR, 2021.
Impact Statement
This work of a theoretical nature, we do not foresee any notable societal consequences.
Cover, T. and Thomas, J. Elements of Information Theory. Wiley, 2012.

---

Online Episodic Convex Reinforcement Learning
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online Markov decision processes. Mathematics of Opera- tions Research, 34(3):726-736, 2009. ISSN 0364765X, 15265471.
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 11:1563-1600, 2008.
Jézéquel, R., Ostrovskii, D. M., and Gaillard, P. Effi- cient and near-optimal online portfolio selection, arXiv preprint arXiv:2209. 13932, 2022.
Flaxman, A. D., Kalai, A.
T.,, and McMahan, H. B. Online convex optimization in the bandit setting: gradient de- scent without a gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 385-394, 2005.
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. Learning adversar- ial Markov decision processes with bandit feedback and unknown transition. Proceedings of the 37th Interna- tional Conference on Machine Learning, pp. 4860-4869, 2020.
Fokkema, H., Van der Hoeven, D., Lattimore, T., and Mayo, J. Online newton method for bandit convex optimisa- tion extended abstract, 2024.
Lavigne, and Pfeiffer, Generalized conditional gradi- ent and learning in potential mean field games. Applied Mathematics & Optimization, 88(3):89, 2023.
Garcia, J. and Fernández, F, A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-110) 2015.
Lavington, J. W., Vaswani, S., and Schmidt, M. Improved policy optimization for online imitation learning. In Pro- ceedings of The 1st Conference on Lifelong Learning Agents, pp. 1146-1173, 2022.
Geist, M., Pérolat, J., Laurière, M., Elie, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. Concave utility reinforcement learning: The mean-field game viewpoint. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 489-497. International Foundation for Autonomous Agents and Multiagent Systems, 2022.
Lee, C.-W., Luo, H., Wei, C.-Y., and Zhang, M. Bias no more: high-probabille data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems, pp. 15522-15533, 2020.
Ghasemipour, S. K. S., Zemel, R., and Gu, S. A divergence minimization perspective on imitation learning methods. In Conference on rohot learning, pp. 1259-1277, 2020.
Luo, H., Wei, C.-Y., and Lee, C.-W. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. In Advances in Neural Information Processing Systems, volume 34, pp. 22931 22931-22942, 2021.
Greenberg, I., Chow, Y., Ghavamzadeh, M., and Mannor, S. Efficient risk-averse reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, pp. 92639-32653 2022.
Maurer, A. and Pontil, M. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.374 2009.
Moreno, B. M., Brégère, M., Gaillard, P., and Oudjane, N. Efficient model- based concave utility reinforcement learning through greedy mirror descent. In International Conference on Artificial Intelligence and Statistics, pp. 2206 2214, 2024.
Hazan, E. and Levy, K. Bandit convex optimization: To- wards tight bounds. In Advances in Neural Information Processing Systems, volume 27, 2014.
Hazan, E. and Li, Y. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv:1603.04333 2016.
Moreno, B. M., Brégère, M., Gaillard, P., and Oudjane, N. (Online) convex optimization for demand-side manage- ment: Application to thermostatically controlled loads. Journal of Optimization Theory and Applications, 205(3): 43, 2025.
Hazan, E.,, Kakade, S., Singh, K., and Van Soest, A. Prov- ably efficient maximum entropy exploration. In Interna- lional Conference on Machine Learning, pp. 2681-2699 2019.
Mourtada, J. and Gaiffas,, S. An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. Journal of Machine Learning Research, 23:1-49, 2022.
Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4): 157-325, 2016.
Hu, X., Prashanth, L., György, A., and Szepesvari, C. (ban- dit) convex optimization with biased noisy gradient ora- cles. In Artificial Intelligence and Statistics, pp. 819 828, 2016.
Mutti, M., Pratissoli, L., and Restelli, M. Task-agnostic exploration via policy gradient of a non parameetitr state entropy estimate. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10):9028 9036, 2021.
10

---

Online Episodic Convex Reinforcement Learning
Mutti, M., De Santi, R., De Bartolomeis, P., and Restelli, M. Challenging common assumptions in convex rein- forcement learning. In Advances in Neural Information Processing Systems, pp. 4489,4502, 2022a.
van der Hoeven, D., Zierahn, L.,, Lancewicki, T., Rosen- berg, A., and Cesa- Resa-Bianchi, N. A unified analysis of nonstochastic delayed feedback for combinatorial semi- bandits, linear bandits, and MDPs. In Proceedings of Thirty Sixth Conference on Learning Theory, pp. 1285- 1321, 2023.
Mutti, M., De Santi, R., and Restelli, M. The importance of non-Mark Markovianity in maximum state entropy exploration. In Proceedings of the 39th International Conference Machine Learning, pp. 16223-16233 2022b.
Wei, C.-Y. and Luo, H. More adaptive algorithms for ad- versarial bandits. In Conference On Learning Theory, PP. 1263-1291, 2018.
Mutti, M., Santi, R. D., Bartolomeis, D., and Restelli, M. Convex reinforcement learning in finite trials. Journal of Machine Learning Research, 24(250); 1-42, 2023.
Wolsey, L. and Nemhauser, G. Integer and Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization. Wiley, 1999.
Nemirovski, A. Interior point polynomial time methods in convex programming. Lecture notes, 42(16))3215-322
Zahavy, T., Cohen, A., Kaplan, H., and Mansour, Y. Appren- ticeship learning via Frank-Wolfe. In AAAI Conference Artificial Intelligence, 2019.
2004.
Neu, G. Explore more: Improved high- high-probabillty regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Zahavy, T., Donoghue, B., Desjardins, G., and Singh, S. Reward is enough for convex MDPs. In Advances in Neural Information Processing Systems, pp. 25746- 25759, 2021.
Neu, G., Gyorgy, A., and Szepesvari, C. The adversarial stochastic shortest path problem with unknown transition probabilities. In Proceedings of the Fifteenth Interna- tional Conference on Artificial Intelligence and Statistics, pp. 805 813, 2012.
Zhang. J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems, pp. 4572 4583, 2020.
Orabona, F. A modern introduction to online learning. arXiv preprint arXiv: 1IXX::9922.13213 2019.
Zhang, J., Ni, C., Yu, z., Szepesvari, C., and Wang, M. On the convergence and sample efficiency of variance- reduced policy gradient method. In Advances in Neural Information Processing Systems, pp. 2240, 2021.
Pan, X., Seita, D., Gao, Y., and Canny, J. Risk averse robust adversarial reinforcement learning. In Interna- tional Conference on Robotics and Automation (ICRA), pp. 8522 8528, 2019.
Zimin, A. and Neu, G. Online learning in episodic Marko- vian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems, pp. 1583-1591, 2013.
Rosenberg, A. and Mansour, Y. Online stochastic short- est path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019a.
Rosenberg, A. and Mansour, Y. Online convex optimization in adversarial Markov decision processes. In Proceed- ings of the 36th International Conference on Machine Learning, pp. 1478-5486 2019b.
Saha, A. and Tewari, A. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the Fourteenth International Confer- ence on Artificial Intelligence and Statistics, pp. 636-642, 2011.
Shalev-Shwartz, S. Online learning and online convex op- timization. Found. Trends Mach. Learn., pp. 107-194, 2012.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. Bradford Book, 2018

---

Online Episodic Convex Reinforcement Learning
A. Auxiliary Results
A.I. Auxiliary lemmas
Lemma A.1. For 0 < < 1,
Σ =1
(2, -
x
N 21 V /2T 2T log (3)
3/11222
with probability at least 28.
Proof. Let E. (2, a) == 1lpx a) p.. ar a)ll1. We denote by o' = (2/ anene[N] the trajectory of the agent at episode t when playing policy n². Let ". 'P(x,, a) 1l ((x), ((xx,aa))=(z,a)) be the empirical state-action distribution computed from the agent's 's trajectory. We consider the following decomposition:
N
ΣΣΣΣ p4 "f (c,,
Σ
Σ
p
Un
p
1=0
2.0
(2)
Term (1) analysis.
We start by analysing the first term. Using Lem. 2.2, we have that for ò E (0, 1), with probability 1 1- 6.
(1) ΣΣΣ (1. & 2| log
T
XIIATT
Σ
p a' (' a)
5
max 1, (xxxx)))
2.a
1= m.a.
Using Lem. 19 from (Jaksch et al., 2008), we have that for all i [M] and xx
p "x, a)
& (V2 + 1) NT
max 1, ((
Therefore, using Jensen's inequality and that E(r,,) NZ = for all ie [W], we have that
T
AT'
((r a)
x-1
Σ
Σ
V
(2,
(2
/ (T,
I=
0 n.
1=0
F,a
N n-1
(13)
Σ
v V
3/2 A
Substituting this inequality into the upper bound for term (1) yields
|XIANNT
(1) V 2 log
3.22 VIIIAAIT
(14)
=3/2/N2
2| log
8
12

---

Online Episodic Convex Reinforcement Learning
Term (2) analysis. We now analyse the second term. Let F o ..... 1 be the filtration generated by the trajectories of the agent from the first episode, up to the end of episode i 1. Note that (x+1 is F measurable, it only depends on observations up to episode f 1. Therefore,
+ a) Ph (xx F
(x a) " "(, (( S2+1 a), ((x, a).
")
For all E [N], let M = 0 and for all i E [T].
M, = Σ
Σ
(pm x (xx, a) ax)
From the observation above, (Mi)ettz is a martingale sequence with respect the filtration Fi. Furthermore, as by definition K a)l 2,
M
M &
Σ
(4 T (xx a) - p.. az) (2, < 2
#EN
aEd
Therefore, by Aruma-Hoefiding. we have that for any > O,
P(MM 3 & exp
8
Applying the union bound on all n e [N], we then have that for any ā E (0, 1), with probability at least - 5,
N
M < 2/281 2T log
holds simultaneously for all [N].
Substituting this inequality into term (2) and summing over n e [M] and i [n - 1), we obtain, with probability at least
1 1- 8, that
N
(2)
Σ Σ MT < 2|X1N2
V log (7)
(15)
Final step. Combining the upper bounds for term (1) from Eq. (14) and term (2) from Eq. (15), we obtain, with probability
least 25, that
T N ΣΣΣΣ
Σ
u (cx,
3/8/N22
| 2
(XIATTT
2//11122 2
2T )
concluding the proof.
Lemma A.2. For any 0 << 8 1,
(N ΣΣ 11
n
3N22 VI + 1 (L (2x
27 log
N 8
holds with probability at least 8.
Proof. Recall that we denote by (xt ( the trajectory of the agent during episode t, when playing policy πí, and that we define by f (xx a) = 1 (f as the empirical state-action distribution computed from the trajectory of
13

---

Online Episodic Convex Reinforcement Learning
the agent. We consider the following decomposition:
I N
Hi (xx a)
T
N
Pn p ((x a)
Σ
Σ (N-
- n)
Σ
n)
Σ
max(1, (2,
max 1, No N/ (2)
2,0
3,a
(1)
(16)
(1 Φ p (2r, a)
(N
D
max 1, N a)}
12
Term (1) analysis.
Using the same decomposition of term (1) of Lem. A.1 in Eq. (13) we have that
(1,0) 3N2 VI
ΣΣ IN (N-n) n) Σ t=n==
(17)
max 1, ())
Term (2) analysis. The analysis of term (2) follows a similar approach to the analysis of term (2) in Lem. A.1, with the key difference being that, instead of carrying the term related to the difference between the true probability transition and the estimated one, we now have the term 1/Vmax max {1, (2r, a)).
Let F := o ...... 1) episode Note that 1/vmaxx max (1, N (z, a)} is F measurable, as it only depends from observations of time step up to episode / 1. Therefore,
o be the filtration generated by the trajectories of the agent from the first episode, up the end of
BLl/ max N, a)}a "(z, a) = 1/v max (1,, a))m ((z,a).
For all [N]. let Mg 0 and for all e [T].
M Σ (N- n) Σ
1h "(x,0)()11/)/) 1))1////////// max (1, (1,
From the observation above, (M)).er) is a martingale sequence with respect to the filtration Ft Furthermore, as by definition [1/v /mx (1, (2, a)}{ &
M M & (N n)
Σ
Σ
(m (ne' (Fx, - po a(x, a) & (N (N-n))
xeX
REA
Therefore, by Azuma-Hon,idingg we have that for any > 0,
P(M > 2) < exp
2 n 2T
Applying the union bound all n [N], we then have that for any 8 (0, 1), with probability at least - 5,
N
Mf
N 27 2T log
8
Summing over n E [N], we have that with probability at least - 8,
N
(2)= Σ M &
2T log 12|N2
(18)
n=0
14

---

Online Episodic Convex Reinforcement Learning
Joining terms (1) and (2). To conclude, replace the final upper bounds of the terms (1) and (2) of Eq. (17) and (18) respectively in the decomposition of Eq. (16), and obtain that, for any 8 (0, 1), with probability at least - 6,
Σ
(N (N-m) n
((x, a) max (1, (1, ())
3N2 V + | 2T log (%)
2=1
z,a
concluding the proof.
Lemma A.3. For all [M (I,0, X Ax X, and t [T) let Ph (a' [x, a) be defined as in Eq. (7). Hence,
11 (zt =0,0
()) Pa (+1,,
max Nn (x, (x,
Proof. From the definition of the estimator p', we have that
1 Put (2) max - (x,
+ +1 (m - -aat-aataaa
Therefore,
c++ Pa41 (x' (2, - (x'1(= max(1, (1,N, N2++1 (x, a)}
=or (x (I, NH(a,
(0 - - 10 (1)-00000)
0,x (2, a)}
Summing over x' E X' we then have that
[s =x,a
I (1,,)() - (1)) <
1 (x,
concluding the proof.
Lemma A.4. For (n, a) [N] x X A. let (q') (e(r) be sequence of probability transition kernels with qf == (ghh) (gh)ne(N] such that
cl (xt. =z,a -a3
14 ++ (112, - (1((12
max
(1, (x, a)}
for some constant e > 0. Then,
T
gh + (-12, a) - a)) eclog(T).
Proof. We have that
NT (w.a)
T
1 (+1, (11,)
<
I fas =x,a = max (1, N (x, (x,a); a)}
Σ
T32 clog(eT) & eclog(T))
t
Lemma A.S. Let (e() be sequence of probubility transition kernels, iee, g¹ = wEIN such that for any state-action pair (z, a) and any step n e [M, Ei= l1 (-1x, - g%((112,, a)l1 & clog(T) for some constant e > 0. Then, for any sequence of policies (Tr* )e(T)..
1 gets
35 100,1 &
While for a fixed policy x.
T
Σ 1
10,1 & Nogg)
15

---

Online Episodic Convex Reinforcement Learning
Proof. Using Lem. B.1 obtain that
T
a
100,1
sup
Σ
Σ M4 x Ef -
ne|v| 1-0 2,
Mu (z,
(2, - (1t1(12,,))
[-1
0 2,0
N
T
ΣΣ
(Lt c|AAIA log(T).
While for fixed policy n.
T N-1
10 -
1
=- 100,1
Pn J (c,o)lon 1 a)
T N-1
[=(a d (-1,
n1- 2.0
Σ (d(z)) = c/
0
Lemma A.6. Consider a sequence of policies (I' ke(r. and define smoothed version of each policy i' for all E [T] as #' : (1 at)x + de [a where 04 1). Let p and be two probability transition kernels, denoted as p = (Pa)ne[N] and q = (ga) (NV). respectively. Therefore, for all t e [T].
N
1 1 - 1 4/
Σ
Σ
pt " (z, a))lpp)1((222000 a) (+11 a)ll + 2Na.
10,1
D 20.0
Proof. See Lem. D.4 from (Moreno et al., 2024).
A.2. Building a closed-form solution for each OMD iteration
In this subsection we argue that the MD optimization problem solved at each iteration in Lem. 2.1 has closed-form solution. Define the convex function G' (1) == (2",, μ)) + [(,, ji"), for > 0.
Optimizing a convex objective function over policies is equivalent to optimizing it over state-action distributions in Mp Therefore, the optimization problem solved in Lem. 2.1 over the state-action distributions induced by qi is equivalent minimizing the same function over the space of policies:
pio
min ('(n)
G (' TE(AA)oON
min
(19)
(si): policy problem
(6): state-action problem
In Thm. 4.1 of (Moreno et al., 2024), it is shown that for each episode t E [T]. an optimal policy for the problem
(' = T<< + 1', =x(AA)AxN
min
(20)
defined in Eq. (19), denoted by 1+1 can be computed using an auxiliary sequence of functions (²t) where Q1, X RR. The sequence starts with (v( (x, and for n E (N,..., .....,,,,, 1}, the following recursion
16

---

Online Episodic Convex Reinforcement Learning
used:
#2+1 (a/z) exp (TQn+I (I,a))
++1 [#/((//))=
En th+1 (al(z) exp (TQ, n+1 (2) a'))
(x) (x, a) Σ antil (1'1 xr a) Σ (
1 T
log En+ila (a'la") " x++ (a' ad(=x"))
The core idea of the proof is to show that, due to the specific divergence used (defined in Eq. (4)), Eq. (20) can be solved using dynamic programming. For further details, the reader referred to Appendix of (Moreno et al., 2024). similar result was also obtained by (Cammardella et al., 2023), though they approached the optimization problem using Lagrangian multipliers instead of dynamic programming.
Problem (i) of Eq. (19) is convex, and the theoretical analysis are given in Lem. 2.1. Thanks the equivalence between the analysis of problem (1) to provide theoretical guarantees for the closed-form
problems (t) and (di) in Eq. (19),
solution policy of problem (ii).
B. Missing Results and Proofs
Lemma B.1. For any strategy x (AA)xxN, for any two probability kernels p (eN) and q (gn)nE(N] such that Pro On X Ax X [0, 11. and n [N].
E a) a)lppt+(()Pp...... a) (1,))112,,))111
1=0
Proof. From the definition of state-action distribution sequence induced by policy in probability kernel p in Eq. (2), we have that for all (x, a) E X' A and E [N].
T.P [z, a) Σ Pa ('r'' (alll=//"))_)....... d')x)( p
Thus,
11. K.P - 11 1
Σ
Im (x, (x.00) a) - (5,9
x
- 17 d')gn(() (xla", (ol"" (m)
a'
Σ Σ
( (2) "7 (z)
v'aa'
ΣΣ Σ
1 (2' a')p (2)= a') - (z) (xla'',)))
s'.a'
- 13 (z', qm (xl (x) a')l
T.P
gn (-1x' a') d')ll Σ
1 (x', a') 2 (2', a')
a'.a'
Σ z'
T.P (a), al ()) Il (1p
gn "a)'',"''l | 1,-1111
Since for n = 0, 140 T.P
4b |1 = 0, by induction we get that
n-1
11
1 &
Σ p l d))))tt - g+1(-12,, a')l
17

---

Online Episodic Convex Reinforcement Learning
B.1. Proof of Prop. 3.1
Proof. In the analysis, we explicitly write the term separately from the other e [N]. We begin with the following decomposition:
T x
T
T
T
T
b
(b) po) = Σ (b,
1 - 1r*
(be
1e p)
+
(b
Ho) mo)
Term (1) analysis.
Using Holder's inequality, we have that
T
(1)
& bololl $0 -0"""111
From the definition of the bonus sequence, have that for all [N], 16ll L(N C) Hence,
N
(1) & LCB Σ Σ IN n)
ΣΣ
(z, (1 (+1,(-1,,))
2,0
(XIIAINNTT
NN)
3/
2|
8
+ 2
2T
8
where the first inequality comes from Lem. B.I, and the second inequality achieved for any å (0, 1), with probability at least 1 -28, using Lem. A.1.
Term (2) analysis. Using the definition of the bonus sequence in equation (11), and recalling that the initial state-action distribution is always the same, we have that, for any E (0, 1), with probability at least - 8,
T N
M PZz a)
=
Σ
Σ
(N
n) Σ
max 1, (Z a)}
N log 2T log
LC
3
XI
8
where the inequality comes from Lem. A.2.
Joining the upper bounds in term (1) and (2). Putting both upper bounds together we get that for any 8 E (0, 1), with probability at least 1 - 36, and from the definition of Co.
Σ 6b
Uy no) & LC 31 2/A[T Σ
T
|XIILAINTT
+ +2/211 log
(
.
3 3 + 1281 2T log (2)
+ LC
o LN LN
log
B.2. Proof Thm. 3.2 (Main result)
For proving the main result we join together all the pieces we presented the main paper and the appendix.
18

---

Online Episodic Convex Reinforcement Learning
Proof. We start by decomposing the regret and using the convexity of the objective function obtaining that
T
RT(m))
F' P) - F² (1
+
Σ
Fs (1
# F² (M)
( p), 1e
1
( De), 1e 18 1..
We analyse each term separately:
Analysis of RT We begin by analyzing the term RyD which represents the cost incurred due to not knowing the true probability kemell. First, we apply Hoeffding's inequality, and the fact that fz is L-Lipschitz with respect the norm || Il1. Following, we apply Lem. B.I, obtaining that
T
N
N
nel
L
Σ
Σ
(x, (1) - P (-12, a)ll2-
m4
We can now apply Lem, A.1 to obtain that for any E (0, 1), with probability at least - 26,
IIIATTNTT
RT
L3|X|N2 2| log
L2| 1
2 log )
(21)
Analysis of Replicy,
To analyse Rpolicy we further decompose it as
T b' n o² - -
R
ppolicy
VF (10 8) b² 1 1
Σ ( ()) 1. pm.0)
Reg RiphlyyMM
Re
where recall that (b,, nEn) is the bonus vector defined in Eq. (11).
Analysis of Rpolicy/MM We begin by addressing the term that accounts for the regret incurred by using online Mirror Descent with changing constraint sets.
From Lemmas A.3 and A.4, we know that the probability sequence (e') satisfies the condition that ΣJ_ 1 Phlla Additionally, at each time step since Ft is T.p-Lipsehitz with respect to the norm c0, have
clog(T) (T) for (VF(())) 1, LF LN for any state-action distribution μ.. From the definition of the bonus vector, we also have that | 1.x0 & LN Consequently. [[) - be 1 & 2LNºC, Therefore, we compute μ²* by solving
# ++ arg min
( (1 - 3 + T(,,
nEM
by applying Lem. 2.1 with v' f= C and the sequence of probability transition kernels (f') (f'))[TT> obtain that for the optimal parameter
V द.. where
b: (118(T)(( (c/21|A1) + +4) + log(IAA) + logT) log((AA))
19

---

Online Episodic Convex Reinforcement Learning
and recalling that Cs = / 2 log (1x))A)NNT/6).
RPolicyMD RT
< 2C BT + [Nel
< 2LN2 2 log
(2V + N (og(T))
8
(22)
- (LN2 log
|
(VN(Allog(T) N Nv (og(T))
8
Depolicy/oonus We start by analysing the second term of the sum in Re poolicyybouus For any 8 E (0, 1), with Analysis of Re probability at least 1 - 6, we have that
V F (1 ),M P.
"Lxll," pT..3 11
14 (1, Pl a)ll
1= R=1 == 2,0
T 1-1
Co
(x, 0)
/max 1, N1(,, a)}
T N-1
Cs
Σ
Σ
(N n Σ
ph 1 (x,
VIma(11, (xr
T
= Σ (b 1
(b Ho)
where the first inequality follows from Holder's inequality, the second from the fact that fú is T-Lipsehitz with respect to the norm || || and Lem. B.I, the third from the concentration bound in Lem. 2.2 where we define Css == /2|X1 log (1 and the last equality comes from the definition of the bonus vector in Eq. (11).
Replacing it at the Rep ppolicyboous term we have that
ppolicy/bonus
b
n :5
-1
V
F
T
(
14 n"
11 -1=-10 +
(b 4 T
Σ
(b Ho)
T
(b'
1
bb mo).
Lastly, we apply Prop. 3.1 to achieve that, for any d E (0, 1), with probability at least 1 - -6,
by mo) o LN 1 /ATTlog
IXIIANNTT
Re
Rpolicybonus
b
(23)
8
Joining the upper bounds on 1t MooolccyMM and R ppolicyybooms from Eq.s (22) and (23) respectively, we achieve that for any 5 e (0, 1), with probability at least 1 45, ignoring logarithmic terms,
Final upper bound on Repolley
Repolcy x/
(24)
20

---

Online Episodic Convex Reinforcement Learning
Joining the upper bounds Re and Replley, Note that the terms in the upper bound Replicy from Eq. (24) dominate those in the upper bound RyP from Eq. (21). Therefore, when combining both terms complete the upper bound on the regret, we obtain that, with probability 66.
Rr(x)= & O(LN")))2
concluding the proof.
C. Proof of Lem. 2.1: Online Mirror Descent with Varying Constraint Sets
Before stating the proof we recall few results from Bregman divergences and in particular the divergence I' defined in Eq. (4) that are used throughout the proof.
To simplify notation, for any probability measure 7) E Åg, where E is any finite space, we define the neg-entropy function, using the convention that 0 (O) 0, as <(n) := ΣgeR 7(()) log 7(z). For any := ((n)nelN) (Axx,) we define (z) A Ma(2; a) for all n E [M] and x E X. representing the marginal distribution over the state space. The function inducing the divergence I" defined in Eq. (4), is given by
N
()4)
Σ ((m)) ==1
Σ pPn))
(25)
By definition of a Bregman divergence, for any two probability transition kernels p. q, for all μ E Mp, and p' M where Mg the subset of M4 where the corresponding policies x satisfy on (a/ax) * we then have that
T(p,))) = (1() v(1) (Vv()), n/)
(26)
Additionally, for any probability transition kernel p, the function z is 1-strongly convex with respect to || ll,,,, within MP (see Thm. 4.1 from (Moreno et al., 2024)). Consequently, consequence from known property of Bregman divergences (Shalev-Shwartz, 2012) is that, for any j Mr, and yt E MM...
p() 3 Illl 1212,,1
(27)
Lemma. Let (g") [e[T]]]]]) be sequence of probability transition kernels, and (z") a sequence of vectors in Nx such that | & for all / [T]. Initialize n (ular) == 1/|A| as the uniform policy. For every I [T]. let #' : (1 az)= + a,|A|-1 be smoothed version the policy with a, == 1/(t + 1) and j := u="""" For each [T]. compute iteratively
1 E arg min T 14) + [H,,
(28)
peMy! 11
Hence, there a such that, for any sequence (v') (e)) with vt N= for common policy w,
Ka' 1² -²> OCNNNCVVTIN (o0
where Vr > 1 1+ (n,,a >F 14 - (- a)ll1-
Proof. Throughout this proof, for all t e [T] we denote by #' the policy inducing n², meaning that μ³¹ == p ah of and jt' := 11" = We assume here that max Σt- |1 (-|ar, 1 (-|x, a)ll & (log(T) for c a constant, as this is the case for all the transition estimators we use to obtain the main results the article.
As Mg convex set (only linear constraints), the optimality conditions and the definition of Bregman divergence in Mp
Eq. (26) imply that for all y*+1 MMg
(T2' + V Vib(at), u++1 1141 2
21

---

Online Episodic Convex Reinforcement Learning
Re-arranging the terms and using the three points inequality for Bregman divergences (Bubeck, 2015) we get that, 1 rl+1 E (Vb(((t)) - Vab(ā"), v(t1 - - = r( ,7") r (ou/t,,,t) - r(u .p).
Therefore, by adding and subtracting T(2,, 1² - -²>> on the left-hand side,
T t+ 1 + T(=", n² 1t) - -T(=' - -²> & r(utt), ,,') - -(ultt ,1(tt))
((ultt, - -T(alt) (²)
T=" n¹¹ -v) & T(22 vltt - -ni> + T 11 + r(ult1 , - r(ult1, ,u(t1) r(u (2.).
Then, by summing over E [T], we obtain that
T
T
T
Σ K p1 v²) $
(T(e", 4² - - - r(u . +
Σ
[T( ,1)) -(v (1utt1,xtt)) [
B
(29)
v++1 vl)
The term A arises due to our lack of knowledge of 2² at the beginning of episode for all episodes (adversarial losses hypothesis). To address this, we employ Young's inequality and the strong convexity of I. For the term B, in the classic Online Mirror Descent proof "Shalev-Shwarte 2012), where the set of constraints is fixed, the sum of the differences between the Bregman divergences telescopes (as would be the case with a fixed v). However, because we are dealing with time-varying constraint sets, this telescoping effect does not occur in our situation. We will now proceed to derive an upper bound for each term, starting with term C' that is straightforward.
Step O: upper bound on C. Applying Holder's inequality, Lem. A.5 with a fixed policy म, and the hypothesis that ||="|1, 1, < C.
T Σ (et vttp v²) 1
T | 1, llottttt
C
Vll,,,1 & (og(T.
(30)
Step 1: upper bound on B. We now analyse the second term of the sum in Eq. (29). To make the Bregman divergence terms telescope we add and subtract T(v", ,1²) - I(vA, fi)). obtaining
T Σ r 11') 1( 1 t1 =
T
T
pl (x) I(v",p))
+
ríp k²) - I(v", ,²)
(1)
(1i)
(31)
T
+
r(v", ,1²) - 1(x 1 11
(1i4)
We analyze each term. Using the definition of a Bregman divergence induced by & in Eq. (26) we get that
(i) ( - ((7²) (V ut+1 5²) ((0) + 6(7') + (Vi(""), v' i0')
Σ 11 - (b(²²² Σ (o((")) v² - wti)
T
<- + Σ 1, with 11,0
22

---

Online Episodic Convex Reinforcement Learning
where in the last inequality we use the telescoping nature of the first term and applied Hölder's inequality the second term. Recall that for (Vn)ne[N] such that U/, RA*'A, we defined ||e||,, SuPre[N] [|aa]]a- We now also define |||| 1, :- (Kw, e))l ||olla,,1 s 1 Σ su,a, (win(1, a)] as the respective dual norm.
With our choice of Bregman divergence, and given that
= (1 - a,t + at T
for each [V], (I) e X A. (n)(")) x, a)t = log(( (ak=)) log(IA//ar).
From the Lemma hypothesis, there is common policy such that for all E [7], ve =- vnn" Hence, from the result above,
T
[A
و - + Σ
log
- 2- 1000
ate
[A
< < + N log
c/ log(T),
[ aq
where the last inequality comes from Lem. A.5 with a fixed æ. As for the second term, using our definition of I, we obtain that
Tn(aaz)
TT (a/=)
(ii)
Σ
Σ
(2r,a) log
Σ (2, log
#[(aa())
TA (a|zz
1=1
n12,0
T
Σ
Σ
n (xs, a) log
1n,
n (a(x)
Σ
Σ
vil (z, a) log
(1-ag) (a(z) + av/ (e/lAA
(-1 I n,z.a
N
(- log(1 - an)) & 2N
where the last inequality is valid if 0 04 & 0.5.
The third term telescopes, hence, since ++ n 11) < 0 because Bregman divergence is always non-negative,
(iii) < ((²),,)))
Before adding back the three terms, note that, for (a(z)) 1/ A|] we have l'v2, (()),p²)) (((²)= -v(("). Furthermore, (w((²) & N Ao)([AA). Therefore,
r(v' ,p) +(v') ) < N log([AA)).
(32)
Summing over our bounds and using the Inequality (32), we get that is upper bounded as
T
M (0) - r 1 []]] & (i) + (ii) + (iii)
(33)
|A log( + N2c log min az)
2N T
log(T)
+
Σ
a4
Step 2: Upper bound on A. It remains to upper bound term A from Eq. (29),
A 1
(e n² 1 - r(u"t) .R")
(34)
23

---

Online Episodic Convex Reinforcement Learning
representing what we pay for not knowing the loss function in advance. For that we use Young's inequality (Beck & Teboulle, 2003): for any 0 be optimized later, and for each episode E [7].
2 1,,0
5 n r(u (7)
10
- 1 1+ 2
00,1 - 1'aatt,,
(35)
2x
2
From the definition of I in Eq. (4), we have that
r(u*t 1a')
Σ
p (a, log
Tn #'(a(x)
T (a/z)
r(u 10 (ft
(x,a)
From the strong convexity of th as n E M and 1** xt'"""" n
E EM9 we then have from Eq. (27) that
r(u xit) I'u't) ++
u g
2 glutt
1 00,1
(36)
Using the fact that for any vectors a, c, IRd and for any norm holds, we then have by Eq. (36)
1. the inequality |a - 613 2(1la - cl2
16
cl(²)
} Ellee- - 11 00,1 20.1
r( (i))
|1' 1t 112,1 11
2 1 10'' 10 1 100,1
2 (11² - 4
10 "=
120,1 + |1|0** 10 - 1
1
1
t
1
11
(37)
2
20,1
2 ||² at ap
00.11
For any n E [M1 we have 1,4, - pr . " the first inequality below. To obtain the second inequality, we apply Lem. A.5 with the sequence of policies ( (r)))
11 < 2. Using this result along with Lem. A.6 for p = fr and q gr we derive
n-1
Σ 1
11
2
Σ sup E ΣΣ
011 a) (1ll)
4N Σ a4
1
t-1 Ne[
t=u
(38)
< 11 log(T) + 4N
a2.
Therefore, summing Eq. (35) over L [T] with 1/2, and plugging the inequality above, yields
Σ 7 1 - - r(ut1 ,1 <
1 + N + 2N
at.
Using that |,00 & and dividing by r entails:
N A T - (cx11141)88()) log()) + Σ 00
(39)
Conclusion. Finally, by replacing the final bounds of Eqs. (33), (39), and (30), obtain
Σ p/ - v')
N TT + т
log(T) + (11111A11og((
T
N
log((-A))
a4
t=1
22c/221 log
LA
2N
log (T)
ai
min4efry at
24

---

Online Episodic Convex Reinforcement Learning
In particular, for ar 1/(1 + 1),
(2 p - v¹) TT ! N Tog(T) (cxx]111) + Iog([AA)) 2Nc/21 log((-A)) 1og(A))) +[Nc/221og(1
Optimising over 7 7
h
(2' -' & +c log(T)
log(T)),
concluding the proof.
D. Bandit Feedback with Bonus in RL
Notations. Throughout App. D. we define the trajectory observed by the learner in episode t as o' := (zt,, o',,% (2" aa2 neN]e Let F denote the o-algebra generated by the observations up to episode t, i.e., F == 0 ,...,o'-1, 1) We use E, to represent the conditional expectation with respect to the observations up to episode t, iee, E.[.1 = BT.
Overview of existing approaches. To adapt Alg. the bandit case, we need to estimate the loss function for each MD update. A classic choice using importance sampling is:
et (1, pn (x, a)
(x, a)
- -
This update is unbiased, ([]](x)=x
= ne, (2r, However, since do know the true transition probability p. we cannot use this estimate directly. In (Rosenberg & Mansour, 2019a), they use μ²' 5 with UC-O-REPS and achieve a regret of (
Consider the following confidence set, that further detailed in Eq. (41),
N = {u (1' a) pl (a' [x, a)l & (1' a), V(r,a, E A N [N]].
In (Jin et al., 2020), the authors incorporate parameter for implicit exploration, an idea from multi-armed bandits (Neu, 2015), and use the following estimate:
(x, Pr (x, a) (x, +
1l [(c) -0,a
(40)
where 77,, (I, a) = max ft ". Although this is a biased estimate (1C) "xx & [n, a)), Ω is constructed to ensure that the bias introduced reasonably small. They also argue that ji can be computed efficiently through dynamic programming. They demonstrate that running UC-O-REPS from (Rosenberg Mansour, 2019h) with this estimate achieves Ö(VT) regret, improving upon previous results.
In Alg. we detail our method for solving the RL problem with adversarial losses, unknown probability transitions and bandit feedback. We proceed to the regret analysis.
D.1. Auxiliary lemmas
Lemma D.1 (Lem. A.2 of (Luo et al., 2021), adapted from Lem. of (Neu, 2015)). Let (2 (Ir a))eer be sequence of functions F-mmeasurable, such that = (zr a) E [0, R] for each (x. X x A, and n E [N]. Let 2 (2, a) [0, be random variable such that (x, a)] = 2 (x, a). Then with probability - 6,
ΣΣΣ
T
N
(at tot==.ot =0) 72(,,
a PI, (ft,a)zz((c
RN
N g
<
log
(r, a) +
(x, a)
2
min=lea R.0
25

---

Update counts Online Episodic Convex Reinforcement Learning
Algorithm 2 MD-CURL with Additive Bonus for Bandit feedback RL
1: Input: number of episodes T', initial policy x² E 11, initial state-action distribution foo, initial state-action distribution sequence y² j f= .² with (1 a) 1/| for all (n,25,)) a), learning rate O, exploration parameter (tuned in the proof of Thm. 4.1), sequence of parameters (as)tttr with at 1/(t 1).
2: Init.: ((,, rr 0, 2.). x. No. (x,, a) = Mn (x'12, a) 0
3: for = ,,..., do
4: Agent starts at (x), ab) ~ mo(-)
5: for 72 = I,..... do
6: Env. draws new state rt Pn (1122 12 1)
7:
N (2n-1 M (I 1 - -
No -
8:
Agent chooses an action of ~ n (11=/)) Observe local loss éx (z", af))
9:
end for
Update transition estimate for all 1,, a, x'): pht (z x a) M (x (x'aaa)
12: Compute bonus sequence for all (n, x, a): (1, a) = max (1,N4 ((zaa)
(N-n)Ca
13: Compute optimistic state-action distribution for all (n, a): Fi,, (I, a) == max 10 where Q2 is defined as in
Eq. (41)
Compute loss estimate for all (n, a): & (x)
(x.a) (.(x,0)+7 (xt
15:
Compute policy =ff+ (x, a) by solving
n arg min (T(O - b, T(u, 7')) peMoo
which has closed-form solution for rt+ (see Sec. A.2) Compute #f+1, the smooth version ++1;
16:
#t1 (1 a1) + ta/lAA
and the associated state-action distribution bt w gt+1
17: end for
26

---

Online Episodic Convex Reinforcement Learning
We define the confidence interval used in Alg. 2
S2' := 1/ (2'12,
(x,a) a) P% (2 a)) & (2'la, a), for all (I,0,z') E A xxxxx Xn n [M]]
(41)
with
(1 x a) log
T
14
TNIX
(x a) a): = 21 max 1, No. N
6
(I, a))
3 max [1 N n (2, a)}
We present two results regarding this confidence set. The first result, based on the empirical Bernstein inequality, shows that the true probability kernel p belongs to this confidence set with high probability. The second a key lemma from (Jin al., 2020), which explains how the confidence set shrinks over time. For the proofs, the reader referred the original references.
Lemma D.2 (Empirical Bernstein inequality, Thm. (Maurer Pontil, 2009)/Lem. (Jin al., 2020)). With probability least 1 - 46, have that e S' for all [T].
Lemma D.3 (Lem. 4 (Jin al., 2020)). With probability least 1 68. for any collection of transition functions (p 2EX such that p² Q! for all we have
ΣΣΣ
In v''
(x,
o p "F a)) = O AT
TN (N|XIAA
5
D.2. Proof of Thm. 4.1
Proof. We start by decomposing the static regret with respect to any policy
(x follows
T
RT(()) =
e px
v
10
b¹, n
p=
4 1
1,
(42)
T
T
T
+
(C 1.
1r
be p 1
b war
3, R. RenGyM
Bonus
1.2.1. TERM 1: RADP
The analysis of this is already provided in App. B.2. Here, we can further leverage the fact that the objective function linear and that, by definition, f [0, 1]. Therefore, with probability at least 1 25, have:
ITANT 8
N
MDP
3///22
2| log
22/2/N22
22 log
2T
(43)
8
D.2.2. TERM R
RRPOICY/MD
In practice, the learner plays using the estimated loss function minus the bonus. Hence, Roolicy/MD accounts for both the bias introduced by the loss estimation and the standard mirror descent regret bound. We start with the following decomposition:
T
ppolicy/MD
Σ
E b¹ b,
n.
(C
?. 11 x
1 F
b
1
1
Bias terms
MD term
27

---

Online Episodic Convex Reinforcement Learning
Mirror Descent term in repolieyMD We begin by analyzing the error term from applying Mirror Descent with varying constraint sets, which is similar to that of Lem. 2.1 with z' = e - b', and (f) (F")etz1 as the probability kernel sequence defining the varying constraint sets. However, special attention is needed for the sup norm of the subgradient term since it now involves an estimate of the loss function. Additionally, the optimal learning rate now also depends on both the exploration parameter y and the analysis of the bias terms, we provide a detailed explanation of how the entire analysis affected below.
In proving Lem. 2.1 in App. C, the regret term for Mirror Descent is split into three terms: term A in Eq. (34), term B in Eq. (31), and term C' in Eq. (30). The analysis of term B remains unchanged since this term is independent of the chosen loss function. We focus on what changes for terms A and C.
As in the proof of Lem. 2.1, we use again the notation μ² := 40" for all t E [T]. From Eq. (34) term defined as
T
1
[Te
b¹, b',p'- - r(utt1,p5))
For fixed f, from Young's 's inequality we have that
N
N
1
T
1/ 1
&
2 211n
11
1
n
2x
Following the analysis of term A in App. C, in special Eqs. (36), (37), and (38), obtain that for 1/2,
1 + e lT)
2N
A
Σ
ar.
(44)
From Eq. (30), with the notation s²
D. term is defined as C= = 1 DT
7 T( ,1, v²) From Young's
inequality with 1/2 we obtain that
7
2
11
10 T
C
|| 1
12 1/ 12c,1
20
T
1-1
(45)
(og())
1
n
27
==1
Bounding the sup norm of the estimated loss function. Recall from the definition of the bonus function in Eq. (11),
11 + |b 2 we can focus on the with L = 1, that (b, & NC2 =: for all n E [N] and & E [2]. As 1 1 < term involving the sup norm of the estimated loss function.
We apply Lem. D.I with () = 1 -x,et -a (z,a) and * (I, a) pi(s,a)+
M " (1x,a) Note that 2 a), (x, & pl. (2,a))t y, that (x, a) meaasuraal,,, and that E, (, a)] = 2 (x, a). Therefore, with probability 1 1-66 5,
& (a, a)²
n=1
1=
3,a
N Σ
(ant m -a) B (2, a) 1l [zt -,,,,,, -aa (a,
PL (x. a) +
1h( a) +7
(ar -aa -a) Z (z,
Σ
Σ
(, a) +7
M (Ir a) ph P(x, ( a)
1 N
N
+
log
p 0) +7
7 22
8
Lem. D.1
28

---

Online Episodic Convex Reinforcement Learning
Lem. D.2 states that the true probability transition p Ω with probability - 46 for all e [T]. Hence, with probability
1 1- 46, nn (a, a) a 1 (xx, Consequently, by replacing it in the previous inequality, we obtain that with probability
1- 56,
T
N
T
N
NT
N 8
(x, a)² +
log
27
NT
< *
+
log
272
where for the last inequality we use that E [0, 1]. Therefore, by replacing in the upper bound of the terms and C Eqs. (44) and (45) respectively, we obtain that
NT
3e. | (T)
2N
+ A+ + C & T
72
log
2r
Or.
The upper bound on term B from Eq. (33) in App. C remains the same:
N B J
[ log
|A
2N T
log(IAA)
log(T) + Σ
ag.
T
min at
t=1
Thus, setting 0₁ = 1/(t + 1). the final upper bound on the Mirror Descent term is, with high probability, given by
C b¹ p 1.
A++++C
(46)
NT N 72
) + C.NIIIAA log(T) N log((-A))
e log(lA[T) log(T).
+4bTN| +
log
T
Before tuning the optimal parameter т, we must first analyze the bias terms.
Bias terms. We now proceed to analyze the bias terms. Our approach is similar the used in (Jin al., 2020), with key difference: they utilize confidence sets in their Mirror Descent iterations, whereas perform iterations the set induced by p². We start by dividing the bias term in two:
T
T
T
c 2.
8¹ - -1
Σ (e
E p
C
et 1 u=
Bias 1
Bias 2
Bias 1. Since 1²= 56 is F'-measurable, we have that Eg[(e- - 2. 11, 1'>''' (E,fe" 2., 1et S¹)). and for any time step E [N].
For any couple (z, a),
16 (2(2, (h(ee + P C (1 a))a p(x,a)
(xx,a)
(L - (x, a)] (x,
(2, +7
16, a) +
Hence,
T N
(z, (z, (h(x,a)+ + 1 (c,
E, Bias 1] = Σ
Σ
Σ
x ph
(1(2,a) +
x.a
From Lem. D.2, and from the definition of j. have that with high probability, ph a) 2 M 56 (x,,)) therefore,
T N
T
E, Bias 1J <
Σ
Σ
Fi (1, a) + p. "Iz a)l <
p a) - - P(z, a)) + IIT
1=1
R.a
2,
29

---

Online Episodic Convex Reinforcement Learning
Note that 1 (xr a) max uh ((x,a) n (d(x) maxpen Pa =P P(x),, where p p()) := Eee 1 (Ir,))) Therefore, for each I E A, there is pa. O2 such that (2, = p x0t (x, a).
From Lem. D.3 we obtain that
(x) - 1% *(x,()))))))) -0(1000(()))))) LA]Tlog / |2IILANTT
Pn t' snd
8
min=lo 2,0
Therefore,
Bias 1] ON2122IN |A|Tlog
(
+ +
8
As we have that Bias 1 [iias 1] + 2 ( &. nt # >
all that remains is to treat the second of the sum.
With high probability, /1,, (2, a) > pr (xr, a), therefore
Σ 7
Σ 2 (z, pp & (x. < Σ Σ
e (x, (35=x, & N.
11 2,0
Thus, Azuma's incquality gives that
[E. - < NN 2T 22 log (+)
which is of smaller order than the terms previously appearing in the bias bound. Hence,
Bias ((N
8 ( )) + 7
Bias 2. The result follows directly from Lem. 14 of (Jin et al., 2020) using nm instead of p.=P:
Bias 2 = E c el 1 = =0 log( |IIAIN
8
Optimizing the learning and exploration parameters 7 and 7. By joinning the Mirror Descent term from Eq. (46)
along with the bounds on Bias and Bias terms, and setting 7 = T, we obtain that
RroliyyMD o [Tb]IX1AAT
N
log
| (T) + log((AA) + N |1X/)
AT + NT N logg( XIIAIN
+ N2 l|
Let p1 (b+ I). and
N log ( + |XI (Tg(T) + (4g( + log() log(T) (T))))))))))) + log
| }
422 := N
8
For For 22/ P. recalling that b = NCs, and that C3 == / 2 log NTT /), we obtain that, with high probability,
Rpolicy/MD
2/ O( = 1 ||
N2 VAAT).
(47)
D.2.3. TERM 3: RPOLICY/MD
The upper bound for this term directly follows from the analysis of adding the bonus term to compensate for insufficient exploration, as discussed in Subsec. 3.2 of the main paper, and is detailed App. B.2. Thus, we have that with high probability, R.
ReolicyMD & 0.
30

---

Online Episodic Convex Reinforcement Learning
D.2.4. TERM 4: BONUS TERM
The analysis of this term follows directly from Prop. 3.1 from the main paper: for any ò e (0, 1), with probability least
1 1 35, we have that
T Σ
b
n -
0(N4)
(48)
D.3. Final bound
Replacing the upper bound on all four terms from Eq.s (43), (47), (48), and that Reelicy/MDD into the regret decomposition RT
in Eq. (42), we obtain that playing Alg. 2 for the RL problem with bandit feedback on adversarial loss functions has, with high probability, static regret of order
Rr(x) - *
E. Curl with Bandit Feedback
Notation Let S and A be two positive integers. For convenience and brevity, we suppose in what follows that X' = [S] and A = [A]] Accordingly, we will often use and in place of [ and |A| respectively. Let À E {A, A 1). For vector SSSA and (n, z. a) [N] x [S] x [Á], use (n(z, a) as shorthand for E((n 1)SA + (z I) + a). Similarly. let Á e {AA A - 13. Then, for an NSÀ x NSA matrix M. we use M(n, x, a, n', ,'',,' .a) to denote the item in row (n 1 ( + (x - 1) + a and column (n' - 1)SAA + (a' - 1) + a' of M. For any E Z4, let 1 E RRd be the vector with all entries equal to one and La the d x d identity matrix.
E.1. An alternative representation for the decision sets
In the following, we will fix an arbitrary transition kernel = (pn) (pn)ne[NN- We recall the notation that for ( E MP.
Ao
pf (z) == LLeA (z(z,, a) for (n, [N] x X, which satisfies pL (x) a Sn-1(z', a') d')Pn((ale palaal' .') for n > 2. At the first step, we define (x) = Σ. A
a' M (nnlx','aa" which satisfies (x(x)) pf(x) for every Ç Mp. and x E X since the initial state distribution is the same for all occupancy measures in MMP
Mo(x",
We describe here the mapping alluded to in Sec. 4.2.1 of MP to a lower-dimensional space where it could have a non-empty interior. This is analogous to how one can define bijective map between the simplex Aa and the set {a IRd-1; 1 ball, see (Jézéquel et al., 2022, Section 2). This can be done since any coordinate I, of a vector E Aa can be recovered from the rest of the coordinates: z,. 1 -- Σitc Tj. In our case, denoting by a* the last action in A (i.e., a* A. recalling that A [A]), we will represent the occupancy measures as vectors R-A-(A-)) by omitting coordinates that correspond to this action. We can afford do so, since for any μ E ME. we have that p,, a*) pH((x) - Mn a) where P is recoverable from Mn-1 and given in the first step by the initial state distribution pf (zz). which does not depend on μ. In the following, we use this idea to define the sought mapping.
and x; > 0 Vi E [d - I]}, which is the intersection of the positive orthant of Rd-1 with the Lı unit
Define the A x (A - 1) matrix
G
and let H be the NSA x NS(AA ([AA]] 1) matrix obtained via taking the direct sum of NS copies of G: = +
NS D
G.?
Define
uP NSA such that
(z, a) = pf(x)[(nn = a, a*). a
Next, for every 2 & m & N, we define WP.m as the NSA x NSA matrix where
WP. (p,
== I(n m, n' m 1, a* (pm
M
For an n matrix M and an n' m' matrix Mr, M $ M' the (n + n') (m + m') block matrix
0
M'
31

---

Online Episodic Convex Reinforcement Learning
Then, define the NSA x NS(A 1) matrix
B (INSA + WP..)..... ...(MAAAI..AA.... (INSA + W
and the vector
B (INSA + WP.)
(OANA ... (INSA WP.3) Wm.
Finally, define the function Ep: (NNS(111 - RNS where
Ep(9) = B B
for & (N--(A-)).
To explain the semantics of =p. let ME and j R-SS(A-) be such that (1, := (6n (2, for all (n, u, x, a) [N] x
X' x Alaa. It then holds that Ep(() = μa. To see this, note that Hü expands j setting (x, = -aaaa Ma( a). To fully recover pn(
what remains is to add (*()). This is achieved at n = 1 by adding w to Hï since a²) = (z( = (z) and w.f (2, (2,a) = 0 for a * a*. Next, at n = 2, the matrix Wr? extracts the values (5(x) when operated on H + uPidl such that (2(2, a²) is recovered at coordinate (2, x.
wh (x,a*)
a²) of (INSA + ( + w Iterating this procedure until step N allows us to fully recover j from jı. While for a generic & E RNN((A-)) 5,,(E) the unique vector in VSA satisfying (E)( a) = En(a,, a) for all n, and o a²; (E,(E))( (1, a²) pf(x) L (=)()))(z, a) for all and (zz (Ep(E( (2,, (pp(a'x',,/n a') Laza= (Ep(E)) for
all x and 3 2.
Note that Bd has full column rank since for any & E RNS(A-1), BPg is only an expansion of &; hence, we can define its left pseudo-inverse (BP)+ = BP (BP)+ projects vectors in NAA onto the column space of BP, which is given by
which satisfies (BP)+ D INS(A-1). On the other hand, the matrix
a BERNAA NNA,
(n)( = Σ (n- d') (alp d) X,2 2 n x'.aa
N and a)) =0 V. x (49)
is easy to verify that for any μ. Mo / μ¹ lies in the column space of BP (recall that E. (1( E. (z, pf (z)). Moreover, 3 MMo as it corresponds to a policy π where TT, [x+)x) 1 for all and Therefore, for any # E MP, 3r belongs to the column space of B", and we consequently have that
Ep((B))+(p - 3²)
Hence, by the definition of Ep. (B*)+ ( 3 coincides with μ on all coordinates (n, x. a) E [N] x X x Affa*) (since the map E, only expands the input vector adding the coordinates corresponding to action a²), and is then the only point in R NS)A-1) that E,p maps to μ. In light of this, define
(MP = (g (S(A-)( Ex(E) E M
the pre-image of Mp under Ep. Accordingly, we define An: (MPn)) - Mp as the restriction of E, to (MPo) that is,
Ap = Ep((MEg))
This then is a bijective function, with (1) (~=)))))))))
Still, (MP,, is not guaranteed to have non-empty interior. Suppose that some state x is not reachable certain step * that is, for every state æ and action a, P, (z+ |x, a) = 0 if n* 2, just that p²(x*) 0 if n 1. Then, for any MPpa. Mns (x", a) 0 for every action a. This implies that for every & E (My) En* (x" a) 0 for all * a" (since these coordinates are preserved under Ap). and hence, (MP mg has an empty interior. To remedy this, we rely on Asm. 4.4, which is equivalent to imposing that for every state x. pf(x) > 0 and there exists for every step n a state-action pair (x', d') such that Pn-1 (ar|z', a') > O. We show next that this condition sufficient for (MP.)) to have a non-empty interior. We first present an alternative characterization of (MP))
Lemma E. It holds that
(MPx) {E (E(A-))))) Bº > -39
32

---

Online Episodic Convex Reinforcement Learning
Hence, (M is polyhedral set formed by NSA constraints; namely that for n,Z,a Ba (n, TE (x, > O.
[N] x x A.
Proof. Any { (M clearly satisfies B -B since B f Ap(5) M whose coordinates are non- negative. Conversely, assume that B > -3" for some & E R (3(-1)), and let μ = Ep(E) = B + fP. Showing that { (MP,)) is equivalent, by definition, to showing that Ep(E) M Since f M and B belongs to the column space of BP specified in (49), it holds that
[nn(z, Σ
Mn (x', ('))p'((ppaa
x¹ x'aal
for every 2 2, and that E. (2, = E. B(, = show that μ (Axxa) By assumption, j only has non-negative coordinates; therefore, only have to show that Le, Pn (z, a) = 1 at every This easily done via induction: Σx,a 11 (1(2aa) E. (2() 1, and for n > 2,
(z()). (()() Then, to show that μ E M jag it remains to
Σ (m((z,)) Mn-ll' (')pnct Mn-i1 x'
x',a'
Lemma E.2. (MP))) has a non-empty interior if and only if Asm. 4.4 holds.
Proof. Necessity immediate as argued before. We prove sufficiency utilizing an argument from the proof of Proposition 2.3 in (Wolsey & Nemhauser, 1999). For every step-state-action triple (n, a), , it is easy verify that Asm. 4.4 implies the existence of some μ MP, such that pnn (z, a) O. Taking convex combination with full support of one such occupancy measure for every (n, a) results, via the convexity of MP in an occupancy measure μ e MP whose entries are all strictly positive. Hence, 5* := Ap*("* is an interior point of the polyhedral set (MY)) as it satisfies with strict inequality all the constraints defining it.
E.2. Entropic Regularization Approach
E.2.1. FITTING A EUCLIDEAN BALL IN THE CONSTRAINT SET
For the following, fix E E (0, From Sec. 4.2.1, recall the definition K == e/(A- 1 + - We now show that #1 (S(AA1) + KV e (Mp ) for any v e () assuming the transition kernel == (Px)ne(NN) satisfies the condition of Asm. 4.2; that is, (n (r, a) > E for all (n, x, x', a) E [N] X2 x A. Take (".P =
+ KV). Note that showing that x1 NS(A-1) + NO E (Mp, is equivalent to showing that ç.. E MY. the following, we proceed with the latter.
Note that via Lem. E. it suffices to show that Ç".P is non-negative. We induction in the following show more particularly that Cu.P E (A By the definition of cu.,, we have that for (n, x) [N] x X,
(x,
(1 + Un (x, a)) Va E Ara" and (x, (x,a"" a²) A- VA
E
Ph 2 (x)
Σ a#a*
(1,
(50)
where " (a) = L'Exx 2 1 (x', al) (x)x'' a') for n 2 2 and pi (x) =
E. x'E ao(x',a')p (x)p)' ,a) = (z). For a², clearly CP.P( a) 2 Un (x a) 2 -1 Note that at any step n and state x, the Cauchy- inequality and the fact that E B (SA- yield that
Σ (2, & <VA-1 a
Σ axta
(nlII VV-
Hence,
Σ a
(I)
Σ
11 + Un (I) Ee.
14
a
33

---

Online Episodic Convex Reinforcement Learning
<a.2 (x) 2 for every x. Hence, (50) gives that S (z, a 0 at every On the other hand, Asm. 4.2 implies that pi
Moreover, (50) also implies that Ei,a Ci 2 (2, a) Ex (x( 1, yielding that G AxxA- For 3 2, assuming
that S & AxxA, Asm. 4.2 implies again that Ph " (x) 2 & for every x. We then get via (50) that ( a²) > 0 c
and that Gh E AxxA since Mi,, (H, a) 2 Ps (a) 1, which holds again via (50) and the assumption that S x Induction then establishes that <".P E (Axx as sought. As mentioned above, this implies via Lem. E.1 that u. MP
"oo or equivalently, that x1 KINS(A-1) + KO (Mpg) and ç Ap(*lNN(A-1) ko).
E.2.2. ESTIMATING THE TRANSITION KERNEL.
In this section, we define and analyze alternative transition kernel estimator to the one given in Eq. (7). What we seek in this new estimator is (I) that it estimates well the true transition kernel, with guarantee similar to that of Lem. 2.2; (2) that drifts across rounds controlled manner, satisfying the bound of Lem. A.3 up to a constant; and (3) that, at the same time, it satisfies the condition Asm. 4.2 almost surely, supposing, naturally, that it satisfied by the true kernel.
To recall the notation, for each round E [T], of denotes random trajectory obtained by executing the policy x' in the environment; that is, of = ...,, x.y, a'y) where at n' (-12%) and xx Po(-laa-11 - We also recall the definitions
N (x, a)
Σ 1 (m)=m_0=0)
and M1 a)
Fix n, [N] X' x A. As an intermediate step, we compute at the beginning of each round / the Laplace (add-one) estimator for p,, (-|ær a); that is, for x' E X.
(, = M M 2 a) +1
(51)
(z,) S
To obtain guarantee on the accuracy of this estimator, we firstly describe a slightly different setting. Let (#:)==1 be an i..d. sequence of states such that di pm((22, a). Then, for k [T]. we define the Laplace estimator
(='101,0)) 1 E ((x--2)) k S
No. (x,a) (-|2r, a). keeping in mind that the number of
Notice that in our setting, the distribution P (-1x,, a) is equivalent to Pr samples N (z. a) is random and dependent on the observed samples. Let (p g) denote the KL-divergence between distributions (probability mass functions) and We derive the following result concerning the divergence between ø and p using known properties of the Laplace estimator and a union bound argument.
Lemma E.3, For fixed t, n, x. e [T] x [M] x X' x A. it holds with probability at least 5 that
1618 + 6y Sog 5/2 ST 310
DEL (pm (x, a) (1x,)))))) a))
max [1, 1 (x,a))
Proof. For a fixed e [T]. Thm. 2 in (Canonne et al., 2023) and Prop. in (Mourtada & Gaiffas, 2022) imply that
p DRL (P (1(,))))))
1615 + 6v 5 log
5/2 $ 310
45
& 8.
k
Via a union bound, we obtain that
P p DKI (pn,-12, ()) ph, (-122, a))
1615 + 5/2 310
48
max 1, N a))
*Recall that (zá, ab) po((s-).
*Note that if No (xr O. then 5%. (.12,,)) is the uniform distribution and DELL (pn( (122,)) (- a)) log S; hence, the bound trivially holds.
34

---

Online Episodic Convex Reinforcement Learning
P 3 [T]: DKL (pa(k,)) (+2,)))) 1615 6y log" 1/g + +30
& 8T'
k
The lemma then follows after rescaling 8.
Note that the distribution P (-|z, a) does not necessarily satisfy the conditions of Asm. 4.2 uniformly. Next, define for given E E [0, 1/S] the set
4 = ( 1/-= = and x e e Vi [d]] S Ax:
which is the set of state distribution assigning probability least to every state. We then define P (-12, a) as the information projection of P. (-|a, a) onto 4x; that is,
a1),, = arg min DKL (q gE
(52)
which exists and unique since 4x is compact and DKL (- (-12, a)) is continuous and strictly convex where it is finite (note that ir, (- (ar a) never assigns zero probability to any state; hence, DKL. (4 1% (-pr,, a)) is finite for any E Ax).
(=,(- a) is not already in xx. this projection can only bring us closer to pn Pr(11z x. a) in the K L-divergeecce sense as the following inequality (Cover & Thomas, 2012, Thm. 11.6.1) states:
DKL(Pn 12, a) P (-12, a)) & (p,(p, a) I1 (+1, DKL (P% (+12, (1(,,)))
(53)
With this fact in mind, we can arrive at the following result, parallel of Lem. 2.2.
Lemma E.4. With probability at least - 5, it holds for all t, x, E [T] [N] X' x A simultaneousty that
3225 + 12V5 log 5/2 S3ANT? + 620 max 1, L, (x,
46
Proof. The statement is consequence of (53), Lem. E.3, and Pinsker's inequality; followed by application of union bound over all rounds, steps, and state-action pairs.
What remains now is show that there exists constant
0 such that
1 16tt-2,0 max(1, (x,
1 (-1x, a) - Ph+ (-1z, a)lla &
This can be easily shown to hold for pt, i.e., before the projection step, states the following lemma.
Lemma E.S. For all n E [N - 1]. (x, a. 2') E X x A x X, and t E [T]; (at1(a'1e, a) as defined in (51) satisfies
21 (mt -0,5-
(+ p (11,, a)lı <
No (x, 5
Proof. The derivation follows along the same lines as the proof of Lem. A.3. We have that
1 ( - -x,t -a}
+ (='(2, +1
p1t (1'12, a) =
No (I, S
-a)
Na a) + S N++ a) + s (h (
(x, +
Hence,
1
+ + (a(2,a) Ng ( S
Pi (2, ( xx
No+1 (I, +
[et =a]
No (x, a) + (1 (1()))))) - (2 ())))).
35

---

Online Episodic Convex Reinforcement Learning
Finally, we conclude that 1 (-1x, a)
1h+1(11z a)Ila
Σ
(Pat) (a'12r,0)) a) - pn+ (1(12,a))
x' a' (2 (#1(2,0)
21 f2g =x (1 Pn+ (2 (1 N (x.
21 = N (x. +
To derive a similar bound for the projected estimator p'. we firstly derive a more explicit characterization of the information projection onto Ax. For a fixed E E (0, 1/S), define the function Is IR x Ax IR
as
(e(r:))= = Σ max(re,p(z)) TEX
Lemma E.6. For any given p E Ax, the map ge (r: is LS-Liccchitz and has a unique fixed point. Moreover, denoting this fixed point by r*, it holds that r* e p(x)x and that ge (e(rp) r r" and ge (e(rp)) r for y*
Proof. We firstly note that (=(:)) can be easily verified be convex. For any r and any subgradient h of ge (<(:p) p) at r. it holds that [A|] < eS. Hence, the convexity of ge(:;)) implies that (ge(r; ge (r':p) & eS r'I for any r, E R, or that ge ()))) is eS-Lipschitz. This implies, since eS < 1 by assumption, that ge (:; p) is contraction mapping; hence, via Banach's 's fixed point theorem, it admits unique fixed point r* R. For < 1, it holds that (s;pp) > p(x) 1 While for > max, p(z)/e, (r) rES < Therefore, r E [1, max, pl p(z)/E). Moreover, for any < r* (r (+>1 r*), must hold that g=(r:p) > (g=(r:)) < r); as otherwise, the intermediate value theorem, applied to ge (r:p) - r, would imply the existence of another fixed point, a contradiction.
Next, we define ra: Ax - R as the function that maps a distribution E Ax to the fixed point of ge(-sp). This function is well-defined as implied by Lem. E.6. now show that the solution the information projection problem onto A can be expressed in terms of the function re. For p é Ax. we define ps 4 as
(P),
Pe(x) Lnrex max(rs (p)ex p(x') max(s,p(=)/rr<())
Lemma E.7. For p Ax, it holds that Pe = arg min GA; DKL(a
Proof. We assume without loss of generality that p(z) for all E X; as otherwise, we can cast the problem into lower dimensional one considering only the elements X for which p(x) > Since the constraint set is compact and the objective is continuous and strictly convex, this minimization problem admits unique optimal solution. We start by rewriting the problem as
Σ ((x) log ((x) p(x)
min geRS
subject to
((x) & 0 X
Σ ((x)= 1 =0
xE
Define the Lagrangian
T(g, u.
Σ
( log
g(x)
Σ u(xx)s +
Σ g(x)) ((x)) -1)
x p(x)
25x
xEX
for R and RS.- We have that
0g(xx) (g, v) log g(z)
àL
1 - u(xx
p(x)
36

---

Online Episodic Convex Reinforcement Learning
We now show that satisfy the KKT conditions by choosing solution pair q" and u², x* where
(z) max(e. u²(x) == log m ((t)eep(()//r and ot == -1 logr=(p).
((x)/r<(P)
Firstly, qº indeed belongs Ax by the definition of Ps. and u* is non non-negative. Moreover, whenever (*(x) E, get that u² (a) 0: hence, complementary slackness holds. Finally,
L (q(2) (4" u )* log
pax(eep(aa//re(/)) + log p(æ)
(ax((ep(x)/rrele 1 logr=(p) 0.
p(x)/re(p)
Therefore, we conclude that P. is the optimal solution.
Computing Pe, or the information projection of p onto A can be performed efficiently. In particular, the following characterization implies that (p) can be computed exactly a finite number of steps by iterating over the set of states. Lemma E.8. Let X3 = fr X: (<(p))/e;p)) < p(z)/s} and X = xxp Then,
re(p) Evex+ p(x))
Proof. As stated in the proof of Lem. E.6, for r 3 max p(x)/EE (r(pp) reS r; hence X is non-empty as least includes arg zax p(r). Moreover, from the same lemma, have that rx(p) < min p(x)/e and Te (p) b max, p(a)/E e (if' X is non-empty). Therefore,
Te(p) gr(r
Σ zeX
(e() max)) (c.l))) Σ p(x). DEX'
The previous lemma also implies that Te (p) & (8- Returning back our original objective, show next that llpe- qella 1 is no larger than constant multiple of [p 4/12 for any two distributions p and q. Towards that end, first show that rr is Lipschitz continuous.
Lemma E.9. For 25. the function r. is I-Lipschitz with respect the || ||| norm; that
(r=(p) rr(()) & 11 4l1
for any p, Ax.
Proof. Note that, for any fixed r R. (r: convex; and that for any p e Ax and subgradient of ge(r::) at p. it holds that & is non-negative and satisfies ||k]| 1. Hence, for any P, E Ax.
1 11pp 9111.
Ige (r:p) -r(:)))
(p(x) - q(x))= Σ
(g(x)
p(x))
(54)
2
p())
((2)>((>)
Then, we obtain that
(re(p) - -r(()) (9-(re(p):p) (=(r(()):))
< (r)((r (e(r(()) p)1 (r (r)
1 < < -r((a)) + _ ali & (re(p)))r(())) -re(1)) + 2 911,
where the second inequality follows from (54) and Lem. E.6, and the last inequality holds since e 25- The lemma then follows after rearranging the last result.
1. Lemma E.10. Assuming & 28, holds for any P. 9 Ax that lipe qe 11 & 31ppp g
37

---

Online Episodic Convex Reinforcement Learning
Proof. We have that
(x(x)) max(re(q)e.q(z))
r=(1)
max(r + max(r=(w)e, re(g)
max(re(9)s, -
Te(p)
re(g) Pe(x).
re(g)
Then,
(x) - (e(x)) rz(9)
(max(r - max(r=())), + (re(p)-radol -ecp))-rr(a))lle r=(1)))((x))
Using Lem. E.9 and the fact that
(()) max(r=(p)s, & mex()lrr(())-((iillaaaa) p(=)1}
< <(|r=(g) r=(p)] + lØ(z) - -p(r))
we obtain that
Ipc 9=111 Σ (lccx)) - P=(x))
Σ (e)r=(1)) (p) + 19(x) - p(x)] pa())rr - -re(0))
Ip 4h
(2 + +5) & lp 4ll
(g)
where the last step uses that eS 1/2 and re (g( > 1.
Finally, we arrive at the sought result, parallel of Lem. A.3. Lemma E.11. For all [N 1]. (x, E X Ax X, and 1 (T); (1'2(x' as defined in (52) with satisfies
51 (z] =.,
1 a) - - a)l <
No (x, + +
Proof. This a direct consequence the definition (52) and Lems. E.5, E.7 and E.
E.2.3. THE ALGORITHM
For E (0, 1), define
S-ANT2
C32 = 1 + 12v5S log
5/2
620
(55)
48
which the leading factor in the confidence bound Lem. E.4. For the purpose of exploration, much like the full information case, we will utilize at each round a bonus reward vector R NSA to be subtracted from the estimated gradient, where
G V mmax(1, (N
(x( = L(N n)
(56)
for (t. n, 1r E [7) x U[N]) x x A.
Finally, with all its components detailed, we present Alg. 3, our first approach for CURL with bandit feedback. As mentioned in Sec. 4,2.1, the main changes compared to Alg. 1 are the use of spherical estimation to obtain surrogate for the gradient and the use of a suitably altered transition kernel estimator.
38

---

Online Episodic Convex Reinforcement Learning
Algorithm 3 Bonus O-MD-CURL (bandit feedback)
input: learning rate т > 0, perturbation rate E (0, 1]. sequence of exploration parameters (as)ettr E (0, 1)a
initialization: Pn [x, a) - 1/5 V(n, x', a), p e arg min for /. = 1,...,T do
NE ((p))
draw w² E SNS(AA1) uniformly at random
Ç - Ap NS(A--) + ku²)
N - (1 (1-6) 10))0++0 6
TH (alxz) - (z, a)/ EneA (x,,00) (x, a)
execute n' and observe F (1= P) and sampled trajectory of == ax)
g' -- NS (1 P''''
construct ÿ' E IR NSA as G. (I, a) - (x, a) for a # a* and 9h (ze a*) -
construct bonus vector b¹ as in (56)
म (a|z) - (1 ( a)/ Eaea 2e (z, a) + a
construct the new estimated kernel g 1 via (51) and (52) set j arg min MeM T (g' - b' 12 + (p, 1tt .F')
end for
E.2.4. AUXILIARY LEMMAS
Lemma E.12. For and pt as defined in (52), it holds that
T N n-1
ΣΣ
uo u (x, a) - Pi < 3C,,NV 2SN2 2T 2T log
N
with probability at least 26.
Proof. This lemma can be proved in the same manner as its full information version Lem. A.1 with only two small changes; we use the bound of Lem. E.4 instead of Lem. B.1 and we modify the definition the filtration to be F, = ouu ...., - _0-=1_ =z)).
Lemma E.13. For any 0 < 6 1,
T N
M " F(z a) max (H
Σ
Σ
(N n Σ
& 3N2 + SN2, 2T log )
holds with probability at least 8.
Proof. The proof is the same as for Lem. A.2 (the version proved in the full information case), except that, again, the filtration used in the proof would be defined as F₂ == o(u', ,.....,, x² r-1 u²).
Proposition E.14. Let and for be as defined in (56) and (52) respectively. Then, for any 5 (0, 1), with probability at least 36,
T
(3C,VSAT+ L 28 / 2og log 8
N
b
Σ
Uo b6) < L
+ LC L 3V 3V LC
+ S S 2T log N
)
Proof. The proof is the same as that of Prop. 3.1 except that we would rely on Lems. E.12 and E.13 in place of Lems. A.I and A.2, and use the definition of if in (56) instead of (11).
39

---

Online Episodic Convex Reinforcement Learning
Lemma E.15. Let X be random variable taking values in R, 21; 22 be two constants, and 8' e (0,1). Xf 22 uniformly and P(X 21) & 8' then [ 21 8'22.
Proof. Simply, [[ F[T(X = [ =
+2 22 21) & 8'22.
B.2.5. REGRET ANALYSIS
The following theorem, restatement of Thm. 4.3, provides a regret bound for Alg. 3. Recall that we have adopted in this section the shorthand notation S | and A = |A].
Theorem E.16. Under Asm. 4.2, Alg. with suitable tuning of T, 6, and (ar) satisfies for any policy π AA that
E [(I 1 A No/3/ + L+1 V
E [[
S A
e
where & signifies that the inequality holds up to factors logarithmic in T, N, S, and A.
Proof. Fixing т E (AA) XXN, we have that
T
E [[R[TT]] =
F (F (1=tor) v)) -- F² (P))))
T
E
> (F' 2) - F² F'( (x))))))) +E
FLl (1=')))
Fd (1T-1')))
+E Σ (F - F((((
It holds with probability at least 1 -
2 that
T
T
1 < L
1
10
11
L
Σ
Pn
pn x x
1=
1=1
N
L.
(x, -1t.aallpp(ttt.) -
1= n= 1-0 a.
x 3LN² / SATC
2LSN 2LSN2 log()
where the first inequality uses the Lipschitz continuity of Ft. the second inequality follows from Lem. B.1, and the last inequality follows from Lem. 12. Hence, since I. D that
-==1 1x" 1²¹ $ & 2NLT, it holds via Lem. E.15 (with 5' = 7
E [ < 3LN / 2LSN (o) + 4LN
(57)
For the third sum, we use again the Lipschitz continuity of F*. Lem. B.I, and Lem. E.4 to get that with probability at least
1
T
T Σ
N Σ
3
1
-
L
t=1
1=
(2 (1,))))
1-
1
T N 1-1
Cip
L
(2,a)
((xx,
T N
Cipr
L Σ E
n)
Σ
F
(x, a) /mx 1, (2
1
2,0
40

---

Online Episodic Convex Reinforcement Learning
Mo, bi)
T
(1 x
14: 1/)
+
Σ
11 11 .b)
[=1
Via Prop. E.14, it holds with probability 1 - T that
no: 1b) & (3C 22
25 27 log(NT))
LC I1 + SV /T (og()
Hence, chaining these last two results and using union bound, we get via Lem. E.15 (with 8' 7) that
E
3 10
1 10 < LC (3C SAT 2 2T log(
LC N3
3v 33 SAT + SV 1V2TT + SLN(1 + GTT,N), (58)
where we have used that
T
1 T - 10
L
1 1 +
16 lo 11 T-0" - 1 2LNT(1 + N.,.
Define ;:: (Axxa) - R.. as
F'(p) EeEgNS(A-1) Ft (11 (111-591- + Sç
As fr satisfies the condition of Asm. 4.2 by design, gu E ME uu = (AxxA) N as argued in App. E.2.1; thus, foe is well-defined. Similarly, since ut SNS(A-1) B NS(--)) and 5¹ qu' it holds that Ç ME No Via the convexity of M jop the fact that μ² e MM and the definition of ft'; it holds that fi' e MM This yields that fi' p " recalling the definition of rt in Alg. 3. Using the Lipschitz smoothness of F`, we have that
F' 56) - F F²((" - (')) = F* - p)p + Sc²) - EPEENSIA-D) [F'(1- 6) + 8C }
< 8LE || - 11 < 28LN
and that
(( - F (( (EERNN(A-D) ['((1 8) + (6 F'
SLE (L - 1 & 26LN.
Hence,
T
Σ F (1+ - -
+ +F'(u') - F' + ) -
V 7f (2'), 11¹ -P=-0>- 48LNT
T
T
(f²' -b', 1p,=² ff - + 48LNT
(b 1r
1
b 1
41

---

Online Episodic Convex Reinforcement Learning
The last term is easily bounded follows:
T
T /0))= =
T <t) <
2 (6' ,²' - 1
bb
bb, k²
>
b 1o0 -c112 < 28
We then conclude that
T 6¹, 1¹ - -= + 48LNT + 280 280 LN (n²)
b 1
1e
<
E
(59)
Then, combining (57), (58), and (59) yields that
T
E [[]([T)]
& E
11'"-1p (n²) - -6",-""- -b.,'² - - + 22 + CI,T
+ 33LL N3 SAT + 2 2T [NT( + 4L + 20/,7-N).
(60)
Define F Fr: (MEr) R 2aasFF F((( = F' (A (E)) and F*(E)= = Fr (Apx Then, recalling that
A-1+VA-1
Fst (Ap' (n")) -p") EUEBNS(A-1)
F' F'((1 8)p² )c"DD')
E EEEENSSA
F'(A7! ((1 5) + oc".0))]
F'((BB)+ ( ((1 5) + 5ç - (P))
E BEENNSAA
(11 - (B²)) 1z (nr - -30) + (((B') + (c - 330))]
= N(A-N)
= E E
F'11 - 6)437((1 (n²) + (A
EEEENSIA
F'((1 - 5) (n²) + 5m11 NS(A-1) + 5k.))
where the fourth equality follows form the fact that Az² (n) = ( 3²') and the last equality follows since 5V = Age (N-INN(AA))) 1S) + RD). Lem. 1 in (Flaxman et al., 2005) and the chain rule imply that
vF 1A755 (n'))
1-6
NS(A A 1)B RegNera-
F' 5) (n²) + 5x1 NS(A-1) + Smsce)e
ōK NS(A - 1) NEBNNAA-
F'((1- F'(11))) (n²) + SAp 5Ap'(("00)) ((")))))
1-
NS(A 1) (CB
1=((1 ((' + Sc 8c"E)Ju yu]
NS(A (ASAA-1)E 1)
[F1 5)1² + 56')
where the last equality uses that 5² = cu' B¹ and that both /² and fr are independent with respect to w'. And since
vF 1f'' (n²)) = (B²) TV (n²), ( we obtain that
(B (B8)) + (VF
1-8 NS(A- - 1) (' 6)p² ((B)((B))))) T uu)
= [
(61)
where
1-6 5 NS 8)p² + 5c
1- 8
g'
8%
8k
42

---

Online Episodic Convex Reinforcement Learning
The vector Ge differs from g' (which is employed in Alg. 3) in that it is defined using F'( instead of F' ('(n"" P). For round & [T], let F+ au" o² 3...., o²) denote the r-algebra generated by the random events up to the end of round t; and let [-11-] == B[- Fi-i] II with Fo being the trivial o-algebra. We then have that
u',
T
E
VF (x'),
p² -
E
(BR* (B8) )B)
(n'), 1² 1 1=--0t
EE [B(((())) { "' n²' -1
E
<((BB) )(118("))()))))) )²) g .1' - 100-8"
E
where the first equality holds via the fact that Bd (Be) (B8))((( (n' - ,,.00) = p¹ - since μ¹¹ --= belongs to the column space of B (see App. E. the second equality uses (61) and the fact that conditioned on F.-1, the only source of randomness in ((BB)) ") is w', which is sampled independently in each round; and the last equality uses the tower rule, linearity of expectation, and the fact that je- n= is measurable with respect to F.-1- Since p¹ n (4²) Agt (uT-D') )), we have that (Q) "(1²- (1²-~~00)
8 (A")
(B') + B (A7' - Ap' (x=")) - (3)) (1)))))=(()7 (17' (n²) A7 (2700)))
since (BD)) + Bed INS(A-1); see App. E.I. Therefore,
E
v P (u'), 1²- - --= E
0 Agd (u²) Agi (1000T))
E
(g', Apt (n²) (1²)
1 )> + E Xgt g", 1, (1²) - 1/t (1000))
t=1
E
( ,1¹
1 E
g - g., A (xt) Apt (1=T)')) ))
where the last equality follows from the definition of jf (see Alg. 3) and the fact that μ² and / 1r are expansions of A (n²) and A A (10.0') respectively, augmented with the entries corresponding to action a*_ Focusing on the second sum, we have that
T g g", ( - 1pt (1xT))
T
(1²)
E
10' g/o A (u²) - Apt (1=00)1
10' golloo lloll - 1 |1,
T
2N
>
11g' g'1loo
8
T
N2
S(A
1) Σ Iu' 10o 1F (2()) F" P)]
4
SAS
F ('(("') F'( sP)]
80
SA
F' (1+ - F ((
4
LN2 >
LN
SA²
1
43

---

Online Episodic Convex Reinforcement Learning
where the fourth inequality uses that x > 24 and that u' e SNS(A-11, and the last inequality uses the Lipschitz continuity of Ft. As shown in (57), we have that
E
< <3N VSATVS 2SN2 V (oN(T) + 4N
Hence,
T
T
4 - 80
(V
- 1
0
E
1
F -
>
LNSSAA(NNSAATCI, + 2SN / (T + 4).
Combining this result with (60) yields that
- 4 INSSA 2SN 27 + +4)
E E|R
(T)
E
g b'
Eδ
t=1
+ 28L(2 + N) + 3LC /LC N3 + 2S 25 4LN + N)
T
< E
5 b" -1- + 12 + NINT +3 2C
1=1
17 LC NT (3N ATC + 2N log NT) +4)
+
(62)
8 E
where the last inequality uses that G/ > VS. Note that
N
1
l
N (1
NS(A
/A
1)F
loo
2ō
2 2 S
N Σ
|
e6"
2 SARNN N
N2
Σ
N
N 2N5/2SA2 |u 1. & Eō
Σ Σ u (x,
2 N33/ =8 =
where the second inequality uses Cauchy-Schware and the last inequality uses that u' NSA--) Moreover, we have that N.N 10 & Σ L(N - w) & LN Hence, using that C² > V5.
I 1,
Ig' - 1
N + LN 50
2 (L 1)C 1/7 V
E6
Via Lems. A.4 and 1,, we can invoke Lem. 2.1 with c 5e, Ç = 3 [L + 1) 1)C C)r VSANN and = 1/(t + 1) to get that (from the proof of Lem. 2.1)
2 (L+
1IC V T+ 20c log(AT)? + +A)
G - b 1 - 11
>
g0
10e2 + eδ (L + D)C 53 S3/2 A7 log(T).
"To invoke Lem. 1,,,, 1, we assume without loss of generality that the constant specified in Asm, 4.2 satisfies & I5
44

---

Online Episodic Convex Reinforcement Learning
Tuning 7 optimally yields that
Σ 0 b" 1 4 1 1..00)
(L
2200SAANNN//22NNNN + log(
Ed
t-1
10e2 + Eō
(L + 1) A2 log(T)
10c2
& (oN AYT VSN)
Hence, plugging back into (62) yields that
| ( + Ea) + 4LN(3 + N)..
E [ <
Setting 8 = min (1,
+u+3a
we get that
E
[ & max 22 +3,) + Es) + 4LN + 20
Consequently, the theorem follows after using the definition of CpPr from Eq. (55) and ignoring log factors.
E.3. Self-Concordant Regularization Approach
We have used the set (M the preimage of Mi under the map Ep (or Ap), to represent in NN the set of valid occupancy measures. A more concise characterization, given by Lem. E.1, that
(Mpb) (E NS(--1) B²C > 3
in other words, (MP
H4o > is a convex polytope formed by the constraints (n,,, x, -. (R > 0 for n, x, e [N] x A' x A. Moreover, Lem. E.2 asserts that int (M the interior of (Mp pg )_ is not empty under Asm. 4.4.
consider then the function vins: int (Mp))) )ー- + R defined as
(E)
Σ a. (, n.z,a
As mentioned in Sec. 4.2.2, Corollary 3.1.1 in (Nemirovski, 2004) yields that eh is a d-self-concordant barrier (see Definition 3.1.1 in Nemirovski, 2004) for (Mp,)) with 0 = N 5 A. The approach we analyze here is to perform OMD directly on the set (MP.)) with thm as the regularizer.
For & int (MP)) and y I NSA-1), define the local norm llvlle == (e) This is indeed a norm since the fact that (Mp, pg ) is bounded implies via Property II in (Nemirovski, 2004, Section 2.2) that the Hessian of the is non-singular everywhere. Its dual norm is denoted as ||y|le, / (V)) The Dikin ellipsoid of radius at int (MP, given by
(E) = ty N SSA-1), 1y Ele < r( V v/n 4/B NS(A-1)
Via Property I in (Nemirovski, 2004, Section 2.2), (E{ _ (ME.) for any & int (Mp,)
For E.y E int )M we denote by Dw (y. {) Vns(y) - ()n(E)) ( &, Vehn ( the Bregman divergence between y and with respect e'1.. From the proof of Thm. E. we recall the definition F = 1ett Ap. As alluded above, our OMD updates will take the form
g++] - arg min J (g',E) + Din (E.5'),
<E(M),,)
where g will be chosen as a surrogate for (IF. Differently from the proof of Thm. E. 16, we redefine the smoothed approximation f (Mr.) IR such that
F (E) BEBBNIIA
F't FF1(1 (1-5)) + 5(5' + (V2 -v2
45

---

Online Episodic Convex Reinforcement Learning
a
8a + 60
6
8b + 80
dc + d0
Figure 4.
This figure provides graphical comparison between the sampling approach used in Alg. 3, represented on the left, and that used Alg, 4, represented on right. The simplified domain here (æ: E [0. 1] |a/]| & 1}. Both approaches are illustrated at three points: a, b, and In the first approach, with some 5 E (0, 1) and 1 6, sample from circle of radius 8/(2 + v2) centered at convex combination between the point of interest and == (1/(2 2). 1/(2 + 22)). In the second approach, we consider barrier - -oog(1 x2) 1,2 log(z;) and sample from the Dikin ellipsoid (of certain common radius) induced hy this function each point.
This is well-defined since we are evaluating F' on convex combination of the argument and point inside the ellipsoid E (g*), which is subset of (MP) as cited before. Via Corollary 6.8 in (Hazan et al., 2016) and the chain rule, we have that
(1-6) NS(A - 1) BeesSsccn [F' ((1 8){ + 8(5' + (V² (V) 5
(63)
Hence, with u' sampled uniformly from NSA-11)) we pick (as mentioned in Sec. 4.2.2)
g' (1 (1-6) NS NS-AN 1)F (g' + (
(64)
5
such that Eu [ = (E'( see also (Saha & Tewari, 201 1) for a similar estimator in another BCO setting. We summarize this approach in Alg. 4, and provide in Fig. 4 graphical comparison with the sampling approach of Alg. on a simple decision set. Before proving the regret bound of Thm. 4.5, we collect few standard properties and auxiliary results concerning self-concordant barriers and their use regularizers.
1. AUXILIARY LEMMAS
For y int (Mp )_, it holds via Property I in (Nemirovski, 2004, Section 2.2) that
)
1
(1 - 2 (m))
Vin(v)
(65)
whenever [ly =l. 1. We state the following auxiliary lemma, which will be used to assert the proximity between Ç and gt+1 for our algorithm. Establishing this 'stability' is crucial step in the local norm analysis. Lemma E.17. Let x E (MP))- and TR NSA-1) be such that |e]l t.s and define
y >= arg min (e + (2)
çein (M)gg)
Then, y (x))
46

---

Online Episodic Convex Reinforcement Learning
Algorithm 4 Bandit O-MD-CURL with logarithmic barrier regularization
input: domain pM J with non-empty interior, learning rate т > 0, exploration parameter 6 E (0, 1]
initialization: ç² + arg mini (Mgg)- 4/n
for t = 1,..., do draw u' E (N((111) uniformly at random
@ - 5º +
w/22
7 + Ap(Et)
प. (a/z)) - (x, a)/ EneA fi' (2, a)
output n' and observe F* (At)
g' - - NS(A - 1) (T') thao (lo() (5 g++1 - arg mingaeim (MBg) T (5' + (5.5))
end for
Proof. For int (Mpb)) ). let
g(E) = (L.E)+ (E,(E,)) = (l + (E)(E) (n(()) - (E - x, Vahn(z)).
Note that g is a self-concordant function on int (M) (Item (ii) in Nemirovski, 2004, Proposition 2.1.1), whose Hessian (hence, local norms and Dikin ellipsoids) coincides with that of th everywhere. Moreover, y is below bounded thanks to (MPio) being bounded set, which implies that g attains its minimum on int (My)) (Property VI in Nemirovski, 2004, Section 2.2). This minimum is also unique via striet convexity. Hence, y well-defined.
The rest of the proof is similar to the proof of Lem. 13 in (Wei & Luo, 2018) and Lem. 9 in (Van der Hoeven et al., 2023). Thanks to the strict convexity of g. to show that y Exy(2) it suffices to show that for any & on the boundary of (x), g(x) & ((E); this is because a E (2) and arg ge 9(E). For any such & on the boundary of (y)( Taylor's 's theorem implies that there exists some 2 on the line segment between x and & such that
s(E) - = (E x, Vg(z)) ( =)T x)
1
= <E x. 1) (5 1) v x)
2
1
3 -5- - x, () + (5 - 1) 1 (z) - x)
8
= (E - x, 1) + Iks - x12
- 16 ==|=||e|1
+ $11 1k - x01
1 2 11 x, +
1
3 0,
32
where the second equality holds since v2g = 2/ and Vg(x)) = + Vvb((>) Vvha(z)= = e, the first inequality holds via (65) and the fact that 2 e (z), the second inequality holds via the definition of dual norm, the last equality holds
since & is on the boundary of (z), and the last inequality holds via the assumption that [[|| < 1
I6
For & E int (Mp,)) , the Minkowski function of (MP php) ) with the pole at æ is defined as (Nemirovski, 2004, Section 3.2)
T,
T (v) == inf > 0: -y x) (MP.)
for y e (M.)) The following lemma readily follows from the properties of the Minkowski function. is used in the analysis to handle the bias term of the standard OMD regret guarantee, which is slightly more involved in this case considering that the comparator need not belong to the interior of (MP, where tho is defined (and finite).
47

---

satisfies for Online Episodic Convex Reinforcement Learning
Lemma E.18. Let x inl (M y (M ô (0,1), and (1-8)9 òx. Then, 4/6(2) & (2)(2)) + NSA log
Further, let à := arg minl zeint (M (x) and 2 == (1 8)y d2. Then,
(2, & NSglog
Proof. Since th is A-fff-oocnn barrier for Mi. Property II in (Nemirovski, 2004, Section 3.2) implies that
1
v/n(2) & v)n(()) NSA log 1- (2)))
On the other hand,
x) x (1- 5)- (1 (1-5)-1(22 5)-
-5yy + 5x - x) x y- x y (MPo))
implying that n. (2) 1. Hence, (2) vx)( + Aog Next, we note that the optimality of 2 implies that
D sh (2) v/n(2)) (3) (2 I. Vvli(i)) 1/1(3)) (i:),
which concludes the proof when combined with the first part.
E.3.2. REGRET ANALYSIS
We are now ready to prove the regret bound of Thm. 4.5, which is stated more explicitly in the following theorem.
Theorem E.19. Under Asm. 4.4, Alg. 4 with any policy E Il that
log T S and 8 min
g3/4
ga/4
/3/4 (log T/
16 V
T74
B [[R((T]] & max 4v IVLNTTT/ (SAT))*
3/4 (log 34,
2LN
Proof. Firstly, we assert that the iterates çx are well defined; similar what argued in the proof of Lem. E.17, the functions (-n(.) and 7 (g',>) + Denl: (::5)) are self-concordant int (MP. ) (Item (ii) in Nemirovski, 2004, Proposition 2.1.1) and bounded from below thanks to (M ) being bounded set, implying via Property VI in (Nemirovski, 2004, Section 2.2) that each of these functions attains its minimum on int [Mp.)] ) which is also unique via strict convexity. Also note that indeed f Mp, since ČL e (Mp, pm ) as we argued before presenting the algorithm.
Let n* arg min peMp, Σy (H) and Pr E EYT (F -)- () (p*))) which satisfies Pr m [Re (T)
Define g* (1 (n*) det, where å (0, is a constant be specified later. To start with, have that
T
T F² (Ap''x") (x'4)))))
R = E
Σ FL -
E Σ (F'("') (²(x)) = (F
Next, we derive that
F'(C") - F'((")
= F (5t +
1122x²) - EMERNSCA-1)
F''(' + 5( + (V
LE LE 13 || Ap 8(V3 -1/2 Ap + 5(V w/o ()) -1/2 ||,
= SLE Ap A ( (V>cbn(E))) 1/2 1/224) - Ap (VV ((V2))) -1 1/20)|11
ST.. //| Ap + 2ha (5))) -1/2 Ap
48

---

Online Episodic Convex Reinforcement Learning
ÖLE
|| + (V2 (V(N)())))) |A, + (V>Dm(E))) +VV'))(E))~1))) [1]
2
where the first inequality uses the Lipschitz smoothness of F and the fact that F F² Api the second and third equalities use the fact that Ap is an affine function; and the last inequality holds since both 5 + and that for any & (MP)) (p((5) E Ma and therefore satisfies AAp(4)l & N.
11/2,,, 5t +
(n(")) 11/20 (5t) = (Mpp) and
We similarly derive that
(E())) I² (A, (x*)) (A))
(CE3
F" ((1 - 8)5" + 5(5' (V (z²)
PEEBNS(A-
F' ((1 (01--8]0 6)(1 -0)
(n*) - 8))5 5(5' + (V -=)
FF' (A, (A²'(x))
LEPERNS(A-1)
(1 - 6)(1 -61u² + (1 ,) 5A, (V> 4/) 1= ||
- 11.] |50 ||||0 (1 5) 3 + A + (mn (60))
LE DE 1)
(8 (5+5))14 8)1 + || 6 + (b2)) (-))))>))>>> 111
28LN + 28LN.
Hence, using also the convexity of 1 obtain that
RT E (F"()) -T((E)) + 45LNT 28LNT
E Σ
5*> 48LNT + 28LNT
(66)
In this proof, let F, := au" ...,,.., w²) denote the r-algebra generated by u',..., u and let E. := [.[ Ft-1] with Fo being the trivial o-algebra. We then have that
- Eu [o = Ex [g'].
where the first equality follows from (63) and the the second equality holds since conditioned on Fi-1, u² is the only source of randomness in g and is sampled identically and independently in every round. Using that ç - 5 is measurable with respect to Fi-1, we then obtain that
T Σ
RT & EE
< g - + 48LNT 28LNT = E
(g' -*)
+ 48LNT + 28LNT.
Via the definition of EL and the fact that E int (MP)) Lem. 6.16 in (Orabona, 2019) implies that
T Ko' et - =+) & (5 (
T
Σ
+
where Ç¹ lies the line segment between Ex and gl+1, We firstly observe that
(1 8) NS(A - 1)
19g 1012
(u')
((V2ro0E))))
8
(1 8) NS(A - 1) ()*)
2
1
N452AA
& 82
8
where we have used that F*(("))) < N. Hence, if
5 16N28A
(67)
49

---

Online Episodic Convex Reinforcement Learning
then rllgelles, $ 1/16. Consequently, Lem. E.17 (with f y -gtt,, and & Tgi) would assert that e E Ey, and hence, 5" (t)) It would then hold via (65) that
1
Ileelle & 411g
(1
On the other hand, via Lem. E.18 and the definitions of g¹ and g*, we have that
Den (5 ( NSA Hence, conditioned on (67), we obtain the following regret bound
NSAlog 8
25 82
RT
N 48LNT 20LNT.
(68)
Setting
log T
17 N3/4
3 ( T) T)1/4 T1/4
8
T=
16 V
N3SAT and 8 8=min
min (V 4L
T
we obtain that
R1 Ng 2T N 48LNT + 2LN
17
53 log T 48LNT + 2LN
max 4V177N (SAT) 3/4 (log T) 1/4 34v N3 + 2LN
(69)
IT > NogllogT)), then our choice of indeed satisfies (67):
5 log T
5 16N2SA
16
N
Otherwise, we can fall back the trivial regret bound
Rr & NT N2
which is dominated by the bound in (69); hence, the theorem follows.
50


Reviews:
[{"review_id": "YX3QrUvcBK", "reviewer": "Reviewer_mGhi", "summary": "The paper proposes a mirror descent algorithm (with exploration bonuses) for achieving sub-linear regret in concave utility RL in an online episodic and adversarial setting. The authors first propose an algorithm designed for full-feedback over adversarial losses, achieving sub-linear regret. Then, they propose two algorithms for the bandit feedback and adversarial losses, achieving sub-linear regret under some assumptions of the convex MDP, but less restrictive ones related to previous works ( model of the dynamics assumed to be known, out of additive noise [Moreno et al 2024]). Finally, the authors test the most scalable algorithm (in terms of assumptions required for sub-linear regret) against one by Moreno, showing better performances in terms of losses and regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. We address the raised concerns below.\n\n- **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.\n\n- **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?\n\n- **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.\n\n- **Questions:**\n    - **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.\n    - **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).\n    - **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. \n\n- **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.\nRegarding 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.", "claims_and_evidence": "Yes. The claims are supported by proofs and empirical corroboration.", "methods_and_evaluation_criteria": "Yes, the authors selected a relevant empirical scenario already considered in the most related work in the literature.", "theoretical_claims": "Yes, I checked the soundness of the steps in the main paper.", "experimental_designs_or_analyses": "Yes, all of the experiments in section 5. Unfortunately, I was not able to find a comment on how the regret was actually computed (with respect to which policy). Also, I was not able to find a discussion on why Moreno et al. 2024's algorithm fails miserably in Fig.3 even though I would say it is not expected to. Finally, I am curious about some performances  in Fig.2 (see Questions).", "relation_to_broader_scientific_literature": "This is the first paper addressing online episodic RL with concave (adversarial) utilities without strong assumptions on the model of the cMDP but guaranteeing sub-linear regret.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "Strengths:\n- Generally extremely well written and rigorous.\n- Relevant contribution for the field.\n\nWeaknesses:\n- Some text re-formatting might help the reader in following the proof outlined in the main paper.\n- Original contributions in proof techniques and/or algorithmic tools (in terms of bonuses) might be made more explicit. \n- Assumptions needed for sub-linearity could be made way more explicit, even in the introduction.", "other_comments_or_suggestions": "- I would suggest to find some space for some concluding comments.\n- I would suggest to comment on the failure modes of Moreno's Algorithm in Fig.3.\n- I would suggest to make what assumptions are make throughout the paper more explicit in the introduction.", "questions_for_authors": "- Does Alg. 4 require to know the MDP? It is stated but not written particularly explicitly. I would definitely suggest to make this fact explicit even in the introduction in case this Is the case.\n- What is $\\xi$ in Eq. 9? Did I miss it in the previous parts?\n- How is the regret computed?\n- Why in Fig. 2 Moreno's algorithm show loss minimisation similar to the most recent algorithm but regret far worse?", "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": "YWXgkXfOxm", "reviewer": "Reviewer_5Sqt", "summary": "This paper studies the setting of online RL with concave utility function. This paper analyze two settings: \n1. When the learner receive the full information of the utility function at each step.\n2. When the learner only receive bandit feedback at each step.\nAt the first setting, the learner propose an FTRL-type algorithm, and proved that the regret is bounded by \\sqrt{T} for tabular MDP case. For the second setting, the authors consider the bandit feedback, where they obtained regret upper bound for unknown MDP but with a lower bound on the transition probability, or known MDP without the assumption. Both the regret bounds are $T^{3/4}$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. We address the raised concerns below.\n\n- **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.\n\n- **Bandit feedback:** The adversarial convex RL setting is not equivalent to adversarial MDPs with the standard (linear) RL objective.\n    Under bandit feedback, we indeed show that in the latter setting (standard linear RL), our method achieves $\\sqrt{T}$ regret (see Thm. 4.1). \n    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).\n    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. \n\n    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).\n    On the contrary, we adopt more common and foundational techniques (building upon works such as Flaxman et al., 2005 and Saha and Tewari, 2011)\n    that though only capable of achieving $T^{3/4}$ regret in our setting (Hu et al., 2016),\n    are arguably more practical, less complicated, and enjoy better dimension dependence. \n    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.\n    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.\n   \n- **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).\n    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.\n\n- **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 \nbecause it is not strongly tied to the structure of the loss function.\n\n*Neu et al., 2010, Online Markov decision processes under bandit feedback, NeurIPS*", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked the proof of some of the theorems, e.g. Theorem 3.2 and Theorem 4.1.", "experimental_designs_or_analyses": "Yes, the experiment setting seems to be sound to me.", "relation_to_broader_scientific_literature": "This paper improves from previous literatures, as they come up with an algorithm which works for concave utility function.", "essential_references_not_discussed": "No, as far as I known.", "other_strengths_and_weaknesses": "This paper has the following strengths and weaknesses:\n\nStrengths:\n1. The setting of concave utility function for RL is interesting to me. \n2. This paper is well-written.\n\nWeaknesses:\n1. This paper only considers the tabular RL case, which is restrictive. It will be better if the results can be generalized into more general setting, e.g. linear MDP or MDP with function approximation.\n2. The regret bound for bandit feedback to suboptimal. This setting is equivalent to the setting of adversarial MDP, where we know the optimal regret is $O(\\sqrt{T})$, without any additional assumptions. \n3. The algorithms and analysis in this paper are very similar to the FTRL and its analysis, except in the MDP setting. The novelty of the results in this paper is limited.", "other_comments_or_suggestions": "I do not have further comments or suggestions.", "questions_for_authors": "I have the following questions for the author:\n1. A common belief in convex optimization is that the curvature of the loss function could help reducing the regret. Can you improve the results from $O(\\sqrt{T}$ to sharper regret bound, if we assume some curvature of the loss function, e.g. if the loss function is quadratic?", "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": "f1KWegIl1k", "reviewer": "Reviewer_vsjZ", "summary": "This paper addresses online convex RL, a generalization of RL in which the loss is a convex/concave function of the state-action occupancy, with adversarial losses and unknown transitions. In the setting with full feedback, i.e., the loss function is revealed to the agent at the end of the episode, the paper provides an optimistic bonus-based online mirror descent algorithm achieving $O (\\sqrt{T})$ regret. Then, the paper studies variants of the algorithm for the bandit feedback setting, in which the loss function is only revealed for the visited state-action pairs. In this (more challenging) setting, the paper shows nearly optimal regret for linear loss (akin to adversarial MDP) and $O (T^{2/3})$ for convex/concave loss.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. We address the raised concerns below.\n- **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.\n\n- **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.\n\n- **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.\n\n- **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.\n\n- **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.\nTo 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.\nTo 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.\n\n- **Questions:**\n  - 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. \n  - 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. \n\n         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.\n  - 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.\n  - 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.\n  - 5. The policy $\\pi $ is the comparator strategy in the regret (see Eq.(5)).\n  - 6. We agree with the reviewer and leave this question for future work (see also answer to Question 1 of reviewer 5Sqt).", "claims_and_evidence": "Mostly yes, but the wording of a couple of claims could be improved:\n- While the paper has a point on providing the first near-optimal regret for this particular online CURL setting, it could do more to acknowledge that previous work studied online CURL (e.g., in a pure exploration PAC setting in Zahavy et al. 2021 or with assumptions on transitions in Moreno et al. 2024) and also regret minimization in a \"trajectory version\" of CURL (Chatterji et al. 2022, Mutti et al. 2023). Perhaps the tile/abstract could mention more clearly that this is the first study of CURL regret with adversarial losses and general transitions;\n- The near-optimality of the regret is also partially misleading. An algorithm with additional $\\sqrt{|X|}$ factor would not be considered nearly matching in standard RL and the claim that the latter is necessary for convex utilities (line 260) is not supported.\n\n(Chatterji et al. 2022) \"On the theory of reinforcement learning with once-per-episode feedback\"", "methods_and_evaluation_criteria": "Regret minimization is widely accepted as an evaluation metric for online RL settings.", "theoretical_claims": "I did not check any proof in the appendix, so the derivations have not been closely inspected other than the high-level considerations on the techniques reported in the main text. While a further inspection of those may be useful, the techniques seem to be generally standard and the results reasonable for the considered settings.", "experimental_designs_or_analyses": "The paper reports a brief empirical validation, although the validated results do not fully match the theoretical setting (e.g., adversarial losses).", "relation_to_broader_scientific_literature": "This paper fits into a stream of works in convex utility reinforcement learning (Hazan et al. 2019, Zhang et al. 2020, Zahavy et al. 2021, Geist et al. 2022...) that generalize the standard RL setting to convex loss functions.\nWithin this area, it mostly builds upon Moreno et al. 2024, which also studies an online mirror descent algorithm in a similar setting but deals with transitions forced to a (less general) structure and only covers full-feedback setting. On a technical level, the extension require the design of optimistic bonuses for exploration (as it is common in online RL with unknown transitions) and borrowing techniques from bandit convex optimization for the bandit-feedback setting.", "essential_references_not_discussed": "A stream of work that is closely related but (almost) not discussed is the one on trajectory-based CURL, such as (Chatterji et al. 2022, Mutti et al. 2022 and 2023) and submodular RL (Prajapat et al. 2023 \"Submodular reinforcement learning\" and De Santi et al. 2024 \"Global reinforcement learning: Beyond linear and convex rewards via submodular semi-gradient methods\"). I think the paper could do more to relate their findings to these works.", "other_strengths_and_weaknesses": "Strengths\n- Interesting results that seem to place CURL in the same ballpark of RL statistically, in terms of regret and methodologies, also with adversarial losses;\n- The paper reads well and significant space is devoted to an overview of technical problems and how to overcome them.\n\nWeaknesses\n- While CURL counts several recent studies, the paper could do more to motivate the specific setting addressed, perhaps with potential applications. The formulation of the objective looks somewhat odd (see below).\n- Techniques are mostly incremental, especially w.r.t. to Moreno et al. 2024;\n- The presentation could be streamlined to give more breath between implications of the reported results and technical challenges to obtain them.", "other_comments_or_suggestions": "The paper is interesting overall, and while the technical novelty is limited, it still covers some important aspects of CURL that seem to be missing from previous works. I think the paper gives a net positive contribution and shall be accepted ideally, but with the given bandwidth constraints there might be more deserving papers for the limited spots. I report below some comments, suggestions on how the paper could further be improved, and questions.\n\nFORMULATION\n\nThe formulation of the problem is somewhat odd. From my understanding, the agent receives a feedback at each step that is a convex/concave function of the state-action occupancy induced by the policy at that step. Thus, the feedback seems to be independent from the realization (given the policy). While this formulation might be easier to motivate in the offline CURL setting, I am wondering when it is justified in online CURL. This has been touched upon in Mutti et al. 2023 with the trajectory-based CURL formulation. While the latter is mentioned briefly in the paper, the justification for adopting the state-action occupancy version (\"To align with prior work, we adopt the classic CURL formulation\") is rather weak. Perhaps a stronger motivation would be to show that the trajectory version cannot be solved efficiently, and to see the occupancy version as a relaxation? I owuld be happy to hear more from the authors on this point of the motivation of CURL.\n\nPRESENTATION\n\nThis is a nice technical work. However, I think the presentation would benefit from a more focused discussion of the results that focuses on fundamental questions (e.g., is CURL harder than RL? Does online CURL require different approaches w.r.t. online RL?) and leave technical aspects for the second part of the paper.", "questions_for_authors": "1) Can the authors comment on the computational tractability of the presented algorithm?\n\n2) Any algorithmic idea to take home for practice? This does not look dissimilar from Hazan et al. FW algorithm in nature, with the addition of count-based optimistic bonuses. However, count-based methods may not be widely employed in practice, e.g., for the same reasons they are not widely adopted in deep RL.\n\n3) What does it mean stochastic/adversarial feedback in the CURL setting? The loss function appears to be always deterministic...\n\n4) What is the point of showing bandit feedback in RL? This result shall not be new in the literature. Perhaps the idea is to see whether the general algorithm is nearly optimal also for the important RL sub-case?\n\n5) The statements of the regret theorems report \"For any policy $\\pi \\in \\Pi$\" and then they show the regret. What does this mean exactly? Is not the policy chosen by the algorithm?\n\n6) The paper analyzes CURL with a generic concave/convex loss (or sometimes linear). Another interesting aspect is to study whether specific form of the loss (e.g. entropy of the occupancy) can lead to better specialized results.", "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": "nzRIVIwSHa", "reviewer": "Reviewer_1pSC", "summary": "This paper studies online learning in episodic finite-horizon Markov Decision Processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. CURL generalizes RL by applying convex losses to state-action distributions induced by policies, rather than just linear losses. The paper's primary contributions are: \n\n  (1) introducing the first algorithm achieving near-optimal O(√T) regret bounds for online CURL without prior knowledge of transition dynamics, using online mirror descent with varying constraint sets and exploration bonuses\n\n  (2) addressing a bandit version of CURL where feedback is only the value of the objective function on the state-action distribution, achieving sublinear regret by adapting techniques from bandit convex optimization.\n\nThe authors develop theoretical guarantees for different feedback settings and provide empirical validation on multi-objective and constrained MDP tasks, demonstrating that the proposed approach outperforms previous methods on tasks requiring exploration.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their long and detailed review. We address below the raised concerns.\n- **References:**\n    - **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. \n\n    - **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. \n       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.\n\n    - **Neu et al (2012/2013):** These two works do *not* use bandit convex optimization (BCO) approaches.\n        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). \n- **Motivation:** We list some motivation applications below that we will add to the final version of the paper.\n    - **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.\n\n    - **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.\n- **Questions:**\n    - Computational complexity: See question 1 of reviewer vsjZ.\n\n    - 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.\n\n    - Improved regret bound for bandit CURL: Please see our response to Reviewer 5Sqt regarding bandit feedback.\n\n    - 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.\n\n    - 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.\n    \n*Coffman et al. 2023, A unified framework for coordination of thermostatically controlled loads, Automatica*", "claims_and_evidence": "The claims in this paper are generally well-supported by theoretical analysis and empirical evidence:\n* The claim that the proposed algorithm achieves O(√T) regret for online CURL with full-information feedback and unknown transition dynamics is well-supported by Theorem 3.2, with detailed proof involving exploration bonuses and regret decomposition.\n* The claims regarding sublinear regret for bandit feedback settings are supported by Theorems 4.1, 4.3, and 4.5, each with comprehensive theoretical analyses for different scenarios.\n* The claim that the proposed approach outperforms previous methods (specifically Greedy MD-CURL) on tasks requiring exploration is supported by experimental results in Section 5, showing clear performance improvements on multi-objective and constrained MDP tasks.\n\nThe assumptions made for the bandit feedback setting (particularly Assumption 4.2) might be restrictive in some real-world scenarios, though the authors acknowledge this limitation and provide an alternative approach with a less restrictive assumption (4.4) for known MDPs.\n\nHowever, I find the paper's novelty claims overstated (see \"Essential References Not Discussed\" section for more details):\n* The claim of being the \"first method achieving sub-linear regret for online CURL with adversarial losses and unknown transition kernels\" appears to be incorrect given Rosenberg & Mansour's prior work.\n* The technical approach of using exploration bonuses with mirror descent builds more incrementally on prior work than suggested, particularly on Jin et al. (2020).\n* The adaptation of bandit convex optimization techniques to the MDP setting has precedents in earlier work by Neu et al. (2012/2013).", "methods_and_evaluation_criteria": "The proposed methods are appropriate for the problem. The authors use online mirror descent with exploration bonuses to handle the exploration-exploitation tradeoff in the unknown dynamics setting. The regret analysis is thorough and establishes strong theoretical guarantees.\n\nThe evaluation consists of:\n* Theoretical bounds on regret for different feedback settings\n* Empirical comparison of the proposed algorithm (Bonus O-MD-CURL) with Greedy MD-CURL on multi-objective and constrained MDP tasks\n\nThe benchmark tasks chosen for evaluation are reasonable examples of CURL problems. However, the empirical evaluation has limitations:\n* The experiments focus only on fixed objective functions and probability kernels, not adversarial settings\n* The authors acknowledge challenges in implementing adversarial and bandit MDPs\n* The state space used (11×11 grid world) is relatively small\n\nDespite these limitations, I think the evaluation criteria are reasonable given the primarily theoretical focus of the paper, and the results do support the key benefit of this approach: better exploration leading to improved performance. However, it’s worth emphasizing that more robust, larger-scale experiments would strengthen practical confidence.", "theoretical_claims": "The theoretical claims and proofs appear to be sound. The key theoretical innovations include:\n* Carefully designed exploration bonuses added to the sub-gradient of the objective function\n* Decomposition of regret terms to handle the exploration-exploitation dilemma\n* Adaptation of bandit convex optimization techniques to the MDP setting\n\nThe proofs follow a logical structure and build upon established results in online learning, reinforcement learning, and convex optimization. The authors extend Lemma 2.1 from previous work to handle sequences of bounded vectors and smoothly varying transitions.\n\nFor bandit feedback settings, the analysis becomes more complex due to the constraint set structure and transition kernel uncertainty. The authors introduce two approaches (entropic regularization and self-concordant regularization) with different assumptions and guarantees.\n\nAssumption 4.2 (requiring minimum probability for all state transitions) may be restrictive in practical scenarios, which the authors acknowledge and provide an alternative approach with Assumption 4.4 for known MDPs.", "experimental_designs_or_analyses": "The experimental evaluation supports the theoretical claims but is somewhat limited. The authors evaluate Bonus O-MD-CURL against Greedy MD-CURL on multi-objective optimization and constrained MDPs.\n\nStrengths of the experimental design:\n* As far as I understand, the tasks are meaningful and good examples of CURL problems\n* The visual representations of state distributions clearly demonstrate the benefit of exploration bonuses\n* The regret/loss curves show consistent improvement over the baseline method\n\nLimitations I identified:\n* Experiments use fixed objective functions and probability kernels, not adversarial settings\n* Only one environment (11×11 grid world) is used\n* Only one baseline method (Greedy MD-CURL) is compared against\n* Limited number of iterations (1000) and repetitions (5)\n\nGiven the primarily theoretical nature of the paper, the experiments provide reasonable evidence for the benefit of the proposed approach. However, as mentioned above, more extensive empirical validation would strengthen the paper more.", "relation_to_broader_scientific_literature": "The paper is well-positioned within the literature on RL, convex optimization, and online learning. The authors provide a thorough discussion of related work:\n\n* For offline CURL, they discuss work by Zhang et al. (2020, 2021), Barakat et al. (2023), Zahavy et al. (2021), Geist et al. (2022), Moreno et al. (2024), and Mutti et al. (2023a, 2023b).\n* For online CURL, they identify Greedy MD-CURL from Moreno et al. (2024) as the only existing regret minimization algorithm for online CURL, explaining its limitations which the proposed work addresses.\n* For RL approaches, they discuss model-optimistic methods (UCRL), value-optimistic methods (UCB-VI), and policy-optimization methods, explaining how the proposed approach differs.\n\nTable 1 comprehensively compares  the proposed method to SOTA approaches, highlighting the contributions in achieving optimal regret, supporting CURL, providing closed-form solutions, incorporating exploration, avoiding model assumptions, handling adversarial losses, and supporting bandit feedback.", "essential_references_not_discussed": "Although all papers below are referenced, there are a few crucial points that I believe significantly impact this work's novelty claims:\n\n* Rosenberg & Mansour (2019) - This is potentially an important oversight. This paper pioneered online convex MDP methods under adversarial losses with unknown dynamics using UC-O-REPS (an OMD approach over occupancy measures) achieving Õ(√T) regret for convex performance criteria. This directly contradicts the paper's claim of being \"the first algorithm achieving near-optimal regret bounds for online CURL with adversarial losses and unknown transition kernels.\"\n* Neu et al. (2012/2013) - These earlier works had already adapted online convex optimization tools to MDPs with unknown transitions. Their Follow-the-Perturbed-Optimistic-Policy algorithm and O-REPS (entropy-regularized mirror descent) approaches achieved Õ(√T) regret in adversarial MDPs, establishing that bandit convex optimization methods can be successfully applied to reinforcement learning.\n* Jin et al. (2020) - While cited in the paper, this contribution seems also not fully acknowledged. This paper already incorporated exploration bonuses into mirror-descent policy updates to achieve Õ(√T) regret for adversarial MDPs with bandit losses, meaning the idea of adding exploration bonuses to mirror-descent RL methods was already established.", "other_strengths_and_weaknesses": "The main strengths I identified are as follows:\n1. The paper introduces a novel approach to handle exploration-exploitation in online CURL with unknown dynamics using exploration bonuses in the gradient.\n2. The theoretical analysis is comprehensive, covering multiple feedback settings with carefully derived regret bounds.\n3. The proposed algorithm has a closed-form solution, making it practical for implementation.\n4. The approach addresses a general class of problems with potential applications in pure exploration, imitation learning, mean-field control, and risk-averse RL.\n5. The paper is well-written with clear explanations of complex concepts, which is impressive for such a topic in my opinion.\n\nThat being said, I also identified a few weaknesses, some of them important:\n1. Insufficient acknowledgment of prior work that directly addresses similar problems using similar techniques.\n2. Overstated novelty claims that could mislead readers about the paper's contributions relative to the existing literature.\n3. Limited discussion of real-world impact and potential applications. Despite CURL representing a significant generalization of RL that could potentially address numerous practical challenges, the paper provides very little context about:\n   * Why readers should care about convex objectives versus linear ones\n   * What real-world problems become tractable with these algorithms\n   * How the algorithms compare with existing approaches for specific applications like risk-averse RL, imitation learning, or exploration\n   * The trade-offs involved in using convex objectives.\n   I understand that the quality of this work is already high and there is a lot to say so the authors likely chose to save space from a discussion, but I think that this is a missed opportunity to connect the very interesting theoretical results to practical impact. The paper would be strengthened by having a short discussion paragraph including perhaps examples of how CURL can better capture real-world requirements than standard RL, or case studies demonstrating problems where the convex formulation enables solutions that weren't previously possible. Without this context, readers may struggle to appreciate the full significance of the contribution beyond its theoretical merits.\n4. Limited empirical validation restricted to specific tasks with fixed objective functions and probability kernels.\n5. Lack of discussion on scalability to large state and action spaces.\n6. The bandit CURL setting only achieves O(T^(3/4)) regret rather than the optimal O(√T).\n7. The paper acknowledges implementation challenges for adversarial and bandit MDPs, limiting practical applicability.\n\n\nAll things considered, in its current form, I'm a bit torn on how to rate this paper. On the one hand, it is a technically sound work with thorough mathematical analysis, it provides closed-form solutions that are practically implementable and successfully extends techniques to the CURL setting. However, on the other hand, I think as I mentioned that novelty claims are overstated and it is positioned as revolutionary rather than incremental.\n\nHence, I am currently rating it as 3 (weak accept) and I'm willing to move this rating either way depending on the author's response. If the authors addressed my citation and novelty concerns, either by explaining why I might be wrong or by providing proper context for the proposed work and accurately positioning it within the literature, I would be very happy to change my rating to accept.", "other_comments_or_suggestions": "Some final comments/suggestions:\n* Ablation studies to isolate the impact of different components (particularly exploration bonuses) would provide more insight.\n* Comparing with additional baselines beyond Greedy MD-CURL would also be beneficial in evaluation.\n* A more detailed analysis of computational complexity would help assess practical applicability.\n* Discussion of potential extensions to function approximation or continuous state/action spaces would enhance impact.\n* Examples of practical applications in areas like multi-objective optimization or risk-averse RL would also be nice to demonstrate relevance.", "questions_for_authors": "- How does the performance of your algorithm scale with the size of the state and action spaces? The theoretical bounds include factors of |X| and |A|, but do you have empirical insights into performance on larger environments?\n- In Section 4.2.2, you restrict the self-concordant regularization method to known MDPs. Do you see a path toward extending this approach to unknown MDPs, and what are the key technical challenges?\n- The regret bound for bandit CURL is O(T^(3/4)) rather than the optimal O(√T). Do you believe this is a fundamental limitation of the problem setting, or is it possible to achieve O(√T) regret for bandit CURL with unknown dynamics?\n- How sensitive is the performance of your algorithm to the choice of exploration bonuses? Have you experimented with alternative forms of bonuses, and if so, how do they compare?\n- Have you applied your algorithm to any specific problem settings mentioned as potential applications (pure exploration, imitation learning, etc.) beyond the grid world examples? If so, what insights did you gain?\n- How does your work specifically advance beyond Rosenberg & Mansour (2019), which already achieved Õ(√T) regret for convex performance criteria in MDPs with unknown dynamics?\n- Your exploration bonus approach bears similarities to Jin et al. (2020)'s method of incorporating confidence-bound bonuses in mirror descent. Could you clarify the technical differences and innovations in your approach compared to theirs?\n- The paper claims to be the first to address bandit feedback in CURL, but how does your approach technically differ from earlier works by Neu et al. (2012/2013) that adapted bandit convex optimization to reinforcement learning?", "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:

Meta-review: This paper studies the episodic setting for online MDPs with concave reward functions (generalized from linear rewards) and provides near-optimal regret bounds in the tabular setting through a novel mirror descent and exploration bonus. They also study the bandit-feedback version of this problem and leverage tools from bandit convex optimization. All reviewers were fairly positive about this submission, in particular mentioning that it makes a solid contribution to the literature. However, some reviewers did have concerns about the restriction to the tabular setting, limited technical novelty over the prior work of Moreno et al (2024), which addressed a similar setting, and the formulation not being sufficiently connected to practice. Based on this feedback, I recommend that the paper be accepted if there is room.
Decision: Accept (poster)