홈 › Papers

Online Double Oracle

2021-03-13 · Le Cong Dinh, Yaodong Yang, Stephen Mcaleer, Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, Haitham Bou Ammar, Jun Wang

Solving strategic games with huge action space is a critical yet under-explored topic in economics, operations research and artificial intelligence. This paper proposes new learning algorithms for solving two-player zero-sum normal-form games where the number of pure strategies is prohibitively large. Specifically, we combine no-regret analysis from online learning with Double Oracle (DO) methods from game theory. Our method -- \emph{Online Double Oracle (ODO)} -- is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO methods, ODO is \emph{rationale} in the sense that each agent in ODO can exploit strategic adversary with a regret bound of $\mathcal{O}(\sqrt{T k \log(k)})$ where $k$ is not the total number of pure strategies, but rather the size of \emph{effective strategy set} that is linearly dependent on the support size of the NE. On tens of different real-world games, ODO outperforms DO, PSRO methods, and no-regret algorithms such as Multiplicative Weight Update by a significant margin, both in terms of convergence rate to a NE and average payoff against strategic adversaries.

📄 PDF Abstract BibTeX arXiv:2103.07780

Code (1)

npvoid/OnlineDoubleOracle

Online Learning and Solving Infinite Games with an ERM Oracle

2023-07-04 · Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis 외

While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on com…

Binary Classification

DO-GAN: A Double Oracle Framework for Generative Adversarial Networks

2021-02-17 · CVPR 2022 1 · Aye Phyu Phyu Aung, Xinrun Wang, Runsheng Yu, Bo An 외

In this paper, we propose a new approach to train Generative Adversarial Networks (GANs) where we deploy a double-oracle framework using the generator and discriminator oracles. GAN is essentially a two-player zero-sum g…

Continual Learning

Learning Rigidity-based Flocking Control with Gaussian Processes

2021-12-14 · Manuela Gamonal, Thomas Beckers, George J. Pappas, Leonardo J. Colombo

Flocking control of multi-agents system is challenging for agents with partially unknown dynamics. This paper proposes an online learning-based controller to stabilize flocking motion of double-integrator agents with add…

Gaussian Processes

Anytime PSRO for Two-Player Zero-Sum Games

2022-01-19 · Stephen Mcaleer, Kevin Wang, John Lanier, Marc Lanctot 외

Policy space response oracles (PSRO) is a multi-agent reinforcement learning algorithm that has achieved state-of-the-art performance in very large two-player zero-sum games. PSRO is based on the tabular double oracle (D…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Double Oracle Neural Architecture Search for Game Theoretic Deep Learning Models

2024-10-07 · Aye Phyu Phyu Aung, Xinrun Wang, Ruiyu Wang, Hau Chan 외

In this paper, we propose a new approach to train deep learning models using game theory concepts including Generative Adversarial Networks (GANs) and Adversarial Training (AT) where we deploy a double-oracle framework u…

Neural Architecture Search