Learning in Games: Robustness of Fast Convergence

Abstract

We show that learning algorithms satisfying a $\text{low approximate regret}$ property experience fast convergence to approximate optimality in a large class of repeated games. Our property, which simply requires that each learner has small regret compared to a $(1+\epsilon )$-multiplicative approximation to the best action in hindsight, is ubiquitous among learning algorithms; it is satisfied even by the vanilla Hedge forecaster. Our results improve upon recent work of Syrgkanis et al. [SALS15] in a number of ways. We require only that players observe payoffs under other players' realized actions, as opposed to expected payoffs. We further show that convergence occurs with high probability, and show convergence under bandit feedback. Finally, we improve upon the speed of convergence by a factor of $n$, the number of players. Both the scope of settings and the class of algorithms for which our analysis provides fast convergence are considerably broader than in previous work. Our framework applies to dynamic population games via a low approximate regret property for shifting experts. Here we strengthen the results of Lykouris et al. [LST16] in two ways: We allow players to select learning algorithms from a larger class, which includes a minor variant of the basic Hedge algorithm, and we increase the maximum churn in players for which approximate optimality is achieved. In the bandit setting we present a new algorithm which provides a "small loss"-type bound with improved dependence on the number of actions in utility settings, and is both simple and efficient. This result may be of independent interest.

27 pages. NIPS 2016

Cited by in corpus (24)

• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• No-regret learning and mixed Nash equilibria: They do not mix
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Optimizing for the Future in Non-Stationary MDPs
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Near-Optimal No-Regret Learning in General Games
• Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
• Hedging in games: Faster convergence of external and swap regrets
• Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes
• Stochastic bandits robust to adversarial corruptions
• The route to chaos in routing games: When is Price of Anarchy too optimistic?
• Corralling Stochastic Bandit Algorithms
• Smooth Bandit Optimization: Generalization to Hölder Space
• Scale Free Adversarial Multi Armed Bandits
• No-regret Learning in Cournot Games
• A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Learning to Price Against a Moving Target
• Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price of Anarchy
• Nonstochastic Bandits and Experts with Arm-Dependent Delays