mlsanityData to 14 Oct 2026

Bandit learning in concave N-person games

arXiv 1810.01925 ↗First posted 3 Oct 2018cs.GT cs.LG math.OCcited by 35

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 35 papers in the map (data through 14 Oct 2026). First posted on arXiv 3 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 12; 2023: 6; 2024: 1; 2025: 4; 2026: 5.

35 papers.

Sort:

By area:

  1. 2021Who Leads and Who Follows in Strategic Classification?cited by 53
  2. 2022Multiplayer Performative Prediction: Learning in Decision-Dependent Gamescited by 44
  3. 2021Scaling up Mean Field Games with Online Mirror Descentcited by 32
  4. 2022Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environmentscited by 32
  5. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  6. 2021The Confluence of Networks, Games and Learningcited by 26
  7. 2022A unified stochastic approximation framework for learning in gamescited by 23
  8. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  9. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  10. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
  11. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  12. 2021Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functionscited by 9
23 more
  1. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  2. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  3. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 7
  4. 2023Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Gamescited by 7
  5. 2022Stochastic Saddle Point Problems with Decision-Dependent Distributionscited by 6
  6. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  7. 2022Risk-Averse No-Regret Learning in Online Convex Gamescited by 5
  8. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  9. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  10. 2022A Zeroth-Order Momentum Method for Risk-Averse Online Convex Gamescited by 3
  11. 2023Exploiting hidden structures in non-convex games for convergence to Nash equilibriumcited by 3
  12. 2023Payoff-based learning with matrix multiplicative weights in quantum gamescited by 2
  13. 2021Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithmscited by 0
  14. 2022No-regret learning for repeated non-cooperative games with lossy banditscited by 0
  15. 2022Stochastic Direct Search Method for Blind Resource Allocationcited by 0
  16. 2024A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffscited by 0
  17. 2025Decoupled SGDA for Games with Intermittent Strategy Communicationcited by 0
  18. 2025Entry Barriers in Content Marketscited by 0
  19. 2025Robust equilibria in continuous games: From strategic to dynamic robustnesscited by 0
  20. 2026Last-Iterate Guarantees for Learning in Co-coercive Gamescited by 0
  21. 2026Nonparametric Learning and Earning with One-Point Feedback under Nonstationaritycited by 0
  22. 2026Learning in Continuous Games from Pairwise Preference Feedbackcited by 0
  23. 2026Decentralized Bandit Learning of Markov Perfect Equilibriacited by 0