Hinge Policy Optimization: Rethinking Policy Improvement and Reinterpreting PPO
Authors: Hsuan-Yu Yao
Ping-Chun Hsieh
Kuo-Hao Ho
Kai-Chun Hu
Liang Chun Ouyang
I-Chen Wu
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
policy optimization
hinge loss
policy improvement
PPO-clip

Abstract: Policy optimization is a fundamental principle for designing reinforcement learning algorithms, and one example is the proximal policy optimization algorithm with a clipped surrogate objective (PPO-clip), which has been popularly used in deep reinforcement learning due to its simplicity and effectiveness. Despite its superior empirical performance, PPO-clip has not been justified via theoretical proof up to date. This paper proposes to rethink policy optimization and reinterpret the theory of PPO-clip based on hinge policy optimization (HPO), called to improve policy by hinge loss in this paper. Specifically, we first identify sufficient conditions of state-wise policy improvement and then rethink policy update as solving a large-margin classification problem with hinge loss. By leveraging various types of classifiers, the proposed design opens up a whole new family of policy-based algorithms, including the PPO-clip as a special case. Based on this construct, we prove that these algorithms asymptotically attain a globally optimal policy. To our knowledge, this is the first ever that can prove global convergence to an optimal policy for a variant of PPO-clip. We corroborate the performance of a variety of HPO algorithms through experiments and an ablation study.

Under review conference paper ICLR 2022
HINGE POLICY OPTIMIZATION: RETHINKING POLICY IMPROVEMENT AND REINTERPRETING PPO
Anonymous authors
Paper under double-blind review
ABSTRACT
Policy optimization is fundamental principle for designing reinforcement learn- ing algorithms, and one example is the proximal policy optimization algorithm with a clipped surrogate objective (PPO-clip), which has been popularly used in deep reinforcement learning due to its simplicity and effectiveness. Despite its su- perior empirical performance, PPO-clip has not been justified via theoretical proof up to date. This paper proposes to rethink policy optimization and reinterpret the theory of PPO-clip based hinge policy optimization (HPO), called to improve policy by hinge loss in this paper. Specifically, we first identify sufficient condi- tions of state-wise policy improvement and then rethink policy update as solving a large-margin classification problem with hinge loss. By leveraging various types classifiers, the proposed design opens up whole new family of policy-based algorithms, including the PPO-clip as special case. Based on this construct, we prove that these algorithms asymptotically attain globally optimal policy. To our knowledge, this the first ever that can prove global convergence to an optimal policy for a variant of PPO-clip. We corroborate the performance of a variety of HPO algorithms through experiments and an ablation study.
INTRODUCTION
Reinforcement learning (RL) has served as a powerful framework for achieving optimal sequen- tial decision making by directly interacting with the environment and learning from the underlying random process. Policy optimization, as a fundamental design principle of RL algorithms, itera- tively searches for an optimal policy by alternating between a policy evaluation step and policy improvement subroutine. Most of the popular policy optimization approaches, including the policy gradient methods (Sutton et al., 1999; MMni et al. 2016 Silver et al, 2014 Lillicap et al. 2016). Trust Region Policy Optimization (Schulman et al. 2015). and Proximal Policy Optimization (PPO) (Schulman al.] 2017). aim to achieve policy improvement in terms of the expected total reward via gradient- based parameter updates. Despite the empirical success of the above approaches, these policy improvement schemes inherently lead to the following fundamental issues: (i) Global conver- gence is usually difficult to establish due to the non-convexity of the underlying objective function (e.g., total discounted reward) and the use of gradient methods, even for the tabular cases; (ii) The policy update direction for improvement is tightly coupled with the true discounted state visitation distribution, which is usually intractable to obtain and needs to be addressed via sampling in practice.
To address the above issues, we propose rethink policy improvement in RL from the perspective of state-wise policy improvement, which aims for improvement directly in the policy space through a partial ordering of the policies. as adopted by policy iteration for the optimal control of Markov deci- sion processes (MDPs). We start by identifying two useful sufficient conditions for state-wis waie-wwiseppi policy improvement and thereafter pinpoint that improvement can be achieved based solely on the sign the advantage function. Based on this insight, we propose Hinge Policy Optimization (HPO) by con- necting state-wise policy improvement to solving large-margin classification problem, where we regard the process of policy improvement as training a binary classifier with hinge loss via empirical risk minimization. As policy improvement of HPO is not enforced in the expected total reward but state-wise manner, the policy update of HPO is completely decoupled from the state visitation distribution, which is by contrast required by many existing popular policy optimization methods. By leveraging various types of classifiers, the proposed HPO framework opens up whole new family of policy-based based RL algorithms. Interestingly, the popular PPO algorithm with surrogate

---

Under review conference paper ICLR 2022
clipped objective (PPO-clip) can be shown to special case HPO with a specific type of clas- sifier. Given the policy improvement property of the proposed classification-bass scheme, we are able to establish global convergence to an optimal policy for the HPO algorithms. To the best of our knowledge, our analysis provides the first global convergence guarantee for a variant of PPO-clip.
This paper meant to provide clear picture the RI. algorithms global convergence guarantees and thereby introduce a new perspective for reinterpreting the popular PPO-clip algorithm. The main contributions of this paper can be summarized as follows:
new HPO family with
We propose HPO, new policy optimization framework where the policy update is built on state- wise policy improvement via hinge loss. The members in the HPO family share generic loss function, and their differences lie in the choice of the margin and the classifier. We also show that the widely-used PPO-clip algorithm can be viewed as special case in this family.
This paper is the first ever that can prove state-wise policy improvement and global convergence for variant of PPO-clip algorithm ! Specifically, we first present a variant of the PPO algo- rithm with an adaptive clipped objective, which can be viewed as an HPO algorithm with adaptive margin, called HPO-AM. We prove the convergence to am optimal policy for HPO-AM, and pro- ceed to generalize the global convergence result to some other HPO-AM like algorithms equipped with other classifiers. We also empirically validate the proposed theoretical framework through experiments and thereby corroborate the performance of various HPO algorithms with different classifiers and margins (with the experimental results provided in Appendices F and
2
MAIN RESULTS
In this section, first review the theoretical background about RL and view PPO-clip update classification problem. Then, we establish glohal convergence for the proposed HPO-AM.
2.1 BACKGROUND
P, r, 7). where S a finiee state space, A is a finite action space, P : S x A x S - [0, is the state transition probability matrix, S A R is the reward function, and 7 (0, 1) is the discounted factor. A stochastic
discounted Markov Decision Process (MDP) is defined by the tuple (S, A,
policy π S + (AA) specifies the action distribution based on the current state, where A(A) is
the probability simplex over A, i..., ((A) {x E RI 2p + ... x A|-1 = 1, 2 0, Vi
0, ..... |A| }.. Given any policy æ, the state value function VT, the state-action value function Q and the advantage function A are defined as follows.
p( (*(s)==
E (.
(1) at) =8
(1)
(=(,,a)
E
Σ Lr=0
Y 7'n(s), 8,000
(2)
#44 1411P((1 ((.
Define (5') = (1 E2 d=(s (s)
(3)
5'130 S, as the normalized discounted state vis- itation frequency, which represents the probability of visiting state s' in a trajectory of म, given that sp s. With the above definition, (Kakade & Langford] (2022) quantified the difference in performance between two policies as follows. Given policies wi and m2.
(s) - V²*
1
Σ SES
d Σ ((als))A(3310)) A
(4)
'Regarding the convergence of PPO. (iu 2019 proves global convergence expected total reward for neural variant of PPO with adaptive Kullback-Leibler penalty (PPO-KL.). Given the salient algorithmic difference between PPO-KL and PPO-clip, the best of our knowledge, there remains proof of global convergence optimal policy for PPO-clip.

---

Under review conference paper ICLR 2022
The TRPO algorithm proceeds to maximize the expected value of surrogate function of 4 over the initial state distribution under the constraint of KL divergence. State-wise policy improvement is formalized based on the following partial ordering relation.
Definition (Partial ordering over policies), Let कi and Ta be two policies. Then, Ti 2 n2. called T1 improves upon T2. if and only VF 2 (s)(s), Vss E S. Moreover, we say > called wi strictly improves upon T2, if and only m π2 and there exists at least one state 8 such that (T > (s).
Definition 2 (An optimal policy). A policy x² is said to be an optimal policy if x- 2 x'. for every policy n². Moreover, we let V* (8) denote the optimal value of each state 8, Le., V*(*) = V (8).
We first introduce sufficient conditions for state- wise policy improvement in Propositions 1 These two conditions have been identified by (Hu al. (020) Section 3.1).
Proposition 1. Given policies and T2. Ti improves upon na if the following condition holds:
Σ aEA
[mi 0, Vs
Proposition 2. Given policies Ti and T2. Ti improves upon T2 if the following condition holds:
(als) =2(a|s)) (s,a) V(s,a) e S A.
(6)
Proposition I holds for the following reason: Since d (s') are non-negative, all values in are non-negative, and hence T1 improves upon T2. Proposition 2 can be derived directly from Proposition 1 and the fact that EaeA (s(
Ys S.
Notably, Proposition offerss a useful insight that state-wise policy improvement can be achieved by determining the sign of the advantage of each state-action pair (regardless of its magnitude) and adjusting the action probabilities accordingly. In this way, no additional constraints, such the KL divergence constraint used in TRPO (Schulman et al., 2015), are needed to ensure policy improvement. This also naturally motivates the design of using the signs of the advantage function as labels in determining the direction of the policy update. More specifically, we draw an analogy between (6) in Proposition 2 and the training of linear classifier: (i) The state-action pair serves as the feature vector of a training sample; (ii) The sign of A² (", a) plays the role of a binary label; (iii) Ti (als) (a(ass) resembles the prediction of linear classifier. In the next section, we substantiate this insight and present the proposed HPO framework.
the rest of this paper, our analysis relies on the following assumptions:
Assumption 1 (Bounded reward). To avoid trivial cases, we assume not all rewards are zero. Since both state and action spaces are finite, holds naturally that there exists a positive constant R (u Al |r(s, a)l > 0.
Assumption (Tabular policies). Policies are parameterized by x(a|s) = 0g,a- where O, E (A(A) refers to the vector of for some fixed state s, and E ((A))S), i.e, 0 is subject to 8,,a 2 and ExE 00.a- = 1, Vs E S, Vu E A.
Notations. Throughout this paper, we let (a, b) and a denote the inner product and the Hadamard product of two real vectors a, b, respectively.
2.2 HINGE POLICY OPTIMIZATION AND PPO-CLIP
In this section, we build on the insight offered by Proposition 2 and formally present the HPO framework. To better describe HPO, use PPO-clip an exemplary algorithm by reinterpreting the policy update of PPO-clip as a large-margin classification problem.
PPO-clip. Since the TRPO algorithm can be costly, e.g., requiring the computation of multiple Hessian-vedd vector product. (Schulman et al.) (017)) proposes two versions of PPO, PPO with KL penalty (PPO-KL) and PPO with clipped surrogate objective (PPO-clip). PPO-KL replaces the KL constraints of TRPO with KL penalty and a certain surrogate objective forms a lower bound on the performance of the policy, while PPO-clip further drops the KL penalty and instead directly clips the probability ratio. As result, the proximal term becomes inherent in the clip function. PPO-KI. and

---

Under review conference paper ICLR 2022
TRPO have been guaranteed to monotonically improve the expected total reward (Liu et al. 2019)
over a given initial state distribution. However, there remains no theoretical analysis for PPO-clip.
The original objective function of PPO-clip (Schulman ct al. 2017) is to maximize the following:
1shp (0)
Ey amwr(-le) (0. a), clip ( e. +. po
Σ SES
d
Σ AEA
<(ass) (0) clipp(p, - -
(7)
where (0) denotes the probability ratio se[e]s)
"[a]eT+ Ao the initial state distribution, (Tass) the old
policy, (a]ss) the new policy parameterized by 0, do (s) the normalized discounted state visitation frequency, and the clipping range. The function clip(ps.a (0), 1 c, 1 + <) in ( modifies the objective by removing the incentive for moving the ratio Ps,a outside of the interval [1-c, ++
Connecting PPO-clip and Hinge Loss. In PPO-clip, the policy stops being updated when the probability ratio is out of the clipping range. That is, the subgradient method keeps "pushing" the new policy away from the old one until it "improves" the old policy by a margin. This behavior coincides with the aage-margin classification problem where the classifier intends to "push" the predicted label out of margin. (Pi et al. (020) has shown that maximizing each term in the empirical average objective function of PPO-clip equivalent to minimizing hinge loss times the magnitude of advantage as follows. Specifically, the equivalence actually refers to their gradients instead of the functions themselves. The gradient of the original clipped objective is indeed the negative of the gradient of the hinge loss objective. Their objective functions differ from each other by a constan P but their policy update rules derived by the gradient methods are exactly the same.
min pin
cliplll.ppppoe (0), ())1-),.+))AGG (s,
ae
(8)
(ssign(A Ps..)) 1,
Here, Ely., fa(2;), c) a hinge loss defined as
max(0,cc3)) x fo(x;)):
(9)
where is the margin, Y4 E {-1.1} the label corresponding to the data æ,, and fx.) serves as the binary classifier. Once vifo(s;)) is larger than the margin, Eys fo(x)), will equal zero, which reflects the sample clipping mechanism in PPO-clip. Note that hinge loss has been commonly used for large-margin classification, most notably for support vector machines (Freund & Schapire [1999). From the above, in the tabular settings maximizing the objective function in (7) can be rewritten as minimizing the following loss function,
(1999).
I.(0)
Σ dw #ES
Σ (s), ((sign(A" P=,a))(())))) e,e). AEA
(10)
In practice, using the sample average to approximately maximize the above loss function as
(s"(s,)) ((sign( AA (s, a)): (0)a 1,
=(0)= = L())=
Σ
(11)
D
(s.a)ED,
where Dx is a batch of samples drawn under æ and (x, a) can be interpreted as the weight or cost associated with each sample in large-margin classification.
Remark 1. For classification problems, if one is able to find a solution (i.e., classifier) that can classify all of the training data correctly, then the "costs" are relatively unimportant compared to the label. Therefore, in the hinge loss function form, this implies that the magnitude of advantage is not important. Note that we do not take the statc-action pair with A A a) 0 into account. As shown later in the experiments in Appendix F algorithms with unweighted loss function also perform well. The "costs" in the cost-sensitive classification matter when the parameter space is not complete when the hinge loss as a cost-sensitive classification problem and extend the analysis.
reduced (nearly) zero. those cases, one can consider it
Please see Appendix for the detailed comparison of the two objectives.

---

Under review conference paper ICLR 2022
Hinge Policy Optimization. Based on the the similarity of PPO-clip objective as that to minimize a hinge loss drawn by (Pi et al,, 2020), we propose a new family of algorithms called Hinge Policy Optimization (HPO), where the general form of the loss function for policy improvement is
L(O)
Σ
weight (labell, classifier, margin).
(12)
D
[s.a]ED
Different combinations of classifiers, margins. and weights lead to different loss functions, and hence represents different algorithms in this new HPO family.
2.3 HPO WITH AN ADAPTIVE MARGIN: ALGORITHM AND GLOBAL CONVERGENCE
In this subsection, we propose an HPO algorithm with an adaptive margin, called HPO-AM. In principle, HPO-AM resembles the PPO-clip algorithm, except for that we represent the objective function in form of hinge loss, as described in (TO) instead of (7). and that is dynamic for all states during the training process, as follows. Let A (s. a) denote the estimated advantage of a state-action pair (s, a) under policy Then, we define
Ener.- T(ass)
a- min {1, Emer, T(als)
O<a< S
(13)
where 1 := {a E (s, > 0}, and and {a E AlA" a) < 0}. The notation 1_+ (I7-) represents the set of actions leading to positive (negative) estimated advantages. The adaptive clipping range is designed for the theoretical proof to "ensure the existence of an improved policy." The ratio in (13) reflects how much the current policy can be improved since HPO is designed to increase the probability of the actions with positive advantages and decrease those with negative advantages. Notably, the adaptive clipping range is in fact smaller than the constant clipping in the original PPO-clip as the adaptive clipping range is the constant times a number no greater than 1.
Our HPO-AM is shown in Algorithm below: Like PPO-clip, HPO-AM proceeds iteratively and, in each iteration 4, runs an old policy (denoted by (*) or x((()) parameterized by ((9) obtained from the previous iteration - I, and then updates the new policy into ((++1) for the next iteration. For simplicity, let (0), ( 1 and - respectively denote the above (0..(0). <g I. and I used during iteration 1. Moreover, let (s), (1) a). (s, a), and (10 a) denote y=*") (s), (s, Qx(") (s,a), (s, and Arr" a). respectively. Define the loss function of HPO-AM as
K, 1 TED, k=0
(00
(Ag ax)).
Plinn (0) p/)
1, (4)
(14)
In HPO-AM, we consider the weighted hinge loss with classifier Pa.a (0) - 1. In each iteration. HPO-AM updates the policy by the entropic mirror descent algorithm (EMDA) (Beck Teboulie 2003 to achieve a sufficiently small loss. Let 8 == min " e- (A (s.a) and set 8.9)
1 un!") is empty. specify the termination condition of EMDA, define 8(0) == min and e00) == min (E("ES))()>>g)) es (8) and choose the threshold as (1 ()) with ( E (0, 1).
Remark 2. As shown in Algorithm EMDA is applied to find a proper g(--1) that achieves a sufficiently small loss (0). While there are alternative ways to minimize the loss (0) over ((A) (S (e.g.. the projected subgradient method), leverage the exponentiated gradient scheme of EMDA to ensure that (9) remains strictly positive for all state-action pairs in each iteration t.
Before obtaining our main theorem, we make the following assumptions.
Assumption 3 (Training data and strict positivity of distributions), Suppose that the sampled train- ing data set during each ierratio of HPO-AM is sufficiently large contain all possible state-action pairs. Strict positivity of the initial state distribution pa and the initial policy n. (0) is a necessary condition for this assumption.
Assumption 4 (Correctness of the sign of the advantage function). We assume that at each iteration I, for each state-action pair. the sign of the estimated advantage the same as that of the true advantage, i.e., sign( (s, (s) sign(A(t)) (t) (s,a)), for all (s, a).

---

Under review conference paper ICLR 2022
Algorithm 1: HPO with an adaptive margin
Algorithm 2: EMDA(C(0), (ms 3. (mia)
Result: Learned policy (r0)
Result: Learned parameter 0
Initialize policy =² π (0))),, initial state
Input: Objective L(O), step sizes (m+)- threshold &, and imitial parameter Binic:
distribution μo: E (0, 1), step sizes of
EMDA {m threshold Ç (0, 1):
Initialize (01 mii O minit and 1;
fort= 0, ..... do
Collect set of trajectories r Dr under policy (* =(((1));
while ((0) & do
4
for each state do
ac(d)
Estimate ( by any policy evaluation
Find Ia.a 89, 000 for each ot
algorithms;
Let W,
(e Tl 10,1 1....11)))
Compute (0), o(t), e(t) based on Á
01++1)
(w, 0!*)):
7
and the collected samples in Dú;
Update the policy by
end
g((+1) =EMDA(E((0)) (m.)
0 = arg ( L(0);
end ()
Increment by I;
end
Remark 3. As pointed out by Assumption the global convergence of HPO requires only the correct signs of the advantage values, as will be shown in Theorem 1 below. This is one major difference from the recent global convergence results of policy gradient methods (Agarwal et al., 2019 Bhandari & Russo 2019 Mei et al. 2020), which require the true policy gradient hence the true advantage function. To address the potentially incorrect signs of the estimated advantage values, one could consider the "label-robust" version of HPO by leveraging the loss functions in the robust classification literature, e.g., (Bertsimas al. 2019: Natarajan et al. (003)) As this paper meant to take the first step toward establishing the theoretical Foundation of the proposed new policy optimization framework and PPO-clip, we leverage Assumption 3 in order rigorously establish the global convergence property of HPO.
Theorem 1 (Global convergence of HPO-AM), Suppose the step size of EMDA is diminishing and non-summable. Under HPO-AM, we have (s) (*) ast 0o, Vs E S.
The proof of Theorem is provided in the next section. Notably, the main difference between HPO- AM and PPO-clip is the choice of margin, and HPO-AM is ensured to monotonically increase all state values, not just the expected total reward as PPO-KL and TRPO. Moreover, Theorem [ ensures that all of the state values converge to the optimal value eventually.
Inspired by (Agarwal al. 2020), based the limits (s)) a) which can be shown exist via Theorem 1 we divide all actions into the following sets for each state s:
I {a E (
(s, a) 0}.
(15)
/ {a E A (00) (s, a) 0}.
(16)
1 {a E A A (5,a) <0}.
(17)
Note that ( converges an optimal policy if I is empty for all As result, I will play important role the proof of Theorem [ Section 3.2 Theorem followed by the two notable Corollaries 2 and their proofs are given in Appendix
Corollary 1. Consider state E S. For each a E I,, the probability for our agent to take action a under state converges to zero. For a E 12. the probability sum of laking these actions under state converges one. That is, nt x00) (a]s) - for all E Io and Every n! (1 (als) -> I as L oc.
Corollary 2. Consider state s E S, if there is only one action a E 1d, i.e., the optimal policy is deterministic, then we have es + 0 as f + cc.
Remark 4 (Multiple optimal actions). In the case that a state has one or more actions with the largest Q-value, any policy that assigns nonzero probability only to these actions with one in total is an optimal policy. From Corollary [ we know that the probability sum of actions belong to fo approaches one. As result, we presume that the actions described above form the set 10.

---

Under review conference paper ICLR 2022
Remark 5 (Label quality). In Theorem we obtain similar state-wise convergence result as Theorem 5.1 in (Agarwal et al. 2020). which proves asymptotic state-wise global convergence of policy gradient for softmax parameterization. In (Agarwal et al. (020), for the convergence result to be true, requires true gradient, which includes true advantage values. In addition, the calculation for true gradient is an expectation over state visitation frequency, so it needs to follow a specific distribution and sum over every state-action pair. In contrast, as stated in Remark [and Assumptions + our method only requires true advantage signs and visiting all state action pairs, and there is no need to approximate the state visitation frequency. Obviously, the requirement of accurate advantage estimate is more demanding than that of accurate advantage signs.
3 PROOF OF GLOOBL CONVERGENCE OF HPO-AM
3.1 SUPPORTING LEMMAS FOR THE PROOF OF THEOREM 1
In this section, we present the important properties of HPO-AM. which would serve as useful lem- mas for proving Theorem
Define the state-wise loss function for each state & each iteration f as [
(O.) = Σ
( a)l ((sign(A((sss))) (0.) I,e!").
(18)
aEA
Based on Assumption 2 where 0g E (AA), we can use Pa.a (0.) to represent Pa.a and further construct the above function of 0g. Regardless of the size of the state space, the loss function can be viewed as optimizing policies on per-state basis. The reason for this lies that the definition state-wise loss function is valid as long as the policy parameterization is "separable by state." That is, the policy parameters under different states are independent, e.g.. the direct tabular parameterization and the softmax parameterization. As result, we know (0) 0 if and only if i.!') (0.) for all s E S. Next, we introduce the supporting lemmas, whose proofs are in Appendix A
Lemma 1 (Strict improvement and strict positivity of policy under HPO-AM), Suppose n0 is strictly positive in all state aetteantion pairs, i.e., (9 (als) > 0, for all (s, a). Under HPO-AM, EMDA takes diminishing non-summen con-uulmalle step sizes, i.e., mk + 0 and Σk-1 Th = 30, then xe ((1-1) satisfies that x ((++1] > T00) and 1(++1) (als) > 0, for all (s,a).
Lemma 2 (Monotonicity in (als)) There exist To and T' such that for all E 17, N (1) is strictly increasing for L > To: for all a E 17 (11 (als) is strictly decreasing for >> Tí.
Lemma 3 (Lower Bound of c.)). If II is not empty set, then there exists positive constant such that e is lower bounded by c, for all TT. Lemma 4. Exerrur, d (als) a)l + a
3.2 PROOF OF THEOREM
We first prove that each state value increases monotonically. Then, under the bounded reward set- ting, we have that each state value is bounded and thus converges. For convergence to the global optimal, prove that the algorithm won't 't stop until there is action with positive advantage. The same analytical framework has also been used by (Agarwal et al. (020) to establish the global convergence of the vanilla policy gradient method. Despite the high-level resemblance, we reach the above three proof steps in a totally different way as the two approaches are fundamentally different.
From Lemma we know that in each iteration t, (1+11 and (()) satisfy the sufficient condition for state-wist wise policy improvement provided by Proposition 2 This implies that the sequence of state values is point-wise monotonically increasing, i.e., (t) Assumption and the discounted setting, we have - ب < (1) S T- The above monotone increasing property and boundedness imply convergence, i.e., (s) (s) Similarly, it can be derived that Q (s, a) + ( a), and thus (s, + (1,0 The above sets 1 1 and 1,- are well-defined, based on the limit (s))),,
(s) > (s)), Vs E S. Moreover, by

---

Under review as conference paper ICLR 2022
To establish that x0) converges to an optimal policy, is sufficient to show that I an empty set for all 8. The proof proceeds by contradiction as follows: Suppose 17 is non-empty with a4 E Ig. From Lemma 2 we have that x (a+ [s] bounded below by x:(oo) (a+ls) for some Tg for all 1 >> To. From Lemma 3 there exists a positive lower bound of cs However, Lemma shows that convergence of ((t) (+) implies that either e, converges to zero or the sum of probability mass over
all actions in I U U converges to zero. This leads to contraction, and thus completes the proof.
HPO-AM WITH ALTERNATIVE CLASSIFIERS
In the previous sections, we propose the HPO update scheme and prove the global convergence for a particular case, HPO-AM, in Theorem In this section, we go beyond HPO-AM as follows:
HPO-AM with Alternative Classifiers. Notably, the HPO update scheme can be readily extended to various other classifiers. In the following Theorem 2 we provide further result that global convergence also holds for HPO-AM with some other classifiers. The proof is given in Appendix C Theorem 2. Theorem 7 is also satisfied for HPO-AM with the following classifiers and the corre- sponding margins with a 1:
(i) HPO-AM with classifier l (a]s)) log(x(a|s)) (HPO-AM-log): Let
E = log(1 a ml, Ever, T(als)
(19)
Enery x(als)
(ii) HPPO-M with classifier v Pa.a (IIO-AMM-oot)) Let
a ming1, Emer T[als)
(20)
Exer =[als)
The classifiers in Theorem also leverage the probability ratio (o.. but in way different from that in HPO-AM in (14). Given the generality of the HPO framework, one can design HPO-AM with other customized classifiers that either does not directly involve the probability ratio or considers the power of the ratio be larger than one, such as (a(a)) =[ass) (called HPO- AM-sub) or (0)) - (called HPO-AM ----urruurre..... remains an interesting open problem how to establish global convergence for HPO with these classifiers. We provide more detailed explanations for the above two unproven classifiers in Appendix D
Remark 6.
5 PRACTICAL IMPLEMENTATION AND EXPERIMENTAL RESULTS
Recall that HPO-AM improves the policy by minimizing the loss (0) in 14). Therefore, like PPO-clip, in practice HPO-AM be readily combined with neural network parameterization and end-to-end training. We implement HPO-AM and its variants on top of the open-source RL Base- lines Zoo framework (Raffin 2020). We empirically evaluate the HPO-AM algorithms in MinAtar (Young & Tian 2019). modified version of Atari games for efficient evaluation, and conduct ablation study to hetter understand the candidate design choices HPO. Due to the space limitation, the ablation study is provided in Appendix E We compare HPO-AM variants with PPO-clip, A2C, and Rainbow in Asterix, Breakout and Freeway with million training steps under 5 random seeds. For PPO-clip and A2C, we use the tuned hyperparameters suggested by Stable Baselines 3, and we disable the entropy regularization for a fair comparison. For Rainbow, we use the open-source implementation from (Obando- CCronn & Castro 2021).
Figure M shows the training curves of the HPO algorithms and multiple popular benchmark RL methods in three different games. The results of A2C and Rainbow are consistent with their perfor- mance in the benchmark (Obando-Ceron & Castro, [202T) In (Kaiser et al. 2222), for Atari games, Rainbow is better than PPO-clip in Asterix, but worse in Breakout and Freeway, which is similar to our results in MinAtar. Figure | indicates that each classifier has its own strengths. Notably, HPO-AM and HPO-AM-rou environments. HPO-A A AM-log gets similar rewards as PPO-clip in Breakout and Freeway, but it gets fewer rewards than PPO-clip in Asterix. APPO-AM-squart is close to A2C in Asterix and Breakout, but its performance is on par with PPO-clip in Freeway. Overall, the above results demonstrate that the HPO algorithms are indeed applicable in high high-dimensional tasks.
achieve comparable or better performance than PPO-clip in the three

---

Under review conference paper ICLR 2022
40
50
35
IFD-M
:25
30
50
40
IPD Affroc
HPD AM
20
10
9m
3M
4M
2M
OM
3M
4M
Training Steps
Training Steps
Training Steps
(a) Breakout
(b) Freeway
(c) Asterix
Figure 1: Experimental results in the MinAtar environments.
6
RELATED WORK
Global Convergence of Policy Gradient Methods. One related line of recent research is on the global convergence of the policy gradient methods. (Agarwal et al. 2019: 2020) establishes global convergence results of various policy gradient approaches, including the vanilla policy gradient (with both tabular and softmax policy parametrizations) and the natural policy gradient method (with softmax policy parametrizatton). Concurrently, (Bhandari & Russo 2019) provides alter- native analysis of global optimality of the policy gradient method. (Wang et al. 2019) provides the global optimality guarantees for both the vamilla policy gradient and natural policy gradient methods under the overparameterized two-layer neural parameterization. (Mei et all, (020) establishes the convergence rates of both vanilla softmax policy gradient and the entropy entropy-regularized policy gradi-
ent. (Liu et al., 2020) further establishes the global convergence rates of various variance-reduuced policy gradient methods. Inspired by the analysis of (Agarwal et al. 2019), establish the global convergence result of the proposed HPO-AM algorithms.
Global Convergence of TRPO and PPO. Regarding TRPO, (Shani et 2020) presents the global convergence rates of an adaptive TRPO, which is established by connecting TRPO and the mirror descent method. (Liu al. 2019) proves global convergence in expected total reward for neural variant of PPO with adaptive Kullbac--Leibler penalty (PPO-KL). To the best of our knowledge, (Liu et al. 2019) appears to be the only global convergence result for PPO-KL. By contrast, our focus is PPO-clip. Given the salient algorithmic difference between PPO-KL and PPO-clip, there remains no proof global convergence to an optimal policy for PPO with a clipped objective. this paper, we rigorously provide the first global convergence guarantee for variant of PPO-clip.
RL as Classification. Regarding the general idea of casting RI. as a classification problem, it has been investigated by the existing literature (Lagoudakis & Parr [2003] Lazaric al. 2010; Farah- mand et al. 2014), which view the one-step greedy update (e.g. in Q-learning) as a binary classifica- tion problem. However, major difference is the labeling: Classification-
Approximate Policy Iteration labels the action with the largest Q value as positive; HPO labels the actions with positive advantage as positive. Despite the high-level resemblance, our paper is fundamentally different from
the prior works (Lagoudakis & Parr 2003 Lazaric et al. 20100] Farahmand et al. (214)) our paper meant study the theoretical foundation of PPO-clip, from the perspective of HPO.
7 CONCLUDING REMARKS
In this paper, we propose to rethink policy optimization methods from the perspective of state- wise policy improvement. Specifically, we propose a classification-ben policy update scheme leveraging hinge loss for policy improvement, and thereby propose new family of algorithms called Hinge Policy Optimization (HPO). This paper proves global convergence of HPO with adaptive margin (MPO-AM), which can be viewed as a PPO-clip algorithm with an adaptive clipping range. Tabular parameterization enables us to perform policy updates for each state separately: viewing each state-action pair as a training sample allows checking state-wise policy improvement, and the adaptive margin ensures the existence of improved policy. We also conduct experiments in both tabular and more complex environments for several variants of HPO-AM algorithms equipped with different classifiers and margins to corroborate their convergence hehavior and performance.

---

Under review conference paper ICLR 2022
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv:1988.0022 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64 66. PMLR, 2020.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Dimitris Bertsimas, Jack Dunn, Colin Pawlowski, and Ying Daisy Zhuo. Robust classification. INFORMS Journal on Optimization, 1(1):2-34, 2019.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint (9Xxv:900600/77000 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Amir-massoud Farahmand, Doina Precup, André Barreto, and Mohammad Ghavamzadeh. Classification-based approximate policy iteration: Experiments and extended discussions. arXiv preprint vrXiv:1407004444 2014.
Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 97(3)27772996 1999.
Kai-Chun Hu, Ping-Chun Hsieh, Ting Han Wei, and I-Chen Wu. Rethinking deep policy gradients via state-wise policy improvement. In "I Can't Believe It's Not Better!"Neurles 2020 workshop, 2020.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan. Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for Atari. In International Conference on Learning Representations, 2020.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, pp. 267-274, 2002.
Michail G Lagoudakis and Ronald Parr. Reinforcement learning classification: Leveraging mod- ern classifiers. In International Conference on Machine Learning, pp. 424-431, 2003.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Remi Munos. Analysis of a classification based policy iteration algorithm. In International Conference Machine Learning. pp. 607-614, 2010.
Timothy P. Lillicrap, Jonathan Hunt, Alexander Pritzel. Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), International Conference on Learning Representations, 2016.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimiza- tion attains globally optimal policy. Advances in Neural Information Processing Systems, 32: (0565-10576 2019.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduueed) policy gradient and natural policy gradient methods, Advances in Neural Information Processing Systems, 33, 2020.
Jincheng Mci, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp. 6820-6829, 2020.
10

---

Under review conference paper ICLR 2022
Volodymyr Mnih, Adrià 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.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in neural information processing systems, 26:1 18:1196-120, 2013.
Johan S Obando-Ceron and Pablo Samuel Castro. Revisiting Rainbow: Promoting more insightful and inclusive deep reinforcement learning research. In International Conference Machine Learning. 2021.
Chen-Huan Pi, Kai-Chun Hu, Stone Cheng, and I-Chen Wu. Low-level autonomous control and tracking of quadrotor using reinforcement learning. Control Engineering Practice, 95:104222, 2020. ISSN 0967-0661. doi:
Antonin Raffin. RL Baselines 3 Zoo.
Available at lattps://qithub. wtt.:/tttth.oooooooooooooomooott DLR-RM/ RM/
basel Saaselines3-emmmmm (innes--zee 2020.
Lorenzo Rosasco, Ernesto De Vito, Andrea Caponnetto, Michele Piana, and Alessandro Verri. Are loss functions all the same? Neural computation, 16(5):1633-1011 2004.
John Schulman, Sergey Levine. Pieter Abbeel. Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference Machine Learning. volume 37, pp. 1889- 1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06:: 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In AAAI Conference on Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin A. Riedmiller. Deterministic policy gradient algorithms. In International Conference Machine Learning, volume 32, pp. 387-395, 2014.
Richard S. Sutton. Learning predict by the methods of temporal differences. Machine Learning, 3:9-44. 44, 1988.
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Infor- mation Processing Systems, pp. 1057-1063, 1999.
Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Global
Kenny Young and Tian Tian. MinAtar: An Atari-Inspired Testbed for Thorough and Reproducible Reinforcement Learning Experiments. arXiv preprint 17X177190..03176, 2019.

---

Under review conference paper ICLR 2022
APPENDIX
A PROOFS OF THE SUPPORTING LEMMAS FOR THEOREM
A.1 ADDITIONAL SUPPORTING LEMMAS
Lemma 5 (Loss value and policy improvement). Suppose that (ols) > 0, for all state-action
pairs (s, a). Given any ( (0,1), if L. (6.) s (1-1)8%) d for s S, then have >> T!),
Proof. Recall that
(0.)= = Σ AA (s, a)l [(sign( (s (s) Pa.a (0,) 1,)
(21)
aeAA
Σ
A (s,a)) a)l (ssinn( (5, a)) Pa.a (0,) 1, (0)
(22)
aeA
2
8(4) max (0, e0 (A (s, (s, (pn (0.) 1)}
(23)
aeAA
where 22 holds by Assumption and (33 holds by the definition of 6! and the non-negativity of
hinge loss. Then, goal is to show the following claim: for each state 1 (0.) s (1 ()o% ca implies that
Ta(als) 2 (1 + cc Ja (als), a 1(0+, Ta(als) & (1 - <c )o (als), a 10-
(24)
(25)
We can prove the above claim by contradiction. If there exists action E (++ such that (a(as) < (1 + (c.)) (x(((()as))) then know 1 (0,) > 90. (8) by 23 Similarly, if there exists an action I.") > (1 ()0. Es by 23p. Therefore, by 24 25 and the sufficient condition for pol-
r!!)= such that To(als) (1 çel (1 (als). then we know
icy improvement in Proposition we know Te
Lemma 6 (Existence of policy with zero loss). Given that the tabular policy parumeterization complete, i.e., any stochastic policy can be represented the class, in each iteration t, we can always find policy my such that (0.) for all s S.
Proof. Recall that 1 == fa E A A > 0} and % == (a AlA 0}. Notice that we ignore the actions with zero advantage. We will prove that there always exists policy We such that
sign ( e))
e
(26)
for all e 100 u 1000 i.e., actions such that (T, + for all S.
For state s, take
To(als) = 0,,a = (1 (1+a + Exer." =(als)
Energo x[als) m(als), Va 19++,
(27)
<a(a)s) = 82,a = (1 a.)ar(((as))) Va -
(28)
We consider two cases, depending on whether the probability sum of actions with positive advantage is bigger than those with negative advantage, under the current state.
Case 1. If - x(als) E Ee [[a|ş] 2 1, then c!
12

---

Under review conference paper ICLR 2022
a E 10 we have
EcERs T(ass)
To (a(a)s) = (1 + a
Loelh T(ass) [((33)
2 (1+ a1+ (1+ (Tla))))))))
(29)
On the other hand, for 1 -0) we have
To(als) = (1 - a)x((|s) = (1 -.)))((()))
(30)
Case 2. If 2 - ((als)
2 -0 (a/s)
Eeeifo+ [[a[s] 1. then (1)
2een [[]a]]
For E 1604 have
En {(abs) x(a]8)
[[olss)((11 a
Exer x(als) (Taas)) (1+ ((()))
(31)
Similarly, for a E 110 we know
Exerhh [aass)
To(as)) a))(aas) 5 (1-
Ener!! T(als) (r(als)
= (1
(32)
Therefore, in both cases we have ny satisfy 26 for all a E - - and for all E S, i.c.,
(
A.2 PROOF OF LEMMA
convenience, we restate Lemma ass follows.
Lemma (Strict improvement and strict positivity of policy under HPO-AM), Suppose (9) is strictly
positive all state-action pairs, iee, x(* (als) >> O, for all (s, a). Under HPO-AM, if EMDA takes diminishing non-summable step sizes, i.e., Tд + 0 and Σ Th then x(++ satisfies that x(++1) > T(t) and z x(++1) > for all (s,a).
Proof. We start by showing that the objective loss function (,00(0) is convex and Lipschitz contin- From (8), have
(0.)
Σ A (x, a)) (siign (A (s. a)), (s.a(0.) - (1))
(33)
asA
( (s, a) max (!))
1)}.
(34)
aEA
By the fact that (0.) is linear and hinge loss is convex (Rosasco al. 2004). their position (ssign(A" (A a)), (0.)
1, ( preserves convexity, for each a E A. Being the non-
negative weighted sum of the above convex functions, ( (8.) is also convex. Hence, (0) is also convex.

---

Under review conference paper ICLR 2022
For Lipschitz continuity, follows from the fact that for any 0, 0 A(A))
mmx 6a sign( (A A (p... - 1)} max sign (1 (s)
1)31
<l(c!" sign(A(') a)) (s...) (0.)- 1)) - (c!" sign(A
1))
(35)
(0.) Pa.a (0.)
(36)
1
[ m
(37)
(als)
(als) 10.0- ma
(38)
- (als) 100 - 0.ll-
(39)
Thus, (s, a) max c - sign( (s (pss,, 1)} is Lipschitz continuous with a Lip-
schitz constant (+,0) each A. As a result, the summation i.5 (0,) over all actions [a]ss
28
M-Lipschitz continuous with M min[x [els]]
(since x for all 8, a).). Hence,
(0) is Lipschitz continuous as well.
Therefore, under a diminishing non-mulmable step size, the convergence of (0) to its minimum, which zero by Lemma 66, follows directly from the standard convergence result of EMDA shown
by (Beck & Teboulle] [2003] Theorem 4.1). Moreover, by the termination condition of EMDA spec-
ified in Algorithm we know that the returned by EMDA must satisfy (() s () (69)
which implies that ((((0) (0) = (1 c)a! Es for every state E S. Hence, by Lemma
we have
((++1) > (())
8. Then, by the termination condition of EMDA specified in Algorithm and the convergence of EMDA, we know that under HPO-AM, EMDA would terminate in finitely many iterations (i.e., finite l in Algorithm 2). for any t. Therefore, is easy to verify that (a)s) > 0 for all (8, a) by the exponentiated gradient update scheme of EMDA and striet positivity =(1)
Next, by the strict positivity (+),, we also have 80 > 0 and e >
A.3 PROOF OF LEMMA 2
For ease of exposition, we restate Lemma as follows.
Lemma (Monotonicity in (als). There exist To and Tr such that for all E It (als) is strictly increasing for > To: for all a E 15. nt (1))s))) is strictly decreasing for >> Tí.
Proof. Consider 1t. Since A (s, > O, there exists To E N such that A (s, 0 for all > To. This implies that
(cls) xx1 > (als)
(40)
i.e., (als) is strictly increasing for To-
The proof of the second claim for is similar.
A.4 PROOF OF LEMMA 3
For ease of exposition, restate Lemma as follows.
Lemma (Lower Bound of ( (0), 181 is not an empty set, then there exists a positive constant e such
that (t) is lower bounded by c, for all >> Tí.
14

---

Under review conference paper ICLR 2022
Proof. From the fact that
x (cls) =0;
(00)
(41)
acA
(42)
we have
Σ (als) Σ x(x0) (cls)A)
(43)
ag
aeI
By Assumption I have (s)) T (s, a)) S - and thus (s,a)
2n (so) (s,a)
Therefore, by Hölder's 's inequality, we have
1-7'
Σ (als) 2 Everl (<x) (als)
(44)
2R
1-9
Define A = min ae (1x0 (s.a) > 0 and Losr n (00) (a|s). Since we know that p
Exer, ((00(a))) Exer ((Tb) (a|s) by Lemma we have p Moreover, by Lemma 2
we
have 1.00- 21, 1 and (alt)((ass) < (alss for all E 1 and f Ti. This implies
PA
Σ (als)
Σ π (als) > Σ
(x) (a|s)
(45)
2R
a
for all / Ti. Therefore, by the definition of c we have
c = a min EoErjo 7 (a|s))
(46)
Eneri (a|s)
Everh (als)
2 Enerfot (a(s))
(47)
Σ
(als) (:: Σ (als)) s 1)
(48)
-
a
PA
(From inequality 455
(49)
2R
1-7
for all / TT.
A.5 PROOF OF LEMMA 4
ease exposition, we restate Lemma F as follows.
Lemma. Exertur: ur (0 (4 o) + 0 00. 00.
Proof. Convergence (s) implics that v(t+ (s) + 0, and by (4). the difference
between the value functions at and + 1 can be written as
(e++)) (8) v()(s)
1 Σ
Σ (0+1)) (ab)))))) aEA
(50)
Following the update rule given by our classification- based scheme, (1+1) satisfies both Proposi- tion [ and Proposition 2 That is,
n (++1 (s 2 ES
(51)
15

---

Under review conference paper ICLR 2022
This implies that for convergence of (s), is sufficient to show that (als') (s', , a) + 0, for all s'
d
x (++1)
(52)
Let focus on s' Simply considering the first term of the discounted state visitation frequency, we obtain
Pr(se = s/so = s, ((+11))
2 Pr(So = s/80 = n (1+1)) = 1,
(53)
and thus
x d (s) (1 -?)
of Pr(sy s|so 1((())))
M=0
2 1 21-7 %
(54)
From 52 and
54
we have
Σ n n(t+1) (sls) 0.
(55)
aEA
Combining the above result and the fact that EOE (c = 0. we have
E (als) ( 0.
(56)
We split the summation over all actions into three parts, according to limits of the advantage function, i.e.,
Σ
m 1) (a|s)
- (cbs)
aEA
Σ
(1(1-2)
1
(57)
Σ
(xr (1(11)( (c(s
aet,
Σ (r(t))(a)ss)) - - (
Let 7' = max (7. Ti,, where To, Ti are the constants defined in Lemma 2 Then, for a E U11
A (s, a) is of the same sign as A (s0) a). for all t T.
After moving the term of summation over 1 in 57 to the left hand side, by our classification-baseed scheme, we have
Σ
(a]s) (cls))
(a(t) - ( (cls))
(58)
aeA
= Σ
(at))
(cls)) Σ
(+t1)) (a|s) (clss)) (s,
(59)
aer
aE
Σ
(+(+1)
(als) (cls)) Σ
(1(1)) x (3.a)
(60)
oE
Σ
(al))) Σ (als)
(61)
aeit
aetf (d077((ss))44''( > 0.
= Σ
(62)
ur
16

---

Under review conference paper ICLR 2022
for all t T. Note that (61) follows from the same argument 24 25
By the fact that
( (a|s) (a)))) -
(63)
aEA
and
Σ (e (als) - (dlss) (s, - 0,
(64)
ae P
converges to zero. Finally, by the sandwich theorem, we have we have
58
Σ
(als)) a) O.
(65)
RELJUr
B PROOFS OF COROLLARIES 1 AND 2
B.I PROOF OF COROLLARY
I
From Theorem
!
we know that I is an empty set, for all E 8. Therefore, the result of Lemma
4
becomes
Σ
a) + 0.
(66)
eEtT
This implies that either e0 0 or Exer, (als) By Lemma 2 1 2 15 for all & Ti. This implies that Σne E (als) )) > Emer, (als), for all Ti. Moreover, we have that e - implies Σ -nginn (alss + and thereby implies Emer, x (a|s) - 0, i.c.,
Emer; 71 (als) + is necessary condition for e 0. Hence, we know
Σ oE
1 (als) - 0
(67)
regardless of the behavior of e
By combining E.Er, 7(% (a|s) and the fact that I empty, we have
Σ
7d +.
(68)
10
B.2 PROOF COROLLARY 2
Since there is only one action a E I and I is empty, for all a' E A {a), we have a' I, By Lemma 2 there exists Tj such that for all > Tr, (s, a') 0, for all a' A) (a). This implies
that (s) > for E A {a).
Tı, ie., for all Tr we have 100+ and e !!")_ for all
Then, by Corollary
I as t + 00
Σ n (cls))
Σ
(als) +1
(69)
aE
ac
Σ (0 (a|s) Σ (als) + 0.
(70)
act5
Σ Σme (als)
Hence, by definition, e = mmmf11, y -. ((0))133) - 0 as + 00.
17

---

Under review conference paper ICLR 2022
C PROOF OF THEOREM 2
For ease of exposition, we restate Theorem 2 as follows.
Theorem. Theorem also satisfied for the following classifters with corresponding margins with
0 < a Ca<L 1:
(i) For classifier log(mo((ass) - log(T((ass)) les
c log(1 min(1, Ener: ((a)s) Enery+ =(1l8) 1).
(71)
(i) For classifier v (l))( - 1. let
EvEr T(als) Exelz 7 ((ass)
1 a min
(72)
Proof. The proof of Theorem follows exactly the procedure that of Theorem D We sketch the proof for the two different classifiers: To begin with, we extend the supporting lemmas to HPO-AM with these two alternative classifiers:
Notice that by using exactly the same argument as Lemma 5
we have that under these two clas-
sifiers, strict policy improvement Re >> x(1) is guaranteed if (0.) I (1 (1-c)= e for all where Ç E 10.
Regarding Lemma 6 the policy Hy we construct in the proof of Lemma 6 also achieves zero loss for the alternative loss functions induced by the two alternative classifiers.
Regarding Lemma 1 since both the logarithm function and the square root function are concave, and hinge loss is convex and non-increasing, their compositions preserve convexity (Boyd et al. 2004). Moreover, by the clipping property of hinge loss, we also know that in each iteration (..) is Lipschitz continuous under the two classifiers log(Ps.. and (0.)) 1-1 if the policy x(1) is strictly positive in all state-action pairs. Hence, f.(0) also remains Lipschitz continuous. By using the same argument convergence of EMDA that in Lemma [ it easy to verify that (t++1) > (t)) and 7 (als)) > 0 for all (s, () if EMDA takes diminishing and non-summable step sizes.
Based on the extended version of Lemma and Lemma for these two alternative classifiers and Assumptions 4 we know that under the design of HPO-AM, strict policy improvement (i.e.,
x (t++1) > x (()) and strict positivity of (1) are satisfied in every iteration Therefore, the limits ((c), Q(s0), and (o)) exist by monotone convergence theorem.
Lemma 2 does not use the specific form of the classifier and hence still holds under the two alternative classifiers.
For the two alternative classifiers, Lemma can be readily extended by adapting the argument in
(46)- to the e defined in (19) and (20 Similarly, Lemma 4 can be extended by adapting the
inequalities in (61--62) 62) to the corresponding eg defined in (19) and (20).
Since all the lemmas hold for these alternative classifiers and their corresponding eg, we can com- plete the proof by showing contradiction similar that in Theorem
D UNPROVEN CLASSIFIERS
In Remark we identify two other classifiers, To (a(aass)T((e (()as) and (0)) 2 -1, which we cannot directly apply similar proof Theorem

---

Under review conference paper ICLR 2022
First, an intuitive reason for the classifier mo(als) (a]s) is explained as follows. To ensure the exis-
tence of improved policy, we must set minge. { [s] -a mimmin((1 - s(u]+)
- x(als) ).0
Note that there is additional term in front, compared to the margin we use in Theorem I before. Due to multiplying this additional term, the margin is bounded by the minimum probability of action. We cannot use Lemma 3 to give lower bound for (t) since min.g A (a(() will prob-
(als)}
ably approach zero f + To be more specific, it makes the probability of all the other actions
increase/decrease slowly, when there exists an action with extremely small probability. Without Lemma 3
we are not able to prove the global convergence by contradiction.
Second, for the classifier (0)) - 1, although we can prove the existence of improved policy by
- m(ale)
defining the margin 6, (1 min(1, E.er71 F[a|o] })² 1, our loss function is longer
convex. Without convexity, the EMDA method is not guaranteed to converge to the optimal value. We leave it as interesting open question of whether not this problem can be solved by using a non-convex optimization method.
E ABLATION STUDY OF HPO-AM VIA EXPERIMENTS TABULAR ENVIRONMENT
E.I GRIDWORLD ENVIRONMENT
For a principled discussion, we use a x gridworld similar to that in (Sutton 1988
Example 4.1),
where optimal policy and all the value functions can be analytically obtained. Regarding the gridworld environment, there are four available actions (up, down, right, left) and terminal state located at the top-left corner. At each non-terminal state, the reward is either 1.0 or - -1.2 with equal probability, for all the actions. All the state transitions deterministic.
E.2 EXPERIMENTAL SETTINGS
In the gridworld environment, all the policies in our experiments are trained for 40000 episodes un- der fixed random seeds. All the source code is supplements aareetrry... zip the supplementary materials. Our code of the HPO algorithms is extended from an open-source PyTorch example") and the gridworld environment is modified from open-source project, -nnddwrwwwor""
E.3 NEURAL NETWORK MODEL
Our neural network model is composed of three layers: two fully connected layers and one output layer, which includes two output heads for the value and the action. The two fully connected layers with 32 hidden units are shared for the output heads. The learning rate and the discount factor (7) are set to be 0.001 and 0.99, respectively. The input of the model is one-hot vector to represent the grid position.
E.4 ABLATIONS FOR THE WEIGHT AND MARGIN
Recall that the loss function of HPO in 12 involves three critical components: classifier, weight, and margin. Regarding the classifier, we evaluate five variants of HPO-AM with the classifiers. including: (i) Pa.a (0) 1. (the standard HPO-AM); (ii) log(
log( ( (a[ss) (HPO-AM-log), (iii) Ps (0) (HPO-AM-root); (iv) ma(a) s) <<ass) (Hu)-AM-suh); (v) (ps.a (0))² - (HPO- AM-square). Regarding the weight and the margin, we consider four different scenarios, including: (i) adaptive and |Á(t) (*k, 0x)l as the weight (denoted as WAE); (ii) adaptive e, and a constant weight of (denoted as AE); (iii) constant c, = 0.1 and ( a+)] as the weight (denoted as WCE); (iv) constant e, 0.1 and a constant weight of (denoted as CE). For the constant margin, follow the popular setting of PPO-clip to set e 0.1. Those methods implemented with
learning/actor wtt.ttoorrrriiitry....
19

---

Under review conference paper ICLR 2022
tabular policy or a neural network policy. Under all the algorithms, the policy trained for 40000 episodes under 10 random seeds.
E.5 TRAINING CURVES
We show the L1 norm between HPO-AM policy with the optimal policy in Figure 2 and Figure S First, evaluate the five variants of HPO-AM under tabular parameterization with true advantage values in F This experiment is meant to verify the convergence behavior of HPO-AM.
HADAMin
L1 Norm
L3 Norm
oot
COXE
0K. St 10c 134 20k 25k sok 452
3k. 30k Lbi 23k, 256 ack Sok
GE St Lik 15k 20k zok s0k 400
Sk. 10k 15k 20k, 25k a0k 2ok 40k
(a) WAE
(b) AE
(c) WCE
(d) CE
Figure 2: Experimental results of tabular policies in the gridworld environments.
We further implement the five variants HPO-AM using neural networks with estimated advantage values. Figure 3 reveals the mean value and the standard deviation of L1 norm. Most of the five algorithms can converge within reasonable number of training episodes, while some of HPO-AM- sub with WAE and WCE settings cannot converge.
HEO-M rost
AM
komm
Rom
hom
1800 400-44-0000 ac.
26
20k
421
60x
10k
100c
06
20k
45%
828
D0c
1000
28
20k
422
601
I0k
100c
D6
20k
45%
00:
1024
(a) WAE
(b) AE
(c) WCE
(d)
Figure 3: Experimental results of neural network policies in the gridworld environments.
E.6 DISCUSSIONS
We measure the L1 norm between the policy learned under each variant of HPO-AM with the op- timal policy the performance criterion. First, we evaluate the five variants of HPO-AM under tabular parameterization with true advantage values. This experiment is meant to verify the con- vergence behavior of HPO-AM. As expected, HPO-AM, HPO-AM-log and HPO-AM-root indeed converge to the optimal policy (in a small number of training episodes). Interestingly, HPO-AM-sull and EIPO-AM-quart which are based on the two weak classifiers without theoretical guarantees as discussed in the previous section, still converges. These results serve as empirical insights into the convergence analysis for these two classifiers. We further implement the five variants of HPO-AM using neural networks with estimated advantage values. Most of the five algorithms can converge within a reasonable number of training episodes. We also observe that the HPO-AM algorithms appear converge slightly faster than PPO-clip. This manifests the potential of the proposed HPO framework in opening up new class of promising RL algorithms.
DETAILED CONFIGURATIONS OF THE EXPERIMENTS IN MINATAR
F.I EXPERIMENTAL SETTINGS
For the experiments in the MinAtar environments (Young & Tian 2019), we implement HPO-AM and its variants with WAE setting on top of the open-source RL Baselines 3 Zoo framework (Raf- hin 2020). Recall the classifier is a critical component for the loss function of HPO in (12). we
evaluate five variants of HPO-AM with the classifiers, including: (i) Ps.a 1, (the standard
20

---

Under review conference paper ICLR 2022
HPO-AM); (it) (a]())(a)s)) lo)()(a(s)) (HPO-AM-log): (ii)) Pe,a (HPO-AM-root) (iv) (e(a]s) x[als) (HPO-AM-sut)) (v) (0)) -19-1o (HPO-AM-squaa In MinAtar, the obser- vation encoded by 10 x n state representations, where each of the channels corresponds a game-specific object. For example, in Breakout, the game-specific objects are ball, paddle and brick. We compare HPO-AM variants with PPO-clip, A2C, and Rainbow in Asterix, Breakout and Freeway with million training steps among random seeds. The source code is in suppl eepentarr zip of the supplementary materials.
F.2 NEURAL NETWORK MODEL
The network model of HPO-AM is composed of two parts: a shared feature extractor and an output layer (including two sets of output heads, one for the Q-value and the other for the policy). For the MinAtar experiments, the feature extractor consists of one 2D convolution layer (with 3 3 kernel and 16 output features) and one fully connected layer with 128 hidden units. Regarding A2C and PPO-clip, we set the entropy coefficient to O to disable the entropy regularization for a fair comparison and follow the configuration suggested by RL Baseline3 Zod for the of the hyperparameters. Table | summarize the hyperparameters for MinAtar and HPO-AM variants use the same setting. For each MiniAtar game, we run the experiments under 5 random seeds with 5,000,000 training steps for all methods.
Table 1: Parameters for the MinAtar experiments (lin 2.5e-4 means that the learning rate decays linearly from 2.5 x 10-4 to O).
Hyperparameters
HPO-AM
PPO-clip
A2C
n.envs
8
16
n_steps
64
128
5
batch
256
512
80
n. eeepchhs
10
learning rate
lin 2.5e-4
lin 2.5e-4
7e-4
vř coef 0.8
0.5
0.5
0.5
G COMPARISON OF THE CLIPPED OBJECTIVE IN PPO-CLIP AND THE HINGE LOSS OBJECTIVE OF HPO
Recall that the original objective of is
I clip(() Eondy
(11)) ( min (p (0)A"(( (s, a), -1
(73)
where Pa.a = matals) In practice, (0) is approximated by the sample average as >[a[s)
(. s0 (.) DDa
1
Σ (s.)eD,
())
(74)
1
Σ
(s. min(px.00) sign clip(ps..()) c,
sign( 17 (s a))
|1a
(s,a)DD;
W. (A)
(75)
http://://ggtthhh...o///.///// nnea3-200 /rees-//oo//lld///aateee///eeeee
21

---

Under review conference paper ICLR 2022
Note that W (0) can be further written
I+e
if (s, > 0 and (0,) 2 1 +
Pa.a(0)
if (s, > 0 and (0) 1 + e
W (0)
(0)a
if (s, < 0 and Ps.o > 1
if (s, < and Pa,a (8) S 1 E oothewwise
Recall from 11 that the loss function of HPO takes the form
((00) ((0) Da
Σ
(x) max {0, (As (0) 1) sign ( (x,a)))
(76)
(s,a)ED,
(.)
Similarly, (0) can be further written as
if (s, > 0 and Pa.a (0) 2 1 +
(0) + +e)
if (s,a) > 0 and Ps.a (0) < 1
W (0) =
(0) - -1
if (s,a) < 0 and Pa.a (0) > 1
if A (s.a) < 0 and Ps.a (0) S 1
otherwise
Therefore, it easy to verify that (. - (0) only differ by constant with respect to This also implies that VoL (V).
22


Reviews:
[{"review_id": "npVpe0CwIBp", "reviewer": "Reviewer_FV8P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Please list both the strengths and weaknesses of the paper. When discussing weaknesses, please provide concrete, actionable feedback on the paper.\n\n**Originality:** To the best of my knowledge, this is the first formalization which allows a theoretical analysis of PPO-clip, albeit, as highlighted in the paper, not the first formalization of reinforcement learning as a classification problem.\n\n**Significance:** Since PPO-clip is one of the most commonly used policy gradient algorithms, a theoretical analysis of the approach is a relevant contribution to the reinforcement learning community.\n\n**Rigour:** The paper is built upon common tools and I could not find any factual errors in the proofs.\n\n**Strengths**\n\n- The paper provides a nice bridge between the existing theoretical tools for the analysis of policy gradient algorithms and the popular PPO-clip algorithm.\n- The presentation of the theoretical results is quite clear.\n\n**Major Concerns**\n\n- I do not fully understand the justification behind the use of the specific EMDA approach as a subroutine in the algorithm. Is this essential for proving convergence of the resulting algorithm? Or would an alternative, perhaps simpler, procedure yield convergence as well albeit with a different proof scheme?\n- The fact that the experimental results are relegated in Appendix is quite disappointing. Albeit they are in small experimental settings and the results are not stellar, they provide a nice additional perspective on the proposed framework. In my opinion, it could take the space now reserved to the proof of Theorem 1, which generally follows (Agarwal et al. 2020).\n- The simple tabular policy representation used in the theoretical analysis burns some of the bridges between theory and practice that the paper is trying to build, since PPO-clip is traditionally associated to neural function approximators. What worries me the most is how the optimality in Definition 1-2 transfers to the setting with function approximation, in which this kind of sorting among policies is often unfeasible.\n\n**Minor Concerns**\n\n- Before Equation (8), it is written that the hinge loss and the PPO-clip gradients differ by a constant, which is not correct, given that the advantage depends on states and actions.\n- Why is Equation (8)-(9) repeated?", "summary_of_the_paper": "The paper proposes hinge policy optimization, a new theoretical framework for interpreting policy gradient algorithms as classification problems to be solved with a hinge loss. In this perspective, the sign of the advantage function becomes the label, and the difference in action probabilities between policy after and before an update becomes the classifier's output. The paper shows the equivalence between such a formulation and the popular PPO-clip objective and provides global converge guarantees on the blueprint of (Agarwal, 2020). It also proposes a range of policy optimization algorithms, depending on the details of the classification algorithm that is used, and empirically evaluates some of them.", "summary_of_the_review": "The paper mostly achieves its goal, which is to provide a theoretical justification for PPO-clip. I currently lean towards acceptance, although the paper suffers from some presentation issues and imperfect justification of some algorithmic/theoretical design choices.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OCYqlafhAiK", "reviewer": "Reviewer_PyUp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "I think this is a very interesting paper that improves a commonly used algorithm and provides both theoretical and empirical evidence that support using this modified algorithm.\nThe paper is very well-written both in terms of how the main parts of the paper are easy to follow, and the appendix section is very detailed.\n\nBesides minor corrections and clarifications below, the only \"weakness\" is that PPO is a heavily used algorithm and the empirical results here are not convincing enough (only a part of the mini atar benchmark and a really small toy problem). However, in my opinion, the theoretical arguments provide enough value for the RL community so even though a more through survey would be valuable for practitioners, the current contents of this work are already enough for a good paper.\n\nMinor issues:\n1. eq 8 = eq 9?\n2. In \"Connecting PPO-clip and Hinge Loss\" section: In practical -> In practice (?)\n3. Regarding:\n\"and |Aπ (s, a)| serves as the weight of the sample.\" \nI think you meant that A could be interpreted as the weight, but on initial read I thought you added an additional multiplicative term of A. Maybe rephrase to clarify it is not an additional modification, but an interpretation of an existing element.\n4. Eq 13: what happens if all the advantages for a given state are 0? (I suspect that the denominator should be greater or equal to 0, since at least one action is non-negative)\n5. Could you clarify the following statement in assumption 3:\n\" Strict positivity of the initial state distribution µ0 and the initial policy π (0) is a necessary condition for this assumption\"\n6. In remark 3: \n\"we leverage Assumption 3 in order to rigorously\" - assumption 4? assumptions 3 and 4? assumption 3 alone seems out of context. And you need both the data assumption and the advantage sign assumption to prove your claims, right?\n7. Eq 15: if I understand correctly, this expression is for the true advantage in the limit, which should be the empty set if the algorithm converges. You don't mention this expression in the remarks directly below. I found it confusing that you don't mention it at all, you probably meant to present it for completeness. It might be helpful to hint on its role in the text as well.", "summary_of_the_paper": "This paper suggests a generalization to the commonly used PPO(-clip) algorithm, by analyzing the loss function from a state-wise perspective and generalizing the policy-ratio clip objective into a hinge loss formulation. The main contributions of this paper are:\n(1) They introduce a family of algorithm that includes PPO-clip\n(2) Show convergence results for these algorithms (under less strict assumptions than previous works)\n(3) They suggest an instance from the suggested family of algorithms  - HPO-AM\n(4) They provide some empirical evidence (specifically on some of the mini atar games) showing this algorithm is competitive with other commonly used algorithms.", "summary_of_the_review": "I found this paper to be valuable to the deep-RL community as it presents an interesting generalization to a commonly used algorithm with theoretical justifications. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LWI-_btOr86", "reviewer": "Reviewer_vtrj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Pros:\n\n-  the paper gives interesting theoretical insight linking PPO-clip with a large margin classification and theoretical analysis of a new group of reinforcement learning as classification methods. \n\nCons:\n\n(1) while the reviewer appreciates the paper is mostly theoretical, it might be a good idea to bring some experimental analysis into the main text to show the performance of the method on a range of benchmark problems, especially given that the experimental analysis is already presented in the appendix. While the proofs are important part of the work, are they more essential for the narrative than the experiments? There is no right or wrong answer on this question, this question is more about gaining insight into why it has been done this way. \n\n(2)restrictive assumptions of the proposed method: “Assumption 4. We assume that at each iteration t, for each state-action pair, the sign of the estimated advantage is the same as that of the true advantage. “;   \"Assumption 2. Tabular policies” . Although it makes sense to  use assumption 4 for the sake of theoretical analysis, it would be good to have some evidence whether it actually could hold in any experimental scenarios. The reviewer wonders whether it is possible to show some experimental analysis in the appendix showing whether the assumption 4 holds during the training (and how it is reflected in training dynamics)?\n\nOther comments:\n\n(1) Page 5: Entropic mirror descent: could the authors give some references?\n\n(2) In the experimental section of the appendix, it would be useful to see the grid world tasks compared with a well-known baseline the same way as the MinAtar problems are. It would be also useful to see more environments to show the advantages and limitations of the proposed idea on more scenarios. ", "summary_of_the_paper": "The paper describes a new family of methods, called Hinge Policy Optimisation (HPO), generalising over proximal policy optimisation algorithm with a clipped surrogate objective (PPO-clip).", "summary_of_the_review": "Pros: novel idea and interesting analysis of reinforcement learning as classification\nCons: restrictive assumptions of the theoretical analysis; the experimental analysis could be given more space given that it actually exists in the appendix. \nStarting from 5, but happy to update the scores to acceptance if there's a convincing answer on the cons during the rebuttal. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HGFy4GX4r58", "reviewer": "Reviewer_PJFP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "\nStrengths:\nThe writing of the paper is clear. The presentations of the theorems are easy to understand. \nThe interesting part of the paper is to generalize PPO to other classifiers. I suggest the author focus more on it.\n\nWeaknesses:\nThe major theoretical contribution is the proof of the convergence of PPO. However, in my view, this paper contributes little to understanding PPO. I give my reasons as follows.\n- The author proves the result by introducing a very strong assumption (Assumption 3), which in fact includes two assumptions.\n\t- First, the initial state distribution is strictly positive; thus the policy is possible to sample the state-action pair over the entire space. However, this is almost impossible in practice. This implies that the result of this paper can contribute to a very limited range of tasks.\n\t- Second, the sampled training dataset are sufficiently large to cover all possible state-action pair. \n- The key of PPO is the clipping technique. This is the key to ensuring the performance is bound. In my view, the theoretical result in this paper (Theorem 1) still holds if one removes the clipping function. If I'm right, then this paper contributes little to understanding PPO.\n- The author claim that \"no additional constraints, such as the KL divergence constraint used in TRPO, are needed to ensure policy improvement\". By this claim, do you think that PPO can remove the clipping technique? How do you think the effect of policy constraint in TRPO (KL divergence constraint) and PPO (clipping technique)?\n\nOverall, in my view, the contribution of the paper is to prove the performance improvement of the objective function without clipping technique (by some very strong assumptions).\n\n", "summary_of_the_paper": "\nThis paper reinterprets the theory of PPO-clip based on the hinge policy optimization. They prove the global convergence of PPO by introducing some assumptions. Besides, they generalize the algorithm to a new family of policy-based algorithms by regarding the policy as a generalized classifier.", "summary_of_the_review": "The paper does a good job in sharing new insights of policy optimization, and in connecting the policy optimization with classification. However, the two main claimed contributions are somewhat weak.\nRethinking policy improvement (Proposition 1 and 2) is not the original idea of this paper. Reinterpreting PPO by hinge loss is also not the idea of this paper. At the same time, the improvement analysis is based on some very strong assumptions. Therefore, I vote for rejection for this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agreed that analysis of PPO is interesting. 
During the discussion, however, there was an agreement that the current work is too thin in novelty and contribution: it provides only convergence analysis under very strong assumptions, and heavily builds on techniques from prior works. Meanwhile, for conventional policy gradient, recent works provided convergence rates.
As one reviewer pointed out - this work does not further our theoretical understanding on why PPO is better than vanilla policy gradient, as all the established results hold for policy gradient, even with less assumptions.
I encourage the authors to strengthen their paper by relaxing Assumption 4 (perhaps based on the robust classification idea raised in the discussion), and by further providing rate results.
Decision: Reject