Research map / Optimization / Nonconvex and smooth optimization
Policy Optimization for Robust Average Reward MDPs
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.
Proposes robust policy mirror descent with a Fréchet sub-gradient for robust average cost MDPs on ergodic chains, proving global convergence (linear with increasing step size, O(1/ε) with constant step size).
Problem
Policy optimization for robust average cost MDPs with general (s,a)-rectangular uncertainty sets, where the worst-case average cost is non-differentiable and non-smooth in the policy, so existing global convergence analyses do not apply.
Approach
Derives a Fréchet sub-gradient of the robust average cost (dπ(s)Qπ(s,a)) and applies policy mirror descent with a state-dependent weighted Bregman divergence; proves a PL-type condition and a lower bound on the difference of robust average costs to obtain global convergence without smoothness.
Key results
- Robust policy mirror descent converges to the global optimum with linear rate under increasing step size and O(1/ε) iteration complexity under constant step size η=1/L_π.
- In simulations on Garnet(5,2), Garnet(10,5) and recycling robot, the robust method reports lower mean robust average cost than the non-robust policy mirror descent baseline (KL uncertainty set, R=0.1, η=0.01, 5 trials).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use robust policy mirror descent instead of the non-robust baseline | Policy optimization · Garnet(3, 2) | robust average cost | Mixed |
| Use robust policy mirror descent instead of the non-robust baseline | Policy optimization · Garnet(5, 2) | robust average cost | Helped |
| Use robust policy mirror descent instead of the non-robust baseline | Policy optimization · Garnet(10, 5) | robust average cost | Helped |
| Use robust policy mirror descent instead of the non-robust baseline | Policy optimization · Recycling Robot | robust average cost | Helped |
Surprising findings
- On the small Garnet(3,2) problem, the robust and non-robust methods converge to nearly the same value, with the robust method only converging faster.
Limitations
- Analysis is model-based; requires known uncertainty set and an oracle for robust Q-functions.
- Assumes ergodicity of all induced Markov chains (Assumption 2.1).
- Experiments are small-scale synthetic and one toy problem; code release deferred to acceptance.
Experimental setup
Datasets: Garnet(3,2) Garnet(5,2) Garnet(10,5) recycling robot MDP
Benchmarks: Garnet(3,2) Garnet(5,2) Garnet(10,5) recycling robot
Metrics: robust average cost
Baselines: non-robust policy mirror descent
Builds on: policy mirror descent performance difference lemma robust policy mirror descent (discounted) projected policy gradient for average cost MDPs
Closest papers by meaning
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.92)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.91)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.90)
- Online MDP with Prototypes Information: A Robust Adaptive Approach (AAAI 2025 · similarity 0.90)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.90)
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.