Échantillonnage de Thompson à prix réduit pour des problèmes de bandit non stationnaires

Les problèmes de bandit multi-bras non stationnaires (NS-MAB) ont récemment reçu une attention significative. Les NS-MAB sont typiquement modélisés dans deux scénarios : les changements brusques, où les distributions de récompense restent constantes pendant une certaine période et changent à des moments inconnus, et les changements progressifs, où les distributions de récompense évoluent de manière fluide selon des dynamiques inconnues. Dans cet article, nous proposons l'échantillonnage de Thompson à prix réduit (DS-TS) avec des priors gaussiens pour aborder les deux configurations non stationnaires. Notre algorithme s'adapte passivement aux changements en incorporant un facteur de réduction dans l'échantillonnage de Thompson. La méthode DS-TS a été validée expérimentalement, mais une analyse de la borne supérieure du regret fait actuellement défaut. Sous des hypothèses modérées, nous montrons que DS-TS avec des priors gaussiens peut atteindre une borne de regret quasi optimale à l'ordre de O (TBT) pour les changements brusques et O (T^β) pour les changements progressifs, où T est le nombre de phases temporelles, BT est le nombre de points de rupture, β est associé à l'environnement à changement progressif et O cache les paramètres indépendants de T ainsi que les termes logarithmiques. De plus, des comparaisons empiriques entre DS-TS et d'autres algorithmes de bandit non stationnaires démontrent ses performances compétitives. En particulier, lorsque des connaissances antérieures sur la récompense maximum attendue sont disponibles, DS-TS a le potentiel de surpasser les algorithmes à la pointe de la technologie.