Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback

2021/12/06 by Wenjia Ba, Ba, Wenjia, Tianyi Lin +5 · 5 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2112.02856

openalex publication_date 2021/12/06 · openalex created_date 2022/07/13 · openalex updated_date 2026/07/28

Abstract

We consider online no-regret learning in unknown games with bandit feedback, where each player can only observe its reward at each time -- determined by all players' current joint action -- rather than its gradient. We focus on the class of smooth and strongly monotone games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct a new bandit learning algorithm and show that it achieves the single-agent optimal regret of Θ(n√(T)) under smooth and strongly concave reward functions (n ≥ 1 is the problem dimension). We then show that if each player applies this no-regret learning algorithm in strongly monotone games, the joint action converges in the last iterate to the unique Nash equilibrium at a rate of Θ(nT^-1/2). Prior to our work, the best-known convergence rate in the same class of games is O(n^2/3T^-1/3) (achieved by a different algorithm), thus leaving open the problem of optimal no-regret learning algorithms (since the known lower bound is Ω(nT^-1/2)). Our results thus settle this open problem and contribute to the broad landscape of bandit game-theoretical learning by identifying the first doubly optimal bandit learning algorithm, in that it achieves (up to log factors) both optimal regret in the single-agent learning and optimal last-iterate convergence rate in the multi-agent learning. We also present preliminary numerical results on several application problems to demonstrate the efficacy of our algorithm in terms of iteration count.

Cited by

• Risk-Averse Learning with Varying Risk Levels
• Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
• Multi-User Contextual Cascading Bandits for Personalized Recommendation
• Decentralized Contextual Bandits with Network Adaptivity
• First- and Zeroth-Order Learning in Asynchronous Games

Related

• Doubly Optimal No-Regret Learning in Monotone Games
• No-regret learning for repeated non-cooperative games with lossy bandits
• Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
• Bandit learning in concave N-person games
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback