Robust Best-arm Identification in Linear Bandits

Wei Wang, Sattar Vakili, Ilija BogunovicarXiv 2023 · DOI · arXiv

Introduction

In safety-critical domains like medicine and engineering, simulators are indispensable tools for decision-making. However, a common pitfall is the "fragility" of optimal solutions: an arm (e.g., a drug dosage) that performs best in a simulator might fail catastrophically in the real world due to minor environmental shifts or modeling errors. This paper introduces a framework for Robust Best-Arm Identification (RBAI) in linear bandits, specifically designed to find solutions that remain resilient under adversarial perturbations.

The RBAI Problem

Standard Best-Arm Identification (BAI) aims to find the arm with the highest average reward. In contrast, RBAI seeks the arm $x^*$ that maximizes the worst-case reward under potential perturbations $y$. Mathematically, the goal is to identify $x^* = \arg \max_x \min_y (x-y)^\top \theta$. This minimax approach is crucial for reliable sim-to-real transfer, ensuring that strategies optimized in simulation are robust enough for real-world deployment.

The RBAI framework: using a simulator to identify robust actions for real-world deployment.

Methodology: Robust RAGE

The authors provide the first instance-dependent lower bounds for RBAI, establishing a theoretical limit on the samples required based on the specific difficulty of the arm set. To meet this challenge, they propose Robust RAGE (Robust Adaptive Gap Elimination), an algorithm that identifies the best robust arm with near-optimal efficiency.

Robust RAGE operates iteratively:

  1. Allocation: It calculates an optimal sampling distribution based on the current set of candidate arms.
  2. Sampling: It collects noisy reward observations.
  3. Elimination: It prunes arms that are statistically guaranteed to be sub-optimal in their worst-case performance.

This adaptive process allows the algorithm to focus its sampling budget on the most promising "robust" candidates rather than wasting resources on clearly inferior arms.

Experimental Evaluation

The performance of Robust RAGE was evaluated across three environments: synthetic tests involving Irrelevant Dimensions and a Unit Sphere geometry, and a high-fidelity UVA/Padova Type 1 Diabetes Simulator. In the clinical simulation, "arms" represented insulin dose parameters, while the "adversary" modeled inaccuracies in standard calculations.

Key Results

In synthetic benchmarks, Robust RAGE demonstrated significant improvements in sample efficiency compared to static allocation methods. As shown in the figures below, its sample complexity remains close to that of an "Oracle" algorithm (which knows the true parameters) and scales much better than non-adaptive baselines as the problem dimension or number of arms increases.

Sample complexity of Robust RAGE compared to baselines in synthetic environments.

In clinical simulations, the RBAI-tuned calculator significantly outperformed standard clinical formulas. It reduced the Risk Index (from 4.07 to 3.77) and decreased the incidence of hypoglycemia while increasing the time patients spent in the healthy euglycemic range (87.17% vs 85.29%).

Conclusion and Future Directions

Robust RAGE bridges the gap between theoretical optimality and practical utility in robust decision-making. While currently limited to linear reward models and discrete arm sets, it provides a rigorous foundation for future work. Potential extensions include handling non-linear systems and continuous action spaces, further enhancing the safety and reliability of autonomous systems in unpredictable environments.

Summary updated

BibTeX
@misc{wang2023robust,
  author = {Wei Wang and Sattar Vakili and Ilija Bogunovic},
  title = {{Robust Best-arm Identification in Linear Bandits}},
  year = {2023},
  eprint = {2311.04731},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.04731},
}
Figure