Research map / Bandits and online learning / Online convex optimization and games
Comparator-Adaptive $\Phi$-Regret: Improved Bounds, Simpler Algorithms, and Applications to 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.
Gives simpler, faster comparator-adaptive Phi-regret algorithms via a special prior over binary transformations (kernelized MWU and prior-aware BM-reduction), improving bounds to O(sqrt(c_phi T log d)) and yielding accelerated adaptive Phi-equilibrium convergence in nonnegative-social-external-regret games.
Problem
Comparator-adaptive Phi-regret in the expert problem: achieving regret bounds that scale with a sparsity-based complexity c_phi of the comparator transformation, and extending to accelerated convergence to Phi-equilibria in games.
Approach
Define a prior distribution over binary row-stochastic transformations built as a mixture of psi-induced distributions; show a prior-dependent regret bound implies c_phi-dependent regret for all phi; achieve it efficiently via a kernelized MWU and a prior-aware BM-reduction, with the latter extended via optimistic learners and a meta-learner with stability correction to games.
Key results
- Achieves Reg(phi)=O(sqrt(c_phi T log d)) for all phi, removing the extra sqrt(c_phi d) term and log d factor of Lu et al. 2025.
- In nonnegative-social-external-regret games, each player's Phi-regret is O(c_phi N log d + N^2 log d), giving O((max c_phi N log d + N^2 log d)/T) approximate Phi-equilibrium rate.
- For correlated equilibria the rate improves over prior work on d-dependence and removes polylog(T) factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the special prior and learn over multiple learning rates | Meta MWU with kernelized MWU · Expert problem, all transformations | regret: \mathcal{O}\Big(\sqrt{c_\phi (T+d) \rbr{\log d}^{3}}\Big) -> \mathcal{O}\rbr{\sqrt{(1+c_\phi \log d)T}+\sqrt{T\log\log d | Helped |
| Use prior-aware BM-reductions and learn over priors and learning rates | Meta algorithm over BM-reductions · Expert problem, all transformations | regret: \mathcal{O}\Big(\sqrt{c_\phi (T+d) \rbr{\log d}^{3}}\Big) -> \mathcal{O}\rbr{\sqrt{(1+c_\phi\log d)T} + \sqrt{T\log d}} | Helped |
| Use optimistic BM-reductions, an external-regret learner, and stability correction | Game meta algorithm · Nonnegative-social-external-regret games, \Phi-equilibrium | convergence rate | Helped |
| Reuse intermediate statistics in the kernelized implementation | Kernelized MWU · Kernelized MWU iteration | time complexity: \mathcal{O}(d^5) -> \mathcal{O}\rbr{ d^2 } | Helped |
Experimental setup
Metrics: regret bound approximate Phi-equilibrium rate
Baselines: Lu et al. 2025 comparator-adaptive algorithm MWU with uniform prior OMWU
Builds on: Kernelized MWU BM-reduction optimistic MWU Lu et al. 2025 comparator-adaptive Phi-regret
Closest papers by meaning
- Near-Optimal No-Regret Learning in General Games (NeurIPS 2021 · similarity 0.90)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.90)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.89)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.88)
- p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.87)
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.