Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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. 
questions: However, there are a few concerns as follows:
1.	In 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. 
2.	The 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. 
3.	Why 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? 
4.	Although the issues in convex MDP are well-investigated in this paper, the contribution in terms of the learning algorithm and associated analysis is limited.

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: ### Originality
To the best of my knowledge, the contributions in this paper are novel, but I am not an expert in convex RL.

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

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

### Significance
The 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.
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.
1. 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?
1. 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.
1. 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.
1. Is the optimal policy in Figure 4 (c, f) also non-Markovian?
1. 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.

### Suggestions
- 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$.
- It would be good to clarify the x-axes in Figure 4.
- 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
The 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.

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

Then, 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.

Finally, 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.
strengths_and_weaknesses: ## Strengths

* 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.
* The analysis is clear, and the reason for the discrepancy pointed out is acceptable.
* The idea behind the illustrative examples is sound, and they are set up to validate the main idea of the paper.
* 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.

## Weaknesses

* 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?
* 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".
* 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].

### References:
[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.

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



questions: ## Suggestions:
* 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.
* 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.

## Questions:
* 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?

### References:
[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
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: # Strengths
1. 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.  
2. I think focusing on different assumptions that don't hold, or produce vacuous bounds is a great way to move the field forward.

# Weaknesses
1. Almost all the challenged assumption statements are imprecise and difficult to interpret.
2. All experiments  are on examples that are so small as to be unrealistic for problem classes which are considered in practice. 
3. The statement of assumptions is extremely sparse, making verification of the novelty of this work difficult.
4. The statement of the results and how to interpret them was also quite confusing. 
5. Work ignores some of the first apprenticeship learning algorithms that actively analyze how working with inexact state-occupancy affects algorithm performance and regret.  
questions: ## Some comments:
Abstract:
1. "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. 
2. "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.  

Introduction:
1. "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. 
2. "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. 
3. "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). 
4. "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. 
5. "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.
6. "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. 
7. "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'? 
8. "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.
9. "(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.
10. "  (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.

Background
1. Making the reward a function only of state is non-standard. 
2. 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.
3. Please explicitly state your assumptions about the class of MDPs you consider, namely tabular. 

Reinforcement learning with Finite trails
1. Again much of your computational tractability comes from the assumption on the reward which is not true for general RL.

Convex Reinforcement Learning in Finite Trials
1. 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. 
2. There is formatting issue with 4.1
3. 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. 
3. "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. 

In-Depth Analysis of Single Trial Convex Reinforcement Learning Setting
1. "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. 
2. Its extremely difficult to untangle what exactly is being stated by 5.2.
3. "The set of stationary randomized policies is sufficient for convex RL." --Sufficient for what. 
4. Formatting issues with Theorem 5.1 
5. 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)).

Illustrative Examples and Experimental Approximation Error
1. 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.

# Citations Mentioned
(1) https://dl.acm.org/doi/abs/10.1145/1015330.1015430

(2) https://proceedings.neurips.cc/paper/2007/file/ca3ec598002d2e7662e2ef4bdd58278b-Paper.pdf

(3) https://arxiv.org/pdf/2102.06924.pdf
limitations: 1. Poor experimental evaluation.
2. Incremental theoretical contribution. 
3. Poor writing quality and paper organization.
4. Code not included in supplemental material.
review_title: null

Meta-review: metareview: This paper provides new insights for convex reinforcement learning using finite vs. infinite trial objectives. Many of the reviewers felt this was a significant theoretical contribution that was presented clearly with the potential for significant theoretical impact. However, there were also concerns about the practicality of these insights: whether existing "real-world" applications of RL and IL were susceptible to the identified theoretical weaknesses of infinite trial objectives, and whether the experiments in this paper were sufficiently complex to demonstrate the advantages of the insights. The latter of these concerns was more widely shared among the reviewers. While I hope the authors might better address the practicality of their paper when revising their paper, I believe the theoretical contributions of the paper are sufficient for publication in NeurIPS and recommend acceptance.
confidence: Certain
Decision: Accept