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

Authors: Ishank Juneja, Carlee Joe-Wong, Osman Yagan
Primary area: reinforcement learning
Keywords: Bandits, Multi-Armed Bandits, Online Learning, Cost-Subsidy, Cost Subsidy, Improved UCB, UCB, Elimination Algorithms

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1730149556934

thread_type:
official_review

<thread_object>
creator: reviewer_cglm

<content>
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.

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).
2. 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.

questions:
### Minor Comments

- 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.
- In Line 321, the `omega` should be $\omega$.
- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730447117027

thread_type:
official_review

<thread_object>
creator: reviewer_mwch

<content>
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.

strengths:
1. The problem is well-motivated. The authors provide interesting examples of applications of the MAB-CS framework.
2. The paper is well-written.
3. 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.
4. 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.

questions:
1. See the weakness.
2. Is it possible to provide some lower bounds for this problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730650232054

thread_type:
official_review

<thread_object>
creator: reviewer_fmrh

<content>
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:

1. Known threshold where there is a fixed reward threshold that should be met in expectation.

2. A reference threshold to an (initially) unknown arm that should be met in expectation.

For 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.

They 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.

They 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).

strengths:
* They consider new settings which seem reasonable to study.

* They propose new algorithms.

* They show bounds on the performance of their algorithms.

* 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.

* The statement of the bounds is difficult to parse (classic ML with too many terms which are hard to interpret).

* 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".

* 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.

questions:
* What tools do you use in the analysis of your algorithms? What is the general strategy?

* How do you re-use samples for downstream comparisons in your algorithms?

* 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?

With 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732081924580

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Update 1: Lower bounds for MAB-CS problem

comment:
As our first update in response to the limitations and criticisms stated by reviewers fMRh, MwCh, and CGLm (particularly the latter two among our three reviewers) we would like to share a new section from the revised Appendix of the paper working out instance-dependent lower bounds on the number of samples of sub-optimal arms (arms other than the best action $a^*$). 

These bounds are available in a PDF as the sole supplementary materials file. This update is not yet reflected in the paper PDF which remains the pre-rebuttal version.

We would like to add that the proved lower bounds on samples match the upper bounds for our PE (up to a constant factor) in the known reference arm $\ell$ setting. For the full cost subsidy case, our PE-CS still matches the lower bounds (up to a constant factor) for arms cheaper than the optimal action (a.k.a best action $a^*$) and in some cases (which have been worked out explicitly) for the arm $i^*$. 
However for arms $i > a^*$ and different from $i^*$ (i.e. that is the so-called high cost arms) there seems to be a room for improvement in PE-CS which we have tabled as future work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732973287131

thread_type:
official_review

<thread_object>
creator: reviewer_wsgz

<content>
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.



=========

After rebuttal: score increased to 6.

strengths:
1. The paper is overall easy to follow.
1. The paper reviewed the various related works.
1. 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.
1. 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?
1. 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?
1. As there are already a number of similar models, what is the motivation to consider this model?

Minor comment:
1. Line 168: Should there be '' We build up our approach to optimize sth. for the regret objectives ..."?

questions:
Please see the *Weaknesses* section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733279336937

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Author’s post reviews summary

comment:
### Author’s post reviews summary

---

This paper takes on a MAB framework with important applications and introduces two novel extensions to it. We propose algorithms for each of the three formulations with regret upper and lower bounds. Novel technical contributions include the first instance-dependent regret lower bounds for the original CS formulation, order-optimal algorithm for known reference arm case, and an algorithm for the original CS setting with a logarithmic instance dependent regret upper bound. Our algorithm outperforms baselines from the literature either outright (in case of ETC-CS) or when performance and reliability are both taken into account (in case of UCB-CS, TS-CS).

We are glad that we were able to satisfactorily address the concerns of all reviewers, two of which increased their scores from their initial assessments. Importantly our work showed that our algorithm PE was order-optimal on cost and quality regret for the known reference arm setting. Moreover PE-CS, the generalization of PE that leverages a best-arm-identification stage, was shown to be order-optimal on the expected number of samples of a certain subset of arms. Future work inspired by our paper would develop elimination based regret minimization algorithms that close the order-gap for the remaining arms.

---
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper explores the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework, a problem of practical importance where decisions minimize costs under reward constraints. The authors propose two algorithms: Pairwise Elimination (PE) for cases with a known reference arm and its extension, PE-CS, for settings where the optimal reference arm is unknown. They provide instance-dependent guarantees on cost and quality regret, achieving logarithmic bounds. Experiments on real-world datasets like MovieLens demonstrate the algorithms' effectiveness.

The authors addressed critical reviewer concerns during the rebuttal. They provided instance-dependent lower bounds for both the known reference arm and general MAB-CS settings, strengthening the theoretical foundation. They revised the presentation to clarify notations, objectives, and experimental setup. New experiments were conducted, exploring variations in parameters across multiple datasets, including a newly added Goodreads dataset. These enhancements addressed criticisms about limited experimentation and strengthened confidence in the algorithms' robustness and generalizability.

The detailed responses effectively addressed the reviewers' comments, leading to raised scores. Considering the above novelties, I recommend acceptance of the paper once the authors incorporate all the reviewer's feedback in the final version.