Exploration by Optimisation in Partial Monitoring

Tor Lattimore, Csaba Szepesvári
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2488-2515, 2020.

Abstract

We provide a novel algorithm for adversarial k-action d-outcome partial monitoring that is adaptive, intuitive and efficient. The highlight is that for the non-degenerate locally observable games, the n-round minimax regret is bounded by 6m k^(3/2) sqrt(n log(k)), where m is the number of signals. This matches the best known information-theoretic upper bound derived via Bayesian minimax duality. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games. High probability bounds and simple experiments are also provided.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-lattimore20a, title = {Exploration by Optimisation in Partial Monitoring}, author = {Lattimore, Tor and Szepesv{\'a}ri, Csaba}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {2488--2515}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/lattimore20a/lattimore20a.pdf}, url = {https://proceedings.mlr.press/v125/lattimore20a.html}, abstract = { We provide a novel algorithm for adversarial k-action d-outcome partial monitoring that is adaptive, intuitive and efficient. The highlight is that for the non-degenerate locally observable games, the n-round minimax regret is bounded by 6m k^(3/2) sqrt(n log(k)), where m is the number of signals. This matches the best known information-theoretic upper bound derived via Bayesian minimax duality. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games. High probability bounds and simple experiments are also provided.} }
Endnote
%0 Conference Paper %T Exploration by Optimisation in Partial Monitoring %A Tor Lattimore %A Csaba Szepesvári %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-lattimore20a %I PMLR %P 2488--2515 %U https://proceedings.mlr.press/v125/lattimore20a.html %V 125 %X We provide a novel algorithm for adversarial k-action d-outcome partial monitoring that is adaptive, intuitive and efficient. The highlight is that for the non-degenerate locally observable games, the n-round minimax regret is bounded by 6m k^(3/2) sqrt(n log(k)), where m is the number of signals. This matches the best known information-theoretic upper bound derived via Bayesian minimax duality. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games. High probability bounds and simple experiments are also provided.
APA
Lattimore, T. & Szepesvári, C.. (2020). Exploration by Optimisation in Partial Monitoring. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2488-2515 Available from https://proceedings.mlr.press/v125/lattimore20a.html.

Related Material