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 = {Dean Foster and Alexander Rakhlin}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {382--390}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 382--390 %U http://proceedings.mlr.press %V 22 %W PMLR %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 PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-foster12 PB - PMLR SP - 382 DP - PMLR EP - 390 L1 - http://proceedings.mlr.press/v22/foster12/foster12.pdf UR - http://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 PMLR 22:382-390

Related Material