When using linear function approximation how (and why) should I incorporate the actions into the feature vector?

Question

When reading R. Sutton: Reinforcement Learning - An Introduction (2nd edition), in chapter 10.1 Episodic Semi-gradient Control, the Mountain Car problem is mentioned and as an example it is solved using Semi-Gradient Sarsa for estimating the action-value function.

Now they use a linear function representation with some feature vector $\vec{x}$:

$$ \hat{q}(s, a, \vec{w}) = \vec{w}^T\cdot\vec{x}(s, a) $$

where $\vec{w}$ is a weight vector (to be learned) and $s, a$ are the state and action respectively (only discrete actions are considered). I understand that feature vectors are used because the "raw" information contained in the state observation $s$ might not be sufficient (for example interactions could be important and hence a polynomial feature representation appropriate). Specifically they used tile coding.

However it is not clear why the feature vector would be computed from the action as well. Especially when considering the update rule corresponding to the above equation we have:

$$ \vec{w}_{t+1} = \vec{w}_t + \alpha\,\delta_t\nabla_{\vec{w}}\hat{q}(s_t, a_t, \vec{w}_t) = \vec{w}_t + \alpha\,\delta_t\,\vec{x}(s_t, a_t) $$

where $\alpha$ is the step size and $\delta_t$ is the temporal difference error.

Since we are updating for a specific action only, most of the entries in $\vec{x}(s_t, a_t)$ will be zero, especially those for $a \neq a_t$. If, on the other hand, we represented the action-value function by a matrix $\mathbf{W}$, where each column corresponds to one action, we could use the following form:

$$ \hat{q}(s, a, \mathbf{W}) = \left(\vec{x}(s)^T\cdot\mathbf{W}\right)_a $$

where we use the same feature vector for each column of weights to compute the corresponding action. This comes with the following update rule:

$$ \mathbf{W}_{t+1, a} = \mathbf{W}_{t, a} + \alpha\,\delta_t\,\vec{x}(s_t) $$

which only updates the relevant weights and avoids all the unnecessary zero additions from the previous representation.

This comes at the "limitation" (is it one?) that there is no "cross-talk" between actions. I.e. when one action is executed and the weights are updated accordingly then there is no influence on other actions in the same state.

So my two questions are:

• Should one representation be preferred over the other? If so, in which situations?
• Are there any scenarios in which "cross-talk" between actions becomes important? I.e. that executing one action should influence the estimate of other actions as well? If so, how would I encode this in my feature representation $\vec{x}(s, a)$?

Answer 1

Function approximation is used for its ability to generalize. Your proposal to parameterize $\hat{q}$ with a matrix $\mathbf{W}$ prevents any sort of generalization (or "cross-talk") across different actions. Depending on your set of actions, you might not need this generalization, and your approach might work just fine. I think this is probably true for the mountain car problem.

However, imagine a 2d analogue to this problem in which the car had to choose a an angle of velocity $0 \leq \theta \leq 360$ that was discretized into 36 actions that are increments of $10^o$. (We're imagining a car that could accelerate in any one of these directions instantaneously.) I wouldn't be surprised if "cross-talk" enabled the agent to learn more quickly that $\hat{q}(s,20^o)$ is often similar to $\hat{q}(s,30^o)$, for example.

As far as feature selection goes, I'd suggest tile coding, described on page 217 of the book you mentioned. By selecting the shape, spacing, and size of your tiles, you can control the nature of the resulting generalization across the state and action space.