Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Formulation du Problème
Cet article étudie les bandits logistiques stochastiques sous l'objectif de regret simple. Dans ce cadre, un apprenant interagit avec un environnement sur $T$ tours, en sélectionnant des actions $A_t$ à partir d'un ensemble $\mathcal{A}$ et en observant des récompenses de Bernoulli $X_t$ de moyenne $\mu(\phi(A_t)^\top \theta^*)$, où $\mu$ est la fonction sigmoïde, $\phi$ est une application de caractéristiques connue, et $\theta^*$ est un paramètre inconnu dans $\mathbb{R}^d$. Contrairement au regret cumulatif, où l'objectif est de maximiser la somme des récompenses durant l'exploration, l'objectif de regret simple évalue l'apprenant uniquement sur la qualité d'une unique recommandation finale $\hat{a}$ après $T$ tours. Le regret est défini comme la différence entre la récompense espérée de l'action optimale et la récompense espérée de l'action recommandée.

Un défi critique dans les bandits logistiques est l'informativité non uniforme des actions. En raison du lien sigmoïde, les actions dans des régions « saturées » (où la récompense moyenne est proche de 0 ou 1) produisent des récompenses presque déterministes mais fournissent peu d'informations sur le paramètre $\theta^*$. À l'inverse, les actions proches de l'origine (où la sigmoïde est la plus raide) sont hautement informatives mais peuvent produire des récompenses immédiates plus faibles. Cela crée une géométrie où les actions les meilleures pour la récompense immédiate (exploitation) diffèrent de celles les meilleures pour identifier l'action optimale (exploration).

Méthodologie
Les auteurs proposent deux algorithmes conscients de la courbure, conçus pour exploiter la géométrie locale de la fonction sigmoïde :

1. MULOG (Max-Uncertainty-Log) : Un algorithme d'exploration pure déterministe.

   • Mécanisme : MULOG maintient un ensemble de confiance $W_t$ pour $\theta^*$ et construit une matrice de conception pondérée par la courbure $L_t$. Le score d'incertitude pour une action $a$ et un paramètre $\theta$ est défini comme $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, où $\dot{\mu}$ est la dérivée de la sigmoïde (représentant la courbure locale).
   • Sélection : À chaque tour, l'algorithme sélectionne la paire action-paramètre $(A_t, \theta_t)$ qui maximise ce score d'incertitude.
   • Terminaison : Après $T$ tours, il renvoie l'action gourmande par rapport à un vecteur de paramètres échantillonné depuis l'ensemble de confiance final.
   • Optimisation : Pour des ensembles d'actions finis, l'étape de sélection se réduit à résoudre une collection finie de problèmes d'optimisation convexe.

2. THATS (Try Hard Thompson Sampling) : Une alternative randomisée, moins coûteuse en calcul.

   • Mécanisme : Au lieu de résoudre pour l'incertitude maximale exacte, THATS échantillonne une direction $\tilde{\theta}_t$ depuis une distribution gaussienne centrée en zéro avec une covariance $L_t^{-1}$.
   • Sélection : Il sélectionne l'action maximisant le score d'incertitude randomisé $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$, où $\bar{\theta}_t$ est une estimation du maximum de vraisemblance contrainte.
   • Compromis : Cette approche évite l'optimisation convexe requise par MULOG mais engendre un coût statistique, résultant en une borne de regret légèrement plus lâche.

Contributions Clés

• Borne Inférieure Minimax : L'article établit une borne inférieure minimax du premier ordre de l'ordre $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, où $\kappa^*$ est l'inverse de la pente de la sigmoïde à l'action optimale (c'est-à-dire $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Mécanisme de Difficulté Distinct : Contrairement aux bornes inférieures de regret cumulatif (par exemple, Abeille et al., 2021) qui reposent sur le coût de l'information (forçant l'apprenant à jouer des bras quasi-optimaux), cette borne inférieure est dérivée d'une construction d'« hypercube saturé décalé ». Dans cette construction, l'information statistique et la sensibilité de la valeur sont toutes deux contrôlées par la même courbure locale dans une région saturée. Cela révèle que même avec la liberté d'échantillonner purement pour l'information, le problème reste difficile si l'action optimale se situe dans une région plate de la sigmoïde.
• Algorithmes Optimaux :
  • MULOG atteint une borne supérieure de regret simple de $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, correspondant à la borne inférieure à des facteurs logarithmiques près. C'est la première garantie d'exploration pure directe pour les bandits logistiques atteignant l'optimalité minimax instance par instance.
  • THATS atteint une borne de $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. Le facteur supplémentaire $\sqrt{d}$ provient de l'utilisation d'une approximation randomisée agnostique à la géométrie de la direction d'incertitude maximale.
• Insight Géométrique : Les auteurs démontrent que la géométrie du pire cas (instances saturées décalées) n'est pas le seul cas. Ils montrent que des « actions informatives à faible récompense » (sondes) peuvent exister dans l'ensemble d'actions. Ces actions se situent dans la région de haute courbure de la sigmoïde, fournissant des informations significatives sur la direction optimale malgré leurs faibles récompenses espérées.

Résultats

• Théoriques : Les bornes dérivées confirment que la difficulté du regret simple logistique est régie par la courbure à l'action optimale. Les algorithmes contrôlent avec succès l'incertitude dans les directions de caractéristiques pondérées par la courbure.
• Empiriques : Les expériences sur des géométries « difficiles » (hyper cubes saturés décalés) et « faciles » (avec des bras sondes informatifs ajoutés) soutiennent les résultats théoriques :
  • Sur des instances difficiles, MULOG et THATS se comportent comme prédit par les bornes minimax.
  • Sur des instances faciles avec des bras sondes, les méthodes d'exploration pure (MULOG et THATS) surpassent nettement les bases de regret cumulatif (comme Thompson Sampling cumulatif et les conversions online-to-batch). Les méthodes d'exploration pure échantillonnent activement les sondes à faible récompense et haute information, réduisant drastiquement le nombre de tours nécessaires pour atteindre un seuil bas de regret simple.
  • Les méthodes de regret cumulatif échouent à exploiter efficacement ces sondes car leur conversion online-to-batch pénalise l'inclusion d'actions à faible récompense dans la distribution de recommandation finale.

Signification
L'article affirme que l'exploration pure dans les bandits logistiques possède une géométrie distincte des problèmes de regret cumulatif. La contribution principale est d'identifier que la courbure locale à l'action optimale ($\kappa^*$) est le facteur gouvernant le taux minimax du premier ordre. En développant des algorithmes qui tiennent explicitement compte de cette courbure, les auteurs atteignent une performance minimax-optimale dans le pire des cas. De plus, le travail met en lumière une implication pratique : dans des contextes comme les tests A/B ou la collecte de données pour les modèles de récompense, chercher activement des actions « informatives mais à faible récompense » peut accélérer considérablement l'identification de la meilleure politique finale, un comportement que les algorithmes de regret cumulatif standards sont structurellement incapables d'exhiber. Les résultats servent de point de départ pour une théorie plus précise de l'exploration axée sur la décision dans les bandits non linéaires.