Résumé technique : Expérimentation adaptative avec changement de récompense post-engagement

1. Formulation du problème

L'article traite d'un dilemme de prise de décision séquentielle auquel sont confrontés les décideurs dans des environnements d'apprentissage où les actions optimales à court terme peuvent entrer en conflit avec les bénéfices à long terme en raison d'un changement environnemental anticipé. Le problème est modélisé comme une expérience adaptative en deux phases avec $T$ périodes totales et $K$ traitements candidats (bras).

• Phase 1 : Phase d'expérimentation (tours $1$à$N$) : Le décideur peut sélectionner de manière adaptative différents bras pour observer des résultats aléatoires. La fonction de récompense pendant cette phase est $f(\cdot)$. Le budget $N$ est déterminé de manière exogène (par exemple, par une période de grâce réglementaire).
• Phase 2 : Phase d'engagement (tours $N+1$ à $T$) : Le décideur doit s'engager sur un bras unique (dans le modèle de base) et l'implémenter pour les $T-N$ tours restants. Crucialement, la fonction de récompense change pour devenir $g(\cdot)$, qui peut différer de $f(\cdot)$. Par conséquent, le bras optimal pour $f$ peut être sous-optimal pour $g$.

L'objectif est de maximiser la récompense cumulée attendue à travers les deux phases. La performance est mesurée par le Regret, défini comme la différence entre la récompense totale d'une stratégie clairvoyante optimale (qui connaît à l'avance les bras optimaux pour $f$ et $g$) et la récompense obtenue par l'algorithme d'apprentissage en ligne.

Le défi central est le compromis : allouer trop d'exploration au profit de $f$ à court terme risque de sélectionner un mauvais bras pour le $g$ à long terme, tandis que trop investir dans l'identification du bras optimal pour $g$ entraîne un regret excessif à court terme.

2. Méthodologie : L'algorithme RAEC

Les auteurs proposent l'algorithme Reserved Arm Eliminations for Commitment (RAEC). Contra irement aux algorithmes de bandits multi-bras (MAB) standards qui équilibrent de manière adaptative l'exploration et l'exploitation, RAEC emploie une stratégie d'allocation prédéterminée.

• Structure : L'algorithme opère dans la phase d'expérimentation ($N$ tours) via deux étapes, suivies d'une étape d'engagement.
  • Étape I (Exploration réservée) : Un nombre prédéterminé d'époques ($L$) sont réservées exclusivement à l'élimination des bras sous-optimaux par rapport à la fonction de récompense de la phase d'engagement $g$. L'algorithme utilise des tests d'hypothèse pour éliminer les bras qui performent mal sous $g$, garantissant que l'ensemble d'engagement final contient le meilleur bras de $g$ avec une probabilité élevée.
  • Étape II (Minimisation du regret) : Les tours restants de la phase d'expérimentation sont utilisés pour minimiser le regret par rapport à la fonction de récompense de la phase d'expérimentation $f$, en utilisant des techniques standard d'élimination de bras.
  • Étape d'engagement : Au tour $N+1$, l'algorithme s'engage uniformément de manière aléatoire sur l'un des bras survivants de l'ensemble de l'Étape I.
• Caractéristique de conception clé : L'algorithme ne cherche pas à apprendre de manière adaptative la structure de l'instance pour décider combien explorer pour $g$. Au contraire, il fixe l'allocation d'effort en fonction des paramètres $N$, $T$ et $K$. Cette approche de « réservation » simplifie la mise en œuvre et offre une transparence concernant l'effort consacré aux gains à long terme.

3. Contributions clés et résultats

A. Bornes supérieures de regret

L'article établit des bornes supérieures de regret serrées pour RAEC à travers tous les régimes de paramètres définis par la relation entre le budget d'expérimentation $N$, l'horizon d'engagement $T-N$, et le nombre de bras $K$. Les bornes de regret présentent une transition de phase :

1. Régime d'expérience courte ($N \lesssim K^{1/3}(T-N)^{2/3}$) : La phase d'expérimentation est trop courte pour équilibrer les deux objectifs. La stratégie optimale se concentre sur l'exploration pure pour $g$.
   • Regret : $\tilde{O}\left(\sqrt{\frac{KT^2}{N}}\right)$.
2. Régime équilibré ($N \gtrsim K^{1/3}(T-N)^{2/3}$ et $T-N \gtrsim K^{1/4}T^{3/4}$) : Les deux phases sont significatives. L'algorithme équilibre l'exploration pour $g$ et l'exploitation pour $f$.
   • Regret : $\tilde{O}\left(K^{1/3}(T-N)^{2/3}\right)$.
3. Régime d'engagement court ($T-N \lesssim K^{1/4}T^{3/4}$) : La phase d'engagement est courte, ressemblant à un problème MAB standard où le regret à court terme domine.
   • Regret : $\tilde{O}\left(\sqrt{KT}\right)$.

B. Bornes inférieures d'information théorique

Les auteurs prouvent des bornes inférieures minimax correspondantes pour toute politique cohérente. Cela confirme que RAEC atteint le taux de regret optimal (à un facteur logarithmique près) et que la stratégie d'allocation « prédéterminée » est suffisante ; des méthodes adaptatives plus sophistiquées qui apprennent la structure de l'instance n'améliorent pas l'ordre de grandeur du regret.

C. Extensions

L'article analyse deux extensions :

1. Connaissance structurelle des changements de récompense : Si le décideur connaît la relation fonctionnelle entre $f$ et $g$ (par exemple, une relation affine perturbée), l'article montre qu'identifier correctement la composante de changement de classement du décalage est bien plus critique que d'estimer l'amplitude absolue du décalage. Si le décalage préserve les classements, la performance du regret s'améliore considérablement.
2. Récompenses d'engagement concaves (Choix de portefeuille) : Dans les contextes où la récompense d'engagement est une fonction concave de l'issue agrégée du portefeuille (par exemple, équilibrer le profit et l'impact environnemental), les auteurs proposent l'algorithme Reserved Online Stochastic Convex Optimization for Commitment (ROSCOC). Au lieu d'éliminer des bras, ROSCOC utilise l'optimisation convexe stochastique en ligne pendant la phase réservée et s'engage sur la distribution empirique du chemin d'exécution. Il atteint des bornes de regret comparables à l'algorithme de base RAEC.

4. Expériences numériques

Les auteurs mènent des expériences numériques pour valider leurs découvertes théoriques :

• Vérification de la mise à l'échelle : Les expériences confirment que le regret empirique de RAEC évolue avec $T$ selon les pentes théoriques prédites (par exemple, $T^{3/4}$, $T^{2/3}$, $T^{1/2}$) à travers différents calendriers d'engagement.
• Comparaison avec les bases de référence : RAEC est comparé à une base de type UCB qui optimise la récompense à court terme $f$ et ne sélectionne que le meilleur bras de $g$ à la fin. Dans les régimes équilibrés, RAEC surpasse la base de référence UCB sur le long terme. La base de référence UCB échoue à allouer suffisamment d'échantillons pour distinguer les bras qui sont sous-optimaux pour $f$ mais optimaux pour $g$, ceant des erreurs d'engagement coûteuses.
• Extension concave : Des résultats similaires sont observés pour ROSCOC par rapport à une base de référence UCB-Portfolio, démontant que réserver l'exploration pour l'objectif à long terme produit une performance supérieure sur le long horizon, même dans des contextes non linéaires.

5. Signification et revendications

L'article affirme fournir une caractérisation précise du coût de l'équilibre entre la performance à court terme et l'engagement à long terme en présence de changements de récompense.

• Compromis fondamental : Le travail souligne que la présence d'un changement de récompense post-engagement modifie fondamentalement la difficulté du problème par rapport aux MAB standards, entraînant souvent des taux de regret plus élevés (par exemple, $T^{2/3}$ contre $T^{1/2}$) dans les régimes équilibrés.
• Suffisance des stratégies simples : Une implication centrale est que l'allocation d'effort prédéterminée est suffisante pour atteindre l'optimalité minimax. Les décideurs n'ont pas besoin de mécanismes adaptatifs complexes pour apprendre la structure de l'instance afin de déterminer combien explorer pour le futur ; une simple réservation calculée de ressources est optimale.
• Aperçu managérial : Les résultats offrent des orientations quantitatives pour les praticiens (par exemple, dans la réglementation des plateformes ou la gestion de la chaîne d'approvisionnement) sur la quantité de capacité à réserver pour l'expérimentation par rapport aux opérations immédiates lorsqu'on anticipe des changements de politique ou d'environnement. Plus précisément, cela clarifie que l'identification du classement des options sous le nouvel environnement est plus critique que l'amplitude précise du décalage de la récompense.

L'article conclut que bien que le problème soit plus difficile que les problèmes de bandits standards en raison du changement de récompense, les algorithmes proposés (RAEC et ROSCOC) gèrent efficacement ce compromis avec des garanties prouvables.