Approachability, fast and slow

Vianney Perchet, Shie Mannor
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:474-488, 2013.

Abstract

Approachability has become a central tool in the analysis of repeated games and online learning. A player plays a repeated vector-valued game against Nature and her objective is to have her long-term average reward inside some target set. The celebrated results of Blackwell provide a 1/\sqrtn convergence rate of the expected point-to-set distance if this is achievable, i.e., if the set is approachable. In this paper we provide a characterization for the convergence rates of approachability and show that in some cases a set can be approached with a 1/n rate. Our characterization is solely based on a combination of geometric properties of the set with properties of the repeated game, and not on additional restrictive assumptions on Nature’s behavior.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Perchet13, title = {Approachability, fast and slow}, author = {Perchet, Vianney and Mannor, Shie}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {474--488}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Perchet13.pdf}, url = {https://proceedings.mlr.press/v30/Perchet13.html}, abstract = {Approachability has become a central tool in the analysis of repeated games and online learning. A player plays a repeated vector-valued game against Nature and her objective is to have her long-term average reward inside some target set. The celebrated results of Blackwell provide a 1/\sqrtn convergence rate of the expected point-to-set distance if this is achievable, i.e., if the set is approachable. In this paper we provide a characterization for the convergence rates of approachability and show that in some cases a set can be approached with a 1/n rate. Our characterization is solely based on a combination of geometric properties of the set with properties of the repeated game, and not on additional restrictive assumptions on Nature’s behavior.} }
Endnote
%0 Conference Paper %T Approachability, fast and slow %A Vianney Perchet %A Shie Mannor %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Perchet13 %I PMLR %P 474--488 %U https://proceedings.mlr.press/v30/Perchet13.html %V 30 %X Approachability has become a central tool in the analysis of repeated games and online learning. A player plays a repeated vector-valued game against Nature and her objective is to have her long-term average reward inside some target set. The celebrated results of Blackwell provide a 1/\sqrtn convergence rate of the expected point-to-set distance if this is achievable, i.e., if the set is approachable. In this paper we provide a characterization for the convergence rates of approachability and show that in some cases a set can be approached with a 1/n rate. Our characterization is solely based on a combination of geometric properties of the set with properties of the repeated game, and not on additional restrictive assumptions on Nature’s behavior.
RIS
TY - CPAPER TI - Approachability, fast and slow AU - Vianney Perchet AU - Shie Mannor BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Perchet13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 474 EP - 488 L1 - http://proceedings.mlr.press/v30/Perchet13.pdf UR - https://proceedings.mlr.press/v30/Perchet13.html AB - Approachability has become a central tool in the analysis of repeated games and online learning. A player plays a repeated vector-valued game against Nature and her objective is to have her long-term average reward inside some target set. The celebrated results of Blackwell provide a 1/\sqrtn convergence rate of the expected point-to-set distance if this is achievable, i.e., if the set is approachable. In this paper we provide a characterization for the convergence rates of approachability and show that in some cases a set can be approached with a 1/n rate. Our characterization is solely based on a combination of geometric properties of the set with properties of the repeated game, and not on additional restrictive assumptions on Nature’s behavior. ER -
APA
Perchet, V. & Mannor, S.. (2013). Approachability, fast and slow. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:474-488 Available from https://proceedings.mlr.press/v30/Perchet13.html.

Related Material