Abstract
In algorithmic game theory, no-regret learning is a cornerstone for understanding how independent agents reach stable, efficient outcomes. While it is known that such learning eventually approaches the Price of Anarchy (PoA), standard convergence rates are often too slow for practical applications. This paper introduces the Low Approximate Regret (LAR) property, proving that common learning algorithms converge to near-optimal social welfare at a fast $O(1/T)$ rate. Unlike previous breakthroughs, these results apply to realistic "realized feedback" settings, scale linearly with the number of players, and encompass a broad range of standard algorithms.
The Challenge of Fast Convergence
The efficiency of decentralized systems is often measured by the Price of Anarchy—the ratio between the social cost of a Nash equilibrium and the social optimum. While no-regret learning is guaranteed to converge to the PoA, the standard rate of $O(1/\sqrt{T})$ is often too slow for dynamic environments.
Recent research (e.g., Syrgkanis et al., 2015) demonstrated that "fast convergence" ($O(1/T)$) is theoretically possible, but these findings came with significant caveats:
- Unrealistic Feedback: They required "expected feedback," where players know the full probability distribution of opponents' moves.
- Algorithm Specificity: Results were limited to a narrow class of "optimistic" algorithms.
- Poor Scaling: The convergence speed degraded quadratically ($O(n^2)$) with the number of players ($n$).
Introducing Low Approximate Regret (LAR)
The authors propose a shift in perspective: instead of demanding vanishing regret against the absolute best action, they require Low Approximate Regret. An algorithm satisfies LAR if its regret is small relative to a $(1 + \epsilon)$-multiplicative approximation of the best action in hindsight.
This slight relaxation—accepting a tiny constant loss $\epsilon$—unlocks powerful properties:
- Ubiquity: Many standard algorithms, such as vanilla Hedge, naturally satisfy LAR.
- Realized Feedback: Analysis can be performed using only the actual costs observed by players in each round, rather than theoretical expectations.
- Robustness: Fast convergence becomes a general feature of learning in "smooth" games (like routing or auctions), rather than a niche property of specialized algorithms.
Key Results and Comparison
The primary contribution of this work is establishing a new state-of-the-art for learning in games. By utilizing the LAR property, the authors improve the convergence rate's dependence on the number of players from $O(n^2)$ to $O(n)$ and reduce the per-round computational complexity from exponential to linear in the number of actions.
As shown in the table above, the LAR framework allows for fast convergence using realized costs while maintaining a significantly lower computational overhead per round compared to the previous RVU (Regret-bounded by Variation in Utilities) property. Notably, the authors also show that Optimistic Hedge enjoys the "best of both worlds," converging to the exact PoA with expected feedback and the approximate PoA with realized feedback.
Efficient Learning in Bandit Settings
For scenarios where players only observe the payoff of their chosen action (bandit feedback), the paper introduces a novel algorithm based on log-barrier regularization with importance sampling. This approach is both simpler and more efficient than prior "small-loss" bandit methods, achieving a bound of $O(d \log T / \epsilon)$ with better dependence on the number of actions $d$.
Implications for Large-Scale Systems
The improved scaling with respect to the number of players ($n$) makes this theory highly relevant for large-scale engineering problems, such as internet traffic routing. Furthermore, the authors extend their analysis to dynamic population games, proving that the system remains near-optimal even as players enter and leave, provided the "churn" (turnover) is not excessive.
Conclusion
By demonstrating that the "slow" $O(1/\sqrt{T})$ rate is often a mathematical artifact of overly strict regret requirements, this paper provides a more optimistic and practical view of learning in games. The LAR property shows that fast convergence is a robust, ubiquitous feature of common algorithms, paving the way for more efficient decentralized optimization in complex, multi-agent environments.
Summary updated