Contextual Bandits with Arm Request Costs and Delays

Lai Wei, Ambuj Tewari, Michael A. Cianfrocco

Introduction

Standard contextual bandit models typically assume that actions are instantaneous and that the primary goal is to maximize the sum of rewards. However, in many real-world scientific and industrial settings, taking an action incurs a non-negligible time cost or "latency." This paper introduces a novel framework for latency-aware contextual bandits, specifically designed to handle scenarios where moving between decision sets is expensive compared to taking actions within them.

The Latency-Aware Bandit Problem

In high-throughput applications like cryogenic electron microscopy (cryo-EM), a microscope must navigate a sample grid to collect high-resolution images of proteins. This process involves a hierarchy of decisions: selecting a square on the grid and then selecting specific "holes" within that square to image.

Hierarchical data collection in Cryo-EM: from grid-level navigation to high-resolution micrographs.

The critical bottleneck is the "setup cost"—the time it takes to move the microscope stage to a new square ($T_{mov}$). Once at a square, taking multiple exposures ($T_{exp}$) is relatively fast. A standard bandit would ignore $T_{mov}$, potentially leading to inefficient "stage-hopping." The authors frame this as a semi-Markov Decision Process (SMDP), where the objective is to maximize the average reward per unit of time rather than the total reward per round.

Methodology: The COAF Algorithm

The core contribution is the Contextual Online Arm Filtering (COAF) algorithm. COAF addresses the trade-off between the overhead of moving to a new context and the diminishing returns of staying in the current one.

Key Components:

  • Average Reward Estimation: COAF uses stochastic approximation to estimate the maximum achievable average reward ($\Gamma$) across the entire session.
  • Subset Selection: Instead of picking a single "best" arm, the algorithm selects an optimal subset of arms from the current decision set. It minimizes a "gap" function that weighs the expected reward of an arm against the estimated average reward $\Gamma$ multiplied by the time cost of that action.
  • Optimism Under Uncertainty: By incorporating Upper Confidence Bounds (UCB), COAF ensures efficient exploration of arms with uncertain reward profiles.

The authors prove that COAF achieves a regret bound of $O(\sqrt{T} \log T)$ for linear reward models, matching the theoretical performance of standard contextual bandits that ignore latency.

Experimental Validation

The researchers evaluated COAF using both synthetic simulations and real-world datasets.

MovieLens 1M

Using the MovieLens recommendation dataset, the authors simulated a scenario where recommending a movie incurs a specific time cost. COAF consistently outperformed fixed-threshold baselines and Thompson Sampling variants, demonstrating its ability to adaptively decide how many recommendations to make based on the "setup cost" of the user context.

Cryo-EM Automation

The most significant impact was seen in automated cryo-EM data collection. By simulating the physical constraints of a microscope (stage movement, exposure times, and low-res previews), COAF was compared against human expert performance. The algorithm collected more high-quality micrographs within the same time window, and the 3D protein structures reconstructed from COAF-selected data achieved higher resolutions (e.g., 4.43 Å) compared to those from human-guided sessions (4.48 Å).

Conclusion

By integrating time costs directly into the bandit framework, this work bridges the gap between theoretical reinforcement learning and the practical needs of laboratory automation. The COAF algorithm provides a robust, theoretically grounded method for maximizing scientific throughput in environments where the clock is just as important as the data.

Summary updated

Abstract

We introduce a latency-aware contextual bandit framework that generalizes the standard contextual bandit problem, where the learner adaptively selects arms and switches decision sets under action delays. In this setting, the learner observes the context and may select multiple arms from a decision set, with the total time determined by the selected subset. The problem can be framed as a special case of semi-Markov decision processes (SMDPs), where contexts and latencies are drawn from an unknown distribution. Leveraging the Bellman optimality equation, we design the contextual online arm filtering (COAF) algorithm, which balances exploration, exploitation, and action latency to minimize regret relative to the optimal average-reward policy. We analyze the algorithm and show that its regret upper bounds match established results in the contextual bandit literature. In numerical experiments on a movie recommendation dataset and cryogenic electron microscopy (cryo-EM) data, we demonstrate that our approach efficiently maximizes cumulative reward over time.
BibTeX
@misc{wei2024contextual,
  author = {Lai Wei and Ambuj Tewari and Michael A. Cianfrocco},
  title = {{Contextual Bandits with Arm Request Costs and Delays}},
  year = {2024},
  eprint = {2410.13109},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.13109},
}
Figure