Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs
Bahram Behzadian, Marek Petrik, Chin Pang Ho
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 |
|---|---|---|---|
| replace Gurobi LP with homotopy Algorithm 1 | SA-rectangular L-inf RMDP · Machine Replacement | time (ms): 2960 -> < 1 | Improved |
| replace Gurobi LP with homotopy Algorithm 1 | SA-rectangular L-inf RMDP · RiverSwim | time (ms): 2240 -> 3 | Improved |
| replace Gurobi LP with homotopy Algorithm 1 | SA-rectangular L-inf RMDP · Inventory Management | time (ms): 9770 -> 10 | Improved |
| replace Gurobi LP with bisection Algorithm 2 | S-rectangular L-inf RMDP · Machine Replacement | time (ms): 129 -> 40 | Improved |
| replace Gurobi LP with bisection Algorithm 2 | S-rectangular L-inf RMDP · RiverSwim | time (ms): 217 -> 52 | Improved |
| replace Gurobi LP with bisection Algorithm 2 | S-rectangular L-inf RMDP · Inventory Management | time (ms): 2740 -> 67 | Improved |
| scale number of states to a few hundred | homotopy and bisection algorithms vs Gurobi · Inventory Management relative runtime | relative time: about 100 times faster | Improved |
| change ambiguity set from L1 to L-inf | SA-rectangular RMDP with fast algorithm · Inventory Management | time (ms): 1 -> 10 | Hurt |
| change ambiguity set from L1 to L-inf | S-rectangular RMDP with fast algorithm · Inventory Management | time (ms): 5 -> 67 | Hurt |
| vary robustness budget kappa | proposed algorithms · Inventory Management | computation time | No clear effect |
| change ambiguity set from L-inf to L1 for Gurobi LP | S-rectangular RMDP · Inventory Management | time (ms): 2740 -> 2260 | Improved |
Closest papers by meaning
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.93)
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.89)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.89)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.89)
- Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces (ICML 2024 · similarity 0.89)
- Time-Constrained Robust MDPs (NeurIPS 2024 · similarity 0.88)
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.
