Research map / Reinforcement learning / MDPs and planning
Hardness in Markov Decision Processes: Theory and Practice
Michelangelo Conserva, Paulo Rauber
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase p_rand | MiniGridEmpty · Episodic MiniGridEmpty, scenario 1 | diameter | Hurt |
| Increase p_rand | MiniGridEmpty · Episodic MiniGridEmpty, scenario 1 | environmental value norm | Improved |
| Increase p_lazy | MiniGridEmpty · Episodic MiniGridEmpty, scenario 2 | diameter | Hurt |
| Increase p_lazy | MiniGridEmpty · Episodic MiniGridEmpty, scenario 2 | environmental value norm | Improved |
| Increase the number of states | MiniGridEmpty · Episodic MiniGridEmpty, scenarios 3 and 4 | cumulative regret | Hurt |
| Increase the number of states | MiniGridEmpty · Episodic MiniGridEmpty, scenarios 3 and 4 | environmental value norm | Mixed |
| Increase p_rand or p_lazy | MiniGridEmpty · Episodic MiniGridEmpty, scenarios 1 and 2 | cumulative regret | Mixed |
| Use the episodic setting rather than the communicating setting | Colosseum agents · Colosseum benchmark | normalized cumulative regret | Improved |
| Use PSRL instead of Q-learning | Tabular agents · Episodic Colosseum benchmark | normalized cumulative regret: .81±.24 -> .30±.33; .83±.23 -> .35±.30 | Improved |
| Use UCRL2 instead of Q-learning | Tabular agents · Continuous ergodic Colosseum benchmark | normalized cumulative regret: .85±.18 -> .17±.26 | Improved |
| Use PSRL instead of Q-learning | Tabular agents · Continuous communicating Colosseum benchmark | normalized cumulative regret: .38±.37 -> .69±.38 | Hurt |
| Use non-tabular DQN rather than the other non-tabular agents | bsuite agents · Continuous ergodic Colosseum environments | cumulative regret | Mixed |
Closest papers by meaning
- Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts (NeurIPS 2026 · similarity 0.88)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.87)
- Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.87)
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.87)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.87)
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.
