Hinge Policy Optimization: Reinterpreting PPO-Clip and Attaining Global   Optimality
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 based on the principle of hinge policy optimization (HPO), called to achieve policy improvement by solving a large-margin classification problem with hinge loss, and thereby reinterprets PPO-clip as an instance of HPO. From this perspective, we present HPO algorithms and establish the following convergence guarantees: (i) We first study HPO with direct parameterization and establish almost-sure asymptotic convergence in the tabular setting; (ii) We present the NeuralHPO algorithm, which substantiates the HPO principle in the neural function approximation setting via a regression-based policy update scheme, and thereafter characterize the convergence rate of NeuralHPO. To the best of our knowledge, this is the first-ever that can prove global convergence to an optimal policy and convergence rate for a variant of PPO-clip.