Introduction to Function Approximation

As we saw in the previous chapter, traditional methods like Q-learning and SARSA rely on tables to store value estimates (Q-values) for every state or state-action pair. This approach works well when the number of states and actions is manageably small, such as in simple grid worlds or tic-tac-toe.

However, many interesting problems have enormous or even infinite state spaces. Consider these scenarios:

• Playing Atari games from pixels: The state is the raw pixel data from the screen. Even a low-resolution screen (e.g., 84x84 pixels) with a few colors results in a number of possible states far exceeding the number of atoms in the universe. Storing a Q-table is impossible.
• Robotics control: A robot's state might involve joint angles, velocities, sensor readings (like lidar or camera feeds), all of which can be continuous values. An infinite number of states exist.
• Financial modeling: Market states can involve numerous continuous indicators, leading to vast state spaces.

In these situations, the tabular approach breaks down completely due to the curse of dimensionality. We face two major challenges:

1. Memory: We simply don't have enough memory to store the Q-table.
2. Learning Time & Generalization: Even if we had the memory, the agent would need an impractical amount of time to visit and learn values for even a fraction of the possible states. Furthermore, the agent wouldn't be able to generalize its knowledge. Learning about one specific state provides no information about similar, previously unseen states. If the screen pixels change slightly, a tabular method treats it as a completely new state requiring separate learning.

To handle these complex, large-scale problems, we need a more scalable approach. Instead of storing explicit values for every single state-action pair, we can approximate the value function using a parameterized function. This technique is called function approximation.

The core idea is to use a function, let's call it $\hat{Q}(s, a; \theta)$, that takes the state $s$ (and possibly the action $a$) as input and outputs an estimate of the true Q-value $Q(s, a)$. The function has a set of parameters, denoted by $\theta$, which we will learn and adjust based on the agent's experience.

Comparing tabular lookup with function approximation for obtaining Q-values. Function approximation uses a parameterized function to estimate values, enabling scalability and generalization.

Function approximation offers significant advantages:

• Compact Representation: Instead of storing potentially billions or trillions of Q-values, we only need to store the parameters $\theta$ of our function. The number of parameters is typically much smaller than the number of states.
• Generalization: This is perhaps the most important benefit. If the function approximator learns a good representation, it can estimate reasonable Q-values for states it has never encountered before, based on their similarity to states it has seen. This allows the agent to make sensible decisions in novel situations.
• Handling Continuous Spaces: Parameterized functions, especially neural networks, can naturally handle continuous input features, making them suitable for problems with continuous state or action spaces where tables are fundamentally impossible.

Various types of functions can serve as approximators, including linear functions, decision trees, and tile coding. However, for complex problems involving high-dimensional inputs like images or intricate state representations, deep neural networks have proven exceptionally effective. Their ability to learn hierarchical features and model complex, non-linear relationships makes them powerful Q-function approximators.

In this chapter, we will focus specifically on using deep neural networks to approximate the action-value function $Q(s, a)$. This combination forms the basis of Deep Q-Networks (DQN), marking a significant step forward from tabular methods and enabling reinforcement learning to tackle much more complex tasks. We will now look at how to construct and train such a network.