Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Solving Robust Markov Decision Processes: Generic, Reliable, Efficient
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.
Provides a generic, reliable, and efficient framework for solving robust MDPs via implicit bounded value iteration on arbitrary (constant-support) uncertainty sets, for total reward and long-run average objectives, with guaranteed stopping criteria.
Problem
Solving robust MDPs with general uncertainty sets and objectives (total reward, SSP, long-run average) reliably (with precision guarantees) and efficiently, where existing tools either are restricted in uncertainty/objective or lack stopping criteria and construct exponentially large or infinite sto
Approach
Reduces RMDPs to stochastic games and performs the SG's Bellman updates implicitly on the RMDP (optimizing linear functions over uncertainty sets), using collapsing of end components under the Constant-Support assumption to enable bounded (lower and upper) value iteration with a correct stopping criterion.
Key results
- On RVI/RRVI/RPPI comparison, the proposed method solves lake-100-U in 6 s and lake-100-M in 12 s, while RRVI and RPPI time out (15 min).
- On PRISM comparison with TR objective, runtimes are in the same order of magnitude (e.g., firewire 78 s vs 111 s for PRISM; brp 88 s vs 40 s), while providing guarantees.
- Solves RMDPs with over a million states (with L2-balls) in under a minute.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use implicit value iteration instead of explicit induced-game construction | RMDP solver · cont-50 | solving time (seconds): 223 -> <1 | Helped |
| use implicit value iteration instead of explicit induced-game construction | RMDP solver · cont-75 | solving time (seconds): 700 -> <1 | Helped |
| use implicit value iteration instead of explicit induced-game construction | RMDP solver · lake-10-M | solving time (seconds): 26 -> <1 | Helped |
| use implicit value iteration instead of explicit induced-game construction | RMDP solver · lake-15-M | solving time (seconds): T/O -> 2 | Helped |
| use the proposed solver rather than PRISM | RMDP solver · firewire | solving time (seconds): 111 -> 78 | Helped |
| use the proposed solver rather than PRISM | RMDP solver · frozenlake | solving time (seconds): 25 -> 52 | Hurt |
| use the proposed solver rather than PRISM | RMDP solver · lake_swarm | solving time (seconds): 68 -> 60 | Helped |
| use the proposed solver rather than PRISM | RMDP solver · brp | solving time (seconds): 40 -> 88 | Hurt |
Surprising findings
- PRISM's heuristic stopping criterion can stop early and wrongly, whereas the proposed method gives correct guarantees.
Limitations
- Stopping criterion and implicit algorithms require Constant-Support assumption; LRA and minimizing TR for non-constant-support RMDPs may need exponential blowup.
- Implementation is a prototype in Java on standard hardware (AMD Ryzen 5, 16GB RAM).
- Lower and upper bounds computed simultaneously cost roughly twice the operations of one-sided methods.
Experimental setup
Datasets: frozenlake models contamination models firewire brp lake_swarm PRISM benchmark models with added uncertainty sets
Benchmarks: frozenlake (lake-n) RMDPs contamination (cont-n) RMDPs firewire frozenlake PRISM lake_swarm brp
Metrics: solving time in seconds timeouts and memory-outs
Baselines: RVI RRVI RPPI PRISM IntervalMDP.jl
Builds on: robust value iteration bounded value iteration optimistic value iteration PRISM IntervalMDP.jl
Closest papers by meaning
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.90)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.90)
- Online MDP with Prototypes Information: A Robust Adaptive Approach (AAAI 2025 · similarity 0.89)
- Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.89)
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.