Published as a conference paper at ICLR 2018 TRUNCATED HORIZON POLICY SEARCH: COMBINING REINFORCEMENT LEARNING & IMITATION LEARNING
In this paper, we propose to combine imitation and reinforcement learning via the idea of reward shaping using an oracle. We study the effectiveness of the nearoptimal cost-to-go oracle on the planning horizon and demonstrate that the costto-go oracle shortens the learner's planning horizon as function of its accuracy: a globally optimal oracle can shorten the planning horizon to one, leading to a onestep greedy Markov Decision Process which is much easier to optimize, while an oracle that is far away from the optimality requires planning over a longer horizon to achieve near-optimal performance. Hence our new insight bridges the gap and interpolates between imitation learning and reinforcement learning. Motivated by the above mentioned insights, we propose Truncated HORizon Policy Search (THOR), a method that focuses on searching for policies that maximize the total reshaped reward over a finite planning horizon when the oracle is sub-optimal. We experimentally demonstrate that a gradient-based implementation of THOR can achieve superior performance compared to RL baselines and IL baselines even when the oracle is sub-optimal.
=== SUMMARY ===
The paper considers a combination of Reinforcement Learning (RL) and Imitation Learning (IL), in the infinite horizon discounted MDP setting.
The IL part is in the form of an oracle that returns a value function V^e, which is an approximation of the optimal value function. The paper defines a new cost (or reward) function based on V^e, through shaping (Eq. 1). It is known that shaping does not change the optimal policy.
A key aspect of this paper is to consider a truncated horizon problem (say horizon k) with the reshaped cost function, instead of an infinite horizon MDP.
For this truncated problem, one can write the (dis)advantage function as a k-step sum of reward plus the value returned by the oracle at the k-th step (cf. Eq. 5).
Theorem 3.3 shows that the value of the optimal policy of the truncated MDP w.r.t. the original MDP is only O(gamma^k eps) worse than the optimal policy of the original problem (gamma is the discount factor and eps is the error between V^e and V*).
This suggests two things: 
1) Having an oracle that is accurate (small eps) leads to good performance. If oracle is the same as the optimal value function, we do not need to plan more than a single step ahead.
2) By planning for k steps ahead, one can decrease the error in the oracle geometrically fast. In the limit of k —> inf, the error in the oracle does not matter.
Based on this insight, the paper suggests an actor-critic-like algorithm called THOR (Truncated HORizon policy search) that minimizes the total cost over a truncated horizon with a modified cost function.
Through a series of experiments on several benchmark problems (inverted pendulum, swimmer, etc.), the paper shows the effect of planning horizon k.
=== EVALUATION & COMMENTS ===
I like the main idea of this paper. The paper is also well-written. But one of the main ideas of this paper (truncating the planning horizon and replacing it with approximation of the optimal value function) is not new and has been studied before, but has not been properly cited and discussed.
There are a few papers that discuss truncated planning. Most closely is the following paper:
Farahmand, Nikovski, Igarashi, and Konaka, “Truncated Approximate Dynamic Programming With Task-Dependent Terminal Value,” AAAI, 2016.
The motivation of AAAI 2016 paper is different from this work. The goal there is to speedup the computation of finite, but large, horizon problem with a truncated horizon planning. The setting there is not the combination of RL and IL, but multi-task RL. An approximation of optimal value function for each task is learned off-line and then used as the terminal cost. 
The important point is that the learned function there plays the same role as the value provided by the oracle V^e in this work. They both are used to shorten the planning horizon. That paper theoretically shows the effect of various error terms, including terms related to the approximation in the planning process (this paper does not do that).
Nonetheless, the resulting algorithms are quite different. The result of this work is an actor-critic type of algorithm. AAAI 2016 paper is an approximate dynamic programming type of algorithm.
There are some other papers that have ideas similar to this work in relation to truncating the horizon. For example, the multi-step lookahead policies and the use of approximate value function as the terminal cost in the following paper:
Bertsekas, “Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC,” European Journal of Control, 2005.
The use of learned value function to truncate the rollout trajectory in a classification-based approximate policy iteration method has been studied by
Gabillon, Lazaric, Ghavamzadeh, and Scherrer, “Classification-based Policy Iteration with a Critic,” ICML, 2011.
Or in the context of Monte Carlo Tree Search planning, the following paper is relevant:
Silver et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, 2016.
Their “value network” has a similar role to V^e. It provides an estimate of the states at the truncated horizon to shorten the planning depth.
Note that even though these aforementioned papers are not about IL, this paper’s stringent requirement of having access to V^e essentially make it similar to those papers.
In short, a significant part of this work’s novelty has been explored before. Even though not being completely novel is totally acceptable, it is important that the paper better position itself compared to the prior art.
Aside this main issue, there are some other comments:
- Theorem 3.1 is not stated clearly and may suggest more than what is actually shown in the proof. The problem is that it is not clear about the fact the choice of eps is not arbitrary.
The proof works only for eps that is larger than 0.5. With the construction of the proof, if eps is smaller than 0.5, there would not be any error, i.e., J(\hat{pi}^*) = J(pi^*).
The theorem basically states that if the error is very large (half of the range of value function), the agent does not not perform well. Is this an interesting case?
- In addition to the papers I mentioned earlier, there are some results suggesting that shorter horizons might be beneficial and/or sufficient under certain conditions. A related work is a theorem in the PhD dissertation of Ng:
Andrew Ng, Shaping and Policy Search in Reinforcement Learning, PhD Dissertation, 2003.
(Theorem 5 in Appendix 3.B: Learning with a smaller horizon).
It is shown that if the error between Phi (equivalent to V^e here) and V* is small, one may choose a discount factor gamma’ that is smaller than gamma of the original MDP, and still have some guarantees. As the discount factor has an interpretation of the effective planning horizon, this result is relevant. The result, however, is not directly comparable to this work as the planning horizon appears implicitly in the form of 1/(1-gamma’) instead of k, but I believe it is worth to mention and possibly compare.
- The IL setting in this work is that an oracle provides V^e, which is the same as (Ross & Bagnell, 2014). I believe this setting is relatively restrictive as in many problems we only have access to (state, action) pairs, or sequence thereof, and not the associated value function. For example, if a human is showing how a robot or a car should move, we do not easily have access to V^e (unless the reward function is known and we estimate the value with rollouts; which requires us having a long trajectory). This is not a deal breaker, and I would not consider this as a weakness of the work, but the paper should be more clear and upfront about this.
- The use of differential operator nabla instead of gradient of a function (a vector field) in Equations (10), (14), (15) is non-standard.
- Figures are difficult to read, as the colors corresponding to confidence regions of different curves are all mixed up. Maybe it is better to use standard error instead of standard deviation.
===
After Rebuttal: Thank you for your answer. The revised paper has been improved. I increase my score accordingly.