{"id":"arxiv/2604.21177","url":"https://arxiv.org/abs/2604.21177","tags":["math.OC"],"score":0,"title":"Revisiting Subgradient Dominance in Robust MDPs: Counterexamples, Hardness, and Sufficient Conditions","domain":"math.OC","source":"arxiv","authors":["Toshinori Kitamura","Arnob Ghosh","Alex Ayoub","Thang D. Chu","Csaba Szepesvári"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-23","reactions":{}}