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 near- optimal cost-to-go oracle on the planning horizon and demonstrate that the cost- to-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 one- step 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. Reinforcement Learning (RL), equipped with modern deep learning techniques, has dramatically advanced the state-of-the-art in challenging sequential decision problems including high-dimensional robotics control tasks as well as video and board games BID13 BID23 . However, these approaches typically require a large amount of training data and computational resources to succeed. In response to these challenges, researchers have explored strategies for making RL more efficient by leveraging additional information to guide the learning process. Imitation learning (IL) is one such approach. In IL, the learner can reference expert demonstrations BID0 , or can access a cost-to-go oracle BID19 , providing additional information about the long-term effects of learner decisions. Through these strategies, imitation learning lowers sample complexity by reducing random global exploration. For example, BID25 shows that, with access to an optimal expert, imitation learning can exponentially lower sample complexity compared to pure RL approaches. Experimentally, researchers also have demonstrated sample efficiency by leveraging expert demonstrations by adding demonstrations into a replay buffer BID28 BID14 , or mixing the policy gradient with a behavioral cloning-related gradient BID18 .Although imitating experts can speed up the learning process in RL tasks, the performance of the learned policies are generally limited to the performance of the expert, which is often sub-optimal in practice. Previous imitation learning approaches with strong theoretical guarantees such as Data Aggregation (DAgger) BID20 and Aggregation with Values (AGGREVATE) BID19 can only guarantee a policy which performs as well as the expert policy or a one-step deviation improvement over the expert policy.1 Unfortunately , this implies that imitation learning with a sub-optimal expert will often return a sub-optimal policy. Ideally, we want the best of both IL and RL: we want to use the expert to quickly learn a reasonable policy by imitation, while also exploring how to improve upon the expert with RL. This would allow the learner to overcome the sample inefficiencies inherent in a pure RL strategy while also allowing the learner to eventually surpass a potentially sub-optimal expert. Combining RL and IL is, in fact, not new. BID5 attempted to combine IL and RL by stochastically interleaving incremental RL and IL updates. By doing so, the learned policy will either perform as well as the expert policy-the property of IL BID19 , or eventually reach a local optimal policy-the property of policy iteration-based RL approaches. Although, when the expert policy is sub-optimal, the learned locally optimal policy could potentially perform better than the expert policy, it is still difficult to precisely quantify how much the learner can improve over the expert.In this work, we propose a novel way of combining IL and RL through the idea of Reward Shaping BID16 . Throughout our paper we use cost instead of reward, and we refer to the concept of reward shaping with costs as cost shaping. We assume access to a cost-to-go oracle that provides an estimate of expert cost-to-go during training. The key idea is that the cost-to-go oracle can serve as a potential function for cost shaping. For example, consider a task modeled by a Markov Decision Process (MDP). Cost shaping with the cost-to-go oracle produces a new MDP with an optimal policy that is equivalent to the optimal policy of the original MDP BID16 . The idea of cost shaping naturally suggests a strategy for IL: pick a favourite RL algorithm and run it on the new MDP reshaped using expert's cost-to-go oracle. In fact, BID16 demonstrated that running SARSA BID26 on an MDP reshaped with a potential function that approximates the optimal policy's value-to-go, is an effective strategy.We take this idea one step further and study the effectiveness of the cost shaping with the expert's cost-to-go oracle, with a focus on the setting where we only have an imperfect estimatorV e of the cost-to-go of some expert policy π e , i.e.,V e = V * , where V * is the optimal policy's cost-to-go in the original MDP. We show that cost shaping with the cost-to-go oracle shortens the learner's planning horizon as a function of the accuracy of the oracleV e compared to V * . Consider two extremes. On one hand, when we reshape the cost of the original MDP with V * (i.e.,V e = V * ), the reshaped MDP has an effective planning horizon of one: a policy that minimizes the one-step cost of the reshaped MDP is in fact the optimal policy (hence the optimal policy of the original MDP). On the other hand, when the cost-to-go oracle provides no information regarding V * , we have no choice but simply optimize the reshaped MDP (or just the original MDP) using RL over the entire planning horizon.With the above insight, we propose the high-level strategy for combining IL and RL, which we name Truncated HORizon Policy Search with cost-to-go oracle (THOR). The idea is to first shape the cost using the expert's cost-to-go oracleV e , and then truncate the planning horizon of the new MDP and search for a policy that optimizes over the truncated planning horizon. For discrete MDPs, we mathematically formulate this strategy and guarantee that we will find a policy that performs better than the expert with a gap that can be exactly quantified (which is missing in the previous work of BID5 ). In practice, we propose a gradient-based algorithm that is motivated from this insight. The practical algorithm allows us to leverage complex function approximators to represent policies and can be applied to continuous state and action spaces. We verify our approach on several MDPs with continuous state and action spaces and show that THOR can be much more sample efficient than strong RL baselines (we compared to Trust Region Policy Optimization with Generalized Advantage Estimation (TRPO-GAE) ), and can learn a significantly better policy than AGGREVATE (we compared to the policy gradient version of AGGREVATE from BID25 ) with access only to an imperfect cost-to-go oracle. We propose a novel way of combining IL and RL through the idea of cost shaping with an expert oracle. Our theory indicates that cost shaping with the oracle shortens the learner's planning horizon as a function of the accuracy of the oracle compared to the optimal policy's value function. Specifically, when the oracle is the optimal value function, we show that by setting k = 1 reveals previous imitation learning algorithm AGGREVATED. On the other hand, we show that when the oracle is imperfect, using planning horizon k > 1 can learn a policy that outperforms a policy that would been learned by AGGREVATE and AGGREVATED (i.e., k = 1). With this insight, we propose THOR (Truncated HORizon policy search), a gradient based policy search algorithm that explicitly focusing on minimizing the total cost over a finite planning horizon. Our formulation provides a natural half-way point between IL and RL, and experimentally we demonstrate that with a reasonably accurate oracle, our approach can outperform RL and IL baselines. We believe our high-level idea of shaping the cost with the oracle and then focusing on optimizing a shorter planning horizon is not limited to the practical algorithm we proposed in this work. In fact our idea can be combined with other RL techniques such as Deep Deterministic Policy Gradient (DDPG) BID12 , which has an extra potential advantage of storing extra information from the expert such as the offline demonstrations in its replay buffer BID28 ). Though in our experiments, we simply used some expert's demonstrations to pre-trainV e using TD learning, there are other possible ways to learn a more accurateV e . For instance, if an expert is available during training BID20 , one can online updateV e by querying expert's feedback.A PROOF OF THEOREM 3.1 Figure 3 : The special MDP we constructed for theorem 3.1Proof. We prove the theorem by constructing a special MDP shown in Fig 3, where H = ∞. The MDP has deterministic transition, 2H + 2 states, and each state has two actions a 1 and a 2 as shown in Fig. 3 . Every episode starts at state s 0 . For state s i (states on the top line), we have c(s i ) = 0 and for state s i (states at the bottom line) we have c(s i ) = 1.It is clear that for any state s i , we have Q * (s i , a 1 ) = 0, Q * (s i , a 2 ) = γ, Q * (s i , a 1 ) = 1 and Q * (s i , a 2 ) = 1 + γ, for i ≥ 1. Let us assume that we have an oracleV e such thatV e (s i ) = 0.5 + δ and V e (s i ) = 0.5 − δ, for some positive real number δ. Hence we can see that |V e (s) − V * (s)| = 0.5 + δ, for all s. DenoteQ e (s, a) = c(s, a) + γE s ∼Psa [V e (s )], we know thatQ e (s i , a 1 ) = γ(0.5 + δ),Q e (s i , a 2 ) = γ(0.5 − δ),Q e (s i , a 1 ) = 1 + γ(0.5 + δ) andQ e (s i , a 2 ) = 1 + γ(0.5 − δ).It is clear that the optimal policy π * has cost J(π * ) = 0. Now let us compute the cost of the induced policy from oracleQ e :π(s) = arg min aQ e (s, a). As we can seeπ makes a mistake at every state as arg min aQ e (s, a) = arg min a Q * (s, a). Hence we have J(π) = γ 1−γ . Recall that in our constructed example, we have = 0.5 + δ. Now let δ → 0 + (by δ → 0 + we mean δ approaches to zero from the right side), we have → 0.5, hence J(π) = Proof of Theorem 3.2. In this proof, for notation simplicity, we denote V π M0 as V π for any π. Using the definition of value function V π , for any state s 1 ∈ S we have: DISPLAYFORM0
Combining Imitation Learning and Reinforcement Learning to learn to outperform the expert
{"src": "scitldr-AIC_train", "paper_id": "ryUlhzWCZ"}