← Paper page Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms Ask this paper arXiv ↗

Multi-Agent Learning for
Iterative Dominance Elimination:
Formal Barriers and New Algorithms

Can learners who only see noisy rewards quickly weed out every move that a rational player would never make?

Jibang Wu, Haifeng Xu, Fan Yao · COLT 2022

Press → or click to step through

Learning a game by trial and error

agent A agent B the game: payoffs unknown to both 2 3 sees only its own payoff, plus noise sees only its own payoff, plus noise no messages, and no view of the other’s moves or payoffs

Goal: stop playing dominated moves, in actual current play, not just on average.

A move is dominated if some other choice (possibly a random mix) does better whatever the others do. Repeatedly removing such moves leads to the “rationalizable” outcomes.

One elimination unlocks the next

buyer’s average value $500 never worth paying new average $250 ruled out next $0$250$500$750$1000 price the buyer offers → high sells only at $800+ medium sells only at $400+ lemon sells at any price high-quality sellers leave medium sellers leave

Only lemons are traded. Each round of elimination makes the next one possible.

Akerlof’s market for lemons, as told in the paper: the three qualities are equally likely; buyers value them at $1000, $500 and $0. The paper asks how fast learners reach such outcomes from noisy feedback.

Try it: the “Diamond in the Rough” game

The paper’s benchmark game with 4 moves each. In each cell: A’s payoff, B’s payoff; −8 is a big loss (payoffs before scaling).

Standard learners take exponentially long

why: old scores act like inertia rounds → total score becomes dominated rough move better move catch-up time schematic
so every layer multiplies the wait layer 1layer 2layer 3layer 4 schematic

In Diamond-in-the-Rough games, the whole Dual Averaging family (Exponential Weights, lazy gradient descent, fictitious play) has not settled on the diamond even after a number of rounds exponential in the number of moves.

This holds with the usual non-increasing learning rates, and even with perfect, noise-free feedback about every move. A rough move looks very profitable before it becomes dominated, so it piles up a large score. (The proof uses games whose penalty is large compared with the number of moves.)

Stronger guarantees don’t rescue them

Diamond in the Rough with 10 moves each the equilibrium (the diamond) 100% a near-equilibrium (deviating gains at most a billionth) at most 50% players’ total payoff plays the diamond 0% of the time

No-swap-regret learners aim at approximate correlated equilibria, but “almost stable” can still be far from the real equilibrium.

In simulations, no-swap-regret learners stayed stuck on the first few moves even after 100 million rounds.

The fix: forget the past, at the right speed

how much a past reward counts today long ago now standard: old rewards count as much as new ones, or more Exp3-DH: old evidence fades schematic

If every agent runs Exp3-DH, all iteratively dominated moves are eliminated within polynomially many rounds, in any game, with high probability, in actual play.

Exp3 with Diminishing History shrinks all past scores a little every round, so impressions formed before a move became dominated wear off. The forgetting rate is tuned to the number of elimination layers (or, safely, the total number of moves); it also uses unbiased payoff estimates and fading exploration.

In experiments, it finds the diamond

progress of elimination (1 means all dominated moves are gone) 01 100 million rounds → five other learners: 5 or 6 of 38 elimination steps Exp3-DH: close to complete traced by hand from the paper’s Figure 1 (right): 20 moves each, payoff noise added; approximate

State-of-the-art bandit learners, even ones built for games, stall in the rough; Exp3-DH gets through.

The others include a no-swap-regret learner and learners with recency bias or increasing learning rates. In the market for lemons (50 and 200 sellers), Exp3-DH also reached the collapse far faster.

What this means

  1. 1Weeding out dominated moves is a natural learning goalIt asks less than an equilibrium does, yet the chain of eliminations can be long, as in the market for lemons.
  2. 2Standard no-regret learning is exponentially slow at itThe whole Dual Averaging family gets stuck in the rough, and no-swap-regret guarantees do not prevent it.
  3. 3Forgetting at the right rate fixes itExp3-DH eliminates all iteratively dominated moves in polynomially many rounds.

Paper page · arXiv