Reward is enough for convex MDPs
Authors: Tom Zahavy
Brendan O'Donoghue
Guillaume Desjardins
Satinder Singh
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: reinforcement-learning
convex optimisation

Abstract: Maximising a cumulative reward function that is Markov and stationary, i.e., defined over state-action pairs and independent of time, is sufficient to capture many kinds of goals in a Markov decision process (MDP). However, not all goals can be captured in this manner. In this paper we study convex MDPs in which goals are expressed as convex functions of the stationary distribution and show that they cannot be formulated using stationary reward functions. Convex MDPs generalize the standard reinforcement learning (RL) problem formulation to a larger framework that includes many supervised and unsupervised RL problems, such as apprenticeship learning, constrained MDPs, and so-called `pure exploration'. Our approach is to reformulate the convex MDP problem as a min-max game involving policy and cost (negative reward) `players', using Fenchel duality. We propose a meta-algorithm for solving this problem and show that it unifies many existing algorithms in the literature.

Reward is Enough for Convex MDPs
Tom Zahavy
Brendan O'Donoghue
DeepMind, London
DeepMind, London derhegnndudddeeeiidn.commmm
tomzahavy @deepmind.com
Guillaume Desjardins
Satinder Singh DeepMind, London baveja @ deepmind.com
DeepMind, London gdesjardins @ drsejaaddnn@deeeedndd.oom
Abstract
Maximising a cumulative reward function that is Markov and stationary, i.e., de- fined over state-action pairs and independent of time, is sufficient capture many kinds of goals in Markov decision process (MDP). However, not all goals can be captured in this manner. In this paper study convex MDPs in which goals are expressed as convex functions of the stationary distribution and show that they cannot be formulated using stationary reward functions. Convex MDPs gen- eralize the standard reinforcement learning (RL) problem formulation to a larger framework that includes many supervised and unsupervised RL problems, such apprenticeship learning, constrained MDPs, and so-called 'pure exploration', Our approach reformulate the convex MDP problem as min-max game involving policy and cost (negative reward) 'players', using Fenchel duality. We propose a meta-algorithm for solving this problem and show that unifies many existing algorithms in the literature.
1 Introduction
In reinforcement learning (RL), an agent learns how to map situations to actions as maximize a cumulative scalar reward signal. The learner is not told which actions to take, but instead must discover which actions lead to the most reward [64]. Mathematically, the RL problem can be written as finding policy whose state occupancy has the largest inner product with reward vector (55 iee.
the goal of the agent to solve
RL:
max de EKC
[r(s,))d
8,0
where dg is the state-action stationary distribution induced by policy æ and the set of admissible stationary distributions (see Definition lp. A significant body of work is dedicated to solving the RL problem efficiently in challenging domains 45 62). However, not all decision making problems of interest take this form. In particular we consider the more general convex MDP problem, min f(dx),
Convex MDP:
d.
where f: K. + F. is convex function. Sequential decision making problems that take this form include Apprenticeship Learning (AL), pure exploration, and constrained MDPs, among others; see Table I In this paper prove the following claim:
We can solve Eq. (2) by using any algorithm that solves Eq. as a subroutine.
In other words, any algorithm that solves the standard RL problem can be used to solve the more general convex MDP problem. More specifically, make the following contributions.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Firstly, we adapt the meta- altorithg of Abernethy and Wang B3] for solving Eq. ( The key idea is use Fenchel duality to convert the convex MDP problem into a two-player zero-sum game between the agent (henceforth, policy player) and an adversary that produces rewards (henceforth, cost player) that the agent must maximize [3] [6. From the agent's 's point of view, the game is bilinear, and so for fixed rewards produced by the adversary the problem reduces to the standard RL problem with non-stationary reward (Fig. I..
Secondly, we propose a sample efficient pol- icy player that uses a standard RL algorithm (eg. 60), and computes an optimistic policy with respect the non-stationary reward each iteration. In other words, we use algorithms that were developed to achieve low regret in the stan- dard RI. setup, to achieve low regret as policy players in the min-man min--mxx game we formulate to solve the convex MDP. Our main result is that the average of the policies produced by the pol- icy player converges to solution to the convex MDP problem (Eq. 2 ) Inspired by this princi- ple, we also propose recipe for using deep-RL RL (DRL) agents to solve convex MDPs heuristically; provide the agent non non-stationary rewards from the cost player. We explore this principle in experiments.
Agent
Action
T
Player
Flaoy Vi
Environment
Figure 1: Convex MDP RL problem
Finally, we show that choosing specific algorithms for the policy and cost players unifies several disparate branches of RL problems, such as apprenticeship learning, constrained MDPs, and pure exploration into single framework, as we summarize in Table T
Convex objective f
Cost player
Policy player
Application
A A- ld dElli
FTL
RL
(Standard) RL with -À as stationary reward function
FTL
Best response
Apprenticeship learning (AL) 75
dg log(de)
FTL
Best response
Pure exploration
30
Id, dgllo
OMD
Best response
Al. [66. 65
Be (dc. (dr - dg(c)))
OMD
Best response
Inverse RL in contextual MDPs
10
d1 dd. s.t. d2 dr S
OMD
RI.
Constrained MDPs 67
12
dist(dz, Cjtt
OMD
Best response
Feasibility of convex envex-constrained MDPs
44
mind......
dt An maxxEA d. (dl dg)
OMD
RI.
Adversarial Markov Decision Processes
55
OMD
RL
Online AL [6], Wasserstein GAIL
73
78
KL(da de)
FTL
RL
GAIL 31 state marginal matching
(dd Br
FTL
RL
Diverse skill discovery
20 27
Table Instances of Algorithm in various convex MDPs. as well as other KL divergences. f context variable. tf C convex set. f is concave. See Sections 4 6 more details.
2 Reinforcement Learning Preliminaries
In RL an agent interacts with an environment over number of time steps and seeks to maximize its cumulative reward. We consider two cases, the average reward case and the discounted case. The Markov decision process (MDP) is defined by the tuple (S, A, P. R) for the average reward case and by the tuple (S, A, P. R, 7, do) for the discounted case. We assume an infinite horizon, finite state-action problem where initially, the state of the agent is sampled according to 8g do, then at each time t the agent is in state E S, selects action E A according to some policy ((s.)) +), receives reward rt- R(st, 0z) and transitions new state 81+1 E 5 according to the probability distribution P(-, St, a.). The two performance metrics we consider are given by
T
Jave lim T00
T1:
=
FF
TT
T
for the average reward case and discounted case respectively. The goal of the agent find a policy that maximizes Javg J7 Any stationary policy π induces state-action occupancy measure dx.

---

which measures how often the agent visits each state-action when following Let P= = -) be the probability measure over states time under policy n, then
T E
(s,
lim T0000
(s (), -
= =1
(1-7)E Σ 2 (
for the average reward case and the discounted case respectively. With these, we can rewrite the RL objective in Eq. (3) in terms of the occupancy measure using the following well-known result, which for completeness we prove in Appendix
Proposition 1. For both the average and the discounted case, the agent objective function Eq. 3 can be written in terms of the occupancy measure as J = = r(s, a) (s,
Given an occupancy measure it is possible to recover the policy by setting T(s, a) d, (s, a)/ E. (s, a) if E. (s, > O, and T(S, a) = 1/|A| otherwise. Accordingly, in this paper shall formulate the RL problem using the state-action occupancy measure, and both the standard RL problem (Eq. (T) and the convex MDP problem (Eq. 2 are convex optimization problems in variable dz. For the purposes of this manuscript do not make distinction between the average and discounted settings, other than through the convex polytopes of feasible occupancy measures, which define next.
Definition 1 (State-action occupancy's polytope admissible state-action occupancies is
555
For the average reward case the set of
Kavg {dz dx O.
= de( (') vs E 5},
and for the discounted case it is given by K., = [d= dx 20,
-1 (11 +2 Σ a'dd Va E).
st
We note that being a polytope implies that K. is convex and compact set.
The convex MDP problem is defined for the tuple (8, A, in the average cost case and (S, A, P. do)) the discounted case. This tuple defining state-action occupancy's 's poly- tope IC (Definition D. and the problem is to find a policy ı whose state occupancy d, is in this polytope and minimizes the function (Eq. 2b)
Meta-Algorithm for Solving Convex MDPs via RL
To solve the convex MDP problem (Eq. (2) we need find occupancy measure d, (and associated policy) that minimizes the function f. Since both f IC - IR and the set are convex this is a convex optimization problem. However, it is challenging
due the nature of learning about the
environment through stochastic interactions. In this section we show how to reformulate the convex MDP problem (Eq. (2) so that standard RL algorithms can be used solve it, allowing to harness decades of work on solving vanilla RL problems. To do that we will need the following definition.
Definition (Fenchel conjugate). For a function f IR" + RU (-00 20), ,, its Fenchel conjugate is denoted fr IR + R f-00, )c} and defined as f*) sup,, x y-yy-floo f(y).
Remark 1. The Fenchel conjugate function f is always convex (when it exists) even if f is not. Furthermore, the biconjugate f (f*)* equals if and only if f is convex and lower semi- continuous.
Using this we can rewrite the convex MDP problem (Eq. 22 as
OOPT
f(d+) min max (A dz (*))) = max min (A 1A-d, dr - (*))) d.Ek
min
(4)
d+ER xEA
XEA d.ek
where A is the closure of (sub-)gradient space (af(d |dd, E K.), which a convex set Theorem 4]. As both sets are convex, this is convex-concave saddle-point problem and zero-sum two-player game (54] [49], and we were able to swap the order of minimization and maximization using the minimax theorem [7]].
3

---

With this we define the Lagrangian =( p- (A). For a fixed À A, minimizing the Lagrangian is standard RL problem of the form of Eq. T i.e., equivalent to maximizing a reward r = -X. X. Thus, one might hope that by producing optimal dual variable X we could simply solve d = argming, EK L( X*) for the optimal occupancy measure. However, the next lemma states that this is not possible in general.
Lemma 1, There exists an MDP M and convex function I for which there is no stationary reward E RSA such that arg maxd, EK d,- arg mina,ek f(dz).
To see this note that for any reward r there is a deterministic policy that optimizes the reward 55 but for some choices of deterministic policy is optimal, eg, when is the negative entropy function. This result tells us that even if we have access to an optimal dual-variable we cannot simply use it to recover the stationary distribution that solves the convex MDP problem in general.
To overcome this issue we develop an algorithm that generates a sequence of policies (T*) such that the average converges to an optimal policy for Eq. ( i.e., (1/KEK E= di + d² E arg mina,ex: f(dz). The algorithm we develop is described in Algorithm I and is adapted from the meta-algorithm described in Abernethy and Wang [3. It is referred to as a meta-algorithm since relies on supplied sub-routine algorithms Alg, and Algx- The reinforcement learning algorithm Alg, takes as input a reward vector and returns a state-action occupancy measure d-. The cost algorithm Alg, can be a more general func- tion of the entire history. We discuss concrete examples of Alg, and Algx in Section 4
JEEN
Algorithm 1: meta-algorithm for convex MDPs
1: Input: convex-concave payoff L: K. x A - R, algorithms Alg,, Alg K KEN
2: for k I..... K do
3: A Alg, (dt ...... 1
4: d= = Alg, ( (-)²)
5: end for
6:
Return dk = K Lk=l tk T
K
K E x
In order to analyze this algorithm we will need a small detour into online convex optimization (OCO). In OCO, learner is presented with sequence of K convex loss functions E1, -2.-.. Eg K. TR.
and at each round must select a point 2g E K. after which it suffers a loss of & (xx)). At time period k the learner is assumed to have perfect knowledge of the loss functions .,....; Ek-1- The learner wants to minimize its average regret, defined as
K Σ (x(x)
K
Rx = K
Σ (x)) BEK
k=1
In the context of convex reinforcement learning and meta-algorithm 1 the loss functions for the cost player are 1 = -[,, )²), and for the policy player are ex = L(d,, )), with associated average regrets R&% and R This brings us to the following theorem.
Theorem (Theorem A. Assume that Alg, and Alg have guaranteed average regret bounded as R < EK and R2 < δg. respectively. Then Algorithm 1 outputs di and X satisfying mind, EK: L(de, X 2 poPT EK ōx and maxλeλ L(ik X) poPr +ex + ōg.
This theorem tells us that so long as the RL algorithm we employ has guaranteed low-regret, and assuming we choose reasonable low-regret algorithm for deciding the costs, then the meta-algorithm will produce a solution to the convex MDP problem (Eq. (2) to any desired tolerance, this hecause jort < f (dk = max, L(dk A) S SOPT+EK + +ōK. For example, we shall later present algorithms that have regret bounded as сg 5g S <O(/VK)), which case we have
+EK
- JOP < O(IVKK).
(5)
Non-Conver f. Remark implies that the game maxλeλ mina, ex (A d, fx is concave- convex for any function f. so we can solve with Algorithm I even for non-convex f. From weak duality the value of the Lagrangian on the output of Algorithm | L(dz, X), is a lower bound on the optimal solution nopt. In addition, since [(dz) always an upper bound on foPr we have both an upper bound and lower bound on the optimal value: L(d,, X) < fOPT < f(dx).

---

Policy and Cost Players for Convex MDPs
In this section we present several algorithms for the policy and cost players that can be used in Algorithm I Any combination of these algorithms is valid and will come with different practical and theoretical performance. In Section 6 correspond to partieular choices of cost and policy players and so fall under our framework.
we show that several well known methods in the literature
In addition, in this section we assume that
Amax
max maX A(s, a)l < <0, AEA 8.0
which holds when the set A is compact. One way to guarantee that A is compact to consider functions ff with Lipschitz continuous gradients (which implies bounded gradients since the set K. is compact). For simplicity, we further assume that Amax I 1. By making this assumption we assure that the stationary rewards produced by the cost player bounded by 1 as usually done in RL.
4.1 Cost Player
Follow the Leader (FTL) is a classic OCO algorithm that selects d to be the best point in hindsight. In the special case of convex MDPs, defined in Eq. 44. FTL has simpler form:
A arg max
Σ j=1 C(d A) = arg max XEA
A Σ j=1 de -
- -V
(6)
XEA
where - k-1 de and the last equality follows from the fact that (V/*)- = f 56 The
average regret of FTL is guaranteed be Rx S c/ e/VV K under some assumptions 29 In some cases, and specifically when the set IC is polytope and the function is strongly convex, FTL can enjoy logarithmic or even constant regret; see 332 29 for more details.
Online Mirror Descent (OMD) uses the following update [4 9
*
arg max (() ((A->--1) VxL(d= x + an (A,
XEA
where og is a learning rate and B, is a Bregman divergence [4] For B, 0.5 I. we get online gradient descent 779 and for (x) x log(x)) we get multiplicative weights special cases. We also note that OMD is equivalent to linearized version of Follow the Regularized Leader (FTRL) 43 288 The average regret of OMD is Rx I c/vK under some assumptions, see, for example 28
4.2
Policy Players
4.2.1 Best Response
In OCO, the best response is to simply ignore the history and play the best option on the current round, which has guaranteed average regret bound of Rx < (this requires knowledge of the current loss function, which is usually not applicable but this case). When applied to Eq. 4). it is possible to find the best response dx using standard RL techniques since
d arg min CK
Cx X²) arg min df A (**(t)) arg max df (-x#), d.ek
d.ek
which an RL problem for maximizing the reward (-x+). principle, any RL algorithm that eventually solves the RL problem can be used to find the best response, which substantiates our claim the introduction. For example, tabular Q-learning executed for sufficiently long and with a suitable exploration strategy will converge to the optimal policy [72). In the non-tabular case we could parameterize a deep neural network to represent the Q-values (45 and the network has sufficient capacity then similar guarantees might hold. We make no claims on efficiency or tractability of this approach, just that principle such an approach would provide the best-response at each iteration and therefore satisfy the required conditions to solve the convex MDP problem.
5

---

4.2.2 Approximate Best Response
The caveat in using the best response as a policy player is that in practice, it can only be found approximately by executing an RL algorithm in the environment. This leads to defining an approximate best response via the Probably Approximately Correct (PAC) framework. We say that policy player PAC 5), if it finds an e-optimal policy to an RL problem with probability of at least addition, we say that policy n' is 6-optimal if its state occupancy d' is such that
In
max dx (-X*) (->x)) S. dyEK
For example, the algorithm in [40] can find an e-optimal policy to the discounted RL problem after seeing O (1-
SA log())) samples; and the algorithm in [36] can find an e-optimal policy for the
average reward RL problem after seeing O SA.SA log( (t)) samples, where mix is the mixing time (see, eg. [42 76 for a formal definition). The following Lemma analyzes the sample complexity of
Algorithm] T with an approximate best response policy player for the average reward RL problem [36].
The result can be easily extended to the discounted case using the algorithm in [4)). Other relaxations
to the best response for specific algorithms can be found in 66
33
30
Lemma 2 (The sample complexity of approximate best response in convex MDPs with average occupancy measure). For convex function f. running Algorithm [ith oracle cost player with regret RiK = O(1/K) and an approximate best response policy player that solves the average reward RL problem in iteration k to accuracy E = 1/k returns an occupancy measure d that satisfies of [d ) foPT I with probability 1 - 8 after seeing (f SA log(2K (og(2K)cd)// e2 samples. Similarly, for Rx O(IVKK), setting 6 1/ 1/V/ /i requires (1 SA (2)))) samples.
4.2.3 Non-Stationary RL Algorithms
We now discuss a different type of policy players; instead of solving an MDP to accuracy e, these algorithms perform single RL update the policy, with cost -Ag. In our setup the reward is known and deterministic but non-stationary, while in the standard RL setup it is unknown, stochastic, and stationary. We conjecture that any RL algorithm can be adapted to the known non-stationary reward setup we consider here. In most cases both Bayesian [5] 48) and frequentist B 35
approaches to the stochastic RL problem solve a modified (eg, by adding optimism) Bellman equation at each time period and swapping in a known but non -on-ssationnay reward is unlikely to present a problem.
To support this conjecture shall prove that this is exactly the case for UCRL2 355. UCRL22 is an RI. algorithm that was designed and analyzed in the standard RI. setup, and we shall show that it is easily adapted to the non-stationary but known reward setup that we require. To make this claim more general, we will also discuss a similar result for the MDPO algorithm [1 that was given in a slightly different setup.
UCRL2 is a model based algorithm that maintains an estimate of the reward and the transition function well as confidence sets about those estimates. In case the reward at time k is known, so we only need to consider uncertainty in the dynamics. UCRL2 guarantees that in any iteration k the true transition function is in a confidence set with high probability, i.e., P E Pa for confidence set Pk. If we denote by J.P.R the value of policy æ in an MDP with dynamics P and reward R then the optimistic policy is मे arg max, ea J Acting according to this policy guaranteed to attain low regret. In the following results for UCRL2 we will use the constant D, which denotes the diameter of the MDP, see [35] Definition 1] for more details. In the supplementary material (Appendix ED. we provide a proof sketch that closely follows (35].
Lemma 3 (Non stationary regret of UCRL2). For an MDP with dynamics P. diameter D, an
arbitrary sequence of known and bounded rewards fr² :max,,a a (r'(s, a)) < 1 ssuch that the optimal average reward at episode k, with respect to P and Tu is Jž. then with probability at least
i-1;
1-8, the average regret of UCRL2 is at most Rx = 1
K E J < O(DS /A Alog(K/6)/K))
Next, we give a PAC(e, d) sample complexity result for the mixed policy # K that is produced by running Algorithm [ with UCRL2 as a policy player.

---

Lemma 4 (The sample complexity of non stationarr RL algorithms in convex MDPs), For a convex function I, running Algorithm | with oracle cost player with regret R'x S co/ v K and UCRL2 as a policy player returns an occupancy measure d that satisfies [d fort S with probability
1 - after K =0 ( D2 log( ) steps.
6
MDPO. Another optimistic algorithm is Mirror Descent Policy Optimization 660] MDPO]. MDPO
is a model free RI algorithm that is very similar to popular DRI. algorithms like TRPO 58 and
MPO 12 In 24 59 51. the authors established the global convergence of MDPO and in [1 the
authors showed that MDPO with optimistic exploration enjoys low regret.
The analysis for MDPO is given in a finite horizon MDP with horizon Ht, which is not the focus of our paper. Nevertheless, to support our conjecture that any stochastic RL algorithm can be adapted to the known non-stationary reward setup, quickly discuss the regret of MDPO in this setup. We also note that MDPO is closer to practical DRL algorithms [70]. In a finite horizon MDP with horizon H and known, non-stationary and bounded rewards, the regret of MDPO is bounded by Rs OHHSSV//RR A/ 61 Lemma 4] with high probability.
To compare this result with UCRL2, we refer to a result from [57]. which analyzed UCRL2 in the adversarial setup, that includes our setup
special case. In finite horizon MDP with horizon
H was shown that setting = -SA/ K with probability 1 - 8 its regret is bounded by Rx S
O A log( K)/K)
57 Corollary 5]. which is better by a factor of H than MDPO.
Discussion. Comparing the results in Lemma 4 with Lemma Lemmaassuggests suggests that using an RL algorithm with non stationary reward as a policy player requires O(1/e²) samples to find an opptimal policy, while using approximate best response requires O(1/e"). In first glance, this results also improves the previously best known result Hazan al. [30] for approximate Frank- (FW) that requires O(1/c²) samples. However, there are more details that have to be considered as we now discuss.
Firstly. Lemma I and Lemma 2 assume access to an oracle cost player with some regret and do not consider how to implement such cost player. The main challenge is that the cost player does not have access to the true state occupancy and must estimate from samples. If we do not reuse samples from previous policies to estimate the state occupancy of the current policy we will require O(1 (() trajectories overall 30 better approach would use the samples from previous episodes learn the transition function. Then, given the estimated transition function and the policy, we compute an approximation of the state occupancy. We conjecture that such an approach would lead to a O(1/e") sample complexity, closing the gap with standard RL.
Secondly, while our focus is on the dependence in e, our bound Lemma 4 is not tight in 6, i.e., scales with 1/8² where it should be possible to achieve log(1/8) scaling, Again we conjecture an improvement the bound is possible; see, eg, 38 Appendix F.].
Convex Constraints
We have restricted the presentation so far to unconstrained convex problems, in this section we extend the above results to the constrained case. The problem we consider
min eK
(dz)
subject to gs (d=) S 0, 1= m,
where f and the constraint functions g, are convex. Previous work focused on the case where both f and are linear 77 67 developed before, but now taking into account the constraints. Consider the Lagrangian
12
68 18. 16 11]. We can use the same Fenchel dual machinery we
L(d = f(dx) + Σ. m
i-1 (=g:(d,)) = max (v- dx fz)))) + Σ
i-1 M4 max (d, gf (v:)). o,
over dual variables μ 2 O. with new variables v, and v. At first glance this does not look convex- concave, however we can introduce new variables G; = μ4 to obtain
L(da, p. v, ,I...., = v. = - (z)
Σn i= (da - (G//p)
(7)
This is convex (indeed affine) in dz and concave in (v, M4 Si,..., Sm), since it includes the perspective transform of the functions 9: [13]. The Lagrangian involves cost vector, + Σm S. linearly
7

---

interacting with d,, and therefore we can use the same policy players as before to minimize this cost. For the cost player, possible to use OMD on Eq. ( jointly for the variables v, f and ç. It is more challenging to use best-response and FTL for the cost-player variables as the maximum value of the Lagrangian is unbounded for some values of dz. Another option is to treat the problem as three-player game. In this case the policy player controls d,, as before, one cost player chooses (v, Ci..... Sm) and can use the algorithms we have previously discussed, and the other cost player chooses i with some restrictions on their choice of algorithm. Analyzing the regret in that case is outside the scope of this paper.
6 Examples
In this section we explain how existing algorithms can be seen as instances of the meta-algorithm for various choices of the objective function f and the cost and policy player algorithms Alg, and Alg We summarized the relationships in Table
6.1 Apprenticeship Learning
In apprenticeship learning (AL), have MDP without an explicit reward function. Instead, an expert provides demonstrations which are used to estimate the expert state occupancy measure dg- Abbeel and Ng [ formalized the AL problem as finding policy æ whose state occupancy is close to that of the expert by minimizing the convex function f(d,) = =|da dell. The convex conjugate of f is given by (y) y dg if [ly]|. S 1 and oo otherwise, where || |l. denotes the dual norm. Plugging f into Eq. (4) results in the following game:
min 1|dx dell EK
min max X dr - dg. A.g.. EX [|A||,
(8)
Inspecting Eq. (8
we can see that the norm in the function f that is used to measure the distance from the expert induces constraint set for the cost variable, which a unit ball the dual norm.
Alg,=OMD Alg,=Best Response/RL. The Multiplicative Weights AL algorithms 65 MWAL] was proposed to solve the AL problem with (dx) = ||d= - d It uses the best response as the policy player and multiplicative weights the cost player special case of OMD). MWAL has also been used to solve AL in contextual MDPs [00] and to find feasible solutions to convex-constraine
MDPs 44]. We note that in practice the best response can only be solved approximately, as we discussed in Section 4 Instead, in online AL [61] the authors proposed to use MDPO as the policy player. which guarantees regret bound of Rx S c/vK. K. They showed that their algorithm is equivalent to Wasserstein GAIL
78
and in practice tends to perform similarly to GAIL.
AIT, Alg, :Best Response. When the policy player plays the best response and the cost player plays FTL, Algorithm is equivalent to the Frank-Wolfe algorithm (22 for minimizing f (Eq. ). Pseudo-code for this is included in the appendix (Algorithm B. The algorithm finds point dh E K that has the largest inner-produc (best response) with the negative gradient (i.e., FTL).
Abbeel and Ng [ proposed two algorithms for AL, the projection algorithm and the max mar- gin algorithm. The projection algorithm is essentially a FW algorithm, as was suggested in the supplementary [I] and was later shown formally in (75). Thus, it is projection free algorithm in the sense that it avoids projecting dz into K,, despite the name. their case the gradient is given by (dz)) dz dg. Thus, finding the best response is equivalent to solving an MDP whose reward is dg - dy. In a similar fashion, FW can be used to solve convex MDPs more generally [30]. Specifically, in (30), the authors considered the problem of pure exploration, which they defined as finding a policy that maximizes entropy.
Fully Corrective FW. The FW algorithm has many variants (see 33 for a survey) some of which enjoy faster rates of convergence in special cases. Concretely, when the constraint set a polytope, which is the case for convex MDPs (Definition []. some variants achieve a linear rate of convergence 34 75 One such variant the Fully corrective FW, which replaces the learning rate update (see line 4 of Algorithm in the supplementary), with mininization problem over the convex hull of occupancy measures at the previous time-step. This is guaranteed be at least as good as the learning rate update. Interestingly, the second algorithm of Abbeel and Ng []] the max margin algorithm, is
8

---

exactly equivalent to this fully corrective FW variant. This implies that the max- margin algorithm enjoys a better theoretical convergence rate than the 'projection'' variant, as was observed empirically in [
6.2 GAIL and DIAYN: Alg,=FTL, Alg, =RL
We now discuss the objectives of two popular algorithms, GAIL [3] and DIAYN 20], which perform AL and diverse skill discovery respectively. Our analysis suggests that GAIL and DIAYN share the same objective function. In GAIL,, this objective function minimized, which a convex MDP, however, in DIAYN it is maximized, which is therefore not convex MDP. We start the discussion with DIAYN and follow with a simple construction showing the equivalence to GAIL.
DIAYN. Discriminative approaches [26] 20 rely on the intuition that skills are diverse when they are entropic and easily discriminated by observing the states that they visit. Given probability space (St F, P), state random variables S f2 + S and latent skills Z 52 - 2 with prior the key term
of interest being maximized DIAYN 20 the mutual information:
T(S: Z) R. Ra Dog p(2|s) log
where di is the stationary distribution induced by the policy x(a 8, For each skill 2, this corresponds to standard RL problem with (conditional) policy x(a 8,2) and reward function r(s]=) = log p(zs))
log p(z). The first term encourages the policy to visit states for which the underlying skill has high-prre -roobbbbbayylity under the posterior p(z s). while the second term ensures high entropy distribution over skills. In practice, the full DIAYN objective further regularizes the
learnt policy by including entropy terms- log <a 5, 2). For large state spaces, p(=[s) is typically intractable and Eq. is replaced with a variational with learned discriminator go (2]s). Here, we focus the simple setting where is categorical
bound, where the true posterior is replaced
distribution over |Z| outcomes, yielding Z| policies n², and Oo is a classifier over these |z] skills with parameters 6.
We now show that a similar intrinsic reward can derived using the framework of convex MDPs. We start by writing the true posterior as function of the per-skill state occupancy d: = p(s 2), and di (s)p(a)
using Bayes rules, p(2(s) = Ex (s)p(E))
Combing this with Eq. yields:
log di (+)p(2)
E Eg ((()()))) - -[=)] Σ p(2) Σ di (s)
- logp(z)
Σx d4 (s)p(k)
Pp()) Σ p(k)dd E. (d
(10)
where KL denotes the Kullback-Leite divergence
39
Intuitively, finding a set of policies T R that minimize Eq. (10) will result in finding policies that visit similar states, measured using the KI. distance between their respective state occupancies J.....,d? d This is a convex MDP because the KL--divergence is jointly convex in both arguments 13 Example 3.19]. We will soon show that this the objective of GAIL. On the other hand, a set of policies that maximize Eq. (10) is diverse, as the policies visit different states, measured using the KL distance between their respective state occupancies d.....,d?
We follow on with deriving the FTL player for the convex MDP in Eq. (10). We will then show that this FTL player is producing an intrinsic reward that is equivalent to the intrinsic reward used in GAIL and DIAYN (despite the fact that DIAYN is not a convex MDP). According to Eq. (6) the FTL cost player will produce a cost A at iteration l given by
d=
d' d=p(2)
V de (L
Σ Σp(k)d=)
E log Σn dkk(k) log(p(=(s)) log(p(>)) +1 p(z|s)
+ 1
s>p(())
Σ. di (k))
E a>p(s)
(11)
Information
Grudient correction
where the equality follows from writing the posterior as function of the per-skill state occupancy d= = p(s =), and using Bayes rules, p(z]s) d' (s)p(=)
Replacing the posterior p(z[s) with
Σ. d (=)p(k))

---

rewards of DIAYN, with additional terms 1 1- pp( s) which we refer as "gradient correction" " terms, Inspecting the common scenario of uniform prior over the latent variables, p(z) = 1/ we get that the expectation of the gradient correction term Σ, p(=) - p(=ls)) = - 1 in each state. From the perspective of the policy player, adding constant to the reward does not change the best response policy, nor the optimistic policy, Therefore, the gradient correction term does not have an effect on the optimization under a uniform prior, and we retrieved the reward of DIAYN. These algorithms differ however for more general priors p(z), which we explore empirically in Appendix
a learnt discriminator (0(2]s) recovers the
GAIL. We further show how Eq. (10) extends to GAIL [3 via simple construction. Consider a binary latent space of size | = 2. where 2 corresponds to the policy of the agent and
corresponds to the policy of the expert which is fixed. In addition, consider a uniform prior over the latent variables, L.e, p(= = 1) = 2- By removing the constant terms in Eq. [1p. one retrieves the GAIL [ algorithm. The cost log(p(z) (2)))) is the probability of the discriminator to identify the agent, and the policy player is MDPO (which is similar to TRPO in GAIL).
Discussion
In this work reformulated the convex MDP problem convex-concave game between the agent and another player that is producing costs (negative rewards) and proposed a meta-algorithm for solving it.
We observed that many algorithms the literature can be interpreted as instances of the meta- algorithm by selecting different pairs of subroutines employed by the policy and cost players. The Frank- Wolfe algorithm, which combines best response with FTL, was originally proposed for AL
but can be used for any convex MDP problem as was suggested in [30]. Zhang et al. (77), unified the problems of RL, AL. constrained MDPs with linear constraints and maximum entropy exploration under the framework of convex MDPs. We extended the framework to allow convex constraints (Section [5) and explained the objective of GAIL as a convex MDP (Section 6.2). We also discussed non convex objectives (Section 3) and analyzed unsupervised skill discovery via the maximization of mutual information (Section 6.2) as a special case. Finally, we would like to point out recent work by Geist et al. (25), which was published concurrently to ours, and studies the convex MDP problem from the viewpoint of mean field games.
1 75
There are also algorithms for convex MDPs that cannot be explained as instances of Algorithm In particular, Zhang et al. [77] proposed a policy gradient algorithm for convex MDPs in which each step of policy gradient involves solving new saddle point problem (formulated using the Fenchel dual). This is different from our approach since we solve a single saddle point problem iteratively, and furthermore we have much more flexibility about which algorithms the policy player can use. Moreover, for the convergence guarantee 77 Theorem 4.5] to hold, the saddle point problem has to be solved exactly, while in practice it is only solved approximately (77 Algorithm 1], which hinders its sample efficiency. Fenchel duality has also been used in off policy evaluation (OPE) in [46] 74). The difference between these works and ours is that we train policy to minimize an objective, while in OPE a target policy is fixed and its value is estimated from data produced by a behaviour policy.
In order to solve practical convex MDP problem in given domain it would be prudent to use an RL algorithm that is known to be high performing for the vanilla RL problem as the policy player. From the theoretical point of view this could be MDPO or UCRL2, which we have shown come with strong guarantees. From the practical point of view using a high performing DRL algorithm, which may be specific the domain, will usually yield the best results. For the cost player using FTL, ie.. using the gradient of the objective function, is typically the best choice.
Acknowledgments and Disclosure of Funding
We would like to thank Yasin Abbasi- Yadkorie, Vlad Mnih, Jacob Abernethy, Lior Shani and Doina Precup for their comments and discussion on this work. Work done at DeepMind, the authors received no specific funding for this work.
10

---

References
[1] Abbeel and A. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference Machine learning, page 1. ACM, 2004.
[2] A. Abdolmaleki, J. T. Springenberg, Y. Tassa, R. Munos. N. Heess, and M. Riedmiller, Maximum a posteriori policy optimisation. arXiv preprint arXiv:1806.000 06920, 2018.
[3] J. D.D. D. Abernethy and J.-K. Wang. On frank-wold wolfe and equilibrium computation. In I. Guyon, U. V, Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https
Paper.pdf
[4] J. Achiam, H. Edwards, D. Amodei, and Abbeel. Variational option discovery algorithms. arXiv preprint /80. 2018.
[5] A. Agarwal, S. M. Kakade, J. D. Lec, and G. Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
[6] Agrawal and R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1405-1424. SIAM, 2014.
[7] E. Altman, Constrained Markov decision processes, volume 7. CRC Press, 1999.
[8] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272, 2017.
[9] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
[10] S. Belogolovsky, P. Korsunsky, Mannor, C. Tessler, and T. Zahavy. Inverse reinforcement learning in contextual mdps. Machine Learning. 2021.
[11] Bhatnagar and K. Lakshmanan. An online actor-crite algorithm with function approximation for constrained markov decision processes. Journal of Optimization Theory and Applications, 153(3):688-7000 2012.
[12] V. S. Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & control letters, 54(3):207-213, 2005.
[13] Boyd and L. Vandenberghe. Corvex optimization. Cambridge university press, 2004.
[14] L. M. Bregman. The relaxation method finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3::000-217, 1967.
[15] Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294 PMLR, 2020.
[16] D. A. Calian, D. J. Mankowitz, T. Zahavy, Z. Xu, J. Oh, N. Levine, and T. Mann. Balancing constraints and rewards with meta-gradient d4 In International Conference on Learning Representations, 2021. URL httpps:/opennevviwwnee//// www.pppennreiiii.e.e///ouummmmma
wwtttonttettteeett/occo iid Tid= UMP
[17] C. Dann and Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems, pages 281 218-2826, 2015.
[18] Y. Efroni, S. Mannor, and M. Pirotta. Exploration-eexpooitation in constrained mdps. arXiv preprint arXiv:2003.02188 2020.
[19] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, Ward, Doron, V. Firoiu, Harley, I. Dunning, S. Legg, and K. Kavukcuoglu. IMPALA: Scalable distributed deep-RI. with importance weighted actor-learner architectures. Proceedings of the 35th International Conference Machine Learning, 2018.

---

[20] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2019. URI httppp/s//ppmeeeeee..ee/oooo/ooa
[21] C. Florensa, Y. Duan, and P. Abbeel. Stochastic neural networks for hierarchical reinforcement learning. In International Conference on Learning Representations. 2016.
[22] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
[23] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 139, 1997.
[24] M. Geist, B. Scherrer, and O. Pictquin. A theory of regularized markov decision processes, In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
[25] M. Geist, J. Pérolat, M. Laurière, R. Elie, S. Perrin, O. Bachem, R. Munos, and O. Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint. arXiv preprint arXiv:2/06.03787 2021.
[26] K. Gregor, D. J. Rezende, and D. Wierstra. Variational intrinsic control. International Confer- ence on Learning Representations, Workshop Track, 2017. URL https://pearrevve.nee/frrmm id=Ske-Fo4Yg
[27] K. Hausman, J. T. Springenberg. Z. Wang, N. Heess, and M. Riedmiller. Learning an embedding space for transferable robot skills. In International Conference on Learning Representations, 2018. J
[28] E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-333 2016.
[29] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Machine Learning, 19(2-3):199-192 2007.
[30] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-2699 PMLR, 2019.
[31] J. Ho and S. Ermon. Generative adversarial imitation learning. arXiv preprint arXiv:1606.03476 2016.
[32] R. Huang, T. Lattimore, A. György, and C. Szepesvári. Following the leader and fast rates in linear prediction: Curved constraint sets and other regularities. In Advances in Neural Information Processing Systems, pages 4970-4978, 2016.
[33] M. Jaggi. Revisiting frank-wolfs Projection-fiee free sparse convex optimization. In Proceedings of the 30th international conference on Machine learning. ACM, 2013.
[34] M. Jaggi and S. Lacoste-Julien, On the global linear convergence of frank-wolfe optimization variants. Advances in Neural Information Processing Systems, 28, 2015.
[35] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563 2010.
[36] Y. Jin and A. Sidford. Efficiently solving mdps with stochastic mirror descent. In International Conference on Machine Learning, pages 4890-4900 PMLR, 2020.
[37] Y. Jin and A. Sidford. Towards tight bounds on the sample complexity of average-reward mdps. arXiv preprint 21X::2206.00046 2021.
[38] E. Kaufmann, Ménard, O. D. Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891. PMLR, 2021.
[39] S. Kullback. Information theory and statistics. Courier Corporation, 1997.
12

---

[40] T. Lattimore and M. Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.
[41] L. Lee, B. Eysenbach, E. Parisotto, E. Xing, S. Levine, and R. Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv: 1etiv:990..000 996.05274, 2019.
[42] D. Levin, Y. Peres, and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2017.
[43] B. McMahan. Follow-the serre-tt--rrgulaiiee---eeeeee II regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 525-533. JMLR Workshop and Conference Proceedings, 2011.
and mirror descent: Equivalence theorems and
[44] S. Miryoosefi, K. Brantley, H. Daumé III, M. Dudík, and R. Schapire. Reinforcement learning with convex constraints. arXiv preprint arXiv:1906.099:: 2019.
[45] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 5 518(7540):529-533 2015.
[46] O. Nachum, Y. Chow, B. Dai, and L. Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. arXiv preprint
04733, 2019.
[47] A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. In Wiley-Interscience,, 1983.
[48] B. O' O'Donoghue. Variational Bayesian reinforcement learning with regret bounds. arXiv preprint 1rXiv:1807.0066 080470947700.0.. 2018.
[49] B. O' D'onogguue T. Lattimore, and I. Osband. Stochastic matrix games with bandit feedback. arXiv preprint wrXiv:2006.05145 2020.
[50] B. O'Donoghue, Osband, and C. Ionescu. Making sense of reinforcement learning and probabilistic inference. In International Conference Learning Representations, 2020.
[51] I. Osband, D. Russo, and B. Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[52] I. Osband, C. Blundell, A. Pritzel, and B. V. Roy. Deep exploration via bootstrapped dqn. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4033-4041, 2016.
[53] I. Osband, Y. Doron, M. Hessel, J. Aslanides, E. Sezener, A. Saraiva, K. McKinney, T. Lattimore, C. Szepesvari, Singh, et al. Behaviour suite for reinforcement learning. In International Conference Learning Representations, 2019.
[54] M. J. Osborne and Rubinstein. course in game theory. MIT press, 1994.
[55] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 1984.
[56] R. T. Rockafellar. Convex analysis. Princeton university press, 1970.
[57] A. Rosenberg and Y. Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages 5478-5486. PMLR, 2019.
[58] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[59] L. Shani, Y. Efroni, and S. Mannor. Adaptive trust region policy optimization: Global conver- gence and faster rates for regularized mdps. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668-5675, 2020.
13

---

[60] L. Shani, Y. Efroni, A. Rosenberg, and S. Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8611 PMLR, 2020.
[61] L. Shani, T. Zahavy, and S. Mannor. Online apprenticeship learning. arXiv preprint arXiv:2102.06924, 2021.
[62] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550
(7676):354-355) 2017.
2017.
[63] A. L. Strehl and M. Littman. An analysis model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-133) 2008.
[64] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[65] U. Syed and R. E. Schapire. A game-theoretic approach to apprenticeship learning. In Advances nearal information processing systems, pages 1449-1456, 2008
[66] U. Syed, M. Bowling, and R. E. Schapire. Apprenticeship learning using linear programming. In Proceedings of the 25th international conference Machine learning, pages 1032-1039. ACM, 2008
[67] C. Szepesvári. Constrained mdps and the reward hypothesis, 2020. URL https://readingsml blogspot..m/222000//oossaaaaaaa settrraiiiddddd----a-e--- hendd--wwrd--ypooiie html
[68] C. Tessler, D. J. Mankowitz, and S. Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2019. URL httpss//openneview.neel forumm"d=SSffvssAPPP
[69] D. Tirumala, A. Galashov, H. Noh, L. Hasenclever, Pascanu, Schwarz, G. Desjardins, W. M. Czarnekki, A. Ahuja, Y. W. Teh, et al. Behavior priors for efficient reinforcement learning. 2020.
arXiv preprint arXiv:2010.
[70] M. Tomar, L. Shani, Y. Efroni, and M. Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.098/ 2020.
[71] Von Neumann. Zur theorie der gesellschaftsspiee.. Mathematische annalen, 100(1):295-320, 1928.
[72] C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8(3-4)277-292. 1992.
[73] H. Xiao, M. Herman, J. Wagner, S. Ziesche, J. Etesami, and T. H. Linh. Wasserstein adversarial imitation learning. arXiv preprint 1rXiv:1906.08113, 2019.
[74] M. Yang, O. Nachum, B. Dai, L. Li, and D. Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint arXiv:2007.03438, 2020.
[75] T. Zahavy, A. Cohen, H. Kaplan, and Y. Mansour. Apprenticeship learning via frank-wolfe. AAAI, 2020, 2020.
[76] T. Zahavy, A. Cohen, H. Kaplan, and Y. Mansour. Average reward reinforcement learning with unknown mixing times. The Conference on Uncertainty Artificial Intelligence (UAI), 2020.
[77] Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforeement learning with general utilities. arXiv preprint arXiv:2007.02115 2020.
[78] M. Zhang, Y. Wang, X. Ma, L. Xia, J. Yang, Z. Li, and X. Li. Wasserstein distance guided adversarial imitation learning with reward shape exploration. In 2020 IEEE 9th Data Driven Control and Learning Systems Conference (DDCLS), pages 165-1 1770. IEFF, 2020.
[79] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928-936 2003.
14


Reviews:
[{"review_id": "o6w-Afvnsav", "reviewer": "Reviewer_WgJu", "summary": "The paper discusses the problem of minimizing a convex function of the stationary distribution of a system with Markov dynamics, subject to the (convex) Bellman flow constraint and optionally subject to other convex constraints. The paper provides a family of algorithms designed to tackle this problem. It also proves results about sample complexity. The proposed framework is a significant innovation since it unifies several apprenticeship learning and imitation learning algorithms, which have been proved to be useful.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "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": "The submission is original and high-quality. It is clearly written despite the breadth of material it covers. The contribution is significant and a good match for NeurIPS.\n\nI have the following questions for the authors:\n1. As a practitioner, I am interested in concrete algorithmic recommendations. The paper lists several choices of algorithms that adjust $\\lambda$ and several that adjust $\\pi$, but at the end of the day, given a concrete problem of the form (2), how do I decide which of these to use? A discussion would be really nice. \n2. In lines 162,163 you say that supporting CMDPs (and other problems with constraints) requires a minor adjustment to the algorithm, but you don't specifically define what adjustment. Can you clarify how Algorithm 1 changes?\n\nI would also suggest removing the experimental section from the main paper and putting it in the appendix - the strength of your submission lies in the generality of the theoretical contribution. \n\nMinor points:\n1. The figures on page 9 are completely illegible on a printed copy. Please enlarge and move to the appendix.\n2. The checklist should be part of the main paper.  \n3. The notations $f^\\star$ for the optimum value and $f^*$ for the Fenchel conjugate are so similar as to be confusing. I would rename the optimum value.\n4. I don't think Figure 1 is very useful. To put it bluntly, people who can understand the rest of the paper are unlikely to need it. \n5. Line 603 in the appendix: \"[31, equation 9 1]\" should be \"[31, equation 9]\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors claim that there is no need to discuss societal implications since this is a theoretical paper. Because of the breath of applications that the paper covers, the discussion would be so inspecific that I tend to agree.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "nJHjMZct1np", "reviewer": "Reviewer_3z88", "summary": "This paper addresses an extended reinforcement learning setting with general utilities, where the agent's objective can be any convex function of the state-action distribution. Especially, it recasts the problem as a min-max game between a policy player and a cost player, and it describes a principled methodology to solve the game. Finally, it provides ways to instantiate the methodology with known algorithms, and a brief experimental evaluation in simple domains.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "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": "*POST-REBUTTAL*\n\nThe score has been updated for the reasons explained in the comment below.\n\n------\n\n\nThis paper studies a very relevant problem, which practically unifies many RL objectives of interest under a unique setting, and it provides a neat formulation of the framework as a two-player min-max game. However, the major takes of this paper are not particularly surprising w.r.t. prior works, and some choices in the presentation of the practical algorithms are quite confusing. Thus, I am currently evaluating this work as borderline, though a convincing authors' response and slight changes to the main text might better clarify the value of the paper.\nI provide below some detailed comments.\n\nTECNICHAL NOVELTY\n\nThe Convex MDP framework has been previously formulated in (J. Zhang et al., 2020). The meta-algorithm and its analysis are taken from (Abernethy and Wang, 2017). The FTL and best response combination is practically equivalent to the algorithm in (Hazan et al., 2019). Even the min-max game interpretation, which is novel to my knowledge, is somehow suggested by the work in (J. Zhang et al., 2020), where the gradient computation requires to solve a max-min problem between the policy update and the reward. I believe that this work successfully meshes these ingredients in a more coherent presentation (Sect.1 to Sect.3), but I have some doubts on the actual novelty of the contributions.\nCan the authors clearly specify the technical novelty their work is contributing w.r.t. prior works?\n\nPRESENTATION AND CONTRIBUTIONS\n\nI found the paper quite neat and clear from Sect.1 to Sect.3, whereas it becomes somewhat confusing thereafter. Instead of the various alternatives provided by Sect.4, I would have rather focused on a single algorithm to tackle convex RL in an online setting, then providing either a complete theoretical analysis or a more thorough experimental evaluation in the next sections. Especially, some of the questions that could be targeted are:\n- There exists any separation between the learning complexity of the Convex MDP setting w.r.t. the standard MDP setting?\n- Can we deploy a single algorithm that is able to address the variety of objectives reported in Table 1 in a practical way?\n\nGENERAL METHODOLOGY\n\nIt is not completely clear to me why different objectives should require different implementations of the policy player and the cost player, rather than just considering the Fenchel dual of the respective objective function. The authors rightly noted that the algorithm from (J. Zhang et al., 2020) is committing to a specific methodology (policy gradient), but a key feature of their approach is that it can be employed with any convex objective. \nCan the authors clarify why they are not providing an objective-agnostic implementation of Algorithm 1?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is mainly theoretical, and it does not need to address potential societal impacts. The limitations are biefly mentioned in the checklist and through the text.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "mXv83x7sbEL", "reviewer": "Reviewer_wKfh", "summary": "The paper studies the convex RL problem, which is defined as finding policy $\\pi$ minimizing $f(d_\\pi)$ where $f$ is a convex function and $d_\\pi$ is the occupancy measure of policy $\\pi$. Using Fenchel duality, this formulation can be written as a min-max and be solved using the well-known framework of repeated game playing first introduced by Freund and Schapire (1999). The authors show that their framework unifies some well-known approaches in RL by appropriately choosing the no-regret algorithm for the policy and cost player.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "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": "**Originality and Quality**\n\nThe proof techniques and theoretical components of the paper already exist in the prior work. However, the paper's main contribution is providing a unifying framework that captures previous approaches through a single lens of convex RLs.  Although the materials already exist in the prior work, they are scattered, and the authors did a great job of bringing all of them under a single framework.  \n\nI believe the paper's main contribution is the framework itself and its connections that have been well discussed. Therefore, I would suggest moving the experiments to the appendix as they are not adding to the paper's contribution.\n\nThe proofs and claims are sound and well-supported.\n\n**Clarity**\n\nI have much enjoyed reading the paper as it's very well-written and well-organized.\n\n**Significance**\n\nThe paper will be of interest to many researchers in the RL community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and societal impact have been adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "hFWwuKXxbd", "reviewer": "Reviewer_BxxS", "summary": "The authors propose to consider a convex optimization problem over the polytope formed by the state-visitation frequency of an MDP. They constructed algorithms based on existing tools of sub-gradient descents, such as Frank-Wolfe, FTL and OMD, in conjunction with an oracle that (approximate)-solves an MDP with scalar rewards. Altogether, they provide a meta-algorithm that translates a scalar reward MDP oracle to an algorithm for the convex MDP. The authors also highlight several applications, such as the Apprenticeship Learning problem and the constrained MDP problem, of their formulation. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "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": "While the authors propose an interesting problem, I have a major concern over the novelty of the paper as compared to the following SODA 2015 paper by Agrawal and Devanur 2015:\n\nhttps://arxiv.org/abs/1410.7596\n\nThe authors' convex optimization can be phrased in their problem setting (in their Definition 1), by putting $A_t = \\mathcal{K}$ for all $t$. (And also rephrasing convex minimization as concave maximization). Algorithm 5.1 in (Agrawal and Devanur 2015) solves convex optimization in Definition 1. The algorithm only requires an oracle that outputs solution to a linear optimization (the definition of $v^\\dagger_t$ in Algorithm 5.1)  over the feasible region $A_t$. The framework in the (Agrawal and Devanur 2015) is quite similar to what is proposed in the paper in the sense that both allow a wide suit of (sub)-gradient descent algorithms, as highlighted in their Section 3. In this regard, the algorithm design and analysis of Algorithm 1 appear to be fundamentally based on existing works.\n\nA difference between the two papers would be that, while Agrawal and Devanur 2015 assume an exact solver in their generation of $v^\\dagger_t$, while the submission allows an approximate solver. Another is that, the submission proposes the use of non-stationary RL algorithms, and they also highlighted how certain objective (for example, the objective based on mutual information in Section 5.2) can be cast under their framework. Nevertheless, in my opinion Algorithm 1 is the main technical part of the paper, and the two differences highlighted previously are secondary in comparison (this is not to say that they are unimportant, but I saw Algorithm 1 in the paper as the main tool that solves the proposed problem).\n\nIn addition, there is also a minor concern on the presentation of Algorithm 1. The authors display the Algorithm 1, which generates a sequence of occupancy measures $d^k_{\\pi}$ for $k = 1, \\ldots, K$. For any occupancy measure $d$, it is asserted in Line 73 that they recover a policy $\\pi$ that generates $d$ by setting $\\pi(s, a) = \\frac{d(s, a)}{\\sum_{a\\in A}d(s, a)}$. But what if $\\sum_{a\\in A}d(s, a) = 0$ for a state $s$? The authors should address this technicality in Line 73. Nevertheless, I do not think it is a technical issue for their Algorithm 1, in the sense that the authors first outputs a policy $\\pi_k$ that solves the maximizing objective when the scalarization is $-\\lambda^k$, only then they report the occupancy measure of $\\pi_k$ as $d^k_{\\pi}$. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is very clearly written, brings together a large literature and using that unification to provide concrete conclusions about a few open problems about convex MDPs. The reviewers all agreed that the unification provided in this work is both very well done and useful to the community. It was also identified that the paper establishes an important sample complexity result: a rate of O(epsilon^{-2}) for convex MDPs, and that this contribution should be better highlighted. The author response helped allay reviewer concerns. More than one reviewer suggested moving the experiments to the appendix, and you could consider this to spend more time on the theoretical contributions. The reviewers each also gave useful suggestions for the work, and I highly encourage the authors to consider incorporating them. 
Decision: Accept (Spotlight)