Introduction
This paper introduces novel algorithms for adversarial linear bandits that achieve tight first- and second-order regret bounds. These algorithms perform exceptionally well in "easy" environments—such as those with low variance or small cumulative loss—while maintaining worst-case optimality. By combining continuous multiplicative weight updates with a novel "distribution truncation" technique, the authors eliminate the need for restrictive assumptions found in prior work. This allows the algorithms to work efficiently even on discrete action sets without prior knowledge of the environment.
The Challenge of Adversarial Linear Bandits
In the adversarial linear bandit problem, a player sequentially chooses actions (represented as vectors) and suffers a loss determined by an adversary. The player only observes the loss of the chosen action, not the full loss vector. Standard algorithms achieve a worst-case regret bound of $\tilde{O}(d\sqrt{T})$, where $d$ is the dimension and $T$ is the number of rounds.
However, real-world environments are rarely purely adversarial. If an environment is relatively benign—for instance, if there is a clear optimal action with a very small cumulative loss, or if the loss vectors do not vary much over time—algorithms should ideally exploit this to achieve much lower regret. Existing algorithms that achieve these adaptive "first-order" (dependent on cumulative loss) or "second-order" (dependent on loss variance) bounds require strong, restrictive assumptions. They typically assume the action set is continuous and convex, require a self-concordant barrier, or demand prior knowledge of the loss variance. This paper tackles the challenge of achieving these advanced, adaptive regret bounds without relying on such restrictive assumptions.
Methods: Distribution Truncation
The authors build upon the Continuous Multiplicative Weight Update (MWU) method over the convex hull of the action set, combined with Optimistic Online Optimization, which uses predicted loss vectors to reduce the variance of loss estimators.
The core methodological breakthrough is a technique called Distribution Truncation. In adversarial bandits, algorithms must construct an unbiased estimator of the hidden loss vector. To ensure this estimator is stable (i.e., doesn't have wildly high variance), previous approaches mixed the MWU distribution with a uniform exploration distribution. However, this forced exploration inherently degrades performance.
Instead of mixing, the authors truncate the support of the MWU distribution. Because the MWU maintains a log-concave distribution, the authors use the concentration properties of log-concave distributions to prove that simply cutting off the extreme "tails" of the distribution controls the magnitude of the chosen actions. This stabilizes the unbiased loss estimator without the performance penalty of forced mixing.
Key Insights
- Truncation beats mixing: The realization that you can stabilize unbiased loss estimators by truncating a log-concave distribution, rather than mixing it with an explicit exploration distribution, is a major theoretical win. It removes a standard bottleneck in bandit algorithm design.
- Simultaneous guarantees: By smartly computing a predicted loss vector $m_t$ on the fly using an online ridge regression subroutine, a single algorithm can simultaneously achieve both first-order and second-order regret bounds.
- Relaxed assumptions unlock discrete action spaces: Because the algorithm only requires a standard linear optimization oracle (rather than a self-concordant barrier), it can be seamlessly applied to discrete action sets (like combinatorial routing problems), which was a significant limitation of prior second-order algorithms.
Key Results and Regret Bounds
The authors provide rigorous mathematical proofs for their algorithm, yielding several main results that match theoretical lower bounds up to polylogarithmic factors.
- Predictable Sequence Bound: Achieved a regret bound of $\tilde{O}(d\sqrt{\sum \langle \ell_t - m_t, a_t \rangle^2})$, showing the algorithm adapts perfectly when given good predictions ($m_t$) of the loss ($\ell_t$).
- Second-Order Bound: Achieved a variance-dependent regret bound of $\tilde{O}(d\sqrt{\sum \|\ell_t - \bar{\ell}\|_*^2})$, meaning regret shrinks if the losses don't deviate much from their average.
- First-Order Bound: For non-negative losses, the algorithm achieves $\tilde{O}(d\sqrt{\sum \langle \ell_t, a^* \rangle})$, meaning regret is small if the best action has a small cumulative loss.
- Matching Lower Bounds: The authors proved a lower bound of $\Omega(d\sqrt{L})$, demonstrating that their proposed upper bounds are mathematically tight up to polylogarithmic factors for general linear bandits.
Limitations and Future Work
While the bounds are tight for general linear bandits, they are not perfectly tight for the specific sub-case of standard Multi-Armed Bandits (MAB). MAB-specific algorithms can achieve bounds that scale better with the dimension $d$. Furthermore, although the algorithm runs in theoretical polynomial time, sampling from log-concave distributions for continuous MWU is computationally heavy in practice.
The authors suggest two main avenues for future work: improving the practical computational efficiency of the algorithm, and exploring "path-length" regret bounds, where regret depends on how much the loss changes from one round to the next, rather than just variance from the mean.
Summary updated