Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, authors attempt to improve sample efficiency as well as accuracy of Monte-Carlo policy evaluation by an interplay between on-policy and off-policy data collection. The key idea being on-policy sampling may not guarantee exact policy state-action visitiation distribution in finite interactions. This could be corrected by doing off-policy sampling while tracking the visitation distribution to ensure on-policy state-action density distribution. To elaborate, they collect some data using on-policy sampling, thereafter, they create a new behavior policy with higher likelihood of under-sampled actions. 

Their method of “Robust On-policy Sampling (ROS)”  covers larger MDPs by assuming parametrized and differential behavior policy representation. This policy is adjusted via gradient descent to increase probabilities for low-sampled actions. 

strengths_and_weaknesses: Originality: Authors attempt to improve Monte-Carlo accuracy and sample efficiency in a novel way. They do have classic baselines as well enough coverage of related work.

Quality: Yes, the proposal is technically reasonable. They also provide theoretical analysis and show experimental results in simpler environments to build their case. Authors did show sensitivity of their method to step-size(hyper-parameter)

Clarity: Yes, the paper is well written and requires minor corrections only

- PE notation is not defined in eq. (1) 
- MC notation is also not defined in eq. (2)

Significance: Authors open up an interesting problem space and the suggested ideas could be borrowed by others. However, the experiments done by authors are in simpler environments, where significant improvements are only found in Gridworld environment with discrete space. This dilutes the practical importance of the method.
questions: I would recommend authors to evaluate their method over  Atari or Gym-based mujoco environments. This might show significant improvement in optimal policy convergence in those cases which are generally sample inefficient.

Also, can your work be adopted to deterministic parameterized policies?
limitations: NA
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: The paper proposes using non-i.i.d. off-policy sampling to improve the efficiency of on-policy RL algorithms.
Specifically, it suggests using a behaviour policy that takes into account past actions to choose future actions to cause the observed data to more closely match the on-policy distribution than simply relying on the law of large numbers.
The paper then presents theoretical and empirical support for the proposed approach.
strengths_and_weaknesses: ### Originality
To the best of my knowledge, the proposed algorithm and contributions are new.

### Quality
The paper seems very well-done. I don't have any complaints about quality.

### Clarity
The paper is written very clearly, with intuitive examples provided to communicate important points to the reader. I was pleasantly surprised by how readable the paper is.

### Significance
The proposed strategy tackles an important problem: the poor sample efficiency of on-policy algorithms. It also seems very general, and therefore could be quite significant.
questions: 1. The definition of a policy is that of a Markov policy, but the paper proposes using a behaviour policy that takes into account more information than just the current state/features.
1. Why does ROS only take into account immediate sampling error, and not sampling error in future states via TD-like bootstrapping? Is it unlikely to make a big difference for the extra complication? Could this drag the behaviour policy further away from the on-policy state distribution?
1. The figures are very small, and some of the colours are quite similar. I would suggest making the figures larger, possibly by using a shared Y axis. Also consider changing the colours, bolding the lines, and/or using arrows and labels instead of a legend to reduce the reliance on colour to tell which algorithm is which.
1. In Figure 2, how is the policy evaluated? Monte Carlo?
1. Would ROS work with a changing target policy?

### Minor suggestions:
- line 33: "upmost" should be "utmost"
limitations: Yes, the paper adequately addressed the limitations and societal impact of the proposed algorithm.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors identify a deficiency in on-policy data collection for policy evaluation; when data are sampled i.i.d., new samples do not take into consideration the possible bias of the previous samples. The authors propose adaptive, *off-policy* sampling as a means to actively correct for this bias in a feedback-based manner. Because computing the exact policy for the bias correction is not feasible when using function approximation, the authors propose Robust On-policy Sampling (ROS), which iteratively perturbs a stochastic policy via gradient ascent to iteratively approximate the required sampling policy. The authors prove some convergence results for their method and demonstrate that it can reduce the expected mean squared error (MSE) for policy evaluation in several low-dimensional control tasks.
strengths_and_weaknesses: **Strengths**
- The authors consider an interesting and relevant problem for on-policy evaluation: Given a batch of previously collected (possibly biased) on-policy data, what *off-policy* sampling strategy should be employed to produce better estimates of the *on-policy* expected returns under the target policy $\pi$? As the paper correctly points out, simply sampling more i.i.d. data using the target policy is a suboptimal strategy.
- The proposed algorithm ROS is an intuitive solution to the above problem. Given that some actions may be underrepresented in the past, it makes sense that their probabilities should be slightly increased in the future. Using gradient ascent on a stochastic policy is an elegant way to do this without requiring the explicit calculation of an analytical solution, which is crucial for non-tabular environments.
- The empirical performance of the proposed method appears to be favorable when compared to a variety of baselines, although I am not familiar enough with the related work to determine the relative strengths of the baselines.
- Overall, the paper is very well written.

**Weaknesses**
- Some of the theoretical results are somewhat weak:
  - Proposition 1, which states that pooling two i.i.d. datasets together is biased unless the first dataset is unbiased, seems obvious and unnecessary; of course, if the first dataset's mean is wrong, then it would require an infinite amount of additional sampling to counteract its bias.
  - Assumption 1 (the MDP is a directed acyclic graph) is a very strong assumption that I think would rarely be satisfied in practice.
  - Theorem 1 establishes the consistency of the ROS estimator. However, the i.i.d. on-policy estimator (which the paper claims is inferior) is also a consistent estimator! I find this confusing, because the main thesis of the paper is that a consistent estimator (i.e., i.i.d. on-policy sampling) is, alone, not sufficient for good performance with finite trajectories. Having consistency/convergence as a theorem therefore seems to overstate its importance; perhaps it would be better as a lemma to Theorem 2?
- I was a bit disappointed to see that the main convergence result (Theorem 2) provides a stochastic bound on the KL divergence between the maximum-likelihood policy $\pi_D$ and the true policy $\pi$, rather than the policy-evaluation MSE. As far as I understood, the authors’ claim in the abstract/introduction is that ROS should lead to lower MSE. Although this is shown empirically, which is great, the paper would be much stronger if the theory also supported this claim. In my opinion, it is not as interesting that ROS is able to estimate the policy $\pi$ with high accuracy, but more so that, by doing this, it can achieve more-accurate estimates of $V^\pi$ or $Q^\pi$.
- The tested environments are relatively small, comprising a bandit, gridworld, and two cartpole variations. I think adding at least one high-dimensional environment – even if it were just one Atari game or the like – would make the experiments much more convincing. At present, it is hard to gauge how scalable the results are, even though the ROS algorithm itself looks scalable.

**Minor Edits**
- Line 122: “is ran” $\rightarrow$ “is run.”
- Line 176: “can be ran” $\rightarrow$ “can be run.”
- Line 191: Should it be $\theta \in \mathbb{R}^d$, not $\theta \subseteq \mathbb{R}^d$?

questions: 1. Is there a possible relationship between the theoretical KL divergence bound in Theorem 2 and the expected, empirical MSE? I understand that, intuitively, a lower KL divergence would generally lead to a lower MSE in practice, but as it stands now, Theorem 2 seems to be relatively disconnected from the empirical results of the paper. I would be willing to raise my score if the authors can strengthen the connection between theory and practice here (e.g., possibly by relaxing/removing Assumption 1).
1. More of a suggestion than a question: Do you think an adaptive gradient method (e.g., RMSProp, Adam) might help mitigate some of the hyperparameter sensitivity observed in Section 6.3?

limitations: N/A
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: The authors propose a method of more efficient policy evaluation, that requires fewer samples from the environment relative to Monte Carlo sampling (running directly in environment), as well as an alternative baseline method BPG. The central idea of the paper is that a marginal log-likelihood loss can be treated as a gradient in the direction of executing actions that appear more often in evaluation trajectories seen so far. Therefore, the negative of the gradient can direct the policy in the direction of executing actions that have been seen less often, which causes our empirical action frequency to stay closer to the true distribution compared to sampling actions naively.

This approach is compared both assuming no existing episodes of interaction, and with episodes of interaction - if there is initial data then it is used to compute the gradient for future interactions in the environment / provide an initial set of episodes for averaging episode return.
strengths_and_weaknesses: The insight that the log-likelihood can be treated as a gradient in the direction of selecting rarer actions is interesting. I do have some concerns about the significance of the method. The method inherently relies on having the ability to sample enough on-policy trajectories to apply meaningful corrections to the current empirical distribution of episode trajectories. I would assume this requires a fairly substantial number of episodes as you try to apply the method to higher dimensional settings. It also seems like this approach becomes more data hungry as you increase the size of the existing initial data, because it will take more on-policy samples to apply the relevant corrections.

There is a theoretical justification of the approach, but the argument for it has some fairly strong cavaets - it is both based on a tabular policy, and requires using a learning rate of $\alpha \to \infty$, such that ROS will always pick an action that is undersampled. This does give a sequence of random variables that strays from the true distribution less, but it's a pretty extreme argument and it's hard to see how this proof says anything about the continuous, non-tabular case with much smaller learning rates. It feels a good deal more extreme than other tabular RL proofs. Most of the time you can tell the proof will not work directly in a continuous setting, but you can see a vague throughline of how it could work assuming a nice enough function approximator. I don't see valid throughline if you need to start from assuming an infinite learning rate.

Additionally, I feel there are errors in the proof used. In the proof of Lemma 1 in Appendix B, the paper says

"The ROS update is given by $\theta'_a = \alpha(\frac{\theta}{\alpha} - term)$. Taking the limit as $\alpha \to \infty$ we see that $\frac{\theta}{\alpha}$ is negligible and thus the parameter is $\theta'_a = \alpha(term)$"

I don't see why this step is justified, it relies on $\lim_{\alpha\to\infty} \alpha \cdot \frac{\theta}{\alpha} = 0$, which is definitely not correct, we cannot cancel this term to 0 if it's getting multiplied by a term going to infinity.

In the proof of Theorem 2, the authors could also be clearer on why $Q_m$ can be treated as O(1) (because the n-th derivative of the KL-divergence at a fixed point $\pi_e$ should still be constant with respect to number of data points $m$). In general it would have also been nicer if size of action space $|A|$ was in the bounds in some way, because this does matter to the convergence rate if we wished to apply this method to different MDPs.

(I suspect that although the proofs have holes, the general results are still correct.)

The method does outperform BPG asymptotically - my concern is that by the time the asymptotics show up, you are already collecting enough on-policy episodes to make the difference not very applicable. Almost all results are in discrete domains with learning rates $\alpha = 10$ to $10^4$ and the results in the one continuous problem with reasonable learning rate (CartPoleContinuous) did not look as exciting.
questions: What do the authors see as potential paths for applying the problem to larger dimensional MDPs? It seems the core of this paper is whether we expect this to work in larger MDPs, because it is only in those MDPs where you need function approximation to work. But it is also in larger MDPs where we'd expect it to be difficult to adjust policy behavior by applying a small number of gradients to the policy.
limitations: Yes
review_title: null

Meta-review: metareview: The paper seeks to improve the efficiency of policy evaluation in reinforcement learning settings. Monte-Carlo sampling is commonly used for on-policy evaluation, but the paper eloquently shows that non-iid off-policy sampling can be a better strategy. The reviewers agreed that the technique was novel, interesting and promising to share with the community.

Some reviewers questioned the theoretical analysis that the authors clarified during the feedback phase. To strengthen the paper, the authors should experiment with ROS in richer problem domains (e.g., with function approximators) to identify realistic regimes where ROS helps empirically. For instance, if ROS is made easy enough to use with DeepRL policies in complex domains, it could be a very significant contribution to on-policy evaluations that are currently plagued by high variance from Monte-Carlo sampling.
confidence: Less certain
Decision: Accept