Policy Optimization by Local Improvement through Search
Authors: Jialin Song
Joe Wenjie Jiang
Amir Yazdanbakhsh
Ebrahim Songhori
Anna Goldie
Navdeep Jaitly
Azalia Mirhoseini
Venue:  (2020)
Keywords: policy learning
imitation learning

Abstract: 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 or from interactive expert policy queries such as DAgger. 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 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.

Under review as a conference paper at ICLR 2020
POLICY OPTIMIZATION BY LOCAL IMPROVE- MENT THROUGH SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Imitation learning has emerged as powerful strategy for learning initial policies that can be refined with reinforcement learning techniques. Most strategies in im- itation learning, however, rely on per-step supervision either from expert demon- strations, referred to as behavioral cloning (Pomerleau) 1989 1991) or from inter- active expert policy queries such as DAgger (Ross al. 2011) lp. These strategies differ on the state distribution at which the expert actions are collected the for- mer 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 Dual Policy lteration (Sun 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 computation- ally expensive, and can also end up training the policy on a state distribution that is far from the current policy's s induced distribution. In this paper, we propose an algorithm that finds a middle ground by using Monte Carlo Tree Search (MCTS) (Kocsis & Szepesvári 2006) 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 improve- ment 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 14 in wall clock time. Fur- thermore, the resulting policy outperforms strong baselines in both reinforcement learning and imitation learning.
INTRODUCTION
Reinforcement learning (RL) has seen a great deal of success in recent years, from playing games (Mnih et al. 2015 Silver et al., (016) to robotic control (Gu et al., 2017 [Sigh et al. 2019). These successes showcase the power of learning from direct interactions with environments. However, a well-known disadvantage of reinforcement learning approaches is the demand for large number of samples for learning; for example, OpenAl Five learned to solve DOTA using Proximal Policy Optimization (PPO) (Schulman al. 2017) by playing 180 years worth of games against itself daily (OpenAl 2018). The issue with sample complexity can be mitigated by learning from expert be- havior. For example, AlphaStar (The Alpha Star Team 2019) uses models that are pre-trained using supervised learning techniques on expert human demonstrations, before RL is used for refinement.
variety of strategies have been developed in imitation learning learn from expert behavior, where the expert can be a human (Stadic et al. 2017) or pre-trained policy (Ho & Ermon 2016). Earlier approaches, such as behavioral cloning (BC), relied on training models to mimic expert behavior at various states in the demonstration data (Pomerleau 1991). However, these models suffer from the problem that even small differences between the learned policy and the expert behavior can lead to a snow-balling effect, where the state distribution diverges to a place where the behavior of the policy is now meaningless since it was not trained in that part of space (Ross & Bagnell 2010). In order to mitigate these issues, DAgger (Ross et al. 2011) uses expert policy to provide supervision to the policy being learned. While these strategies differ on the state distribution at which the expert actions optimized for example BC uses the state distribution of the expert, DAgger-like approaches

---

Under review as a conference paper at ICLR 2020
use the state distribution from the policy being trained- the supervision signal itself is the expert's behavior at each step.
On the other end of the spectrum, approaches rooted in policy iteration, such Dual Policy Iteration (Sun et al. 2018b) do not mimic next step actions of a policy directly, but instead use planning or search over the policy to choose action distribution to train towards (Silver et al., 2017). However, this can be computationally expensive, and can also end up training the policy on 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) (Kocsis & Szepesvári 2006) perform local trajectory improvement over states sampled from different time steps in the trajectory unrolled from the policy. This approach has the benefit of training the policy on a state distribution that is close to that induced by the policy itself, while using local search or planning over smaller horizon to generate a good policy to train towards. This approach stands in contrast to other works interactive imitation learning that correct distribution mismatch by using one-step feedback. We provide theoretical justification for the advantage of balanced local trajectory improvement and show that MCTS can serve as a policy improvement operator under certain condition
An added benefit of our effort is computational depth parallel MCTS on local trajectory segments is much faster than traditional sequential MCTS to generate demonstrations. We show that our pro- posed algorithm can casily be parallelized to enable more efficient imitation learning from MCTS. Notably, this level of parallelism is present at varying depths which differs from existing works on parallel MCTS (Chaslot et al. 2008
In summary, main contributions are:
A general interactive imitation learning algorithm that balances the expert feedback qual- ity and the state distribution divergence. Our proposed approach provides a flexible local trajectory improvement based on MCTS.
Theoretical analysis on the general benefit of local improvement and specific case study using MCTS as a local improvement operator.
Strong empirical performance on a suite of high-dimensional continuous control problems based on both sample efficiency and training time.
RELATED WORK
Imitation Learning. Imitation learning (IL) refers the problem of learning to perform a task from
expert demonstrations. Behavioral cloning (Widrow & Smith 1964) is one popular approach which
maximizes the likelihood of expert actions under the agent policy (Pomerleau
1989 Schaal 1999
Muller et al. 2006 Miling et al. 2013 Bojarski et al. 2016 Giusti et al. 2016 Mahler & Goldberg,
2017 Wang al. 2019 Bansal et al. 2018). Inverse Reinforcement Learning is another popular
form of II. where reward function is extracted from expert demonstrations and then policy is
trained to maximize that reward (Ziebart et al. 2008 Finn et al. 2016 Fu et al. 2018 Ho & Ermon 2016).
In this work we focus on imitation learning via behavioral cloning. Despite its success in canonical problems, such Go (Silver et al.) 2017) and Starcraft (The Alpha Star Team, 2019). behavioral cloning suffers from many challenges, most notably distributional shift (Daumé et al. 2009).
To explain distributional shift, let us assume train an agent by performing supervised learning on the actions an expert has taken. A small error in the first time step of training may bring the agent to state that the expert has rarely visited and is therefore not well modeled. Over time, this error compounds, leading the agent to states far from expert behavior and diverging further from the expert demonstrations. The longer the episode is, the more likely the agent is deviate from expert demonstrations.
'We note that other techniques such as Generative Adversarial Imitation Learning (GAIL) have been de- veloped that use example demonstrations in modified objective which is still trained by interacting with the environment (Ho& & Ermon] 2016). These approaches directly operate on the induced state distribution itself; we do not consider these approaches here
2

---

Under review as a conference paper at ICLR 2020
Various solutions the problem of distributional shift have been proposed (Daumé et al., 2009
Ross & Bagnell 2010 Ross et al. 2011: Ho & Ermon 2016; Laskey et al. 2017 Bansal et al,
2018 de Haan 2019). Some of these approaches reduce the effects of distributional shift by iteratively querying the expert (Daumé et al., 2009; Ross et al. 2011). DAgger (Ross et al. 2011). one of the most widely used of these solutions, queries the expert on each of the states that are visited by the policy and uses expert demonstrations to improve the policy.
At the other extreme, have Policy Iteration approaches, such Dual Policy Iteration (Sun al. 2018b), AlphaZero (Silver et al. (0177) and ExIT (Anthony et al.] (017) that do not directly mimic the actions of an expert. but instead plan or search over the policy to choose an action distribution to train towards (Silver et al. (017)). These methods can be computationally expensive and their long planning horizon can cause the state distribution to diverge far from the current policy's 's induced distribution.
In this paper, we propose a new algorithm, named POLISh, that strikes a middle ground by per- forming multi-step improvements over states sampled from different time steps in the trajectories generated by the policy. We use MCTS (Kocsis & Szepesvári 2006) to perform the local trajectory improvements. We show the promise of our approach with both theoretical and empirical results.
Monte Carlo Tree Search. We refer the reader to (Browne et al. 2012) for comprehensive sur- vey MCTS. To generate the proposed locally optimized trajectories, follow recent work that explores using MCTS to provide feedback for policy improvement (Guo et al. 2014 Silver et a 2017 Anthony et al. 2017p. MCTS is best-first tree search method which uses policy to explore the most promising actions first. Through repeated simulation, MCTS builds a tree whose nodes represent states and whose branches correspond actions that be taken from those states. The objective is to maximize total return, so after all simulations have been completed, a final trajectory generated by traversing the most visited sequence of nodes.
BACKGROUND & PRELIMINARIES
Markoy Decision Processes. We consider policy learning for Markov Decision Processes (MDPs) represented a tuple A, y, D). Let S denote the state space, AA the action space, P(s' a) the (probabilistic) state dynamics, r(s, a) the reward function, y the discount factor and 'D the initial state distribution.
Policy Learning. A stochastic policy maps a state E S to a distribution over the actions A, denoted by x (s). At each state, an action a is sampled from (s)) with probability (a]ss) and a reward of r(s, a) is received by The goal is to learn policy that maximizes the accumulated discounted rewards (=( = Eysz [Ei 7rr(ss, a;]]. We omit the dependency of the initial state distribution D when the context is clear. A few useful quantities related to policy the value function Vu,, the state-action value function Qn and the advantage function Ag defined as follows:
x (r(s = =s],
Vs(() Eyso
ax = E
7 7r((3,, 5, a),
1=0
A= a) -=((s))-V=(s)
As the policy takes sequence of actions, its performance has a strong connection to the state distribution induced by its actions. We define quantities related to the state distributions induced by policies at different time steps. Let d' denote the state distribution obtained by following for I
steps. We use d, = (1-7) xc d'd,, to denote the accumulated discounted state distribution. With these quantities, we can rewrite [Tx) Eee Eandy (0=x())>>)))))) (r"(s, a)] = Eeedd, (r(, a)).
We will make use of the following relationship between the two policies in our analysis (Kakade & Langford 2002):
J(x') J(m) Bynd, (Fawz (s, a)]] Throughout the paper, we use nt to denote the expert policy.
3

---

Under review as a conference paper at ICLR 2020
4 THE POLISH ALGORITHM
We first present general framework for imitation learning from local trajectory improvements in Section 4.1 We then describe method based on MCTS perform the proposed local trajectory
optimization in Section 4.2
4.1 MAIN ALGORITHM
Our main algorithm builds the observation that behavioral cloning (Pomerleau) 1991) and DAgger (Ross et al. 2011) are two extremes along a spectrum of possible algorithmss us- ing experts generate trajectory improvement. This is illustrated in Figure 1 The solid nodes represent the states visited by a current policy during rollout of length T. DAgger seeks to collect expert feedback on every state along while behavioral cloning only imitates sin- gle complete trajectory from the expert. DAg- ger collects 1-step demonstrations from every state while behavioral cloning collects T-step from single step. It is easy is a spectrum of algorithms that lie in between, parametrized by the time horizon É to collect expert demonstrations and the frequency with which to choose the start state for the expert policy.
1-8tap expert demonssraatins
T-step expert demonstrations
expert demonstrations
that there
DAgger
Cloning
Approach
Figure I: DAgger (Ross et al., 201 collects 1- step feedback at every state. Behavioral cloning collects T T-step feedback only from the initial state. Our method collects 1-step feedback at the frequency of every & states.
We present our main algorithm in Algorithm that collects locally improved partial trajecto- ries, as shown Figure a trains policy to imitate the expert on the collected trajectories. For each iteration, we first collect trajectories
from current policy π; (Line 3). Then, collect every k states from each trajectory to as starting states for running the expert policy (Line 7, 8, 9). From each state collected, we rollout n for steps generate partial trajectory (Line 12, 13). Once all the data has been generated, op- timize for the behavioral cloning loss L(D,a) T) [D] Σ ((.,er) (T(T()) * a")), i.e., the supervised learning loss from data collected in D, to generate new policy and repeat the process.
4.2 MCTS AS THE EXPERT POLICY
General imitation learning requires having access to expert policy. We follow series of recent works that explore applying MCTS to provide feedback for policy improvement (Guo et al.) 2014] Silver al., 2017 Anthony al., 2017). Specifically, for every iteration, n" becomes the policy obtained by running MCTS with n; by following variant MCTS that uses a slightly modified
UCT rule to select leaf node in MCTS: UCT(s, = =(s.a)
m(s,a) + e. (aas)) Ingg(s)
"issa)) where n(x) is
the number of times the node s has been visited so far. n(ss, a) is the number of times action is selected at node and r(s, a) is the sum of all rewards obtained in simulations by taking in s. At leaf node, Monte Carlo rollouts for value estimation (Browne et al,, (002)) is replaced by an estimate obtained from value network trained with the policy. This approach removes the need for a pre-defined expert policy and can be effective MCTS can serve to improve the policy. We provide sufficient condition that justifies this design choice.
THEORETICAL ANALYSIS
In this section, we provide theoretical justification for considering local trajectory improvement in relation to both behavioral cloning and DAgger. We then prove that, under certain conditions, MCTS
4

---

Under review as a conference paper at ICLR 2020
Algorithm POLISH (Policy Optimization by Local Improvement through Search)
1: Input: an initial policy Ti the expert policy n², the segment length t, number of iterations N, policy class
2: for S N do
3:
Sample {T,}ー=1 from x;
4:
5+0 0
5:
+ 0
6:
for each trajectory Tj = (su, au. $1, ... 81-1, 01-1,,8) do
7:
k [T/[]
8:
S; - (80, S1, 821: ... [kr)
9:
SUS
10:
end for
for each E S do
12:
Run nt" for & steps from the state to generate partial
trajectory
(s, 5. s/,,... -.-1.
13:
D DU [(8, dg), (1) ((-1))
14: end for
15: T++1 arg min L(D,x)
16:
end for
17:
return TN+1
can serve as a method for improving local trajectories, thus providing theoretical foundation for previous empirical works (Silver 2017: Anthony et al. 2017). We provide our proofs in the Appendix.
5.1 MOTIVATION FOR LOCAL TRAJECTORY IMPROVEMENT
Imitation learning only makes sense if the policy we are imitating is better than our current policy. We formalize below what "better" means this context:
Assumption 1. Assume that ** is an expert policy such that for every state 2 Eunn(s)lQ a)) and (ewrr (V* (8') > B (e)=x(e)))"wP(((la) VV (s')] for every 2 where Vh denotes the accumulated discounted k-step returns.
6 S, (s)
The first assumption ensures that J(x*) (Tr) according Equation 1 The second assumption ensures that one-step deviation from n" according to a will result in lower-valued states if we were follow n¹ from that point on. This is typically true if a is greedy policy so it pays less attention to future rewards.
To motivate the idea of using local trajectory improvement instead of complete trajectory imitation learning, we extend the analysis in (Ross & Bagnell 2010) on behavioral cloning. A major issue with
behavioral cloning is the potential cascading errors learned policy makes a mistake early on. This compounding behavior is captured in the following theorem:
Theorem 1. (Theorem 2.1 in (Ross& & Bagnell 2010), rewritten in terms of rewards instead of costs)
Let x be policy such that 6 Band_ ex {8]. Then J(T) 2 J(T*) - T2,, where T. is the task horizon and (s) (Bawa()) (s) [T a²))
The cascading error effect manifests as quadratic function in the task horizon. We can do a more careful analysis that motivates the design of algorithm that clones behaviors at shorter time scale. Define ffeff441 + (IT) to be the rewards obtained by following x' from time step to f from the start distribution d= -1, Assume we divide the time horizon into equal parts with length so that have T/t segments with f it.
T/t J(T) Σ
T/t
7 a(i-1) 1) f Jh (T) 2 Σ y ti ((li-)((ttttt)) Jlalee (T*) -(G)
(2)
5

---

Under review as a conference paper at ICLR 2020
where E, is the error rate computed between steps t, and 1,41 Assuming 6; holds across different segments, the expression above simplifies to
T/t
Tyt )- Σ
T/t
7" a(i-1) 1) Justenl (x²) ) 1 7 Pe
J(T) 2
Σ y 1 Ju
(x
D = Σ D0
(3)
The objective is to maximize (Tr and this is done by optimizing the lower bound on the right hand side via imitating n². Next, we consider how the two terms on the right hand side interact.
Proposition 1. Under Assumption E 7 1 flali 1 a multiple t. Furthermore, is maximized at T.
(T** S ΣTH (111-11 (T*) it
This proposition says that by multiplying the length of a segment, the first term grows.
Proposition 2. 1-22 1- ehe is an increasing function of for (0,
So the second term is also an increasing function in there can be a balance point where the right hand side is maximized, giving the tightest lower bound on the performance of policy
There is empirical evidence, (Silver et al. 2017 Anthony et al. 2017), that fitting to the expert action distribution is more robust approach than fitting to single action that the expert takes. In Proposition 2, we show that we can relate e to the KL-divergence between the action distributions of the policy and the expert.
Proposition 3. c c Esnd,- [e)( I Eand,- KL-divergence between two distributions and H the entropy of distribution.
+ H(T()))), where DKL is the
As a result, by optimizing the objective presented in Section 4.1 we are improving the lower bound presented in Equation 3
5.2 MONTE CARLO TREE SEARCH AS A LOCAL TRAJECTORY IMPROVEMENT OPERATOR
Now we turn our attention to π². traditional imitation learning, the expert policy x can be human expert (Ross et al., 2011] Stadie et al. (017)) or a pre- pre-trained policy (Ho & Ermon 2016). In either case, " considered fixed and independent of the current learned policy. Recently, several works (Guo et al. 2014, Silver et al.) 2016 Anthony et al.) 2017) explored using MCTS to plan ahead when a generative model of the underlying MDP is available (Kearns et al.) 2002 Kakade et al. 2003) and thus produce better action decisions compared with directly following a policy. This approach circumvents the requirement of having a pre-defined expert and has the nice property of bootstrapping from the existing policy (Sun et al. 2018b). However, it is not clear whether MCTS can always produce better trajectories for demonstrations. Another complication MCTS procedure, whose changes include that the UCT algorithm weights the exploration term by the policy prior probability and actual Monte Carlo rollout estimation of a state value is replaced by a value network.
the modified
Let V be a value network that estimates the true value function V&2 for π. During MCTS, whenever value estimation for a leaf node is needed, the value network is used. We can derive Q-function estimation Q for by using the following equation Q a) E/r(s, a) (s')s that is, we use the sampled rewards and value estimation for the next state to form an estimation for the Q- function, where the expectation is taken over the stochasticity of the environment transitions. The following theorem, for which we provide a proof the appendix, demonstrates that MCTS can effectively generate local trajectory improvement.
Theorem 2. For a state s S, let e S (1- T(aa(s)) ()) minaza (Q=(s,a") (=, (s,))))). After performing MCTS searches according the modified MCTS algorithm described in Section 4.2 we use (s( (8) to denote the action distribution at state s, which is proportional to n(,s, a). If V? ( V=(+)] < S.. as + 0o, Eas),, Qx (s, a)) 2 Ea-zte) (x(1,, (s, a)), that is, Tn(s) provides a one-
step improvement over

---

Under review as a conference paper at ICLR 2020
Art
Vallerdd
Happer
Dur Ratumn
Reum
Raturs
2000
23
1084
heattoon
beraiooe
beration
(a) Ant
(b) Walker2d
(c) Hopper
Figure 2: Average returns for continuous control tasks with different t values and the PPO baseline.
Experiment results are across 5 random seeded runs. Shaded area indicates +1 standard deviation.
300
Codle Theecree
200
begnon Lmggl
Segrost Lengh
(a) The MCTS improvement becomes higher as segment length increases (as suggested by Proposition] but the vari- ance also grows.
(h) The Kl--divergence of ac- tion distributions between pol- icy and MCTS grows as seg- ment length grows.
Wall clock time gener- ate MCTS trajectories par- allel increases as the segment length increases.
Figure 3: Tradeoff' between and improved rewards from MCTS, KL-divergence, time to generate data from MCTS in the Ant environment.
6 EXPERIMENT
The goals of our experimental evaluation are threefold: (1) to verify that there exists balance point for optimized length for local trajectory improvement, (2) to show that there is a trade-off between reward improvement by MCTS, and the divergence of action distributions between the policy and the expert (MCTS), (3) to demonstrate that the POLISH algorithm, by design, enables significant speedup with a parallel implementation that simple and efficient.
6.1 EXPERIMENT SETUP
We evaluate our algorithm on three environments (Ant, Walker2d, and Hopper) from OpenAl Gym (Brockman et al. 2016) with the MuloCo physical engine (Todorov al.) 2012). For each envi- ronment, we use the standard maximum trajectory length of 1000. For each trajectory, there are multiple MCTS rollouts, each of which is distributed on separate machine. This implementation takes advantage of the parallelizable nature of Lines 11, 12 in Algorithm [ For instance, with tra- jectory length of 1000 and a segment length of 32, we can achieve maximum parallelization by using 32 machines. Because the modified MCTS described in Section 4.2 relies on policy during search, we need a reasonably performant policy in order for MCTS to be able to improve trajectories locally as shown in Theorem 2 Thus, we pre-train policy with 1000 iterations of PPO (Schulman ct al. 2017). In the policy optimization step (Line 15 in Algorithm [T), we use an augmented version of DD, (TI((T] + (T) + (D, TT. The first two terms, as shown in Proposition 3 quantify the disagreement between т and π²", which we want to minimize. Note that in practice, we do not the 0-1 loss presented in Section [ since fitting distribution target leads more stable learning as noted (Anthony et al. (017)). The third term is a value loss similar to PPO (Schulman et al. 2017). need refine the value network for better MCTS performance.
7

---

Under review as a conference paper at ICLR 2020
6.2 MAIN RESULTS
Figure 2 compares POLISH with different segment lengths: 1000 (behavioral cloning), t = 32 and DAgger (Ross et al. (011). which can be regarded as t = with dataset aggregation across iterations, as well as the vanilla PPO. Overall, MCTS-driven imitation learning achieves a higher return compared to PPO in all three environments, and by significant margin with the best choice of segment length in particular. Regarding the choice of segment lengths, we show that our choice of / = 32 achieves a higher return than the two other extremes (4 and / 1000), in Ant and Walker2d which are complex environments. This provides empirical support for Equation [ which states that there exists a sweet spot for segment length in MCTS rollouts. However, in the simple Hopper environment, it is inconclusive which segment length leads to the best return.
6.3 EMPIRICAL EVIDENCE OF THEORY BEHIND POLISH
To further understand the impact of segment length on the return, we show the reward improvement after running MCTS with the current policy in Figure 3a and the KL-divergence of the action distributions between the MCTS and the policy in Figure 3b Ba shows how the first term in Equation 3 chhanges as function of segment length, and 3b depicts the Ant environment, we show both metrics for select range of segment lengths of (1, 4, 32, 256, 1000). As shown in our theoretical analysis, the MCTS return improvement (over the policy) generally increases with segment length, but so does the KL-divergence. Thus, there is a sweet spot for the segment length, where both the MCTS return improvement is high and the policy can effectively learn to imitate the MCTS expert.
approximation of the second term. For
6.4 PARALLEL IMPLEMENTATION SPEEDUP
able to achieve significant speedup with a parallel implementation. Our algorithm, by design, is easy to parallelize over distributed compute (Lines 11, 12 in Algorithm D. Every MCTS rollout from an initial state is independent, and thus can be conducted separate workers. The overhead of a parallel implementation, which arises from model synchronization across different workers and data transmission over the network, is likely insignificant compared to the workload of a MCTS rollout, especially for complex environments. Figure 3c shows the actual runtime of the parallel version of MCTS rollouts over a trajectory, compared the ideal lower-bound which is the runtime for one single MCTS rollout at a segment length t. Even with a small segment length, e.g., / = 32, which implies a high number of parallel tasks (=32) over a fixed trajectory length (=1000), the actual runtime is close to ideal. This suggests that we can easily achieve 0(10)X speedup for OpenAl Gym-liks environments. The overhead outweighs the benefit only when segment length is very small.
Lastly, we show that
7 CONCLUSION AND FUTURE WORK
In this work, we propose POLISH, general imitation learning algorithm that provides flexible local trajectory improvement based on MCTS. We provide theoretical analysis that sheds light on the benefit of local trajectory improvement as well a specific case study on MCTS. We validate the proposed approach by demonstrating strong empirical performance on suite of high- digensiinnsi continuous control problems, providing empirical support for our theory.
Model based methods have been proposed as a way to improve the sample efficiency of policy optimization (Watter et al., 2015) Finn & Levine 2016) Hafner et al.) 2018 Piergiovanni et al.) 2018 Clavera et al.) 2018 Sun et al.] 2018b] Janner et al.) 2019). However, model based policy optimization methods are vulnerable to model inaccuracy, which can lead to compounding errors for long horizon planning (Cheng et al. 2018). Nevertheless, the model can still be accurate enough for planning shorter trajectories, meaning that we can leverage it for the proposed POLISH algorithm, as it relies only local trajectory improvement. In particular, and use that model to perform MCTS. As long as the learned model is reasonably accurate on short time horizons (Sun et al. 2018b), can expect that it will be able improve the policy.
learn a model of the environment
8

---

Shixiang Gu. Ethan Holly. Timothy Lillicrap, and Sergey Levine. Deep reinforeement learning for robotic manipulation with asynchronous off off-policy updates. In 2017 IEEE international confer- Under review as a conference paper at ICLR 2020
In this work, focused expert feedback collection method with a fixed local search horizon. One future direction would be to design a more adaptive approach where the length of local search horizons are learned, striking balance between feedback quality and state distribution shift.
REFERENCES
Rajeev Agrawal. Sample mean based index policies by (log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4):1054-1000 1995.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Advances in Neural Information Processing Systems, pp. 5360-5370, 2017.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-255 2002.
Mayank Bansal, Alex Krizhevsky, and Abhijit S. Ogale. Chauffeurne:: Learning drive by imitating the best and synthesizing the worst. CoRR, abs/1812.03079, 2018. URL http:
//arxiv.orr//bb//1122200
Mariusz: Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, and Jiakai Zhang. End end learning for self-driving cars. arXiv preprint arXiv: 16440:160 2016.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 540, 2016.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
Guillaume MJ-B Chaslot, Mark HM Winands, and Jaap van Den Herik. Parallel monte-carlo tree search. In International Conference Computers and Games, pp. (0- 2008
Ching-An Cheng, Xinyan Yan, Nathan D. Ratliff, and Byron Boots. Predictor-ccoreector policy optimization. CoRR, abs/1810.06509, 2018. URL/http:// http://aaai....o//////////////1/
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. CoRR,
2018.
Hal Daumé, John Langford, and Daniel Marcu. search-based structured prediction. Machine learn- ing, 75(3):997-325, 2009.
Pim de Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. CoRR, abs/1905.1 11979, 2019.
Chelsea Finn and Sergey Levine. Deep visual foresight for planning robot motion. CORR, abs/1610.00666, 2016.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning; Deep inverse optimal control via policy optimization. Internation Conference Machine Learning, 2016.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse rein- forcement learning. International Conference in Learning Representations, 2018.
Alessandro Giusti, Jerome Guzzi, Dan Ciresan, Fang- He, Juan Pablo Rodriguez. Flavio Fontana, Matthias Faessler, Christian Forster, Jurgen Schmidhuber, Gianni Di Caro, Davide Scaramuzza, and Luca Gambardella. A machine learning approach visual perception of forest trails for mobile robots. IEEE Robotics and Automation Letters, 2016.
on robotics and automation (ICRA), pp. 3389-3399 IEEE, 2017.

---

Under review as a conference paper at ICLR 2020
Xiaoxiao Guo, Satinder Singh, Honglak Lee, Richard L Lewis, and Xiaoshi Wang. Deep learning for real-time atari game play using offline monte-carlo tree search planning. In Advances in neural information processing systems, pp.
2014.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. CoRR, 18111181155,, 2018.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems, pp. 4565 4573, 2016.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. https://urrxxvorrg//d// 906. http:///////........22....... 2019.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference Machine Learning, 2002.
Sham Machandranath Kakade et al. On the sample complexity of reinforcement learning. PhD thesis, 2003.
Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine learning, 49(2-3):193-208, 2002.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-288220 292.299. Springer, 2006.
Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. 2006.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6(1):4-2,, 1985.
Michael Laskey, Jonathan Lee, Roy Fox, Anca Dragan, and Ken Goldberg. Dart: Noise injection for robust imitation learning. arXiv preprint 17X3::7703009322 2017.
Jeffrey Mahler and Ken Goldberg. Learning deep policies for robot bin picking by simulating robust grasping sequences. In Sergey Levine, Vincent Vanhoucke, and Ken Goldberg (eds.), Proceedings of the 1st Annual Conference on Robot Learning, volume 78, pp. 515-524, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51550)))):52, 2015.
Urs Muller, Jan Ben, Eric Cosatto, Beat Flepp, and Yann L Cun. Off-road obstacle avoidance through end-to-end learning. Advances in neural information processing systems, pp. 739746, 2006.
Katharina Mlling, Jens Kober, Oliver Kroemer, and Jan Peters. Learning to select and generalize striking movements in robot table tennis. Journal of Robotics Research, pp. 263279, 2013.
Andrew Y Ng. Shaping and policy search in reinforcement learning. PhD thesis, University of California, Berkeley, 2003.
OpenAl. Openai five, 2018. URL
wtw.ppppaa...oopppaaaaaa.a.a five/
A. J. Piergiovanni, Alan Wu, and Michael S. Ryoo. Learning real-world robot policies by dreaming. CoRR, 0tts//805.078111 2018.
Dean A Pomerleau. Alvinn:
An autonomous land vehicle a neural network. In Advances in neural information processing systems, pp. 305-313, 1989.
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral Computation, 3(1):88-97, 1991.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the
thirteenth international conference on artificial intelligence and statistics, pp. 661-668 2010.
10

---

Under review as a conference paper at ICLR 2020
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference artificial intelligence and statistics, pp. 627-635, 2011.
Stefan Schaal. Is imitation learning the route to humanoid robots? Trends in cognitive sciences, pp- 233242, 1999.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)3354, 2017.
Avi Singh, Larry Yang, Kristian Hartikainen, Chelsea Finn, and Sergey Levine. End-to-end robotic reinforcement learning without reward engineering. arXiv preprint arXiv: 1904007904 2019.
Bradly C Stadie, Pieter Abbeel, and Ilya Sutskever. mhird-person imitation learning. arXiv preprint arXiv:1703.01703 2017.
Wen Sun, Andrew Bagnell, and Byron Boots. Truncated horizon policy search: Combining rein- forcement learning & imitation learning. arXiv preprint arXiv: 2018a.
Wen Sun, Geoffrey Gordon, Byron Boots, and Bagnell. Dual policy iteration. In Advances in Neural Information Processing Systems, pp. 7059-7069, 2018b.
The Alpha Star Team. Alphastar: Mastering the real-time strategy game starcraft 11, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Dequan Wang, Coline Devin, Qi-Zhi Cai, Philipp Krähenbühl, and Trevor Darrell. Monocular plan view networks for autonomous driving. CoRR, Nes/1995.06937, 2019. URL http::////a/ hrg/abs/19955 06937
Manuel Watter, Jost Tobias Springenberg, Joschka Boedecker, and Martin A. Riedmiller. Em- bed control: A locally linear latent dynamics model for control from raw images. CoRR, abs/1506.07365. 2015.
Bernard Widrow and Fred W Smith. Pattern- necten-reeoggizzing control systems. In Computer and Infor- mation Sciences: Collected Papers on Learning, Adaptation and Control in Information Systems, pp. 288-317. Spartan Books, 1964.
Brian D Ziebart, Andrew Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. pp. 14331438, 2008.
A PROOFS FROM SECTION
Proof of Proposition
Proof. Let t' kt for some positive integer k. Since Algorithm [ collects initial state every and steps, respectively. The set of starting states collected with the interval t' is subset of those collected with an interval of We will show that for the first segment of length t' starting from some state s, fox (л*)= 2 E ()-1)) (afaa1(7)) Similar proof holds for the other segments as well.
11

---

Under review as a conference paper at ICLR 2020
& Σ
Jun (x*)
2(6 1) J (TT)
(4)
k
7 1(8 jliieet (TT*)
(5)
The inequality holds term-by-term because by Assumption following и instead of x² generates
state distributions that induce lower valued states.
To show that the sum is maximized at = T, consider any t < T.
T/t
JoT (T
Σ
26 1) 1 plaffe (TT)
(6)
x
T/t
Σ
16 jhile+ (TT")
follows that the is maximized & T.
Proof of Proposition
Proof. Let f(t) T-
To prove this proposition, it suffices to show that f(t) is increasing function for 0. First we take the derivative and get f'(1) 21(1- + 1n
71-
Let gt) = 21(1- -²) + f²² In y be the numerator term. sufficient to show that g(t) >> 0 for
t 0. Taking the derivative for g(t), obtain
g'(t) 2 2t/ ln + (2th + Inn)
2- + (In (2
the last inequality follows from 7 E (0, So g(t) is increasing, i.e., g(t) > g(0) = =0. It follows
that (1( and (t) is increasing function tf
L
Proof of Proposition
Proof.
Bend; [s)(s)]
Egnd, . 12 (1
(9)
aEA
< Eandar (T(())) log (als))
(10)
= Eandg,
+ H(T())))
(11)
Proof of Thcorem 2
We first provide analysis that extends theoretical guarantees of UCT Koesis et al. 2006 Koesis & Szepesvári 2006) to the setting with the modified UCT rule as in 4.2
As usual, connect UCT with the Sopper-Confidenee Bound algorithm in multi-armed bandits problem (Lai & Robbins 1985 Agrawall 19955; Auer et al., (002) by framing the UCT as a non- stationary bandit problem. Specifically, assume there K arms. At time step arm i has
12

---

Under review as a conference paper at ICLR 2020
reward distribution Xa which lies in the interval [0, 1] for simplicity. Unlike in traditional multi- armed bandits, we allow X to vary as a function of t. Following the standard procedure for ana- lyzing UCT-type algorithms in (Kocsis et al. 2006 Kocsis & Szepesvári 2006), we assume that the reward distributions concentrate.
Assumption 2. For each 1 S i Xin E Xat converges. Let Pin E[Xin] in) and 14 = -imo Pin- Let sen be the bias with respect to pug Le., den = P4-Pin assume that there exists a constant Cp > 0 and an integer Np such that for n 2 for any ō > 0, An( = C the following two tail probability inequalities are satisfied
a
P(X is 2 14 + A. (1) 8
(12)
P(X S 14 - A. (8)) 5
(13)
The UCB algorithm balances the ingloration-exploitaaiinn est upper confidence bound. We consider a related variant of UCB that weights the exploration term by some prior probabilities p; for arm i. A central quantity analyzed in multi-armed bandit problems is the regret which connects the number of times some sub-optimal arm is chosen. Let (n) be random variable representing the total number of times that arm is chosen in the first rounds. We assume a unique optimal arm exists and its related quantities will be indexed by *, ie.. Po, Po,"", T. (n), X, We first upper bound the expected number of choices of sub-optimal arm in terms of its sub-optimality A; μ=" U4 and the prior probability.
problem by selecting arms with the high-
Since Jiin converges to b4g as n -> DO, din converges to zero, so for any 6 > 0, there exists an index No(E) such that if No(e), then 10:r1 S شي for every arm i.
Theorem 3. Under Assumption
if we use Cr.s = 2Cpp + No(e) + No + r (e + e.?).
Int for the modified UCB algorithm. Fix x
e <> 0, [[T((n)]
16p In
[--PA
Proof. We follow the proof in (Koesis al. 2006). Define eo(n, min(s]ers S (1-e)a J. Since Cts 20pv Inn,
2p;
/ 8 co(n, =
100 (1-cp-a7
Let A(n,e) max(Ao(n, No((),,, No(c),N)).
Then
n
(imn= =1
Σ 1(1=1)
(14)
t=K-1
S A(n,)) +
Σ
11:=i, 1)2 c(n,e))
(15)
t=K+1
1-1
[-1
S <((n,)) + ΣΣΣ Σ
1(x,
+ Six + p.css)
(16)
1=1 s=1 s'=A(n,c)
We observe that X, + P.Ct,s S Xie + PiCa, implies that at least one of the following is true
X + PpCcs S n¹
(17)
X 2 u4 + P:Ct,s'
(18)
n² < #4 + Pi
(19)
Since s' 2 A(n, c) and by the construction of A(n, c), A(n, c) Z Ao(n, and A(n, c) 2 No(c),
so the inequality (19) does not hold. Thus, either (17) or (18) must hold. So I(X, + p. <
X + piCt,ar) < I(X; + P.C,, S p²) + I(X,, i,'' 2 p4 + p. Now we can utilize inequalities (4) and (5) to derive upper bound on the two probabilities, so
T(X, +' 5p PXX S 1 - p' ((s))) S o 12/11
(20)
I(X i,'' 2 14 p.ct,s) = PXX,, o 2 p4 + pia),) S eat /
(21)
Plugging those quantities into (8) and use the relaxation that A(n,c) S An( + No(c) + N,, obtain the desired result.
13

---

Under review as a conference paper at ICLR 2020
It follows that the asymptotic probability of choosing sub-optimal goes zero, the same guarantee in the original UCT algorithm, the rate of convergence multiplied by the the square of the prior probability př. This means that if the prior probability is informative that it assigns small probabilities to sub-optimal arms, we can identify the optimal arm faster.
Next, consider the rollout step with an estimation, usually from a value network learned with a policy (Silver et al, 2017 Anthony al., 2017). An accurate value estimation can effectively reduce the amount of lookahead necessary to identify an optimal action (Ng. 2003 Sun et al. 2018a). On the other hand, an inaccurate value estimation can mislead the MCTS process. We provide sufficient condition under which MCTS is guaranteed to improve the policy. It follows that, compared with the true Q-function (T a).
drastic change to the MCTS procedure by replacing the Monte Carlo
(0, a) (s) |E[r(ss a) (s)) +VV())))
- =>|BIV (5') - (s)))
(22)
S7 27
Before we finally prove the main theorem, we need the following lemma stating improvement when computed with respect the estimated Q-function.
Lemma 1. Let a" arg max,, (= a) for state and S (1 (s)"ls)) minaye- (=(,aa)) ()) Then as + xx, (s)) [Qth (8, a)] 2 Eu-a(s) [0t (s, a)] +
Proof. As n + 0o, (s) becomes a delta distribution with probability mass I on the a", so
E (s)n, (Q= a)] E (+, (15 =
(= a²) - (a
(23)
= (1 - x xaa" (s)) (s, a²) Bann(e). 12% (8, a)]
(24)
2 (1 x(aa (s)) min (% (5,))
(25)
aza
(26)
Finally, we prove the main theorem,
E (x) 2 (s)
(27)
an E (3,
(28)
E (2 -e-
(29)
Rawa(s) (Q) ")
(30)
2 Ea- (2
(31)
14


Reviews:
[{"review_id": "rkgsiAyOOS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes POLISH, a reinforcement learning learning algorithm based on imitating partial trajectories produced by an MCTS procedure. The intuition behind this idea is that behavioral cloning suffers from distribution shift over time, and using MCTS allows imitation learning to be done on states closer to the policy's state distribution, which the authors justify using techniques similar to DAgger. The authors evaluate this method on continuous OpenAI Gym tasks, and show that it consistently beats a PPO baseline.\n\nOverall, my decision for this paper errs on the side of reject. This primarily comes from the fact that the writing is unclear to me, and this algorithm needs both access to an expert and a reward function, which is a setting that I'm not sure is very applicable in practice. Additionally, the experimental results seem fairly weak. In the imitation learning setting, there appears to be little difference between behavioral cloning, DAgger, and an intermediate segment length. In the reinforcement learning setting, the PPO baseline seems to be unfair, which I detail below. \n\nThe writing is confusing to me as it mixes two seemingly distinct problem settings (imitation learning and reinforcement learning) and interferes with my full understanding of the motivation of the paper. My current guess is that this paper is primarily aimed towards policy optimization in a reinforcement learning setting. The algorithm can start from scratch with a random initial policy, and optimize the policy to maximize total returns. However, much of the paper is written as if the setting were imitation learning, where expert advice is available. If this paper is primarily aimed at imitation learning paper, I am unsure of the advantage of using this method over DAgger. My hypothesis is that the primary use-case of POLISH over DAgger is when the provided expert is suboptimal, and using MCTS allows the policy to improve beyond the expert. However, this point is not provided in the paper.\n\nFor the experiments, I'm not sure that PPO is a directly comparable baseline. \n1) Were queries to the simulator used during MCTS accounted for when measuring sample complexity? (Figure 2). Being able to query the environment without cost is a significant advantage to POLISH in terms of sample complexity. \n2) Additionally, it was stated that POLISH had access to a pre-trained policy, which is additional information that PPO cannot exploit. A reasonable comparison could be to initialize the PPO agent from that pre-trained policy, or to not give POLISH access to the pre-trained policy.\n\nFor related work, I would argue that an important class of algorithms to mention are RL methods based on imitating some sort of policy improvement procedure. This includes work such as (not exhaustive) self-imitation learning (Oh 2019), the cross-entropy method, guided policy search (Levine 14), reward-weighted regression (Peters 07) and UREX (Nachum 17).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1g0TOI8KS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper was confusing and difficult to read.  I think it is trying to devise a methodology that improves upon a given expert policy, but I am not confident whether if this is the objective.  The main contribution of the paper is the algorithm POLISH on page 5.  However, it was unclear how MCTS with UCT is used with the expert policy in the algorithm.  The first mention of the 0-1 loss objective is in section 4.1, and Algorithm 1 on page 5 claims to minimize this loss on line 15.  However, in the experiment, the loss function is then switched to another L(D, \\pi) = D_{KL}(\\pi || \\pi*) + H(\\pi) + Lv(D, \\pi).  Why the switch?  And what is the definition of the third term?  By examining the experimental results, Algorithm 1 seems to outperform PPO.  Since the expert policy is known and given to Algorithm 1, I speculate Algorithm 1 is only replicating the expert policy, which would have outperformed PPO that has to learn from scratch.  Thus, the comparison does not seem fair.  It would be interesting to see how POLISH compares with the expert policy.\n\nOther comments:\n\n* Page 1 in Introduction: “However, these models suffer from the problem that even small difference between the learned policy and the expert behavior can lead to a snow-balling effect, where the state distribution diverges to a place where the behaviour of the policy is now meaningless since it was not trained that part of space”.  Do you mean that the algorithm diverges instead of the state distribution diverges?   The agent may incur errors in a space that has not been observed, but it should be able to learn eventually.  So, what is causing divergence in states that have not yet encountered?  \n\n* Page 4 in The POLISH Algorithm Main Algorithm: the 0-1 loss function is defined to be “L(D, \\pi) = 1/|D| \\sum_{s,a*}\\in D (I(\\pi(s) \\neq a*)), where a* is the expert policy’s selected action.  I think it makes more sense to write “L(D, \\pi)\" as 1/|D| \\sum_{s,a*}\\in D I ( a \\neq a* : a ~ \\pi(s)).  Also, in RL, we don't say that the policy receives a reward, but rather the agent receives a reward. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gDz3KpYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n[Summary]\nThis 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.\n\n[Decision]\nA 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.\n\n[Explanation]\nIn 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.\n\nIt 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. \n\nThe 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.\n\nDoes 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.\n\nDoes 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.\n\nIn 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.\n\nIn 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?\n\n\n[Minor comments]\n- 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.\n- How is t=32 chosen for the experiments in Fig 2?\n-------------------\nAfter 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.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your detailed responses to the reviewers, which helped us a lot to better understand your paper.
However, given that the current manuscript still contains many unclear parts, we decided not to accept the paper. We hope that the reviewers' comments help you improve your paper for potential future submission.
Decision: Reject