Revisiting Subgradient Dominance in Robust MDPs: Counterexamples, Hardness, and Sufficient Conditions

Toshinori Kitamura, Arnob Ghosh, Alex Ayoub, Thang D. Chu, Csaba Szepesvári

arXivarxiv/2604.21177Apr 23, 2026math.OCscore 0

Projected subgradient descent (PSD) has gained popularity for solving robust Markov decision processes (RMDPs) because it applies to a broader class of uncertainty sets than traditional dynamic programming. Existing work claims that RMDPs with a general compact uncertainty set satisfy the subgradient dominance property, under which exact PSD finds an $\varepsilon$-optimal policy in a polynomial number of updates (e.g., Wang et al., 2023). We show that these claims are incorrect. Even when the uncertainty set has cardinality two, the RMDP objective need not be subgradient-dominant and can…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.21177
curl -X POST /api/v1/records/arxiv/2604.21177/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.21177/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'