Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a method, Dual-AC, for optimizing the actor(policy) and critic(value function) simultaneously which takes the form of a zero-sum game resulting in a principled method for using the critic to optimize the actor. In order to achieve that, they take the linear programming approach of solving the bellman optimality equations, outline the deficiencies of this approach, and propose solutions to mitigate those problems. The discussion on the deficiencies of the naive LP approach is mostly well done. Their main contribution is extending the single step LP formulation to a multi-step dual form that reduces the bias and makes the connection between policy and value function optimization much clearer without loosing convexity by applying a regularization. They perform an empirical study in the Inverted Double Pendulum domain to conclude that their extended algorithm outperforms the naive linear programming approach without the improvements. Lastly, there are empirical experiments done to conclude the superior performance of Dual-AC in contrast to other actor-critic algorithms. 

Overall, this paper could be a significant algorithmic contribution, with the caveat for some clarifications on the theory and experiments. Given these clarifications in an author response, I would be willing to increase the score. 

For the theory, there are a few steps that need clarification and further clarification on novelty. For novelty, it is unclear if Theorem 2 and Theorem 3 are both being stated as novel results. It looks like Theorem 2 has already been shown in "Randomized Linear Programming Solves the Discounted Markov Decision Problem in Nearly-Linear Running Time”. There is a statement that “Chen & Wang (2016); Wang (2017) apply stochastic first-order algorithms (Nemirovski et al., 2009) for the one-step Lagrangian of the LP problem in reinforcement learning setting. However, as we discussed in Section 3, their algorithm is restricted to tabular parametrization”. Is you Theorem 2 somehow an extension? Is Theorem 3 completely new?

This is particularly called into question due to the lack of assumptions about the function class for value functions. It seems like the value function is required to be able to represent the true value function, which can be almost as restrictive as requiring tabular parameterizations (which can represent the true value function). This assumption seems to be used right at the bottom of Page 17, where U^{pi*} = V^*. Further, eta_v must be chosen to ensure that it does not affect (constrain) the optimal solution, which implies it might need to be very small. More about conditions on eta_v would be illuminating. 

There is also one step in the theorem that I cannot verify. On Page 18, how is the squared removed for difference between U and Upi? The transition from the second line of the proof to the third line is not clear. It would also be good to more clearly state on page 14 how you get the first inequality, for || V^* ||_{2,mu}^2. 


For the experiments, the following should be addressed.

1. It would have been better to also show the performance graphs with and without the improvements for multiple domains.

2. The central contribution is extending the single step LP to a multi-step formulation. It would be beneficial to empirically demonstrate how increasing k (the multi-step parameter) affects the performance gains.

3. Increasing k also comes at a computational cost. I would like to see some discussions on this and how long dual-AC takes to converge in comparison to the other algorithms tested (PPO and TRPO).

4. The authors concluded the presence of local convexity based on hessian inspection due to the use of path regularization. It was also mentioned that increasing the regularization parameter size increases the convergence rate. Empirically, how does changing the regularization parameter affect the performance in terms of reward maximization? In the experimental section of the appendix, it is mentioned that multiple regularization settings were tried but their performance is not mentioned. Also, for the regularization parameters that were tried, based on hessian inspection, did they all result in local convexity? A bit more discussion on these choices would be helpful. 

Minor comments:
1. Page 2: In equation 5, there should not be a 'ds' in the dual variable constraint
review_title: Overall a good paper, with a few details that need clarification

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper is well written, and the authors do an admirable job of motivating their primary contributions throughout the early portions of the paper. Each extension to the Dual Actor-Critic is well motivated and clear in context. Perhaps the presentation of these extensions could be improved by providing a less formal explanation of what each does in practice; multi-step updates, regularized against MC returns, stochastic mirror descent. 

The practical implementation section losses some of this clear organization, and could certainly be clarified each part tied into Algorithm 1, and this was itself made less high-level. But these are minor gripes overall.

Turning to the experimental section, I think the authors did a good job of evaluating their approach with the ablation study and comparisons with PPO and TRPO. There were a few things that jumped out to me that I was surprised by. The difference in performance for Dual-AC between Figure 1 and Figure 2b is significant, but the only difference seems to be a reduce batch size, is this right? This suggests a fairly significant sensitivity to this hyperparameter if so.

Reproducibility in continuous control is particularly problematic. Nonetheless, in recent work PPO and TRPO performance on the same set of tasks seem to be substantively different than what the authors get in their experiments. I'm thinking in particular of:

Proximal Policy Optimization Algorithms (Schulman et. al., 2017)
Multi-Batch Experience Replay for Fast Convergence of Continuous Action Control (Han and Sung, 2017)

In both these cases the results for PPO and TRPO vary pretty significantly from what we see here, and an important one to look at is the InvertedDoublePendulum-v1 task, which I would think PPO would get closer to 8000, and TRPO not get off the ground. Part of this could be the notion of an "iteration", which was not clear to me how this corresponded to actual time steps. Most likely, to my mind, is that the parameterization used (discussed in the appendix) is improving TRPO and hurting PPO.

With these in mind I view the comparison results with a bit of uncertainty about the exact amount of gain being achieved, which may beg the question if the algorithmic contributions are buying much for their added complexity?

Pros:
Well written, thorough treatment of the approaches
Improvements on top of Dual-AC with ablation study show improvement

Cons:
Empirical gains might not be very large

review_title: Good contribution

final_score: rating: 7: Good paper, accept
review_content: This paper studies a new architecture DualAC. The author give strong and convincing justifications based on the Lagrangian dual of the Bellman equation (although not new, introducing this as the justification for the architecture design is plausible).

There are several drawbacks of the current format of the paper:
1. The algorithm is vague. Alg 1 line 5: 'closed form': there is no closed form in Eq(14). It is just an MC approximation.
line 6: Decay O(1/t^\beta). This is indeed vague albeit easy to understand. The algorithm requires that every step is crystal clear.

2. Also, there are several format error which may be due to compiling, e.g., line 2 of Abstract,'Dual-AC ' (an extra space). There are many format errors like this throughout the paper. The author is suggested to do a careful format check.

3. The author is suggested to explain more about the necessity of introducing path regularization and SDA. The current justification is reasonable but too brief.

4. The experimental part is ok to me, but not very impressive.

Overall, this seems to be a nice paper to me.
review_title: an interesting paper

Meta-review: All of the reviewers agree that the paper clearly presents promising ideas in developing a novel actor critic algorithm. The experiments do not show a significant gain against the baselines, but they support the presented ideas. I appreciated the ablation study on dual-AC.

Detailed comments:
My understanding is that the x-axis in Figures 1 & 2 shows the number of iterations each of which contains batch_size*1000 environment steps. It is more standard to show those plots in terms of the number of environment steps. Further, the optimal batch_size for different algorithms may be different, so using the same batch_size for all of the algorithms is not fair.
Decision: Accept (Poster)