Research map / Reinforcement learning / MDPs and planning

On Representation Complexity of Model-based and Model-free Reinforcement Learning

ICLR 2024 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows via circuit complexity that in a class of "majority MDPs" the transition and reward functions are in constant-depth polynomial-size circuits while the optimal Q-function is not, and supports this with MuJoCo fitting-error experiments.

Problem

Why model-based RL usually has better sample complexity than model-free RL, framed as a representation-complexity question: are transition and reward functions easier to represent than optimal Q-functions?

Approach

Uses constant-depth Boolean circuit complexity (AC^0, parity/majority hardness) as a rigorous representation-complexity measure and constructs majority MDPs where the transition and reward are in AC^0 but the optimal Q-function (and value function) is not, extending a prior piecewise-linear example that is restricted to a special MDP class.

Key results

• In majority MDPs, the transition and reward functions are computable by polynomial-size constant-depth circuits while the optimal Q-function is not (theorems for unconditioned and conditioned settings).
• Across five MuJoCo environments with 2-hidden-layer width-32 networks, the approximation errors of the optimal Q-function are consistently much larger than those of the transition and reward functions (5 runs, mean and std reported).

Measured effects reported in the paper

Limitations

• Separation is shown for a specially constructed class of majority MDPs; it is unclear how common such separation is in general MDPs.
• Experiments are limited to five MuJoCo environments and rely on SAC-estimated Q-values, which may be biased.
• Results are about circuit representation complexity, not directly about sample complexity.

Experimental setup

Datasets: MuJoCo Gym environments (Ant-v4, Hopper-v4, HalfCheetah-v4, InvertedPendulum-v4, Walker2d-v4)

Benchmarks: MuJoCo Ant-v4 MuJoCo Hopper-v4 MuJoCo HalfCheetah-v4 MuJoCo InvertedPendulum-v4 MuJoCo Walker2d-v4

Metrics: relative approximation error (normalized MSE)

Baselines: Soft Actor-Critic

Builds on: Soft Actor-Critic

Closest papers by meaning

• Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity (NeurIPS 2024 · similarity 0.93)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective (ICLR 2026 · similarity 0.90)
• Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs (ICLR 2023 · similarity 0.89)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting (NeurIPS 2021 · similarity 0.89)
• Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.88)
• On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage (NeurIPS 2026 · similarity 0.87)