Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Énoncé du problème
L'article traite du problème des bandits linéaires gaussiens, un cadre de prise de décision séquentielle où un joueur choisit des actions $A_t \in \mathcal{A} \subset \mathbb{R}^d$ pour maximiser les récompenses cumulées. La récompense à l'instant $t$ est générée par $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, où $\theta_\star$ est un vecteur de paramètres inconnus et $W_{t+1}$ est un bruit gaussien i.i.d. de variance $\sigma^2$. L'objectif est de minimiser le regret bayésien, défini comme la différence attendue entre la récompense de l'action optimale et celle de l'action choisie sur un horizon $T$, en supposant une distribution a priori $\rho$ sur $\theta_\star$. Plus précisément, les auteurs se concentrent sur le cas où $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ et où l'ensemble des actions est une boule $\ell_2$ mise à l'échelle de rayon $r$.

Méthodologie
Les auteurs analysent l'échantillonnage de Thompson (Thompson sampling), un algorithme d'échantillonnage de la distribution a posteriori qui tire une estimation du paramètre $\hat{\theta}_t$ à partir de la distribution a posteriori donnée par l'historique $H_t$ et sélectionne l'action maximisant la récompense attendue sous $\hat{\theta}_t$.

Pour dériver les bornes de regret, les auteurs utilisent une décomposition du regret instantané en deux termes :

1. Terme (I) : Le regret encouru lorsque le paramètre échantillonné $\hat{\theta}_t$ est proche du véritable paramètre $\theta_\star$ (au sein d'un événement de haute probabilité défini par la matrice de précision a posteriori).
2. Terme (II) : Le regret encouru lorsque le paramètre échantillonné est éloigné du véritable paramètre.

L'innovation technique centrale réside dans l'analyse du Terme (I). Les auteurs introduisent un lemme de potentiel elliptique généralisé (Lemme 3). Contrairement aux lemmes de potentiel elliptique standards utilisés dans la littérature des bandits linéaires (par exemple, Abeille & Lazaric, 2017 ; Dani et al., 2008), qui exigent généralement que la matrice de précision initiale soit bornée loin de zéro (par exemple, $V_0 \succeq I$) et bornent les erreurs quadratiques, ce nouveau lemme :

• Permet à la matrice de précision initiale $V_0$ d'être arbitrairement petite (ou même nulle dans la limite), accommodant ainsi les a priori diffus.
• Introduit un exposant flexible $p \in [0, 1]$ dans la sommation des normes.
• Sépare explicitement la borne en un terme de logarithme du déterminant (capturant le gain d'information à long terme) et un terme de trace impliquant la précision initiale (capturant le coût de « chauffe » ou burn-in initial).

L'analyse du Terme (II) repose sur des inégalités de concentration standards pour les distributions gaussiennes afin de borner la probabilité des écarts importants entre $\hat{\theta}_t$ et $\theta_\star$.

Contributions clés et résultats
La contribution principale est une nouvelle borne de regret bayésien pour l'échantillonnage de Thompson dans le cadre linéaire-gaussien qui découple le terme de « chauffe » dépendant de l'a priori du taux de regret minimax.

1. Borne de regret améliorée : Les auteurs prouvent que l'échantillonnage de Thompson atteint un regret de :
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Ici, $\sigma d \sqrt{T}$ représente le taux minimax asymptotique, tandis que $d r \sqrt{\text{Tr}(\Sigma_0)}$ représente le coût initial de réduction de l'incertitude de l'échelle de l'a priori vers l'échelle du bruit.

2. Découplage des termes : Les bornes précédentes (par exemple, Kalkanli & Özgür, 2020) présentaient une dépendance multiplicative, telle que $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, où la diffusivité de l'a priori $\sqrt{\text{Tr}(\Sigma_0)}$ mettait à l'échelle l'ensemble du taux minimax. Le nouveau résultat montre que, à des facteurs logarithmiques près, la diffusivité de l'a priori n'ajoute qu'une constante additive au regret, indépendamment de l'horizon temporel $T$.

3. Bornes inférieures : L'article établit une borne inférieure pour toute politique dans ce cadre, démontrant que le terme de chauffe $d r \sqrt{\text{Tr}(\Sigma_0)}$ est inévitable pour les a priori gaussiens. Cela confirme que la structure additive de la borne supérieure est serrée (à des facteurs logarithmiques près) et que la diffusivité de l'a priori ne peut pas être entièrement éliminée du regret.

4. Généralisation : Les auteurs notent que leurs résultats peuvent être étendus aux a priori fortement log-concaves et aux distributions de bruit, sans se limiter strictement au cas gaussien.

Signification
L'article affirme que ses résultats résolvent un relâchement dans les bornes de regret existantes pour l'échantillonnage de Thompson. En prouvant que le terme dépendant de l'a priori est additif plutôt que multiplicatif, ce travail clarifie le rôle de la diffusivité de l'a priori : elle agit comme un coût de « chauffe » unique requis pour réduire l'incertitude au niveau du bruit d'observation, après quoi la performance de l'algorithme est uniquement gouvernée par la variance du bruit $\sigma$ et la dimension $d$. Cela fournit une caractérisation plus précise de l'efficacité de l'algorithme, particulièrement dans les régimes où l'a priori est hautement diffus (grand $\text{Tr}(\Sigma_0)$), montant qu'une telle diffusité ne dégrade pas de façon permanente le taux de convergence asymptotique. L'introduction du lemme de potentiel elliptique généralisé est présentée comme un outil permettant une analyse plus flexible des problèmes d'optimisation stochastique où l'incertitude initiale peut être non bornée.