The authors develop Optimistic Payoff Balancing (OPB), an algorithm for unknown finite matrix games with bandit payoff feedback and observed opponent actions. OPB achieves instance-dependent O(log^2 T) Nash regret against arbitrary adaptive opponents, even when equilibria are nonunique. This extends previous results that only worked for 2x2 games to any finite dimensions, using a reference strategy and uncertainty-scaled adjustments.
Polylogarithmic Nash regret achieved for any finite matrix game
Optimistic Payoff Balancing extends bandit-feedback guarantees from 2x2 to general dimensions, resolving an open problem.
Academic
Yuheng Zhang
University of Illinois Urbana-Champaign
Research Digest··2 min read
Thread:RL Regret Bounds
In one line
Optimistic Payoff Balancing achieves polylogarithmic Nash regret in arbitrary finite matrix games with bandit feedback.
Read it as
The authors study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions.
The authors consider two-player zero-sum matrix games where the learner observes only the opponent's action and a noisy payoff for the sampled action pair (bandit feedback).
How it works
stage by stageThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.