Bandit Learning in Concave N-Person Games

Mario Bravo, David S. Leslie, Panayotis Mertikopoulos

Introduction

In complex, multi-agent environments, players often operate with severely limited information. They may only observe their own rewards without any knowledge of the game's underlying structure, the payoff functions, or even the existence of other players. This paper demonstrates that even in this "fog of war"—formally known as the bandit framework—players can still converge to a stable Nash Equilibrium. By employing a specific "no-regret" learning algorithm based on mirror descent, individual players can collectively reach a stable state with a convergence rate of $O(n^{-1/3})$.

The Challenge of the Bandit Framework

Traditional game theory frequently assumes omniscient players who fully understand the rules and the mathematical functions governing payoffs. However, in real-world scenarios like online auctions, ad bidding, or network routing, players simply take an action and receive a reward.

The core question is: can these "blind" players, who only aim to minimize their own regret (the difference between their actual earnings and their optimal hypothetical earnings), eventually settle into a stable Nash Equilibrium? Previous research established that this is possible if players have access to the "gradient" (the exact direction of maximum reward). Achieving the same stability using only a single scalar reward per round—bandit feedback—is a significantly harder problem.

Multi-Agent Online Mirror Descent

To solve this, the authors propose a multi-agent adaptation of Online Mirror Descent (OMD). Because players lack access to actual gradients, they must estimate them using a technique called Simultaneous Perturbation Stochastic Approximation (SPSA).

Algorithm 1: Multi-agent mirror descent with bandit feedback.

The learning loop for each player proceeds in four main steps:

  1. Perturb: Instead of playing their "ideal" action, the player adds a small amount of random noise (a perturbation) to their choice.
  2. Observe: The player receives a single payoff based on the collective, simultaneous actions of all participants.
  3. Estimate: Using only that single reward and the direction of their random noise, the player constructs a "one-shot" estimate of the reward gradient.
  4. Update: The player uses Mirror Descent to update their "pivot" point for the next round.

To ensure players do not accidentally select an invalid action (e.g., bidding a negative amount), the algorithm incorporates a "safety net". This feasibility adjustment projects the players' updated actions back within the valid boundaries of the game's action space.

Geometric illustration of the perturbation and projection steps.

Key Insights and Theoretical Guarantees

Monotonicity is the Key

While no-regret learning can lead to chaotic, cyclical behavior in some games, the authors prove it is guaranteed to stabilize in monotone games. In these environments, the collective "incentives" of the players naturally point toward the equilibrium.

The Bias-Variance Dilemma

Estimating gradients from single scalar rewards introduces a severe bias-variance trade-off. A tiny perturbation radius ($\delta_n$) keeps the bias low, but causes the variance of the gradient estimate to explode. The authors resolve this by carefully decaying both the perturbation radius and the learning step size ($\gamma_n$) over time, finding the mathematical "sweet spot" that guarantees convergence.

Stability Without Rationality

One of the paper's most profound takeaways is that reaching a Nash Equilibrium does not require "common knowledge of rationality." Players do not need to be hyper-rational or model their opponents; a simple, individualistic no-regret algorithm is sufficient to guide the entire system to a stable equilibrium.

Convergence Rates and the "Bandit Price"

The paper proves that the sequence of actual play converges to the Nash Equilibrium almost surely (with probability 1) in monotone games. For "strongly monotone" games, the authors derive a convergence rate of $O(n^{-1/3})$.

In standard optimization with full gradient information, convergence typically occurs at $O(1/n)$. With single-agent bandit feedback, the optimal rate is $O(n^{-1/2})$. The slightly slower $O(n^{-1/3})$ rate achieved here is the "bandit price" paid for tracking the actual actions taken at every step in a multi-agent setting, rather than relying on a time-averaged version of play (which is easier to stabilize mathematically but less realistic for actual game dynamics).

Limitations and Future Work

While this work provides strong theoretical foundations, several open challenges remain:

  • The Rate Gap: There is still a theoretical gap between the $n^{-1/3}$ rate achieved in this multi-agent setting and the $n^{-1/2}$ rate seen in single-agent optimization. More sophisticated gradient estimators might eventually close this gap.
  • Synchronicity: The current mathematical proofs assume all players update their strategies simultaneously. Extending these guarantees to decentralized, asynchronous environments where players experience lag is a crucial next step for real-world applicability.
  • High-Probability Bounds: The results primarily focus on convergence "in expectation." Proving that the algorithm succeeds with "high probability" in any single, isolated run remains an open problem for future research.

Summary updated

Abstract

This paper examines the long-run behavior of learning with bandit feedback in non-cooperative concave games. The bandit framework accounts for extremely low-information environments where the agents may not even know they are playing a game; as such, the agents’ most sensible choice in this setting would be to employ a no-regret learning algorithm. In general, this does not mean that the players' behavior stabilizes in the long run: no-regret learning may lead to cycles, even with perfect gradient information. However, if a standard monotonicity condition is satisfied, our analysis shows that no-regret learning based on mirror descent with bandit feedback converges to Nash equilibrium with probability 1. We also derive an upper bound for the convergence rate of the process that nearly matches the best attainable rate for single-agent bandit stochastic optimization.
BibTeX
@inproceedings{bravo2018bandit,
  author = {Mario Bravo and David S. Leslie and Panayotis Mertikopoulos},
  title = {{Bandit Learning in Concave N-Person Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=snYucn0pgrO},
}
Figure