Multiscale Reward Hedging from Correct Demonstrations

Résumé Technique : Couverture de Récompense Multi-échelle à partir de Démonstrations Correctes

Formulation du Problème
L'article traite du problème de l'apprentissage à partir de démonstrations correctes dans des contextes où plusieurs actions peuvent être optimales. Contrairement à l'apprentissage supervisé standard, l'apprenant observe une unique démonstration valide $a^*_t$ pour un contexte $x_t$, mais ne reçoit aucun retour indiquant si sa propre prédiction $\hat{a}_t$ était correcte, ni n'observe la fonction de récompense sous-jacente ou l'ampleur de sa perte. L'objectif est de minimiser l'écart cumulé « caché » (la différence entre la récompense de l'action optimale et celle de l'apprenant) par rapport à une fonction de récompense inconnue $r^*$.

Ce cadre généralise les travaux précédents sur les classes de récompenses finies (Joshi et al., 2026) à des classes de récompenses continues, une lacune jusqu'alors non traitée pour les classes continues générales. Le modèle de rétroaction est distinct de l'optimisation inverse en ligne ou des bandits contextuels standards car l'apprenant n'observe jamais une valeur de récompense ou un bit de correction ; il observe seulement une action valide parmi un ensemble d'actions optimales inconnues.

Méthodologie : Couverture de Récompense Multi-échelle (Multiscale Reward Hedging)
La contribution centrale est un algorithme déterministe de couverture de récompense multi-échelle qui opère sans connaître l'horizon temporel. La méthodologie repose sur les composantes suivantes :

1. Métrique d'Écart et Proxys : L'algorithme se concentre sur la fonction d'écart d'optimalité $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$. Au lieu d'estimer directement la fonction de récompense, l'apprenant maintient un vote pondéré sur un ensemble de « proxys binaires tolérants ».
2. Couverture Multi-échelle : Pour une séquence d'échelles de précision $\epsilon_j = 2^{-j-1}$, l'algorithme construit des recouvrements appropriés $\epsilon_j$ ($C_j$) de la classe de fonctions d'écart $G$. Chaque élément $h \in C_j$ définit un proxy $q_{j,h}$ qui étiquette une action comme « bonne » si $h(x, a) \le \epsilon_j$.
3. Vote Partagé : Plutôt que d'exécuter des apprenants séparés pour chaque échelle (ce qui produirait des actions incompatibles), l'algorithme agrège tous les proxys à travers toutes les échelles en un vote pondéré unique. Le poids initial d'un proxy à l'échelle $j$ est proportionnel à $2^{-j}$.
4. Règle de Mise à Jour : La mise à jour est « insensible aux erreurs » (mistake unaware). Lors de l'observation d'une démonstration $a^*_t$, l'algorithme met à jour les poids en se basant uniquement sur la comparaison entre le jugement du proxy et la prédiction de l'apprenant :
   • Si le proxy considère la démonstration comme bonne mais l'action de l'apprenant comme mauvaise, le poids du proxy double.
   • Si le proxy considère la démonstration comme mauvaise, son poids est remis à zéro.
   • Sinon, le poids reste inchangé.
     Cette règle garantit que si l'action de l'apprenant présente un écart important par rapport à une échelle spécifique, le poids du proxy représentant cette échelle augmente, effectuant ainsi une « couverture » (hedging) contre cette échelle d'erreur.

Résultats Théoriques Clés

• Bornes de Queue Indépendantes de l'Horizon : L'algorithme fournit une borne de queue simultanée pour le nombre de tours où la perte dépasse un seuil $2^{-j}$ :
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  où $N(G, \epsilon)$ est le nombre de recouvrement de la classe de l'écart. L'intégration de ces queues produit une borne de l'écart caché cumulé indépendante de l'horizon temporel $T$ :
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  Cette somme est bornée par une intégrale d'entropie métrique, $H_{dyad}(G)$.

• Entropie Polynomiale et Taux de Regret :

  • Pour les classes avec des nombres de recouvrement polynomiaux $N(G, \epsilon) \le (A/\epsilon)^d$, le gap total est borné par $O(d \log A)$.
  • Cela se traduit par un taux statistique de $O(d/m)$ dans le cadre de l'apprentissage en ligne vers le lot (online-to-batch).
  • Recommandation Contextuelle Linéaire : Pour les récompenses linéaires bornées avec un rayon de paramètre $B$ et un diamètre de menu $K$, le regret est de $O(d)$ pour des menus compacts arbitraires. C'est la première borne finie polynomiale pour des menus arbitraires sans restrictions structurelles (ex: M-convexité), obtenue via un prédicteur impropre.
  • Récompenses de Bas Rang et Réseaux de Neurones : Le cadre s'étend aux récompenses bilinéaires de bas rang ($O(BKr(m+n))$) et aux réseaux ReLU bornés avec des bornes explicites dépendant de la profondeur et des paramètres du réseau.

• Complexité Computationnelle :

  • L'algorithme général est informationnel et peut être coûteux en termes de calcul en raison de l'énumération des recouvrements.
  • Cependant, pour les courbes de paramètres Lipschitz unidimensionnelles (ex: recommandation de rang deux à rayon fixe), l'algorithme est exact et s'exécute en temps polynomial. Plus précisément, pour la recommandation de rang deux à rayon fixe avec une taille de menu $k$ et un coût d'évaluation de la récompense $C$, la complexité temporelle est de $O(kCT^2)$.

• Bornes Inférieures et Robustesse :

  • L'article prouve une borne inférieure $\Omega(d)$ correspondante pour les classes continues avec un exposant d'entropie $d$, confirmant l'étroitesse de la dépendance $O(d)$.
  • Une variante robuste gère les démonstrations sous-optimales, n'ajoutant à la borne de regret que la sous-optimalité cumulée $\Delta_T$ du démonstrateur.

Signification et Revendications
L'article affirme résoudre la question de l'apprentissage à partir de démonstrations correctes pour les classes de récompenses continues. Sa principale importance réside dans :

1. Premier Garant de l'Indépendance de l'Horizon pour les Classes Continues : Il fournit les premiers taux de regret pour les classes continues qui ne dépendent pas de l'horizon temporel $T$, en s'appuyant plutôt sur l'entropie métrique.
2. Prédiction Impropre pour des Menus Arbitraires : Il atteint un regret de $O(d)$ pour la recommandation contextuelle linéaire avec des menus compacts arbitraires, un cadre où les algorithmes propres précédents nécessitaient des restrictions structurelles (comme la M-convexité) ou souffraient de dépendances de dimension plus élevées.
3. Efficacité dans des Géométries Spécifiques : Bien que le vote général soit coûteux, l'article isole un cas non trivial (courbes Lipschitz 1D) où l'algorithme exact est polynomial, comblant le fossé entre les bornes informationnelles et la faisabilité computationnelle.
4. Validation Empirique : Un test de stress reproductible sur les données de MovieLens démontre que l'algorithme s'adapte aux échelles et améliore l'écart latent moyen par rapport aux politiques de notation démontrées et aux bases en ligne propres, en utilisant uniquement des démonstrations d'actions sans observer les récompenses.

L'auteur souligne que bien que la solution générale soit impropre (le vote peut ne pas correspondre à un paramètre de récompense valide unique), elle minimise avec succès l'écart de récompense cible, ce qui la distingue des méthodes d'optimisation inverse en ligne propres qui visent à estimer le paramètre de récompense lui-même.