Research map / Reinforcement learning / MDPs and planning
Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization
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 coupled-reward robust MDPs with known transitions and an L_p-ball reward uncertainty set, showing the robust return equals the nominal return minus a frequency-norm regularizer, and proposes a policy-gradient method with convergence guarantees and an actor-critic variant.
Problem
Robust MDPs with rectangular reward uncertainty are overly conservative; coupled (non-rectangular) reward uncertainty with known transitions lacks tractable solutions and convergence guarantees for policy gradient.
Approach
For a coupled L_p-ball reward uncertainty set, the worst-case reward has closed form and the robust return equals the nominal return minus alpha times the L_q norm of the occupancy measure (a frequency regularizer). This yields a robust Bellman evaluation operator, a policy-gradient theorem, and global convergence for p in (1, infinity).
Key results
- Robust return for L_p-ball coupled reward uncertainty equals nominal return minus alpha times the L_q norm of the occupancy measure, enabling closed-form worst-case reward.
- Tabular experiment: the coupled-reward model attains better CVaR_5% worst-case performance than s-rectangular robust PG and is more stable to radius estimation errors.
- On Mountain Car Continuous and Ant-v3 with perturbed penalty regions, the method outperforms PPO and domain randomization when the perturbation deviates significantly from nominal; the suboptimality gap decays as O(1/k).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coupled L2 reward uncertainty instead of s-rectangular L2 reward uncertainty | Model-based policy gradient · Tabular reward-perturbation experiment | CVaR_5% | Helped |
| Use reward-robust actor-critic instead of PPO or domain randomization | Mountain Car Continuous and Ant-v3 · Mountain Car Continuous and Ant-v3 under perturbed rewards | performance | Helped |
| Use reward-robust actor-critic instead of non-robust PPO | Mountain Car Continuous and Ant-v3 · Mountain Car Continuous and Ant-v3 under the nominal reward | performance | Helped |
Surprising findings
- The proposed robust method also outperformed the non-robust PPO under the nominal reward in the high-dimensional experiments.
- Naive robust Bellman value iteration on non-rectangular sets yields an overly conservative value function (fixed point corresponds to the smallest rectangular superset).
Limitations
- Theory and convergence proof only hold for p in (1, infinity); p=1 (one-hot penalty) is left for future work due to possible non-differentiability.
- Only reward uncertainty with known transitions is considered; extension to coupled kernel uncertainty is open.
- Radius alpha is assumed known; learning the uncertainty radius from trajectories is left open.
Experimental setup
Datasets: Mountain Car Continuous Ant-v3
Benchmarks: Mountain Car Continuous Ant-v3
Metrics: CVaR_5% return under perturbed reward
Baselines: PPO domain randomization s-rectangular robust policy gradient
Builds on: robust MDP rectangularity framework policy gradient theorem PPO domain randomization
Closest papers by meaning
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.92)
- Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.90)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- Robust Offline Reinforcement Learning with Linearly Structured $f$-Divergence Regularization (ICML 2025 · similarity 0.90)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · 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.