PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast swap regret minimization and applications to approximate correlated equilibria

Binghui Peng, Aviad Rubinstein

arXiv:2310.19647v2cs.GTcs.AIcs.DScs.LGcs.MA

TL;DR

Prior swap-regret algorithms required at least a linear number of rounds, leaving open whether mixed strategies could achieve sublinear regret minimization. The paper gives an algorithm with a polylogarithmic-in-n round bound for fixed ε, with matching lower-bound dependence on ε.

  • Problem

    Prior algorithms did not guarantee diminishing swap regret before a linear number of days, leaving open whether mixed strategies could achieve it in sublinear time.

    Source: §1 · p. 2

  • Method

    The paper introduces an algorithm that minimizes swap regret by using mixed strategies.

    Source: §1 · p. 2

  • Results

    For any ε>0, the algorithm obtains at most ε-swap regret in (log(n)/ε)^O(1/ε) days, with exponential dependence on ε matched by a lower bound.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The swap-regret algorithm yields faster convergence to approximate correlated equilibrium, including uncoupled dynamics for normal-form games.

    Source: Game Theory · p. 4, §4.4 · p. 15

    The algorithm holds against a strong adaptive adversary, but the lower bound rules out better algorithms only against an oblivious adversary; adaptive adversaries suffice for correlated-equilibrium applications.

    Source: §2.1 · p. 7

Abstract

from arXiv · show

We give a simple and computationally efficient algorithm that, for any constant $\varepsilon>0$, obtains $\varepsilon T$-swap regret within only $T = \mathsf{polylog}(n)$ rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum and Mansour 2007]. Our algorithm has an exponential dependence on $\varepsilon$, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to $\varepsilon$-Correlated Equilibrium ($\varepsilon$-CE) in several regimes: For normal form two-player games with $n$ actions, it implies the first uncoupled dynamics that converges to the set of $\varepsilon$-CE in polylogarithmic rounds; a $\mathsf{polylog}(n)$-bit communication protocol for $\varepsilon$-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]); and an $\tilde{O}(n)$-query algorithm for $\varepsilon$-CE (resolving an open problem of [Babichenko'2020] and obtaining the first separation between $\varepsilon$-CE and $\varepsilon$-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for $\mathit{normal}$ $\mathit{form}$ $\mathit{correlated}$ $\mathit{equilibria}$, a solution concept often conjectured to be computationally intractable (e.g. [Stengel-Forges'08, Fujii'23]).

1 Introduction

The paper resolves the open problem of faster swap-regret minimization with a polylogarithmic-round guarantee for fixed ε. It uses this advance to obtain faster approximate correlated-equilibrium algorithms across several game-theoretic settings.

1 Introduction

  • Prior algorithms required at least Ω(n) days for diminishing swap regret, and asked whether mixed strategies could achieve sublinear time.The reduction of requires Θ(log(n^n)) = ~Θ(n) days, while show ~Θ(n) is tight for pure strategies.Source: §1 · p. 2
  • For any ε>0, the algorithm obtains at most ε-swap regret in (log(n)/ε)^O(1/ε) days.For fixed ε, the number of days is polylogarithmic in n.Source: §1 · p. 3
  • The algorithm’s dependence on ε is exponential, and the paper proves a matching lower bound.The improvement over prior round complexity is exponential for constant ε.Source: §1 · p. 3

Game Theory

  • The result yields uncoupled dynamics converging to ε-approximate correlated equilibria in (log(n))^O(1/ε) iterations.Earlier swap-regret-based dynamics converged in ~Θ(n) iterations.Source: Game Theory · p. 3
  • For two-player games, the paper gives an ε-CE protocol using (log(n))^O(1/ε) communication bits and query algorithms using at most mn(log(mn))^O(1/ε) payoff queries.Both algorithms have success probability 1−1/(mn)^ω(1) or higher, as specified in their respective corollaries.Source: Game Theory · p. 4
  • A randomized algorithm computes ε-approximate correlated equilibrium in time mn(log(mn))^O(1/ε), with success probability at least 1−1/(mn)^ω(1).The bound applies to m-player games with n actions.Source: Game Theory · p. 4
  • The paper gives a PTAS for normal-form correlated equilibrium in extensive-form games, with uncoupled dynamics running in poly(m,n)·(Φ log(n))^O(1/ε) time.The result addresses a solution concept whose efficient computation was described as a major open problem [FP23].Source: Game Theory · p. 4

1.1 Related work

  • Prior work connects diminishing external regret to coarse correlated equilibria, while diminishing swap regret is needed to approach correlated equilibria.Earlier algorithms and analyses left open whether uncoupled dynamics could reach correlated equilibria in sublinear or polylogarithmic rounds.Source: §1.1 · p. 5

2 Preliminary

The preliminaries set up adversarial online learning and define swap regret as a benchmark for action-switching rules. They connect low swap regret to approximate correlated equilibrium and introduce MWU as a tool for controlling external regret.

2.1 Online learning

  • In adversarial online learning, the algorithm chooses a distribution over actions each round and receives rewards selected by an adversary.The model distinguishes an oblivious adversary from adaptive adversaries that may observe past or current strategies.Source: §2.1 · p. 7

2.2 Correlated equilibria and swap regret

  • If every player incurs at most R(T) swap regret over T rounds, their empirical joint-action distribution is an R(T)/T-correlated equilibrium.Correlated equilibrium constrains the gain available from deviating from a recommended action.Source: §2.2 · pp. 7–8

2.3 Useful tools

  • MWU provides a small-external-regret guarantee against a strong adaptive adversary for bounded reward vectors.The stated guarantee uses a learning rate based on the reward bound, number of actions, and rounds.Source: §2.3 · p. 8

3 Multi-scale MWU

Multi-scale MWU combines restarted MWU threads with different time scales to obtain swap regret at most ε in a polylogarithmic-in-n number of days for constant ε. Its analysis bounds regret by splitting it across thread groups and applying induction.

3 Multi-scale MWU

  • For any ε > 0, multi-scale MWU obtains at most ε-swap regret in (log(n)/ε)^O(1/ε) days.The algorithm runs 2S MWU threads and aggregates them uniformly, with S := log_2(1/ε) + 1.Source: §3 · p. 8
  • The algorithm restarts threads at different intervals, treating blocks of days as meta-days for MWU updates.The k-th thread restarts every T/H^k days, and each restart lasts H^k days.Source: §3 · pp. 8–9
  • The proof splits swap regret between earlier threads and newly added threads, then bounds both parts by induction over scales.Within each interval, the newer threads’ strategies are fixed, allowing intervals to be viewed as meta-days.Source: §3 · pp. 10–11
  • The analysis chooses H = Θ(log(n)/ε^2) and S := log_2(1/ε) + 1 to set the total duration T_S = H·2^S.The resulting duration is (log(n)/ε)^O(1/ε).Source: §3 · pp. 8, 11

4 Applications

Multi-scale MWU yields approximate correlated equilibria through uncoupled dynamics and supports query, communication, and computation procedures. In extensive-form games, it also gives a polynomial-time approximation scheme for normal-form correlated equilibrium.

4 Applications

  • An uncoupled dynamic converges to the set of ε-approximate correlated equilibria in (log(n))^O(1/ε) iterations.The protocol has players run multi-scale MWU while estimating rewards by sampling other players’ mixed strategies.Source: §4 · p. 12

4.1 Query complexity of correlated equilibria

  • mn(log(mn))^O(1/ε) payoff queries suffice for a randomized ε-approximate correlated equilibrium algorithm, with success probability at least 1 − 1/(mn)^ω(1).The query model allows queries to entries of otherwise unknown utility matrices or tensors.Source: §4.1 · p. 13

4.2 Communication complexity of correlated equilibrium

  • (log(n))^O(1/ε) bits suffice for a randomized protocol finding an ε-approximate correlated equilibrium in a two-player n-action game.The protocol’s success probability is at least 1 − 1/n^ω(1).Source: §4.2 · p. 13

4.3 Computational complexity of correlated equilibrium

  • mn(log(mn))^O(1/ε) time suffices for a randomized algorithm to compute an ε-approximate correlated equilibrium, with success probability at least 1 − 1/(mn)^ω(1).The computation bound includes sampling, reward-vector construction, and maintaining the multi-scale MWU threads.Source: §4.3 · pp. 14–15

4.4 Polynomial time approximation scheme for extensive-form game

  • In an extensive-form game, the algorithm returns an ε-approximate NFCE in poly(m, n)·(Φ log(n))^O(1/ε) time.The result is a randomized uncoupled dynamics algorithm with success probability at least 1 − 1/(mnΦ)^ω(1).Source: §4.4 · pp. 15–16

5 Lower bound

At T=n^(1−2δ), the lower bound gives swap regret at least Ω(T/log T), proved using an adversarial sequence built from a randomly skipped K-ary tree.

5.1 Hard sequence

  • Nature traverses a K-ary tree depth-first, sometimes skipping the rest of a subtree, and sets rewards according to which leaves and actions have been visited.Each leaf represents two actions; other actions receive rewards based on their position in the tree, while previously passed actions receive −1.Source: §5.1 · pp. 16–17

5.2 Analysis

  • The analysis uses a two-coin game at each visited leaf, with an unknown uniformly chosen biased coin and a dummy outside option, to bound switching regret.The coins draw from Bernoulli distributions B1/2 and B1/2+∆ over H=1/(400∆²) days.Source: §5.2 · p. 20

5 Lower bound

  • Against an oblivious adversary, every algorithm incurs at least Ω(n^(1−2δ)/log n)=Ω(T/log T) swap regret when T=n^(1−2δ).For T≤n^(1−2δ), the proof extends the bound by merging actions with identical rewards.Source: §5 · p. 16, §5.2 · p. 22

A A historical remark on internal vs swap regret

The appendix distinguishes the paper’s swap-regret definition from related internal-regret variants and explains why those variants differ for constant-ε regret.

A historical remark on internal vs swap regret

  • The paper’s internal-regret discussion traces the origin of the closely related notion to, whose definition differs in where expectation over the algorithm’s randomness is taken.For oblivious adversaries, the two definitions are equivalent; cited lower bounds for adaptive adversaries use realized actions.Source: A A historical remark on internal vs… · p. 29
  • Later internal-regret definitions can be stricter or more lenient than swap regret, depending on how deviations are allowed.[FV99] use a stricter definition, while the definition common today is more lenient.Source: A A historical remark on internal vs… · p. 29
  • Although these notions are equivalent up to poly(n) factors when regret approaches zero, they are not equivalent for constant-εT regret.Under the common internal-regret notion, a uniformly random strategy trivially obtains T/n regret.Source: A A historical remark on internal vs… · p. 29

B Missing proof from Section 4

The appendix supplies proof details for sparsifying correlated-equilibrium distributions and for recursively computing and sampling strategies in extensive-form games.

B Missing proof from Section 4

  • The sparsified distribution p′ is formed by sampling D rows from the row distribution and properly normalizing them.The sample size is D=O(S² log(n)/δ²).Source: B Missing proof from Section 4 · p. 29
  • With high probability, p′ is an (ε+δ)-approximate correlated equilibrium with row support O(S² log(n)/δ²) and column support S.These support bounds are stated for p′ after sampling and normalization.Source: B Missing proof from Section 4 · p. 29
  • For extensive-form games, the proof samples strategies from a partition-function distribution, with the partition function computed recursively over information sets.The sampling proceeds top-down through information sets; the appendix gives the efficient implementation for games with a chance player.Source: B Missing proof from Section 4 · pp. 30, 32, 33

C Missing proof from Section 5

The appendix’s lower-bound proof analyzes the reward of an unknown biased coin, tracks probability mass across the tree, and bounds the time spent visiting nodes.

C Missing proof from Section 5

  • The proof bounds an algorithm’s reward using Pinsker’s inequality, independence, KL(B1/2||B1/2+∆) ≤ 8∆², and H = 1/(400∆²).Source: C Missing proof from Section 5 · p. 36
  • The analysis accounts for probability mass placed on actions before Nature visits their leaves by decomposing node intervals into intervals for descendant leaves.The proof combines the resulting mass expressions for Xi and Ma.Source: C Missing proof from Section 5 · p. 38
  • An induction over tree levels bounds expected time spent at nodes, using Nature’s child-skipping probability and the leaf-visit duration H=1/(400∆²).The proof treats unvisited nodes as having zero visit time.Source: C Missing proof from Section 5 · p. 38
Loading 2310.19647v2…