Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini’s Regret

Tor Lattimore
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:1547-1575, 2022.

Abstract

We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any p ∈ [1/2, 1] there exists an infinite partial monitoring game for which the minimax regret over n rounds is n^p up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is n^(4/7) up to subpolynomial factors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-lattimore22a, title = {Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini’s Regret}, author = {Lattimore, Tor}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {1547--1575}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/lattimore22a/lattimore22a.pdf}, url = {https://proceedings.mlr.press/v178/lattimore22a.html}, abstract = {We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any p ∈ [1/2, 1] there exists an infinite partial monitoring game for which the minimax regret over n rounds is n^p up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is n^(4/7) up to subpolynomial factors.} }
Endnote
%0 Conference Paper %T Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini’s Regret %A Tor Lattimore %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-lattimore22a %I PMLR %P 1547--1575 %U https://proceedings.mlr.press/v178/lattimore22a.html %V 178 %X We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any p ∈ [1/2, 1] there exists an infinite partial monitoring game for which the minimax regret over n rounds is n^p up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is n^(4/7) up to subpolynomial factors.
APA
Lattimore, T.. (2022). Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini’s Regret. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:1547-1575 Available from https://proceedings.mlr.press/v178/lattimore22a.html.

Related Material