Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper develops both on-policy and off-policy deterministic policy gradient theorems under the average reward setting; here, the off-policy theorem only gives an approximated form of the gradient but shows the error between the approximated gradient and the true gradient is bounded. Based on the theorems, the paper proposes an on-policy average reward policy gradient algorithm which defeats the other two average reward policy gradient algorithms in both learning speed and final performance. Meanwhile, the paper derives upper bounds for the smallest expected square norm of the gradients in linear on-policy and off-policy algorithms, respectively.
strength_and_weaknesses: Strength: The paper makes a good progression from theory to practice. It has enough novel contributions and provides convincing experiment results.

Weakness: The paper is not clearly written and has a few mismatched mathematical notations. Furthermore, the theorems of non-asymptotic bounds have unstated assumptions and conditions. The proof is also hard to follow. Also, the bounds do not directly describe the properties of algorithms; the regret bound or the bound on the optimality of the policy would be better.
clarity,_quality,_novelty_and_reproducibility: 1. The structure of the paper

(1) The last paragraph on page 1 is confusing. It suddenly jumps into the details of average reward algorithms. And those details are not linked with their proposed algorithms.

(2) The paper throws the authors almost a page of update rules. It is better to introduce one update rule at a time and give some descriptions. Also, it is not necessary to explain and show every rule.

(3) The paper introduces policy gradient theorems for both on-policy and off-policy cases, but only an on-policy practical algorithm is presented. It needs a short explanation. Also, it needs to be mentioned in the paper that Algorithm 1 is on-policy.

(4) The paper states that it introduces three-timescale algorithms, but Algorithm 1 is two-timescale, and Algorithms 2 and 3 are one-timescale. 

2. Notations

(1) Equation 9 is incorrect; the constant should be 1/(1-\gamma).

(2) Equation 11 is incorrect; the term on the right-hand side approximates the gradient, not equals to.

(3) The approximation symbol in Theorem 2 is not correctly used. This symbol is only used when the error is tiny.

(4) In Equation 20, one notation,\rho, is given a second definition.

(5) Equations 24 and 25 have typos. Differential Q-values should depend on bar{w}, and the subscripts of w are wrong.

(6) What is Q in Assumption 5? Should it be the true value for any policy or the estimated value for all parameters?

(7) In Algorithm 2, the size of the batch is sometimes expressed as N and sometimes as M. Also, on line 12, there is a typo to write Q^{\pi}.

3. Finite-time analysis

(1) The meaning of the current bounds is not explained and is unclear. Maybe use an optimization theorem to gain error upper bounds on the average reward or the regret instead of the gradient. For example, the optimization Theorem 59 in Agarwal et al. (2021).

(2) There is one assumption used but is unstated. The paper uses that the differential Q-values for all policies can be linearly expressed in Lemma 6.

(3) The constant used in the lemmas are only defined among the proof and cannot be tracked. Please describe all constants in the lemmas.

(4) The bounds ignore important dependencies on several variables. The upper bound depends on a newly introduced variable \eta, the dimension of Q-value features, the dimension of policy parameters and not clearly defined constants C_s and C_a.  \lambda_min in Lemm6 seems to depend on the dimension of features. \lambda_min in Lemma 13 depends on the number of policy parameters. They cannot be treated as constants. Also, what are C_a and C_s?

(5) There is a typo in Equation A.10. The \eta w term is missing, but the proof is correct. Also, on page 20. why do you define function g and \bar{g}? They are not used. 

(6) This question does not influence my decision on acceptance or rejection. Could you point me to some literature assuming Q-value features to be dependent on policies? 

Agarwal, A., Kakade, S. M., Lee, J. D., & Mahajan, G. (2021). On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. J. Mach. Learn. Res., 22(98), 1-76.
summary_of_the_review: The paper may not be ready for publication and needs rewriting.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper extends the deterministic policy gradient algorithm to the average reward case and introduces an average reward version of DDPG. Finite-time analysis of linear function approximator version of the algorithm is also shown for both the on-policy and off-policy case. Empirically, the new algorithm is shown to outperform other on-policy average reward algorithms.
strength_and_weaknesses: Average-reward RL has only started gaining attention in the last 2-3 years and this work fills an important gap in that it provides a practical off-policy deep reinforcement learning algorithm that shows potential in high dimensional continuing control tasks. My detailed comments are below:
- The methods introduced in the paper can be seen as an average-reward extension to [1] and [2]. Intuitively, especially for off-policy settings, the deterministic policy gradient approach is probably easier to use and analyze. I also liked Section 3.4 where the authors provided comparisons to alternatives.
- One comment/question I have is regarding the step size. One thing that has always been tricky with average reward algorithm is the choice of learning rate since we need both the Q function and the average reward rho converge, this essentially gives us a multi-time scale problem which are notoriously hard to tune and can have complicated requirements in terms of their step size choice (an example is the proof for differential Q learning found in [3]. I was also quite surprised that in the practical algorithm, the authors used the same step size for the actor, critic, and average reward and the resulting algorithm actually works quite well.
- For the experiments, it seems that in the original papers for the two baselines used in the paper (ATRPO, PPO), both papers used OpenAI gym instead of DM control for their experimentation work. So it is unclear whether the original implementation/settings for the baselines would work just as well on DM control. I wonder if the authors accounted for this in their experiment work.
- Also concerning the choice of baselines, I wonder how your algorithm performs against discounted DDPG/SAC? That is, empirically, is there any evidence that the average reward algorithm outperforms the discounted version? Since it has been pretty well-known that off-policy algorithms generally perform better in terms of sample efficiency compared to on-policy algorithms, the results in the experiments are not surprising. I’m curious how your algorithm performs when compared to other off-policy methods.
- Another question I have concerning the experiments is the update frequency of the actor/critic/average reward value. You mentioned in the experiment section that you update the critic network with more frequency, however in the hyperparameter section the update frequency is listed as 10, is this the frequency for the actor or critic or the average reward? More importantly, could you comment on the different update frequency since this issue did not seem to come up in the theoretical analysis. Also related to my previous point concerning step sizes, some comments on the update frequency of the average reward would be much appreciated.

[1] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin A. Riedmiller. Deterministic Policy Gradient Algorithms. ICML 2014

[2] Thomas Degris, Martha White, and Richard S. Sutton. Linear Off-policy Actor-Critic. ICML 2012

[3] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and Planning in Average-Reward Markov Decision Processes. ICML 2021


clarity,_quality,_novelty_and_reproducibility: Clearly written, method introduced is novel, some additional details needed for experiments.
summary_of_the_review: Overall, I think this paper does make an important contribution to the field but some important issues still need to be addressed, especially in the experiment section. As of now I am setting my score to borderline reject but I am open to changing my score upon a satisfactory response from the authors. I look forward to hearing back from the authors.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces an off-policy deterministic policy gradient for the average reward setting. The authors follow a standard approach, first deriving the policy gradient, then finding a class of compatible value function approximators, and finally providing a finite time analysis for the on-policy and off-policy cases. Alternative approaches for deriving the off-policy policy gradient are proposed, with an explanation of why they could be less appealing to follow. Finally, an experimental comparison with existing on-policy actor-critic algorithms based on the average reward shows that the proposed method performs well. This confirms that off-policy algorithms might be more sample efficient than on-policy algorithms also in the average reward setting.
strength_and_weaknesses: 
Strengths:

- The average reward problem is pretty unexplored, and to my knowledge this is the first work properly formalizing this setting for deterministic policies
- The theoretical results mostly follow in a straightforward way from previous work, and most of them are exactly how one would expect them. Nevertheless, it is important to have a good reference for such results, like it is in this paper.
- All the assumptions are well stated before each main result


Weaknesses:

- (major) The paper would benefit from some rewriting. The theory sometimes lacks a proper explanation. For instance, the results of Theorem 3 and 4 are not even commented on. Why should we care about these results? Are they surprising? For a theoretical paper like this, it is important to convey the result to the reader properly.
- Parts of the paper could be better organized. Sometimes definitions appear a bit after quantities are used for the first time (See Lemma 1 and then Eq. 5). The long list of equations (24)->(32) should be rewritten in a more organized way.

- Target estimators in Eq. 24 appear without any justification

- In the experimental results the authors reimplemented the baselines and used the original hyperparameters reported in the baseline papers. This seems pretty unfair, as it is well-known that slightly different implementations can have very different experimental results. Since the authors tuned their hyperparameters, but not the baselines, how can we consider the experiments fair?

Minor:

- There are too many repetitions of "came up with" throughout the paper
- In Eq 12 should there be $d^{\mu}$ instead of $\rho^{\pi}$?

Other questions:

- Some proofs in the Appendix use a projector operator. Is the operator used in the implementation?
- Could the authors clarify why Eq. 21 is not a good off-policy objective? It was not clear to me from the explanation given in the paper.
- Assumption 2 is stated without comments. Could the authors explain it in the paper? 
- What happens if the training phase is 1000 and the evaluation phase is 1000? How does the proposed method compare to the baseline in this case?
clarity,_quality,_novelty_and_reproducibility: The theory in the paper is clear, novel, and of good quality, but the paper needs major rewriting in order to properly present and explain the results to the reader. The experiments do not perform a hyperparameter search on the baseline, so it is difficult to assess their fairness. The authors include the hyperparameters used.
summary_of_the_review: The paper introduces an average reward off-policy deterministic policy gradient algorithm. While the theory is sound and significant, the authors should improve the quality of the writing in order to explain better the importance of their results. Some concerns about the experiments need to be addressed before acceptance.

-----------------------------------
Edit: Updating my score after author's response
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents deterministic policy gradient theorems (both on- and off-policy) for the average reward setting. The paper then presents an Average Reward actor-critic algorithm based on DDPG (ARO-DDPG). A finite-sample analysis is conducted, and the algorithm is demonstrated empirically on several environments.
strength_and_weaknesses: **Strengths:**
+ The proposed approximate off-policy policy gradient for continuous states and deterministic policies is an intriguing solution to a difficult problem.
+ The paper is written fairly clearly.
+ The proposed algorithm performs well in the experiments.

**Potential Weaknesses/Questions/Things to improve:**
- Spelling mistake in the title of the paper ("DETERMINSITIC").
- "In the case of recurrent Markov Decision Processes (MDPs), average reward happens to be the most selective optimization criterion." What does "most selective" mean in this sentence?
- "Moreover, an obvious discrepancy between the objective function and the evaluation metric, that exists for discounted reward setting, is resolved by opting for the average reward criterion." What discrepancy is the paper referring to?
- It's generally good to comment on the assumptions made just after making them. Are they necessary or just for convenience? If necessary, why? For example, Assumption 3 can always be made true by normalizing the feature vectors, and is therefore just for convenience, whereas Assumption 1 seems necessary for the steady-state visit distribution to be well-defined.
- "$P_t^\pi$ is the state distribution at instant t given by (9)." This should say Equation 10, right?
- Is Equation 9 correct? I've only seen the discounted state visit distribution defined as $\frac{1}{\sum_{t=0}^\infty \gamma^t} \sum_{t=0}^\infty \gamma^t P^\pi_t(s) = (1-\gamma) \sum_{t=0}^\infty \gamma^t P^\pi_t(s)$, because the denominator is a geometric series that converges to $\frac{1}{1-\gamma}$. Where did the $\frac{1}{\gamma}$ term come from?
- It would be good to comment further on the extra error term $\mathcal{O}(N_\theta^2)$ due to off-policy sampling. What situations could cause it to be small or large? Does it increase over time as the learned target policy deviates more and more from the behaviour policy?
- What are the shaded regions in the plots? Confidence intervals?
- The plots do not use colourblind-friendly colours. Consider removing the legend and instead using labels and arrows to show which line corresponds to each algorithm. Doing so would greatly reduce the reliance on colour to determine the performance of each algorithm.
- The paper only reports experiment hyper-parameters, but does not describe how they were chosen. Which values were checked for each of the methods? Do all of the methods use the same hyper-parameter settings (this is not good)? Are the chosen hyper-parameters representative of algorithm performance? Without conducting a grid search for each method, it's difficult to draw conclusions about the relative performance of each algorithm, and the experiments are more like demonstrations than rigorous comparisons.

**Minor comments/suggestions:**
- There seems to be a lot of vertical space near the equations on pages 2 and 3. Is "\allowdisplaybreaks[4]" in the preamble of the LaTeX file?
- It would be clearer to move equations 24-32 inside of Algorithm 1 instead of referring to them, and would save a lot of space.
- It would be good to clarify that the definition of the policy in Section 2 is for deterministic policies.
- It looks like $\rho^\pi(s)$ is used for discounted state visit distribution and $\rho(\pi)$ is used for average reward. Using $\rho$ for both makes the notation more confusing for the reader than it needs to be.
- The policy gradient theorem from Degris et al. (2012) is only valid for the tabular case. When using function approximation, the true off-policy policy gradient is given by Imani et al. (2018). However, the emphatic weightings rely on importance sampling, which as stated in Section 3.4 will not work with deterministic policies in continuous state spaces. The proposed approximate off-policy policy gradient expression is an interesting alternative.

**References:**
- Imani, E., Graves, E., & White, M. (2018). An off-policy policy gradient theorem using emphatic weightings. Advances in Neural Information Processing Systems, 31.
clarity,_quality,_novelty_and_reproducibility: **Clarity:**
The paper is fairly clearly written and not difficult to understand.

**Quality:**
I have a few concerns about quality, mostly regarding the experiments.

**Novelty:**
To the best of my knowledge the proposed method is novel, but I am not extremely familiar with the average-reward literature.

**Reproducibility:**
Enough details are given to reproduce the experiments.
summary_of_the_review: Despite liking the proposed algorithm, I must recommend rejection due to the concerns listed above, the experiments in particular. If the authors can address my concerns satisfactorily, I would be willing to recommend acceptance.

**Update:** The authors have addressed some—but not all—of my concerns, and I am increasing my score and recommendation in response.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper extends the canonical deterministic policy gradient from the discounted setting to the average reward setting. Finite sample analysis is provided.
strength_and_weaknesses: Strength:
The idea is straightforward and seems doable

Weaknesses:
The presentation is very confusing so I cannot evaluate the correctness of the proofs at all. 
For example, in Algorithm 2, the critic is a state value function. However, in the update of the actor, it uses the **ground truth** action value function. How can we get the ground truth action value function? Moreover, in line 8 in Algorithm 2, there is projection in updating the critic. In the analysis of the critic, the first equation in page 19, the projection, however, disappears. 

Overall, this work combines several existing ideas and I generally believe such a combination should work. But there are many details that need to be taken care of, which the authors fail. 
clarity,_quality,_novelty_and_reproducibility: See above
summary_of_the_review: See above
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work addresses the important problem of developing an off-policy actor-critic method for the average reward setting. The work addresses the problem by developing on-policy and off-policy deterministic policy gradient theorems under the average reward setting and corresponding algorithms.

However, several reviewers pointed out that the exposition of the theoretical results requires significant improvement as many issues arose during the back-and-forth between the reviewers and the authors. The responses indicate that a thorough draft update, including the theoretical results and a fresh review of the theoretical results, is warranted. Specifically, the non-iid nature of data when sampling from a replay buffer, as well as the dropping of the projection, which was necessary for bounding the critic, should be addressed either to correct the result or to remove misunderstandings. We strongly encourage the authors to resubmit to the next venue after addressing these issues.

justification_for_why_not_higher_score: There are significant concerns about the theoretical results.
Decision: Reject