% Useful text commands \newcommand{\hr}{\begin{center}\rule{0.5\linewidth}{\linethickness}\end{center}} % Abbreviations \newcommand{\ie}{\emph{i.e.}} \newcommand{\iid}{\emph{i.i.d.}} \newcommand{\eg}{\emph{e.g.}} \newcommand{\cf}{\emph{cf}} \newcommand{\hook}{\newline\ensuremath{\hookrightarrow}\;} \newcommand{\citationright}[1]{\hfill{}\tiny{\textcolor{gray}{#1}}\normalsize} \newcommand{\citationbottomright}[1]{\vfill{}\hfill{}\tiny{\textcolor{gray}{#1}}\normalsize} \newcommand{\citationbottomrightsmall}[1]{\vfill{}\hfill{}\small{\textcolor{gray}{#1}}\normalsize} % Maths \newcommand{\bigO}[1]{\ensuremath{\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(#1\right)}} \newcommand{\smallO}[1]{\ensuremath{\mathop{}\mathopen{}o\mathopen{}\left(#1\right)}} \newcommand{\E}{\mathbb{E}} \renewcommand{\Pr}{\mathbb{P}} \newcommand{\indic}{\mathbbm{1}} \newcommand{\kl}{\ensuremath{\mathrm{kl}}} \newcommand{\KL}{\ensuremath{\mathrm{KL}}} \newcommand{\Ccal}{\mathcal{C}} % Algorithms \newcommand{\UCBalpha}{\ensuremath{\mathrm{UCB}_{\alpha}}} \newcommand{\UCB}{\ensuremath{\mathrm{UCB}_1}} \newcommand{\UCBH}{\ensuremath{\mathrm{UCB}}-\ensuremath{\mathrm{H}}} \newcommand{\ExpThree}{\ensuremath{\mathrm{Exp}3}} \newcommand{\BayesUCB}{\ensuremath{\mathrm{Bayes}\mathrm{UCB}}} \newcommand{\klUCB}{\ensuremath{\mathrm{kl}\text{-}\mathrm{UCB}}} \newcommand{\KLUCB}{\ensuremath{\mathrm{KL}\text{-}\mathrm{UCB}}} \newcommand{\rhoRand}{\ensuremath{\mathrm{Rho}\mathrm{Rand}}} \newcommand{\RhoRand}{\ensuremath{\mathrm{Rho}\mathrm{Rand}}} \newcommand{\rhoFixedRank}{\ensuremath{\mathrm{Rho}\mathrm{FixedRank}}} \newcommand{\rhoRandRot}{\ensuremath{\mathrm{Rho}\mathrm{Rand}\mathrm{Rot}}} \newcommand{\rhoRandSticky}{\ensuremath{\mathrm{Rho}\mathrm{Rand}\mathrm{Sticky}}} \newcommand{\rhoRandALOHA}{\ensuremath{\mathrm{Rho}\mathrm{Rand}\mathrm{ALOHA}}} \newcommand{\rhoLearn}{\ensuremath{\mathrm{Rho}\mathrm{Learn}}} \newcommand{\rhoRandEst}{\ensuremath{\mathrm{Rho}\mathrm{Est}}} % \newcommand{\rhoRandUCB}{\ensuremath{\mathrm{Rho}\mathrm{Rand}\text{-}\mathrm{UCB}_1}} \newcommand{\rhoRandklUCB}{\ensuremath{\mathrm{Rho}\mathrm{Rand}\text{-}\mathrm{KLUCB}}} % \newcommand{\Selfish}{\ensuremath{\mathrm{Selfish}}} \newcommand{\RandTopM}{\ensuremath{\mathrm{RandTopM}}} \newcommand{\MCTopM}{\ensuremath{\mathrm{MCTopM}}} \newcommand{\TDFS}{\ensuremath{\mathrm{TDFS}}} \newcommand{\MEGA}{\ensuremath{\mathrm{MEGA}}} \newcommand{\MusicalChair}{\ensuremath{\mathrm{Musical}\,\mathrm{Chair}}} \newcommand{\SICMMAB}{\ensuremath{\mathrm{SIC}}-\ensuremath{\mathrm{MMAB}}} % Abbreviations \newcommand{\Mbest}{\ensuremath{M\text{-}\mathrm{best}}} \newcommand{\Mworst}{\ensuremath{M\text{-}\mathrm{worst}}} \newcommand{\TopM}{\widehat{M^j}} \newcommand{\limInf}{\underline{\lim}}