Introduction
In the field of online learning, multi-armed bandit problems are typically categorized into two distinct environments: the stochastic regime and the adversarial regime. In the stochastic setting, rewards follow a fixed distribution, and algorithms aim for "gap-dependent" regret that grows logarithmically with time ($T$). Conversely, in the adversarial setting, rewards are chosen by an opponent, and the goal is to achieve regret that grows with $\sqrt{T}$.
The "Best-of-Both-Worlds" (BoBW) challenge seeks to develop a single algorithm capable of automatically adapting to either environment without prior knowledge. While significant progress has been made for simpler bandit models, extending these results to Linear Contextual Bandits has proven difficult. In this setting, the learner observes a context (feature vector), and the reward is a linear function of that context. Previous BoBW approaches for linear contextual bandits were often computationally intractable or required advance knowledge of the context distribution's covariance matrix.
Algorithmic Frameworks
This research introduces the first computationally efficient algorithms for linear contextual bandits that achieve near-optimal performance in both regimes simultaneously. The authors propose two main frameworks:
MWU-LC (Continuous Multiplicative Weight Update)
This algorithm utilizes a black-box reduction framework to achieve "data-dependent" bounds. It is particularly effective when the best action has a small cumulative loss (first-order) or small variance (second-order). However, its primary drawback is the requirement of the inverse covariance matrix ($\Sigma^{-1}$) of the context distribution.
FTRL-LC (FTRL with Shannon Entropy)
A more practical approach, FTRL-LC employs Follow-the-Regularized-Leader with Shannon entropy and an adaptive learning rate. To address the challenge of an unknown covariance matrix, the authors integrate Matrix Geometric Resampling (MGR). MGR allows the algorithm to estimate $\Sigma^{-1}$ on the fly. A key contribution of this work is the analysis of how to handle the bias introduced by this estimation while maintaining BoBW guarantees.
Theoretical Results
The proposed algorithms provide strong theoretical guarantees across different environments. The following table summarizes the regret bounds achieved by the new methods (Proposition 8, Theorem 1, Corollary 1, and Theorem 2) in comparison to existing literature.
Key Performance Metrics
- Stochastic Regime: The algorithms achieve polylogarithmic regret, specifically $O(\frac{(dK)^2 \text{polyln}(dKT)}{\Delta_{min}})$, where $d$ is the dimension, $K$ is the number of arms, and $\Delta_{min}$ is the suboptimality gap.
- Adversarial Regime: MWU-LC achieves first-order bounds of $\tilde{O}(dK\sqrt{L^*})$, where $L^*$ is the loss of the best action. FTRL-LC achieves a worst-case bound of $\tilde{O}(dK\sqrt{T})$ without requiring knowledge of the context distribution.
- Robustness: The algorithms are also robust to the "corrupted stochastic" regime, where a stochastic process is partially influenced by an adversary. In this case, the regret depends on the square root of the corruption level ($\sqrt{C}$).
Insights and Limitations
The efficiency of these algorithms stems from focusing on the linear structure of rewards rather than competing against an exponential set of policies. This focus enables polynomial-time complexity in both $d$ and $K$. The integration of MGR is particularly noteworthy; by adaptively choosing the number of resampling steps, the authors successfully control the bias of loss estimators, preserving logarithmic regret in stochastic settings without compromising adversarial performance.
Despite these advancements, some limitations remain. The stochastic regret bounds contain higher-order logarithmic factors, suggesting that alternative regularizers might yield tighter results. Additionally, while FTRL-LC does not need the full covariance matrix, it still requires the minimum eigenvalue ($\lambda_{min}(\Sigma)$) for parameter tuning. Removing this requirement remains an open challenge for future research.
Summary updated