# Q learning
###### tags: `notes`
## Policy Gradient
Policy $\pi$ is a network with parameter $\theta$
- input : the observation of the machine, which is represented as matrix or vector
- output : each action will link to a corresponding neuron, and each neuron will give the probability of each action

reward fumction : given a state and action to determine how many points to get
Trajectory $\tau$ : a series of action and state will form the trajecotry
$$
R(\tau) = \sum^T_{t=1}r_t
$$

:::info
$p(\tau)$ represents the pobability of the trajectory $\tau$
:::

$$
\bar{R}_\theta = \sum^T_{t=1} R(\tau)p_\theta(\tau)
$$
$$
\nabla \bar{R}_\theta = \sum_{\tau} R(\tau)\nabla p_\theta(\tau) = \sum_{\tau} R(\tau)p_\theta(\tau) \nabla \log p_\theta(\tau) \\
= E_{\tau\sim p_{\theta}(\tau)}\left[R(\tau)p_\theta(\tau) \nabla \log p_\theta(\tau)\right]
$$

:::info
note that : $\nabla f(x) = f(x) \nabla\log f(x)$
:::

__tips :__
1. add baseline
During sampling the game with all positive value, if one of the positive-reward action is not being choose, the opportunity of it may be lessen since all items in sampling will be enhanced in opportunity.
2. sutible credit
We will only calculate the cumulated reward after the action happened, since the reward before has no correclation with this action.

### Proximal Policy Optimization
#### on policy and off policy
- On policy : the same agent learn and interact with the same policy
- Off policy : the agent interact with environment with the policy will watch to learn

using the on policy may takes many time for collecting data, but using off policy may save more time.
#### importance sampling
$$
\int f(x)p(x)dx = \int f(x)\frac {p(x)}{q(x)}q(x)dx = E_{x\sim q}\left[f(x)\frac {p(x)}{q(x)}\right]
$$

note that $E_{x\sim q}\left[f(x)\frac {p(x)}{q(x)}\right]$ may far from $E_{x\sim q}\left[f(x)\right]$ if the amount of sampling is not enough

After using importance smapling, we use the followinf line to update the model
$$
J^{\theta^{\prime}}(\theta) = E_{(s_t,a_t)\sim\pi_{\theta^{\prime}}}\left[\frac{p_\theta(a_t\mid s_t)}{p_{\theta^\prime}(a_t\mid s_t)}A^{\theta^\prime}(s_t,a_t)\right]
$$

#### PPO

$$
J^{\theta^\prime}_{PPO}(\theta) = J^{\theta^{\prime}}(\theta)-\beta KL(\theta,\theta^\prime)
$$

What is the KL diversions :
the behavior distance between two distribution
#### PPO algoritm
1. Initilal policy parameters $\theta^0$
2. In each iteration
- Using $\theta^k$ to interact with the environment to collect ${s_t,a_t}$ and compute advantage $A^{\theta^k}(s_t,a_t)$
- find $\theta$ to optimize $J_{PPO}(\theta)$

$$
J^{\theta^k}_{PPO}(\theta) = J^{\theta^k}(\theta)-\beta KL(\theta,\theta^k)
$$

Adaptive KL diversions
- if $KL(\theta,\theta^k) > KL_{max}$ , increase $\beta$
- if $KL(\theta,\theta^k) < KL_{min}$ , deccrease $\beta$

## Q learning
### critic
- a critic does not directly determine the action
- Given an actor $\pi$ , it evalutes how good the actor is
- State value function $V^{\pi}(s)$

Given a state _S_, critic calculate how much reward will the actor $\pi$ gain in the future.
:::info
The output values of a critic depend on the actor evaluted.
:::

### how to estimate $V^{\pi}(s)$
- Monte-Carlo based approach
After seeing $S_a$ , the cumulated reward should be $G_a$

We use the regression to train the $V^{\pi}(s)$ .
- Temporal-difference approach
$V^{\pi}(s_t) = V^{\pi}(s_{t+1}) + r_t$

we train $V^{\pi}(s)$ and $V^{\pi}(s_{t+1})$ so that $r_t$ can be as close as possible

MC has large varieance, since $G_a$ is the summation of many step.

### another critic
- state-action value fuction $Q^{\pi}(s,a)$
When using acotr $\pi$ , the cumulated reward expected to be optained after taking __a__ at state __s__
:::info
__a__ may be use only at the instant, afterwards it can take other action
:::

### Q learning
1. $\pi$ interacts with the environment
2. Learning $Q^{\pi}(s,a)$ from TD or MC
3. Find a new actor $\pi^{\prime}$ better than $\pi$

#### what is "better"
when $V^{\pi^{\prime}}(s) \ge V^{\pi}(s)$ , for all state s
we can calculate it as follow
$$
\pi^{\prime}(s) = arg\ max_a\ Q^{\pi}(s,a)
$$

Proof
$$
V^{\pi}(s) = Q^{\pi}(s,\pi(a)) \le max_a\ Q^{\pi}(s,a) = Q^{\pi}(s,\pi^{\prime}(s))
$$

It show that if you only follow $\pi^{\prime}$ for one step, it is still better than follows $\pi$ for the whole time

### Target network

While training $Q^{\pi}(s_t,a_t) = Q^{\pi}\left(s_{t+1},\pi\left(s_{t+1}\right)\right) + r_t$ , we often fixed the hyperparameters of the right side and adjust the left side only. After updating N times, then copy the hyperparameters to the left side.

### exploration
If the action haven't been trained in the certain state, then it may only take the action that have seen.

#### Epsilon Greedy
$\epsilon$ would decay during learning

$$
a =
\left\{
\begin{matrix}
arg\ max\ Q(s,a),& &with\ probability\ 1-\epsilon \\
random,& &otherwise
\end{matrix}
\right.
$$

#### Boltzman Exploration
$$
P(a|s)=\frac{exp(Q(s,a))}{\sum_a exp(Q(s,a))}
$$

#### Replay Buffer
While $\pi$ interacts with the environment, we put the experienced $s_t,a_t,r_t,s_{t+1}$ to the buffer.
The experience in the buffer comes from different policies(different $\pi$).

__Benefits__
1. Save times to interact with the environment
the experience before can be used several times
2. better performance
the experience from different policy makes it more diverse

### tip
#### Double DQN
Q value is usually over-estimated

Why is Q value usually over estimate?
we always choose the highest rewarded action as the target value, so it is apt to have bigger value.

Double DQN:
$$
Q^{\pi}(s_t,a_t) = r_t + Q^{\prime}(s_{t+1},arg\ max_a\ Q(s_{t+1},a))
$$

we use the real Q to choose the action and the rest remain the same.

#### Dueling DQN
First calulate the scalar $V(s)$　and another $A(s,a)$, then add them together

we need to give a constraint for the model $A(s,a)$, so it'll inclined to update $V(s)$

first, we have to normalize $A(s,a)$ before adding with $V(s)$

#### Prioritized reply
The data with larger TD　error in previous training has higher probability to be sampled.

#### Multi-step
#### Noisy Net
During the epsilon greedy policy, metting same state may cause different action. We can instead impose the noise on Q function, which called State-dependent Exploration.

#### Distributional Q-function
Try to ouput the distribution instead of the expected mean value.

### Continuous Actions

action $a$ is a continuous vector(like angle)

- sloution 1
sample a set of actions
- solution 2
using gradient ascent to solve the optimization problem.
- solution 3
Design a network to make the optimazation easy

$Q$ is a function that takes both $a$ and $s$, but before we interact with a, we let $Q^{\pi}$ output three function
1. a vector $\mu(s)$
2. a matrix $\Sigma(s)$
3. a scalar $V(s)$
$$
Q(s,a) = -(a-\mu(s))^T\Sigma(s)(a-\mu(s))+V(s)
$$

__a__ is a vector, if the robot has 10 joints, we can set the vector as 1x10 and each digits represents the angle of the corresponding joint.

:::info
to get the max of $Q$, we can let $a = \mu(s)$

$$
\mu(s) = arg\ max_a\ Q(s,a)
$$
:::

## actor critic
### what is actor-critic
While using policy gradient, we use the samples to update the parameter. However this samples has randomness, we try to use the expectaiton to replace the sampling result.

- State value function $V^{\pi}(s)$
When using actor $\pi$, the cumulated reward expected to be obtained after visiting state __s__
- State-action value function $Q^\pi (s,a)$
When using actor $\pi$, the cumulated reward expected to be obtained after taking __a__ at state __s__

:::info
$V$ only output one value ; $Q$ will have several outputs accoring to each discrete action
:::

$$
\nabla \bar{R}_\theta \approx \frac{1}{N}\sum^N_{n=1}\sum^N_{t=1} \left(Q^{\pi_\theta}(s^n_t,a^n_t) - V^{\pi_\theta}(s^n_t)\right)\nabla\log p_\theta(a^n_t\mid s^n_t)
$$

:::info
Q represents the expectation of the sampling ; V represents the baseline
:::

Estimate two networks will cause double error, so we'll use the V to estimate Q

$$
Q^{\pi}(s^n_t,a^n_t) = E\left[r^n_t + V^{\pi}(s^n_{t+1})\right]
$$
$$
Q^{\pi}(s^n_t,a^n_t) - V^{\pi}(s^n_{t}) = r^n_t + V^{\pi}(s^n_{t+1}) - V^{\pi}(s^n_t)
$$

### tips
1. $\pi(s)$ unput a state and output the distribution of the action ; $V^{\pi}(s)$ input the state and output the cumulated reward. Since the input are the same we can share several layers from the top.
2. use output entropy as regularization for $\pi$, larger entropy means larger entropy

### Asychronous Advantage Actor-Critic(A3C)
1. Copy global parameters
2. Sampling some data
3. Compute gradients
4. Update global models

## Pathwise Derivative Policy Gradient
We try to learn an actor, which will tell a proper action, to solve the question that arg max is not easy to find.
### algorithm

1. given state $s_t$, take action $a_t$ based on $\pi$, also need exploration
2. Obtain reward $r_t$ and reach new state $s_{t+1}$
store $s_t,a_t,r_t,s_{t+1}$ into buffer
sample $s_t,a_t,r_t,s_{t+1}$ from buffer
3. Target $y = r_i + \hat{Q}(s_{i+1},\hat{\pi}(s_{i+1}))$
upgrade the parameters of $Q$ to make $Q(s_i,a_i)$ close to y
4. Update the parameters of $Q$ to maximize $Q(s_i,\pi(s_i))$
5. every C steps reset $\hat{Q} = Q$ ; every C steps reset $\hat{\pi} = \pi$

## Sparse Reward
Some task, like picking up a stick, may be very difficult for a robot to train from begin. It's not posssible that the bot can finish the task simply from the action exploration, so we have to design some mechanism to lead the robot at first.
### Rewrard shaping
Some of the action may have its effect in the future, so adding some artificial reward which may describe the movement of agent well.

#### Curiosity
ICM = intrinsic curiosity module

input $s_1,a_1,s_2$ and output another reward $r_i$.
When ending up the game, we not only need the total reward be maximize, we also want to optimize $r_i$.

ICM take $s_1,a_1$ as input and count $\hat{s}_{t+1}$. the larger difference between $\hat{s}$ and $s$ will result to larger reward $r_i$.

Note that some actions are hard to predict, but with low importance.

#### Feature extractor
We try to learn another network that takes the $s_t$ and $s_{t+1}$ as input and output an action $\hat{a}_t$ which predicts the action that cause the state change. If $\hat{a}_t$ and $a_t$ is not close enough, then we won't output to the curious network.

### Curriculum Learning
The robot should start from easy task, rather than the general case.

#### Reverse Curriculum Generation

1. Given a goal state $s_g$, and sample some state $s_1$ that are close to goal state.
2. Frim $s_1$ , each state that reach to $s_g$ will get reward $R(s_1)$.
3. Delete those case that are too easy(large reward) or too hard(small reward), and keep sample more state from the surviving.

### Hierachical Reinforcement Learning

The upper agent will provide goal for lower agent. If the lower agent cannot finish the goal, the upper layer will get penalty. If the lower agent get the wrong goal, then just assume the original goal is wrong.

## Imitation learning
There are two approaches for imitation learning :
1. begavior cloning
2. inverse reinforcement learning

### behavior cloning
Given a state and output a supervise network. However the expert may have occurs limited scenario.
#### dataset aggregation
We get the actor $\pi_1$ by behavior cloning and let $\pi_1$ to interact with environment. Meanwhile, the expert will record what he will do, but do not influence the actor.