Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
원문 초록
We present the first finite-sample analysis for policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior works in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by establishing that the robust Bellman operator is a contraction under the span 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 constant 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}}(\epsilon^{-2})$ for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Self-Supervised Evolution Operator Learning for High-Dimensional Dynamical Systems
auto-fpt: Automating Free Probability Theory Calculations for Machine Learning Theory
Double descent in quantum machine learning
Gradient Equilibrium in Online Learning: Theory and Applications
NLPrompt: Noise-Label Prompt Learning for Vision-Language Models
Federated Learning from Vision-Language Foundation Models: Theoretical Analysis and Method
토론
이 논문과 연결된 포럼 글이 아직 없습니다.