arXiv CSopen access

Vanishing L2 regularization for the softmax Multi Armed Bandit

Vanishing L2 regularization for the softmax Multi Armed Bandit

Ştefana-Lucia Aniţa * 1 Gabriel Turinici * 2

arXiv:2605.03752v1 [cs.LG] 5 May 2026

Abstract

and investigate both theoretical convergence and numerical performance.

Multi Armed Bandit (MAB) algorithms are a cornerstone of reinforcement learning and have been studied both theoretically and numerically. One of the most commonly used implementation uses a softmax mapping to prescribe the optimal policy and served as the foundation for downstream algorithms, including REINFORCE. Distinct from vanilla approaches, we consider here the L2 regularized softmax policy gradient where a quadratic term is subtracted from the mean reward. Previous studies exploiting convexity failed to identify a suitable theoretical framework to analyze its convergence when the regularization parameter vanishes. We prove here theoretical convergence results and confirm empirically that this regime makes the L2 regularization numerically advantageous on standard benchmarks.

The outline of the work is the following : we recall some results from the literature in this section and introduce the main notations in Section 2. We state the convergence results in Section 3 which are then illustrated numerically in Section 4. Finally, Section 5 is devoted to concluding remarks and the Appendix contains all the proofs and further numerical results. 1.1. Brief literature review Policy gradient algorithms have achieved notable success across various reinforcement learning applications and have been adapted to ensure stable convergence. Prominent examples include the log-barrier penalized REINFORCE algorithm (Zhang et al., 2021), trust-region policy optimization (TRPO) (Schulman et al., 2015), and proximal policy optimization (PPO)—OpenAI’s standard reinforcement learning framework. All of these methods employ regularization techniques to constrain policy updates and enhance learning stability. In this work, we explore an alternative regularization approach, focusing on its application within the Multi-Armed Bandit (MAB) framework.

1. Introduction Backed by efficient practical achievements in diverse domains such as video games (Mnih et al., 2015), game playing (e.g., Go (Silver et al., 2016)), conversational AI (e.g., ChatGPT (OpenAI, 2024)), recommender systems (Afsar et al., 2022), wifi antenna placement (Boldrini et al., 2018), autonomous driving (Bojarski et al., 2016) and healthcare (Yu et al., 2021; Gottesman et al., 2019), Reinforcement Learning (RL) algorithms emerged as promising field of ongoing research. Among the various frameworks within RL, the Multi-Armed Bandit (MAB) model (Chu et al., 2011; Slivkins, 2019) stands out for its extensive use in both theoretical analysis and practical applications.

Although policy gradient algorithms perform well empirically, their theoretical convergence properties for MABs have only recently been clarified. Fazel et al. (Fazel et al., 2018) established high-probability convergence results for stochastic gradient methods in linear quadratic regulator problems. Building on this, Agarwal et al. (Agarwal et al., 2020) analyzed convergence within a general Markov process framework and, for the softmax parameterization studied here, considered three approaches: basic policy gradient descent, entropy-regularized policy gradient, and the natural policy gradient method, proving global optimality for the latter. Still in the context of entropy-regularized multi-armed bandits, Ding et al. (Ding et al., 2025) establish global convergence guarantees for entropy-regularized softmax policy gradient methods using (nearly) unbiased stochastic estimators, while Aghaei (Aghaei, 2025) studies convergence in bandit and tabular MDP settings and characterizes when convergence holds under linear function approximation. In contrast, our analysis focuses on the softmax parameterization with L2 regularization for which only a recent work

Our attention is directed toward a specific procedure, the softmax parameterized policy gradient, cf. (Sutton & Barto, 2018) (Sect. 2.8 & Chap. 13). But, distinct from this standard setting, we also include L2 regularization on the preference vector (see notations in the following section) 1 CEREMADE, Université Paris Dauphine - PSL, CNRS, Paris, France 2 ‘Octav Mayer” Institute of Mathematics of the Romanian Academy, Bd. Carol I 8, Iaşi 700505, Romania . Correspondence to: Gabriel Turinici <[email protected]>.

Preprint. May 6, 2026.

1

Regularized policy gradient for MAB

(Aniţa & Turinici, 2024) is available when regularization parameter is large enough to ensure convex functional. This precludes the interesting case of vanishing regularization parameter, the only one that can convergence to the optimal solution.

ization component follows a step-size schedule that does not necessarily fit within this framework, see Theorem 3.9 for details. More precise analyses are available when the criterion is convex, see (Kassing et al., 2025) or when the regularization is entropic (Weissmann et al., 2025). These studies show that when the regularization coefficient decreases sufficiently fast, the asymptotic behavior of the algorithm coincides with that of the unregularized case. From a practical point of view, introducing a time-dependent quadratic penalty can stabilize the early stages of optimization while maintaining asymptotic unbiasedness. More recent analyses, such as the work of Bach (Bach, 2015), further emphasize the connection between decaying regularization, stability, and the adaptive properties of averaged SGD in locally strongly convex settings. But applying these general results to Multi Armed Bandit requires some assumptions which are not always satisfied in our setting.

Also recently, Bhandari and Russo (Bhandari & Russo, 2024) examined the softmax parameterization under an idealized policy gradient scheme assuming exact gradient evaluations. Here, we instead investigate the more practical case of stochastic (approximate) gradients, under slightly stronger assumptions. Additional related studies include (Wang et al., 2019), which explores deep neural network parameterizations, and (Zhang et al., 2020), which proposes a Monte Carlo variant with random roll-out horizons for infinite-horizon discounted problems. In a series of recent works, Mei et al. (Mei et al., 2020; 2023) further advanced this line of research by showing that exact-gradient policy gradient methods with softmax parameterization converge at a rate of O(1/t), and that entropy regularization can accelerate convergence. They also show that, at odds with common lore, the stochastic gradient can converge for MAB even for a constant learning rate albeit at the price of having an important number of iterations (see also the comments in (Baudry et al., 2025)). However, their analysis relies critically on the assumption that the reward distribution is bounded—an assumption we do not make in our work. Furthermore, their framework does not account for the presence of L2 regularization, which is a key component in our setting.

Indeed, convergence results for SGD, such as those in (Chen, 2002) (Thms. 1.2.1 and 1.3.1), rely on several hypotheses, e.g. the uniqueness of the critical point (which does not hold here), boundedness conditions (the optimal preference vector is unbounded when regularization is not present) or the existence of a suitable Lyapunov function (the standard one degenerates in this setting) and boundedness of trajectories (Mertikopoulos et al., 2020). Despite these challenges, our approach still builds upon this theoretical foundation, combining estimates and results from prior literature that, to our knowledge, have not yet been applied in this specific context. We are therefore able to obtain first, state of the art, results for the convergence of the L2 regularized softmax policy gradient with vanishing regularization parameter.

From a broader theoretical perspective, our analysis focuses on softmax-parameterized policy gradients with L2 regularization. We build on arguments similar to those used in establishing the convergence of general stochastic gradient descent (SGD), starting with the classical work of Robbins and Monro (Robbins & Monro, 1951). A comprehensive reference on this topic is provided in (Chen, 2002), see also (Fehrman et al., 2020; Mertikopoulos et al., 2020) for recent contributions including non-convex objectives.

2. The L2 regularized softmax parameterized policy gradient Multi Armed Bandit The Multi Armed Bandit problem in the formulation of (Sutton & Barto, 2018), involves a choice among k alternatives called ’arms‘ and indexed by

Classical results on stochastic approximation also provide a rigorous foundation for the analysis of stochastic gradient descent (SGD) algorithms with time-varying perturbations. Early work by Blum (Blum, 1954), and later extensions by Borkar et. al. (Borkar, 2008)(Chap. 2), (Borkar et al., 2025) and Kushner and Yin (Kushner & Yin, 2003)(Chap. 5), establish almost sure convergence of iterative methods subject to diminishing step sizes and vanishing regularization terms. Further results are available when the gradient is perturbed by a bounded term, see (Ajalloeian & Stich, 2021); in our case the perturbation is the gradient of the L2 regularization term which is not a priori bounded. Moreover the regular-

a ∈ [k] := {1, 2, . . . , k}.

(1)

When chosen, each arm a gives rewards sampled from some reward distribution R(a); we introduce the notation for the average of the distribution corresponding to arm a: q∗ (a) := E[R(a)], ∀a ∈ [k].

(2)

For instance, reward can be sampled from a normal variable with mean q∗ (a) and variance σ(a)2 = 1, but we allow for more general choices (see Section 4.3). The choice selected at time step t is denoted At and the reward Rt ∼ R(At ) is 2

Regularized policy gradient for MAB

sampled from the distribution R(At ) associated with arm At . The objective is to maximize the average reward.

gradually diminish the impact of regularization and to find a solution of the original problem of maximizing L0 .

We will denote

We first recall known results that allow to see update formula (8) as a stochastic gradient ascent algorithm à la Robins and Monro (Robbins & Monro, 1951). The reward Rt represents the consequence of choosing arm At and this choice is independent of Ft but depends on Ht through ΠHt . Chronologically, the choice At is made between time t and t + 1. Denote Ft the filtration constructed with information available up to time step t. It is known that (see (Sutton & Barto, 2018)) :

Pk = {Π ∈ (R+ )k :

X

Πa = 1},

(3)

a∈[k]

the set of all probability distributions with outcomes in [k]. The softmax policy gradient algorithm works with a ’preference vector’ H ∈ Rk that, through the softmax mapping : ΠH (a) = P

eH(a) , H(b) b∈[k] e

(4)

E[Rt 1a=At |Ft ] = q∗ (a)ΠHt (a), ∀a ∈ [k], E[1a=At |Ft ] = ΠHt (a), X E[Rt |Ft ] = ΠHt (a)q∗ (a) = L0 (Ht ).

creates a distribution ΠH ∈ Pk from which the choice is made. Here, when the preference vector is H, the probability to choose arm A is ΠH (A). To this classical framework we add L2 regularization so that finally the goal is to find the H ∈ Rk solution to : maximizeH∈Rk Lγ (H), 1

with Lγ (H) := EA∼ΠH

i γ R(A) − ∥H∥2 . 2

(11)

a

As is standard we assume from now on that :2 there exists a constant Cm > 0 such that :

(5) h

(9) (10)

E[R(a)2 ] ≤ Cm , ∀a ∈ [k].

(6)

(12)

We also assume that γt is a deterministic function of the time t (all that follows also works for non-deterministic choices independent of Ft under mild additional assumptions). We use the notations (see Equation (8)) :

The parameter γ ≥ 0 is the L2 regularization coefficient; in particular L0 (H) := EA∼ΠH [R(A)] . (7) When the dependence of γ is not important we will only write L(H) instead of Lγ (H). The difference with the classical MAB (Sutton & Barto, 2018)(Sect 2.8) lies in the presence of the regularization γ2 ∥H∥2 . Assuming possible dependence of γ on the index t, problem (5) is solved using a stochastic gradient ascent algorithm :

ut (a) := (Rt − R̄t )(1a=At − ΠHt (a)),

(13)

gt (a) := ut (a) − γt Ht (a).

(14)

With these notations, we recall that (Sutton & Barto, 2018): E [ ut | Ft ] = ∇H L0 (H)|H=Ht ,

(15)

E [ gt | Ft ] = ∇H Lγt (H)|H=Ht ,

(16)

and thus:

which means that the update (8) is indeed an unbiased estimation of the true gradient ∇H Lγt (H). Note moreover that:3

Ht+1 (a) = Ht (a)   + ρt (Rt − R̄t )(1a=At − ΠHt (a)) − γt Ht (a) , a ∈ [k]. (8)

L0 (H) = ⟨q∗ , ΠH ⟩, (17)  k X ∇H L0 (H) =  q∗ (b)ΠH (b)(1a=b − ΠH (a))

Here R̄t is the mean reward up to time t constructed from Rτ , τ < t; the use of R̄t is not compulsory but has been showed to improve numerical behavior. Note that R̄t does not bias the right hand side as the overall average is null. The ’learning rate‘ (also called ’time step’) ρt and the regularization coefficient γt are both positive.

b∈[k]

a=1

= q∗ ⊙ ΠH − ΠH · EΠH [q∗ ] = ΠH ⊙ (q∗ − ⟨ΠH , q∗ ⟩) . (18) In addition it was also proved (see (Mei et al., 2020; 2023)) that for some constant cq∗ depending only on q∗ and Cm and Cq∗ = 2c2q∗ :

3. Theoretical convergence results when γt ↘ 0

E[∥ut ∥2 ] ≤ c2q∗ ,

We are interested in what happens when γ is varying in time; the most natural behavior is to take γt decreasing in order to

2

(19)

This will be relaxed in Section 4.3. Here ⊙ denotes the Hadamard, i.e., componentwise, product of vectors.

1

3

The notation V ∼ µ means that the random variable V is sampled from the distribution µ.

3

Regularized policy gradient for MAB

which shows that:

Proof. See Appendix.

E[∥gt ∥2 |Ft ] ≤ Cq∗ + 2γt2 ∥Ht ∥2 .

(20)

The convergence of the ”liminf” of the gradient norm to zero in (29) ensures that the algorithm repeatedly approaches stationary points of the objective function, justifying gradient-based stopping criteria, and showing that meaningful progress is achieved despite the inherent stochastic noise of the updates.

Some convergence results have been proved in the literature but none allows to have insight in the behavior of Ht when the regularization parameter γt vanishes. This is the main object of this contribution. We will assume in the following that : Hypγ :

To obtain results stronger than those in Proposition 3.3, we will need two technical lemmas A.2 and A.3 that are stated and proved in the Appendix.

γt is a decreasing sequence, lim γt = 0. (21) t→∞

We will introduce for any Π ∈ Pk the regret:

3.1. Non constant ρt

R(Π) := max q∗ (a) − ⟨q∗ , Π⟩.

When ρt depends on t we make the standard assumption: X X Hypρ : ρt = ∞ and ρ2t < ∞. (22) t≥0

a

Regret is the key metric optimized during training and serves as an indicator of result quality. Lower regret implies better performance, with the ideal scenario being no regret at all. Denote δa the Dirac mass supported in the arm a i.e. δa = (0, ..., 1, ..., 0) with 1 in the position a ∈ [k] and:

t≥0

We start with a technical remark: Lemma 3.1. Under assumptions (12), (22), (21) denote t0 the first index such that for all t ≥ t0 : ρt γt ≤ 14 . Then:

D = {δa , a ∈ [k]},

∀t ≥ t0 : E[γt2 ∥Ht ∥2 ] ≤ max{γt20 E[∥Ht0 ∥2 ], c2q∗ }. (23)

(31)

k

∀π ∈ R : ∥π − D∥ := min ∥π − µ∥. µ∈D

Moreover there exists a constant Cg > 0 such that : E[∥gt ∥2 ] ≤ Cg , ∀t ≥ 0. Proof. See Appendix.

(30)

(32)

We consider several hypotheses, it will be made clear below when each one is invoked:

(24)

Hyp-diff : ∀a ̸= b ∈ [k] : q∗ (a) ̸= q∗ (b).

Remark 3.2. It can be noted that Lemma 3.1 remains true when instead of (22) we only assume ρt → 0. For completeness, the analogous result when limt→∞ γt > 0 is given in Appendix, Lemma A.1.

3

Hyp-3 : ∀a ∈ [k] : E[|R(a)| ] < ∞.

(33) (34)

Hyp-ργ : ∃ cργ > 0 such that: ∀t ≥ 0 : cργ ρt γt2 ≤ γt − γt+1 .

(35)

We state now a first result that gives information on the behavior of the sequence (Ht )t≥0 , namely the summability of the gradient.

Remark 3.4. Note that under (33) there exists some unique best arm a∗ such that:

Proposition 3.3.PUnder assumptions (12), (22), (21) and T denoting ΛT = t=0 ρt :

∀a ∈ [k] : q∗ (a∗ ) ≥ q∗ (a).

∞ X

ρt E[∥∇H Lγt (Ht )∥2 ] < ∞,

(36)

As a notational convenience, from now on, for a sequence of random variables Xt :

(25)

t=0 ∞ X γt − γt+1 t=0 ∞ X

2

L2

2

E[∥Ht+1 ∥ ] < ∞,

γt − γt+1 E[∥Ht ∥2 ] < ∞, 2 t=0

Xt −−−→ Y

(26)

t→∞

2

lim inf E[∥∇H Lγt (Ht )∥ ] = 0. t→∞

4

t→∞

(37)

We can now give the main result for time-varying ρt which shows that, under appropriate hypothesis, we can guarantee the convergence of the gradient, regret and the limit distribution.

(27)

T

1 X ρt E[∥∇H Lγt (Ht )∥2 ] = 0, T →∞ ΛT t=0 lim

means lim E[∥Xt − Y ∥2 ] = 0.

(28)

Theorem 3.5. Under assumptions (12), (22), (21):

(29) 1. If in addition (34) holds then: L2

∇H Lγt (Ht ) −−−→ 0.

Such a t0 exists because ρt γt is deterministic and ρt γt → 0.

t→∞

4

(38)

Regularized policy gradient for MAB

2. If instead of (34) we have (35) then (38) still holds and moreover : ∞ X t=0 ∞ X

ρt E[∥γt Ht ∥2 ] < ∞,

(39)

ρt E[∥∇H L0 (Ht )∥2 ] < ∞,

(40)

Remark 3.8. Proving the convergence towards a critical point in (43) does not require complicated hypotheses. For the convergence of the regret (46), the assumption (33) is standard in the literature ; the hypothesis (45) is a strong assumption, but (when ρt is not constant) is still required in state of the art results (even without regularization) unless the support is considered bounded. Of course, a general proof without using (45) would be desirable. Note that this is exactly what the ϵ-greedy policies, very popular in reinforcement learning, try to do because, unless the rewards are bounded, there is nothing that prevents some exceptional reward obtained from a non-optimal arm to perturb the optimization indefinitely.

t=0

the sequences E[γt ∥Ht ∥2 ] t≥0 , (E[L0 (Ht )])t≥0 and (E[Lγt (Ht )])t≥0 converge, L

(41)

2

γt Ht −−−→ 0,

(42)

t→∞

L2

∇H L0 (Ht ) −−−→ 0.

(43)

t→∞

Remark 3.9. To the best of our knowledge, the assumption (35) is never used in the literature; this regime is different from the one in (Kushner & Yin, 2003) that are closer to the classical Robbins-Monro setting (Robbins & Monro, 1951); the offending part is the P γt sequence whose sum is not necessarily diverging and t γt2 is not necessarily converging; therefore the tools presented there do not apply. The assumption (35) is satisfied for the linear decay schedule 1 γt = c1 +c when ρt remains bounded (and in particular for 2 ·t 1 any ρt satisfying (22)). When ρt = c′ +c ′ ·t many functional

3. Assuming (33) and (35) hold true then: L2

ΠHt −−−→ D. t→∞

(44)

4. If in addition to (33) and (35) we have5 : inf ΠHt (a∗ ) ≥ c0 > 0, a.s.

t≥1

1

(45)

then :

1

L2

R(ΠHt ) −−−→ 0, t→∞

L

t→∞

(46) (47)

Proof. See Appendix. Remark 3.6. A stronger convergence result than (44), but under more restrictive hypotheses, is given in Appendix Lemma A.4. Remark 3.7. The result shows that in the limit of large t, the distribution ΠHt will converge to a Dirac mass; under suitable hypothesis this is optimal and the regret is also converging to zero.

3.2. Constant ρt = ρ We now switch to the situation when ρt is a constant, denoted ρ; note that we still honor the assumption (21). Analogous results to Theorem 3.5 can be formulated, we will only give the most complete conclusions and not all intermediary statements.

Such a result may seem at first non-standard as one may rather expect that we prove that Ht , the primal optimization variable, converges to some optimal value. This is not possible because the best reward value is realized when ΠH is a sum of Dirac masses supported in the non-empty set O = {a∗ ∈ [k] : q∗ (a∗ ) ≥ q∗ (ℓ), ∀ℓ ∈ [k]}

2

1 are diverging). On the contrary, for γt = c3 +c3 ·log(log t) linear schedule for ρt is not enough but ρt = c′ +c′1·t log t 1 2 (which fulfills (22)) will be. In general, for a sequence ρt there always exists a sequence γt satisfying assumption (35), take for instance γt = c +Pct−1 ρ where c > 0 and c0 ≥ 0 0 τ =1 τ P are arbitrary constants. Note that in this case t ρt γt = ∞ which is not a regime already seen in the literature.

2

ΠHt −−−→ δa∗ .

To ease notations, when a nonnegative sequence Ut depending on t and ρ is such that for all t ≥ 0, ρ > 0 we have Ut ≤ cρ for some constant c independent of ρ (and t) we √ will denote Ut = O(ρ); same for notation O( ρ). Theorem 3.10. Let ρt = ρ (constant) and denote

(48)

(argmax of q∗ ). Such a distribution is only reached when H(a) = ∞ for any a ∈ O so there is no finite solution that Ht could converge to. 5

2

forms ensure (35), such as γt = c′′ +c1′′ ·tα , α > 0 and γt = 1 2 P P 2 1 (note that in this case both ′′′ ′′′ t ρt γt and t γt c +c ·log t

Pt Π̄t =

See Equation (36) for definition of a∗ .

5

s=1 ΠHs

t

.

(49)

Regularized policy gradient for MAB

Under assumptions (12), (21), (35) and (33):

1.6

t = 0.1, L2 = 0, Ent = 0

1 t = 0.1, L2 = 0, Ent = 1 + 0.2t 1 t = 0.1, L2 = 1 + 0.2t , Ent = 0

1.4

Pt

2 s=1 E[∥∇H Lγs (Hs )∥ ] = O(ρ), t √ R(Π̄t ) = O( ρ), √ ∥Π̄t − δa∗ ∥ = O( ρ).

1.2 Regret

(50) (51)

1.0 0.8 0.6

(52)

0.4 0.2

Proof. See Appendix.

0.0

The interpretation of the result is as follows: when the step ρ is small enough, the procedure is converging with an error of order ρ. Of course, ideally, one would like to obtain stronger results as in Theorem 3.5 while here we do not have information directly on ΠHt but rather on its average Π̄t . However, as we will see in the numerical results, ΠHt behaves well in practice.

0

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 2. The average regret and 95% CI when starting from H0 = (5, ..., 0), ρt = 0.1 (constant); the non regularized baseline (γL2 = 0 = γEnt is compared with the L2 (only) regularization γ0 schedule γL2 (t) = 1+0.2·t γEnt (t) = 0 and with the entropy γ0 only regularization schedule γL2 (t) = 0 γEnt (t) = 1+0.2·t . The L2 regularization seems to perform best while the entropy does not seem to help much.

4. Numerical simulations t = 1, L2 = 0, Ent = 0

1.6 1.2

1.4 1.0 0.8 0.6

Regret

t = . 01, L2 = 0, Ent = 0 t = . 1, L2 = 0, Ent = 0 t = 1, L2 = 0, Ent = 0 t = 10, L2 = 0, Ent = 0 t = 100, L2 = 0, Ent = 0

1.2 Regret

1 t = 1, L2 = 0, Ent = 1 + 0.2t 1 t = 1, L2 = 1 + 0.2t , Ent = 0

1.4

1.6

1.0 0.8 0.6 0.4 0.2

0.4

0.0

0.2 0

250

500

750

1000 1250 Time step (t)

1500

1750

0

250

500

750

2000

1000 1250 Time step (t)

1500

1750

2000

Figure 3. Same as in Figure 2 except that for the main step ρt we use a non-optimal value (constant); it is seem that the L2 regularization helps ’correct’ the bad ρt value.

Figure 1. The average regret and 95% confidence intervals when ρt is constant, spanning several orders of magnitude from 0.01 to 100. Initial distribution ΠH0 corresponds to H0 = (5, ..., 0). No regularization (neither L2 nor entropic) is used. The value ρt = 0.1 appears to be the clear winner. This is used as baseline for latter comparisons (also coherent with results in Figure 11 in appendix where an extensive grid search for time-dependent ρt is presented).

1.4 1.2 Regret

1.0

We tested the regularized MAB for several decay schedules γt → 06 . The Python code is available at https://github.com/gabriel-turinici/ regularized_policy_gradient version December 20th 2025. See Section A.9 Equation (91) for the precise meaning of γL2 and γEnt .

1 t = 0.1, L2 = 1 + 0.2 t (linear) 1 t = 0.1, L2 = 1 + 0.2 t (square root) 1 t = 0.1, L2 = 1 + 0.2 logt + 1 (log)

0.8 0.6 0.4 0.2 0.0

0

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 4. The average regret and 95% CI when starting from H0 = (5, ..., 0), ρt = 0.1 (constant); several decay regimes are considered for γt : linear, square root and logarithmic.

As in (Sutton & Barto, 2018)(fig 2.5 page 38) we perform M = 1000 runs, each having T = 2000 time steps with k = 10 arms; averages q∗ (a), a ∈ [k] are independent and sampled from a normal distribution located at 4 and unit variance. For each of the arms a ∈ [k] the conditional distribution of R(a) with respect to a is a Gaussian of mean q∗ (a) and variance 1.

Each of the M runs has its own q∗ (·) which do not change during the T steps of the run. To obtain coherent comparisons, we use the same values of q∗ (·) for all the bandits that are plotted in the same figure. We plot the regret, cf. the definition in (30), the lower the regret the better the algorithm performs.

6 See also Section C for the scope of our experiments and additional results on UCB algorithm.

6

Regularized policy gradient for MAB

In all cases we take the starting point to be biased, here H0 = (5, 0, ..., 0) as this was shown to correspond to more difficult situations (Mei et al., 2020). This is also motivated by possible application to transient MAB where the averages q∗ may shift in time.

t = 0.1, L2 = 0, Ent = 0

1 t = 0.1, L2 = 0, Ent = 1 + 0.2t 1 t = 0.1, L2 = 1 + 0.2t , Ent = 0

Regret

2.0

4.1. Usefulness of the L2 regularization

1.5 1.0 0.5

4.1.1. BASELINE

0

We first check that the regularization is useful by comparing the convergence with or without regularization; in order to make the addition of the regularization more clear we set as non-regularized baseline the best performing order of magnitude of vanilla policy gradient MAB by looking on a grid spanning from ρ = 0.01 to ρ = 100; the results are in Figure 1 and show that ρt = 0.1 performs better than all the others. This optimal value will be taken as baseline from now on. We also give corresponding results for entropy regularization in Figure 12 and see that the best constant is in the range 0.01 − 1, with lowest values being better when t is large; accordingly, we take for our entropy the schedule 1 γt = 1+0.2t to span all optimal ranges. Further baseline considerations are to be found in the Appendix, including a more extensive grid search for linear time schedules of the c1 form ρt = 1+c , see Figure 11. 2 ·t

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 5. The analogue of Figure 2 except that now we have k = 50 arms. The L2 regularization still has the lowest regret among all scenarios considered: no regularization, L2 regularization, entropy regularization.

2.25

t = 1, L2 = 0, Ent = 0

1 t = 1, L2 = 0, Ent = 1 + 0.2t 1 , = 1, = t L2 1 + 0.2t Ent = 0

2.00 1.75 Regret

1.50 1.25 1.00 0.75 0.50 0.25 0

4.1.2. R ESULTS WITH RESPECT TO BASELINE

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 6. The analogue of Figure 3 for k = 50 arms.

We now compare the baseline with a regularized version in Figure 2; the decay schedule chosen for the regularization γ0 is linear γt = 1+c , c1 > 0. The results show that the 1t presence of a regularization term helps converge faster and displays faster decay in the early phases. Compared to entropy, the L2 regularization seems to be the only way to consistently outperform the baseline.

4.2. Robustness with respect to number of arms To ensure the results are not specific to a given setting, we varied the number of arms. The results when we increased k to 50 are presented in Figure 5, which is the analogous to Figure 2 and Figure 6 which is analogous to Figure 3. We observe in Figure 5 that L2 regularization is still performing best among all scenarios.

We also tested the robustness with respect to the optimality of ρt ; we take a value that is the second best in Figure 1 i.e., ρt = 1; in this case the difference is even more striking, as seen in Figure 3, where the result indicates that the L2 regularization is able to ’repair’ the non-optimal ρt value and make it converge as the optimal one. This shows that the L2 regularization is robust to other parameters and works towards improving the outcome.

As a comparison we also tested the results for k = 3 arms. It is no surprise that in this case the convergence is faster and the no-regularization and entropic regularization manage to do a good job at it, as we can see in Figure 7 but L2 regularization is still outperforming both.

4.1.3. S EVERAL DECAY SCHEDULES

4.3. Robustness with respect to the reward distribution

We next compare several decay schedules in Figure 4: linear, logarithmic and square root. Based on these results the linear schedule appears to be the best, but other test cases may yield different results depending on the parameter set.

One of the important characteristics of the theoretical results is that it does not requires the support of the random distributions to be bounded. Accordingly, we test here robustness with respect to the heavy-tailed nature of the distribution and consider the situation where the rewards are drawn from a Student-t distribution with finite second order moments but infinite third order moments i.e. has ν = 2.5 degrees of freedom. In order to be consistent with previous tests 7

Regularized policy gradient for MAB t = 0.1, L2 = 0, Ent = 0

1 t = 1, L2 = 0, Ent = 1 + 0.2t 1 t = 1, L2 = 1 + 0.2t , Ent = 0

1.4 1.2 Regret

0.6 Regret

t = 1, L2 = 0, Ent = 0

1.6

1 t = 0.1, L2 = 0, Ent = 1 + 0.2t 1 t = 0.1, L2 = 1 + 0.2t , Ent = 0

0.8

0.4

1.0 0.8 0.6 0.4

0.2

0.2 0.0

0

250

500

750

1000 1250 Time step (t)

1500

1750

0.0

2000

Figure 7. The analogue of Figures 2 and 5 for k = 3 arms. The convergence is faster but L2 regularization manages to obtain lowest regret after fewer steps than the other two methods.

0

250

500

750

1000 1250 Time step (t)

t = 0.1, L2 = 0, Ent = 0 t = 0.1,

1.4

t = 0.1,

1.2

Regret

Regret

4 3

0.6

2

0.4

1

0.2

0 250

500

750

1000 1250 Time step (t)

1500

1750

1 t = 0.1, L2 = 0, Ent = 1 + 0.2t 1 , = 0.1, = t L2 1 + 0.2t Ent = 0

5

0.8

0

2000

t = 0.1, L2 = 0, Ent = 0

6

1 L2 = 0, Ent = 1 + 0.2t 1 L2 = 1 + 0.2t , Ent = 0

1.0

0.0

1750

Figure 9. The analogue of Figure 3 when the rewards are drawn from a Student-t distribution with parameter ν = 2.5.

7 1.6

1500

2000

0

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 10. The analogue of Figure 2 except that now the stochasticity is given by a heavy tailed Student-t distribution with parameter ν = 1.5. The L2 regularization still has the lowest regret among all scenarios considered.

Figure 8. The analogue of Figure 2 except that now the stochasticity is given by a Student-t distribution. with parameter ν = 2.5. The L2 regularization still has the lowest regret among all scenarios considered.

p we also rescaled by constant (ν − 2.0)/ν so that is has unit variance. The result in Figure 8 shows that the L2 regularization works well even for such situations.

ized by a multiplicative coefficient γt and we consider for the first time the vanishing regime γt ↘ 0; we present both theoretical (convergence) and numerical (performance) results.

A equally spectacular difference appears in Figure 9; as in Figure 3 we took here some non-optimal ρt = ρ and let L2 regularization ’correct’ it. We see that the plain softmax gradient and the entropy-regularized gradients are simply not converging, stagnating at a regret of around 0.5 which, at this scale, is rather important. On the contrary the L2 regularization helps restore the convergence.

We prove that when γt ↘ 0 the gradient of the average reward vanishes, that is, critical point equations are satisfied in the limit. Unlike prior work on non-regularized MAB, our analysis does not rely on any bounded-support assumption on the arm reward distributions R(a), a ∈ [k]. This is the first result known for this setting. During the proof we highlight an interesting new regime, cf. (35), that links the main learning rate ρt with the regularization decay γt ; this regime goes beyond classical Robbins-Monro setting P that would correspond to t ρt γt < ∞ and may be interesting to explore further. We also prove convergence under hypotheses coherent with the literature.

Finally, we pushed the experiments even further and tested a Student-t distribution with parameter ν = 1.57 ; the result in Figure 10 confirms the good performance of the L2 regularization for such heavy tailed distributions.

5. Summary and discussion

The theoretical results were tested numerically; it is seen that the L2 regularization improves the convergence when compared with non-regularized or entropy-regularized alternatives. The improvement is robust across a large range of conditions including the number of arms and the distribution of the rewards. In particular we also tested success-

We analyze in this work the L2 regularized softmax policy gradient for MAB. The regularization term is parameter7 Note that for this value of ν the distribution does not even have finite variance.

8

Regularized policy gradient for MAB

fully heavy tailed distributions (Student-t with ν = 2.5 or ν = 1.5) which are beyond the scope of the previous known results even for the non-regularized setting.

9

Regularized policy gradient for MAB

References Afsar, M. M., Crump, T., and Far, B. Reinforcement learning based recommender systems: A survey. ACM Comput. Surv., 55(7), December 2022. ISSN 0360-0300. doi: 10.1145/3543846. URL https://doi.org/10. 1145/3543846. Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 64–66. PMLR, 09– 12 Jul 2020. URL https://proceedings.mlr. press/v125/agarwal20a.html. Aghaei, M. Convergence of softmax policy gradient: Incorporating entropy regularization and handling linear function approximation. M.sc. thesis, University of Alberta, February 2025. Computing Science Theses, Identifier: etd23667. Ajalloeian, A. and Stich, S. U. On the convergence of sgd with biased gradients, 2021. URL https://arxiv. org/abs/2008.00051. Aniţa, Ş.-L. and Turinici, G. On the Convergence Rate of the Stochastic Gradient Descent (SGD) and Application to a Modified Policy Gradient for the Multi Armed Bandit, 2024. arxiv:2402.06388.

Blum, J. R. Approximation methods which converge with probability one. Annals of Mathematical Statistics, 25(2): 382–386, 1954. doi: 10.1214/aoms/1177728727. Bojarski, M., Testa, D. D., Dworakowski, D., Firner, B., Flepp, B., Goyal, P., Jackel, L. D., Monfort, M., Muller, U., Zhang, J., Zhang, X., Zhao, J., and Zieba, K. End to end learning for self-driving cars, 2016. arxiv:1604.07316. Boldrini, S., De Nardis, L., Caso, G., Le, M. T. P., Fiorina, J., and Di Benedetto, M.-G. mumab: A multi-armed bandit model for wireless network selection. Algorithms, 11(2), 2018. ISSN 1999-4893. doi: 10.3390/a11020013. URL https://www.mdpi.com/1999-4893/11/ 2/13. Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 35(2):936 – 982, 2025. doi: 10.1214/ 24-AAP2132. URL https://doi.org/10.1214/ 24-AAP2132. Publisher: Institute of Mathematical Statistics. Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge, UK, 2008. doi: 10.1017/CBO9780511721338. Chen, H.-F. Stochastic approximation and its applications, volume 64 of Nonconvex Optim. Appl. Dordrecht: Kluwer Academic Publishers, 2002. ISBN 1-4020-0806-6.

Aniţa, Ş.-L. and Turinici, G. Convergence of a L2 Regularized Policy Gradient Algorithm for the Multi Armed Bandit. In Antonacopoulos, A., Chaudhuri, S., Chellappa, R., Liu, C.-L., Bhattacharya, S., and Pal, U. (eds.), Pattern Recognition, pp. 407–422, Cham, 2025. Springer Nature Switzerland. ISBN 978-3-031-78395-1.

Chu, W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Gordon, G., Dunson, D., and Dudı́k, M. (eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 208–214, Fort Lauderdale, FL, USA, 11–13 April 2011. PMLR. URL https://proceedings. mlr.press/v15/chu11a.html.

Bach, F. Adaptivity of averaged stochastic gradient descent to local strong convexity of the loss. Journal of Machine Learning Research, 16(88):595–627, 2015. URL http: //jmlr.org/papers/v16/bach15a.html. Baudry, D., Johnson, E., Vary, S., Pike-Burke, C., and Rebeschini, P. Does stochastic gradient really succeed for bandits? In Eighteenth European Workshop on Reinforcement Learning, 2025. URL https://openreview. net/forum?id=rSruZDo2E7.

Ding, Y., Zhang, J., Lee, H., and Lavaei, J. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. IEEE Transactions on Automatic Control, 70(8):5129–5144, 2025. doi: 10.1109/TAC.2025.3540965. Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1467–1476. PMLR, July 2018. URL https://proceedings.mlr.press/v80/ fazel18a.html.

Bhandari, J. and Russo, D. Global Optimality Guarantees for Policy Gradient Methods. Operations Research, January 2024. ISSN 0030364X. doi: 10.1287/opre.2021.0014. URL https://pubsonline.informs.org/doi/ full/10.1287/opre.2021.0014. Publisher: INFORMS. 10

Regularized policy gradient for MAB

Fehrman, B., Gess, B., and Jentzen, A. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21(136):1–48, 2020. URL http: //jmlr.org/papers/v21/19-636.html.

Robbins, H. and Monro, S. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400 – 407, 1951. doi: 10.1214/aoms/ 1177729586. URL https://doi.org/10.1214/ aoms/1177729586. Publisher: Institute of Mathematical Statistics.

Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi, L. A. Guidelines for reinforcement learning in healthcare. Nature Medicine, 25(1):16–18, 2019.

Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1889–1897, Lille, France, 07–09 Jul 2015. PMLR. URL https://proceedings.mlr.press/v37/ schulman15.html.

Kassing, S., Weissmann, S., and Döring, L. Controlling the flow: Stability and convergence for stochastic gradient descent with decaying regularization, 2025. URL https://arxiv.org/abs/2505.11434. Kushner, H. J. and Yin, G. G. Stochastic Approximation and Recursive Algorithms and Applications, volume 35 of Applications of Mathematics. Springer, New York, NY, 2nd edition, 2003. doi: 10.1007/978-1-4612-0059-6.

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, January 2016. ISSN 1476-4687. doi: 10.1038/nature16961. URL https://doi.org/10.1038/nature16961.

Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. On the Global Convergence Rates of Softmax Policy Gradient Methods. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6820–6829. PMLR, July 2020. URL https://proceedings.mlr.press/ v119/mei20b.html.

Slivkins, A. Introduction to Multi-Armed Bandits. Foundations and Trends® in Machine Learning, 12(1-2):1–286, 2019. ISSN 1935-8237. doi: 10.1561/2200000068. URL http://dx.doi.org/10.1561/2200000068.

Mei, J., Zhong, Z., Dai, B., Agarwal, A., Szepesvari, C., and Schuurmans, D. Stochastic gradient succeeds for bandits. In International Conference on Machine Learning, pp. 24325–24360. PMLR, 2023.

Sutton, R. S. and Barto, A. G. Reinforcement learning. An introduction. Adapt. Comput. Mach. Learn. Cambridge, MA: MIT Press, 2nd expanded and updated edition edition, 2018. ISBN 978-0-262-03924-6.

Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V. On the Almost Sure Convergence of Stochastic Gradient Wang, L., Cai, Q., Yang, Z., and Wang, Z. Neural policy Descent in Non-Convex Problems. In Larochelle, H., gradient methods: Global optimality and rates of converRanzato, M., Hadsell, R., Balcan, M. F., and Lin, H. gence, 2019. arxiv:1909.01150. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1117–1128. Curran Associates, Inc., 2020. URL https://proceedings.neurips. Weissmann, S., Klein, S., Azizian, W., and Döring, L. Almost sure convergence of stochastic gradient methods uncc/paper_files/paper/2020/file/ der gradient domination. Transactions on Machine Learn0cb5ebb1b34ec343dfe135db691e4a85-Paper. ing Research, 2025. ISSN 2835-8856. URL https: pdf. arxiv:2006.11144. //openreview.net/forum?id=OTwnNBxZFB. Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., VeYu, C., Liu, J., Nemati, S., and Yin, G. Reinforcement learnness, J., Bellemare, M. G., Graves, A., Riedmiller, M., ing in healthcare: A survey. ACM Computing Surveys Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, (CSUR), 55(1):1–36, 2021. C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-level Zhang, J., Kim, J., O’Donoghue, B., and Boyd, S. Samcontrol through deep reinforcement learning. Nature, 518 ple efficient reinforcement learning with reinforce. Pro(7540):529–533, February 2015. ISSN 1476-4687. doi: ceedings of the AAAI Conference on Artificial Intelli10.1038/nature14236. URL https://doi.org/10. gence, 35(12):10887–10895, May 2021. doi: 10.1609/ 1038/nature14236. aaai.v35i12.17300. URL https://ojs.aaai.org/ OpenAI. Gpt-4 technical report, 2024. arxiv:2303.08774. index.php/AAAI/article/view/17300. 11

Regularized policy gradient for MAB

Zhang, K., Koppel, A., Zhu, H., and Başar, T. Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies. SIAM Journal on Control and Optimization, 58(6):3586– 3612, 2020. doi: 10.1137/19M1288012. URL https://doi.org/10.1137/19M1288012. eprint: https://doi.org/10.1137/19M1288012.

12

Regularized policy gradient for MAB

A. Appendix: proofs and further numerical results A.1. Proof of Lemma 3.1 Proof. We take t ≥ t0 and first prove the inequality (23). Recall the update formula (8) for Ht+1 : Ht+1 = (1 − ρt γt )Ht + ρt ut . We multiply by γt to obtain γt Ht+1 = (1 − ρt γt )γt Ht + γt ρt ut ,

(53)

and thus : E[∥γt+1 Ht+1 ∥2 ] ≤ E[∥γt Ht+1 ∥2 ] = E[∥(1 − ρt γt )γt Ht + γt ρt ut ∥2 ] ≤ (1 − ρt γt )E[∥γt Ht ∥2 ] + γt ρt E[∥ut ∥2 ],

(54)

where the last inequality is due to convexity; together with (19) this leads to E[∥γt+1 Ht+1 ∥2 ] ≤ max{E[∥γt Ht ∥2 ], c2q∗ },

(55)

which ends the proof of (23). The inequality (24) is then a consequence of (20) and (23). A.2. Boundedness result when limt→∞ γt > 0 Lemma A.1. Under assumptions (12), (22) and Hyp>0 γ :

γt is a decreasing sequence, lim γt = γ̄ > 0, t→∞

(56)

denote t0 the first index such that for all t ≥ t0 : ρt γt ≤ 1. Then: ∀t ≥ t0 : E[∥Ht ∥2 ] ≤ max{E[∥Ht0 ∥2 ], c2q∗ /γ̄ 2 }.

(57)

Moreover there exists a constant Cg′ > 0 such that : E[∥gt ∥2 ] ≤ Cg′ .

(58)

Proof. For (57) the proof is similar to that of (23) as we obtain by convexity that : E[∥Ht+1 ∥2 ] ≤ max{E[∥Ht ∥2 ], c2q∗ /γt2 } ≤ max{E[∥Ht ∥2 ], c2q∗ /γ̄ 2 } and conclude as before. Inequality (58) results from (20) and the boundedness of E[∥Ht ∥2 ]. A.3. Proof of Proposition 3.3 a q∗ (a) Proof. It was noted that cf. (Aniţa & Turinici, 2025)(Eqn (29))8 denoting c⋆ = maxa q∗ (a)+min >0: 2

|∇2H L0 (H̄)(δH, δH)| ≤ c⋆ ∥δH∥2 ,

∀δH, H̄ ∈ Rk .

(59)

Taylor’s formula allows to write : Lγt (Ht+1 ) − Lγt (Ht ) − ⟨∇H Lγt (Ht ), Ht+1 − Ht ⟩ =

1 (Ht+1 − Ht )T ∇2H Lγt (H̄t )(Ht+1 − Ht ), 2

(60)

and consequently ρt ⟨∇H Lγt (Ht ), ut − γt Ht ⟩ −

c⋆ ∥Ht+1 − Ht ∥2 ≤ Lγt (Ht+1 ) − Lγt (Ht ). 2

(61)

8 For any operator F : Rk → R we denote by ∇2H F its second differential which acts from Rk × Rk to R by: ∇2H F(H1 , H2 ) = H1T HF H2 where HF is the Hessian matrix of F. When there is no ambiguity we also write ∇2 F.

13

Regularized policy gradient for MAB

That implies −c⋆ [ρ2t ∥ut ∥2 + ρ2t γt2 ∥Ht ∥2 ] + ρt ⟨∇H Lγt (Ht ), ut − γt Ht ⟩ ≤ Lγt+1 (Ht+1 ) − Lγt (Ht ) +

γt+1 − γt ∥Ht+1 ∥2 . 2

(62)

Using the conditional expectation with respect to Ft and then E we get that − ρ2t C1 + ρt E[∥∇H Lγt (Ht )∥2 ] +

γt − γt+1 E[∥Ht+1 ∥2 ] ≤ E[Lγt+1 (Ht+1 )] − E[Lγt (Ht )], 2

(63)

for any t ∈ N, where C1 is some positive constant. We obtain ρt E[∥∇H Lγt (Ht )∥2 ] +

γt − γt+1 E[∥Ht+1 ∥2 ] ≤ E[Lγt+1 (Ht+1 )] − E[Lγt (Ht )] + C1 ρ2t . 2

(64)

Since {E[Lγt (Ht )]}t∈N is bounded, γt decreasing and ρ2t summable we obtain conclusions (25) and (26). For (27) we use that E[∥Ht+1 − Ht ∥2 ] ≤ ρ2t Cg which is also summable. Since on the other hand Hypothesis (22) implies that ΛT → ∞ so that 1/ΛT → 0 we obtain also (28). Finally, arguing by contradiction we also get that on a subsequence E[∥∇H Lγtl (Htl )∥2 ] −→ 0,

(65)

i.e. ∇H Lγtl (Htl ) −→ 0 in L2 , which is another way to express (29). A.4. Lemma A.2 Lemma A.2. Let (Y ) be sequences of real-valued random variables with  (Xn )n≥1 and P∞ P∞ n n≥1 2 E |Y | < ∞. Then E[|X Y n n n |] < ∞. n=1 n=1

P∞



n=1 E

|Xn |2



< ∞,

Proof. We repeatedly use the Cauchy–Schwarz inequality: ∞ X

∞ p X E[|Xn Yn |] ≤ E[Xn2 ] E[Yn2 ] ≤

n=1

∞ X

!1/2

∞ X

E[Xn2 ]

E[Yn2 ]

< ∞.

(66)

n=1

n=1

n=1

!1/2

A.5. Summability Lemma A.3 Lemma A.3. Let (αn )n≥1 ⊂ R be a sequence with αn ≥ 0 and assume that there exists a sequence (βn )n≥1 ⊂ R such that ∀n ≥ 1 : αn+1 − αn ≤ βn . If

P∞

(67)

n=1 |βn | < ∞ then the sequence (αn )n≥1 converges to some ᾱ ∈ [0, α1 +

P∞

n=1 βn ].

Pn Proof. Summing the P inequalities in (67) we obtain that αn − α1 ≤ k=1 βk < ∞ thus the sequence (αn )n≥1 is bounded ∞ from above by α1 + n=1 |βn | < ∞ and from below by 0. Assume that is has two distinct accumulation points ᾱ1 < ᾱ2 and denote ϵ P = ᾱ2 − ᾱ1 . Since the series of general term βn is absolutely convergent, there exists n0 such that for any n2 n1 , n2 ≥ n0 n=n |βn | < 2ϵ . Since ᾱ1 is an accumulation point there exists some n1 > n0 such that |αn1 − ᾱ1 | < ϵ/4 1 and some n2 > n1 such that |αn2 − ᾱ2 | < ϵ/4. But then ϵ = ᾱ2 − ᾱ1 ≤ |ᾱ2 − αn2 | + |αn2 − αn1 | + |αn1 − ᾱ1 | <

nX 2 −1 ϵ ϵ + |βn | + < ϵ, 4 n=n 4 1

which is a contradiction. Therefore there is only one accumulation point and, since the sequence is bounded, it converges. 14

(68)

Regularized policy gradient for MAB

A.6. Proof of Theorem 3.5 Proof. Proof of assertion (38): Denote Gt = ∥∇L0 (Ht ) − γt Ht ∥2 . To analyze the difference Gt+1 − Gt we invoke the identity: ||ζ||2 − ||ν||2 = ||ζ − ν||2 + 2⟨ζ − ν, ν⟩, true for any vectors ζ, ν ; we choose: ζ = ∇L0 (Ht+1 ) − γt+1 Ht+1 and ν = ∇L0 (Ht ) − γt Ht and thus: Gt+1 − Gt = ||∇L0 (Ht+1 ) − ∇L0 (Ht ) − (γt+1 Ht+1 − γt Ht )||2 | {z } term (I)

+ 2 ⟨∇L0 (Ht+1 ) − ∇L0 (Ht ) − (γt+1 Ht+1 − γt Ht ), ∇L0 (Ht ) − γt Ht ⟩ . | {z }

(69)

term (II)

For the term (I) we obtain: E[||∇L0 (Ht+1 ) − ∇L0 (Ht ) − (γt+1 Ht+1 − γt Ht )||2 ]  ≤ 3E ||∇L0 (Ht+1 ) − ∇L0 (Ht )||2 + (γt − γt+1 )2 ||Ht+1 ||2 + γt2 ||Ht − Ht+1 ||2  ≤ 3E (L∇L0 + γ02 )||Ht − Ht+1 ||2 + γ0 (γt − γt+1 )||Ht+1 ||2 ,

(70)

where L∇L0 is the Lipschitz constant of ∇L0 (H), which is finite because if only involves components of ΠH . The second term of the last expression is member of a summable series as proved in (26). The first term E[(L∇L0 + γ02 )||HtP − Ht+1 ||2 ] 2 2 2 2 is the same as ρt E[(L∇L0 + γ0 )||gt || ] and is summable because E[||gt || ] is bounded as proven in (24) and t ρ2t < ∞ (hypothesis Hypρ in (22)). Thus the term (I) is a member of a summable series. Let us now discuss term (II) in (69) that can be decomposed as ⟨∇L0 (Ht+1 ) − ∇L0 (Ht ) − (γt+1 Ht+1 − γt Ht ), ∇L0 (Ht ) − γt Ht ⟩ = ⟨∇L0 (Ht+1 ) − ∇L0 (Ht ), ∇L0 (Ht ) − γt Ht ⟩ | {z } term (*)

+ ⟨γt Ht − γt+1 Ht+1 , ∇L0 (Ht ) − γt Ht ⟩ . {z } |

(71)

term (**)

For the term (*) we can write : E[⟨∇L0 (Ht+1 ) − ∇L0 (Ht ), ∇L0 (Ht ) − γt Ht ⟩] = E[⟨∇2 L0 (Ht )(Ht+1 − Ht ) 1 + ∇3 L0 (H̄)(Ht+1 − Ht , Ht+1 − Ht ), ∇L0 (Ht ) − γt Ht ⟩] 2 = E[E[⟨∇2 L0 (Ht )(Ht+1 − Ht ), ∇L0 (Ht ) − γt Ht ⟩|Ft ]] 1 + E[⟨ ∇3 L0 (H̄)(Ht+1 − Ht , Ht+1 − Ht ), ∇L0 (Ht ) − γt Ht ⟩] 2 = ρt E[⟨∇2 L0 (Ht )(∇L0 (Ht ) − γt Ht ), ∇L0 (Ht ) − γt Ht ⟩] 1 + E[⟨ ∇3 L0 (H̄)(Ht+1 − Ht , Ht+1 − Ht ), ∇L0 (Ht ) − γt Ht ⟩] 2 ≤ c1 ρt E[∥∇L0 (Ht ) − γt Ht ∥2 ] + c2 E[ρ2t ∥gt ∥2 · ∥∇L0 (Ht ) − γt Ht ∥],

(72)

with c1 and c2 some constants depending only on q∗ . In the last expression, the first part is the general term of a convergent series as proven in (25). The second part is also summable because ρ2t is summable and E[∥gt ∥2 · ∥∇L0 (Ht ) − γt Ht ∥] ≤ E[∥gt ∥3 ]2/3 · E[∥∇L0 (Ht ) − γt Ht ∥3 ]1/3 is bounded because of the hypothesis (34)9 . Thus term (*) is absolutely summable. We are now left with term (**) that can be further decomposed as : ⟨γt+1 (Ht − Ht+1 ), ∇L0 (Ht ) − γt Ht ⟩ + ⟨(γt − γt+1 )Ht , ∇L0 (Ht ) − γt Ht ⟩ . | {z } | {z } term (†)

(73)

term (‡)

9 We also use a variant of Lemma 3.1 which ensures that the third order moment of gt and γt Ht are both bounded; the proof being totally analogous to that before we do not give it here.

15

Regularized policy gradient for MAB

The average of (†) is non-positive, while, arguing as before, the average of (‡) is upper bounded by (γt − γt+1 ) · E[∥Ht ∥2 ]+E[∥∇L0 (Ht )−γt Ht ∥2 ] which is summable. Coming back to (69) we can summarize the whole analysis by saying that 2 E[Gt+1 ] − E[Gt ] is upper bounded by the general term of an absolutely summable series. Now we can apply Lemma A.3 to conclude that E[Gt ] is a converging sequence. But, from (29) its liminf is zero so the whole sequence is converging to zero, which ends the proof of assertion (38). Proof of assertions (40), (41), (42) and (43) ((38) is a consequence of and (42) and (43)): From the summability (27) and relation (35) we obtain that ∞ X

ρt γt2 E[∥Ht ∥2 ] < ∞,

(74)

t=0

and then, since ∇H Lγt (Ht ) = ∇H L0 (Ht ) − γt Ht we recover (40) from (25). Denote G(H) = ∥∇L0 (H)∥2 .

(75)

The gradient ∇H G is a Lipschitz function of H, we denote LG its Lipschitz constant, and thus  |E[G(Ht+1 )] − E[G(Ht )]| ≤ E[⟨∇ ∥∇L0 (Ht )∥2 , Ht+1 − Ht ⟩] + LG E[∥Ht+1 − Ht ∥2 ]  = E[E[⟨∇ ∥∇L0 (Ht )∥2 , Ht+1 − Ht ⟩|Ft ]] + LG E[∥Ht+1 − Ht ∥2 ]  = ρt E[⟨∇ ∥∇L0 (Ht )∥2 , ∇L0 (Ht ) − γt Ht ⟩] + LG E[∥Ht+1 − Ht ∥2 ] ≤ c1 ρt E[∥∇L0 (Ht )∥ · ∥∇L0 (Ht ) − γt Ht ∥] + c2 ρ2t ,

(76)

P P where only on q∗ . Recall that series t ρ2t is convergent, same as t ρt E[∥∇L0 (Ht )∥2 ] Pc1 and c2 are constants depending and t ρt E[∥∇L0 (Ht ) − γt Ht ∥2 ]. By Lemma A.2 we obtain that |E[G(Ht+1 )] − E[G(Ht )]| is bounded by a convergent series and by Lemma A.3 we obtain that E[G(Ht )] is convergent. From (40) the only possible limit is zero which proves (43). To prove (41) we write: E[γt+1 ∥Ht+1 ∥2 ] − E[γt ∥Ht ∥2 ] ≤ E[γt (∥Ht+1 ∥2 − ∥Ht ∥2 )]   = γt E (∥Ht+1 − Ht ∥2 ) + 2⟨Ht+1 − Ht , Ht ⟩   = γt E (∥Ht+1 − Ht ∥2 ) + 2ρt ⟨∇L0 (Ht ) − γt Ht , Ht ⟩ (we used conditioning byFt ) ≤ Cg γt ρ2t + 2ρt E[∥∇L0 (Ht ) − γt Ht ∥ · γt ∥Ht ∥],

(77)

and, using (74) we conclude as in (76) that E[γt+1 ∥Ht+1 ∥2 ] converges. Since γt → 0 we obtain (42). Analogous arguments show that E[L0 (Ht )] is also converging and hence E[Lγt (Ht )] as difference of two converging sequences. We now turn to (44). Denote ∆ the ’gap’ ∆ := mina,b∈[k],a̸=b |q∗ (a) − q∗ (b)|; from (33) we obtain ∆ > 0. Invoking formula (14) from (Mei et al., 2023) we can write ∥∇H L0 (Ht )∥2 =

X

ΠHt (a)2 (q∗ (a) − qt )2 ,

(78)

a∈[k]

where qt := ⟨q∗ , ΠHt ⟩. Note that qt ∈ [mina q∗ (a), maxa q∗ (a)] and denote At one minimizer of |q∗ (a) − qt | among all arms a; in particular At is measurable thus a random variable. Moreover, since ∆ is the minimal gap we obtain that 16

Regularized policy gradient for MAB

|q∗ (a) − qt | ≥ ∆/2 whenever a ̸= At . Thus: ∥∇H L0 (Ht )∥2 =

X

ΠHt (a)2 (q∗ (a) − qt )2 ≥

a≤k

 ≥

=

∆ 2

2

X 1 · · ΠHt (a) = k−1 a̸=At



∆ 2

2 ·

X

ΠHt (a)2 (q∗ (a) − qt )2 ≥

a̸=At

2



ΠHt (a)2



a̸=At

1 · (1 − ΠHt (At ))2 k−1 

 ∆2  ∆2 (1 − ΠHt (At ))2 + (1 − ΠHt (At ))2 = 8(k − 1) 8(k − 1)

∆ 2

2

2  X   2 ΠHt (a)  (1 − ΠHt (At )) +  

a̸=At





≥

X

X from (32) ∆2  ∆2 ∆2 ΠHt (a)2  = (1 − ΠHt (At ))2 + ∥ΠHt − δAt ∥2 ≥ ∥ΠHt − D∥2 , 8(k − 1) 8(k − 1) 8(k − 1)

(79)

a̸=At

which together with (43) proves (44). To prove (46) we use Lemma 3 from (Mei et al., 2020) that in our setting reads ∥∇L0 (H)∥ ≥ ΠH (a∗ )R(ΠH ). Using (45) we obtain ∥∇H L0 (Ht )∥ ≥ c0 · R(ΠHt ) which implies (46) because of (43). To prove (47) we write for a general distribution Π ∈ Pk : 2

 R(Π)2 = 

X

X

Π(b)(q∗ (a∗ ) − q∗ (b)) = 

 2 X ∆  Π(b) =  2 ∗ 2

≥ ∆2 

Π(b)(q∗ (a∗ ) − q∗ (b))

b∈[k],b̸=a∗

b∈[k]



b∈[k],b̸=a



≥

2



∆2  (1 − Π(a∗ ))2 + 2

2 X b∈[k],b̸=a∗

Π(b)2  =

b∈[k],b̸=a∗

X

Π(b) + 

 X

 b∈[k],b̸=a∗

2   Π(b) 

∆2 · ∥Π − δa∗ ∥2 , 2

(80)

which, setting Π = ΠHt and using (46), proves (47). A.7. A stronger convergence result for ΠHt under more restrictive hypotheses Lemma A.4. Under assumptions (12), (22), (21), (33), and assuming additionally that the rewards are bounded and that ∞ X

ρt (ρ0 + ρ1 + · · · + ρt−1 )2 γt2 < ∞,

(81)

1F −1 (q∗ (a)) a=1

(82)

t=1

then ΠHt −→

k

in L2 ,

where F is a real-valued random variable satisfying F ∈ {q∗ (1), q∗ (2), ..., q∗ (k)} a.s.. Proof. Since ∥Ht+1 ∥ ≤ ∥Ht ∥(1 − ρt γt ) + M ρt (M is some positive constant) then for any t > t0 : ∥Ht ∥ ⇒ γt ∥Ht ∥ ⇒ γt2 ∥Ht ∥2

≤ ∥Ht0 ∥(1 − ρt0 γt0 )(1 − ρt0 +1 γt0 +1 ) · · · (1 − ρt−1 γt−1 ) +M [ρt−1 + ρt−2 (1 − ρt−1 γt−1 ) + · · · + ρt0 (1 − ρt0 +1 γt0 +1 ) · · · (1 − ρt−1 γt−1 )] ≤ γt ∥Ht0 ∥ + M γt (ρt−1 + ρt−2 + · · · + ρ0 ) ≤ M̃ [γt2 + γt2 (ρ0 + · · · + ρt−1 )2 ]. | {z } at

17

(83)

Regularized policy gradient for MAB

Here M̃ is another positive constant. So, γt2 ∥Ht ∥2 ≤ at a.s., where

P∞

t=1 at ρt < ∞.

By Taylor’s formula we get that L0 (Ht+1 )

= L0 (Ht ) + ⟨∇L0 (Ht ), Ht+1 − Ht ⟩ + 21 (Ht+1 − Ht )T ∇2H L0 (H̄t )(Ht+1 − Ht ) ≥ L0 (Ht ) + ρt ⟨∇L0 (Ht ), ut ⟩ − ρt γt ⟨∇L0 (Ht ), Ht ⟩ − c2⋆ ∥ρt ut − ρt γt Ht ∥2

(84)

γ2

≥ L0 (Ht ) + ρt ∥∇L0 (Ht )∥2 − ρt ∥∇L0 (Ht )∥2 − ρt 4t ∥Ht ∥2 − cρ2t ≥ L0 (Ht ) − C(ρ2t + ρt at ),

⇒ E[L0 (Ht+1 )|Ft ]

where c and C are positive constants. Pt−1 Denote by St = l=0 (ρ2l + ρl al ). Note that (St )t∈N∗ is a convergent sequence. So, E[L0 (Ht+1 ) − CSt+1 |Ft ] ≥ L0 (Ht ) − CSt . By Doob’s theorem we get that L0 (Ht ) − CSt −→ F̃

a.s.,

where F̃ is a real-valued random variable. And so L0 (Ht ) −→ F ∈ [mina q∗ (a), maxa q∗ (a)] a.s. . We have that E[∥∇L0 (Ht )∥2 ] =

X

E[ΠHt (a)2 (q∗ (a) − L0 (Ht ))2 ]

a∈[k]

X

⇒

E[ΠHt (a)2 (q∗ (a) − F )2 ] −→ 0.

(85)

a∈[k]

We prove by contradiction that F ∈ {q∗ (1), q∗ (2), ..., q∗ (k)} a.s.. Assume that on Ω0 (with P(Ω0 ) > 0): (q∗ (a) − F )2 > 0 a.s.,

i.e.

min{(q∗ (a) − F )2 ; a ∈ [k]} > 0 a.s. in Ω0 .

By (85) we get via the Cauchy-Schwarz inequality we get that:    2 1 X   ΠHt (a) · min{(q∗ (a) − F )2 ; a ∈ [k]} −→ 0 E 1Ω0  k a∈[k]

⇔ E[1Ω0 min{(q∗ (a) − F )2 ; a ∈ [k]}] −→ 0, | {z }

which is a contradiction.

strictly positive on Ω0

So, F ∈ {q∗ (1), q∗ (2), ..., q∗ (k)} a.s.. Let Ωl = F −1 (q∗ (l)), l ∈ [k]. If P(Ωl ) > 0 then X E[ΠHt (a)2 (q∗ (a) − F )2 1Ωl ] −→ 0. a̸=l

Using that

1 2 a̸=l ΠHt (a) ≥ k−1 (

2 2 2 a̸=l ΠHt (a)) and that (q∗ (a) − F ) ≥ min{|q∗ (a) − q∗ (l)|; a ̸= l} we get

P

P

E[(1 − ΠHt (l))2 1Ωl ] −→ 0 ⇒ 1Ωl (1 − ΠHt (l)) −→ 0 in L2 ⇒ 1Ωl ΠHt (a) −→ 0

in L2 , a ̸= l.

So, 1Ωl ΠHt (l) −→ 1Ωl in L2 . And consequently, ΠHt (a) −→ 1F −1 (q∗ (a)) in L2 , a ∈ [k] which gives the conclusion (82). 18

Regularized policy gradient for MAB

A.8. Proof of Theorem 3.10 Proof. Proof of assertion (50): Some part of the proof for ρt constant is similar to the case when ρt is depending on t. More specifically, using exactly the same techniques as in the proof of Proposition 3.3 we obtain (64) in the form: ρE[∥∇H Lγt (Ht )∥2 ] +

γt − γt+1 E[∥Ht+1 ∥2 ] ≤ E[Lγt+1 (Ht+1 )] − E[Lγt (Ht )] + C1 ρ2 . 2

(86)

Note on the other hand that, as before: - E[Lγt (Ht )] is bounded from above being a difference of a bounded term and a negative part - Lemma 3.1 remains true when ρt is constant i.e., the sequence E[γt2 ∥Ht ∥2 ] is bounded and the same is E[∥∇H Lγt (Ht )∥2 ]. Summing up (86) up to time t we obtain (50). We also obtain that t X γs − γs+1

2

s=1

E[∥Hs+1 ∥2 ] ≤ c1h · t · ρ2 ,

(87)

for some positive constant c1h and under hypothesis (35) we obtain: t

1X E[∥γs Hs ∥2 ] = O(ρ), t s=1

(88)

t

1X E[∥∇H L0 (Hs )∥2 ] = O(ρ). t s=1

(89)

Note too that the proof of assertions (40), (41), (42) and (43) can also adapted to ρt = ρ. To prove (51) we use again Lemma 3 from (Mei et al., 2020) in the form ∥∇H L0 (Ht )∥ ≥ c0 · R(ΠHt ) and write: !2 t t t X 1X 1X 2 21 2 2 E[∥∇H L0 (Hs )∥ ] ≥ c0 R(ΠHs ) ≥ c0 R(ΠHs ) = c20 R(Π̄t )2 , O(ρ) = t s=1 t s=1 t s=1

(90)

where we used that the regret R is linear in its argument Π which proves (51). On the other hand the conclusion (52) follows from (51) using the inequality (80) for Π = Π̄t . A.9. Implementation of the entropy regularization: formulaes We compared L2 and entropy regularization and, for clarity and because these are not available in the literature and on online code repositories, we give below for reference the formulas that were used for the implementation; this is the convention use in all figures of the paper. The objective is to maximize L(t) = E[Rt ] − where Ω(Π) = −

P

γL2 (t) ∥Ht ∥22 + γEnt (t) Ω(ΠHt ), 2

(91)

a∈[k] Π(a) log Π(a) is the Shannon entropy and γL2 (t), γEnt (t) ≥ 0 are decay schedules.

Sign conventions: - we perform gradient ascent on L(t) - with the L2 penalty term: − γL22(t) ∥Ht ∥2 , whose gradient contribution is −γL2 (t)Ht , - and an entropy term: γEnt (t) Ω(ΠHt ) whose gradient contribution is γEnt (t)∇H Ω(ΠHt ). Entropy gradient: ∇H(b) Ω(ΠHt ) = −

X

(log ΠHt (a) + 1)∇H(b) ΠHt (a) = −

a

X a

19

ΠHt (a)(log ΠHt (a) + 1)(1a=b − ΠHt (b)).

(92)

Regularized policy gradient for MAB

Recall that action At is sampled according to ΠHt so the unbiased gradient is given by the formula: gt = [rt − r̄t − γEnt (t) − γEnt (t) log(ΠHt )] ⊙ (1At − ΠHt ) − γL2 (t)Ht , where r̄t is the running average reward (baseline). This gives the full preference update Ht+1 = Ht + ρt gt . In fact, following (Mei et al., 2020)(’Update 2’ section 4.2.1) we replace 1 + log(ΠHt ) by log(ΠHt ) above as it does not change the unbiasedness of the gradient.

B. Further numerical results B.1. Grid search for best linear decay schedules for ρt c1 We give here the analogue result of Figure 1 but here for linear decay schedules ρt = 1+c . To be closer to the realistic 2 ·t setting we plot the empirical regret i.e. maxa q∗ (a) − Rt instead of exact regret R; note that empirical regret is, up to a constant, available during training while R() is not; in practice to choose a decay schedule only such outputs are available and not R(). We checked that comparison between the decay schedules is the same when true regret is used.

1.60 1.55 1.50 1.45 1.40 1.35 1.30 1.25 1.20 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2

1.65

0.01 t = 1 + 0.005t

1.60 1.55 1.50 1.45 0.01 t = 1 + 0.0005t

0

500 1000 1500 2000 0.1 t = 1 + 0.0005t

1.40

0

1.6

1 t = 1 + 0.0005t

1.4

1.55

1.50

1.50

1.45

1.45

1.50

1 t = 1 + 0.005t

1.4

0 1.6

1.0

1.0

1.0

0.8

0.8

0.8

0.6

0.6

0.4

0.4 10 t = 1 + 0.0005t

1.4 1.3 1.2 1.1 1.0 0.9 0

100 t = 1 + 0.0005t

1.625 1.600 1.575 1.550 1.525 1.500 1.475 1.450

0.6 0

500 1000 1500 2000 10 t = 1 + 0.005t

1.5 1.4 1.3 1.2 1.1 1.0 0.9

500 1000 1500 2000

1.40

1.6

10 t = 1 + 0.05t

0

1 t = 1 + 0.5t

500 1000 1500 2000 100 t = 1 + 0.005t

1.60

500 1000 1500 2000

0 1.6

100 t = 1 + 0.05t

1.65

500 1000 1500 2000 10 t = 1 + 0.5t

0

500 1000 1500 2000

0

500 1000 1500 2000

500 1000 1500 2000

1.60

10 t = 1 + 5.0t

1.40 0

500 1000 1500 2000

1.65

100 t = 1 + 5.0t

1.65 1.60 1.55 1.50

1.45

1.45

0

1 t = 1 + 5.0t

1.45

1.50

1.50

1.40

1.50

1.55

1.55

500 1000 1500 2000

1.60

1.55

1.60

1.60

1.45

1.1

0

0.1 t = 1 + 5.0t

1.45

1.2 0

500 1000 1500 2000

1.50

1.3

0

0

1.55

1.4

0.8

500 1000 1500 2000

1.45

500 1000 1500 2000

1.5

1.0

0.01 t = 1 + 5.0t

0

1.50 0.1 t = 1 + 0.5t

1.60 1.55 1.50 1.45 1.40 1.35 1.30 1.25

500 1000 1500 2000

1.2

1.50

500 1000 1500 2000

0

1.4

1.55

0

1 t = 1 + 0.05t

1.4 1.2

500 1000 1500 2000

500 1000 1500 2000

1.40

1.55

1.45

1.35

1.6

500 1000 1500 2000

1.60

1.45

500 1000 1500 2000

1.45

1.65

1.0

0

1.50

1.60 1.55

0.4

1.55

1.65

1.50 1.40

1.65 1.60

0

1.2

1.2

1.5

0.1 t = 1 + 0.05t

1.60

1.2

0

500 1000 1500 2000

1.55

0.6 500 1000 1500 2000

1.55

1.4

0.8

0

1.60

0

0.01 t = 1 + 0.5t

1.65

1.60

500 1000 1500 2000 0.1 t = 1 + 0.005t

1.6

0.01 t = 1 + 0.05t

1.65

100 t = 1 + 0.5t

0

500 1000 1500 2000

1.45 0

500 1000 1500 2000

c1 Figure 11. Extensive grid search for several linear decay schedules of the form ρt = 1+c , both parameters spanning several orders 2 ·t of magnitude. Initial distribution ΠH0 corresponds to H0 = (5, ..., 0). No regularization (neither L2 nor entropic) is used. The value 0.1 ρt = 1+0.0005·t appears to be the winner. We plot the average empirical regret. This is to be compared with Figure 1.

20

Regularized policy gradient for MAB

B.2. Search for best entropy constants For the setting in Section 4.1.1, we give below the empirical results for entropy regularization in Figure 12; we set ρt with best value obtained in Figure 1. At odds with Figure 1 we see here that there is no clear winner and the best constant is in 1 the range 0.01-1, with lowest values being best when t is large; accordingly we take for our entropy tests γt = 1+0.2t to span all optimal ranges.

1.2

Regret

1.0 0.8 0.6

t = 0.1, t = 0.1, t = 0.1, t = 0.1, t = 0.1,

L2 = 0, L2 = 0, L2 = 0, L2 = 0, L2 = 0,

Ent = 0.01 Ent = 0.1 Ent = 1 Ent = 10 Ent = 100

1500

1750

2000

0.4 0.2 0

250

500

750

1000 1250 Time step (t)

Figure 12. Search for best γt constant for entropy. As before H0 = (5, ..., 0). No L2 regularization is used. There is no winner and curves seem to overlap quite a bit but values in the range 0.01 to 1 seem to belong to the best performing cluster, with small values being 1 increasingly efficient at t gets large. This orients us towards the decay rate γt = 1+0.2t used in latter tests. Cf. also Figure 1.

C. Comparison with other classes of algorithms One may ask what about other classes of algorithms such as UCB, Thompson Sampling, Adversarial bandit algorithms and so on. The short answer is: we do not compare with other classes of algorithms because our main point here is to investigate the relevance of the L2 regularization within the softmax parameterized policy gradient class, so we are somehow working conditional to the fact that the user has already chosen, for some reason10 , the softmax policy gradient algorithm and wants, if possible, to improve by regularizing. But, for the curious reader we provide in Figure 13 tests that confirm the common lore for e.g., the UCB algorithm: it performs well when there are not so many arms and the distribution is well behaved; on the contrary the performance deteriorates when the number of arms is increasing and the distribution is heavy tailed.

10

There can be many reasons to use softmax MAB over the other procedures, for instance when the number of arms is large, or when the arms averages q∗ may drift over time or when the number of arms itself is variable, or when the distributions R(a) of the arms are heavy tailed and so on.

21

Regularized policy gradient for MAB

2.5

=1.5, n_arms=10 =2.5, n_arms=10 =10, n_arms=10

Regret

2.0

=1.5, n_arms=50 =2.5, n_arms=50 =10, n_arms=50

1.5 1.0 0.5 0.0 0

250

500

750

1000 1250 Time step (t)

1500

1750

2000

Figure 13. Performance of the UCB algorithm. The number of degrees of fredom ν is a proxy for how much the reward distribution is heavy tailed, with ν = 1.5 being severely heavy tailed and ν = 10 a smooth example. We see that best results are for ν = 2.5 and ν = 10 and 10 arms; once we exit this smooth, low arm regime the regret is severely impacted, with results being most sensitive to ν. A quick check with Figure 10 confirms that L2 regularized MAB outperforms UCB in this case.

22