Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy
Authors: Ishank Juneja
Carlee Joe-Wong
Osman Yagan
Venue: ICLR 2025 Poster (2025)
Keywords: Bandits
Multi-Armed Bandits
Online Learning
Cost-Subsidy
Cost Subsidy
Improved UCB
UCB
Elimination Algorithms
Primary area: reinforcement learning
TL;DR: Novel algorithm for the Multi-Armed Bandits with Cost Subsidy framework with logarithmic problem instance dependent upper bound

Abstract: Multi-armed bandits (MAB) are commonly used in sequential online decision-making when the reward of each decision is an unknown random variable. In practice however, the typical goal of maximizing total reward may be less important than minimizing the total cost of the decisions taken, subject to a reward constraint. For example, we may seek to make decisions that have at least the reward of a reference ``default'' decision, with as low a cost as possible. This problem was recently introduced in the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework. MAB-CS is broadly applicable to problem domains where a primary metric (cost) is constrained by a secondary metric (reward), and the rewards are unknown. In our work, we address variants of MAB-CS including ones with reward constrained by the reward of a known reference arm or by the subsidized best reward. We introduce the Pairwise-Elimination (PE) algorithm for the known reference arm variant and generalize PE to PE-CS for the subsidized best reward variant. Our instance-dependent analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret, making our policies the first with such a guarantee. Moreover, by comparing our upper and lower bound results we establish that PE is order-optimal for all known reference arm problem instances. Finally, experiments are conducted using the MovieLens 25M and Goodreads datasets for both PE and PE-CS revealing the effectiveness of PE and the superior balance between performance and reliability offered by PE-CS compared to baselines from the literature.

Published as a conference paper at ICLR 2025
PAIRWISE ELIMINATION WITH INSTANCE-DEPENDENT GUARANTEES FOR BANDITS WITH COST SUBSIDY
Ishank Juneja, Carlee Joe- Joe-Wong & Osman Yağan Department of Electrical and Computer Engineering Cameeie Mellon University Piusburgh, PA 15213, USA (ijune coowwnng, waa.yaagnnnnnaraar
ABSTRACT
Multi-armed bandits (MAB) are commonly used in sequential online decision- making when the reward of each decision is an unknown random variable. practice however, the typical goal of maximizing total reward may be less im- portant than minimizing the total cost of the decisions taken, subject to reward constraint. For example, may seek to make decisions that have least the reward a reference "default" decision, with as low a cost as possible. This problem recently introduced in the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework. MAB-CS is broadly applicable to problem domains where primary metric (cost) constrained by a secondary metric (reward), and the re- wards are unknown. In our work, we address variants of MAB-CS including ones with reward constrained by the reward of a known reference arm or by the subsi- dized best reward. We introduce the known reference arm variant and generalize PE PE-CS for the subsidized best reward variant. Our cestance-dependet analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret, making policies the first with such guarantee. Moreover, by compar- ing our upper and lower bound results we establish that PE is order-optimal for all known reference the MovieLens 25M and Goodreads datasets for both PE and PE-CS revealing the effectiveness of PE and the superior balance between performance and reliability offered by PE-CS compared to baselines from the literature.
(PE) algorithm for the
problem instances. Finally, experiments
conducted using
INTRODUCTION
Online sequential decision-making problems capture many applications where decisions must be made without knowing their outcomes in advance. After each decision, the resulting outcome or reward is observed, and an internal model is updated to improve future decisions. In clinical trials for example, the goal is compare the therapeutic value of various drugs against ailment. The decisions in this case represent administering a certain drug and the rewards are the apriori unknown efficacies of the candidate drugs. Communication networks are another example. Here decisions must be made about the communication channel to be employed. In this scenario the reward rep- resents the success or lack thereof of communicating over a chosen channel. Multi-Armed Bandits (MABs) (Lattimore & Szepesvári 2020 are a framework for stateless sequential decision making where the available decisions are abstracted as arms of MAB problem instance. The stateless assumption implies that the distribution of rewards associated with an arm is not affected by the choices of past arms. The setting within MABs we work with is that of stationary stochastic bandits where the distribution of arm rewards does not evolve with time.
The generality of the assumptions imposed by the stationary stochastic bandits setting provides a wide net to capture a range of problem domains. However, in real-world applications there are often several competing objectives that go beyond the limited goal of maximizing reward. For instance consider the problem faced by marketing agency where there several communication modalities available to communicate the agency's advertising message. Blindly maximizing the overall success rate (reward) in this case would be naive. Since such approach would ignore the

---

Published as a conference paper at ICLR 2025
drastically different costs of using these modalities. Our example reveals that costs being associated with the sampling of any particular arm is a structure that appears quite naturally in applications.
In the marketing ageney problem we know that the various communication modalities shall have un- known success rates for any brand new ad campaign. However, the cost of employing any modality will typically be known. These known sampling costs might manifest themselves in the form of a prescribed cost budget (Badanidiyuru et al. 2018), or as a metric whose cumulative value is to be minimized (Sinha et al. 2021). specify two among many possible cost structures. We work with the latter among these settings, In particular our paper works with variants of the MAB with Cost-Subsidy (MAB-CS) framework introduced recently in Sinha et al. (021).
1.1 MULTI-ARMED BANDITS WITH COST SUBSIDY (MAB-CS) SETTING
What makes the MAB-CS setting interesting is that it requires the bandit policy minimize cu- mulative costs while obtaining cumulative reward that is feasible and not necessarily maximal. The problem therefore involves dual objectives: minimizing costs while ensuring that the reward meets or exceeds the feasibility threshold, denoted by pcs. For an MAB-CS problem instance with K arms use o to denote the known cost associated with sampling any arm E [K], and μa to denote the expectation of the reward received from sampling arm i. The optimal arm in our setting is then the least cost feasible arm. Mathematically if S = {i E [K] : μ pcs} denotes the set of feasible arms, then the optimal arm a² arg minjes
To honor the dual objectives of minimizing cost while maintaining feasible reward, cumulative cost and quality regret over a time horizon T, for instance v, with policy π are defined as follows,
K
Cost_Reg (T) =
Σ
Ex
(Ck, - -c-))
(n,
t=1
Quality-Reg (T, v, T)
Σ t=1
Ex (HES mxx))
Σ i=1
A O B [n (T)
Where k; is the arm sampled by bandit policy π in time slot t, and n, (T) is random variable denoting the number times arm i was sampled over T time steps. The initial definitions of regret accumulated over horizon T in the center have been re-written in terms of the expected number of samples of each of the K arms at the right. Moreover we have used the definitions of cost gap Ac,i = (c. Ca-) and quality gap Aq.: (Pes p4) in the decomposition. We highlight that as is standard for stationary stochastic bandits, the operator E, represents the expectation over the choices of arm hs made by policy æ during time slot l. In the remainder of this section, we discuss three variants of MAB-CS, each of which have different specification for μcs. We end by motivating the importance of t 2 where x denotes max {0, in the regret definitions.
Take as example the problem faced by marketing agency. Consider that there are three modal- ities available for the agency to deliver their message, which are: (1) very expensive personalized door-step solicitation, (2) moderately expensive automated phone call, and (3) inexpensive email. Given these modalities, the agency's goal may be to achieve a prescribed sales rate with the mini- mum possible cost. Or. the goal may be that sales be least a prescribed fraction of the sales of certain communication modality. Finally, we may not have reference mode in mind, and we may just desire a conversion rate that is (say) 80% as much as the highest unknown sales rate.
The first setting is captured by our novel contribution of the fixed threshold setting. In the fixed threshold setting we specify Pcs = No for a known M4 E R. We call the second setting the known reference arm setting which specifies pAcs (1-a) oaue.. Here e is the index of the reference arm, and E [0, 1] a known subsidy factor. The third setting was introduced in prior work and specifies MCs (1 a)u where μ² is the largest among expected rewards. In particular, μ² is the expected reward from sampling arm i* = arg [ax 14. Similar to the known reference arm setting a is the subsidy factor. We refer to this third setting as the subsidized best reward setting.
With the MAB-CS framework, we target applications that are agnostic to the level of quality as long the quality exceeds threshold Mcs. This structure necessitates the zero-clipped operation inside the cost and quality regret definitions. Consider for example a problem where known that customers need to be provided a certain (possibly unknown) service quality level for them to
2

---

Published as a conference paper at ICLR 2025
continue their subscription. Any quality top of the feasibility level pes would not improve the performance of our solution. For the marketing communication example from earlier, the quality threshold represents sales conversation rate beyond which the profitability of the campaign is ensured. In this case too we would like decisions that are agnostic to sales success over JAcs-
In the absence of the zero-clipped structure, cost and quality regret that are sub-linear in horizon could be achieved for our examples in an unintended fashion. An algorithm that samples sub- optimal arms j a" a linear fraction of times but balances positive regret from infeasible decisions, by negative regret from stellar decisions would satisfy the un-clipped quality constraint but would be unsuitable for our example applications.
1.2 KEY CONTRIBUTIONS
Our first contribution is to extend the MAB-CS framework to include two new settings. (1) The fixed threshold setting, and (2) The known reference arm setting. Second, we present instance dependent lower bounds on the expected number of pulls of any sub-optimal arm i * a" for our two novel settings as well as the third subsidized best reward setting from the literature.
Next, we present an original order optimal algorithm Pairwise Elimination (PE) for regret minimiza- tion in the known reference arm setting. Under PE non non-reference arms are pit against the reference arm in the ascending order of their costs. PE uses principled elimination based regret minimiza- tion algorithm called Improved-UCH (Auer & Ortner 2010 to determine whether an arm provides feasible rewards. We show that our PE has an instance dependent upper bound both expected cost and quality regret that is O (log 7), and that PE only samples arms more expensive than the optimal action a* at most constant number of times under expectation.
Next, we develop a generalization of PE for the subsidized best reward setting called PE-CS. We show that PE-CS too admits an O (log7) instance dependent upper bound on both cost and quality regret that involves both notions of conventional sub-optimality gaps and quality gaps. Not only PE-CS the first algorithm for the subsidized best reward setting with instance dependent upper bounds on regret, but also PE-CS offers a substantial improvement in performance over the only other algorithm from the literature for the subsidized best reward setting which admits guarantee, namely ETC-CS, Although we find that PE-CS is not order optimal for all instances, our contribution includes characterizing the class of instances for which PE-CS is order optimal.
RELATED WORK
There have been numerous works that impose additional structure onto the stationary stochastic bandits problem with the goal of better addressing specific application domains. This structure can sometimes come in the form of relationships imposed on the rewards of arms.
Structured Bandits:
These reward-relationshiis may be known (Kleinberg al.) (2008) or unknown (Gupta al.] (021). Adding constraints that depend on the risks associated with sampling the rewards of an arm as in Wu et al. (2016) Chen al. (2022) is another form of the structured problem.
Bandits with Costs: We contextualize the core contributions of this paper by comparing and con- trasting our setting and methods with related ones from the literature. We build on the MAB-CS setting introduced in Sinha et al. (2021). A core component of the MAB-CS setting is that there known cost associated with sampling any arm that is specified as part of the problem instance. There have been numerous works within the MAB literature that include the notion that price has to be paid for sampling an arm. Notably the Bandits with Knapsacks (Badanidiyuru et al.. 2018) line of work also considers setting with known costs. However, in (Badnnidiyuru et al. (2018) 8) there a limited cost-budget and reward must be optimized while satisfying strict budget constraints. In MAB-CS and its variants the other hand, the goal is to minimize cumulative costs without there being any explicit constraints on cost. In MAB-CS, the constraints are in fact on reward, and are referred to as quality constraints.
Bandit with Constraints: The quality constraints in our work closely resemble the constraints on expected rewards that imposed in the work on Conservative Bandits (Wu et al., 2016). In both our work and in Wu et al.] (2016). there a constraint that requires the accumulated reward to exceed (1 a) discounted version of the reward of reference arm. The conservative bandits
3

---

Published as a conference paper at ICLR 2025
setting only considers the cases where either the return of the reference arm is known constant fo, or the case where the reference arm is known, but its return is unknown. The primary difference in our work is that in addition to satisfying quality constraint, in the MAB-CS setting, to minimize the cumulative cost. The notion of costs are completely absent in Wu et al. (2016), moreover, in addition to the cases with known reward threshold (Ap, and a known reference arm with an unknown return, which we consider as novel extensions to the MAB-CS framework, we also address the problem of the original MAB-CS framework where the reference arm the unknown best reward arm. Another key difference is that Wu et al. (2016) imposes the reward constraints in cumulative anytime manner, whereas we impose
must work
every time-step.
In our paper, we work with the notions of cost regret and quality regret which are identical to the ones introduced by Siinha et al. (202T), however unlike the setting in Sinha et al. (2021) which only considers the case where the reference reward comes from the so-far unidentified best reward arm, we consider the additional cases (1) Where there fixed known threshold to be exceeded, and (2) When there is a known reference arm E whose reward fe has to be exceeded however μ4 itself is unknown. In addition to our novel PE-CS algorithm for the setting from [Siha et al. (021)) we present novel algorithms for new settings (1) and (2) as well. In /Sinaa et al. (2021) the authors present three novel algorithms for the MAB-CS setting, the former two among which construct set of empirically feasible arms by interleaving exploration and exploitation. We build up our approach to optimizing for the regret objectives by first solving the known reference arm with unknown reward Pe setting using a successive elimination style algorithm that compares candidate arms one at time against the reference arm to see if they are feasible. We call this approach Pairwise Elimination (PE), and we adapt the elimination based regret minimization algorithm Improved-UCH (Auer & Ortner 2010) to develop it. Then we generalize PE the case where the reference arm is the unknown best reward arm by prepending PE with a Dest-Arrm-lennificaat (BAI) stage and call this latter algorithm PE-CS.
BAI and Improved UCB:
3 ALGORIHTMMS AND ANALYSIS
As discussed in Section I introduce novel settings called: (1) Fixed threshold setting with
JAcs -Ma. and (2) known reference arm setting with Jacs = (1 - a' In interest of building up to our presentation PE-CS we start with the known reference arm setting and relegate the discussion and analysis of the known threshold setting to Appendix H For the known reference arm setting, we present the lower bound and our novel Eliminatinnn algorithm in Section 3.1
Our PE algorithm builds upon Improved- UCCB (Figure in Auer & Ortner (2010), a regret mini- mization algorithm for the stationary stochastic bandits setting. We choose to build on the method since its successive elimination approach to regret minimization readily incorporates our insight that arms be evaluated in the order of their costs. One of the core features of Improved-UCB is that the cadence of sampling and elimination is governed by rounds. Each round is period where every active arm sampled to the extent prescribed by a function of the round number. round concludes when all active arms have been sampled sufficiently, and at the end of round, unsatisfactory arms are climinated. We inherit the use of these rounds and associated formulas from Improved-UCB.
Finally, our third setting has the reward threshold pcs (1 c))"". This subsidized best reward setting is strictly more challenging than the known reference arm e setting since the best reward arm i" itself is unknown. To solve it, extend the PE algorithm by pre-pending it with Best-Arm- Identification (BAI) stage to develop the PE-CS algorithm. The lower bound for the setting and the PE-CS algorithm are presented in Section 3.2
3.1 KNOWN REFERENCE ARM SETTING
The known reference arm setting specifies cccs = (1 a)) as the subsidized (unknown) return of a known reference arm. Without loss of generality, we assume that all MAB-CS setting bandit instances have arms indexed in the ascending order of their costs. In the known reference arm setting any arm with cost higher than ce is necessarily sub-optimal and can be pruned out. Moreover, in any instance with K arms, can think of arm l as the arm with index K + 1. First we provide an instance dependent lower bound on the expected number of samples of sub-optimal arms for a class of consistent policies. The definition of consistent policies is available in Appendix E
4

---

Published as a conference paper at ICLR 2025
Theorem 3.1 (Lower bound for known reference arm setting). Under any consistent policy the expected number of samples of a low cost arm and of the reference arm & are lower bounded as,
E [n (T)
li (T)
2)1-a)²
lim inf 7-000
for arms i i<a" 2.2
lim inf T-200
max +5Sa
log
log'I
Where T denotes the problem horizon and the rewards of all K arms are Gaussian distributed with variance o² Low cost is term used relative the cost of optimal arm a*.
The proof of Theorem 3.1 (available in Appendix E uses analytic techniques and arguments similar those used establish lower bounds for the classical multi-armed bandit setting (Garivier al. 2019). We now discuss our PE (Algorithm D for the known reference arm setting. Under this setting, quality regret is calibrated against the expected reward of the reference arm & which we denote μ4, For jointly optimizing cost and quality regret, we take an approach where the feasibility of arms evaluated in the order the costs of the arms: cheapest first. This insight motivates pairwise comparison between the reference arm and the non-reference candidate arms.
Function 1: Pairwise Elimination Function PE()
Function PE( Sample Vector, ju: Empirical Means, w: Round Numbers, T: Horizon, i: Episode, l Reference Arm, az Subsidy Factor ):
+ - 2 T
) A
3
for & E
if my {i do then return k,w, 11 his = k, round numbers w and ep. unchanged
8 + (og(T
6
2r
7
if (1 a) (pr + B) fu; 3 then
return 1, 1, None
// Declare i as winner, set episode to None
else if j4 + 8 < (1 a) (ite B) then return + 1, 1,w, i i unchanged, Update episode to that next candidate arm
10
// Sample next candidate arm, Rounds
11
else
12
Wi - wi +1 // Increment round only for arm i being evaluated return i,
13
// Move to next round within same episode
Algorithm 1: Pairwise Elimination (PE) for a known reference arm
Inputs: Bandit Instance Horizon T, Reference Arm É, Subsidy Factor Initialize: Samples nı = 0, Empirical Means jaM = 0, Current Rounds wa = vk [K] U {e), PE Episode
Time 1.
1 while t do if & (None, () then wi, PE(n, fa, w, T, updated round numbers, and updated episode number
2
3
// receive arm to be sampled,
4
else
5
// sample winning arm for remaining budget att + 1), natt + 1),t t +- sample and update(ke, ((t), // Appendix
L kt +- hi-1
PE tracks and updates three bookkeeping variables. The number of times each arm has been sampled n, the empirical mean reward sampled from each arm f., and the round ongoing by each w.
Although the round number achieved by arm & can be uniquely determined from its number of samples ng. we track them separately for more lucid presentation.

---

Published as a conference paper at ICLR 2025
For PE we asses candidate arms in the ascending order of their cost by assigning episode to each candidate arm. This is represented by the main loop in Algorithm [ in which is used to refer to both the index of the arm being evaluated for feasibility and to the episode number associated with that arm. PE( keeps getting invoked until all K candidate arms are evaluated and we reach episode or until when a lower cost feasible arm has been identified.
Inside the PE() subroutine the sample prescription T is computed using the current round number wi associated with candidate arm (line 2). Once the sample prescription T is met for both arm and arm &, we check for elimination. Since no samples are ever discarded, episodes that are further downstream will re-use samples of arm from prior episodes when n2 > т. If candidate arm is able to eliminate arm & then the optimal arm has been identified. Else if arm é is able to eliminate arm i, then the episode is incremented and we proceed to evaluating the next cheapest arm. If no elimination occurs, then we simply increment the round number wi. For the PE algorithm, we show the upper bound on cumulative cost and quality regret stated in Theorem [3.2]
Theorem 3.2 (Instance dependent upper bound cumulative cost and quality regret for PE). For bandit instance v, over horizon T, the expected cumulative cost regret E [Cost Reg (T, v)] and qual- ity regret E. [Quality Reg (T, of the PE algorithm upper bounded respectively as,
1 + max-
32 log (T)
At
Σ
43
43
max A
A 2
C.P
A
Q
CiSt
C2
Contribution from under
Contribution from arm under mats-terminationn in PE episode SSa"
Contribution from episodes "00 in case of mis termination during ep a²
nominal termination in P'E episode
32 log (T AQU
43 Aq.
43
AQst +
max Q a CICE
Contribution from arms < a" under nominal termination episode
Contribution from armms < a² under mis-termination PE episode Sa"
Contributtin from episodes >> In case of mis-termination during a²
There are two dimensions to the execution of PE being nominal. First, within an episode the worse quality arm should be eliminated after a reasonable amount of sampling. Second is that execution across episodes should terminate in episode a" (with arm & eliminated). To prove Theorem 3.2 we separately bound the expected number of samples of arms with cost lower and higher than the optimal action a", and the reference arm E. To bound these samples we condition on the desirable and anticipated events at both the intra and inter episode levels and show that the probability of these desirable events not occurring is small. The details are available in Appendix
Overall, we find that not only does PE achieve cost and quality regret that are O (lo but also PE matches up to constant factors the lower bound on cost and quality regret implied by Theorem 3.1 To see this clearly, we breakdown Theorem 3.2 by contribution. For cost regret, the O (log T) dependence on arm E is contained in the first term, and the dependence on higher cost arms is a constant captured by the third. For quality regret the first term captures the O (log T)) dependence on low cost arms, and the entire contribution of higher cost arms is captured by a constant.
Practical Extensions of PE. We highlight that although PE makes comparisons between the can- didate arms and the reference arm in a pairwise manner, samples of the reference arm are re-used across episodes. Since during most episodes the samples accrued shall be limited to ones of the can- didate arm undergoing evaluation, this sample reuse is a key feature of the PE algorithm and endows it with good sample efficiency. In PE as presented in Algorithm I during an arbitrary episode eval- uating the candidacy of arm i, the reference arm E shall only ever have to be sampled if the samples of arm start to exceed the samples of reference arm E that were already available. practice, we can implement another version of PE called asymmetric-PE. Asymmetric-Pin allows for mismatch between the number of samples of arms and é that go into computing the exploration bonus terms 3. The details of the variant and an example comparing it to vanilla PE are available in Appendix C
3.2 SUBSIDIZED BEST REWARD SETTING
Theorem 3.3 (Lower bound for subsidized best reward setting). Under any consistent policy n, the expected number of samples of low cost arms, high cost arms, and the best reward arm i" are lower
6

---

Published as a conference paper at ICLR 2025
bounded respectively as,
I8 [ng
(T)
2 i i<
me (T)
lim inf
lim inf
1-a - -1:)2 -
7-000
log T
A
I T
log T"
E [ng-
(T)
lim inf
2(11 a)² max
1 mii AQr S (1- (1-a) J.
log'T
A Q
Where Amin 1²* max44s p4g is the smallest conventional gap, denotes the horizon and the rewards of all K arms are Gaussian distributed with o² 1.
The proof of Theorem 3.3
closely parallels the proof of Theorem barring two salient differences.
First, in Theorem 3.3 there is a non-trivial lower bound on the number of samples of high-cost arms. This is because unlike the known reference arm setting the arm i and reward μx" are unidentified. Second, the lower bound samples of i* is not only function of quality gaps Aq. I a", but also depends on the relationship between min;ça- Âq. and the smallest conventional gap Amin- Next diseuss the extension of PE to the subsidized best reward setting develop PE-CS.
Algorithm 2: Pairwise Elimination for Cost Subsidy Problem (PE-CS).
Inputs: Bandit Instance Horizon T, Subsidy Factor Initialize: Samples ng = 0, Empirical Means NI = O, Current Rounds wi. = 0 V E [K]. BAI Active Arms A = [K]. Arm f None, PE Episode 1, Time f 1.
1 while & To if (AA) then kr, W. <- BAI(n, p, A)
2
3
// receive arm to be sampled, updated round numbers, and updated active arms if (len(AA) = then L A[0] continue
// set l to be identified best arm // ignore sample zecomnendation h
7
else i & {None, f} then
w, PE(n, fi, w. (,i
// receive arm to be sampled, updated round numbers, and updated episode number
9
else
10
// sample winning ing arm for remaining budget AL + 1), nll + 1), aample_and.update/ (()), // in Appendix
he hi-1
11
When solving the subsidized best reward setting we face the additional challenge that the arm i" unidentified. To solve this problem, PE-CS (Algorithm comprises two stages, the BAI stage and the PE stage. The BAI() ) subroutine uses the same round mumber based cadence of sampling and elimination leveraged in PE() and is specified in Appendix B Function 3 Under BAI() ) once the set of active arms collapses to a single arm, sampling decisions are passed over to the PE stage.
The PE stage in the PE-CS algorithm works identically to the PE algorithm described in Algorithm T In fact, due to the modular and phased nature of PE-CS we use precisely the same subroutine Func- to make best of the
tion for PE(). For the PE-CS algorithm, there is all the more accumulated samples of the reference arm since not only can ny accumulate during episodes of the PE stage, but also acerue in the BAI stage where the empirical best reward arm é is the last sur- viving and therefore most sampled arm. In passing control from the BAI stage to the PE stage, key role played by the ongoing rounds w. Used in both BAI() and PE() ), w is responsible for tracking the round up to which any arm has been sampled at any point in time. Once the time comes for passing over control from BAI() ) to PE(). ), the PE stage is able to pick up sampling and elimination checks in any of its pairwise comparison episodes right where the BAI stage left-off. For PE-CS we show upper bounds on expected cumulative cost and quality regret in Theorem 3.4
Theorem 3.4 (Instance dependent upper bound on cumulative cost and quality regret for PE-CS), For bandit instance u, over horizon T, the expected cumulative cost regret TE [Cost Reg v), and
7

---

Published as a conference paper at ICLR 2025
quality regret E (Quality Reg (T, wi] of the PE-CS algorithm are upper bounded respectively as,
32 log (TA?)
43
32
43
A C,s'
+ max DEA
+ C.5
A
2
A
AQ
Q
Q,a'
32
43
32 log (T
1>a [K]]
max
A
C₁
A
+
A Q,a
Σ
Aci
1
4
4'
11
32
max A kE(K]
Σ
A
A
mnn
jji
3ogog (TA (.5)
a' -1
43
32
43
Qq.t +
+
max isa' KE(K]
At
AQ,i
A
Q,a"
Σ Q
32 log (TA?) 1+
max Q SE[K]
11
32
A
A2 min
A
is SE(KTMPP
j
Where A, = 1t¹ Mi are conventional gaps, Amin p max bs is the smallest conventional gap, and A = [Amin] U {Aq.i) is defined to bound samples of arm i* under expectation.
We bound the expected number of samples of any arm under PE-CS by first conditioning on the outcome of the BAI-stage being either proper (L i') or improper (E * i²). The phased nature of PE-CS admits modular analysis where conditioned on the outcome of BAI being proper, the bounds on samples shown in Theorem 3.2 for PE hold with slight modifications. In particular the three leading terms in the PE-CS bounds correspond directly (in order) to the three terms in the PE bounds for cost and quality regret. The fourth term in both the PE-CS cost and quality regret bounds corresponds to samples of high cost arms accrued during the BAI stage and the fifth term is the constant contribution to regret from an improper BAI outcome. Proof is available in Appendix G
Finally, with Theorem 3.2 we see that both the expected cost and quality regret are bounded by a quantity that is O (log l). On comparing the upper bounds in Theorem 3.4 to the regret lower
bounds implied by Theorem 3.3 we find a gap between the two. This gap arises from the class
of bandit instances where precisely identifying arm i' using BAI detracts from the actual goal of sampling cheap feasible arms A more detailed discussion is available in Appendix
EXPERIMENTS
In Section 3 we presented the merits of the PE and PE-CS algorithms in the known reference and subsidized best reward MAB-CS settings. While the presentation so far has been based exclusively on theoretical bounds on cost and quality regret here we complement our theoretical analysis with a study of the empirical performance of our methods In particular, we compare PE and PE-CS with baselines from Sinha et al. (202T) on problem instances derived from real-world datasets. The real-world datasets we use are MovieLens 25M (Harper & Konstan 2015) and Goodreads (Wan & McAuley 2018). Next we describe how we make use of these datasets for our experiments.
The MovieLens 25M dataset consists of 25 million ratings for 62,000 movies rated by 162,000 users. It is popular dataset for studying the performance of recommendation systems. The movie ratings in the dataset are from numerous users and on 5 point scale. Moreover, every movie for which ratings are available in the dataset tagged with one or more genres. The Goodreads dataset already comes organized into overlapping genres with a single genre containing between 36,514 and 335,449 books. Each book is associated with at least one numeric review, and the number of reviews associated with the books tagged with certain genre range between 150 thousand and 3.5 million.
Our Goodreads and MovieLens experiments simulate a scenario where a book subscription service or movie streaming website attempt to recommend books and movies to their users. The available
Code available httpthttt///gih/io shank waahhaann-jjjjjjjaeae
/bbandi ttsttts- t.stwttttttt witht costs
8

---

Published as a conference paper at ICLR 2025
MovieLens varying
Goodreads varying!
pe
10n
cs
Quality Regret
Cost Ragret. Quality
1.0
107
Cost Regret
100
10"
13
1.
7M
Arm i index
Arm Index
MovieLens varylng o, Known
Goodreads varylng Known
106
Cost Regret Quality Rogrett
403
Cost Qualltt
10*
10-
10a
10*
Subsidy Factor
Subiidy Factor
Figure 1: Fig. I(a) varies the index L for MovieLens. Fig. 1(b) does the same for Goodreads (a both). Fig. I(c) fixes = 11 and varies a for MovieLens while Fig. I(d) fixes for Goodreads and varies Data points represent terminal regret at T =5M and each data point represents the outcome from an experiment. There are 25 such independent runs for each algorithm. There is no inherent notion of reference arm in either dataset, & is picked arbitrarily.
selection organized into genres and the service deploys a recommendation system to decide which genre of content be served to its user. Whenever genre chosen by the recommendation system, a random book or movie tagged with that genre is drawn with replacement. Under these conditions, bandit arms become natural abstraction for genres. The cost associated with pulling the arm corresponding to a certain genre is simply the average of the royalties that must be paid to the authors or producers for every new reader of book or streamer of movie. Since royalty data is unavailable as part of either two datasets, we draw the costs associated with sampling any bandit arm (genre) lie uniformly at random between and 1. For every genre we first obtain the mean 5 5-point scale rating of all books movies tagged with that genre and then divide this rating by so that it lies between and 1. We then treat this fractional rating as the expected reward return from that genre. Through this process we end up with bandit instances consisting of 20 arms for MovieLens and 8 arms for Goodreads the details which are available Appendix
In experiments discussed in Section 4 we plot the summed together values of the cost and quality regret. The goal in all MAB-CS settings is to converge onto sampling optimal arm a*. To do so reliably we must explore sufficiently but eventually regret allows us to compare the merit of various methods in achieving this goal. tangential yet interesting goal is to understand the trade offs between cost and quality regret. To better showcase the performance our methods we relegate trade offs to supplemental experiments in Appendix
exploration. Looking at trends in summed
4.1 EVALUATING OUR PAIRWISE ELIMINATION (PE) ALGORITHM
To understand the effectiveness of PE empirically, we compare CS algorithm from Sinha et al.] (2021). In the specification of UCB-CS (Algorithm 5 Appendix B), the target reference arm (whose reward determines μocS) is the best reward arm t". UCB-CS estimates the index of arm i" as the arm with the largest UCB-index in any time-slot. To develop comparison with PE for the known reference arm setting, we simply replace this estimate with the known index of the reference as UCB-CS -S Known & and compare to PE on MovieLens and Goodreads Figure [ From the summed regret results in Figure] I we find that approach outperforms UCB-CS invariably for
natural variant of the UCB-
while retaining the rest of the Algorithm. We call this variant

---

Published as conference paper at ICLR 2025
Cost Regret + Quality Regret
Average Regret
MovieLens varying
200K
Cost Regret Quality Regret
10"
pe-cs
etc-cs
-07
150K
ts-cs
30
100K
100
50K
0.0
toics
0K
101
0M
1M
2M
3M
4M
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
Time (t)
Subsidy
Cost Regret + Quality Regret
Average Regret
Goodreads varying
80K
10a
60K
pe-cs ts-cs
30*
Regret + Quality
10
40K
102
20K
pe-cs
15-05
0K
ucb cs
esc
0M
1M
2M
5M
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.90
0.45
Time (t)
Subsidy Factor
Figure 2: Fig. 2(a) shows the regret trend for MovieLens and Fig. 2(c) does the same for Goodreads. Both are for 0.25. Similar to Fig. 1(c) and (d)) Fig. 2(b) and 2(d) show the terminal regret trend (T =5M, 50 runs of each algorithm). UCB-CS omitted from (a) and (c) its regret was orders of magnitude worse as can be seen from Fig. 2(b), 2(d).
smaller and when the reference arm lies in the cheaper half of all available arms. We highlight that UCB-CS lacks any performance guarantees and is susceptible to linear regret, as demonstrated in Appendix A Figure ? Overall, we contend that UCB-CS is unreliable and typically performs worse than PE.
4.2 EVALUATING OUR PE-CS (PAIRWISE ELIMINATION COST SUBSIDY) ALGORITHM
In Section we saw that PE-CS admitted logarithmic instance dependent guarantees on expected cumulative cost and quality regret. The only algorithm for the full cost-subsidy problem from the literature that has an upper bound guarantee on expected cumulative regret is the ETC-CS algorithm from Sinha et al. (2021). Moreover their work also prescribes the UCB-CS and TS-CS algorithms which are approaches to solving the subsidized best reward problem that interleave exploration and exploitation but lack any performance guarantees. The three algorithms ETC-CS, UCB-CS, and
TS-CS comprise all the algorithms from the literature and are specified in Appendix B PE-CS against all three these approaches Figure
We compare
ETC-CS consists of pure exploration phase where each arm is sampled O (T2/3) times followed by an exploitation phase. As the only other algorithm with a regret guarantee ETC-CS is our primary competitor. Moreover PE-CS also outperforms the UCB-CS baseline and the latter algorithm has linear regret trend arising from persistent mis-identification of the best action. Although we find that the average of the regret for TS-CS is lower than PE-CS, closer examination the regret trend (Fig. a(a)) reveals the problem with the performance of TS-CS. While initially it takes PE-CS more exploration to lock onto the best action, it does so in a consistent and reliable way and once does, there is further incremental regret. Whereas for TS-CS, while interleaving exploration and exploitation leads to lower regret at the outset, there is a distinct slow-but steady upward trend in regret observed for the method.
10

---

Published as a conference paper at ICLR 2025
5 ACKNOWLEDGMENTS
This research was generously supported by National Science Foundation (NSF) grant CNS- 2103024, NSF grant CCF-2007834, Office of Naval Research (ONR) Grant N00014-33-1-2275, Cargenie Institute of Technology Dean's Fellowship and the CyLab Security and Privacy Lab at Camegie Mellon University.
REFERENCES
Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armes bandit problem. Periodica Mathematica Hungarica, 61(1-2):55 65, 2010.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks.
J. ACM, 65(3), mar 2018. ISSN 0004-5411, doi: 10. 10.1145/3164539,
URL https:///oi.
org/10.1145/3166.
Tianrui Chen, Aditya Gangrade, and Venkatesh Saligrama. Strategies for safe multi-armed bandits with logarithmic regret and risk. In International Conference on Machine Learning, pp. 3123- 3148. PMLR, 2022.
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-39,, 2019.
Samarth Gupta, Shreyas Chaudhari, Gauri Joshi, and Osman Yağan. Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory, 67(10):671-6633) 2021.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM doi: 10.1145/2827872. URL
Trans. Interact. Intell. Syst., 5(4), dee 2015. ISSN 2160-6455.
http::://doi.org///// 0et.g//....11/22221711
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium Theory of computing, pp. 681-6986999099 2008.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms.. Cambridge University Press, 2020.
Deeksha Sinha, Karthik Abinav Sankararaman, Abbas Kazerouni, and Vashist Avadhanula. Multi- armed bandits with cost subsidy. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceed- ings of The 24th International Conference on Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pp. 5014-3024 PMLR, 13-15 Apr 2021. URL
Mengting Wan and Julian McAuley. Item recommendation on monotonic behavior chains. Pro- ceedings of the 12th ACM conference recommender systems, pp. 86-94, 2018
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvari. Conservative bandits. In Maria Flo- rina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1264- New York, New York, USA, 20-22 Jun 2016. PMLR. URL https: pestps://proceee http://pcceens....//. mml. press/ 8 wu htmll
11

---

Published as a conference paper at ICLR 2025
A SUPPLEMENT TO EXPERIMENTS
MovieLens 25M Experiment
1.0
C15
0.8
Expected Quality
0.02
0.07
0.09
0.38
0.42
0.53
0.55
610
0.80
0.65
0.83
0.93
0.6
0.4
0.70
0.71
0.70
0.66
0.67
0.72
Min
0.70
p13
6.76
0.70
0.72
0.71
0.2
0.0
1
2
3
4
5
10
11
12
13
14
15
16
17
18
19
20
Am Index
Figure 3: Problem instance for MovieLens 25M experiments
Goodreads Experiment
1.0
0.8
Expected Quality
0.78
0.28
0.35
0.39
0.53
0.57
0.89
0.85
0.6
0.4
0.68
0.66
0.67
0.64
0.69
Aig
0,71
0.2
0.0
4
6
7
Arm Index
Figure 4: Problem instance for Goodreads experiment
EXTENDED COMMENTARY EXPERIMENTS SECTION
A close examination of the Algorithm descriptions for UCB-CS and TS-CS reveals the source of their unreliability. Both these algorithms work by constructing set of empirically feasible arms and choose to sample the cheapest arm in this empirical set. This approach is vulnerable to feasible arm being consistently excluded as result of an initially poor performance. In our PE-CS on the other hand there is systematic comparison between the arms where they evaluated in the order of their costs and eliminated only when they have been sampled to be excluded with sufficient confidence.
To take closer look at the sensitivity of PE-CS and all three baselines, we perform an additional synthetic experiment the known reference arm setting which we call the toy experiment. For the toy experiment, arms. Then we run all four algorithms over 50 independent runs each instance. The expected reward of the first in the instance varies uniformly in the range 0.6 through 0.93 over the 12
create family of 12 subsidized best reward problem instances each with four
12

---

Published as a conference paper at ICLR 2025
instances in the family. Since the optimal return in all instances is f 0.95 and the subsidy factor a = 0.2, the reward threshold pcs for all the instances is 0.8 x 0.95 = 0.76.
We plot the results from the toy experiment on scatter plot. On the y-axis is the summed terminal cost and quality regret (in log scale) and on the x-axis is the value of the varying expected return of the first arm of the instance family. Firstly, find that almost all instances, PE-CS performs either similar to or better than our primary comparator ETC-CS. Among the 12 instances tested here, the ones where the return of arm is close μccs 0.76 the most challenging. We find that most runs of UCB-CS and several runs of TS-CS are unsuccessful at satisfactorily solving the N1 0.78 case. Moreover, from Figure 8 we conclude that among the four algorithms tested here, PE-CS arguably offers the best balance between performance and reliability.
TRADE OFF BETWEEN COST AND QUALITY REGRET
Tradeoff In Subsidized Best Reward Setting
Terminal Cost Regret
10
Terminal Cost Regret
10a
10y
10>
20a
10²
10--
pe-cs ucbics
ts-cs
eto.cs
10a
10a
10
10
10F
10'
10'
16'
10'
Terminal Quality Regret
Terminal Quality Regret
Figure 5: Trade off between cost and quality regret for subsidized best reward setting with Movie- Lens (left) and Goodreads (right). The data used for visualization remain the same as the experiment in Figure Section
Tradeoff Reference Setting
Terminal Cost Regret
Terminal Cost Regret
:07
10p
10F2
10>
20?
20a
101
201
10a
107
207
10'
10a
10a
107
10'
10*
10"
Terminal Quality Regret
Terminal Quality Regret
Terminal Cost Regret
100
Terminal Cost Regret
20+
20*
202
10²
pe
101
200
10a
10a
20"
10a
10a
107
10"
10*
Terminal Quality Regret
Terminal Quality Regret
Figure 6: Trade off between cost and quality regret for known reference setting with MovicLens (left) and Goodreads. The data used for visualization remain the same as the experiment in Figure Section 4 Top plots bottom two we use the data from the varying a with arbitrary fixed in known reference arm setting.
the data from the varying in known reference setting, and
13

---

Published as a conference paper at ICLR 2025
Average Regret
Cost Regret Quality Regret
1400K
pe
ucb-cs
1200K
1000K
800K
600K
400K
200K
0K
0M
1M
3M
5M
Time (t)
Figure 7: Fixed MovieLens Experiment. In the experiment: b= 11, u4 0.703, Pccs 0.668.
Toy Experiment
10c
pe-cs ucb-cs
ts-cs etc-cs
Cost Regret + Quality Regret
10a
10a
10a
102
101
0.60
0.63
0.66
0.69 0.72
0.75 0.78 0.81 0.84
0.87
0.90
0.93
Expected Return of Varying Arm
Figure 8: Toy Experiment performed using family of four armed bandit instances. Expected
rewards: μ1 = 0.6..... 0.93, μ1 = 0.81, #3 = 0.95, f4 = 0.8, and costs: = 0.05, 0.9, C4 1.0. subsidy factor: a 0.2.
0.9, =
14

---

Published as a conference paper at ICLR 2025
B APPENDIX ALGORITHMS
In this Section we collect all the Algorithm blocks relevant to our work that couldn't find space in the main paper. First we present the sample_and und_daee ) subroutine used in Algorithm and Algorithm 2 and also used in the baselines in the current Appendix section.
Function 2: Sample and Update Function update variables in in-place and return them
Function sample and update( kę Chosen Arm, ft: Empirical Means, n: Sample Vector; t:
Time-Step ):
1
ju, (1 + 1) + (jxx, (1) x Ti, (1) + (rx)/(mn, +1) // sample reward for arm k nk, (t) +1
sample(ki)
2
// update mean // update number of samples return (t + 1), n(t +), // return updated means, samples, and
3
nk. (t +
4
same-step
Next we have the specification for the sub-routine BAI() used in PE-CS Algorithm 2
Function 3: Best Arm Identification BAI()
Function BAI( n. Sample Vector, ft: Empirical Means, wt Round Numbers, T: Horizon, A: Active Arms ):
1
Â 2 maxie[M]
log (T
2
A=
3
for &s E A do
if nr < then
return k w. A // next arm to be sampled, unchanged w and A
log (T2)
2r
7
for A do
8
/LUB LLCB &- in + 3, 3
UCB
9
At + EiE A: UCB 2 maxjeA LBBB // update set of active arms
10
h: t Uniform (A+)
// tentatively, the next arm to be sampled
11
forie + do
12
L Wi + wi +
// increment round number for still active arms
return hr, A+
Next, we provide a precise specification of algorithmss from prior work that we compare our methods against. In particular these are the ETC-CS, TS-CS, and UCB-CS Algorithms introduced by |Sinaa
al. (202]) and specified in Algorithms 3 and 5 respectively. For the upper bound on regret
provided in Sinha al. (2021) hold, we require the exploration budget satisfy = c f where e is some unspecined proportionality constant. Based on few trial runs and examples we pick since in the average case, the above seemed to give the best performance overall for the ETC-CS approach.
15

---

Published as a conference paper at ICLR 2025
Algorithm 3: Cost-Subsidized Explore-Then-Comin (ETC-CS)
Inputs: Bandit instance v, Cost Vector Horizon T, Exploration Budget 7. Initialize: Empirical means jıg: 0, Number of Samples O, Ak E [K].
while _ Kr do
2 :; 4- t mod K Ít + 1), re(t + 1), + sample.and.updatt(/. ((t), ())
3
while KT
do
5
for i E [K] do
(i(t)= + / 2
6
mi(l]
7
puCB + min (t) + (:(
8
1LCB + max (ár(()) 8:(1).0
9
& arg max (()
10
Reas(t) () {i: 14, UCB (t) 2 (1 aa)
he 4 arg (e C
12
it + 1), nlt + 1), + sample and update( (i, (((),
Algorithm 4: Cost-Subsidized Thompson Sampling with Beta Priors (TS-CS)
Inputs: Bandit Instance v, Cost Vector c, Subsidy Factor o, Beta Priors and Binomial Likelihood (Bernoulli Rewards).
Initialize: Successes S₁ = 0, Failures Fi. = 0 4 [K].
while - do
2
ha <- 1.
rt < sample (kit)
4
Sp, (t + t- Sk, (t) +
5
(t+ f- Fk, (t) +
6
(+t+1
7
while K <t do
for [K]
9
L (t) ~ Beta (S:(t) + 1, Fi(t) +1)
10
+ arg e [K] (t(
Feas(t) t {i: (t) 2 (1 a (t)
12
ha arg min,gFeas(!) C
13
rit sample (kx)
14
St, + Sk, (t) +
(1+ (1) (1) (1 r²)
C ASYMMETRIC PAIRWISE ELIMINATION
Algorithms I and as described in Section 3 use Function 1 PE() sub-routine. While in PE() the round number Wi is used to determine the stipulated number of samples for both the candidate arm and the reference arm f, this does not have to be the case. By the time we commence episode i to evaluate the candidacy of arm i, we would have already accrued numerous samples of arm l. In particular, we denote the number samples arm as ne(t) = Twes where the vector w, first introduced in Section 3 is vector recording highest round up to which the samples of each arm have evolved. Consequently, Wy is the highest round number reached for the samples of reference arm l.
Based on this observation about the greater progressed round number We we create a variant of PE called Asymmetric-PEs in Function 4 that replaces Function I in Algorithm [
Asymmetric-P described Function has all the same inputs that conventional PE did. addi- tion, it has input 6. called the Maximum round deviation. While have bound how much
16

---

Published as a conference paper at ICLR 2025
Algorithm 5: Cost-Subsidized UCB (UCB-CS)
Inputs: Bandit Instance v, Cost Vector c, Horizon Subsidy factor a.
Initialize: Empirical means fig = O, Number of Samples ne = 0 A E [K].
while I do
2
ha t-t. At + 1), n((t + 1), t + sample.and..uddatt(H... (tt),
3
while K <t< do
5
for i E [K] do
(((t) +
/2logT
ni(l)
7
u t min (t) + 3:(t), 1}
8
+ arg ma UCB (t)
9
(las(() &i [K] J 2 (1- a)) pe,
UCB
10
le arg (f Ci
11
Át + 1), n(t + 1), + sample.and.update((. ((t),
Average Regret
700.0
Cost Cost Regret Quality Regret
600.0
500.0
asymmetric- pe
400.0
300.0
200.0
100.0
0.0
0K
50K 100K 150K 200K 250K 300K 350K 400K Time (t)
Figure 9: An experiment that illustrates potential savings in regret from the asymmetric-pe opti-
mization. Bandit instance with Expected rewards: μl = 0.74, #2 = 0.5, μ3 0.8, μ4 = 0.75, and costs: C 0.15, C2 = 0.2, cg 0.21, C4 0.25, subsidy factor: 0.0, = 3.
larger we is compared to wi. when it comes to inferring the gap Å corresponding to arm in Line of Function 4 we restrict the round number we use be most larger than the round wi.
Effectively, the use of the further advanced round number trades performance for tightness of the upper bound (as we shall see in the analysis of Section F.. We get an improvement in performance since Be < 3r potentially leading to resolution in lines 7 or of Function with smaller value of 3, thereby requiring fewer samples of candidate arm i.
17

---

Published as a conference paper at ICLR 2025
Function 4: Asymmetric Pairwise Elimination Function Asymmetric PE()
Function Asymmetric PE( fa: Empirical Means, f: Reference Arm, n: Sample Vector, T: Horizon, w: Round Numbers, i: Episode, az Subsidy Factor, k: Max Round Deviation ):
1
for k E { do
2
Å +- 2- min(wctx.w)) the smaller of we or wi + R.
11 when k= we use War if k =
2 A
3
o
if n& < Tk then return k w
// h = round numbers and ep. unchanged
8x (ng(TA()
6
7
if (1 a:) (ite + BB) f4 3, then
8
L return L.W.Nnnee
// Declare i as winner, set episode to None
9
else 14 + 3; < (1 a) (iu - 3r) then
10
return + l,w, unchanged, Update episode to that of next candidate arm
// Sample next candidate arm, Rounds
else
12
// Always increment round of arm i We + max (wi, // we unchanged until w; > wr. After which wr tracks Wi return i, i,
+ wi +1
// Sample arm i, Stay in same episode
18

---

Published as a conference paper at ICLR 2025
D PRELIMINARIES
In this section of the appendix, we collate the preliminary results required for the analysis of our cost- subsidy framework algorithms that follow the forthcoming sections. The results stated without proof are standard results from the MAB literature.
Definition D.1 (Subgaussian Random Variable). We say that X a-subgaussian for any 2 0,
Pr - E S exp 20
Lemma D. (Bounded random variables are Subgaussian, Example 5.6(c) in Lattimore & Szepesvári (2220). If Random Variable X E [a, b) almost surely, then X is b- subgaussian.
2
Lemma D.2 (Hoeffding Bound, Section 5.4 in Lattimore
Szepesváni (2020). Ler
X1, X2,..., Xn be independent random variables, each bounded within the interval [a, bj
a S X; S The empirical mean of these variables is given by,
X=
X
(2)
Then Hoeffding's 's inequality states that,
2nt2
Pr (X - E S exp (T(b - a)²
(3)
Lemma D.3 (Iterated expectation over mutually exclusive and exhaustive events). Let X be any tegrable random variable over probability space (12, Pr), and let {E, be a collection of mu- tually exclusive and exhaustive measurable events. That is U E, = S and E; n nE = 6, Vi E [n), 8 # j. Then the following identity holds,
[ = E EIXIEEXXI Pr.)
(4)
As a special case if the events are just some E and its complement E then,
E [ = E E
E Pr (P))))+B [ E (r
(5)
Proof. Define a sub o-algebra of F, g = { E1, Ez,..., En, 22). Then,
"o,...,,..: E [ = E | |X []] (Because C F)
(6)
Σ E E P))r(E.).
Lemma D.4 (Expectation is at most equal to larger of the conditioned expectations). Let X be any integrable random variable over probability space (S, F, Pr), and let (E,)² be collection of mutually exclusive and exhaustive measurable events. That is U E, = S and E, Ey o, Vi,j E [n]. i + j. Then,
[X]
max [E E.]. n
(8)
Proof. Lemma D.4 can be considered a Corollary to Lemma D.3 as is illustrated by the following proof,
X = Σ
E[X E, Pr(()) (From the proof of Lemma D.3)
(9)
t=1
19

---

Published as a conference paper at ICLR 2025
(max [ Fa]) rEin)
Pr (Fa))
(10)
max
E [X| E.]] sein]
(11)
Lemma D.5 (Regret Decomposition Lemma, Lemma 4.5 in Lattimore & Szepesvári (2020)). For any policy π. and stochastic bandit environment v with K arms, for horizon T, the Expected Cumu- lative Regret Reg, (T, of policy in satisfies.
E Reg (T,
Σ A, (T)]
(12)
SE|K]
This result may be trivially generalized to other notions of regret where the gap determining the incremental regret due arm is some arbitrary Ax In this case, the regret decomposition shall be,
E Reg x (T₁ = Σ (n,
(13)
(E[K]
In particular in our problem we have Cost and Quality regret which are,
E Regs,
Σ
Ac,
[n
(T))
(14)
KE(K]
MaullityReg([T) []]= = Σ
A
(T))
(15)
Q
kE(K]
20

---

Published as a conference paper at ICLR 2025
E INSTANCE DEPENDENT LOWER BOUNDS FOR MAB-CS
LOWER BOUNDS FOR THE KNOWN REFERENCE ARM SETTING
We consider the case where the reference arm, denoted by arm L, is known. Let = fu...=.....KK denote the vector of reward distributions associated with all arms = ........ where the index of the reference arm be thought of as l K 1. Let M denote the model under consideration that is a collection all possible instances v. Recall that without loss generality we assume the arm indices are ordered, i.e., ei 02 defined as the cheapest arm whose mean reward meets the feasibility threshold pacs In the known reference arm setting, the feasibility threshold defined as pcs (1 - a)pu for some a [0, where is the mean reward of the reference arm L, which yields a" arg (Bx2((1))))) Cs
CK Gr, and that a" denotes the optimal action
Definition E.1 (Consistent Policies). A policy is consistent for all bandit instances v and for all arms * a", E [ns (T)) = o(T") ) for all 0 < S 1
Definition E.2 (The key quantity Dint). Let KL denote the Kullbuck-Leiün Leibler divergence between two probability distributions. Given distribution E M and real number a, we define
2,, x)
inf (KL(v,, v/)) v E M and Elv/ z).
where E[v]] denotes the mean of the distribution v4. We also need slightly modified version of this key quantity defined as follows:
D inf (KL(V,,)) v/): E.M and Flv1)
Although not always explicitly stated, we will be using Di x) for distributions vs with μ4 and Us us, x.) for distributions vs with ps > x.
Proofs of both Theorem E.2 and Theorem E. follow arguments similar to those used in establish- ing the well-known lower bounds for the classical multi-armed bandit setting. Here, we adopt the approach presented in Garivier et al. (2019) that is based the following fundamental inequality (Garivier et al. [0]))))) For any 1,,1'
(T) 2 [.,,
(16)
RE(I....,KK K.e)
where kl denotes the Kullback-Leiie divergence for Bernoulli distributions, i.c.,
P q vp,q [0, 1)3 kl(p, q) p log
p) log q
and where is any random variable with values in [0, 1] (that is measurable with respect to the probability space that all reward random variables are defined on).
p.(T) We will use (16 with Z T for some arm i, and will also rely on the bound
kl(p, q) plo P + p) log 1-P z (1 p) log 1
log
(17)
a
-
Theorem E.1 (Lower bound for the number of pulls of low-cost arms). For any bandit instance over horizon T, for all consistent strategies, we have
Ep [ns (T))
lim inf T-20
for arms i 1....,a" a" -
log T Dur(v, (1- (1-a))e))
Proof. Given any bandit instance v and any arm I,..., a' 1, we consider a modified instance // where i is the unique optimal action: v/g = My for all E {l.... K, { {i} and 1/f is any distribution in M such that its expectation μ4 satisfies 1f 2 (1 aa)e The key idea here is that any consistent policy should have E, [n,(]) = o(T>) while E, [n,())) = o(?)). We now apply the fundamental inequality (16) with Z = (7) Noting that all KL terms except that for arm i is
zero on the left hand side and using (77). we get
E, [m,
Ep n (T)
(T) 2 kl
T
T
21

---

Published as a conference paper at ICLR 2025
(1- Ey [n,((T) Given that arm i o a" in instance and i= a" in v', any consistent policy must have Ex (n; o(T?) and Ey [T)(T) T o) which leads to.
T log
log
(18)
T
T Eg (T:(T))
Ex [n, 1 (1-
T
lim inf T log T
log T En (m²
2 21-7
T
for all 0 0 1. Thus, we get
EN [n (T)
liminf 7-500
(19)
log?7 T
KL(P;, 14)
and taking the supremum in the right-hand side over all distributions μt 2 (1 aije,, we get the bound of Theorem E.
Remark E.1. The line of arguments used the proof given above would not yield a similar lower bound for high-cost arms, i.e., arms i = a" + 1,..., K. This is because even if the reward distri- bution of an arm E {a² + +,.... . K} } is modified to make its mean exceed the feasibility threshold (1-a) (1-a))g, arm a would remain to be the optimal action and thus would not be able state that E. [m)] = - o. This is consistent with the upper bounds established in Lemma F:7 for our PE algorithm where the number of samples for high-cost arms seen be upper bounded by a O() term. In fact, the upper bounds for the PE algorithm will be seen to match within a constant factor the lower bounds for all sub-optimal arms; see Remark E.2 below.
Theorem E.2 (Lower bound for the number of pulls of the reference arm E). For any bandit instance over horizon T, for all consistent strategies, we have
{
[ng (T)
1
lim inf T-200
2 max
max ii=1 'i=1....,a" a
(20)
log T
Dinr (ves
Muu I-a
Dins (ve, I
Proof. Proof of Theorem E.2 follows similar arguments to that of Theorem E. but requires more subtle application of the fundamental inequality (T6). We will first establish the second part of (20) (associated with modifications that make an arm i a" optimal) followed by the first part (that arises from modifications that make an arm > a" optimal).
Consider any bandit instance v with arm a" being the optimal action. If a* f, then any consis- tent policy must choose it at least T o(T") times and the bound given in the Theorem follows immediately. Next, we assume a* * f. Consider any arm = I,...,,'' a" - and note that we must have 14 Ma' for all such arms. Now, consider a modified instance v', where v/j Vj for all j 1,.... K and v/ is any distribution in M such that its expectation μu satisfies (1 (1-a) a)( 44- This means that arm is feasible in the modified instance v', and given that it has lower cost than a", a" is no longer the optimal action. In fact, in v', the optimal action is guaranteed be among .i} be the new optimal action. We will apply the fundamental
the arms (1.....4). Let j E (1....,i)
inequality 16) with Z (T) and note that any consistent policy should have E, [T)) o(T") while E. [T) = =T of (ry). Proceeding similarly with the proof of Theorem E.1 we get
Ear [n (Tx
E, (T) kl
T
T
Ey (ng((T)
T
1
log
log 2.
(21)
T
T Ey-Ey (T,
Noting that E,, [n, (T) = (T)) and Eg [n,(T)) = o(T)) and using similar arguments as in
the proof of Theorem E.1
we get
E, [ine (T)
1
lim inf T-000
(22)
log T
KL(
22

---

Published as a conference paper at ICLR 2025
Taking the supremum in the right-hand side over all distributions 2/2 M with μáz $ a get
Ev [nne (T))
1
lim inf
(23)
I 100
log T
Diat
Ves I-a
Finally, since these arguments can be applied for any arm .,.... a
1, we get
E [n
(T)
1
lim inf
max
(24)
10000
log
Dint
Ves
pe 1-n
To complete the proof of (0 now consider modified distribution that would make a" sub- optimal. Consider any bandit instance y with arm a" o being the optimal action. Consider modified instance v', where 1/j = 2 for all = .....,K K
and 1/2 is any distribution in M such that its expectation 1lg satisfies (1 a)p} > uu- With this modification, the arm a* is no longer feasible and thus not optimal. The optimal action should then be in the set fa* + 1..., K. E). Let j E {a" + 1..... , K, { be the new optimal action. We will apply the fundamental inequality (T6) T
with Z = (2(2) and note that any consistent policy should have E. [n, (T)) = o(T%) (since in the original instance a* * j was optimal) while E, (T)(T)) T o(T"). Using the same ideas as before, we then get
Ev (rge (T) log T
lim inf T-000
(25)
KL(Ve, vs)
and taking the supremum in the right-hand side over all distributions v/ E M with 14 > t=a we get
Eg [nne (T)
1
lim inf T-000
(26)
log T
Dint
Ves i-o
Finally, we combine 24 and 26 to complete the proof of 20
Remark E.2. When the reward distributions are Gaussian, i.e. the family M of distributions con- tain all Gaussian distributions with a common variance a², the key terms Day(Us; x) and Do x) take the form of
Dog(us Us xt) Din(ui, x)) (14: - x2)
(27)
2a²
More generally, shown in Lattimore & Szepesvári (2020) that Din(Vi, O((p; x² for most distribution families. Using this with 6² 1, obtain from Theorem E.1 and Theorem E.2
that
[, (T))
lim inf 7'500
for arms i= 1, 1....,
log T
A2
and
E [ne (T)
2(1 - =x)2
lim inf T T-000
log
$5a
D2.s
where AQus is defined as before, i.e. AQ. (1-a)u μ4a These results match within a constant factor the upper bounds of our PE algorithm established in Lemmas F2 and F.3 showing that the PE algorithm is order-wise optimal.
LOWER BOUNDS FOR THE SUBSIDIZED BEST REWARD SETTING
We now present lower bounds for the subsidized best reward setting. The core ideas in establishing these results the same with those used in the known reference arm case. Namely, to establish a lower bound on the number of pulls needed from a given arm, we are secking a modification in that arm's reward distribution that leads to a change in the optimal arm, i.e., arm a" being
23

---

Published as a conference paper at ICLR 2025
longer optimal. Among the modified distributions that change the optimal arm, the that has the minimum KL-divergence with the original distribution leads to the tightest lower bound on that arm's 's number of pulls. We will repeatedly repetitive parts of the proofs are omitted for brevity.
this argument in the following discussion but the
Let M denote the model under consideration that contains all bandit instances v, where specifies the reward distributions V4 of all arms = 1..... K. Recall that the arm indices are cost ordered, i.e, ei < Co- < Ci- <... сk. where a" is the optimal action and i* is the arm with the largest mean reward; namely i* = arg [1... [4i and a* = arg ( where μr max,e 14 = prr The definition of consistent policy and key quantities Dant, Dint remain as in the previous section.
LOWER BOUND ON THE NUMBER OF SAMPLES FOR ARMS a
Theorem E.3 (Lower bound for the number of pulls of low-cost arms), For any bandit instance over horizon T, for all consistent strategies, we have
Ey [mg (T)
lim inf 7-000
for arms i ==,..... 1,...."" -
log T
Din(Ve, (1 a)))))²
Proof. For arms cheaper than the optimal action a', i.e., arms i 1,...,a" 1, our approach is to modify their reward distribution so that their mean reward is now larger than the feasibility threshold (1 aa) Since these arms have lower cost than a", a" will no longer be optimal in the modified instance, paving the way to establishing a lower bound for the number of arms Formally, given any bandit instance and any arm
.1,...."" 1. 1,..., ......a"" a* 1, we consider a modified instance // where i the unique best action: V/j = 1' for all j E {I...., ......,K - {i} and v/ is any distribution .M such that its expectation μ4 satisfies μ4 > (1 - a)ju In the modified instance v', the feasibility threshold is either (1 a),, as before, or it changes to (1 a) by virtue of arm being the arm with the largest mean reward. In either case, n4; exceeds this threshold and since < Cat, a becomes sub-optimal action. This proves that
E. [nn (T))
lim inf T-400
(28)
log
and taking the supremum in the right-hand side over all distributions vs E M with μ1 > ox) we get the bound of Theorem E.3
Remark E.3. arms =,.....a a
1, recall that the quality gaps are defined as Aq.i see from Theorem E.3 that when the reward distributions
(1-a)u² usy Recalling Remark E.2 are Gaussian with o²
E [n (T)
2
lim inf 7-000
A for arms i 11....,.d
log
T
matching the upper bound of PE-CS algorithm given in Lemma G.3
LOWER BOUND ON THE NUMBER OF SAMPLES FOR ARMS i > a", i
Theorem E.4 (Lower bound for the number of pulls of high-cost arms). For any bandit instance over horizon T, for all consistent strategies, we have
E, [n. (T))
inf 7-000
for arms i {a" + +....,,K K} - {
log
Ding Vi,
thr (1-aa)
Proof. For arms more expensive than a" but with mean reward less than jt, the only modification make in their reward distribution to render a' sub-optimal would be to increase their mean reward to a level where they will be the highest-mean arm and (1 (1-a) a times their new mean exceeds Mar (so that a" is no longer feasible and thus not be optimal). Formally, given any bandit instance
24

---

Published as a conference paper at ICLR 2025
and any arm {a* + 1, 1...., K} - { we consider modified instance v/ such that v/j "j for all j E {I,... K} {i} and v/ is any distribution in M such that its expectation μ satisfies (1 4) > Paa. In the modified instance v', we have 14 > h(1= - a) 2 p4. with the second inequality following from Pa- (1 --0 -))4 since a was feasible in the original instance. Thus, in the modified instance arm i has the highest mean and the feasibility threshold becomes (1 - a)pp
which exceeds the mean reward Ma- of arm a" by construction. Thus, in the modified instance v', arm a" is no longer the optimal action leading to
Ep [n (T))
1
lim inf T-000
(29)
log T
KL(U;, 44)
and taking the supremum in the right-hand side over all distributions v/ E .M with p4 get the bound of Theorem E.3
I-a" we
Remark E.4. As before, when reward distributions are Gaussian with o² = Theorem E.4 gives
E [n (T)
2
lim inf 700
for arms i E {a" + +1...., {ir}.
log
[ ps)
The corresponding upper bound for the number of samples from the high-cost arms for PE-CS
algorithm, given in Lemma G.5 scales as L Since arm a* is feasible, we have
A..
Pa - SE 1
This suggests that there is potential for improvement in the PE-CS algorithm regarding the number of samples drawn from high-cost arms. For instance, if the two arms with the highest mean rewards have a small gap, it may not be critical determine which one is superior (making Ds less relevant), provided that there exists cheaper arm whose mean reward significantly exceeds the feasibility threshold corresponding to either of the two arms in contention be the one with the largest mean reward.
LOWER BOUND ON THE NUMBER OF SAMPLES FOR ARM i"
Theorem E.5 (Lower bound on the expected number of samples of the best arm). For any bandit instance v over horizon T, for all consistent strategies, we have
By [14- (T))
lim inf T00
(30)
log
Din Vir (1-a)
Also, with (1 = maxie (iax,e(l....' (I....a- M4 and μ1 = maxic (l K)- -it pig we have
Ep [n,- (T)
1
lim inf T 70000
if
H 2 a1-
(31)
logT T
Din (vr, (t
Proof. For the arm i* that has the largest mean reward, establishing a lower bound is more subtle since we need to consider modifications in two different manners. First, we shall consider modifi- cations its reward distribution to make its mean larger such that arm a" is no longer feasible and thus not optimal. Formally, given any bandit instance v/ we consider a modified instance v/ such that D = 14 for E (I,..., KK - {i*} and v/. is any distribution in M such that its expectation n/:. satisfies (1 a)) Mar In the modified instance v', arm i" is still the one with the largest mean reward and the feasibility threshold has changed to (1 a: )(... Since Pa < (1 a)p by
construction, arm a* is no longer feasible and thus not be optimal. This leads to
E, [n-- (T)
lim inf 7-000
(32)
log
(L(V+-,
and taking the supremum in the right-hand side over all distributions 1/.- M with p/.- Hee
get the first bound 30 Theorem E.5
25

---

Published as a conference paper at ICLR 2025
Next, we consider ways of reducing the mean reward of arm i" that would render a" sub-optimal by feasible. Here, we shall notice that by reducing making one of the cheaper arms = ....., a the mean reward of arm i",, can reduce the feasibility threshold to no lower than (1 - 422 where [4:- Even then,
j22 is the second largest mean reward among all arms, i.e., //2 = (L.. this modification would make a" sub-optimal only if one of the arms = 1, ....... a (that all have smaller cost than a²) has a mean reward that would make it feasible at this threshold. Namely, with Mj = m "0..==_1....-111]] M4 (i.e.. M4 the largest mean reward among arms 1....,, a" 1, and second largest among arms I,.... a²), this would be possible only if f 2 (1 - a)ju nj < (1 p2 then no matter how much the mean reward of arm i" is reduced, the arms i = 1...., a= - would not
be feasible (with feasibility threshold being least (1 a))22), and arm a' would remain optimal.
In such cases, the only lower bound we can establish for the number of samples of arm i" is that given by (30).
Now, consider any bandit instance y for which μ, 2 (1 (1l-a)p a)p.. Then, consider a modified instance and 1/2- is any distribution in M such that its expectation p¹; satisfies (1 (1-a)d4- S My. Since arm j was not feasible in the original instance v, we must have (1- > H1,, so ju/-- < plr the modified instance v', the arm with the largest mean reward is either still i* or it becomes the arm with mean 1/2- Thus, the feasibility threshold changes to (1 - at max Hz2 By construction 2 2 (1 a) and due to our initial assumption on the instance we have Hjj 2 (1 a)μ² (which holds in the instance v/ since the distribution of all arms but i remain the same). Thus, we get H 2 (1 1-- a) max(p';- : M2), meaning that the arm with mean reward Hj is feasible in instance v'. Since this arm is in {1, f1,...,00 a" 1}. its cost is less than the cost of arm a" meaning that arm a" is not optimal in v/; instead the arm with mean reward (4j is optimal. This leads
v' such that v/ = V4 for all i E (1....,K, K} (1n}
Ev (ng- (T)
lim inf T0000
(33)
log T
KL(U;-, 1/-)
and taking the supremum in the right-hand side over all distributions 1/g- M with μ4z- S ns a we
get the second bound 31 of Theorem E.5
Remark E.5. As before, when reward distributions are Gaussian, Theorem gives us
E [m-- (T)
2(1 - a)²
2(1 - -0)
lim inf 70000
log T
2 max
\ (a)=-))k-- Ma-) )22
1115 2 (1 -a)pp) ((1 -a) k²y
1
2(1 - a))² maxx
A3
.mxx i<a"
2
1Hg 2 (1 -a))22)
1
= 2(1 - a)² max
1 [min AQ,i S (1 - a) a) i<a"
A
max
i<aa
A
Q,
where AQ. (1 o:)p² pr is the quality gap of arm Ammin n³ ug is the smallest of the regular gaps, and the last equality in the indicator funttion follows from the fact that
min AQ. = (1-a)) p1j = A min +11 0) 11j
Remark E.6. The lower bound established in Theorem E.3 particularly the need to consider the case phj 2 (1-a) separately can be explained as follows. For a policy determine that a" is the optimal action, it needs to be able to decide that arms 1,.... a² - 1 are not feasible but arm a" is. For the latter, the gap between pa- and the feasibility threshold (1 oi) is important and affects the number of samples needed from the arm i", and this is seen in the bound (30). For the former, i.e., to decide that arms I..... a 1 are not feasible, a policy may not need any samples from arm in if it can determine their noa-iiasiyility through another arm. For example, if the mean reward of arms 1,....a"
are all less than (1 02) then they can be determined to be not feasible based on the samples from the arm with mean reward μ2z (i.e., the arm with the second largest mean reward among all). This is what gives rise to (30 being the only lower bound on the samples from arm i" when μú < (1 u22 On the other hand, when μú 2 (1-o) ox) then at least one arm in 1,...,a' can not be deemed non- fea-feaie by comparing it with the arm with mean reward μ and samples from it would be necessary. The number of samples needed from i would be tied to
the gaps between the mean reward of arms 1..... a" - 1 and the feasibility threshold (1 a x)p nd and
the smallest of these gaps is given by (1 a)) [tj which is consistent with the bound 37)
26

---

Published as a conference paper at ICLR 2025
Remark E.7. We now compare the lower bound established in Theorem E.5 with the upper bound for our PE-CS algorithm given in Lemma G.4 We can see that if f4j 2 a2 the dominant gap term in the established lower bound will be given by min;ça- A which in this case is also smaller than minn = 14 P22 Thus, the upper bound of the PE-CS algorithm given in Lemma G.4 matches the lower bound in this case within constant factor. When bt (1 a) as also explained in the previous remark, the lower bound on the number of samples from i' is only governed by Aq,s, while the PE- CS upper bound depends additionally on minica. AQ. and Amin-
LOWER BOUNDS FOR THE FIXED THRESHOLD SETTING
Finally, we provide lower bounds for the fixed threshold setting where μcs = μo and μo 0, pi R is a known threshold. The result is stated in Theorem E. and the definitions for various terms remain the same those at the beginning of Appendix The key difference is that the optimal arm a" is now a" = arg 2 G. Further, in the fixed threshold setting, there are only low-cost arms and high-cost arms and no special reference arm.
Theorem E.6 (Lower bound for the number of pulls of low-cost arms). For any bandit instance over horizon T, for all consistent strategies, we have
E (T)]
lim inf 7-000
Din (Vi) for arms i I....,,""
log T
Proof. The proof follows along similar lines to the proof of Theorem E. Given any bandit instance v and any arm i ,,..., ...,.,"' a"
we construct modified instance v.. The instance v/ satisfies v/ Vj: Vj [K] \ {i}. Since a" is the optimal action, for instance 1/, for the reward distribution V/ of arm i we must have that V/ be drawn from set M and the expected reward n4 2 Po so in the new environment the optimal arm changes. As in the proof of Theorem F we shall leverage (T*) and E,, [n;
that any consistent policy must simultaneously satisfy Ey [m:(T)]
T-o (T*) Ay E (0, 1]. Selecting ni(T) and following the steps in the proof of Theorem E. precisely we get,
Ey [T) log T
lim inf T-200
KL (Us, v/) 1
(taking supremum over all permissible v/)).
Dint (1/, po)
Remark E.8 (No lower bound for high cost arms). As remarked earlier for the known reference arm (.6
setting, there is no lower bound corresponding to Theorem E.6 high cost arms a' +l...., K. In the modified instance v' these arms shall not become optimal even p. 2 pi since they are more expensive than action a". This fact prevents developing lower bound for their samples.
Remark E.9 (Lower bound in terms of gap AQ,). As worked out in previous remarks, when M is the family of Gaussian reward distributions with variance o² 1, we have Din((Us, 2) (HC-2)²
and therefore,
lim (T,) T-0000
2
for arms i I,....."" 1.
log T
(14 1a)
Q
We shall later see in Appendix rithm designed for this setting.
H
the lower bound matches the upper bound for our FT-UCB algo-
27

---

Published as a conference paper at ICLR 2025
F ANALYSIS FOR PE IN THE KNOWN REFERENCE ARM SETTING
In this Section we build to the proof of Theorem 3.2 by upper bounding the expected num- ber of samples of low-cost infeasible arms, the reference arm L, and of high-cost arms under the Asymmetric-PEE setting with maximum round-deviation K. We then particularize these results to the 0 case corresponding to conventional PE obtain an upper bound on the expected regret for Algorithm PE.
F.1 DEFINITIONS AND SETUP REQUIRED FOR ANALYSIS
As discussed in the main paper, the PE algorithm is inspired by the Improved-UCT successive elimination approach where sampling of arms occurs in un-interrupted batches called rounds. In Improved-UCB. a set of active arms is maintained and at the end of every round, arms in the active are re-tested for their candidacy using an elimination criteria. Since in Paariis-EEimmiattion we inherit the un-interrpted round based sampling scheme and climination-criteria first used in Improved-UCCE to prove Theorem 3.2 we build on the analysis from Auer & Ortner (2010).
Definition F.1 (Round pi). For i S at, define round number to be,
P: min {
wil will <
(34)
Intuitively, P: is the PE round number during episode by which we expect to either identify low-cost infeasible arm i < a" as being unsuitable or identify the best action a" as being suitable.
Definition F.2 (Samples associated with round T). From Function 4 required number of samples to be drawn by round w; is given by,
we know that for any arm the
log (Ā
Twn
(35)
A2
Table 1: Probabilistic Events Descriptions and Symbols for PE Analysis
Symbol
Event Description
G1,5, Viga" a"
Episode i is executed to evaluate arm
G2,1, Vi <aa
Arm is eliminated by arm & by when round wi = Pis during episode
G2
Arm i is eliminated by arm a" by when wa Par, during episode a"
G3.,, Vi < a*
Arm É is not eliminated by arm i by when round w/ episode
1, during
G3.
Arm a" is not eliminated by arm & by when round War Pa 1, during
episode
E,, Vi
Available samples out during episode before the sampling for round Ps could conclude and before an arm could be eliminated
Definition F.3 (Samples between time interval n4(t1, t2)). For the forthcoming analysis we intro- duce notation (t1, t2) for the random variable denoting the number of samples of arm accrued between time steps and l2 both inclusive.
Definition F.4 (Final time-step in episode i). We use t, denote the final time-step in episode i.
Combining definitions F.3 and F.4 the variable ne(1, t,) denotes the number of samples of reference arm É accrued by the end of episode i. At the outset of our analysis. we define large collection of probabilistic events needed for developing Theorem 3.2 intermediate results in Table Each event in Table 1 is subset of the sample space Ω associated with run of PE. In the descriptions
28

---

Published as a conference paper at ICLR 2025
of events in Table 1 when we say that an elimination event occurs by round, we including the round being mentioned. For example: "Arm is eliminated by round pi means that the arm i was eliminated in round wi such that wi S Pi-
Remark F.1. In the event descriptions, whenever we refer to the reference arm available to the algorithm,
really referring to the action whose expected return is (1 a)je, where is the subsidy factor.
Arm l not being climinated by arm i during round ps is covered by G2,5, hence the rounds range up to p; - 1 in the definition of G3.z- Unlike the episodes < a" where the nominal outcome for the reference
win over the candidate arm, for episode a", nominally the arm a" shall be the winner and therefore the events 22 G3 are defined separately to account for this reality.
Lastly, define compound event G; using events in Table I as,
G G1, O ((G2,, O G3,)) F.).
(36)
In English the event G,, S a* is the event that episode occurs (event G1,;) and that either an accurate and timely elimination of one arm by another is made (event G2 n G3,)), or we run out of samples before a decision could be made and prior to the conclusion of round (event E,). Conditioning the samples n. (T) for PE on event G3 gives us the following key result,
Pr (T²(T) S Tp. G2) =1
(37)
We leverage Equation 37 in conjunction with Lemma D.3 to prove Theorem 3.2 To use this pro- cedure, we require Lemma F.T that partitions the probability space Q into mutually exclusive and exhaustive events including G..
Lemma F.1 (Partition of Ω with G:). The events G,, B1, = Gi and B, = G1, (G5, U G n Ej are exhaustive and pairwise exclusive Vi S a".
Proof. We can prove that the events stated in Lemma F.1 are mutually exclusive and exhaustive by showing that Gj B1, B,. Since G; and G exhaustive showing so will show that the three events are exhaustive. Moreover, since G; and G; are mutually exclusive, and since B1 and B, are mutually exclusive by construction, we would also have all the events being pairwise mutually exclusive in addition to being exhaustive.
B1, U B; = G U (GL, n (G2, UGG,) nE;
(38)
= (GG, n (Gi, u ((G), UG ( E)) Gi U ((GS, U G. E.)
(U distributes over n)
(39)
(40)
G
(41)
Where Equation 41 follows from the expression obtained using De Morgan's 's laws for G. using the definition of G in Equation 36
BOUND SAMPLES FOR THE CASE < a"
Lemma F.2 (Bound on the number of samples of low-cost infeasible arm under Sirrwis-EElimi. nation). When the maximum round deviation = 0, the expected number of samples of a low-cost arm with index < a" over horizon T is upper bounded by.
32 2. E n4 (T) <
43
+
A
Q
The expected number of pulls E [n: (T) are bound by using the Iterated Expectation Lemma D.3 and conditioning on the event collection G., Br,s, B, which are mutually exclusive and exhaus-
Proof.
D.3
live per Lemma F.1
[n;
(T)
in (T) G.) Pr (G.) + E [m, (T) | BGd] Pr (B..)
E [m (T) B.) Pr (B,)
(42)
29

---

Published as a conference paper at ICLR 2025
(43)
= E En, (T)
+. Pr [ G3,) nE;))
(B, from Lemma FT
(44)
S [, (T)
(45)
= E [m (7)
G.] + [T]++TPPP T-TPPr [G (T U (GI, n G, (distributivity of ()
(46)
< E m (T)
G.] + T. U B3,i) (simplifying notation)
(47)
= E n, (T)
+ (Pr (B2,) Pr (Bz,)) (using the union bound).
(48)
Where Equation 43 follows from the fact that n; (T) B1 0 since there can be no samples of arm
i if episode never occurs, and we define GI n G2 and G1,5 n G3 as B2 and B3,; respectively for notational simplicity.
First we bound the number of samples of arm i conditioned on the good event G, Since during episode i < a", we either make the correct decision of eliminating arm i by episode 4, P3 as captured by G2.4 n G3,3. Alternatively, under G, we run out of samples as captured by E, In either case we will not have more than To; samples of arm i, where Tp. is given by.
log( p.)
AZ By construction of the round p.. for all i S a², we have,
Tp:
(49)
A
AQ.i
< A p1
(50)
4
2
Plugging in the bounds in Equation 50
(TA3.
32 log
Tp: S
(51)
22 Q
32 log (7 2
1 +
(52)
2
Therefore, we have,
32 log 2.
E[n,(T) G. S Tpp <+
(53)
2/21
Next we bound Pr (B2,) and Pr (Bo.)) in order. Since B2, = G1.5 n G. from the specification of G5 and the fact that intersecting with G1 puts us in the sub-space of 12 where episode i occurs,
B2, Vi < a" is the event: "Arm i is not eliminated by arm by when round wi = Pi. during episode i", Similarly B3, Vi a* is the event that "Arm l is eliminated by arm by when round wi- P: 1, during episode i"
Along the lines of the proof composition in Auer & Ortner (2010) for the Improved UCB algorithm.
we construct three clauses on the empirical returns of arms and l in Equations 54 55 and 56
log (TA2,
i4 S 14 +
(54)
2Fw
log T
ee 2 14
(55)
2Ta
log
(Tă3,
je p4
(56)
2Twz
Clauses 54 and 55 holding when wi Pj lead to the elimination of arm i by arm as shown in the work that follows,
log (Tăz) ) /25o. S Soo.22 < i4
(57)
30

---

Published as a conference paper at ICLR 2025
Therefore,
log (T33,
log TA2
P;
P4 +
S 14 + 21
(From clause 54 and wi
Pi
(58)
pm
2Tp:
log ( Ps
14 QQi -21
(From the ordering (77
(59)
2Tp
log
( pi
(1 (1-a)He 21
(60)
2Tp:
log (TÂa.
(1 -a)āe -01 -11-a)
(From clause 55 and wi Pt
2Tp:
(61)
log (Tă3,)
- a1- (1 a)
(Since we 2 wi).
(62)
2Twz
Here, Equation 62
the criteria for arm being eliminated by arm & in PE. We upper bound the probability of the arm i not being eliminated by union bounding the probability of the complements of the Clauses 54 and (55 using Lemma D.2 (Hoeffding's Inequality). In addition, we include the bound on the complement of Clause 56 which shall be useful later in bounding Pr (B3,1).
log (T wi
1
Pr
is > +
(63)
2Tw;
TÁ2,
log
T
Twe log ( )
1
Pr
e < pe
exp
(Since Two 2 Tw:)
2Tws
Two
(64)
log
(TA2,
4t
Pr
je < ke-
S
(Since we S wi + Ks, and Åm = 2 2-m).
2Twe
TÁZ,
TÁz
(65)
If either of the two clauses 54 or 55 we can bound,
violated, then elimination of arm will occur. Therefore,
log
T mi;
log (
Pr (B..)) Pr
p > Mi
+
+ Pr
ju < ue
(66)
2Tw:
2Tw
< TÃ2
(67)
Plugging in round number w, P: in Equation 67 and then plugging in the lower bound on A p. from Ordering 50) we have,
2
32
Pr (B2,) -
<
(68)
T P:
TA
Q
Finally, we wish to bound Pr (Ba.) Say that the actual elimination arm by arm i occurs in some round Wi P < Pi- To bound the probability of this clause of the event Gç, note that the
31

---

Published as a conference paper at ICLR 2025
holding simultaneously preclude arm E from being removed by arm i regardless the round number p in question. Therefore, using the results in Equations 63 and 65 the probability of round where l is removed, existing, can be found by plugging in w/ p, and is upper bounded by 41+
clauses in Equations 54 and 56
While there is no definitive round number associated with p. from the
TA
clause itself we know that must have p pi.
+1
1
44 + 1) 4
(r(
(Using Åm = m
(69)
T
P=0
P=0
4t +
.4 (Using the formula for the sum of a Geometric Series)
(70)
3T
4" +1
(Since Am 2 m
(71)
3T Ps
16 (4" +1) (Because Ap 2
AQa
(72)
3 Q.
4
11 TA7
(Since we impose Lemma F:2)
(73)
Plugging in the bounds Expressions 53 the number of samples stated in Lemma F22
68 and 73
into Equation 48 we get the overall bound on
BOUNDING SAMPLES OF REFERENCE ARM
Let the random variable Z denote the final episode in the run of PE. Then {2 =} constitutes a measurable event the sample space Q indicating that the terminal PE episode was z. This construction lets us establish F3
Lemma E.3 (Bound on Samples of Reference arm l under Pairwise-Elimination) Elimination). Samples of ref- erence arm emanate from the episodes of candidate arms being compared to arm f. When = 0, we show the bound,
32 log (T
43 A
E (T)e(T)] 1 max 'Sa"
(2>
2
Q
Where Z is the terminal episode of PE.
the nominal outcome is for episodes i i= 1....., to result in the candidate arm i being eliminated by arm é, followed arm a" eliminating arm é during episode a". To prove Lemma F33 we condition on this nominal sequence and upper bound the probability of the outcome deviating from this sequence by factor proportional to 4. Throughout the episodes i= 1...., a the number of samples n& (T) are equal to the number of samples of the most sampled candidate arm i S a". This is because in PE re-use samples of arm l across episodes and only further sample to keep up with the samples of a candidate arm. Motivated by this fact about ny we begin by defining compound tighprrobabllity good event G.
Proof. Under
Definition F.5 (Event G). The compound good event G is the event that for each episode i i a" that was executed, the episode satisfied the episode-wise good event Gj. Mathematically we define,
G G= U (z= (Z==)]naa
(74)
The complement of G, namely G can be written out using the definition of and De Morgan's laws as,
a" Ge = n (z =
(75)
#=1
i=1
Because for any events A, B, and C, Pr Pr(An B) S Pr(C") Pr S (A
32

---

Published as a conference paper at ICLR 2025
SUGUIz+a
(picking = = a" from the iterated intersection)
(76)
i=1
(77)
( >d}
(78)
==1
(79)
U uu
(80)
Where the first term in Equation 78 follows from the equivalence between G. and B1,; U B; shown the proof of Lemma F.1 The second term in Equation 78 based on the equivalence between the event {Z < a*) j. meaning that the final episode precedes a", and the event U Bi, which means that some episode i ,,...,a' a was not executed.
We leverage event G to bound the expected number of samples of arm l. In particular we consider three events G, G n {2 S a²}, and G n {Z > a²} that are mutually exclusive and exhaustive by construction. We decompose E [ne(T)) by conditioning on this collection.
E [Te(T)]
E (T) Pr G C
E [T) G [ (G" ( s [ + -
(81)
Pr n S {' B (Z a Pr)>'')'')
(82)
Where bound 82 follows from the simplified form of G developed in Equation 80
Since samples of arm l are reused between episodes with further sampling of arm & only occurring match the demand from a higher round number, we have,
n2 (T) | G
E
max n, (1, (1,tz) 12
|G
(using definitions and F.4
(83)
max n, (1,4a)) | isa
(:: 2 (
(84)
max Tp: <5a
(using Equation 37 and by construction of G as O G;))
(85)
2 2og
TÂ P.)
max iSa
(86)
2 log
T
+ max
(87)
iSa'
Â
32 log
(T (TA2
1 + max
(Using the ordering in Relation 50
(88)
<Sa*
32 log
(TA3 +.+)
1+ max
(89)
A
To complete the bound E [TT] develop bound on the term Pr (G' n (Z S {)")) in Lemma
F.6 However, to prove Lemma F.6 we first require two intermediate results in the form of Lemmas
F4
and E.5
33

---

Published as a conference paper at ICLR 2025
Lemma F.4. In all the outcomes contained in G ending in some episode Z i a', some By, S i must have held.
G (z) S S UB, B3 visa"
(90)
5=1
Proof.
G (2 = ((CUUG)
(91)
((GF) (iistiibuue over J)
(92)
(GEn(==0)j((::22-:)000} (: ( - c
(93)
((B,JU=))) (: (: = B1, U B,)
(94)
S (2) (:' (
=()
(95)
Now consider just the event G; n (Z n G from Equation 95 We find event it is
subsumed within in the following way,
| - =G Na. nG: #=1
i-1 G3
niz=
(96)
i-1 - (antnnnnnaaannnnnn---
u
(97)
j=1
= =Z no [)
s=1
j=1
(98)
G (B. (from Lemma
F.
(99)
i-1
G (
(. nfz = = o, < (100)
j=1
i-1 S
U
Bj.
(101)
j=1
Plugging in Equation 101 into Equation 95 gives us the result stated in Lemma
Lemma F.5. Within the space of events that constitute GO, episode i S a" does occur, then there exists j < i such that the event Bj occurred. Mathematically,
G C C Bj, Visa..
(102)
j=1
Proof. We can prove the result by induction. First note that B1, since Episode always occurs.
Let i = 2 represent the base case. Then,
B1.2 G G
(Z
1)
(103)
C B (Using Lemma F4
(104)
Now say that the statement in Lemma E.5 holds true for some i a". That is,
BI G c U
Bz.
(105)
34

---

Published as a conference paper at ICLR 2025
To prove Lemma F.5
we need to show this result for i 1.
B B1,4+1
(Bi n))
(106)
= (Bi (DI,,n U k)nG)
nover U
(107)
S U
B, u U B3
(using the induction hypothesis and Lemma F.4
(108)
i=1
j=1
B₁.
(109)
f=1
Where Equation 106 uses the identity BI = BI, 1 which breaks down the event of episode k + 1 not occurring into the event that episode did occur, the event that episode was the final episode Z. Equation T09 is the required result from the statement of Lemma F.5
Lemma F6 (Bound on Pr (G n 12 a))}))
We can upper bound Pr (G n 1z S a }*}) as,
Pr (2 S a'))
Pr(B,)
(110)
43
Pr (Ba.)
(111)
TA?
1=1
Where B;, Vi S a" is as defined in Lemma F.1 and using the bound on Pr (B:) shown in the proof
of Lemmal
F.2
Proof. We begin by introducing the expanded expression for G developed in Equation 80
(G n niZ a²)) Pr
Pr (G" ((Z
(112)
Pr
G G
/0 oz} nlzsatncr
(from Equation
80
(113)
( )
Pr Pr
(n distributes over U)
(114)
Ü (G)nG))
Pr
(union bound and Pr (A, B) & Pr (A))
(115)
Pr
((BI)UB))
(by definition of G.)
(116)
U ( (B):
Pr
(n distributes over U)
(117)
B, U U Bj ) /=1
< Pr
(using Lemma F5
(118)
Pr
B;
(119)
Pr (B,)
(Union bound, and (Z a"} = Ba)).
(120)
To complete the upper bound on the expected number of samples E [m, (T)) from Equation upper bound Pr (Ba-) along the same lines as Pr (B:) á a" in the proof of Lemma 22
82
35

---

Published as a conference paper at ICLR 2025
The key difference being that the roles of candidate arm a' and reference arm l are reversed as compared to the earlier procedure since Ha- 2 Pt. Moreover, just like the earlier proof we can define a G1 n G5 and a not eliminated by arm a" by when wa- = Par, during episode a²" Similarly, B3,a- is the event "Arm a" is eliminated by arm é by when round was fa during episode a"".
Gi,a* n G In words B2 is the event that "Arm &
We bound Pr (B2,a)) and Pr (B3,a-) separately by constructing clauses on pr, and Pa- as before.
log
T We-
Le S Met +
(121)
2Twa*
T log
W
i S pe +
(122)
2Twz
log
Pa 2 Ma
(123)
2Twrs
Clauses 121 and 123 holding when War = Pa lead the elimination of arm & by arm a" as is shown in the following steps,
log (Tå /2T < App. < Aq 1/4.
(124)
Therefore using Wa- Pa
log T
log (TA3.. P.-
(1 (1-a)
A +
$ (1 -a) a)
+ \
(125)
2Tws
2Tp
log (AA Pa-
$ a1
Me + 2
(Equation 121
(126)
2Tp..
log T Pa*
$ (1-a))e a)μe +21
(127)
2T
log T
aope 11 21
Pa-
(From 124)
2T
(128)
log T
p..
Ma' 2
(129)
2Tp.-
log
TĀ Pa.
$ Pa
(From Equation (23)
(130)
2Tp.-
Here Equation 130 the criteria for arm being eliminated by arm a* in PE, Since Clause |21 and Clause 123 being true and applicable at round wi a" imply arm e being eliminated, we can upper bound Pr (B2 as,
log (TÁZ..)
log
T
Pr PrB2,ar) S Pr
je > me
Pr
Mar < Ha.
2Twer
2T
(131)
36

---

Published as a conference paper at ICLR 2025
(Similar to the bounds in 63 and 64
(132)
TA W
Plugging in round number We Pa- in Equation 132
and then plugging in the lower bound on
Ap.- from Ordering 50 we have,
2
32
Pr (B2 5
<
(133)
T Pa
TA Q.a.
To complete the bound on Pr (Ba-) ) we must bound Pr (a which the the probability of arm a² being climinated by arm e by round Wa Pa-. Similar the arguments in the Proof of Lemma F.2 the clauses in Equations 121 and 123 holding simultaneously preclude arm a" from being removed by arm l regardless of the round number, and shall have,
16 14 + +1)
Pr (B3,a.)
(134)
ATA2 Q.0"
11
(When we impose K = 0).
(135)
TA
Q,a
Using steps identical to those that lead up to Equation 48 we shall have,
Pr (Bar) S Pr + Pr (B3,a))
(136)
43
< TA7
(from upper bounds in Equations 133 and 135).
(137)
Q.a" Q.a
Combining the upper bound the expected number of samples of arm é in Equation 89 with the
bound on Pr (G {Z < a²}) in Lemma F.6 and the bound on Pr (Ba-) in Equation 137 all into
82
reach the upper bound stated in Lemma F3
BOUNDING SAMPLES FOR HIGH COST ARMS <i<l
Lemma E7 (Bound on the expected number of samples of all high cost arms under Pairwise-Elie ination). When 0 the expected number of samples of all the higher cost, non-reference arms, that is, arms with index in the range a" <i is upper bounded by.
Σ E
SE
Σ n; (T) a') Pr(Z>
a' CICE
La'cskt
Where Z is the terminal PE episode. We shall later see that this amounts to a constant.
Proof. We upper bound the expected number of samples E. cice E [n; (T) by conditioning on the event {2 < a²} and its complement.
Σ E. mm (T))
E
Σ ni (T) <iEE
(from the linearity of Expectation operator) (138)
CKE
Σ
ny (T) (Z S a²)
-rr(t5 ((lzsa))
<iKE
+ E
Σ
n4 (T) (2 > d²}
-rr(1 > >d}) (from Lemma D.3
La ciii
(139)
Where E Ei (T( (2 S a²) follows from the fact that there cannot be any samples of arm i > a" in the case when the final episode Z is less than a".
Finally, in position to Prove Theorem 3.2
37

---

Published as a conference paper at ICLR 2025
Proof of Theorem 3.2
First, we apply Regret decomposition in Lemma D.5 to Cost Regret,
E Regst (T, v] v
Σ
BE I (2))
(because Ac, S 0 for S a²)
(140)
1=
= A B [e (T) + Σ
E
(T)
(141)
a a'iict
S o E [ (T)
+ max a' <'<itt
A
C2
Σ
E
[T)
(142)
a'<itt
32 (T Q.1)
43
+ max i5a
C.
A
q,i
Q,
E (T)
11 > a H
Pr (Z > a²)
+ max ciel
E
Σ
n4e (T) 12 > a²}
(Pr xa*)
(143)
<i'E
32 log (TA
(2)
a"
43
+ max 15a
c
Q
Q
max ciSe
C2 . (Z > a²)
(144)
1 + max
32 32 (TA
Σ
43
A
Q
A2
1=1
max
At
T Pr (Ba.)
(:: (Z > aa}
= Ba-)
(145)
a" <ist
1+ max iaa
32 log (T
(2.5
43
At c
43
max At
Q
Ag.a.
a Rise
(146)
Where the final inequality follows from the bound in 137 Similarly for Quality Regret we have,
E Quaaltty Reg(T T, Tv)]
=
Q. E In (T)
(147)
i=l
Qq E n44 (T)
Σ
A [n (T)
(148)
+=
A E [n: (T)
+ max A+ a" <ice
Σ
E [n, (T)
(149)
i=a++1
32 log (TA2 2.))
43
43
Aq.i +
+
max A+
<ict Q, (150)
AQ.
AQ.i
Which are the bounds stated in Theorem 3.2
For an improved understanding of these upper bounds, we provide description of the terms.
First for Cost Regret,
32 log (T (TA2.)
43
43
1 max *5a*
A
Σ A i=1
max A CiSiSE
A3.
C.P
A
C,S
Contribaion from under nominal termination PE episode
Contritution mis-termination in PE opisodo Sa"
Contribution from episodes >a" in case of mis termination during ep a²
38

---

Published as a conference paper at ICLR 2025
Next for Quality Regret,
32 log (T (TA).)
43 Q
43 max A QQ o <iel
Ao.+ +
QQ
Contribution from < under nominal termination episode
Contribution from a" under mis-termination PE episode
Contribution from episodes >a lermination during
39

---

Published as a conference paper at ICLR 2025
G ANALYSIS FOR PE-CS IN THE FULL COST-SUBSIDY SETTING
We now turn towards proving Theorem 3.4 that establishes an upper bound expected cumula- tive cost and quality regret for PE-CS. The PE-CS algorithm operates in the subsidized best reward setting (Sinha et al. (02II) We have already shown upper bounds on cost and quality regret for Pairwise-Eliminn
(PE) for its operation the known reference arm setting. The principle hurdle in generalizing the PE analysis to an analysis for PE-CS is working through the uncertainty asso- ciated with the identification of the best arm in the BAI stage of PE-CS. To perform the PE-CS analysis, not only do we need the definitions. notation, and setup from the analysis of PE, but also we require some additional constructs spelled out in the following section.
G.1 PE-CS AND UNKNOWN REFERENCE ARM SETTING SPECIFIC DEFINITIONS
(BAI) phase and a Pairwise Elimination (PE) phase. As discussed in Section 3 the BAI phase of PE-CS is the Improved UCB algorithm Auer & Ortner (2010) terminated once there is a single active arm remaining. The single remaining arm is assigned to be the empirical reference arm denoted by f. As we show the subsequent work, by the manner in which PE-CS is setup, the event that the identified reference arm gets arm i" in the line l <- A [0] (Line 6, Algorithm 2 is high prohability event. The core idea behind the analysis is to condition the expected number of samples on this desirable and likely outcome occurring during the BAI stage.
As described in Algorithm 2 PE-CS operates in two phases,
addition to the notation defined in the main paper, we define more constructs that are specific to the analysis of PE-CS. For arm i, define round number o; within the Best-Arm-ldeniifiation (BAI) phase of PE-CS to be,
A 2
min m Åm
(151)
Intuitively, round o, is the round number by which we expect the BAI stage of PE-CS.
be eliminated by arm i in
We let the final round during which arm i was sampled during the BAI stage be denoted by the random variable 2, To apportion the contributions of the BAI stage and the PE stage to the total number of samples n, (T), we introduce the variable ÍAAI to denote the final time-step in the BAI stage. As a consequence of these two definitions n; (1, (BA)) I TE. The highest round number reached during the BAI stage overall for any and active arms denoted,
E = max Σg-
(152)
And to denote the set of active arms at the last time-step of the BAI stage we use,
As A (IBAI).
(153)
Next, define collection of useful events in Table for the analysis that follows. These events are contingent on outcomes occurring during the BAI stage alone.
Table Probabilistic Events Descriptions and Symbols for PE-CS Analysis
Symbol
Event Description
r. Vi 4 it
Arm i is eliminated by when round m = a, during the BAI-stage
B1 Vi +
Arm is not eliminated by when round m o; and Arm E As. during the BAI-stage
B2 Vi + i
Arm is not eliminated by when round m = G, and Arm i' $ As, during the BAI-stage
F,, Vi
Final BAI round Y, < a; and Arm E As
40

---

Published as a conference paper at ICLR 2025
Remark G.1 (The event Fj). The event F; in words is the event that samples out before the validity of the event I; could be checked and before the arm could be eliminated. Equivalent to the description in Table 2 complement is given by F. {Eg 2 Ji U Ar}. Consequently, D S F3, and D;; ; Fg. Since event F; requires that i E Ag. the event {iANs =T) vi
write F; {Eg < ni As}. Using De Morgan's 's rules, its
Remark G.2 (Events are proper subsets of It). Similar to the events defined in Table D the analysis of PE, the events in Table 2 are proper subsets of the sample space Q. From the setup inherited from Improved- UCB, r, is desirable and likely fate for Arm during the BAI-stage.
To analyze the outcome of the BAI stage of the PE-CS algorithm we intuit and validate three way partition of the sample space S2 into the events r, B3 and F. I is the event conditioning on which ensures that f = 1" by requiring that the events I held for each arm & it Additionally we require that there are samples remaining at the end the BAI stage by intersecting with (IRAI < T). This structure makes the downstream analysis of the PE-stage tractable.
r = {FBAI < T N r
(154)
Let A denote the set of arms other than the maximum reward arm 1", We use P(A) to denote the power set of A, that is the collection of all the possible sub-sets of A. Let S E P(A) denote an arbitrary subset A. We define an event F(S) C l parameterized by the set as,
(NED n (T)NF)) iES
F(S) = (IBAI = n
(155)
JEAYS
Intuitively, the set consists of arms i E S for which F; held thereby making r unverifiable. In contrast the arms contained in E A those for which [3 held. An inspection of the definition of (S5) in Equation 155 reveals that F(S1) n F(22) = 6 V1,, E S1 # S2. Taking union over all possible F(S) we get the compound event F,
== U F(S).
(156)
SEP(A)
Finally, the event 3 is the event that I; did not hold for some arm i + 1 despite it being verifiable (FF holding).
B U UMMA iffi"
(157)
Lemma G.1 (A partition of Ω using I'). The events I, F, and 3 as defined in Equations 154
156
and 157 respectively, form a mutually exclusive and exhaustive partition of the sample space 1
Proof. First we show that the sets are mutually exclusive by showing that their pairwise intersections namely I' n F. F Fn 3, and 3 n are all ø. Starting off, it is easy to see that I'n F á since,
T F C (LbΛ < T) n [lBAl 7) (definitions from Equations
154 and 1.66
(158)
Next, to show that F n B = Φ. it is sufficient to show that F(S) é for arbitrary SE P(A).
(NE n (r, (TynF))
F(S) [teAl n
n n (TEEF)))
(159)
iES
JEAYS
Since both F. n (T& P.) = o and (T, (F) (Tç (?)
G. we shall have F(S) n =Φ.
Lastly, for the pair 33 T we have,
8nr= U (T)) NT,
(since the indexing for 3 and need not coincide) (160)
j#
41

---

Published as a conference paper at ICLR 2025
U ( N (T, (z) j#
(since -
(161)
U (L (Line)n()) = Φ.
(162)
Next we show that TUFUB = Ω2 that is, the event collection considered in Lemma G.1 exhaustive.
TUFSTUF()) N (Tin
(plugging F(S) when Φ per Equation 155
(163)
TUFUSD n (T) U (1)
(164)
if
= U ((TEE))
(165)
jff
2
n (CT) (E) R.)
F F.. 6gh1
(166)
We shall now show that FU, Ul F; which combined with Equation 166 on the exhaustive criteria. To do this we show that F; C FFBViT
completes the check
PROOF THAT P. C FUB:
To prove this result, we start with the event F((i)),
F((i)) [LBAl n En N (1)nez)
(167)
JEANSi
= Fin N (T) (: C (IBAI= T}). jEAjfi
(168)
Without loss of generality, let the set of remaining arms in A, i.. A (i] {p, g..... The idea behind this proof to identify sub-events F(.) such that iteratively taking their union with one another and with events lying in 3 reveals that F; S CFU.U FUB. Since B = Uk7i (Fg n n have,
(F CB = (n(T) n
N (L)FF) CB
(169)
SEAMLP)
(intersecting with sets keeps inside (3)
= (()))RN((3)))) N
CFUF)
(cF() FF) (170)
jEAl(ip)
PNAn
n (GNE)CFUL
(171)
jEA((ED)
(T, U (Tp n (5)) from B, F((i))
F(iip))FFEB
(CFF)CFU
(172)
jEAMipp
EO n (F
(C)NF))FUR CFUB
(173)
jEANLip)
In reaching Equation 173 we have removed the dependence on Arm p for the event on the left. With the next series of equations, we further remove the dependence on Arm q.
F&N N (T,OF)) CUUB
(174)
jEAMLet
- Fin FT n
N
(TyFF)) FUB.
(175)
42

---

Published as a conference paper at ICLR 2025
Similar to what we saw in the first iteration of this procedure, we have,
P (Tg n 12) n n
(L)) CB
(176)
jEAMisD.)
= FOF
n
CFUB (
(T))E))
(combining with Equation 175
(177)
JEAMiD.))
Similar how we reached the result in Equation 173 in starting from F(()), if instead we had started with the set F(fi, 4)), and then eliminated the dependence on we would have shown,
FOFD
(
(178)
(EAR(A.-2)
Combining Equations 177 and 178
have,
F
n
(.NF))FFUS
(179)
jEAM(ip-))
Repeating this procedure iteratively, is clear that the event on the left can be pruned down to simply F,, and therefore,
FUFUB
(180)
Since no assumptions were made on the choice of i, we have,
U
UACFUR
(181)
As mentioned carlier, combine I TUFUS B o Nize Ff from Equation 166 and F U 8
Uigi- from Equation 18I obtain I FO FUF Ω2
Corollary G.1 (Corollary to Lemma G.1 The events I, (F(S)) ,3 form a mutually exclu-
sive and exhaustive partition over the sample space Q. This result follows trivially from Lemma G.I and the fact that S # S2 F( F(S2) =
Next we prove an upper bound on the probability of the event 3 which we will need repeatedly in proving subsequent results.
Lemma G.2 (Bound on Pr (3)). To bound the expected number of samples in all the cases pertinent PE-CS we show the following bound on Pr (B).
11
32
PB(
(182)
TA2
TA
min
if1"
Where Amin n² p2 the difference between the highest and second highest reward.
Proof.
Pr (3) Pr
(UIDE))
(183)
Pr
U
(B1, U Ba,i)
(since I n F. B1,5 U (2,))
(184)
Pr
U $1,1 in-i
Pr
U B2, 1t1-
(Union Bound)
(185)
(B +r
U
iA & An.) (Union Bound, Latter clause of (2.;)
(186)
43

---

Published as a conference paper at ICLR 2025
Σ $310
( Pr Arm & Am }).
(187)
Where max m di and Equation 187 follows from the fact that 1" Ao. 1" & Aaz when 02 01-
The event 31,; is the event that Arm is not eliminated by round o while Arm i" is active at the end of the sampling for round d;. The term Pr (81.z) therefore can be bounded in a manner analogous to the way the probability of low-cost infeasible arm not being eliminated by reference arm l was bound in Equation 67 The difference being that the round number Pt is replaced by the round oN or equivalently, the gap Aq, i replaced by the gap A. Therefore.
32 Pr (B S TA?
(188)
The problem of analyzing Pr (12.)) is analogous to the analysis of Pr (Ba,) in the proof of Lemma F.2 for the PE algorithm. By applying the Hoeffding bound (Lemma [.2] the clauses in Equations [4 and 56 we were able to establish that the probability of the event {Arm eliminated by infeasible arm i after the sampling for arbitrary round p concludes] is up- per bounded by 1"+1 тΔ
Since for the BAI setting the samples of all the arms are always matched
(x 0) here we shall have,
M Memax -1
M -1
2
Pr ({ Arm i" & Aomax 1)s
4
(189)
T P
T
P=
p=
2 4 m0ox
(190)
3T
(191)
3T A
max
32
(192)
37 A
min
11
(193)
TA 2
min
Combining the bounds shown in Equations Lemma G.2
188 and
193
we obtain the overall bound stated in
We now move on analyzing the evolution of samples in the PE stage of PE-CS. The pieces needed from the analysis of the BAI stage are the partition over Ω from Lemma G. the bound on Pr (3) shown in Lemma G.2] and the Iterated Expectation Lemma D.3 The key difference between the analysis of PE and the PE-stage in PE-CS is the possibility that the round number Σ, to which the samples of an arbitrary arm é * i advance during the BAI-stage exceeds the round number ps 34 Our modular proof technique sequesters both the pathological (event F) and the unlikely (event (3) outcomes the BAT stage away from the PE stage. our approach the n; P case in the analysis of the PE-stage of PE-CS only surfaces for episode a*. Moreover, analyzing samples accrued during episode a" is only called for when bounding the expected number of samples of the best arm i*
defined in Equation
Remark G.3. Similar to Remark F.1 we note here that Arm during the PE stage of PE-CS really refers to hypothetical Bandit Arm with expected return (1 - a))...
Using all the definitions and constructs introduced in this section, an upper bound on the expected number of samples of low-cost arms in Lemma G.3 the maximum reward arm it in Lemma G.4 and high-cost arms in Lemma G.5
now in position show
44

---

Published as a conference paper at ICLR 2025
UPPER BOUND ON THE NUMBER OF SAMPLES FOR ARMS i a'
Lemma G.3 (Bound on the expected number of samples of low-cost arm under PE-CS). For any low cost infeasible arm i < a", its expected number of samples accrued is upper bounded by,
n: (T) <1+ 32 log (TA Q.))
+
(1)n((2)
+
Σ
32
A
TA min
TA
Q
3
We begin the analysis by applying the Iterated Expectation Lemma D.3 to the partition de- veloped Lemma
Proof.
G.1
E [n (T) = E In (T)
(T)
Σ
En (T) F(S)) + [, (T) [] Pr (8)
SEP(A)
(194)
< max E [n (T)
[ [ng (T) ((S))) } + + [ng (T) Pr
(195)
(: + Σ Pr (F(S)) < 1)
S max {E [n [], To, + E (T) Pr
(196)
Where Equation 196 follows from the fact that conditioned any F(S), the maximum round up to which arm i can sampled is og both in the case when T; holds (i & S), and in the case when E S, and F. = { < ) (i AA holds instead. We now proceed by separately bounding the E [m (7) [] term by further conditioning on the cases where Eg > P and Σ, S Pt.
E (T)(T) | = E (m, Σ, S p. r
Pr E S A IT) Pr ( > T)
E (m, Σ Ps.
(using Lemma
D.3 on E S pi))
(197)
SEIn(( E - p.. 1'| E (T)]
(introducing shorthand notation E1).
(198)
Where Ps is as defined in Equation 34 In writing Equation 198
we leverage the fact that for a low a)) - M4 is necessarly smaller gap than A nl, p4
cost arm with index i < a", Aq, since by construction, each of these low cost arms has a return 14 < /cc = (1 - a) It follows that Pr (E, > Pi, I)- Pr (E, Ps [)- 0 because the largest value that the random variable Σ; can take under I' is o; and ΔQ. A
> oz.
BOUND Ej [n, (T))
Since we enter the PE stage of the algorithm with a round number Σ, S Pi. we use the same event construction of the compound event G2 i < a", defined and used in the Proof of Lemma F.2 There- fore, just as before we work towards a bound by conditioning on the partition with G; introduced in Lemma | Let A; be the random variable denoting the highest round number corresponding which sampling was performed for arm during the run of PE-CS.
E, [T.( E, (T) G.) (G.) + E, (T, B Pr (BI.) E, (T,(T) B.) Pr (B,)
(199)
< max [En (T) G.), Eg (T) B1.1} + T Pr (B,
(200)
(Since Pr (G.) Pr (B1,) <1)
max (E, [T) G.]] E,
ne(tnAl + 1,7) Bı,]) T Pr (B:)
(201)
< max (E, [TX Gt). E, [TE. + 0 B1.)} + T PB()))
(202)
"The prohability operator Pr in the work that follows is also for the conditional distribution conditioned on
EE S Ps T).
45

---

Published as a conference paper at ICLR 2025
(Tm as defined in Equation 35)
I max (Ta, Ta, TT (B:))
(203)
Tp: + . Pr (B:) (since Pi > 0; vi<aa)
(204)
32 log (TA a.)
< 1
+T -T-Pr(B) (Using bound on Tp. in Equation 53).
(205)
Q.5
Where the treatment of the random variable (/BAI + 7, (from definition F33 is based on the expression for the additional rounds for which arm is sampled during the PE stage of PE-CS. In Equation 202 conditioned on Gj there may be more samples, however conditioned on B1, there shall be no further samples since the episode corresponding to i never initiated. Now to bound Pr (B, Σ S P) we use arguments similar to the ones in Proof of Lemma
F.2
(B. E. pt, Pr (B U B2, E, pc,
(206)
Where B1,; = GI. n 2 2, and B = G1 n G3,, as in the proof of Lemma F.2
The Probability
Pr (B1,)) in Lemma F.2
F.2 was bound by the probability of either 3lause{544or Clause 55 being violated
during round Pt- Due to the parallel nature of the construction here, and the possibility of round Ps being conducted, we can upper bound Pr (Bi, Σ; S Pi, I') identically as,
32 Pr (BI & S P) TA
(207)
Now move to bounding Pr (B2, Σ, S pi T) by bounding the probability of arm being eliminated in any round wi = lying in the range Σ, S pi Just like in the proof of Lemma
even here Clauses 54 and holding simultaneously preclude arm l from being eliminated by arm i regardless of round p. Therefore using work identical to the one that goes into establishing
F2
Equations 72 and we have,
4th +1
Pr (B2, E, S Ps. P)
S
(208)
TÁ
4th +1
(Because E; 2 0)
(209)
T
p=0
11
(From Equation 73 in Lemma
F2 0).
(210)
TA2
Q
Applying the Union bound to Equation 206 and plugging in the bounds in 207 and 210 we have,
43
Pr (B, Σ < Pt. I)
(211)
TA A
Substituting the bounds in Equations 211 205 and Lemma G.2
into Equation 196 we obtain,
E I2 (T) S max {Tp. + +T Pr (B,). Ta,
E [mg (T)
||] Pr (B)
(212)
32 log (TA2.)
43
1 A
+
E [n, (T) [ Pr (8).
(213)
A
Q
Which when combined with Lemma G.2 is the bound stated in Lemma G.3
BOUND ON THE NUMBER OF SAMPLES FOR ARM i"
Lemma G.4 (Bound on the expected number of samples of the maximum reward arm). For the arm. arg [ μa the expected number of samples accrued is upper bounded as,
32 log (TA?)
43
32
E 11-- (T)) < + max
+
+
AEA
2
i=1
A
Q,i
A2
32
43
+ E E (T) 12 > a }.
TA2.
TAP
Q.a
46

---

Published as a conference paper at ICLR 2025
E
142-
(T)
11
+
Σ
32
TA min
TA7
Where A {Amic] u (Aq.stjsa
Proof. Just like the proof Lemma analysis of the PE stage intractable.
G.3 we sequester away outcomes of the BAI stage that make
E [np (T) = E [n.. (T) PT())
E In (T) P())))((F(S)) +E [m.- (T) | Pr (8)
SEP(A)
(214)
< max
E [n.- (T) [T] { (n (T) [(()))
E (T) Pr Pr (3)
(215)
C: Pr)) < 1)
< max {E [ne-- [T) Tamax J
} + [m.. (T) 1 Pr
(216)
Equation 216 results from the observation that the maximum round number up till which any arm is
sampled during the BAI stage under F(S) AS E P(A) is maxx Conditioned on I, the reference arm é is identified correctly to be i*. Consequently, the expected number of samples E [n.- (T") can be analyzed in a manner that closely parallels the analysis of [me(T)] in the Proof of Lemma FB
that we grapple with the case E., >> Pa. This possi- bility arises because our bandit instance may have A. < AQ.a", which in turn implies that Pr (Pa- Eg- < aa- I)
The key difference from Lemma
The outcome Ea- > Pa- skips the checks associated with the events G2.-- and G3.0-. Mathematically, this means that for the event G. defined in Equation This motivates us to
36 we shall have Pr (Gi.a n ((G2,a* G3,a)) Ea+) E.. > Por, expand the scope of the good event Gar.
First we define new event G1,a" C Ω and then we augment the definition of G.- using this new event.
G {Arm is eliminated by arm a" in round Ea,, during ep. a' of the PE stage of PE-CS)
Remark G.4. Since arm a' enters the PE stage of PE-CS with samples corresponding La- number of rounds already accrued, checking whether the event Ga,a- holds does not involve any further sampling of arms.
The definition of Ga+ is now changed to the one in Equation 217 which supersedes the prior generic G.- (Equation 36
Ga =
Gí
((G2,a n
U n (Ea > Pa-
(217)
executed
Prior Guo Clause
New Clause
Remark G.5 (Implicit event in Prior Ga clause). We remark here that the event (Ea- S Pa-) implicit the event Gi O ((G2.a O Gz,a U Eay) i.e. Gi O ((G2.a O Gz,a)) U Enr) S {E S Pa }. This is because the event is contingent correct eliminations happening leading up to and during Par.
While retaining the definition of from Equation 74 and the definition of B1,a- from Lemma F.I redefine B., that the relation G B U..,. continues to hold.
G. G1.a" n (((G2a Gs U Ea- U (G4,a afaa- > P)r
(218)
G O (((G22 G3 U Eg. n Daa & Pa. U n (2a. > pa H)
(219)
47

---

Published as a conference paper at ICLR 2025
(due Remark G.5
G.- Gi,0- U (1(G UG -.aa))) ( Pa+ (n+) (Gi,a Ufza- S Pa-
Bugun
(220)
B U ((( ((aarreiill n (f S (o u uf Pa-3)
n(GGaa- n fE > partt fEa- I Pa- Pa-1))
(221)
a U
( Boriginal
n f2 S Pa. U UG n (2ia > Pa- 11
(222)
Bu²
Where Equation 221 follows from AU B = (An B*) U B being applied to both the left and right clauses. Equation 222 gives us the updated definition of the event B.
To continue bounding E [mg- (T) [T] from Equation 216 we shall condition on the collection of mutually exclusive and exhaustive events C, G {2 S a'), and G n {2 at} earlier used in Appendix [F] Armed with the updated event B.
now develop bound for
Pr (G' n (2 S [ using the result in Lemma F.6 By trivially generalizing the proof of
Lemma to the scenario for this proof where condition I we have,
(Z
Pr (B, IT)
(223)
1=1
43
Pr Pr(Ba. (T),
(224)
TA Q
from Equation 211 and Pr (E; P: D) = 0 Vi < a". We need now only develop bound for
Pr (Ba- (T) under definition in Equation 222
r) = Pr (( (Ba. priginall n (Ea- S Pa- U (G n (Ea- > Pa- 1r)
Pr (B.
(225)
< Pr (original
n Ea. sp.)11) + Pr Pr(G9 n taa > pa (T)
(226)
(Union Bound)
43
Pr (G n (Ea- > Pat IT)
(From Equation
137
(227)
- Q
From Equation 132 in the Proof of Lemmal F.2 we have the probability of arm l not being eliminated by arm a" during round wa- of episode as being upper bounded by 2 Therefore since climination under G4,a happens during episode a' in round Ea,,
TA3,-
2
Pr (G n aaa > )o-} ()) <
(228)
T
(since Pr (Ex- > oa- [T) 0, and Ám decreases with m).
32
(since by definition of A.
(229)
T
4
Combining the bounds in Equations
227 and 229
with the Expression 224 we have,
43
43
32
Pr n
+
+
(230)
TA
TA.
TA2.
We are now in a position to bound |na- (T) [T]. For brevity of notation we use the symbols Er and Prr to denote expectation and probability conditioned on r.
Er (ma- (T) Er (m-- (T) G Prr (G) Er (nv- (T) G 0 (7 s a a²)]
Prr Prr (G (Z 1755a) a'))
48

---

Published as a conference paper at ICLR 2025
+ Er (
(231)
I Er Inp (
+ tEr (T)
(Z d') ((>aa)) a')) (:
(232)
a--l
S Ep mp (T) G Σ
43
43
32
+
A
A
A
2,a
+ EE [ng. (T) (2 > a"}] Prp ((Z > a'}).
(233)
To bound E In- (T) G.T] we leverage the fact that due to the samples of the reference arm be-
ing Pr (mg- (T) max174 n, (1,12) G,T) o]] Conditioned G, T there can be no further sampling of the best arm i" beyond time Iz, since under I the best arm i" is the reference arm. Consequently.
E [n.- (T)
G,I
E
max (1,t2) G,T Eighs
(234)
S
E
max n4 (1, (.)) G it*
(because Pr (r a² G, = 0)
(235)
E mmax {[me (1, to Bica na- (1, to-), inz (1, )iza- } || [ (236)
E max [TAilisc The fre bise G.r]
(237)
(using definitions of A, and Σ)
max {[Teiiia max (Tp.. Tou-h } toati
(238)
(because Pr (Aa- max (pa- aa }}
0)
$ max (Talisa- Tamax
(239)
Plugging Equation of Lemma G.4
239 into 233 23d and the subsequent result into Equation 216
we obtain the statement
43
43
32
E [n- (T) max Tp. | Jiga Tamax
+
A Q2
2
A
E [m;- (T)
(2 > a²) Pr > a" IIT
E
[14- (T)
Pr (240)
32 log (TA2 min)
32 log (T (.))
43
32
max
A min
A
A
Q
iSa
1=1
32
43
+ E [n (T)) 12 > aa),11
TA
TAQ.a
TA
11
32
E [23- (T)
+
(241)
TA
TA
min
j
Where Equation 241 follows from from the bound on Tp. shown in Equation
52 and from Lemma
G.2 In reaching the bound used for Pr (f7 a²} [T) we use {Z > a"} C B. and the bound on
Pr (B - IT) shown leading up to Equation 230
UPPER BOUND ON THE NUMBER OF SAMPLES FOR ARMS > a², a., #
Lemma G.5 (Bound on the expected number of samples of high-cost arms). For any high cost arm with > i + i", its expected number of samples are upper bounded as,
32 log (TA?) + Em (T) 12 > d'),]]
32
43
E [m (T) 1 +
+
TA
TA
Q.Q.a*
TThis is because in PE-CS all sampling of arm it, or of any arm for that matter, leading up time tz always matched exactly by the number of samples of another
49

---

Published as a conference paper at ICLR 2025
E [T (T)
())
11
Σ
32
TA min
TA
Proof. To prove the bound stated in Lemma G.5 proceed with initial steps identical the that go into proving Lemmas G.3 and G.4
E (n; = E (2) Pr
Σ
E (Z)( P( + (T) 8) Pr (3)
SEP(A)
(242)
max
E (T) [r],
max ([)((T) F(8)) + (m((T) Pr
(243)
SEP(A)
(::Pr(T) + Pr (F)
1)
S max (T) [T), To.} + E [n, [s]
Σ J
(244)
TA
TA
min
Where the final bound is from Lemma G.2 Now we must bound the expectation term EE [T, [r]. For this recognize that during the PE-stage, the critical event which determines the number of samples further accrued for a high-cost arm is whether the final PE episode Z > a* or not. In the case when Z S a", there are no further samples of arm accrued beyond the BAI-stage.
E (T) r] E In (T) 12 Pz a² (] + + (m) [2 ['3 < a" (T)
(245)
To. B (T) [2>0"",
(T)
(since (z>a") C Ba
(246)
32
43
T.. (B 2Z a').1
(247)
TA
T
aaa
Where the final line follows by using the bound developed in Equation 227 [ne (T) we obtain the bound stated in Lemma G.5
Returning to bounding
32
43
E [n,(T)) < Ta. + (T) 12 > a²) a1
T
TA
Q,0
+ (E(n:(T) [.3]
11
+
Σ
32
(248)
TA2 min
TA
3
32 log (TA?)
32
43
< 1 +
+ E (T)
{2 ,"),
A7
TA
TD
+ E (T)
Ø
11
+
Σ johs
32
(249)
TA2
TA
min
We combine the results obtained in Lemmas G.3 G.4 and G.5 by adding together the contributions to regret of the three categories of
Finally, we have all the pieces needed to prove Theorem 3.4
arms while coalescing terms.
Proof of Theorem 3.4 Using Equation 13 from the regret decomposition Lemma D.5 we can ex- press and bound the expected cumulative cost regret as,
E. [Cost Reg (T,v)
(250)
50

---

Published as a conference paper at ICLR 2025
K
Σ
t
E m4 (T)
(251)
C
Σ
(T))
A.,- [n (T)
(because 40,; =0, Vi a²)
(252)
i>a", .ip1"
Σ
A C.
1
log (7A?)
+ E [m (T)
32
+
43
A?
TA
TA
Q
11
32
+ E [24 (T) 3
Σ
TA
TA
min
371
32 log (TA?)
43
32
+ +.0.-
1 max DEA
+
+
2
A
A
1=1
32
43
+ E (14-(7)
(2 > a" r|
+
TA
TA
Q
Q,0"
+ | (T) /1
11
+
Σ
32
(253)
TA
TA
= Σ
A E
C. [m (T) (8)
11
32
Σ
A
1+
32 log (TA?)
TA2
TA?
A
$>0*
min
i>e* .it
32 log (T
43
32
+ + C,
1 max AEA
+
2
A2
A2
1=1
Q4
32
43
Σ E (n, (T)
(Z a") J
(254)
TA2
T
1>
11
32
32 log (TA?)
< max
+
Σ
Σ
A+
1+
[E[K]
2
A?
A?
min
j71
ia .ifi
32 log
(T
43
+ C
+ max AEA
+
2
A
22
1=1
Q
32
43
+ max
At C₁
+
(255)
i>a" [[]K]]
A2
a
A
Q,a"
Where the final expression stated in Equation 255 is derived using Σise 4 [T,(T) X s
max a .. Here X is used as a placeholder for conditioning 3 or {Z a',,r. Proceeding identically, for Quality Regret we shall have,
(Quality_Ree (T, v)]
(256)
K
1 E | (T)]
(257)
Aq (m:E(((TT)
Σ
En,
(258)
i :ight"
AQs
1+
32 log (TA3.) ),
43
+
E
In (T) |
11
+
Σ
32
(259)
22.1
2
TA2 min
TA?
K<a*
373
51

---

Published as a conference paper at ICLR 2025
Σ
2Qi 1
32 log (TA?)
+ R.
(T)
32
43
A
T
TAQ
i>a" ,i7t1'
)) T43
11
32
+ E [n (T) |1]-
+
Σ
TA
jj("
32 log (TA Q.1)
43
11
Σ
32
max A+
Σ
K
E (T) 1
K<a"
Qq
AQ.i
T
min
TA
iE[K]
1=1
TA2
32
TA
43
Q
Σ
[[n((T)
13 > a²) a"},1j
A+
32 log (TA?)
A+ 2
(260)
A?
1>a" .ifi""
32 log (TA)
43
Σ
AQ.
32 log (TA?)
QQ.
AQ.i
Q
A
<<a"
K
32
43
11
32 TA
max A
A
+
A
Q
sE[K]
max A
Q
TA min
+
Σ
A
Q
(261)
Where Equation 261 the upper bound on expected cumulative quality regret stated in Theorem 3.4
and follows from the linearity of the expectation operator and the total sample budget being T.
Similar to the description that followed the proof of Theorem 3.2 the regret bound and provide their interpretation underbraces.
we rearrange the various terms in
32 log (T
Σ
43
32 A
43
max 1
AEA
A
A
Q,a"
Contribution from under nominal lerminatiion in PE PE-slage episanee a
Contribution from i" under mis-termination in PE-stage episode S'a"
+
Σ
32 log (TA?) A?
max A C2
32 AZ
43 2
Q,a
Contribation from high-cost arms with proper end the BAl-stage
Contribation from PÉ-stage episodes >a" case mis- termination during op a"
11
32 プマ
+ max C
[E[K]
A2 min
Contribution from impruper end BAI stage
And for quality regret,
32 log (TA2 DQ.
43
32
43
AQ.i
max A+ D [E[K]
+
AQ.
A
2
Contribttion from < a" under nominall terinnation in PE-stage opisode
Contribution from 3 < a under mnistteriiaaton in PE-stage opisode S.a
Contribation from PE-stage episodes 2
of mis-termination during op
A i>a" (
Σ
32 log (TA?) 1+
max A+ (E
11
32 AZ
A?
2 min
j
Contribation from PF-stage episndes >a" in of mis-terminationn during op
Contribution from improper cad BAI stage
52

---

Published as a conference paper at ICLR 2025
Where A; μ4¹ A4 conventional gaps, Amin 1r m 14, is the smallest conven- tional gap, and A [Amin] U (Aq.) jsa is defined especially to bound samples of arm i* under expectation.
53

---

Published as a conference paper at ICLR 2025
H ALGORITHMS AND ANALYSIS FOR THE FIXED THRESHOLD SETTING
As described the main paper the fixed threshold setting is the variant of the cost subsidy frame- work that imposes reward constraint in the form of fixed known reward threshold μо- Below in Algorithm 6 we present a pricipled approach for regret minimization in the fixed threshold MAB-CS setting.
Algorithm 6: FIXED THRESHOLD UCB (FT-UCB)
Inputs:
Bandit instance v/, Fixed threshold μо.
Initialize: Samples n2 0, Empirical Means P k E [K], Time
1
while f < do
ift K then
3
ke +
4
else
5
C. t [k: (x()) +
2log
2 pe
1/ Identify all arms with UCB
(2)
satisfying reward threshold if C, # Φ then
k + arg minjec, Gi
else
k + Uniform(K)
10
(t + 1), nlt + 1), 1
(()) // in Appendix
ANALYSIS FOR FT-UCB
operates the fixed threshold setting with fess no, where No > 0, pm E R a known threshold. Although the setup for the fixed threshold setting remains similar to the known reference arm and subsidized best reward settings discussed in the main paper, the key difference in the definition of optimal arm a". In this section, optimal action a arg 2,0 G. We highlight that while in the known reference arm and subsidized best reward settings, the structure of the problem ensured that feasible arm always existed. In the fixed threshold setting, assume that there is at least one feasible arm satisfying the reward constraint.
Theorem H.1 (Instance dependent upper bound
and quality regret for FT-UCB), For bandit instance over horizon T, the expected cumulative cost regret E (Cosi_Reg (T v)] and quality regret E [Quality Reg (T, v)] of the FT-UCB algorithm are upper bounded respectively as,
E Reg (T,v))
Σ
C
+
6
max A $20"
ima++1
0
8 8log T
a"
n² max A KE[K]
E QQuality_Reg (T,v)]
A
Q
Q,
Q
Along the lines of the analysis the expected cumulative regret for PE in Appendix F to prove Theorem H.T we first bound the expected number of samples of sub-optimal arms and then combine the results together into a regret bound using the regret decomposition lemma.
UPPER BOUND ON THE NUMBER OF SAMPLES OF ARMS i a²
Lemma H.1 (Upper bound the sum of the expected number of samples of all high cost arms). The sum of the expected number of samples of all high cost arms accrued after the initial sampling of each arm upper bounded as,
2
Σ E [K (K= 1, <
54

---

Published as a conference paper at ICLR 2025
Proof. We prove Lemma H.1 by first writing an expression for the samples of any high-cost arm. Then upper bound the expression by the number of times the optimal arm a" excluded from the set of empirically satisfactory arms G. We can bound this way because at time an arm > a" can only be picked if the arm a* is not inside the set C..
Σ ni(K 1,7)
Σ
Σ
1 (k: =
Σ k=
1 {a" + +1....,K? K}} (262)
+1t=K+1
1fa" $ Oi}
(263)
t= k+++
T
2log(1 - 1)
1
Par (May (t - 1)) + /
< 1o
(264)
Na (t - 1)
t=
2 2log(t (t 1)
Σ t=
Par (May (t 1)) Ma < po Ma
na (t - 1)
(265)
2 log(t - 1)
Pa (8) Har < Muu Ma.
(266)
tm K+1
Taking expectations, and perform a shift of in time-indexing, we have,
K
K
E
ni(K + 1,7
Σ
E (n,(K + 1,7)
(267)
i=
+1
=
2 log
Pr
Paa (s)
pa- 140 Ma"
(268)
2logt
Σ
exp
-2s
(using Hoeffding Inequality D.2
8
(269)
(270)
(271)
UPPER BOUND ON THE NUMBER OF SAMPLES OF ARMS i < a²
Lemma H.2 (Bound on the expected number of samples of low-cost arms under FT-UCB), For any low cost infeasible arm a", its expected number of samples accrued upper bounded by,
8 8log T (2
2
Eln <
+E
1
Where the last expectation term represents any samples of i accrued by uniform random sampling when we find C, empty.
Proof. We begin by writing expression for the random variable nT(T) denoting the number of samples of arm i.
T
n. TT(T) 1+
Σ t=
1ske = i, 1,
Σ
1 1 = =
(272)
t=
55

---

Published as a conference paper at ICLR 2025
T
T - +
Σ k=++1
1 [
Σ
1(k = i, =
(273)
t=k-1
T
mg
Σ t=++1
1k i, C, 6, nt(t 1) ス mo}
Σ
1 = -, o}
I=++1
(274)
T
2 2 -1] ni(l 1)
2 no, niit -11 2 mo }
m0g +
Σ
ji (ni(1 1))
mi(t-1)
t=K+1
T
+
1 1ike -;
(275)
t= K+1
2ogt 2 Mo
< mg
Σ
Σ [=1 8=11
1 (i(s)) +
+ Σ
1 = =i i (276)
t=l
Taking expectations on both sides, we have,
20
2 logt
E| [[n{ S mo +
Pr ((r(8)) - ui 2 AQ.
8i
[= S1=1
flie = i, C, = =0]]
+ E
(277)
Applying Hoeffding Inequality, we have,
Pr sas - 2 Aes - v
2 logt
2 log
< exp
-28; AQ,i
(278)
2 2logt
2 llog
S exp
-2s; (Aq.))+
+
2
Si
(279)
Plugging in the bound in Equation
279 into Equation 277
we have,
2oot
2 log
[T)) S
mo
exp
-2s;
+ (2Q,)² - -2Ae.1
+
8;
1=1 m
+ E
(kg = i; C2 Φ5}
(280)
1=1
We pick mg
Blog [
in the proof technique in Auer al. 2002).
logt
-1)
1 1)
x²
[[n, S mo
Σ
exp
-4logt 2s, (A.,))
(1 VogT
(281)
6
t=1 a.=mg
Since & < T, we have,
E [T,( < llg'
x
Σ
Σ
exp (-4log () +
Σ 1 - C
ik=
(282)
(2
8y Symmp
8 loo'? T
1
<
+ ++
+ E
the = C, =0) Σ
(283)
(q..)²
13
1=1
56

---

Published as a conference paper at ICLR 2025
8 log T <
x²
8
+
+
1
-k==i,
= =
(284)
(A.
6
1=1
We are now in a position to prove Theorem H. by combining regret decomposition (Lemma with the results of Lemmas and
D.5
Proof of Theorem H.
First for cost regret we have,
K
Reg (T,v)
Σ
A G
In (T) (because 4., -A0 S a')
(285)
+1
K
A 1
ne (1, K) + n (K + 1,T]]
(286)
Σ
A C₁i
max At
Σ
E [m; (K (K 1))
(287)
12.2
i==++1
x=
K
π
max A., 6 i>a
(plugging in Lemma H.1
(288)
C₁i
1= +1
Next for quality regret,
K Σ
Quality Reg (T, =
E
n (T)]+
A [ns (T)
(because AQ... = -))
i=a'+1 41
(289)
8logT (AQ..)²
π²2 +E E
+ +1+
Σ l==1
(kr = -i, =]
Q
6
K
Σ
a (E [n (1.
+ E [n
(K + 1,T)))
(290)
i=a7+1
8log T (AQ.))
n²
+
1+
+
E
(kr i o0
Q
6
1=1
K
max A D
Σ
E
(he fa" + +1..... [.....,]]]
Q
ima"41
K+1
(reused from Equation 262
(291)
8log D
+
1+
A+
6
Q
i=1
80
max 4 E Ka"
kt E fl....,,"
a" 11. = of
Clause A
Σ
A
max A D=
Σ I=K+1
E
1
ke E far +1....,KKK K)
i=0441
Clause
(292)
1
SlogT
+1+
x2
a' Σ
A Q
+
6
A
Q
i=1
57

---

Published as a conference paper at ICLR 2025
+ max xE[K]
E
[Clause or Clause B}
(293)
1
Blog? T
x
+
+
A Q
QQ,i
6
i=1
max
A
2,
E
1
La
&CJ
(because a" C. 2 Clause A, Clause B)
(294)
8log'T
(1+
m² max 40. iE(K)
(295)
Q
Q
Where Equation 295 follows from the bound on Er Pr (a" & C,) shown in the proof of Lemma
Remark H.1 (Comparison with lower bound). Theorem H.l and its analysis reveal that FT-UCB is
an orter-optimal algorithm for the fixed threshold MAB-CS setting. The lower bound of Theorem E.6
is matched precisely by FT-UCB's O(1) bound on expected cumulative cost regret and its O (log T)
bound with dependence only on the quality gaps of arms i < a² for its expected cumulative quality regret.
58


Reviews:
[{"review_id": "npzDc88fY4", "reviewer": "Reviewer_wsgZ", "summary": "This work studied the bandit problem with cost subsidy. It proposed the PE-CS algorithm and derived an upper bound on its cost regret and quality regret. The paper provided a detailed description on the design of the algorithm. It also evaluated its performance with numerical simulations.\n\n\n\n=========\n\nAfter rebuttal: score increased to 6.", "questions": "Please see the *Weaknesses* section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is overall easy to follow.\n1. The paper reviewed the various related works.\n1. Algorithms are evaluated with both toy data set and real-life MovieLens data set.", "weaknesses": "1. As the CS model is built on Sinha et al. (2021), I would suggest the author(s) to compare the theoretical results with Sinha et al. (2021) after stating the theorems.\n1. There are various related works with slightly different models, are the algorithms and their performance comparable? Can those algorithms work under this setting and what are their performance?\n1. Considering the plots in Section 4, the target of the algorithm seems to be minimizing the sum of the cost regret and the reward regret. Is that true? I think the target of an algorithm in this problem should be clarified. Besides, is there a trade off between minimizing the cost regret and the reward regret? Why are we interested in the sum of the two regrets?\n1. As there are already a number of similar models, what is the motivation to consider this model?\n\nMinor comment:\n1. Line 168: Should there be '' We build up our approach to optimize sth. for the regret objectives ...\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "IavoszkQHy", "reviewer": "Reviewer_fMRh", "summary": "This paper considers multi-armed bandits. Instead of the traditional problem of maximizing total reward, they consider the problem of minimizing cost subject to a reward constraint. This formulation has been recently proposed in SSKA '21. In this paper, the authors extend the formulation to two settings:\n\n1. Known threshold where there is a fixed reward threshold that should be met in expectation.\n\n2. A reference threshold to an (initially) unknown arm that should be met in expectation.\n\nFor both problems, they consider A) the cost regret which is the zero-clipped total expected cost of the algorithm relative to the lowest-cost arm that meets the reward constraint and B) the quality regret which is the zero-clipped difference in expected reward of the algorithm relative to the reward threshold.\n\nThey propose a pairwise elimination algorithm that compares arms in a pairwise manner while recording the history of arms to improve efficiency. For the unknown reference threshold setting, they add an exploration phase where they learn they try to learn the reward of the unknown arm. In both settings, they show logarithmic bounds on the cost and quality regret in terms of the number of steps $T$ and the maximum instance-wise quality and regret differences.\n\nThey try these algorithms on a few datasets and find that it performs better than other algorithms (which, to be fair, were not designed for this setting).", "questions": "* What tools do you use in the analysis of your algorithms? What is the general strategy?\n\n* How do you re-use samples for downstream comparisons in your algorithms?\n\n* Can you make the case for the zero-clipped comparison again? I wasn't persuaded by the (repetitive) paragraph about stellar performance for different ad products in section 1.1. In addition, does your analysis require the zero-clipped comparison?\n\nWith additional experiments on other datasets and settings, and satisfactory answers to the above questions, I would be happy to increase my score to at a 6.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* They consider new settings which seem reasonable to study.\n\n* They propose new algorithms.\n\n* They show bounds on the performance of their algorithms.\n\n* They evaluate their algorithms in practice.", "weaknesses": "* Without reading the appendix, it's unclear to me what tools they use in the analysis of their algorithms.\n\n* The statement of the bounds is difficult to parse (classic ML with too many terms which are hard to interpret).\n\n* The algorithms are similarly difficult to understand. For example, I don't see how the history is recorded to \"intelligently re-use samples for downstream comparisons\".\n\n* The algorithms are only tested on the movielens dataset and a toy dataset under specific hyperparameter settings. I would prefer at least three datasets and plots of performance for each hyperparameter ($\\ell$, $\\mu_\\ell$, and $\\mu_{CS}$) to validate that the performance is consistent in different settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "e5anF4SqVl", "reviewer": "Reviewer_MwCh", "summary": "This work studies the Multi-Armed Bandits with Cost Subsidy (MAB-CS) problem, where a primary metric (cost) is constrained by a secondary metric (reward), and there is an inability to explicitly determine the trade-off between these metrics. The authors introduce the Pairwise-Elimination (PE) algorithm for a simplified variant of the cost-subsidy problem with a known reference arm, and generalize PE to PE-CS to solve the MAB-CS problem in the setting where the reference arm is the unidentified optimal arm. The authors provide instance-dependent bounds for PE and PE-CS for both Cost Regret and Quality Regret. They also conduct experiments to support the theoretical claims.", "questions": "1. See the weakness.\n2. Is it possible to provide some lower bounds for this problem?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is well-motivated. The authors provide interesting examples of applications of the MAB-CS framework.\n2. The paper is well-written.\n3. This work extends the MAB-CS framework to include two new settings, and develops two novel algorithms PE and PE-CS . The authors also provide instance-dependent bounds for the proposed algorithms.\n4. The authors conduct experiments on real-world data to support the theoretical claims.", "weaknesses": "I feel some statements are somehow overclaimed. In Lines 115-126, the authors claim that the regret bounds of their proposed algorithms are $O(\\log T)$, while for ETC-CS it is $O(T^{2/3})$. However, their bounds are instance-dependent and are not $O(\\log T)$ in the worst case, while the  $O(T^{2/3})$ is the worst-case bound. Therefore, such a comparison seems to be over-claimed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "HPRUHXVXgk", "reviewer": "Reviewer_CGLm", "summary": "This paper proposes the pairwise elimination (PE) algorithm for bandits with a cost subsidy model. First, it develops a simple PE algorithm that addresses two simplified versions of the MAB-CS model with a known reference arm. Then, it extends the PE algorithm with a BAI subroutine to address the MAB-CS model without knowing the reference arm. Theoretical analysis verifies that the algorithms have instance-dependent logarithmic regret/cost upper bounds. Experiments also verify the PE-CS’s performance.", "questions": "### Minor Comments\n\n- For the `sample_and_update` subroutine, it would be better to give the details, possibly in the appendix, if there is no space in the main paper.\n- In Line 321, the `omega` should be $\\omega$.\n- Why, in the experiment, the regret and cost are always reported in a summation form. Would it be interesting to plot one as the x-axis and the other as the y-axis and check whether there is a trade-off?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. New theoretical results. This paper proposes the first algorithm with instance-dependent logarithmic regret/cost guarantees for the MAB-CS model.", "weaknesses": "1. The algorithm design and analysis of the paper are not novel, and the theoretical results from the proposed algorithm are not interesting (i.e., expected). The algorithmic technique is very similar to prior literature, and the analytical approaches are also similar to other related works. The reviewer would suggest the author look into some challenging parts of the topic, like the lower bound for the MAB-CS model and proposing near-optimal algorithms (e.g., how to revise the UCB-CS algorithm so as it also works for the MAB-CS model).\n2. The writing of this paper is not easy to follow. For example, when introducing the three types of model settings (Lines 93—101), which are supposed to be mathematically rigorous (e.g., for clear math notations and definitions), the paper uses an example to explain these three settings vaguely. Another example is the inconsistency of the notations. The notation $\\mu_{\\text{CS}}$ was used much earlier before it was formally defined. The two gaps $\\Delta_C$ and $\\Delta_Q^+$ should both have a plus on the superscript, but one is defined explicitly, and the other implicitly, which is inconsistent and confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)