Absolute Policy Optimization

1. The compared methods include TRPO (2015), PPO (2017), and A2C (2016). I think the recently proposed RL methods (After 2020) should be compared with the proposed one.
2. I suggest the authors improve the recently proposed RL methods by their APO for this comparison.
3. Running time comparison should be given.
4. It seems that a performance sample may be a long-length rollout.

I think the presentation of Section 4 needs to be improved substantially. It is not easy to read in current version. The lower/upper bound surrogates are introduced in Equation 4 and all definitions of associated terms are put below in a whole. I recommend the authors to take other means like using a table or list for more compact and clearer presentation. In addition, I think the explanation on the key steps of derivation is lacking.

For Equation 13, I do not see how the weighted sum form addresses the challenge mentioned above.

For some other thoughts, the optimization objective of AMDP given by Equation 3 reminds me of distributional RL. In distributional RL, the variance of policy performance can be computed with proper presentation of value distribution. Thus it seems that Equation 3 can also be optimized via distributional RL. And intuitively, it is more straightforward to resort to distributional RL when consider the distribution and the worst case of policy performance, especially when approximation and surrogates are inevitable to adopt and the theoretical guarantee may be last. It will be interesting to add some discussion on this.

For the experiments, the overall advantage of APO is not prominent due to many overlaps in error bars (i.e., the shades). As to the key hyperparameter $k$, the ablation in Section 7.6 is only conducted in one environment, which is not convincing enough to me.

Moreover, I recommend the authors to consider including V-MPO (Song et al., ICLR 2020) as a baseline since it is also a popular and performant on-policy policy optimization algorithm.

Minors:

• It should be $\omega_1, \omega_2$ in ‘where $\omega_1, \omega_1$ are weights to control the importance of optimization objectives’.
• $\pi_k$ is missing below ‘via importance sampling with a sampling distribution $\pi_k$’. It should be $\pi_j$ I guess.

• In Equation (7) and the following terms, there are several terms needed to calculate maximization over the entire state space. I don't think this surrogate function is computationally feasible when handling continuous control tasks, e.g., MuJoCo. This is my largest concern for this work. If the authors can explain this properly, I am happy to increase the score.
• Some points about clarity:
  • The meanings of the x-axis and y-axis are missing in Figure 1.
  • Typo: Two w_1 at the end of page 5.

Clarity

Some important concepts are presented in a rather vague and confusing way.

1. One of the most important contribution, monotonic improvement in Theorem 1, is presented in a vague way. It is unclear how the monotonic improvement has been achieved. In the proof, Equation (76) shows the performance bound can be lower bounded by the differences $M_j(\pi_{j+1}) – M_j(\pi_j)$. However, $M_j(\pi_{j+1})$ itself is a function over $\pi_{j+1}$ and it remain unknowns whether there exists such $\pi_{j+1}$ that leads to $M_j(\pi_{j+1}) > M_j(\pi_j)$. Hence, that “by maximizing $M_j$ at each iteration” will “guarantee that the true absolute performance $B_k$ is non-decreasing” may not hold. The paper needs to show, either via proof or a concrete example, that there exists at least one feasible $\pi_{j+1}$ that yields $M_j(\pi_{j+1}) > M_j(\pi_j)$.

2. Many conversions and transformations in Optimized APO are not well theoretically justified. Specifically, the optimization problems in Equation (11) and Equation (12) are inherently different: how the trust region constraint suddenly appears in Equation (12) and how this KL constrained optimization is approximately equivalent to lower bound surrogate-constrained optimization? Furthermore, why “equation 12 may often lead to infeasible solutions”? If this new formulation, as an approximation to the Equation (11), is infeasible, then why do we need this conversion in the first place? Moreover, the optimization in Equation (13) may not even share the same solution to the optimization in Equation (12). Also, the approximation to this Equation (13) in Equation (14) is not even consistent: how the advantage function becomes a squared function?

Significance

1. There is a substantial discrepancy between the proposed theory and the devised algorithm. While the formulation of improving the worst-case performance samples is interesting and has been theoretically analysed, the resulting algorithm, APO, deviates greatly from the original formulation. Specifically, the original formulation of the problem in Equation (2) & (3), i.e., Chebyshev-motivated variance analysis, is inherently different from the final optimization problem in Equation (13), Trust Region Optimization. This noticeable discrepancy between the original theory and the algorithm APO may invalidate all the theoretical analysis and conclusions for APO.

2. The final algorithm to the theoretical results is rather similar to the TRPO. Even the implementation shares the same idea to TRPO. The paper starts with a new set of theory, which tries to investigate the worst-performance sample. It is followed by some in-depth analysis. However, it suddenly ends up with many approximations and the final algorithm shares rather similar ideas to TRPO. I’m wondering how the new set of theory really helps the development of the new method (or they are just a different interpretation of TRPO?). Further, the final KL constrained optimization problem is solved using exactly the same method as in TRPO: second-order approximation to KL.

3. The empirical results are not sufficient to show the good performance of APO. Most empirical results in Figure 5 & 6 show that APO performs rather similarly to TRPO, which makes sense to me since these two algorithms have a rather similar formulation. More empirical investigations are needed to support that APO can be better.