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

UCB-Typ-Algorithmus für budgetbeschränktes Expertenlernens

Grundlegende Informationen

  • Papier-ID: 2510.22654
  • Titel: UCB-type Algorithm for Budget-Constrained Expert Learning
  • Autoren: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • Klassifizierung: cs.LG (Machine Learning), cs.MA (Multiagent Systems)
  • Veröffentlichungsdatum: 28. Oktober 2025 (Preprint)
  • Papierlink: https://arxiv.org/abs/2510.22654

Zusammenfassung

In vielen modernen Anwendungen muss ein System dynamisch zwischen mehreren online trainierten adaptiven Lernalgorithmen wählen. Beispiele sind Modellauswahl in Stream-Umgebungen, Handelsstrategiewechsel in der Finanzwirtschaft sowie die Koordination mehrerer kontextabhängiger Banditen oder Reinforcement-Learning-Agenten. In jeder Runde muss der Lernende einen Prädiktor aus K adaptiven Experten auswählen, während er unter einem festen Trainingsbudget höchstens M≤K Experten aktualisieren kann.

Dieser Artikel löst dieses Problem in stochastischen Einstellungen und schlägt den M-LCB-Algorithmus vor – einen rechnerisch effizienten UCB-Stil-Metaalgorithmus mit Bedauernisgarantien zu beliebigen Zeitpunkten. Seine Konfidenzintervalle werden direkt aus realisierten Verlusten konstruiert, ohne zusätzliche Optimierung, und spiegeln nahtlos die Konvergenzeigenschaften der zugrunde liegenden Experten wider. Wenn jeder Experte ein inneres Bedauern von Õ(T^α) erreicht, stellt M-LCB eine Gesamtbedauernisgrenze von Õ(√(KT/M) + (K/M)^(1-α)T^α) sicher.

Forschungshintergrund und Motivation

Problemdefinition

Viele praktische Anwendungen erfordern dynamische Auswahl zwischen mehreren selbstlernenden Experten:

  1. Empfehlungssysteme: Paralleles Ausführen mehrerer Prädiktoren mit Aktualisierung basierend auf Benutzer-Feedback
  2. Finanzplattformen: Wechsel zwischen Handelsstrategien mit sich entwickelnden Marktmechanismen
  3. Großflächige Online-Dienste: Verwaltung von Kombinationen kontextabhängiger Banditen oder Reinforcement-Learning-Algorithmen

Kernherausforderungen

Einschränkungen traditioneller Ansätze:

  • Klassische Multi-Armed Bandits (MAB): Gehen von statischen oder adversarialen Belohnungsverteilungen aus, berücksichtigen nicht die Lernfähigkeit der Arme
  • Expertenalgorithmen: Erfordern typischerweise vollständiges Feedback, berücksichtigen nicht die Lernraten der Experten
  • Bestehende Methoden: Adressieren nicht angemessen die Herausforderung der Verwaltung mehrerer gleichzeitig lernender Experten unter Trainingsbudgetbeschränkungen pro Runde

Forschungsmotivation

Dieser Artikel zielt darauf ab, diese Lücke zu schließen und ein einheitliches Verfahren für Vorhersage und selektives Training unter Berücksichtigung fester Rechenbudgetbeschränkungen pro Runde vorzuschlagen.

Kernbeiträge

  1. Neuartiger UCB-Typ-Metaalgorithmus (M-LCB): Schlägt einen neuen Algorithmus zur Verwaltung eines Pools von K selbstlernenden Experten unter Berücksichtigung eines begrenzten Lernbudgets M pro Runde (M≤K) vor
  2. Rechnerische Effizienz: Bietet eine Methode zur direkten Konstruktion von Konfidenzgrenzen aus realisierten Verlusten, die rechnerisch effizient ist und teure Hilfsoptimierungen vermeidet
  3. Theoretische Analyse: Schätzt die Metaalgorithmus-Leistung basierend auf individuellen Konvergenzraten der Experten; wenn das Expertengedauern Õ(n^α) beträgt, beträgt das Gesamtbedauern Õ(√(KT/M) + (K/M)^(1-α)T^α)
  4. Erweiterung auf Multi-Play-Banditen: Zeigt, dass M-LCB auf Multi-Play-Bandit-Einstellungen skalierbar ist

Methodische Details

Aufgabendefinition

  • Entscheidungsraum U: Raum der Expertenempfehlungen
  • Umgebungsraum E: Raum stochastischer Ergebnisse
  • Verlustfunktion: ℓ : U×E → R₊
  • Expertennorm: Jeder Experte k wird durch das Tupel (Wₖ,Hₖ,Aₖ,gₖ,υₖ) spezifiziert
    • Wₖ: Zustands-/Parameterraum
    • Hₖ: Verlaufsraum
    • Aₖ: Online-Lernalgorithmus
    • gₖ: Abbildung von Zustand zu Empfehlung
    • υₖ: Generator für sichere Empfehlungen

Protokollablauf

Ausführungsablauf in jeder Runde t:

  1. Das Metaprogramm wählt einen Berater iₜ∈K und eine Trainingsuntermenge Sₜ⊆K mit |Sₜ|≤M und iₜ∈Sₜ
  2. Experte iₜ liefert sichere Empfehlung uₜ = υᵢₜ(Hᵢₜᵗ)∈U
  3. Die Umgebung sampelt ξᵗ～D, das Programm erleidet Verlust ℓ(uₜ,ξᵗ)
  4. Experte k∈Sₜ aktualisiert Verlauf und inneren Zustand

M-LCB-Algorithmus-Kern

Konfidenzgrenzen-Definition

Für Experte k definieren wir:

  • Normalisierter Laufverlust: LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
  • Untere Konfidenzgrenze: LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
  • Obere Konfidenzgrenze: UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

Wobei:

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

Auswahlstrategie

  • Trainingsmenge-Auswahl: Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
  • Berater-Auswahl: iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

Technische Innovationen

  1. Direkte Konfidenzgrenzen-Konstruktion: Konstruktion direkt aus realisierten Verlusten ohne zusätzliche Optimierung
  2. Adaptive Expertenverwaltung: Berücksichtigung sowohl der Expertenauswahl als auch der Trainingsbudgetverteilung
  3. Garantien zu beliebigen Zeitpunkten: Bereitstellung von Bedauernsgrenzen für alle Zeitschritte T
  4. Flexibles Framework: Unterstützung verschiedener Arten von Lernalgorithmen als Experten

Experimentelle Einrichtung

Datensätze

Das Papier führt hauptsächlich synthetische Experimente durch:

Generalisierte lineare Modellauswahl

  • Anzahl der Experten: K=10 generalisierte lineare Modelle
  • Merkmalsdimension: Merkmalsvektoren gleichmäßig aus der Einheitssphäre Sᵈ⁻¹ gesampelt
  • Herausfordernde Einstellung: Funktionen f₇,f₈,f₉ sind in datenreichen Regionen stark ähnlich, was die Explorationsschwierigkeit erhöht

Bewertungsmetriken

  1. Kumulativer Verlust: ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
  2. Arm-Auswahlverteilung: Endgültige Häufigkeit der Auswahl jedes Experten
  3. Rechenbudgetverteilung: Verteilung der Trainingsanzahl für jeden Experten

Vergleichsmethoden

  1. ED2RB: Algorithmus mit lernbaren Arm-Garantien
  2. LimitedAdvice: Expertenalgorithmus, der mehrere Arm-Aktualisierungen pro Runde verarbeitet

Implementierungsdetails

  • Aktualisierungsbeschränkung: M∈{1,2,3}
  • Wiederholungen: 30 unabhängige Durchläufe für Durchschnittswertbildung
  • Konfidenzintervalle: Anzeige von ±0,5 Standardabweichungen
  • Hyperparameter-Tuning: ED2RB-Explorations-Parameter c=0,1, M-FLCB-Konzentrationstermskalierung 0,3

Experimentelle Ergebnisse

Hauptergebnisse

  1. Konvergenzleistung: M-LCB erreicht sublineares Bedauern, vergleichbar mit Baseline-Methoden
  2. Expertenidentifikation: Erfolgreiche Identifikation des optimalen Experten (k=9)
  3. Budgeteffizenz: Hauptsächliche Zuweisung von Aktualisierungen zu leistungsstarken Experten, während LimitedAdvice gleichmäßiger verteilt

Theoretische Ergebnisse

Obere Grenze Theorem

Theorem 2: Seien α,δ∈(0,1), und nehmen Sie an, dass jeder Experte k Uₖ(t,δ)=O(t^α c(δ)) erfüllt, dann ist mit Wahrscheinlichkeit mindestens 1-δ das Bedauern von Algorithmus 1 für alle T≥1 begrenzt durch:

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

Untere Grenze Theorem

Theorem 1: Es existieren Konstanten c₁,c₂>0, so dass für jeden Lernalgorithmus und jedes Metaprogramm:

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

Dies zeigt, dass M-LCB innerhalb von Logarithmischen Faktoren optimal ist.

Verwandte Arbeiten

Selbstlernende Experten (Arme)

  • 6: Führt selbstlernende Arme in MAB-Einstellungen ein, wobei jeder Arm eine parametrisierte Funktion ist, deren Parameter nach Auswahl aktualisiert werden

Meta-Level-Modellauswahl

  • CORRAL8: Verwaltet einen Pool von Bandit-Algorithmen durch wichtigkeitsgewichtetes Feedback unter log-barrier Online-Spiegeldescent
  • Dynamische Ausbalancierung9: Metaalgorithmus basierend auf bekannten Bedauernisraten-Ausdrücken, aktualisiert pro Runde nur einen Lerner
  • 10: Online-Schätzung von Koeffizienten pro Lerner, erhält hochwahrscheinliche datenabhängige Garantien für stochastische Banditen

MAB mit mehreren Arm-Aktualisierungen

  • Begrenzte Beratung12: Abfrage von höchstens M Armen, erhält Õ(√(KT logK/M)) Bedauernisgrenze
  • 13: Minimax-optimales Bedauern Õ(max{√(KT/M), √(T logK)})

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

  1. Erste Etablierung von Bedauernisgarantien für mehrere adaptive Experten unter Trainingsbudgetbeschränkungen pro Runde
  2. M-LCB-Algorithmus ist innerhalb von Logarithmischen Faktoren minimax-optimal
  3. Framework vereinheitlicht Online-Optimierung und stochastische Bandit-Einstellungen

Einschränkungen

  1. Bekannte Konfidenz-Skalierung: Analyse setzt voraus, dass die Konfidenz-Skalierungsfunktion c(δ) bekannt ist
  2. Annahme beschränkter Verluste: Konzentriert sich hauptsächlich auf Fälle mit beschränkten Verlusten
  3. Stochastische Einstellung: Hauptsächlich in stochastischen Umgebungen analysiert, adversariale Einstellungen erfordern weitere Forschung

Zukünftige Richtungen

  1. Unbekannte c(δ): Wie in Pacchiano et al.11 behandelt
  2. Erweiterung auf zusätzliche Beobachtungen: Erweiterung auf begrenzte Beratung und Multi-Play-Banditen
  3. Kontextabhängiges Regime: Erweiterung auf Fälle, in denen Experten basierend auf Beobachtungsmerkmalen spezialisiert sind

Tiefgreifende Bewertung

Stärken

  1. Bedeutsame theoretische Beiträge: Erste theoretische Garantien für Multi-Experten-Lernen unter Budgetbeschränkungen
  2. Elegantes Algorithmus-Design: Konfidenzgrenzen werden direkt aus Verlusten konstruiert, rechnerisch effizient
  3. Starke Framework-Universalität: Anwendbar auf verschiedene Expertentypen (parametrische Modelle, Bandit-Algorithmen usw.)
  4. Rigorose theoretische Analyse: Bereitstellung von übereinstimmenden Ober- und Untergrenzen, Beweis der Algorithmus-Optimalität

Mängel

  1. Begrenzte experimentelle Validierung: Hauptsächlich synthetische Experimente, fehlende Validierung in echten Anwendungsszenarien
  2. Starke Annahmebedingungen: Erfordert bekannte Form der Expertengedauernsgrenzen
  3. Konstanten-Faktor-Analyse: Konstanten in theoretischen Ergebnissen können groß sein, praktische Leistung erfordert Validierung

Auswirkungen

  1. Hoher theoretischer Wert: Bietet theoretische Grundlagen für Expertenlernens unter Budgetbeschränkungen
  2. Großes praktisches Potenzial: Anwendbar auf Empfehlungssysteme, Finanzhandel und andere Bereiche
  3. Starke Skalierbarkeit: Framework ist auf komplexere Lernszenarien erweiterbar

Anwendungsszenarien

  1. Online-Modellauswahl: Dynamische Modellauswahl in Stream-Datenumgebungen
  2. Multi-Strategie-Systeme: Finanzhandel, Werbeplatzierung und andere Szenarien, die Strategiewechsel erfordern
  3. Ressourcenbeschränktes Lernen: Multi-Modell-Koordination bei begrenzten Rechenressourcen

Literaturverzeichnis

Dieses Papier zitiert wichtige Literatur aus den Bereichen Multi-Armed Bandits, Online-Lernen und Expertenalgorithmen, insbesondere:

  • Klassischer UCB-Algorithmus von Auer et al.1
  • Expertenalgorithmus-Theorie von Cesa-Bianchi und Lugosi4
  • Online-konvexe Optimierung von Hazan5
  • Moderne Meta-Learning-Algorithmen wie CORRAL8

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Papier, das bedeutsame Beiträge zu einem wichtigen, aber bisher unterforschten Problem des budgetbeschränkten Expertenlernens leistet. Das Algorithmus-Design ist ausgeklügelt, die theoretische Analyse ist rigoros und legt eine solide Grundlage für weitere Entwicklungen in diesem Bereich.