Robust Pure Exploration in Linear Bandits with Limited Budget

Ayya Alieva, Ashok Cutkosky, Abhimanyu DasICML 2021 · OpenReview

This mini-paper summarizes the research "Robust Pure Exploration in Linear Bandits with Limited Budget" by Alieva, Cutkosky, and Das, originally presented at ICML 2021.

TL;DR

The authors introduce LinearExploration, a novel algorithm for identifying the best option (or "arm") in a linear bandit setting within a strict, fixed trial budget. Uniquely, it is robust to unknown noise levels and model misspecification, scaling its sample complexity with the problem's underlying dimensionality rather than the total number of available choices.

The Problem: Fixed-Budget Pure Exploration

In many real-world scenarios—such as tuning hyperparameters for a machine learning model or selecting the optimal ad to display—practitioners have a limited "exploration budget" (e.g., 1,000 trials) to identify the best performer before making a final, permanent decision. This challenge is known as the fixed-budget pure exploration problem.

While standard Multi-Armed Bandit (MAB) algorithms treat every choice as completely independent, Linear Bandits assume that choices possess underlying features and that their rewards follow a linear model ($y = \langle \theta, x \rangle$). This structure allows an algorithm to learn about one choice by testing a similar one.

However, most existing linear bandit algorithms are fragile: they fail if the linear assumption is even slightly wrong (model misspecification) or if they lack exact knowledge of the environment's noise level. This paper tackles the challenge of designing an algorithm that is "linear-aware" to exploit structure, yet robust to the "messiness" of real-world data.

Methods: The LinearExploration Algorithm

The authors propose LinearExploration, an algorithm built on two primary pillars:

  1. Sequential Halving: A classic strategy where the algorithm proceeds in rounds. In each round, it pulls a set of arms, estimates their rewards, and discards the bottom 50% of performers.
  2. Optimal Experimental Design (OptDesign): Instead of pulling arms uniformly, the algorithm uses experimental design techniques to select a subset of arms that provides the maximum information about the entire set. Specifically, it employs an algorithm by Allen-Zhu et al. (2017) to minimize the variance of the reward estimates obtained via linear regression.

What makes it novel? Unlike prior work, LinearExploration does not require the user to input the noise variance ($\sigma^2$) or the level of model misspecification ($\gamma$). It is entirely adaptive. If the linear model is perfect, it leverages that structure to find the best arm rapidly. If the model is highly misspecified, it "decays gracefully," performing no worse than standard algorithms that ignore the linear structure entirely.

Experimental Setup

The researchers evaluated their algorithm using synthetic datasets designed to test different geometric arrangements of arms:

  • Uniform: Arms sampled uniformly from a hypercube.
  • Gaussian Mixture: Arms clustered around three different means.
  • Clusters: Arms sampled from two very tight, opposing clusters (designed as a "hard" instance).
  • Subspace: Arms lying close to a lower-dimensional subspace.

Key Insights

  • Dimension over Cardinality: The algorithm's performance depends on the dimension of the feature space ($d$) rather than the total number of arms ($n$). This is a massive advantage when choosing from thousands or millions of options.
  • Handling "Lies": The paper explicitly accounts for misspecification ($y = \langle \theta, x \rangle + \gamma$). The authors prove that as long as the "lie" ($\gamma$) isn't larger than the gap between the best and second-best arm (scaled by $\sqrt{d}$), the algorithm can still successfully identify the winner.
  • The "Right" Geometry: The authors define a new complexity measure, $\tilde{H}_2$, which captures how difficult a linear bandit instance is based on both the reward gaps and the geometric layout of the arms.

Key Results

Theoretically, the paper contributes a bound on the probability of error that is nearly tight with the lower bounds they provide.

Empirically, LinearExploration consistently outperformed baselines like BayesGap, Successive Halving, and XY-Allocation across various geometries.

Performance across different arm distributions.

Furthermore, the algorithm proved remarkably robust. While its performance naturally dips as the model becomes more misspecified or as the number of dimensions increases, it maintains a lead over other linear-aware methods and significantly outperforms the non-linear Successive Halving baseline.

Robustness to misspecification and dimensionality.

Limitations and Future Work

  • Misspecification Threshold: The current theory requires the misspecification to be relatively small compared to the reward gaps. Relaxing this requirement is a prime target for future work.
  • Infinite Arms: While the paper provides a theoretical extension for an infinite number of arms (using a covering argument), the resulting algorithm is computationally inefficient. Developing a practical version for continuous action spaces remains an open challenge.
  • Tightness of Gaps: There is still a small logarithmic gap between the upper and lower bounds that future research could aim to close.

Summary updated

Abstract

We consider the pure exploration problem in the fixed-budget linear bandit setting. We provide a new algorithm that identifies the best arm with high probability while being robust to unknown level...
BibTeX
@inproceedings{alieva2021robust,
  author = {Ayya Alieva and Ashok Cutkosky and Abhimanyu Das},
  title = {{Robust Pure Exploration in Linear Bandits with Limited Budget}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=_HEQnlW7fSV},
}
Figure