# Policy evaluation

## Fit what ?

![Policy evaluation](https://4133958719-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LigLKy0c06y4iTEtrkI%2F-LlW-XG9L2UQDu8jetgD%2F-LlW-d17CYTygjyhOvt8%2F1564992490924.png?generation=1564995655241610\&alt=media)

So now we need to fit one of $$Q^\pi,V^\pi,A^\pi$$. The question is fit what to what? We knew:

$$
\begin{aligned}
Q^\pi(s\_t,a\_t)&=\sum\_{t'=t}^T \mathbb{E}*{\pi*\theta}\[r(s\_{t'},a\_{t'})|s\_t,a\_t] \\
V^\pi(s\_t)&=\mathbb{E}*{a\_t\sim \pi*\theta(a\_t|s\_t)}\[Q^\pi(s\_t,a\_t)]    \\
A^\pi(s\_t,a\_t)&=Q^\pi(s\_t,a\_t)-V^\pi(s\_t)
\end{aligned}
$$

Firstly, both $$Q^\pi$$ and $$A^\pi$$ can be calculated or approximated by $$V^\pi$$:

$$
\begin{aligned}
Q^\pi(s\_t,a\_t) &=  \sum\_{t'=t}^T \mathbb{E}*{\pi*\theta}\[r(s\_{t'},a\_{t'})|s\_t,a\_t] \\
&\approx r(s\_t,a\_t)+\sum\_{t'=t+1}^T \mathbb{E}*{\pi*\theta}\[r(s\_{t'},a\_{t'})|s\_t,a\_t] \\
&\approx r(s\_t,a\_t)+V^\pi(s\_{t+1})\\

A^\pi(s\_t,a\_t)&\approx r(s\_t,a\_t)+V^\pi(s\_{t+1})-V^\pi(s\_t)
\end{aligned}
$$

Apart from this, both $$Q^\pi$$ and $$A^\pi$$ need 2 inputs $$s\_t, a\_t$$, but $$V^\pi$$ only need $$s\_t$$, which may be easier.

So let's just fit $$V^\pi$$.

## Fitted to what?

$$
V^\pi(s\_t)=\sum\_{t'=t}^T \mathbb{E}*{\pi*\theta}\[r(s\_{t'},a\_{t'})|s\_t]
$$

Fit $$V^\pi(s\_t)$$, evaluate how good is the policy, which is called policy evaluation. As what policy gradient does, we can use Monte Carlo policy evaluation.

$$
V^\pi(s\_t)\approx\sum\_{t'=t}^T r(s\_{t'},a\_{t'})
$$

if we are able to reset the simulator, we can do more than one samples:

$$
V^\pi(s\_t)\approx\frac{1}{N}\sum\_{i=1}^N\sum\_{t'=t}^T r(s\_{t'},a\_{t'})
$$

But the former is still pretty good, so the supervised learning condition is:

training data: $$\left{\left (s\_{i,t},\sum\_{t'=t}^T r(s\_{i,t'},a\_{i,t'})\right) \right}$$. Define target $$y\_{i,t}=\sum\_{t'=t}^T r(s\_{i,t'},a\_{i,t'})$$.

supervised regression: $$\mathcal{L}(\phi)=\frac{1}{2}\sum\_i ||\hat{V}\_{\phi}^\pi(s\_i)-y\_i||^2$$

## Bootstrapped estimate

The Monte Carlo target $$y\_i$$ is not perfect. Can we do better? The ideal target is:

$$
\begin{aligned}
y\_{i,t}&=\sum\_{t'=t}^T \mathbb{E}*{\pi*\theta}\[r(s\_{i,t'},a\_{i,t'})|s\_{i,t}] \\
&\approx r(s\_{i,t},a\_{i,t})+\sum\_{t'=t+1}^T \mathbb{E}*{\pi*\theta}\[r(s\_{i,t'},a\_{i,t'})|s\_{i,t}] \\
&\approx r(s\_{i,t},a\_{i,t})+V^\pi(s\_{t+1})\\
&\approx  r(s\_{i,t},a\_{i,t})+\hat{V}^\pi\_{\phi}(s\_{t+1})\\
\end{aligned}
$$

Sample one step and the directly use previous fitted value function.

This estimate will cause more bias but lower variance.

## Algorithm

> Batch actor-critic algorithm:
>
> repeat until converge:
>
> \====1: sample $${s\_i,a\_i }$$ from $$\pi\_\theta(a|s)$$ (run it on the robot)
>
> \====2: fit $$\hat{V}^\pi\_\phi(s)$$ to sampled reward sums (use bootstrapped estimate target)
>
> \====3: evaluate $$\hat{A}^\pi(s\_i,a\_i)=r(s\_i,a\_i)+\hat{V}^\pi\_\phi(s\_i')-\hat{V}^\pi\_\phi(s\_i)$$
>
> \====4: $$\nabla\_\theta J(\theta)\approx \sum\_i \nabla\_\theta \log \pi\_\theta (a\_i|s\_i)\hat{A}^\pi(s\_i,a\_i)$$
>
> \====5: $$\theta \leftarrow \theta+ \alpha\nabla\_\theta J(\theta)$$

![Batch actor-critic algorithm](https://4133958719-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LigLKy0c06y4iTEtrkI%2F-LlW-XG9L2UQDu8jetgD%2F-LlW-d1C2_gXHmXkBuBZ%2F1564995241809.png?generation=1564995654869959\&alt=media)
