Unclear paragraph in Sutton-Barto on "Tile Coding"

Question

Sutton-Barto (Tile Coding, page 218):

For example, choosing $\alpha = 1/n$, where n is the number of tilings, results in exact one-trial learning. If the example $s\to v$ is trained on, then whatever the prior estimate, $\hat{v}(s,w_t)$, the new estimate will be $\hat{v}(s,w_t)=v$.

This part is not clear for me. I need to see mathematically why that is the case.

Answer 1

In short, this works because the derivative of the (implied) loss function happens to be numerically equal to the difference between current estimate and the target (this is actually a relatively common setup in regression and classifier estimators). In turn, the partial derivatives of weights associated with active tiles in tile coding each inherit that property, because their derivative factor used in the chain rule to figure out the impact of changing them in isolation is exactly 1 (whilst inactive weights have a factor of 0 and are not important to the calculation).

Taking a unit step for any single weight would correct the current estimate to the new observed value. As the next part of the text in S&B explains, you would not usually make such an update step if you need the estimator to generalise.

We can show this a little more rigorously using the formulae from the book. The general update rule for estimators is:

$$\mathbf{w} \leftarrow \mathbf{w} + \alpha[G - \hat{v}(s, \mathbf{w})]\nabla \hat{v}(s, \mathbf{w})$$

Where $G$ is the sampled or measured return, and $G - \hat{v}(s, \mathbf{w})$ is therefore a measure of the error in the estimate.

Let's call the error in the estimate $\delta$, we can treat that as a single number from now on - any update that adjusts the estimate by $\delta$ makes it match the new data exactly.

So now we have:

$$\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta \nabla \hat{v}(s, \mathbf{w})$$

In linear approximators, we have feature vector $\mathbf{x} = x(s)$, and:

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

Therefore:

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

In tile coding, we always have $n$ active features (the $n$ tiles that the current state vector is contained by) with a feature vector value of $1$, and the rest are $0$. In terms of calculating $\hat{v}$ we can ignore all the $0$ values. The value of $\hat{v}$ is the sum of all the active weights that are associated with the $n \times 1$ values. For convenience (of keeping the notation simple) we can create a vector of length $n$ which is only the weights associated with those $1$s - let's call that $\mathbf{w^1}$. The associated part of $\mathbf{x}$ is a vector of $n$ $1$s that we can call $\mathbf{1}_n$

With the new vector, only for this one specific value of $s$ that has these specific $n$ features:

$$\hat{v}(s,\mathbf{w^1}) = \sum_{i=1}^n \mathbf{w^1}_i$$

Now the update rule for the selected weights is:

$$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\nabla \hat{v}(s, \mathbf{w^1})$$

We also know that $\nabla \hat{v}(s, \mathbf{w^1}) = \mathbf{1}_n$. This matches to the intuition used in the S&B quote - if you change any active weight by some amount $y$, then the estimate also changes by that amount. Second-order derivatives need to be always zero for this to hold, otherwise you cannot make such easy statements about large changes (e.g. this logic would not work for any neural network).

So the update rule becomes:

$$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\mathbf{1}_n$$

This causes a change to the value estimate:

$$\hat{v}(s,\mathbf{w^1} + \alpha\delta\mathbf{1}_n) = \hat{v}(s,\mathbf{w^1}) + \sum_{i=1}^n \alpha\delta$$

That is when calculated using the old $\mathbf{w^1}$ from before the update - this works as above because $(\mathbf{w^1} + \mathbf{y})\mathbf{x} = \mathbf{w^1}\mathbf{x} + \mathbf{y}\mathbf{x}$

A correction of $\delta$ would be "perfect" for the single data point, so if we want that, we want:

$$\delta = \sum_{i=1}^n \alpha\delta = n \alpha\delta$$

or

$$\alpha = \frac{1}{n}$$