2021-07-21-hsieh21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium	In game-theoretic learning, several agents are simultaneously following their individual interests, so the environment is non-stationary from each player’s perspective. In this context, the performance of a learning algorithm is often measured by its regret. However, no-regret algorithms are not created equal in terms of game-theoretic guarantees: depending on how they are tuned, some of them may drive the system to an equilibrium, while others could produce cyclic, chaotic, or otherwise divergent trajectories. To account for this, we propose a range of no-regret policies based on optimistic mirror descent, with the following desirable properties: (\emph{i}) they do not require \emph{any} prior tuning or knowledge of the game; (\emph{ii}) they all achieve $\mathcal{O}(\sqrt{T})$ regret against arbitrary, adversarial opponents; and (\emph{iii}) they converge to the best response against convergent opponents. Also, if employed by all players, then (\emph{iv}) they guarantee $\mathcal{O}(1)$ \emph{social} regret; while (\emph{v}) the induced sequence of play converges to Nash equilibirum with $\mathcal{O}(1)$ \emph{individual} regret in all variationally stable games (a class of games that includes all monotone and convex-concave zero-sum games).	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	hsieh21a	0	Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium	2388	2422	2388-2422	2388	false	Hsieh, Yu-Guan and Antonakopoulos, Kimon and Mertikopoulos, Panayotis	given family Yu-Guan Hsieh given family Kimon Antonakopoulos given family Panayotis Mertikopoulos	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/hsieh21a/hsieh21a.pdf