Value Function Approximation

CS287 - Advanced Robotics

I think it’s this idea that you hand engineering you value function as a sum of features $\theta$.

Whereas before we defined our value function in terms of a Bellman Equation

Example 1: Tetris

See Value Iteration where we show the implementation combining that.

Intuition

So far we have represented value function by a lookup table, i.e. every state $s$ has an entry $V(s)$ on the table, or every state-action pair $s,a$ has an entry $Q(s,a)$ on the table.

However, with large MDPs:

• There are too many states and/or actions to store in memory
• It is too slow to learn the value of each state individually

Real-world problems oftentimes have enormous state and/or actions spaces, so the tabular representation is insufficient.

Solution for large MDPs:

• Estimate value function with function approximation $\hat{v}(s,w)\approx v_{\pi }(s)$ $\hat{q}(s,a,w)\approx q_{\pi }(s,a)$

David Silver: To update w, we use MC or TD Learning.

So what Function Approximators should we use? There are several options, but we focus on differentiable function approximations:

• Linear Feature Representations
• Neural Network

Linear Feature Representations

Some thoughts afterwards! Connections

This is actually the same thing as the gradient descent case below, except the equation $\Delta w=\alpha ((v_{\pi }(S)-\hat{v}(S,w)){\nabla }_w\hat{v}(S,w)$ gets simplified to $\Delta w=\alpha ((v_{\pi }(S)-\hat{v}(S,w))x(S)$

Let $x(S)$ be the feature vector, $x(S)=(x_1(S)⋮x_n(S))$

Represent value function by a linear combination of features $\hat{v}(S,w)=x(S{)}^{\top }w={\sum }_{j=1}^n{x}_j(S)w_j$

Objective function is quadratic in parameters $w$: $J(w)={\mathbb{E}}_{\pi }[v_{\pi }(S)-x(S{)}^{\top }w{)}^2]$

Stochastic gradient descent converges on global optimum Update rule is particularly simple ${\nabla }_w\hat{v}(S,w)=x(S)$ $∆w=\alpha (v_{\pi }(S)-\hat{v}(S,w))x(S)$ Update = step-size × prediction error × feature value

Notice in the above how all of this works assuming that we have this true value function $v_{\pi }(s)$, this “oracle” as David Silver calls it, which tells us how much we are wrong for $J(w)$. However, in RL, there is no supervisor, only rewards. We don’t have $v_{\pi }(s)$. In practice, we substitute a target for $v_{\pi }(s)$.

• In MC, we replace $v_{\pi }(s)$ with $G_t$
• In TD(0), we replace $v_{\pi }(s)$ with the TD-target
• In TD($\lambda$), we replace with the $\lambda$-return

Approximation by Gradient Descent

Goal: find parameter vector w minimizing mean-squared error between approximate value fn ˆv(s, w) and true value fn vπ(s)

We defined the loss as $J(w)=E_{\pi }[(v_{\pi }(S)-\hat{v}(S,w){)}^2]$

We can use gradient descent finds a local minimum $∆w=-\frac{1}{2}\alpha {\nabla }_{w}J(w)$ After applying chain rule, we get $\Delta w=\alpha E_{\pi }[(v_{\pi }(S)-\hat{v}(S,w)){\nabla }_w\hat{v}(S,w)]$

Instead of doing the full gradient descent, we can sample the gradient with stochastic gradietn descent.

$\Delta w=\alpha ((v_{\pi }(S)-\hat{v}(S,w)){\nabla }_w\hat{v}(S,w)$ Expexted update is equal to full gradient update.

TD Learning with VFA

TD is biased. 3 forms of approximation:

• function approximation
• bootstrapping
• sampling

VFA for Control

Policy Evaluation - Approximate policy evaluation