Year: 2021

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.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has served as a powerful framework for achieving optimal sequential 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, iteratively searches for an optimal policy by alternating between a policy evaluation step and a policy improvement subroutine. Most of the popular policy optimization approaches, including the policy gradient methods (Sutton et al., 1999; Mnih et al., 2016; Silver et al., 2014; Lillicrap et al., 2016), Trust Region Policy Optimization (Schulman et al., 2015), and Proximal Policy Optimization (PPO) (Schulman et 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 convergence 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 to 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 decision processes (MDPs). We start by identifying two useful sufficient conditions for state-wise policy improvement and thereafter pinpoint that improvement can be achieved based solely on the sign of the advantage function. Based on this insight, we propose Hinge Policy Optimization (HPO) by connecting state-wise policy improvement to solving a 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 in a 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 a whole new family of policy-based RL algorithms. Interestingly, the popular PPO algorithm with a surrogate
clipped objective (PPO-clip) can be shown to be a special case of HPO with a specific type of classifier. Given the policy improvement property of the proposed classification-based 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 is meant to provide a clear picture of the RL algorithms in the new HPO family with 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:
• We propose HPO, a new policy optimization framework where the policy update is built on statewise policy improvement via hinge loss. The members in the HPO family share a 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 a special case in this family.
• This paper is the first ever that can prove state-wise policy improvement and global convergence for a variant of PPO-clip algorithm1. Specifically, we first present a variant of the PPO algorithm with an adaptive clipped objective, which can be viewed as an HPO algorithm with adaptive margin, called HPO-AM. We prove the convergence to an optimal policy for HPO-AM, and proceed 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 E and F).

heading: 2 MAIN RESULTS
text: In this section, we first review the theoretical background about RL and view PPO-clip update as a classification problem. Then, we establish global convergence for the proposed HPO-AM.

heading: 2.1 BACKGROUND
text: A discounted Markov Decision Process (MDP) is defined by the tuple (S,A,P, r, γ), where S is a finite state space,A is a finite action space, P : S ×A×S → [0, 1] is the state transition probability matrix, r : S × A → R is the reward function, and γ ∈ (0, 1) is the discounted factor. A stochastic policy π : S → ∆(A) specifies the action distribution based on the current state, where ∆(A) is the probability simplex over A, i.e., ∆(A) = {x ∈ R|A| | x0 + ... + x|A|−1 = 1, xi ≥ 0, ∀i = 0, ..., |A| − 1}. Given any policy π, the state value function V π , the state-action value function Qπ , and the advantage function Aπ are defined as follows.
V π(s) := E at∼π(·|st),
st+1∼P(·|st,at)
[ ∞∑ t=0 γtr(st, at) ∣∣∣s0 = s] , (1)
Qπ(s, a) := E at∼π(·|st),
st+1∼P(·|st,at)
[ ∞∑ t=0 γtr(st, at) ∣∣∣s0 = s, a0 = a] , (2)
Aπ(s, a) := Qπ(s, a)− V π(s). (3) Define dπs (s ′) := (1 − γ) ∑∞ t=0 γ t Pr(st = s ′|s0 = s, π) as the normalized discounted state visitation frequency, which represents the probability of visiting state s′ in a trajectory of π, given that s0 = s. With the above definition, (Kakade & Langford, 2002) quantified the difference in performance between two policies as follows. Given policies π1 and π2,
V π1(s)− V π2(s) = 1 1− γ ∑ s′∈S dπ1s (s ′) ∑ a∈A π1(a|s′)Aπ2(s′, a). (4)
1Regarding the convergence of PPO, (Liu et al., 2019) proves global convergence in expected total reward for a neural variant of PPO with adaptive Kullback-Leibler penalty (PPO-KL). Given the salient algorithmic difference between PPO-KL and PPO-clip, to the best of our knowledge, there remains no proof of global convergence to an optimal policy for PPO-clip.
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 1 (Partial ordering over policies). Let π1 and π2 be two policies. Then, π1 ≥ π2, called π1 improves upon π2, if and only if V π1(s) ≥ V π2(s), ∀s ∈ S. Moreover, we say π1 > π2, called π1 strictly improves upon π2, if and only if π1 ≥ π2 and there exists at least one state s such that V π1(s) > V π2(s).
Definition 2 (An optimal policy). A policy π∗ is said to be an optimal policy if π∗ ≥ π′, for every policy π′. Moreover, we let V ∗(s) denote the optimal value of each state s, i.e., V ∗(s) = V π ∗ (s).
We first introduce two sufficient conditions for state-wise policy improvement in Propositions 1-2. These two conditions have been identified by (Hu et al., 2020, Section 3.1). Proposition 1. Given policies π1 and π2, π1 improves upon π2 if the following condition holds:∑
a∈A π1(a|s)Aπ2(s, a) ≥ 0, ∀s ∈ S. (5)
Proposition 2. Given policies π1 and π2, π1 improves upon π2 if the following condition holds:
(π1(a|s)− π2(a|s))Aπ2(s, a) ≥ 0, ∀(s, a) ∈ S ×A. (6)
Proposition 1 holds for the following reason: Since all dπ1s (s ′) are non-negative, all values in (4) are non-negative, and hence π1 improves upon π2. Proposition 2 can be derived directly from Proposition 1 and the fact that ∑ a∈A π2(a|s)Aπ2(s, a) = 0, ∀s ∈ S.
Notably, Proposition 2 offers 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 as 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 can draw an analogy between (6) in Proposition 2 and the training of a linear classifier: (i) The state-action pair serves as the feature vector of a training sample; (ii) The sign ofAπ2(s, a) plays the role of a binary label; (iii) π1(a|s)− π2(a|s) resembles the prediction of a linear classifier. In the next section, we substantiate this insight and present the proposed HPO framework.
In 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, it holds naturally that there exists a positive constant R = sup(s,a)∈S×A|r(s, a)| > 0. Assumption 2 (Tabular policies). Policies are parameterized by π(a|s) = θs,a, where θs ∈ ∆(A) refers to the vector of θs.· for some fixed state s, and θ ∈ ∆(A)|S|, i.e., θ is subject to θs,a ≥ 0 and∑ a∈A θs,a = 1, ∀s ∈ S, ∀a ∈ A.
Notations. Throughout this paper, we let 〈a, b〉 and a◦ b denote the inner product and the Hadamard product of two real vectors a, b, respectively.

heading: 2.2 HINGE POLICY OPTIMIZATION AND PPO-CLIP
text: In this section, we build on the insight offered by Proposition 2 and formally present the HPO framework. To better describe HPO, we use PPO-clip as 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-vector product, (Schulman et al., 2017) 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 a result, the proximal term becomes inherent in the clip function. PPO-KL and
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 et al., 2017) is to maximize the following: Lclip(θ) = Es∼dπµ0 ,a∼π(·|s) [ min{ρs,a(θ)Aπ(s, a), clip(ρs,a(θ), 1− , 1 + )Aπ(s, a)} ]
= ∑ s∈S dπµ0(s) ∑ a∈A π(a|s) min{ρs,a(θ)Aπ(s, a), clip(ρs,a(θ), 1− , 1 + )Aπ(s, a)}, (7)
where ρs,a(θ) denotes the probability ratio πθ(a|s) π(a|s) , µ0 the initial state distribution, π(a|s) the old policy, πθ(a|s) the new policy parameterized by θ, dπµ0(s) the normalized discounted state visitation frequency, and the clipping range. The function clip(ρs,a(θ), 1 − , 1 + ) in (7) modifies the objective by removing the incentive for moving the ratio ρs,a(θ) outside of the interval [1− , 1+ ]. 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 large-margin classification problem where the classifier intends to “push” the predicted label out of a margin. (Pi et al., 2020) has shown that maximizing each term in the empirical average objective function of PPO-clip is equivalent to minimizing a 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 constant2, but their policy update rules derived by the gradient methods are exactly the same.
∂
∂θ min{ρs,a(θ)Aπ(s, a), clip(ρs,a(θ), 1− , 1 + )Aπ(s, a)}
=− ∂ ∂θ |Aπ(s, a)| `(sign(Aπ(s, a)), ρs,a(θ)− 1, ).
(8)
Here, `(yi, fθ(xi), ) is a hinge loss defined as
max{0, − yi × fθ(xi)}, (9) where is the margin, yi ∈ {−1, 1} the label corresponding to the data xi, and fθ(xi) serves as the binary classifier. Once yifθ(xi) is larger than the margin, `(yi, fθ(xi), ) 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,
L(θ) = ∑ s∈S dπµ0(s) ∑ a∈A π(a|s)|Aπ(s, a)| `(sign(Aπ(s, a)), ρs,a(θ)− 1, ). (10)
In practice, using the sample average to approximately maximize the above loss function as L(θ) ≈ L̂(θ) = ∑
(s,a)∈Dπ
|Aπ(s, a)| `(sign(Aπ(s, a)), ρs,a(θ)− 1, ) |Dπ| , (11)
where Dπ is a batch of samples drawn under π and |Aπ(s, 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 state-action pair with Aπ(s, a) = 0 into account. As shown later in the experiments in Appendix E, algorithms with unweighted loss function also perform well. The “costs” in the cost-sensitive classification matter when the parameter space is not complete or when the hinge loss is not reduced to (nearly) zero. In those cases, one can consider it as a cost-sensitive classification problem and extend the analysis.
2Please see Appendix G for the detailed comparison of the two objectives.
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(θ) = 1 |D| ∑
(s,a)∈D
weight× `(label, classifier,margin). (12)
Different combinations of classifiers, margins, and weights lead to different loss functions, and hence represents different algorithms in this new HPO family.

heading: 2.3 HPO WITH AN ADAPTIVE MARGIN: ALGORITHM AND GLOBAL CONVERGENCE
text: 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 a form of hinge loss, as described in (10) instead of (7), and that is dynamic for all states s 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
πs := α ·min { 1, ∑ a∈Iπ−s π(a|s)∑ a∈Iπ+s π(a|s) } , 0 < α < 1, ∀s ∈ S, (13)
where Iπ+s := {a ∈ A|Âπ(s, a) > 0}, and Iπ−s := {a ∈ A|Âπ(s, a) < 0}. The notation Iπ+s (Iπ−s ) represents the set of actions of s 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 1 below: Like PPO-clip, HPO-AM proceeds iteratively and, in each iteration t, runs an old policy (denoted by π(t) or π(θ(t)) parameterized by θ(t)) obtained from the previous iteration t − 1, and then updates the new policy into π(t+1) for the next iteration. For simplicity, let ρ(t)s,a(θ), (t) s , I (t)+ s , and I (t)− s respectively denote the above ρs,a(θ), πs , I π+ s , and I π− s used during iteration t. Moreover, let V (t)(s), Q(t)(s, a), A(t)(s, a), and Â(t)(s, a) denote V π (t)
(s), Qπ (t) (s, a), Aπ (t) (s, a), and Âπ (t) (s, a), respectively. Define the loss function of HPO-AM as
L̂(t)(θ) = ∑ τ∈Dt Kτ∑ k=0 |Â(t)(sk, ak)|` ( sign(Â(t)(sk, ak)), ρ (t) sk,ak (θ)− 1, (t)sk ) . (14)
In HPO-AM, we consider the weighted hinge loss with classifier ρs,a(θ) − 1. In each iteration, HPO-AM updates the policy by the entropic mirror descent algorithm (EMDA) (Beck & Teboulle, 2003) to achieve a sufficiently small loss. Let δ(t)s := mina∈I(t)+s ∪I(t)−s |Â
(t)(s, a)| and set δ(t)s =∞ if I(t)+s ∪ I(t)−s is empty. To specify the termination condition of EMDA, define δ(t) := mins∈S δ(t)s and (t) := min
s∈{s′∈S| (t) s′ >0}
(t) s , and choose the threshold as (1− ζ)δ(t) (t), with ζ ∈ (0, 1).
Remark 2. As shown in Algorithm 1, EMDA is applied to find a proper θ(t+1) that achieves a sufficiently small loss L̂(t)(θ). While there are alternative ways to minimize the loss L̂(t)(θ) over ∆(A)|S| (e.g., the projected subgradient method), we leverage the exponentiated gradient scheme of EMDA to ensure that π(t) 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 training data set during each iteration of HPO-AM is sufficiently large to contain all possible state-action pairs. Strict positivity of the initial state distribution µ0 and the initial policy π(0) is a necessary condition for this assumption.
Assumption 4 (Correctness of the sign of the advantage function). 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, i.e., sign(Â(t)(s, a)) = sign(A(t)(s, a)), for all (s, a).
Algorithm 1: HPO with an adaptive margin Result: Learned policy π(∞)
1 Initialize policy π(0) = π(θ(0)), initial state distribution µ0, α ∈ (0, 1), step sizes of EMDA {ηk}, threshold ζ ∈ (0, 1); 2 for t = 0, 1, · · · do 3 Collect a set of trajectories τ ∈ Dt under policy π(t) = π(θ(t)); 4 Estimate Â(t) by any policy evaluation algorithms; 5 Compute L̂(t)(θ), δ(t), (t) based on Â(t) and the collected samples in Dt; 6 Update the policy by
θ(t+1) = EMDA(L̂(t)(θ), {ηk}, (1− ζ)δ(t) (t), θ(t))
7 end
Algorithm 2: EMDA(L(θ), {ηk}, ξ, θinit)
Result: Learned parameter θ̃ 1 Input: Objective L(θ), step sizes {ηk},
threshold ξ, and initial parameter θinit; 2 Initialize θ̃(1) = θinit, θ̃ = θinit, and k = 1;
3 while L(θ̃) > ξ do 4 for each state s do 5 Find gs,a =
∂L(θ) ∂θs,a |θ=θ̃(k) , for each a; 6 Let ws = (e−ηkgs,1 , · · · , e−ηkgs,|A|); 7 θ̃ (k+1) s = 1
〈ws,θ̃(k)s 〉 (ws ◦ θ̃(k)s );
8 end 9 θ̃ = arg minθ∈{θ̃(i):1≤i≤k+1} L(θ);
10 Increment k by 1; 11 end
Remark 3. As pointed out by Assumption 4, 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 and 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 et al., 2019; Natarajan et al., 2013). As this paper is 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 to 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 V (t)(s)→ V ∗(s) as t→∞, ∀s ∈ S.
The proof of Theorem 1 is provided in the next section. Notably, the main difference between HPOAM 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 in PPO-KL and TRPO. Moreover, Theorem 1 ensures that all of the state values converge to the optimal value eventually.
Inspired by (Agarwal et al., 2020), based on the limits A(∞)(s, a) which can be shown to exist via Theorem 1, we divide all actions into the following sets for each state s:
I+s := {a ∈ A|A(∞)(s, a) > 0}, (15) I0s := {a ∈ A|A(∞)(s, a) = 0}, (16) I−s := {a ∈ A|A(∞)(s, a) < 0}. (17)
Note that π(t) converges to an optimal policy if I+s is empty for all s. As a result, I + s will play an important role in the proof of Theorem 1 in Section 3.2. Theorem 1 is followed by the two notable Corollaries 1-2, and their proofs are given in Appendix B. Corollary 1. Consider state s ∈ S. For each a ∈ I−s , the probability for our agent to take action a under state s converges to zero. For a ∈ I0s , the probability sum of taking these actions under state s converges to one. That is, π(t)(a|s)→ 0 for all a ∈ I−s and ∑ a∈I0s π(t)(a|s)→ 1 as t→∞.
Corollary 2. Consider state s ∈ S , if there is only one action a ∈ I0s , i.e., the optimal policy is deterministic, then we have (t)s → 0 as t→∞. 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 1, we know that the probability sum of actions belong to I0s approaches one. As a result, we presume that the actions described above form the set I0s .
Remark 5 (Label quality). In Theorem 1, we obtain a 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., 2020), for the convergence result to be true, it 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 1 and Assumptions 3-4, 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.

heading: 3 PROOF OF GLOBAL CONVERGENCE OF HPO-AM

heading: 3.1 SUPPORTING LEMMAS FOR THE PROOF OF THEOREM 1
text: In this section, we present the important properties of HPO-AM, which would serve as useful lemmas for proving Theorem 1. Define the state-wise loss function for each state s in each iteration t as
L̂(t)s (θs) = ∑ a∈A |Â(t)(s, a)| `(sign(Â(t)(s, a)), ρs,a(θs)− 1, (t)s ). (18)
Based on Assumption 2, where θs ∈ ∆(A), we can use ρs,a(θs) to represent ρs,a(θ) and further construct the above function of θs. Regardless of the size of the state space, the loss function can be viewed as optimizing policies on a per-state basis. The reason for this lies in that the definition of 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 a result, we know L̂(t)(θ) = 0 if and only if L̂(t)s (θs) = 0 for all s ∈ 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 π(t) is strictly positive in all state-action pairs, i.e., π(t)(a|s) > 0, for all (s, a). Under HPO-AM, if EMDA takes diminishing non-summable step sizes, i.e., ηk → 0 and ∑∞ k=1 ηk = ∞, then π(t+1) satisfies that π(t+1) > π(t) and π(t+1)(a|s) > 0, for all (s, a).
Lemma 2 (Monotonicity in π(t)(a|s)). There exist T0 and T1 such that for all a ∈ I+s , π(t)(a|s) is strictly increasing for t > T0; for all a ∈ I−s , π(t)(a|s) is strictly decreasing for t > T1.
Lemma 3 (Lower Bound of (t)s ). If I+s is not an empty set, then there exists a positive constant c such that (t)s is lower bounded by c, for all t > T1.
Lemma 4. ∑ a∈I+s ∪I−s (t) s π(t)(a|s)|A(t)(s, a)| → 0 as t→∞.

heading: 3.2 PROOF OF THEOREM 1
text: We first prove that each state value increases monotonically. Then, under the bounded reward setting, we have that each state value is bounded and thus converges. For convergence to the global optimal, we prove that the algorithm won’t stop until there is no action with positive advantage. The same analytical framework has also been used by (Agarwal et al., 2020) 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 1, we know that in each iteration t, π(t+1) and π(t) satisfy the sufficient condition for state-wise policy improvement provided by Proposition 2. This implies that the sequence of state values is point-wise monotonically increasing, i.e., V (t+1)(s) ≥ V (t)(s), ∀s ∈ S. Moreover, by Assumption 1 and the discounted setting, we have − R1−γ ≤ V
(t)(s) ≤ R1−γ . The above monotone increasing property and boundedness imply convergence, i.e., V (t)(s)→ V (∞)(s). Similarly, it can be derived that Q(t)(s, a)→ Q(∞)(s, a), and thus A(t)(s, a)→ A(∞)(s, a). The above sets I+s , I0s and I−s are well-defined, based on the limit A (∞)(s, a).
To establish that π(t) converges to an optimal policy, it is sufficient to show that I+s is an empty set for all s. The proof proceeds by contradiction as follows: Suppose I+s is non-empty with a+ ∈ I+s . From Lemma 2, we have that π(t)(a+|s) is bounded below by π(T0)(a+|s) for some T0 ∈ N for all t > T0. From Lemma 3, there exists a positive lower bound of (t) s . However, Lemma 4 shows that convergence of V (t)(s) implies that either (t)s converges to zero or the sum of probability mass over all actions in I+s ∪ I−s converges to zero. This leads to a contraction, and thus completes the proof.

heading: 4 HPO-AM WITH ALTERNATIVE CLASSIFIERS
text: In the previous sections, we propose the HPO update scheme and prove the global convergence for a particular case, HPO-AM, in Theorem 1. 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 a further result that global convergence also holds for HPO-AM with some other classifiers. The proof is given in Appendix C. Theorem 2. Theorem 1 is also satisfied for HPO-AM with the following classifiers and the corresponding margins with 0 < α < 1:
(i) HPO-AM with classifier log(πθ(a|s))− log(π(a|s)) (HPO-AM-log): Let πs = log(1 + α ·min{1, ∑ a∈Iπ−s π(a|s)∑ a∈Iπ+s π(a|s) }). (19)
(ii) HPO-AM with classifier √ ρs,a(θ)− 1 (HPO-AM-root): Let
πs =
√ 1 + α ·min{1, ∑ a∈Iπ−s π(a|s)∑ a∈Iπ+s π(a|s) } − 1. (20)
Remark 6. The classifiers in Theorem 2 also leverage the probability ratio ρs,a(θ), but in a 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 to be larger than one, such as πθ(a|s) − π(a|s) (called HPOAM-sub) or (ρs,a(θ))2−1 (called HPO-AM-square). It 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.

heading: 5 PRACTICAL IMPLEMENTATION AND EXPERIMENTAL RESULTS
text: Recall that HPO-AM improves the policy by minimizing the loss L̂(t)(θ) in (14). Therefore, like PPO-clip, in practice HPO-AM can 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 Baselines 3 Zoo framework (Raffin, 2020). We empirically evaluate the HPO-AM algorithms in MinAtar (Young & Tian, 2019), a modified version of Atari games for efficient evaluation, and conduct an ablation study to better understand the candidate design choices of 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 5 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-Ceron & Castro, 2021).
Figure 1 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 performance in the benchmark (Obando-Ceron & Castro, 2021). In (Kaiser et al., 2020), 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 1 indicates that each classifier has its own strengths. Notably, HPO-AM and HPO-AM-root achieve comparable or better performance than PPO-clip in the three environments. HPO-AM-log gets similar rewards as PPO-clip in Breakout and Freeway, but it gets fewer rewards than PPO-clip in Asterix. HPO-AM-square 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-dimensional tasks.

heading: 6 RELATED WORK
text: 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 a softmax policy parametrization). Concurrently, (Bhandari & Russo, 2019) provides an alternative analysis of global optimality of the policy gradient method. (Wang et al., 2019) provides the global optimality guarantees for both the vanilla policy gradient and natural policy gradient methods under the overparameterized two-layer neural parameterization. (Mei et al., 2020) establishes the convergence rates of both vanilla softmax policy gradient and the entropy-regularized policy gradient. (Liu et al., 2020) further establishes the global convergence rates of various variance-reduced policy gradient methods. Inspired by the analysis of (Agarwal et al., 2019), we establish the global convergence result of the proposed HPO-AM algorithms.
Global Convergence of TRPO and PPO. Regarding TRPO, (Shani et al., 2020) presents the global convergence rates of an adaptive TRPO, which is established by connecting TRPO and the mirror descent method. (Liu et al., 2019) proves global convergence in expected total reward for a neural variant of PPO with adaptive Kullback-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 of global convergence to an optimal policy for PPO with a clipped objective. In this paper, we rigorously provide the first global convergence guarantee for a variant of PPO-clip.
RL as Classification. Regarding the general idea of casting RL as a classification problem, it has been investigated by the existing literature (Lagoudakis & Parr, 2003; Lazaric et al., 2010; Farahmand et al., 2014), which view the one-step greedy update (e.g. in Q-learning) as a binary classification problem. However, a major difference is the labeling: Classification-based 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., 2010; Farahmand et al., 2014) as our paper is meant to study the theoretical foundation of PPO-clip, from the perspective of HPO.

heading: 7 CONCLUDING REMARKS
text: In this paper, we propose to rethink policy optimization methods from the perspective of statewise policy improvement. Specifically, we propose a classification-based policy update scheme leveraging hinge loss for policy improvement, and thereby propose a new family of algorithms called Hinge Policy Optimization (HPO). This paper proves global convergence of HPO with an adaptive margin (HPO-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 behavior and performance.

heading: APPENDIX

heading: A PROOFS OF THE SUPPORTING LEMMAS FOR THEOREM 1

heading: A.1 ADDITIONAL SUPPORTING LEMMAS
text: Lemma 5 (Loss value and policy improvement). Suppose that π(t)(a|s) > 0, for all state-action pairs (s, a). Given any ζ ∈ (0, 1), if L̂(t)s (θs) ≤ (1−ζ)δ(t)s (t)s for all s ∈ S, then we have πθ > π(t).
Proof. Recall that L̂(t)s (θs) = ∑ a∈A |Â(t)(s, a)| `(sign(Â(t)(s, a)), ρs,a(θs)− 1, (t)s ) (21)
= ∑ a∈A |Â(t)(s, a)| `(sign(A(t)(s, a)), ρs,a(θs)− 1, (t)s ) (22)
≥ ∑ a∈A δ(t)s max{0, (t)s − sign(A(t)(s, a))(ρs,a(θs)− 1)}, (23)
where (22) holds by Assumption 4, and (23) holds by the definition of δ(t)s and the non-negativity of hinge loss. Then, our goal is to show the following claim: for each state s, L̂(t)s (θs) ≤ (1−ζ)δ(t)s (t)s implies that
πθ(a|s) ≥ (1 + ζ (t)s )π(t)(a|s), a ∈ I(t)+s , (24) πθ(a|s) ≤ (1− ζ (t)s )π(t)(a|s), a ∈ I(t)−s . (25)
We can prove the above claim by contradiction. If there exists an action a ∈ I(t)+s such that πθ(a|s) < (1 + ζ (t)s )π(t)(a|s), then we know L̂(t)s (θs) > (1 − ζ)δ(t)s (t)s by (23). Similarly, if there exists an action a ∈ I(t)−s such that πθ(a|s) > (1 − ζ (t)s )π(t)(a|s), then we know L̂ (t) s (θs) > (1 − ζ)δ(t)s (t)s by (23). Therefore, by (24)-(25) and the sufficient condition for policy improvement in Proposition 1, we know πθ ≥ π(t).
Lemma 6 (Existence of a policy with zero loss). Given that the tabular policy parameterization is complete, i.e., any stochastic policy can be represented in the class, in each iteration t, we can always find a policy πθ such that L̂ (t) s (θs) = 0, for all s ∈ S.
Proof. Recall that I(t)+s := {a ∈ A|Â(t)(s, a) > 0} and I(t)−s := {a ∈ A|Â(t)(s, a) < 0}. Notice that we ignore the actions with zero advantage. We will prove that there always exists a policy πθ such that
sign(Â(t)(s, a))(ρs,a(θ)− 1) ≥ (t)s (26)
for all a ∈ I(t)+s ∪ I(t)−s , i.e., actions such that Aπ(s, a) 6= 0, for all s ∈ S. For state s, take
πθ(a|s) = θs,a = ( 1 + α · ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s)
) π(a|s),∀a ∈ I(t)+s , (27)
πθ(a|s) = θs,a = (1− α)π(a|s),∀a ∈ I(t)−s . (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 ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) ≥ 1, then (t) s = α.
For a ∈ I(t)+s , we have
πθ(a|s) = ( 1 + α · ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) ) π(a|s)
≥ (1 + α)π(a|s) = (1 + (t)s )π(a|s). (29)
On the other hand, for a ∈ I(t)−s , we have
πθ(a|s) = (1− α)π(a|s) = (1− (t)s )π(a|s). (30)
Case 2. If ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) < 1, then (t) s = α ·
∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) .
For a ∈ I(t)+s , we have
πθ(a|s) = (1 + α · ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) )π(a|s) = (1 + (t)s )π(a|s). (31)
Similarly, for a ∈ I(t)−s , we know
πθ(a|s) = (1− α)π(a|s) ≤ (1− α · ∑ a∈I(t)−s
π(a|s)∑ a∈I(t)+s π(a|s) )π(a|s)
= (1− (t)s )π(a|s). (32)
Therefore, in both cases we have πθ satisfy (26) for all a ∈ I(t)+s ∪ I(t)−s and for all s ∈ S , i.e., L̂(t)(θ) = 0.

heading: A.2 PROOF OF LEMMA 1
text: For convenience, we restate Lemma 1 as follows.
Lemma (Strict improvement and strict positivity of policy under HPO-AM). Suppose π(t) is strictly positive in all state-action pairs, i.e., π(t)(a|s) > 0, for all (s, a). Under HPO-AM, if EMDA takes diminishing non-summable step sizes, i.e., ηk → 0 and ∑∞ k=1 ηk = ∞, then π(t+1) satisfies that π(t+1) > π(t) and π(t+1)(a|s) > 0, for all (s, a).
Proof. We start by showing that the objective loss function L̂(t)(θ) is convex and Lipschitz continuous. From (18), we have
L̂(t)s (θs) = ∑ a∈A |Â(t)(s, a)| `(sign(Â(t)(s, a)), ρs,a(θs)− 1, (t)s ), (33)
= ∑ a∈A |Â(t)(s, a)|max{0, (t)s − sign(Â(t)(s, a))(ρs,a(θs)− 1)}. (34)
By the fact that ρs,a(θs) − 1 is linear and hinge loss is convex (Rosasco et al., 2004), their composition `(sign(Âπ(s, a)), ρs,a(θs) − 1, (t)s ) preserves convexity, for each a ∈ A. Being the nonnegative weighted sum of the above convex functions, L̂(t)s (θs) is also convex. Hence, L̂(t)(θ) is also convex.
For Lipschitz continuity, it follows from the fact that for any θ, θ̄ ∈ ∆(A)|S|,
|max{0, s − sign(Â(t)(s, a))(ρs,a(θs)− 1)} −max{0, s − sign(Â(t)(s, a))(ρs,a(θ̄s)− 1)}| ≤|( (t)s − sign(Â(t)(s, a))(ρs,a(θs)− 1))− ( (t)s − sign(Â(t)(s, a))(ρs,a(θ̄s)− 1))| (35) =|ρs,a(θs)− ρs,a(θ̄s)| (36)
= 1
π(t)(a|s) |πθ(a|s)− πθ̄(a|s)| (37)
= 1
π(t)(a|s) |θs,a − θ̄s,a| (38)
≤ 1 π(t)(a|s) ‖θs − θ̄s‖. (39)
Thus, |Â(t)(s, a)|max{0, (t)s − sign(Â(t)(s, a))(ρs,a(θs)− 1)} is Lipschitz continuous with a Lipschitz constant |Â
(t)(s,a)| π(t)(a|s) , for each a ∈ A. As a result, the summation L̂ (t) s (θs) over all actions is
M -Lipschitz continuous with M = 2R 1−γ
min{π(t)(a|s)} < ∞ (since π (t)(a|s) > 0 for all s, a). Hence,
L̂(t)(θ) is Lipschitz continuous as well.
Therefore, under a diminishing non-summable step size, the convergence of L̂(t)(θ) to its minimum, which is zero by Lemma 6, follows directly from the standard convergence result of EMDA shown by (Beck & Teboulle, 2003, Theorem 4.1). Moreover, by the termination condition of EMDA specified in Algorithm 1, we know that the θ returned by EMDA must satisfy L̂(t)(θ) ≤ (1− ζ)δ(t) (t), which implies that L̂(t)s (θ) ≤ (1 − ζ)δ(t)s (t)s , for every state s ∈ S . Hence, by Lemma 5, we have π(t+1) > π(t).
Next, by the strict positivity of π(t), we also have δ(t)s > 0 and (t) s > 0, for all s. Then, by the termination condition of EMDA specified in Algorithm 1 and the convergence of EMDA, we know that under HPO-AM, EMDA would terminate in finitely many iterations (i.e., finite k in Algorithm 2), for any t. Therefore, it is easy to verify that π(t+1)(a|s) > 0 for all (s, a) by the exponentiated gradient update scheme of EMDA and the strict positivity of π(t).

heading: A.3 PROOF OF LEMMA 2
text: For ease of exposition, we restate Lemma 2 as follows.
Lemma (Monotonicity in π(t)(a|s)). There exist T0 and T1 such that for all a ∈ I+s , π(t)(a|s) is strictly increasing for t > T0; for all a ∈ I−s , π(t)(a|s) is strictly decreasing for t > T1.
Proof. Consider a ∈ I+s . Since A(∞)(s, a) > 0, there exists a T0 ∈ N such that A(t)(s, a) > 0 for all t > T0. This implies that
π(t+1)(a|s)− π(t)(a|s) > (t)s π(t)(a|s) > 0, (40)
i.e., π(t)(a|s) is strictly increasing for t > T0. The proof of the second claim for a ∈ I−s is similar.

heading: A.4 PROOF OF LEMMA 3
text: For ease of exposition, we restate Lemma 3 as follows.
Lemma (Lower Bound of (t)s ). If I+s is not an empty set, then there exists a positive constant c such that (t)s is lower bounded by c, for all t > T1.
Proof. From the fact that ∑ a∈A
π(∞)(a|s)A(∞)(s, a) = 0; (41)∑ a∈I0s π(∞)(a|s)A(∞)(s, a) = 0, (42)
we have ∑ a∈I+s π(∞)(a|s)A(∞)(s, a) = ∑ a∈I−s π(∞)(a|s)|A(∞)(s, a)|. (43) By Assumption 1, we have |V (∞)(s)| ≤ R1−γ , |Q (∞)(s, a)| ≤ R1−γ and thus |A
(∞)(s, a)| = |Q(∞)(s, a)− V (∞)(s)| ≤ 2R1−γ . Therefore, by Hölder’s inequality, we have∑
a∈I−s
π(∞)(a|s) ≥ ∑ a∈I+s π (∞)(a|s)A(∞)(s, a) 2R
1−γ . (44)

heading: Define ∆ := mina∈I+s A
text: (∞)(s, a) > 0 and p := ∑ a∈I+s π
(∞)(a|s). Since we know that p =∑ a∈I+s π (∞)(a|s) > ∑ a∈I+s π
(T0)(a|s) by Lemma 2, we have p > 0. Moreover, by Lemma 2, we have I(t)−s ⊇ I−s and π(t+1)(a|s) < π(t)(a|s) for all a ∈ I−s and t > T1. This implies∑
a∈I(t)−s π(t)(a|s) > ∑ a∈I−s π(t)(a|s) > ∑ a∈I−s π(∞)(a|s) ≥ p∆ 2R 1−γ (45)
for all t > T1.
Therefore, by the definition of (t)s , we have (t)s = α ·min{1, ∑ a∈I(t)−s
π(t)(a|s)∑ a∈I(t)+s π(t)(a|s) } (46)
≥ α · ∑ a∈I(t)−s
π(t)(a|s)∑ a∈I(t)+s π(t)(a|s) (47)
≥ α · ∑
a∈I(t)−s
π(t)(a|s) (∵ ∑
a∈I(t)+s
π(t)(a|s) ≤ 1) (48)
≥ α · p∆ 2R
1−γ (From inequality (45)) (49)
for all t > T1.

heading: A.5 PROOF OF LEMMA 4
text: For ease of exposition, we restate Lemma 4 as follows. Lemma. ∑ a∈I+s ∪I−s (t) s π(t)(a|s)|A(t)(s, a)| → 0 as t→∞.
Proof. Convergence of V (t)(s) implies that V (t+1)(s) − V (t)(s) → 0, and by (4), the difference between the value functions at t and t+ 1 can be written as
V (t+1)(s)− V (t)(s)
= 1 1− γ ∑ s′∈S d(t+1)s (s ′) ∑ a∈A π(t+1)(a|s′)A(t)(s′, a). (50)
Following the update rule given by our classification-based scheme, π(t+1) satisfies both Proposition 1 and Proposition 2. That is,∑
a∈A π(t+1)(a|s′)A(t)(s′, a) ≥ 0 ∀s′ ∈ S. (51)
This implies that for convergence of V (t)(s), it is sufficient to show that d(t+1)s (s ′) ∑ a∈A π(t+1)(a|s′)A(t)(s′, a)→ 0, for all s′ ∈ S. (52)
Let us focus on s′ = s. Simply considering the first term of the discounted state visitation frequency, we obtain
∞∑ t′=0 γt ′ Pr(st′ = s|s0 = s, π(t+1))
≥ γ0 Pr(s0 = s|s0 = s, π(t+1)) = 1, (53)
and thus
d(t+1)s (s) = (1− γ) ∞∑ t′=0 γt ′ Pr(st′ = s|s0 = s, π(t+1))
≥ 1− γ. (54)
From (52) and (54) we have ∑ a∈A π(t+1)(a|s)A(t)(s, a)→ 0. (55)
Combining the above result and the fact that ∑ a∈A π
(t)(a|s)A(t)(s, a) = 0, we have∑ a∈A (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)→ 0. (56)
We split the summation over all actions into three parts, according to limits of the advantage function, i.e., ∑
a∈A (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)
= ∑ a∈I0s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)+
∑ a∈I+s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)+
∑ a∈I−s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)
(57)
Let T = max{T0, T1}, where T0, T1 are the constants defined in Lemma 2. Then, for a ∈ I+s ∪ I−s , A(t)(s, a) is of the same sign as A(∞)(s, a), for all t > T .
After moving the term of summation over I0s in (57) to the left hand side, by our classification-based scheme, we have∑
a∈A (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)− ∑ a∈I0s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a) (58)
= ∑ a∈I+s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a) + ∑ a∈I−s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a) (59)
= ∑ a∈I+s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)− ∑ a∈I−s (π(t+1)(a|s)− π(t)(a|s))|A(t)(s, a)| (60)
≥ ∑ a∈I+s ζ (t)s π (t)(a|s)A(t)(s, a) + ∑ a∈I−s ζ (t)s π (t)(a|s)|A(t)(s, a)| (61)
= ∑
a∈I+s ∪I−s
ζ (t)s π (t)(a|s)|A(t)(s, a)| > 0, (62)
for all t > T . Note that (61) follows from the same argument as (24)-(25). By the fact that∑ a∈A (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)→ 0 (63) and ∑ a∈I0s (π(t+1)(a|s)− π(t)(a|s))A(t)(s, a)→ 0, (64)
we have (58) converges to zero. Finally, by the sandwich theorem, we have∑ a∈I+s ∪I−s (t)s π (t)(a|s)|A(t)(s, a)| → 0. (65)

heading: B PROOFS OF COROLLARIES 1 AND 2

heading: B.1 PROOF OF COROLLARY 1
text: From Theorem 1, we know that I+s is an empty set, for all s ∈ S. Therefore, the result of Lemma 4 becomes ∑
a∈I−s
(t)s π (t)(a|s)|A(t)(s, a)| → 0. (66)
This implies that either (t)s → 0 or ∑ a∈I−s π
(t)(a|s) → 0. By Lemma 2, I(t)−s ⊇ I−s , for all t > T1. This implies that ∑ a∈I(t)−s π(t)(a|s) > ∑ a∈I−s π
(t)(a|s), for all t > T1. Moreover, we have that (t)s → 0 implies ∑ a∈I(t)−s π(t)(a|s)→ 0 and thereby implies ∑ a∈I−s π
(t)(a|s)→ 0, i.e.,∑ a∈I−s π
(t)(a|s)→ 0 is a necessary condition for (t)s → 0. Hence, we know∑ a∈I−s π(t)(a|s)→ 0 (67)
regardless of the behavior of (t)s . By combining ∑ a∈I−s π
(t)(a|s)→ 0 and the fact that I+s is empty, we have∑ a∈I0s π(t)(a|s)→ 1. (68)

heading: B.2 PROOF OF COROLLARY 2
text: Since there is only one action a ∈ I0s and I+s is empty, for all a′ ∈ A \ {a}, we have a′ ∈ I−s . By Lemma 2, there exists T1 such that for all t > T1, A(t)(s, a′) < 0, for all a′ ∈ A\{a}. This implies that A(t)(s, a) > 0, for all t > T1, i.e., for all t > T1, we have a ∈ I(t)+s and a′ ∈ I(t)−s , for all a′ ∈ A \ {a}. Then, by Corollary 1, as t→∞∑
a∈I(t)+s π(t)(a|s) = ∑ a∈I0s π(t)(a|s)→ 1 (69)
∑ a∈I(t)−s π(t)(a|s) = ∑ a∈I−s π(t)(a|s)→ 0. (70)
Hence, by definition, (t)s = α ·min{1, ∑ a∈I(t)−s
π(t)(a|s)∑ a∈I(t)+s π(t)(a|s)} → 0 as t→∞.

heading: C PROOF OF THEOREM 2
text: For ease of exposition, we restate Theorem 2 as follows.
Theorem. Theorem 1 is also satisfied for the following classifiers with corresponding margins with 0 < α < 1:
(i) For classifier log(πθ(a|s))− log(π(a|s)), let πs = log(1 + α ·min{1, ∑ a∈Iπ−s π(a|s)∑ a∈Iπ+s π(a|s) }). (71) (ii) For classifier √ ρs,a(θ)− 1, let
πs =
√ 1 + α ·min{1, ∑ a∈Iπ−s π(a|s)∑ a∈Iπ+s π(a|s) } − 1. (72)
Proof. The proof of Theorem 2 follows exactly the same procedure as that of Theorem 1. 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 classifiers, strict policy improvement πθ > π(t) is guaranteed if L̂s(θs) ≤ (1 − ζ)δ(t)s (t)s for all s, where ζ ∈ (0, 1).
• Regarding Lemma 6, the policy πθ 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 t, L̂s(θs) is Lipschitz continuous under the two classifiers log(ρs,a(θs)) and √ (ρs,a(θs)) − 1 if
the policy π(t) is strictly positive in all state-action pairs. Hence, L̂(θ) also remains Lipschitz continuous. By using the same argument of convergence of EMDA as that in Lemma 1, it is easy to verify that π(t+1) > π(t) and π(t+1)(a|s) > 0 for all (s, a) if EMDA takes diminishing and non-summable step sizes.
• Based on the extended version of Lemma 5 and Lemma 1 for these two alternative classifiers and Assumptions 3-4, we know that under the design of HPO-AM, strict policy improvement (i.e., π(t+1) > π(t)) and strict positivity of π(t) are satisfied in every iteration t. Therefore, the limits V (∞), Q(∞), and A(∞) 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 3 can be readily extended by adapting the argument in (46)-(49) to the πs defined in (19) and (20). Similarly, Lemma 4 can be extended by adapting the inequalities in (61)-(62) to the corresponding πs defined in (19) and (20).
Since all the lemmas hold for these alternative classifiers and their corresponding πs , we can complete the proof by showing a contradiction similar to that in Theorem 1.

heading: D UNPROVEN CLASSIFIERS
text: In Remark 6, we identify two other classifiers, πθ(a|s)−π(a|s) and (ρs,a(θ))2−1, which we cannot directly apply similar proof as Theorem 1.
First, an intuitive reason for the classifier πθ(a|s)−π(a|s) is explained as follows. To ensure the existence of improved policy, we must set s = mina∈A{π(a|s)}·α·min{1, ∑ a∈Iπ−s
π(a|s)∑ a∈Iπ+s
π(a|s)}, 0 < α < 1. Note that there is an additional term in front, compared to the margin we use in Theorem 1 before. Due to multiplying this additional term, the margin is bounded by the minimum probability of action. We cannot use Lemma 3 to give a lower bound for (t)s , since mina∈A{π(t)(a|s)} will probably approach zero as t → ∞. 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 (ρs,a(θ))2− 1, although we can prove the existence of improved policy by defining the margin as s = (1 + α · min{1, ∑ a∈Iπ−s
π(a|s)∑ a∈Iπ+s π(a|s)}) 2 − 1, our loss function is no longer
convex. Without convexity, the EMDA method is not guaranteed to converge to the optimal value. We leave it as an interesting open question of whether or not this problem can be solved by using a non-convex optimization method.

heading: E ABLATION STUDY OF HPO-AM VIA EXPERIMENTS IN A TABULAR ENVIRONMENT

heading: E.1 GRIDWORLD ENVIRONMENT
text: For a principled discussion, we use a 4× 4 gridworld similar to that in (Sutton, 1988, Example 4.1), where an 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 a 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 are deterministic.

heading: E.2 EXPERIMENTAL SETTINGS
text: In the gridworld environment, all the policies in our experiments are trained for 40000 episodes under 10 fixed random seeds. All the source code is in supplementary.zip of the supplementary materials. Our code of the HPO algorithms is extended from an open-source PyTorch example3, and the gridworld environment is modified from an open-source project, gym-gridworld4.

heading: E.3 NEURAL NETWORK MODEL
text: 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 (γ) are set to be 0.001 and 0.99, respectively. The input of the model is a one-hot vector to represent the grid position.

heading: E.4 ABLATIONS FOR THE WEIGHT AND MARGIN
text: Recall that the loss function of HPO in (12) involves three critical components: a classifier, a weight, and a margin. Regarding the classifier, we evaluate five variants of HPO-AM with the classifiers , including: (i) ρs,a(θ)−1, (the standard HPO-AM); (ii) log(πθ(a|s))− log(π(a|s)) (HPO-AM-log); (iii) √ ρs,a(θ)−1 (HPO-AM-root); (iv) πθ(a|s)−π(a|s) (HPO-AM-sub); (v) (ρs,a(θ))2−1 (HPOAM-square). Regarding the weight and the margin, we consider four different scenarios, including: (i) adaptive s and |Â(t)(sk, ak)| as the weight (denoted as WAE); (ii) adaptive s and a constant weight of 1 (denoted as AE); (iii) constant s = 0.1 and |Â(t)(sk, ak)| as the weight (denoted as WCE); (iv) constant s = 0.1 and a constant weight of 1 (denoted as CE). For the constant margin, we follow the popular setting of PPO-clip to set = 0.1. Those methods are implemented with a
3https://github.com/pytorch/examples/blob/master/reinforcement_ learning/actor_critic.py
4https://github.com/podondra/gym-gridworlds
tabular policy or a neural network policy. Under all the algorithms, the policy is trained for 40000 episodes under 10 random seeds.

heading: E.5 TRAINING CURVES
text: We show the L1 norm between HPO-AM policy with the optimal policy in Figure 2 and Figure 3. First, we evaluate the five variants of HPO-AM under tabular parameterization with true advantage values in Figure 2. This experiment is meant to verify the convergence behavior of HPO-AM.
We further implement the five variants of 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 a reasonable number of training episodes, while some of HPO-AMsub with WAE and WCE settings cannot converge.

heading: E.6 DISCUSSIONS
text: We measure the L1 norm between the policy learned under each variant of HPO-AM with the optimal policy as 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 convergence 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-sub and HPO-AM-square, 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 to converge slightly faster than PPO-clip. This manifests the potential of the proposed HPO framework in opening up a new class of promising RL algorithms.

heading: F DETAILED CONFIGURATIONS OF THE EXPERIMENTS IN MINATAR

heading: F.1 EXPERIMENTAL SETTINGS
text: 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 (Raffin, 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) ρs,a(θ) − 1, (the standard
HPO-AM); (ii) log(πθ(a|s)) − log(π(a|s)) (HPO-AM-log); (iii) √ ρs,a(θ) − 1 (HPO-AM-root); (iv) πθ(a|s)−π(a|s) (HPO-AM-sub); (v) (ρs,a(θ))2−1 (HPO-AM-square). In MinAtar, the observation is encoded by 10×10×n state representations, where each of the n channels corresponds to 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 5 million training steps among 5 random seeds. The source code is in supplementary.zip of the supplementary materials.

heading: F.2 NEURAL NETWORK MODEL
text: 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 0 to disable the entropy regularization for a fair comparison and follow the configuration suggested by RL Baseline3 Zoo5 for the rest of the hyperparameters. Table 1 summarize the hyperparameters for MinAtar and all 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.

heading: G COMPARISON OF THE CLIPPED OBJECTIVE IN PPO-CLIP AND THE HINGE LOSS OBJECTIVE OF HPO
text: Recall that the original objective of PPO-clip is
Lclip(θ) = Es∼dπµ0 ,a∼π(·|s) [ min{ρs,a(θ)Aπ(s, a), clip(ρs,a(θ), 1− , 1 + )Aπ(s, a)} ] , (73)
where ρs,a(θ) = πθ(a|s) π(a|s) . In practice, L clip(θ) is approximated by the sample average as
Lclip(θ) ≈ L̂clip(θ) = 1 |Dπ| ∑ (s,a)∈Dπ min{ρs,a(θ)Aπ(s, a), clip(ρs,a(θ), 1− , 1 + )Aπ(s, a)}
(74)
= 1 |Dπ| ∑
(s,a)∈Dπ |Aπ(s, a)| ·min{ρs,a(θ) sign(Aπ(s, a)), clip(ρs,a(θ), 1− , 1 + ) sign(Aπ(s, a))}︸ ︷︷ ︸ =:W clips,a(θ) .
(75)
5https://github.com/DLR-RM/rl-baselines3-zoo/blob/master/benchmark.md
Note that W clips,a (θ) can be further written as
W clips,a (θ) =  1 + , if Aπ(s, a) > 0 and ρs,a(θ) ≥ 1 + ρs,a(θ) , if Aπ(s, a) > 0 and ρs,a(θ) < 1 + −ρs,a(θ) , if Aπ(s, a) < 0 and ρs,a(θ) > 1− −(1− ) , if Aπ(s, a) < 0 and ρs,a(θ) ≤ 1− 0 , otherwise
Recall from (11) that the loss function of HPO takes the form as
L(θ) ≈ L̂(θ) = 1 |Dπ| ∑ (s,a)∈Dπ |Aπ(s, a)| ·max { 0, − (ρs,a(θ)− 1) sign(Aπ(s, a)) }︸ ︷︷ ︸
=:Ws,a(θ)
. (76)
Similarly, Ws,a(θ) can be further written as
Ws,a(θ) =  0 , if Aπ(s, a) > 0 and ρs,a(θ) ≥ 1 + −ρs,a(θ) + (1 + ) , if Aπ(s, a) > 0 and ρs,a(θ) < 1 + ρs,a(θ)− (1− ) , if Aπ(s, a) < 0 and ρs,a(θ) > 1− 0 , if Aπ(s, a) < 0 and ρs,a(θ) ≤ 1− , otherwise
Therefore, it is easy to verify that L̂clip(θ) and −L̂(θ) only differ by a constant with respect to θ. This also implies that∇θL̂clip(θ) = −∇θL̂(θ).

Review summaries:
 This 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.

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.