Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback
Wenjia Ba, Tianyi Lin, Jiawei Zhang, Zhengyuan Zhou
Operations Research · 2025 · Volume 73 · Issue 6
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 ( 𝑛 ≥ 1 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 ˜ Θ ( 𝑛 𝑇 − 1 / 2 ) Θ ˜ ( n T − 1 / 2 ) . Prior to our work, the best-known convergence rate in the same class of games is ˜ 𝑂 ( 𝑛 2 / 3 𝑇 − 1 / 3 ) O ˜ ( n 2 / 3 T − 1 / 3 ) (achieved by a different algorithm), thus leaving open the problem of optimal no-regret learning algorithms (the known lower bound is Ω ( 𝑛 𝑇 − 1 / 2 ) Ω ( n T − 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 multiagent learning. We also present preliminary numerical results on several application problems to demonstrate the efficacy of our algorithm in terms of iteration count. Funding: This work was generously supported by the National Science Foundation [Grant NSF-2106508]. This work was also partially funded by the New York University Center for Global Economy and Business [2025 grant]. Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2021.0445 .
Keywords
Optimization, no-regret learning, bandit feedback model, strongly monotone games, optimal regret, optimal last-iterate convergence rate, mirror descent
Enable JavaScript for citation tools and additional paper interactions.