Geometric Resampling in Nearly Linear Time for Follow-the-Perturbed-Leader with Best-of-Both-Worlds Guarantee in Bandit Problems
Authors: Botao Chen
Jongyeong Lee
Junya Honda
Venue: ICML 2025 poster (2025)
Keywords: multi-armed bandit
follow-the-perturbed-leader
best-of-both-worlds
geometric resampling
Primary area: theory->online_learning_and_bandits
TL;DR: The authors propose a novel technique, with which Follow-the-Perturbed-Leader policy achieves nearly linear time complexity without sacrificing the Best-of-Both-Worlds regret guarantee for bandit problems.

Abstract: This paper studies the complexity and optimality of Follow-the-Perturbed-Leader (FTPL) policy in the $K$-armed bandit problems. FTPL is a promising policy that achieves the Best-of-Both-Worlds (BOBW) guarantee without solving an optimization problem unlike Follow-the-Regularized-Leader (FTRL). However, FTPL needs a procedure called geometric resampling to estimate the loss, which needs $O(K^2)$ per-round average complexity, usually worse than that of FTRL. To address this issue, we propose a novel technique, which we call Conditional Geometric Resampling (CGR), for unbiased loss estimation applicable to general perturbation distributions. CGR reduces the average complexity to $O(K\log K)$ without sacrificing the regret bounds. We also propose a biased version of CGR that can control the worst-case complexity while keeping the BOBW guarantee for a certain perturbation distribution. We confirm through experiments that CGR does not only significantly improve the average and worst-case runtime but also achieve better regret thanks to the stable loss estimation.

Geometric Resampling in Nearly Linear Time for Follow-he-Perturbeel-Leddd with Best-of-Both-Wordd Guarantee in Bandit Problems
Botao Chen
Jongyeong Lee 22 Junya Honda 13
Abstract
environment and the player can only observe the incurred loss l,,,, from the chosen arm. The player's objective is to minimize his/her cumulative losses over all rounds. The performance of the player is measured by the pseudo-regret, which describes the gap between the cumulative loss of the player and of the optimal arm fixed in hindsight.
This paper studies the complexity and optimal- ity of Bealow-the-Perturedd--eeee icy in the K-armed bandit problems. FTPL is a promising policy that achieves the Best-of- Both-Worlds (BOBW) guarantee without solv- ing an optimization problem unlike Follow-the- Regularized-Leadee (FTRL). However, FTPL needs a procedure called geometric resampling to estimate the loss, which needs O(K²) per-round average complexity, usually worse than that of FTRL. To address this issue, we propose a novel technique, which we call Conditional Geomet- ric Resampling (CGR), for unbiased loss estima- tion applicable to general perturbation distribu- tions. CGR reduces the average complexity to O(K log K) without sacrificing the regret bounds. We also propose a biased version of CGR that control the worst-case complexity while keeping the BOBW guarantee for a certain perturbation distribution. We confirm through experiments that CGR does not only significantly improve the aver- age and worst-case runtime but also achieve better regret thanks the stable loss estimation.
(FTPL) pol-
Stochastic setting (Lai & Robbins, 1985; Auer al., 2002a) and adversarial setting (Auer et al., 2002b; Audibert & Bubeck, 2009) are two fundamental formulations of the enviromment to determine loss vectors. In the stochastic setting, the losses fa.5 from arm i are i.i.d. from an unknown but fixed distribution over [0, 1] with expectation 14s, The suboptimality gap is expressed by A; = #4 [4;- for the optimal arm i' E arg [i] The optimal (problem- dependent) regret bound given these gaps is known to be E.A. O( loxg) (Lai & Robbins, 1985), which can be achieved by several policies such as UCB (Auer et al., 2002a; Cappé et al., 2013) and Thompson sampling (Kauf- mann et al., 2012; Agrawal & Goyal, 2013; Riou & Honda, 2020), some of which further improve the regret bound by incorporating the dependence on the loss distribution itself.
In the adversarial setting, the loss vectors l are not assumed to follow any specific distribution, and the environment may choose them based on the history of the decisions. For this setting, the optimal regret bound ((VKT) (Auer et al., 2002b) is achieved by some policies, including a family of policies called the Follow-the- Reguula----gul Leader (FTRL) with appropriate regularization functions (Audibert & Bubeck, 2009; Zimmert & Lattimore, 2019).
1. Introduction
The multi-armed bandit (MAB) is sequential decision- making problem under uncertainty, which describes a model of a gambler playing slot machines. It has been widely applied in practical scenarios, such as online advertising, clinical trials, recommendation systems. In this problem, the player chooses an arm 4 out of K arms in each round t E [ = ..., T) for time horizon T. The loss vector 4, = (,,,,,,, (x,x) E [0. 1] determined by the
In reality, the environment to determine the loss is often unknown, and thus it becomes necessary to develop pol- icy that is optimal in both stochastic and adversarial set- tings at the same time. The Tsallis INF policy (Zimmert Seldin, 2021) an FTRL-based policy that can overcome this difficulty. Tsallis-INF achieves O(vKT) regret in the adversarial setting and Eitr- O 0lon T regret in the stochas- (BOBW, Bubeck & Slivkins, 2012) guarantee. It has also been shown that FTRL framework can achieve BOBW for the problems beyond the classic bandit problems, such as partial mon- itoring (Tsuchiya et al., 2023b;c) and combinatorial-semi bandits (Zimmert et al., 2019: Ito, 2021).
'Equal contribution "yyoto University, Kyoto, Japan "Seoul National University. Seoul, Korea 'RIKEN AIP, Tokyo, Japan. Cor- respondence to: Botao Chen achen.botao.do 63r@st st.tsst.kooouu up...........pp. Jongycong Lee <jongyconge @nnu.ackr>>.
tic setting, which is called a Bost-of-Both-Warr
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
One limitation of FTRL is that the arm-selection probabil- ity wi is required to be explicitly computed and stored in each round, which requires to solve optimization prob- lem involving a regularizer. This becomes problematic in some complex settings, and the framework of Follow-the- Perturbed-Leate (FTPL) is a promising candidate to over- come this limitation. FTPL greedily chooses an arm with the minimum cumulative estimated loss with some random perturbation and does not require to solve an optimization problem nor store the vector Wt. These properties have made FTPI. across various online learning and ban- dit problems, including combinatorial semi-bandin (Neu & Bartók, 2016), online learning with non-linear losses (Dudik et al., 2020), and MDP bandits (Dai al., 2022), though the regret guarantees of FTPL are often somewhat weaker than FTRL (see Appendix A for more details of FTPL literature).
simple update rule without iterations, though its empirical performance is worse than Tsallis-NN.
Contribution of the Paper This paper proposes a novel technique which we call Conditional Geometrie Resampling (CGR), which gives unbiased or low-bias estimators for Wi,s in FTPL. The idea behind the technique is that, while the original GR "faithfully" simulates the arm-selection procedure of FTPL by resampling the perturbation until ter- mination, CGR resamples the perturbation only from those satisfying a necessary condition for termination. By appro- priately choosing this necessary condition we can signifi- cantly reduce the required number of resampling M, while keeping the complexity of resampling once to be O(K).
We propose three variants of CGR (CGR I, Il-unbiased Il-biased), all of which achieve the quasi-linear average complexity of O(K log K) without sacrificing the regret of the original GR with O(K2) complexity. These variants differ in the detailed guarantees and requirements, which are summarized in Table 1. In summary, while the complexity guarantee of CGR II is stronger than CGR I, CGR II requires that the cumulative distribution F(x) and its inverse are computable. Furthermore, CGR significantly improves the regret from FTPL with GR empirically thanks to the reduced variance of the estimators as we will see in Section 5.
From the theoretical viewpoint, FTPL has also been studied for the standard MAB in terms of the duality between FTRL and FTPL, and Kim & Tewari (2019) raised an open prob- lem that FIPL achieving O( / KT) regret (if exists) would have perturbations following Fréchet-type distributions. As solution to this conjecture, it has recently been proved that FTPL with Fréchet perturbation with a = 2 achieves the BOBW guarantee (Honda et al., 2023), which was later extended to more general Fréchet-type distributions with some mild conditions (Lee et al., 2024).
2. Problem Setup
From the practical viewpoint, however, the advantage of FTPL for the standard MAB has been somewhat limited compared with the clear computational advantage of FTPL for complex problems. The reason is that FTPL and FTRL generally need an unbiased (or low-bias) estimator for the loss vector & for each round. In FTRL, the Importance- Weighted (IW) estimator is often used, which is an unbiased estimator for l using the inverse of the arm-selection prob- ability - -1 On the other hand FTPL, wi is not explicitly computed and the IW estimator becomes unavailable.
In this section, we formulate the problem and introduce the framework of FTPL with geometric resampling. At each round t E [T] = 21, .., T,, the environment determines a loss vector & = (,,,1, l..,...,, k E [o, _]K, The player then pulls an arm 45 E [K], and observes the incurred loss lr,,, associated with the chosen arm.
The loss vector is determined in either a stochastic or adversarial way. In the stochastic setting, loss vectors
L fa.2...,44 l [0, 1j are i.i.d. from an unknown but fixed distribution P over [0, 1] The expected loss from arm i is denoted by 14, Ee-p [Ct,,] [0, 1]. The suboptimality gap of arm i is A; μ4; [4i-, where i* arg wrggiingg K represents the optimal arm. In this paper, we assume that i* is unique in the stochastic setting. In adversarial setting, the loss l, is determined adversarially, which may depend on the history of the chosen arm (1.)==)
To address this problem, Neu & Bartók (2016) proposed a technique called Geometric Resampling (GR) to obtain an unbiased estimator for " but its computational cost is O(K2) per round in average. On the other hand, W/ for Tsallis- (i.e. FTRL with Teallss regularizer) can be efficiently computed by, e.g., Newton's 's method, whose computational cost per iteration is O(K). Though the re- quired number of iterations to keep the theoretical guarantee formally unknown, is empirically known that O(1) it- erations is sufficient. Therefore, the entire computational cost of Tsallis INF per round becomes O(K) in practice, which becomes more efficient than FTPL with ((32) cost. In addition, very recently Zimmert& & Marinov (2024) pro- posed TS-Prod policy, which is related to the first-order approximation of online mirror descent and Isa. TS-Prod provably achieves the BOBW guarantee with a
We measure the performance of the player in terms of the pseudo-regret R(T)) defined as
T (le,1 -lat .000 E arg min E Σ
R(T)- E
Σ le,
[E[K]
2.1. wewttthh-eeruuued--eeee
We consider the www.-tteeeerture--Leeee Leader (FTPL) pol- icy, whose entire procedure is in Algorithm 1. At ev-
2

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Table Comparison on the number resampling Mr computational requirements on the CDF of the perturbation and regret bounds between original geometric resampling (GR) and conditional geometric resampling (CGR). Note that Neu & Bartók (2016) considers combinatorial semi-bandits and the result here is the one when applied to the MAB. The last column is the regret guarantee under appropriate choice of perturbation distribution, which is exponential distribution & with unit scale for Neu & Bartók (2016), Fréchet-type distributions with some conditions in Lee et al. (2024, Theorem 2) for GR, CGR I, CGR II ll-unbiaeed, and the Fréchet distribution F2 with shape for CGR II-biased.
Algorithms
[[M]]
D Mi L.]
B Mi LL.
Worst-case Mr
Computational Requirement Regret Bounds
GR
O(K)
O(K)
Unbounded
Unbounded
None
BOBW
GR (Neu & Bartók, 2016)
O(K)
O(K)
O(VKT) (under E1)
VKT (under E1
None
Adversarial
CGRT T
(log K)
Olog K)
Unbounded
Unhounded
None
BOBW
CGR H-unbiased
Olog K)
Oloog K)
O(K) [under F2)
Unhounded
Explicit F(x) and F (ar)
BOBW
CGR I1-biased
Ollog K) (loo K)
O(K) (under F2)
[K log (under F2)
Explicit F(x) and F
BOBW
Algorithm Fooloow-th- therttttheeetttrrrc----eeee
Algorithm Geometric Resampling
1: Input: Learning rate 7/-
1: Input:
2: Set L1 := 0
Chosen arm I, cumulative loss L, learning rate n
3: for mrr=11 1,2, ..,,, do
2: Set m ==
4: Sample ri = Tr, Fr.k)) i..d. from D
3: repeat
5: Pull arm 1 = arg ei (L., re,s/m) and ob-
4: m == m +
serve ft.,,
5: Sample r = (r' r.2...,,, r(,K) iidd from D
6: until 1t arg min sinj (Le, - r/s/
6: Compute estimator W,J, for w by geometric
resampling
7: Set wt.1, == m
7: Set l, == b1,11 W, en, and Lif1 == Li +h
8: end for
Here the gap of a vector from its minimum is expressed by underlines, for example, L = L, 1 minge Le,s E [0, oo) where 1 is the all-one vector.
ery round 1, FTPL keeps the estimated cumulative loss f, E R specified later and draws a perturbation vec- tor r. (.....
R&K from some distri- bution. Then, it pulls the arm minimizing the perturbed loss Le,; - -rt,s/n, where 7) is the learning rate. Unless specified otherwise, we assume that the components of r. = (r,, ,T,,, k)) are i.i.d. from a common dis- tribution D over IR, whose density function and cumulative distribution function (CDF) are denoted respectively by fx) and (x)) In particular, when D is supported on [V, oo) for some finite v -00, we assume
2.2. Geometric Resampling
Since the loss in every round is partially observable, both FTRL and FTPL generally use an estimator é, for loss vector l, The estimator of the cumulative loss L, = E.=1 la is
then obtained as L, = -'=1 l.
In many policies for the adversarial setting like FTRL, the Importance-Weighhed Weighted (IW) estimator & = (fr, /wr,,) er, is employed as an unbiased estimator for &, where ea is a unit vector with the i-th component set to one. However, as we can from (1), Wt,r, is not explicitly computed in FTPL unlike FTRL. To address this limitation, FTPL instead uses an estimator w for w by the technique called Geometric Resampling (GR) described in Algorithm 2.
0 without loss of generality by considering the location shift of D.
Given L, the probability of pulling arm is given by
Wt,1 PTDD
i= arg
arg min L - re.s/me ]E[K]
/ 1(=+ In.))
II
F(z + n de.
In GR employed in Neu & Bartók (2016) and Honda et al. (2023), another perturbation vector P/ is repeatedly drawn from the same distribution D until arg min;e( LZe, r'm//Te = I, is satisfied, that is, resampling from D is repeated until the arm that would be pulled under the pertur- bation r. coincides with the actually pulled arm I,-
jfi
When D is supported over [0, 20) we can write
We,i = 10 f(z + ((2+mL),))
II
F(z + mebee dz.
Here the chosen arm T is determined prior to the initia-
371
3

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
tion of the GR process. Since the stopping condition is satisfied with probability W in each iteration, the number of resampling follows geometric distribution with success probability We.d++ whose expectation is 1/W,,,, Letting "t,, be the number m of resampling, we observe that wi,h serves as an unbiased estimator for wi.
is satisfied since Lu,,, 2 L,,;;- Thus it is somewhat "waste- ful" to sample r' satisfying Ti,,, < ",5; and it becomes suffi- cient to resample r' only from those satisfying T'.1, 2 ".it""
Now let formalize this idea. Let Ae be arbitrary necessary condition for termination given in (2), which may depend on L, and I, For example, the above discussion corresponds to A = (r'.,, 2 2r(ir)- Then, we can easily derive the following property, whose proof is shown in Appendix B.I.
Denote the number of resampling taken by geometric re- II sampling round L as M,, which is equal to w.,,, in the original GR explained here. Then, the expectation of M, given L, is expressed as
Lemma 1. Consider resampling of from 'D conditioned on At until (2) is satisfied. Then, the number Mj of resam- pling satisfies
[[M[L]]=
Σ *E|K]
P(T il EM T
PLA, LL, Itl
=
Σ KE[K]
Wi,i"
W1,5 = K.
B Le. 47]
Wt.
By this lemma we can use M,/P(A,1 Lne Ie] as an unbiased estimator of w. In addition, we can reduce the number of resampling we take A, such that P[A,, [L,, I,] is small.
Since generating a perturbation vector from D needs K' random number generations, the expected complexity per round becomes O(K²). From the viewpoint of the worst-case complexity, is known that OVKTTllog log K) re- gret is achievable even if we terminate the resampling after O(VKT) repetitions, which leads to O(VK3T) worst-case complexity (Neu & Bartók, 2016). On the other hand, the per-round complexity of FTRL is usually O(K) if the opti- mization stops within (1)) iterations. Though FTPL is still efficient for moderate size of K (Honda et al., 2023) thanks to its optimization-fre free nature, the worse dependence on K motivates us to develop a more efficient version of FTPL.
Here note that we can trivially minimize P[[A,] L2, L,] by taking the termination condition (2) itself as A,. Still, such a choice makes it difficult to compute P[A L2 Ia] and to resample ry from the conditional distribution given A,. In the following algorithmss, we construct necessary conditions A, such that P P, 1 is small and easily computed, while the resampling from the conditional distribution given A is also efficient.
3.2. Conditional Geometric Resampling
3. Proposed Algorithms
Based on the above idea, we propose three variants of con- ditional geometric resampling called CGR I (Algorithms 3), CGR II-unbiased and CGR Il-biased (Algorithms 4). Here, CGR II-unbiased and Il-biased consider resampling from the same conditional distribution, and thus we will discuss them together. In the algorithm description, blue parts are the ones different from the original GR.
In this section, we introduce a family of algorithms which we call Conditional Geometric Resampling (CGR). This family is designed as an improvement over the original GR, providing estimator for W efficiency. In the following, we write ort to denote the number of arms (including itself) whose cumulative losses do not exceed Le,,, that is, La, is the -th smallest among [JEkk] where of, otj can happen when Li, Le.j. For example, a current best arm àz E arg min, Le,j is an arm i such that ot, = 1. For notational simplicity, we omit the subscript / in or when the context is clear.
-1 with better computational
This version corresponds the case where we sample ri conditioned on A, {r',,, max " that is, the event that ri,,, is the largest among the arms whose cumulative estimated losses are no worse than arm I. By the symmetric nature of the i.i.d. perturbations, sampling from this conditional distribution can be realized by simple operations as shown in Algorithm 3, which only needs the extra value-swapping operation in addition to the original GR. This fact and other properties of CGR I are formalized as follows.
CGR I
3.1. General Idea
Before explaining the specific procedures of the proposed algorithms, we first give the intuition behind them. When run the original GR, some possible values of r clearly vi- olates the condition for termination. For example, when the pulled arm I is not the current best arm i E arg min, Lu,s, then the resampled perturbation must satisfy r',,, 2 1,,t so that the condition for termination
Lemma 2. The sample r' obtained by Algorithm 3 fol- lows the conditional distribution of D given Ae = (r max r...). In addition,
4 arg min [) (Le,s r'ce/
P PonD[Ail Ij] = 1/0r.1.

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Algorithm 3 Conditional Geometric Resampling I
Algorithm 4 Conditional Geometric Resampling II
1: Input: Chosen arm 4, cumulative loss L, learning rate
1: Input: Chosen arm Lt, cumulative loss Le, learning rate
Jt maximum number of resampling Ge E N U {oo}
2: Set m := 0
2: Set m == 0
3: repeat
3: repeat
4: m: m +
m == m +11
5: Sample r/z = 1/2.1.7/2.... F.,x) i.d.. from
Sample {r/, 1 01.) i..d. from D
6: Swap the values of ri and r r.,, where
6: Sample r2.,, from Dor, truncated over [m L, oo),
i' = arg io, The
whose CDF is (4)
7: until 1, = arg mi (Le /
7: Sample {r/, 0o S0, + [1 i.i. from D trun-
cated over (0,r,, whose CDF is (5)
8: Set 11 = mar
8: until 1, = arg [ (L, - r /
or m 2 G.
Set Wt,1 maa Fou (m (n
and the number M, of resampling satisfies
[M log K
Next, we sample {re, I la So,, 1 1.) i..d from D trun- cated over [0, (0.T(,1)) whose CDF is given by
The proof of this lemma is shown in Appendix B.2. Com- bined with Lemma 1, this result suggests Wt,J. = Mior, given by CGR is unbiased estimator for w,J,," Moreover, the expected number of resampling per round is bounded by log K + 1, which is independent of L..
-
x x 10,0,r...) (5)
Note that the computation of F(x) and F-1(xx) necessary in this algorithm to generate samples from (4) and (5) by the method of inverse transform sampling. We can show that the samples generated by this procedure indeed follow the conditional distribution given A.,
only use the symmetry of the distribution of re R As result, the unbiasedness and Lemma are still valid even if the components of r. E R are not independent as far as the joint distribution is symmetric, though the regret bounds discussed in this paper are for independent perturbations.
Remark 1. In CGR
Lemma 3. In CGR II, r' follows the conditional distribution of D given A in (3). In addition,
P PnND|Ai It] [+]= (1- (1--F% pos. (neLe, 1. /o1,
CGR II In this version assume that D is supported over [0, oc). CGR II corresponds to the case where we sample ri from D conditioned on
and the number Me of resampling satisfies
EAADDA [M|L]] S log K +
A Teu-- max rhes rh.,. 2 mide.e EoiSor
(3)
Besides, if is the Fréchet distribution with shape 2, then M, satisfies
that is, we impose the extra condition Ft,, Z neLe. in addition to the condition in CGR We also set the maximum number of resampling Ge N U {oo}. where we refer to by
the versions G2 CGR Il-biased. The complete procedure of CGR II is given in Algorithm 4, which is explained below.
by CGR Il-unbiased and G2
The proof of this lemma is shown in Appendix B.3. Com- bined with Lemma 1, we see that
Let Dm be the distribution the maximum of m i.i.d. sam- ples from D. whose CDF is Fm FT'(x) = (F(x)))* CGR II we initially sample r',,, conditioned on At, which follows Do,, truncated over indL,,, ,, 00) with CDF given by
W L.J. (Mo1/(1-FoM (m.
serves an unbiased estimator for w 1 if G, oc. In addition, the last statement of this lemma shows that the expected number of resampling is bounded by K V 4 in the worst case of L, and L, regardless of the choice of G, if D is the Fréchet distribution with shape 2. We will show in Section 4 that the choice G = (K V 4) log t is sufficient to guarantee the BOBW regret bound.
Fou (x) F (Tele,e)) F1, (x; - Fon (m.Le...)
n m.L.. (4)
5

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
3.3. Comparison between CGR and CGR II
which is smaller in CGR I and Il-unbiased Though the improvement is hidden in the big-O notation, it explains the better empirical performance of CGR given in Section 5.
Now let us consider the complexity per round, which can be expressed as
Remark 3. In particular, CGR II slightly improves the dom- inant term of the adversarial regret by 0.4v KT compared with the existing bound for GR. This fact is formalized in Theorem 10 in Appendix D.
Mj x (complexity of resampling once).
The first factor is analyzed depending on the algorithms and conditionings in Lemmas 2 and 3, which are summarized in Table 1. The second factor is O(K) in both CGR and II, but its factor usually becomes slightly larger in CGR II due to the computation of F and F-1 For this reason, while CGR II always achieves smaller M, than CGR I, the total computational cost becomes higher in CGR II in most cases as shown in the experiments in Section 5.
In CGR I-biased, where the maximum number of resam- pling G, finite, the estimator for w becomes biased. Here, we provide the regret analysis of CGR II-biased and show that it can also achieve the BOBW result, stated in the following theorem.
Theorem 5. FTPL CGR Il-biased with learning rate f c/ fi e >> O and maximum number of resampling G. = (K V 4) log t satisfies that
4. Regret Analysis
In this section, we first show that CGR I and Il-unbiased keep the regret bounds for the original GR as a direct conse- quence of the unbiasedness of the estimators. We then show that CGR II-biased also achieves a regret bound with the same order as the unbiased ones.
R(T)= S (O(VKT)
in adversurial bandits, in stochastic bandits,
10 log.)
if is the Fréchet distribution with shape 2.
4.1. Regret Bounds
This result shows that FTPL with CGR Il-biased reduces both the worst-case and average complexities while pre- serving the same order of the regret bound when using the Fréchet perturbation with shape 2. Here note that the GR by Neu & Bartók (2016) achieves O(v log K) regret for the adversarial setting with the maximum number of re- sampling G. = O(v KT). Therefore our result shows that the BOBW guarantee is achievable by significantly better maximum number of resampling in most cases.
As we demonstrated in the last section, CGR I and II- unbiased still provide the unbiased estimator for w and thus for L,i We can directly apply this property to the BOBW analysis by Honda et al. (2023) and Lee et al. (2024) for Fréchet-type perturbations which we state below for completeness.
Proposition 4. FTPL with CGR I and Il-unbiased with learning rate T)- = <// >>> 0 satisfies
Remark 4. Our choice G, = O log t) is slightly worse than G. = O(VKT) in Neu & Bartók (2016) if = K, but it is just because their goal is to bound the bias by O(VKT) rather than Olog T). In fact, by following the same argu- ment as Theorem 5 we can see that G2 O ( log(T/K)) is enough to achieve O(V KT) bias, which is no worse than G, = O(VKT) whenever K S.
[O(VKT)
in adversarial bandits,
RR(T) S (0
IoE'T A.
in stochastic bandits,
if the perturbation distribution D is Fréchet-type and satis- fies the conditions in Lee al. (2024, Theorem 2).
This proposition is straightforward and we omit the proof. This is because the proofs of Honda et al. (2023) and Lee al. (2024) only use the variance bound given in (6) below for the property of the unbiased loss estimator as far as the loss estimator é, is nonnegative, where the nonnegativity trivially holds for CGR I and -l-ubbased.
4.2. Proof Sketch for Biased Estimator
In this section we give a sketch of a proof of Theorem 5. The complete proof is given in Appendix C. We begin with the following regret decomposition similar to Neu & Bartók (2016, Lemma 5).
Remark 2. To be more precise, FTPL with CGR and ll-unbiased can attain slightly better regret guarantee than the one with the original GR. This is because the variance of the estimator WT becomes
Lemma The expected regret of FTPL with CGR II satis- fies
T
Var [, |L,, Ii]
R(T)
E
le Wi -
-c+)
1=1
(original GR),
We.ft
(6)
Wass
(CGR I, Il-unbiased),
E
Wi,t 1
IP(AA Lr, I =
1=1
KE[K]
6

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
The restriction on the maximum number of resampling al- ways reduces the expected value of " M, M,/P(A,l)) compared to the case G2 = Do. By using this fact we can show that the first term on the RHS can be directly bounded by the one with the unbiased estimator in Honda et al. (2023). Therefore, it becomes sufficient to consider the second term, which is bounded as follows.
FTPL CGR II-U, FTPL CGR II-B, and FTPL GR. In all the experiments we used Fréchet distribution with shape = 2 for the perturbation of FTPL.
We also compare the performance with Tsallis-INF and TS- Prod. Tsallis- is FTRL with Tsallis-entropy regularizer. In our experiments, Wy in this policy was computed by Newton's method. For the loss estimator of Tsallis-INT INF,, we consider Importance- euportance-Weighteed Weighted (IW) estimator and Reduced- Variance estimator (RV, Zimmert & Seldin, 2021), the latter of which has better regret bounds than the former. We denote Tsallis-INF with these estimators respectively as T-INF IW and T-INF RV.
Lemma 7. When D is the Fréchet distribution with shape 2 and G2 = (K V 4) log t, FTPL with CGR Il-biased satisfies
G.
W1.b
E [
We,i 1
S log T.
P(A I =
1=
We used the same learning rate for T-INF as that of Zimmert & Seldin (2021) (1): = c/vt with c = 2 for IW and c 4 for RV). Since FTPL in this paper and those in Lee et al. (2024); Honda et al. (2023) are designed to mimie T-INF IW. we use the same learning rate for FTPL as that of T-INF IW.
This lemma shows that the additional regret introduced by the bias is at most logarithmic in T independent of K.
The key to this proof is bounding wr, (x,:/P((All)) from below by constant independent of L, When we consider the Fréchet perturbation we can derive simple bounds on Wt, and -.al))) in terms of 1T, and nhe I,, From these bounds we can show (tt.:/P(A.l)) 2 1/(K V 4) by considering the worst case of 0T, and ne We expect that this result can be generalized to more general Fréchet-type distributions by using bounds on wy for various cases in Lee et al. (2024).
TS-Prod is a variant of Prod serving as an approximation of T-INF. Unlike T-INF, TS- Prod requires only one-step update rather than solving an optimization problem, resulting in more efficient computa- tion with complexity of O(K). We used the same learning rate for TS-Prod as that of Zimmert & Marinov (2024).
et al., 2007),
Figure I shows the number of resampling at each round for adversarial setting on log scale. From this figure we see that the number of resampling is significantly and stably kept small under all the variants of FTPL CGR. In particular, the medians of FTPL CGR II-U and FTPL CGR II-B are one, that is, resampling terminates within only one trial for more than half of the rounds.
Number of Resampling
Still, it requires heavy case-by-case analysis and we leave it to future work.
5. Experiments
In this section we give results of experiments on the num- ber of resampling of geometric resampling and compare the regret and computational efficiency with existing poli- cies. All of the figures are the results of 100 trials, with shaded areas representing confidence intervals computed using standard deviations. The experiments were conducted on an AMD EPYC 7763 CPU, implemented in Python 3.9 using the NumPy library. The code is available at: ht https: / //github. . com/ BotaoChenn 23 22tpe/111/////////// CGR!
Furthermore, as observed from the outliers, the number of re- sampling of FTPL GR is somewhat unstable and sometimes prohibitively large (recall that the plot is in log scale), while FTPL CGR effectively controls the maximum number of resampling. In addition, the actual maximum number of resampling under FTPL CGR II-B was much smaller than the theoretical guarantee of G. = (K v 4) log L, which is for example G. RJ 295 for K = 32 and t = 10000. For this reason the behaviors of FTPL CGR II-U and FTPL CGR II- B were empirically indistinguishable. To avoid redundancy, we present only the results for FTPL CGR II-U the fig- ures of runtime and regret performance, simply referring to it as FGR II.
Following Zimmert& & Seldin (2021), we consider the stochastically constrained adversarial setting and the stochastic setting. Since we observed the same tendency between them, we only give the results for the former setting here and the results for the stochastic setting is given in the appendix. The details of the instances as well as the additional results are given in Appendix E.
Environments
Regret Comparison Figure 3 is the comparison of the re- gret of FTPL with those of FTPL GR, T-INF and TS-Prod As can be seen from this result, the regret of FTPL CGR is slightly better than FTPL GR. Furthermore, the regret of FTPL CGR ll is close to T-INF IW, and even better in some settings, despite the fact that FTPL CGR is also based on the IW estimator. As discussed in Remark 2, this improved regret of FTPL CGR seems to be thanks to the reduced
Policies We compare FTPL with three variants of conditional geometric resampling (CGR I, CGR II- unbiased, CGR Il-biased) with FTPL with geometric re- sampling, which we will respectively write FTPL CGR I,
Addapted from the code of Tsuchiya et al. (2023a) available at https:/ / http/ggttuubuuge/g www www.////ttcctiiitectctceteestttt /bobwwbweeeeee va variance/ tree/ rree/master.
7

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
10
FTPL GR
FTPL CGR
FTPL CGR
T-INF IW
10
3
T-INF RV
TS-Prod
10
2
10
10"
FTPL GR
FTPL C
FTPL CGR II-U
FTPL CGR II-B
2
16
32
48
64
80
96
112
128
Figure 1. Number of resampling for adversarial setting, K 32,
Figure 2. Runtime (sec) for adversarial setting and different K.
FTPL GR
FTPL GR
FTPL CGR
FTPL CGR
FTPL CGR
1000
FTPL CGR
T-INF IW
T-INF IW
500
T-INF RV
T-INF RV
800
TS-Prod
TS-Prod
400
600
300
400
200
100
2500
5000
7500
10000
0
2500
5000
7500
10000
(a) K = 8
(b) K 32
Figure 3. Pseudo regret adversarial setting.
variance of the loss estimator. On the other hand, the regret of FTPL CGR ll is still worse than T-INF RV. Therefore it is still an important future work to devise counterpart of RV estimator for FTPL. The regret of TS-Prod is the worst among all compared algorithms,, seemingly due to the approximation error introduced by its update rule.
One interesting observation is that the runtime of FTPL CGR is consistently better than FTPL CGR despite its larger number of resampling shown in Figure 1. This comes from the fact that the conditioning procedure of CGR I only needs swapping of the maximum and is very fast.
Computational Efficiency Figure 2 shows the runtime for selection over 10000 rounds of FTPL, T-INF and TS-Prod for varying K from 2 to 128. When K is small enough, both of FTPL GR and FTPL CGR run much faster than T-INF. However, as K increases, the runtime of FTPL GR sharply grows, while those FTPL CGR, T- INF and TS-Prod are kept small. particular, the runtime of FTPL CGR and TS-Prod is much smaller than T-INF thanks its optimization free nature. Additionally, the runtime of FTPL CGR slightly exceeds TS-Prod when K is large, seemingly due to the additional log K factor in its complexity.
6. Conclusion
In this paper, proposed Conditional Geometric Resam- pling (CGR), which is technique to give unbiased or small-bias estimators for w The most important con- tribution is that, CGR is the first algorithm to enable FTPL to achieve BOBW with average complexity O(K log K) without sacrificing the regret. For the second version of CGR with perturbations following Fréchet distribution with shape 2, we provided bound of O(K) for the expected number of resampling given the chosen arm, and proved the BOBW property of CGR I1-baased with the maximum num- ber of resampling [K V 4) log t7. We empirically demon-
8

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
strated that CGR not only significantly improves runtime efficiency, but also improves the regret from FTPL with the original geometric resampling.
Cesa-Bianchi, N., Mansour, Y., and Stoltz, G. Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321-352, 2007.
Dai, Y., Luo, H.,, and Chen, L. follow-the-poe -eroowtt---ertured---ee perturbed-leader for adversarial markov decision processes with bandit feedback. Advances in Neural Information Processing Systems, 35:1 35:11437-11449, 2022.
Acknowledgements
BC was supported partially by JST/CREST Innovative Mea- surement and Analysis (Grant Number JPMJCR2333). JL
was supported by the National Research Foundation of Ko- rea (NRF) grant funded by the Korea government (MSIT) (No.RS-28) (S$2002-003353303 JH was supported partially by JSPS KAKENHI (Grant Number (P25KK3184)
Dudik, M., Haghtalab, N., Luo, H., Schapire, R. E.,, Syrgka- nis, V., and Vaughan, J. W. Oracle-efficient online learn- ing and auction design. Journal of the ACM, 67(5):1557 2020.
Impact Statement
Hannan, J. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):77-339, 1957.
This paper provides a primarily theoretical contribution to the study of the multi-armed bandit problem, and we believe there no direct negative ethical or societal consequences that should be highlighted here. Our research may facilitate real-world applications of the FTPL algorithm, such as in recommendation systems and dynamic pricing.
Honda, J., Ito, S., and Tsuchiya, T. Bellow-the-Perturbee Leader achieves best-of-bott both-worlds for bandit problems. In Algorithmic Learning Theory, volume 201, pp. 726- 754. PMLR, 2023.
References
Ito, S. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. In Advances in Neural Information Processing Systems, volume 34, pp. 2654- 2667. Curran Associates, Inc., 2021.
Agrawal, S. and Goyal. N. Further optimal regret bounds for thompson sampling. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, pp. 99-107. PMLR, 2013.
Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7103):21-337,
Audibert, J.-Y. and Bubeck, S. Minimax policies for adver- sarial and stochastic bandits. In Conference on Learning Theory, pp. 217-226, 2009.
Kaufmann, E., Korda, N., and Munos, R. Thompson sam- pling: An asymptotically optimal finite-time analysis. Algorithmic learning theory, pp. 199-213. Springer, 2012.
Auer, P., Cesa-Bianchi, N., and Fischer, Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-2555 2002a.
Kim, B. and Tewari, A. On the optimality of perturbations in stochastic and adversarial multi-armed bandit problems. Advances in Neural Information Processing Systems, 32, 2019.
Auer, P., Cesa- Bianch,,, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(():48-777 0:0:488777,70 2002b.
Awerbuch, B. and Kleinberg. R. D. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 45-53, 2004.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1) 4-22, 1985.
Lee, J., Honda, J., Ito, S., and Oh, M.-h. Follow-the- ceturbed-Leadde with Fréchet-type tail distributions: Op- timality in adversarial bandits and best-of-both-worldd In Conference on Learning Theory, volume 247 of PMLR, pp. 3375-3430. PMLR, 2024.
Bubeck, S. and Slivkins, A. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Confer- ence Proceedings, 2012.
Cappé, O., Garivier, A., Maillard, O.-A., Munos, R., and Stoltz, G. Kullback-leible upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pp. 1516-1541, 2013.
Neu, G. and Bartók, G. Importance weighting without im- portance weights: An efficient algorithm for combinato- rial bandiss. Journal of Machine Learning Research, 17(154): 2016

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Poland, FPL analysis for adaptive bandits. In Interna- fional Symposium Stochastic Algorithms, pp. 58-69. Springer, 2005.
Riou, C. and Honda, J. Bandit algorithms based on thomp- son sampling for bounded reward distributions. In Algo- rithmic Learning Theory, pp. 777-826. PMLR, 2020.
Tsuchiya, T., Ito, S., and Honda, J. Further adaptive best-of- both-worlds algorithm for combinatorial semi-bandits. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pp. 8117-8144. PMLR. 2023a.
Tsuchiya, T., Ito, S., and Honda, J. Best-of-both-worldd al- gorithms for partial monitoring. In Algorithmic Learning Theory, pp. 1484-1515. PMLR, 2023b.
Tsuchiya, T., Ito, S., and Honda, J. Stability-penale adaptive gellow-the-rguularizee--dddddd dependency, and sest-of-both-wool Advances in Neu- ral Information Processing Systems, 36, 2023c.
Sparsity, game-
Zimmert, J. and Lattimore, T. Connections hetween mirror descent, thompson sampling and the information ratio. Advances in Neural Information Processing Systems, 32,
2019.
Zimmert, J. and Marinov, V. Productive bandits: Impor- tance weighting no more. Advances in Neural Informa- tion Processing Systems, 37, 2024.
Zimmert, J. and Seldin, Y. Tsal An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49) 2021.
Zimmert, J., Luo, H., and Wei, C.-Y. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pp. 7683-7692. PMLR, 2019.
10

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
A. Details of FTPL Literature
While originally proposed by Hannan (1957), FTPL gained significant attention for its computational efficiency and simplicity after Kalai & Vempala (2005) introduced it in the context of linear optimization. These properties have made FTPL effective across various online learning and bandit settings, including combinatorial semi-bandits (Neu & Bartók, 2016), online learning with non-linear losses (Dudik et al., 2020), and MDP bandits (Dai et al., 2022). Although variants of FTPL have been developed improve computational efficiency by avoiding direct optimization, many either sacrifice theoretical performance compared to FTRLs or become computationally expensive when only partial information is available. For example, an earlier efficient FTPL algorithm was shown to suffer O(T2/3) regret (Awerbuch & Kleinberg, 2004), while another achieving O (TT KT log K) regret required ( numerical operations per round (Poland, 2005). This inefficiency in bandit settings comes from the nature of FTPL., which avoids explicit optimizations to compute importance weights in closed form. To address this issue, Neu & Bartók (2016) proposed GR in the line of combinatorial semi-banditss, whose reduction to MAB achieves OVK K) regret with O(K²) numerical operations per round. Further refinements by Honda et al. (2023) and Lee et al. (2024) showed that FTPL with GR achieve optimal O (VKKT) regret and even BOBW guarantees for MAB problems when using appropriately chosen perturbation distributions. However, in standard MAB problems, GR often incurs a higher computational cost than FTRL algorithms, despite FTRL requiring the solution of a convex optimization problem each round. This observation contrasts with combinatorial bandit settings, where GR was initially introduced, and motivates the design of more efficient resampling method for FTPL.
B. Proofs of Lemmas on Number of Resampling
In this section, we provide the proofs for Lemmas 1, 2 and 3.
For convenience of describing the conditions in the proof, we define an indicator function as
1, if = arg migg -
L4 rt//net.
(r,
0, otherwise.
Then, the condition (2) for termination in GR or CGR equivalent to Xt. (t, = 1, which we simply write as xe(r() 1.
B.1. Proof of Lemma
Lemma 1 (restated) Consider resampling of from 'D conditioned on A, until (2) is satisfied. Then, the number Me of resampling satisfies
P[A. Ln,
E BrENDIA, [M] Te]
Wt.b.
Proof. Consider the arm-selection probability wt,1, with the condition As. wt. can be expressed as
Wt,F. = Plxx(r)) = 1|2,, l.] =P(x)(rr)) 1|Ar, L., I.].[A. P(x(r)) = 1|48, Lu, [.JI[[AA) Tt).
Note that Ar is an arbitrary necessary condition for (x = 1, which implies that
Pix((()) 1|44, L. [,] 0.
Therefore, from (7) we have
W4.r, (r)) = 11,,, t.,, T.]P[A. It).
(8)
Now we consider the expected number of resampling Mr. Recall that rf is sampled from DD conditioned on A, until (2) is satisfied, that is, Xe(r() = 1. Then M, follows geometric distribution with probability mass function
P[M: mn/., M (1- (((x((r)) = 1|Ar, Lr. (
19- P(x(()))) = 1|A,, L. Tt).

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Therefore, the expected number of resampling given ig and expressed
B, 1:] Pix((r)) 1|A, L, Ld] n (1-1PP(x((r) P(xa(r() 1|A,, Les Lel m-1
= =P(x((r!) 1|. Les /ol/ ((xx(r))) 1| Los Lo,
= 11/Pix((1) 1|A Le
(9)
Combining (8) and (9), we obtain
PIA Li, IJ)
E B.AAII (y [d]
W1.1e
B.2. Proof of Lemma 2
Lemma 2 (restated) The sample ry obtained by Algorithm 3 follows the conditional distribution of D given A. [12, = max,o,sor, r. . In addition,
Pr 41 1//0,,
and the number Mr of resampling satisfies
By (iMill S log K + 1.
Proof.
Let [-] denote the probability distribution of rę after the malue-swapping operation. We have
P. Miaison (r's s aid E..
Σ p thoison (res S saj rhi S San rhn S Saj, Teg max rhes b It i0
fo:san
Phoison senny (ris s ait t/i s ar Th., Sas
t'. Les de r
rees (10)
Le d1
max zan
= max
co.son
So0
By the symmetry of r E [0, oo) K we have
r
max s0.50.,
The Le, Ie
-Prc..
max ré. Le Is s0r.0nn
(11)
for any j suth that o, 01. Then we have
1= P
U
fr's
reat in, to,
max
500
p rhe
max c0:5an
rhis Lu Is
jon, San
11, 1P
rh.
Té.s Le, ho,501
max
12

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
which means that (11) is equal to 1/0 Therefore, from (10) have
pa N
son tres
s ar}
Les 10
1
tre S ai), r/. s a4 r'e, S Eagp'ss
The re Lg) (12)
IP
max c0sson
01.
By symmetry, each probability term on RHS of (12) is equal. Therefore, we have
I N fre S a;} L.
P pP fre S sai Ap, L I1
which means that CGR samples ry from the conditional distribution of D given A (r'... max Tz,) Combining this fact with Lemma 1, for CGR I we have
1
EAA-DIA [M]
01, Wt.
Then, the expected number of resampling given L, in CGR I is bounded by
K
ErA-DIA, (yy.DIA,|MMoLL =
Σ
P(4 = [
[Mr 4e =
1=1
i=1
K
$ 1 +
dx
log
K +
B.3. Proof Lemma Lemma (restated) CGR II, ri follows the conditional distribution of D given A, in (3). addition,
(1-Fai, Pre-DAde Iel (1- FFFo, ((_ /o1
and the number M, of resampling satisfies
Ex.DD(MoLLi S log K + 1.
Besides, D is the Fréchet distribution with shape 2, then M2 satisfies
E BR. L,, 4] s 4
Proof. Recall that Do,, be the distribution of the maximum of o,, i.dd samples from D. whose cumulative distribution function is given by
F (x) = (F(z))""
Then, the probability density function of D..,, is expressed
(z) x 00, otherwise.
(o)(
0,
13

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Since r',,, is sampled from the truncated distribution of Pos, with support (mede. 20). it follows the probability density function
01 ( - (1- pos (neL..)): x (o). otherwise.
(0.
For any i # L that satisfies S o1e given r,,,, ar, rh is sampled i..d. from the truncated distribution of D with support [0, a1,)- Therefore, it follows the probability density function
f(z) f(z)/F(an)) x [0.
M(x;a1))
0,
otherwise.
Given La the joint probability density of rh,s for i satisfying o; S ot, is denoted by fk (s Then, for (01, 02 ak) we have
1 (k(am(dn)))) = f1. (arii (.be,))
II fila;ar,)
no S
01, f0 Iio f(a:)/ (1-))(1-F)))) (1-F01c (neL..))
if az, maxtor Og 01, 2 neLi,
0,
otherwise.
Let [-] denote the probability distribution of ra under the resampling method in CGR II. We have
Nuoison
Ir's s ai} Le le
ra;
fI. (n( dz7,
II So
f( (1 dzs
(13)
Tt, integralls
O1.
aas
f(z)
II Eo,501,
F(a; A A dz
1 por (eeten
01,
P Mioosso
fre aa) A Lg
(14)
1T (1eLe..))
Here, (13) is used as a distinct index from i, satisfying the constraint oy S Sar, Now we consider the probability of A r'.. max Son, Th,, 2 v.Le, given L, and 4, which is expressed
P[A. Lu,, Ie]
r(,,, = max Th 2 n n. Lne Te
t0,50n,
f(z)Fo1 (2)
100
Foi: (2) (2)
(1 polc (InLe..)) /or.
(15)
Combining (14) and (15), we have
P (r's S ai) AA Fre, Te
a-* N
tre S ai) L,
P[Ai|Le 11]
= =P(Nunso San fr', S asi
Aes Les Le
which means that CGR II samples r/ from D conditioned on A. = fris maxim Pess 2 m.nnn
14

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
The value of [ 1 is given in (15). According to Lemma for CGR II, My satisfies
For (mLL..))
BA 4]
01, We
where the equality holds if and only if G, cc.
Then, the expected number of resampling given L, in CGR II is bounded by
K
R BIAADIA [Molta] =
Σ
P( = il [u]] B BLNDDI [Mel le = i)
1=1
1 - por (ToLe.s))
Σ
W4,a"
o,wii
1
< 1 + }
dx
x
= log K + 1.
According to Lemma I, we have E, I = P[[A| Le, I.//ur,,- Therefore, to prove By>-DA,,Mll Ie =]
S V 4, we only need to show P[A,) F, 1 = 1// S
K V 4. See the proof in Appendix C.2.
C. Proofs of regret analysis
In this section, we provide the proof's for Lemmas and 7 the bias and the regret of CGR Il-biased.
C.1. Proof of Lemma 6
Before presenting the proof of Lemma 6, we first provide an explicit expression for the expectation of the loss estimates generated by CGR II, similar to the approach used in Lemma 4 of Neu & Bartók (2016).
Lemma 8. For all i [K] and such that Wei > the loss estimates of CGR Il satisfies that
1- (11-11-
E L E.
less
Pr 4 i)
Proof. In CGR II, the probability of pulling an arm i, denoted by qt.i. is given as
It. = P (x.)
= P )
= Le = -,
Wy,6 P(AL,, = i)
where the last equality follows from (8). Let My,5 denote the number of resampling for an arm i at round (. Then, we have
20
By~D|A,|M,, [
k(1
2,,1) (-,
90.s Σ
(k - G.)(1
*k, gr.i
k=1
k=G.
00
00
k(1 41,1) x-
qc.t 11 - (1- qc,1) Gr
Σ k=
(k: 11-G:)(1 - q(,1)* G 9e.b
x
1- (1 (r
(1 (1 (e.)) Gr) Σ
k(1 -1.)) h- 14-1
2t
Jt.i
A=1
By definition of Ee,t, we have
E l [r]
(M = (1 (1 -g..) )e.))
Me. E.,.B
15

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Lemma 6 (restated) The expected regret of FTPL with CGR satisfies
Ge
R(T)
E (b6, we e
Σ
E
1
W L, = i)
t=1
KE(K]
Proof. The overall proof is simple reduction of the results combinatorial semi-bandits (Neu & Bartók, 2016, Lemma 5) to MAB. By definition, we have for any [K]
B We, Cn. [t]]
i. Le, Le
Ge.
W2,i
Wr
befi
(by Lemma 8)
PP Le Ie === i)
Gea
We,i
Le,i
P((Ay) Le, =
GLi
Wei
2 Wr wed
(16)
PP(A.) Lr, le-
Then, by definition of RT)), we have
R(T) = Σ
(e,, Wi - c---
t=1
T
Ga.
(le - (ce,
+
Σ
E
Wtis
1
We,
(by (16))
4(
1=1
1=1
[
which concludes the proof.
C.2. Proof of Lemma 7
Lemma 7 (restated) When D is the Fréchet distribution with shape 2 and G2 = (K (KV44)log' logt, FTPL with CGR Il-biased satisfies
G.
ΣΣ KE[K]
E
Wz,s
1
Wr,i
S log
P(A
t=1
Proof. For notational simplicity, we denote show that for any N and i [K]
(P by IPA)))) this proof. Since (1 (1-x)) x²) S ear suffices
Wt.i P(A,,))
1 -
exp
G2
To this end, we address the term P(A..) and set appropriate Ge to establish a tight regret upper bound. We.s
By definition of Ar, when o; denotes the number of arms such that Less 5 Lr, it holds that
P(A..) 1 J
When D is Frécher distribution with shape 2, whose density and distribution functions are given as
-
f(x) z
and F(x) =
(17)
16

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
it holds that
2
0
P(A..)
23
exp
dz
M.i 1
dt
(by 1yy= =
0
exp
25,1
(18)
Now, let consider the lower bound W2 When >> O and Ar, dr i.., og 2 of have
1 )1,)
1
(z 21)
On the other hand, when 2 dr, and A S 2r,i have
4
2 212
sttdee )es)
2
21,
Therefore, obtain
1
exp
de
(z + 13
t + )1.) )2
(z + 21,13 )3
exp
(z + 21,1) )2
dz
jE(K
4(o;
1) K o. + 1
(2 + )3,13 exp
de
(z + ),,)) )
Ari
3(0,-1)+K''
exp
127,:
(19)
3(0, 1) + K
h(x) = - -e=#\//z Then, by combining (18) and (19), we obtain
- exp
P(Ar.))
X
3(0;
1) + K
<
di
1 - exp
3(0,- 11+,-1)+
12f
4h(x)
(20)
h(y)
where x = 0:/22,6 and 3(a;1))KK 422
Except the case o; = K = 2, we can see
3(0
1) + K K
47
and therefore
P(Ars)
4h(x)
sup
W4.s
0.y>0 Kx/1
h(y)
4h(x)
sup
#>0
h(Kxr44)
17

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
since hty) is decreasing. For K S 4, is bounded from above by since h(x) < h(Kx by 2 Kx/4. For K 2 4, have
4h(x)
e
sup 2>0 /KKx/4)
K sup a>0 1 c Rz/4
(21)
1 6 c Ka/4
K sup #>0
S K.
Kx/4
Finally, when 0, = K = y/r x- 5/8 holds. Since hyy) is decreasing, we again obtain
P(A.)) W2s 2>0 (5xz/8)
4h(x))
S sup
S 4.
Hence, for all / N and i E [K]. we obtain
P(Ars)
I K V
Wrii
This implies that for any G.
Σ
Wh,i Gr 5 Σ (P(r))))
Ge
Wee exp
Wt, Wrppexp exp
KV4
Gi (KV4
exp
(by E.
Therefore, setting G. (K V 4) log/ concludes the proof.
C.3. Proof of Theorem' 5
Theorem 5 (restated) FTPL with CGR H-biassd with learning rate тe c/vi for e O and maximum number of resampling G. (K 4) log satisfies that
0
VKT
KT
in adversarial bandits, in stochastic bandits,
R(T) <
0
Eigio
T
if the perturbation distribution 'D is the Fréchet distribution with shape 2.
Proof. The regret of FTPL with CGR Il-unbiased with Ge = (K V 4) log satisfies
T'
T
G.7
( (e, we - ext)
Wr
R(T)= <
R
E
We,i
(by Lemma 6)
P
t=1
1=1 iE(K]
<
I8 (le,w: ex + log T.
(by Lemma 7)
1=1
Let 2 JOGR and ?Ç denote the IW estimators of CGR Il-ubbiased and GR, respectively. By construction, E[ S E E| holds, allowing the first term on the RHS be directly bounded by the results for GR in Honda al. (2023). Further details on adversarial regret can be found in Lemma in Appendix D. For the stochastic setting, the analysis remains identical to the previous one, we refer readers to Honda et al. (2023, Theorem 2) for further details.
D. Improved regret analysis of CGR II
In this section, we formalize Remark by presenting an improved analysis of the adversarial regret for FTPL with CGR when the perturbation D follows the Fréchet distribution with shape parameter as detailed the following Theorem 10.
18

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
To understand how the transition from GR CGR II affects the regret analysis, we first introduce the necessary notations and summarize relevant prior results. With a slight abuse of notation, we define function @; for i [K] by
K
(A - S. (a
exp
dz.
2++
When D is Fréchet distribution with shape 2, whose density and distribution functions are given in (17), one can see that 6x (n,L,) W, holds. Let Φ (ø1, Φx) denote arm-selection probability vector. Then, the following result has been established.
Lemma (Overall results in Honda et al. (2023)). In adversarial setting, FTPL with GR, Fréchet distribution with shape 2, and learning rate Tue = c/ c/vifor for >> satisfies
1
V
R(T)=
S
E
Ces Wz+1 we)
Blret1
- 1241,]
91+1
T)
dependent term only on D. n12
stability
penalty
IF
lep W1+1- -wwl
3.7
VTT
V
c
c
T
3.7 V KT + V ( (le, Mln (0n((((t(tt + +()) + log(T + +1)
-
(22)
1=1
3.7 S 12ov7++
3.7)
VKT + log(( +1+ VTK
whose dominant term can be optimized as R(T) 117.8VT + O(VK + log when 0.42.
In the adversarial setting, the penalty term is bounded by 3.7 WTVKT/c, independent of the value of the cumulative loss estimator h,, as shown through worst-case analysis (see Honda et al., 2023, Lemma 9). In the derivation of (22), by definition of c. we have
Wt - W++1 = =(LL) S(1etLL4t))
Ll)L))) p(n++1 (L, +())
(nL()) o(n.lL. + +()) (ln + 2.) - (ln +2)),
which implies
T
Σ E 1 ((r, -
- = Σ E ( -oile +(m))++++)))]
T
Σ e (e +(0) o(n+1 +.))
Here, the second term is also bounded by log(T 1), regardless of the use of GR (see Lee et al., 2024, Lemma 8). Therefore, the transition from GR to CGR II affects the upper bound of the stability term, particularly when accounting for the variance of the IW estimator, which is related to the first term in (22). The following theorem, which formalizes Remark 3, shows that using CGR II can further improve the dominant term
Theorem 10 (Formal version of Remark 3). In adversarial setting, FTPL with CGR II, Fréchet distribution with shape 2.
and learning rate Tt- = c/Vit satisfies
R(T) S (IL50VT
3.7 e
V KT + log(T [T +1)+
V T
T
Whis
Wt,i
G.
P(A, 11 = i)
i [
whose dominant term can be optimized as R(T) 17.37
+ O(VK + log T) when 0.43 and G2 2 (K V 4) log
19

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
Note that the optimized of CGR II is greater than that of GR, shown in Lemma 9, implying that FTPL with CGR Il-unbaised can further improve the additive constant term.
Before the proof, we define another function introduced in Honda et al. (2023)
(,, = 1/- (2 21)a
K
exp
(z + 23)2
dz > 0,
(23)
which satisfies
(A 21,33
= - + 4l),(A).
(24)
Then, the following result was established.
Lemma 11 (Lemma 5 in Honda al. (2023)). If X is the o:-th smallest among Ai.... AK (ties are broken arbitrarity) then
(2((2)
1/O
(2
Proof of Theorem 10. As discussed above, it suffices show
T Σ [e((oo)(LL)) - o(n(le + (0)i{| < 11.5cv RKT.
Here, Honda et al. (2023) showed that their proof Lemma 7 that
(,(n) - (x((ch + ((..w,))e))))
Mnee + re;)dr
Ti,0(yp res)dr
(by (24))
< 6
(monotonicity of 4.,)
< 6n T a (p.
Here, the monotonicity of 7,,4 in its i-th element might not appear trivial. From the definition of in (23), can interpret this function arm-selection probability of FTPL when r; is of density of order (a Ax)* and rys for * follows the Fréchet distribution with shape 2. Therefore, Ia, is monotonically decreasing with respect to the i-th argument.
Under CGR II, we obtain
2 Le, Ie = Var Wi,
E
W Wile
Li Ie
+ E² Wi,1e
Le, Is
2
w2.1.
We,,, (At))
Recall (20), which shows
P(A.))
4h(x)
Wt.i
h(y))
where ((x)) 1-e" and = 3(a, 11+
One can see that for any E [K] and K 2
x.-
4x
y/
3( 1)
K
K
40;
0,
Following the same arguments in (21), we have
PP P(Ac.))
4h(x)
4h(x))
4K
< sup
h(v)
h(KK/// /
a>0
20

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
which implies
1
E Wtle
Le, Ie
(2
1
P(A,)
4K wii
4k
Wi.
Since l (Le,0077 ) when Ie we obtain
E (( S. (n + +Zi)//an
3 x(4: i Sniee,ili,a (T
)
Le
I B E
2 1K
P.c
wg.
lg R.I Le
= B
2 4K
(by (24))
Te (ee.)
< B
2
L
(: C. E [0.
4K
(17 Le,i)
3V 1E
2
voi
(by Lemma 11)
Voi
4K
Therefore,
E3 ((. o(n(le +()l)
3V
K
2
Voi
1/t
Vor
4K
1=1
K
3
(f/*t
x/12
$ 33/Mm
14
x 1/2 dz
2 11
dr
11
4K
VK
-3 K -
1) 1)
v TT/
4
I 2T VKn.
By taking summation with 7/. = c/vl, we have
Σ 1 -ott) (1))) x
TT
4
VE
23 23 TC
< 2
VKT,
which concludes the proof.
E. Details and Additional Results of Experiments
In this appendix, we firstly describe the details of stochastic setting and stochastically constrained adversarial setting (or adversarial setting in short), and then provide results of additional experiments to complement those presented in Section 5,
E.1. Details of Settings
In our experiments for both settings, the losses of each arms follow the Bernoulli distributions, and we exclusively consider the case where the suboptimality gap A 0.125. For the stochastic setting, which is implemented for the experiments shown in Figures 4, 5, 6, 8c and 8d, the mean losses decided (1 A)/2 for the single optimal arm and (1 + 2 for the other suboptimal arms.
For stochastically constrained adversarial setting, which is implemented for the experiments shown in Figures 2, 3, 8a and 8b, the mean losses for the single optimal arm and the suboptimal arms switch between (1 A, 1) and (0, A), with the duration of each phase growing exponentially by a factor of 1.6 after every switch. Both settings are similar to those in Zimmert & Seldin (2021).
21

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
FTPL GR
FTPL CGR I
10
FTPL CGR II-U
FTPL CGR
T-INF IW
T-INF RV
TS-Prod
10
10
10"
FTPL GR
FTPL CGR
FTPL CGR II-U
FTPL CGR 11-B
16
32
64
112
128
Figure Number of resampling for stochastic setting, K 32. Figure 5. Runtime (sec) for stochastic setting and different K.
E.2. Additional Results
Consistently with the experiments in Section 5, the results of 100 trials shown in this appendix. Figures 4 and show the results of the number of resampling and runtime for stochastic setting. Figures and show the regret performance for stochastic setting and that for adversarial setting, respectively. Note that we include the results both of FTPL CGR II-B and FTPL CGR II-U to explicitly demonstrate their empirical indistinguishabiiiy,, as discussed in Section
The results for stochastic setting lead the similar conclusions to those for the adversarial setting, that is, FTPL CGR only effectively controls the number of resampling and significantly improves the runtime, but also achieves the better empirical regret performance, which seems be due to the reduced variance of the loss estimator. In addition, Figure 8 provides a visualization of the average and maximum number of resampling at each round over 100 trials for both settings, as complement to the overview shown in Figures and 4. We can see that, under all the variants of FTPL CGR, the number of resampling at each round is stably controlled at significantly low value, which is particularly pronounced for FTPL CGR Il. Another interesting observation from Figures 8a and &c is that, for FTPL GR and FTPL CGR the average number of resampling fluctuates within range throughout the horizon, whereas that for FTPL CGR tends to gradually reduced as the round progresses, seemingly due to the widening gap of the cumulative estimated losses between the arms.
22

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
FTPL GR
FTPL
600
FTPL CGRI
FTPL CGR
FTPL CGR II-U
1000
FTPL CGR II-U
500
FTPL CGR II-B
FTPL CGR II-B
T-INF IW
800
T-INF
T-INF RV
T-INF RV
400
TS-Prod
TS-Prod
600
300
400
200
200
100
2500
5000
7500
10000
2500
7500
10000
(a) K
(b) 32
Figure Pseudo regret in stochastic setting.
FTPL GR
FTPL GR
600
FTPL CGRI
FTPL CGR
FTPL CGR II-U
1000
FTPL CGR II-B
FTPL CGR II-B
500
T-INF IW
T-INF IW
800
T-INF RV
400
TS-Prod
PS-Prod
600
300
400
200
200
100
2500
5000
7500
10000
2500
5000
7500
10000
(a) K =
8
(b) K
32
Figure 7. Pseudo regret in adversarial setting.
23

---

GR in Nearly Linear Time for FTPL with BOBW Guarantee in Bandit Problems
FTPL GR
FTPL CGR
FTPL CGR II-U
FTPL CGR Il-B
2000
4000
6000
8000
0000
(a) Average, adversarial setting.
10
10'
10a
10
10
2000
4001
6000
8000
0000
(b) Maximum, adversarial setting.
2000
4000
6000
8000
1000
(c) Average, stochastic setting.
2000
4000
6000
8000
0000
(d) Maximum, stochastic setting.
Figure 8. Average Maximum number of resampling each round for K 32.
24


Reviews:
[{"review_id": "ck56MVXSzm", "reviewer": "Reviewer_sBDa", "summary": "The paper proposes Conditional Geometric Resampling (CGR) to improve the computational efficiency of the Follow-the-Perturbed-Leader (FTPL) algorithm in the multi-armed bandit problem.\nBy introducing a carefully selected, necessary stopping condition in the resampling process, CGR reduces the expected computational complexity of standard Geometric Resampling from the quadratic $O(K^2)$ expected per-round time to the near-linear $O(K \\\\log K)$ while guaranteeing the same best-of-both-worlds regret guarantees from Honda et al. (2023) and Lee et al. (2024).\nMore precisely, three variants of CGR are introduced: CGR I, CGR II-unbiased, and CGR II-biased.\nThese variants offer different trade-offs between computational efficiency and estimation bias.\nThe authors provide both theoretical regret bounds and experimental results that demonstrate lower runtime and improved regret performance compared to previous approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback on our work. We have addressed your questions and comments below.\n\n**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?**  \n**A1.** The main technical difficulties in constructing the Reduced-Variance (RV) estimator for FTPL with GR are as follows:\n\nThe 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). \n\nMoreover, 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.\n\nJulian Zimmert and Yevgeny Seldin. \"Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits.'' JMLR, 2021.\n\nTiancheng 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.\n\nTaira Tsuchiya, Shinji Ito, and Junya Honda. \"Best-of-Both-Worlds Algorithms for Partial Monitoring.'' ALT, 2023.\n\n**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?**  \n**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$.\nWe 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\n\n**Q3. Assumption on the losses in the adversarial setting: we may assume they depend on $(I_1,\\ldots, I_{t-1})$.**  \n**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.\nStill, 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).\nWe will modify the writing accordingly.\n\nRaman Arora, Ofer Dekel, and Ambuj Tewari. \"Online bandit learning against an adaptive adversary: from regret to policy regret.'' ICML, 2012.\n\nJulian Zimmert and Yevgeny Seldin. \"Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits.'' JMLR, 2021.\n\n**Q4.**  \n- **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.** \n- **Theorem 5 seems more of a remark than an actual theorem.**\n\n**A4.** We sincerely appreciate your helpful suggestion. We will modify the notation accordingly to improve clarity.\n\n**Q5. In Section 5, it would be clearer to also specify how the confidence intervals around the curves were chosen (e.g., standard deviation?).**  \n**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.", "claims_and_evidence": "The theoretical claims are clearly stated with complete proofs.\nThe claims on the empirical performance are also validated by appropriate experiments.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, with more focus on the proofs of claims relative to the number of resampling iterations.", "experimental_designs_or_analyses": "My main concern about experiments is the omission of FTPL CGR II-B from the experiments other than the number of resampling.\nThe reason provided by the authors is because the number of resampling is essentially indistinguishable from that of FTPL CGR II-U, and so the other experiments only consider the latter algorithm.\nHowever, it would still be interesting to observe whether the performance is indistinguishable with respect to other performance metrics too (at least for the experiments performed in this work).\nFor instance, the indistinguishability seems to appear for large enough $K$, e.g. $K \\\\ge 32$, but the first experiment measuring the cumulative regret considers $K = 8$.", "relation_to_broader_scientific_literature": "The adoption of FTPL with geometric resampling to achieve best-of-both-worlds regret guarantees for multi-armed bandits has alredy been considered by previous work.\nThe main contribution of this paper lies in the design of more clever conditional geometric resampling procedure that employ a carefully chosen necessary stopping condition.\nThis allows an improved computational complexity with respect to other algorithms that achieve a similar regret performance.\nThe authors are clear in the comparison with the main related work.", "essential_references_not_discussed": "The authors seem to have covered the essential related work in their discussion.", "other_strengths_and_weaknesses": "The main techincal contribution is the design of variants of and the consequent improvement in the computational complexity of FTPL while preserving BOBW guarantees.\nRegarding the regret analysis per se, there seems to be no significant difference compared to prior work.\nNevertheless, the time performance is also a relevant factor in practice and the contribution in this direction is interesting.", "other_comments_or_suggestions": "- In the Problem Setup section, you define losses $\\\\ell_t$ in the adversarial setting as being possibly functions of the history of losses and chosen arms, but it seems that you may assume they depend on $(I\\_1, \\\\dots, I\\_{t-1})$ w.l.o.g.\n- 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.\n- Theorem 5 seems more of a remark than an actual theorem.\n- In Section 5, it would be clearer to also specify how the confidence intervals around the curves were chosen (e.g., standard deviation?).", "questions_for_authors": "- 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?\n- 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YoaaI5Ch8Q", "reviewer": "Reviewer_JGty", "summary": "The paper proposes a new estimation procedure based on conditional resampling to improve both theoretically and empirically the sample efficiency of FTPL while maintaining the regret guarantees.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We have addressed your question below.\n\n**Q1. How would the analysis change in the proposed sampling approach when extending from bandits to semi-bandits?**  \n**A1.** \nThe 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. \nStill, their results are only for near-optimal regret bound in the adversarial setting, and extending the BOBW analysis to semi-bandits is significantly difficult.\nIn 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}$.\nThus, the expression of $w_{t,i}$ significantly impacts the regret analysis.\nIn 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.\nAs a result, several techniques used in Honda et al. (2023) and Lee et al. (2024) become no longer applicable.\nIn 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.", "claims_and_evidence": "Claims are supported by clear evidence.", "methods_and_evaluation_criteria": "Evaluation criteria and methods make sense.", "theoretical_claims": "I have not checked the correctness of proofs.", "experimental_designs_or_analyses": "I checked all experimental designs and they look valid to me.", "relation_to_broader_scientific_literature": "The paper presents a significant result in FTPL literature.", "essential_references_not_discussed": "Prior work discussion seems extensive.", "other_strengths_and_weaknesses": "The conditional resampling is a refreshing idea to overcome potential computational issue in FTPL.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "How would the analysis change in the proposed sampling approach when extending from bandits to semi-bandits?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VN7iL82rdI", "reviewer": "Reviewer_tSdm", "summary": "This paper studies FTPL for MAB problem. The authors first propose a general receipe for designing loss estimate procedure. Then they also give several concrete variants under this framework and shows that they enjoy certain improved time complexity while maintain the optimal BOBW guarantee. These theoretical findings are complemented by comprehensive numerical results. The proposed CGR I and II both bring improved empirical time complexity and regret compared to the conventional GR.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We have addressed your question below.\n\n**Q1. Any intuitions for why the new proposed scheme would give better empirical regret?**  \n**A1.**\nGenerally, 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. \nSince 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). \nTherefore, 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the main body which looks good to me.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "potential audience: people studying bandits/RL/stats", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths\n\n1. Gives a new framework for loss estimate in FTPL.\n\n2. Supporting empirical results.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1. any intuitions for why the new proposed scheme would give better empirical regret?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tyrvgw0Gah", "reviewer": "Reviewer_tXhY", "summary": "The paper proposed some useful variants of the Geometric Resampling (GR) algorithm called Conditional Geometric Resampling (CGR) and those algorithms improve the sample complexity from O(K^2) to O(Klog(K)) in each round while keeping the BOBW guarantee for a certain perturbation distribution. The experiment result shows the proposed algorithms do perform well in the sample complexity and runtime while keeping a low regret while keeping the BOBW guarantee for a certain perturbation distribution.\n\n## update after rebuttal\nI thank the authors for the response. Nothing major has changed, and I keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We have addressed your question and comment below.\n\n**Q1. Are there any disadvantages of CGR to the other algorithms (such as Tsallis-INF)?**  \n**A1.** \nGenerally, 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.\n\nAlthough 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.\n\n**Q2. Novelty of the regret analysis.**  \n**A2.** Thanks for your comment. The main novelty in the regret analysis lies in the analysis of CGR II-B.\nThe 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.\nBy deriving a lower bound on $w_t/P(A_t)$, we obtained the desired result even with a smaller maximum number of resampling.\nWhile 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.", "claims_and_evidence": "Yes, they claim the CGR algorithm has a great improvement compared to the GR algorithm and the experiments do show the improvement for runtime and sampling time.", "methods_and_evaluation_criteria": "Yes, the paper says the reason that CGR achieves success is that CGR resamples the perturbation only from those satisfying a necessary condition for termination, and that makes sense.", "theoretical_claims": "Yes, such as Theorem 6.", "experimental_designs_or_analyses": "Yes, I checked Section 5.", "relation_to_broader_scientific_literature": "The paper proposed an experimental beneficial algorithm CGR and its method might have chances to be applied to other time-cost algorithms.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "The proposed algorithms greatly improve the sample complexity and runtime from previous GR algorithm.", "other_comments_or_suggestions": "Could you discuss more about the novelty of the proof of those regret theorems? It is unclear what technical contributions this paper adds.", "questions_for_authors": "Are there any disadvantages of CGR to the other algorithms (such as Tsallis-INF)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies a novel loss estimation procedure for FTPL in multi-armed bandits called Conditional Geometric Resampling (CGR).

While FTPL offers no direct advantage in terms of memory or computational complexity for multi-armed bandits, the techniques of this paper likely apply to problem settings where FTPL is computationally more attractive than FTRL. All reviewers agree that this is a solid contribution which is of interest to the community.
Decision: Accept (poster)