An Adversarial Analysis of Thompson Sampling for Full-Information Online Learning: From Finite to Infinite Action Spaces
We develop an analysis of Thompson sampling for online learning under full feedback—also known as prediction with expert advice—where the learner's prior is defined over the space of an adversary's future actions, rather than the space of experts. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret. In the classical finite-expert setting, this recovers optimal rates. As an initial step towards practical online learning in settings with a potentially-uncountably-infinite number of experts, we show that Thompson sampling with a certain Gaussian process prior widely-used in the Bayesian optimization literature has a $\mathcal{O}(\beta\sqrt{T\log(1+\lambda)})$ rate against a $\beta$-bounded $\lambda$-Lipschitz adversary.
Analyse antagoniste de l'échantillonnage de Thompson pour l'apprentissage en ligne avec informations complètes : des espaces d'action finis aux espaces d'action infinis
Nous développons une analyse de l'échantillonnage de Thompson pour l'apprentissage en ligne avec rétroaction complète (également connu sous le nom de prédiction avec avis d'expert) lorsque l'a priori de l'apprenant est défini sur l'espace des actions futures d'un adversaire, plutôt que sur l'espace des experts. Nous montrons que le regret se décompose en un regret que l'apprenant attendait a priori, plus un terme de type robustesse a priori que nous appelons regret excédentaire. Dans le cadre classique d'un nombre fini d'experts, cela permet de retrouver des taux optimaux. En guise de première étape vers l'apprentissage en ligne pratique dans des contextes où le nombre d'experts est potentiellement infini, nous montrons que l'échantillonnage de Thompson avec un certain processus gaussien préalable largement utilisé dans la littérature sur l'optimisation bayésienne a un taux $\mathcal{O}(\beta\sqrt{T\log(1+\lambda)})$ contre un adversaire $\beta$ borné $\lambda$-Lipschitz.
Date and Time
-
Langue de la présentation orale
Anglais
Langue des supports visuels
Anglais