Function Approximation in Reinforcement Learning

The methods reviewed so far, such as Q-Learning, SARSA, and basic Policy Gradients, often rely on a tabular representation of value functions (like $V(s)$ or $Q(s, a)$ ) or policies ( $\pi(a|s)$ ). This means we maintain an explicit value or probability for every single state, or state-action pair. While simple and theoretically well-understood in small, discrete environments (like tic-tac-toe or small grid worlds), this approach quickly becomes impractical as the complexity of the problem grows.

The Limits of Tabular Representations

Environments with very large or continuous state spaces present a challenge.

Games: Chess has an estimated $10^{47}$ states, and Go has around $10^{170}$ . Storing a table for these is impossible. Even simpler video games like Atari Pong, if represented naively by pixel values, have an astronomically large number of possible screen configurations (states).
Robotics: A robot arm's state might be defined by the continuous angles and velocities of its joints. A mobile robot's state includes its continuous position and orientation. Discretizing these spaces finely leads to an explosion in the number of states, while coarse discretization loses important information.
Practical Control: Controlling industrial processes, managing financial portfolios, or optimizing logistics networks involves high-dimensional state spaces, often with continuous variables.

This explosion in the number of states or state-action pairs is often called the curse of dimensionality. Tabular methods suffer from it in two main ways:

Memory: Storing the table requires enormous amounts of memory.
Learning Time: Each state or state-action pair must be visited potentially many times to obtain accurate estimates. In large spaces, an agent might never encounter most states, making learning impossibly slow or incomplete.

Furthermore, tabular methods cannot generalize. Learning about one state provides no information about similar, unvisited states. If you learn that a particular chess position is bad, a tabular method has no way to infer that a very slightly different, but strategically equivalent, position is also bad without visiting it explicitly.

Introducing Parameterized Function Approximation

To overcome these limitations, we introduce function approximation. Instead of storing explicit values for each state or state-action pair in a table, we use a parameterized function, often denoted with parameters $\theta$ , to approximate the true value function or policy.

Value Function Approximation:
- State-value function: $V(s) \approx \hat{V}(s; \theta)$
- Action-value function: $Q(s, a) \approx \hat{Q}(s, a; \theta)$
Policy Approximation:
- Stochastic Policy: $\pi(a|s) \approx \pi_\theta(a|s)$
- Deterministic Policy: $a = \mu(s) \approx \mu_\theta(s)$

Here, $\hat{V}$ , $\hat{Q}$ , $\pi_\theta$ , and $\mu_\theta$ represent functions (like linear functions, neural networks, decision trees, etc.) whose behavior is determined by the parameter vector $\theta$ . The goal of the learning algorithm becomes finding the parameters $\theta$ that make the approximation as accurate as possible.

Contrasting tabular methods with function approximation for representing value functions or policies.

Types of Function Approximators

Various function approximators can be used in RL:

Linear Function Approximation: This is the simplest form. We first define a feature vector $\phi(s)$ that represents the state $s$ (or $\phi(s, a)$ for state-action pairs). The approximation is then a linear combination of these features:
$\hat{V}(s; \theta) = \theta^T \phi(s) = \sum_{i=1}^d \theta_i \phi_i(s)$ $\hat{Q}(s, a; \theta) = \theta^T \phi(s, a) = \sum_{i=1}^d \theta_i \phi_i(s, a)$
Here, $d$ is the number of features. The quality of approximation heavily depends on the quality of the hand-crafted features $\phi$ . While simple and computationally efficient, linear methods may lack the capacity to represent complex, non-linear value functions or policies.
Non-linear Function Approximation (Neural Networks): Deep Neural Networks (DNNs) have become the dominant choice for function approximation in modern RL, leading to the field of Deep Reinforcement Learning (DRL). A neural network can learn complex, non-linear relationships directly from raw inputs (like pixels from a screen or joint angles) without requiring manual feature engineering.
- Value Networks: $\hat{V}(s; \theta)$ or $\hat{Q}(s, a; \theta)$ are represented by a neural network with parameters $\theta$ (weights and biases).
- Policy Networks: $\pi_\theta(a|s)$ or $\mu_\theta(s)$ are represented by a neural network. For discrete actions, the network typically outputs probabilities for each action (e.g., using a softmax output layer). For continuous actions, it might output the mean and possibly variance of a distribution (e.g., Gaussian).
Common architectures include Multi-Layer Perceptrons (MLPs) for vector inputs, Convolutional Neural Networks (CNNs) for image inputs, and Recurrent Neural Networks (RNNs, like LSTMs or GRUs) for sequential inputs or partially observable environments. The power of DNNs lies in their ability to learn hierarchical features automatically and approximate highly complex functions.

How Algorithms Adapt

RL algorithms are adapted to work with function approximators, typically by using gradient-based optimization methods. Instead of updating table entries, we update the parameters $\theta$ .

Value-Based Methods (e.g., Q-Learning): In tabular Q-learning, the update rule adjusts $Q(s_t, a_t)$ towards a target value $y_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$ . With function approximation $\hat{Q}(s, a; \theta)$ , we treat this as a supervised learning problem. The target $y_t$ (often computed using a separate, slowly updated target network $\theta^-$ for stability, as we'll see in Chapter 2) becomes the "label" for the input $(s_t, a_t)$ . We aim to minimize the error between the predicted Q-value $\hat{Q}(s_t, a_t; \theta)$ and the target $y_t$ . A common loss function is the Mean Squared Bellman Error (MSBE):
$L(\theta) = \mathbb{E} \left[ (y_t - \hat{Q}(s_t, a_t; \theta))^2 \right]$
where $y_t = r_{t+1} + \gamma \max_{a'} \hat{Q}(s_{t+1}, a'; \theta^-)$ . The parameters $\theta$ are then updated using gradient descent on this loss: $\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta)$ .
Policy-Based Methods (e.g., REINFORCE): As reviewed earlier, the policy gradient theorem provides an expression for the gradient of the expected return $J(\theta)$ :
$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} G_t \nabla_\theta \log \pi_\theta(a_t|s_t) \right]$
Here, $\pi_\theta(a|s)$ is our parameterized policy (e.g., a neural network). We estimate this gradient using sampled trajectories $(\tau)$ generated by running the current policy $\pi_\theta$ in the environment. The parameters are then updated using gradient ascent: $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$ .
Actor-Critic Methods: These methods, which we will explore in detail in Chapter 3, use function approximation for both the policy (actor) and the value function (critic). The critic helps provide lower-variance estimates for the policy update, combining ideas from both value-based and policy-based approaches.

Benefits and Challenges

Using function approximation offers significant advantages:

Scalability: Enables RL in large or continuous state/action spaces where tabular methods fail.
Generalization: Allows the agent to generalize knowledge from visited states to similar, unseen states. If $\hat{V}(s_1; \theta)$ is high, and $s_2$ is "close" to $s_1$ (in terms of features or network representation), then $\hat{V}(s_2; \theta)$ is also likely to be high.
Efficiency: Can potentially learn faster by leveraging the underlying structure of the state space captured by the approximator. Deep learning methods can perform automatic feature extraction.

However, it also introduces new challenges:

Loss of Convergence Guarantees: Unlike tabular methods, convergence to the optimal value function or policy is not always guaranteed, especially with non-linear approximators and off-policy data.
Instability: Learning can become unstable or diverge. This is particularly problematic when combining three elements: function approximation, off-policy learning (learning from data generated by a different policy), and bootstrapping (updating estimates based on other estimates, like in TD learning). This combination is known as the "Deadly Triad", which we will discuss next.
Hyperparameter Sensitivity: Performance can be highly sensitive to the choice of approximator architecture, learning rates, optimization algorithms, and other hyperparameters.

"Function approximation is indispensable for applying RL to complex problems. Understanding how to integrate it effectively with core RL algorithms, and being aware of the associated challenges, is fundamental to mastering advanced reinforcement learning techniques. The subsequent chapters will build extensively on these ideas, particularly using deep neural networks as the primary function approximators."

References

Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto, 2018 (The MIT Press) - A comprehensive textbook covering foundational reinforcement learning concepts, including tabular methods, function approximation (linear and non-linear), policy gradient methods, and challenges like the deadly triad.
Human-level control through deep reinforcement learning, Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg and Demis Hassabis, 2015 Nature, Vol. 518 (Nature Publishing Group) DOI: 10.1038/nature14236 - Introduces Deep Q-Networks (DQN), a seminal work that successfully combines deep neural networks with reinforcement learning, using techniques like experience replay and target networks to stabilize learning with function approximation.
Reinforcement Learning Lecture 6: Value Function Approximation, David Silver, 2015 (UCL) - Lecture notes from a highly respected reinforcement learning course, offering an accessible overview of value function approximation methods and their integration with RL algorithms.