Improved Algorithms for Replicable Bandits

Thank you for your careful reading and for correctly pointing out our mistake. We fixed the proof in the revision by defining $N_C$ to be the minimum of a set of integers (Appendix E, changes are colored red). Let us know if this is unclear.

Also, I think some of the proof sketches should be given in the main text.

Thank you for your suggestion. We could not put them due to page limitation.

Thank you for your time and reading. We feel the review score is a bit harsh given the reviewer agrees on the novelty of the paper. It would be great if you raised the score to match the actual sentiment.

The title of this work starts with 'Improved algorithms'. I doubt whether it is an appropriate title. I feel that this work is more likely to be an extensive study on replicable bandits

We agree with this. In particular, Section 3 formalizes the way to guarantee the reproducibility that is implicitly (and inprecisely in terms of the multiplication count) used in (Esfandiari et al.'23). We revised the paper so that this contribution is clear. We have not changed the title, but we welcome your suggestion.

Bingshan Hu, Nidhi Hegde. "Near-optimal Thompson sampling-based algorithms for differentially private stochastic bandits." UAI 2022.

Thank you for pointing out relevant work. DP considers the change of decision against the change of a single data point, whereas in our case, we have more than one change of data points between two datasets that are generated from the identical data-generating process. We added this to the revision of the related work section (Section 9, changes are colored red).

The distribution-independent bound is only provided for the RSE algorithm. However, it is usually not so difficult to derive a distribution-independent bound for the other algorithms when the distribution-dependent ones already exist. I suggest the author(s) to provide distribution-independent bounds for other algorithms and a comparison or explain the analytical challenge.

Thank you for your suggestion. Following your recommendation, we removed the claim to be "the first distribution-independent bound".

As the lower bound for the standard setting is provided, may the author(s) discuss the gap between upper and lower bounds?

Thank you for clarifcation. The gap is tight up to a logarithmic factor for $K=2$. We added this in Section 6 (colored red).

I appreciate the efforts to study the linear setting, may the author(s) also provide a lower bound (or explain the difficulty)?

Thank you for pointing it out. The difficulty here is not from the linear model but from extending the lower bound to $K>2$ arms. Note that even $K=2$, ours is the first lower bound in this problem.

From Table 1, I cannot tell RSE is obviously better than REC.

You are completely right, for most practical cases REC is better than RSE. If $\Delta_2$ is very small compared with $\Delta_3,...,\Delta_K$, then RSE would outperform, which is model 1. In model 1, RSE eliminated arms $3--5$ after $T=1000$ and thus outperforms REC, but the difference looks subtle due to the exploration before $T<1000$.

I appreciate the comparison among bounds in Table 1 but have a minor suggestion: it would be better to include the name of algorithms( and the theorems index), and rearrange the table.

Revised accordingly; thank you for your suggestion.

Thank you for many other suggestions. We highlighted the changes in the red lines.

Thank you for your careful reading. We updated the paper accordingly (colored red in the revision). Below are our updates.

Incompativility of $O(K^3)$ and $O(K)$ bounds

You are correct. We denote this several times, but revised the paper to clarify that "when the suboptimality gaps for each arm are within a constant factor".

We establish the first distribution-independent regret bound for the replicable $K$-armed bandit problem

We agree that and drop this statement.

Section 3: I believe that the non-replication framework is inspired by the long line of work on batched bandits and bandits with low adaptation.

Thank you for the reference. We added batched bandit papers in the related work (Section 9).

Section 4: The explore-then-commit algorithm was mentioned in the warm-up section of Esfandiari et al. for the case where the suboptimality gap is given to the designer and a sketch of the regret analysis was also provided. Essentially, Algorithm 2 of the current submission gets rid of the assumption that is known by using the doubling-trick approach.

Thank you for the reference. We added this at the end of Section 4. Their algorithm is $O(T \sum_i \Delta_i)$, and our EtC clearly provides a better bound.

Section 5: Essentially, this algorithm is a best of both worlds combination of Algorithm 2 and the replicable arm elimination algorithm of Esfandiari et al. '23. It is easy to see that if the algorithm detects a large gap between the two best arms, it just eliminates all of them except for the best, otherwise it performs the replicable arm elimination process of Esfandiari et al. '23. I think this comparison should be mentioned in the text. Given this discussion, I don't see where the simplicity of this algorithm compared to Esfandiari et al. '23 lies.

We agree with the word "simplicity" is somewhat imprecise. We think Section 3 in our paper clarified what is somewhat implicitly used in [Esfandiari et al. '23], and we revised the paper so that our contributions are more clearly mentioned.

Not a weakness, but relevant the the related works section: Some other references that could be useful: "List and Certificate Complexities in Replicable Learning", Peter Dixon, A. Pavan, Jason Vander Woude, N. V. Vinodchandran "Replicability and stability in learning", Zachary Chase, Shay Moran, Amir Yehudayoff Both of these works study a different notion of replicability that has to do with the number of different outputs of a learning algorithm. "Replicable Reinforcement Learning", Eric Eaton, Marcel Hussing, Michael Kearns, Jessica Sorrell "Replicability in Reinforcement Learning", Amin Karbasi, Grigoris Velegkas, Lin F. Yang, Felix Zhou Both of these papers study replicable algorithms for RL. "Statistical Indistinguishability of Learning Algorithms", Alkis Kalavasis, Amin Karbasi, Shay Moran, Grigoris Velegkas This paper provides a relaxation of the replicability definition and extends some of the equivalences shown in Bun et al. '23 to uncountable domains.

Thank you for pointing them out. We added this to the related work (Section 9).

Instance-independent regret bound for linear vs. multi-armed bandits: for linear bandits the regret bound is whereas for multi-armed bandits it is. Isn't the former always worse even though there is more structure?

It is always worse in terms of distribution-independent bound because we use a naive bound $N_i^{lin}(p) \le N^{lin}(p)$ for linear bandits, which still outperforms Esfandiari et al. '23.

Appendix F.2, proof of the (A) case. Isn't there an additive term O(K) missing in the regret bound?

We consider it correct, but let us know if some steps are unclear. We are happy to revise it.

Thank you for many other corrections. We updated the paper accordingly. All changes in revisions are colored in red.

Thank you for your thoughtful comments. The main point is the novelty comparison with the literature by Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg (2016). "Batched Bandit Problem." Annals of Statistics 2016, Vol. 44, No. 2, 660–681 [PRCS2016].

The batched bandit problem [PRCS2016] utilizes an explore-then-commit policy that conducts uniform exploration for each batch. As you correctly mentioned, if it is applied with geometric size of batches (Sec 4.2 therein), one can obtain the high probability guarantee that the rejection of arms occurs in one of two rounds; we use this fact in our algorithms as well. In view of this, our novelty is as follows:

• The analysis in [PRCS2016] focuses on the case of $2$ arms, whereas our algorithm extends to $K$ arms.
• We use randomization of the confidence bound so that the reproducibility is guaranteed with probability more than $1-\rho$ for $\rho < 0.5$, unlike the algorithm in [PRCS2016].
• We formalize the sufficient condition for a sequential algorithm to be replicable, which is implicitly used in [EKKKMV2023]. Thank you for clarifying the multiple correction on replication. In fact, [EKKKMV2023] incorrectly counts the correction factor needed for the multiplity, and the formalization in our Section 3 has a significant contribution.
• Furthermore, we unify the explore-then-commit [PRCS2016] and successive rejects [GHRZ2019,EKKKMV2023] for $K$ arms in a way that guarantees reproducibility (Algorithm 2).

[GHRZ2019] Zijun Gao, Yanjun Han, Zhimei Ren, Zhengqing Zhou. "Batched Multi-armed Bandits Problem." NeurIPS 2019.

[EKKKMV2023] Hossein Esfandiari and Alkis Kalavasis and Amin Karbasi and Andreas Krause and Vahab Mirrokni and Grigoris Velegkas. "Replicable Bandits." ICLR 2023.

Since these two papers [PRCS2016,GHRZ2019] as well as other papers in batched bandits are clearly relevant to our work, we revised our related work (Section 9) to add a discussion (highlighted in red color). Thank you again for introducing these materials.

Dear Reviewer tkZN:

In our understanding, your second comment is summarized as follows:

• You are not convinced of the novelty of the replicable bandit problem setting (K-armed bandits with replicability).
• You are unsatisfied with the gap between the upper bound and the lower bound.

Let us set the first one aside because it is somewhat subjective as you mentioned. Regarding the second question, you strongly believe you can have a better bound in both lower and upper bound. Please tell us some idea of how the tight bound should looks like? I think you understand the problem structure well, and it would be great if you shared your insight.

Best, Authors

For worst-case regret, you can be a lot more aggressive with batch sizes - using a squaring trick to get $\log\log T$ batches/adaptive rounds in total achieving $\tilde{O}(\sqrt{KT})$ regret rather than the instance-dependent case which requires a more conservative doubling trick to get $\log T$ batches/adaptive rounds in total achieving $\sum \log T/\Delta_i$ regret.

In any case, I think we have made all our points, and it is up to other reviewers and the meta reviewers to weigh in with their opinions.

Thank you for your reply.

• We think we can extend our lower bound from $2$ to $K$-arms relatively easily to get $\sum_i (\frac{\log T}{\Delta} + \frac{1}{\Delta \rho^2})$ bound that you consider ideal.
• We hypothesize (though we are not very sure) that it is impossible to have this upper bound of $\sum_i (\frac{\log T}{\Delta} + \frac{1}{\Delta \rho^2})$ because it implies $K-1$ decisions of eliminating each suboptimal arm at some round, and it is subject to $O(K)$ different decision points. We guess there are some limitations (Algorithm 1 focused on deleting all arms at the same time to the cost of $\Delta_K/\Delta_2$ coefficient as you correctly pointed out). But we are not sure; our current framework is just incapable of removing this $K$ multiplication.
• Worst-case bound is easily improvable to replace $\sqrt{\log T}/\rho$ of the current paper with $\sqrt{\log \log T}\rho + \sqrt{\log T}$. Moreover, if we can reduce the number of batches to $\log \log T$ as you suggested, then we can further improve upon it. This was not in our mind, thank you for your suggestion.

I was not arguing for the lower bound to be multiplicative, though looking back at my comment I understand it came off that way. We are essentially operating with two different "scales" here - one is the replicability parameter $\rho$, and the other is the time horizon $T$, which are independent of each other, due to which the penalty due to replicability will be independent of $T$. I apologize for the carelessness in the writing of my response. The point I was trying to make is that you should be trying to improve your upper bound to $\sum \log T/\Delta_i + 1/(\Delta\rho^2)$, which is substantially stronger than the $O(\sum \Delta_i\log T/\Delta^2)$ that you prove in this paper, which I think follows straightforwardly from existing analyses in the batching space. Moreover, you should at least try to prove a $K$ armed lower bound rather than a 2 armed one. Regarding further improvements to the upper bound, a $\log\log T$ dependence in the term that contains the replicability parameter is something I believed would be possible due to the union bound over only the $\log T$ epochs, but I did not want to commit to it since I have not formally worked out the analysis. If it is truly possible to get a regret that looks like $\sum_i \log\log T/(\rho^2\Delta_i) + \log T/\Delta_i$, it would be a massive improvement over the $O(\sum \Delta_i\log T/(\Delta^2\rho^2))$ regret proved in this work. This would also substantially shrink the gap between your upper and lower bounds, to just a $O(\log\log T)$ factor, which I think is near negligible. I also wonder whether its possible to achieve an even stronger result for worst-case regret (additive, with a $\log\log\log T$ dependence in the term that contains the replicability parameter $\rho$), since you can achieve near-optimal $O(\sqrt{KT\log T})$ regret in just $\log\log T$ batches in the usual non-replicable case, as opposed to $\log T$ batches required to achieve the optimal $O(\sum_i \log T/\Delta_i)$ instance-dependent regret. If this is indeed the case, I would indeed be willing to change my evaluation of this work. I still have my reservations about the motivation behind this setting, and that even this further improvement comes from a more careful analysis of existing batching ideas rather than the introduction of truly new tools, the fact that this work would then provide a near-complete resolution (up to low order terms) to the replicability question would make up for these deficiencies.

1. There are two components to my opinion regarding novelty, and both arise from the fact that the batched bandits work is already an established result in this area. (a) Subjective - since batched bandits already provides "near" replicability, I am not convinced about the motivation for $1-\rho$ replicability in the stochastic bandits setting. It is an extremely stringent condition and I cannot think of any practical situation where one might desire these stronger properties over the weaker guarantees already provided by the batching approach which importantly come at no asymptotic loss in regret. (b) Not as subjective - I do not believe there are any new techniques being developed in this work that would be more broadly applicable beyond the scope of the problem considered here, which further limits the impact of this paper. These two factors together make me question the novelty here.

2. The point is, there is a big gap between the upper and lower bounds. I find it quite hard to believe that the new replicability lower bound you have introduced must be independent of $T$. If you strongly believe that it must be the case, then that means the correct upper bound you should be aiming toward must contain two terms (additive instead of multiplicative), the first being the usual MAB regret, and the other additive term being the excess regret due to replicability. This seems implausible to me, though I cannot say for certain. I certainly think there is scope for improvement in your upper bounds though, through a more careful analysis exploiting subgaussianity and anti-concentrations to bound the probability of non-replication. That being said, this is as far as I can get based on intuition alone.

Lastly, I do understand that some of my reservations regarding this work are quite subjective. I would like to see both the authors as well as other reviewer's thoughts on the matter.