When we apply machine learning to complex, high-dimensional environments, we rarely expect to map out every state perfectly. Instead, we rely on function approximators—such as neural networks, linear combinations of features, or decision trees—to compress the environment's complexities into a manageable mathematical form.
In theoretical reinforcement learning (RL) and imitation learning (IL), proofs often rely on the assumption of realizability: the premise that the true optimal policy, value function, or expert behavior lives comfortably within the set of functions our model can represent.
In practice, this assumption is routinely violated. This mismatch creates a fundamental representational capacity bottleneck. No matter how many samples an agent collects, and no matter how perfectly its optimization algorithms run, its performance is ultimately bounded by a hard floor dictated by the expressivity of its function class.
The Representational Barrier: Why Optimization Cannot Save Us
It is tempting to treat reinforcement learning primarily as an optimization or sample-efficiency problem. If an agent fails to learn, we often assume it needs more training data, a better exploration strategy, or a more stable gradient step. However, a core thread of research demonstrates that the bottleneck is frequently structural rather than algorithmic.
There is a sharp distinction between the computational difficulty of finding a policy and the representational difficulty of storing it. As proven by Eric Allender et al., even when an environment possesses simple, highly structured rules (such as factored dynamics), its optimal policy can be so complex that no polynomial-sized function approximator can succinctly represent it. Settling for an approximate solution does not bypass this barrier; even sub-optimal policies that capture only a fraction of the total reward can remain impossible to represent within standard parametric architectures.
When an agent's underlying function approximator has a fixed or coarse capacity, it hits an inescapable performance plateau. As observed empirically by Matthew E. Taylor et al., once an agent reaches the representational limit of its architecture, additional training time yields no further improvement. This boundary is not a failure of the optimization algorithm, but a reflection of the model's geometric constraints.
The Realizability Gap in Imitation Learning
The consequences of representational limits are particularly stark in imitation learning, where a student agent attempts to mimic an expert's behavior.
Standard imitation learning frameworks assume that the student's hypothesis space is rich enough to encompass the expert's policy. When the expert is significantly more complex than the learner—a phenomenon known as the realizability gap—traditional algorithms break down. As He He et al. demonstrate, this capacity mismatch leads to high training error and prevents the learner from acquiring useful behaviors, even when provided with flawless demonstrations.
Expert Policy Space (Highly Complex / Non-linear)
┌────────────────────────────────────────────────────────┐
│ ★ (True Expert Strategy) │
└────────────────────────────────────────────────────────┘
│
▼ [Violates Realizability]
┌────────────────────────────────────────────────────────┐
│ ○ (Best Possible Approximation) │
└────────────────────────────────────────────────────────┘
Learner Hypothesis Space (Restricted / Lower Capacity)
When this gap is present, standard theoretical guarantees for long-term error bounds evaporate. Tian Xu et al. and Gokul Swamy et al. highlight that if the expert's behavior exceeds the representational capacity of the learner, established convergence and performance bounds no longer hold. To address this, Yichen Li et al. formalize "agnostic" interactive imitation learning, explicitly modeling settings where the expert cannot be perfectly represented and developing algorithms that provide finite-sample guarantees despite this structural deficit.
One way to bypass an unrepresentable expert policy is to change what the model is trying to represent. For instance, Antoine Moulin et al. propose shifting the realizability assumption away from the expert's policy and onto the environment's value functions instead, allowing agents to match expert performance without needing to directly capture highly complex or non-stationary human behaviors.
Persistent Bias in Policy Gradients
The representational bottleneck also places a strict floor on policy optimization methods, such as Natural Policy Gradient (NPG) and Actor-Critic algorithms.
Even when an optimization algorithm is mathematically proven to converge efficiently, it can only converge to the best available policy within its specified architecture. For example, Carlo Alfano et al. show that while NPG can achieve fast linear convergence under log-linear policy parametrizations, the ultimate quality of the final policy is strictly bounded by a performance floor determined by feature bias.
This limitation means that optimization and representation are decoupled:
- Optimization dictates how fast the agent approaches its architectural limit.
- Representation dictates the quality of that limit.
As analyzed by Washim Uddin Mondal et al. and Yudan Wang et al., a residual approximation error always persists if the policy class is not sufficiently expressive to capture the global optimum. Yanli Liu et al. reinforce this by showing that global convergence results are inherently bounded by a compatible function approximation error; optimization algorithms can navigate the parameter space perfectly, but they cannot escape the geometric constraints of the neural network itself.
The Capacity Allocation Problem
Because function approximators have finite representational resources, they face a budgeting problem: they must choose which features of the environment to model and which to ignore.
In standard Actor-Critic setups, this creates an objective mismatch. As Sharan Vaswani et al. explain, a critic network with limited capacity might exhaust its representational power minimizing overall mean squared error across irrelevant parts of the state space. By focusing its capacity on regions that do not influence the actor's decisions, the critic introduces severe function approximation bias into the policy update step.
This coarseness of parametrization ripples through every aspect of the learning framework:
- Value Function Instability: If a model cannot fit the intricate contours of the true value function, iterative value learning can fail to expand across the state space, trapping the agent in a localized, incomplete policy (Justin A. Boyan et al.).
- Exploitation of Errors: If an agent uses exact action optimization against an imprecise value function, it can inadvertently exploit the function's approximation errors, leading to highly suboptimal real-world outcomes (Moonkyung Ryu et al.).
- Loss of Mathematical Structure: In constrained RL, the theoretical guarantee of a zero duality gap relies on the fluid geometry of the policy space. Coarse parametrizations break this geometry, preventing primal-dual algorithms from reaching true optimal solutions (Santiago Paternain et al.).
Ultimately, as framed by Ching-An Cheng et al., integrating function approximation into reinforcement learning introduces an inescapable representational bias. Even with infinite samples, an agent's performance remains tethered to the expressivity of its underlying value function and policy models.
Expanding the Bottleneck
To mitigate these representational limits, modern reinforcement learning explores several distinct pathways:
- Expressive Policy Classes: Rather than relying on simple Gaussian distributions, researchers are adopting highly flexible architectures. For instance, Zhendong Wang et al. utilize conditional diffusion models as policies in offline RL, allowing the agent to capture complex, multi-modal behavior distributions that traditional parametric families cannot represent.
- Strategic Capacity Allocation: Algorithms are being redesigned to force models to spend their capacity where it matters most. This includes learning balanced state representations to minimize distribution shift (Yao Liu et al.) or using decision-aware objectives that explicitly align the critic's capacity with the actor's optimization needs (Sharan Vaswani et al.).
- Alternative Representation Spaces: When standard continuous or linear representations fail, shifting to alternative spaces—such as relational policy languages (Alan Fern et al.) or compatible reward features in inverse RL (Alberto Maria Metelli et al.)—can make complex strategic structures representable.
By understanding that function approximation bias is a hard geometric constraint rather than a soft optimization hurdle, the field moves away from simply training models longer, focusing instead on designing architectures and objectives that expand the representational bottleneck itself.
Key Foundational Work
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics (2002) — contributed 3 concept elements to this direction.
Generalization in Reinforcement Learning: Safely Approximating the Value Function (1994) — contributed 1 concept elements to this direction.