An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Technical Summary: An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Problem Definition

The paper addresses the adversarial linear contextual bandit problem. In this setting, an oblivious adversary selects a sequence of hidden loss vectors $\theta_t \in \mathbb{R}^d$ before the interaction begins. In each round $t$, an action set $A_t \subset \mathbb{R}^d$ is drawn i.i.d. from a fixed but unknown distribution $\mathcal{D}$ and revealed to the learner. The learner must select an action $a_t \in A_t$ and incurs a loss $\ell_t$ with expectation $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. The goal is to minimize regret against the best fixed policy $\pi$, where a policy maps any observed action set $A$ to a point in its convex hull $\text{conv}(A)$.

This setting generalizes classical linear bandits by allowing the action sets (contexts) to vary stochastically over time, while the losses remain adversarial. A critical challenge is that the distribution $\mathcal{D}$ is unknown, and the learner does not have access to a simulator that can generate free samples from $\mathcal{D}$. Furthermore, the number of possible actions $K$ can be exponentially large in the dimension $d$ (e.g., in combinatorial problems like shortest paths), making algorithms with complexity polynomial in $K$ infeasible.

Methodology

The core contribution is a computationally efficient reduction that transforms the adversarial linear contextual bandit problem into a misspecification-robust adversarial linear bandit problem with a fixed action set.

1. Reduction to Fixed Action Sets:
   The authors define a mapping $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, which maps a policy $\pi$ to its mean action. Since $\mathcal{D}$ is unknown, the true set of mean actions $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ cannot be accessed directly. Instead, the algorithm constructs an empirical approximation $\hat{\Omega}$ using $N$ i.i.d. samples of action sets drawn from $\mathcal{D}$.

   • $\hat{\Omega}$ is defined as the Minkowski sum of the convex hulls of the sampled action sets: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • The reduction relies on the fact that for linear classifier policies, the difference between the expected loss on the true distribution and the empirical distribution is small (uniform convergence), provided $N$ is sufficiently large.

2. Handling Discrepancy via Misspecification Robustness:
   Because the learner operates on $\hat{\Omega}$ rather than $\Omega$, the feedback received by the underlying linear bandit algorithm is "misspecified." Specifically, the expected loss observed by the linear bandit algorithm differs from the true expected loss by a bounded error term $\epsilon$.

   • The authors utilize a $\alpha$-misspecification-robust adversarial linear bandit algorithm as a black box. This algorithm guarantees low regret even when the feedback satisfies $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • To execute a point $y_t \in \hat{\Omega}$ suggested by the linear bandit algorithm, the learner uses a Frank-Wolfe-based decomposition (Algorithm 2) to express $y_t$ as a convex combination of points on the boundary of $\hat{\Omega}$. These boundary points correspond to linear classifier policies $\pi_\phi$, which can be executed using a linear optimization oracle for the individual action sets $A_t$.

3. Algorithmic Components:

   • Algorithm 1: The main framework that interacts with the environment, decomposes the linear bandit's suggestion into a mixture of linear policies, and feeds the resulting loss back to the linear bandit algorithm.
   • Algorithm 3 (Misspecification-Robust Continuous Exponential Weights): A specific instantiation of the robust linear bandit algorithm. It adapts the clipped continuous exponential weights method (Ito et al., 2020) by adding a "bonus term" $b_t$ to the loss estimator. This bonus encourages exploration and offsets the regret overhead caused by misspecification.
   • Doubling Trick: To handle the unknown optimal sample size $N$, the algorithm employs a doubling trick, restarting the process at epochs $2, 4, 8, \dots$ and using all accumulated context samples to refine $\hat{\Omega}$.

Key Contributions

• Oracle-Efficient Algorithm: The paper presents the first algorithm for adversarial linear contextual bandits with stochastic action sets that achieves regret bounds independent of the number of actions $K$ in its computational complexity. It only requires a linear optimization oracle for the individual action sets in each round.
• Combinatorial Applicability: The method is the first to achieve $\text{poly}(d)\sqrt{T}$ regret in polynomial time for combinatorial bandits with stochastic action sets and adversarial losses. Prior algorithms either required semi-bandit feedback or had computational complexity scaling polynomially with $K$ (which is exponential in $d$ for many problems).
• Novel Reduction: The work establishes a polynomial-time reduction from adversarial linear contextual bandits to misspecification-robust linear bandits. Unlike previous reductions (e.g., Hanna et al., 2023) which focused on stochastic settings or lacked polynomial-time implementations, this reduction operates under adversarial losses and is computationally efficient.

Results

The algorithm achieves the following regret bounds (ignoring logarithmic factors):

• Without Simulator: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • This resolves an open question by Liu et al. (2023) regarding whether $\text{poly}(d)\sqrt{T}$ regret is achievable in polynomial time independent of $K$.
  • The computational complexity is $\text{poly}(d, T)$ plus $\text{poly}(d, T)$ calls to the linear optimization oracle.
• With Simulator: If the learner has access to a simulator that can generate free contexts, the regret bound improves to $\tilde{O}(d\sqrt{L^*})$, where $L^*$ is the cumulative loss of the best policy. This is a first-order bound that adapts to the difficulty of the problem instance.

Significance and Claims

The authors claim this work provides a general framework that significantly broadens the applicability of adversarial linear contextual bandits to problems with exponentially large action spaces (e.g., shortest path, flow, bipartite matching) without requiring knowledge of the context distribution or a simulator.

The paper explicitly notes that while the bound $\tilde{O}(d^2\sqrt{T})$ is an improvement over previous polynomial-time results dependent on $K$, it remains an open question whether the near-optimal $\tilde{O}(d\sqrt{T})$ bound can be achieved without a simulator in polynomial time. The authors also highlight that their approach removes the unrealistic assumption of log-concave context distributions required by some prior work (Olkhovskaya et al., 2023) when specialized to certain formulations. Finally, they suggest the reduction framework may be applicable to other settings, such as linear MDPs with fixed transitions and adversarial losses.