Research map / Reinforcement learning / MDPs and planning
Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
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.
Gives the first finite-sample policy evaluation analysis for robust average-reward MDPs by proving a semi-norm contraction of the robust Bellman operator and using a truncated geometric-MLMC estimator for TV and Wasserstein support functions.
Problem
Policy evaluation (robust value function and robust average reward) in average-reward MDPs with (s,a)-rectangular uncertainty sets, using only nominal-model samples; prior work gave only asymptotic guarantees since the robust average-reward Bellman operator is not a contraction in any norm.
Approach
Constructs a semi-norm (extremal norm over the joint spectral radius of fluctuation matrices plus a quotient term) under which the robust average-reward Bellman operator contracts; then uses a truncated MLMC estimator with geometric parameter 0.5 and cap N_max so expected samples are finite (O(N_max)) with bias decaying as 2^{-N_max/2}.
Key results
- Truncated MLMC estimator has expected sample size E[M]=N_max+2 and bias bounded by 6(1+1/delta)2^{-N_max/2}||V||_sp for TV.
- Robust average-reward TD achieves order-optimal O~(epsilon^-2) sample complexity for policy evaluation under contamination, TV, and Wasserstein uncertainty sets.
- Robust Bellman operator is shown to be a contraction under a constructed semi-norm, under ergodicity of the nominal chain and radius restrictions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use robust average-reward TD with the contamination support-function estimator | Robust policy evaluation · Contamination uncertainty | sample complexity: \cO\left(\frac{SAt^2_{\mathrm{mix}}}{\epsilon^2(1-\gamma)^2} \right) | Helped |
| Use robust average-reward TD with truncated MLMC support-function estimation | Robust policy evaluation · TV and Wasserstein uncertainty | sample complexity: \tilde{\cO}\left(\frac{SAt^2_{\mathrm{mix}}}{\epsilon^2(1-\gamma)^2} \right) | Helped |
| Use robust average-reward TD to estimate the robust average reward | Robust average-reward estimation · Contamination, TV, and Wasserstein uncertainty | sample complexity: \tilde{\cO}\left(\frac{SAt^2_{\mathrm{mix}}}{\epsilon^2(1-\gamma)^2} \right) | Helped |
| Truncate geometric MLMC sampling at N_max and set Ψ=0.5 | MLMC support-function estimator · TV and Wasserstein uncertainty | expected samples per estimate: \mathbb{E}[M]=N_{\max}+2=\mathcal{O}(N_{\max}) | Helped |
| Truncate geometric MLMC sampling at N_max | MLMC support-function estimator · TV uncertainty | absolute bias: 6(1+\frac{1}{\delta}) 2^{-\frac{N_{\max}}{2}}\|V\|_{\mathrm{sp}} | Mixed |
| Truncate geometric MLMC sampling at N_max | MLMC support-function estimator · Wasserstein uncertainty | absolute bias: 6\cdot 2^{-\frac{N_{\max}}{2}}\|V\|_{\mathrm{sp}} | Mixed |
Surprising findings
- Average-reward Bellman operator is not a contraction under any norm even in the non-robust case, so the semi-norm construction is needed.
Limitations
- Requires ergodicity (irreducible, aperiodic nominal chain) and radius restrictions for the contraction.
- Results are tabular; function approximation is left open.
- Tightness in S, A and gamma is not claimed.
Experimental setup
Metrics: sample complexity bias variance
Baselines: Robust average-reward RVI TD (asymptotic) MLMC-based robust estimators (infinite expected samples)
Builds on: Multi-Level Monte Carlo estimator for robust Bellman operator biased stochastic approximation robust average-reward TD learning (Wang et al.)
Closest papers by meaning
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.93)
- Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.91)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.90)
- A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward (ICML 2025 · similarity 0.90)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.89)
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.