Proximal policy optimization

Proximal policy optimization (PPO) is a reinforcement learning (RL) algorithm for training an intelligent agent's decision function to accomplish difficult tasks. PPO was developed by John Schulman in 2017, and had become the default RL algorithm at the US artificial intelligence company OpenAI. Since 2018, PPO has seen success in a wide variety of applications, such as controlling a robotic arm, beating professional players at Dota 2, and excelling in Atari games. Many experts called PPO the state of the art, due to its ability to strike a balance between performance and comprehension. Compared with other algorithms, the three main advantages of PPO are simplicity, stability, and sample efficiency.

PPO is classified as a policy gradient method for training an agent's policy network. This network approximates a policy function, used by the agent to make decisions. Essentially, to train the policy function, PPO takes a small policy update step, so the agent can reliably reach the optimal solution. A step size that is too big may direct the policy in a suboptimal direction, thus having little possibility of recovery; a step size that is too small lowers the overall efficiency. Consequently, PPO implements a clip function that constrains the policy update of an agent from being too large, so that larger step sizes may be used without negatively affecting the gradient ascent process.

Development

In 2015, John Schulman introduced Trust Region Policy Optimization (TRPO), which was a predecessor of PPO. TRPO addressed the instability issue of another algorithm, the Deep Q-Network (DQN), by using the trust region constraint to regulate the KL divergence between the old and new policies. However, TRPO is computationally complex and inefficient due to its use of second-order optimization, leading to difficulties and expensiveness when implementing solutions to large-scale problems.

In 2017, John Schulman solved the complexity issue of TRPO by adopting first-order optimization in PPO. Schulman and his team designed a clipping mechanism that stops the new policy from deviating significantly from the old one when the likelihood ratio between them exceeds a certain clip threshold. In other words, PPO modifies the objective function of TRPO by penalizing policy updates that are too large. PPO also obviates the complicated trust region constraints, and utilizes the clipping function instead. As a result, PPO improves performance and implementation based on the framework of TRPO.

Theory

This section first explores the key components of PPO, then delves deep into the main objective function.

Basic concepts

To begin the PPO training process, the agent is set in an environment to perform actions based on its current input. In the early phase of training, the agent can freely explore solutions and keep track of the result. Later, with a certain amount of transition samples and policy updates, the agent will select an action to take by randomly sampling from the probability distribution $P(A|S)$ generated by the policy network. The actions that are most likely to be beneficial will have the highest probability of being selected from the random sample. After an agent arrives at a different scenario (a new state) by acting, it is rewarded with a positive reward or a negative reward. The objective of an agent is to maximize the cumulative reward signal across sequences of states, known as episodes.

Policy gradient laws: the advantage function

The advantage function (denoted as $A$) is central to PPO, as it tries to answer the question of whether a specific action of the agent is better or worse than some other possible action in a given state. By definition, the advantage function is an estimate of the relative value for a selected action. If the output of this function is positive, it means that the action in question is better than the average return, so the possibilities of selecting that specific action will increase. The opposite is true for a negative advantage output.

The advantage function can be defined as $A=Q-V$, where $Q$ is the discounted sum of rewards (the total weighted reward for the completion of an episode) and $V$ is the baseline estimate. Since the advantage function is calculated after the completion of an episode, the program records the outcome of the episode. Therefore, calculating advantage is essentially an unsupervised learning problem. The baseline estimate comes from the value function that outputs the expected discounted sum of an episode starting from the current state. In the PPO algorithm, the baseline estimate will be noisy (with some variance), as it also uses a neural network, like the policy function itself. With $Q$ and $V$ computed, the advantage function is calculated by subtracting the baseline estimate from the actual discounted return. If $A>0$, the actual return of the action is better than the expected return from experience; if $A<0$, the actual return is worse.

Ratio function

In PPO, the ratio function ($r_{t}$) calculates the probability of selecting action $a$ in state $s$ given the current policy network, divided by the previous probability under the old policy. In other words:

• If $r_{t}(\theta )>1$, where $\theta$ are the policy network parameters, then selecting action $a$ in state $s$ is more likely based on the current policy than the previous policy.
• If $0\leq r_{t}(\theta )\leq 1$, then selecting action $a$ in state $s$ is less likely based on the current policy than the old policy.

Hence, this ratio function can easily estimate the divergence between old and current policies.

PPO objective function

The objective function of PPO takes the expectation operator (denoted as $E$) which means that this function will be computed over quantities of trajectories. The expectation operator takes the minimum of two terms:

1. $r_{t}(\theta )\cdot A$: this is the product of the ratio function and the advantage function introduced in TRPO, also known as the normal policy gradient objective.
2. $\operatorname {clip} (r_{t}(\theta ))\cdot A$: the policy ratio is first clipped to the range $[1-\epsilon ,1+\epsilon ]$; generally, $\epsilon$ is defined to be 0.2. Then, as before, it is multiplied by the advantage.

The fundamental intuition behind PPO is the same as that of TRPO: conservatism. Clipping results in a conservative advantage estimate of the new policy. The reasoning is that if an agent makes significant changes due to high advantage estimates, its policy update will be large and unstable, and may diverge from the optimal policy with little possibility of recovery. There are two common applications of the clipping function: when an action under a new policy happens to be a good choice based on the advantage function, the clipping function limits how much credit can be given to a new policy for up-weighted good actions. On the other hand, when an action under the old policy is judged to be bad, the clipping function constrains how much the agent can accept the down-weighted bad actions of the new policy. Consequently, the clipping mechanism is designed to discourage the incentive of moving beyond the defined range by clipping both directions. The advantage of this method is that it can be optimized directly with gradient descent, as opposed to the strict KL divergence constraint of TRPO, making the implementation faster and more intuitive.

After computing the clipped surrogate objective function, the agent has two probability ratios: one non-clipped and one clipped. Then, by taking the minimum of the two objectives, the final objective becomes a lower bound (a pessimistic bound) of what the agent knows is possible. In other words, the minimum method makes sure that the agent is doing the safest possible update.

Advantages

Simplicity

PPO approximates what TRPO does, with considerably less computation. It uses first-order optimization (the clip function) to constrain the policy update, while TRPO uses KL divergence constraints (second-order optimization). Compared to TRPO, the PPO method is relatively easy to implement and requires less computational resource and time. Therefore, it is cheaper and more efficient to use PPO in large-scale problems.

Stability

While other RL algorithms require hyperparameter tuning, PPO comparatively does not require as much (0.2 for epsilon can be used in most cases). Also, PPO does not require sophisticated optimization techniques. It can be easily practiced with standard deep learning frameworks and generalized to a broad range of tasks.

Sample efficiency

Sample efficiency indicates whether the algorithms need more or less data to train a good policy. On-policy algorithms, including PPO and TRPO, generally have good sample efficiency (they do not require as many samples as alternative algorithms). However, PPO achieved sample efficiency because of its use of surrogate objectives. The surrogate objective allows PPO to avoid the new policy moving too far from the old policy; the clip function regularizes the policy update and reuses training data. Sample efficiency is especially useful for complicated and high-dimensional tasks, where data collection and computation can be costly.

See also

• Reinforcement learning
• Temporal difference learning
• Game theory

External links

• Announcement of Proximal Policy Optimization by OpenAI
• GitHub repo