Research map / Optimization / Nonconvex and smooth optimization
Virtual Double Oracle: Faster Convergence by Leveraging Strategies That Were Watching All Along
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Virtual Double Oracle, a variant of online Double Oracle that improves convergence in two-player zero-sum games by changing how newly discovered strategies are initialised in the MWU weights.
Problem
Computing Nash equilibria in two-player zero-sum games with large strategy spaces via Double Oracle / PSRO, where MWU-based online variants reset newly discovered strategies at each expansion, which may slow convergence.
Approach
Identifies the reinitialisation step of newly added strategies in online Double Oracle as an underexplored design choice; the proposed method instead leverages strategies that were already being tracked (virtually watched) rather than resetting new ones, yielding faster convergence than ODO's O(sqrt(k ln k / T)) rate.
Key results
- Online Double Oracle obtains an O(sqrt(k ln k / T)) convergence rate, which the proposed Virtual Double Oracle is claimed to improve upon (abstract only; exact rate not stated in provided text).
Limitations
- Only the abstract was available; full experimental scope unknown.
Experimental setup
Metrics: convergence rate exploitability
Baselines: Double Oracle PSRO Online Double Oracle
Builds on: Double Oracle PSRO Online Double Oracle multiplicative weights update
Closest papers by meaning
- Regret-Minimizing Double Oracle for Extensive-Form Games (ICML 2023 · similarity 0.91)
- XDO: A Double Oracle Algorithm for Extensive-Form Games (NeurIPS 2021 · similarity 0.90)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.87)
- Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.87)
- Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.87)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.