Best of both worlds: Stochastic & adversarial best-arm identification

2026-04-17 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

A new study submitted to arXiv on April 16, 2026, investigates best-arm identification in bandit problems with arbitrary and potentially adversarial rewards. While a simple uniform random learner achieves optimal error rates in adversarial scenarios, it performs suboptimally with stochastic rewards. The research explores the feasibility of designing a single learner that performs optimally in both stochastic and adversarial reward environments without prior knowledge of the reward nature. The authors demonstrate that such a universal learner is generally impossible, establishing that robustness to adversarial rewards limits optimal error rates to a subset of stochastic problems. They provide a lower bound characterizing the optimal rate under this constraint and introduce a simple, parameter-free algorithm that matches this lower bound (up to log factors) in stochastic problems while maintaining robustness to adversarial rewards.

Key takeaway

For research scientists developing bandit algorithms, you should recognize the inherent trade-off between optimal performance in stochastic versus adversarial reward settings. Your design choices must prioritize either robustness or stochastic optimality, as a single universally optimal learner is not feasible. Consider implementing the proposed parameter-free algorithm when facing environments with unknown or mixed reward characteristics to achieve a "best of both worlds" performance profile.

Key insights

Optimal best-arm identification across both stochastic and adversarial bandit rewards is generally impossible.

Principles

• Adversarial robustness limits stochastic optimality.
• Uniform random learners are suboptimal for stochastic rewards.

Method

The paper designs a parameter-free algorithm that achieves near-optimal error rates in stochastic bandit problems, matching a derived lower bound, while also being robust to adversarial rewards.

In practice

• Consider reward nature when selecting bandit strategies.
• Use the proposed algorithm for mixed reward environments.

Topics

• Best-Arm Identification
• Bandit Algorithms
• Stochastic Rewards
• Adversarial Rewards
• Optimal Rates

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Best of both worlds: Stochastic & adversarial best-arm identification — Designing a single optimal learner for both stochastic and adversarial bandit best-arm identification is generally impossible.
• Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses — This work extends adversarial bandit optimization to general convex and β-smooth losses with globally bounded post-action perturbations.
• An Anytime Algorithm for Good Arm Identification — APGAI offers an adaptive, anytime, and parameter-free solution for Good Arm Identification in stochastic bandits.
• Not all uncertainty is alike: volatility, stochasticity, and exploration — Optimal exploration is enhanced by volatility but suppressed by stochasticity, challenging the "more uncertainty, more exploration" paradigm.
• Batched Single-Index Global Multi-Armed Bandits with Covariates — BIDS is a novel batched multi-armed bandit algorithm that uses single-index regression to efficiently manage covariates and related arm rewards.
• Sharp analysis of linear ensemble sampling — Linear ensemble sampling achieves near Thompson sampling regret in linear bandits using a novel continuous-time analysis.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.