Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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:

https://arxiv.org/abs/1410.7596

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

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

In 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}$. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: **Originality and Quality**

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

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

The proofs and claims are sound and well-supported.

**Clarity**

I have much enjoyed reading the paper as it's very well-written and well-organized.

**Significance**

The paper will be of interest to many researchers in the RL community.
limitations_and_societal_impact: The limitations and societal impact have been adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

I have the following questions for the authors:
1. 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. 
2. 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?

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

Minor points:
1. The figures on page 9 are completely illegible on a printed copy. Please enlarge and move to the appendix.
2. The checklist should be part of the main paper.  
3. 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.
4. 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. 
5. Line 603 in the appendix: "[31, equation 9 1]" should be "[31, equation 9]".
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: *POST-REBUTTAL*

The score has been updated for the reasons explained in the comment below.

------


This 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.
I provide below some detailed comments.

TECNICHAL NOVELTY

The 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.
Can the authors clearly specify the technical novelty their work is contributing w.r.t. prior works?

PRESENTATION AND CONTRIBUTIONS

I 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:
- There exists any separation between the learning complexity of the Convex MDP setting w.r.t. the standard MDP setting?
- Can we deploy a single algorithm that is able to address the variety of objectives reported in Table 1 in a practical way?

GENERAL METHODOLOGY

It 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. 
Can the authors clarify why they are not providing an objective-agnostic implementation of Algorithm 1?
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_title: null

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)