Research map / Reinforcement learning / MDPs and planning

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets

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.

Studies exact value computation for discounted (s,a)-rectangular robust MDPs with L_p uncertainty sets, giving a reduction of RMDP policy iteration to RMC oracles, strongly polynomial policy-iteration bounds for RMCs with L1 and L-infinity sets, and p-ROOT-SUM hardness plus an existential-theory-of-reals upper bound for integer 1<p<infinity.

Problem

Exact value computation for discounted robust MDPs and robust Markov chains with L_p uncertainty sets, and whether policy iteration runs in strongly polynomial time.

Approach

Reduces RMDP policy iteration to repeated RMC solves, uses a cumulative transition-probability potential over value-sorted successors to bound RMC policy iteration for L1 and L-infinity sets, and proves hardness for other integer p via a reduction from p-ROOT-SUM with KKT-based ETR membership.

Key results

• Policy iteration for RMDPs is shown to need O(nm log(1-gamma)/log gamma) iterations, given RMC oracle access, for any compact uncertainty set.
• For RMCs with L1 and L-infinity uncertainty sets, policy iteration needs O(n^3 log n log((1-gamma)/n)/log gamma) iterations, improving the L-infinity bound by a factor of n and giving the first polynomial bound for L1.
• Experiments on five benchmarks up to n=256 show iteration counts in the low double digits for standard benchmarks, far below the theoretical bound.

Limitations

• Gap between square-root-sum hardness lower bound and ETR upper bound for general integer p.
• No lower bounds on policy iteration iterations for RMDPs were established.
• Results restricted to (s,a)-rectangular L_p uncertainty sets.

Experimental setup

Datasets: Gridworld Inventory Management Machine Replacement GARNET Long Chain

Benchmarks: Gridworld Inventory Management Machine Replacement GARNET Long Chain

Metrics: outer policy iteration count total inner RMC policy iteration count

Baselines: value iteration linear programming

Builds on: policy iteration for RMDPs strongly polynomial PI for L_infinity RMDPs

Closest papers by meaning

• Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.92)
• 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)
• Revisiting Subgradient Dominance in Robust MDPs: Counterexamples, Hardness, and Sufficient Conditions (NeurIPS 2026 · similarity 0.90)
• Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.90)
• Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.90)