arXiv (Cornell University) · 2018 · 11 citations · 12 references
ComputingComputer ScienceMathematicsAlgorithmsDecision TheoryGame TheoryAlgorithmic Game TheoryConvex AnalysisConvex OptimizationNash EquilibriumReinforcement LearningReinforcement Learning FoundationsConvex GamesCurvatureEquilibriumEquilibrium ComputationFrank-wolfe AlgorithmNash Equilibrium Computation
We consider the use of no-regret algorithms to compute equilibria for particular classes of convex-concave games. While standard regret bounds would lead to convergence rates on the order of $O(T^{-1/2})$, recent work \citep{RS13,SALS15} has established $O(1/T)$ rates by taking advantage of a particular class of optimistic prediction algorithms. In this work we go further, showing that for a particular class of games one achieves a $O(1/T^2)$ rate, and we show how this applies to the Frank-Wolfe method and recovers a similar bound \citep{D15}. We also show that such no-regret techniques can even achieve a linear rate, $O(\exp(-T))$, for equilibrium computation under additional curvature assumptions.
12
Maurice Sion · Pacific Journal of Mathematics · 1958 · 1.9K citations · Full text
Logarithmic regret algorithms for online convex optimization
Elad Hazan, Amit Agarwal, Satyen Kale · Machine Learning · 2007 · 874 citations · Full text
Constrained minimization methods
E. S. Levitin, B. T. Polyak · USSR Computational Mathematics and Mathematical Physics · 1966 · 852 citations
An analog of the minimax theorem for vector payoffs
David Blackwell · Pacific Journal of Mathematics · 1956 · 758 citations · Full text
Linli Xu, James Neufeld, Bryce Larson et al. · 2004 · 457 citations