Research map / Reinforcement learning / MDPs and planning

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

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Robust MDP policy gradient · 0 citations (OpenAlex)

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.

Shows that projected subgradient descent for robust MDPs lacks subgradient dominance in general (counterexample with two transition kernels), proves NP-hardness of epsilon-optimal policy finding for finite and sa-rectangular-with-finite-cost uncertainty sets, and gives two sufficient conditions (unique worst-case kernel or robust action-value function) under which PSD converges.

Problem

Existing claims that robust MDPs with general compact uncertainty sets satisfy subgradient dominance, so projected subgradient descent finds epsilon-optimal policies in polynomial updates, may be false; the computational hardness of approximate policy optimization in RMDPs is unclear.

Approach

A counterexample showing a suboptimal strict local minimum of the robust cost with two transition kernels, NP-hardness reductions from 3-SAT for finite transition sets and sa-rectangular sets with finite non-rectangular costs, and two sufficient conditions (unique worst-case transition kernel per policy, or existence of a robust action-value function) that restore subgradient dominance.

Key results

• On a three-state deterministic RMDP with two transition kernels (gamma=0.9), a suboptimal strict local minimum has robust cost 0.505 versus 0.1 for the optimal policy, so subgradient dominance fails for every constant D.
• PSD initialized at the suboptimal policy stays within O(eta) of it (||pi_t - pi_2||_inf <= 3 eta).
• Finding an epsilon-optimal policy is NP-hard for finite transition sets with singleton cost (eps < 0.5 gamma^3/(1-gamma)), and for sa-rectangular finite transition sets with finite non-rectangular costs.

Surprising findings

• Published subgradient-dominance proofs for general RMDPs (Wang et al. 2023, Kitamura et al. 2025) contain errors, so PSD guarantees claimed for finite uncertainty sets do not hold.
• Even a two-kernel finite RMDP can have a suboptimal strict local minimum.

Limitations

• Sufficient conditions do not cover s-rectangular RMDPs, which remain an open problem.
• Convergence rate O(eps^-4) is slower than the O(eps^-1) rate for standard MDPs and its tightness is unknown.
• Hardness constructions use mu(s_ini)=1, violating the full-support assumption; the result is extended only via a mixing argument.

Experimental setup

Metrics: subgradient dominance constant robust total cost gap

Baselines: Wang et al. (2023) PSD analysis Kitamura et al. (2025) PSD analysis dynamic programming for rectangular RMDPs

Builds on: gradient dominance for MDPs Danskin's theorem Moreau envelope weak convexity analysis

Closest papers by meaning

• On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.90)
• Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.90)
• A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
• Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.89)
• Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.89)
• Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.88)