Offline-to-Online Learning in Linear Bandits

Technisches Resümee: Offline-zu-Online-Lernen in linearen Banditen

Problemstellung
Diese Arbeit befasst sich mit dem Problem des Offline-zu-Online-Lernens im Kontext stochastischer linearer Banditen. Das Szenario umfasst einen Lernenden, der sequenziell Aktionen aus einer Menge $\mathcal{A} \subset \mathbb{R}^d$ wählt, um die kumulativen Belohnungen über einen Horizont $n$ zu maximieren, während er Zugriff auf einen bereits existierenden Offline-Datensatz $\mathcal{D}$ hat. Die Offline-Daten werden durch ein festes, nicht-adaptives Design (deterministische Aktionszählungen) gesammelt und folgen einem linearen Belohnungsmodell mit subgaussischem Rauschen.

Die zentrale Herausforderung liegt im Zielkonflikt zwischen zwei konkurrierenden Zielen:

1. Online-Regret ($R_n$): Minimierung des Regrets relativ zur optimalen Aktion $\mu^*$. Standardmäßige Online-Algorithmen (z. B. LinUCB) verlassen sich auf Optimismus, um zu explorieren, erreichen einen sublinearen Regret, könnten aber einen hohen anfänglichen Regret erleiden, wenn die Offline-Daten ignoriert werden.
2. Offline-Regret ($R_n^{off}$): Minimierung des Regrets relativ zur mittleren Belohnung des Offline-Datensatzes ($\mu_{off}$). Standardmäßige Offline-Algorithmen (z. B. LinLCB) verlassen sich auf Pessimismus, um die bekannten Daten zu exploitieren, was eine Leistung nahe bei $\mu_{off}$ sicherstellt, aber das Explorationsvermögen einschränkt, was zu einem linearen Regret führt, wenn der Offline-Datensatz suboptimal ist oder der Horizont lang ist.

Bisherige Arbeiten haben diese Regime weitgehend getrennt behandelt oder sich auf Multi-Armed Bandits (MAB) konzentriert, bei denen der Regret mit der Anzahl der Aktionen skaliert. Diese Arbeit versucht, die Lücke in strukturierten (linearen) Umgebungen zu schließen, in denen der Regret mit der Dimension $d$ statt mit der Größe des Aktionsraums skalieren sollte.

Methodik: Der LinOtO-Algorithmus
Die Autoren schlagen LinOtO (Linear Offline-to-Online) vor, einen Algorithmus, der durch die Verwaltung eines Explorationsbudgets dynamisch zwischen Exploration und Exploitation abwägt. Der Algorithmus arbeitet durch das Wechseln zwischen zwei Strategien basierend auf einer Konfidenzmenge $C_t$, die sowohl aus Offline- als auch aus Online-Daten konstruiert wird:

1. Konfidenzmenge: Der Algorithmus pflegt einen Kleinste-Quadrate-Schätzer $\hat{\theta}_t$ und eine Konfidenzellipsoid $C_t$ um den wahren Parameter $\theta^*$. Der Radius dieser Menge berücksichtigt die Unsicherheit sowohl aus den Offline-Daten ($\beta_{off}$) als auch aus den Online-Interaktionen ($\beta_t$).
2. Optimistische vs. pessimistische Aktionen:
   • UCB-Aktion ($U_t$): Die Aktion, welche die obere Konfidenzgrenze (Upper Confidence Bound) innerhalb von $C_t$ maximiert. Dies fördert die Exploration und reduziert $R_n$, birgt aber das Risiko, $R_n^{off}$ zu erhöhen.
   • LCB-Aktion ($L_t$): Die Aktion, welche die untere Konfidenzgrenze (speziell das Maximum der minimalen Konfidenzgrenzen über die Zeit) maximiert. Dies fördert die Exploitation der Offline-Daten, reduziert $R_n^{off}$, kann aber $R_n$ erhöhen.
3. Budget-Mechanismus:
   • Der Algorithmus definiert eine sichere Baseline-Belohnung $r_b$, die aus einer unteren Schranke auf die Belohnung einer spezifischen „sicheren“ Aktion $L_{off}$ (der ausschließlich aus Offline-Daten berechneten LCB-Aktion) abgeleitet wird. Proposition 2 garantiert, dass $L_{off}$ mit hoher Wahrscheinlichkeit nahe bei $\mu_{off}$ liegt.
   • Ein Explorationsbudget $B(t)$ wird verwaltet, welches die kumulative Überschussbelohnung des Algorithmus über die Baseline $r_b$ darstellt.
   • Entscheidungsregel: Wenn $B(t) > 0$, wählt der Algorithmus die optimistische Aktion $U_t$ (Exploration). Wenn $B(t) \le 0$, wählt er die pessimistische Aktion $L_t$ (Exploitation), um das Budget aufzubauen.
   • Dieser Mechanismus stellt sicher, dass der Algorithmus nur dann exploriert, wenn er sich das Recht dazu durch das Bleiben sicher relativ zur Offline-Baseline „verdient“ hat.

Wesentliche Beiträge

1. Algorithmus-Design: Die Arbeit präsentiert LinOtO, den ersten Algorithmus, der speziell für das Offline-zu-Online-Szenario linearer Banditen entwickelt wurde und gleichzeitig UCB- und LCB-Strategien über einen budgetbasierten Wechselmechanismus ausbalanciert.
2. Theoretische Garantien: Die Autoren etablieren High-Probability-Regret-Schranken für beide Metriken:
   • Online-Regret ($R_n$): Theorem 1 zeigt, dass LinOtO einen sublinearen Regret relativ zur optimalen Aktion erreicht. Die Schranke besteht aus einem Term, der vom Horizont $n$ abhängt (ähnlich wie LinUCB), und einer additiven Konstante, die von der Qualität der Offline-Daten abhängt. Wenn die Offline-Daten den Raum gut abdecken, verbessert sich die Schranke.
   • Offline-Regret ($R_n^{off}$): Theorem 2 zeigt, dass der Regret relativ zur Offline-Referenz linear mit $n$ skaliert, aber mit $O(1/\sqrt{m})$ mit der Anzahl der Offline-Stichproben $m$ abnimmt. Dies entspricht der Leistung einer rein offensiven (pessimistischen) Lösung.
3. Pareto-Tradeoff-Analyse: Die Analyse offenbart einen abstimmbaren Tradeoff, der durch einen Parameter $\alpha$ gesteuert wird. Ein höheres $\alpha$ begünstigt die Online-Leistung (näher an LinUCB), während ein niedrigeres $\alpha$ die Offline-Leistung begünstigt (näher an LinLCB).

Experimentelle Ergebnisse
Empirische Auswertungen auf synthetischen linearen Bandit-Aufgaben (Dimension $d=20$, $|A|=100$) zeigen:

• Horizont-Sensitivität: Bei kurzen Horizonten folgt LinOtO der konservativen LinLCB-Baseline. Für lange Horizonte geht es zur Exploration über und erreicht einen sublinearen Regret vergleichbar mit LinUCB.
• Qualität der Offline-Daten:
  • Wenn der Offline-Datensatz die optimale Aktion ausschließt, weicht LinOtO erfolgreich von der suboptimalen Offline-Prior ab, um zu explorieren, und übertrifft schließlich LinLCB (welches einen linearen Regret erleidet) und nähert sich der LinUCB-Leistung an, wenn die Größe der Offline-Daten $m$ steigt.
  • Wenn der Offline-Datensatz die optimale Aktion enthält, konvergiert LinOtO schnell und erzielt eine Leistung, die vergleichbar mit LinUCB und LinLCB ist.
• Robustheit: Der Algorithmus agiert konsistent zwischen den Extremen reiner Exploration (LinUCB) und reiner Exploitation (LinLCB) und passt sich an die Problemparameter an.

Bedeutung und Ansprüche
Die Arbeit behauptet, dass LinOtO den „schwer zu verstehenden“ Offline-zu-Online-Tradeoff in strukturierten Umgebungen effektiv löst. Im Gegensatz zu bisherigen Arbeiten in MAB-Settings (z. B. Sentenac et al., 2025) nutzt dieser Ansatz die lineare Struktur, um sicherzustellen, dass der Regret mit der Dimension $d$ statt mit der Anzahl der Aktionen skaliert, was ihn für hochdimensionale Probleme skalierbar macht.

Die Autoren merken bescheiden an, dass ihr Framework derzeit von Fixed-Design-Offline-Daten ausgeht und keine Verteilungsverschiebungen zwischen Offline- und Online-Daten oder adaptive Logging-Policies berücksichtigt. Sie identifizieren die Adressierung dieser Einschränkungen sowie die Erweiterung des Frameworks auf nichtlineare Settings als wichtige Richtungen für die zukünftige Forschung. Die Arbeit trägt zur breiteren Literatur bei, die das Wissen über die Nutzung von Vorwissen (Hinweise, Offline-Daten) zur Steuerung von Exploration-Exploitation-Tradeoffs im Online-Lernen leistet.