> For the complete documentation index, see [llms.txt](https://theshank.gitbook.io/ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://theshank.gitbook.io/ai/reinforcement-learning/deep-reinforcement-learning/value-function-approximation.md).
# Value Function Approximation
## Value Function Approximation
SO far we have represented value function using look-up table:\
\- Every state s has an entry V(s)\
\- Every state-action pair have an entry Q(s,a)
Now it is impossible to have V(s) entry if we have large number of states. Hence, to solve this we use **Value Function Approximator.** Which are basically functoins which can map state to its value i.e $$v: s \rightarrow a$$ .
## Stochastic Gradient Descent
$$
J(w) = E\_\pi\[(v\_\pi(s)-\hat{v}(s,w))^2]
$$
Here, $$v\_\pi$$ is the original taget and $$\hat{v}$$ is the value approximation function with parameters w. Now we will update the $$w$$ using gradient descent in order to minimize the the cost $$J(w)$$ . Hence
$$
\triangle w = \alpha (v\_\pi(s)-\hat{v}(s,w))\triangledown\_w\hat{v}
(s,w)
$$
But is the problem that we don't know the target value funtion $$v\_\pi(s)$$ in reinforcement learning before hand . We will see below how to handle this problem.
## Different Value approximation
### Linear Function Approximation
**Feature Vector:** We represent state using a vector as below.
Using this state feature vector and weights. Linear approximation is as follows:
$$
\hat{v}(s,w) = x(s)^Tw = \sum x\_j(s)w\_j
$$
Hence in this case update become:
$$
\triangle w = \alpha (v\_\pi(s)-\hat{v}(s,w))x(s)
$$
**Table Lookup Features:** It is special case for linear function approximation. Here the state vector have all the states in itself. see below:
## Incremental Prediction Algorithms
Here we talk about the ways in which we can substitute the value of $$v\_\pi(s)$$ from the the weights.
### Monte-Carlo with Value Funtoni Approx.
Use $$G\_t$$ calucuated from the episodes here in place of $$v\_\pi(s)$$. We will have \
$$<(S\_1, G\_1), (S\_2, G\_2),...(S\_T, G\_T)>$$ , which will be ou training data.
Hence using linear Monte-carlo policy evaluation, algorithm will be:
$$
\triangle w = \alpha (G\_t-\hat{v}(s\_t,w))x(s\_t)
$$
**Monte-Carlo evaluation will converge to a local optimum. Even with non-linear value funtion approximation.**
### **TD Learning with value funtion approx.**
The TD-target $$R\_{t+1} + γ v̂ (S\_{t+1} , w)$$ is a biased sample of true value $$v\_\pi(s\_t)$$**.**
Supervised learning can be applies using traingin data: $$<(S\_1, R\_2 + γ v̂ (S\_2 , w)), (S\_2, R\_3 + γ v̂ (S\_3 , w)),...(S\_{T-1}, R\_T)>$$
$$
\triangle w = \alpha (R\_{t+1} + γ v̂ (S\_{t+1} , w)-\hat{v}(s\_t,w))x(s\_t)
$$
Linear TD(0) coverges(close) to global optimum.
### TD() with value funtion approximation.
The λ-return $$G\_t^λ$$ is also a biased sample of true value $$v\_\pi(s\_t)$$
Apply Supervised learning with following data: $$<(S\_1, G\_1^\lambda), (S\_2, G\_2^\lambda),...(S\_T, G\_T^\lambda)>$$
Forward View linear TD():
$$
\triangle w = \alpha (G\_t^\lambda-\hat{v}(s\_t,w))x(s\_t)
$$
Backward view linear TD():
$$
\delta\_t = R\_{t+1} + γ v̂ (S\_{t+1} , w)-\hat{v}(s\_t,w)\\
E\_t = \gamma \lambda E\_{t-1} + x(S\_t)\\
\triangle w = \alpha \delta\_t E\_t
$$
Forward and backward view llinear TD() are equivalent.
## Incremental Control Algorithms
Policy Evalutaion: Approximate policy evaluation: $$\hat{q}(.,.,w) \approx q\_\pi$$ \
Policy Improvement : $$\epsilon-greedy$$ policy improvement
Here
$$
J(w) = E\_\pi\[(q\_\pi(S,A,w)-\hat{q}(S,A,w))^2]
$$
$$
\triangle w = \alpha (q\_\pi(S,A,w)-\hat{q}(S,A,w))\triangle\_w \hat{q}(S,A,w)
$$
### Linear approximation:
$$
\hat{q}(s,a,w) = x(s,a)^Tw = \sum x\_j(s,a)w\_j
$$
### Algorithms
Now we have to substitute a target for $$q\_\pi(S,A)$$
**MC:** The taget wiill be return $$G\_t$$
$$
\triangle w = \alpha (G\_t-\hat{q}(S,A,w))\triangle\_w \hat{q}(S,A,w)
$$
**TD(0):** The target is TD target $$R\_{t+1} + γ \hat{q} (S\_{t+1}, A\_{t+1} , w)$$
$$
\triangle w = \alpha (R\_{t+1} + γ \hat{q} (S\_{t+1}, A\_{t+1} , w)-\hat{q}(S,A,w))\triangle\_w \hat{q}(S,A,w)
$$
**Same goes with forward and backward view TD(lambda).**
### Gradient Temporal-Difference Learning
## Batch Methods
### Least Square Prediction
Given value function $$\hat{v}(s,w)$$ approximation amd experience D consisting of \ pairs. $$D = {\,\,...\}$$
Learning paramters w for the best fitting value funtion$$\hat{v}(s,w)$$.
Least-square algorithm: find $$w$$ minimizing the least square error between apprx funtion and target values.
$$
LS(w) = \sum\_{t=1}^T(v\_t^\pi - \hat{v}(s\_t,w))^2 \\
\=E\_D\[(v^\pi-\hat{v}(s,w))^2]
$$
#### SGD with experience replay
* Sample state, value from experience\
$$\ \sim D$$
* Apply SGD update\
$$\triangle w = \alpha (v^\pi-\hat{v}(s,w))\triangledown\_w\hat{v}(s,w)$$
This converges to least square solution
$$
w^\pi = arg \min\_w LS(w)
$$
#### Experience Replay in Deep Q-Networks
### Least Square Control
#### Least square Action-Value Function Approximation
Approximate action-value funtion.
Minimize least square error between $$\hat{q}(s,a,w)$$ and $${q}\_\pi(s,a,w)$$ from experiences generated using policy $$\pi$$ consisting of <(state, actoin), value> pairs $$D = {<(s\_1,a\_1), v\_1^\pi>,<(s\_2,a\_2), v\_2^\pi>,...<(s\_t,a\_t), v\_t^\pi>}$$
