Research map / Reinforcement learning / MDPs and planning
Efficient Value Iteration for s-rectangular Robust Markov Decision Processes
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.
Derives explicit optimal s-rectangular Lp robust Bellman operators and a threshold-form optimal robust policy, enabling robust value iteration that is much faster than prior LP/SDP/homotopy methods.
Problem
Solving s-rectangular robust MDPs is strongly NP-hard in general and existing exact or approximate methods (LP, SDP, homotopy-bisection, R2 Bellman operators) are either slow or inapplicable to moderately large state spaces.
Approach
Reformulate the s-rectangular Lp-constrained robust Bellman operator as a reward-value-policy regularized Bellman operator with a p-variance penalty and a policy-norm penalty, yielding closed forms (p=1, 2, infinity) and binary search for general p; the optimal robust policy is a threshold policy proportional to advantages.
Key results
- For p=1,2 the s-rectangular robust Bellman operator is evaluated in O~(S^2A + SA log A) time, faster than prior methods by at least a factor of S.
- Empirically, the proposed method's relative cost stays close to non-robust value iteration (about 1.1-2.6x) while the LP baseline becomes infeasible (e.g., 72625x at S=10, A=10 for L1 sa-rectangular LP... reported relative times up to 4904004x for S=50, A=10).
- Optimal s-rectangular robust policies are threshold policies that play only actions with positive advantage, with probabilities proportional to advantage raised to p-1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed value iteration instead of the Linear Program | sa-rectangular L1 robust MDP value iteration · Random MDP (S=10, A=10) | running cost relative to non-robust MDP: 1438 -> 1.7 | Helped |
| Use the proposed value iteration instead of the Linear Program | s-rectangular L1 robust MDP value iteration · Random MDP (S=10, A=10) | running cost relative to non-robust MDP: 72625 -> 1.4 | Helped |
| Use the proposed value iteration instead of the Linear Program | sa-rectangular L1 robust MDP value iteration · Random MDP (S=30, A=10) | running cost relative to non-robust MDP: 6616 -> 1.3 | Helped |
| Use the proposed value iteration instead of the Linear Program | s-rectangular L1 robust MDP value iteration · Random MDP (S=30, A=10) | running cost relative to non-robust MDP: 629890 -> 1.5 | Helped |
| Use the proposed value iteration instead of the Linear Program | sa-rectangular L1 robust MDP value iteration · Random MDP (S=50, A=10) | running cost relative to non-robust MDP: 6622 -> 1.5 | Helped |
| Use the proposed value iteration instead of the Linear Program | s-rectangular L1 robust MDP value iteration · Random MDP (S=50, A=10) | running cost relative to non-robust MDP: 4904004 -> 1.2 | Helped |
| Use the proposed value iteration instead of the Linear Program | sa-rectangular L1 robust MDP value iteration · Random MDP (S=100, A=20) | running cost relative to non-robust MDP: 16714 -> 1.4 | Helped |
Surprising findings
- Optimal robust policies in s-rectangular MDPs are stochastic threshold policies, contrasting with softmax policies from entropy regularization.
- Imposing a simplex condition on kernel noise changes the regularizer from the q-norm of the value to the q-variance of the value.
Limitations
- Robust Bellman operator for general p is only approximable by binary search
- Experiments are limited to randomly generated small MDPs
- Only Lp-norm uncertainty sets are covered; general norms are challenging for s-rectangular case
Experimental setup
Benchmarks: randomly generated MDPs with varying S and A
Metrics: relative running time of value iteration w.r.t. non-robust M
Baselines: LP (linear programming) robust Bellman operator Ho et al. 2020 homotopy-bisection Derman et al. 2021 R2 Bellman operator Wiesemann et al. 2013 SDP
Builds on: Wiesemann et al. 2013 s-rectangular robust MDPs Derman et al. 2021 R2 Bellman operators Ho et al. 2020 homotopy bisection Anava & Levy 2016 water filling
Closest papers by meaning
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.92)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.91)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.91)
- Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces (ICML 2024 · similarity 0.91)
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.90)
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.