Research map / Reinforcement learning / MDPs and planning
Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization
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.
Proposes approximate factorization of MDPs with a synchronous sampling scheme (graph-coloring-based), yielding a model-based Q-value iteration and a model-free variance-reduced Q-learning (VRQL-AF) with sample complexity scaling with the sum over colored groups rather than |S||A|.
Problem
Sample complexity of RL grows exponentially with state-action dimensionality; existing factored MDP methods require perfect factorization and lack provable model-free algorithms.
Approach
Approximately factorize the transition kernel and reward into low-dimensional components with bounded approximation error, and sample multiple components synchronously from shared samples, with the grouping cast as a cost-optimal graph coloring problem; apply this to both model-based value iteration and variance-reduced Q-learning.
Key results
- On the wind farm storage control problem, the approximate factorization method reduces cumulative penalty cost by 19.3% versus vanilla model-based RL with 60,000 samples.
- Theory: model-based sample complexity scales with the sum over colored groups of substate-subaction sizes (about max component size up to a factor of the number of groups), versus |S||A| for standard minimax bounds.
- Synthetic experiments (50 and 200 trials) show factorized methods have lower Q-function error than vanilla RL, and that the best number of components depends on sample budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate factorization with three components instead of vanilla model-based RL | Wind farm storage control · Wind farm storage control | cumulative system penalty cost: 19.3% | Helped |
| Use full factorization (K_ω = 4) rather than partial or no factorization (ablation) | Model-based and model-free RL · Imperfectly factorizable synthetic MDPs | convergence speed and asymptotic error | Mixed |
| Use partial factorization (K_ω = 2) rather than full or no factorization (ablation) | Model-based and model-free RL · Imperfectly factorizable synthetic MDPs | convergence speed and asymptotic error | Mixed |
| Use no factorization (K_ω = 1) rather than full or partial factorization (ablation) | Model-based and model-free RL · Imperfectly factorizable synthetic MDPs | asymptotic error | Helped |
| Use approximate factorization instead of vanilla RL | Model-based and model-free RL · Perfectly and imperfectly factorizable synthetic MDPs | Q-function error | Helped |
Surprising findings
- Full factorization converges fastest with small sample sizes but has higher asymptotic error, while no factorization gives the lowest asymptotic error.
- The approximation scheme is a tunable hyperparameter that trades sample complexity against model misspecification bias.
Limitations
- Results rely on a generative model (access to arbitrary state-action queries) rather than online exploration.
- Approximation bias term does not vanish for imperfectly factorized MDPs, and the choice of factorization is manual.
- Experiments are limited to small synthetic MDPs and one storage control problem.
Experimental setup
Datasets: synthetic MDPs wind farm storage control simulation
Benchmarks: synthetic factorizable MDPs imperfectly factorizable MDPs wind farm storage control
Metrics: l-infinity Q-function error cumulative system penalty cost cost reduction percentage
Baselines: vanilla model-based RL variance-reduced Q-learning without factorization
Builds on: factored MDP variance-reduced Q-learning synchronous Q-learning
Closest papers by meaning
- Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL (ICLR 2021 · similarity 0.92)
- Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes (NeurIPS 2020 · similarity 0.90)
- Efficient Solution and Learning of Robust Factored MDPs (AAAI 2026 · similarity 0.89)
- Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting (NeurIPS 2020 · similarity 0.89)
- Polynomial-Time Approximability of Constrained Reinforcement Learning (ICML 2025 · similarity 0.86)
- Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · 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.