Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention
Authors: Junwen Yang
Tianyuan Jin
Vincent Y. F. Tan
Venue: Accepted by TMLR ()

Abstract: We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic innovation: \emph{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 {\em 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.

Published in Transactions on Machine Learning Research (04/2026)
Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention
Junwen Yang
junwen Sa.
Institute of Operations Research and Anolytics National University of Singapore
Tianyuan Jin
tianyuan Cu.mus. mus. edu
Department Electrical and Computer Engineering National University of Singapore
Vincent Y. F. Tan
vtan Stars.ruu..oo hew.uus.ssuu.... edu.sg
Department of Mathematics Department Electrical and Computer Engineering Institute of Operations Research and Analytics National University of Singapore
Reviewed on OpenReview: https: // openreview.ew net/ farum? id= AVp5zccFA
Abstract
We introduce a novel extension of the canonical multi- nulti-armed bandit problem that incorpo- rates additional strategic innovation: abstention. In this enhanced framework, the agent is not only tasked with selecting arm at cach time step, but also has the option to abstain from accepting the stochastic instanlaneous reward before observing it. When opting for abstention, the agent either suffers a fixed regret or gains guaranteed reward. This added layer of complexity naturally prompts the koy 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-theorriiee 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.
1 Introduction
In online decision-making, the multi-armed bandit model, originally introduced by Thompson 1933 has long served as a quintessential benchmark for capturing the delicate interplay between exploration and exploitation. In stochastic multi-armed bandit problems, the agent sequentially selects an arm from the given set each time step and subsequently observes a random reward associated with the chosen arm. To maximize cumulative rewards, the agent must strike a balance between the persistent pursuit of the arm with the highest estimated reward (exploitation) and the adventurous exploration of other arms to gain a deeper understanding of their potential (exploration). This fundamental challenge finds applications across wide array of domains, ranging from optimizing advertising campaigns to fine-tuning recommendation systems.
However, real-world scenarios often come fraught with complexilies that challenge the simplicity of the canonical bandit model. One notable complexity arises when the agent equipped with an additional option abstain from accepting the stochastic instantancous reward before observing it. This added layer of prreisionmmainng enriches the strategic landscape, altering how the agent optimally navigates the trade-off between exploration and exploitation.

---

Published in Transactions on Machine Learning Research (04/2026)
Consider clinical trials, where concerns about participant harm, insurance, and compensation prominent issues discussed in the literature; see, for example, Steinbrook (2006); Munshi & Thatte (2013) No-fault compensation or prophylactic measures (Henry et al.) 2015) allow researchers to observe the response to a potentially hazardous treatment while avoiding exposure to random harmful effects. When evaluating potentially hazardous medical treatments, researchers can proactively deploy saleguards such as preemptive medications or rely on arrangements for insurance or compensation against possible rescarch-related injuries. However, these protective measures come with costs, which may be modeled as either fixed regrets or fixed rewards in the context of the clinical study's cumulative regret. In these scenarios, researchers have the option to observe the outcomes of a treatment while abstaining from incurring the associated random regret through these costly prearranged measures. Subsequently, these observed outcomes can be leveraged to inform more efficacious future experimental designs. Consequently, opting for abstention has the potential to promote more responsible decision- making and reduce the overall cumulative regret of the study.
To further illustrate our motivation, consider another example in online advertising, where companics fre- quently grapple with the challenge of allocating their advertising budget optimally across multiple plat/orms (Google Ads, LinkedIn, etc.) to promote their products. This scenario naturally parallels the framework of multi-armed bandits, with each arm representing distinct advertising platform. Typically, these platforms operate on a cost-per-click pricing model, while performance- based alternatives such as cost-per-action (CPA) pricing have been extensively studied as a mechanism to shift the risk of uncertain consumer behavior from the advertiser to the platform (Nazerzadeh et al., 2008; Hu et al. 2016). As detailed by Hu et al. (2016). CPA models act as a financial safeguard for advertisers by guarantecing that payments are only exacted upon successful downstream conversions, rather than merely clicks. However, what companies truly care about is the outcome, such as conversions purchases, which are random variables sampled from unknown distributions. When faced with such uncertainty and the possibility of underperformance,, companies may instead opt for a cost-per-actioe strategy, which involves a predetermined payment for a specific outcome (i.e., payment is made only when a desired outcome, such as a conversion or purchase, occurs). This strategy essentially serves as an abstention option, where instead of risking uncertain returns (from unknown distri- butions), companies choose to pay a fixed cost for a known outcome. By embracing the abstention option, companies can mitigate the uncertainties associated with stochastic outcomes and ensure a deterministic result. Morcover, by opting for abstention, the company still retains the ability to observe the advertising conversion rate of the platform, enabling them to gather valuable insights for future decision-making,
Building upon this challenge, we introduce an innovative extension to the canonical multi-armed bandit model that incorporates abstention as a legitimate strategic option. At each time step, the agent not only selects which arm to pull but also decides whether to abstain. Depending on how the abstention option impacts the cumulative regret, which the agont's primary optimization objective, our abstention model offers two complementary settings, namely, the fixed-regret setting where abstention results in a constant regret, and the fixed-reward setting where abstention yields deterministic reward. Collectively, these settings provide the agent with a comprehensive toolkit for adeptly navigating the complicated landscape of online decision-making.
Main contributions. Our main results and contributions are summarized follows:
(i) In Scction 2 we provide a rigorous formulation of the multi-armed bandit model with abstention. Our focus is on cumulatiie regret minimization across two distinct yet complementary settings: fired- regret and ftred-reward. These settings give rise to different metrics, each offering unique analytical insights. Importantly, both settings encompass the canonical bandit model as a particular case.
(ii) In the fixed-regret setting, we judicioussy combine two abstention criteria into a Thompson Sampling- based algorithm proposed by Jin et al. (2023). This integration ensures compatibllity with the ab- stention option, as elaborated in Algorithm The first abstention criterion employs a carefully constructed lower confidence bound, while the second is tailored to mitigate worst-cass case scenarios.
We highlight that this example stylized mathematical abstraction used solely to motivate the abstention framework. It. does not capture the complex ethical and practical constraints of actual clinical trials and should not interpreted proposal for real-world medical protocols.
2

---

Published in Transactions on Machine Learning Research (04/2026)
We establish both asymptotic and minimax upper bounds on the cumulative regret, requiring ap- plication of analytical techniques inspired by both Thompson Sampling and UCB methooologies. Furthermore, we derive corresponding lower bounds, thereby showcasing the concurrent attainment of asymptotic and minimax optimality by our algorithm. Our approach entails extensive application of analytical techniques inspired by both Thompson Sampling and UCB methodologies.
(ii) In the fixed-reward setting, we introduce a general strategy, outlined in Algorithm 2 This method transforms any algorithm that is both asymptotically and minimax optimal in the canonical model to one that also accommodates the abstention option. Remarkably, this strategy maintains its universal applicability and straightforward implementation while provably achieving both forms of optimality asymptotic and minimax.
(iv) To corroborate our theoretical contributions, we conduct series of numerical experiments in Ap- pendix F. These experiments substantiate the effectiveness of our algorithms and highlight the performance gains achieved through the inclusion of the abstention option.
1.1 Related Work
Canonical multi-armed bandits. The study of cumulative regret minimization in canonical multi-armed bandits has attracted considerable scholarly focus. Within this domain, two dominant paradigms for evaluat- ing optimality metrics have emerged: asymptotic optimality and minimax optimality. In essence, the former considers the behavior of algorithms as the lime horizon approaches infinity for a specific problem instance, while the latter seeks to minimize the worst-case regret over all possible instances. A diverse array of policies have been rigorously established to achieve asymptotic optimality across various model settings. Notable ex- amples include UCB2 (Auer et al., 2002). DMED (Honda & Takemura 2010), KL-UCB (Cappé et al. 2013). and Thompson Sampling (Agrawal & Goyal 2012: Kaufmann et al. 2012). Tn the context of the worst-case regret, MOSS (Audibert & Bubeck 2009) stands out as the pioneering method that has been verified to be minimax optimal. Remarkably, KL-UCB (Ménard & Garivier 2017 became the first algorithm proved to achieve both asymptotic and minimax optimality. Recently, Jin et al. (2023) introduced Less- Dess-Exploring Thompson Sampling, an innovation that boosts computational efficiency compared to classical Thompson Sampling while concurrently achieving asymptotic and minimax optimality. For a comprehensive survey of bandit algorithms, we refer Lattimore & Szepesvári 2020)).
1970 the concept of learning with abstention (also referred to rejection) has been extensively explored in various machine
Machine learning with abstention. Starting with the seminal work of Chow 1957
learning paradignns. These include classification (Herbei & Wegkamp 2006 Bartlett & Wegkamp
2008
Cortes ct al. 2016), ranking (Cheng et al. 2010 Mao et al. 2023) and regression WWener & El- Yaniv 2012
Zaoui et al. 2020 Kalai & Kanade 2021
Within this broad spectrum of research, our work most directly related to those that explore the role of abstention in the context of online learning. To the best of our knowledge, Cortes et al. (2018) firstly incorporated the abstention option into the problem of online prediction with expert advice (Littlestone & Warmuth 1994). In their model, at each time step, each expert has the option to either make a prediction based on the given input abstain from doing so. When the agent follows the advice of an expert who chooses to abstain, the true label of the input remains undisclosed, and the learner incurs a known fixed loss. Subsequently, Neu & Zhivotovskiy (020)) introduced a different abstention model, which is more similar to ours. Here, the abstention option is only available to the agent. Crucially, the true label is always revealed to the agent after the decision has been made, regardless whether the agent opts to abstain. Their findings suggest that equipping the agent with an abstention option can significantly improve the guarantees on the worst-case regret.
2 Problem Setup
Multi-armed bandits with abstention. We consider K-armed bandit model, enhanced with an ad- ditional option to abstain from accepting the stochastic instantaneous reward prior to its observation. Tet
3

---

Published in Transactions on Machine Learning Research (04/2026)
Ar, Bi
Action
A
B
B, =0
B =
Instantancous Regret
Fixed-
Agent
Environment
M1 X,,
Regret
X
X
Fixed-
Vc-cc- X,
Vi
Reward
Figure 1: Interaction protocol for multi- aatt-- bandits with regret and fixed-rewar abstention.
J E := demole a specific bandit instance, where μa, represents the unknown mean reward of arm i E [K]. We assume that arm 1 is the unique optimal arm, i.e., 1 = arg maX Pi, and we define A := μl #4 as the suboptimality gap for each arm
At each time step & N, the agent chooses an arm A, [K], and, simultaneously, decides whether not to abstain, indicated by binary variable B,. Regardless of the decision to abstain, the agent observes random variable X, from the selected arm A,, which is drawn from a Gaussian distribution ((A,, 1) independent of observations obtained from the previous time steps. Notably, the selection of both A and B. might depend on the previous decisions and observations, as well as on each other. Formally, let F. = (A1, B1, Xi..... Ar, X,) denote the o-filld generated by the cumulative interaction history up to and inchuding time It follows that the pair of random variables (A,, B,) is Fi-1 -eaa-alaura.
The instantancous regret at time is determined by both the binary abstention variable B, and the observa- tion X,. Based the outcome of the abstention option, now discuss two complementary settings. In the fized-regret setting, the abstention option incurs constant regret. Opting for abstention (B, = 1) leads to a deterministic regret of с > 0, in contrast to the initial regret linked to arm A when not selecting abstention which is given by p1 - X₂.
In the fwred-reward setting, the reward of the abstention option E R R Since the abstention reward may be larger than μi, the highest expected reward each time step is μu V := max(pı, c). If the agent decides to abstain (B, = 1), it is guaranteed deterministic reward of c, leading to regret of μn V If B, = 0, the agent receives a reward of X,, resulting in a regret of μn V X₁-
See Figure for a schematic of our model in the two settings.
Remark 1. We note that if the agent cannot observe the sample from the chosen arm when opting for abstention, then it is oquivalent to skipping the time step, rendering the model trivial. In other words, the learner gains no information from the time step but incurs an instantaneous regret. In view of this, our model well aligns with that of Neu & Zhivotovskiy (2020), which explored the role of abstention in the context of online prediction with expert advice.
Remark 2 (Graph Feedback). Bandits with graph feedback (Liu et al. 2018 Alon et al. 2017) are a natural extension of the standard multi-armed bandit setting. In this framework, each arm is represented as a node in graph, and pulling one arm reveals not only its own reward but also observations from the neighboring nodes connected to it in the graph. Our model bears a conceptual resemblance to bandits with graph feedback: it can be represented as bipartite graph in which each stochastic arm a associated with corresponding abstention arm Qu. Pulling stochastic arm reveals reward drawn from arm a's distribution, while choosing the corresponding abstention arm Qa yields an observation drawn from the reward distribution of the associated stochastic arm as well.
That said, there a key structural difference between the two frameworks. In bandits with graph feedback, selecting an arm reveals not only the reward of the chosen arm but also observations from its neighboring arms. In contrast, our model, choosing an abstention arm does not provide any information about the
With slight abuse notation, we the symbol e represent the abstention regret and the abstention reward within their respective settings. The surrounding context should elucidate the exact meaning of c.
4

---

Published in Transactions on Machine Learning Research (04/2026)
abstention arm itself. Instead, the mean reward (or regret) of each abstention arm is known to the learner at the beginning of the game.
Regret minimization. Our overarching goal is to design and analyze online algorithmss x that minimize their expected cumulative regrets up to and including the time horizon T The regrets are formally defined for the two distinct settings as follows:
Fexed-regret setting:
T
RBG (T, (T: = u.c
Σ 1=1
((1 - X²) 1(B, = 03 c 1(B, = 13)
(1)
Fixed--eward setting:
T
Ree = T= Vc) E
Σ
[BB =0 t 1(B
= (BB, -
(2)
An online algorithm π consists of two interrelated components: the arm sampling rule that selects A,, and the abstention decision rule that determines B, each time step t E [T]. Additionally, we use I and R7 to denote the collections of all online policies for the fixed-regret and fixed-reward settings, respectively. For the sake of analytical convenience, we also introduce the canonical regret Ry, (T) Tu - E E' X.). which disregards the abstention option and remains well-defined within our abstention model. Furthermore, when there is no ambiguity, we will omit the dependence of the regret on the policy. For example, we often abbreviate RRG (T, π as (T).
Remark 3. It worth mentioning that our model is a strict generalization of the canonical multi-armed bandit model (without the abstention option). Specifically, it particularizes to the canonical model as the abstention regret e tends to +oo in the fixed-regret setting and as the abstention reward tends to -oo in the fixed-reward setting. Nevertheless, the incorporation of an extra challenge, the abstention decision (denoted as B,), offers the agent the potential opportunity to achieve superior performance terms of either regret. One might wonder whether our setting reduces to a (K + 1)-armed bandit model where the (K+) + +1)-tt arm models abstention. It does not; for a detailed discussion on why our framework cannot be reduced to a standard bandit problem with an additional deterministic arm, the reader is referred to Appendix B
Other notations. For x, R, we denote A y = min v) and VVy == max(x, y). For any arm [K], let N:(1) = Σx 1(A, = i] and (a:(() == X,11A = i)/N.(!) denote its total number of pulls and empirical estimate of the mean up to time t, respectively. In particular, we set ft((t +oo if (i(t) = 0. To count abstention records, we also use ( (t) and N₂ (t) to denote its number of pulls without and with abstention up to time t, respectively. That is, N/! (t):= 1 = and B, 0} and (t = E'= ='= 1(A, = and B, = 1}. Additionally, we define Piie as the empirical mean of arm i based on first pulls. Furthermore, we use a, an, and so forth to represent universal constants that do not depend the problem instances (including μt, c, T, K), with possibly different values in different contexts.
1(4,
3 Fixed-Regret Setting
In this section, we focus on the fixed-regret setting. Specifically, we design conceptually simple and computationally efficient algorithm, namely Fixed-Regret Thompson Sampling with Abstention (or FRG- TSwA), to minimize the cunulative regret while incorporating fixed-regret abstention. To evaluate the performance of our algorithm from a theoretical standpoint, we establish both instance-depended asymptotic and indeeendet minimax upper bounds on the cumulative regret, as elaborated upon in Section 3.1 Furthermore, in Section 3.2 we provide lower bounds for the problem of regret minimization multi-armed bandits with fixed-regret abstention. These findings substant that our algorithu achieves both asymptotic
In certain real-world applications, the time horizon T may be unknown the agent. In fact, all of our proposed methods are inherently angttime in nature, as they not necessitate prior knowledge the horizon.
5

---

Published in Transactions on Machine Learning Research (04/2026)
Algorithm Fixed-Regret Thompson Sampling with Abstention (or FRG-TSWA) Input: Arm set [K] and abstention regret c > 0.
1: Sample each arm once, and choose to abstain (B, = 1) if and only if / / 2c
Initialize Pr (K) and N₂(K) for all E [K]. for t= = K + ,...., T do
4: For each arm i E [K], sample (,(t) ~ (N(i(tt - 1/N, 1)) and set
(t = (1))
with probability 1/K with probability 1- 1/K.
[
Pull the arm A, arg max az(t), and choose to abstain (B, 1) if and only if
K
max LCB,(t) - (t, or tta 2c
6: Observe Xe from the arm A,, and update Pa(t) and N((t) for all E [K].
7: end for
and minimax optimality simultancously. The pscudocode for FRG-TSWA is presented in Algorithm 1 and elucidated in the following.
In terms of the arm sampling rule, our algorithm is built upon Less- expsooipp Thompson Sampling (Jin et al. 2023), a minimax optimal enhancement of the celebrated Thompson Sampling (TS) algorithm (Thompson 1933 3. We refer to Remark for the reason behind this choice. During the initialization phase, each arm is sampled exactly once. Following that, each time t, an estimated reward (t) is constructed for each arm E [K], which is either drawn from the posterior distribution (t (), 1/N, 1)) with probability 1/K set to be the empirical mean ft,(t 1) otherwise. Subsequently, the algorithm consistently pulls the arm A, with the highest estimated reward.
To pursue the dual optimality properties, it is essential to carefully balance the simultaneous control of asymptotic and worst-case regrets resulting from potential misjudgments in choosing the abstention option. With regard to the abstention decision rule, we propose two abstention criteria that work in tandem (as detailed in Step of Algorithm [] The first criterion gap-dependent in nature. In particular, for each arm i [K], we define its lower confidence bound
(C fc( 6 Glog t + 2 1og
(3)
N₁ ((6--)
Then we choose to abstain there exists an arm E [K] {At} for which the difference between LCB,(t) and the empirical mean of the arm A, exceeds c. This condition signifies that the suboptimality gap AA, is least e with high probability. The LCB in the fact that it takes the value of the abstention regret e into consideration. Notably, besides its asymptotic optimality, our choice lo employ this LCB rather than other natural types of upper or lower confidence bounds in the abstention criteria (e.g., those that do not include c) is primarily due to the imperative to constrain the minimax regret to be O(VKT).
custom-tailored for our speeific application, which is unique in
The second abstention criterion is gap-independent. It is motivated from the construction of worst-case scenarios as detailed in the proof of our lower bound. Under this criterion, we opt for the abstention option if c S K/t,, which implics that the abstention regret remains acceptably low at time in view of the worst-case scenarios.
Remark As previously highlighted, our model in the fixed-regrot setting particularizes to the canonical multi-armed bandit model as the abstention regret tends infinity. Similarly, when tends to infinity, the two abstention criteria are never satisfied, and the procedure of Algorithm simplifies to that of Less-

---

Published in Transactions on Machine Learning Research (04/2026)
Exploring Thompson Sampling. It is worth noting that this latter algorithm is not only asymptotically optimal but also minimax optimal for the canonical model. This is precisely why we base our algorithm upon it, rather than the conventional Thompson Sampling algorithm, which has been shown not to be minimax optimal (Agrawal & Goyal 2017
3.1 Upper Bounds
Theorem
I below provides two distinct types of theoretical guarantees pertaining to our algorithm's perfor-
mance on the cumulative regret Rge (T), defined in Equation 1 for the fixed-regret setting.
Theorem 1. For all abstention regrets
0 and bandit instances p u, Algorillm 7 guarantees thal
RRC (T)
A Ac
limsup T-000
log T
A
i>1
Furthermore, there erists a universal constant a >> 0 such that
cT RRG((T S aa(KK
{ + E Ad)
if VK/T 8f>> VK/T.
The proof of Theorem 1 is deferred to Appendix D.1 The theoretical challenges arising from proving Theorem revolve around the quantification of the regret that results from inaccurately estimating the suboptimality gaps associated with the abstention criteria. More precisely, it crucial to establish upper bounds on E[N[" (T)) lor arms i with A; e (which, by definition, includes the best arm), and on E for arms with A, These bounds need to be derived from both asymptotic and minimax perspectives, adding layers of complexity to the analytical process. To accomplish these tasks, we initially decompose the target expectations into manageable components, and subsequently bound the resulting subterms in the two respective regimes. Our approach, merging TS-based sampling rule with I.CB-based abstention criteria, necessitates a careful amalgamation of both TS-type and UCB-type analytical techniques.
Furthermore, for the asymptotic upper bound, take deeper exploration into the randomized arm sam- pling dynamics inherent to Kess-Exploring Thompson Sampling. A pivotal aspect of this exploration is a characterization of high probability lower bound on the number of pulls of the optimal arm, as detailed in Lemma 5 inspired by the work of Korda et. al. 2013)
Finally, we remark that the numerous intricacies involved in these analyses preclude us from formulating a generalized strategy akin the forthcoming Algorithm for the fixed-reward setting.
3.2 Lower Bounds
In order to establish the asymptotic lower bound, we need introduce the concept of RRG -Ro-consss,,,,y, which rules out overly specialized algorithms that tailored exclusively to specific problem instances. Roughly speaking, -gtG-coonssttett algorithm guarantees subpolynomial cumulative regret for any given problem instance.
Definition 1 (RRG-consiine (B"GGconsistency). An algorithm क E [ is said to be PRG-cconistenn if for all abstention regrets e > 0, bandit instances μ E U, and a > 0, RRG (T, T) = o(T
Now we present both asymptotic and minimax lower bounds on the cunulative regret in Theorem 2 which is proved in Appendix D.2
Theorem 2. For any abslention regrel c > 0, bandil inslance E U and -cosiistell algoriliam n, il holds that
RRG (T, [T, n.c log T
A Ac
lim inf 700
2
A
For any abstention regret e 0 and time horizon T K, there exists universal constant a >> 0 such that
inf sup RRG (T, x) 2 a (o(VKY KT (TTAAI ATT..
TENRR pell

---

Published in Transactions on Machine Learning Research (04/2026)
Comparing the upper bounds the cumulative regret of our algorithm FRG-TSWA in Theorem with the corresponding lower bounds in Theorem 2 it is evident that our algorithm exhibits both asymptotic and minimax optimality,
Asymptotic optimality. For any abstention regret c > 0 and bandit instance μ E U, the regret of our algorithm satisfics the following limiting bchaviour:
R (T)
A
lim T-000 log
A
1>1
The above asymptotically optimal result yields several intriguing implications. First, the inclusion of the additional fixed-regret abstention option does not obviate the necessity of differentiating between suboptimal arms and the optimal one, and the exploration-cxploitatii case in which the cumulative regret grows polynomially, the agent must still asymptotically allocate the same proportion of pulls to each suboptimal arm, as in the canonical model. This assertion is rigorously demonstrated in the proof of the lower bound (refer to Appendix D.2 for details). Nevertheless, the abstention option does indeed reduce the exploration cost for the agent. Specifically, when exploring any suboptimal with suboptimality gap larger than c, our algorithm tends towards employing the abstention option to minimize the instantancous regret. This aspect is formally established in the proof of the asymptotic upper bound (see Appendix D.I.
trade-off remains crucial. In fact, to avoid the
Minimax optimality.
the context of worst-case guarantees for the cumulative regret, we focus on the dependence on c, K, and T. Notably, the Ei> A term is typically considered as negligible in the literature
(Audibert & Bubock 2009: Agrawal & Goyal 2017 Lattimore & Szeposvári, 2020). Therefore, Theorem [ demonstrates that our algorithm attains worst-case regret of O(vKT A cT), which is minimax optimal in
light of Theorem 2
A phase transition phenomenon can be clearly observed from the worst-casc guarantees, which dovetails with our intuitive understanding of the fixed-regret abstention setting. When the abstention regret e is sufficiently low, it becomes advantageous to consistently opt for abstention to avoid the worst-case scenarios. On the contrary, when the abstention regret exceeds a certain threshold, the abstention option proves to be inadequate in alleviating the worst-case regret, as compared the canonical model.
Remark 5. Although our model allows for the selected arm A, and the abstention option B, to depend on each other, the procedure used in both algorithms within this work is to first determine A, before B,; this successfully achieves both forms of optimality. Nevertheless, this approach might no longer be optimal beyond the canonical K-armed bandit setting. In K-armed bandits, each arm operates independently. Converscly, in models like linear bandits, pulling one arm can indirectly reveal in information about other arms. Policies based on the principle of optimism in the face of uncertainty, as well as Thompson Sampling, fall short of achicving asymptotic optimality in the context of lincar bandits (Lattimore & Szepesvári 2017). Therefore, the abstention option becomes particularly attractive if there exists an arm that incurs substantial regret but offers significant insights into the broader bandit instance.
Stochastic and heterogeneous abstention regret. If the regret incurred by the agent when opting for abstention is not deterministic but stochastically generated from a distribution with known expectation c, Algorithm remains effective, and our analyses of the upper and lower bounds remain valid. Additionally, another natural exlension of our model is that the abstention regret different for different arms. Specifically, the agent incurs regret of c; > 0 when pulling arm and choosing abstention. In this scenario, the abstention criteria in Algorithm [ can be adapted accordingly, and the same asymptotic and minimax optimality be established; see Appendix D.3 for details.
4This unavoidable when the abstention regret e sufficiently high, since every reasonable algorithm has allocate fixed number of pulls each arm.
8

---

Published in Transactions on Machine Learning Research (04/2026)
Algorithm 2 Fixed-Reward Algorithm with Abstention (or FRW-ALGWA)
Input: Arm set [,], abstention reward E I, and & base algorithm ALG that is both asymptotically and minimax optimal for the canonical multi-armed bandit model.
Initialize (0) +oo for all arms i E [K].
2: for ( 2....., do
Pull the arm A, chosen by the base algorithm ALG.
4: Choose to abstain (B, = 1) if and only if AA, (t-1(t-)))))) S
5: Observe Xe from the arm A,, and update (a(() for all i e [K].
end for
4 Fixed-Reward Setting
In this section, investigate the fixed-reward setting. Here, the reward associated with the abstention option remains consistently fixed at E R. When exploring specific arm, the agent has the capability to determine whether selecting the abstention option yields higher reward solely based on its own estimated mean reward. However, in the fixed-regret setting, this decision can only be made by taking into account both its own estimated mcan reward and the estimated mean reward of the potentially best arm. In this regard, the fixed-reward setting is inherently less complex than the fixed-regret selting. As a result, it becomes possible for us to design more general strategy Fixed-Reward Algorithm with Abstention (or FRW-ALGwA), whose pseudocode is presented in Algorithm 2 Despite the straightforward nature of our algorithm, we demonstrate its dual attainment of both asymptotic and minimax optimality through an exhaustive theoretical examination in Sections 4.1 and 4.2
FRW-ALGWA A leverages base algorithm ALG that is asymptotically and minimax optimal for canonical multi-armed bandits as its imput. For comprehensive definitions of asymptotic and minimax optimality within the canonical model, see Appendix A Notably, eligible candidate algorithms include KL-UCB++ (Ménard & Garivier 2017), ADA-UCB (Lattimorc 2018), MOTS-J (Jin et al., 2021) and Less-Exploring Thompson Sampling (Jin et al. 2023). In our algorithm, at each time step L, the base algorithm determines the A2,
selected arm A, according to the partial interaction historical information Subsequently, the algorithm decides whether or not to abstain, indicated by the binary random variable B,, by comparing the empirical mean of the arm A,, denoted as P. (t - 1), to the abstention reward c.
XI-).
4.1 Upper Bounds
Recall the definition of the cumulative regret REW (T), presented in Equation (2) for the fixed-reward setting. Theorem establishes both the instance-dependent asymptotic and instance- indeeenden minimax upper bounds for Algorithm 2 see Appendix E.1 for the proof.
Theorem 3. For all abstention rewards c E IR and bandit instances E U, Algoritio 2 guarantees that
RRW (T) p.c
RI VCVC- V4
lim sup T-000
< 2
log T
A
Furthermore, there erists a universal constant a >> O such that
RRW (T) Sa
V Σ (uive-m)) iE|K]
Remark 6. It is worth considering the special case where f1, where opting for abstention results in a reward even greater than, or equal to, the mean reward of the best arm. For this particular case, as per Theorem 3 since μ1 V 14 c for all i> 1, our algorithm achieves a regret of o(log This result, in fact, is not surprising. In contrast the fixed-regret sctting where the regret associated with the abstention option is strictly positive, in this specific scenario of the fixed-reward setting, selecting the abstention option is indeed the optimal action at single time step, regardless of the arm pulled. Therefore, there is

---

Published in Transactions on Machine Learning Research (04/2026)
necessity to distinguish between suboptimal arms and the optimal one, and the exploration-exxllttation trade-off becomes inconsequential. However, when the abstention reward is below the mean reward of the best arm, ie., с < maintaining a subpolynomial cumulative regret still hinges on the delicate balance between exploration and exploitation, as evidenced by the forthcoming exposition of the asymptotic lower bound.
4.2 Lower Bounds
We hereby introduce the concept of RRW -consistency for the fixed-reward setting, in a manner analogous to the fixed-regret setting. Following this, we present two distinct lower bounds for the problem of regret minimization multi-armed bandits with fixed-reward abstention Theorem The proof for Theorem 4 is postponed to Appendix [.2
Definition 2 (RRWW-coe consistenccy). An algorithm x E I[RW is said to be RRw -consistent if for all abstention rewards E R. bandit instances j U, and 0, RRW (T, x) o(T").
Theorem 4. For any abslention reward E I, bandit inslance μ U and D -consistent algorithm x, il
holds that
RRe (T,
41 V 14
Tim inf T +-000
log T
A
For any abstention reward IR and time horizon T K, there cxists a universal constant such that
inf
sup RRW (T,x) 2 KVKT.
sEllow pell n.c
By comparing the upper bounds in Theorem 3 with the lower bounds in Theorem 4 it firmly confirmed that Algorithm 2 is both asymptotically and minimax optimal in the fexed-reward setting.
Asymptotic optimality. For any abstention reward e E and bandit instance μ E U our algorithm ensures the following optimal asymptotic behavior for the cumulative regret:
RRW (T)
lim T-000
2 8>1
V1 V.
log T
A
Since it holds that in Ve- V A, for all i i> 1, our algorithm elfectively reduces the cumulative regret in the asymptotic regime through the incorporation of the fixed-reward abstention option.
Minimax optimality. Concerning the worst-case performance of our algorithm, disregarding the additive term Σiery (A1 Vc-4), (i), achieves an optimal worst-case regret of O(VKT). While this worst-case regret is the same as that for canonical multi-armed bandits, achieving non-trivial as we have to simultaneously achieve the minimal asymptotic Instance-dependent regret.
Moreover, there is occurrence of the phase transition phenomenon in the fixed-reward setting. This absence can be attributed to the intrinsic nature of the fixed-reward abstention option. For any abstention reward E R and online algorithm, we can always construct a challenging bandit instance that leads to a cumulative regret of Q(VKT), as demonstrated in the proof of the minimax lower bound in Appendix E.2
5 Numerical Experiments
In this section, we conduct numerical experiments to empirically substantiate our thcoretical insights. To reduce clutter, we report our results only for the fixed-regrel setting here. Results pertaining to the fixed- reward setting are deferred to Appendix F where we consider two particular realizations of our algorithm basod on Explorinn Thompson Sampling (Jin al. 2023) and KL-UCB++ (Ménard & Garivier 2017). In each experiment, the reported cumulative regrets are averaged over 2, 0,000 independent trials and the corresponding standard deviations displayed as error bars in the figures.
10

---

Published in Transactions on Machine Learning Research (04/2026)
250
200
Regret
Regret
150
100
100
I
FRG-TSwA
50
Less- Less--xxloring TS
50
Asymp. Lower Bound
0
0.5
1.5
2
0.5
1.5
x10
T
x 100
(a) Instance p
(b) Instance jr²
Figure 2: Empirical regrets with abstention regret = 0.1 for different time horizons T.
200
240
220
Regret
160
Regret
200
140
180
120
ERG-TSwA
160
Less- Exploring TS
100
140
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
(a) Instance at
(b) Instance lu
Figure Empiriaal regrets with time horizon 10, 000 for different abstention regrets
To confirm the benefits incorporating the abstention option, we compare the performance of our proposed algorithm FRG-TSWA (Algorithm D with that of gess-Exploring Thompson Sampling (Jin al. 2023 which serves instances. The first instance jut with K = has uniform suboptimality gaps: n4 = and n 0.7 for
bascline algorithm without the abstention option. We consider two synthetic bandit
all E [K] \ {1}. For the second instance u² with K = 10, the suboptimality gaps are more diverse: af 1, n 0.7 for i E (2,3, 4}, nn 0.5 for i E (5.6,7} and of 0.3 for i e {8, 10). The empirical averaged cumulative regrets of both methods with abstention regret
0.1 for different time horizons T are presented in Figure 2 To demonstrate their asymptotic behavior, we also plot the instance-dependent asymptotic lower bound on the cumulative regret (refer to Theorem 2 in each sub-figure. It can be observed that FRG-TSWA is clearly superior compared to the non-abstaining baseline, especially for large values of T. This demonstrates the advantage of the abstention mechanism. With regard to the growth trend, the time horizon T increases, the curve corresponding to FRG-TSWA closely approximates that of the asymptotic lower bound. This suggests that the expected cumulative regret of FRG-TSWA matches the lower bound asymptotically, thereby substantiating the thcoretical results presented in Section 3
To illustrate the effect of the abstention regret c, we evaluate the performance of FRG-TSWA for varying values of c, while keeping the time horizon T' fixed at 10, 000. The experimental results for both bandit instances ut and nt are presented Figure 3 Within cach sub-figure, we observe that as e increases, the empirical averaged cumulative regret initially increases but eventually saturates beyond certain threshold value of These empirical observations align well with expectations. Indeed, when provided with
11

---

Published in Transactions on Machine Learning Research (04/2026)
complete information about the bandit instance, if the abstention regret exceeds the largest suboptimality gap, the agent gains no advantage in choosing the abstention option when selecting any arm. However, we remark that the agent lacks this oracle-like knowledge of the suboptimality gaps and must estimate them on the fly. Consoquently, this results in the inevitable selection the abstention option, even when the abstentiin regret large.
6 Conclusions and Future Work
In this paper, we consider, for the first time, a multi-armed bandit model that allows for the possibility of abstaining from accepting the stochastic rewards, alongside the conventional arm sclection. This inno- valive framework is motivated by real-world scenarios where decision-makers may wish to hedge against highly uncertain or risky actions, exemplified in clinical trials. Within this enriched paradigm, address both the fixed-regret and fixed-reward settings, providing tight upper and lower bounds on asymptotic and minimax regrets for each scenario. For the fixed-regret setting, we thoughtfully adapt a recently devel- oped asymptotically and minimax optimal algorithm by Jin et al. (2023) to accommodate the abstention option while preserving its attractive optimality characteristics. For the fixed-reward setting, we convert any asymptotically and minimax optimal algorithm for the canonical model into one that retains these op- timality properties when the abstention option is present. We remark that our proposed algorithms are computationally efficient, incurring only negligible constant-time overhead per step beyond the standard arm selection mechanisms. Finally, experiments synthetic datasets validate our theoretical results and clearly demonstrate the advantage of incorporating the abstention option.
While our analysis focuses on Gaussian rewards, the framework naturally extends to other distributions, provided that specific boundary cases are handled with care. As highlighted Remark 3 a fruitful avenue for future research lies in expanding the abstention model from K-armed bandits linear bandits; specifically, it remains open question whether the inclusion of the abstention feature can lead to enhanced asymptotic and minimax theoretical guarantees. Furthermore, in work, the abstention option exerts influence the stochastic observation from the selected arm. Delving into more sophisticated and general approaches to model the effect of the abstention option promises as captivating future direction.
Acknowledgments
We thank the anonymous reviewers for their helpful comments. T. Jin and V. Y. F. Tan are supported by a Singapore Ministry of Education (MOE) AcRF Tier 2 grant under grant number A-8004062-00-00.
References
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory (COLT), pp. 39- 1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling. Journal of the ACM (JACM), 64(5):1-24 24, 2017.
Noga Alon, Nicolo Desa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Non- stochastic multi-armed bandits with graph-structured feedback. STAM Journal on Computing, 46(6): 1785 1826, 2017.
Jean-Yves Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference Learning Theory (COLT), volume 7, pp. 1 122, 2009.
Peter Auer, Nicolo Cisnchianchi, Yoav Freund, and Robert E. Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-33 322-331. IEEE, 1995.
Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235 256, 2002.
12

---

Published in Transactions on Machine Learning Research (04/2026)
Peter L Bartlett and Marten H Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 9(8), 2008.
Olivier Cappé, Aurélien Garivier, Odalric-Amin Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, pp. 2013.
Weiwei Cheng, Michaël Rademaker, Bernard De Baets, and Eyke Hüllermeier. Predicting partial orders: Ranking with abstention. In Machine Learning and Knowledge Discovery in Databases: European Con- ference, ECML PKDD 2010, pp. 215 230. Springer, 2010.
Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, pp. 247-254, 1957.
Chi-Keung Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970.
Corinna Cortes, Giulia DeSalvo, and Mchryar Mohri. Learning with rejection. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Baly, October 19-21, 2016, Proceedings 27, pp- 67 82. Springer, 2016.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. International Conference on Machine Learning, pp. 1059 1067. PMLR, 2018
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Leslie Meltzer Henry, Megan E Larkin, and Elizabeth R Pike. Just compensation: no-fault proposal for rescarch-related injurics. Journal of Law and the Biosciences, 2(3)6645-668, 2015.
Radu Herbei and Marten H Wegkamp. Classification with reject option. The Canadian Journal of Statistics / La Revue Canadienne de Slatistique, pp. 709 721, 2006.
Junya Honda and Akimichi Takemura, An asymptotically optimal bandit algorithm for bounded support models. In Conference on Learning Theory, pp. 67-79. Citescer, 2010.
Yu Hu, Jiwoong Shin, and Zhulei Tang. Incentive problems in performance- based online advertising pricing: Cost per click vs. cost per action. Management Science, 62(():2002 2002220888, 2016.
Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Leurning, pp. 5074 5083. PMLR, 2021.
Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration is fast and optimal. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 15239 15261. PMLR, 2023.
Adam Kalai and Varun Kanade. Towards optimally abstaining from prediction with ood test examples. Advances in Newral Information Processing Systems, 34:12774-12785, 2021.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, Oclober 29-31, 2012. Proceedings 23, pp. 199 213. Springer, 2012.
Nathaniel Korda, Emilie Kaufmann, and Rémi Munos. Thompson sampling for 1-dimensional exponential family bandits. Advances in Neural Information Processing Systems, 26, 2013.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22 22, 1985.
Tor Lattimore. Refining the confidence level for optimistic bandit strategics. Journal of Machine Learning Research, 19(1):765-703 2018.
13

---

Published in Transactions on Machine Learning Research (04/2026)
Tor Lattimore and Csaba Szepesvári. The end of optimism? An asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statislics, pp. 737- PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandil Algorithms. Cambridge Universily Press, 2020.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithmm. Information and Computation, 108(2):212-25)) 261, 1994.
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Anqi Mao, Mchryar Mohri, and Yutao Zhong, Ranking with abstention. arXiv preprint arXiv:2307.00000 2023.
Pierre Ménard and Aurélien Garivier. A minimax and asymptolically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pp. 223 237. PMLR, 2017.
Renuka. Munshi and Urmila Thatle Compensation for research related injury. Perspeclives in clinical research, 4(1):61-65 69, 2013.
Hamid Nazerzadeh, Amin Saberi, and Rakesh Vohra. Dynamic cost-per-action mechanisms and applications to online advertising. In Proceedings of the 17th international conference on World Wide Web, pp. 179-188, 2008.
Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prodiction with abstention. In Conference on Learning Theory, pp. 3030 3048. PMLR, 2020.
Robert Steinbrook. Compensation for injured research subjects. The New England journal of medicine, 354 (18):1871-1873, 2006.
William R. Thompson. On the likelihood that one unknown probability excoeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-29) 294, 1933.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Scries in Statistics. Springer, 2009.
Yair Wiener and Ran Yl-ia..v. Pointwise tracking the optimal regression function. Advances in Newral Information Processing Systems, 25, 2012.
Ahmed Zaoui, Christophe Denis, and Mohamed Hebiri. Regression with reject option and application to knn. Advances in Neural Information Processing Systems, 33:20073-20088 2020.
A Asymptotic and Minimax Optimality in Canonical Multi-Armed Bandits
In the canonical multi-armed bandit model, there is no additional abstention option. Given a bandit instance I E U, at each time step N, the agent employs an online algorithm æ to choose an arm A, from the arm set [K], and then observes random variable X, from the selected arm At, which is drawn from Gaussian distribution ((AA,, 1) and independent of observations from previous time steps. The choice of A, might depend on the prior decisions and observations. To describe the setup formally, A, is mea-measurable, where FCA == (A1, X1, X2, X2...., At, X,) represents the o-field generated by the cumulative interaction history to and including time t. Subsequently, the agent suffers an instantaneous regret of μI X..
The agent aims at minimizing the expected cumulative regret over a time horizon T, which is defined as
T
(CA(TT x) Tp E
Σ
X
We refer to the collection of all online policies for the canonical multi-armed bandit model CAA
14

---

Published in Transactions on Machine Learning Research (04/2026)
Remark 7. It is worth noting that any algorithm designed for canonical multi-armed bandit model possesses the capability to decide the arm A, to pull at each time step based on the partial interaction history X1, ,,,xX,,A,,,. " XI-), within the abstention model. Conversely, any algorithm tailored for the abstention model in the fixed-regret sctting (or in the fixed-reward setting) can be applied to the canonical multi-armed bandit. model, provided that the abstention regret (or the abstention reward) has been prede- termined. Specifically, the algorithm can determine both the selected arm A₃ and the binary abstention variable B, although B, purely auxiliary and exerts influence on the cumulative regret R (T, xt).
Lower bounds. Both the asymplolic and minimax lower bounds for the canonical multi-armed bandit model have been thoroughly established (Lai & Robbins 1985 Auer et al. 1995). For comprehensive overview, refer to Sections 15 and 16 of Lattimore & Szepesvári (2020). Here, we summarize the results in the following:
Definition (RCA-consistency). An algorithm E ITCA is said to be cCo-connistent if for all bandit. instances U and a > O, Re (T, (I, o)
Theorem 5. For any bondil inslance U and RCA -co-ssssst algorithm n, il holds that
RC (T, TT)
2
lim inf T-000
log T
A
8>1
For any time horizon T > K, there exists universal constand >> O such that
(T,(TT inf sup R (T, 2 KT.
AETIC pell
Asymptotic and minimax optimality. According to Theorem in the canonical bandit model, an algorithm æ ITCA is said to be usyroplotically optimal if for all bandit instances μ E U, ensures that
lim T
(T,
Σ
2
log T
A
i>1
Furthermore, is said to be minimar optimal if there exists a universal constant a > such that
RCA (T, (TA Sa VKT+ <VT++ Σsi
8>1
To the best of our knowledge, for canonical multi-armed bandits with Gaussian rewards, KL-UCB++ ++ Ménard
& Garivier 2017), ADA-UCB (Lattimore/ 2018), MOTS-J (Jin et al. 2021) and Less--xpllorin Thompson Sampling (Jin al. 2023) exhibit simultancous asymptotic and minimax optimality. As their names suggest, the former two algorithms follow the UCB-style, while the latter
are rooted in Thompson Sampling.
Remark 8. One valuable byproduct derived from the proof of the asymptotic lower bound in Theorem 3 is that, for any -consissittt algorithm n, bandit instance 24 and suboptimal arm i > 1, we have
lim inf E[N((T) T-
2
logT
A?
Therefore, any algorithm that is asymptotically optimal ensures that for all suboptimal arms i >
E[N,(T)
lim
T
log T
A
15

---

Published in Transactions on Machine Learning Research (04/2026)
B Comparison with the (K + 1)-Armed Bandit Reduction
A natural question arises regarding the formulation of our abstention model: can the problem be simply roduced to a standard multi-armed bandit setting with K + 1 arms? In such reduction, the additional + (K+s)-st arm would represent the abstention option, yielding deterministic reward (in the fixed-reward setting) or fixed regret (in the fixed-regret setting).
While such a reduction might appear intuitive and indeed may suffice for achieving coarse worst-case (min- imax) guarantees of ((VKT), it fundamentally fails to capture the strategic advantages of our framework. Specifically, the reduction cannot achieve the same instance-dependent asymptotic optimality. In the follow- ing, we discuss the essential differences between our model and the (K + 1)-armed reduction.
Structural Difference: Decoupling Learning from Reward. The most critical distinction lies in the bandit model, selecting the deterministic
mechanism of information acquisition. In a standard (K+1)-th arm (the "safe" option) fixes the instantancous outcome but reveals no information regarding the distributions of the original K stochastic arms. To learn about a specific arm E [K], the agent is forced to pull it and fully accept its stochastic outcome.
In contrast, our abstention framework allows the agent to decouple the observation of an outcome from the acceptance of its reward. When the agent exercises the abstention option, they secure a guaranteed result (equivalent to the deterministic arm) but, crucially, simultaneously observe the stochastic sample X, from the selected arm A,. This structure enables what can be termed "safe exploration": the agent can continue to gather valuable statistics about potentially risky or unknown arms to refine their estimates, all while shielding themselves from the full cost of stochastic underperformance.
Asymptotic Optimality. To illustrate how this structural difference translates into superior asymptotic performance, we show below that in both the fixed-reward and fixed-regret objec- tives, the (K + +111)aamm 1)-armed reduction and our abstention model admit different instanco-dependent asymptotic behavior.
Performance Gap:
Fixed Reward: In a standard (K + 1)-armed bandit reduction, to learn about a suboptimal arm i, the agent must select it. Consequently, the agent incurs a regret proportional the full suboptimality gap A; =1=- - by for every exploratory sample. The asymptotic regret contribution from arm i is thus driven by the factor A, However, in our fixed-reward abstention model, the agent can leverage the abstention option to mitigate this cost. Specifically, if the abstention reward satisfies 14 < c < μl, the agent can pull arm i while simultaneously choosing to abstain. In this scenario, the agent observes the outcome of arm i (gaining information) but receives the fixed reward c. The resulting instantaneous regret is μl c, which is strictly less than the full gap - p4:
This mechanism facilitates a more cost-effective form of exploration. Consequently, our derived asymptotic regret bound scales with the term μn V #4 V c, rather than the larger gap A; that arises from the (K+1)- armed reduction. This confirms that a simple reduction to a (K + 1)-armed bandit cannot replicate the superior asymptotic optimality achieved by our proposed model.
Fixed Regret: A simple (K + 1)-armed reduction also fails in the fixed-regret objective. In that reduction, the (K + 1)-st "abstain" arm incurs a deterministic regret c, but it reveals no information about the original K stochastic arms. Hence, to statistically verify that a suboptimal arm is worse than the best arm, the learner must still pull arm and accept its stochastic outcome, paying regret about As per sample. By the standard asymptotic lower bound in Lai & Robbins (1985), the regret caused by pulling arm is on the order of 2 Therefore, the leading asymptotic term under the (K + 1)-arm reduction is En>1 A. is independent of c. In contrast, in our abstention model the learner can pull arm i while abstaining, still observing X, but capping the instantaneous regret by c. Thus, exploration of arm i costs A, A c per sample, yielding the strictly smaller scaling 2 E ArAC log T, and in particular improves l to 2e whenever A:
2logT A, which
reduction cannot replicate the fixed-regret asymptotic achieved At
A > c. This again shows the by our model.
16

---

Published in Transactions on Machine Learning Research (04/2026)
C Auxiliary Lemmas
Lemma 1 (Bretagnolle-Huber incquality (Tyybkkvv 2009 ). Let P and P be two probability distributions
on the same measurable space F). For any event A E F and ils complement. A = 22 \ A, the sollowing inequality holds:
P(A)+ P(A)+ 2 exp( exp(-KL(PPP)))
where KL(P,PP) denotes the Kullbock- Leibler (KL) divergence between P and IP.
Lemma 2 (Divergence decomposition lemma). Consider both the fized-regret setting and the fized rewerd setting. Fir an arbitrary policy æ. Let (I...... Px) represent the reward distributions associated with one bandit instance, and let v' (P''...,,,P, .Pk) represent the reward distributions associated with another bandit instonce. Define Pv.c as the probability distribution of the sequence (A1, B1, Ar. Br, induced by the algorithm under the abstention regret in the fized-regret setting (or the abstention reward in the feued-reward setting) for the bandit instance v. Similarly, let Pv'cc denote the same for the bandit instance v'. Then the KL divergence belween Puςe and Pur,o can be decomposed as:
KL
= Σ (L. HE]K]
The proof of Lemma 2 is similar to the well-known proof of divergence decomposition in the canonical multi-armed bandit model (excluding abstention). and is therefore omitted. This proof can be located, for instance, Garivier et al. (2019) Section 2.1) and Lattimore & Szepesvári (2020) Lemma 15.1).
Lemma 3 (Hoeffding's s inequality for sub- Gaussian random variables). Let X Xn be independent a- sub-Gaussian random variables with mean Then for any & 2 0,
ne² and P( S p - 8) S exp
ns²
Pp 2 +) S exp
2
20
where á 1,2 Eiz1 X,, Lemma 4. Let {Xi)ien be a sequence of independent Gaub-Gausian random variables with meam p. Then for any O and N E N
N E
20²
N
20
P(an 2 u (++ S
and
Σ m=1
P(nn S 1 - E) =) 8
=²
==1
where Pn == n ER X,.
Proof. By symmetry, it suffices to prove the first part. According Lemma
have
ng²
P( 2 2
+
exp
20
n=1
exp
2n
exp
207
1
exp
20
202
<
c2
where the last inequality follows from the fact that e
for any 0.
17

---

Published in Transactions on Machine Learning Research (04/2026)
D Analysis of the Fixed-Regret Regret Setting
D.1 Upper Bounds
Proof of Theorem Duc to the law of total expectation, we can decompose the regret R (T, π) as
T
n.C (T, π) = E
((1 - Xx) -) + 1BB = =
0)
E
((1z MA,)) 1[B: = + 1(B, = 1})
(T)) + Σ ( EIN (7)
(T) + B(N!"
(4)
For any amm i with A < c (including the best arm), it holds that
|| (T))
1
=E E
1 (A: = and B, = 11
K 2
< E
I
A; = i and
6 logt + 2 2log(cVV)
-a(ll - }
+E
I A: i and
max JE(K]N()
1)
N, ((t--)
(=K+1
K 2
$ E
A₁ = i and
V
c
6log t + 2log(cV
2 2m1 }}
+ E
Σ
I
A i and max jE[K]
Aayt pyy(t11- V
(t 1)
K+1
+
Σ
pu((t - 1) 20
(5)
k(=+1
where the last incquality arises from the observation that when A = i
(
6logt t + 2log(cV
max JE(K((()
Ai(t - -1)20
N2(t - 1)
2 mn ) 1 U (ur - Ai(t -1) 2 c)
(2(t-1)) V
6 Glog + 2 2log(c
max jEIKTMO
N2 -) 1)
6 log t + 2 Vog(cV
max jEIK]
(y((-11-
2 11 1 Uim Aslt - 1) 2 2c..
N2 -
For convenience, for any E [K] such that A, < c, we introduce three shorthand notations to represent the
terms in Equation 5 These terms correspond to distinct conditions under which the algorithm chooses abstain:
ΣT I { A = and / o]
T Σ I i(Ar = and max,e(K) (Rg(t - 1)
6logt42 (logee)) (t
2 m1)
- K+1 I {A, = and p - 1) 2 ct)
18

---

Published in Transactions on Machine Learning Research (04/2026)
To clarify the intuition behind these terms:
represents the gap-independent abstention. This captures the case where the algorithm abstains purely because the time step is small, independent of the empirical estimates.
represents abstentions caused by the overestimation of LCBs. This captures the low-probability event. where the lower confidence bound of any arm j exceeds the true mean of the optimal arm J4.
represents abstentions caused by the undercstimation of the selected arm. This captures the event where the empirical mean of the chosen arm i deviates significantly below its true mean μ4 (specifically such that μ41 fii(t 1) 2 c), triggering the gap-dependent abstention criterion.
We will analyze (}) and later to establish the two forms of upper bounds.
On the other hand, for the term Jo which relates strictly to the concentration of arm i, we have
E
Σ
T(A, = Pai pa (c A:) and Ni(L 8}
K+1
s=l
E
I Hise 14 (c- A0)
(6)
2
(7)
(c - A,)2'
Line 6
follows from the fact that for all E [T' 1],
Σ I(A= and Ni(t 1) =} 1
Line 7 is due to Lemma
For any arm i with A; c, since arm E [K] (i), we have
[ (0)
(T)
I (A, = and B, 0}
T
<1+B
Σ ((=-1
1
A. = and
6 6log 2 log(c
-d, < and / K
A,(t - 1)-
max (E(K](()
(1 1
T
6 Glogt t + 1--+210000 2log(c
A. 1) < off
<1+
Σ K=K-1
A₂ = and
[1((t- 1)
(8)
(1
Minimax upper bound. Ifc S V then the abstention option is always invoked because
/ / 22 for I [T). Consequently, is straightforward to deduce that.
RRG (T) & cT.
19

---

Published in Transactions on Machine Learning Research (04/2026)
Next, consider the case that c> 4 Compared with the canonical multi-armed bandit model, at a single time step, the agent in our abstention model incurs greater (expected) regret only if an arm with A < is pulled and the abstention option selected. Thus, we have
u.c (T) S Rx (T)+ Σ (c--A)-ENN
(9)
EAAE
Due to the minimax optimality of Less-Exploring Thompson Sampling (Jin et al. 2023 there exists a universal constant 01 >> 0 such that
R (A( (T) 00 01 ( + -
(10)
Recall the upper bound of E[N!" (T) for arm with A; c, as given in bounds for the following terms:
Subsequently, we will establish
Σ (c- (*)
Σ cc
(c A.)
and Σ (c
Ai)
(()
HAiCO
For the first term, we have
Σ (c)
Σ C.E
Σ
A, and
K V
V
2 c
iAice
K
S. E
V
20
K
KT.
(11)
For the second term, we can obtain
Σ (c-A))
(N) S
Σ c.
T
Glog + 2 (oo((eV))
< c
max KE[K]
(t)--1)-
M1
Ny
+ K+1
6logt 2log(c 1)
Sc.
Rty(t
2 #1
N2 11)
KE|K]
20

---

Published in Transactions on Machine Learning Research (04/2026)
For all j [K], by union bound over all possible values of N2 1) and Lemma 3 have
T
Pg(t - 1) 6 Glogt + 2 2lo
E
Σ
I
Ny(t 1)
++=
Σ
Σ
Ass - 6logt 2log(c (1)
2 M1
Glogt t + V
Σ
Σ
P
Ajo
Uj
k
(12)
(cV1)
k
Pc
t=K+1
Ke
where the last inequality follows from the numerical fact that
Σ
1
dr
2
==
x2
K³
t=11
Thus, we can bound the second term as
Σ (c- Sc.
Σ jE[K]
(13)
Kc
For the third term, in addition to the upper bound of in we can identify another straightforward upper bound as follows:
E
Σ
I(A 1} S ([N.
K+1
By applying these two bounds separately for distinct scenarios,, we have
Σ #A,
(c-
Σ
(c- + + Σ (c- Di)
22
K
Σ
E[N((T)) +
Σ C- A
Re-A227
K T
T
T
Σ
2
K
A
T
< VKT+K
2
K
= KT.
(14)
By plugging Inequalities
13
and
14 into
5
we have
Σ #AKE
(c- Ad E
$1
21

---

Published in Transactions on Machine Learning Research (04/2026)
Together with 9 and 10
can conclude that
R (T) S (a1 4) KT taj a1 Σ C4
Therefore, there must exist a universal constant
O such that
Re (T) a a VKT Σs. A
This completes the proof of the minimax upper bound.
Asymptotic upper bound. Consider any arm with A, < e (including the best arm). In the following,
will further elucidate the upper bound of B[N (T) as given in 5 within the asymptotic domain.
For the first term in we have
T
K
t
2
c
2
For the second term
iss using Inequality
12 can get
Mi M1
6 Glog / + 2 2log(cV
E
R,lt 1 1)
jE
N2(t-1) 1)
t= K
T
6logt + +2 +2log(cV1) 1)
=m1]
E
I pty(t
11-1 -
2/11
(2
]E[K]
-t= K++
c
Incorporating 7
we obtain
EIN 1) (T) S
K
+-+ c
1
2 A,)
o(log T)-
2
(c
Consider any amm with A, > c. We will further explore the upper bound of E[N!") (T) in
According the fact that
6 6log l + 2 2lo((cV))
A, and
(1 11
Ni
6logt+ + Vog(cV
A1(1 - -1)+ +1++1
$ 141
Nt - 1)
6 Glogt + 2 2log(c 1)
U
A, = i and
(1 -
2
- 1)
Ai(t-1) 1)
Ni - 1)
have
E (T)
S1+E E
Σ
T
PIA== = and
(pi(t-1)= 1)- -v 6log / 2 22lo(ce )
Ai(t 1) -
Ni 1)
M=
22

---

Published in Transactions on Machine Learning Research (04/2026)
T
6 log t + +2 2og((e
M4 /
<1+E
Σ
I
(1 - 1) V
Ni 1) 1)
Lt=++1
T
log + log(e (1) (1 1
+ E
Σ
At = and
As(t -)) -
(15)
(1 1)
++
Following a similar argument as in 12 we can derive
6 6logt + 21og(c 1)
1
E
Σ
in An(t-11 1) +
Sm M1
(16)
(1 ((t--)
Ke
k+=++1
Now we focus on the last term in 11 which is denoted by (*);.
For any fixed b E (0, 1), there must exist constant & (b, p. c) 2 K 1 such that for all t 2 t1:
6 logt 2log(cV1) 1)
A c
2
(t - 1)6
Notice that for all t 2 ti,
6log + 2 2log(e
A, = and (u1-2 V/
- -i(l 1) <0 -
(1
C (Ni(l 1))
- (1 (1-1)b}
u {f Ar = and (m (u--2 2/
6logt + 2 2log(c
- -1:(1 - 1) < e and Ni 1) (1-)0
(1
N1(1 1)
A -
c
s (1- ((- u
At = and po:( - 1) 2 M +
2
From the above, we deduce that
A c
+E * sh+ + Pt +E
Σ
A and
Po 1) p1
2
Using the approach similar the one used to bound
in we have
A
Σ t=
Ar = and pu - 1) Z p1 +
<
2
(A: - -)
By applying Lemma 5
we can get
8
+0,, + (A, c)2
) S (1,
where the term 3(b, ,, K) is subsequently defined in Lemma
Substituting the above inequality and 16 into
15 we arrive
1
E (T))
< 1 + Ke
+ t1 k), + (A. c)2
23

---

Published in Transactions on Machine Learning Research (04/2026)
o(log T).
Due to the asymptotic optimality of Less-Exploring Thompson Sampling arm i, we have
Jin et al. 2023 for any suboptimal
2 T
(T)
<
+ ollog T).
A
Finally, based on the regret decomposition in we can conclude
(PC(T) = c- C (2) (T)
Σ A E (0) (T) + (eN+M.
=c- -C-E 12) (T) (T)
(A, E(N
+ Σ ( - A (()) N R (T)) (c - (c- A.).).
(A, AC) E[N(TT)
A.) Σ c4 C) (T))
1>
EAIEE
iA,2e
A AC
$ (2 7)
+ o(logT)
A
$>1
where the second equality is due to the fact that ! Therefore, holds that
=[N = [[), for all arms i [K].
RRG log T
A Ae
lim sup
2
T T
A
i>1
as desired.
Lemma 5. Consider Algorithm 1 For any b (0, 1), there exists a constant 3(b, μ, K) such that
Σ P (Ni(t) S st') S p,,
Proof. The proof of Lemma closcly follows that of Proposition 5 in Korda et al. 2013). which was used to analyze the classical Thompson Sampling algorithm. In fact, the only dilference between arm sampling rule, which is built upon Less-Exploring Thompson Sampling (Jin et al. 2023). and the classical Thompson Sampling is how the estimated reward (t( is constructed for each arm i E [K]. Specifically, in our arm sampling rule, (t) is either drawn from the posterior distribution (( - 1), 1/N with probability 1/K or set to be the empirical mean (t, - 1) otherwise. In classical Thompson Sampling, (t()) always drawn from the posterior distribution. Therefore, it suffices to verify the parts concerning the probability distributions of a, ((); these correspond to Lemmas 9 and 10 in the proof of Proposition 5 in Korda et al. 2013)
It is straightforward to see that Lemma 9 in Korda et al. 2013) is applicable to our algorithm. For Lemma 10 therein, its counterpart is demonstrated in Lemna 6 below.
After establishing the counterparts of Lemmas 9 and 10 in the proof of Proposition 5 in Korda et al. (0133
we can extend the same analysis to our specific case. For the sake of completeness, we provide a proof sketch in the following.
Let Tj denote the time of the j-th pull of the optimal arm (ie., arm 1), with TO == 0. Define E := (Tz41 - 1) - Ty as the random variable measuring the number of time steps between the j-th and (j + 1)-th pull of the optimal arm. With this setup, we can derive an upper bound for P (N) < (*) as:
(NN < 2 <P(jj E [t]], Es 1b - 1)
Σ
P(s 2 1- 1).
24

---

Published in Transactions on Machine Learning Research (04/2026)
Consider the interval Σy {T) .......77 1t 1/}. f 2 2/-=b. - 1, then no pull of the optimal arm occurs zz.
The subsequent analysis aims to bound the probability that no pull of the optimal arm occurs within the interval Zz. It relics on two key principles:
First, for suboptimal arm, if it has been pulled sufficient number of times, then, with high probability, its estimated reward (sample) cannot deviate significantly from its true mean. This obscrvation is quantitatively characterized in Lemma 10 of Korda et al. (2013). corresponding to Lemma in our paper.
Second, for the optimal arm, the probability that its estimated reward (sample) deviales significantly below its true mean during a long subinterval of Ij is low. This observation is quantitatively characterized in Lemma 9 of Korda al. (2013), which directly applies to our case.
Lemma 6. Consider Algorithm 7
For all E N, it holds that
A 2
128 log
K
P 1s 1ss,,312 (x) 14
Ni(s
1)>
5
A
$2
Proof. For any fixed S t and > 1, we have
A
128 log t
P (,(s))
#4 +
Ne(s - 1)>
2
A?
A
128 log
P Ai(s 1) > +
Ni(s -1)
(17)
A
A
128 log t
1) S pi + 4
+ PP (a((s) #
(1(5 1)>
pa(s
2
A
For the first term in 17 by Lemma
bound it
A:
128 log
pr(s 1)> ps +
Ni(s 1)
A?
A
Σ
P
Pii > μs
+
Ni(5 - 1) = =x)
4
128 loge A?"
A
P
Pii
Mi +
4
128 lowe
128 log
A.
13
For the second term in according to the construction of (x()) in Algorithm I and Lemmaa we can get
A Ni(s - 1) > 128 log L
A
(s()) > 14 +
fu((s - 1) s +
2
4
25

---

Published in Transactions on Machine Learning Research (04/2026)
S P (i(b) > Po(s - 1) + A Ni(s - -1)> 128 logt
4
a,(ss > ps(s +)+ A,
P
Ni(s - 1) = x
4
125 log A?
1 1
K
128 log
Ktt
Thus, for any s E t and 1, it holds that
P (s(()) p(a((s) I4 2
A: Ni(8
128 log / A
1
K +1
N1(8-1>>
1
Kt3
Kt3
Finally, by union bound, we can conclude
P Jss 1: p4
A N. 1)
128 log t
(K + 1)(K - 1)
K
KI2
D.2 Lower Bounds
Proof of Theorem In the following, we will establish the asymptotic and minimax lower bounds, respec- tively.
Asymptotic lower bound.
Consider any algorithm that is RRG connsiste.. Sine E[N! (0) (T)
+
E|N! (T)) = E[N((T)) for all arms i E [K], we can utilize the regret decomposition in to derive
RRG (T, π) 2 Σ - ( +c. ENN"
i>1
Σ
(A(AA))EEN((T))
Fix any abstention regret c > Then for all bandit instances μ E l and 0, it holds that
RCA (T, σ)
Tp1 E X₁
A
(T)
Σ (Di)c) E(N((T)))
< max
A Ac
i>1
A
< max il
RRG p.c
(T,
A Ac c
o(
Therefore, in accordancee with Definition 3 the algorithm π also RCA -co-csnnitt for arbitrary abstention
regret
26

---

Published in Transactions on Machine Learning Research (04/2026)
Subsequently, for any abstention regret and bandit instance ,e, have
RR (T, xT) log T
Eist (1A, Ac) (T))
lim inf T-+00
2 lim inf
T-000
log
[[N
Σ (A, A Ac)
lim inf inf T-000
log T
A AC
2
A
where the last inequality follows from the property of RCA-consistent policies detailed in Remark S This concludes the proof of the instance-dependent asymptotic lower bound.
Minimax lower bound. We extend the proof of the minimax lower bound from the canonical multi- armed bandit model to the model incorporating fixed-regrel abstention.
Consider any fixed abstention regret > O, time horizon T 2 K and algorithm π E _1 We construct a bandit instance E U, where μ1 = and μ4: = for all é E [K] \ {1}. Here, A > is some parameter whose exact value will be determined later. We use P p.e to represent the probability distribution of the sequence (A1; B1, XI,..., Ar, Br,Xr) Xr) induced by the algorithm for the abstention regret and bandit instance Jr. Since Ei [N)) = T, according to the pigeonhole principle, there must exist an index [K] (1)
such that
T [N, K-1
Now we construct another bandit instance jl' E U where /4 A, 11, =4 and 14 = 0 for all E [K] (1, Let pe denote the probability distribution of the sequence (Ai, Xi,..., Ar, Br, Xr) induced by the algorithm for the abstention regret and bandit instance p'.
For the first bandit instance 14, regardless of the abstention option, if (T(T) s T/2, then the cumulative regret must be at least (A A 222 Therefore, we have
(AAC)T
RBC (T, πT)
(N) ST/2).
2
Similarly, for the second bandit instance y', we can obtain
(DAC)T
RRG (T, (T))) R
(TT
2
By combining the aforementioned two inequalities and applying Lemma I we obtain the following:
CCT (P (Ti < T/2) + +
BBGGTT (T, π) + RRG (T, (T n.0
A A C)T
exp (-KL (P a.P. Pp).
Leveraging Lemma 2 and the KL divergence between Gaussian distributions, can derive
(2
27A
KL (P, p.es P.rcc) = Ey.c (N, (n,c(N,(TT)
2
K 1
Altogether, we can arrive at
(A A
T
2TA 2 K
PRG que
(T + RBG (T, (T, x)>
exp
4
27

---

Published in Transactions on Machine Learning Research (04/2026)
Now, we set A = / Ac, which leads to
VKT ATT
2T K
T n cc2
R (T, ωT + R (T, 2
exp
K
VKT ACT
2K
4
exp
K K
exp(-4)
(VKTACH ACT)
Consequently, either (T,
(T, π) R (T, x) is at least exp(-4) (VKT cT), which completes the proof of the instance-independent minimax lower bound.
D.3 Heterogeneous Abstention Regret
In the scenario of heterogeneous abstention regret, for each arm i E [K], the agent incurs regret of > 0 when pulling arm and choosing abstention. By the law of total expectation, the expected cunulative regret to the time horizon T can be expressed as:
RBC (T, T)) = Σ ((m) - (w)
= =0 ca. - = -1))
= =1 E (T)) + Σ (A. E|N (T)) + (
i>1
For of presentation, define e [ Q the maximum abstention regret level. The lower bound part is straightforward. Specifically, obtain the following lower bounds.
Theorem 6. For any abstention regret (c))et])) bandit instance U and -conssiiitt algorithm x, il holds that
ReRG (T,
A
lim inf T-0
log T
A?
i>1
For any marimum abstention regret level 0 and time horizon T 2 K, there crists universal constant a > 0 such that
inf sup RRG (T, 2 alVKT
*EIRRG pell.c
With respect to the algorithm design, for each arm i E [K], we redefine its lower confidence bound as
LCB,(t) = f4((t - 1) 11-1 6logt + log(c V1)
N,(t 1)
Then in the abstention decision rule, we choose to abstain (B: = 1) if and only if
K max LCB,(t) - AA. 2c or 1 (E(K]H[t)
2c
(18)
Note that in 18 we compare / with c= max G-
Theorem 7. For any abstention regref c = (ci)εejk) and bandit instance μe U, Algorithm abstention criteria in (18 guorantees that
with the new
RRG (T)
A A c
lim sup T
log T
A
28

---

Published in Transactions on Machine Learning Research (04/2026)
Furthermore, there erists universal constant 0 such that
(RC((T S {aWKT
CT alVKT Eis Ai)
ifs VK/T 'f>> VKTT.
The proof of ( follows that of Theorem I in Appendix D.1 While many steps are analogous, it is noteworthy that in this context, for any arm i with A; < Gi, we can upper bound B[N!" (T) as
T
K
E[N (1)
(T)
SE
E
A = and Vt
2c c
T
Glog + 2 log((c, V1) N₂ 1) 2 21
+ E
Σ
1
A and max je[k]
Ai(t 1)
U=
T
+ E
Σ
[( = and μn - Ault - 1) 2 at
μ=K+1
E Analysis of the
Setting
E.1 Upper Bounds
Proof of Theorem following:
Utilizing the law of total expectation, we can decompose the regret REW (T, x) in the
T
X, 1[B, 03 0) + 1(B, = =1))
RRW 240
(T, π5) =T x) (11 Vc) - E
Ur. 1(B; = 0) 1BB = 11)
T Vc) - E
E (wi m4) B[N, (0) (T) KE[K]
(nveecc ()) (T)I.
(19)
Recall that we define (1(1) 4000 if N2(1) for all arms E [K]. Thus, for any arm i with b4 > C, we can
obtain
E[N
= E (
Σ
(A and B, = 13
T
= E
{A = and pa 1) cc
T-1
S E
T(A. i and Pio S c and N₂(! - 1) =}}
E
I{A i and Pio c and N.(t 1) $}
E
I (fir S sc
2
(14 c)2
where the penultimate inequality derived from an argument analogous to that in (6) and the last inequality is consequence of Lemma
29

---

Published in Transactions on Machine Learning Research (04/2026)
Similarly, for any arm with #4 C, we have
T
E
1
(T)
E
[ = and B, 0}
T
Σ
[[A = and Relt - 1) > c
=
T T-1
Σ
[[A, = and Pio > and N₁(t 1)= =
==
T-1
<1+E
Σ
I(A =i and Puo > and Ni(t - 1) = s}
1=1 ==1
2
11+ (c- 23)
Asymptotic upper bound.
First, we consider the scenario where μr & c. In this case, based on the we can bound the regret as follows:
regret decomposition in Equation
19
RRW (T)
Σ (c 14)
E[N (T))
Σ (c- (b) E (T)
(20)
C- Mi +
c 14
<4 <c
o'logTT).
Next, consider the scenario where in Due to the asymptotic optimality of the base algorithm, for any suboptimal arm i, we have
log
B[N:(T)) <
+ ollog T).
A
Thus, we can bound the regret as:
R. (T)
Σ
(11 -4) E(N, (T) + (11 - c) -[N (T))
TE|K]
Σ
(.) (ANTC--))B///(/))) + (#1 Vc- E(N!
-
K[[K]
Σ
(m (m 24 vc) E[N((T) (M4 Vc- EIN + (T)I
SE[K]
(M1
p4 (Vc)-E[((TT) + Σ (c-M))EIN
(T) (T) Σ (m- (ek-c)-E(p - (T)
< (2 T)
11 14
Vc
Σ
c- M4 +
2
+
Σ
+ o(log T)
A
14
#4
i>1
Epice
ispibe
M1
14
V
c
(2 T")
T')
A
where the third equality is due to the fact that [I + E|N
E(N.(T)) for all arms i (K).
30

---

Published in Transactions on Machine Learning Research (04/2026)
Altogether, in both scenarios, it holds that
RRW (T)
Vc
P Vc
lim sup T-000
2
log T
A
f>1
Minimax upper bound.
First, in S c, by utilizing the regret decomposition in Equation
20
WC
have
RlW (T)
Σ (c- mi) B (0) (T)
Σ
(c- o +
Σ
(c- ps) B[N (T)
hO<C-MEV
to-m22 K
K
E
E[N
[[N(O(T) (T)) +
Σ
2
C- +
c 14
M2V V
(21)
K
T
Σ
c p4 + 2
T K
T
hc-p22
T
T
S KT +
(c- 14) +.)+K22 21
K
KE|K]
-3 +
Σ (MiVe-M)) m1).
KE[K]
Next, if ii c, then the best possible (expected) reward at single time step is μı, which coincides with the canonical multi-armed bandit problem. Consequently, compared with canonical multi-armed bandits, single time step, the agent in our problem incurs greater (expected) regret only if an arm i with > is pulled and the abstention option is chosen. Thus, we have
RRW (T) S (CRAATT (T)+ Σ (4- (A-,))B[N," ([N
kppb
Due to the minimax optimality of the base algorithm, there exists a universal constant 01 > 0 such that
RC (C)(T)
(T) aa VKT + Σs, A
S>
Furthermore, using a similar argument as in
21 we can derive
Σ (wi- -) c) B[N (T)
Σ
(Mi c) E (T) (T)
Σ
(M4 -) c) E(N!") (T)
10CH4-RE K
< VKT+
Σ
Mi -C
i /
K
<3VKT.
31

---

Published in Transactions on Machine Learning Research (04/2026)
Therefore, we can bound the regret
R (T) S (a1 +3)
VKT +
ΣA.)
11
(a1 +3)
VKT Σ
(1z (c-Ve-
iE[K]
As result, the desired minimax upper bound holds in both scenarios.
E.2
Lower Bounds
Proof of Theorem 4 The proof structure for @ parallels that of Theorem 2 Appendix D.2 although certain specific details contain significant variations. Therefore, we will streamline the shared components and elaborate on the distinctions.
Asymptotic lower bound. Consider any RRW consissten algorithu a and bandit instance μ E U. The case that c 2 ji trivial, as RRW (T, n) non-negative, and μi Ve- M4 Ve 0 for all > Thus, it suffices to demonstrate that for any abstention reward < M1,
RRW (T, π log T
41 M VC
lim inf T-200
2
A
i>1
When e < M1, we can establish a lower bound on RRW (T, x) as follows:
RRW (T, TT) (T,
Σ
(11 - :4) E (0) (T) + (M) - -c) . (T))
kE[K]
(wI n4) E[N (7)) (i1 c) BIN!" (T))
2
1>
Σ
(1- 14 ([)((T)))
1>1
Therefore, we only need to show for all suboptimal arms i i>> 1,
lim inf E[N((T)
(22)
T-
log
A?
However, unlike the asymplotic lower bound part of the proof of Theorem 2 cannot apply the properties of -consisssty here, RRW -cWoconsiyyy does not imply RCA *C*Acoonisttency in general. Instead, we will demonstrate the desired result (22) directly.
Fix an index >> and lake >> O. We now proceed to create an alternative bandit instance μ' E u, where n¹ = P1 + s and n = μr for all i [K] (j}. Note that for the new bandit instance, it holds that max 14 = u4 μl > e. To distinguish between the two scenarios, we will refer to the probability distribution associated with the sequence (A1, XI.... Ar, Br, Xr), generated by the algorithm æ for the abstention reward and the original bandit scenario n4, as IP plecs and for the new bandit instance μl, we denote the corresponding distribution Py
A straightforward computation yields
RRW n.c (T,T) (#1 M4
(1-MA VoTT
P Pm,((N((T) > T/2)
2
and
ET Pwic(N,(T)) $ T/2).
RR (T .T) 2
2
32

---

Published in Transactions on Machine Learning Research (04/2026)
Employing similar approach to the one used in the minimax lower bound part of the proof of Theorem 2 utilizing Lemmas
and 2
can derive:
((11 - 14 - V) NEJT
R
x)
R RRW
(T, T)
(PH,c(N, T/2) (M) S T/2))
2
((1 14 C) A EJT
exp (-KL (P. Mres Put,o)
(1) - p4 Vc) exp (NEy.olN, (A, +
2
By rearranging the above inequality and taking the limit inferior, we have
log
(HT -Live)ee ROW (T) RBW (Tix))
E[N, (T)
lim inf
1 lim sup T-000
T-000
log
(Aj + =))
log
2
log u. (T, x +
H'. .e
(T, ,
1- lim sup T-+00
(A, + 8)2
log T
Recall the definition of RRW -eW-cssssttency. For all a > 0, both R (T, and R. (T, x) are on the order of o(T"), and hence,
log (RRW (T, x²) + R (T, T))
lim lip
a.
T+xx0
log
By letting both a and e approach zero, we can establish the desired result (22.. thereby concluding the proof of the asymptotic lower bound.
Minimax lower bound. The construction employed in the fixed-reward setting here is analogous to the one utilized in the proof of Theorem 2
Consider any fixed abstention reward E R, time horizon T 2 K and algorithm π E IIW Let A > 0 be a parameter to be determined later. We construct a bandit instance E U, where μ1 = A + c and 14 = for i [K] \ (1). Note that there must exist an index j E [K] \ [1} such that [N,,(N, S K-T- We then
construct another bandit instance pl Ut where μ A + c, n²) 2A + and n¹ for all [K] \ {1.5).
Similarly, by applying Lemmas and 2
derive that
AT
RBW (T, BB (T, m)
(P (N..o(NN (I) + PP ( T/2))
AT
exp
(-KI. (T. p.cc P,),e)
AT
-R (2
exp
2
AT
2TA2
N
exp
4
K -
By choosing A we have
K V7 T
exp(-4) KT.
RRW (I, + R RR
(T,
8
Consoquently, either RRW (T, T) or RRW (T. T) at least exp(-4)
VKT.
&
Therefore, have established the instance-independeni minimax lower bound.
33

---

Published in Transactions on Machine Learning Research (04/2026)
250
280
200
200
Regret
150
100
FRW-TSWA TRW-UCDWA
Las-Eaaporing T5
KL-UCB"
Asyup, Lowe Bound 1.5
0.5
1.5
(a) Instance n
(b) Instance μ
Figure 4: Empirical regrets with abstention reward 0.9 for different time horizons T.
250
250
200
200
FRW-TSWA
RRW-UCBWA
Less-Exploring
KL-UCB"
8.5
0.2
(a) Instance nt
(b) Instance μ²
Figure 5: Empirical regrets with time horizon T = 10, for different abstention rewards c.
F Numerical Experiments
F.1 Results for the Fixed- Reward Setting
In this subappendix, we present the empirical results pertaining to the fixed-reward setting. Specifically, we examine the empirical performances of two particular realizations our algorithm FRW-ALGWA (as outlined in Algorithm 2 FRW-TSWA and FRW-UCBWA. The former uses Exploring Thompson Sampling (Jin et al. 2023) as its base algorithm, while the latter employs KL-UCB+* (Ménard & Garivier 2017). Note that KI-UCB++ time horizon T instances ut and μ², as previously defined in Appendix F.1
not anytime algorithm; that is, requires the prior knowledge of the input parameter. In the following experiments, continue to utilize the two bandit
In a manner analogous to our methodology for the fixed-regret setting, we adopt the original versions of Exps-oxpliinng TS and KL-UCB++ as baseline algorithms without the abstention option. The experimental results of the different methods with abstention reward e = 0.9 for different time horizons T are presented in Figure ! Additionally, we plot the instance-dependent asymptotic lower bound (ignoring the limit in T) on the cumulative regret (sce Theorem 4 within each sub-figure. From Figure 4 have the following observations:
Both realizations of our algorithm, FRW-TSWA and FRW-UCBWA, exhibit marked superiority the two non-abstaining baselines.
34

---

Published in Transactions on Machine Learning Research (04/2026)
650
800
350
400
Regret
250
Regret
200
100
200
HRG-TSWA
50
Exploring
Asymp, Lower Bound
x10
7
x10
(a)
(b)
Figure 6: Empirical regrets with abstention regret 0.1 for different time horizons T.
Concerning the observed growth trend, as the time horizon T increases, the performance curves for both FRW-TSWA and FRW-UCBWA approximate the asymptotic lower bound closely. This behavior indicates that the expected cunulative regrets of FRW-TSWA and FRW-UCBW A attain the instance-deue deneeneet lower bound asymptotically, validating the theoretical findings discussed in Section 4
While both FRW-TSWA and FRW-UCBWA represent implementations of our general algorithm and share identical theoretical guarantees, FRW-TSwA demonstrates superior empirical perfor- mance. This is particularly evident in the first instance μ², suggesting its enhanced applicability for real-world applications.
Next, we examine the impact of the abstention reward by assessing the performance of FRW-TSWA and FRW-UCBWA for different c, while keeping the time horizon T fixed at 10, 000. The experimental results for bandit instances je and pl are shown in Figure 5
Within each sub-figure, a pattern emerges. As the abstention reward increases, the empirical average cunulative regret initially remains relatively stable and starts to decline once e crosses a certain threshold, eventually stabilizing around a small value. These observations are consistent with our theoretical expecta- tions. Specifically, when the abstention reward the agent derives no benefit from opting for the abstention action over selecting an arm. On the other hand, when the abstention reward exceeds the highest mean reward of the arms, abstention becomes the optimal decision and its reward is even superior to choosing the best arm. In this specific scenario, it is possible to achieve a regret of o(log T); see Remark 6 for further insights.
lower than the smallest mean reward among the arms,
F.2 Random Instances
In this subappendix, present additional numerical experiments, using random instances with large mum- bers of arms. The construction of these random instances mirrors the method Jn et al. (2023. Specifically, for a given number of arms denoted by K 2 10, we set = and 0.7 for i E #4 Unif(0.3, 0.5] for E [K] [10].
10}. while
For the sake of simplicity in presentation, we focus on the fixed-regret setting, examining two choices of K, namely, K = 20 and K 30. The empirical averaged cumulative regrets with abstention regret c 0.1 for different time horizons T are shown in Figure 0 while the experimental results with time horizon T 10, 000 for different abstention rewards are illustrated in Figure 7
It is evident that the findings in Figures 6 and 7 closely resemble those in Figures 2 and Notably, FRW-TSwA A outperforms Less-Exploring TS which not tailored to the setting with the abstention option.
35

---

Published in Transactions on Machine Learning Research (04/2026)
450
550
400
500
BeG-TSWA
Less-Exploring TS
850
850
0.1
3.1
(a) K 20
(b) K 30
Figure 7: Empirical regrets with time horizon T = 10, 000 for different abstention regrets
36


Reviews:
[{"review_id": "MerzcfdgrZ", "reviewer": "Reviewer_gExo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces an abstention-augmented bandit framework that extends the classical stochastic multi-armed bandit setting by allowing the agent, at each round, to choose an abstention option with a fixed reward or regret. The setting is well motivated and captures a meaningful class of decision-making problems where a safe, deterministic outside option coexists with uncertain stochastic actions. The authors provide a comprehensive theoretical study of the problem under two distinct regimes—fixed-reward and fixed-regret. For each setting, the paper establishes both minimax and asymptotic lower bounds on the regret, and proposes algorithms whose upper bounds provably match these limits.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The proofs are provided in the appendix.", "audience_yn": "Yes", "audience_explanation": "Learning theory is a topic of interest to the TMLR community.", "requested_changes": "(1) While the proposed abstention setting is interesting and potentially broadly applicable, the motivating examples provided in the paper (e.g., clinical trials and online advertising) do not fully align with the abstraction captured by the model. In particular, in these examples, the abstention option appears to operate at a different semantic or decision-making level (e.g., insurance purchase or pricing scheme selection), rather than constituting an alternative action that is directly comparable to pulling an arm within the same decision round. As a result, the examples may obscure, rather than clarify, the core modeling contribution.\n\nIn my view, the main strength of the framework lies in modeling scenarios where, at each round, the agent must choose between a stochastic action with unknown reward and a safe, deterministic baseline option with fixed reward or regret. This structure arises naturally in settings such as online recommendation or A/B testing, where the agent can either deploy a novel, uncertain option or fall back to a well-understood default (e.g., a control policy or a historically strong item), while still observing feedback. Clarifying the motivation along these lines would help better position the contribution and highlight the practical relevance of the abstention mechanism.\n\n(2) In the fixed-reward setting, it is not entirely clear whether the abstention option introduces behavior beyond what can be captured by modeling it as an additional $(K+1)$-th arm with known reward $c$ and zero variance. It would be helpful if the authors could clarify whether such a reduction yields the same regret guarantees or if there are essential differences between the two formulations. \n\n(3) In Remark 5, the authors state that when $c \\ge \\mu_1$, the regret is $o(\\log T)$. Under the alternative viewpoint above, one might expect that existing lower bound arguments would still require $\\Omega(\\log T / (c - \\mu_1)^2)$ regret to identify arm 1 when $c > \\mu_1$. Could the authors comment on this point? \n\n(4) For the fixed-regret setting, the authors propose a Thompson Sampling–type algorithm, whereas for the fixed-reward setting, their analysis applies to any algorithm that is minimax-optimal. It would be helpful to clarify whether alternative algorithms, such as KL-UCB, can also be adapted to the fixed-regret setting under a similar modification", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}, {"review_id": "JV00XUEUsV", "reviewer": "Reviewer_mgKH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces and studies multi-armed bandits with abstention, a stochastic bandit model with an abstain option.\nThe reward distributions are assumed to be Gaussian with unknown means and fixed variance $1$.\nThe learner may choose to abstain from observing the reward after selecting an arm, thereby avoiding potential negative outcomes at the cost of forfeiting the stochastic reward. The authors formalize two variants of this model: one where abstention incurs a fixed regret penalty, and another where abstention yields a fixed deterministic reward.\nFor each setting, the authors develop an algorithm called FRG-TSwA and FRW-ALGwA, respectively, and establish both instance-dependent asymptotic optimality and instance-independent minimax optimality. They also provide matching lower bounds, thereby characterizing the optimal regret rates in both settings.\n\nThe work also includes numerical experiments demonstrating the practical benefits of abstention and validating the theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "This paper has a solid theoretical analysis. The results have been presented in a clear way and I find it easy to follow.", "audience_yn": "Yes", "audience_explanation": "This paper analyzes an extension to the standard multi-armed bandit problem, which provides the learner with the option to decide whether to abstain from the action before observing the outcome. This is a new problem formulation that has not been well-studied in the literature. Although it focuses on a narrow setting, the results are solid and interesting.", "requested_changes": "Minor changes:\n\n1. While the algorithms are claimed to be computationally efficient, a brief discussion comparing per-round complexity to standard TS or UCB variants would be useful.\n\n2. The authors could consider adding a brief discussion on potential extensions to non-Gaussian reward distributions, even if only speculative.\n\n3. Notations used in the appendix are not standard. It would be better to assign a more meaningful notation with some explanation.", "broader_impact_concerns": "No broader concerns since this is a theoretical paper that analyzes an interactive learning algorithm.", "additional_comments": "Overall, it is a nice and solid work, and I find it is easy to follow. The notations used in the appendix, such as spades and circles, are a little bit annoying since it does not convey any meaningful concept but are only abstract notations. It could be better to use more reasonable notations with explanations.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XW8aHHASGk", "reviewer": "Reviewer_5hFf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a stochastic multi-armed bandit model with an additional abstention option, where after choosing an arm, the agent may abstain from accepting the stochastic reward while still observing the outcome. Two settings are considered: fixed-regret abstention: abstaining incurs constant regret, and fixed-reward abstention: abstaining yields constant reward. \nThe authors design algorithms achieving both asymptotic and minimax optimal regret, and provide matching lower bounds. Numerical experiments illustrate the advantage of abstention.", "claims_and_evidence_yn": "No", "claims_explanation": "I would like to raise concerns regarding the reasonableness of the proposed abstention model from two perspectives: intuitive motivation and mathematical modeling.\n\n(1) From the intuition perspective, the examples used to motivate abstention appear problematic.\n\nFirst, in the clinical trial example, the described safeguard policies may themselves influence patient outcomes, and therefore, the resulting observations would no longer correspond to the original treatment distribution. Moreover, the claim that purchasing insurance or deploying safeguards can effectively circumvent the risks of hazardous treatments oversimplifies medical realities and may unintentionally understate the ethical and practical constraints inherent in clinical decision-making. In practice, protective interventions typically alter treatment effects rather than simply paying additional cost while leaving observations unchanged.\n\nSecond, the online advertising example is conceptually unclear. It is not obvious what action precisely corresponds to abstention, nor how the outcome of the original decision remains observable after abstention. If a company chooses some abstention option (I do not know what it is), it is unclear how the stochastic outcome associated with the original decision would still be observed. The mapping between abstention and real advertising mechanisms, therefore, requires clearer explanation.\n\n(2) Mathematical modeling: I also have concerns regarding the mathematical modeling in both the fixed-regret and fixed-reward settings.\nIn the fixed regret setting, the final regret reads like $cT$ if $c \\le \\sqrt{K/T}$, $\\sqrt{KT}$ otherwise. However, this kind of regret is not surprising, as the regret of the abstention option $c$ is known to the agent.  It suffices to always choose the abstention option when $c \\le \\sqrt{K/T}$, and then apply the standard bandit algorithm otherwise. \n\nIn the fixed-reward setting, the problem formulation appears nearly equivalent to augmenting the action set with an additional arm corresponding to an “abstention action” that yields deterministic reward $c$. In this interpretation, applying a standard bandit algorithm to the enlarged action set of size $K+1$ will achieve a regret of $O(\\sqrt{(K+1)T})$ = $O(\\sqrt{KT})$, same as the upper bound given in Theorem 3. From this perspective, the abstention mechanism does not seem to provide additional algorithmic advantage, and the value of the proposed setting remains suspicious.\n\n(3) Finally, the intuition of Algorithm 1 is unclear. In Remark 3, it only shows why it applies LessExploring Thompson Sampling, instead of TS. However, it is unclear why we do not apply other types of optimal algorithms for the multi-armed bandit, such as UCB.", "audience_yn": "Yes", "audience_explanation": "(1) It generalizes the standard multi-armed bandit setting to the case with abstention.\n\n(2) It proposes conceptually simple algorithms. The proposed methods remain implementable and close to standard TS/UCB approaches.\n\n(3) It provides matching upper and lower bounds for the problem.", "requested_changes": "Please consider the questions proposed above. Especially, the current description of the clinical trial in the introduction part may suffer from ethical issues.", "broader_impact_concerns": "The authors should add a broader impact statement on the motivation of the problem.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)