Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy

Response to reviewer CGLm

Response Key: Wi: Direct response to weakness number i

Qi: Direct response to question number i

#################

W1

We respectfully disagree with the reviewers objections about a lack of novelty and with their comment about the theoretical results being expected. To make our case for the novelty in algorithm design and analysis we would like to draw attention to specific original contributions that we believe are significant.

1. We introduce two new structured bandit problem settings: fixed threshold, and known reference arm within MAB-CS. While these new settings are natural extensions of the work in sinha et al. 2021, they significantly enhance the utility of MAB-CS to practitioners.
2. Our PE algorithm is the first approach to MAB-CS that evaluates feasibility of arms in cost order. It builds upon improved-ucb (Auer and Ortner, 2011) but has significant additional structure that is novel and original. A feature is sample re-use where the same samples of the reference arm $\ell$ are leveraged to evaluate the feasibility of candidate arms across episodes of PE. (Lines 275-282)
3. A practical extension to PE is asymmetric-PE (the details of which we present in Appendix C). Asymmetric PE uses a completely different arm elimination criteria than any prior works. In particular it uses different exploration bonus terms $\beta_{\ell}$ and $\beta_i$ for the reference arm $\ell$ and candidate arm $i$ under evaluation. (Lines 311-319).
4. We provide an analysis of PE that conditions both on events at the intra and inter-episode levels. We show that the probability of improper outcomes at both the intra and the inter episode levels is small. (Lines 298-303)
5. We develop PE-CS by cascading BAI() and PE() and analyze it in part by characterizing the probability of our best arm identification subroutine making an error which is an original style of analyzing an algorithm. (Lines 399-405)
6. Through experiments we show that PE-CS significantly outperforms the only other algorithm from the MAB-CS literature that has a regret guarantee (namely ETC-CS). Moreover we argue that even including other baselines that lack any guarantee, PE-CS offers the best balance between reliability and performance (Figures 2, 3).
7. Lower bounds which have been included in the rebuttal revisions (see below).

Lower Bounds:

• The reviewer's suggestion about working on other challenging topics like the lower bounds is well taken. We have worked out lower bounds for the known reference arm and subsidized best reward cases and these are now stated in Theorems 3.1 and 3.3 respectively (line 216, 322). Extended discussion and L.B. proofs are available in Appendix E.

• In particular we would like to highlight that PE is now shown to be an order optimal algorithm for the known reference arm setting (lines 305-310). Moreover, we find that while PE-CS is not order optimal, there is a class of bandit instances for which it is order optimal (Lines 407-410, and Remark E.7 in Appendix E).

• Finally, we argue that the while the general form of the upper bounds can be considered expected, working out the details is a significant contribution and represents an important step towards characterizing the MAB-CS problem formally. We have updated the presentation of the upper bound result in Theorem 3.2 for PE and in lines 399-405 for PE-CS to better reveal the saliency.

• The reviewers suggestion about proposing near-optimal algorithms is well taken. We would like them to consider that PE and PE-CS do in fact satisfy this requirement (PE-CS only for a certain problem class).

• We are not sure what the reviewer's suggestion was when they suggested that work be done on revising the UCB-CS algorithm for the MAB-CS model. The UCB-CS algorithm (Sinha et al. 2021) was in fact proposed for the MAB-CS model. Moreover, through experiments in Section 4.2 we make the case that the strategy of the algorithm is flawed and has a fixed probability of permanently incorporating an infeasible arm in its empirically feasible set. We may have misunderstood the reviewer's intent with their feedback and would really appreciate a clarification.

Response to reviewer CGLm

#################

W2

The reviewer's feedback on issues with the writing are well received. While we have used the rebuttal period to significantly improve the presentation in many ways we highlight specific corrections made in response to W2.

• The three types of model settings are now introduced more formally in lines 96-102 of the revised version
• The notation $\mu_{\text{CS}}$ is now defined before its first use in line 66-67.
• We now have made both cost and quality gaps explicitly zero-clipped, and have applied this change through the paper. (Lines 75, 78, 283 (Thm 3.2 ), 377 (Thm 3.4)). We thank the reviewer for this suggestion as it improves readability.

#################

• Q1: We apologize for the oversight in not including sample_and_update(). It is now included in Appendix B and a reference as such has been provided as an inline comment in blocks Algorithm 1 and Algorithm 2. (Lines 263, 358)

• Q2: Corrections to change text omega to symbol ${\omega}$ made

• Q3: The reviewers feedback on the regret metrics being summed together and not plotted separately is well taken. The reason we chose to do this is that we did not find the differences in the trade off's made by different algorithms (we test 4 for the subsidized best reward setting) to be particularly insightful. However, please see our post tomorrow when we shall share a revised Experiments section with new results addressing this and other experiments requested by reviewer fMRh.

Response to reviewer CGLm (2/2)

---

Trade Offs

The reviewer pointed out in their initial assessment that discussion and experimental results around trade-offs between cost and quality regret were lacking. We however highlight that from the point of view of the optimal policy on MAB-CS there is no tradeoff between cost and quality regret. This is because optimal policy sampled arm $a^*$ as often as possible and arm $a^*$ has zero incremental cost and quality regret.

The zero-clipping in regret definitions ensures that samples from 'an arm with high quality and low cost regret' can not be traded off (in terms of its informativeness about $a^*$) with samples from 'an arm with low quality and high cost regret'. This is why in the experiments we plot the summed together values of cost and quality regret on the y-axes to gauge how close each method is to the optimal policy.

We acknowledge that this might not have been clear from the writing in the paper and the initial rebuttal response. We realized that this point had to be made clear while responding to reviewer wsgZ in response (2/3).

We do in fact perform an experiment where we vary $\alpha$ for both the known reference arm and subsidized best reward setting like the reviewer asks (Figures 1 and 2 in Section 4 and associated observations in Sections 4.1 and 4.2).

It is unclear in their most recent comment: "For the additional trade-off experiments … performance of the algorithm would change" was referring to performance as we interpret it (summed cost and quality regret as explained above) (called (a)) or as the trade-off between cost (y-axis) and quality regret (x-axis) as they referred to in their official review (called (b)). We address both:

Fig. 1 (c), (d), Fig. 2 (a), (b) plot the terminal summed regret of all algorithms for different values of $\alpha$ for the same bandit instance. We chose to use the plot to discuss how our methods (PE / PE-CS) do better overall across all values of $\alpha$ ; however the plots could also be used to gauge the effect of $\alpha$ on regret performance. To see if the various methods systematically make choices that favor one of either cost or quality regret we plot the entire data from this experiment (i.e. across 25-50 runs each of for a range of values of $\alpha$) in Figures 5 and 6 (bottom row only in Fig. 6, top row of Fig. 6 represents data from varying $\ell$) as a scatter plot. This however is tangential to the goal of gauging performance and so did not make it to the main paper and is in Appendix A.

---

Response to reviewer CGLm (1/2)

---

The authors thank the reviewer for reviewing our rebuttal response and for their suggestions for directions of future work. We would like to respond to them with the following.

First, to counter the reviewer's assessment of novelty we provide an intuitive explanation for why our algorithms and results are novel, interesting, and even unexpected. The arguments there assume we have an agreement on the utility of the model. In case that is not the case we would request that the reviewer see our examples in the response linked here. Second, we directly address the point on trade-offs and new experiments raised by the reviewer. This part has overlap with the responses to other reviewers response W4 here and response (2/3) for W3 here.

—

Novelty

In our response to the original review we listed out the original contributions of our work. Here we provide a narrative explanation of the core novelty of the work. Our lower bound results (Section 3, Thm 3.1 and 3.3) reveal that only a reduced number of samples are needed from high cost arms in both the known reference arm and subsidized best reward settings. This reality, which is an original contribution in itself makes it clear that an order-optimal algorithm for these settings must consider (and eliminate) candidate arms one at a time in an episodic manner. This also means that a traditional UCB-like approach (UCB-CS in Sinha et al. for example) in which all arms are always (through $T$ samples) in contention for sampling cannot be order optimal. As the reviewer recognizes, PE (using elimination) is order optimal for the known reference arm setting. We highlight that PE-CS is order optimal in its regret contribution from low cost arms (for all instances) and for the best reward arm for some instances that we characterize.

Moreover, as stated in Theorem 3.3 the precise lower bound on the expected number of samples for the best reward arm $i^*$ under PE depends on the expected reward of 4 distinct arms. Namely the optimal action $a^*$, the best reward cheap arm $\arg \max_{i < a^*} \mu_i$, the best reward arm $i^*$, and the overall second best reward arm $\arg \max_{i \neq i^*} \mu_i$. This is a result that is unexpected and cannot be seen without carefully working out the details like we do in the proof of Theorem 3.3, Remark E.5 in Appendix E.

---

Response to reviewer MwCh

Response Key: Wi: Direct response to weakness number i

Qi: Direct response to question number i

#################

W1

• We thank the reviewer for highlighting the over claimed comparison between the worst case regret bound of ETC-CS and our instance dependent bounds. We have deleted the direct comparison from the revised Section 1.2 Key Contributions. The only reference to the different regret upper bounds now is in Section 4 and is a more nuanced comparison (Lines 513-521).

#################

Q1 = W1

Q2

• We have worked out lower bounds for the known reference arm and subsidized best reward cases and these are now stated in Theorems 3.1 and 3.3 respectively (line 216, 322). Extended discussion and L.B. proofs are available in Appendix E.

• In particular we would like to highlight that PE is now shown to be an order optimal algorithm for the known reference arm setting (lines 305-310). Moreover, we find that while PE-CS is not order optimal, there is a class of bandit instances for which it is order optimal (Lines 407-410, and Remark E.7 in Appendix E).

• Overall we believe that with our novel instance dependent lower bounds our rebuttal revised paper is significantly stronger than our original submission.

As we are working on the fresh experiments on new datasets and more detailed experiments from varying hyper-parameters the authors would like to request a clarification from reviewer fMRh on one of their questions.

The reviewer says under W4 (Weakness bullet 4) that they would prefer among other things: "at least three datasets and plots of performance for each hyperparameter $\ell, \mu_{\ell}$, and $\mu_{\text{CS}}$ to validate that the performance is consistent in different settings" This point is well received and these results have already been worked out for the MovieLens dataset we already used and are still being tested on the additional new datasets. However it is not clear to us what they mean by varying $\mu_{\ell}$ since \mu_{\ell} is uniquely determined by the choice of arm $\ell$ and the dataset (from which we infer explicitly or implicitly the values of the expected return of each arm).

A clarification would be greatly appreciated in this regard.

Response to reviewer fMRh

#################

Response Key:

Wi: Direct response to weakness number i

Qi: Direct response to question number i

#################

Q1: We agree with the reviewer that an explanation around analysis techniques was lacking in our original submission. We have made an effort to amend this at several places in the rebuttal revised version of the paper. We highlight the line numbers in the revised paper where changes were made and share a version of the same content here for convenience.

The general strategy for both PE and PE-CS regret upper bound proofs is to bound the expected number of samples of every arm type (low cost, high cost, or reference) by conditioning the expected number of samples on a nominal (good) event while simultaneously bounding the probability of the good event not happening by a small quantity.

• For analysis of PE in the known reference arm setting - (Theorem 3.2, Lines 283-310)

There are two dimensions to the execution of PE being nominal (good). First within an episode of PE the worse quality arm should be eliminated after a reasonable amount of sampling. Second is that execution across PE episodes should terminate in episode $a^*$

We separately bound the expected number of samples of arms with cost lower than the optimal action $a^*$, higher than the optimal action $a^*$, and the reference arm $\ell$. 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.

Finally in the regret upper bound Theorem 3.2 statement, we have also added underbraces to explain the origin of each regret contribution term.

• For analysis of PE-CS in the subsidized best reward setting - (Theorem 3.4, Lines 377-406)

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 (meaning $\ell = i^*$ identified correctly) or improper (meaning $\ell \neq i^*$ and there was a mistake in BAI). The phased nature of PE-CS admits a 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 (referring to the bound expression in lines 380-395) correspond directly (in order) to the three terms in the PE bounds for cost and quality regret (referring to Theorem 3.2 bound expression in lines 286-295). 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.

#################

Q2: Sample re-usage occurs in two contexts: Vanilla PE (our focus) and asymmetric-PE (our practical extension to PE). We have updated the draft to improve the explanation of sample re-usage. This explanation is now at lines 275-279 for sample re-usage in vanilla PE and in lines 311-319 for asymmetric-PE.

• PE computes a sample prescription $\tau$ using the current round number $\omega_i$ of episode $i$. During episode $i$ we are sampling arm $i$ and (possibly) arm $\ell$. Once the sample prescription $\tau$ is met for both arm $i$ and arm $\ell$, we check for elimination. Since no samples are ever discarded, episodes that are further downstream will re-use samples of arm $\ell$ from prior episodes when $n_\ell > \tau$ and forgo any additional sampling.

• In PE as presented in Algorithm 1, during an arbitrary episode evaluating the candidacy of arm $i$, the reference arm $\ell$ shall only ever have to be sampled if the samples of arm $i$ start to exceed the samples of reference arm $\ell$ that were already available. In practice, we implement another version of PE called asymmetric-PE. Asymmetric-PE allows for a mismatch between the number of samples of arms $i$ and $\ell$ that go into computing the exploration bonus terms $\beta$. Reusing all the samples of arm $\ell$ that have been amassed in this manner (from episodes leading up to the current episode) leads to earlier elimination decisions (Details in Appendix C).

Response to reviewer fMRh

#################

Q3

We appreciate the reviewer pointing out a lack of clarity in the need for zero-clipping. To address this we have re-written the corresponding paragraph in Section 1.

• Revised motivation for zero-clipping in Section 1, Introduction, lines 103-114:

With the MAB-CS framework, we target applications that are agnostic to the level of quality as long as the quality exceeds threshold $\mu_{\text{CS}}$. This structure necessitates the zero-clipped operation inside the cost and quality regret definitions. Consider for example a problem where it is known that customers need to be provided a certain (possibly unknown) service quality level for them to continue their subscription. Any quality on top of the feasibility level $\mu_{\text{CS}}$ would not improve the performance of our solution. For the marketing communication example from earlier, the quality threshold represents a 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 $\mu_{\text{CS}}$.

In the absence of the zero-clipped structure, cost and quality regret that are sub-linear in horizon $T$ could be achieved for our examples in an unintended fashion. An algorithm that samples sub-optimal arms $i \neq 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.

• Is the zero-clipped comparison required for the analysis?

While the zero-clipped gaps/comparison are not required for the analysis, they are closely tied to the analysis. The zero-clipping (or lack thereof) does not change the upper or lower bounds on the expected number of samples of an arm (arm of any category: low cost, high cost, reference). This is because the number of samples needed to make an elimination decision with high probability of accuracy is a function of the gap between their rewards regardless of the sense of the gap (i.e. regardless of which arm is higher quality). However the zero-clipped comparison does effect the the final regret expression as can be seen through lines 74-78.

#################

W1 = Q1

W2: We appreciate the feedback on the bound expressions being hard to parse. To address this weakness we have made the following changes:

1. For the PE upper bound (Thm 3.2, Line 283) we have added underbraces to every term in the bounds explaining the source of the term from the point of view of the analysis. This improves readability in that the $\sum_i E [ n_i ] \Delta_i$ form of expression becomes more apparent. Particularly the fact that some terms stem from "nominal" execution and others from an improper run.
2. Right after the PE upper bound statement in Thm 3.2 (Line 298) we have added a new explanation of the terms in the upper bound. In particular we have mentioned how the terms correspond to low cost arms, high cost arms, and the reference arm $\ell$.
3. For the PE-CS upper bound right after the bound expressions in Thm 3.4 starting line 399 we have mentioned that the first three terms correspond precisely to the three terms in the PE bound.
4. Right after the PE-CS bound, we have explained the origin of the fourth and fifth terms there too (line 404) and connected them to the proof technique of conditioning on the proper outcome of the BAI stage.
5. We have reduced the number of unique symbols in the regret expression, and have defined every symbol used (outside of ones that have already been defined and used repeatedly) at the end of the Theorem statement.

W3 = Q2

W4: The requested experiments are underway but have not been finished yet. Please expect another PDF revision and accompanying comment tomorrow addressing W4 on experiments.

#################

Lower Bounds

• To conclude we would like to highlight that with our novel instance dependent lower bounds (Thm 3.1 for known reference arm setting and Thm 3.3 for subsidized best reward setting) the rebuttal revised paper is significantly stronger than our original submission.

Response to reviewer fMRh

#################

W4: In our original submission there were two experiments on the MovieLens dataset separately for the known reference arm (setting 1) and subsidized best reward (setting 2) settings. These experiments were limited in that they worked with a single arbitrarily chosen reference arm $\ell$ for setting 1 and a single value of the subsidy factor $\alpha$ for setting 2.

In the most recent rebuttal revised version of the paper we have included more extensive experiments. We discuss the details of these updates below. Now there are three new and more extensive experiments performed on two datasets MovieLens and Goodreads (new). We thank the reviewer for inspiring these new experiments with their review.

• The first new experiment is for the known reference arm setting and varies the reference arm $\ell$ while keeping $\alpha = 0$ fixed. It looks at the terminal sum cost and quality regret for each of these choices of $\ell$ at the end of T = 5 million samples. The result is a scatter plot showing the distribution across 25 independent runs of PE and competitor UCB-CS. Available in Fig. 1(a), (b).

• The second new experiment is also for the known reference arm setting. It keeps $\ell$ fixed at an arbitrarily chosen arm from the bandit instances associated with the datasets and varies $\alpha$ between 0 and 0.45 in intervals of 0.05 (so 10 unique $\mu_{\text{CS}}$ values). This experiment too looks at the 5 million sample terminal regret across 25 independent runs for PE and UCB-CS. Available in Fig. 1(c), (d)

• The third new experiment is for the subsidized best reward setting where we vary the only available lever of the subsidy factor $\alpha$ between 0.05 and 0.45 at intervals of 0.05 (9 $\mu_{\text{CS}}$ values). Similar to the first two experiments we scatter plot terminal regret for 50 independent experiments and compare with ETC-CS, UCB-CS, TS-CS baselines from the literature (Fig. 2(a), (b)).

#################

Added in Edit:

We get the following key takeaways about performance of algorithms from these experiments (Figures 1 and 2 of Section 4).

• PE beats UCB-CS (modified with $\ell$) most of the times outside of cases when $\alpha > 0.3$ (so last three values of $\alpha$). We see this both in MovieLens and Goodreads.

• PE-CS always beats ETC-CS (exception being a single Goodreads experiment with $\alpha=0.05$ where ETC-CS is slightly better). Large $\alpha$ values do favor TS-CS and UCB-CS to the point where PE-CS is not comparable to them.

#################

• We would also like to take the opportunity to clarify one of the reviewer's observations in their reviewer paper summary. They said that the baselines "were not designed for this setting". This is not true since the ETC-CS, UCB-CS, and TS-CS algorithms which we use as baselines against PE-CS were introduced in Sinha et al. 2021 precisely for subsidized best reward setting (which Sinha et al simply call MAB-CS). It is true however that we modify UCB-CS to work as a baseline in our novel fixed reference arm setting so the reviewer's observation is correct for the known reference arm setting since without the modification UCB-CS cannot be used in the setting.

• In addition to these three kinds of new experiments on the two datasets, we retain the toy experiment we had designed to highlight the issues with the baselines that lack guarantees namely UCB-CS and TS-CS. However, in the revised paper this has been moved to Figure 8, Appendix A.

• Another visualization of the data from the aforementioned three new experiments is the trade off between cost and quality regret by plotting them on the y and x axis respectively. Since the insights from these visualizations are tangential to the aim of Section 4, they were put in Appendix A.

• We realize that one of the reviewer's conditions for increasing their score was experiments on three datasets. However between the several kinds of revisions needed there was not enough time to add a 3rd dataset and its associated set of three experiments. We can however add the experiments we did not get a chance to complete during the rebuttal in the camera ready version if ICLR policy allows.

• Moreover, we highlight that lower bounds for setting 1 and setting 2 are now included in Section 3, Thm 3.1 and 3.3. Since the regret upper bounds for PE match the lower bound developed in Theorem 3.1 up to constant factors, PE is shown to be order optimal. This reduces the reliance on experiments for validating PE's performance. In light of this, we would ask that the reviewer consider going through with increasing their score to 6.

Update: Supplementary PDF deleted, lower bounds incorporated in main paper and paper PDF updated.

Responses directed to individual reviewers to follow shortly.

Response (2/3) to reviewer wsgZ

---

W3

We appreciate the reviewer raising this point and acknowledge that this had not been made clear in our original writing. In fact another reviewer (reviewer CGLm) pointed this out as well.

• The objective of the cost-subsidy framework is to solve decision making problems where a primary metric (cost) is constrained by a secondary metric (reward) (Abstract lines 17-20). Looking at the cost or quality regret metrics individually is not meaningful. Since the cost of sampling each arm is known, a bad policy could trivially make cost regret zero by sampling cheap arms regardless of quality. In reality there is no trade-off between cost and quality regret, and the underlying goal is to converge onto sampling optimal arm $a^*$ as sampling $a^*$ incurs neither cost nor quality regret.

• The reason there is no trade-off is due to the zero-clipping in the regret definitions. The zero-clipping ensures that samples from 'an arm with high quality and low cost regret' can not be traded off (in terms of its informativeness about $a^*$) with samples from 'an arm with low quality and high cost regret'.

• This is why in the experiments we plot the summed together values of cost and quality regret on the y-axes. We implicitly aim to minimize the sum as it is the natural objective. We would be happy to make this point clearer in the final version of our paper.

• Lastly, we would like to highlight that as of the rebuttal revised paper we now have instance dependent lower bounds on the number of pulls of sub-optimal arms for both the known reference arm and subsidized best reward settings. From our lower bounds (Section 3, Theorem 3.1 and 3.3) we prove that among a class of consistent policies PE is the policy that samples all sub-optimal arms an order-wise optimal number of times. Meanwhile, PE-CS achieves this goal for some sub-optimal arms. Where consistent policies represent the policy class that does not incur linear summed regret on any bandit instance.

---

Response (1/3) to reviewer wsgZ

Response Key: Wi: Direct response to weakness number i

---

We thank the reviewer for their insightful review, and would like to share our rebuttal response promptly as the discussion closure deadline is almost here.

At the outset we would like to highlight that the paper has been updated and the locations in the paper (line numbers, theorem's, and figure numbers) we refer to in this response are those in the revised version.

W1

• While setting three in our work (a.k.a. the subsidized best reward setting) is indeed identical to the cost subsidy setting introduced in Sinha et al. 2021, in our work we prove instance-dependent guarantees (lower and upper regret bounds), while Sinha et al. worked on worst-case guarantees. Thus a direct comparison between the bounds is not suitable.

• While we do not make direct comparisons between the bounds (for the above stated reasons), in Section 4, lines 517-519, and in lines 524-526 we talk about why and how the empirical performance of ETC-CS (The only algorithm with a guarantee in Sinha et al. 2021) compares to that of PE-CS (our approach).

W2

We had given considerable thought to adapting the approaches from other related works as baselines, a discussion of which never made it to the paper therefore we think this is a great question!

The related works to ours in the Cost-Subsidy framework can be classified broadly into (a) Bandits with constraints, (b) Multi-objective multi-armed bandits (MO-MAB), and (c) Bandits with costs. We separately address why approaches from none of these families worked out as baselines.

(a) Bandits with constraints: This class of work accounts for some kind of a constraint on reward in decision making. An example would be Conservative Bandits (Wu et al. 2016). The problem with adapting any of these methods into MAB-CS is the absence of any considerations for the primary metric of cost in their design. While costs can be shoehorned into these methods, their cost-augmented variants when tested on MAB-CS instances would in general incur linear regret.

(b) MO-MAB: While the MAB-CS line of work (ours and Sinha et al. 2021) do fall into this category of multiple objective multi-armed bandits, the other methods in this class can be thought of as solving the “Pareto bandits” problem, for example the paper “Pareto Regret Analyses in Multi-objective Multi-armed Bandit” (Xu et al. 2023). These methods work quite generally with multiple objectives by working in the world of “reward vectors”. While useful for many applications, these have no built-in notion of an explicit quality constraint like that imposed by MAB-CS. This unfairly sets them up to incur linear regret on MAB-CS. We discuss a related point in our response W4.

(c) Bandits with costs: We are particularly thinking of the bandits with knapsacks (BwK) line of work (Badanidiyuru et al., 2018). While bandits with knapsacks is similar to MAB-CS in that it assumes there is a known cost of sampling each arm, the critical difference is that BwK imposes strict cost budget constraints, and the objective of the algorithms is to maximize reward subject to these cost constraints. MAB-CS instead imposes constraints under expectation on the apriori unknown rewards. Moreover MAB-CS does not impose and strict budget constraints on cost/quality. So there was no way to augment BwK to work in the MAB-CS without proposing entirely novel algorithms.

Any comparison of the methods categorized (a), (b), and (c) to our PE / PE-CS would have unreasonably favored our approach and hence we decided to not use them as baselines in our simulations.

---