Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the effects of off-policy updates for policy gradient methods in RL. The authors show that under certain conditions on the state update distribution and learning rate, exact PG methods will converge to the optimal solution. Based on this result, the authors propose an RL algorithm where the policy is trained on states from two distributions: 1) the on-policy data distribution and 2) the distribution of an "exploratory" policy. This method is demonstrated on two exceedingly simple tasks.

main_review: Edit: I have updated my score following the author rebuttal. Please see my remaining concerns in my comment to the author rebuttal.


It is difficult to ascertain the significance of the results / ideas in the paper.

The claimed primary contribution seems to be the convergence of Eq 3 under some step-size schedule; however, this is not particularly novel and seems to follow quickly from the policy improvement theorem and standard results in stochastic approximation (unless I am misunderstanding the result).

All of the results are exclusively in the fully-parameterized regime with exact access to Q functions; while in this regime, off-policy updates do converge to the optimal policy, this breaks as soon as either condition is broken, for example when dealing with arbitrary function classes F or imperfect estimates of Q (e.g. approximate policy iteration). Given that both of these things hold when applying RL on any non-toy problem, I am not convinced about the relevance of the ideas / results derived in the paper.

It would be very interesting to see analysis as to how quickly (or slowly) these results break under these more realistic assumptions. I think something of this form would strengthen the paper significantly.

It would be useful to explicitly highlight why using the on-policy distribution is bad based on the formal results in your paper. While it is clear intuitively that the on-policy distribution will visit some states sparingly, it is not clear from the text to what degree this slows down convergence.

This paper proposes J&H as a mechanism to ensure that the policy is updated on a wide state distribution instead of the narrow on-policy distribution -- why should this mechanism be preferred over the standard mechanism of using a replay buffer to achieve the same effect? The replay buffer is a very common mechanism, and used with almost all recent practical actor-critic methods (e.g SAC, DQN)

The current experiments in the chain / random MDP / 4 room domains are in very toy settings (all either completely tabular, or in general, no need for generalization). Echoing my previous comment earlier, while these results do affirm the theoretical results, they provide very little intuition for how this kind of method will do on more standard domains that policy gradient and actor critic methods are applied to (as an example, Gym or Atari). For example, I imagine in many domains of interest with large state spaces, a dithering based strategy will perform better than this decoupled exploration / exploitation behavior, because the number of interesting states is simply dwarfed by the number of less useful states.

Minor notes:
- Is a formal definition of $\delta(s)$ provided in the main text?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper addresses exploration with policy optimization methods by explicitly separating the exploration and exploitation parts of the policy. First, some theory is developed to support this idea by generalizing the policy gradient to allow arbitrary state distributions. Then, experiments in small MDPs and in deep RL demonstrates its advantages empirically.


main_review: 
I find that the idea of explicitly separating exploration and exploitation makes sense for policy-based RL methods. I think the theoretical contributions are particularly interesting and I would have liked to see them developed further, especially with regards to doing updates with arbitrary $d(s)$ using samples. 
Generally, the experiments were well-done and thorough although I have certain concerns about the deep RL section. 
The writing was satisfactory overall (didn't spot any typos!) although there were a few parts I would have like to have clarified. The proofs were well-written and clear as far as I could tell. 

Detailed comments:
- There is a line of work on off-policy actor-critic algorithms that I haven't seen mentioned [1,2,3], which feature different state-distribution weightings and analyze these algorithms theoretically and empirically. 
While all state-distribution weightings are subsumed in a general $d(s)$ in this paper, I would have liked some discussion on what weighting should be used then. 
Currently, C4 and C4-s are fairly loose constraints on $d_t$ and $\eta_t$. I think it would be interesting to look into this further and see what forms of d_t are theoretically advantageous, beyond simply covering all the states. In the experiments, a mix of the the on-policy state distribution and an exploratory policy's state distribution is used. Perhaps there could be some theory to support this choice? 

One issue to consider would be the compatibility of a specific $d(s)$ with sampling. In particular, these previous algorithms [1,2,3] can usually be run in an online fashion (updating at every step or at every episode). In this paper, it hasn't been discussed much although there is the mention of experience-replay to help. Even with experience replay, there are many sampling strategies that could be used and it would be interesting if the theory could guide it.

[1] Off-Policy Actor-Critic, Degris et al. (2012),
[2] An Off-policy Policy Gradient Theorem Using Emphatic Weightings, Imani et al. (2018),
[3] Generalized Off-Policy Actoc-Critic, Zhang et al. (2019)

- I find theorem 2 to be a nice result since it gives necessary and sufficient conditions for arbitrary state distributions $d_t(s)$. I have various questions about the lines that follow and the interpretations of this result though.
- Line 107-110: Could you clarify how this is related to generalized policy iteration? I'm not sure how this theorem is helping towards a generalized policy iteration theorem or what this GPI theorem would say.
- Line 118-119: "the convergence propoerties of policy gradient and undiscounted updates require the same set of assumptions and conditions". Could you clarify this statement?
- Line 123: "prove that off-policy updates... are necessary to guarantee convergence to optimality". Why is this true? I don't see how this follows from the theorem. There are also convergence results for on-policy PG algorithms e.g. "On the Global Convergence Rate of Softmax Policy Gradient" Mei et al.
- Line 125-128: Although the initial state distribution doesn't have to cover the space, it isn't clear that this approach solves the exploration issue theoretically. If my interpretation is correct, the open problem outlined in the citation ("Optimality and Approximation..."Agarwal et al.) is not to relax A2 with any algorithm but with the standard policy gradient. That is, can we get the convergence rates for vanilla PG in the survey by Agarwal et al. without having A2? So, I don't think the claim of solving this open problem would be justified.

- Concerning condition C4 and theorem 3 (the convergence rate), why is that we can't just choose eta_t to be extremely large (even increasing over time)? Then we would satisfy C4 or C4-s easily for any d_t that is nonzero everywhere. Also, we would seemingly get the best convergence rate.

- In the deep RL experiments, J&H uses value-based methods for each part. This confuses me since the original motivation seemed to be to improve the behaviour of policy gradient algorithms. Hence, I would have expected, at least, Dr Jekyll (the exploitation agent) to be a policy-based algorithm. As presented currently, I don't really see any connection between the theory and the practical method proposed. For example, the point about the policy gradient being weighted by the stationary distribution doesn't apply to value-based methods anymore. Similarly, the point about policy-based methods having a slow-moving policy (lines 211-218) aren't relevant. 
To me, this disconnect between the theory and implementation casts doubt on whether these experiments actually support the rest of the paper.

I appreciate that the other experiments were done with an actor-critic method though and those seem to be properly done. The thorough study of various parameters was a good addition.

- About the finite MDP experiments, I didn't see the performance of just Q-learning with exploration bonuses. How does that perform compared to J&H? In a similar vein, what would the performance of just Mr Hyde look like for these experiments? While Mr Hyde only seeks to explore perhaps that would be enough to do well in these domains?

- In the finite MDP experiments, how important is it to decay epsilon for the performance? All the runs for J&H decay epsilon over time, indicating that Jekyll gets chosen more often over time. 

- Have you tried a version where Hyde (the exploratory agent) gets to choose all the actions and Jekyll only learns off-policy from the data? In principle, it seems like with the right replay mechanism, this could do well too. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors propose an extension to policy gradient theory which considers policy updates under any state distribution density. Moreover, they present the necessary conditions for convergence to optimality under their new formulation. Subsequently, they implement the ideas supported by their theory and construct a new agent which they call J&H (Dr Jekyll and Dr Hyde). The main idea of this agent is to consider two policies one which is fully exploitative (Jekyll) and one which is completely exploratory (Hyde). This way during training they can combine on-policy and off-policy updates. Finally, they test their agent in a series of simple MDPs and show that their proposed agent is superior at  recovering from converging to a suboptimal policy. 
main_review: The main contribution of the paper is a new theoretical framework for designing  new actor critic methods which are more robust to the common problem of converging to suboptimal policies. By defining an update rule which can be applied under any state density, it is possible to combine data from exploratory policies which cover the state space and thus avoid early convergence to suboptimal policies. The authors show an example of such an approach with their J&K algorithm. 

In their analysis the authors consider only the direct and softmax parameterization of the policy to prove their theoretical claims. This is a limitation which the authors acknowledge and is left as a future work, while they also provide empirical results to support the claim over the
generality of their method. 

Minor Comments
line 35: designates ? 
line 40: Define n_t before using it
line 75: Degine adv before using it
line 676: Lemmas are denoted as Theorems a, b. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper extends the policy gradient theorem from purely on-policy gradients to arbitrary state distributions. The authors provide proofs of convergence and (improved) rate of convergence under milder assumptions than the original policy gradient theorem. They propose a simple agent that separately performs on-policy and off-policy updates, and include a carefully-designed toy experiment that elegantly shows their algorithm achieve globally-optimal results when traditional policy gradient approaches fail. They also demonstrate their approach on a simple deep-RL benchmark.

main_review: ## Novelty

The work is novel. It brings together a collection of previous work and resolves some open questions in the theory of policy gradient methods. It provides theoretical grounding for the long-established engineering technique of using off-policy updates to improve RL performance, an algorithm design with convergence guarantees, and more.

The authors clearly identify related work and place it in context in their paper.

## Quality

This is a comprehensive look at the theoretical underpinnings of off-policy policy gradient methods. Claims are systematically introduced, proved, and eventually experimentally verified. (In the appendix) the proofs are clearly laid out, with proof sketches explaining complicated proofs as necessary.

The paper also includes the chain-MDP experiment that elegantly demonstrates how their method learns the globally optimal policy when traditional policy gradient approaches fail. This experiment shows the theoretical advantages manifest in practice. They also demonstrate their method in a simple Deep-RL setting.

The authors clearly identify and discuss limitations of their work. The greatest limitation of the work is that convergence proofs don’t necessarily cover the deep RL case, but that is unsurprising.

## Clarity

The paper is written very clearly, and is a pleasure to read. At each stage of the derivation, the importance, implications, and potential pitfalls are identified. The derivation of their final result proceeds logically and methodically from related work.

(As a small suggestion, consider adding a brief explanation/proof sketch of Theorem 2 in the main text, because it is a key theorem and its truth is not obvious. It is explained well in the appendix.)

## Significance

The results are important, both because they provide theoretical grounding for common RL engineering strategies, and because it is likely to lead to a long line of further work in applying their results to more complex domains.

limitations_and_societal_impact: The paper deals with basic research and doesn't directly have societal impact.
review_title: null

Meta-review: The reviewers discussed this paper and came to a consensus that it is a useful contribution and should be accepted. 

There were concerns about the fact that this work is primarily in the tabular setting and novelty relative to existing work. The restriction to the tabular setting is quite limited, in that convergence behavior is known to be quite different for (biased) policy gradient methods in the tabular setting (namely that convergence is still guaranteed, as opposed to under function approximation where there are known counterexamples). An issue raised by a reviewer is in the omission of previous work for off-policy policy gradients, that highlight some of these issues, and that consider a different behavior distribution in the objective (somewhat similarly to what is done here, though it is less general since it is restricted to the distribution under a fixed behavior). This connection should be discussed, and the issue of potential divergence more clearly highlighted. The authors do acknowledge this in the paper, refering to the work on biased actor-critic, but it is somewhat buried. This paper would be improved with a much more explicit discussion about this, and if or how the authors think these results might extend to function approximation.

As mentioned, despite some of these issues, the insights provided, particularly about convergence rates and relationships to the state weightings, are useful. 
Decision: Accept (Poster)