Challenging Common Assumptions in Convex Reinforcement Learning
Authors: Mirco Mutti
Riccardo De Santi
Piersilvio De Bartolomeis
Marcello Restelli
Venue: NeurIPS 2022 Accept (2022)
Keywords: Convex reinforcement learning
Reinforcement learning with general utilities
Theoretical aspects of reinforcement learning

Abstract: The classic Reinforcement Learning (RL) formulation concerns the maximization of a scalar reward function. More recently, convex RL has been introduced to extend the RL formulation to all the objectives that are convex functions of the state distribution induced by a policy. Notably, convex RL covers several relevant applications that do not fall into the scalar formulation, including imitation learning, risk-averse RL, and pure exploration. In classic RL, it is common to optimize an infinite trials objective, which accounts for the state distribution instead of the empirical state visitation frequencies, even though the actual number of trajectories is always finite in practice. This is theoretically sound since the infinite trials and finite trials objectives are equivalent and thus lead to the same optimal policy. In this paper, we show that this hidden assumption does not hold in convex RL. In particular, we prove that erroneously optimizing the infinite trials objective in place of the actual finite trials one, as it is usually done, can lead to a significant approximation error. Since the finite trials setting is the default in both simulated and real-world RL, we believe shedding light on this issue will lead to better approaches and methodologies for convex RL, impacting relevant research areas such as imitation learning, risk-averse RL, and pure exploration among others. 

Challenging Common Assumptions in Convex Reinforcement Learning
Mirco Mutti"
Riccardo De Santi' ETH Zurich rdesanti@ethz.co ch
Piersilvio De Bartolomeis
Politecnico di Milano Università di Bologna
ETH Zurich
pdebartol@ethz.cm ch
mirco. mutti @eeetipppmii.....
Marcello Restelli Politecnico di Milano
marcello. wercello.restell1@eee..
Abstract
The classic Reinforcement Learning (RI.) formulation concerns the maximization of scalar reward function. More recently, conver RL has been introduced to extend the RL formulation all the objectives that are convex functions of the state distribution induced by a policy. Notably, convex RL covers several relevant applications that do not fall into the scalar formulation, including imitation learning, risk-averse RL, and pure exploration. In classic RL, it is common to optimize an infinite trials objective, which accounts for the state distribution instead of the empirical state visitation frequencies, even though the actual number of trajectories is always finite practice. This is theoretically sound since the infinite trials and finite trials objectives are equivalent and thus lead to the same optimal policy. this paper. we show that this hidden assumption does not hold in convex RL. In particular, prove that erroneously optimizing the infinite trials objective in place of the actual finite trials one, as it usually done, can lead to significant approximation error. Since the finite trials setting is the default in both simulated and real-world RL, we believe shedding light on this issue will lead to better approaches and methodologies for convex RL, impacting relevant research areas such as imitation learning, risk-averse RL, and pure exploration among others.
Introduction
Standard Reinforcement Learning (RL) (50 is concerned with sequential decision-making problems in which the utility be expressed through linear combination of scalar reward terms. The coefficients of this linear combination are given by the state visitation distribution induced by the agent's policy. Thus, the objective function be equivalently written as the inner product between the mentioned state distribution and reward vector. However, not all the relevant objectives can be encoded through this linear representation 2 Several works have thus extended the standard RL formulation to address non-linear objectives of practical interest. These include imitation the problem of finding a policy that minimizes the distance between the induced state distribution and the state distribution provided by experts' interactions [[] 29 32 33 22 [7]. risk-averse RL 20 in which the objective sensitive to the tail behavior of the agent's 'ss policy [52]
learning 330 (22
43
51 16 15
pure exploration 27 where the goal is to find policy that maximizes the
entropy of the induced state distribution
53
38 diverse skills
'Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

discovery [23 [9 25 48 II, 35 28 58), constrained RL 4 3 37 45 56 6 and others. All this large body of work has been recently unified into a unique framework, called convex RL 660 57 21) which admits as an objective any convex function of the state distribution induced by the agent's s policy. The convex RL problem has been showed to be largely tractable either computationally. as
admits dual formulation akin to standard RI. [44], or statistically, as principled algorithms achieving sub-linear regret rates that are slightly worse than standard RL have been developed [60] [57
However, we note that the usual convex RL formulation makes an implicit infinite trials assumption which is rarely met in practice. Indeed, the objective is written as a function of the state distribution, which is an expecta- tion over the empirical state distributions that are actually obtained by running the policy in a given episode. In practice, we always run our policy for finite number of episodes (or trials), which in general prevents the empir- ical state distribution from converging to its expectation. This has never been a problem in standard RL: due to the scalar objective, optimizing the policy over infinite trials or fi- nite trials is equivalent, as it leads to the same optimal policy. Crucially, in this paper, we show that this property does not hold for the convex RL formulation: policy optimized over infinite trials can be significantly sub-optimal when deployed over finite trials (Figure D. In light of this observation, we reformulate the convex RL problem from a finite trials perspective, developing insights that can be used to partially rethink the way convex objectives have been previously addressed in RL, with potential ripple effects to research areas of significant interest, such as imitation learning, risk-averse RL, pure exploration, and others.
Finite Trials
Infinite Trials
RL
E r dnl = r d. d pp
Convex RL
E dnppp
[F(dn) # F(dr)
Figure I: Summary of the main finding of this paper: the equivalence between finite and infinite trials ob- jectives does not hold for the convex RI. formulation.
In this paper, we formalize the notion of a finite trials RL problem, in which the objective is function of the empirical state distribution induced by the agent's policy over trials rather than its expectation over infinite trials. As an illustrative example, consider a financial application, in which we aim to optimize trading strategy. In the real world, we can only deploy the strategy over single trial. Thus, we are only interested in the performance of the strategy in the real-world realization, rather than the performance of the strategy when averaging different realizations. Similar considerations apply to other relevant real-world applications, such as autonomous driving or treatment optimization in healthcare domain. Following this intuition, we first define the (linear) finite trial RL formulation (Section 3. for which it is trivial to prove the equivalence with standard RL. In Section 4 we provide the finite trial convex RL formulation, for which we prove an upper bound on the approximation error made by optimizing the infinite trials as proxy of the finite trials objective. In light of this finding, we challenge the hidden assumption that (1) convex RL can be equivalently addressed with an infinite trials formulation, even if the setting is finite-trial. We corroborate this result with an additional numerical analysis showing that the approximation bound non-vacuous for relevant applications (Section 6). Finally, in Section 5 we include an in-depth analysis of the single trial convex RL, which suggests that other common assumptions in the convex RL literature, i.e., that (2) the problem is always computationally tractable and that (3) stationary policies are in general sufficient, should be reconsidered as well. The proofs of the reported results can be found in the Appendix.
2 Preliminaries
In this section, we report the notation and background useful to understand the paper. We denote with (T' a set of integers [1,... T',, and with lower case letter a a scalar or vector, according to the context. For two vectors a, b Rd, we denote with b Di asb; the inner product between a, b.
2.1 Probabilities and Percentiles
Let X' denote a measurable space, we will denote with A ( the probability simplex over X', and with p E A(X) probability measure over X. For two probability measures p, q over X,, we define their ( -idistance as l|p <llp= == (Eeex |p(x) (²) % and their Dallback-Leibler (KL) divergence
2

---

as (L(pll)):= := Exx p(x) log (p(z)/q(x)) Let X be random variable distributed according to p, having a cumulative density function Fx (x) = Pr(X X S x). We denote with X its expected value, and its a-percentile is denoted as ( = inf {z Fx(x) 2 a} = Fx (a), where a E (0, 1) is a confidence level, and VaRa stands for Value at Risk (VaR) at level a. We denote the expected value of X within its a-percentile as CVaRa (X) = E [X] X S VaRa(X), where
CVaR,, stands for Conditional Value at Risk (CVaR) at level a.
2.2 Markov Decision Processes
A tabular Markov Decision Process (MDP) 4H1
is defined as M == (S.A.P.T, p,,.. where S is state space of size S, A is an action space of size A. P is Markovian transition model P P:S x A + (SS), such that P(s'|p [s, a) denotes the conditional probability of the next state given the current state 8 and action a, T is the episode horizon, la is initial state distribution Jr A(S), and r is a scalar reward function r S + IR, such that r(s) is the reward collected in the state 8.
In the typical interaction episode, agent first observes the initial state so 1 of the MDP. Then, the agent select an action ag, so that the MDP transitions to the next state 81 ~ P(-|so, ao), and the agent collects the reward r(s1). Having observed 81, the agent then selects an action di triggering subsequent transition to $2 ~ P(-|s1,0; a1). This process carries on repeatedly until the episode ends.
A policy æ defines the behavior of an agent interacting with an MDP, i.e., the strategy for which an action is selected at any step of the episode. It consists
sequence of decision rules (TT) that ht (st, a H4 with a distribution over actions म. : H₂ + A(A). where Hi denotes the set of trajectories of length t. A non-stationary policy is sequence of decision rules Te : S + (AA). A stationary (Markovian) policy a cime-consistent decision rule S - (AA), such that (a)ss denotes the conditional probability of taking action in state
maps the current trajectory F
trajectory h. obtained from interaction episode, induces empirical distribution d over the states of the MDP M, such that d(s) = Th. Ex,e,
Eh 11 (s; = 8). We denote with p" the probability of drawing d by following the policy æ. For E N, we denote with d, the empirical distribution (x) = - -i= di (s),, and with P. the probability of drawing d, by following the policy क for n episodes. Finally, we call the expectation dm Batpp [d] the state distribution induced by x.
3 Reinforcement Learning in Finite Trials
In the standard RL formulation 50) an agent aims to learn an optimal policy by interacting with an unknown MDP M. An optimal policy is decision strategy that maximizes the expected sum of rewards collected during an episode. Especially, we can represent the value of a policy x through the value function (s) == E, ΣT_ r(sw] s; = s]. The value function allows us to write the RL objective as maxzem Esy=gl [VT (+1() where II is the set of all the stationary policies. Equivalently, we can rewrite the RI. objective into its dual formulation 44 i.e.,
RL
(r. =::
max #Ell
where we denote with r E S a reward vector, and with dt the state distribution induced by n. We call the problem T the infinite trials RL formulation. Indeed, the objective (T) considers the sum of the rewards collected during an episode, i.e., -- d"', that we can achieve on the average of an infinite number of episodes drawn with This is due to the state distribution d" being expectation of empirical distributions dh = Edwzg [d]. However, in practice, we can never draw infinitely many episodes following policy æ. Instead, we draw a small batch of episodes d,, ~ ph. Thus, we can instead conceive a finite trials RL formulation that is closer to what is optimized in practice.
We will call sequence of states and actions trajectory history indifferently.
3

---

Table 1: Various convex RL objectives and applications. The last column states the equivalence between infinite trials and finite trials settings, as derived in Proposition [ Appendixx.
OBJECTIVE F
APPLICATION
INFINITE
FINITE
r.d
R², rER A(S)
|| dell
KL(d] dg)
d,dg E A(S)
IMITATION LEARNING
-d log (d)
de A(S)
PURE EXPLORATION
CVaR,, [r.]
r r-d- Varlr-d
r A(S)
RISK-AVERSE RL.
r. r- S.T. c E. KL dd E1 de)
r, r, CE R dE A(S)
LINEARLY CONSTRAINED RL
2 ZER R d, de (A))
DIVERSE SKILL DISCOVERY
Finite Trials RL
dr (r. =: (n)
maxx xE11
da-up
One could then wonder whether optimizing the finite trials objective leads to results that differ from the infinite trials one ( functions actually equivalent
To this point, it is straightforward to see that the two objective
(T)
E duppp
[r dd.] =
E de mPT
[dm] -r. (T),
since is a constant vector and the expectation is a linear operator. It follows that the infinite trials and the finite trials RL formulations admit the same optimal policies. Hence, one can enjoy both the computational tractability of the infinite trials formulation and, at the same time, optimize the objective function that is employed in practice. the next section, we will show that similar result does not hold true for the convex RL formulation.
4 Convex Reinforcement Learning in Finite Trials
Even though the RL formulation covers a wide range of sequential decision decision-making problems, several relevant applications cannot be expressed by means of the inner product between linear reward vector r and a state distribution d' 49]. These include imitation learning, pure exploration, constrained problems, and risk-sensitive objectives, among others. Recently, convex RI formulation [60 57 has been proposed to unify these applications in a unique general framework, which
Convex RL
max #Ell (F(IT) =o
where F A(S) IR is function of the state distribution d= In Table 1 recap of the most relevant problems that fall under the convex RI. formulation, along with their specific F function. As happens for linear RL, in any practical simulated or real-world scenario, we can only draw finite number of episodes with a policy From these episodes, we obtain an empirical distribution d, P, rather than the actual state distribution d= where n is the number of episodes. This can cause mismatch from the objective that is typically considered in convex RL [60 57]. and what can be optimized practice. overcome this mismatch, we define a finite trials formulation of the convex RL objective, as we did in the previous section for the linear RL formulation.
Finite Trials Convex RL
max KEII
[F(d))) =: (T())) dr
(4)
'In this context, we use the term convex to distinguish from the standard linear RL objective. However, in the following we will consider functions F that are either convex, concave or even non non-convex. In general, problem takes the form of a max problem for concave F. min problem for convex F.

---

Comparing objectives 3 and (4), one can notice that both of them include an expectation over the episodes, being d' E E-pp" [d.. Especially, we can write
Soc (T) = F(d") F( E Cmp
(d.)) d, P.
(d..)
E
[F(d.)] (TT)
through the Jensen's inequality. As a consequence, optimizing the infinite trials objective Çoa (T)) does necessarily lead an optimal behavior for the finite trials objective (. From mathematical perspective, this is due to the fact that the empirical distributions d,, induced by the policy are averaged by the expectation d' before computing the F function into objective (3). thus losing measure of the performance FF for each batch of episodes, which we instead keep in the objective (4)
4.1 Approximating the Finite Trials Objective with Infinite Trials
Despite the evident mismatch between the finite trials and the infinite trials formulation of the convex RL problem, most existing works consider (3) as the standard objective, even if only a finite number of episodes can be drawn in practice. Thus, it is worth investigating how much approximating a finite trials objective with an infinite trials one. First, we report a useful assumption on the structure of the function F.
lose by
Assumption 4.1 (Lipschitz). A function F X - R is Lipschit--continuuus if it holds for some constant
F(x) F(y) s L1|z -vl v(z,y) E x².
Then, we provide an upper bound on the approximation error in the following theorem.
Theorem 4.1 (Approximation Error). Let N be number of trials, let ò E (0, be confidence level, let x² E arg max (T) and xt* E arg max (oo Then, it holds with probability at least
28 log 4T/88)
err :r (s(()) - So (n S V
7
The previous result establishes approximation error rate err O S/n) that is polynomial in the number of episodes n. Unsurprisingly, the guarantees over the approximation error scales with O(1//n), one expect the empirical distribution d, to concentrate around its expected value for large n [54). This implies that approximating the finite trials objective Go (T) with the infinite trials Soo (I) can be particularly harmful in those settings in which n is necessarily small. As example, consider training a robot through a simulator and deploying the obtained policy in the real world, where the performance measures often based single episode (n 1). The performance that we experience from the deployment can be much lower than the expected Soo (r), which might result in undesirable or unsafe behaviors. However, Theorem 4.1 Jolly reports instance-agnostic upper bound, and it does not necessarily imply that there would be a significant approximation error in specific instance, i.e., a specific pairing of an MDP M and a function F. Nevertheless, in this paper we argue that the upper bound of the approximation error is not vacuous in several relevant applications, and we provide an illustrative numerical corroboration of this claim in Section 6
Challenged assumption 1. The convex RI. problem can be equivalently addressed with an infinite trials formulation.
Finally, in Figure 2 we report visual representation of the approximation error defined in Theo- rem 4.1 Notice that the finite trials objective Sn converges uniformly to the infinite trials objective Çoo as trivial consequence of Theorem 4.1 This is particularly interesting as it results in x converging
to Rt in the limit of large n as shown Figure 2
In-Depth Analysis of Single Trial Convex Reinforcement Learning Setting
Having established a significant mismatch between the infinite trials convex RL setting that is usually considered in previous works, i.e., (so (r), and the finite trials formulation that is actually targeted in
'Note that it is not possible to represent the objective functions in two dimensions in general. Nevertheless, provide abstract one- mie-immeniional representation of the policy space to bring the intuition.
5

---

Sn
600
00o
Figure 2: The two illustrations report an abstract visualization of G. and (so for small values of n (left) and large values of n (right) respectively. The green bar visualize the distance || - d= || in which d, ~ p."" The blue bar visualize the distance (n(xT) (T The orange bar visualize the approximation error, ie., the distance [Sn. -n (n
practice, ie., Sn. (T), it is now worth taking a closer look at the finite trials optimization problem (4) Indeed, to avoid the approximation error that occur by optimizing (4) through the infinite trials formulation (Theorem 4.1). one could instead directly address the optimization of (4). Especially, how does the finite trials convex RL problem compare its infinite trials formulation and the linear RL problem? What kind of policies do we need to optimize the finite trials objective? Is the underlying learning process statistically harder than infinite trials convex RL. In this section, investigate the answers to these relevant questions. To this purpose, we will focus on a single trial setting, i.e., Ca (T) with n which allows for clearer analysis, while analogous considerations should extend to general number of trials n > 1.
Single Trial Convex RL
max nEll
[F(d)) =: (TT) d~-p'
E
(5)
Taking inspiration from [57], we can cast problem (5) defined over an MDP M into a convex MDP CMM == P.T. u, where S, A. P. T, defined as in standard MDP (see Section 2 and F: Á(S) + R is convex function that defines the objective Ç1 (T). ). Is solving a convex MDP
CMM significantly harder than solving an MDP M?
5.1 Extended MDP Formulation of the Single Trial Convex RL Setting
We can show that any finite-horizon convex MDP CM can be actually translated into an equivalent MDP M₁ = Ac, Pt, Pe, re), which we call an extended MDP. The main idea is to temporally- extend CM so that each state contains the information of the full trajectory leading the convex objective can be cast into a linear reward. To do this, we define the extended state space Sy to be the set of all the possible histories up to length T. so that se E Se now represents history. Then, we can keep Ae, Pe. Me equivalent to A, P. μ of the original C.M, where for the extended transition model P. ( sr, a)) we solely consider the last state in the history 8y to define the conditional probability to the next history syc. Finally, we just need to define scalar reward function re: : + IR such that (s{) F(da,) for all the histories 8y length and re(se) = 0 otherwise, where we denoted with da, the empirical state distribution induced by sg.
it, so that
Notably, the problem of finding an optimal policy for the extended MDP Mr. i.e., T² arg max d=,, is equivalent to solve the problem (5). Indeed, we have
T8 d=
Σ re(ss)dd - F(d.,) (1sa) = T)p" (d.,)
E der
[F(d..))
etES;
#rES;
Whereas Mr can be solved with classical MDP methods [44) the size of the policy S A(Ar) to be learned does scale with the size of Mr, which grows exponentially in the episode horizon as we have [Sel > ST Thus, the extended MDP formulation and the resulting insight cast some doubts the notion that the convex RL not significantly harder than standard RL [60 57].
Challenged assumption 2. Conver RL is only slightly harder than the standard RL formulation.

---

5.2 Partially Observable MDP Formulation of the Single Trial Convex RL Sefting
Instead temporally extending the convex MDP CM as the previous section, which causes the policy space grow exponentially with the episode horizon T.
alternatively formulate C.M as a Partially Observable MDP (POMDP) S B1 P.M = Ae, Pt. Te, Tt, S2, Q), in which Ω denotes an observation space, and O St (2)) is an observation function. The process to build PM is rather similar to the one we employed for the extended MDP Mr. and the components Se. Ae; Pe, re remain indeed unchanged. However, in POMDP the agent does not directly access a state 8/ E St, but just a partial observation E f2 that is given by the observation function O. Here (s5²)
is deterministic function such that the given observation is the last state in the history Sg. Since the agent only observes a stationary policy can be defined as a function T: : Ω + ((A), for which the size depends the number of states S of the convex MDP C.M, being Ω = S. However, it is well known [3I] that history-depende
policies should be considered for the problem of optimizing a POMDP. This is in sharp contrast with the current convex MDP literature, which only considers stationary policies due to the infinite trials formulation [60].
Challenged assumption 3. The set of stationary randomized policies is sufficient for convex RL.
5.3 Online Learning in Single Trial Convex RL
Let us assume to have access to planning oracle that returns an optimal policy n² for a given C.M. so that we can sidestep the concerns on the computational feasibility reported in previous sections. is worth investigating the complexity of learning "T" from online interactions with an unknown C.M. typical measure of this complexity is the online learning regret ((N), which is defined as
N
R(N) Σ V V*-)(t,
where N is the number of learning episodes, V VT (s1) is the value of the optimal policy, V(0) 4 is the value of the policy स. deployed at the episode t. We now aim to assess whether there exists a principled algorithm that can achieve a sub-linear regret R(N) in the worst case. To
can cast our learning problem in the Once-Per- Pnce-Per-EEpisoee (OPE) RL formulation [12) In the latter setting, the agent interacts with the MDP for T steps, receiving a 1 feedback at the end of the episode, where the feedback is computed according
this purpose,
logistic model that is function of the history. To translate our objective Çi (T) = Ed [F(d] into the OPE framework (12), we have to encode into a linear representation. With the following assumption, we state the existence of such representation.
Assumption 5.1 (Linear Realizability). The function F is linearly-realizable if it holds
F(d) w.. ((d),
where w. E ddw is vector of parameters such that || [ww 1|2 B for some known B > 0, and x(d) (z) is a known vector of basis functions such that [|o(d)] 1, e ASS).
With the Assumption 5. and other minor changes that are detailed in the Appendix, we can invoke the analysis of OPE- UCBVI in [12 to provide an upper bound to the regret R(N) in our setting.
Theorem 5.1 (Regret). For any confidence ò E (0, 1] and unknown convex MDP C.M, the regret of the OPE-UCBVI algorithm is upper bounded as
(( 13 VN)
R(N) S
with probability 1 1 8.
The latter result states that the problem of learning an optimal policy in a unknown convex MDP is at least statistically efficient assuming linear realizability and the access to a planning oracle. Those are fairly strong assumptions, but principled approximate solvers may be designed to overcome the planning oracle assumption, whereas in several convex RL settings the function F is assumed to be known, and thus trivially realizable.
7

---

(a) Pure exploration
(b) Risk-averse RI.
(c) Imitation learning
Figure 3: Visualization of the illustrative MDPs. In (b), state 0 is a low-reward (r) low-risk state,
state 2 a high-reward (R) high-risk state, and state is a penalty state with zero reward.
6 Numerical Validation
In this section, we evaluate the performance over the finite trials objective achieved by a policy rt arg mIX (T) maximizing the same finite trials objective against a policy x' arg max ( (T) maximizing the infinite trials objective (3) instead. The latter infinite trials n can be obtained by solving dual optimization on the convex MDP (see Sec. 6.2 in (4]).
max F(w), wEA(SXA)
subject to
Σ a(s
E S'ES,0'EA
P(s)s',a')utt a').,a))sssss ,'), E
To get the finite trials z!, we first recover the extended MDP as explained in Section 5.1 and then we apply standard dynamic programming 77. In the experiments, we show that optimizing the infinite trials objective can lead sub-optimal policies across wide range of applications. In particular, we cover examples from pure exploration, risk-averse RL, and imitation learning. We carefully selected MDPs that are simple as possible in order to stress the generality of results. For the sake of clarity, we restrict the discussion to the single trial setting (n 1).
Pure Exploration For the pure exploration setting, we consider the state entropy objective (27]. i... F(d) = (d) = - log d, and the convex MDP in Figure 3a In this example, the agent aims to maximize the state entropy over finite trajectories of T steps. Notice that this happens when policy induces an empirical state distribution that is close to uniform. In Figure 4al we compare the average entropy induced by the optimal finite trials policy त and the optimal infinite trials policy n². An agent following the policy πt always achieves uniform empirical state distribution leading to the maximum entropy. Moreover, æ is a non- non-nonoeeee -arakovva deterministic policy. In contrast, the policy n² is randomized in all the three states. As result, this policy induces sub-optimal empirical state distributions with strictly positive probability, as shown in Figure 4d
Risk-Averse RL For the risk-averse RL setting, we consider Conditional Value-at-Risk (CVaR) objective [46] given by F(d) = CVaR,lr- d], where r [o, 1] is reward vector, and the convex MDP in Figure 3b in which the agent aims to maximize the CVaR over finite-length trajectory of steps. First, notice that financial semantics can be attributed to the given MDP. An agent, starting in state 2, can decide whether to invest in risky assets, e.g., crypto-currencies, or in safe ones, e.g., treasury bills. Because of the stochastic transitions, a policy would need to be reactive to the realizations of the transition model in order to maximize the single trial objective (5). This kind of behavior is achieved by an optimal finite trials policy æτ. Indeed, 7t function of history, and thus takes into account
Markvvano
deterministic policy, which can take decisions the other hand, an optimal infinite trials policy x' is a Markovian policy,
current realization. and it cannot take into account the current history. As a result, the policy x² induces sub-optimal trajectories with strictly positive probability (see Figure 4c). Finally, in Figure [ 4b] we compare the single trial performance induced by the optimal single trial policy m! and the optimal infinite trials policy n². Overall, π! performs significantly better than n..
Imitation Learning For the imitation learning setting, we consider the distribution matching objective (32. i.e., F(d) KL (d) dg), and the convex MDP Figure Bc The agent aims to learn policy π inducing an empirical state distribution close to the empirical state distribution de demonstrated by an expert. In Figure we compare single trial performance induced by the optimal single trial policy x² and the optimal infinite trials policy x². An agent following m² induces an empirical state distribution that perfectly matches the expert. contrast, an agent following "" induces sub-optimal realizations with strictly positive probability (see Figure 4f

---

0.2
0.8
CVaRa ( d
dl
0.15
H(d
0.6
0.4
0.2
0.05
π
x!
T!
(a) Entropy average
(b) CVaR average
(c) KL average
Frequency
Frequency
0.8
Frequency
0.8
π
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
10
0.8
(dd)
CVaR [r
KL(d) (dg)
(d) Entropy distribution
(e) CVRR distribution
(I) KL distribution
Figure 4: rt denotes an optimal single trial policy, n" denotes optimal infinite trials policy. In (a, d) we report the average and the empirical distribution of the single trial utility H(d) achieved in the pure exploration convex MDP (T = 6) of Figure 3a In (b, e) we report the average and the empirical distribution of the single trial utility [Va dJ (with = 0.4) achieved in the risk-averse convex MDP (T 5) of Figure [bb In (c, f) we report the average and the empirical distribution of the single trial utility (T, (d)g) (with expert distribution de = (1/3, 2/3)) achieved in the imitation learning convex MDP (T = 12) of Figure 3c For all the results, we provide 95 % c.i. over 1000 runs.
Related Work
To the best of our knowledge, 27 were the first introduce the convex RL problem, gener- alization of the standard RL formulation to non-linear utilities, especially the entropy of the state distribution. They show that the convex RL objective, while being concave (convex) in the state distribution, can be non-concave (non-convex) in the policy parameters. Anyway, they provide a provably efficient algorithm that overcomes the non-convexity through Frank-Wolfe approach. (60 study the convex RL problem under the name of RL with general utilities. Especially, they investigated hidden convexity of the convex RL objective that allows for statistically efficient policy optimization the infinite-trials setting. Recently, the infinite trials convex RL formulation has been reinterpreted from game-theer theoretee perspectives [57] 21 The former [57] notes that the convex RI. problem can be seen as min-max game between the policy player and a cost player. The latter [2]] shows that the convex RL problem is subclass of mean-field games.
Another relevant branch of literature the one investigating the expressivity of scalar (Markovian) rewards [2] 49 Especially, 2 shows that not all the notions of task, such inducing set of admissible policies, (partial) policy ordering. a trajectory ordering, can naturally encoded with scalar reward function. Whereas the convex RL formulation extends the expressivity of scalar RL w.r.t. all these three notions of task, it is still not sufficient to cover any instance. Convex RL is powerful in terms of the policy ordering it induce, but it is inherently limited the trajectory ordering as it only accounts for the infinite trials state distribution. Instead, the finite trials convex RL. setting that presented this paper is naturally expressive in terms of trajectory orderings, the expense of a diminished expressivity on the policy orderings w.r.t. infinite trials convex RL.
Previous works concerning RL in the presence of trajectory feedback are also related to this work. Most of this literature assumes an underlying scalar reward model [e.g., [8] which only delays the feedback at the end of the episode. One notable exception is the once-per-episode formulation in [12 which we have already commented on Section
Finally, the work in 13 14 considers infinite-horionn MDPs with vectorial rewards as mean to encode convex objectives in RI. with a multi-objective flavor. They show that stationary policies are in general sub-optimal for the introduced online learning setting, where non-stationarity becomes

---

essential. In this setting, they provide principled procedures to learn an optimal policy with sub-linear regret. Their work essentially complement our analysis the infinite-horizon problem formulation, where the difference between finite trials and infinite trials fades away.
8 Conclusion and Future Directions
While in classic RL the optimization of an infinite trials objective leads to the optimal policy for the finite trials counterpart, we have shown that true convex RI does not have this property. First, we have formalized the concept of finite trials convex RL, which captures problem that until now has been cast into an unfounded optimization problem. Then, we have given an upper bound on the approximation error obtained by erroneously optimizing the infinite trials objective, it is currently done in practice. Finally, we have presented intuitive, yet general, experimental examples to show that the approximation error can be significant in relevant applications. Since the finite trials setting the standard in both simulated and real-world RL, we believe that shedding light on the above mentioned performance gap will lead to better approaches for convex RL and related areas. Future work could target approximate solutions to the finite trials objective rather than the infinite trials one, which can cause sub-optimality even when solved exactly. Methods in POMDPs 26 34 optimistic planning algorithms [00 could provide useful inspiration.
Acknowledgements
Riccardo De Santi and Piersilvio De Bartolomeis thank professor Niao He for offering graduate students ETH the opportunity work in exciting research areas within the "Foundations of Reinforcement Learning" course. Further, we thank Ali Batuhan Yardim for his generous feedback on an early version of this work.
References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine learning, 2004.
[2] David Abel, Will Dabney, Anna Harutyunyan, Mark Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of Markov reward. In Advances in Neural Information Processing Systems, 2021.
[3] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference on Machine Learning, 2017.
[4] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[5] Karl Johan Aström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10: 174-255, 1965.
[6] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In AAAI Conference on Artificial Intelligence 2022.
[7] Richard Bellman. Dynamic programming. Princeton University Press, 1957.
[8] Bisi, L Sabbioni, E Vittori, M Papini, and M Restelli. Risk-averse trust region optimization for reward-volatility reduction. In International Joint Conference on Artificial Intelligence, 2020.
[9] Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alek- sandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. In Advances in Neural Information Processing Systems, 2020.
[10] Sébastien Bubeck and Rémi Munos. Open loop optimistic planning. In Conference on Learning Theory, 2010.
10

---

[11] Victor Campos. Alexander Trott, Caiming Xiong, Richard Socher, Xavier Giró-i Nieto, and Jordi Torres. Explore, discover and lear:: Unsupervised discovery of state-covering skills, In International Conference on Machine Learning, 2020.
[12] Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with once-per-episode feedback. In Advances in Neural Information Processing Systems, 2021.
[13] Wang Chi Cheung. Exploration cenittion-elliiaattion trade-off in reinforcement learning on online markov decision processes with global concave rewards. arXiv preprint 2019.
[14] Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 2019.
[15] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. cisk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, (8(1):6070-612)) 2017.
[16] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: a evar optimization approach. In Advances in Neural Information Processing Systems, 2015.
[17] Robert Dadashi, Leonard Hussenot, Matthieu Geist, and Olivier Pietquin. Primal wasserstein imitation learning. In International Conference on Learning Representations, 2020.
[18] Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In AAAI Conference Artificial Intelligence, 2021.
[19] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In International Conference on Learning Representations, 2018.
[20] Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, ((()):1437-1480, 2015.
[21] Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: The mean-field game viewpoint. In International Conference on Autonomous Agents and Multiagent Systems, 2022.
[22] Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimiza- tion perspective on imitation learning methods. In Conference on Robot Learning, 2020.
[23] Karol Gregor, Danilo Rezende, and Daan Wierstra. Variational intrinsic control. International Conference on Learning Representations, Workshop Track, 2017.
[24] Zhaohan Daniel Guo, Mohammad Gheshlagi Azar, Alaa Saade, Shantanu Thakoor, Bilal Piot, Bernardo Avila Pires, Michal Valko, Thomas Mesnard, Tor Lattimore, and Rémi Munos. Geometric entropic exploration. arXiv preprint arXiv:2 2021.
[25] Steven Hansen, Will Dabney, Andre Barreto, David Warde-Farley, Tom Van de Wiele, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. In Interna- tional Conference on Learning Representations, 2019.
[26] Milos Hauskrecht. Value-function approximations for partially observable markov decision processes. Journal of Artificial Intelligence Research, 13:33-94, 2000.
[27] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, 2019.
[28] Shuncheng He, Yuhang Jiang, Hongchang Zhang, Jianzhun Shao, and Xiangyang Ji. Wasserstein unsupervised reinforcement learning. In AAAI Conference on Artificial Intelligence, 2022.

---

[29] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, 2016.
[30] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: survey of learning methods. ACM Computing Surveys (CSUR), 50(2):1-35, 2017.
[31] Leslie Pack Kaclbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 1998.
[32] Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribu- tion matching. In International Conference on Learning Representations, 2019.
[33] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Rus- lan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arX1v:1906.00274, 2019.
[34] Michael L Littman, Anthony R Cassandra, and Leslie Pack Kaclbling. Learning policies for partially observable environments: Scaling up. In Machine Learning, pages 362-370. Elsevier, 1995.
[35] Hao Liu and Pieter Abbeel. APS: Active pretraining with successor features. In International Conference on Machine Learning, 2021.
[36] Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training, In Advances in Neural Information Processing Systems, 2021.
[37] Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert Schapire. Reinforcement learning with convex constraints. In Advances in Neural Information Processing Systems, 2019.
[38] Mirco Mutti, Riccardo De Santi, and Marcello Restelli. The importance of non-markovianity in maximum state entropy exploration. International Conference on Machine Learning, 2022.
[39] Mirco Mutti, Mattia Mancassola, and Marcello Restelli. Unsupervised reinforcement learning in multiple environments. In AAAI Conference on Artificial Intelligence, 2022.
[40] Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task agnostgc exploration via policy gra- dient of non-parametric state entropy estimate. In AAAI Conference on Artificial Intelligence, 2021.
[41] Mirco Mutti and Marcello Restelli. An intrinsically-motivaee approach for learning highly exploring and fast mixing policies. AAAI Conference on Artificial Intelligence, 2020.
[42] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trends@ in Robotics, 7(1-2):1-179 2018
[43] LA Prashanth and Mohammad Ghavamzadeh. Actor-critic algorithms for risk-sensitive mdps. In Advances in Neural Information Processing Systems, 2013.
[44] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[45] Zengyi Qin, Yuxiao Chen, and Chuchu Fan. Density constrained reinforcement learning. In International Conference on Machine Learning. 2021.
[46] R Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21-41, 2000.
[47] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State en- tropy maximization with random encoders for efficient exploration. International Conference on Machine Learning, 2021.
12

---

[48] Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics- aware unsupervised discovery of skills. In International Conference on Learning Representa- lions; 2020.
[49] David Silver, Satinder Singh, Doina Precup, and Richard S Sutton, Reward is enough. Artificial Intelligence, 299: 103535, 2021.
[50] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press. 2018.
[51] Aviv Tamar. Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In Advances in Neural Information Processing Systems, 2015.
[52] Aviv Tamar and Shie Mannor. Variance adjusted actor critic algorithms. arXiv preprint arXiv:1310.3697 2013.
[53] Jean Tarbouriech and Alessandro Lazaric. Active exploration in Markov decision processes. In International Conference on Artificial Intelligence and Statistics, 2019.
[54] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the deviation of the empirical distribution. Newleu--Packare Labs, Tech. Rep, 2003.
[55] Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Reinforcement learning with prototypical representations. In International Conference on Machine Learning, 2021.
[56] Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi-objective competitive rl. In International Conference on Machine Learning, 2021.
[57] Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. In Advances in Neural Information Processing Systems, 2021.
[58] Tom Zahavy, Yannick Schroecker, Feryal Behbahani, Kate Baumli, Sebastian Flennerhag, Shaobo Hou, and Satinder Singh. Discovering policies with domino: Diversity optimization maintaining near optimality. arXiv preprint arXiv:2205. 13225,, 2022.
[59] Chuheng Zhang, Yuanying Cai, Longbo Huang, and Jian Li. Exploration by maximizing Rényi entropy for rewerd-free RL framework. In AAAI Conference Artificial Intelligence, 2021.
[60] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems, 2020.
[61] Shangtong Zhang, Bo Liu, and Shimon Whiteson. Mean-variance policy iteration for risk-averse reinforcement learning. In AAAI Conference on Artificial Intelligence, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] Lines 57-73 details the main contributions and where to find them.
(b) Did you describe the limitations of your work? [No] We did not explicitly commented the limitations in the paper. However, we note that this is an analytical paper that does not include algorithmic contribution. This could be seen potential limitation, but we believe that developing methodologies for finite trials convex RL settings can be matter for future works.
(c) Did you discuss any potential negative societal impacts of your work? [No] This is
mainly theoretical paper, we cannot foresee any potential societal impact beyond speculation.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
13

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions 4.1 5.1 and the Appendix for additional details.
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [No] Our paper is mainly theoretical. While reported a brief numerical evaluation, the experiments are straightforward to reproduce given the description provided in Section 6
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes] See Section
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] We reported 95 % c.i. over 1000 runs, as specified in the caption of Figure 4
(d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [No] The needed computation is negligible.
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "sLCp-wJ0Wju", "reviewer": "Reviewer_eN8u", "summary": "In this paper, the framework of convex Reinforcement Learning (RL) which covers applications such as imitation learning, and risk-averse RL is considered.  In vanilla RL, the idea of approximating the infinite trial objective by the finite counterpart works. However, the authors have established this assumption does not hold true in the convex RL setting. Further, they have proved and shown using experiments that optimizing an infinite trial objective instead of the finite one in convex RL may lead to a significant approximation error. The other contribution of the paper is that the authors have shown that other common assumptions in the convex RL literature such as computational tractability and sufficiency of stationary policies require re-investigation. ", "questions": "However, there are a few concerns as follows:\n1.\tIn the introduction, the authors have given an example of a financial application. Some more motivating examples for the single-trial case need to be highlighted to strengthen the motivation. \n2.\tThe equivalence of the reward function in the extended MDP as in Section 5.1 and that of a finite-horizon convex MDP is not clear. \n3.\tWhy do we need to encode $\\mathcal{F}$ into a linear representation in Section 5.3, and why this particular linear representation is chosen in this paper? Can we make the approximation term in Theorem 5.1 better by choosing an alternative linear representation? The linear dependence of the approximation term on $N$ is a limiting factor. Can the OPE algorithm be adapted to the setting where no approximation is required and $\\mathcal{F}$ can be used directly? \n4.\tAlthough the issues in convex MDP are well-investigated in this paper, the contribution in terms of the learning algorithm and associated analysis is limited.\n", "limitations": "Overall, this is the first paper that establishes that the infinite trial objective optimization does not lead to the optimal policy in the finite trial in convex RL, unlike the classical RL. However, there are concerns in terms of the extended MDP formulation and the linear dependence on $N$ because of the employed approximation. Therefore, the contribution in terms of the online learning mechanism seems to be limited. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and easy to follow. The contribution of the paper is significant as this is the first paper that establishes that the infinite trial objective optimization does not lead to the optimal policy in the finite trial in convex RL, unlike the classical RL. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "p7hov2Zzkur", "reviewer": "Reviewer_CnKV", "summary": "This paper shows that optimizing the objective posed by \"convex RL\" using a finite number of trials can lead to significant differences in policy performance when compared to what the analysis yields under infinite trails. They argue that this approximation error can be decreased by explicitly accounting for the use of a finite number of trials in the convex RL objective, and verify this gap in performance both theoretically and empirically. ", "questions": "## Some comments:\nAbstract:\n1. \"More recently, convex RL has been introduced to extend the RL formulation to all the objectives that are convex functions of the state distribution induced by a policy.\" -- I would rephrase this to address the fact that recent work can provide solutions in non-stationary MDPs. What the reward is a function of is only important in so much as it changes with the policy distribution. \n2. \"Notably, convex RL covers several relevant applications that do not fall into the scalar formulation, including imitation learning, risk-averse RL, and pure exploration\" --This statement is confusing are you proposing to optimize vector valued rewards or rewards that are convex in the induced state distribution of the policy.  \n\nIntroduction:\n1. \"The coefficients of this linear combination are given by the state visitation distribution induced by the agent’s policy.\" -- This is not true for general RL just the variant which is discussed in this paper and RL under general utilities paper. \n2. \"Thus, the objective function can be equivalently written as the inner product between the mentioned state distribution and a reward vector.\" -- Again not true for general RL, only the tabular settings in which there are a finite number of states and actions. \n3. \"Several works have thus extended the standard RL formulation to address non-linear objectives of practical interest.\" -- I would not call imitation learning an extension of RL. In most cases its a much simpler problem, unless you are actually talking about apprenticeship learning or imitation learning from observation alone (e.g. only states induced by an expert policy are observed). \n4. \"All this large body of work has been recently unified into a unique framework, called convex RL\" --Please just explicitly state what the assumptions for convex RL are, then explain why each of these sub-fields falls into this framework. \n5. \"The convex RL problem has been showed to be largely tractable either computationally, as it admits a dual formulation akin to standard RL [24], or statistically, as principled algorithms achieving sub-linear regret rates that are slightly worse than standard RL have been developed [31, 30].\" --This sentence is poorly worded, and makes it hard for the reader to understand what is being asserted.\n6. \"This has never been a problem in standard RL: due to the scalar objective, optimizing the policy over infinite trials or finite trials is equivalent, as it leads to the same optimal policy\" -- Please be more clear, the use of equivalent is vague and it does not leave the reader with a notion of what is lost when we don't work with exact expectations. Also the assertion that using finite numbers of samples does not affect standard RL problems is definitely not true in general. Please make this statement more precise. \n7. \"a policy optimized over infinite trials can be significantly sub-optimal when deployed over finite trials\" -- Did you mean to say, '`'significantly more sub-optimal than a policy  optimized over finite trials'? \n8. \"In the real world, we can only deploy the strategy over a single trial. Thus, we are only interested in the performance of the strategy in the real-world realization, rather  than the performance of the strategy when averaging different realization\" -- Again this phrasing really throws me off. Just say that \"in the real world we gather finite numbers of examples so we should consider algorithms which explicitly use a finite number of examples during training\" if that is indeed what you are trying to say.\n9. \"(1) convex RL can be equivalently addressed with an infinite trials formulation\" -- This is extremely vague. Please make your assertion more direct and testable. Especially when this is the core motivation for the paper.\n10. \"  (3) stationary policies are in general sufficient\" This also needs to be made more clear. You have not introduced a notion of stationarity, nor have you explicitly stated for what they are sufficient. Without this clarity inclusion of this statement in the introduction is meaningless.\n\nBackground\n1. Making the reward a function only of state is non-standard. \n2. You have multiple definitions of \\pi_t that are inconsistent with one-another. In fact the whole destinction between stationary and non-stationary is unclear. What do you mean by a time-consistent rule? In the classic RL literature, if I am not mistaken, stationary usually means that the policy produces a value function which satisfies the bellman equations.\n3. Please explicitly state your assumptions about the class of MDPs you consider, namely tabular. \n\nReinforcement learning with Finite trails\n1. Again much of your computational tractability comes from the assumption on the reward which is not true for general RL.\n\nConvex Reinforcement Learning in Finite Trials\n1. All of this is predicated on the idea that the expectation is taken before the model is run. Which in general its not, and many standard RL algorithms function and have been analyzed in this regime. \n2. There is formatting issue with 4.1\n3. I am uncertain about the claim from Theorem 4.1. Are you proposing this as a this a novel contribution of this paper? I know that even extremely old Apprenticeship learning papers analyze the solution dependency between exact and inexact expectations, namely (1) and (2). There has also been more work following mirror-decent algorithms that even inexact updates can provide algorithms with sub-linear regret (3). I am not sure if these extend to \"Convex RL\" with general utilities but I am not sure why they would not. If they don't please comment on the limitations of online mirror decent algorithms. \n3. \"Challenged assumption 1. The convex RL problem can be equivalently addressed with an infinite trials formulation\" -- What does equivalently addressed mean? If this is one of the main points of the paper it needs to be a precise statement. \n\nIn-Depth Analysis of Single Trial Convex Reinforcement Learning Setting\n1. \"Thus, the extended MDP formulation and the resulting insight cast some doubts on the notion that the convex RL is not significantly harder than standard RL [31, 30].\" -- Just state what the finding is. Your statement here is so conservative so as to be basically meaningless. \n2. Its extremely difficult to untangle what exactly is being stated by 5.2.\n3. \"The set of stationary randomized policies is sufficient for convex RL.\" --Sufficient for what. \n4. Formatting issues with Theorem 5.1 \n5. Are you claiming that Theorem 5.1 is unique in providing sub-linear regret for the task of RL under general utilities in the presence of function approximation / inexact optimization / inexact expectations? It seems as though there must be result that are similar (e.g. provide sub-linear regret in the online mirror decent literature. Might look here (3)).\n\nIllustrative Examples and Experimental Approximation Error\n1. These are nice toy examples but if the point of this paper was to provide a better bridge between theory and practice please include an example which actually has a reasonably large state action space. Most problems that are used in practice e.g. autonomous vehicles or estimation of volatility usually have horizons and state-action spaces that are significantly larger then what is described here. Without a stronger, or clearer theoretical contribution I think more experiments illustrating your point would be helpful.\n\n# Citations Mentioned\n(1) https://dl.acm.org/doi/abs/10.1145/1015330.1015430\n\n(2) https://proceedings.neurips.cc/paper/2007/file/ca3ec598002d2e7662e2ef4bdd58278b-Paper.pdf\n\n(3) https://arxiv.org/pdf/2102.06924.pdf", "limitations": "1. Poor experimental evaluation.\n2. Incremental theoretical contribution. \n3. Poor writing quality and paper organization.\n4. Code not included in supplemental material.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. I really like the intended theme of the paper. I think that many results that I have seen in terms of work in online learning and minimax problems ignore crucial issues that lead to either algorithms that function poorly in practice or bounds that are effectively meaningless.  \n2. I think focusing on different assumptions that don't hold, or produce vacuous bounds is a great way to move the field forward.\n\n# Weaknesses\n1. Almost all the challenged assumption statements are imprecise and difficult to interpret.\n2. All experiments  are on examples that are so small as to be unrealistic for problem classes which are considered in practice. \n3. The statement of assumptions is extremely sparse, making verification of the novelty of this work difficult.\n4. The statement of the results and how to interpret them was also quite confusing. \n5. Work ignores some of the first apprenticeship learning algorithms that actively analyze how working with inexact state-occupancy affects algorithm performance and regret.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M05P4xg6EbV", "reviewer": "Reviewer_EMAG", "summary": "This paper analyzes the setting of convex reinforcement learning, where the objective is a function (mostly convex) of the state visitation distribution induced by an agent's policy.\nThe convex RL formulation as has been recently defined optimizes an objective that assumes access to the agent policy's state visitation distribution after executing this policy for an infinite number of trajectories. In practice, the objective is optimized using finite samples.\n\nThe paper argues that optimizing this infinite trials objective is not equivalent to optimizing the finite trials objective due to Jensen's inequality, and could lead to sub-optimal results. It also shows that the above mismatch does not exist for the setting of maximizing undiscounted cumulative rewards, due to the linear relationship between the state visitation distribution and the rewards vector in that setting.\n\nThen, the paper further analyses the specific setting of a convex RL in a single trial. Here, the paper shows that casting the convex RL problem into an extended MDP where the state space is augmented to include all possible histories allows the problem to be cast into a linear reward setting, and thus allows it to be solved using finite trial RL settings. However, the policy space here scales exponentially with the horizon in this setting. The rest of the analysis considers the ramifications of instead casting this problem as a partially observable MDP (POMDP) or through the lens of online learning.\n\nFinally, the paper backs up the analysis with some illustrative examples which optimize three objectives used in convex RL by optimizing the finite trials objective directly or instead optimizing the infinite trials objective with a finite number of trials. These examples seem to bear out the analysis in the paper.", "questions": "## Suggestions:\n* While Section 5 adds some depth to the analysis of the paper, it also seems slightly off topic for the paper. Better motivation for section 5, and a greater preview of these results in the beginning of Section 5 as well as the introduction would be helpful.\n* Citation number [30] from the paper has been published at a peer-reviewed conference. It would be better to use that citation [3] instead of ArXiv.\n\n## Questions:\n* Could ideas that try to characterize the full distribution induced by the agent's policy [1] and correct for the sampling error [2] be useful for optimizing the infinite trajectory objective with some off-policy correction?\n\n### References:\n[3] Zahavy, Tom, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. \"Reward is enough for convex MDPs.\" Advances in Neural Information Processing Systems 34 (2021): 25746-25759.", "limitations": "Adequately", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* The paper's main result is fairly simple, straightforward, and impactful. It brings to light a discrepancy that might negatively affect applications of RL to convex objectives of the state visitation distribution.\n* The analysis is clear, and the reason for the discrepancy pointed out is acceptable.\n* The idea behind the illustrative examples is sound, and they are set up to validate the main idea of the paper.\n* Section 5 adds in some depth to the analysis in the paper, and takes some steps to propose possible ways in which the finite trials objective might be optimized.\n\n## Weaknesses\n\n* While the idea behind the illustrative examples is well-intentioned, the way the results are presented leaves something to be desired. For example, in Figures 4 (d), (e), and (f), what is the x-axis?\n* The text and Figure 4 caption contradict each other. Text: \"optimal finite trials policy $\\pi^\\dagger$ and the optimal infinite trials policy $\\pi^*$\". Caption: \"With $\\pi^*$ we denote an optimal finite trial policy, with $\\pi^\\dagger$ an optimal infinite trial policy\".\n* The related work would be better rounded out by considering work in linear RL that has considered analyzing the full distribution induced by an agent's policy [1] and also work that has considered the impact of finite samples in such settings [2].\n\n### References:\n[1] Chandak, Yash, Scott Niekum, Bruno da Silva, Erik Learned-Miller, Emma Brunskill, and Philip S. Thomas. \"Universal off-policy evaluation.\" Advances in Neural Information Processing Systems 34 (2021): 27475-27490.\n\n[2] Pavse, Brahma, Ishan Durugkar, Josiah Hanna, and Peter Stone. \"Reducing sampling error in batch temporal difference learning.\" In International Conference on Machine Learning, pp. 7543-7552. PMLR, 2020.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JjiKdKF9POK", "reviewer": "Reviewer_J5z6", "summary": "The paper points out that the usual way convex RL is formulated implicitly assumes infinite trials, which can be a problem when learned policies are used in a finite number of trials (i.e., any application). The paper then introduces a formulation of convex RL that is appropriate for use with a finite number of trials, proves an upper bound on the approximation error introduced by optimizing the infinite trials objective instead of the finite trials objective, validates this bound empirically, and highlights other questionable assumptions from the convex RL literature.", "questions": "1. Could the authors better motivate Section 5.3 at the start of the section? At the end of the section it concludes that $\\mathcal{F}$-specific algorithms will need to be developed for each of the specific instances of convex RL, but up until that point it was not really clear to me why we were doing this regret analysis.\n1. Could the authors elaborate on why OPE-UCBVI is a principled algorithm for this setting? Is it near optimal? Is the regret analysis for this single algorithm actually a good representation of how hard the problem is?\n1. How exactly were the policies in Section 6 arrived at? The text says they were obtained by optimizing the finite trial objective, but does not elaborate.\n1. Can existing algorithms for optimizing the infinite trials convex RL objective be easily modified to optimize the finite trials version? It seems very unlikely, given the reduction of convex MDPs to extended MDPs and POMDPs. It would be good to emphasize this takeaway throughout the paper (at least in the conclusion), as it has the biggest implications for other researchers in the area; their algorithms are unlikely to transfer directly to the finite trials convex RL objective.\n1. Is the optimal policy in Figure 4 (c, f) also non-Markovian?\n1. Can the authors expand the discussion of related works [6] and [7] to clarify how the paper's contributions differ? A related works section is better if it not only summarizes related work but also explains how the current work is different/similar to the related work.\n\n### Suggestions\n- The caption for Figure 4 contradicts the text in the paragraph starting at line 268 about whether the optimal finite trials policy is $\\pi^*$ or $\\pi^\\dagger$.\n- It would be good to clarify the x-axes in Figure 4.\n- Line 278: the text describes a reward vector \"r\", but the definition of $\\mathcal{F}$ for risk-averse RL doesn't contain an \"r\" anywhere. Should \"r\" be $\\lambda$ or vice versa?", "limitations": "The paper addressed a limitation of the bound on the approximation error, stating that it's not instance-dependent, as well as the limitation of the finite trials objective being less expressive in terms of policy orderings w.r.t. infinite trials convex RL.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nTo the best of my knowledge, the contributions in this paper are novel, but I am not an expert in convex RL.\n\n### Quality\nThe paper seems very well-done; I couldn't find many issues with quality. I would've liked to see more explicit discussion of the implications of the proposed finite-trials convex RL objective, but there was a good amount.\n\n### Clarity\nThe paper is extremely well-written and clear, with both the text and derivations being easy to follow. Actually a joy to read. This is very important for a paper pointing out a problem with the conventional way of doing things.\n\n### Significance\nThe paper points out an issue with the current convex RL formulation, which includes several important sub-fields of RL, such as risk-averse RL, imitation learning, diverse skills discovery, constrained RL, etc. For this reason, the paper could be very significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept