RL: Overview and basic policy gradient

Difference between normal supervised learning

Reinforcement learning is unsupervised and it will solve the problem there is no standard answer(or humans also don't know the best way to solve).

The basic problems and parameters

All the purpose of the machine learning problem is to find a function, reinforcement learning is no exception.

To find a function is a set of Actor:

In the learning process of chess, since there is no reward for moving in the chess game no matter how, it is stipulated that winning a game gets 1 point, losing a game gets -1 point.

Three components of reinforcement learning

Function with unknown

Policy Network(Actor), input from environment(observation of machine represented as a vector or matrix), output an action, actually it's a classification task, each action corresponds to a neuron in output layer.

In order to ensure randomness(paper scissor stone), the probability is usually determined according to the reward, and then the behavior is randomly selected according to the probability, rather than directly choosing the behavior with the highest reward.

Define loss

The entire process from the beginning of training to the triggering of the termination condition that brings the game to an end is called an episode.

A total reward(return) can be calculated at the end of an episode:

$$R=totalreward=\sum _{t=1}^T{r}_t$$

Our target is to maximize $R$.

$$Loss=-R$$

Optimization

Find a set of network parameters that make the total reward as large as possible.

A complete set of s and A is called Trajectory:

$$\tau =\{s_1,a_1,s_2,a_2,...\}$$$$R(\tau )=\sum _{t=1}^T{r}_t\uparrow$$

$R$ is a random variable, we can only know it's expect.

Calculating the $R$ expectation for a particular parameter $\theta$ requires exhausting all possible trajectories, calculating the probability of all $\tau$ occurrences, multiplying the probability by its reward value and summing:

$${\bar{R}}_{\theta }=\sum _{\tau }R(\tau )p_{\theta }(\tau )=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )]$$

Difficulty

Since action is generated by probability, the network may take different actions when faced with the same environment.

Also, the mechanics of environment and reward are not clear, and we can only treat them as black boxes. To make matters worse, the circumstances and rewards are also random in some cases(For example, in chess, the opponent's position is uncertain when facing the same game).

Policy Gradient

When controlling the behavior of an actor, you can think of it as a classifier that sees a situation and takes a specific action.

Both $e_1$ and $e_2$ are cross-entropy loss, and the overall loss is defined as:

$$L=e_1-e_2$$$${\theta }^{\ast }=arg\underset{\theta }{min}L$$

Since e2 is about what not to do, the loss is calculated with a negative sign.

This allows you to write the total loss function by defining how good or bad each behavior is:

$\{s_i,{\hat{a}}_i\}$	$A_i$
$\{s_1,{\hat{a}}_1\}$	+1.5
$\{s_2,{\hat{a}}_2\}$	-0.5
$\{s_3,{\hat{a}}_3\}$	+0.5
$⋮$	$⋮$
$\{s_N,{\hat{a}}_N\}$	-3

$$L=\sum A_i{e}_i$$$${\theta }^{\ast }=arg\underset{\theta }{min}L$$

(important)How to define $\{s_i,{\hat{a}}_i\}$ and $A_i$​?

A short-sight version:

Defining $A$ directly in terms of the number of rewards, which always makes the model tend to get more reward points in an interaction.

This method is too eager for quick success, sometimes the local optimal solution may be very unfavorable to the overall situation, and sometimes the appropriate abandonment of some small benefits can ultimately obtain the most rewards.

version1

This method adds up all the rewards for selecting an action (i.e., what the outcome of the action was). Use the effect of the sum to determine $A$.

$s_1$	$s_2$	$s_3$	$\cdots$	$s_N$
$a_1$	$a_2$	$a_3$	$\cdots$	$a_N$
$r_1$	$r_2$	$r_3$	$\cdots$	$r_N$

$$A_i=G_i=\sum _{t=i}^N{r}_t$$

This approach is not good enough. If the whole process is long, we cannot simply attribute the reward $r_N$ to a1's decision, or $a_1$'s influence on the outcome is not that great.

version2

The introduction of a attenuation factor indicates that the farther away from $a_1$ the reward is, the more independent it is of $a_1$​.

$$G_1^{\prime }=r_1+\gamma r_2+{\gamma }^2{r}_3+...,0<\gamma <1$$$$G_i^{\prime }=\sum _{t=i}^N{\gamma }^{t-i}{r}_t$$

version3

Good and bad are relative, and if the rewards are all non-negative, then $A$'s are all non-negative, so it's very difficult for the model to avoid making bad decisions. So to standardize the $G$​ value, even if the reward is positive, it should be preferred to choose the largest and avoid the small one.

Minus baseline $b$​

All $G$ is subtracted by the same $b$ and then assigned to $A$:

$$A_i=G_i^{\prime }-b$$

Pseudocode of policy gradient
initialize actor network parameters ${\theta }^0$ for training iteration $i=1$ to $T$  using actor ${\theta }^{i-1}$ to interact  obtain data $\{s_1,a_1\},\{s_2,a_2\},...,\{s_N,a_N\}$  compute $A_1,A_2,...,A_N$  compute loss $L$  ${\theta }^i\leftarrow {\theta }^{i-1}-\eta \mathrm{\nabla }L$

Unlike the general model, the process of collecting data is within the for loop, that is, its data is dynamically collected along with the training.

In this process, each set of data can only update the parameter once, and the next time the parameter is updated, new data comes in. That's why RL training is slow.

A set of environments is only suitable for updating certain parameters, and if it is used to update other parameters, it may cause a bad effect. The so-called: his honey, my arsenic.

Exploration

The actor interacting with the environment should be made as random as possible, because this allows for as many effects of different behaviors as possible. This can be done by increasing entropy or directly adding noise to the parameters, making it easier for actors to take low-probability actions.

math: How to calculate gradient?

we know that

$$R=totalreward=\sum _{t=1}^T{r}_t$$

and $R$ is a random variable, we can only know it's expect.

Calculating the $R$ expectation for a particular parameter $\theta$ requires exhausting all possible trajectories, calculating the probability of all $\tau$ occurrences, multiplying the probability by its reward value and summing:

$${\bar{R}}_{\theta }=\sum _{\tau }R(\tau )p_{\theta }(\tau )=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )]$$

so how can we find $\mathrm{\nabla }{\bar{R}}_{\theta }$​ ?

Since the gradient of $R$ is actually the gradient of probability, you can move the gradient symbol in:

$$\mathrm{\nabla }{\bar{R}}_{\theta }=\sum _{\tau }R(\tau )\mathrm{\nabla }{p}_{\theta }(\tau )$$

therefore, $R_{\tau }$ do not have to be differentiable.

$$\sum _{\tau }R(\tau )\mathrm{\nabla }{p}_{\theta }(\tau )=\sum _{\tau }R(\tau )p_{\theta }(\tau )\frac{\mathrm{\nabla }{p}_{\theta }(\tau )}{p_{\theta }(\tau )}$$

using formula:

$$\mathrm{\nabla }f(x)=f(x)\mathrm{\nabla }logf(x),$$$$\sum _{\tau }R(\tau )p_{\theta }(\tau )\frac{\mathrm{\nabla }{p}_{\theta }(\tau )}{p_{\theta }(\tau )}=\sum _{\tau }R(\tau )p_{\theta }(\tau )\mathrm{\nabla }log{p}_{\theta }(\tau )$$$$=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )\mathrm{\nabla }log{p}_{\theta }(\tau )]$$

This gradient can not be calculated directly at this stage, so it is necessary to sample $N$ groups of $\tau$, calculate the value of each group of samples, and then average to approximate the gradient:

$$\mathrm{\nabla }{\bar{R}}_{\theta }\approx \sum _{n=1}^{N}R({\tau }^n)\mathrm{\nabla }log{p}_{\theta }({\tau }^n)$$$$=\frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}R({\tau }^n)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)$$

$s_t$ and $a_t$ is a state-action pair in trajectory $\tau$. If $a_t$ is performed in the face of $s_t$ and the reward for $\tau$​ is found to be positive, the probability of it is increased.

using Pytorch or TF, we can do it conveniently:

$$\frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}R({\tau }^n)log{p}_{\theta }(a_t^n|s_t^n)\to TF\to \frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}R({\tau }^n)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)$$

if add a baseline, the gradient becomes:

$$\mathrm{\nabla }{\bar{R}}_{\theta }\approx \frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}(R({\tau }^n)-b)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n),b\approx E[R(\tau )]$$

Imagine a situation where the first step was a very good decision, but the second step was wrong and the final score is not so good, but the score is still good because the first step was well done, then the model mistakenly believes that the second step is also good.

If you apply the calculation method in version2, you should not use the overall R to calculate the correctness of a certain step, but should calculate the sum of rewards after this step, so as to avoid the problems raised above:

$$\mathrm{\nabla }{\bar{R}}_{\theta }\approx \frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}(\sum _{t^{\prime }=t}^{T_n}{r}_{t^{\prime }}^n-b)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n)$$

Then further, directly using the method of version3 combined with the attenuation factor to calculate, we can get the final gradient expression:

$$\mathrm{\nabla }{\bar{R}}_{\theta }\approx \frac{1}{N}\sum _{n=1}^N\sum _{t=1}^{T_n}(\sum _{t^{\prime }=t}^{T_n}{\gamma }^{t^{\prime }-t}\cdot r_{t^{\prime }}^n-b)\mathrm{\nabla }log{p}_{\theta }(a_t^n|s_t^n),0<\gamma <1$$

On policy v.s. Off-policy

If the actor to train and the actor for interacting is the same, we call it on-policy. In other words, if the actor himself does training to gain experience, it is on policy; if the actor gains experience by watching other actors train, it is off-policy.

An advantage of off-policy is that it can be trained with the experience of other actors, so there is no need to constantly collect data, which can greatly improve the training efficiency.