Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the stochastic multi-armed bandit problem (K-armed as well as the linear version) under "reproducibility constraints," i.e., the policy should play the same sequence of arms in any two i.i.d. instances of the problem (using the same algorithmic random seed) with probability at least $1-\rho$. The authors propose $\rho$-reproducible policies with rate-optimal regret (w.r.t. $T$). 
strength_and_weaknesses: The paper is technically sound. It is insightful to see that while standard bandit algorithms are not reproducible in general, one can with only a slight multiplicative increase in sample complexity ensure reproducibility.
clarity,_quality,_novelty_and_reproducibility: It certainly is an interesting problem to study from a mathematical perspective; the authors point to antecedents in the literature that underscore the importance of reproducibility. The main technical contribution (in my opinion) is showing that one can get rate-optimality of regret w.r.t. $T$ while guaranteeing reproducibility simultaneously. The paper is well written and appears comprehensive in fleshing out connections to extant literature.

Question: Is the $1/\rho^2$-scaling of the upper bounds best possible w.r.t. $\rho$? Can you please elaborate on this in the paper?
summary_of_the_review: Based on my assessment of this paper's contributions, I vote for an acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The purpose of this paper is to investigate reproducible bandit algorithms while keeping a reasonable regret guarantee. The paper starts with a notion of reproducibility for a bandit algorithm following the definition of Impagliazzo et al. (2022). It states that a bandit algorithm is reproducible if two different executions of the algorithm would lead to the same sequence of played arms with high probability.

The authors first studied the problem for standard stochastic bandits in Section 3 and proposed a first version of algorithm based on reproducible mean estimation (Impagliazzo et al., 2022) and a batched bandits algorithm (Esfandiari et al., 2021) (using traditional optimal algorithms like UCB is unlikely to be feasible under current definition). This first version incurs an extra factor of $O(K^2\log^2(T)/\rho^2)$ compared to its non-reproducible counterpart. The authors then managed to get rid of a $\log^2(T)$ factor in Section 4, which reduces the extra factor to $O(K^2/\rho^2)$.

The authors also managed to propose an algorithm with the same extra $O(K^2/\rho^2)$ factor for linear bandits (finitely-armed) proposed in Section 5.1. A study in the infinitely-armed case is also provided (with an extra $d^2$ factor against its non-reproducible counterpart).
strength_and_weaknesses: Strength:
- The topic is novel and could have an impact on the community.
- A first definition of reproducible bandit algorithms is provided and is supported by some non-trivial algorithms.
- A very clear thinking process on how the algorithms (and improvements) are proposed.
- Correct theoretical contributions: regret bounds provided are non-trivial.

Weakness:
- One of my major concerns is that the paper didn't provide any experimental illustration while the paper is talking about reproducibility. I do understand that the authors want to provide a fundamental study of the problem, but reproducibility itself is a very practical-oriented notion for which lack of experiments seems not quite reasonable to me.
- Another related point, not necessarily a weak point but rather something arguable, is the extra dependence of $K$ in the regret bound compared to non-reproducible algorithms. It seems that the extra $K^2/\rho^2$ factor is rather difficult to be get rid of under current context. This could particularly cause problems when we have a large arm space in practice. And somehow, reproducibility makes more sense in a large scale environment. This is a question rather about the validity of the definition itself in my opinion: does it really make sense in practice? I think the authors could probably provide more discussion on that rather than (alongside some experiments ideally) stacking theoretical results for different problem settings one by one. 
clarity,_quality,_novelty_and_reproducibility: Clarity and quality: The paper is well written. In particular, I appreciate a lot the warm-up part in Section 2, which provided a more comprehensible view of the problem to readers.

Novelty: The topic is new and important. The algorithms inspired a lot from Esfandiari et al. (2021) which reduces a bit the novelty, but it's ok.

Reproducibility: The reproducibility aspect is not really applicable here since the paper seems to be pure theoretical, which is somehow disappointing since the paper itself is discussing about reproducibility.
summary_of_the_review: In summary, I appreciate the authors' effort and I think the topic of reproducibility is important to the community. The algorithms and regret bounds provided are rather solid under the current definition of reproducibility. But I do have some doubt on whether the definition really makes sense given the dependence of $K$ in the proposed algorithms and the lack of experimental illustration.

Misc:
- Section 1, Paragraph 1: "due to the to the" -> "due to the"

__________________________________________________________________

After rebuttal, paper solid in theoretical aspects. Some experimental illustration added, which is appreciated, though still moderate for a paper on reproducibility. I decide to increase my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The submission studies the intersection of reproducibility and bandits. The submission proposes and analyses four algorithms for the stochastic MABs and stochastic linear bandits, with optimal dependency on the reproducibility parameter. The submission reveals a valuable insight between reproducible interpretability and exploration-exploitation tradeoff.
strength_and_weaknesses: - (a) Introducing reproducibility to bandits provides a new perspective to contemplate the bandit problem.
- (b) The submission presents its algorithms step-by-step, providing a clear picture of which parts are the novelties and how a novel design is combined with existing techniques to achieve the desired regret bound. The critical components of leveraging batch bandits, uniformly sampled thresholds (step 13 of Algorithm2 and step 13 of Algorithm 3), G-optimal design, LSE, and ReproducibleLSE become intuitive and easy to follow.
- (c) The submission clearly explains the challenges and the intuitions of algorithm design. Regarding similar approaches, the submission carefully compares differences between the proposed method and published ones.
- (d) The regret bounds offer insights and the impact of reproducible learning. The submission explains how to spend additional rounds to guarantee reproducibility and the extra factors compared to the conventional bounds.

Given the above, the results and contribution of this submission are substantial. The proofs are rigorous.

- (e) The minor question is, in step 9 of Algorithm 1, is a "min" missing in the assignment of \tau?
clarity,_quality,_novelty_and_reproducibility: The paper is well-written. The novelties provide a new perspective and algorithms for studying bandit problems.
summary_of_the_review: Reproducibility is becoming crucial in comparing, interpreting, and understanding different methods. Introducing reproducible bandit algorithms gives us a perspective to make better sense of bandits. The reproducible bandit algorithms also link themself to the field of reproducible learning. Given these merits and the strengths listed above, I would like to recommend an acceptance of the submission.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper designs reproducible policies for classic multi-armed bandit model and linear bandit model. In the classic multi-armed bandit setting, the authors first design an algorithm that directly applies existing reproducible algorithms for estimating the means of random distributions, and propose an regret upper bound that is  $O({K^2\log^2 T \over \rho^2})$ larger than non-reproducible algorithms. Here $K$ is the number of arms, $T$ is the time horizon, and $\rho$ is the reproducible rate (i.e., with probability at least $1-\rho$, the algorithm will output the same sequence). Then they improve their algorithm by some specific properties of bandits setting, and reduce the $O(\log^2 T)$ factor in the regret upper bound. As for the linear bandit case, the authors first consider the finite arm set case, and propose an algorithm that achieves regret upper bound of $\tilde{O}({K^2 \over \rho^2}\sqrt{dT})$, which is also $\tilde{O}({K^2 \over \rho^2})$ higher than existing non-reproducible algorithms. When the arm set is infinite, the authors also provide a reproducible algorithm that achieves $\tilde{O}({d^3 \over \rho^2})$ higher regret than non-reproducible ones. 
strength_and_weaknesses: Strength

1. Applying reproducity to bandits problems in an interesting and novel idea.

2. I check some of the proofs in appendix, and they seem to be correct. 

Weaknesses

1. About the motivation.

Though the reproducity of scientific findings are very important, I do not really understand why we need to design reproducible algorithms for bandit problems. Maybe one can claim that we can reproduce others' experimental results easily when the designed algorithms are reproducible, but in this case, I think i) the definition of reproducible (Definition 1) is too strict; and ii) the cost is too large. And  I guess that ii) maybe a consequence of i). In fact, to reproduce others' experimental results, we do not really need the sequence to be exact the same.

2. About the regret upper bounds.

The regret upper bound seems to be not very tight. For example, when we choose $\rho \to 1$, the algorithms does not have any reproducible properties, but we still suffer an extra $K^2$ factor in the regret upper bound. What is the reason of this?

3. Lack of regret lower bounds.

I guess that the regret lower bound analysis could be difficult, especially for the linear bandit case. However, I think some discussions would be very helpful here. After I read the paper, I cannot really understand the difficulty of designing reproducible algorithms, and also do not know which kinds of instances could be very hard to solve in this case. Besides, it is mentioned in the comclusion that the factor of ${1\over \rho^2}$ is tight (according to (Impagliazzo et al., 2022)). However, after I read that paper, I do not think its proof can be directly used for the bandit case. Maybe I miss some important things, but I think there should be more detailed explanations.
clarity,_quality,_novelty_and_reproducibility: Clarity

The section 2.1 is not very helpful for understanding. In fact, after I read this part, I guess there is a $\log{1\over \rho}$ factor in the regret upper bound, while it should be ${1\over \rho^2}$. 

I suggest the authors to give some insights about the ${1\over \rho^2}$ factor, so that the readers could understand the real hardness of this problem. For example, in section 2.2, the authors could explain about where the ${1\over \rho^2}$ factor in the complexity of ReprMeanEstimation comes from (i.e., from the random offset used in ReprMeanEstimation). After these explanations, one can understand the reason of using random $\bar{U}_i$ (or $\bar{\epsilon}_i$) in Algorithm 2 and 3 as well. 

Some other minor typos.

- In the last sentence of the first paragraph, there are two "to the".
- In related works, the regret upper bound in (Bubeck et al., 2012a) when there are $K$ arms is $O(\sqrt{dT\log K})$, but not $O(d\sqrt{T\log K})$.
- In Proposition 2, why using $\Omega$ but not $O$?

summary_of_the_review: My main concern here is about the motivation of this paper, and therefore I give the score of "marginally below the threshold".

=======After the rebuttal===========

After reading the explanations about the motivation and the lower bound, I am willing to change my score to 6.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies stochastic "reproducible bandits". A reproducible bandit algorithm is one that plays the same sequence of arms with probability at least 1-rho on any two runs of the algorithm, where the algorithm can share a random number seed across runs but the arms' rewards are generated iid.  It is easy to create a reproducible bandit --- simply pull arms in an order fully determined by the random seed --- but it isn't easy to do this while achieving low regret. Reproducibility supports debugability and interpretability. The paper studies both standard (K-armed) bandits and linear bandits.

The paper proposes rho-reproducible policies with rate-optimal regret in the time horizon. Somewhat surprisingly, while randomization seems critical in the stochastic setting, one can obtain reproducilibity with only a small multiplicative increase in regret.

Strengths
- Reproducibility is a novel and important topic
- Algorithms are interesting and clearly justified
- Regret bounds are non-trivial and technically sound
- Paper is clearly written

Weaknesses
- It is unclear about the extent to which this definition of reproducibility is truly needed to support debuggability and intepretability. Perhaps a weaker or different notion of reproducibility would be sufficient. It is also unclear whether users will value reproducibility enough to pay the regret penalty required.
- Experimental section uses only synthetic data without real-world context and is not especially compelling. While the paper is theoretical, experiments or numerical studies seem to provide an opportunity to give a more concrete support to the importance of the problem
- Regret bound has an extra dependence on K that may be problematic in large-K settings
- Novelty is somewhat reduced by the similarity of the proposed algorithms with Esfandiari et al. (2021)
- While the regret is optimal in T, there may be a gap in its dependence on other parameters

justification_for_why_not_higher_score: - Questions about whether this definition of reproducibility is the right one, and incomplete tie-in between the definition and how it would be used. This is compounded by an experimental section that doesn't take the opportunity to tie the theory to something concrete and practical.
- Smaller weaknesses called out in the meta-review
justification_for_why_not_lower_score: - Interesting and important problem setting
- Non-trivial algorithm and analysis
- Well-written
Decision: Accept: poster