As we discussed in the chapter introduction, representing value functions using tables becomes infeasible when dealing with problems that have a very large number of states or continuous state spaces. Imagine trying to create a table entry for every possible pixel configuration on a screen or every possible joint angle combination for a complex robot! Function approximation provides a way forward by estimating the value function using a more compact representation. A fundamental step in this process is defining how we represent the state $s$ itself as input to our approximator. Instead of using the raw state description, we often work with a feature vector, denoted as $x(s)$ .

A feature vector $x(s)$ is typically a column vector of real-valued numbers that captures important properties of the state $s$ :

x(s) = \begin{pmatrix} x_1(s) \\ x_2(s) \\ \vdots \\ x_d(s) \end{pmatrix}

Here, $d$ is the number of features, and each $x_i(s)$ is the value of the $i$ -th feature for state $s$ . The crucial idea is that the number of features $d$ is usually much, much smaller than the total number of states $|S|$ . This compressed representation allows our learning algorithm to generalize. If two states $s$ and $s'$ have similar feature vectors, $x(s) \approx x(s')$ , the function approximator will likely produce similar value estimates for them, even if one of the states has never been visited.

What Makes a Good Feature?

The goal is to select features that are informative about the state's value. Good features should:

Capture Essential Information: They should represent the aspects of the state that are most relevant for predicting future rewards. Information irrelevant to the task can often be discarded.
Enable Generalization: States that require similar actions or have similar expected returns should have similar feature representations.
Form a Compact Representation: The feature vector should have significantly lower dimensionality ( $d$ ) compared to the size of the state space ( $|S|$ ), especially for large or continuous spaces.

The process of designing these features is often called feature engineering. It can range from simple techniques to quite sophisticated ones, sometimes requiring significant domain expertise.

Common Feature Engineering Techniques

Let's look at some ways to construct feature vectors:

1. Raw State Information (Low-Dimensional Problems)

For some problems, the state representation might already be a relatively low-dimensional vector of numerical values. In the classic CartPole environment, for instance, the state is often represented by four numbers: cart position, cart velocity, pole angle, and pole angular velocity.

s = (\text{position}, \text{velocity}, \text{angle}, \text{angular velocity})

In such cases, we might simply use the state representation directly as the feature vector:

x(s) = \begin{pmatrix} \text{position} \\ \text{velocity} \\ \text{angle} \\ \text{angular velocity} \end{pmatrix}

Even here, normalization or scaling of these raw values is often beneficial.

2. Hand-Crafted Features (Domain Expertise)

When the raw state is complex (like an image or a configuration in a board game), we can use our understanding of the problem domain to manually define relevant features.

Games: In chess, features could include material balance (difference in piece values), king safety (number of attacking pieces), control of the center squares, pawn structure evaluation, etc.
Robotics: For a robot navigating a room, features might include distance to the nearest obstacle in different directions, distance to the goal, current battery level, or whether it's currently carrying an object.

Creating good hand-crafted features often requires iteration and experimentation.

3. Polynomial Basis Functions

If the underlying value function is expected to be a non-linear function of some basic state variables, we can create polynomial features. For a state $s$ with basic features $f_1(s)$ and $f_2(s)$ , we could create a feature vector including polynomial terms:

x(s) = (1, f_1(s), f_2(s), f_1(s)^2, f_2(s)^2, f_1(s)f_2(s), \dots)^T

The constant feature '1' allows the approximator to learn a bias term. This approach can capture some non-linearities but can lead to a high number of features quickly.

4. Tile Coding (Coarse Coding)

Tile coding is a popular technique, especially for continuous state spaces. It discretizes the space by overlaying multiple grids (tilings), each offset from the others. A state activates one tile in each tiling. The feature vector $x(s)$ is then typically a large binary vector where each component corresponds to one tile across all tilings. A component is 1 if the corresponding tile is active for state $s$ , and 0 otherwise.

A conceptual illustration of tile coding in 2D. A state (red dot) falls into one tile in each offset grid (Tiling 1 and Tiling 2). The active tiles (e.g., b2 and y3) correspond to '1' entries in the binary feature vector.

The key benefit of tile coding is its ability to provide good generalization. States close to each other will share some active tiles, leading to similar feature vectors and thus similar value estimates. The degree of generalization is controlled by the width of the tiles and the number/offset of the tilings.

5. Radial Basis Functions (RBFs)

Another approach for continuous spaces involves using Radial Basis Functions. You define a set of prototype points (centers) $c_i$ in the state space. The features are then calculated based on the distance between the current state $s$ and these centers, typically using a function like a Gaussian kernel:

x_i(s) = \exp\left( - \frac{\| s - c_i \|^2}{2 \sigma_i^2} \right)

Each feature $x_i(s)$ measures the similarity of state $s$ to the center $c_i$ . States near a particular center will have a high value for the corresponding feature. Like tile coding, RBFs provide smooth generalization.

6. Learned Features (Deep Learning)

Instead of manually designing features, we can use powerful function approximators like deep neural networks to learn the relevant features directly from raw, high-dimensional input (like pixels from a screen or sensor readings). This is the core idea behind Deep Reinforcement Learning, which we will introduce in Chapter 7 (Deep Q-Networks). The network's hidden layers transform the raw input into progressively more abstract and useful representations (features) that are then used by the output layer to estimate the value function.

Features for Action-Values

So far, we've focused on features $x(s)$ for state-value functions $V(s)$ . When approximating action-value functions $Q(s, a)$ , the features usually need to depend on both the state and the action. We denote this feature vector as $x(s, a)$ .

A common approach is to first compute state features $x(s)$ and then combine them based on the action $a$ . For example, if there are $|A|$ discrete actions, one might construct $x(s, a)$ by taking the state feature vector $x(s)$ and placing it into a specific block of a larger vector, corresponding to action $a$ , with zeros elsewhere.

The Role of Features in Approximation

Once we have a feature vector $x(s)$ (or $x(s, a)$ ), it serves as the input to our chosen function approximator. For example, in linear function approximation (which we'll cover next), the value function is estimated as a weighted sum of the features:

\hat{v}(s, \mathbf{w}) \approx \mathbf{w}^T x(s) = \sum_{i=1}^d w_i x_i(s)

or for action-values:

\hat{q}(s, a, \mathbf{w}) \approx \mathbf{w}^T x(s, a) = \sum_{i=1}^d w_i x_i(s, a)

Here, $\mathbf{w} = (w_1, w_2, \dots, w_d)^T$ is the vector of weights (parameters) that the RL algorithm learns. The goal of the learning process is to find the weights $\mathbf{w}$ such that the approximation $\hat{v}$ or $\hat{q}$ is close to the true value function $v_\pi$ or $q_\pi$ .

Choosing or designing appropriate features is often critical for the success of function approximation methods in reinforcement learning. Good features make the learning task easier and enable effective generalization across the state space. In the following sections, we will explore how to learn the weights $\mathbf{w}$ using these feature representations.