Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a policy improvement algorithm inspired by the minimum-variance policy of importance sampling (IS) technique in Monte Carlo simulation community. Properties of the new policy improvement algorithm such as convergence and implicit trust region are well studied in the paper. And in practical, the paper leverages a surrogate objective with the non-central alpha-moment as the finite sample objective for the algorithm. The new algorithm is used in the policy optimization in reinforcement learning. Empirical experiments on several continuous control demonstrate the benefit of the new proposed algorithm compared with existing trust region baselines, especially on the robustness to the small batch sizes.
main_review: ## Strong points:
Significance and Novelty: The paper is motivated by the technical tools of importance sampling (IS). The starting point of the paper is the difference of using IS in different communities, in RL community, IS is served as a **passive** tool but in Monte Carlo simulation community the behavior policy of IS can be **actively** picked and learned to reduce the variance. The minimum-variance behavior distribution can also be served as an improved policy compared with the original one. The paper later discuss how this minimum-variance policy can connect with the trust region improvement by discussing several theorems with the Renyi's Divergence.
I enjoy reading those connections and I think the discussion of the minimum-variance policy reveals a new way to thinking trust region/safe RL algorithm, which can draw a potential interest of the RL community.

Technical Clarity: The paper is well-organized the easy to follow. The mathematical formula is clear and strict.

Soundness: all the proof is sound to me.

## Weak points:
Empirical Clarity: I feel like the final algorithm is not that clear from the first pass of my reading especially the inner loops of the algorithm (see detailed questions below).

Empirical Evaluation: The design of the experiment is fine and clear to me, but I would expect for more ablation study coming up along the the detailed discussion in the previous Section, such as the choices of $\alpha$ and more choices of h (such as Ackley function you mentioned in Figure 1).  I would feel like the empirical results does not fully support the theoretical discussion.

The Original Motivation: Most of the paper (section 4-5) discussed the policy improvement property of the minimum-variance policy. But I think the **variance** itself is as importance as a topic you might also want to highlight, as you mentioned the robustness to small batch size in the experiment. I would expect a paragraph to make this point more clear (for now from Eq. (6) I could have a vague sense why the algorithm is robust to small batch size)

## Questions:
Here are a few questions I would like the authors to answer to clarify my understanding.

1. Does Eq. (6) your final objective? Or do you include the finite sample upper bound in Theorem 6.1 as well? If you use Eq, (6), how do you guarantee a minimization of Line 5 in your algorithm? It seems to me in Appendix D you mention a closed form for Gaussian, is that the closed form for minimization of Eq. (6) (or Theorem 6.1)? Or do you just use several steps of stochastic gradient descent?

2. It seems to me that in the experimental session you fix $\alpha = 2$. Have you tried different $\alpha$? How will $\alpha$ affect the robustness of batch sizes.

3. The model assumption you use for TRPO, POIS and you algorithm is a linear Gaussian policy. What happened if you use a more complex policy class such as neural network? Will your algorithm still outperform TRPO in this case?

4. Most of the analysis in your algorithm is not specific to RL. But in RL, there is a famous "curse of horizon" phenomenon in long horizon setting [1] when your importance ratio is using the product of policy ratio for each time step. Is that a problem in your experiment? How long is the horizon you use in your experiments? 

## Minors:
In the paragraph under Theorem 4.2, "all three properties" should be "both properties" (I did not see 3 properties in Theorem 4.2).

References:
1. Liu, Q., Li, L., Tang, Z., & Zhou, D. (2018). Breaking the curse of horizon: Infinite-horizon off-policy estimation. arXiv preprint arXiv:1810.12429.
summary_of_the_review: Although there are several points need to be addressed by the authors, I feel the theoretical contribution is strong enough to recommend at least a borderline acceptance at this point. I am open to raise my score if my questions can be addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a novel policy optimization algorithm called POPE that is based off of ideas about how to use importance sampling for variance reduction from the Monte Carlo estimation community. The paper proves that the policy that minimizes the variance of the evaluation step actually provides a policy improvement, and then creates an algorithm that repeatedly estimates the minimal variance policy as a policy improvement step. It concludes with some small-scale experiments with linear policy classes on low-dimensional control tasks and claims modest improvements over TRPO and POIS baselines. 
main_review: ## Strengths:

1. The paper raises an interesting connection between the two types of importance sampling. Usually in RL we are thinking of using importance sampling to re-weight off-policy updates, but here the authors take inspiration from the Monte Carlo estimation community and instead try to find the policy that will yield the lowest variance importance-weighted estimator. While this connection seems to have been briefly made by Hanna et al. for policy evaluation (as cited in the paper), the idea to use this in policy optimization seems novel and interesting.
2. The connection yields a novel algorithm that will potentially have different strengths than previous policy optimization methods. This has the potential to expand the array of available policy optimization algorithms. 



## Weaknesses:

1. Clarity. The entire paper is presented at such a level of generality that it is often unclear how the method and theory pertain to the RL problem and how the algorithm compares with other methods. One particularly stark example of this problem is the function $ f$. Throughout the paper everything is presented as trying to optimize $ f$, but it is never made clear how $ f$ relates to the RL problem in particular (which seems to be the ultimate goal of the paper). This makes it especially difficult to compare POPE to related algorithms. There is not a clear explanation in the paper about how POPE is similar and different to TRPO for example in a formal way. This sort of context would make the paper much easier to understand.
2. A fundamental problem is hidden by the lack of clarity. The issue of defining $ f $ is finally addressed in Appendix C where it is explained that $ f $ can only easily be defined for RL problems in deterministic MDPs and even then relies on having a "sufficiently powerful" policy space, where the exact definition of this sufficiency is left vague. The fact that the algorithm cannot function in stochastic environments without estimate $ \mathbb{E}[\mathcal{R}(\tau)|\underline{a}]$ (according to appendix C) seems like a serious problem.  This seems to be a fundamental limitation of the proposed algorithm and the misdirection and obfuscation of the problem in the paper is a serious issue. Moreover, it is very unclear how the algorithm is actually implemented in experiments given this limitation. 
3. The paper provides no clear reason to prefer the proposed algorithm over alternatives. There doesn't seem to be any theory as to what particular cases the proposed algorithm would improve over something like TRPO. There is some evidence in the experiment section of a slight improvement on some small-scale problems, but I will address this more fully below. In general, the paper lacks a coherent comparison to related policy optimization methods.
4. The algorithm is proposed as a multi-level optimization where evaluation is carried out inside of an inner loop. However, in practice the number of iterations of the inner loop is set to $ J=1$. This calls into question why the algorithm needed the complicated multi-level structure to begin with. Is the inner loop of the algorithm necessary? Why might it be beneficial? When $ J=1$, the algorithm seems to be much simpler. Is it more similar to related policy optimization algorithms in this case?
5. I see a few problems with the experiments in the paper:
   1. Hyperparameter tuning. Were all algorithms tuned in the same way? Appendix E does not give enough information to tell. It seems that 4 values of one hyper parameter were tuned for TRPO, but that perhaps several times more hyperparameters were tuned for POPE (between delta, std/variance init, and step size, not to mention $ \beta$ and $J$ which also seem to be tuned from Figures 3 and 4). 
   2. Scale of experiments is small. A major motivation for TRPO and PPO is that they work well wit neural net policies on large-scale problems. It is difficult to conclude that POPE is a better or more useful algorithm without a comparison in those larger settings with neural network policies and larger MDPs. 
   3. The batch-size experiments don't seem to have very clear motivation. The paper emphasizes some experiments using very small batch sizes, but it is not clear why the different between batch sizes of ~10 and ~50 matters very much. They are all small enough to easily fit into memory and be computed quickly, especially with linear policies. It's unclear why this is a benefit of the proposed approach.



**Typos**:

- Page 4 after Thm 4.2: "all three properties", but there are only two properties listed in the theorem 
- Page 5, example 4.1, last sentence: "elad" should be "lead"
- Page 5, section 5, second paragraph "More in general, when consider" is not grammatical
summary_of_the_review: While the paper provides an interesting connection that yields a (to my knowledge) novel algorithm, I don't think it is ready for publication at this time. There are major issues with clarity that make it unclear how the algorithm is implemented at all and I am wary of a few parts of the experimental setup too. But, the core idea is interesting enough that I would encourage the authors to resolve these issues and re-submit the paper to another conference.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: Importance sampling (IS) is at the core of many off-policy reinforcement learning (RL) algorithms. 
The common use of IS in RL is to consider a _fixed_ policy behavior, say $q$ and an optimization policy $p$. The samples are acquired with the behavior policy $q$. The objective is to maximize

$$
\max_p \mathbb{E}_{x\sim q}\left[\frac{p(x)}{q(x)}f(x)\right].
$$

This approach suffers from high variance. 

This paper highlight that originally, IS was thought to _reduce_ the variance of Monte-Carlo estimates. The main idea of this paper is to use IS as a variance minimization technique. It is interesting to see that the $\min_q Var[p(x)/q(x)f(x)]$ leads to a _policy improvement_.

The paper is structured as follow:

1. The authors show in Equation 1 the _minimum variance_ $q^*$. This analytical result is (as far as I understand) purely theoretical and cannot be used directly in RL. Note that Equation 2 also shows how the minimum variance behavior is a policy improvement.
The authors, therefore, suggest that one could simply iterate the minimum variance to consistently improve the policy. At this point, a few questions remain open: will this process converge to a local or global optimum? Can one quantify the divergence between consecutive distributions?

2. To study the convergence properties, the authors introduce an operator $\mathcal{I}$ which takes in input a distribution $p$ and produces the next _minimum variance_ distribution $q$, which will be the next behavior policy. The operator $\mathcal{I}$ has several fixed points: if $p$ is deterministic then $p = \mathcal{I}p$. Theorem 4.2 ensures that the iterated application of $\mathcal{I}$ converges to the optimum in the domain of $p$.

3. Often, trust-region methods are used in RL to ensure stability in the learning process. Theorem 4.3 shows that the application of $\mathcal{I}$ produces a policy with bounded Renyi divergence with the previous policy. Interesting, this result is valid for any order of the divergence. This result is stronger than many other results in RL, where the divergence is only bounded for a unique order (typically 2: KL divergence), leaving the divergence on other orders unbounded. 

4. However, the finding $q^*$ is often not possible. In short, if we consider a generic set of distribution, the application of $\mathcal{I}$ to an element of the set, might produce a distribution not contained in the set. The authors need at this point to devise an _approximation_ of $\mathcal{I}$, and check again for the convergence properties. 
The first approximation consists in minimizing a $\alpha$-Renyi divergence. The difference between classic divergence minimization (or constraint) approaches is that in this paper, the authors are constraining divergence between "return distribution" (even though modified by the monotonic function $h$) rather than the divergence between parameter distribution or state distribution like in REPS or TRPO (@authors: correct me if I am wrong on this point).

5. The authors analyze the policy improvement of this "approximated" operator. They notice that the policy improvement happens only for some particular choice of $h$  

6. The authors prove in Theorem 5.4 that the approximated operator has a tighter trust region (for every single choice of $\alpha$) w.r.t. the unconstrained operator $\mathcal{i}$.

7. The authors provide a practical algorithm in Section 6, and evaluate its efficacy in four classic control benchmarks. They also provide an analysis of the hyperparameters used (monotonic function $h$ and batch-size).


To summarize, the paper proposes a different use of IS, which allows both for variance reduction and policy improvement. 
The improvement scheme is new (although it can be related to other approaches) and sheds new light on policy gradient optimization. 


 

main_review: Strengths:

The paper considers an important problem: the minimization of variance in off-policy policy gradient methods.
Usual (unbiased) estimators rely on importance sampling. In the community, such estimators, are considered to suffer from high variance. 
The high variance comes from the "mismatch" between the behavior policy and the optimization policy.
Cleverly, the authors turn the utilization of importance sampling as a variance minimization approach, by finding the optimal behavior policy w.r.t. this objective.

The method is sound and sheds light on different aspects of of-policy gradient estimation. In particular, this minimum-variance approach is shown to theoretically improve the policy and to provide implicitly a trust region (which is usually needed in off-policy policy optimization).

The authors provide a theoretical analysis of their approach, considering approximation due to the impossibility of the realization of the trajectory distribution. 

The authors provide also an empirical analysis of their algorithm, comparing it with TRPO and POIS, analyzing its robustness w.r.t. small batch-sizes (which, usually, can affect negatively the variance), and analyzing the effect of the function $h$.

To conclude, the problem considered is important, the proposed method is sound, the theoretical and empirical analysis are satisfying. 
In addition, I think that the authors made a good job in drawing connections with related work.

WEAKNESSES

As also considered in POIS, the usual policy gradient can happen at two different levels: parameter and action. In fact, the authors of POIS provided both a parameter-based POIS and an action-based POIS. 

The most common policy gradient methods, like SAC, PPO, TRPO, DDPG, are action-based. It seems to me that PO^2PE, instead, is parameter-based. I ask the author to confirm or deny this.

I think that this is actually the most unclear point of the paper. All the derivations are kept abstract, by considering generic samples $x$. It is not clear to me if the sample $x$ (for example in Equation 6) are policy parameters (i.e., like in $\omega_{\rho'/\rho}(\theta)$ in page 16 of https://www.jmlr.org/papers/volume21/20-124/20-124.pdf) are trajectories, or are something different. In my understanding, $x$ should be regarded as "lower-level" policy parameters, and $q$ is a process sampling policy parameter (what "A Survey on Policy Search for Robotics", calls Exploration in Parameter Space, page 16). 

If this is the case, then I do not fully understand the comparison with TRPO. TRPO performs exploration in the action space. 

Further, I think it was not specified in parameter-base POIS or action-based POIS was utilized.

My suggestion, however, is to well clarify what $x$ is at the beginning of the document. 

In general, I think that while the authors did a great job in explaining the theory, they used little space in the paper to describe the actual algorithm. In general, I would enjoy more reading the paper, if more and clear references were made in the theory about the RL problem and the designing of the algorithm. 


To outline another minor issue, the experiments consider only low-dimensional benchmarks. The usage of a more complicated high-dimensional environment would have made this submission stronger. 





summary_of_the_review: PROS

The paper considers an important problem and proposes a sound solution to it. I did personally enjoy learning the application of the importance sampling technique to reduce the estimation variance. I think that the theory shed new light on off-policy policy gradient algorithms.

The theoretical and empirical analyses are satisfying. 

CONS

The clarity of exposition could be improved by making the theory more linked to the actual RL problem. 

The authors considered only low-dimensional problems in the empirical evaluation, raising the question of whether the algorithm could be applied to more complex domains. However, I think that the theoretical analysis compensates for this minor weakness.


I would like the authors to clarify the doubt I wrote in the main review.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper analyzes the connection between searching for an optimal behavior policy that minimizes variance, and policy improvement in RL. The paper shows a number of interesting theoretical results, such as non-negative policy improvements, convergence and connections to implicit trust regions between consecutive policy iterates. The paper also shows results in constrained case where the policy class is parameterized. Finally, the paper shows empirical results on a few low-dimensional RL examples.
main_review: ========== Novelty =============

The idea of relating importance sampling (IS) to policy optimization and policy evaluation is not new. However, this paper digs into the technique of finding variance-minimization behavior distribution of IS, and establishes a few interesting & novel results related to policy optimization.

========== Literature reviews =============

This paper has followed the general logic and narrative of [1], relating "trajectory-based" policy optimization with IS. In "stepwise-based" formulation of RL, which is more common in the general RL literature, [2-5] also adopt ideas of stepwise IS for policy evaluation and optimization. I think such prior work and direct references therein should be of direct interest.

[1] Metelli et al, policy optimization via importance sampling, 2018
[2] Jiang et al, doubly robust off-policy value estimation for reinforcement learning, 2015
[3] Munos et al, safe and sample efficient off-policy reinforcement learning, 2016
[4] Huang et al, from importance sampling to doubly robust policy gradient, 2020
[5] Tang et al, taylor expansion policy optimization, 2020

========== Detailed questions =============

1. Throughout the paper, the authors assume the function f to be non-negative, such that the mathematical treatment of the variance-minimizing behavior distribution is more straightforward. I wonder how this can be implemented in practice, when the return functions are negative. For example, in many high-d continuous control benchmarks (e.g. Ant from openai gym), the initial returns are negative. Since on these environments, the trajectory lengths are not constant, adding a constant positive reward to each time step will not work since it modifies the optimal policy of the problem. If we add a single positive constant to the entire return, what constant should we choose? How does the additive constant impact stability of the algorithm?

2. Eqn 2 shows that the improvement is proportional to the variance of f under the previous distribution. In case the algorithm erroneously converges to a locally optimal deterministic policy, does it mean that the algorithm cannot get out of the local optimal because in such cases the improvement is zero (zero variance from a deterministic policy). Do such observations happen in practice with sampling errors & function approximations?

3. The implicit trust region in Thm 4.3 is interesting from a theoretical perspective, in that one could adjust the effective trust region size based on diff choices of the function h. However, I wonder how useful this result is in practice. In particular, can we choose h in a computationally efficient way to enforce a trust region of particular sizes? How do we estimate the implicit trust region given that it takes the form of a ratio? The trust region also depends on the numerical scale of f itself, which brings back to the issue of tackling problems where f is originally negative -- in this case, adding diff positive offset values will impact trust regions too. Can the authors elaborate on such points?

4. I suggest that the authors update algo 1 to reflect how the algorithm is implemented in practice. From what I understand, algo 1 specifies the ideal algorithm of finding variance minimizing behavior dist at each iteration. However, since the objective is rather diff to estimate, one resorts to an upper bound optimization with finite samples in Eqn 6, backed by Prop 5.1. Then the authors introduce a finite sample correction in Thm 6.1. This makes the algorithm a bit difficult to understand.

5. On experiments, I think the TRPO results in Fig 2-4 are a bit questionable. TRPO has long been considered a good performing algorithm if not state-of-the-art, yet I am rather surprised to see TRPO gets underperformed by many IS baseline algorithms on such low-dimensional problems. I wonder if the TRPO implementation deviates much from the original TRPO algorithm in Schulman et al, 2015.
Do the authors adopt a trajectory-based TRPO implementation or the stepwise-based TRPO implementations in Schulman et al, 2015?

6. Trajectory-based formulation of policy optimization is easier for mathematical treatment but I would argue it has limited application in large-scale practices. I think this is because product of IS ratios usually induce too much variance that in practice such methods are not quite stable. On toy examples, I could understand that such methods are still useful. This leads me to wonder -- is there a way to extend such formulations to step-wise optimization algorithms (PPO, TRPO, IMPALA, MPO...), in which case such ideas could be made more practically appealing.

7. All toy examples seem to have a natural non-negative return function. I wonder if the algorithm could be useful when returns are by design negative, in which case the choice of h is critical.

8. Minor note: I suggest replacing Q_theta by another notation as Q_theta confuses with Q-function, whereas here it refers to the parametric dist.
summary_of_the_review: Overall, I think the paper is solid in its theoretical contributions, yet is a bit lacking in a few important practical aspects.

1. Trajectory-based formulations of policy optimization is not practical when horizons are long. The application of such techniques to RL feels very black-box, as they do not leverage the Markov structure of the problem at all. I think extending such techniques to step-wise based policy optimization algorithm would make the approach more practically appealing.

2. Empirical results are a little bit suspicious in that TRPO underperforms in a significant manner. I would even argue that the combination of this approach with ideas from TRPO can make a more solid empirical case.
review_title: null

Meta-review: This paper received a split of scores, from 3 to 10. Among the reviewers, there are both strong advocates and strong rejects. All reviewers agree that finding a policy that is not only improving value but also has lowered variance is an interesting ideas. However, many reviewers point out that are major clarity issues that might hide fundamental problems. The proved guarantees seem to require strong assumptions that are unlikely to hold in practice, and experimental comparisons also have some subtleties. Taking together, although this could be a very interesting work, it will require a major revision and another round of review+discussions before it can be shaped into an acceptable paper.
Decision: Reject