Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, **Robust Halpern Iteration (RHI)**. We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a $K$-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and $\chi^2$ divergence sets, and show that our RHI algorithm achieves an $\varepsilon$-optimal robust policy with a sample complexity of $\tilde{\mathcal{O}}\left( \frac{SA\mathcal{H}^2}{\varepsilon^{(2+o(1))}}\right)$, where $S,A$ are the number of states and actions, and $\mathcal{H}$ is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.

To reliably deploy autonomous systems (e.g., robotics, smart power grids, or automatic portfolio management), artificial intelligence (AI) must not only optimize for continuous, indefinite operations (a modality often referred to as the "average-reward" setting), but also withstand potentially severe mismatches between it's training simulator and the real-world scenario. While designing a resilient or "robust" strategy is critical for bridging this gap, learning these long-term decision-making rules (or "policy") typically involves either construction of a massive, computationally expensive model of the entire environment or relying on algorithms that lack guarantees for the amount of training data needed, leading to prohibitively long training times. To address this, our research proposes a novel, data-driven approach called Robust Halpern Iteration (RHI). Instead of building a model or reducing the problem to a short-term horizon that demands prior knowledge of the problem at hand, RHI instead learns an optimal strategy by interacting directly with the simulator. A core innovation of this method is our carefully designed sampling technique, which inherently corrects for estimation error that usually plagues direct learning under uncertainty. By significantly reducing this bias, we show that RHI can discover optimal policies which are robust to abnormalities (e.g., an animal running in front of a self-driving car on a rainy night) by using a minimal amount of data or knowledge of the problem. Ultimately, this work provides a highly efficient, practical, mathematically guaranteed method for training AI to safely and reliably operate in complex, changing conditions over the long run.