Robust learning method for zero-sum games with limited data
Toward Online Robust Zero-Sum Markov Games with Function Approximation
Machine LearningArtificial Intelligence
Summary
Sometimes, computer programs need to learn how to make decisions in uncertain, competitive settings where they face an opponent. This paper studies a way to help such programs learn the worst-case strategies they might face, even when only limited or imperfect data is available from past interactions. The authors develop a new method that carefully balances exploring different actions, estimating risks, and planning future moves to reduce mistakes. They prove mathematically how this method works in different situations and show small experiments to confirm its behavior.
What this means in practice
- •For multi-agent system developers: Design algorithms that can safely learn competitive strategies under uncertain environments with limited data.
- •For financial trading teams: Develop trading bots that account for worst-case opponent reactions when training from historical market data.
Authors
Chenhao Zhou, Jiyu Wei
Abstract
Online robust zero-sum Markov games pose a coupled operator-learning and game-solving problem: from nominal interaction data, the learner must recover a worst-case minimax Bellman operator while maintaining strategic coverage and controlling stage-game approximation error. Existing robust reinforcement-learning theory does not yet provide such an operator-learning perspective beyond specialized multi-agent settings. We develop an optimistic dual robust Bellman framework that combines dual robust Bellman fitting, optimistic minimax planning, backward-validated confidence sets, and exploiter-mix data collection. Our analysis is organized around the robust Bellman residuals induced by the candidate value class and yields a regret reduction that separates exploration complexity, robust operator-estimation error, stage-game solution error, and misspecification. Under explicit interpretable assumptions, we obtain conditional theorem interfaces for general and projected function approximation, together with closed results in several structured regimes, including tabular, epochwise cross-fit linear, self-normalized pure-online linear / finite-rank kernel, and projected RKHS truncation. Small-scale numerical experiments illustrate robustness calibration, strategic coverage, and the return-gap trade-off predicted by the framework.