Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention

Junwen Yang, Tianyuan Jin, Vincent Y. F. Tan

TL;DR

This paper introduces a novel extension to the multi-armed bandit (MAB) problem by adding an "abstention" option, allowing agents to observe an arm's outcome without fully committing to its stochastic reward or regret. The authors develop algorithms that achieve both asymptotic and minimax optimality, proving that "safe exploration" can significantly reduce cumulative regret in scenarios like clinical trials and online advertising.

What Problem Does This Paper Address?

In the classic stochastic multi-armed bandit model, an agent faces a fundamental trade-off: exploration (trying new arms to learn their value) vs. exploitation (pulling the best-known arm). The catch is that every exploratory pull is a gamble; if the arm is poor, the agent suffers the full weight of that suboptimality.

However, real-world decision-making often includes a "safety valve." Consider a clinical trial for a risky new treatment. Researchers might use preemptive medications or insurance to shield against negative outcomes. They still see how the patient reacts (learning), but the "cost" of a bad reaction is mitigated by the safeguard (abstention). Similarly, in advertising, a company might opt for a "cost-per-action" model—paying a fixed price for a guaranteed outcome—rather than risking uncertain returns on a "cost-per-click" basis.

The authors formalize this as Multi-Armed Bandits with Abstention. The core challenge is determining when to use this abstention option to maximize rewards while still gathering enough information to eventually identify the optimal arm.

Methods

The authors explore two primary settings, illustrated in the interaction protocol below:

Figure 1: Interaction protocol for multi-armed bandits with fixed-regret and fixed-reward abstention.
  1. Fixed-Regret Setting: Choosing to abstain results in a constant, known regret $c$. The agent pulls an arm $A_t$, observes the outcome $X_t$, but if they chose to abstain ($B_t=1$), they incur regret $c$ instead of the usual $\mu_1 - X_t$.
  2. Fixed-Reward Setting: Abstaining yields a deterministic reward $c$. The agent receives $\max\{\mu_1, c\} - c$ in regret if they abstain.

The Algorithms

  • FRG-TSwA (Fixed-Regret Thompson Sampling with Abstention): This algorithm builds on "Less-Exploring Thompson Sampling." It uses two criteria for abstention: a gap-dependent rule using a custom Lower Confidence Bound (LCB) to detect if an arm is likely much worse than the best arm, and a gap-independent rule that triggers abstention during early time steps when it is theoretically "cheap" to do so.
  • FRW-ALGwA (Fixed-Reward Algorithm with Abstention): This is a more general "meta-algorithm." It can wrap any standard optimal bandit algorithm (like KL-UCB++). It simply pulls the arm suggested by the base algorithm but chooses to abstain if that arm's empirical mean is lower than the fixed reward $c$.

Datasets

The paper relies on synthetic and randomized bandit environments to validate the theory:

  • Synthetic Instances: Two specific configurations ($\mu^\dagger$ with $K=7$ arms and $\mu^\ddagger$ with $K=10$ arms) with varying suboptimality gaps.
  • Random Instances: Larger-scale tests with $K=20$ and $K=30$ arms, where suboptimal arm means are drawn from a uniform distribution.

Key Insights and Ideas

  • Decoupling Learning from Reward: The most significant insight is that abstention allows for "safe exploration." In standard bandits, you must "pay to learn." Here, you can pull a risky arm to get information (the observation $X_t$) while shielding yourself from the potential loss by choosing the abstention reward/regret.
  • Phase Transitions in Regret: In the fixed-regret setting, the authors identified a phase transition. If the cost of abstaining ($c$) is very low, it’s always better to abstain early. If it’s high, the agent behaves more like a classic bandit.
  • Dual Optimality: The proposed algorithms are "best of both worlds." They achieve asymptotic optimality (performing as well as possible for a specific instance over an infinite horizon) and minimax optimality (minimizing the worst-case regret across all possible instances).

Key Results

  • Theoretical Bounds: The authors proved that their algorithms match the information-theoretic lower bounds. Specifically, the minimax regret is $O(\sqrt{KT} \wedge cT)$.
  • Superiority over Baselines: In numerical experiments, FRG-TSwA significantly outperformed standard "Less-Exploring Thompson Sampling." As the time horizon $T$ increased, the empirical regret of the new algorithm closely tracked the theoretical lower bound, proving its efficiency.
  • Practical Benefit: The experiments showed that even when the abstention cost $c$ is relatively high, the agent still benefits from the option because it can estimate suboptimality gaps "on the fly" and use abstention as a hedge against uncertainty.

Limitations and Future Work

  • Gaussian Assumption: The current analysis focuses primarily on Gaussian reward distributions. While the authors suggest the framework extends to others, specific boundary cases require more care.
  • Linear Bandits: A major open question is how to apply this to linear bandits, where pulling one arm provides information about many others. The authors note that the "independence" of arms in the K-armed model makes the current strategy work, but linear dependencies would complicate the abstention logic.
  • Observation Impact: Currently, abstaining does not change the observation $X_t$. Future work could explore models where the act of safeguarding or abstaining actually alters the information the agent receives.

Summary updated

Abstract

We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic innovation: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the stochastic instantaneous reward before observing it. When opting for abstention, the agent either suffers a fixed regret or gains a guaranteed reward. This added layer of complexity naturally prompts the key question: can we develop algorithms that are both computationally efficient and asymptotically and minimax optimal in this setting? We answer this question in the affirmative by designing and analyzing algorithms whose regrets meet their corresponding information-theoretic lower bounds. Our results offer valuable quantitative insights into the benefits of the abstention option, laying the groundwork for further exploration in other online decision-making problems with such an option. Extensive numerical experiments validate our theoretical results, demonstrating that our approach not only advances theory but also has the potential to deliver significant practical benefits.
BibTeX
@article{yang2026asymptotically,
  author = {Junwen Yang and Tianyuan Jin and Vincent Y. F. Tan},
  title = {{Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention}},
  journal = {Accepted by TMLR},
  year = {2026},
  url = {https://openreview.net/forum?id=AYp5zOcFdA},
}
Figure