Sample inefficiency is a long-lasting problem in reinforcement learning (RL).   The state-of-the-art uses action value function to derive policy while it usually involves an extensive search over the state-action space and unstable optimization. Towards the sample-efficient RL, we propose ranking policy gradient (RPG), a policy gradient method that learns the optimal rank of a set of discrete actions.   To accelerate the learning of policy gradient methods, we establish the equivalence between maximizing the lower bound of return and imitating a near-optimal policy without accessing any oracles. These results lead to a general off-policy learning framework, which preserves the optimality, reduces variance, and improves the sample-efficiency. We conduct extensive experiments showing that when consolidating with the off-policy learning framework, RPG substantially reduces the sample complexity, comparing to the state-of-the-art. One of the major challenges in reinforcement learning (RL) is the high sample complexity (Kakade et al., 2003) , which is the number of samples must be collected to conduct successful learning. There are different reasons leading to poor sample efficiency of RL (Yu, 2018) . Because policy gradient algorithms directly optimizing return estimated from rollouts (e.g., REINFORCE (Williams, 1992) ) could suffer from high variance (Sutton & Barto, 2018) , value function baselines were introduced by actor-critic methods to reduce the variance and improve the sample-efficiency. However, since a value function is associated with a certain policy, the samples collected by former policies cannot be readily used without complicated manipulations (Degris et al., 2012) and extensive parameter tuning (Nachum et al., 2017) . Such an on-policy requirement increases the difficulty of sampleefficient learning. On the other hand, off-policy methods, such as one-step Q-learning (Watkins & Dayan, 1992) and variants of deep Q networks (DQN) (Mnih et al., 2015; Hessel et al., 2017; Dabney et al., 2018; Van Hasselt et al., 2016; Schaul et al., 2015) , enjoys the advantage of learning from any trajectory sampled from the same environment (i.e., off-policy learning), are currently among the most sampleefficient algorithms. These algorithms, however, often require extensive searching (Bertsekas & Tsitsiklis, 1996, Chap. 5) over the large state-action space to estimate the optimal action value function. Another deficiency is that, the combination of off-policy learning, bootstrapping, and function approximation, making up what Sutton & Barto (2018) called the "deadly triad", can easily lead to unstable or even divergent learning (Sutton & Barto, 2018, Chap. 11) . These inherent issues limit their sample-efficiency. Towards addressing the aforementioned challenge, we approach the sample-efficient reinforcement learning from a ranking perspective. Instead of estimating optimal action value function, we concentrate on learning optimal rank of actions. The rank of actions depends on the relative action values. As long as the relative action values preserve the same rank of actions as the optimal action values (Q-values), we choose the same optimal action. To learn optimal relative action values, we propose the ranking policy gradient (RPG) that optimizes the actions' rank with respect to the long-term reward by learning the pairwise relationship among actions. Ranking Policy Gradient (RPG) that directly optimizes relative action values to maximize the return is a policy gradient method. The track of off-policy actor-critic methods (Degris et al., 2012; Gu et al., 2016; Wang et al., 2016) have made substantial progress on improving the sample-efficiency of policy gradient. However, the fundamental difficulty of learning stability associated with the bias-variance trade-off remains (Nachum et al., 2017) . In this work, we first exploit the equivalence between RL optimizing the lower bound of return and supervised learning that imitates a specific optimal policy. Build upon this theoretical foundation, we propose a general off-policy learning framework that equips the generalized policy iteration (Sutton & Barto, 2018, Chap. 4) with an external step of supervised learning. The proposed off-policy learning not only enjoys the property of optimality preserving (unbiasedness), but also largely reduces the variance of policy gradient because of its independence of the horizon and reward scale. Besides, we empirically show that there is a trade-off between optimality and sample-efficiency. Last but not least, we demonstrate that the proposed approach, consolidating the RPG with off-policy learning, significantly outperforms the state-of-the-art (Hessel et al., 2017; Bellemare et al., 2017; Dabney et al., 2018; Mnih et al., 2015) . In this work, we introduced ranking policy gradient (RPG) methods that, for the first time, resolve RL problem from a ranking perspective. Furthermore, towards the sample-efficient RL, we propose an off-policy learning framework that allows RL agents to be trained in a supervised learning paradigm. The off-policy learning framework uses generalized policy iteration for exploration and exploit the stableness of supervised learning for policy learning, which accomplishes the unbiasedness, variance reduction, off-policy learning, and sample efficiency at the same time. Last but not least, empirical results show that RPG achieves superior performance as compared to the state-of-the-art. Corollary 3. The pairwise ranking policy as shown in Eq (2) constructs a probability distribution over the set of actions when the action space m is equal to 2, given any relative action values λi, i = 1, 2. For the cases with m > 2, this conclusion does not hold in general. It is easy to verify that π(ai|s) > 0, ∑ 2 i=1 π(ai|s) = 1 holds and the same conclusion cannot be applied to m > 2 by constructing counterexamples. However, we can introduce a dummy action a ′ to form a probability distribution for RPG. During policy learning, the algorithm will increase the probability of best actions and the probability of dummy action will decrease. Ideally, if RPG converges to an optimal deterministic policy, the probability of taking best action is equal to one and π(a ′ |s) = 0. Similarly, we can introduce a dummy trajectory τ ′ with trajectory reward r(τ The trajectory probability forms a probability distribution since The proof of a valid trajectory probability is similar to the following proof on π(a|s) is a valid probability distribution with a dummy action. The practical influence of this is negligible since our goal is to increase the probability of (near)-optimal trajectories. To present in a clear way, we avoid mentioning dummy trajectory τ ′ in Proof 9.2 while it can be seamlessly included. This condition can be easily satisfied since in RPG we only focus on the relative relationship of λ-values and we can constrain its range so that λm satisfies the condition 1. Furthermore, since we can see that m 1 m−1 > 1 is decreasing w.r.t to action dimension m. The larger the action dimension, the less constraint we have on the λ-values. ′ and set π(a = a ′ |s) = 1 − ∑ i π(a = ai|s), which will construct a valid probability distribution (π(a|s)) over the action space A ∪ a ′ . Proof. Since we have π(a = ai|s) > 0 ∀i = 1, ..., m and ∑ i π(a = ai|s) + π(a = a ′ |s) = 1. To prove this is a valid probability distribution, we only need to show that π(a = a ′ |s) ≥ 0, ∀m ≥ 2, i.e. 9.4 LISTWISE POLICY GRADIENT In order to learn the stochastic policy that optimizes the ranking of actions with respect to the return, we now introduce the Listwise Policy Gradient (LPG) method. In RL, we want to optimize the probability of each action (ai) to be ranked higher among all actions, which is the sum of the probabilities of all permutations such that the action ai in the top position of the list. This probability is computationally prohibitive since we need to consider the probability of m! permutations. Luckily, based on Cao et al. (2007) [Theorem 6], we can model the such probability of action ai to be ranked highest given a set of relative action values by a simple softmax formulation, as described in Theorem 3. Theorem 3 (Theorem 6 Cao et al. (2007) where ϕ( * ) is any increasing, strictly positive function. A common choice of ϕ is the exponential function. Closely built upon the foundations from learning to rank Cao et al. (2007) where the listwise ranking policy π θ parameterized by θ is given by Eq (17) for tasks with deterministic optimal policies: a = arg max or Eq (18) is the probability that action i being ranked highest, given the current state and all the relative action values λ1 . . . λm. The proof of Theorem 4 exactly follows the direct policy differentiation Peters & Schaal (2008); Williams (1992) by replacing the policy to the form of the softmax function. The action probability π(ai|s), ∀i = 1, ..., m forms a probability distribution over the set of discrete actions [Cao et al. (2007) Lemma 7] . Theorem 4 states that the vanilla policy gradient Williams (1992) parameterized by a softmax layer is optimizing the probability of each action to be ranked highest, with respect to the long-term reward. Condition 2 If we want to preserve the optimality by TRS, the optimal trajectories of MDP needs to cover all initial states or equivalently, all initial states will lead to at least one optimal trajectory. Similarly, the near-optimality is preserved for all MDPs that its near-optimal trajectories cover all initial states. Theoretically, it is possible to transfer more general MDPs to satisfy Condition 2 and preserve the optimality with potential-based reward shaping Ng et al. (1999) . More concretely, consider the deterministic binary tree MDP (M1) with the set of initial states S1 = {s1, s . This reward shaping requires more prior knowledge, which may not be feasible in practice. A more realistic method is to design a dynamic trajectory reward shaping approach. In the beginning, we set c(s) = mins∈S 1 r(τ |s(τ, 1) = s), ∀s ∈ S1. Take M1 as an example, c(s) = 3, ∀s ∈ S1. During the exploration stage, we track the current best trajectory of each initial state and update c(s) with its trajectory reward. Nevertheless, if the Condition 2 is not satisfied, we need more sophisticated prior knowledge other than a predefined trajectory reward threshold c to construct the replay buffer (training dataset of UNOP). The practical implementation of trajectory reward shaping and rigorously theoretical study for general MDPs are beyond the scope of this work. Under review as a conference paper at ICLR 2020
We propose ranking policy gradient that learns the optimal rank of actions to maximize return. We propose a general off-policy learning framework with the properties of optimality preserving, variance reduction, and sample-efficiency. This paper proposes to reparameterize the policy using a form of ranking to convert the RL problem into a supervised learning problem. This paper presents a new view on policy gradient methods from the perspective of ranking. 