Research map / Reinforcement learning / MDPs and planning
Qualitative Analysis of ω-Regular Objectives on Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Ali Shafiee
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 |
|---|---|---|---|
| use oracle-based ASReach instead of long-run-average policy iteration RPPI for almost-sure reachability | robust MDP reachability · Frozen Lake and QComp, L1/L2/Linf uncertainty | instances solved within 60 s: 81 -> 426 | Improved |
| use ASReach instead of RPPI on instances both solve | robust MDP reachability · instances solved by both | average time (s): 6.3 -> 0.1 | Improved |
| ASReach applied to L2 uncertainty sets, which RPPI does not support | ASReach · Frozen Lake, L2, R_max=1 | instances solved within 60 s: 24 of 24 solved | Improved |
| use ASParity instead of EffASParity despite worse worst-case complexity (ablation) | parity objectives on Frozen Lake · Frozen Lake parity benchmarks | instances solved within 60 s: 120 -> 135 | Improved |
| use ASParity instead of EffASParity (ablation) | parity objectives · Frozen Lake, L1 uncertainty, R_max=0.5 | average time (s): 7.8 -> 7.3 | Improved |
| increase uncertainty radius R_max from 0.5 to 1.5 for EffASParity on L2 Frozen Lake (ablation) | EffASParity · Frozen Lake parity, L2 | instances solved within 60 s: 12 -> 15 | Improved |
Closest papers by meaning
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.90)
- Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.88)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.88)
- Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.88)
- Revisiting Subgradient Dominance in Robust MDPs: Counterexamples, Hardness, and Sufficient Conditions (NeurIPS 2026 · similarity 0.88)
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (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.
