Gradient Descent for Parameter Learning

Function approximation allows for the representation of value functions, such as $\hat{v}(s, \mathbf{w})$ or $\hat{q}(s, a, \mathbf{w})$, using a set of parameters or weights, denoted by the vector $\mathbf{w}$. For linear function approximation, this takes the form $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s)$, where $\mathbf{x}(s)$ is the feature vector for state $s$. Determining the best values for these weights $\mathbf{w}$ is a primary objective.

The answer lies in borrowing a fundamental technique from supervised machine learning: gradient descent. The idea is to adjust the weights iteratively to minimize some measure of error between our approximation and the true value function we're trying to learn.

Defining the Objective: Minimizing Error

Our goal is to make our approximation $\hat{v}(S_t, \mathbf{w})$ as close as possible to the true value $v_\pi(S_t)$ for all states $S_t$ encountered under the policy $\pi$. A standard way to quantify this is using the Mean Squared Value Error (MSVE), which we aim to minimize:

$$J(\mathbf{w}) = \mathbb{E}_\pi \left[ (v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}))^2 \right]$$

This objective measures the expected squared difference between the true value and our approximation, averaged over the states visited while following policy $\pi$.

The Challenge in Reinforcement Learning: Unknown Targets

In typical supervised learning, you'd have a dataset of input-output pairs (like state features $\mathbf{x}(s)$ and their corresponding true values $v_\pi(s)$). You could then directly apply gradient descent to minimize the MSVE on this dataset.

However, in reinforcement learning, we almost never know the true value function $v_\pi(s)$! Instead, we have estimates or targets derived from experience. These targets are based on the rewards received and subsequent state values (either observed until the end of an episode or bootstrapped). Examples include:

1. Monte Carlo (MC) Target: $U_t = G_t$. This is the full return observed starting from state $S_t$ until the end of the episode. It's an unbiased estimate of $v_\pi(S_t)$.
2. Temporal Difference (TD) Target: $U_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})$. This is the TD(0) target, using the immediate reward $R_{t+1}$ and the current estimate of the next state's value, $\hat{v}(S_{t+1}, \mathbf{w})$. This target is biased because it relies on our current (possibly inaccurate) estimate.

Since we collect experience step-by-step (state, action, reward, next state), we can't compute the full expectation in the MSVE objective easily. Instead, we use Stochastic Gradient Descent (SGD).

Stochastic Gradient Descent (SGD) for Value Function Approximation

SGD updates the weights incrementally using one sample (or a small batch) of experience at a time. For each interaction step $t$ yielding a state $S_t$ and a target value $U_t$, we update the weight vector $\mathbf{w}$ in the direction that reduces the error for that specific sample.

The general idea of gradient descent is to update the parameters in the direction opposite to the gradient of the error function. For a single sample $(S_t, U_t)$, the squared error is $\frac{1}{2} (U_t - \hat{v}(S_t, \mathbf{w}))^2$. (We add the $\frac{1}{2}$ for mathematical convenience, as it cancels out during differentiation).

The gradient of this single-sample error with respect to the weights $\mathbf{w}$ is:

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

The SGD update rule moves the weights in the opposite direction of this gradient, scaled by a learning rate $\alpha$:

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

Here:

• $\mathbf{w}_t$ is the weight vector before the update.
• $\alpha$ is the learning rate (a small positive number controlling the step size).
• $(U_t - \hat{v}(S_t, \mathbf{w}_t))$ is the prediction error for the current sample.
• $\nabla_\mathbf{w} \hat{v}(S_t, \mathbf{w}_t)$ is the gradient of the value function approximation with respect to the weights, evaluated at state $S_t$. This term tells us how changing each weight affects the value estimate for the current state.

Applying SGD to Linear Function Approximation

Things become quite concrete when we use linear function approximation, $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s) = \sum_{i=1}^d w_i x_i(s)$. The gradient of this approximation with respect to the weight vector $\mathbf{w}$ is simply the feature vector $\mathbf{x}(s)$ itself:

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

Substituting this into the general SGD update rule gives the update rule for linear VFA:

$$\mathbf{w}_{t+1} \leftarrow \mathbf{w}_t + \alpha (U_t - \hat{v}(S_t, \mathbf{w}_t)) \mathbf{x}(S_t)$$

This update has an intuitive interpretation:

• Calculate the error: $\delta_t = U_t - \hat{v}(S_t, \mathbf{w}_t)$. This is how far off our current prediction was from the target.
• Scale the error by the learning rate: $\alpha \delta_t$.
• Adjust the weights based on the features: Multiply the scaled error by the feature vector $\mathbf{x}(S_t)$. Features that were active ($x_i(S_t) \neq 0$) for the state $S_t$ will have their corresponding weights $w_i$ adjusted. If the error $\delta_t$ is positive (underestimation), weights corresponding to active features are increased. If the error is negative (overestimation), they are decreased.

Flow of a single Stochastic Gradient Descent update step for linear value function approximation.

The Semi-gradient Distinction

There's a subtle but important point when using TD targets like $U_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t)$. Notice that the target $U_t$ itself depends on the current weights $\mathbf{w}_t$ through the term $\hat{v}(S_{t+1}, \mathbf{w}_t)$.

When we calculated the gradient of the single-sample squared error $\frac{1}{2} (U_t - \hat{v}(S_t, \mathbf{w}_t))^2$, we treated the target $U_t$ as if it were a fixed, constant value, even though it depends on $\mathbf{w}_t$. A true gradient calculation would need to account for the derivative of the target with respect to $\mathbf{w}_t$, which is significantly more complex.

By ignoring the dependence of the target on the weights, we are not following the true gradient of the MSVE (using the TD target). Instead, we are following what's called a semi-gradient. Methods that use bootstrapping (like TD learning) with function approximation are therefore called semi-gradient methods.

Why do we do this?

1. Simplicity: Semi-gradient updates are much simpler to compute and implement.
2. Effectiveness: Empirically, semi-gradient TD methods work very well and converge reliably under standard conditions (like decaying learning rates and sufficient exploration), although they converge to a solution slightly different from the minimum MSVE solution.

In contrast, if you use the Monte Carlo target $U_t = G_t$, the target does not depend on the current weights $\mathbf{w}_t$. Therefore, SGD updates using the MC target are true gradient methods and are guaranteed to find a local minimum of the MSVE objective (assuming linear VFA and appropriate conditions).

The Learning Rate

The learning rate $\alpha$ is a hyperparameter that determines how large each update step is.

• If $\alpha$ is too large, the updates might overshoot the optimal weights, leading to oscillations or divergence.
• If $\alpha$ is too small, learning will be very slow.

In practice, $\alpha$ is often started at a moderate value and gradually decreased over time. This allows for larger adjustments early in training when the weights are likely far from optimal, and finer tuning later on.

By combining feature representations with gradient descent methods, we can now train RL agents on problems with state spaces far too large for the tabular methods we discussed previously. The next section introduces how non-linear function approximators, particularly neural networks, can be used to handle even more complex relationships between states and values.