Research map / Reinforcement learning / MDPs and planning
Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping
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.
Partitions MDP actions into groups by transition/reward similarity, derives a performance-loss bound with approximation and estimation error, and proposes a utility-based optimization to select the grouping function balancing loss with sample and computational cost.
Problem
Large action spaces cause exponential growth in sample and computational complexity for RL; action abstraction via grouping reduces complexity but introduces approximation error, and the trade-off with estimation error under limited samples and computation is not characterized.
Approach
Linear decomposition of transition kernel and reward into group-level components plus action-specific deviations (beta_P, beta_R); the bound shows finer grouping reduces approximation error but increases estimation error under limited samples/computation, so grouping is optimized as a trade-off, with a practical method estimating deviations on randomly sampled actions.
Key results
- Theoretical bound: performance loss = approximation error (beta_P*, beta_R*) + estimation error scaling with sqrt(S|g|/K) and epsilon_opt, showing finer grouping can hurt when samples/computation are limited.
- Simulation: with K'=10 samples per state-action pair, the grouped setting achieves lower performance loss than the non-grouping setting; with K'=500 the non-grouping setting is better.
- Tightness: the approximation error bound is tight up to a constant factor of 2 in a constructed example, and the estimation error matches a known minimax lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a finer grouping with more groups | Action grouping for model-based RL · Grouped MDP | approximation error | Helped |
| Use a finer grouping with more groups when samples or computation are limited | Action grouping for model-based RL · Grouped MDP with limited resources | estimation error | Hurt |
| Use coarser grouping with fewer groups when samples or computation are limited | Action grouping for model-based RL · Grouped MDP with limited resources | estimation error | Helped |
| Increase the sample size | Model-based RL with a generative model · Grouped MDP | performance loss | Helped |
| Increase the number of planning iterations | Model-based RL with a generative model · Grouped MDP | performance loss | Helped |
| Use non-grouped actions rather than grouped actions when samples are sufficient | Model-based RL · Downlink wireless transmission, K'=500 | performance loss | Helped |
| Use grouped actions rather than non-grouped actions when samples are limited | Model-based RL · Downlink wireless transmission, K'=10 | performance loss | Helped |
| Choose a coarser grouping with G=20 instead of other tested groupings | Action grouping for model-based RL · Performance loss versus sample size, K=10^4 | performance loss | Helped |
| Use non-grouping rather than grouped actions when samples are effectively unlimited | Action grouping for model-based RL · Performance loss versus sample size, K=10^7 | performance loss | Helped |
Surprising findings
- A finer grouping (more groups) can increase overall performance loss when sample or computation budgets are limited, because estimation error grows.
- Coarser grouping is preferred when total sample size is limited (e.g., K=10^4), while non-grouping is preferred when samples are unlimited (K=10^7).
Limitations
- Requires prior knowledge or feasible grouping set D from domain expertise.
- Approximation error bounds depend on small deviation factors beta_P, beta_R; practical method valid only for MDPs with group-wise similarity.
- Experiments are simulation-based on two wireless-style scenarios only.
Experimental setup
Benchmarks: simulated downlink transmission scenario simulated wireless access scenario
Metrics: performance loss (value function gap)
Baselines: non-grouping setting
Builds on: value iteration policy iteration leave-one-out analysis
Closest papers by meaning
- Partially Equivariant Reinforcement Learning in Symmetry-Breaking Environments (ICLR 2026 · similarity 0.88)
- Exact Reduction of Huge Action Spaces in General Reinforcement Learning (AAAI 2021 · similarity 0.88)
- Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model (NeurIPS 2021 · similarity 0.88)
- Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs (ICLR 2023 · similarity 0.87)
- Group-in-Group Policy Optimization for LLM Agent Training (NeurIPS 2025 · similarity 0.86)
- Excluding the Irrelevant: Focusing Reinforcement Learning through Continuous Action Masking (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.