首次实现鲁棒平均回报强化学习的有限样本分析，解决样本复杂度难题。
Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
- 基于半范数构造收缩的鲁棒贝尔曼算子，结合截断的多级蒙特卡洛方法
- 在截断后仍保持指数衰减偏差，实现ε^{-2}阶最优样本复杂度
- 适合关注强化学习理论严谨性的研究者和高可靠性系统设计者
本文首次对鲁棒平均回报马尔可夫决策过程中的策略评估进行有限样本分析。以往工作仅给出渐近收敛结果，未明确样本复杂度。本文证明了在特定半范数下，鲁棒贝尔曼算子具有收缩性，并构建了带可控偏差的随机逼近框架。方法基于多级蒙特卡洛（MLMC）技术高效估计鲁棒贝尔曼算子，通过基于几何分布的截断机制克服标准 MLMC 中无限期望样本复杂度的问题，确保有限期望样本复杂度的同时，保持偏差随截断层级指数衰减。所提方法在鲁棒策略评估与平均回报估计中均达到$ ilde{ ext{O}}(ε^{-2})$阶最优样本复杂度，显著推进了鲁棒强化学习的理论发展。
原文摘要 · Abstract (English)
We present the first finite-sample analysis of policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior work in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by showing that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent in standard MLMC, we introduce a truncation mechanism based on a geometric distribution, ensuring a finite expected sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of $\tilde{\mathcal{O}}(ε^{-2})$ for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。