Blackwell Approachability and Low-Regret Learning are Equivalent

2010/11/08 by Abernethy, Jacob, Bartlett, Peter L., Hazan, Elad · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1011.1936

Abstract

We consider the celebrated Blackwell Approachability Theorem for two-player games with vector payoffs. We show that Blackwell's result is equivalent, via efficient reductions, to the existence of "no-regret" algorithms for Online Linear Optimization. Indeed, we show that any algorithm for one such problem can be efficiently converted into an algorithm for the other. We provide a useful application of this reduction: the first efficient algorithm for calibrated forecasting.

Cited by

• Playing Markov Games Without Observing Payoffs

Related

• Refined approachability algorithms and application to regret minimization with global costs
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent
• Time-Dependent Blackwell Approachability and Application to Absorbing Games
• Approachability, Regret and Calibration; implications and equivalences
• Response-Based Approachability and its Application to Generalized No-Regret Algorithms