Handling Large State Spaces

Algorithms like Q-learning and SARSA typically work by building a table. For Q-learning, this table stores a Q-value, $Q(s, a)$, for every possible state $s$ and action $a$. This approach is effective when the number of states and actions is reasonably small, such as in simple Gridworld examples. Values for each entry can be directly stored and updated based on experience.

"However, many applications of Reinforcement Learning present a significant challenge: the sheer size of the state space. Here are some examples:"

1. Games: A game like Chess has an estimated $10^{47}$ possible states. The game of Go has an astronomical number, often cited as larger than the number of atoms in the observable universe (around $10^{170}$). Storing a Q-table for every state is physically impossible.
2. Robotics: Imagine a robot arm with multiple joints. The state could be defined by the angle and velocity of each joint. Since these are continuous values, there are technically infinitely many states. Even if we discretize the angles and velocities, the number of combined states grows exponentially with the number of joints (this is often called the "curse of dimensionality"). For instance, if a robot has 6 joints, and we discretize each joint's angle into just 100 positions, we already have $100^6 = 10^{12}$ states, without even accounting for velocities.
3. Resource Management: Optimizing traffic light controls in a city involves states representing traffic flow at numerous intersections, which can change continuously and depend on many factors.

Let's visualize how quickly state spaces can grow. If each dimension of our state has $D$ possible values, and we have $k$ dimensions, the total number of states is $D^k$.

The number of states ($D^k$) grows exponentially with the number of state dimensions ($k$), quickly becoming computationally infeasible for tabular methods, even for moderate values per dimension ($D$). Note the logarithmic scale on the y-axis.

This explosive growth leads to several problems for tabular methods:

• Memory Requirements: We simply don't have enough memory (RAM or disk) to store the massive value tables (V-tables or Q-tables) required.
• Computational Cost: Even if we could store the table, learning the value for every single state would require an enormous amount of experience and computation time. Many states might be visited rarely, or never, during a practical training period.
• Lack of Generalization: Tabular methods treat each state independently. Learning about one state provides no information about other, potentially very similar, states. If a robot learns to navigate around an obstacle at position (1.0, 2.0), it has no inherent knowledge about navigating around an obstacle at (1.1, 2.0) unless it specifically experiences and updates that exact state entry in its table.

The way forward is to move from storing explicit values for every state to approximating the value function. We need a mechanism that can generalize from experienced states to unseen states. If we learn that certain states are good or bad, we want to infer that similar states are also likely good or bad.

This is where function approximation comes in. Instead of a table, we use a function (like a linear function, a neural network, or a decision tree) with a set of parameters $\mathbf{w}$. This function takes a state $s$ (or state-action pair $(s, a)$) as input and outputs an estimated value:

• State-value function approximation: $\hat{v}(s, \mathbf{w}) \approx V^\pi(s)$
• Action-value function approximation: $\hat{q}(s, a, \mathbf{w}) \approx Q^\pi(s, a)$

The number of parameters in $\mathbf{w}$ is typically much smaller than the number of states $|S|$. For example, we might have billions of states but only need a few thousand or million parameters in our function approximator. By adjusting these parameters $\mathbf{w}$ based on experience, we aim to find an approximation that works well across the entire state space, including states the agent hasn't visited before.

The following sections will explore how we can represent states in a way suitable for these functions and how we can adapt our learning algorithms (like TD learning) to update the parameters $\mathbf{w}$ instead of table entries. We will start with simpler linear function approximators before touching upon more complex non-linear ones like neural networks.