Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization

Summary

The paper proposes a novel contextual bandit algorithm that balances cumulative and simple regret guarantees using a surrogate objective and optimal cover. By constructing the conformal arms sets (CASs) which improve the coverage guarantees for the optimal policy, the algorithm efficiently finds the policy that minimizes simple regret while balancing with the cumulative regret. Cumulative and simple regret upper bounds are considered in the case when the model can be misspecified and the hardness result shows that the trade-off between simple and cumulative regret is unavoidable.

Strengths

The paper provides a theoretical analysis of the balance and trade-off between cumulative and simple regrets, which are not considered in the previous literature. The definition of cover and conformal arm sets is new and paves the way to characterize simple regret minimization. Generalizing regret bounds to the case when the model can be misspecified extends the currently existing literature.

Weaknesses

W1. More discussions on theoretical results are required. Specifically, (a) the role of the action selection kernel q in Assumption 2, (b) what happens when $\min_{(x,a)\in\mathcal{X}\times\mathcal{A}} p(a|x)=0$in Assumption 2 (line 180), (c) how the bias $B$ is multiplied to $\sqrt{1/T}$ term rather than $O(1)$, (d) examples of the setting that satisfies the assumptions in Theorem 3. W2. The experiment section does not include the balance of cumulative regret and simple regret, which is the key part of the paper. More diverse settings are required to evaluate the algorithm.

Questions

Q1. My main concern is in Theorem 3. The assumption in Theorem 3 implies a positive gap between the optimal and the second-best arm (e.g., Section 5.2 in [1] ) which enables the algorithm to attain zero simple regrets after $O(\log T)$ exploration rounds and thus logarithmic cumulative regret bound. Does this result contradict Theorem 3? Q2. I couldn't understand the sentence "it (the algorithm) does not utilize the structure of the policy class being explored" in line 349. Could you elaborate more on this? Q3. In line 109, the integral in $f(x,S)=\int_{a} f(x,a) d\mu(a) / \mu(S)$ ranges over $S$? Should it be $f(x,S)=\int_{S} f(x,a) d\mu(a) / \mu(S)$? [1] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. "Improved algorithms for linear stochastic bandits." Advances in neural information processing systems 24 (2011).

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Yes. This work is mostly theoretical and the negative societal impact of the work is unseen.

Summary

This paper studies contextual bandits and develops a flexible algorithm that can be adapted to both cumulative regret minimization and simple regret minimization. New techniques are developed to analyze the proposed algorithm, e.g., constructing the conformal arm sets. The authors also prove a negative result stating that one cannot simultaneously achieve optimal simple regret and cumulative regret.

Strengths

This paper proposes a novel algorithm called RAPR, which utilizes two computational subroutines, an estimation subroutione and an evaluation subroutine. The RAPR algorithm takes a hyperparameter as input, which can be tuned to adapt to either cumulative regret minimization or simple regret minimization. This result seems quite interesting to me. The authors also complement the theoretical upper bound with a lower bound stating that one cannot simultaneously achieve optimal cumulative regret bound and simple regret bound.

Weaknesses

I have questions regarding some wording used in the paper. More specifically: 1. The paper claims that they develop a new computationally efficient algorithm. However, it seems that the proposed algorithm is not entirely efficient under model misspecification since a cost-sensitive classification (CSC) subroutine is used in this case. It is known that CSC oracle can be NP-hard to implement even in simple cases. 2. The paper claims instance-dependent guarantees for simple regret minimization. However, it seems that the guarantees stated in Theorem 2 have a worst-case flavor, compared to instance-dependent results stated in Li et al, 2022.

Questions

See the weaknesses part.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

As stated on Page 9.

Summary

This paper focus on the continues objective between simple regret minmization (SRM) and cumulative regret minimization (CRM) in contextual bandits, and propose an algorithm that can be either optimal in SRM, or optimal in CRM. Meanwhile, a new uncertainty quantification is propsed. Numerical simulations validate the efficacy.

Strengths

- Novelty: the paper focus on the objective between best arm identification (BAI) and regret minimization (RM), which is rarely studied but of great practical significance, as most works focus on either RM or BAI. - Technical contribution: the conformal arm set as a new type of confidence bound is new, and is of independent interests beyond the topic. - The results are strong, as a single algorithm can optimally change from one objective to another is not easy. It's also valuable for multi-objective related topics.

Weaknesses

- The geometic covering in the algorithm (doubling the epochs) is common in RM, however, when it comes to simple regret minimization, there might be the case that only limited round $T$ is given, and thus requires an any-time algorithm. - $\beta_{max}$ as the threshold of $\beta$ constrains that $\beta$ can not be too big, and restrains the smallest possible CAS. I'm confused with the counter-intuitive parameter, as for the objective of BAI, CAS should be as small as possible eventually. Why do we need the trucation threshold and why it's selected as $1/4$ should be explained. - Though it is mentioned that the optimal cover can be seen as the surrogate objective for BAI, it is mainly used to estimate arbitrary policy $\pi$, while how it can be optimized to achieve a better $\pi$ is not clear.

Questions

See weaknesses above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

\

Summary

This paper provides a computational efficient algorithm for contextual bandit that is capable of trading off between near-optimal minimax cumulative regret guarantees and instance-dependent simple regret guarantees. Additionally, It handles model misspecification, works in the continuous arm setting, and provides a lower bound that shows there is always a trade off in achieving simple regret and the cumulative regret.

Strengths

- A significant contribution in achieving a trade-off between simple regret and cumulative regret. - One advantage of the algorithm is that it is regression based which makes it computationally efficient, while it does not rely on the realizability assumption, as it can adapt to model misspecification.

Weaknesses

The weaknesses mainly lie in the paper's poor writing and presentation, as well as in the insufficiently conducted simulations, detailed as bellow. - The motivation in the introduction lacks conviction and the main story is postponed to the related work section. - The introduction lacks a clear image of the achieved bounds and the bounds of related works, which could have been presented together in a single table along with all limitations. - in Section Preliminaries, the notations are listed in the footnote, which make it difficult for readers to follow the setup. In general, the flow in this section is confusing and needs improvement. Moreover, the authors used $\Pi$ and $\mathcal{F}$ in the "objectives" subsection without defining them before in the problem setup. Also definition of "CB algorithm" is missing. - Lack of clarity regarding the specific location in the appendix for referenced proofs and details. - Algorithm section is tedious with numerous links to various definitions, making it challenging to follow the flow. Besides that, the provided intuition is not sufficient for a non-expert reader to understand the complex formulas used for variables such as $\lambda$, $\eta$, and $\alpha$. This can hinder comprehension for readers. Moreover, line 15 of algorithm $\omega$-RAPR seems to be incorrect. - There are many arXiv papers listed in the references, whereas for most of them there are already the published version in some journal or conference. - The simulation part is extremely brief and lacks comparison to existing baselines, as well as an illustration of the results. I believe the paper requires a major revision due to various identified weaknesses.

Questions

- I request the authors to elaborate further on the optimality of the achieved trade-off between simple regret and cumulative regret. Additionally, I am curious to understand how the provided lower bound sheds light on this trade-off and its implications in the context of the paper's contributions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

N/A

After rebuttal

I thank the authors for their response. I suggest the authors add these related discussion into the main paper during revision. I'd like to keep my score and lean towards accepting the paper.