A Short Note on a Variant of the Squint Algorithm

Cette note présente une variante simple de l'algorithme Squint et démontre, par une modification analogue de la preuve originale, qu'elle garantit une borne de regret similaire à celle obtenue récemment par Freund et al. pour une variante de l'algorithme NormalHedge.

L'essentiel

🎯 Le Problème : Choisir le bon conseiller

Imaginez que vous êtes un chef d'orchestre (le "learner") face à un public très exigeant (l'"adversaire"). Vous avez à votre disposition N conseillers (les "experts"). Chaque jour, vous devez décider de la part de musique que chaque conseiller va diriger.

• Le jeu : Chaque jour, vous répartissez votre attention entre les conseillers. Ensuite, le public vous donne une note de performance (une "perte").
• Le but : Votre objectif est de faire aussi bien que le meilleur conseiller, ou presque. Mais comme il y a beaucoup de conseillers, vous ne voulez pas seulement battre le meilleur absolu (qui est souvent un miracle), vous voulez battre les top 10 %, ou les top 1 %, selon votre humeur. C'est ce qu'on appelle le "regret quantile".

🧠 L'Algorithme Original : "Squint" (Le Coup d'œil)

En 2015, deux chercheurs (Koolen et Van Erven) ont créé un algorithme génial appelé Squint (qui signifie "squint" ou "regarder en plissant les yeux").

Comment ça marche ?
Imaginez que chaque conseiller a un carnet de notes avec deux colonnes :

1. Sa performance globale (R) : Combien il a bien ou mal fait jusqu'ici.
2. Sa volatilité (V) : À quel point ses performances ont été irrégulières (des hauts et des bas).

L'algorithme original est très prudent. Il dit : "Je vais faire confiance à ce conseiller, mais seulement si je connais exactement sa propre histoire de hauts et de bas."
Il calcule sa confiance en regardant le carnet individuel de chaque conseiller. Si le conseiller A a eu des hauts et des bas, on ajuste sa confiance en fonction de ses hauts et ses bas.

Le problème : C'est un peu comme si chaque conseiller avait sa propre météo personnelle. C'est précis, mais ça peut être compliqué à gérer si vous voulez une vue d'ensemble simple.

🚀 La Nouvelle Variante : "Squint" Simplifié

Dans cette nouvelle note (écrite par Haipeng Luo en 2026), l'auteur propose une petite modification, une "variante", qui change la façon dont on regarde la météo.

L'idée de la métaphore :
Au lieu de regarder la météo individuelle de chaque conseiller, imaginez que vous avez un thermomètre central pour tout le groupe.

• L'ancien Squint : Regarde la température de la chambre de chaque conseiller individuellement.
• La nouvelle variante : Regarde la température moyenne de tout le bâtiment, mais l'ajuste dynamiquement en fonction de ce qui se passe maintenant.

En termes techniques (simplifiés) :
Dans l'ancien algorithme, la "volatilité" (V) était calculée séparément pour chaque expert. Dans la nouvelle version, on utilise une volatilité globale (V) qui est mise à jour collectivement à chaque tour, basée sur la moyenne des erreurs de tout le groupe.

C'est comme si, au lieu de dire "Je fais confiance à Paul parce qu'il a été stable cette semaine", on disait "Je fais confiance à Paul parce que, globalement, l'équipe a été stable aujourd'hui, et Paul fait partie de cette stabilité."

🏆 Pourquoi c'est génial ?

1. La même garantie, mais plus simple : L'auteur prouve mathématiquement que cette version simplifiée fonctionne aussi bien que l'originale. Elle garantit que vous ne ferez pas beaucoup plus d'erreurs que les meilleurs conseillers, même si vous ne savez pas à l'avance qui sera le meilleur.
2. Un lien avec d'autres travaux : Cette nouvelle formule ressemble étrangement à une autre méthode célèbre (NormalHedge) utilisée par d'autres chercheurs. C'est comme si deux chemins différents dans une forêt menaient au même magnifique point de vue. Cela suggère qu'il y a une "vérité fondamentale" derrière ces algorithmes que nous commençons juste à comprendre.
3. La flexibilité : Comme l'ancien algorithme, on peut adapter cette nouvelle version pour prendre en compte des préjugés initiaux (par exemple, si vous pensez que certains conseillers sont plus fiables dès le départ).

💡 En résumé

Imaginez que vous devez choisir un itinéraire pour un voyage.

• L'algorithme original vous dit : "Regarde l'historique de chaque route individuellement. Si la route A a eu des nids de poule hier, ne la prends pas, peu importe le trafic global."
• La nouvelle variante dit : "Regarde l'état général de la circulation sur tout le réseau aujourd'hui. Si le réseau est fluide, on peut prendre la route A, même si elle a eu un petit problème hier, car le système global est stable."

Cette petite modification rend l'algorithme plus élégant et le relie à d'autres grandes idées en intelligence artificielle, prouvant que parfois, moins de détails individuels et plus de vision globale peuvent mener à la même (voire meilleure) performance.

Résumé technique

1. Problème : Le Problème de l'Expert

Le document s'inscrit dans le cadre classique du problème de l'expert en apprentissage en ligne.

• Contexte : Un apprenant interagit avec un adversaire sur $T$ rounds.
• Mécanisme : À chaque round $t$, l'apprenant choisit une distribution de probabilité $p_t$ sur $N$ experts. L'adversaire révèle ensuite un vecteur de pertes $\ell_t \in [0, 1]^N$. L'apprenant subit une perte pondérée $\langle p_t, \ell_t \rangle$.
• Objectif : Minimiser le regret quantile ($\text{Reg}_\epsilon$). Pour un $\epsilon \in [1/N, 1)$, ce regret compare la perte cumulative de l'apprenant à celle du $\lfloor \epsilon N \rfloor$-ième meilleur expert (celui ayant la $i_\epsilon$-ième plus faible perte cumulative).
  • Lorsque $\epsilon = 1/N$, on retrouve le regret externe standard (comparaison au meilleur expert unique).

2. Méthodologie et Algorithme Proposé

L'auteur propose une variante simple de l'algorithme Squint original (Koolen et Van Erven, 2015), en modifiant la manière dont la variance cumulée est estimée et utilisée.

A. L'Algorithme Squint Original

L'algorithme original met à jour la distribution $p_t$ proportionnelle à la dérivée partielle du potentiel $\Phi$ par rapport à la regret instantané $R$ :
$$p_{t,i} \propto \frac{\partial \Phi}{\partial R}(R_{t-1,i}, V_{t-1,i})$$
Où $V_{t,i}$ est la variance cumulée spécifique à l'expert $i$ ($V_{t,i} = \sum r_{s,i}^2$).

B. La Variante de Squint (Squint Variant)

La contribution principale de cette note est une modification de la mise à jour de la variance. Au lieu d'utiliser une variance par expert, l'algorithme utilise une variance globale partagée $V_t$ mise à jour dynamiquement.

• Prédiction : $p_{t,i} \propto \frac{\partial \Phi}{\partial R}(R_{t-1,i}, V_{t-1})$.
• Mise à jour de la variance : La valeur $v_t$ (ajoutée à $V_t$) est définie implicitement via une distribution auxiliaire $q_t$.
  • $q_{t,i} \propto -\frac{\partial \Phi}{\partial V}(R_{t,i}, V_t) = \frac{\partial^2 \Phi}{\partial R^2}(R_{t,i}, V_t)$.
  • $v_t$ est la solution de l'équation $f(v) = \sum_i \frac{\partial^2 \Phi}{\partial R^2}(R_{t,i}, V_{t-1} + v) (v - r_{t,i}^2) = 0$.
  • Bien que récursive, cette équation peut être résolue efficacement par une recherche linéaire (ou recherche binaire) car la fonction $f$ est continue, avec $f(0) \le 0$ et $f(1) \ge 0$.

C. Potentiel et Preuve

L'analyse repose sur le potentiel de Squint :
$$\Phi(R, V) = \int_0^{1/2} \frac{e^{\eta R - \eta^2 V} - 1}{\eta} d\eta$$
L'auteur démontre (Lemme 3) que la somme des potentiels sur tous les experts ne croît jamais, grâce à une modification simple de la preuve originale de Koolen et Van Erven. Cette propriété clé permet de borner le regret.

3. Résultats Principaux

Le théorème principal (Théorème 4) établit une borne de regret quantile pour la variante proposée. Pour tout $\epsilon$, le regret satisfait :

$$\text{Reg}_\epsilon \le \sqrt{2V_T} \left( 1 + \sqrt{2 \ln \left( \frac{1}{2} + \frac{\ln(T+1)}{\epsilon} \right)} \right) + 5 \ln \left( 1 + \frac{1 + 2 \ln(T+1)}{\epsilon} \right)$$

Points clés de la comparaison :

• Différence majeure : Par rapport à l'algorithme Squint original, le terme $V_{T, i_\epsilon}$ (variance de l'expert spécifique) est remplacé par $V_T$ (la variance globale partagée).
• Comparabilité : Les deux bornes sont généralement incomparables (l'une peut être meilleure que l'autre selon la distribution des pertes), mais la variante proposée offre une structure de borne plus uniforme.

4. Signification et Contributions

1. Simplicité de la preuve : L'auteur montre qu'une modification mineure de l'algorithme (changement de la définition de la variance) permet de conserver la structure de preuve élégante de l'algorithme original, tout en changeant la nature de la borne de regret.
2. Lien avec d'autres travaux : La borne obtenue ressemble fortement à celle d'un travail récent de Freund et al. [2026] concernant une variante de l'algorithme NormalHedge (Chaudhuri et al., 2009). Cela suggère une convergence théorique entre différentes approches d'algorithmes de type "Hedge" adaptatif, malgré des définitions de potentiels différentes.
3. Extensibilité : La note mentionne que, comme pour l'algorithme original, il est possible d'intégrer une distribution a priori $q$ pour convertir la borne quantile adaptative en une borne de regret contre n'importe quelle distribution $u$, en remplaçant le terme $\ln(1/\epsilon)$ par la divergence de Kullback-Leibler $\text{KL}(u, q)$.

Conclusion

Cette note technique démontre qu'en modifiant subtilement la gestion de la variance dans l'algorithme Squint (passant d'une variance par expert à une variance globale optimisée), on obtient un algorithme dont les garanties de performance sont structurellement similaires à celles d'autres algorithmes avancés récents, tout en conservant la simplicité analytique de l'approche originale.