Bandit learning in concave N-person games

Mario Bravo, David S. Leslie, Panayotis Mertikopoulos

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 agents may not even know they are playing a game; as such, the agents' most sensible choice in this setting is 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.

Introduction: The Challenge of Decentralized Learning

In classical game theory, researchers often assume that players possess a high degree of information. In these models, agents typically know the payoff functions of the game, observe the actions of their opponents, or at the very least, can calculate the gradient of their own reward function to determine how a strategy tweak might improve their outcome.

However, real-world decentralized systems—such as online auctions, network routing, or high-frequency trading—rarely offer such transparency. These are "bandit" environments, characterized by a "fog of war." In a bandit setting, a player chooses an action and receives a single scalar reward. They do not know the underlying rules of the game, what their opponents did to influence the reward, or what the payoff would have been had they chosen a different action.

This paper addresses a fundamental question: Can decentralized agents, each acting selfishly with this minimal information, still reach a stable Nash Equilibrium? This is particularly difficult because the environment is non-stationary; as one player learns and adjusts, the environment changes for everyone else, creating a moving target and introducing significant bias into the learning process.

Methodology: Mirror Descent with Bandit Feedback (MD-b)

The authors propose a learning framework called Multi-agent Mirror Descent with Bandit Feedback (MD-b). This approach combines several sophisticated optimization techniques to handle the lack of information:

  1. Mirror Descent (MD): A generalization of gradient descent, MD is designed to handle various action space geometries (such as simplices or general convex sets) by using a "regularizer" function to stabilize updates.
  2. Simultaneous Perturbation Stochastic Approximation (SPSA): Because players lack direct access to gradients, they must estimate them. The authors employ a "one-shot" approach: at each time step, a player selects a "pivot" point, adds a small random perturbation (defined by a query radius $\delta$), plays that perturbed action, and uses the resulting scalar reward to estimate the gradient.
  3. Feasibility Adjustments: To prevent random perturbations from pushing a player outside the legal bounds of the action space, the algorithm includes a safety mechanism that keeps pivot points slightly away from the boundaries.
  4. Decentralization: Crucially, the MD-b process is entirely decentralized. Each player runs their own algorithm independently without the need for coordination or shared information.

Theoretical Insights: Stability and the Bias-Variance Dilemma

The paper identifies monotonicity as the structural anchor required for convergence. In monotone games—a class that includes concave potential games and zero-sum games—the "aggregate drift" of the players' learning processes naturally points toward the Nash Equilibrium. Without this property, even players with perfect information might fall into limit cycles.

A core challenge in bandit learning is the Bias-Variance Dilemma. To obtain an accurate gradient estimate (low bias), a player needs a tiny perturbation radius $\delta$. However, a tiny $\delta$ makes the estimate extremely sensitive to noise (high variance). The authors provide a specific tuning schedule for shrinking both the step-size and the perturbation radius over time to balance this tradeoff and ensure long-term stability.

Furthermore, while much of the previous literature focuses on the convergence of the time-average of play, this paper proves convergence for the actual sequence of play. This is a significantly stronger result, as agents in real-world games care about their immediate rewards rather than an abstract historical average.

Key Results and the "Price of Blindness"

The research establishes two landmark results for monotone concave games:

  • Almost Sure Convergence: Theorem 5.1 proves that if players tune their learning parameters according to the prescribed schedule, their sequence of actions will converge to the Nash Equilibrium with probability 1.
  • Convergence Rate: For strongly monotone games, the authors derive a convergence rate of $O(n^{-1/3})$.

This rate highlights the "Price of Blindness." If players had access to perfect first-order (gradient) feedback, they could converge at a rate of $O(n^{-1})$. The reduction to $O(n^{-1/3})$ represents the inherent mathematical cost of operating in a multi-agent environment where gradients must be estimated from noisy, scalar rewards.

Limitations and Future Directions

While the paper provides a robust theoretical foundation for bandit learning in games, several avenues for future research remain:

  • Synchronicity: The current proofs assume players update their strategies simultaneously. Extending these results to asynchronous systems would increase their applicability to real-world networks.
  • Closing the Rate Gap: There remains a slight gap between the $O(n^{-1/3})$ rate and the $O(n^{-1/2})$ rate often seen in single-agent bandit optimization. Closing this gap might require more complex "two-point" gradient estimates, which currently require more coordination than the decentralized MD-b allows.
  • High-Probability Bounds: The current convergence rates are calculated in expectation. Future work could explore high-probability bounds to provide performance guarantees for every individual run of a game.

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