Research map / Reinforcement learning / MDPs and planning
Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
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 and MLP expressiveness that model representation is easier than optimal policy, which is easier than optimal value (a hierarchy) for constructed MDP classes (3-SAT/NP MDPs and CVP/P MDPs), with a small MuJoCo approximation-error experiment.
Problem
Whether a representation complexity hierarchy exists among model-based, policy-based, and value-based RL, measured by computational complexity (time and circuit) and the expressiveness of log-precision MLPs.
Approach
Introduces general NP MDPs and P MDPs (generalizing 3-SAT MDPs and CVP MDPs) where the model (and for P MDPs also the optimal policy) is AC^0 while the optimal policy/value is NP-complete or P-complete, and transfers these gaps to constant-layer ReLU MLPs under TC^0 != NP and TC^0 != P.
Key results
- In all four MuJoCo environments and MLP configurations, the approximation error of the optimal Q-function exceeds that of the optimal policy, which exceeds that of the transition kernel and reward.
- 3-SAT and NP MDPs have AC^0 reward/transition but NP-complete optimal policy and value; constant-layer ReLU MLPs cannot represent the latter under TC^0 != NP.
- CVP and P MDPs have AC^0 reward/transition/policy, but P-complete optimal value that constant-layer MLPs cannot represent under TC^0 != P.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| approximate the transition kernel and reward instead of the optimal policy or value | 3-SAT MDP and NP MDP · 3-SAT MDP; NP MDP | representation complexity (circuit complexity) | Helped |
| approximate the optimal policy instead of the optimal value function | CVP MDP and P MDP · CVP MDP; P MDP | representation complexity (circuit complexity) | Helped |
| use a constant-layer MLP with polynomial hidden dimension to represent the model | 3-SAT MDP and NP MDP · 3-SAT MDP; NP MDP | MLP representability | Helped |
| use a constant-layer MLP with polynomial hidden dimension to represent the optimal policy or value | 3-SAT MDP and NP MDP · 3-SAT MDP; NP MDP | MLP representability | Hurt |
| represent the model and optimal policy rather than the optimal value function | CVP MDP and P MDP · CVP MDP; P MDP | MLP representability | Helped |
| approximate the transition kernel and reward rather than the optimal policy | MLPs trained on TD3-generated data · HalfCheetah-v4; Humanoid-v4; InvertedPendulum-v4; Ant-v4 | relative approximation error | Helped |
| approximate the optimal policy rather than the optimal Q-function | MLPs trained on TD3-generated data · HalfCheetah-v4; Humanoid-v4; InvertedPendulum-v4; Ant-v4 | relative approximation error | Helped |
Surprising findings
- Majority MDPs from prior work can be represented by constant-layer MLPs, so they cannot demonstrate the MLP-based hierarchy.
Limitations
- The hierarchy is not valid for all MDPs; e.g., MDPs with complex transitions and zero rewards can invert it.
- Results rely on complexity-theoretic assumptions (TC^0 != NP, TC^0 != P) and worst-case constructions.
- Experiments use approximation error on MuJoCo only as empirical support, not a formal test.
Experimental setup
Datasets: MuJoCo HalfCheetah-v4 MuJoCo Humanoid-v4 MuJoCo InvertedPendulum-v4 MuJoCo Ant-v4
Benchmarks: MuJoCo HalfCheetah-v4 MuJoCo Humanoid-v4 MuJoCo InvertedPendulum-v4 MuJoCo Ant-v4
Metrics: relative approximation error of transition kernel, reward, o
Baselines: TD3
Builds on: Majority MDP TD3 Cook-Levin theorem
Closest papers by meaning
- On Representation Complexity of Model-based and Model-free Reinforcement Learning (ICLR 2024 · similarity 0.93)
- Representation Learning Enables Scalable Multitask Deep Reinforcement Learning (NeurIPS 2026 · similarity 0.89)
- Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning (ICML 2021 · similarity 0.88)
- Near-Optimal Representation Learning for Hierarchical Reinforcement Learning (ICLR 2019 · similarity 0.88)
- Bridging State and History Representations: Understanding Self-Predictive RL (ICLR 2024 · similarity 0.87)
- Towards General-Purpose Model-Free Reinforcement Learning (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.