Imitation learning has emerged as a powerful strategy for learning initial policies that can be refined with reinforcement learning techniques. Most strategies in imitation learning, however, rely on per-step supervision either from expert demonstrations, referred to as behavioral cloning (Pomerleau, 1989;1991) or from interactive expert policy queries such as DAgger (Ross et al., 2011). These strategies differ on the state distribution at which the expert actions are collected -the former using the state distribution of the expert, the latter using the state distribution of the policy being trained. However, the learning signal in both cases arises from the expert actions. On the other end of the spectrum, approaches rooted in Policy Iteration, such as Dual Policy Iteration (Sun et al., 2018b) do not choose next step actions based on an expert, but instead use planning or search over the policy to choose an action distribution to train towards. However, this can be computationally expensive, and can also end up training the policy on a state distribution that is far from the current policy's induced distribution. In this paper, we propose an algorithm that finds a middle ground by using Monte Carlo Tree Search (MCTS)  to perform local trajectory improvement over rollouts from the policy. We provide theoretical justification for both the proposed local trajectory search algorithm and for our use of MCTS as a local policy improvement operator. We also show empirically that our method (Policy Optimization by Local Improvement through Search or POLISh) is much faster than methods that plan globally, speeding up training by a factor of up to 14 in wall clock time. Furthermore, the resulting policy outperforms strong baselines in both reinforcement learning and imitation learning.
[Summary]
This paper proposes POLISH, an imitation learning algorithm that provides a balance between Behavioral Cloning (BC) and DAgger. The algorithm reduces the mismatch between the target policy and an expert policy on states obtained from starting at the target policy's state distribution and following the expert policy for a time segment of t steps. The claim is that a suitable t will keep the training states close to the target policy's state distribution and avoid the compounding errors that arise when the agent drifts away from its training distribution. The paper also explores the possibility of policy optimization by replacing the pre-defined expert policy in POLISH with a policy derived from Monte Carlo Tree Search. Theoretical and empirical analyses in the paper studies the effect of t and MCTS planning in POLISH on policy improvement.
[Decision]
A clear study of the dimension between BC and DAgger is a useful contribution to the literature and an algorithm that effectively solves the distributional shift problem in BC will be of high practical value. However, the results in this paper do not support the claim that a reasonable time segment length in POLISH alleviates this problem. The theory shows a bound on the performance of the target policy that varies with t, but it is not clear if a suitable t is better than the two extremes, i.e., BC and DAgger. The experiments section is limited and, on two out of the three tasks, there is no considerable difference between the performance of POLISH, BC, and DAgger. I am leaning towards rejecting this paper.
[Explanation]
In Section 5, Theorem 1 shows the effect of t, the length of time segments, on the performance and the target policy by providing a bound. If this theorem is motivating a middle ground between BC and DAgger, it needs to show that a value of t other than the extremes will maximize the bound. The bound in the paper consists of a positive term and a negative term, both of which grow with t. It is then concluded that a balance point will maximize the overall bound. I do not see how it follows that this balance point is a middle ground and not an extreme value. If, for example, the negative term grows faster than the positive term, then DAgger (t=1) will be have the best performance according to this theorem.
It is not clear how the bound in Theorem 1 is comparing the performance of algorithms with different values of t. For a fixed policy, one can obtain different bounds by choosing different values of t. These bounds will have different values of \epsilon. The state distribution for \epsilon is the distribution of states visited in a limited time segment (which depends on the target policy, the expert policy, and the segment length). Using \epsilon (or \epsilon_i) in the bound drops the relationship between \epsilon and the length of time segments, and hides the fact that different algorithms are minimizing different errors. 
The equality in Eq 2 is not obvious to me. J(\pi) is and expectation under the discounted visit distribution. For example, if gamma is small, then the states in the start state distribution will have a higher weight in J(\pi) while the right-hand side sums over the expected performance in all time segments equally. I believe the later terms in the sum should also be discounted.
Does changing t also affect the MCTS step and the expert policy obtained from it? If so, it is possible that a suitable t will result in better performance because the MCTS step finds a stronger expert policy, and not because the imitation learning step better reduces the error.
Does the MCTS step use the perfect simulator or a learned model in the experiments? If POLISH, unlike PPO, has access to the MDP, the comparison of these two methods is not fair.
In Fig 2 (a) and (c), the curves for t=1, t=32, and t=1000 overlap through most of the training process. This is not conclusive evidence that a sweet spot for t results in better performance. An experiment on a simpler setting with more runs may elucidate the effect of t on the performance.
In 6.3, what does the reward improvement after running MCTS with the current policy precisely mean, and how does this correspond to the first term in the bound, i.e., the sum of the expected performance of \pi_* over time segments?
[Minor comments]
- I suggest adding the process of obtaining an expert policy through MCTS to Algorithm 1. It is hard to understand the process without a clear step-by-step description.
- How is t=32 chosen for the experiments in Fig 2?
-------------------
After rebuttal: I have read the authors' response and the other reviews. The rebuttal addresses my questions and concerns about clarity of presentation. However, I am still not convinced by the evidence in this paper. On two out of the three environments, the performance of the three values of t is not much different through the training and this is not because of the advantage over PPO. On Ant, for example, the curves for t=32 and t=1000 are not even one std apart through most of the training.