Polylogarithmic regret achieved in matrix games with limited feedback
Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback
Machine LearningComputer Science and Game Theory
Summary
This paper looks at how to learn strategies in game situations where you only see your own payoffs and the other player's moves, but not the full game. The authors present a new method called Optimistic Payoff Balancing that learns to play nearly as well as the best stable strategy in such games, even when there are several equally good options. Their approach uses estimated confidence in payoffs to adjust strategies and reduce mistakes over time. This work extends previous results from very small games to games with any number of strategies.
What this means in practice
- •For online advertising teams: Develop bidding strategies that learn efficiently from limited feedback and adapt to competitor actions in multi-player ad auctions.
- •For robotics system designers: Tune multi-agent robotic systems where agents learn to coordinate or compete with only partial payoff feedback and observation of other agents’ actions.
Authors
Yuheng Zhang
Abstract
We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.