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

Algoritmo di tipo UCB per l'Apprendimento di Esperti con Vincoli di Budget

Informazioni Fondamentali

  • ID Articolo: 2510.22654
  • Titolo: UCB-type Algorithm for Budget-Constrained Expert Learning
  • Autori: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • Classificazione: cs.LG (Machine Learning), cs.MA (Multiagent Systems)
  • Data di Pubblicazione: 28 Ottobre 2025 (Preprint)
  • Link Articolo: https://arxiv.org/abs/2510.22654

Riassunto

In molte applicazioni moderne, i sistemi devono selezionare dinamicamente tra molteplici algoritmi di apprendimento adattivo addestrati online. Ad esempio, la selezione di modelli in ambienti di flusso, il cambio di strategie di trading in finanza, e il coordinamento di molteplici banditi contestuali o agenti di apprendimento per rinforzo. In ogni round, l'apprendente deve scegliere un predittore da K esperti adattivi per fare previsioni, mentre può aggiornare al massimo M≤K esperti entro un budget di addestramento fisso.

Questo articolo affronta il problema in un contesto stocastico, proponendo l'algoritmo M-LCB — un meta-algoritmo di tipo UCB computazionalmente efficiente che fornisce garanzie di rimpianto in qualsiasi momento. I suoi intervalli di confidenza sono costruiti direttamente dalle perdite realizzate, senza richiedere ulteriori ottimizzazioni, e riflettono senza soluzione di continuità le caratteristiche di convergenza degli esperti sottostanti. Se ogni esperto raggiunge un rimpianto interno di Õ(T^α), M-LCB garantisce un limite di rimpianto complessivo di Õ(√(KT/M) + (K/M)^(1-α)T^α).

Contesto di Ricerca e Motivazione

Definizione del Problema

Molte applicazioni nel mondo reale richiedono la selezione dinamica tra molteplici esperti auto-apprendenti:

  1. Sistemi di Raccomandazione: esecuzione parallela di molteplici predittori, aggiornamento in base al feedback degli utenti
  2. Piattaforme Finanziarie: cambio tra strategie di trading con l'evoluzione dei meccanismi di mercato
  3. Servizi Online su Larga Scala: gestione di combinazioni di banditi contestuali o algoritmi di apprendimento per rinforzo

Sfide Fondamentali

Limitazioni degli approcci tradizionali:

  • Banditi Multi-Braccio Classici (MAB): assumono distribuzioni di ricompensa statiche o avversariali, non considerano la capacità di apprendimento dei bracci
  • Algoritmi di Esperti: tipicamente richiedono feedback completo, non considerano i tassi di apprendimento degli esperti
  • Metodi Esistenti: nessuno affronta adeguatamente la sfida di gestire molteplici esperti che apprendono simultaneamente sotto vincoli di budget di addestramento per round

Motivazione della Ricerca

Questo articolo mira a colmare questo vuoto, proponendo una procedura unificata di previsione e addestramento selettivo, considerando vincoli di budget computazionale fissi per round.

Contributi Fondamentali

  1. Nuovo Meta-Algoritmo di Tipo UCB (M-LCB): propone un nuovo algoritmo per gestire un pool di K esperti auto-apprendenti, considerando un budget di apprendimento limitato per round M (M≤K)
  2. Efficienza Computazionale: fornisce un metodo per costruire intervalli di confidenza direttamente dalle perdite realizzate, computazionalmente efficiente ed evita costose ottimizzazioni ausiliarie
  3. Analisi Teorica: stima le prestazioni del meta-algoritmo in base ai tassi di convergenza individuali degli esperti; quando il rimpianto dell'esperto è Õ(n^α), il rimpianto complessivo è Õ(√(KT/M) + (K/M)^(1-α)T^α)
  4. Estensione a Banditi Multi-Gioco: dimostra che M-LCB è estendibile all'impostazione di banditi multi-gioco

Dettagli del Metodo

Definizione del Compito

  • Spazio Decisionale U: spazio dei suggerimenti degli esperti
  • Spazio Ambientale E: spazio dei risultati stocastici
  • Funzione di Perdita: ℓ : U×E → R₊
  • Specifica degli Esperti: ogni esperto k è specificato dalla tupla (Wₖ,Hₖ,Aₖ,gₖ,υₖ)
    • Wₖ: spazio di stato/parametri
    • Hₖ: spazio di storia
    • Aₖ: algoritmo di apprendimento online
    • gₖ: mappatura da stato a suggerimento
    • υₖ: generatore di suggerimenti sicuri

Flusso del Protocollo

Flusso di esecuzione per ogni round t:

  1. Il meta-programma seleziona un consulente iₜ∈K e un sottoinsieme di addestramento Sₜ⊆K, con |Sₜ|≤M e iₜ∈Sₜ
  2. L'esperto iₜ fornisce un suggerimento sicuro uₜ = υᵢₜ(Hᵢₜᵗ)∈U
  3. L'ambiente campiona ξᵗ～D, il programma subisce una perdita ℓ(uₜ,ξᵗ)
  4. Gli esperti k∈Sₜ aggiornano la storia e lo stato interno

Nucleo dell'Algoritmo M-LCB

Definizione degli Intervalli di Confidenza

Per l'esperto k, si definisce:

  • Perdita di Esecuzione Normalizzata: LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
  • Intervallo di Confidenza Inferiore: LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
  • Intervallo di Confidenza Superiore: UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

Dove:

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

Strategia di Selezione

  • Selezione dell'Insieme di Addestramento: Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
  • Selezione del Consulente: iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

Punti di Innovazione Tecnica

  1. Costruzione Diretta di Intervalli di Confidenza: costruiti direttamente dalle perdite realizzate, senza richiedere ulteriori ottimizzazioni
  2. Gestione Adattiva degli Esperti: considera simultaneamente la selezione degli esperti e l'allocazione del budget di addestramento
  3. Garanzie in Qualsiasi Momento: fornisce limiti di rimpianto per tutti i passi temporali T
  4. Framework Flessibile: supporta diversi tipi di algoritmi di apprendimento come esperti

Impostazione Sperimentale

Dataset

L'articolo conduce principalmente esperimenti sintetici:

Selezione di Modelli Lineari Generalizzati

  • Numero di Esperti: K=10 modelli lineari generalizzati
  • Dimensione delle Caratteristiche: vettori di caratteristiche campionati uniformemente dalla sfera unitaria Sᵈ⁻¹
  • Impostazione Impegnativa: le funzioni f₇,f₈,f₉ sono altamente simili nella regione densa dei dati, aumentando la difficoltà dell'esplorazione

Metriche di Valutazione

  1. Perdita Cumulativa: ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
  2. Distribuzione di Selezione dei Bracci: frequenza finale di selezione di ogni esperto
  3. Allocazione del Budget Computazionale: distribuzione del numero di volte che ogni esperto viene addestrato

Metodi di Confronto

  1. ED2RB: algoritmo con garanzie di bracci apprendenti
  2. LimitedAdvice: algoritmo di esperti in grado di gestire aggiornamenti multi-braccio per round

Dettagli di Implementazione

  • Limite di Aggiornamento: M∈{1,2,3}
  • Numero di Ripetizioni: 30 esecuzioni indipendenti per la media
  • Intervalli di Confidenza: mostrano ±0.5 deviazioni standard
  • Sintonizzazione degli Iperparametri: parametro di esplorazione ED2RB c=0.1, fattore di scala del termine di concentrazione M-FLCB 0.3

Risultati Sperimentali

Risultati Principali

  1. Prestazioni di Convergenza: M-LCB raggiunge rimpianto sublineare, competitivo con i metodi di base
  2. Identificazione dell'Esperto: identifica con successo l'esperto ottimale (k=9)
  3. Efficienza del Budget: alloca principalmente gli aggiornamenti agli esperti con prestazioni eccellenti, mentre LimitedAdvice alloca più uniformemente

Risultati Teorici

Teorema del Limite Superiore

Teorema 2: Siano α,δ∈(0,1), si assuma che ogni esperto k soddisfi Uₖ(t,δ)=O(t^α c(δ)), allora con probabilità almeno 1-δ, il rimpianto dell'Algoritmo 1 è limitato per tutti i T≥1:

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

Teorema del Limite Inferiore

Teorema 1: Esistono costanti c₁,c₂>0 tali che per qualsiasi algoritmo di apprendimento e meta-programma:

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

Questo dimostra che M-LCB è ottimale entro fattori logaritmici.

Lavori Correlati

Esperti Auto-Apprendenti (Bracci)

  • 6: introduce bracci auto-apprendenti nell'impostazione MAB, dove ogni braccio è una funzione parametrizzata con parametri aggiornati quando selezionato

Selezione di Modelli a Livello Meta

  • CORRAL8: gestisce pool di algoritmi di banditi attraverso discesa di specchio online con barriera logaritmica e feedback ponderato per importanza
  • Bilanciamento Dinamico9: meta-algoritmo basato su espressioni di tasso di rimpianto noto, aggiorna solo un apprendente per round
  • 10: stima online i coefficienti per apprendente, ottenendo garanzie ad alta probabilità dipendenti dai dati per banditi stocastici

MAB con Aggiornamenti Multi-Braccio

  • Consiglio Limitato12: interroga al massimo M bracci, ottenendo limite di rimpianto Õ(√(KT logK/M))
  • 13: rimpianto minimax ottimale Õ(max{√(KT/M), √(T logK)})

Conclusioni e Discussione

Conclusioni Principali

  1. Stabilisce per la prima volta garanzie di rimpianto per molteplici esperti adattivi addestrati simultaneamente sotto vincoli di budget per round
  2. L'algoritmo M-LCB è minimax ottimale entro fattori logaritmici
  3. Il framework unifica l'ottimizzazione online e l'impostazione di banditi stocastici

Limitazioni

  1. Scalatura di Confidenza Nota: l'analisi assume che la funzione di scalatura della confidenza c(δ) sia nota
  2. Ipotesi di Perdita Limitata: si concentra principalmente su perdite limitate
  3. Impostazione Stocastica: l'analisi principale è in ambienti stocastici; l'impostazione avversariale richiede ulteriori ricerche

Direzioni Future

  1. Caso di c(δ) Sconosciuto: come affrontato da Pacchiano et al.11
  2. Estensione con Osservazioni Aggiuntive: estensione a consigli limitati e banditi multi-gioco
  3. Regime Contestuale: estensione a esperti specializzati in base a caratteristiche osservate

Valutazione Approfondita

Punti di Forza

  1. Contributo Teorico Significativo: fornisce per la prima volta garanzie teoriche per l'apprendimento multi-esperto sotto vincoli di budget
  2. Progettazione dell'Algoritmo Elegante: gli intervalli di confidenza sono costruiti direttamente dalle perdite, computazionalmente efficienti
  3. Framework Altamente Generale: applicabile a molteplici tipi di esperti (modelli parametrici, algoritmi di banditi, ecc.)
  4. Analisi Teorica Rigorosa: fornisce limiti superiori e inferiori corrispondenti, provando l'ottimalità dell'algoritmo

Insufficienze

  1. Verifica Sperimentale Limitata: principalmente esperimenti sintetici, mancanza di validazione in scenari di applicazione reale
  2. Condizioni di Ipotesi Forti: richiede la conoscenza della forma del limite di rimpianto dell'esperto
  3. Analisi dei Fattori Costanti: i risultati teorici potrebbero avere fattori costanti grandi; le prestazioni pratiche richiedono verifica

Impatto

  1. Alto Valore Teorico: fornisce fondamenti teorici per l'apprendimento di esperti con vincoli di budget
  2. Grande Potenziale Pratico: applicabile a sistemi di raccomandazione, trading finanziario e altri domini
  3. Forte Scalabilità: il framework è estendibile a scenari di apprendimento più complessi

Scenari Applicabili

  1. Selezione Online di Modelli: selezione dinamica di modelli in ambienti di dati in flusso
  2. Sistemi Multi-Strategia: scenari come trading finanziario e posizionamento di annunci che richiedono cambio di strategia
  3. Apprendimento con Risorse Limitate: coordinamento multi-modello quando le risorse computazionali sono limitate

Riferimenti Bibliografici

L'articolo cita letteratura importante nei campi dei banditi multi-braccio, apprendimento online, algoritmi di esperti, in particolare:

  • Algoritmo UCB classico di Auer et al.1
  • Teoria degli algoritmi di esperti di Cesa-Bianchi e Lugosi4
  • Ottimizzazione online convessa di Hazan5
  • Algoritmi di meta-apprendimento moderni come CORRAL8

Valutazione Complessiva: Questo è un articolo teorico di alta qualità che fornisce contributi significativi a un importante problema di apprendimento di esperti con vincoli di budget che era stato precedentemente poco studiato. La progettazione dell'algoritmo è ingegnosa, l'analisi teorica è rigorosa, e getta solide basi per lo sviluppo futuro del campo.