Name
Abstract | ||
|---|---|---|
We address online combinatorial optimization when the player has a prior over the adversaryu0027s sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based on the {em information ratio}, resulting in optimal worst-case regret bounds. In this paper we introduce three novel ideas to this line of work. First we propose a new quantity, the scale-sensitive information ratio, which allows us to obtain more refined first-order regret bounds (i.e., bounds of the form $sqrt{L^*}$ where $L^*$ is the loss of the best combinatorial action). Second we replace the entropy over combinatorial actions by a coordinate entropy, which allows us to obtain the first optimal worst-case bound for Thompson Sampling in the combinatorial setting. Finally, we introduce a novel link between Bayesian agents and frequentist confidence intervals. Combining these ideas we show that the classical multi-armed bandit first-order regret bound $tilde{O}(sqrt{d L^*})$ still holds true in the more challenging and more general semi-bandit scenario. This latter result improves the previous state of the art bound $tilde{O}(sqrt{(d+m^3)L^*})$ by Lykouris, Sridharan and Tardos. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Learning | Journal |
Volume | Citations | PageRank |
abs/1902.00681 | 0 | 0.34 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sébastien Bubeck | 1 | 0 | 0.68 |
| Mark Sellke | 2 | 14 | 2.11 |