Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy
Bandits;Multi-Armed Bandits;Online Learning;Cost-Subsidy;Cost Subsidy;Improved UCB;UCB;Elimination Algorithms
Yes
No ethics review needed.
* 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.
* 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.
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).
* 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.
Yes
No ethics review needed.
1. See the weakness.
2. Is it possible to provide some lower bounds for this problem?
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.
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.
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.
Yes
No ethics review needed.
### 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?
1. New theoretical results. This paper proposes the first algorithm with instance-dependent logarithmic regret/cost guarantees for the MAB-CS model.
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.
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.
Novel algorithm for the Multi-Armed Bandits with Cost Subsidy framework with logarithmic problem instance dependent upper bound
@inproceedings{
anonymous2024pairwise,
title={Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=eB7T1bqthA},
note={under review}
}
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. 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 there is an inability to explicitly determine the trade-off between these metrics. In our work, we first introduce the Pairwise-Elimination algorithm for a simplified variant of the cost subsidy problem with a known reference arm. We then generalize PE to PE-CS to solve the MAB-CS problem in the setting where the reference arm is the un-identified optimal arm. Next, we analyze the performance of both PE and PE-CS on the dual metrics of Cost and Quality Regret. 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 policy the first with such a guarantee. Finally, experiments are conducted using the MovieLens 25M dataset for both PE and PE-CS and using a synthetic toy experiment for PE-CS revealing that our method invariably outperforms the ETC-CS baseline from the literature.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Bandits Multi-Armed Bandits Online Learning Cost-Subsidy Cost Subsidy Improved UCB UCB Elimination Algorithms
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/1ab0007eca526e1ca899a92f79a878d39e63f4e7.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission