PaperlayerView exact revision on arXiv

Source-linked AI summary

Blackwell Approachability and Low-Regret Learning are Equivalent

Jacob Abernethy, Peter L. Bartlett, Elad Hazan

arXiv:1011.1936v1cs.LGcs.GT

TL;DR

For games with vector-valued payoffs, the paper asks how to guarantee outcomes when scalar-payoff guarantees do not directly apply. It proves an algorithmic equivalence between Blackwell Approachability and no-regret learning for Online Linear Optimization, using conic duality for the reductions. The equivalence yields the first efficient algorithm for calibrated forecasting.

  • Problem

    For two-player games with vector-valued payoffs, the paper asks what guarantee can replace scalar-payoff guarantees such as the minimax result.

    Source: §1 · p. 2

  • Method

    The paper uses conic duality to reduce Blackwell Approachability to no-regret Online Linear Optimization and vice versa.

    Source: §1 · p. 2

  • Results

    The two problems are algorithmically equivalent, and the reduction gives the first efficient algorithm for calibrated forecasting.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Online Linear Optimization exactly captures the power of approachability, and the reduction provides an efficient route to calibrated forecasting.

    Source: §1 · p. 3, §4.1 · p. 9

    The stated duality result applies as long as S is halfspace-satisfiable with respect to the payoff mapping.

    Source: §3 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The paper asks how to guarantee outcomes in repeated games with vector payoffs, where scalar-payoff guarantees do not directly apply. It proves that Blackwell Approachability and no-regret learning for Online Linear Optimization are algorithmically equivalent, and uses the connection to obtain an efficient calibrated-forecasting algorithm.

1 Introduction

  • For vector payoffs, the target is whether the payoff vector can be guaranteed to lie in a convex set, rather than whether a scalar payoff reaches a threshold.In repeated play, Blackwell's theorem guarantees that the average payoff vector approaches the set.Source: §1 · p. 2
  • Blackwell's Approachability Theorem already yielded a low-regret guarantee as a special case, connecting repeated vector-payoff games with learning.Hannan gave the first no-regret algorithm for the discrete-action setting.Source: §1 · p. 2
  • Blackwell Approachability and no-regret learning for Online Linear Optimization are algorithmically equivalent: an algorithm for either problem can be converted into one for the other.The reductions use conic duality, relating low-regret learning in a cone K to approachability of its dual cone.Source: §1 · p. 2
  • The authors give the first efficient algorithm for calibrated forecasting by reducing calibration to approachability and then using the approachability-to-Online-Linear-Optimization reduction.Earlier calibration techniques had not provided efficiency guarantees on the strategy.Source: §1 · p. 2
  • The equivalence extends approachability beyond the discrete setting and shows that Online Linear Optimization captures its full power, despite prior views that it was strictly stronger than regret minimization.Blackwell had noted that approachability implies no-regret algorithms in the discrete setting.Source: §1 · p. 3

2 Preliminaries

The preliminaries define approachability through repeated vector-payoff games, introduce Online Linear Optimization and regret, and establish cone facts used in the later reductions.

2.1 Blackwell Approachability

  • Satisfiability requires one strategy to work against every opponent move, while response-satisfiability allows the player's strategy to depend on the opponent's move.The section also defines halfspace-satisfiability and proves it equivalent to response-satisfiability for closed convex sets.Source: §2.1 · pp. 3, 5
  • Approachability weakens one-shot guarantees: an adaptive player seeks an average payoff in a convex target set over repeated play.For a closed convex set, Blackwell's theorem states that approachability is equivalent to response-satisfiability.Source: §2.1 · p. 4

2.2 Online Linear Optimization

  • Online Linear Optimization chooses points from a bounded convex decision set and incurs the linear cost of each choice; regret compares performance with a fixed alternative.A no-regret algorithm has regret growing as O(√T), as defined in the section.Source: §2.2 · p. 5
  • For any bounded decision set, a no-regret algorithm exists, and the paper later uses Zinkevich's Gradient Descent algorithm in its equivalence proof.The section identifies this existence result as the theorem to be shown equivalent to Blackwell's theorem.Source: §2.2 · p. 5

2.3 Convex cones in Hilbert space

  • For a convex cone C, the double polar equals C, and supporting hyperplanes of its polar correspond to points of C up to scaling.These cone identities provide geometric tools for the approachability and learning reductions.Source: §2.3 · p. 6
  • Lifting a convex set K into the cone generated by {1} ⊕ K bounds its original distance by the lifted distance, within a factor of 1 + ∥K∥.The stated inequalities compare dist(1 ⊕ x, C) and dist(x, K) for x outside K.Source: §2.3 · p. 6

3 Duality of Approachability and Low-Regret Learning

The section proves a two-way reduction between Blackwell approachability and no-regret Online Linear Optimization. Each problem’s algorithm can be converted into one for the other, with the approachability-to-learning reduction yielding a regret bound and the reverse reduction requiring halfspace-satisfiability.

3 Duality of Approachability and Low-Regret Learning

  • The reductions connect approachability and low regret for Online Linear Optimization, whose goal is regret sublinear in T.The OLO decision set is bounded and convex, and the algorithm receives linear cost functions over successive rounds.Source: §3 · p. 6
  • An approachability algorithm can be converted into an OLO algorithm, establishing one direction of the equivalence.Proposition 1 states that the reduction produces an OLO algorithm for any input approachability algorithm.Source: §3 · p. 6
  • The first reduction uses a vector-payoff game with payoff ⟨f, x⟩⊕−f and an approach set defined from the decision set K.These choices form the game and approach set for converting approachability into OLO.Source: §3 · p. 7
  • A low-regret OLO algorithm can be converted into an approachability algorithm when the target set is halfspace-satisfiable.The construction uses an OLO algorithm and a halfspace oracle; its distance bound is given in Proposition 2.Source: §3 · p. 7

4 Efficient Calibration via Approachability and OLO

The section characterizes ε-calibration through prediction frequencies, establishes a randomized forecaster via approachability, and then constructs an efficient algorithm using OLO. Its construction uses a binary-search oracle and Online Gradient Descent.

4 Efficient Calibration via Approachability and OLO

  • The (ℓ1, ε)-calibration rate equals the distance of the calibration vector to the ℓ1 ball of radius ε/2.The calibration frequency is evaluated on rounds when predictions lie near a given probability; intervals used sublinearly often can be ignored.Source: §4 · p. 8

4.1 Existence of Calibrated Forecaster via Blackwell Approachability

  • The calibration reduction uses response-satisfiability, which the section describes as easier and more intuitive than the earlier approachability reduction.The earlier reduction is attributed to Foster.Source: §4.1 · pp. 8–9
  • A randomized forecaster is (ℓ1, ε)-calibrated with high probability when its approachability strategy approaches the ℓ1 ball of radius ε/2.The forecaster draws predictions according to its distribution over the discretized probability values.Source: §4.1 · p. 9

4.2 Efficient Algorithm for Calibration via Online Linear Optimization

  • The algorithm chooses a unit-cube decision set and an oracle mapping each OLO vector to a distribution satisfying the calibration bound for any outcome.The reduction sets the OLO cost vectors to −ℓ(wt, yt).Source: §4.2 · p. 10
  • The section’s calibration algorithm runs its oracle in O(log 1/ε) computation using binary search over prediction coordinates.The oracle selects a distribution over prediction values to satisfy the required bound for every outcome.Source: §4.2 · p. 10
  • Online Gradient Descent supplies the learning algorithm; sparse payoff vectors allow O(1) computation per round and O(min{T, m}) memory.The vectors have at most two nonzero coordinates, and the stored state is the OGD vector.Source: §4.2 · p. 11

A Proofs

The proofs relate distance to a convex set to a dual-cone optimization and compare distance to K with distance to its cone. They use these bounds to establish approachability under the stated halfspace-oracle conditions.

A Proofs

  • The distance from x to C equals the maximum inner product of x with a unit vector in the dual cone C0.The proof establishes both inequalities by using the projection of x onto C.Source: A Proofs · p. 13
  • Distance to K is bounded by (1 + ∥K∥) times distance to its cone in the comparison shown for Figure 1.The proof uses the closest points to 1 ⊕ x in the cone and to x in K; Figure 1 describes the corresponding distance ratio.Source: A Proofs · p. 13, Figure 1 · p. 13
  • The halfspace-satisfiability condition supplies an oracle response, and the proof converts a bound on distance to cone(S) into a bound on distance to S.It removes the first coordinate and applies the comparison factor 1 + ∥S∥ before concluding.Source: A Proofs · p. 14

B A generalization of Blackwell to convex functions

The paper extends Blackwell approachability to function-valued payoffs using an oracle and Online Convex Optimization. Under the stated oracle conditions, the set S is approachable, and the average gain’s distance to S converges to zero.

B A generalization of Blackwell to convex functions

  • The generalization defines halfspaces by x, with Hx containing functions f for which f(x) ≤ 0.Its dual set consists of points x satisfying f(x) ≤ 0 for every f in S, and distance to S is measured by the maximal inner product with such a hyperplane.Source: B A generalization of Blackwell to… · p. 15
  • Under the stated oracle conditions, the set S of functions is approachable.The oracle maps a halfspace containing S to a distribution over strategies whose resulting loss function lies inside that halfspace.Source: B A generalization of Blackwell to… · p. 15
  • Online Convex Optimization makes the proof a simple generalization, where Blackwell’s geometric proof does not directly generalize.The OCO algorithm produces x_t, the oracle returns a mixed strategy p_t, and that strategy defines the iteration’s cost function.Source: B A generalization of Blackwell to… · p. 15
  • The average gain function’s distance to S converges to zero.The oracle guarantee f_t(x_t) ≤ 0 combines with the OCO low-regret guarantee to establish this conclusion.Source: B A generalization of Blackwell to… · p. 15
Loading 1011.1936v1…