Research map / Learning theory and algorithms / Submodular and game algorithms
Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends kernelization (exact MWU simulation via kernel functions) to bandit and semi-bandit feedback in polyhedral games, yielding kernelized GeometricHedge and IX-based algorithms with efficient per-iteration cost and runtime to epsilon-CCE for Colonel Blotto, graphic matroid and network congestion games.
Problem
Efficiently learning coarse correlated equilibria in polyhedral games (exponentially many actions with combinatorial structure) under bandit and semi-bandit feedback, where prior runtimes are impractically large in the action-dimension parameters.
Approach
Kernelize the second moments of MWU (needed for GeometricHedge's unbiased combinatorial bandit estimator) and the first moments (for IX semi-bandit estimators) with d^2 and d kernel computations, plus a kernelized exact sampling procedure using extra d kernels, so that no-realized-regret learning runs in polynomial time in d and m.
Key results
- Bandit-feedback regret of O~(d^{2/3} m^{4/3} T^{2/3}) with high probability for kernelized GeometricHedge.
- Semi-bandit regret of O~(m sqrt(Td)) with high probability, the first high-probability general result for this setting per the authors.
- Colonel Blotto runtime to epsilon-CCE improves to O~(n^{2+omega} k^{6+omega}/eps^3) under bandit and O~(n^2 k^4/eps^2) under semi-bandit feedback.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use kernelized learning instead of prior bandit learning | Colonel Blotto · Colonel Blotto, bandit | runtime to ε-CCE: \widetilde{\mathcal{O}}( {n^{18} k^{11}}/{\varepsilon^2} ) -> \widetilde{\mathcal{O}}\left(n^{2+\omega}k^{6+\omega}/\var | Helped |
| Use kernelized learning instead of prior bandit learning | Graphic matroid congestion games · Graphic matroid congestion games, bandit | runtime to ε-CCE: \widetilde{\mathcal{O}}(|V|^{29}/\varepsilon^2) -> \widetilde{\mathcal{O}}\big({|E|^3|V|^6(|V|^{\omega-1}+|E|)}/{\vareps | Helped |
| Use kernelized learning instead of prior bandit learning | Network congestion games · Network congestion games, bandit | runtime to ε-CCE: \widetilde{\mathcal{O}}(|E|^9K^{10}/\varepsilon^2) -> \widetilde{\mathcal{O}}(|E|^{2+\omega}K^4/\varepsilon^3) | Helped |
| Use kernelized learning instead of prior semi-bandit learning | Network congestion games · Network congestion games, semi-bandit | runtime to ε-CCE: \widetilde{\mathcal{O}}(|E|^{1+\omega}K^3/\varepsilon^2) -> \widetilde{\mathcal{O}}(|E|^{1+\omega}K^2/\varepsilon^2) | Helped |
Limitations
- Bandit regret has d and m dependence that is worse than the optimal expected-regret bound for semi-bandit (sqrt(m) factor)
- Bandit-setting epsilon-CCE runtime scales as 1/eps^3 rather than 1/eps^2
- Results are theoretical; no empirical experiments reported in the provided text
Experimental setup
Metrics: runtime to epsilon-CCE regret bound
Baselines: Leon et al. Zimmert and Lattimore Beaglehole et al. Bartlett et al. Dani et al.
Builds on: GeometricHedge kernelized MWU implicit exploration barycentric spanners optimistic MWU
Closest papers by meaning
- Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.89)
- Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games (NeurIPS 2024 · similarity 0.87)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.87)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.87)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.86)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · 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.