Function Approximation
in Reinforcement Learning

§1 Motivation & Intuition

The Curse of Dimensionality

Classical tabular RL — Q-tables, V-tables — represents the value function as a lookup table with one entry per state (or state-action pair). This is elegant and convergence-guaranteed, but collapses catastrophically as state spaces grow.

Why Tabular RL Fails

Three fundamental failures of tabular RL in real-world problems:

The Need for Generalization

The key insight is that nearby states should have similar values. A robot 1mm to the left vs 1mm to the right of a door threshold has nearly the same long-term reward potential. Function approximation exploits this smoothness by representing \(V\) or \(Q\) as a parametric function — learning generalizes across the entire state space from a subset of samples.

§2 Formal Setup

The MDP Framework

We work within a Markov Decision Process \(\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \gamma)\).

The Objects We Approximate

Function approximation can target three fundamental objects:

§3 Function Classes

Linear Function Approximation

The most theoretically tractable class. The approximated value function is linear in the feature representation of states:

where \(\phi: \mathcal{S} \to \mathbb{R}^d\) is a feature map and \(\theta \in \mathbb{R}^d\) are learnable weights. The key property: the function is linear in \(\theta\), not necessarily in \(s\) — the features \(\phi(s)\) can be highly nonlinear.

Basis Functions

Polynomial Basis

For \(s \in \mathbb{R}^n\), polynomial features: \(\phi(s) = [1, s_1, s_2, \ldots, s_1^2, s_1 s_2, \ldots]\). Degree-\(k\) polynomials give \(\binom{n+k}{k}\) features — still exponential in \(n\).

Fourier Basis

Periodic features that capture oscillatory structure:

Radial Basis Functions (RBF)

Gaussian bumps centered at prototype states \(\{s_1, \ldots, s_d\}\):

Neural Networks

Neural networks are universal function approximators — given sufficient width/depth, they can approximate any continuous function on a compact domain to arbitrary precision (Universal Approximation Theorem).

In practice, neural networks provide extraordinary expressiveness but come with optimization challenges: non-convex loss landscapes, saddle points, and — critically in RL — non-stationarity of training targets.

§4 Value Function Approximation

The Projection View

Let \(\mathcal{F} = \{\hat{V}(\cdot;\theta) : \theta \in \mathbb{R}^d\}\) be our function class. For linear FA, \(\mathcal{F}\) is a \(d\)-dimensional linear subspace of the space of all functions \(\mathcal{S} \to \mathbb{R}\).

The Bellman Operator

The Bellman operatorThe Bellman operator 𝒯 maps value functions to value functions. Its fixed point is the true value function V*. Key property: it is a γ-contraction under the max-norm. \(\mathcal{T}^\pi\) is central to all RL algorithms. For policy \(\pi\):

Key property: \(\mathcal{T}^\pi\) is a \(\gamma\)-contraction under the \(L^\infty\) norm, meaning repeated application converges to \(V^\pi\):

The Deadly Triad

Sutton and Barto identified three conditions whose simultaneous presence leads to instability and divergence in RL with function approximation.

§5 Core Algorithms

TD(0) with Function Approximation

Convergence of Semi-Gradient TD

Gradient TD Methods (GTD2, TDC)

To address off-policy divergence, Sutton et al. (2009) developed true gradient methods that converge under off-policy sampling by minimizing the projected Bellman errorThe Projected Bellman Error (PBE) is ‖ΠTᵖV − V‖²_μ. Unlike VE, its gradient includes terms from differentiating the TD target, making it a true gradient..

Fitted Value Iteration

An alternative: treat value estimation as a supervised regression problem. In each iteration, use the current value function to generate targets, then fit a new function.

§6 Q-Learning with Function Approximation

Semi-Gradient Q-Learning

Q-learning directly estimates the optimal Q-function \(Q^*\). With function approximation:

Deep Q-Network (DQN)

Mnih et al. (2015) made Q-learning with neural networks work in practice via two key tricks:

DQN Variants

§7 Policy Gradient & Actor-Critic

REINFORCE

Actor-Critic Methods

Replace the Monte Carlo return with a bootstrapped critic estimate to reduce variance:

where \(\hat{A}(s,a) = r + \gamma \hat{V}(s';\omega) - \hat{V}(s;\omega)\) is the advantage estimate. Two sets of parameters: \(\theta\) for the actor (policy), \(\omega\) for the critic (value function).

PPO, TRPO, SAC

§8 Approximate Dynamic Programming

Fitted Q-Iteration (FQI)

FQI is the batch analog of Q-learning. Given a fixed dataset \(\mathcal{D}\), it iteratively applies the Bellman optimality operator and projects back onto the function class:

Batch RL

Batch RL encompasses methods that learn from a fixed dataset without additional interaction. Key algorithms include:

• Fitted Q-Iteration (FQI): Regression-based Bellman iteration
• LSTD (Least-Squares TD): Direct solution to the linear TD fixed-point equation
• LSPI (Least-Squares Policy Iteration): Policy iteration using LSTD for evaluation
• NFQ (Neural Fitted Q-Iteration): FQI with neural network function approximator

LSTD: Direct Solution

For linear FA, the TD fixed-point satisfies \(A\theta = b\). LSTD estimates \(A\) and \(b\) from data and solves directly:

LSTD is data-efficient (no learning rate) but \(\mathcal{O}(d^2)\) in memory and \(\mathcal{O}(d^3)\) in computation per update. For large feature dimensions, LSTD(λ) or recursive variants are needed.

§9 Offline RL Connection

The Offline RL Problem

Offline (or batch) RL aims to learn the best possible policy from a fixed dataset \(\mathcal{D} = \{(s, a, r, s')\}\) collected by some (possibly unknown) behavior policy \(\mu\), without further environment interaction.

Distribution Shift

The learned policy \(\pi_\theta\) may visit state-action pairs not in the training distribution \(\mu\). Under the learned policy, the true Q-values in out-of-distribution (OOD) regions are unknown, but the model may assign arbitrarily high values there.

Offline RL Solutions

Conservative Q-Learning (CQL)

CQL (Kumar et al., 2020) adds a regularization term to the standard Q-learning objective that pushes down Q-values for OOD actions while maintaining accuracy for in-distribution ones:

§10 Theory

Approximation vs Estimation Error

The total error in value function learning decomposes into two components:

Bellman Error Minimization

The Bellman residual or Bellman error at a function \(f\) is:

Minimizing BE directly is appealing but faces the double sampling problem: the gradient of BE requires two independent samples from the same state, which is typically unavailable in sequential data.

Stability: Positive Definiteness of A

For linear TD, the key stability condition is that the matrix \(A = \Phi^\top D(I - \gamma P^\pi)\Phi\) be positive definite. This holds when:

• On-policy: \(D\) is the stationary distribution of \(\pi\), which satisfies a balance condition making \(A\) PD.
• Off-policy: No guarantee. \(A\) can have negative eigenvalues, causing divergence (Baird's example).

Concentrability Coefficients

Munos (2003, 2005) formalized how the mismatch between training distribution \(\mu\) and target distribution affects error propagation in ADP. The concentrability coefficient:

measures how quickly the policy occupancy can grow relative to the data distribution. When data lacks coverage, \(c(m)\) is large, and approximation errors compound over policy iterations.

Neural Tangent Kernel (NTK) Perspective

For overparameterized neural networks, training dynamics in the lazy training regime are governed by the Neural Tangent Kernel \(K(s, s') = \nabla_\theta f_\theta(s)^\top \nabla_\theta f_\theta(s')\). This kernel remains approximately constant during training, effectively reducing to linear FA in feature space defined by the network Jacobian.

§11 Modern Advances

Deep RL Scaling

Modern deep RL systems (AlphaZero, MuZero, Gato, RT-2) show that scale matters enormously. Larger networks, more diverse training environments, and longer training lead to emergent capabilities not seen in smaller systems. Key insights:

• Transformer-based policies (Decision Transformer, Gato) treat RL as sequence modeling
• World models (DreamerV3) enable efficient learning from raw pixels via imagined rollouts
• Foundation model pre-training for RL initialization

Representation Learning in RL

The quality of the state representation \(\phi(s)\) fundamentally determines the difficulty of function approximation. Modern approaches to learning representations:

Offline RL Progress

Offline RL has seen dramatic progress since 2020, enabling learning from large pre-collected datasets:

• IQL (Implicit Q-Learning): Avoids evaluating OOD actions entirely via expectile regression
• Decision Transformer: Reframes offline RL as conditional sequence modeling
• Offline-to-Online: Fine-tuning offline-learned policies with online interaction
• Dataset scaling: D4RL, RoboMimic, Bridge Data — larger offline datasets enable better policies

Implicit Regularization in Neural FA

Recent work shows that gradient descent on neural networks in RL has implicit regularization effects. Overparameterized networks may converge to minimum-norm solutions, and the inductive biases of specific architectures (CNNs for spatial tasks, Transformers for sequential tasks) can be understood through the lens of function approximation.

§12 Historical Timeline

Summary

References

• [1]
  Reinforcement Learning: An Introduction (2nd ed.)

  Sutton, R.S. & Barto, A.G. (2018). MIT Press. — The canonical textbook. Chapters 9–13 cover function approximation thoroughly.
• [2]
  An Analysis of Temporal-Difference Learning with Function Approximation

  Tsitsiklis, J.N. & Van Roy, B. (1997). IEEE Transactions on Automatic Control. — Proves convergence of linear TD under on-policy sampling.
• [3]
  Error Bounds for Approximate Policy Iteration

  Munos, R. (2003). ICML. — Introduces concentrability coefficients and error propagation bounds for ADP.
• [4]
  Fast Gradient-Descent Methods for Temporal-Difference Learning

  Sutton, R.S., Maei, H.R., et al. (2009). ICML. — GTD2 and TDC: true gradient methods for off-policy learning.
• [5]
  Human-Level Control through Deep Reinforcement Learning

  Mnih, V., et al. (2015). Nature. — DQN: experience replay + target networks enable deep Q-learning.
• [6]
  Reinforcement Learning: Theory and Algorithms

  Agarwal, A., Jiang, N., Kakade, S., & Sun, W. (2022). — Modern theoretical treatment with sample complexity guarantees.
• [7]
  Conservative Q-Learning for Offline Reinforcement Learning

  Kumar, A., et al. (2020). NeurIPS. — CQL: pessimistic Q-learning for offline settings.
• [8]
  Offline Reinforcement Learning: Tutorial, Review, and Perspectives

  Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020). arXiv. — Comprehensive survey of offline RL methods and theory.
• [9]
  Policy Gradient Methods for Reinforcement Learning with Function Approximation

  Sutton, R.S., McAllester, D., Singh, S., & Mansour, Y. (2000). NeurIPS. — The Policy Gradient Theorem.
• [10]
  Mastering Atari, Go, Chess and Shogi without Rules (MuZero)

  Schrittwieser, J., et al. (2020). Nature. — Deep model-based RL at scale with learned world models.