Cover Image

An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$-Regret Minimization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Farina, Gabriele, Perdomo, Juan Carlos
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Stability of Online Algorithms in Performative Prediction
by: Farina, Gabriele, et al.
Published: (2026)

Efficient $Φ$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2024)

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
by: Zhang, Brian Hu, et al.
Published: (2025)

Faster Rates for No-Regret Learning in General Games via Cautious Optimism
by: Soleymani, Ashkan, et al.
Published: (2025)

On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
by: Fan, Zhiyuan, et al.
Published: (2024)

Meta-Learning in Self-Play Regret Minimization
by: Sychrovský, David, et al.
Published: (2025)

Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games
by: Soleymani, Ashkan, et al.
Published: (2025)

GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning
by: Fan, Zhiyuan, et al.
Published: (2026)

Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
by: Cai, Yang, et al.
Published: (2023)

GPU-Accelerated Counterfactual Regret Minimization
by: Kim, Juho
Published: (2024)

Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
by: Maiti, Arnab, et al.
Published: (2025)

Polynomial-Time Computation of Exact $Φ$-Equilibria in Polyhedral Games
by: Farina, Gabriele, et al.
Published: (2024)

Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation
by: Ren, Hang, et al.
Published: (2025)

The Relationship between No-Regret Learning and Online Conformal Prediction
by: Ramalingam, Ramya, et al.
Published: (2025)

Regret Minimization in Bilateral Trade With Perturbed Markets
by: Lunghi, Anna, et al.
Published: (2026)

Regret Minimization in Stackelberg Games with Side Information
by: Harris, Keegan, et al.
Published: (2024)

Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
by: Cai, Yang, et al.
Published: (2025)

Honor Among Bandits: No-Regret Learning for Online Fair Division
by: Procaccia, Ariel D., et al.
Published: (2024)

Improved Regret Bounds for Online Fair Division with Bandit Learning
by: Schiffer, Benjamin, et al.
Published: (2025)

Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent
by: Xu, Hang, et al.
Published: (2024)

Selling Joint Ads: A Regret Minimization Perspective
by: Aggarwal, Gagan, et al.
Published: (2024)

Online Learning and Equilibrium Computation with Ranking Feedback
by: Liu, Mingyang, et al.
Published: (2026)

Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond
by: Bacchiocchi, Francesco, et al.
Published: (2025)

Computational Lower Bounds for Regret Minimization in Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2024)

Learning not to Regret
by: Sychrovský, David, et al.
Published: (2023)

Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints
by: Bechavod, Yahav, et al.
Published: (2025)

Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
by: Liu, Junyan, et al.
Published: (2026)

Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
by: Potfer, Marius, et al.
Published: (2025)

On Tractable $Φ$-Equilibria in Non-Concave Games
by: Cai, Yang, et al.
Published: (2024)

Next-Token Prediction and Regret Minimization
by: Mohri, Mehryar, et al.
Published: (2026)

LiteEFG: An Efficient Python Library for Solving Extensive-form Games
by: Liu, Mingyang, et al.
Published: (2024)

Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2025)

Barriers to Welfare Maximization with No-Regret Learning
by: Anagnostides, Ioannis, et al.
Published: (2024)

On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
by: Maiti, Arnab, et al.
Published: (2023)

Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization
by: D'Amico-Wong, Luca, et al.
Published: (2024)

Real-Time Parallel Counterfactual Regret Minimization
by: Li, Boning, et al.
Published: (2026)

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
by: Zhang, Brian Hu, et al.
Published: (2022)

Deep (Predictive) Discounted Counterfactual Regret Minimization
by: Xu, Hang, et al.
Published: (2025)

Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
by: Lu, Jiuyao, et al.
Published: (2025)

ReLExS: Reinforcement Learning Explanations for Stackelberg No-Regret Learners
by: Huang, Xiangge, et al.
Published: (2024)