Invariance-Based Dynamic Regret Minimization

Die Arbeit stellt ISD-linUCB vor, einen Algorithmus für stochastische nicht-stationäre lineare Banditen, der durch die Annahme einer Zerlegung des Belohnungsmodells in stationäre und nicht-stationäre Komponenten historische Daten nutzt, um Invarianzen zu lernen und so die Problemdimensionalität zu reduzieren sowie das dynamische Regret in sich schnell verändernden Umgebungen signifikant zu verbessern.

Das Wesentliche

Stell dir vor, du bist ein Koch, der jeden Tag ein neues Gericht für seine Gäste zubereitet. Deine Aufgabe ist es, herauszufinden, welche Kombination aus Zutaten (dem „Kontext") und Kochtechnik (der „Aktion") am besten schmeckt, um die Gäste glücklich zu machen (die „Belohnung").

In der Welt des maschinellen Lernens nennt man das einen Bandit-Algorithmus. Das Problem ist: Die Geschmackspräferenzen deiner Gäste ändern sich ständig. Vielleicht magten sie gestern viel Salz, heute aber gar keines. Das nennt man nicht-stationär – die Regeln des Spiels ändern sich mit der Zeit.

Das Problem: Alles neu lernen?

Die meisten bisherigen Kochbücher (Algorithmen) sagen: „Vergiss alles, was du gestern gelernt hast! Die Gäste mögen heute etwas anderes." Sie werfen alte Daten weg oder gewichten sie so stark ab, dass sie fast nichts mehr zählen. Das ist wie ein Koch, der jeden Morgen ein neues Rezeptbuch aufschlägt und alles von vorne lernt. Das kostet viel Zeit und führt zu vielen Fehlern (Regret), besonders wenn sich die Vorlieben schnell ändern.

Die geniale Idee: Was bleibt gleich?

Die Autoren dieses Papers haben eine andere Frage gestellt: Gibt es Dinge, die sich nicht ändern?

Stell dir vor, deine Gäste mögen vielleicht heute weniger Salz, aber sie mögen niemals bitteres Essen. Oder sie mögen vielleicht die Gewürzmischung ändern, aber die Grundtechnik des Bratens bleibt immer gleich.

Das ist der Kern der ISD-linUCB-Methode (Invariant Subspace Decomposition). Die Autoren teilen die Welt der Zutaten in zwei Bereiche auf:

1. Der unveränderliche Bereich (Invariant): Das sind die Dinge, die immer gleich bleiben (z. B. „Salz ist gut, Bitterkeit ist schlecht"). Diese Informationen kann man aus der Vergangenheit (den alten Daten) lernen und für immer behalten.
2. Der veränderliche Bereich (Residual): Das sind die Dinge, die sich täglich ändern (z. B. „Heute mögen sie scharf, morgen mild"). Hier muss man neu lernen und experimentieren.

Wie funktioniert der Algorithmus? (Die Metapher)

Stell dir vor, du hast einen riesigen Kochkeller mit tausenden alten Rezepten (Offline-Daten).

• Der alte Weg: Du nimmst nur die letzten 5 Rezepte, wirfst die anderen weg und versuchst, aus diesen 5 zu lernen. Das ist riskant, wenn die 5 zufällig alle schlechte Gerichte waren.
• Der neue Weg (ISD-linUCB):
  1. Du gehst in den Keller und suchst nach den Grundregeln, die in allen tausenden alten Rezepten gelten. (Das ist das Lernen der „Invarianten"). Du merkst dir: „Ah, Fett macht Essen saftig, das gilt immer."
  2. Jetzt, wo du die Grundregeln kennst, musst du dich im neuen Restaurant (Online-Phase) nur noch auf die Änderungen konzentrieren. Du musst nicht mehr raten, ob Fett gut ist. Du musst nur noch herausfinden: „Soll ich heute Chili oder Paprika nehmen?"

Warum ist das so cool?

In der Mathematik (und im Kochen) ist es viel schwieriger, viele Dinge gleichzeitig zu lernen, als wenige.

• Wenn du versuchst, 100 Zutaten zu meistern, die sich alle ändern, brauchst du ewig.
• Wenn du aber weißt, dass 90 davon immer gleich sind, musst du nur noch die verbleibenden 10 lernen.

Das Paper zeigt mathematisch und durch Simulationen, dass dieser Trick den Fehler (Regret) drastisch reduziert.

• Ohne Trick: Der Fehler wächst mit der Gesamtzahl der Zutaten ($p$).
• Mit Trick: Der Fehler wächst nur mit der Zahl der sich ändernden Zutaten ($p - p_{inv}$).

Wenn sich die Umgebung schnell ändert (wie bei einem Launen-Gast), aber du genug alte Daten hast, um die Grundregeln zu kennen, bist du dem alten Koch um Längen voraus. Du musst nicht bei Null anfangen; du startest mit einem riesigen Vorsprung an Wissen.

Zusammenfassung in einem Satz

Statt jedes Mal das Rad neu zu erfinden, wenn sich die Welt ändert, nutzt dieser Algorithmus alte Daten, um zu erkennen, was immer wahr ist, und konzentriert sich dann nur noch auf das, was sich gerade ändert. Das macht ihn schneller, effizienter und weniger fehleranfällig.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel: Invariance-based dynamic regret minimization (Invarianzbasierte Minimierung des dynamischen Regrets)

Autoren: Margherita Lazzaretto, Jonas Peters, Niklas Pfister
Veröffentlichung: arXiv (2026)

---

1. Problemstellung

Das Paper adressiert das Problem der stochastischen nicht-stationären linearen Banditen (Stochastic Non-Stationary Linear Bandits).

• Kontext: Ein Agent trifft über $T$ Runden sequenziell Entscheidungen basierend auf Kontexten $X_t \in \mathbb{R}^p$.
• Ziel: Maximierung der kumulierten Belohnung durch Lernen einer Policy, die Exploration und Exploitation balanciert.
• Herausforderung: Im Gegensatz zu stationären Umgebungen ändert sich der lineare Parameter $\gamma_{0,t}$, der Kontext und Belohnung verbindet, über die Zeit.
• Bestehende Ansätze: Herkömmliche Algorithmen für nicht-stationäre Umgebungen (z. B. gleitende Fenster, Diskontierungsfaktoren, periodische Neustarts) behandeln historische Daten oft als veraltet. Sie verwerfen oder gewichten alte Daten herunter, um sich an Änderungen anzupassen. Dies führt dazu, dass der effektive Lernhorizont schrumpft und die Regret-Schranken stark von der vollen Dimension $p$ und der Variationsbudget $B_T$ abhängen (typischerweise $\tilde{O}(p^{7/8} T^{3/4} B_T^{1/4})$).
• Kernannahme des Papers: In vielen realen Szenarien enthält die historische Datenmenge dennoch teilweise Informationen über das Belohnungsmodell, da sich nicht alle Komponenten des Parameters ändern. Es wird angenommen, dass sich der Parameter in einen invarianten (zeitunabhängigen) und einen nicht-invarianten (zeitvariablen) Teil zerlegen lässt.

2. Methodik: ISD-linUCB

Die Autoren schlagen den Algorithmus ISD-linUCB (Invariant Subspace Decomposition linear Upper Confidence Bound) vor. Dieser nutzt historische Offline-Daten, um Invarianzen zu lernen, und verbessert so die Online-Leistung.

A. Invariant Subspace Decomposition (ISD)

Das Modell basiert auf der Annahme, dass der Parameter $\gamma_{0,t}$ in zwei orthogonale Unterräume zerlegt werden kann:
$$\gamma_{0,t} = \beta_{inv} + \delta_{res,t}$$

• $\beta_{inv} \in S_{inv}$: Ein zeitinvarianter Anteil in einem Unterraum der Dimension $p_{inv} < p$.
• $\delta_{res,t} \in S_{res}$: Ein zeitvariabler Restanteil in einem Unterraum der Dimension $p_{res} = p - p_{inv}$.
• Annahme: Die Projektionen der Kontext-Features auf diese beiden Unterräume sind unkorreliert.

B. Algorithmus-Ablauf

Der Algorithmus besteht aus zwei Phasen:

1. Offline-Phase:
   • Nutzung von $T_0$ historischen Beobachtungen (gesammelt von einer vorherigen Policy).
   • Schätzung der orthogonalen Matrix $U$, die die Kovarianzmatrizen der Features block-diagonalisiert.
   • Identifikation der Unterräume $S_{inv}$ und $S_{res}$ sowie Schätzung des invarianten Parameters $\hat{\beta}_{inv}$.
2. Online-Phase:
   • Der Algorithmus adaptiert sich an die Nicht-Stationarität, indem er nur im residualen Unterraum $S_{res}$ Exploration betreibt.
   • Der invariante Anteil $\beta_{inv}$ wird als bekannt (oder hochpräzise geschätzt) angenommen und nicht weiter adaptiert.
   • Die Entscheidung (Action Selection) erfolgt basierend auf einer Konfidenzmenge, die die Summe aus dem geschätzten invarianten Teil und dem adaptiven residualen Teil bildet ($\hat{C}_\beta \oplus \hat{C}_\delta$).

3. Wichtige Beiträge

1. Neuer Algorithmus (ISD-linUCB): Ein praktischer Algorithmus, der die Online-Anpassung auf einen niedrigerdimensionalen residualen Unterraum reduziert, indem er Invarianzen aus Offline-Daten nutzt.
2. Theoretische Regret-Schranken:
   • Es wird gezeigt, dass das Regret nicht von der vollen Dimension $p$, sondern von der Dimension des residualen Raums $p_{res}$ skaliert.
   • Unter der Annahme, dass genügend Offline-Daten ($T_0 \gg T$) verfügbar sind, verbessert sich die Schranke von $\tilde{O}(p\sqrt{T})$ auf $\tilde{O}(p_{res}\sqrt{T})$.
   • Selbst bei Schätzung der Unterräume aus Daten bleibt der Vorteil erhalten, solange $T_0$ groß genug ist.
3. Analyse von Schätzfehlern: Das Paper liefert eine vollständige Analyse, die auch Fehler bei der Schätzung der Unterräume ($S_{inv}, S_{res}$) und des invarianten Parameters berücksichtigt. Es wird bewiesen, dass diese Fehler mit wachsendem $T_0$ vernachlässigbar werden.

4. Ergebnisse

Theoretische Ergebnisse

• Oracle-Fall: Wenn die Zerlegung und $\beta_{inv}$ bekannt sind, beträgt das Regret $\tilde{O}(p_{res}\sqrt{T})$.
• Mit Offline-Daten: Wenn $\beta_{inv}$ aus $T_0$ Daten geschätzt wird, lautet die Schranke:
  $$\tilde{O}\left(\sqrt{T} \left( p_{res} + \sqrt{\frac{p_{inv} T}{\lambda_0 T_0}} + \frac{1}{\lambda_0}\sqrt{\frac{T}{T_0}} \right) \right)$$
  Dies zeigt, dass für $T_0 \gg T$ der Term mit $p_{res}$ dominiert und der Vorteil gegenüber klassischen Methoden (die von $p$ abhängen) signifikant ist.
• Untere Schranke: Es wird gezeigt, dass $\Omega(p_{res}\sqrt{T})$ eine untere Schranke für das Problem ist, wenn die Invarianz bekannt ist, was die Optimalität des Ansatzes bestätigt.

Experimentelle Ergebnisse

• Simulationen: Die Autoren führen Experimente durch, bei denen $p=10$ und $p_{res}$ variiert wird.
• Vergleich: ISD-linUCB (mit Oracle-Wissen über den Unterraum) zeigt ein Regret, das linear mit $p_{res}$ und sublinear mit $T$ wächst. Im Gegensatz dazu wächst das Regret des Standard-LinUCB linear mit der vollen Dimension $p$.
• Schätzung des Unterraums: Auch wenn der Unterraum aus den Offline-Daten geschätzt wird, nähert sich die Leistung von ISD-linUCB mit steigendem $T_0$ der Oracle-Leistung an und übertrifft dabei deutlich den Standard-LinUCB und andere nicht-stationäre Algorithmen (wie gleitende Fenster oder Diskontierung).

5. Bedeutung und Fazit

Das Paper bietet einen Paradigmenwechsel im Umgang mit nicht-stationären Bandit-Problemen:

• Effizienzsteigerung: Anstatt historische Daten zu verwerfen, werden sie genutzt, um stabile (invariante) Strukturen im Belohnungsmodell zu identifizieren.
• Dimensionsreduktion: Durch die Trennung von invarianten und variablen Komponenten wird das effektive Lernproblem auf einen niedrigerdimensionalen Raum reduziert. Dies ist besonders vorteilhaft in Umgebungen mit schnellen Änderungen, wo der "Lernraum" für den variablen Teil klein ist, aber historische Daten für den invarianten Teil reichlich vorhanden sind.
• Praktische Relevanz: Der Ansatz ist besonders nützlich in Anwendungen wie personalisierten Empfehlungssystemen oder medizinischen Behandlungen, wo bestimmte zugrundeliegende Mechanismen (z. B. physiologische Reaktionen) stabil bleiben, während andere Faktoren (z. B. Tageszeit, externe Einflüsse) variieren.

Zusammenfassend demonstriert ISD-linUCB, dass die Ausnutzung von Invarianzen in nicht-stationären Umgebungen zu signifikanten Verbesserungen des Regrets führen kann, ohne die Flexibilität zu verlieren, sich an echte Änderungen anzupassen.