## Abstract

The PhD thesis of Maillard (2013) presents a rather obscure algorithm for the K-armed bandit problem. This less-known algorithm, which we call Maillard sampling (MS), computes the probability of choosing each arm in a closed form, which is not true for Thompson sampling, a widely-adopted bandit algorithm in the industry. This means that the bandit-logged data from running MS can be readily used for counterfactual evaluation, unlike Thompson sampling. Motivated by such merit, we revisit MS and perform an improved analysis to show that it achieves both the asymptotical optimality and √KT log T minimax regret bound where T is the time horizon, which matches the known bounds for asymptotically optimal UCB. We then propose a variant of MS called MS^{+} that improves its minimax bound to √KT log K. MS^{+} can also be tuned to be aggressive (i.e., less exploration) without losing the asymptotic optimality, a unique feature unavailable from existing bandit algorithms.

Original language | English (US) |
---|---|

Pages (from-to) | 54-72 |

Number of pages | 19 |

Journal | Proceedings of Machine Learning Research |

Volume | 151 |

State | Published - 2022 |

Event | 25th International Conference on Artificial Intelligence and Statistics, AISTATS 2022 - Virtual, Online, Spain Duration: Mar 28 2022 → Mar 30 2022 |

## ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability