[Reinforcement Learning Algorithm] Proximal Policy Optimization (PPO)

Fundamentals

Value-Based

This category includes methods such as Q-Learning and DQN.

(1) Q and V Values

• V value: The sum of the rewards from all future states given the current state. (Make N copies of the current state. For each state, select a different possible action according to the policy, continue until the final state, and calculate the average of the N rewards.) It measures how reasonable the current policy’s action selection is.
• Q value: Measures the value of an action node. (Make N copies of the current action. Let each action continue interacting with the environment, record the rewards obtained, and calculate the average of the N rewards.) The Q value is not directly related to the policy but is related to the environment’s state transition probabilities.

(2) Monte Carlo

For a given state, first proceed from the current state to the end (the policy may generate different actions, creating different branches), calculate all the rewards r, and then backtrack to calculate the G value.

• G value: $G=r+\gamma \cdot G$. The G value represents the total return from a state to the final state.
• The V value is the average of the G values from N copies of state S. (It is closely related to the policy. With different policies, the probabilities that the N copies of state S produce action A are different.)

The disadvantage is that every state must proceed from beginning to end each time, so updating the G value may take a long time. An estimation method is therefore considered:

$$V(S_t)=V(S_t)+\alpha[G_t-V(S_t)]$$

That is, the V value estimated at the previous time step uses the learning-rate hyperparameter to move the V value closer to $G_t$. This way, whenever any state reaches the end and returns a G value, an update can be performed.

However, this method still requires a branch to reach the final state before an update can be performed. This led to the temporal-difference (TD) algorithm.

Unlike Monte Carlo, the TD algorithm only needs to proceed N steps before it can start backtracking and updating. That is, it assumes that the final state has been reached after N steps. If no branch has ever visited the final state, set the state to 0. If a branch has visited this state, the V value of this state is its current value.

$$V(S_t)=V(S_t)+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

Here, $R_{t+1}+\gamma V(S_{t+1})$ is equivalent to the $G_t$ value calculated by Monte Carlo, and $V(S_{t+1})$ represents the V value of the state after N steps.

Policy-Based

(1) Policy Gradient

The idea behind policy gradient (PG) is to directly use a neural network that takes state as input and outputs action. This process does not calculate Q.

The goal of PG is to maximize the total reward over the entire episode. Because both the actor and the environment are stochastic, $R_\theta=\sum^T_{t=1}r_t$ is random. Its expectation, $\bar{R_\theta}$, must therefore be maximized to measure how good the actor is.

$$\bar{R_\theta}=\sum_\tau R(\tau)P(\tau|\theta)\approx\frac{1}{N}\sum^N_{n=1}R(\tau^n)$$

Here, $P(\tau|\theta)$ is the probability of obtaining trajectory $\tau$ through the actions selected by the policy. Averaging the rewards obtained from all trajectories $\tau$ gives $\bar{R_\theta}$.

$$\theta^*=\mathop{\arg\max}\limits_{\theta}\bar{R_\theta}$$

The PG algorithm optimizes the network $\theta$ to maximize the expected reward. That is, it uses a gradient descent strategy to differentiate $\bar{R_\theta}$ with respect to $\theta$ and optimize the network through gradient descent.

$$\nabla\bar{R_\theta}=\sum_\tau R(\tau)\nabla P(\tau|\theta)=\sum_\tau R(\tau)P(\tau|\theta)\frac{\nabla P(\tau|\theta)}{P(\tau|\theta)}$$

Using the derivative form of the log function, this can be written as:

$$=\sum_\tau R(\tau)P(\tau|\theta)\nabla logP(\tau|\theta)\approx\frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla logP(\tau^n|\theta)$$

Here, $P(\tau|\theta)=p(s_1)\prod^T_{t=1}p(a_t|s_t,\theta)p(r_t,s_{t+1}|s_t,a_t)$ represents the probabilities from $s_t$ to $a_t$ and from $a_t$ to $s_{t+1}$. Their product represents the probability that the current trajectory occurs.

Because log converts a product into a sum,

$$logP(\tau|\theta)=logp(s_1)+\sum^T_{t=1}[logp(a_t|s_t,\theta)+logp(r_t,s_{t+1}|s_t,a_t)]$$

its derivative with respect to $\theta$ is:

$$\nabla logP(\tau|\theta)=\sum^T_{t=1}\nabla logp(a_t|s_t,\theta)$$

Therefore,

$$\nabla \bar {R_\theta}\approx\frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla logP(\tau^n|\theta)=\frac{1}{N}\sum^N_{n=1}R(\tau^n)\sum^T_{t=1}\nabla logp(a_t|s_t,\theta)=\frac{1}{N}\sum^N_{n=1}\sum^T_{t=1}R(\tau^n)\nabla logp(a_t|s_t,\theta)$$

In other words, for the action taken in the state at time t, if the total reward obtained is positive, the model should be updated so that the probability $p(a^n_t|s^n_t,\theta)$ becomes as large as possible, and vice versa.

Actor–Critic

Two networks can be used to estimate the Q value and V value separately.

• Actor: Can be based on PG; it takes a state as input and outputs a policy, namely, an action selection (policy gradient RL).
• Critic: Takes a state as input and calculates the score of each action (Value-Based RL).

However, when two networks are used, the parameters of both networks need to be adjusted, creating a greater risk of inaccurate estimates. Therefore, consider using only one V value and replacing the Q value with $\gamma\cdot V(s')+r$. The difference $\gamma\cdot V(s')+r-V(s)$ is called the TD error (that is, $Q(s,a)-V(s)$).