No Internal Regret via Neighborhood Watch

Dean Foster, Alexander Rakhlin
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:382-390, 2012.

Abstract

We present an algorithm which attains O(\sqrtT) internal (and thus external) regret for finite games with partial monitoring under the local observability condition. Recently, this condition has been shown by Bartok, Pal, and Szepesvari (2011) to imply the O(\sqrtT) rate for partial monitoring games against an i.i.d. opponent, and the authors conjectured that the same holds for non-stochastic adversaries. Our result is in the affirmative, and it completes the characterization of possible rates for finite partial-monitoring games, an open question stated by Cesa-Bianchi, Lugosi, and Stoltz (2006). Our regret guarantees also hold for the more general model of partial monitoring with random signals.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-foster12, title = {No Internal Regret via Neighborhood Watch}, author = {Foster, Dean and Rakhlin, Alexander}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {382--390}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/foster12/foster12.pdf}, url = {https://proceedings.mlr.press/v22/foster12.html}, abstract = {We present an algorithm which attains O(\sqrtT) internal (and thus external) regret for finite games with partial monitoring under the local observability condition. Recently, this condition has been shown by Bartok, Pal, and Szepesvari (2011) to imply the O(\sqrtT) rate for partial monitoring games against an i.i.d. opponent, and the authors conjectured that the same holds for non-stochastic adversaries. Our result is in the affirmative, and it completes the characterization of possible rates for finite partial-monitoring games, an open question stated by Cesa-Bianchi, Lugosi, and Stoltz (2006). Our regret guarantees also hold for the more general model of partial monitoring with random signals.} }
Endnote
%0 Conference Paper %T No Internal Regret via Neighborhood Watch %A Dean Foster %A Alexander Rakhlin %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-foster12 %I PMLR %P 382--390 %U https://proceedings.mlr.press/v22/foster12.html %V 22 %X We present an algorithm which attains O(\sqrtT) internal (and thus external) regret for finite games with partial monitoring under the local observability condition. Recently, this condition has been shown by Bartok, Pal, and Szepesvari (2011) to imply the O(\sqrtT) rate for partial monitoring games against an i.i.d. opponent, and the authors conjectured that the same holds for non-stochastic adversaries. Our result is in the affirmative, and it completes the characterization of possible rates for finite partial-monitoring games, an open question stated by Cesa-Bianchi, Lugosi, and Stoltz (2006). Our regret guarantees also hold for the more general model of partial monitoring with random signals.
RIS
TY - CPAPER TI - No Internal Regret via Neighborhood Watch AU - Dean Foster AU - Alexander Rakhlin BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-foster12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 382 EP - 390 L1 - http://proceedings.mlr.press/v22/foster12/foster12.pdf UR - https://proceedings.mlr.press/v22/foster12.html AB - We present an algorithm which attains O(\sqrtT) internal (and thus external) regret for finite games with partial monitoring under the local observability condition. Recently, this condition has been shown by Bartok, Pal, and Szepesvari (2011) to imply the O(\sqrtT) rate for partial monitoring games against an i.i.d. opponent, and the authors conjectured that the same holds for non-stochastic adversaries. Our result is in the affirmative, and it completes the characterization of possible rates for finite partial-monitoring games, an open question stated by Cesa-Bianchi, Lugosi, and Stoltz (2006). Our regret guarantees also hold for the more general model of partial monitoring with random signals. ER -
APA
Foster, D. & Rakhlin, A.. (2012). No Internal Regret via Neighborhood Watch. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:382-390 Available from https://proceedings.mlr.press/v22/foster12.html.

Related Material