Multi-Armed Bandits with Abstention

We express our gratitude to the reviewer for the favorable assessment of our paper and for providing us with constructive feedback. We would like to respond to the questions in the following.

---

Weakness (Significance):

We do not fully understand concerns raised by the reviewer, and we welcome any additional comments. In particular, we do not fully understand the phrase "no matter the value of $B_t$ does not seem realistic, as it implies that there is some estimation of the reward/regret from pulling a treatment arm". The agent indeed observes the stochastic outcome $X_t$ after selecting an arm $A_t \in [K]$ and the abstention option $B_t\in \\{0,1\\}$. In the example of clinical trials presented in the introduction, if researchers implement costly prearranged measures, the treatment outcomes will not contribute to the optimization objective of the study. However, the researcher can still observe these outcomes, thereby leading to more efficient future experimental designs. If the researcher is unable to observe the outcomes, then conducting medical treatments becomes meaningless. In line with this model assumption, our model well aligns with Neu & Zhivotovskiy (2020), which explored the role of abstention in the context of online prediction with expert advice.

The abstention decision $B_t$ must be made before observing the outcome $X_t$. Consequently in each time step, the agent utilizes estimates of the reward/regret from pulling the chosen arm to make the abstention decision.

Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Conference on Learning Theory, pp. 3030–3048. PMLR, 2020.

---

Question 1 (Experiments):

We extend our sincere appreciation to the reviewer for offering constructive suggestions. In the revised manuscript, we have presented the performance of baselines in Figures 3 and 5, and provided a concise summary of the subsequent explanation. When the abstention reward $c$ is lower than the smallest mean reward in the fixed-reward setting, or the abstention regret $c$ exceeds the largest suboptimality gap in the fixed-regret setting, the agent gains no advantage in choosing the abstention option when selecting any arm. Unfortunately, the agent lacks precise knowledge of the bandit instance, leading to the inevitable selection of the abstention option. This unavoidable choice introduces a subtle gap between the performance of our algorithms and the baselines.

---

Question 2 (Extension beyond Gaussian distributions):

Epsilon(=1/K)-TS is asymptotically and minimax optimal for various popular reward distributions, including Gaussian, Bernoulli, Poisson, and Gamma. The extension beyond Gaussian distributions appears to be straightforward based on our current analysis, although careful consideration is necessary for specific "boundary" cases. For instance, in Bernoulli bandits where the stochastic rewards are bounded in $[0, 1]$, the behavior of minimax regrets might be different from the canonical case of $O(\sqrt{KT})$, when the abstention reward approaches 1 in the fixed-reward setting.

---

Thank you once more for providing us with your valuable feedback. We sincerely hope that our responses effectively address the raised concerns.

Weakness 3 (Selection of the base algorithm):

In the fixed-reward setting, our algorithm FRW-ALGwA can leverage any base algorithm that is asymptotically and minimax optimal for canonical multi-armed bandits as its input. In Appendix A, we provide comprehensive definitions of asymptotic and minimax optimality within the canonical model. Eligible candidate base algorithms include both Thompson Sampling-based and UCB-based approaches. Due to space limitations, we defer all experimental results pertaining to the fixed-reward setting to Appendix E. In this appendix, we examine the empirical performances of two particular realizations of our algorithm: FRW-TSwA and FRW-UCBwA. The former uses Less-Exploring Thompson Sampling (Jin et al., 2023) as its base algorithm, while the latter employs KL-UCB++ (Menard & Garivier, 2017). Notably, while both FRW-TSwA and FRW-UCBwA represent implementations of our general algorithm and share identical theoretical guarantees, FRW-TSwA demonstrates superior empirical performance, as illustrated in Figures 4 and 5.

In the fixed-regret setting, the sampling rule of our algorithm FRG-TSwA is built upon Less-Exploring Thompson Sampling. The fixed-reward setting is inherently more complex than its fixed-regret counterpart because, in the latter setting, we need to dynamically estimate the suboptimality gaps and quantify the regret that results from inaccurately estimating the gaps. These complexities necessitate a more meticulous exploration into the arm sampling dynamics, and preclude us from formulating a generalized strategy. To achieve both forms of optimality, we suspect that the sampling rule should be anytime (i.e., not dependent on the time horizon $T$), a criterion not met by current UCB-based approaches. Nevertheless, we do believe it is possible to design a UCB-based algorithm for our abstention model. Finally, regarding the empirical performance, our focus lies on algorithms with solid theoretical guarantees.

Pierre Menard and Aurelien Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pp. 223–237. PMLR, 2017.

---

Thanks again for your valuable review. Hope these replies resolve your concerns, and any further comments are welcome!

We express our gratitude to the reviewer for providing insightful comments and valuable suggestions on our paper. In response, we have conscientiously attended to all the raised concerns.

---

Weakness 1 (Theoretical contribution):

Regarding the theoretical contribution of our paper, while we submit that the individual ingredients that constitute the algorithms and their analysis are not groundbreaking in the bandit literature, the adaptation to being amenable to incorporating the abstention option (which is a novel setting in the bandit literature) and retaining the asymptotic and minimax optimality of the resultant algorithms is far from straightforward, as acknowledged by both Reviewers n2KC and ahVb.

Turning to the significance of our work, our findings offer valuable quantitative insights into the advantages of the abstention option, thereby laying the groundwork for further exploration in other online decision-making problems with such an option. This positive aspect is also recognized by all three other reviewers. Specifically, we have extensively discussed the rationale and insights behind the asymptotic and minimax regret within the main text, offering potential inspiration for addressing analogous challenges in other online learning problems involving abstention.

Due to the density in exposition and comprehensiveness of our results, we struggled with space limitations, which prevent us from incorporating proof sketches in the main text. Nevertheless, we are confident that the proofs presented in the appendix are lucid and easily understandable. For the more intricate fixed-regret setting, we delve into the theoretical challenges associated with designing and analyzing the algorithm in Remark 2, which are decidedly non-trivial and demands meticulous effort.

---

Weakness 2 (Motivation):

In the example of clinical trials presented in the introduction, if researchers incorporate costly prearranged measures such as insurance packages, the stochastic treatment outcomes, whether favorable or unfavorable, will not contribute to the optimization objective of the study. Nevertheless, these outcomes remain observable to the researcher and can be utilized to make more effective future experimental designs. If the researcher is unable to observe the outcomes, then conducting medical treatments becomes meaningless.

We do not fully comprehend the meaning of "avoiding catastrophic outcomes", and would appreciate it if the reviewer could provide further comments so that our response is better tailored to the reviewer. In our model, the abstention option is indeed present to mitigate catastrophic outcomes, as the algorithm(s) can utilize the abstention option if it finds that the reward accrued from the chosen arm at a particular time is unacceptably low. Furthermore, the decision to abstain does not influence the stochastic outcome from the selected arm. Its impact is confined to the instantaneous regret at a specific time step, which is modeled as either fixed regrets or fixed rewards. In both the fixed-regret and fixed-reward settings, the instantaneous regret does not depend on the random outcome when the agent chooses to abstain. Exploring a more sophisticated approach to model the cost associated with the abstention option will be an intriguing avenue for future research.

---

Dear Reviewer 4Y9t,

We hope this message finds you well. As the rebuttal period draws to a close on November 22nd, just four days away, we would like to reach out to you and inquire if you have any additional suggestions regarding our paper. We would be immensely grateful if you could kindly review our responses to your comments. This would allow us to address any further questions or concerns you may have before the rebuttal period concludes.

We sincerely appreciate the time and effort you have put into reviewing our work and providing valuable feedback. Thank you for your contributions towards improving the quality of our research.

Best regards,

Authors of Submission2358

We thank the reviewer for the positive feedback, valuable comments, and suggestions on our paper. Please find below our response to the raised concerns.

---

Weakness 1 (Insufficient numerical experiments):

Our paper is primarily positioned as a theoretical work, with numerical experiments serving to validate our theoretical findings. The selection of instances $\mu^{\dagger}$ and $\mu^{\ddagger}$ was not deliberate. In Appendix E.2 of the revised manuscript, we have heeded the reviewer's advice and incorporated additional numerical experiments, using random instances with large numbers of arms. The construction of these random instances follows the method in Jin et al. (2023). Due to time constraints and for the sake of simplicity in presentation, we focus on the fixed-regret setting. It can be seen that the results in Figures 6 and 7 closely resemble those in Figures 2 and 3.

---

Weaknesses 2 and 3:

Thank you for bringing the typo and the presentation issue to our attention. In the revision, we have corrected the typo and explicitly clarified that $\beta(b, \mu, K)$ is defined in Lemma 5.

---

Weakness 4 (Proof Sketch of Lemma 5):

Thank you for the constructive suggestion. In response, we have incorporated a proof sketch for Lemma 5 in the revised version. It is highlighted in red within the appendix, focusing on the core ideas.

We thank the reviewer for the insightful comments and suggestions on our paper. We have carefully addressed your concerns in the following.

---

Weakness (The abstention model):

We consider the assumption that the agent can observe the sample regardless of the abstention decision to be rather natural to our problem setting of bandits with abstentions and in particular to the clinical trials example presented in the introduction. In the example of clinical trials, if researchers implement costly prearranged measures, the treatment outcomes will not contribute to the optimization objective of the study. However, the researcher can still observe these outcomes, thereby leading to more efficient future experimental designs. Furthermore, conducting medical treatments becomes meaningless if the researcher is unable to observe the outcomes. In line with this model assumption, our model well aligns with that of Neu & Zhivotovskiy (2020), which explored the role of abstention in the context of online prediction with expert advice.

Regarding the learnability of the abstention bandit model, if the agent cannot observe the sample from the chosen arm when opting for abstention, then it is equivalent to skipping the time step, rendering the model trivial. In other words, the learner gains no information from the time step but incurs an instantaneous regret. Finally, we would like to remark that the above statement holds true only for the stochastic bandit model. The dynamics change in non-stationary or adversarial bandits, providing intriguing avenues for future research.

Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Conference on Learning Theory, pp. 3030–3048. PMLR, 2020.

---

Small Issue 1 (Longer proof sketches):

We sincerely thank you for your valuable suggestion and understanding. Due to the density of our results, we, as with many other authors, struggled with space limitations, which prohibits us from incorporating comprehensive proof sketches in the main text. Our paper is positioned as a theoretical work, with numerical experiments serving to validate our theoretical findings. Opinions on the inclusion of experiments in the main text vary, and one reviewer suggests more numerical experiments. In light of this, we have chosen not to relocate all experiments to the appendix. According to the ICLR guidelines, the page limit for the main text is strict, and no additional pages can be added in the final version. Consequently, we are unable to include longer proof sketches in the main body. However, we are confident that the proofs presented in the appendix are lucid and easily understandable.

---

Small Issue 2 (Order of the presentation):

We express our gratitude to the reviewer for providing the constructive suggestion. While preparing the manuscript, we ensured clarity by presenting comprehensive explanations in the first setting and avoiding unnecessary repetitions in the second setting. In particular, in the corresponding proofs, we typically streamlined the common components. Although we appreciate the reviewer's kind suggestion, when preparing the initial manuscript, we have thought through whether to present the fixed-regret or fixed-reward settings first, aiming to ensure that the overall paper is as concise as possible.

---

Question 2 (Regret bound for the new model):

This point pertains to the point of weakness above. In the context of stochastic multi-armed bandits, if the agent cannot observe the sample from the chosen arm when opting for abstention, then no information is gained during that time step, rendering it equivalent to skipping the time step altogether. Consequently, the abstention option becomes a means to shorten the time horizon with costs. Regarding the cumulative regret bound during time steps when the agent chooses not to abstain, it is the same as that of the canonical bandit model. Hence, there is nothing to analyze in this setting.

---

Question 3 (Regret bound of Algorithm 2):

Thank you for the question. Since the base algorithm is asymptotically optimal (see Appendix A for relevant definitions), our model that possesses the abstention option and leverages the base algorithm, inherits the asymptotic optimality of the base algorithm. Hence, our regret bound is indeed a function of that of the base algorithm but in a rather unusual way; both of them are asymptotically optimal. Concerning the minimax upper bound, we indeed possess a result of that type, specifically expressed as a function of the minimax upper bound of the base algorithm. For further details, please refer to the concluding lines of the proof of Theorem 3 in Appendix D.1.

Dear Reviewer n2KC,

We hope this message finds you well. As the rebuttal period draws to a close on November 22nd, just four days away, we would like to reach out to you and inquire if you have any additional suggestions regarding our paper. We would be immensely grateful if you could kindly review our responses to your comments. This would allow us to address any further questions or concerns you may have before the rebuttal period concludes.

We sincerely appreciate the time and effort you have put into reviewing our work and providing valuable feedback. Thank you for your contributions towards improving the quality of our research.

Best regards,

Authors of Submission2358