Bandit learning in concave $N$-person games

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.

24 pages, 1 figure

Cited by in corpus (12)

• Fixed Point Strategies in Data Science
• Multi-agent online learning in time-varying games
• Fast Optimization with Zeroth-Order Feedback in Distributed, Multi-User MIMO Systems
• Gradient-free Online Learning in Games with Delayed Rewards
• No-regret distributed learning in subnetwork zero-sum games
• Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces
• Who Leads and Who Follows in Strategic Classification?
• No-regret Learning in Cournot Games
• A Warped Resolvent Algorithm to Construct Nash Equilibria
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Distributed No-Regret Learning in Multi-Agent Systems
• The Confluence of Networks, Games and Learning