Ranking Policy Gradient
Authors: Kaixiang Lin
Jiayu Zhou
Venue:  (2020)
Keywords: Sample-efficient reinforcement learning
off-policy learning.

Abstract: Sample inefficiency is a long-lasting problem in reinforcement learning (RL). The state-of-the-art estimates the optimal action values 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.

Published as a conference paper at ICLR 2020
RANKING POLICY GRADIENT
Kaixiang Lin
Jiayu Zhou
Department of Computer Science and Engineering Michigan State University East Lansing, MI 48824-4403, USA linkain @msu. edu
Department of Computer Science and Engineering Michigan State University East Lansing, MI 48824-4403, USA j jiayuz@msu.edu
ABSTRACT
Sample inefficiency is long-lasting problem in reinforcement learning (RL). The state-of-the-art estimates the optimal action values while usually involves an extensive search over the state-action space and unstable optimization. Towards the sample-efficiett RL, we propose ranking policy gradient (RPG), a policy gradient method that learns the optimal rank of set of discrete actions. To accelerate the learning of policy gradient methods, we establish the equivalence between maximiz- ing the lower bound of return and imitating a near-optimal policy without accessing any oracles. These results lead to 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- off-policy learning framework, RPG substantially reduces the sample complexity, comparing to the saaee-o-thee-e
INTRODUCTION
One of the major challenges in reinforcement learning (RL) the high sample complexity (akkade
iet 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 value function is associated with a certain policy, the samples collected by former policies cannot readily used without complicated manipulations (Degris et al. [0112 and extensive parameter tuning (Nachum) ct al. 2017). Such an on-policy requirement increases the difficulty of sample-efficient 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.
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 sample- efficient 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 that, the combination of off-policy learning, bootstrapping, and function approximation, making up what Suttonn & Barto (018) 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 cample-efficient reinforcement learning from ranking perspective. Instead of estimating optimal action value function, we concen- trate on learning optimal rank of actions. The rank of actions depends on the relative action values. As long the relative action values preserve the same rank of actions 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 maximize the return is a policy gradient method. The track of off ooolccy actor-critic methods (Degris et al.) 2012 Gu et al. 2016: Wang et al. 2016) have made substantial progress on improving the sample-efficiency

---

Published as a conference paper at ICLR 2020
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 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 off-policy learning, significantly outperforms the state-of-the-ar (Hessel et al. 2017: Bellemare et al. 2017 Dabney et al. 2018 Mnih et al., 2015).
2 RELATED WORKS
Sample Efficiency. The sample efficient reinforcement learning can be roughly divided into two categories. The first category includes variants of Q-learning (Mnih et al. 2015) Schaul et al. 20115 Van Hasselt et al. [016]] (Hessel et al. (017). The main advantage of Q-learning methods is the use of
off-policy learning, which is essential towards sample efficiency. The representative DQN (Mnih et al.
2015) introduced deep neural network in Q-learning, which further inspried a track of successful
DQN variants such as Double DQN (Van Hasselt et al. 2016), Dueling networks (Wang et al. 2013)
prioritized experience replay (Schaul et al. 2013). and RAINBOW (Hessel al. 2017). The second
category is the actor-critte approaches. Most of recent works (Degnis et al.) 2012) Wang et al. 2016]
Gruslys et al., 2018) in this category leverage importance sampling by re- weighting the samples to correct the estimation bias and reduce variance. Its main advantage is in the wall-clock times due to the distributed framework, firstly presented in (Mnih et al.) 2016), instead of the sample-efficiene As of the time of writing, the variants of DQN (Hessel et al. 2017 Dabney et al. [018 Bellemare jet al. 2017 7 Schaul et al.) 2015; Van Hasselt et (0116) are among the algorithms of most sample efficiency, which are adopted as baselines for comparison.
RL as supervised learning. Numerous amount of works have developed the connections between RL and supervised learning such as Expectation Expectation-Maxiiizz Maximization algorithms (Dayan & Hinton Peters
& Schaal [2007] Kober& & Peters 2009: Abdolmaleki et al., 2018), Entrooy-Reeularizee RL (Oh
et al. [2088] Haarnoja et al.[ 2018). and Interactive Imitation Learning (III.) (Daumé et al.] 2009
Syed & Schapire, 2010; Ross & Bagnell 2010; Ross et al. 2011 Sun et al. [017] Hester et al.
2018 Osa et al. 2018). EM-based approaches utilize the probabilistic framework to transfer RL maximizing lower bound of return as re- re-weighted regression problem while it requires on-policy estimation on the expectation step.
RL optimizing entropy augmented objectives can lead to off-policy learning without the usage of importance sampling while it converges to soft optimality (Haarnoja et al. 2018).
Of the three tracks in prior works, the III. is most closely related to our work. The III. works firstly pointed out the connection between imitation learning and reinforcement learning (Ross& & Bagnell 2010: Syed & Schapire| 2010; Ross et al., 2011) and explore the idea of facilitating reinforcement learning by imitating experts. However, most of imitation learning algorithms assume the access to the expert policy demonstrations. Our off- off-policy learning framework can be interpreted as an online imitation learning approach that constructs expert demonstrations during the exploration without soliciting experts, and conducts supervised learning maximize return at the same time.
In conclusion, our approach is different from the prior work in terms of at least one of the following aspects: objectives, oracle assumptions, the optimality of learned policy, and on-policy requirement. More coneretely, the proposed method is able to learn both deterministic and stochastic optimal policy in terms of long-term reward, without access to the oracle (such as expert policy or expert demonstration) and it can be trained both empirically and theoretically in an off-policy fashion. Due to the space limits, we defer the detailed discussion of the related work in the Appendix Section 10.1
3 NOTATIONS AND PROBLEM SETTING
In this paper, we consider finite horizon T. discrete time Markov Decision Process (MDP) with finite discrete state space S and for each state s E S, the action space A₂ is finite. The environment dynamics is denoted
P {p(s/ s'Is,,,, a), Ys, E S.a a A, }. We note that the dimension of action space can vary given different states. We use m = max, |A,|| to denote the maximal action dimension among all possible states. Our goal is to maximize the expected sum of rewards, or return
2

---

Published as a conference paper at ICLR 2020
J(Ø) = E,,,o Ei= r(st de)l, where (r(s.a) a)] 0o, Vs,a. In this case, the optimal deterministic Markovian policy always exists (Puterman (2014) Propossiionn 4.4.3]. The upper bound of trajectory reward (r(T)) is denoted as Rmax max, T(T). A comprchensive list of notations are elaborated in the Appendix Table
4 RANKING POLICY GRADIENT
Value function estimation is widely used in advanced RL algorithms (Mnih et al. 2015 2016
Schulman et al. 2017 Gruslys et al. 2018 Hessel et al., 2017: Dabney et al. (0188) 8) to facilitate
the learning process. In practice, the on on-policy requirement of value function estimations in actor- critic methods has largely increased the difficulty of sample-efficient learning (Degris et al. 2012
Cruslys et al., 2018). With the advantage of off-policy learning, the DQN (Mnih et al. 2015) variants are currently among the most sample-efficiet algorithms (Hessel et al. 2017] Dabney et al.
2018: Bellemare et al.) 2017). For complicated tasks, the value function can align with the relative relationship of action's s return, but the absolute values are hardly accurate (Mnih et al. 2015 llyas
ct al. 2018).
The above observations motivate us look the decision phase of RL from different prospect: Given a state, the decision making is to perform a relative comparison over available actions and then choose the best action, which can lead to relatively higher return than others. Therefore, an alternative solution is to learn the optimal rank of the actions. In this section, we show how to optimize the rank of actions to maximize the return, and thus avoid the necessity of accurate estimation for optimal action value function. To learn the rank of actions, we focus on learning relative action value (A-values), defined as follows:
Definition (Relative action value (A-values)). For a state s, the relative action values of m actions (M(s, ax), ) k = L..... m.) is a list of scores that denotes the rank of actions. If X(s, a,) > Mss.;), then action a; is ranked higher than action aj-
The optimal relative action values should preserve the same optimal action as the optimal action values:
arg max X(s, a) arg max (s,
where QT (s, (z) and X(s, az) represent the optimal action value and the relative action value of action a,, respectively. We omit the model parameter 0 in Aø(s, a;) for concise presentation.
Remark 1. The A-values are different from the advantage function (s, (* (s)... The advantage functions quantitatively show the difference of return taking different actions following the current policy æ. The X-values only determine the relative order of actions and its magnitudes are not the estimations of returns.
To learn the v-valu, we can construct probabilistic model of X-values such that the best action has the highest probability to be selected than others. Inspired by learning to rank (Burges et al. (200)). we consider the pairwise relationship among all actions, by modeling the probability (denoted p:j) of an action to be ranked higher than any action aj follows:
exp(A(s, a.) X(s,a,))
Pi 1+ exp(A(s,a)) - A(s, az))
where Pt, = 0.5 means the relative action value of a; is same as that the action aj. P;j > 0.5 indicates that the action a; is ranked higher than aj. Given the independent Assumption T we can represent the probability of selecting one action as the multiplication of a set of pairwise probabilities in Eq (T). Formally, define the pairwise ranking policy in Eq (2). Please refer Section 10.10 in the Appendix for the discussions on feasibility of Assumption
Definition 2. The pairwise ranking policy is defined as:
T(a = a,ls) 11
(2)
where the Pig is defined in Eq 7 The probability depends the relative action values [Ai,.., Am). The highest relative action value leads to the highest probability to be selected.
3

---

Published as a conference paper at ICLR 2020
Assumption 1. For state the of events E = (eiglVi + j} are conditionally independent, where Eij denotes the event that action a; is ranked higher than action aj. The independence of the events is conditioned on a MDP and a stationary policy.
Our ultimate goal is maximize the long-term reward through optimizing the pairwise ranking policy or equivalently optimizing pairwise relationship among the action pairs. Ideally, we would like the pairwise ranking policy selects the best action with the highest probability and the highest X-value. To achieve this goal, we resort to the policy gradient method. Formally, we propose the ranking policy gradient method (RPG), as shown Theorem !
Theorem (Ranking Policy Gradient Theorem). For any MDP, the gradient of the expected long- term reward J (0) Σ. (T)r((T w.r.t. the parameter 0 of a pairwise ranking policy (Deff2 2) can be approximated by:
VoJ(O) = F E
Σ V Σ
T
j j= (A: - 2y)/2) r(T)
(3)
and the deterministic pairwise ranking policy Ty is: a = arg max; Ais i = 1,..., m. where X; denotes the relative action value of action a; (Ag(st, at), a; = ar). 8, and 04 denotes the t-th state- action pair in trajectory T, >j, Vj + denote the relative action values of all other actions that were not laken given state St in trajectory T, i.e,, A0(SE, az), Vaj j 0r.
The proof of Theorem is available in Appendix Section 10.2 Theorem I states that optimizing the discrepancy between the relative action values of the best action and all other actions, is optimizing the pairwise relationships that maximize the return. One limitation of RPG is that it is not convenient for the tasks where only optimal stochastic policies exist since the pairwise ranking policy takes extra efforts to construct probability distribution [see Section 10.3 in Appendix]. In order to learn the stochastic policy, we introduce Listwise Policy Gradient (LPG) that optimizes the probability of ranking a specific action on the top of set of actions, with respect to the return. In the context of RL, this top one probability is the probability of action to be chosen, which is equal to the sum of probability all possible permutations that map action a, in the top. Inspired by listwise learning to rank approach (Cao et al., 2007), the top one probability can be modeled by the softmax function. Therefore, I.PG is equivalent to the REINFORCE (Williams) 1992) algorithm with a softmax layer. LPG provides another interpretation of REINFORCE algorithm from the perspective of learning the optimal ranking and enables the learning of both deterministic policy and stochastic policy. Due to the space limit, we defer the detailed description of LPG in Appendix Section 10.4
To this end, seeking sample-efficenng motivates us to learn the relative relationship (RPG (Theorem I and LPG (Theorem (4) of actions, instead of seeking accurate estimation of optimal action values and then choosing action greedily. However, both of the RPG and LPG belong to policy gradient methods, which suffers from large variance and the on-policy learning requirement (Sutton & Barto 2018). Therefore, the direct implementation of RPG or I.G is still far from sample-efficient In the next section, we will describe general off-policy learning framework empowered by supervised learning, which provides an alternative way to accelerate learning, preserve optimality, and reduce variance.
OFF-POLICY LEARNING AS SUPERVISED LEARNING
In this section, we discuss the connections and discrepancies between RL and supervised learning, and our results lead to sample-efficiens off- policy learning paradigm for RL. The main result in this section is Theorem which casts the problem of maximizing the lower bound of return into a supervised learning problem, given one relatively mild Assumption 2 and practical Assumptions 1 As we show by Lemma 4 in the Appendix that assumptions are valid a range RL. tasks. The central idea is to collect only the near-optimal trajectories when the learning agent interacts with the environment, and imitate the opar-optimal policy by maximizing the log likelihood of the state-action pairs from near-optimal trajectories. With the road map in mind, then begin introduce approach as follows.
In discrete action MDP with finite states and horizon, given the near-optimal policy T.. the stationary state distribution is given by: Pr. (s) = Σ p(s[T)p.. (7), where p(s(T) is the probability of a certain state given specific trajectory and is not associated with any policies, and only
4

---

Published as a conference paper at ICLR 2020
Pr. (T) is related to the policy parameters. The stationary distribution of state-action pairs is thus: Pr. (s,a) = Px. (a)s). In this section, we consider the MDP that each initial state will lead to at least one (near)- trajectory. For more general case, please refer to the discussion in Appendix 10.5] In order to connect supervised learning (i.e., imitating a near-optimal policy) with RL and enable sample-efficiet off-policy learning, first introduce the trajectory reward shaping (TRS), defined as follows:
Definition 3 (Trajectory Reward Shaping, TRS). Given a fixed trajectory T, its trajectory reward is shaped as follows:
w(T)= = { 1, if((T) 2 O, o.w.
where c c= -Rmax- - is problem-dependemt near-optimal trajectory reward threshold that indicates the least reward of neur-optimal trajectory, 2 0 and e < Rmaxe We denote the set of all possible retirolptmaal trajectories as T = [T [T] = 1}, i.e., =
The threshold c indicates a trade-off between the The higher the threshold, the less frequently it will hit the near-optimal trajectories during exploration, which means it has higher sample complexity, while the final performance is better (see FigureB).
Remark 2.
and the optimality.
Remark 3. The trajectory reward can be reshaped to any positive functions that are not related to policy parameter 0. For example, if we set w(T) r(T), the conclusions in this section still hold (see Eq 38 in Appendix, Section 10.6. For the sake of simplicity, we set w(T) = 1.
Different from the reward shaping works (gg et al. 1999), we directly shape the trajectory reward, which will enable the smooth transform from RL SL. After shaping the trajectory reward, we can transfer the goal of RL from maximizing the return to maximize the long-term performance (Def
Definition 4 (Long-term Performance).
Σ, Po(F))((T)
(4)
The long-term performance is the expected shaped trajectory reward, as shown in Eq 44 By Def 3 the expectation over all trajectories is the equal to that over the near-optimal trajectories in T, i.e. Σ, (T) ΣreT (T)
The optimality preserved after trajectory reward shaping (c 0. Rmaxx since the opti- mal policy maximizing long-term performance is also an optimal policy for original MDP. i.e. Σ, Pr. (T)r(T) = ErET Px, (T)r(T) = Rmax, where म. arg max ne Σ, Prv (T)W(T) and Ps. (T) = 0, VT $ T (see Lemma 2 in Appendix 10.6). Similarly, when e >> the optimal policy after trajectory reward shaping is near-optimal policy for original MDP. Note that most policy gradient methods use softmax function, in which we have Er & .Pro (T) > (see Lemma 3 in Appendix T0.6). Therefore when softmax is used to model policy. it will not converge to an exact optimal policy. On the other hand, ideally, the discrepancy of the performance between them can be arbitrarily small based on the universal approximation (Hornik et al. 1989) with general conditions on the activation function and Theorem 1. in (Syed& & Schapire 2010).
Essentially, we use TRS to filter out near-optimal trajectories and then we maximize the probabilities of near-optimal trajectories to maximize the long-term performance. This procedure can be approx- imated by maximizing the log- likelihood of near-optimal state-action pairs, which is supervised learning problem. Before we state our main results, we first introduce the definition of uniformly near-optimal policy 5 and a prerequisite (Asm. 2 specifying the applicability of the results.
Definition 5 (Uniformly Near-Optimal Policy, UNOP). The Uniformly Near-Optimal Policy n. is the policy whose probability distribution over near-optimal trajectories (T) is a uniform distribution. | VT E T, where [T] is the number of near-optimal trajectories. When we set c c= Rmaxo it is an optimal policy in terms of both maximizing return and long-term performance. In the case of c Rmax the corresponding uniform policy is an optimal policy, we denote this type of optimal policy as uniformly optimal policy (UOP).
i.e. (T)
Assumption 2 (Existence of Uniformly Near-Optimal Policy). We assume the existence of Uniformly Near-Optimet Policy (Def5) 5
5

---

Published as a conference paper at ICLR 2020
Assumption 2 is satisfied for certain MDPs that have deterministic dynamics. Other than Assumption 2 all other assumptions in this work (Assump- tions B can almost always be satisfied in practice, based on empirical observation. With these relatively mild assumptions, we present the following long-term performance theorem, which shows the close connection between supervised learning and RI..
Based on Lemma 4 in Appendix Section 10.9
Theorem (Long-term Performance Theorem). Maximizing the lower bound of expected long-term performance (Eq ( is maximizing the log- agglikelihood of state-action pairs sampled from an uniformly (near)- policy Te, which is a supervised learning problem:
arg max Σ Pr. (3, (5,()) log To (als)
(5)
The optimal policy of maximizing the lower bound also the optimal policy of maximizing the Long-termpp performance and the return.
Remark 4. It is worth noting that Theorem 2 does not require uniformly near-optimal policy Ra to be deterministic. The only requirement is the existence of uniformly near-optimal policy.
Remark 5. Maximizing the lower bound of long-term performance of long-term reward since we can set w(T) r(T) and E-po(T)((7 " ET {. An optimal policy of muximizing this lower bound also an optimal policy of maximizing the long-term
maximize the lower bound
performance when e = Remaxo thus maximizing the return.
The proof of Theorem 2 can be found in Appendix, Section 10.6 Theorem 2 indicates that we break the dependency between current policy my and the environment dynamics, which means off off-policy learning is able to be conducted by the above supervised learning approach. Furthermore, we point out that there is potential discrepancy between imitating UNOP by maximizing log likelihood (even when the optimal policy's 's samples given) and the reinforcement learning since we maximizing a lower bound of expected long-term performance (or equivalently the return over the near-optimal trajectories only) instead of return over all trajectories. In practice, the state-action pairs from an optimal policy is hard to construct while the uniform characteristic of UNOP can alleviate this issue (see Sec Towards sample-efficient RI,, apply Theorem 2 to RPG, which reduces the ranking policy gradient to a classification problem by Corollary []
Corollary (Ranking performance policy gradient). Optimizing the lower bound of expected long-
term performance (defined in Eq (74) using pairwise ranking policy (Eq (2)) can be approximately optimized by the following loss:
min E.., Pr. (s. a:)
(En max(0, margin X(s,a)) -(ss)))((s.
(6)
s,a;
where margin is a small positive value. We set margin equal to one in our experiments.
The proof of Corollary [ can be found in Appendix, section 10.7 Similarly, we can reduce LPG to classification problem (see Appendix 10.7.I). One advantage of casting RL to SL is variance reduction. With the proposed off-policy supervised learning, we can reduce the upper bound of the policy gradient variance, shown in the Corollary 2 Before introducing the variance reduction results, we first make the following standard assumption similar to (Degris et al.] 2012] A1). Furthermore, the assumption is guaranteed for bounded continuously differentiable policy such as softmax function.
Assumption 3. We assume the maximum norm of policy gradient is finite, i.e.
3C < oo, s.t. || log [o(ss))l S &C
Corollary 2 (Policy gradient variance reduction). The upper bound of the variance of each dimension of policy gradient C M²). The upper bound of gradient variance of maximizing the lower bound of long-term performance Eq (5) is O where C is the maximum norm of log gradient based on Assumption 3 M is the maximum absolute value of trajectory reward (i.e., M Z |r(T)], VT), and T is the horizon. The upper bound of gradient variance by supervised learning compared that of the regular policy gradient is reduced by an order of (T2 (T²M² given M 1,T > 1, which is a very common situation in practice, and stationary policy.

---

Published as a conference paper at ICLR 2020
Policy evelustion &
Fosile dharpss aptriisttt
Exploration handlan for Eaptatioon
n
Policy inprovement gredy())
pygiztoree Nequenty
He estima
Time
Exploitation
(Near)-Optimal Trajectories More sumplic bokler gereralaatb
Gasneegg do UNOP pulicy
Inirae drouph sapervoud lomning nooe
Appescinues
Stats-action distribution
from UNOP
UNOP Xt"
Figure 1: The off-policy learning as supervised learning framework for general policy gradient methods.
The proof of Corollary 2 can be found in Appendix T0.8] This corollary shows that the variance of regular policy gradient upper-bounded by the square of time horizon and the maximum trajectory reward. It is aligned with our intuition and empirical observation: the longer the horizon the harder the learning. Also, the common reward shaping tricks such as truncating the reward [-1, (Castro et al.] 2018) can help the learning since it reduces variance by decreasing the range of trajectory reward. long-time horizon into the exploration phase, which is an inevitable issue for all RL algorithms,, and we drop the dependence on 7 and M for policy variance. Thus, it is more stable and efficient to train the policy using supervised learning. One potential limitation of this method is that the trajectory reward threshold e is task-specific, which many applications such as Dialogue
With supervised learning, we concentrate the difficulty
is crucial to the final performance and sample-efficiency. system (Li al., 2017), recommender system (Melville & Sindhwani 2011), etc., we design the reward function to guide the learning process, in which e is naturally known. For the cases that we have no prior knowledge on the reward function of MDP, we treat
tuning parameter to balance the optimality and efficiency, as we empirically verified in Figure 3 The major theoretical uncertainty on general tasks the existence of a uniformly near-optimal policy, which negligible to the empirical performance. The rigorous theoretical analysis of this problem is beyond the scope of this work.
AN ALGORIHHMIC FRAMEWORK FOR OFF-POLICY LEARNING
Based on the discussions in Section 5 exploit the advantage of reducing RL into supervised learning via a proposed two-stages off off-policy learning framework. As we illustrated in Figure [ the proposed framework contains the following two stages:
Generalized Policy Iteration for Exploration. The goal of the exploration stage is to collect different near-optimal trajectories as frequently as possible. Under the off off-policy framework, the exploration agent and the learning agent can be separated. Therefore, any existing RL algorithm can be used during the exploration. The principle of this framework is using the most advanced RL agents as an exploration strategy in order to collect more near-optimal trajectories and leave the policy learning to the supervision stage.
Supervision. In this stage, we imitate the uniformly near-optimal policy, UNOP (Det Although we have no access to the UNOP, we can approximate the state-action distribution from UNOP by collecting the near-optimal trajectories only. The vetr-optimal samples are constructed online and we are not given any expert demonstration or expert policy beforehand. This step provides sample-efficient approach to conduct exploitation, which enjoys the superiority of stability (Figure 2 variance reduction (Corollary ( and optimality preserving (Theorem 2
The two-stage algorithmic framework can be directly incorporated in RPG and LPG to improve sample efficiency. The implementation of RPG is given in Algorithm]] [ and LPG follows the same procedure except for the difference in the loss function. The main requirement of Alg. [ is on the exploration efficiency and the MDP structure. During the exploration stage, a sufficient amount of the different near-optimal trajectories need to be collected for constructing a representative supervised learning training dataset. Theoretically, this requirement always holds [see Appendix Section [0.9 Lemma 5). while the number of episodes explored could be prohibitively large, which makes this
7

---

Published as a conference paper at ICLR 2020
algorithm sample-inefficiee inefficient. This could be practical concern of the proposed algorithm. However, according to our extensive empirical observations, we notice that long before the value function based state-of-the- of-the-art converges to near-optimal performance, enough amount of near-optimal trajectories are already explored.
Therefore, we point out that instead of estimating optimal action value functions and then choosing action greedily, using value function to facilitate the exploration and imitating UNOP is a more sample-efficient approach. As illustrated in Figure [] value based methods with off-policy learning. bootstrapping, and function approximation could lead to a divergent optimization (Sutton & Barto 2018 Chap. 11). In contrast to resolving the instability, we circumvent this issue via constructing a stationary target using the samples from (near) opptimal trajectories, and perform imitation learning. This two-stage approach can avoid the extensive exploration of the suboptimal state-action space and reduce the substantial number of samples needed for estimating optimal action values. In the MDP where we have a high probability of hitting the near-optimal trajectories (such as PONG), the supervision stage can further facilitate the exploration. It should be emphasized that our work focuses on improving the sample-efficiency through more effective exploitation, rather than developing novel exploration method. Please refer to the Appendix Section 10.1] for more discussion exploration efficiency.
7 EXPERIMENTAL RESULTS
Pitfall
Bowling
KPG
10
-1.0
DCM
-100
-200
0.2
Steps (Millions)
3.8
0.8
Steps (Millins)
2.5
0.8
Steps (Millions)
25
Breakout
Dankllalst
DoubleDunk
400
1200
CRS
20
250
200
200
Ransow
200
-20
Steps (Millions)
Stupa (Millions)
Steps (Million))
Robotank
Boxing
Pang
20
40
mc
-30
C3L
CC)
-20
St.
(Million))
12 14
Steps (Million)
Steps [Milliens)
The training curves of the proposed RPG and state-of -he-thterrrtttrr All results are averaged over random seeds from 1 to 5. The r-axis represents the number of steps interacting with the environment (we update the model every four steps) and the y-axis represents the averaged training episodic return. The error bars are plotted with a confidence interval of 95%.
Figure 2:
To evaluate the sample-efficiency of Ranking Policy Gradient (RPG), we focus on Atari 2600 games in OpenAl gym Bellemare et al. (2013); [Brocmman et al. (0016), without randomly repeating the previous action. We compare our method with the state-of of-the-art basclines including DQN Mnih al. (2015), C51 Bellemare et al. (2017). Dabney et al. 20118). RAINBOW Hessel al. 20117). and self-imitation learning (SIL) et al. (2018). For reproducibility, we use the implementation provided Dopamine framework Castro et al. (2018) for all baselines and proposed methods, except
8

---

Published as a conference paper at ICLR 2020
for SIL using the official implementation Following the standard evaluation protocol Oh al. (2018); Hessel et al. (2017): Dabney et al. 2018); Bellemare et al. (2017), we report the training performance of all baselines as the increase of interactions with the environment, or proportionally the number of training iterations. We run the algorithms with five random seeds and report the average rewards with 95% confidence intervals. The implementation details of the proposed RPG and its variants are given as follows
EPG: EPG is the stochastic listwise policy gradient (see Appendix Eq (18) incorporated with the proposed off-policy learning. More concretely, we apply trajectory reward shaping (TRS, Def to all trajectories encountered during exploration and train vanilla policy gradient using the off- samples. This is equivalent to minimizing the cross-entropy loss (see Appendix Eq (69) over the near-optimal trajectories.
LPG is the deterministic listwise policy gradient with the proposed off- off-policy learning. The only difference between EPG and LPG that LPG chooses action deterministically (see Appendix Eq (17)
LPG:
during evaluation.
RPG: RPG explores the environment using a separate EPG agent PONG and IQN other games. Then RPG conducts supervised learning by minimizing the hinge loss Eq (6). It is worth noting that the exploration agent (EPG or IQN) can be replaced by any existing exploration method. In our RPG implementation, we collect all trajectories with the trajectory reward no less than the threshold e without eliminating the duplicated trajectories and we empirically found it is reasonable simplification. More details of hyperparameters are provided in the Appendix Section TO.12
Sample-efficinney: As the results shown in Figure 2 our approach, RPG, significantly outperform all tasks. Furthermore, RPG not
the state-offie of-the-art baselines in terms of sample-efficiene only achieved the most sample-efficient results, but also reached the highest final performance at ROBOTANK, DOUBLEDUNK, PITFALL., and PONG, comparing to any model-free state-of-the-art. In reinforcement learning, the stability of algorithm should be emphasized as an important issue. As we can see from the results, the performance of baselines varies from task task. There is no single baseline consistently outperforms others. In contrast, due to the reduction from RL to supervised learning, RPG is consistently stable and effective across different environments. In addition to the stability and efficiency, RPG enjoys simplicity at the same time. In the environment PONG, it is surprising that RPG without any complicated exploration method largely surpassed the sophisticated value-function based approaches.
7.1 ABLATION STUDY
The effectiveness of pairwise ranking policy and off-policy learning as supervised learning. To get a better understanding of the underlying reasons that RPG is more sample-effccinnt than DQN variants, we performed ablation studies in the PONG environment by varying the combination of policy functions with the proposed off-policy learning. The results of EPG, LPG, and RPG are shown in the bottom right, Figure 2, Recall that EPG and LPG use listwise policy gradient (vanilla policy gradient using softmax as policy function) conduct exploration, the off- off-policy learning minimizes the cross-entropy loss Eq (69) In contrast, RPG shares the same exploration method as EPG and IPG while uses pairwise ranking policy Eq ( in off off-policy learning that minimizes hinge loss Eq (6). We can see that RPG is more sample-efficient than EPG/LPG. We also compared the most advanced on-policy method Proximal Policy Optimization (PPO) Schulman et al. (2017) with EPG, LPG, and RPG. The proposed off-polic learning largely surpassed the best on on-policy method. Therefore, substantially,
conclude that off-policy as supervised learning contributes to the sample-efficienee while pairwise ranking policy can further accelerate the learning. In addition, we compare RPG to off-policy policy gradient approaches: ACER Wang et al. (2016) and self-imitation learning Oh et al. (2018). As the results shown, the proposed off-policy learning framework is more sample-efficient than the sfate-of-the-ad off-policy policy gradient approaches.
The eedimallity-fflfiiiene trade-off. As reported in Figure 3 we empirically demonstrated the trade-off between the sample-efficiency and optimality, which is controlled by the trajectory reward threshold (as defined in Def The higher value of trajectory reward threshold suggests we
Code available at httt:://tthuuh.cm///lllaaaaaaagn

---

Published as a conference paper at ICLR 2020
Breakout
Bankifeist
DoubleBunk
300
2200
100
APCO
&PG-L148
20
6.00
Stups (Million)
Staps (Millions)
Staps (Millions)
Figure 3: The trade-off between sample efficiency and optimality on DOUBLEDUNK, BREAKOUT, BANKHEIST. As the trajectory reward threshold (c) increase, more samples are needed for the learning converge, while leads to better final performance. We denote the value by the numbers at the end of legends.
have higher requirement defining near-optimal trajectory. This will increase the difficulty of collecting near-optimal samples during exploration, while it ensures a better final performance. These experimental results also justified that RPG also effective in the absence of prior knowledge on trajectory reward threshold, with a mild cost on introducing an additional tuning parameter.
8 CONCLUSIONS
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, propose an off-policy learning framework that allows RL agents to be trained in a supervised learning paradigm. The off- 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 the same time. Last but not least, empirical results show that RPG achieves superior performance compared to the state-of-the-an
ACKNOWLEDGEMENT
The authors would like to thank Yuan Liang, Qiaozi Gao, Rundong Zhao, Shaohua Yang, Qi Wang, Boyang Liu, Juanyuan Hong, and Mengying Sun for proofreading the earlier version of this manuscript and gave helpful suggestions the writing. This material based in part upon work supported by the National Science Foundation (NSF) I14-1749940, 161-16,, and the Office of Naval Research (ONR) N00014-17-1-2265.
REFERENCES
Abbas Abdolmalcki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum posteriori policy optimisation. arXiv preprint arXi::1806.06920, 2018.
Marc Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents, Journal of Artificial Intelligence Research, 47:253- 279, 2013.
Marc Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. arXiv preprint (txXxx::77.0000 06887, 2017.
Dimitri Bertsekas and John Tsitsiklis. Neuro-dynamic programming, volume Athena Scientific Belmont, MA, 1996.
Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech 7aremba. Openai gym. arXiv preprint arXiv:1606.00 01500, 2016.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, pp. 89 99-96. ACM, 2005.
Zhe Cao, Tao Qin, Yan Liu, Ming-Feng Tsai, and Hang Li. Learning rank: from pairwise approach to listwise approach. In ICML, pp. 129-136. ACM, 2007.
10

---

Published as a conference paper at ICLR 2020
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Mare G. Bellemare. Dopamine: research framework for deep reinforcement learning. CoRR, abs/1812.06110, 2018. URttt:////arxi
org/abs/ /tt.b////822...66 06110
Will Dabney. Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. arXiv preprint (8X.:0800006693 2018.
Hal Daumé, John Langford, and Daniel Marcu. Search-based structured prediction. Machine learning, 75(3):
297-325, 2009.
Peter Dayan and Geoffrey E Hinton. Using expectation-maxiiizaiiio for reinforcement learning, Neural Computation, 9(2):771-276 1997.
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. arXiv preprint arXiv: 4205.8839 2012.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman. Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https://githui com/ openai /basslineseeeee 2017.
Benjamin Eysenbach and Sergey Levine. If maxent is the answer, what is the question? arXiv preprint arXiv:/9/0001913, 2019.
Audrunas Gruslys, Will Dabney, Mohammad Gheshlaghi Azar, Bilal Piot, Mare Bellemare, and Remi Munos. The reactor: A fast and sample-efficient actor-critic agent for reinforcement learning. 2018.
Shixiang Gu, Timothy Lillicrap. Zoubin Ghahramani, Richard Turner. Sergey Levine. Q-prop: Sample- efficient policy gradient with an off off-policy critic. arXiv preprini 1rXiv:1611.02247, 2016.
Tuomas Haaroja,, Aurick Zhou, Pieter Abheel, and Sergey Levine. Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with stochastic actor. International Conference on Machine Learning, pp. 1856-1865, 2018.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforvement 2017.
learning. arXiv preprint 1rXiv:1710.000
Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep q-learning from demonstrations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Andrew Ilyas, Logan Engstrom, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry, Are deep policy gradient algorithms truly policy gradient algorithms? arXiv preprint arXiv: 1.02533, 2018.
Sham Machandranath Kakade al. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Jens Kober and Jan Peters. Policy search for motor primitives in robotics. In Advances neural information processing systems, pp. 049-856, 2009.
Xiujun Li. Yun-Nung Chen, Lihong Li. Jianfeng Gao, and Asli Celikyilmaz. End-to-end task-completion neural dialogue systems. arXiv preprint vrXiv:1703.01000 2017.
Prem Melville and Vikas Sindhwani. Recommender systems. In Encyclopedia of machine learning, pp. 829-838. Springer, 2011.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu. Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Volodymyr Maih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver. and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. Safe and efficient off aff-policy reinforce- ment learning. In Advances Neural Information Processing Systems, pp. 1054-1062, 2016.

---

Published as a conference paper at ICLR 2020
Ofir Nachum, Mohammad Norouzi. Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement leamiing Advances Neural Information Processing Systems, pp. 2775 2785, 2017.
Andrew Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICMI, volume 99, pp. 278-287, 1999.
Brendan O'Donoguue. Variational bayesian reinforcement learning with regret bounds. arXiv preprint MwXiv:/807009641 2018.
Brendan O' O'Donoghue, Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. Combining policy gradient and q-learning. arXiv preprint arXiv:1611.01626. 2016.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. arXiv:1806. 05635, 2018.
arXiv preprint
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et An
algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 7(1-2)11-19, 2018.
Jan Peters and Stefan Schaal. Reinforcement learning by reward weight-weighted regression for operational space control. In Proceedings of the 24th international conference on Machine learning, 745-750. ACM, 2007.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural networks, 21 (4):682-697, 2008.
Martin L Puterman. Markov decision processex: discrete stochaxtic dynamic programming. John Wiley & Sons, 2014.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings the thirteenth international conference on artificial intelligence and statistics, pp. 661-668. 2010.
Stephane Ross and Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint 1406. 5979, 2014.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, 2011.
Tom Schaul, John Quan. Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:/511.05952,00 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 4rXiv:1707.06347, 2017.
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):354, 2017.
Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell, Deeply aggrevated: Differentiahle imitation learning for sequential prediction. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3309-3318. JMLR. org, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Umar Syed and Robert E Schapire. reduction from apprenticeship learning classification. In Advances Neural Information Processing Systems, pp. 2253-2261, 2010.
Ahmed Touati, Pierre-Luc Bacon, Doina Precup, and Pascal Vincent. Convergent tree-backup and retrace with function approximation. arXiv preprint arXiv: 2017.
Leslie G Valiant. A theory of the learnable. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 236-445, ACM, 1984.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-lcarning. In AAAI, volume pp. 5. Phoenix, AZ, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanetot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 151 2015.
12

---

Published as a conference paper at ICLR 2020
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay, arXiv preprint 161..v::61110220 2016.
Christopher JCH Watkins and Peter Dayan. Q-learnigg Machine learning, 8(3-4):279-22)) 292, 1992.
Ronald J Williams. Simple statistical gradient-fllowing algorithms for connectionist reinforcement learning. Machine learning, 2(3-4):29-2256, 1992.
Yang Yu. Towards sample efficient reinforcement learning. In I/CAI. pp. 5739-5743, 2018.
13

---

Published as a conference paper at ICLR 2020
10 APPENDIX
In Table
provide hrief summary of important notations used in the paper:
Notations
Definition
Aij
The discrepancy of the relative action value of action and action j. X A Ay. where X = A(s, a,). Notice that the value here is not the estimation of return, it represents which action will have relatively higher return if followed.
Q" a)
The action value function or equivalently the estimation of return taking action at state 8, following policy π.
Pij
Pij P(), > X1) denotes the probability that i-th action is to be ranked higher than j-th action. Notice that Pij is controlled by through A, X
(s(T, T t), a(T, t) collected from the environment. It is worth noting that this trajectory is not associated with any policy. only represents a series of state-action pairs. We also use the abbreviation 8, 8(T, 1), 0r a(T, ().
A trajectory
r(T)
The trajectory reward r(r) Ei= r(st, 01) is the sum of reward along one trajectory.
Rinx
Rmax is the maximum trajectory reward, i.e., Rmmx max, r(r). Since we focus on MDPs with finite horizon and immediate reward, therefore the trajectory reward is bounded.
M
M is the upper bound of the absolute value trajectory reward, i... |r(r) S M. Vr.
Σr
The summation over all possible trajectories T.
Po(T)
The probability of specific trajectory is collected from the environment given policy Tg- Pa(T) p(sn))(())))))))) [[] Ta (a,l (s (..+p St. a.)
T
The of all possible near-optimal trajectories. [7] denotes the number of near-optimal trajectories in T.
The number of training samples or equivalently state action pairs sampled from uniformly optimal policy.
m
The number of discrete actions.
Table 1: Notations
10.1 A DISCUSSION OF PRIOR WORKS ON REDUCING RL TO SL.
There are two main distinctions between supervised learning and reinforcement learning. In supervised learning. the data distribution D is static and training samples are assumed to be sampled i.i.d. from D. On the contrary. the data distribution is dynamic in RL. It is determined by both environment dynamics and the learning policy. The policy keeps evolving during the lcarning process, which results in the dynamic data distribution Secondly, the training samples we collected are not independently distributed due to the change of learning policy. These intrinsic difficulties of RL. make the learning algorithm unstable and sample-inefficient. However, if we review the wfate-of-the-ars in RL community, every algorithm eventually acquires the policy, either explicitly implicitly, which is mapping from the state an action probability distribution over the action space. Ultimately, there exists a supervised learning equivalent to the RL problem, if optimal policies exist. The paradox is that is almost impossible to construct this supervised learning equivalent on the fly, without knowing any optimal policy. Although what is the proper supervision still lingered in the RL community, pioneers have developed a set of insightful approaches reduce RI. into its SI. counterpart over the past several decades. Roughly, can classify the prior work into the following categories:
RL.
AopectationMMaxiiiaatti (EM) Dayan & Hinton 1997
Peters & Schaal 2007) Kober & Peters
20099; Abdolmaleki et al. 2018 etc.
Rntrapy-Regularized RL (ERL) 0' Donoghue et al.
2016
Oh et al.
2018
Haarojja et all 2018 etc.
Interactive Imitation Learning (IIL) Daumé et al.
2009 Syed Schapire (2010)
Ross
Bagnell
(2010): Ross et al. (201 1): [Sun al. (207) etc.
The early work in the EM track transfers objective by Jensen's 's incquality and the maximizing the lower bound of
the original objective, which resembles Expectation- Expeetation-Maxiiizaatii Maximization procedure and provides policy improvement
14

---

Published as a conference paper at ICLR 2020
Algorithm 1 Off-Policy Learning for Ranking Policy Gradient (RPG)
Require: The near-optimal trajectory reward threshold the number of maximal training episodes Nruaa
Maximum number of time steps each episode T, and batch size
1:
while episode < Nmax do
2: repeat
3: Retrieve state and sample action a, by the specified exploration agent (can be random, e-greedy, any RL algorithms).
4:
Collect the experience & = (#e: Ve, 8841) and store to the replay buffer.
5:
1= +
6:
if't % update step == 0 then
7:
Sample batch of experience {e, 15 from the near-optimal replay buffer.
8:
Update He based on the hinge loss Eq ( for RPG.
9:
Update exploration agent using samples from regular replay buffer (In simple MDPs such as PONG where we access to near-optimal trajectory frequently, we can use near-optimal replay buffer to update exploration agent). end if
10:
11:
until terminal 8, or Luu >=
12:
if return Σi= r 2 c then
13:
Take the near-optimal trajectory e,, ft, 11:,,,,,,, 1,..., T in the latest episode from the regular replay buffer into near-optimal replay buffer.
14:
end if
15:
if % cvaluation step == then
16:
Evaluate the RPG agent by greedily choosing the action. If the best performance is reached, then stop training.
17:
end if end while
18:
guarantee. While pioneering at the time, these works typically focus the simplified RL setting, such as Dayan & Hinton (197] the reward function is not associated with the state in PPteers & Schaal (2008) the goal is to maximize the expected immediate reward and state distribution is assumed to be fixed. Later on in Kober & Peters (2009) the authors extended the EM framework from immediate reward into episodic return. Recent advance Abdolmalcki et al. (2018) utilizes the EM-framework on a relative entropy objective, which adds parameter prior regularization. As mentioned in the paper, the evaluation step using Retrace MMunos et al.. (2016) can be unstable even with linear function approximation Touati et al. (2017). In general, the estimation step in EM-based algorithms involves on-policy evaluation. which is one difficulty shared for any policy gradient methods. One of the main motivation that we want to transfer the RL into a supervised learning task is the off-policy learning enable sample efficiency.
Retrace|Munos
To achieve off-policy lcarning, PGO/O'Donoghuc Donoghue al. (2016) connected the regulai-ee policy gradient with Q-Icarning under the constraint of small regularization. In the similar framework. Soft Actor- Actor-Critic Haarnoja et al., (2018) was proposed to enable sample-efficient and faster convergence under the framework RL. It is able to converge to the optimal policy that optimizes the long-term reward along with policy entropy. It is efficient way to model the suboptimal behavior and empirically it is able to learn reasonable policy. Although recently the discrepancy between the entropy entropy-regularizer objective and original fong-term reward has been discussed in O DDooghuue (2018) Eysenbach Levine (2019), they focus on learning stochastic policy while the proposed framework is feasible for both learning deterministic optimal policy (Corollary] [ and stochastic optimal policy (Corollary 6 In Oh et al. (2018). this work shares similarity to our work in terms of the method we collecting the samples. They collect good samples based on the past experience and then conduct the imitation learning w.r.t those good samples. However, differentiate how do we look at the problem thcoretically. This self-imitation lcarning procedure was eventually connected to lower-bound-soft Soltt-Q-leaning, which belongs to entropy-regue regulariee reinforcement learning. We comment that there is trade-off between canple-efficiency and modeling suboptimal behaviors. The more strict requirement we have on the samples collected we have less chance hit the samples while the optimal behavior.
of entropy-regularizz
close to imitating
From the track of interactive imitation lcarning, initial representative works such as Ross & Bagnell (2010) Ross et al.] (201T) firstly pointed out the main discrepancy between imitation learning and reinforcement learning is the i.i.d. assumption does not hold and provides SMILE Ross & Bagnell (2010) and DAGGER Ross et al. (01 I overcome the distribution mismatch. The theorem 2.1 in Ross & Bagnell II 2010) firstly analyzed if the learned policy fails to imitate the expert with certain probability, what is the performance degradation comparing to the expert. While the theorem seems to resemble the long- teem-termm performance theorem 2 it considers the learning policy is trained through the state distribution induced by the expert, instead of state-action distribution as we did in Theorem Their theorem thus may be more applicable to the situation where interactive procedure is needed, such querying the expert during the training process. On the contrary, we focus directly applying
15

---

Published as a conference paper at ICLR 2020
Methods
Objective
Cont. Action
Optimality
Off-Policy
No Oracle
EM
ERL
IIL
V
X
RPG
X
Table 2: A comparison with prior work on reducing RL to SL. The objective column denotes whether the goal is to maximize long-term reward. The Cont. Action column denotes whether the method is applicable for both continuous action space and discrete action space. The Optimality denotes whether the algorithms can model the optimal policy. The v' denotes the optimality achieved by ERL is w.r.t. the entropy regularize objective instead of return. The Off- Off-Policy column denotes if the algorithm enable off- off-policy learning. The No Oracle column denotes the algorithms need to access to certain type of oracle (expert policy expert demonstrations).
supervised learning approach without having access to the expert to label the data. The optimal state-action pairs are collected during exploration and conducting supervised learning on the replay buffer will provide a performance guarantee in terms of long-tem expected reward. Concurrently, a resemble of theorem 2.1 in Ross & Bagnell (20TO) is Theorem in Syed & Schapire (20T0), the authors reduce the apprenticeship learning classification, under the assumption that the apprentice policy is deterministic and the misclassification all time steps is bounded, which we do not make. Within the IIL track, later on the AGGRE VATE Ross Bagnell (2014) was proposed to incorporate the information of action costs to facilitate imitation learning, and differentiable version called AGGREVATE
Sun et al. (2017) was recently developed and achieved impressive empirical results. Recently, hinge loss combined with regular Q-learning loss pre-training step for learning from demonstration Hestte al. (018 or a surrogate loss for imitating optimal trajectories Osa al.) (2018). In this work, we show that hinge loss constructs a new type of policy gradient method and can learn optimal policy directly.
In conclusion, our method approaches the problem of reducing RL to SL from unique perspective that is different from all prior work. With reformulation from RL SL, the proposed off-policy framework preserves optimality
reduces variance simultaneously. Furthermore, also leads stable optimization since we are imitating a stationary target (UNOP), and is agmoistic to the knowledge of Oracle, such as expert policy demonstrations. A multi-aspect comparison between the proposed method and relevant prior studies is summarized in Table
10.2 RANKING POLICY GRADIENT THEOREM
The proof of Theorem can be found follows:
Proof. The following proof based direct policy differentiation Peters & Schaal (008 Williams (992 concise presentation, the suhscript for action value de, Ay, and Piy is omitted.
VoJ(0) Vo Σ po(T)r(F)
Lpa(t)Vologpo(17)
Eea(t)V Www. r(r)
V. Vologro(a(ss))())
Va 7o
-E
Va
-E
V
log(
+ e (r()]
16

---

Published as a conference paper at ICLR 2020
1
E
log(
+ e }r(+)]
1=1
1=1,, plz
V8
Σ fm1.ff
(A: - X33/2 r(T)
(8)
t=1
where the trajectory is a series of state-action pairs from t 1,..,, 1. i.e.r 81, 81,01, 82, O2 0 Sr. From Eq 7
to Eq (8), we use the first-order Taylor expansion of log(1 + +e = log 2 - + O(x²) to further simplity the ranking policy gradient.
10.3 DISCUSSION ON THE PROBABILITY DISTRIBUTION OF RPG
Corollary 3. The pairwise ranking policy shown in Eq (2) constructs a probability distribution over the set of actions when action space m is equal 2, given any relative action values Xi, 1,2. For the cases with m > 2, this conclusion does not hold in general.
It is easy to verify that T(a:)a) > 0, E T(ails)
holds and the same conclusion cannot he applied to m >> 2 by constructing counterexamples. However, we can introduce dummy action a' form probability RPG. During policy learning. the algorithm will increase the probability 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 x (s) = 0. Similarly. we can introduce a dummy trajectory r' with trajectory reward r(r') = 0 and pr = Σ, po(T). The trajectory probability forms and ps (s(T)
distribution
best actions and
probability distribution since E, pe (T) + pe
vT and po(T') 2 The proof of valid trajectory probability is similar to the following proof on {[a s) is valid probability distribution with dummy action. The practical influence of this is negligible since our goal is to increase the probability of (near)-optimal
trajectories. To present in clear way, we avoid mentioning dummy trajectory 7' in Proof 10.2 while it can be seamlessly included.
Condition
(The range of A-value). We restrict the range of A-values in RPG so that it satisfies Am 2 In(m m - 1), where Am = min.,, Àza m is the action dimension.
This condition can be casily satisfied since RPG we only focus on the relative relationship X-values and we can constrain its range so that Am. satisfies the condition Furthermore, since we can see that m - > 1 decreasing w.r.t to action dimension m. The larger the action dimension, the less constraint we have on the A-values.
Corollary 4. Given Condition we introduce dummy action a' and set w(a d'1s) =1 T(a which will construct a valid probability distribution (T((a(s) over the action space AUa'.
Proof. Since have :aa a.ls) 0 Vi L...., and E a(a asss) + x(aa
a'|s) 1. To
prove this a valid probability distribution, we only need show that Taa d'(s) 2 0, Vmn 2 2, i.e. Σ, (aa- = a,1s) & 1, vm 2 Let Am = min,, Ayis
Σ T(a a.ls)
(9)
Σ 11 Pij
(10)
Σ
11 11=1,441
1
(11)
1 + cAsi
1
T==
(12)
+ e
1
m-1
Condition
0
(13)
I
cdm
<1
(14)
10.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 RI. we want optimize the prohability of each action
17

---

Published as a conference paper at ICLR 2020
(ai) to be ranked higher among all actions, which is the sum of the probabilities of all permutations such that the action o, the top position of the list. This probability is computationally prohibitive since we need to consider the probability of m! permutations. Luckily, based on [ao et al. (2007) [Theorem 6), we can model the such probability of action d; 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)), Given the relative action values q [AI,..., Am.. the probubility of action i be taken (i.e. to be ranked the top of the list) is:
((A.)
T( = [s(s:)
(15)
j=1 o(2g)
where (b()) is any increasing, strictly finnttinn A common choice of & is the exponential
Closely built upon the foundations from learning rank Cao et al. (007), we present the listwise policy gradient method, as introduced in Theorem 4
Theorem 4 (Listwise Policy Gradient Theorem). For any MDP, the gradient of the long-term reward (0) Σ; (a(T) (T()) w.r.f the parumeter 0 of listwise ranking policy takes the following form:
(o)
E m
Vo
log
r(T)
(16)
exa
where the listwise ranking policy me parameterized by 0 is given by Eq policies:
17
for tasks with deterministic optimal
arg max Xi, i 1, I,..,,
(17)
or Eq 18 for stochastic optimal policies:
[=|ss,
i= =,1,.. 1,..,,m
(18)
where the policy takes the form as in Eq 19
T( ds ds(s))
(19)
Σn= eA
the probability that action being ranked highest, given the current state and the relative action values
A1. .2...u Am-
The proof of Theorem exactly follows the direct policy diffcrentiation Peters & Schaal 20088 Williams 1992)
exxeryy by replacing the policy to the form of the softmax function. The action probability x: <[a; s). Vi
raa 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 softmax layer is optimizing the probability of each action be ranked highest, with respect to the long-tern reward.
10.5 DISCUSSIONS ON THE OPTIMALITY PRESERVING
Condition 2 (Initial States). The (near)-optimal trajectories will cover all initial states of MDP. i.e. {s(T, Vr T) (s(T, 1)1 VT where T == {r|W(T) = 1) 2 c).
The Condition describes what type of MDPs is directly applicable to the trajectory reward shaping (TRS, Def3). The MDPs satisfying this condition cover a wide range tasks such as Dialogue System et al. (2017)
Go Silver et al. (201). video games [Bllemaae et al. (2013) and all MDPs with only one initial state. If we want to preserve the optimality by TRS, the optimal trajectories of MDP needs to cover all initial states equivalently,
all initial states will lead least one optimal trajectory. Similarly, the near-optimality is preserved for all
MDPs that its near-optimal trajectories cover all initial states.
Theoretically, is possible to transfer more general MDPs to satisfy Condition and preserve the optimality with potential-base based reward shaping Ng et al. (1999). More concretely, consider the deterministic binary tree MDP (M1) with the set of initial states S
(81.61 s1) as defined in Figure 4 There are eight possible trajectories r(T))
Vi 2, ...7. Therefore, this MDP daes not satisfy Condition 2 We can compensate the trajectory reward of best trajectory starting from s to the Rmax by shaping the reward with the potential- based function d(s²)= = and d(s) = O, Vss * 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,
in M1. Let r(7))
10 Rmax. r(Ts)
set c(s) min.es, ((T[s(T, 1) 8), Vs E Sj. Take Vs E St. During the exploration stage, we track the current best trajectory of
Mi an example, c(s) 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 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.
18

---

Published as a conference paper at ICLR 2020
S1
S1
S2
S3
S
S3 '
S4
S5
S6
S7
S4
S5
S6
S7
Tl
F2
3
T4
T5
26
T7
T8
Figure 4: The binary tree structure MDP with two initial states (S1 {s1, s D., similar discussed in Sun et al. (2117). Each path from the root to the leaf node denotes one possible trajectory in the MDP.
10.6 PROOF OF LONG-TERM PERFORMANCE THEOREM 2
In this subsection, reduce maximizing RL objective into supervised learning problem with Theorem Before that, we prove Lemma I to link the log probability of trajectory to state action distribution. Then using this lemma, we can connect the trajectory probability of UNOP with its state-action distribution, from which we prove the Theorem
Lemma Given a specific trajectory т. averaged state-action pair log-likelihood over horizon equal to the weighted sum over the entire state-action space, i.e.:
Σ log Ne (arls:)
Eps,, log to(als)
(20)
T
8,a
where the sum in the right hand side is the summation over all possible state-action pairs. is worth noting that pls, a/r) is not related to any policy parameters. It is the probobility of specific state-action pair (s, 0, in specific trajectory T.
Proof. Given trajectory r = {s(T, a), 1)), a(r,, ()) = ((81, az). (ST, ar) denote
the unique state action pairs in this trajectory U(T) [(st, a,)) where is the number of unique state-action pairs in and T. The number of occurrences of state-action pair (si, az) the trajectory denoted (s;, a:)l.
log no (a:ls:)
(21)
T
(ss an)l
log (ails;)
(22)
p(ss, a log (og
(23)
Σ
(log
(24)
(s,))
Σ
Σ p(s, logmo(a))
(25)
(sa))U(F)
(n.))((())
Σ (gg)
(26)
(5.a)
where from Eq
24 to Eq
25
we use E(o.)ee p(), = EE p()1, = -
(
T
:. p(s, a/T) = v s. a) & (T)).
This thus completes the proof.
Now ready prove the Theorem
19

---

Published as a conference paper at ICLR 2020
Proof. The following proof holds for arbitrary subset of trajectories 7 which is determined by the threshold in
5 The n. associated with and this subset of trajectories.
arg max Σ (o(T))((F)
(27)
(T() 0, TT
(28)
arg max
Σ (o(
(29)
-ET
use Lemma
: p7()) > and w()) > 00.: Σ ps(())(T)) >
(30)
EET
arg max log!
Σ (o(T))((T)
(31)
TET
log
mz/n)= 2
log(zi)/n, Vi, > 0, we have:
(32)
log(
pa (T(T)((T)) 2 Σ
log (o()))((7)
(33)
TET
TET
The lower bound holds when (T())((T)) = 1 Vr E T. To this end, we maximize the lower bound of the expected long-term performance.
arg max
logp)())u(()
(34)
arg
sec w()())
(35)
TET
= arg max
log
(36)
TET
arg max
logp(s1) + Σ log p(
Σ log logmo(ar(ss) + log w(()
(37)
TET
This the reason that wr) can be set as arbitrary positive constant
(38)
arg max
[T
log no (sr|s:)
(39)
FET
arg max
log ne (ac (sx)
(40)
T
ET
arg max
log To (st) Use Assumption the existence of UNOP
(41)
T
YET
arg
Pr. (T)
Σ
log Ne (a(a) (s))
(42)
TET
where T. is UNOP (De
(43)
Pa. (T) O.T $ T
(44)
Eg 44 can be established based
Σ Pr. (T) = Σ 1/
(45)
TET
TET
arg max Σ Pr. (T)
Σ log (asl(t))
Use lemma
= arg max Σ Pr. (T) Σ p(s,, alt) log To(als)
(46)
The 2nd sum over all possible state-action pairs. (s, a) represents specific state-action pair.
arg max
ΣΣ Pr. (T)p(s, a77) log (a]s)))
(47)
arg max
Σ Σ
Pr. (T)p(s, a/7) log (als)
(48)
4.4
20

---

Published as a conference paper at ICLR 2020
arg max
Σ Pr. (s. (a(]s) 4,0
(49)
In this proof we use & a(7, f) and ar = a(T, t) as abbreviations, which denote the 1-th state and action in the trajectory 7, respectively. [T] denotes the number of trajectories in T. We also use the definition of w(r) to only focus on near-optimal trajectories. We set wr(r) = 1 for simplicity but will not affect the conclusion if set to other constants.
Optimality: Furthermore, the optimal solution for the objective function Eq 49 is a uniformly (ncar)-optimal policy
arg max
Σ Px. (s, a) mo(as))
(50)
arg max
Σ Pr. (s)
Σ T (ogmmaa))
(51)
arg max
Σ Pr. Pr.(s) (8)
Σ
T (als) (og (a(ss) Σ Pr. (8)
Σ log n. (a|s)
(52)
To (a|s) log xo(a|s)
arg max
Σ Pr. (r.(s)
Σ
(a|s)
(53)
arg max
Pr. (8)
Σ
K [L(TT(as))] = n
(54)
Therefore, the optimal solution of Eq Σ, Ps. (T)((T) ΣtEt (T) Rmax c. The optimal solution is obtained when we set Rmax-
49 is also the (near)-optimal solution for the original RL problem since
Given any optimal policy n of MDP satisfying Condition 2 VT & T. we have pa (T) = 0,, where T denotes the set of all possible optimal trajectories in this lemma. If नr & T, such that pr (T) > O. then x is not optimal policy.
Lemma 2.
Proof. We prove this by contradiction. We assume is an optimal policy. If 3r's & T. such that 1) p=(7') * O. or equivalently: (T') > 0 since ps (7') E 01. and 2) 7 & T. We can find better policy n' by satisfying the following three conditions:
Pr (+') = 0 and
P+ (TI) Pa + pr T E and
P+ (T) (T) VT $ m)
Since (T) 2 0, VT and E, pa (T) = 1, therefore 2x constructs a valid probability distribution. Then the expected long-term term performance of n is greater than that of .:
Σ per por (F) pTx(T)
+ Σ (+) (p w((7') ((tr)))
(r)))(()+
w(('))
(n) w + - (())))))))))))(())))))))) (p.) w(n) (((')
77' $ T.'. w(r') = 0 and 7 E TT.: 11
(1) - -
-Pr(T)) + (p'(r')- p+ (T)) = p=(7))
Essentially, we can find a policy that has higher probability on the optimal trajectory 71 and zero probability on r' This indicates that it is better policy than न. Therefore, и is not an optimal policy and it contradicts our assumption, which proves that such r' does not exist. Therefore, VT & T. we have (=(T) = O.
Lemma 3 (Policy Performance). VT. pe(T) > O. if the policy takes the form as in Eg (5) or Eq (2) This means for all possible trajectories allowed by the environment, the policy takes the form of either ranking policy or softmax will generate this trajectory with probability Po(T) > 0. is worth noting that because of this property, wo is not an optimal policy according to Lemmo though can be arbitrarily close to the optimal policy.
21

---

Published as a conference paper at ICLR 2020
Prouf.
Y :P(() p(s)) (fool and (ar > 0, p(s)) > 0, 0(p(sta)ss,, at)
(55)
(56)
if p( 18; az) = 0 or p(81) = 0,
then the probability of sampling from any policy is zero. This trajectory does not exist.
:. (T()) 0.
(57)
This thus completes the proof.
10.7 PROOF OF PERFORMANCE POLICY GRADIENT COROLLARIES
Corollary 5 (Ranking performance policy gradient). Optimizing the lower bound of expected long-term per- formance (defined in Eq ( using pairwise ranking policy (Eq (2) can be approximately optimized by the following loss:
min E.,. Pa. (s)
m (Ejai.sss max((O,marga) + Ms, (1s.a,)-((8.4))) ((..
(58)
where margin is small positive value. We margin equal to one in our experiments.
Proof. RPG, the policy =e (als) is defined as Eq We then replace the action probability distribution Eq (5) with the RPG policy.
#(a (8) Th j=i.z=Pu
(59)
Because RPG is fitting a deterministic optimal policy,
we denote the optimal action given sate as as, then we have
mAx
Σ
Ps. (s, a.) log ((sls)
(60)
max Σ Ps. (s, a.) log log (1Pp)))))))))))
(61)
max
Pr. (s. a.) log fi 1 1
(62)
min
Dr. (8, a.)
Σ
log(1 + e first order Taylor expansion
(63)
jøij=1
Rs min
Pau (8, 01)
Σ
A
st. 1,
(64)
m
min Σ
Pr. (s, a:)
Σ
(Ag
As)
stt s. - -1= 1,
(65)
min Σ Pr. (s, L:)
(66)
where the pairwise loss L(s,a;) is defined as:
L(s,ad) = Σ
ma margin + A(s, a,) A(s, a.)),
(67)
where the margin in Eq 66 a small positive constant.
(68)
index denote The optimal action at each state. The optimal X-values minimizing Eq (65 (denoted by X²) need to satisfy X X; + c, Vj # i. The optiaml A-values minimizing Eq (66) (denoted by X²) need to satisfy
From Eq 65 to Eq (66). we consider learning deterministic optimal policy a, (s). where
X max X3 margin, Vij # In both cases, the optimal policies from solving Eq (65) and Eq (66) are the same: (*)) arg max, A arg max, X Therefore, we use Eq (66) surrogate optimization
problem of Eq 65
22

---

Published as a conference paper at ICLR 2020
10.7.1 LISTWISE PERFORMANCE POLICY GRADIENT
Corollary 6 (Listwise performance policy gradient). Optimizing the lower bound of expected long-term perfor- mance by the listwise ranking policy (Eq
(79 is equivalent
max Σ Pr. (8)
Σ no (a.|s) (s) log
(69)
=j=1 ca
5m
The proof of Corollary iis a direct application of thcorem by replacing policy with the softmax function.
10.8 POLICY GRADIENT VARIANCE REDUCTION
Corollary 7 (Variance reduction). Given stationary policy, , the upper bound of the variance of each dimension of policy gradient is O C M The upper bound of gradient variance of maximizing the lower bound of long-term performance Eq ( OCC)), where C is the maximun norm of log gradient hased Assumption The upper bound of gradient variance by supervised learning compared to that of the regular policy gradient reduced by an order of O(T M²), given M 1, 1, which a very common situation in practice.
Proof. The regular policy gradient of policy my is given as William 1992
Σ
pe( Ve log((o((((r)))))) ()) (())]
(70)
The regular policy gradient variance of the i-th dimension is denoted as follows:
T
Var Σ Vo (og(
(71)
We denote (T) ΣT, Vo (a(T,, ()(()) for convenience. Therefore, v, random variable.
Then apply var(z) E E [2-) Ep [o)] we have:
Var
vo (olog(oo(ar.))))))00)))))
(72)
=Var (2:(7))
(73)
Σ (T) E [oo(t)a((t))
(74)
$ Σ (T)
(75)
Epo(T)
Ve (ologttola(..0)44440)))) (use M 2 (r(
(76)
Σ pa(T)
Ve
(77)
T
=M² Σ (T)
Va Loog(oo(a((.))))((7.)))) log(To(a(7, ()|ss, k):)] (Assumption
(78)
SM² Σ (o()))
1
Σ c9
(79)
M Epo(T)T=0²
(80)
M²
(81)
The policy gradient of long-term performance 4
Σ
Pr. (s, a) Vo log To (a]s)
(82)
4,0
23

---

Published as a conference paper at ICLR 2020
The policy gradient variance of the i-th dimension is denoted var( (Vo log ())
(83)
Then the upper bound given by
var Vo log to(a))))
(84)
Σ pr. (s, aV (o Per (e
(85)
Σ Pr. logoo use Assumption
(86)
Σ Pu. (s,a)C²
(87)
8,8
C
(88)
This thus completes the proof.
10.9 DISCUSSIONS OF ASSUMPTION 2
In this section. we show that UNOP exists in range of MDPs. Notice that the lemma shows the sufficient conditions of satisfying Caumptionrratiin rather than necessary conditions.
Lemma 4. For MDPs defined in Section 3 satisfying the following conditions:
Each initial state leads to one optimal trajectory. This also indicates |S1 = [T), where denotes the set of optimal trajectories in this lemma, S₁ denotes the set of initial states.
Deterministic transitions, i.e. p(s'(s, a) E 10.
Uniform initial state distribution, i.e. p(s1) + Asi St.
Then we have: 3m, where s.t. Ps. (T) 1 VT E T. It means that a deterministic uniformly optimal policy always exists for this MDP.
Proof. We can prove this by construction. The following analysis applies for any 7 E T.
Pr. (T) [
(89)
logg- (7) = log [T]
(90)
log((s1) + log ((spp(s(11e) ax)
Σ log n. (a.(s)) = llg 'T]
991)
log T. (as/ss) = logp(s1)
log p( 1 log T
(92)
where use as abbreviations of a(T, 1), s(r.
We denote D(7) logp(ss) Σ pogg(s
log n. (a:(s:) = D(T) - log '7]
(93)
we can obtain a uniformly optimal policy by solving the nonlincar programming:
log n.
D(r) - log ( ET
(94)
log T. (o(r, 0, Vr T = I....T (a)(s((T,))) Vr T, == 1,..,
(95)
(96)
24

---

Published as a conference paper at ICLR 2020
R, M, s
R, M,
Q1
Q2
Q3
I12
T13
12.3
(a)
(b)
Figure 5: The directed graph that describes the conditional independence of pairwise relationship of actions, where Qi denotes the return of taking action âi at state following policy in M. ie.. Q (5, a1). 112 is a random variable that denotes the pairwise relationship of Q1 and Q2, ie.. 1 iif. Q1 2 Q2, o.w. 1,2 0.
Use the condition p(s1) [T]- then have:
T
log T- (a(T, t)) = Σ log 1 (LHS of Eq 94
(97)
log p(s))
Σ ( |og log [T] log |7| (RHS of Eq
(98)
D(r) log [7]
Σ log (a(,, VTET.
(99)
Also the deterministic optimal policy satisfies the conditions Eq 96). Therefore, deterministic optimal policy a uniformly optimal policy. This lemma describes one type of MDP in which UOP exists. From the above reasoning. we can see that as long as the system of non-linear equations Eq 9495 96 uniformly (opara- policy exists.
has a solution, the
Lemma (Hit optimal trajectory). The probability that a specific optimal trajectory was not encountered given an arbitrary softmax policy ne is exponentially decreasing with respect to the number of training episodes. No matter MDP has deterministic probabilistic dynamics.
Proof. Given a specific optimal trajectory == (*(T, l), (T,T))))__1 and an arbitrary stationary policy mss the probability that has never encountered at the rithh episode is po(T)]" = <". based on lemma 3 we have (T( 0, therefore have E [0, 1).
10.10 DISCUSSIONS OF ASSUMPTION
I
Intuitively, given state and stationary policy æ, the relative relationships among actions be independent, considering fixed MDP M. The relative relationship among actions the relative relationship actions' return. Starting from the same state, following a stationary policy, the actions' return determined by MDP properties such as environment dynamics, reward function, etc.
More concretely, we consider MDP with three actions (a1, d2, aa) for each state. The action value Qha satisfies the Bellman equation in Eq (100). Notice that in this subsection, that estimates the absolute value of return M.
QM denote the action value
Q a:) r a:) + max las
1,2,3.
(100)
As we can see from Eq 110). (s, i 1, is only related to and environment dynamics P. It means if π,, M and directed graph [Bihhpp (2006) model the relationship action values, as shown Figure Similarly, we only consider the ranking of actions, this ranking is consistent with the relationship of actions' return, which is also determined by s. n. and P. Therefore, the pairwise relationship among actions can be described as the directed graph in Figure 5 (h), which establishes the conditional independence of actions' pairwise relationship. Based the above reasoning, we conclude that Assumption ii realistic.
given, the action values of three actions determined. Therefore,
25

---

Published as a conference paper at ICLR 2020
10.11 EXPLORATION EFFICIENCY
The proposed off policy learning framework indicates the sample complexity related to exploration efficiency supervised learning efficiency. Given a specific MDP, the exploration efficiency of an exploration strategy can be quantified by how frequently we can encounter different (near)-optiml trajectories in the first & episodes. The supervised learning efficiency under the probably approximately correct framework Valiant ( (1984) is how many samples need collect that we achieve good generalization performance with high probability. Joindl consider the efficiency in two stages, we can theoretically analyze the sample complexity of the proposed off-policy learning framework, which will be provided in the long version of this work.
Improving exploration efficiency is not the focus of this work. In general, exploration efficiency is highly related the properties of MDP, such transition prohabilities, horizon, action dimension, etc. The exploration strategy should be designed according to certain domain knowledge of the MDP to improve the efficiency. Therefore, did not specify our exploration strategy adopt the state-of-the-at conduct exploration.
Based on the above discussion, we can see that how frequently we can encounter different (near)- trajectories is a bottleneck of sample efficiency for RPG. In the MDPs with small the transition probabilities of reaching the near-optimal trajectories, rarely collect any near-optimal trajectories during the carly stage of exploration. The benefit of applying the proposed off-policy framework would be limited.
10.12 HYPERPARAMETERS
We present the training details of ranking policy gradient in Table The network architccture the same as the convolution neural network used in DQN Mnih et al. (2015). update the RPG network every four timesteps with a minibatch of size 32. The replay ratio is equal to eight for all baselines and RPG (except for ACER we use the default setting in openai baselines Dhariwal et al. (017) for better performance).
Table 3: Hyperparameters of RPG network Hyperparameters Architecture
Value
Conx(32-8x8-4)
-Conv(64-4x4-2)
-Conv(64-3x3-2)
-FC(512)
Learning rate
0,0000625
Batch size
32
Replay buffer size
1000000
Update period
4
Margin in Eq (6)
1
26


Reviews:
[{"review_id": "rJenP7R6FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 work first establishes the connection of maximizing the lower bound of accumulated reward and supervised learning on near-optimal policies. Then it proposes a general framework for policy learning: during the exploration stage, the agent will collect near-optimal trajectories while in the exploitation stage, the agent will perform supervised learning on the collected data. Under this framework, the author argues that the ranking loss could outperform the state-of-the-art on the Atari benchmark.\n\nThe overall idea is intuitive yet interesting, and the empirical result is quite impressive. \n\nSome questions which I think the paper could discuss more:\n- In the paper, the near-optimal policy is defined with an absolute threshold, which could be task/environment-specific. I am wondering whether the author tried to set the `near-optimal policy` as a relative value (in the current replay buffer). Then the hyper-parameter could be shared.\n- I think some empirical comparisons of the gradient variance (i.e., for Corollary 2) will be more demonstrative, although I could imagine that the near-optimal trajectories will have smaller variance. \n- The choice of C could be tricky in the method as the whole algorithm is highly depending on it. How does the author choose C? If C is tuned for each environment, I am not sure whether it is a fair comparison with C51/Rainbow/IQN. \n- More algorithm training details on the experimental setting (like the hyper-parameters) are needed. \n\n======\nFrom eq (7) -> eq (8): Does the Taylor expansion near $\\lambda_{ji}=0$ make sense?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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 at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "r1lM4XHstB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 to reparameterize the policy using a form of ranking, and updating the policy gradient update accordingly. This on it's own isn't particularly useful, however the authors use this insight to attempt to convert the RL problem into a supervised learning problem. I think this is an interesting paper and approach, however some issues remain.\n\nHigh level:\n\nThe reward threshold appears to require a-priori knowledge of the correct scale to set it at, and the maximum possible reward, which is unfortunate. Also I'm not sure it would make sense in a sparse reward environment, or an environment with small reward leading up to a single large reward, since the trajectories that get small reward might be discarded erroneously. Maybe there should be an annealing schedule for this parameter? This deserves some discussion at least.\n\nThe experimental results are very good, however you are using off-policy replay data and therefore have the issue that using the same data many times can (often) improve performance for any off-policy algorithm. This needs to be controlled and investigated very closely, however I don't even see the batch size being used listed anywhere. The authors need to really demonstrate that the benefit is coming from their algorithm and *not* just the re-use of replay data that the baselines don't get to see as much of.\n\nMore minor:\n\nFirstly, there is very bad writing in places, .e.g, abstract: \"The state-of-the-art uses action value function to derive policy\". Things like this appear in many places.\n\nQ-learning, Q-values sometimes Q is upper case sometimes lower case.\n\nRelative action values are never defined, but if they are what I think they are then they are usually referred to as 'advantage values', and are generally given the notation of A(s,a).\n\nDoes the policy in (2) sum to 1?\n\nAssumption 1 is written very confusingly. I would state it as something like:\n\n\"Assumption 1. For a state s and action i the set of events {E^i_j}_{j \\neq i}, where E^i_j corresponds to action ai being ranked higher than action aj, are conditionally independent, given a MDP and a stationary policy.\"\n\nAssumption 1: What is is conditioned on?\n\nThm 1: the statement of the theorem has an equality, but the proof has a clear 'approximate equality', this is very misleading since the statement is not actually true!\n\nI don't follow the proof of corollary 5, especially the sentence explaining (65) -> (66), which doesn't parse. Again the proof is actually approximate but the statement is given using an equality, which is false.\n\nThe appendix is very messy and several parts of it just consist of series of equations with no supporting explanation.\n\nRefs:\nThe original DQN paper (Mnih et al) should be cited after you mention DQN.\n\nI was surprised not to see references to \nACER: https://arxiv.org/abs/1611.01224 and \nPGQ: https://arxiv.org/abs/1611.01626 when discussing the off-policy / RL + SL work.\n\nFurther, in your discussion about entropy regularized RL \"However, the discrepancy between\nthe entropy-regularized objective and original long-term reward exists due to the entropy term.\" - this has been corrected by a recent work: https://arxiv.org/abs/1807.09647. Probably worth mentioning it here too.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SyxNjjojKB", "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": "This paper presents a new view on policy gradient methods from the perspective of ranking. The end goal in policy learning is to achieve the right ranking of actions at a state (in the case when deterministic policies are optimal), and the paper proposes a method of doing this inspired from the work on learning to rank. They further argue that in the case with stochastic optimal policies, REINFORCE with softmax policies is rank wise optimal, which is not surprising, but at the same time interesting as well. The other main part of the paper is casting off-policy RL as supervised learning similar to work on self-imitation learning and reward weighted regression methods. This section is presented differently from the past analyses of self-imitation methods and requires the existence of UNOP, which seems like a strong assumption. They then instantiate the framework with GPI based exploration, and show that it achieves better performance than IQN and Rainbow on a subset of atari games.\n\nI am leaning towards a weak reject for this paper, although I am happy to revise my score based on the rebuttal. While the paper is interesting with regards to the ranking perspective, I am not fully convinced about the novelty of the reduction of off-policy learning to supervised learning. This appears already in past works (which the paper cites in the appendix) and the assumption of the existence of UNOP seems strong. I find using a Q-learning agent for exploration a bit complicated and perhaps unnecessary. Also, the paper currently lacks intuition about the effectiveness of their policy gradient approach on top of the data collected from an DQN-based agent. Since reward shaping is done at the trajectory level, why would we expect the supervised regression step to do better than the best trajectory in the data? Also, can the same Q-learning based method perform better if one controls for the number of gradient updates? How would the other methods such as self-imitation or reward weighted regression instead of their proposed supervised learning approach perform on top of data collected from a policy iteration based exploration policy? But the results seem quite promising. \n\nI would also appreciate some more clarity in terms of writing and presentation.  While this is done in the appendix, I would suggest making references with regards to the supervised learning section (Sec 5) more explicit and refining some of the text in the paper, although this is a minor point.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a novel and effective approach to policy optimization.  The overall contribution is sufficient to merit acceptance.  Nevertheless, the authors should improve the presentation and experimental evaluation in line with the reviewer criticisms.  The criticisms of AnonReviewer2 in particular should not be neglected.  Regarding the theory, I agree with AnonReviewer3 that the UNOP assumption is too limiting.  The paper would be much stronger if this assumption could be significantly weakened, or better justified.
Decision: Accept (Poster)