Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers joint human-algorithm system in multi-armed bandits. The authors explore multiple possible frameworks for human objectives and provide theoretical regret bounds. They also give experimental results which show how regret varies with the human decision-maker’s objective and the number of arms.
strength_and_weaknesses: Strengths:

1. The considered joint human-algorithm system in multi-armed bandits is very interesting and well-motivated.

Weaknesses:

1. While the considered joint human-algorithm system in multi-armed bandits is a very interesting and well-motivated problem, the formulation for this human-algorithm system in this paper is too simple. Specifically, the formulation just considers a simple combination of selecting the empirical best arm and selecting the optimistic best arm (according to the classic UCB algorithm). Under this simple formulation, the joint human-algorithm system does not bring too many challenges to the original multi-armed bandit problem. 

2. The theoretical analysis and results in this paper are similar to those in the classic multi-armed bandit works, e.g., the upper confidence bound-based analysis and the empirical myopic analysis. It is unclear to me what unique challenges the joint human-algorithm system impose on the theoretical analysis in this paper.

3. The writing of this paper seems causal. There are several blanks and typos.

clarity,_quality,_novelty_and_reproducibility: The considered joint human-algorithm system in multi-armed bandits is a very interesting and novel problem. But the theoretical analysis and techniques in this paper are similar to those in classic bandit works. The authors present experimental results, and do not provide the code.
summary_of_the_review: This paper considers a very interesting and well-motivated problem, i.e., a joint human-algorithm system in multi-armed bandits. But the formulation considered in this paper is too simple, which makes the theoretical analysis in this paper too standard (very similar to classic UCB analysis). The unique challenge of joint human-algorithm system is not well captured and analyzed in this paper. The writing of this paper looks causal, and needs to be improved. For these reasons, I give rejection.

=========

Thank the authors for their response. I think this problem is well-motivated and worth a deeper analysis. The current formulation and analysis is too simple to fully capture the interesting insights and unique challenges of human-algorithm decision making. I think this work can be significantly improved by using theoretically deeper formulation and analysis. Therefore, I keep my score.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper considers the problem of reward maximization in human-algorithm coorperation situation. The paper provides a policy and theoretical analysis. Then the paper shows some experiment results.
strength_and_weaknesses: Strength:
* The problem of human-algorithm coorperation is interesting. The authors provide sufficient literature on such problem.

Weaknesses:
* The problem formulation is quite standard, which provides narrow space to make contributions.
* Section~3.2 only introduces the part of a policy for "human", and I don't see the other part for "algorithm" (or assumptions on how the "algorithm" will behave). So I don't understand what the theoretical analysis and the regret results are for.
clarity,_quality,_novelty_and_reproducibility: Both the writing and the content of this paper is questionable.
summary_of_the_review: This paper is not ready to be published.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper is about a model of sequential decision-making in which the algorithm is only allowed to select a subset of the possible options, and a human user is then required to choose one among them. The authors analysed theoretically the case in which both the agents (algorithm and human) are both relying on a Hoeffding-like bound to select the options. Finally, they present some synthetically generated experiments to evaluate the performance of the UCB-like algorithm when different numbers of arms are shown to the user.
strength_and_weaknesses: I think that the motivating example provides an interesting setting in which the research is still somehow missing a deeper analysis. However, the arguments and analysis of the authors do not seem to be complete enough yet for publication at ICLR. In my opinion, the author should focus more on the setting, for instance analysing the lower bound on the regret before proposing algorithms.

Moreover, I think that the regret defined by the authors does not reflect the fact that the user might have different goals. I think that the modeling in this aspect may be revised and improved.

Finally, the experimental results are not convincing at all. Indeed, they are on a too narrow set of settings, and statistical significance is not provided in most of the cases.

Lemma 1: Increasing in K is a bit generic. What is the dependence on this parameter?



Minor:
Remove all the contractions like isn't and doesn't

I think that in the literature review, you should also mention and discuss the corrupted bandit setting. For instance,

Gajane, Pratik, Tanguy Urvoy, and Emilie Kaufmann. "Corrupt bandits." EWRL (2016).

Zhao, Heyang, Dongruo Zhou, and Quanquan Gu. "Linear contextual bandits with adversarial corruptions." arXiv preprint arXiv:2110.12615 (2021).

and literature therein cited.

Define a symbol for regret.

Please provide the comments on Theorem 1 after it has been stated.

Theorem 1: It is not clear to me where did you use the fact that \alpha_h > 1 and \alpha_a > 1

Theorem 2: Does this regret match the theoretical lower bound? Is it possible to show that this is the best one might do in this setting?

Assuming the shaded areas are the confidence intervals for the analysed mean regret (it is not clearly stated in the text), I think that the results provided are not statistically significant.
clarity,_quality,_novelty_and_reproducibility: The paper is clear, and the novelty in terms of the setting is evident.
The authors did not provide the code for the experiments, even if they are described in detail.
summary_of_the_review: The paper presents a novel setting, but the authors did not succeed in providing a deep analysis of it.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers a human-algorithm collaborative framework in bandit problems. In this framework, the algorithm will first pick several candidate arms based on its picking rule, and then the human will choose one arm in this candidates to pull, based on his/her choosing rule. In this paper, the authors mainly consider the case that both the human and the algorithm are running UCB-type algorithms, i.e., their decisions are made based on the upper confidence bounds of all the arms (with different parameter $\alpha_h$ and $\alpha_a$). In this case, they show that when both $\alpha_a$ and $\alpha_h$ are large enough (e.g., larger than 1), then the regret of the system is at most the same as the worse one (either the human or the algorithm). On the other hand, if $\alpha_h = 0$ (i.e., the human is totally greedy), then the regret of this system is linear with $T$, as long as the algorithm must provide at least 2 candidate arms to the human. Finally, the authors use some experimental results to demonstrate their theoretical findings. 
strength_and_weaknesses: Strength

1. The human-algorithm collaborative framework plays an important role in machine learning researches.

Weakness

1. The algorithm seems to be useless in the system.

When $\alpha_h = 0$, it is showed that the regret is linear with $T$, even if there is an algorithm that controls the candidate arms. Though this regret can be better than the only-human case, we do not want to regard it as an efficient framework.

When $\alpha_h \ge 1$, according to Theorem 1, the algorithm can only make the regret upper bound worse (or at least the improvement is limited).

Then my question is, why we must use such a human-algorithm collaborative framework is these examples? Why not get rid of the algorithm and only let the human make decisions?

2. The theoretical contribution of this paper is limited.

The theorems and lemmas in this paper seem trivial. I read the full proofs, but I do not see any new techniques or novel insights within them. They are just tranditional UCB-based analysis and there seem to be no technical challenges.


clarity,_quality,_novelty_and_reproducibility: Some concerns about the proof of Theorem 2.

What do you mean by the last inequality in Page 6? I can understand that when the first pull of arm 0 is less than that threshold, then the regret can be linear with $T$. But what if the first pull of arm 0 is larger than that threshold, while the second pull of arm 0 is bad enough so that the empirical mean is then smaller than that threshold?

I think you may need to define $p_{i,\epsilon}$ as the probability of "the empirical mean of arm 0 is less than that threshold in some time step".
summary_of_the_review: Overall, I do not think the contribution of this paper is enough for an ICLR submission.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces a hybrid human-ML algorithm for the classic multi-armed bandit problem. 

All reviewers felt that this general idea was novel and interesting, however the specific model was much too simple to be of theoretical or practical interest.
justification_for_why_not_higher_score: All reviewers agree that the actual model in this paper is trivial and uninteresting, though the overall direction could be interesting.
Decision: Reject