Generalizing Tabular Reinforcement Learning to Function Approximation

10 concepts21 papers1 proposal

In theoretical reinforcement learning (RL), there is a mathematical paradise known as the tabular setting. In a tabular Markov Decision Process (MDP), the state and action spaces are discrete and small enough that we can maintain a literal lookup table, dedicating a unique row and column to every single state-action pair.

Because every state is isolated from every other state, updates to our value estimates are perfectly decoupled. This isolation allows theorists to prove remarkable guarantees about efficiency, convergence, and optimality.

However, real-world environments are continuous, high-dimensional, and effectively infinite. To scale RL, we must replace lookup tables with function approximation—such as linear models or deep neural networks—that compress the state space and generalize across similar states. Yet, when we move from tables to functions, the mathematical machinery that guarantees success frequently breaks down. Bridging this "function approximation gap" is one of the most significant open challenges in modern RL theory.


The Tabular Paradise: What We Can Prove

To understand why function approximation is difficult, we must first appreciate the extraordinary guarantees we can achieve when we don't use it. In the tabular setting, researchers have successfully pushed algorithms to their absolute theoretical limits across several dimensions:

1. Minimax and Instance Optimality

In a tabular MDP, we can determine exactly how many samples are required to find an optimal policy. For example, He et al. introduced an algorithm that achieves the absolute minimax lower bound for discounted MDPs, effectively closing a long-standing sample-efficiency gap. When the environment possesses a clear "gap" between the best action and the second-best action, Xu et al. demonstrated that we can exploit this structure to achieve even tighter, gap-dependent performance bounds.

This precision extends to offline RL (learning from a fixed dataset) and pure exploration. Yin et al. established instance-optimal bounds for offline settings tailored to the exact difficulty of individual environments, while Li et al. proved minimax-optimal bounds for reward-agnostic exploration, where an agent explores an environment effectively without knowing the reward function in advance.

2. Distributional and Robust RL

Tabular isolation also simplifies tracking complex statistics beyond expected values. In distributional RL, where we map the entire probability distribution of future returns, Rowland et al. and Peng et al. independently proved that learning a full distribution is statistically no harder than learning a single mean value, achieving near-minimax optimality.

When the deployment environment shifts from the training environment, distributionally robust RL provides a safety net. Zhou et al. provided the first finite-sample optimal regret bounds for robust offline RL, and Clavier et al. demonstrated a "robustness dividend," showing that high environmental uncertainty can sometimes actually reduce the number of samples needed to find a robust policy.

3. Constraints and Game Dynamics

Safety and multi-agent competition are highly manageable in tabular forms. For Constrained MDPs (CMDPs), Gattami et al. guaranteed convergence by reframing the problem as a Markov-Bandit game, while Stradi et al. provided algorithms that handle both adversarial losses and hard stochastic safety constraints simultaneously. In competitive zero-sum Markov games, Cen et al. achieved fast "last-iterate" convergence, ensuring that the final policy learned by the agents is an equilibrium, rather than just an average of past attempts.

4. Fundamental Convergence

At a foundational level, tabular isolation allows for airtight convergence proofs. This includes the finite-sample analysis of contractive stochastic approximation by Chen et al., the stability of two-time-scale natural actor-critic algorithms by Doan 0001 et al., optimal posterior sampling for policy identification by Kone et al., and the almost sure convergence of average-reward Temporal Difference (TD) learning by Zhang et al..


Why the Tabular Machinery Breaks Down

If our tabular algorithms are so powerful, why can't we simply apply them to neural networks? The answer lies in three fundamental mathematical friction points introduced by function approximation.

Intuition 1: The Loss of Isolation (State Aliasing)

In a table, updating the value of State A has zero impact on State B.

Tabular Update:
[State A: Q=2.5]  --> Update -->  [State A: Q=3.0]
[State B: Q=1.2]                  [State B: Q=1.2] (Unchanged)

In function approximation, states are mapped to a lower-dimensional feature space or share weights in a neural network. When you update the network to correct an error at State A, the weights shift. Because State B shares those same weights, its value estimate changes too.

Function Approximation Update:
Shared Weights [W] --> Predicts Q(A) and Q(B)
Update Weights to fix Q(A) --> [W'] --> Alters BOTH Q(A) and Q(B)

This coupling destroys the $L_\infty$-norm contraction property of the Bellman operator. In tabular RL, every time we apply a Bellman backup, our estimates strictly get closer to the true values. With function approximation, the geometric projection step required to fit the function can fight against the Bellman update, causing value estimates to spiral outward and diverge.

Intuition 2: The Failure of Counting-Based Exploration

To achieve optimal sample complexity, an agent must explore intelligently. Tabular algorithms like UCBVI-$\gamma$ rely on counting exactly how many times a specific state-action pair $(s,a)$ has been visited to calculate an uncertainty bonus.

In a continuous or high-dimensional space, the agent will almost never visit the exact same state twice. If every state is unique, a tabular counting mechanism sees every state as completely unvisited, causing the exploration bonus to fail. Generalizing uncertainty across a continuous space requires making structural assumptions about the environment, which introduces bias and invalidates minimax guarantees.

Intuition 3: Non-Linear Optimization Landscapes

Tabular updates are essentially linear operations on vectors. Proving that an algorithm converges "almost surely" or reaches a stable equilibrium is straightforward because the underlying optimization landscape is convex.

When we introduce deep neural networks, we introduce highly non-linear, non-convex optimization landscapes filled with saddle points and local minima. The elegant Lyapunov functions used to prove tabular convergence—such as the smooth convex envelopes developed by Chen et al.—cannot easily accommodate the erratic trajectories of neural network weights during gradient descent.


Bridging the Chasm

Every single one of the aforementioned papers concludes with a similar caveat: their guarantees are currently restricted to the tabular setting, and extending them to function approximation remains an open challenge.

How is the field attempting to bridge this gap?

[ Tabular MDPs ]  ======>  [ Linear Function Approx ]  ======>  [ Deep Neural Networks ]
  Exact Counting             Feature-Based Geometry               Non-Convex Landscapes
  Full Isolation             Partial Coupling                     Total Coupling

The primary stepping stone is linear function approximation, where a state is represented by a vector of hand-crafted features, and the value function is a linear combination of those features. As noted by Kone et al., moving from tabular MDPs to linear function approximation is the logical next frontier. It allows researchers to preserve some geometric intuition (like vector projections) and convexity while forcing the mathematics to handle state generalization.

The ultimate goal is to translate these insights into non-linear regimes. By isolating exactly why tabular proofs work—whether through contractive properties, distribution stability, or bounded variance—the RL community is gradually building the mathematical vocabulary needed to provide the same ironclad guarantees for deep neural networks that we currently enjoy for simple tables.

Key Foundational Work

Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap (2021) — contributed 1 concept elements to this direction.
Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs (2021) — contributed 1 concept elements to this direction.
Towards Instance-Optimal Offline Reinforcement Learning with Pessimism (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_function_approximation_gap_c984fb12,
  title = {function approximation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/function-approximation-gap/rdr_c984fb12a71d419696c3f8dc3e5dccd1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_function_approximation_gap_c984fb12_v1,
  title = {function approximation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/function-approximation-gap/rdr_c984fb12a71d419696c3f8dc3e5dccd1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake