Introduction

So far, we have stored one value for every state.

$$S_1 \rightarrow V(S_1), \qquad S_2 \rightarrow V(S_2)$$

When there are only a few dozen states, this is the most intuitive approach. But if a single camera image is a state, we cannot build a table containing every possible combination of pixels. The same problem arises when the state is continuous, as with the joint angles of a robot. The robot may never encounter the exact same pose twice.

The necessary shift is from “memorize the answer for each state” to “calculate the answer from the characteristics of the state.”

$$\text{Value table} \quad\longrightarrow\quad \hat v(s,\mathbf w)$$

$\mathbf w$ contains parameters shared across many states. This article begins with the simplest form of value function approximation, a linear function, and then works through how Monte Carlo and TD targets become learning targets for that function.

Where a Table Reaches Its Limit

A tabular method changes only the entry for the state that was visited.

$$V(S_t) \leftarrow V(S_t)+\alpha\left[U_t-V(S_t)\right]$$

$U_t$ may be a Monte Carlo return or a TD target. The important point is that the entry for $S_t$ is independent of every other state's entry.

This independence is convenient in a small problem, but it creates two difficulties.

1. If there are too many states, we cannot store every entry.
2. Knowledge learned in similar states cannot be shared between them.

For example, suppose the lane position in an autonomous-driving state changes from $0.201$ to $0.202$. These states describe almost the same situation, but a table gives them entirely different addresses. Even if the agent has learned a great deal at $0.201$, it sees $0.202$ as a new state.

Function approximation lets similar states share representations and parameters.

An Approximation, Not the Exact Value

Let $v_\pi(s)$ be the true state value under policy $\pi$. Our function approximates it.

$$\hat v(s,\mathbf w) \approx v_\pi(s)$$

The hat means “an estimate calculated with the current parameters.”

• $s$: the input state
• $\mathbf w$: the parameters to learn
• $\hat v(s,\mathbf w)$: the value predicted by the function
• $v_\pi(s)$: the true expected return we want to know but cannot observe directly

The structure resembles supervised learning. We feed in $s$, obtain a prediction, and update $\mathbf w$ to reduce the difference from a target. The difference is that no one supplies a correct label in reinforcement learning. A return or bootstrap target constructed from experience acts as a temporary answer.

Features Describe a State with Numbers

Before we feed a state into a function, we need to represent it as a numerical vector.

$$\mathbf x(s) = \begin{bmatrix} x_1(s) \\ x_2(s) \\ \vdots \\ x_d(s) \end{bmatrix}$$

For an elevator state, we might define features such as

• the normalized current floor,
• whether an upward call button is active,
• whether a downward call button is active, and
• whether the door is open.

Features resemble a list of questions that describe the state. A neural network also learns the features themselves. With a linear function, however, people often define the input features by hand.

A Linear Value Function

The simplest approximation is a weighted sum of the features.

$$\hat v(s,\mathbf w) = \mathbf x(s)^\top\mathbf w = \sum_{j=1}^{d}x_j(s)w_j$$

For example, if

$$\mathbf x(s) = \begin{bmatrix} 1 \\ 0.5 \\ -1 \end{bmatrix}, \qquad \mathbf w = \begin{bmatrix} 2 \\ 4 \\ 1 \end{bmatrix},$$

then

$$\hat v(s,\mathbf w) = 1\times2 +0.5\times4 +(-1)\times1 =3.$$

$w_j$ expresses the direction and degree to which its feature affects the value. If repeated experience shows that the value rises when the second feature grows, for example, $w_2$ increases.

Moving in a Direction That Reduces Error

Suppose we have a target $U_t$. The squared error for one sample is

$$L_t(\mathbf w) = \frac{1}{2} \left[ U_t-\hat v(S_t,\mathbf w) \right]^2.$$

The $1/2$ is simply a convenience that cancels the leading $2$ when we differentiate.

Updating the parameters with gradient descent gives

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ U_t-\hat v(S_t,\mathbf w) \right] \nabla_{\mathbf w}\hat v(S_t,\mathbf w).$$

It is easier to read the equation as three pieces.

1. $\alpha$: the step size that determines how far to move
2. $U_t-\hat v$: the error that says how wrong the current prediction is
3. $\nabla_{\mathbf w}\hat v$: the direction that says which parameter will change the prediction

For a linear function, the gradient is the feature vector itself.

$$\nabla_{\mathbf w}\hat v(s,\mathbf w) = \mathbf x(s)$$

The update therefore becomes even simpler.

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ U_t-\hat v(S_t,\mathbf w) \right] \mathbf x(S_t)$$

Weights connected to features with larger values move farther.

Learning One State Changes Other States Too

In a table, updating $S_A$ leaves the value of $S_B$ unchanged. With function approximation, every state shares the same $\mathbf w$, so an update using $S_A$ also changes the predictions for $S_B$ and $S_C$.

This is both the advantage and the risk of function approximation.

• When useful features are shared, the agent can learn several similar states from relatively little experience.
• When it generalizes incorrectly, an error in one state can damage predictions for unrelated states as well.

A table learns slowly, but an error in one entry does not spread to another. A function generalizes quickly, but every update has a wider range of influence.

Using a Monte Carlo Target

If the episode has ended and we can calculate the actual return $G_t$, then we set

$$U_t=G_t.$$

The update becomes

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ G_t-\hat v(S_t,\mathbf w) \right] \nabla_{\mathbf w}\hat v(S_t,\mathbf w).$$

Because the target does not contain the current value function, this looks most like familiar supervised regression. The usual properties of Monte Carlo remain: we must wait until the episode ends, and the return has high variance.

Using a TD Target

TD(0) bootstraps from the estimate one step ahead.

$$U_t = R_{t+1} + \gamma\hat v(S_{t+1},\mathbf w)$$

The TD error is

$$\delta_t = R_{t+1} + \gamma\hat v(S_{t+1},\mathbf w) - \hat v(S_t,\mathbf w),$$

and the update is

$$\mathbf w \leftarrow \mathbf w + \alpha\delta_t \nabla_{\mathbf w}\hat v(S_t,\mathbf w).$$

Here, the target is also constructed with the same parameters $\mathbf w$. During the update, however, we do not differentiate through the target side. We change only the prediction for the current state, $\hat v(S_t,\mathbf w)$. This is why the method is called semi-gradient TD.

For now, it is enough to understand the process as follows: “temporarily fix the next state's estimate as the answer, and move only the current prediction toward it.”

Function Approximation Is Not Always Stable

Training can become unstable when function approximation, bootstrapping, and off-policy learning appear together. These three elements are commonly called the deadly triad.

• Function approximation: several states share parameters.
• Bootstrapping: the target contains a current estimate.
• Off-policy: the policy that produced the experience differs from the policy being learned.

An overestimate can spread through shared parameters. If that incorrect estimate is then used to construct another target, the error may grow. DQN, the subject of the next article, uses experience replay and a target network to mitigate this problem.

What to Remember

Value function approximation calculates values with a function that has shared parameters instead of storing a separate value for every state. This allows the estimate to generalize to states it has never seen.

1. $\hat v(s,\mathbf w)$ approximates $v_\pi(s)$.
2. A linear function is written as $\hat v=\mathbf x(s)^\top\mathbf w$.
3. We can read an update as the product of a step size, prediction error, and gradient.
4. Monte Carlo uses $G_t$ as its target, while TD uses $R_{t+1}+\gamma\hat v(S_{t+1})$.
5. Shared parameters create generalization, but they can also spread a bad update across many states.

The next article approximates $Q(s,a)$ with a neural network and introduces DQN, which produces action values directly from pixel inputs.

References

• David Silver, Lecture 6: Value Function Approximation
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition