NeurIPS 2019poster51 citations
Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
Abstract
The information-theoretic analysis by Russo and Van Roy [2014] in combination with minimax duality has proved a powerful tool for the analysis of online learning algorithms in full and partial information settings. In most applications there is a tantalising similarity to the classical analysis based on mirror descent. We make a formal connection, showing that the information-theoretic bounds in most applications are derived from existing techniques from online convex optimisation. Besides this, we improve best known regret guarantees for $k$-armed adversarial bandits, online linear optimisation on $\ell_p$-balls and bandits with graph feedback.
BibTeX
@inproceedings{NEURIPS2019_92cf3f7e,
author = {Zimmert, Julian and Lattimore, Tor},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Connections Between Mirror Descent, Thompson Sampling and the Information Ratio},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/92cf3f7ef90630755b955924254e6ec4-Paper.pdf},
volume = {32},
year = {2019}
}