Stochastic Linear Bandits with Parameter Noise

Technisches Fazit: Stochastische lineare Banditen mit Parameterrauschen

Problemdefinition
Diese Arbeit untersucht das Modell der stochastischen linearen Banditen mit Parameterrauschen. In diesem Setting interagiert ein Lernender über einen Zeithorizont $T$ mit einer Umgebung, indem er Aktionen $a_t$ aus einer Aktionsmenge $\mathcal{A} \subseteq \mathbb{R}^d$ auswählt. Im Gegensatz zum Standardmodell mit additivem Rauschen, bei dem die Belohnung $X_t = a_t^\top \theta^\star + \eta_t$ ist (mit festem $\theta^\star$ und Rauschen $\eta_t$), geht das Parameterrauschen-Modell davon aus, dass die Belohnung durch $X_t = a_t^\top \theta_t$ gegeben ist, wobei $\theta_t$ i.i.d. aus einer festen, unbekannten Verteilung $\nu$ mit Erwartungswert $\theta^\star$ und Kovarianzmatrix $\Sigma$ gezogen wird.

Die Arbeit hebt einen wesentlichen Unterschied hervor: Im Parameterrauschen-Modell kann der Lernende die Varianz der Belohnung beeinflussen. Spezifisch gilt $\text{Var}(X_t) = a_t^\top \Sigma a_t$, wohingegen im Modell mit additivem Rauschen die Varianz ausschließlich von der Umgebung bestimmt wird. Die Autoren stellen fest, dass das Parameterrauschen-Modell zwar eine Relaxierung des adversarischen linearen Banditen-Modells ist (wobei $\theta_t$ von einem Gegner gewählt wird), es jedoch einzigartige strukturelle Eigenschaften aufweist, die in bestimmten geometrischen Settings potenziell engere Regret-Schranken als das Modell mit additivem Rauschen ermöglichen.

Methodik und Algorithmen
Die Autoren schlagen zwei Algorithmen vor, die auf unterschiedliche Geometrien von Aktionsmengen zugeschnitten sind:

1. VASE (Variance Aware Optimal Design Successive Elimination):

   • Ziel: Allgemeine endliche Aktionsmengen (und unendliche Mengen über Überdeckungsargumente).
   • Mechanismus: Ein sukzessiver Eliminationsalgorithmus, der Varianzinformationen nutzt. In jeder Phase berechnet er ein G-optimaler Design $\pi_\ell$, um Aktionen auszuwählen. Er schätzt explizit die Varianz der Aktionen im Träger des Designs unter Verwendung eines Stoppregel-Algorithmus (SR).
   • Schlüsselinnovation: Der Algorithmus nutzt geschätzte Varianzen auf zwei Arten: um die für die Exploration erforderliche Anzahl an Stichproben zu reduzieren und als Gewichte in einem gewichteten Kleinste-Quadrate-Schätzer. Diese Gewichtung stellt sicher, dass die Kovarianz des Schätzers auch bei weniger Stichproben kontrolliert bleibt, was zu varianzabhängigen Regret-Schranken führt.

2. VALEE (Variance Aware Linear Explore-Exploit):

   • Ziel: $\ell_p$-Einheitskugeln mit $p \in (1, 2]$ (und deren Dualnormen $q \ge 2$).
   • Mechanismus: Ein einfacher Explore-Exploit-Algorithmus.
     • Exploration: Der Algorithmus spielt Standardbasisvektoren $e_i$. Er schätzt den Mittelwertvektor $\theta^\star$ koordinatenweise unter Verwendung der Median-of-Means (MoM)-Technik. Falls die Kovarianzmatrix $\Sigma$ unbekannt ist, schätzt er zunächst die Varianzen der Basisvektoren.
     • Exploitation: Sobald der Schätzfehler im Verhältnis zur Varianz und zum Zeithorizont hinreichend klein ist, verpflichtet sich der Algorithmus zu einer Aktion $\hat{a}$, die aus dem geschätzten Mittelwert $\hat{\theta}$ abgeleitet ist, spezifisch $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Schlüsselinnovation: Die Analyse nutzt die Geometrie der $\ell_p$-Kugel und die Struktur des Parameterrauschens aus. Die Autoren zeigen, dass das Explorieren von Basisvektoren einen Schätzfehler liefert, der proportional zu $\sqrt{\sigma^2(e_i)}$ ist, was enger ist als die Standard-$\epsilon$-Schranke in Modellen mit additivem Rauschen. Dies ermöglicht dem Algorithmus, optimale Regret-Schranken zu erreichen, die von der Varianzstruktur der Belohnungsverteilung abhängen.

Hauptergebnisse
Die Arbeit etabliert sowohl obere als auch untere Schranken und zeigt, dass die vorgeschlagenen Algorithmen für spezifische Settings minimax-optimal (bis auf logarithmische Faktoren) sind.

• Allgemeine endliche Aktionsmengen ($K$ Aktionen):

  • Obere Schranke: VASE erreicht einen Regret von $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, wobei $M_\sigma$ eine varianzabhängige Größe ist, die durch $\max_a \sigma^2(a)$ beschränkt ist.
  • Untere Schranke: Eine untere Schranke von $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ wird bewiesen, was zeigt, dass die obere Schranke bis auf logarithmische Faktoren eng ist, wenn $\log(K) \approx d$.

• $\ell_p$-Einheitskugeln ($p \le 2$):

  • Bekannte Kovarianz: VALEE erreicht einen Regret von $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, wobei $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Dies wird durch eine passende untere Schranke von $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$ als optimal erwiesen.
  • Unbekannte Kovarianz: VALEE verursacht einen zusätzlichen additiven Term, was zu einem Regret von $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$ führt. Die Autoren stellen fest, dass dieser additive Term aus der Phase der Varianzschätzung resultiert.

• $\ell_p$-Einheitskugeln ($p > 2$):

  • Die Arbeit liefert eine untere Schranke von $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, die mit den bekannten unteren Schranken für das adversarische Setting in diesen Geometrien übereinstimmt.

Bedeutung und Behauptungen
Die Arbeit behauptet, einen „kuriosen Fall" bezüglich linearer Banditen zu lösen, bei dem das Modell mit additivem Rauschen für bestimmte Aktionsmengen wie die $\ell_2$-Einheitskugel oft schlechtere Regret-Schranken ($d\sqrt{T}$) liefert als das adversarische Modell ($\sqrt{dT}$). Die Autoren zeigen, dass das Parameterrauschen-Modell besser mit der Intuition übereinstimmt, dass stochastische Modelle einfacher sein sollten als adversarische.

• Engere Schranken: Für $\ell_p$-Kugeln mit $p \le 2$ ermöglicht das Parameterrauschen-Modell Regret-Schranken der Ordnung $\sqrt{dT \sigma^2_q}$, die bei kleiner Varianz erheblich kleiner sein können als die für Modelle mit additivem Rauschen typische Schranke $d\sqrt{T}$.
• Struktureller Vorteil: Die Ergebnisse unterstreichen, dass die Linearität der Realisierung (nicht nur des Erwartungswerts) und die Fähigkeit des Lernenden, die Varianz zu beeinflussen, entscheidend für das Erreichen dieser verbesserten Schranken sind.
• Einfachheit: Überraschenderweise ist der optimale Regret für $\ell_p$-Kugeln ($p \le 2$) mit einem sehr einfachen Explore-Exploit-Algorithmus (VALEE) erreichbar, im Gegensatz zu den komplexen optimalen Design-Algorithmen, die in Settings mit additivem Rauschen oft erforderlich sind.

Die Autoren schließen, dass ihre Ergebnisse für $p \le 2$ bei bekannter Kovarianz optimal (bis auf Logarithmen) sind, während der Fall unbekannter Kovarianz eine offene Lücke (den Term $T^{1/3}$) lässt, die zukünftige Arbeiten adressieren könnten. Sie lassen zudem die Entwicklung eines Algorithmus, der die untere Schranke für $p > 2$ erreicht, als offene Frage zurück.