Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a practically feasible algorithm for the average reward setting in RL. The key idea is to propose a lower bound policy improvement objective, for the average reward setting compared to the more popular and general discounted reward setting. This work follows directly from previous impactful works on policy gradients with trust region optimization (TRPO) and shows why previous approaches cannot be directly applied for the average reward criterion. This is a significant contribution in RL research, for the average reward performance criterion, and opens doors for future works in this direction that might be impactful to the community. Overall this is a good paper. There are few major and minor concerns I have about the contribution, mostly from an algorithmic point of view, which are described in details below. 

Overall comments : 
- This work provides monotonic performance improvement guarantees, by deriving a lower bound policy improvement criterion for the average reward setting. It is well known, even though less significantly realized that the existing policy improvement theorem for the discounted reward setting leads to a trivial bound for the average performance criterion. This work builds from that and derives a novel result which can bound the average reward performance objectives based on the divergence between two policies, as mostly done in a lot of policy optimization algorithms (e.g TRPO and many variants building from TRPO). 
- Additionally, the authors propose a constrained optimization variant of their algorithm, building from the CPO algorithm (Achiam et al) and shows that the average reward criterion can also be used for policy optimization under cost constraints. 
- The paper is well written and easy to follow, with the key theoretical contributions clearly defined. It builds from the well known proposition from Achiam et al., for the upper and lower bounds for the performance difference lemma (Proposition 1). Lemmas 1-3 are known results, adapted for the average reward setting, including the performance difference lemma for the average reward objective. 
- The key result is shown in theorem 1, which bounds the performance difference based on the average reward criterion, but reduces to the divergence between policies only. Equations 9 and 10 are extensions from Achiam et al., adapted for this setting, with the typical assumption that the changes in occupancy measures between $\pi'$ and $\pi$ are insignificant. This is a standard assumption, assuming minimal state distribution shift between the two policies, as typically done in TRPO, CPO and variants. 
- Experimentally this work nicely demonstrates the significance of the average reward criterion in continuous control tasks, which are adapted for a continuing setting, instead of the typical episodic setting with reset states. Under this modification, the authors compare to TRPO and CPO with different discount factors in the continuing environment, and shows the significance of optimizing the average reward lower bound objective. The authors do not compare to other well known policy gradient baselines, which I believe is fine in this case; since the key contribution is to propose an algorithm applicable for continuing environments - and modifications on top of their ATRPO algorithm can be made, as required, to compare to other well known existing baselines. Even though the experimental results are less exhaustive, I think this is not too of a problem, compared to the significant algorithmic contribution this paper introduces. 

Few issues and comments for improvement : 
I think the major drawback or clarity this paper requires is to describe their algorithmic steps more clearly. At first glance, there are few issues which seems unavoidable, and it would be better if the authors can clarify on these. These are as follows : 
- Lemma 3 bounds the divergence between stationary distributions in terms of the divergence between policies. This result is adapted, as shown in appendix, following from Achiam et al., and is known from other papers that such divergence between stationary distributions can be bounded. Lemma 3, equation 8 shows that this bound depends on the l-infinity norm between the transitions under the policies. Proof of Lemma 3 is easy to follow. My major concern is how is this term in equation 8 dealt with in the overall algorithm?
- Theorem 1 following from the stated lemmas, depends on this, as highlighted in the $\epsilon$ term and in Algorithm 1 (equation 12). It seems that the assumption that the stationary distributions between \pi' and \pi are close in this case is less justified in the average reward setting compared to the discounted setting. Can the authors comment on this? In the discounted setting, the normalized occupancy measures between two policies can perhaps be assumed to remain close, as done in TRPO. However, does the same hold for stationary distributions? If so, why would that be? I think this is a major assumption. 
- I do see why in the overall algorithm, this assumption is made; since otherwise finding the sensitivity of stationary distributions w.r.t changes in policy parameters might be difficult to compute; but theoretically, it would be better if authors can comment on it. 
- Section 5.1 outlines the key algorithm and steps. Equation 13 shows the overall objective with KL constraints, which at first glance, is almost equivalent to the discounted reward setting. However, as pointed out later, the advantage function takes account of the average reward, and the overall algorithm can be naturally extended from TRPO and CPO. However, I think it would be better if the authors comment on the above issues, and how is the overall algorithm implemented. In appendix C, there are discussions on the critic estimate, if this was to be extended in an actor-critic setup with lambda returns - however, appendix C does not really give anything meaningful as expected. It seems that the overall difference is in equation 33, where the target is now modified with the average reward. This makes the algorithmic contribution clean, but I wonder how is this implemented in practice. The target now requires computation of the average reward, for every s,a pairs? This seems to be a bottleneck, and comes to the major drawback for the average performance criterion anyway? How is this avoidable?
- Overall, I think the algorithmic implementation of this is not clearly explained. It seems there are major steps ommited in the overall description of the algorithm - and this is partly also because the authors propose ATRPO and ACPO algorithms, which are two different contributions itself. I think it would be better if the key algorithmic idea and implementation details are rather included in the main text, so that the significance of the work can be better highlighted; and perhaps the extensions with cost constraints can be moved to the appendix.

Summary : I think overall this is a good paper, with some clarities that are still required from the authors. This is a good contribution, extending existing impactful works from the discounted reward setting to the average reward setting. The authors propose theoretical justifications as well as a practically feasible algorithm. If the authors can clarify some of the major concerns I have, given my understanding is correct, I am willing to further increase the score. However, as it is, I would recommend marginal acceptance, and open to discussions with other reviewers and authors to clearly understand the significance of the work. 
review_title: Interesting paper with practical significance for average reward policy gradient setting

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper advocates for the use of the average reward objective in long horizon, continual reinforcement learning settings, and it examines whether a limiting argument for the discount is sufficient for extending theoretical results from the discounted setting to the average-reward setting. In the case of policy optimization, the paper shows the monotonic improvement bound from Schulman et al. (2015) becomes vacuous as gamma approaches one. The rest of the paper presents theory to support a new, non-vacuous bound, which leads to a new algorithm analogous to TRPO (A-TRPO). The paper additionally shows how their main theorem can be applied to constrained MDPs in Section  5.2. Empirical results are provided in three MuJoCo domains modified to provide non-episodic experience.      

I found many strengths in the paper. For one, it was enjoyable to read and fairly well organized. The authors presented their ideas clearly, and they appeared logically-connected throughout the paper.

The paper is also well motivated. Continual reinforcement is a broad area of open research where new advancements stand to improve the generality of our current AI/ML systems. In that setting, the average reward objective for MDPs seems most natural. But despite the existence of average-reward RL algorithms, many of them are not well theoretically well understood (e.g. R Learning). And as the authors bring up, it is not known if more current theoretical results about policy optimization apply to the average-reward setting. 

There are few minor issues I have with the presentation, and some questions I have regarding the experimental results. Pending a satisfactory response to these issues, which I describe below, this paper could be ready for publication.

Although the results of Section 5.2 seem useful for those interested in constrained decision making processes, they also seem fairly anecdotal in relation to the paper’s main claims and for what the main paper presents. The claims supported with substantial empirical evidence only use A-TRPO.  The A-CPO results have been tucked away in the appendix.  I suggest the authors remove this material, since the A-TRPO results are sufficient to support your main claims, and considering the constrained MDP setting in addition to average reward and discounted is too much for the length of a conference paper

Section 7 presents empirical data showing the performance of the proposed algorithm (A-TRPO) and compares it to TRPO with different discount factors. The presented results seem positive: suggesting that A-TRPO finds useful policies within the considered data regime. However, this section is terse, and so I have a few questions for the authors:

I’m not yet convinced the evaluation is entirely sound. The performance of an average reward agent is compared to discounted agents using their respective returns averaged over the last 1000 steps of their 100 most recent trajectories. I take issue with this approach for several reasons:

1. It is not clear that it has a meaningful connection to the average-reward criterion. Why not use the average reward, which is what the paper advocates for as the natural metric in continual settings?
2. Restricting the evaluation to the last 1000 steps, or trajectories of length 1000, (authors please specify) biases the outcome against discounted agents whose effective horizon is 1000 or greater. These agents are trained to maximize cumulative reward on horizons greater than or equal to 1000, but then they are evaluated on horizons less than that.
3. In a continual setting, there is no separate evaluation phase; learning continues indefinitely. Therefore, it seems more appropriate to report the reward averaged over a horizon where sufficient mixing has occurred, rather than report offline evaluation performance.

It is not immediately clear to me that the modifications to MuJoCo result in a well posed continual learning problem. Can the authors please clarify if the maximum episode length cap was removed for training?  Can they also clarify exactly how the start states were sampled? Are there any aspects that change or remain the same between falling down and restarting? A complete characterization of the factors of variation would be helpful here.

I do not have a good sense for what data is being plotted in Figures 1 and 2. The data seems to vary between the plot markers. So my question is: what do the plot markers represent? Has this data been smoothed at all? If so, then can you please provide more details so we can understand how the data was processed.

The paper does a good job of positioning its contribution with respect to prior work throughout the text. Though it wouldn’t hurt to expand the Related Work section so it reads less like a list of facts. The goal would be to help readers understand the contribution by comparing and contrasting it with what others have done.

It would be helpful to include a video showing the execution of the policy as it is being learned. This would allow reviewers to verify if the learned average-reward polices are actually useful, and they do not simply achieve better evaluation metrics than the presented baselines. 

The questions identified in the beginning of Section 7 could be more specific. For example: “Which performance criterion is more suitable for continuing control tasks?”. This question strikes me as something that has been answered in the affirmative throughout the long history of average-reward and infinite horizon discounted MDPs. This is also mentioned in two references you provide (Sutton & Barto, and Naik et al. 2019). Could you be more specific about what you are trying to address here, how this is different than what others have shown, and about how Question 2 is different from Question 3.

Many of the theoretical results cite a set of class notes (Achiam 2017). I suggest the authors remove this citation and reproduce the results needed for their arguments in the appendix. This provides a way for those to be peer reviewed and for future work to reliably cite them.

review_title: Shows strong signs of a good paper, but a few questions remain about the empirical evaluation.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper identifies an important problem: policy optimization in undiscounted continuing tasks. This is indeed important since the discounting factor may not be appropriate in certain applications such as health care or robotics. I feel the main contribution of this paper is Theorem 1, an average reward version of the monotone improvement theorem. Naively applying the discounted version results in a trivial bound.

My concern is about the algorithm (13) that is almost the same as TRPO, with a bit straightforward extension on the estimation for the advantage function. In the constrained form, the KL radius is viewed as a tuning parameter but in the regulaized version (12), the \xi involves a complicated form involving true P to guarantee the monotone improvement. This does not make very much senses to do this approximation. Note that in TRPO, there is no true P involved. 

A large body of policy optimization works that focus on average-reward is perhaps missing. 1. Online Markov Decision Processes. (2009). 2. Online markov decision processes under bandit feedback (2010). Those two assumes the P is known but the average reward performance difference lemma has been explicitly derived in those two. More recently, "POLITEX: Regret Bounds for Policy Iteration Using Expert Prediction" considered a fully RL setting and average-reward setting with guarantee. 

====================
Thanks the authors' response. Based on the originality of Theorem 1, I increase my score by 1 but still a bit worry about the sufficient algorithmic contribution beyond TRPO. 

review_title: undiscounted version of TRPO

final_score: rating: 6: Marginally above acceptance threshold
review_content: ***Summary***
The paper proposes an extension of the performance improvement bound, introduced for the first time by Kakade & Langford (2002), to the case of average reward performance index instead of discounted return. The paper starts with a theoretical contribution in which all the steps of the original derivation are adapted for the new setting, leading to a new performance improvement bound. Then, this theoretical achievement is employed to derive the corresponding adaptation of TRPO (called Average Reward TRPO) and CPO (called Average Cost CPO). Finally, an experimental evaluation on some Mujoco domains is provided.

***Major***
- (About the fundamental matrix) The main difference between the performance improvement bound for the discounted return and the one presented in this paper is the constant that multiplies the expected total-variation divergence between the policies. While for the discounted case, this constant is a function of the discount factor and of the maximum advantage, in the average reward case it depends on the maximum advantage as well and on the norm of the fundamental matrix of the Markov chain. The authors clarify that this matrix is guaranteed to exist for regular chains. However, the value of its norm, although finite, can be very large. From a practical perspective, this has limited implications as the objective that is actually optimized translates the penalization into a constraint, ignoring this constant. Nevertheless, it would be interesting if the authors could elaborate more on the properties of this matrix, maybe providing some bounds of its norm, if possible, in terms of more manageable quantities.
- (Organization) I have some concerns about Section 5.2. First, the change of perspective from rewards to costs might not favor the clarity of the paper. Second, concerning Average Cost CPO, no experiments are reported in the main paper but in the appendix only. Moving also Section 5.2 to the appendix and reserve more space for the proofs of the theoretical results in the main paper might improve the organization.
- (Experiments) I have some concerns about the interpretation of the experimental results, especially on how ATRPO is compared to TRPO. The two algorithms are designed to optimize different objective functions: the average reward and the discounted return, respectively. The plots that are shown in Figures 1 and 2 report the "Return", which I assume to be the undiscounted sum of the rewards over 1000 and 10000 steps respectively. I am wondering whether drawing conclusions based on this performance index is meaningful. Indeed, optimizing the undiscounted sum of the rewards is closer to optimizing the average reward rather than the discounted return and I am not surprised that ATRPO outperforms TRPO. Can the authors elaborate on this point and explain why they think that the comparison is fair?

***Minor***
- In Section 2, the paper requires that the state and action spaces are finite. Is this assumption really necessary to derive the presented results? In the experimental evaluation section, the algorithms are tested on the Mujoco suite that is made of continuous state-action environments.
- Equations (9), (10), (12) sometimes the state below the expectation is bold.

***Overall***
I think that the paper can be considered incremental compared to TRPO and, more in general, to the papers that study the performance improvement bounds in the discounted setting.  Moreover, I have some concerns about the interpretation of the experimental results. Therefore, my current evaluation is borderline.
review_title: Average Reward Reinforcement Learning with Monotonic Policy Improvement

Meta-review: This paper proposes an extension of the monotonic policy improvement approach to the average reward case.
Although the reviewers acknowledge that this work has merits (well written, clearly organized, well-motivated, technically sound) the reviewers have raised several concerns, which have been only partially addressed by the authors' responses. In particular, Reviewer4 is still concerned about the discrepancy between the theorem and the implemented algorithm, and the proposed simplification used in the implementation boils down to an algorithm that is very similar to TRPO, thus making the contribution quite incremental as also stressed by Reviewer1. Furthermore, I share the concerns raised about the fairness of comparing algorithms that optimize different objective functions.
I suggest the authors take into serious consideration the suggestions provided by the reviewers in order to produce an improved version of their work.
The paper is borderline and I think that it needs another round of fresh reviews before being ready for publication. 
Decision: Reject