2025-11-11T09:55:09.434704

UCB-type Algorithm for Budget-Constrained Expert Learning

Latypov, Suvorikova, Kroshnin et al.
In many modern applications, a system must dynamically choose between several adaptive learning algorithms that are trained online. Examples include model selection in streaming environments, switching between trading strategies in finance, and orchestrating multiple contextual bandit or reinforcement learning agents. At each round, a learner must select one predictor among $K$ adaptive experts to make a prediction, while being able to update at most $M \le K$ of them under a fixed training budget. We address this problem in the \emph{stochastic setting} and introduce \algname{M-LCB}, a computationally efficient UCB-style meta-algorithm that provides \emph{anytime regret guarantees}. Its confidence intervals are built directly from realized losses, require no additional optimization, and seamlessly reflect the convergence properties of the underlying experts. If each expert achieves internal regret $\tilde O(T^α)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-α}\,T^α\Bigr)$. To our knowledge, this is the first result establishing regret guarantees when multiple adaptive experts are trained simultaneously under per-round budget constraints. We illustrate the framework with two representative cases: (i) parametric models trained online with stochastic losses, and (ii) experts that are themselves multi-armed bandit algorithms. These examples highlight how \algname{M-LCB} extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
academic

Algorithme de Type UCB pour l'Apprentissage d'Experts sous Contrainte Budgétaire

Informations Fondamentales

  • ID de l'article : 2510.22654
  • Titre : UCB-type Algorithm for Budget-Constrained Expert Learning
  • Auteurs : Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • Classification : cs.LG (Apprentissage Automatique), cs.MA (Systèmes Multi-Agents)
  • Date de Publication : 28 octobre 2025 (Préimpression)
  • Lien de l'article : https://arxiv.org/abs/2510.22654

Résumé

Dans de nombreuses applications modernes, les systèmes doivent effectuer une sélection dynamique entre plusieurs algorithmes d'apprentissage adaptatifs entraînés en ligne. Par exemple, la sélection de modèles dans les environnements de flux, la commutation de stratégies de trading en finance, ainsi que la coordination de plusieurs machines à bandits contextuels ou d'agents d'apprentissage par renforcement. À chaque tour, l'apprenant doit sélectionner un prédicteur parmi K experts adaptatifs pour effectuer une prédiction, tout en pouvant mettre à jour au maximum M ≤ K experts sous un budget d'entraînement fixe.

Cet article résout ce problème dans un cadre stochastique en proposant l'algorithme M-LCB — un méta-algorithme de type UCB efficace en calcul offrant des garanties de regret valides à tout moment. Ses intervalles de confiance sont construits directement à partir des pertes réalisées, sans optimisation supplémentaire, et reflètent de manière transparente les caractéristiques de convergence des experts sous-jacents. Si chaque expert atteint un regret interne Õ(T^α), alors M-LCB garantit une limite de regret global de Õ(√(KT/M) + (K/M)^(1-α)T^α).

Contexte et Motivation de la Recherche

Définition du Problème

De nombreuses applications pratiques nécessitent une sélection dynamique entre plusieurs experts auto-apprenant :

  1. Systèmes de Recommandation : Exécution parallèle de plusieurs prédicteurs, mise à jour selon les retours utilisateurs
  2. Plateformes Financières : Commutation entre stratégies de trading à mesure que les mécanismes de marché évoluent
  3. Services en Ligne à Grande Échelle : Gestion de pools de machines à bandits contextuels ou d'algorithmes d'apprentissage par renforcement

Défis Fondamentaux

Limitations des approches traditionnelles :

  • Machines à Bandits Multi-Bras Classiques (MAB) : Supposent des distributions de récompenses statiques ou adversariales, sans considérer la capacité d'apprentissage des bras
  • Algorithmes d'Experts : Nécessitent généralement une rétroaction complète, sans tenir compte des taux d'apprentissage des experts
  • Méthodes Existantes : Aucune n'a pleinement résolu le défi de gérer plusieurs experts apprenant simultanément sous des contraintes de budget d'entraînement par tour

Motivation de la Recherche

Cet article vise à combler cette lacune en proposant une procédure unifiant la prédiction et l'entraînement sélectif, en tenant compte des contraintes de budget de calcul fixes par tour.

Contributions Principales

  1. Nouveau Méta-Algorithme de Type UCB (M-LCB) : Propose un nouvel algorithme pour gérer un pool de K experts auto-apprenant, en tenant compte d'un budget d'apprentissage limité par tour M (M ≤ K)
  2. Efficacité Computationnelle : Fournit une méthode de construction d'intervalles de confiance directement à partir des pertes réalisées, efficace en calcul et évitant les optimisations auxiliaires coûteuses
  3. Analyse Théorique : Estime les performances du méta-algorithme en fonction des taux de convergence individuels des experts ; lorsque le regret des experts est Õ(n^α), le regret global est Õ(√(KT/M) + (K/M)^(1-α)T^α)
  4. Extension aux Machines à Bandits Multi-Jeux : Démontre que M-LCB s'étend au cadre des machines à bandits multi-jeux

Détails de la Méthode

Définition de la Tâche

  • Espace de Décision U : Espace des recommandations d'experts
  • Espace Environnemental E : Espace des résultats aléatoires
  • Fonction de Perte : ℓ : U×E → R₊
  • Spécification des Experts : Chaque expert k est défini par le tuple (Wₖ,Hₖ,Aₖ,gₖ,υₖ)
    • Wₖ : Espace d'état/paramètres
    • Hₖ : Espace d'historique
    • Aₖ : Algorithme d'apprentissage en ligne
    • gₖ : Fonction de mappage d'état vers recommandation
    • υₖ : Générateur de recommandation sûre

Protocole d'Exécution

Flux d'exécution à chaque tour t :

  1. Le méta-programme sélectionne un conseiller iₜ ∈ K et un sous-ensemble d'entraînement Sₜ ⊆ K, satisfaisant |Sₜ| ≤ M et iₜ ∈ Sₜ
  2. L'expert iₜ fournit une recommandation sûre uₜ = υᵢₜ(Hᵢₜᵗ) ∈ U
  3. L'environnement échantillonne ξᵗ ～ D, le programme subit une perte ℓ(uₜ,ξᵗ)
  4. L'expert k ∈ Sₜ met à jour son historique et son état interne

Cœur de l'Algorithme M-LCB

Définition des Intervalles de Confiance

Pour l'expert k, on définit :

  • Perte d'Exécution Normalisée : LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
  • Intervalle de Confiance Inférieur : LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
  • Intervalle de Confiance Supérieur : UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

Où :

  • δₐᵣₘ = δ/(2K), δₙ = δ/(7Kn²)
  • G(n,δ) = √(2log(1/δ)/n) + 2log(1/δ)/(3n)
  • H(n,δ) = √(2log(1/δ)/n)

Stratégie de Sélection

  • Sélection d'Ensemble d'Entraînement : Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
  • Sélection de Conseiller : iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

Points d'Innovation Technique

  1. Construction Directe d'Intervalles de Confiance : Construits directement à partir des pertes réalisées, sans optimisation supplémentaire
  2. Gestion Adaptative des Experts : Considère simultanément la sélection d'experts et l'allocation du budget d'entraînement
  3. Garanties Valides à Tout Moment : Fournit des limites de regret pour tous les pas de temps T
  4. Cadre Flexible : Supporte différents types d'algorithmes d'apprentissage comme experts

Configuration Expérimentale

Ensembles de Données

L'article a principalement mené des expériences synthétiques :

Sélection de Modèles Linéaires Généralisés

  • Nombre d'Experts : K=10 modèles linéaires généralisés
  • Dimension des Caractéristiques : Vecteurs de caractéristiques échantillonnés uniformément à partir de la sphère unitaire Sᵈ⁻¹
  • Configuration Difficile : Les fonctions f₇,f₈,f₉ sont hautement similaires dans les régions denses de données, augmentant la difficulté d'exploration

Métriques d'Évaluation

  1. Perte Cumulée : ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
  2. Distribution de Sélection de Bras : Fréquence finale de sélection de chaque expert
  3. Allocation du Budget de Calcul : Distribution du nombre d'entraînements reçus par chaque expert

Méthodes de Comparaison

  1. ED2RB : Algorithme avec garanties de bras apprenant
  2. LimitedAdvice : Algorithme d'experts capable de gérer les mises à jour multi-bras par tour

Détails d'Implémentation

  • Limite de Mise à Jour : M ∈ {1,2,3}
  • Nombre de Répétitions : 30 exécutions indépendantes en moyenne
  • Intervalles de Confiance : Affichage de ±0.5 écart-type
  • Ajustement d'Hyperparamètres : Paramètre d'exploration ED2RB c=0.1, mise à l'échelle du terme de concentration M-FLCB 0.3

Résultats Expérimentaux

Résultats Principaux

  1. Performance de Convergence : M-LCB réalise un regret sous-linéaire, compétitif avec les méthodes de base
  2. Identification d'Experts : Identifie avec succès l'expert optimal (k=9)
  3. Efficacité Budgétaire : Alloue principalement les mises à jour aux experts performants, tandis que LimitedAdvice les distribue plus uniformément

Résultats Théoriques

Théorème de Limite Supérieure

Théorème 2 : Soit α,δ ∈ (0,1), supposons que chaque expert k satisfait Uₖ(t,δ)=O(t^α c(δ)), alors avec une probabilité d'au moins 1-δ, le regret de l'Algorithme 1 est borné pour tout T ≥ 1 :

Reg(T) = O(√(KT/M)log(KT/δ) + (K/M)^(1-α)T^α c(δ))

Théorème de Limite Inférieure

Théorème 1 : Il existe des constantes c₁,c₂ > 0 telles que pour tout algorithme d'apprentissage et méta-programme :

sup EReg(T) ≥ c₁√(KT/M) + c₂T^α(K/M)^(1-α)

Ceci montre que M-LCB atteint l'optimalité à des facteurs logarithmiques près.

Travaux Connexes

Experts Auto-Apprenant (Bras)

  • 6 : Introduit les bras auto-apprenant dans le cadre MAB, où chaque bras est une fonction paramétrée, les paramètres étant mis à jour après sélection

Sélection de Modèles au Niveau Méta

  • CORRAL8 : Gère un pool d'algorithmes de bandits via une descente de miroir en ligne avec barrière logarithmique et rétroaction pondérée par importance
  • Équilibrage Dynamique9 : Méta-algorithme basé sur des expressions de taux de regret connus, mettant à jour un seul apprenant par tour
  • 10 : Estime en ligne les coefficients par apprenant, obtenant des garanties de données dépendantes à haute probabilité pour les bandits stochastiques

MAB avec Mises à Jour Multi-Bras

  • Conseil Limité12 : Interroge au maximum M bras, obtenant une limite de regret Õ(√(KT logK/M))
  • 13 : Regret minimax optimal Õ(max{√(KT/M), √(T logK)})

Conclusion et Discussion

Conclusions Principales

  1. Établit pour la première fois des garanties de regret pour plusieurs experts adaptatifs entraînés simultanément sous contrainte budgétaire par tour
  2. L'algorithme M-LCB atteint l'optimalité minimax à des facteurs logarithmiques près
  3. Le cadre unifie les paramètres d'optimisation en ligne et de bandits stochastiques

Limitations

  1. Mise à l'Échelle de Confiance Connue : L'analyse suppose que la fonction de mise à l'échelle de confiance c(δ) est connue
  2. Hypothèse de Perte Bornée : Se concentre principalement sur les cas de perte bornée
  3. Cadre Stochastique : L'analyse principale concerne les environnements stochastiques ; le cadre adversarial nécessite des recherches supplémentaires

Directions Futures

  1. Cas c(δ) Inconnu : Comme traité par Pacchiano et al.11
  2. Extension avec Observations Supplémentaires : Extension au conseil limité et aux machines à bandits multi-jeux
  3. Régime Contextuel : Extension aux cas où les experts se spécialisent en fonction des caractéristiques observées

Évaluation Approfondie

Points Forts

  1. Contribution Théorique Significative : Fournit pour la première fois des garanties théoriques pour l'apprentissage multi-experts sous contrainte budgétaire
  2. Conception d'Algorithme Élégante : Les intervalles de confiance sont construits directement à partir des pertes, efficaces en calcul
  3. Cadre Très Générique : Applicable à plusieurs types d'experts (modèles paramétrés, algorithmes de bandits, etc.)
  4. Analyse Théorique Rigoureuse : Fournit des limites supérieures et inférieures correspondantes, prouvant l'optimalité de l'algorithme

Insuffisances

  1. Validation Expérimentale Limitée : Principalement des expériences synthétiques, manque de validation sur des scénarios d'application réelle
  2. Conditions d'Hypothèse Fortes : Nécessite de connaître la forme de la limite de regret des experts
  3. Analyse des Facteurs Constants : Les facteurs constants dans les résultats théoriques peuvent être importants, les performances réelles nécessitent vérification

Impact

  1. Valeur Théorique Élevée : Fournit une base théorique pour l'apprentissage d'experts sous contrainte budgétaire
  2. Grand Potentiel Pratique : Applicable à plusieurs domaines tels que les systèmes de recommandation et le trading financier
  3. Forte Extensibilité : Le cadre peut s'étendre à des scénarios d'apprentissage plus complexes

Scénarios d'Application

  1. Sélection de Modèles En Ligne : Sélection dynamique de modèles dans les environnements de flux de données
  2. Systèmes Multi-Stratégies : Scénarios nécessitant une commutation de stratégie comme le trading financier et la publicité programmatique
  3. Apprentissage avec Ressources Limitées : Coordination multi-modèles lorsque les ressources de calcul sont limitées

Références

Cet article cite d'importantes contributions dans les domaines des machines à bandits multi-bras, de l'apprentissage en ligne et des algorithmes d'experts, notamment :

  • L'algorithme UCB classique d'Auer et al.1
  • La théorie des algorithmes d'experts de Cesa-Bianchi et Lugosi4
  • L'optimisation convexe en ligne de Hazan5
  • Les algorithmes de méta-apprentissage modernes comme CORRAL8

Évaluation Globale : Ceci est un article théorique de haute qualité qui apporte des contributions significatives à un problème important mais peu étudié jusqu'à présent : l'apprentissage d'experts sous contrainte budgétaire. La conception de l'algorithme est ingénieuse, l'analyse théorique est rigoureuse, et elle jette une base solide pour le développement futur du domaine.