Geometric Resampling in Nearly Linear Time for Follow-the-Perturbed-Leader with Best-of-Both-Worlds Guarantee in Bandit Problems

Thank you for taking the time to review our paper. We have addressed your question and comment below.

Q1. Are there any disadvantages of CGR to the other algorithms (such as Tsallis-INF)?
A1. Generally, we believe that CGR has no disadvantages over the conventional GR, as it is intuitively just cutting the redundant part of GR, and thus CGR is more effective on each metric.

Although CGR overcomes the computational inefficiency compared with GR, it still inherits the general disadvantages of FTPL. This is mainly the difficulty of the theoretical analysis, such as the difficulty of the analysis for RV estimators and extensions to other settings.

Q2. Novelty of the regret analysis.
A2. Thanks for your comment. The main novelty in the regret analysis lies in the analysis of CGR II-B. The key difference in the regret analysis stems from the biased estimator, where the relevant term involves both $P(A_t)$ and $w_t$ differently from the original GR. By deriving a lower bound on $w_t/P(A_t)$, we obtained the desired result even with a smaller maximum number of resampling. While our current analysis is specific to the chosen definition of $A_t$ and the expression of $w_t$, we expect that similar results can be achieved in different settings beyond MAB by appropriately designing $A_t$ and selecting perturbations.

Thank you for taking the time to review our paper. We have addressed your question below.

Q1. Any intuitions for why the new proposed scheme would give better empirical regret?
A1. Generally, the variance of the estimator $\widehat{w_{t,I_t}^{-1}}$ introduces an additional regret term in the analysis, which is strongly related to the expected number of resampling in GR and CGR. Since the expected number of resampling is significantly reduced in CGR, the variance of $\widehat{w_{t,I_t}^{-1}}$ is also effectively reduced, compared with that of GR (as explained in Remark 2). Therefore, the regret from the estimation error of $w_{t,I_t}^{-1}$ gets improved effectively, which also leads to the improved theoretical guarantee in Theorem 5.

Thank you for your thorough review and valuable feedback on our work. We have addressed your questions and comments below.

Q1. What is the main technical difficulty in designing a variant of GR that is a sort of counterpart of Tsallis-INF with the Reduced-Variance estimator, especially compared to using importance weighting?
A1. The main technical difficulties in constructing the Reduced-Variance (RV) estimator for FTPL with GR are as follows:

The RV estimators can take negative value, which makes the analysis significantly difficult. Owing to this issue, after Zimmert & Seldin (2021) proposed RV estimator, there are still some papers on FTRL that only considers the Importance-Weighted estimator (Jin et al., 2023; Tsuchiya et al., 2023).

Moreover, for FTPL with GR, since the importance weight $w_{t,i}^{-1}$ is replaced with $\widehat{w_{t,i}^{-1}}$, the design and analysis of the RV estimator is more challenging.

Julian Zimmert and Yevgeny Seldin. "Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits.'' JMLR, 2021.

Tiancheng Jin, Junyan Liu, and Haipeng Luo. "Improved best-of-both-worlds guarantees for multi-armed bandits: FTRL with general regularizers and multiple optimal arms.'' NeurIPS, 2023.

Taira Tsuchiya, Shinji Ito, and Junya Honda. "Best-of-Both-Worlds Algorithms for Partial Monitoring.'' ALT, 2023.

Q2. Did you actually run all the other experiments for FTPL CGR II-B on your own? If so, was there no meaningful difference compared to FTPL CGR II-U?
A2. We actually ran all the experiments for FTPL CGR II-B, including the pseudo regret for $K=8$ and $K=32$, running time for $K$ varying from $2$ to $128$, and the number of resampling for $K=8$ and $K=32$. We confirmed that there is no meaningful difference compared to FTPL CGR II-U. The detailed results can be found at the this link: https://anonymous.4open.science/api/repo/ICML2025_CGRII_Experiments-9807/file/additional_experiments.pdf?v=86d6493c

Q3. Assumption on the losses in the adversarial setting: we may assume they depend on $(I_1,\ldots, I_{t-1})$.
A3. Thank you for the comment. While we mentioned the loss may depend on both $\ell$ and $I$, this phrasing was introduced primarily to clarify that we consider an adaptive adversary rather than an oblivious one. Still, we understood that as pointed out it is indeed sufficient to consider the loss as a function of $I$'s as in the literature considering an adaptive adversary (Arora et al., 2012; Zimmert & Seldin, 2021). We will modify the writing accordingly.

Raman Arora, Ofer Dekel, and Ambuj Tewari. "Online bandit learning against an adaptive adversary: from regret to policy regret.'' ICML, 2012.

Julian Zimmert and Yevgeny Seldin. "Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits.'' JMLR, 2021.

Q4.

• Starting from Section 3, $\sigma_i$ is introduced but it seems to also depend on the round $t$; making this dependence explicit (e.g., writing $\sigma_{i,t}$) is probably clearer.
• Theorem 5 seems more of a remark than an actual theorem.

A4. We sincerely appreciate your helpful suggestion. We will modify the notation accordingly to improve clarity.

Q5. In Section 5, it would be clearer to also specify how the confidence intervals around the curves were chosen (e.g., standard deviation?).
A5. Thank you for the valuable suggestion. The confidence intervals in the experimental results represent the standard deviation. We will modify the writing to clarify it.

Thank you for taking the time to review our paper. We have addressed your question below.

Q1. How would the analysis change in the proposed sampling approach when extending from bandits to semi-bandits?
A1. The analysis would not change so much if we are just interested in extending our sampling approach to derive results similar to Neu and Bartók (2016) for semi-bandits. Still, their results are only for near-optimal regret bound in the adversarial setting, and extending the BOBW analysis to semi-bandits is significantly difficult. In general, the key to the BOBW analysis in FTPL and FTRL is obtaining a uniform bound on $-w_{t,i}'/w_{t,i}^{3/2}$. Thus, the expression of $w_{t,i}$ significantly impacts the regret analysis. In the semi-bandit setting, the arm selection probability vector $w_t$ no longer lies in the probability simplex since multiple arms can be selected in one round. As a result, several techniques used in Honda et al. (2023) and Lee et al. (2024) become no longer applicable. In addition, to obtain the desired results for CGR II-B, the events $A_t$ would need to be modified according to the behavior of $w_t$ in semi-bandits.