Follow-the-Perturbed-Leader Achieves
Best-of-Both-Worlds for Bandit Problems
Junya Honda (Kyoto Univ. / RIKEN)
Shinji Ito (NEC)Taira Tsuchiya (Kyoto Univ. / RIKEN)

ALT2023, Singapore
February 22th, 2023

1 / 15

K -armed Bandit Problems• Model of a gambler pulling arms of K slot machines sequentially.
• At each round t = 1, 2, . . . , T :• The environment sets loss ℓt = (ℓt,1 , . . . , ℓt,K ) ∈ [0, 1]K ofarms.
• The player pulls an arm It ∈ [K ] = {1, 2, . . . , K }.
• Loss ℓt,It only for the pulled arm is observed.
• (Pseudo-)regret: Gap of the cumulative loss compared with i ∗ :Regret(T ) = E" T
Xℓt,It −

t=1

T
X
t=1

#
ℓt,i ∗ , i ∗ ∈ argmin E
i∈[K ]" TX#ℓt,i ∗ .

t=1• Goal: minimize the regret.

2 / 15

Settings of Environments• Adversarial setting:• Loss is determined by an (adaptive) adversary.
√• Lower bound: Regret(T ) ≥ O( KT )• Stochastic setting:• Loss ℓt,i ∈ [0, 1] from arm i is i.i.d. from unknown Pi .
P
• Lower bound: Regret(T ) ≥ O( i̸=i ∗ log T /∆i ) whereµi = EX ∼Pi [X ], ∆i = µi − minj∈[K ] µj .
• A Best-of-Both-Worlds (BOBW) policy:• A policy simultaneously achieving both bounds

3 / 15

Follow-The-Regularized-Leader (FTRL)• Pulls an arm randomly from wt = (wt,1 , wt,2 , . . . , wt,K ) forno⊤wt = argmin w L̂t + ϕ(w )/ηt .
Pt−1

w ∈PK

• L̂t = s=1 ℓ̂t ∈ RK : unbiased cumulative loss estimator• ϕ(·) ≥ 0: regularization function• ηt : learning rate
∑

α

i wi
• Tsallis-INF [Zimmert+2021]: Tsallis-entropy ϕ(w ) = 1−1−αwith learning rate ηt = O(t −1/2 ).
• Achieves BOBW property.
• Optimization with roughly O(K ) complexity• Becomes problematic for, e.g., combinatorial bandits.

4 / 15

Follow-The-Perturbed-Leader (FTPL)• Generates a random perturbation vector rt ∈ RK .
• Pulls the arm minimizing the perturbed estimated loss:
It = argmin{L̂t,i − rt,i /ηt }.
i∈[K ]• Gumbel distribution for rt reproduces EXP3 [Auer+2002].
• No distribution reproduces Tsallis-INF [Kim+2019].
√• Conjecture: if FTPL achieves O( KT ) regret then theperturbation distribution would have Fréchet-type tail(that is, not Gumbel/Weibull-type tail).
√• We derive O( KT ) bound for Fréchet distribution(⊂ Fréchet-type tail).

5 / 15

FTPL with Geometric Resampling (GR)• Typical loss estimator: Importance-Weighted (IW) estimator(−1ℓt,i wt,i
i is pulled,ℓ̂t,i =
0otherwise.
• wt,i is not computed in FTPL.
−1• Geometric resampling [Neu+2016]: unbiased estimation of wt,i.
• Used technique: if the success prob. of a trial is pthen the expected # of trials until success is 1/p.

/ O(K ) complexity: seemingly worse than FTRL
, Optimization-free, no need to store w
2t(potential applicability to combinatorial settings?)

6 / 15Main Result
Theorem 1 (BOBW Property of Fréchet FTPL)
Under FTPL with Fréchet distribution (shape α = 2), learning rate√
ηt = c/ t and GR,(√√
23c + c4
KT + o( KT )(adversarial),
Regret(T ) ≤P log T1 2∗
(4c + c )i̸=i ∗ ∆i + o(log T ) (stochastic, unique i ).
√• First result to show O( KT ) regret of FTPL.
• Constant factors are large (particularly for the stochastic case).
−1• 4c is improved to 2c if we exactly compute wt,i
without GR.

7 / 15

Analysis of FTRL and FTPL
• Regret is usually decomposed into two terms:• Penalty term: greediness for the estimated loss
• Stability term: how stably the policy (or wt ) behaves• Hard to analyze the stability of FTPL due to complicated wt .
• Arm-selection probability of FTPL: wt,i = ϕi (ηt L̂t ) forZ ∞ϕi (L) =
0

X
1
2
exp
−
3
(z + Li )(z + Lj )2
j

!
dz,

L ∈ [0, ∞)K .

• Comes from the joint density of Fréchet RVs.
(For simplicity minj Lj = 0 is assumed w.l.o.g.)

8 / 15

Stability Analysis of FTPL
• The stability term is roughly bounded by
" T
#
E
XD
Stability = Eℓ̂t , wt,i − wt+1,i
t=1

≲

T
X
t=1



ηt E 

X ϕ′ (ηt L̂t )ii∈[K ]ϕi (ηt L̂t ),where ϕ′i (L) =

∂ϕ(L)
.
∂Li

• Ratio between ϕi (L) and ϕi′ (L) is important (“hazard rate”):• [Abernethy+2015] uniformly bounds ϕ′i (L)/ϕi (L):√
Leads to a loose regret bound of O( KT log K ).
• [Bubeck2019] discussed that ϕ′i (L)/ϕi (L)3/2 = O(1) is√
suﬃcient for O( KT ) bound: diﬃcult to show unlike FTRL.
9 / 15

Key Finding
Lemma 2 (informal)
Under Fréchet FTPL, for any L ∈ RK , if Li is the σi -th smallest thenpϕ′i (L)≤ O( 1/σi ).
ϕi (L)• Technical tool: monotonicity analysis by the technique ofsymmetric polynomials.
• Heavily depends on the form of the Fréchet distribution.
• Unclear on the extension to other perturbations.
√• O( KT ) adversarial bound is immediate from this lemma.

10 / 15

Transformation into a Stochastic Bound for FTRL
• Self-bounding technique [Zimmert+2021]: Typical tool fortransforming the adversarial bound into the stochastic bound.
• Key argument: wt results in regret increases ofPp• at most O
w
/t
,
∗
t,i
i̸=i
P
• at least i̸=i ∗ wt,i ∆i .
• Worst case of {wt }Tt=1 without contradiction: wt,i = O( t∆1 2 )
P
P
 i
PT 1 log T→ Regret(T ) ≤ O=O.
i̸=i ∗
t=1 t∆ii̸=i ∗ ∆i

11 / 15

Transformation into a Stochastic Bound for FTPL
• Hard to apply the same discussion.
• Can still derive some bounds depending on event
At = {estimated losses L̂t,i for i ̸= i ∗ are large enough}:• If At holds (well converged) then the regret increase isPp• at most O
w
/t
,
∗
t,i
i̸=i
P
• at least i̸=i ∗ wt,i ∆i .
• Otherwise (not converged):p• at most O( K /t),
• at least O(mini̸=i ∗ ∆i ).
• Taking the worst case on {(wt,i , 11[At ])}Tt=1 :!
X log T
Regret(T ) ≤ O
.
∆
i
∗
i̸=i
12 / 15

Comparison with Other Policies (1/2)
Consider Fréchet FTPL with IW estimator and• GR: Geometric resampling,d−1• GR10: GR is run 10 times (x10 smaller variance of wt,i ), almost
equivalent to exact computation of 1/wt,i .
Compared with:• Thompson Sampling (TS): designed only for the stochastic case.
• Tsallis-INF (T-INF) with two loss estimators:• Importance Weighted (IW) estimator (same as FTPL),• Reduced Variance (RV) estimator (not applicable to FTPL).
Environments: 8-armed Bernoulli bandits under• Stochastic setting,• Stochastically constrained adversarial setting.
13 / 15

Comparison with Other Policies (2/2)

Stochastic

betterAdversarial• FTPL GR10 performs similarly to Tsallis-INF IW (as expected).
d−1• FTPL GR performs a little worse due to the variance of w.
t,i• Tsallis-INF RV performs much better.
• Thompson sampling only works for the stochastic case.
14 / 15

Conclusion√• Showed that FTPL with Fréchet perturbation achieves O( KT )P
adversarial regret and O( i̸=i ∗ log∆iT ) stochastic regret.
• The constant factors in the bounds are large.
• Smaller variance of ℓ̂t leads to better performance.

Future directions:• General suﬃcient conditions on the perturbation distribution to√achieve O( KT ) regret.
• Extension to other (especially combinatorial) settings.
• Adversarial: maybe possible but still nontrivial.
• BOBW: diﬃcult since known FTRLs use hybrid regularizers.
• Loss estimators with small variances.
15 / 1516 / 15

Eﬀect of Parameters and Variance Reduction

Stochastic

betterAdversarial• Parameter c controls the learning rate:• Small c: stably explores arms,• Large c: aggressively exploits seemingly good arms.
• Recommended c from the regret bound: around 0.2–0.5.
• Performs much better for 1.0–2.0.
• Theoretically suggested c makes the policy too stable.
• Suggests looseness of the analysis on the stability.
17 / 15