Sélection de modèles dans les problèmes de bandits stochastiques contextuels

Résumé

Nous étudions la sélection de modèles de bandits dans des environnements stochastiques. Notre approche repose sur un algorithme maître qui sélectionne entre les algorithmes de base candidats. Nous développons une abstraction de l'algorithme maître-base qui peut fonctionner avec des classes générales d'algorithmes de base et différents types d'algorithmes maîtres adversaires. Nos méthodes s'appuient sur une transformation de lissage nouvelle et générique pour les algorithmes de bandits qui nous permet d'obtenir des garanties de sélection de modèle optimales O(√T) pour les problèmes de bandits contextuels stochastiques tant que l'algorithme de base optimal satisfait une garantie de regret à haute probabilité. Nous montrons par une borne inférieure que même lorsqu'un des algorithmes de base a un regret O(logT), il est en général impossible d'obtenir mieux que Ω(√T) de regret dans la sélection de modèle, même asymptotiquement. En utilisant nos techniques, nous abordons la sélection de modèles dans une variété de problèmes tels que les bandits contextuels linéaires mal spécifiés \citep{lattimore2019learning}, les bandits linéaires de dimension inconnue \citep{Foster-Krishnamurthy-Luo-2019} et l'apprentissage par renforcement avec des cartes de caractéristiques inconnues. Notre algorithme nécessite la connaissance du regret de base optimal pour ajuster le taux d'apprentissage maître. Nous montrons que sans cette connaissance préalable, tout maître peut subir un regret plus grand que le regret de base optimal.