Paper deep dive
How Log-Barrier Helps Exploration in Policy Optimization
Leonardo Cesani, Matteo Papini, Marcello Restelli
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/22/2026, 5:16:59 AM
Summary
The paper introduces the Log-Barrier Stochastic Gradient Bandit (LB-SGB) algorithm to address the lack of explicit exploration in standard Stochastic Gradient Bandit (SGB) methods. By regularizing the SGB objective with a log-barrier function, the authors enforce a minimal exploration level, ensuring the policy does not collapse to the simplex boundary. They prove that LB-SGB achieves a sample complexity of O~(ε⁻¹) and eliminates the need for unrealistic assumptions regarding the sampling probability of the optimal arm, while also establishing a theoretical connection between log-barrier regularization and Natural Policy Gradient.
Entities (5)
Relation Signals (3)
LB-SGB → uses → Log-barrier regularization
confidence 100% · Log-Barrier Stochastic Gradient Bandit (LB-SGB) matches the sample complexity of SGB
LB-SGB → regularizes → SGB
confidence 90% · We propose to regularize the SGB objective with a log-barrier on the parametric policy
Log-barrier regularization → connectedto → Natural Policy Gradient
confidence 85% · We also show a connection between the log-barrier regularization and Natural Policy Gradient
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Recently, it has been shown that the Stochastic Gradient Bandit (SGB) algorithm converges to a globally optimal policy with a constant learning rate. However, these guarantees rely on unrealistic assumptions about the learning process, namely that the probability of the optimal action is always bounded away from zero. We attribute this to the lack of an explicit exploration mechanism in SGB. To address these limitations, we propose to regularize the SGB objective with a log-barrier on the parametric policy, structurally enforcing a minimal amount of exploration. We prove that Log-Barrier Stochastic Gradient Bandit (LB-SGB) matches the sample complexity of SGB, but also converges (at a slower rate) without any assumptions on the learning process. We also show a connection between the log-barrier regularization and Natural Policy Gradient, as both exploit the geometry of the policy space by controlling the Fisher information. We validate our theoretical findings through numerical simulations, showing the benefits of the log-barrier regularization.
Tags
Links
- Source: https://arxiv.org/abs/2603.15001v1
- Canonical: https://arxiv.org/abs/2603.15001v1
Trouble viewing inline? Open PDF directly →
Full Text
157,488 characters extracted from source content.
Expand or collapse full text
How Log-Barrier Helps Exploration in Policy Optimization Leonardo Cesani Matteo Papini Marcello Restelli Abstract Recently, it has been shown that the Stochastic Gradient Bandit (SGB) algorithm converges to a globally optimal policy with a constant learning rate. However, these guarantees rely on unrealistic assumptions about the learning process, namely that the probability of the optimal action is always bounded away from zero. We attribute this to the lack of an explicit exploration mechanism in SGB. To address these limitations, we propose to regularize the SGB objective with a log-barrier on the parametric policy, structurally enforcing a minimal amount of exploration. We prove that Log-Barrier Stochastic Gradient Bandit (LB-SGB) matches the sample complexity of SGB, but also converges (at a slower rate) without any assumptions on the learning process. We also show a connection between the log-barrier regularization and Natural Policy Gradient, as both exploit the geometry of the policy space by controlling the Fisher information. We validate our theoretical findings through numerical simulations, showing the benefits of the log-barrier regularization. Machine Learning, ICML 1 Introduction Stochastic gradient algorithms have been widely studied in the context of Reinforcement Learning (RL, Sutton and Barto, 2018) and Multi-Armed Bandit (MAB, Lattimore and Szepesvári, 2020) problems. Starting from foundational algorithms such as REINFORCE (Williams, 1992), and GPOMDP/PGT (Baxter and Bartlett, 2001; Sutton et al., 1999), Policy Gradient (PG) methods have become a standard tool for direct policy optimization. These methods have also been effectively adapted to modern deep architectures, leading to the development of algorithms showing impressive performance (Lillicrap et al., 2015; Schulman et al., 2017; Haarnoja et al., 2018; Ahmadian et al., 2024; Shao et al., 2024; Ouyang et al., 2022). Despite their empirical success, providing rigorous finite-time convergence guarantees for PG methods remains a significant challenge (Agarwal et al., 2021; Yuan et al., 2022). Mei et al. (2020b) proposed to study policy gradient methods in the simplified setting of MABs with parametric softmax policies, to gain insights on the behavior of this family of algorithms that could transfer to the more general RL problem. In this “gradient bandit” setting (Sutton and Barto, 2018, Section 2.7), REINFORCE assumes a very simple form and is amenable to detailed analysis. Following Mei et al. (2023), we call it Stochastic Gradient Bandit (SGB). In this work, we will focus on the sample complexity of gradient bandits, that is, the number of samples or pulls required to find an ϵε-optimal policy.111Sample complexity results can be easily translated into convergence rates (Mei et al., 2023). Also note that iteration complexity coincides with sample complexity in the bandit setting. For a discussion of regret guarantees, see (Baudry et al., 2025) instead. For detailed related works, refer to Appendix A. Mei et al. (2023) showed that SGB enjoys (ϵ−1)O(ε^-1) sample complexity. However, Baudry et al. (2025) highlighted the dependence of this upper bound on a potentially large problem-dependent constant that was previously neglected and hides a problematic assumption on how often the learning algorithm samples the optimal arm. This could be part of a broader problem. In fact, unlike classic bandit algorithms that explicitly address the exploration-exploitation dilemma through optimism in the face of uncertainty (Auer et al., 2002) or posterior sampling (Agrawal and Goyal, 2012), vanilla PG methods such as SGB lack a direct mechanism to control exploration, relying solely on the stochasticity of the policy. As the gradient updates drive the policy toward the boundary of the probability simplex, the gradient itself vanishes, possibly leading to premature convergence to sub-optimal policies. To mitigate this problem, practitioners often resort to entropy regularization (Haarnoja et al., 2018). In the context of gradient bandits, it has been studied only in combination with exact gradients (Mei et al., 2020b), where it significantly improves the iteration complexity, but the sample complexity is meaningless. Several works in the RL literature have argued that, although speeding up convergence by smoothing the objective landscape, entropy regularization provides insufficient support to exploration (Ahmed et al., 2019; O’Donoghue et al., 2020; Mei et al., 2021a; Bolland et al., 2025). Our proposal is to instead adopt a log-barrier regularization, which provides a more aggressive behavior near the simplex boundary, structurally enforcing that minimum level of exploration that might be missing from SGB (and its entropy-regularized counterpart). Contributions. We adopt the MAB framework as a test bed to analyze the dynamics of policy optimization with log-barrier regularization. In particular: • We introduce Log-Barrier Stochastic Gradient Bandit (LB-SGB), a PG algorithm designed to guarantee a minimum amount of exploration; • We analyze the convergence guarantees of LB-SGB, establishing ~(ϵ−1) O(ε^-1) sample complexity, comparable to state-of-the-art algorithms under the same assumptions; • We show that LB-SGB eliminates the need for an implicit assumption regarding the sampling probability of the optimal arm during the learning process, just converging at a slower rate, (ϵ−7)O(ε^-7); • We show a connection between log-barrier regularization and Natural Policy Gradient (NPG, Kakade, 2001; Mei et al., 2022), shedding light on the role of Fisher information in exploration. • We empirically show that log-barrier regularization improves convergence to the optimal policy as the number of arms K increases compared to (entropy regularized) SGB, and NPG. Complete proofs of all theoretical statements are provided in Appendix C. 2 Preliminaries Notation. For a measurable set X, we denote as Δ() (X) the set of probability measures over X. For P∈Δ()P∈ (X), we denote with p its density function w.r.t. a reference measure that we assume to exist whenever needed. We will use x∼Px P to express that random variable x is distributed according to P. For n∈ℕn , we denote ⟦n⟧≔0,1,…,n n \0,1,…,n\. For a∈ℝa , we define (a)+=max0,a.(a)^+= \0,a\. Given a symmetric matrix A∈ℝd×dA ^d× d, we denote its eigenvalues with μi _i, where i∈⟦D⟧i∈ D . Given two matrices A and B, we say that A⪰BA B if the matrix A−BA-B is positive semidefinite. K-armed Bandit. We formulate the stochastic K-armed bandit as a sequential decision-making problem where, at each time t∈⟦T⟧t∈ T , the learner chooses an action at∈⟦K⟧a_t∈ K and receives a reward Rt(at)R_t(a_t). This reward Rt(at)R_t(a_t) is the ata_t-th component of a random reward vector t∈ℝK R_t ^K, whose components are sampled i.i.d. from an unknown multivariate distribution ν supported on [−Rmax,Rmax]K[-R_ ,R_ ]^K. Given νa _a as the a-th component of ν, the mean reward of each action is defined as r(a)≔Rt(a)∼νa[Rt(a)]r(a) _R_t(a) _a [R_t(a) ]. The vector of mean reward for each arm is denoted ≔(r(a))a∈⟦K⟧ r (r(a))_a∈ K . Following Mei et al. (2023), we make the following assumption on r. Assumption 2.1. (No ties) For all a,a′∈⟦K⟧a,a ∈ K , if a≠a′a≠ a , then r(a)≠r(a′)r(a)≠ r(a ). Furthermore, we define the optimal arm as a∗≔argmaxa∈⟦K⟧r(a)a^* _a∈ K r(a) which, under Assumption 2.1, is unique and the optimal deterministic policy π∗≔argmaxππ⊤π^* _π r. Finally, we denote the optimal reward gap as Δ∗≔mina≠a∗|r(a∗)−r(a)| ^* _a≠ a^* |r(a^*)-r(a) |, and the minimum reward gap as Δ=mina≠a′|r(a)−r(a′)| = _a≠ a |r(a)-r(a ) |. Stochastic Gradient Bandit Algorithm. The Stochastic Gradient Bandit (SGB) algorithm (Sutton and Barto, 2018) parametrizes a stochastic policy π _ θ over actions a∈⟦K⟧a∈ K using a softmax distribution: π(a)=exp(a)∑b∈⟦K⟧exp(b), _ θ(a)= \ θ(a)\ _b∈ K \ θ(b)\, (1) where ∈ℝK θ ^K is a vector of parameters representing action preferences. Starting from an initial parameter vector 1=K θ_1= 0_K, inducing an uniform policy, the algorithm seeks to learn a policy maximizing the expected reward ()≔π⊤J( θ) _ θ r, where ∈ℝK r ^K is the vector of mean rewards. Since r is unknown, SGB employs Stochastic Gradient Ascent (SGD) with the update rule: t+1←+α∇t(πt⊤^t), θ_t+1← θ+α _ θ_t ( _ θ_t r_t ), where ^t∈ℝK r_t ^K is an unbiased importance-sampling estimator of r with components r^t(a)≔at=aπt(a)Rt(ar) r_t(a) I\a_t=a\ _ θ_t(a)R_t(a_r). The stochastic gradient ∇(πt⊤^t) _ θ ( _ θ_t r_t ) is an unbiased estimator of ∇t(πt⊤t)=(diag(πt)−πtπt⊤)t _ θ_t ( _ θ_t r_t )= (diag( _ θ_t)- _ θ_t _ θ_t ) r_t. The pseudo-code for the SGB algorithm can be found in Appendix B. 3 Limitations of SGB In this section, we analyze the theoretical limitations of current Stochastic Gradient Bandit (SGB) algorithms. We begin by reviewing the structural flaw in existing convergence analyses identified by Baudry et al. (2025), showing that these rely on implicit assumptions about exploration that fail in worst-case scenarios. The convergence analysis of SGB in Mei et al. (2023) relies on a hidden assumption regarding the sampling probability of the optimal arm, originating from a flaw in the proof. As identified by Baudry et al. (2025), when this implicit assumption is violated, the resulting sample complexity result may become vacuous. Specifically, the analysis in Mei et al. (2023) overlooks the impact of “extreme” events, i.e., low-probability trajectories where an initial sequence of unfavorable rewards causes the sampling probability of the optimal arm, πt(a∗) _ θ_t(a^*), to vanish. In these scenarios, the constant governing the sample complexity result may become unbounded. This discrepancy originates from a structural error in the convergence proof of SGB (Theorem 5.5, Mei et al. (2023)), in which the term ζ∗=inft≥1[πt2(a∗)]ζ^*= _t≥ 1E[π^2_ θ_t(a^*)] is treated as a constant independent on the sub-optimality gap δ()≔(π∗−π)⊤δ( θ) (π^*- _ θ) r. In the stochastic setting, the sampling probability π(a∗) _ θ(a^*) is a trajectory-dependent random variable; therefore, its infimum cannot be assumed independent on the policy dynamics, as the history of rewards determines both the current parameters t θ_t and the probability of the optimal arm. To address this analytical flaw, Baudry et al. (2025) propose shifting the dependence to the second moment of the reciprocal probability, defining c∗≔supt[πt(a∗)−2]c^* _tE [ _ θ_t(a^*)^-2 ], which yields a sample complexity of (c∗ϵ−1)O (c^*ε^-1 ). However, while Mei et al. (2023) prove that the probability of the optimal arm remains strictly positive (Theorem 5.1), this does not preclude the policy from becoming arbitrarily close to zero on specific trajectories. This requires a stronger condition, namely an uniform lower bound πt(a∗)≥C>0 _ θ_t(a^*)≥ C>0 almost surely, to ensure the boundedness of c∗c^*. Furthermore, even if a finite c∗c^* were to exist, it remains theoretically uncharacterized in the standard SGB framework. Without explicit control over “extreme” events, where the policy approaches the simplex boundary (Baudry et al., 2025; Fan and Glynn, 2025), the second moment of the reciprocal probability may diverge, rendering the resulting convergence guarantee vacuous. We argue that the problem we described is due to the lack of an explicit exploration mechanism in the SGB algorithm. To address this, we propose decoupling reward maximization from the exploration requirement by formulating the learning objective as a Constrained Optimization Problem (COP) with constraints on the learned action probabilities. We solve the COP using an Interior-Point Method (IPM) with a log-barrier, ensuring constraint satisfaction throughout the learning process. 4 Log-Barrier Stochastic Gradient Bandit In this section, we present the optimization framework addressed by our proposal. Then, we propose Log-barrier Stochastic Gradient Bandit (LB-SGB), a version of SGB with log-barrier regularization to ensure that the learned probability assigned to each action never vanishes. Furthermore, we present the properties of the regularized objective, which will be used to prove the convergence results in Section 5. The Optimization Framework. Our goal is to learn a parametric policy π _ θ maximizing the expected reward ()J( θ), under the constraint that the learned policy never gets too close to the boundary of the simplex. For this purpose, we reformulate the PG objective as follows: max∈ℝK()s.t.π(a)>0,∀a∈⟦K⟧. _ θ ^KJ( θ) .t. _ θ(a)>0,~∀ a∈ K . (2) To solve the Constrained Optimization Problem (COP) of Equation (2) while maintaining feasibility throughout the learning process, we employ an Interior Point Method (IPM, Boyd and Vandenberghe, 2004). Specifically, we approximate the COP by regularizing the performance index with a logarithmic barrier function, ℬη()≔1η∑a∈⟦K⟧logπ(a)B_η( θ) 1η _a∈ K _ θ(a), which penalizes solutions that are too close to the simplex boundaries. The influence of this regularization is governed by a barrier parameter η>0η>0, such that 1/η1/η represents the strength of the penalty. As discussed in Section 5, the barrier parameter should be chosen big enough to contrast the bias of the learned policy w.r.t. the optimal policy. This means that the effect of the regularization on the objective is minimal, but still enough to enforce a minimum sampling probability for all arms. The resulting regularized objective is defined as: Φη()≔()+1η∑a∈⟦K⟧logπ(a). _η( θ) ( θ)+ 1η _a∈ K _ θ(a). (3) The LB-SGB Algorithm. To optimize the regularized objective in Equation (3), the LB-SGB algorithm implements the SGD update rule: t+1←t+α∇^Φη(t), θ_t+1← θ_t+α ∇_ θ _η( θ_t), where ∇^Φη(t) ∇_ θ _η( θ_t) is the sample-based gradient of Equation (3). The complete pseudo-code for LB-SGB is provided in Appendix B (Algorithm 4). The gradient ∇^tΦη() ∇_ θ_t _η( θ) is composed of two distinct terms. The first term represents the stochastic gradient of the performance index ∇() _ θJ( θ), using the unbiased importance sampling estimator ∇(πt⊤^t) _ θ ( _ θ_t r_t ) presented in Section 2. In contrast, the gradient of the barrier term ∇ℬη()≔1η(−Kπ) _ θB_η( θ) 1η( 1-K _ θ) is deterministic. This means that ∇^Φη() ∇_ θ _η( θ) is an unbiased estimator of ∇Φη() _ θ _η( θ) and has the same variance as the SGB estimator. We refer to Appendix B.4 for a complete derivation of ∇Φη() _ θ _η( θ). Properties of the Barrier Function. Here, we present the regularity properties of the barrier-augmented objective Φη() _η( θ). Detailed derivations are provided in Appendix C.1. Standard convergence analyses for non-convex optimization often rely on global L-smoothness (Mei et al., 2020b); however, the softmax PG exhibits a non-uniform curvature and, to capture this behavior, we leverage the framework of non-uniform smoothness introduced by Mei et al. (2021b). The first property characterizes the local curvature of the optimization landscape, showing that the Hessian’s spectral radius is adaptively bounded by the norm of the gradient of the regularized objective function. Lemma 4.1 (Non-uniform Smoothness). For all ∈ℝK θ ^K, and for all ∈ℝK r ^K the spectral radius of the Hessian matrix H()∈ℝK×KH( θ) ^K× K of Φη() _η( θ) is upper bounded by a function of θ. Precisely, for all ∈ℝK y ^K, |⊤H()|≤3(‖∇Φη()‖2+5Kη)‖22. | y H( θ) y |≤ 3 (\| _ θ _η( θ)\|_2+ 5Kη )\| y\|_2^2. Lemma 4.1 characterizes the local geometry of the regularized objective. The Hessian bound consists of two terms: a gradient-dependent component, indicating that the landscape flattens near stationary points, and a baseline curvature (Kη)O ( Kη ) induced by the log-barrier. This constant term modifies the optimization geometry to enforce the learned policy to be bounded away from the simplex constraints. The regularization term inevitably introduces a shift in the stationary points. Following Mei et al. (2020b), we present a generalized Łojasiewicz inequality that accounts for this shift. Lemma 4.2 (Weak Non-Uniform Łojasiewicz). Under Assumption 2.1, we have, ‖∇Φη()‖2≥(π(a∗)(r(a∗)−π⊤)−Kη)+. \| _ θ _η( θ)\|_2≥ ( _ θ(a^*)(r(a^*)- _ θ r)- Kη )^+. Lemma 4.2 establishes a gradient domination condition adapted to the regularized objective. It explicitly relates the gradient norm to the sub-optimality of the policy, showing that, as the gradient approaches zero, the algorithm converges to a neighborhood of the optimal solution. The size of this neighborhood is determined by the term Kη Kη, which quantifies the unavoidable bias introduced by the barrier function to maintain feasibility. 5 Convergence of LG-SGB In this section, we discuss the convergence of the LB-SGB algorithm. Based on the properties presented in Section 4, we show the general convergence results under the same assumptions of Mei et al. (2023). Then, we prove that, through an appropriate selection of the learning rate α and the barrier parameter η, the LB-SGB algorithm guarantees that πt(a∗) _ θ_t(a^*) is bounded away from zero. Building upon this guarantee, we derive the worst-case iteration complexity. The proofs for all the results presented in this section can be found in Appendix C. Before stating the convergence results, we begin by establishing the stochastic properties of the LB-SGB gradient estimator. Following the framework proposed by Mei et al. (2023) for SGB, we show that the second moment of the stochastic gradient is (partially) controlled by the norm of the true gradient. This result allows us to provide convergence guarantees with constant learning rates. Lemma 5.1 (Self-bounding Property). Under Assumption 2.1, for all t≥1t≥ 1, the stochastic gradient estimator of Φη(t) _η( θ_t) satisfies: t[‖∇^Φη(t)‖22]≤16Rmax3K3/2Δ2‖∇Φη(t)‖2+b(η), _t [\| ∇_ θ _η( θ_t)\|_2^2 ]≤ 16R_ ^3K^3/2 ^2\| _ θ _η( θ_t)\|_2+b(η), where b(η)≔2Kη(4Kη+16Rmax3K3/2Δ2)b(η) 2Kη ( 4Kη+ 16R_ ^3K^3/2 ^2 ). Lemma 5.1 establishes that the magnitude of the noise vanishes as the gradient approaches zero. In fact, as the policy approaches stationarity, the dominant source of noise diminishes. However, the presence of the bias term b(η)b(η) is due to regularization and represents a persistent noise floor that persists even when the gradient is close to zero. 5.1 Convergence Analysis Assuming Bounded c∗c^* Building upon the regularity properties established in Section 4 and the self-bounding nature of the log-barrier estimator, we can now characterize the convergence guarantees of LB-SGB analysing the evolution of the sub-optimality gap [(π∗−πt)⊤t]E [ (π^*- _ θ_t ) r_t ]. The following result characterizes the performance of LB-SGB under the same assumptions as (Mei et al., 2023). Under the condition that the expected second moment of the reciprocal probability c∗c^* remains bounded, the following theorem shows that the LB-SGB algorithm achieves a linear convergence rate toward a neighbourhood of the optimal policy. Theorem 5.2 (Convergence Rate and Iteration Complexity). Under Assumption 2.1, selecting the learning rate α=(1)α=O(1), the LB-SGB algorithm guarantees: [δ(T)] [δ( θ_T) ] ≤(1−122α2bηc∗)T[δ(0)]+2bc∗η, ≤ (1- 12 2α^2bη c^* )^TE [δ( θ_0) ]+ 2bc^*η, where [δ(t)]≔[(π∗−πt)⊤t]E [δ( θ_t) ] [ (π^*- _ θ_t ) r_t ], b=(K)b=O(K), and c∗≔supt≥0[1πt(a∗)2]>0c^* _t≥ 0E [ 1 _ θ_t(a^*)^2 ]>0. In particular, for sufficiently small ϵ>0ε>0 and selecting the barrier parameter as η=(ϵ−1)η=O (ε^-1 ), the number of iterations sufficient to ensure [(π∗−πT)⊤]≤ϵE [ (π^*- _ θ_T ) r ]≤ε is: T=O~(K3/2Δ−2ϵ−1), T= O (K^3/2 ^-2ε^-1 ), where ~ O hides logarithmic factors. Theorem 5.2 provides a last-iterate convergence guarantee for LB-SGB to an ϵε-optimal policy under the same assumptions of Mei et al. (2023). Our approach exploits a recurrence of the instantaneous regret (Montenegro et al., 2024) that allows controlling the bias term β=2bc∗ηβ= 2bc^*η. This analysis highlights a structural trade-off: while the log-barrier prevents the vanishing gradient problem by ensuring that the optimal action a∗a^* is sampled with sufficient frequency, it simultaneously prevents the policy from learning the optimal deterministic policy. Hence, it is necessary to carefully tune the barrier parameter η to ensure sufficient exploration without preventing it from learning the optimal one. In the limit η→∞η→∞, the regularized objective Φη() _η( θ) asymptotically recovers the undergularized performance index ()J( θ), eliminating the bias β. However, without the barrier, this regime risks the divergence of c∗c^*, as the policy is no longer structurally prevented from forgetting the optimal action and approaching the simplex boundary. While Theorem 5.2 matches the rate established by Mei et al. (2023) for a well-behaved c∗c^*, Theorem 5.5 will show that LB-SGB implicitly controls exploration to guarantee convergence even in the worst-case scenarios where c∗c^* is potentially unbounded. 5.2 Worst-case Sample Complexity Table 1: Comparison of sample complexities and learning rates for different PG algorithms. † We define c∗≔supt[πt(a∗)−2]c^* _tE [ _ θ_t(a^*)^-2 ]. Reference Sample Complexity Learning Rate α Method Assumption on c∗†c^* Mei et al. (2023) (ϵ−1)O (ε^-1 ) (1)O (1 ) Vanilla PG (SGB) ✓ This work ~(ϵ−) O (ε^-1 ) () O (1 ) Log-barrier ✓ Zhang et al. (2021) (ϵ−6)O (ε^-6 ) (1/logt)O (1/ t ) Log-barrier, Clipping ✗ Ding et al. (2022) (ϵ−4.5)O (ε^-4.5 ) (1/t)O (1/ t ) Log-barrier, Momentum ✗ This work (ϵ−) O (ε^-7 ) (ϵ) O (ε^3 ) Log-barrier ✗ In this section, we show that LB-SGB converges to the optimal policy without assuming c∗c^* to be bounded. We will first show that LB-SGB provides a connection between πt(a∗) _ θ_t(a^*) and the gradient ‖∇Φη(t)‖2\| _ θ _η( θ_t)\|_2. Then, we will provide the local and global convergence properties of LB-SGB, along with a regret bound. The following lemma provides a lower bound on the probability of the optimal arm. Lemma 5.3 (Bounded πt(a∗) _ θ_t(a^*)). For any t∈⟦T⟧t∈ T , the LB-SGB algorithm ensures, πt(a∗)≥(1K(1−η‖∇Φη(t)‖2))+ _ θ_t(a^*)≥ ( 1K (1-η\| _ θ _η( θ_t)\|_2 ) )^+ Lemma 5.3 provides the explicit mechanism ensuring that the exploration condition assumed in Section 5.1 is met. While this bound holds deterministically at every iteration t, we control the lower bound of πt(a∗) _ θ_t(a^*) by controlling the true gradient in expectation. By ensuring ‖∇Φη(t)‖2\| _ θ _η( θ_t)\|_2 remains small on average, LB-SGB induces a strictly positive lower bound on πt(a∗) _ θ_t(a^*) in expectation, preventing the policy from collapsing to the simplex boundary. Theorem 5.4 shows that, by properly selecting the hyperparameters of the problem, we can effectively control the gradient norm ‖∇Φη()‖2\| _ θ _η( θ)\|_2. Theorem 5.4 (Local Convergence). Under Assumption 2.1, and after T0=(ηK5/2α2)T_0=O ( ηK^5/2α^2 ), and choosing the learning rate α≤(Δ2/K3/2)α ( ^2/K^3/2 ), the LB-SGB algorithm guarantees: 1T∑t=0T−1[‖∇Φη(t)‖22]≤(K5/2αηΔ2). 1T _t=0^T-1E [\| _ θ _η( θ_t)\|_2^2 ] ( K^5/2αη ^2 ). Theorem 5.4 establishes that the gradient norm, and consequently the tightness of the lower bound in Lemma 5.3, is explicitly controllable via the barrier parameter η and the learning rate α. Now, we can show the sample complexity required by the LB-SGB algorithm to converge to an ϵε-optimal policy without assuming the existence of a bounded c∗c^*. Theorem 5.5 (Worst-case Sample Complexity). Under Assumption 2.1, for a target accuracy ϵ>0ε>0, and selecting the learning rate α=(ϵ3)α=O (ε^3 ) and the barrier parameter η=(ϵ−1)η=O (ε^-1 ) the number of iterations T required by the LB-SGB to guarantee 1T∑t=1T[(π∗−πt)⊤t]≤ϵ 1T _t=1^TE [(π^*- _ θ_t) r_t ]≤ε is: T=(K17/2Δ2ϵ−7). T=O (K^17/2 ^2ε^-7 ). We note that, unlike Theorem 5.2, Theorem 5.5 establishes average-iterate convergence by analyzing the average instantaneous regret. This approach is necessary because the bias introduced by the lower-bound on πt(a∗) _ θ_t(a^*) prevents the direct application of the last-iterate proof technique. Crucially, this result also implies best-iterate convergence to the optimal policy. Finally, the following corollary allows us to bound the regret of LB-SGB. Corollary 5.6 (Regret). Under Assumption 2.1, given a target accuracy ϵ>0ε>0 and choosing the learning rate to be α=(T−3/7)α=O (T^-3/7 ) and the parameter η=(T1/7)η=O (T^1/7 ), the LB-SGB ensures sub-linear regret. Specifically, we have, [∑t=1T(π∗−πt)⊤t]≤(Δ−2/7T6/7) [ _t=1^T(π^*- _ θ_t) r_t ] ( ^-2/7T^6/7 ) The result of Corollary 5.6 establishes a sub-linear regret bound for LB-SGB. It is important to note that the parameters used to prove this result are horizon-dependent and, therefore, this does not constitute an anytime regret guarantee.222Note that the Δ is the minimum reward gap defined in Section 2, which is different from the sub-optimality gap Δ∗ ^*. 5.3 Discussion Table 1 summarizes our theoretical contributions in relation to existing state-of-the-art results. Specifically, assuming c∗<∞c^*<∞, LB-SGB matches the optimal ~(ϵ−1) O (ε^-1 ) sample complexity result established in Mei et al. (2023) up to logarithmic factors. The ~(ϵ−7) O (ε^-7 ) sample complexity bound, despite being significantly larger, is obtained without any assumptions on c∗c^* and without any algorithmic tweaks, only relying on the properties of the log-barrier regularization. We can also compare it with other log-barrier regularized PG methods from tabular MDPs with softmax policies, a generalization of gradient bandits. Zhang et al. (2021) obtained ~(ϵ−7) O (ε^-7 ) by explicitly clipping the actions’ probabilities, while Ding et al. (2022) achieved ~(ϵ−4.5) O (ε^-4.5 ) by leveraging variance reduction techniques. Our upper bound, although larger, shows that the log-barrier alone is sufficient. We conjecture that our current analysis is not tight and leaves room for future improvements of the sample complexity with no or minimal algorithmic modifications. 6 Connection between Log-barrier and NPG In this section, we show a connection between LB-SGB and the Natural Policy Gradient (NPG) algorithm, highlighting the role of Fisher information in exploration. We start presenting NPG in the bandit setting, highlighting its limitations. Then, exploiting a reparametrization of the softmax policy, we show that LB-SGB can be recovered by imposing constraints on the Fisher Information Matrix (FIM), which is defined as: F() F( θ) =a∼π[∇logπ(a)∇logπ(a)⊤] =E_a _ θ [ _ θ _ θ(a) _ θ _ θ(a) ] =diag(π)−ππ⊤, =diag( _ θ)- _ θ _ θ , NPG in Bandits. The NPG algorithm (Kakade, 2001) preconditions the gradient update with the inverse FIM, updating the parameters in the direction of F()−1∇()F( θ)^-1 _ θJ( θ), ensuring that the optimization step is adjusted according to the local curvature of the policy space rather than the Euclidean geometry of the parameters (Amari, 1998). Due to the singularity of the FIM under softmax parametrization, the natural gradient cannot be directly computed via explicit inversion. Hence, in order to obtain the NPG update rule it is necessary to find the solutions of the linear system F()⋅x=(at)F( θ)· x= g(a_t), where (at)=∇logπ(at)=at−π g(a_t)= _ θ _ θ(a_t)=e_a_t- _ θ being the score of the policy given the sampled arm ata_t, and ate_a_t denotes the one-hot encoding of action ata_t (Chung et al., 2021, Appendix D.2). Solving the system, we obtain a sparse update rule, which updates only the parameter associated to the played action: t+1←t+α⋅Rt(at)(1πt(at)a). θ_t+1← θ_t+α· R_t(a_t) ( 1 _ θ_t(a_t)e_a ). A detailed description of the NPG algorithm is provided in Appendix B. Despite its theoretical benefits, NPG is known to suffer from premature convergence to suboptimal arms due to its aggressive update rule. Specifically, Mei et al. (2022) proved that unregularized NPG has a positive probability of converging to sub-optimal actions. This issue is due to the algorithm’s tendency to drive the policy parameters toward the simplex boundaries too quickly. As noted by Chung et al. (2021), this results in over-committal behavior, where the algorithm repeatedly samples a potentially suboptimal arm, suppressing the exploration required to identify the optimal action. While the aggressive behavior of NPG often leads to instability in practice, the algorithm serves as a fundamental pillar for establishing global convergence results of PG. These theoretical guarantees, however, typically necessitate a specific regularity condition on the policy’s geometry to ensure the FIM remains a well-behaved metric for the update. Fisher-non-degeneracy. Theoretical analyses of PG methods with generic policy parametrization frequently rely on the Fisher-non-degeneracy assumption to guarantee global convergence rates (Liu et al., 2020; Ding et al., 2022; Fatkhullin et al., 2023). This condition states that the curvature of the parameter space remains well-behaved, ensuring that the FIM acts as a strictly positive-definite preconditioner of the gradient of the performance index. Assumption 6.1 (Fisher-non-degeneracy). For all ∈ℝK θ ^K there exist some constant μF>0 _F>0 such that the FIM induced by the policy π _ θ satisfies F()⪰μFF( θ) _F I, where I is the identity matrix. The Fisher-non-degenerate setting implicitly guarantees that the agent effectively explores the action space (Ding et al., 2022). To characterize this property, we interpret the FIM as a measure of feature coverage. Proposition 6.1 (FIM as Covariance Matrix). Consider the softmax parameterization where a∈ℝKe_a ^K denotes the canonical basis vector for action a. The Fisher Information Matrix F()F( θ) is equivalent to the covariance matrix of the action features ae_a under the policy distribution π _ θ. Under this interpretation of the FIM, proved in Appendix B.3.1, requiring F()F( θ) to be strictly positive definite ensures that the policy maintains non-zero variance along all directions of the simplex, hence maintaining sufficient coverage along all the directions of the feature space. In the context of SGB with softmax parametrization, this assumption is violated. The standard softmax parametrization (see Equation (1)) has K linearly dependent parameters, making the FIM singular by construction. Hence, we can consider a reparametrization of the softmax policy (Metelli et al., 2022) that projects the parameter onto a space of dimension K−1K-1, obtaining a policy with the parameter ¯∈ℝK−1 θ ^K-1 defined as: π¯(a)=eθ¯(a)1+∑beθ¯(b)if a≠aK1−∑i=1K−1π¯(ai)otherwise. _ θ(a)= cases e θ(a)1+ _be θ(b)&if a≠ a_K\\ 1- _i=1^K-1 _ θ(a_i)&otherwise cases. However, even with the reparametrized policy, the Fisher-non-degeneracy assumption is violated when π¯ _ θ approaches a deterministic policy (Ding et al., 2022). In fact, when the policy is close to the boundaries of the simplex, the variance of the score function vanishes. Consequently, the smallest eigenvalue of the FIM decays to zero, and F(¯)F( θ) cannot be uniformly lower-bounded by a positive constant μF _F. (a) K=100K=100 (b) K=1000K=1000 Figure 1: Comparison between SGB and LB-SGB with K=100,1000K=\100,1000\ and Δ∗=0.1 ^*=0.1 (100100 runs ±95%± 95\% C.I.). Spectral Regularization. To overcome the singularity of the FIM in SGB with softmax policy parametrization, rather than relying on the Fisher-non-degenerate assumption or the NPG update rule, we define a COP that imposes constraints on the FIM’s eigenvalues. Considering the reparametrization of the softmax policy discussed above, the COP can be written as: max¯∈ℝK−1(¯)s.t.μi(F(¯))>0∀i∈⟦K−1⟧. _ θ ^K-1J( θ) .t. _i(F( θ))>0 ∀ i∈ K-1 . Since solving the constrained problem directly is not tractable, we can approximate the constraint using the log-barrier method with η being the barrier parameter, obtaining: Φη(¯)=(¯)+1ηlogdet(F(¯)), _η( θ)=J( θ)+ 1η (F( θ) ), where we used the fact that ∑i=1K−1logμi(F(¯))=logdetF(¯) _i=1^K-1 _i(F( θ))= ( θ) (a detailed derivation is provided in Appendix B.3.2). Now, computing the determinant of the FIM for the reparametrized Softmax policy, we obtain: Φη(¯)=(¯)+1η∑i=1Klogπ¯(ai), _η( θ)=J( θ)+ 1η _i=1^K _ θ(a_i), recovering the log-barrier regularized objective function of LB-SGB from Section 4. This means that LB-SGB translates the Fisher-non-degeneracy assumption into an explicit constraint on the policy optimization process. In fact, when the constraints are satisfied, the minimum eigenvalue of the FIM is strictly larger than zero, meaning that every direction of the feature space, described by the basis vectors a e_a, has been covered. (a) Δ∗=0.05 ^*=0.05 (b) Δ∗=0.005 ^*=0.005 Figure 2: Comparison between SGB and LB-SGB with K=100K=100 and Δ∗=0.05,0.005 ^*=\0.05,0.005\ (100100 runs ±95%± 95\% C.I.). This shows a connection between LB-SGB and the information-geometric principles of NPG. Both algorithms exploit the geometry induced by the Fisher metric, but while NPG preconditions the gradient directly exploiting the Fisher information in the update rule, LB-SGB restricts the optimization trajectory in the area of the feature space in which the Fisher geometry is non-degenerate. Consequently, LB-SGB captures the second-order curvature information similarly to NPG, but preventing the “over-committal” behavior, not by inverting the FIM but regularizing the policy to ensure the metric remains strictly positive definite throughout the learning process. Finally, this analysis offers a novel perspective on the role of geometric assumptions in policy gradient methods. It has been established that, under the Fisher-non-degeneracy assumption, the convergence dynamics of vanilla PG mimic those of NPG (Ding et al., 2022). By actively enforcing the positive definiteness of the FIM through constraints, LB-SGB effectively integrates the Fisher information dynamically, without the computational cost of matrix inversion. Furthermore, establishing the equivalence between the FIM determinant and the log-barrier penalty provides a concrete operational interpretation of the abstract Fisher-non-degeneracy assumption. Rather than serving merely as a technical regularity condition, this analysis reveals it as a structural requirement for sufficient exploration, which LB-SGB explicitly satisfies by design. 7 Experimental Results In this section, we empirically validate the theoretical results derived in Section 5. The code to run the experiments is provided in the supplementary materials. We evaluate the performances of SGB and LB-SGB. We will focus on the convergence dynamics of the policy πt _ θ_t toward the optimal action a∗a^*. We will compare the algorithms across MAB instances with varying numbers of arms K and analyze their behavior across instances with different sub-optimality gaps Δ∗ ^*. Finally, we show that LB-SGB achieves better performance than SGB with entropy regularization (ENT) and NPG.The experiments aggregate results across N=100N=100 independent runs, and the learning rate used is α=0.1α=0.1. In the plots, the solid curve represent the sample mean, while the shaded regions denote the 95%95\% confidence intervals computed using t-intervals. Experimental details are provided in Appendix D. Sensitivity to Number of Arms K. In this experiment, we investigate the scalability of LB-SGB by evaluating the convergence dynamics of πt(a∗) _ θ_t(a^*) across MAB instances with a high number of actions, specifically K=100,1000K=\100,1000\ with the minimum gap w.r.t. the optimal arm of Δ∗=0.1 ^*=0.1 and a maximum reward Rmax=3R_ =3. The time horizon used is T=5⋅106T=5· 10^6, with the exploration parameters are chosen to be η=2⋅103(K=100)η=2· 10^3~(K=100) and η=5⋅103(K=1000)η=5· 10^3~(K=1000). As shown in Figure 1, SGB fails to achieve optimal convergence, learning a suboptimal policy for both MAB instances. Conversely, LB-SGB ensures convergence to the optimal policy even with a high number of arms. This result suggests that the sample complexity obtained in Theorem 5.5 could be improved. Sensitivity to Sub-optimality Gap Δ∗ ^*. The difficulty of a MAB problem may be determined by the minimum gap with respect to the optimal arm Δ∗ ^*. In this experiment, we compare the performance for Δ∗=0.05,0.005 ^*=\0.05,0.005\ with K=100K=100. We set the exploration parameter η=3⋅103(Δ∗=0.1)η=3· 10^3~( ^*=0.1) and η=2⋅103(Δ∗=0.1)η=2· 10^3~( ^*=0.1) over T=5⋅104T=5· 10^4 steps. Figure 2 illustrates that LB-SGB performs well even when the sub-optimality gap is very small. Comparison with ENT and NPG In this experiment, we compare LB-SGB, ENT and NPG in MAB instances with K=10,100K=\10,100\ with a minimum sub-optimality gap Δ∗=0.1 ^*=0.1. The experiments have been performed selecting a learning rate α=0.1α=0.1, and Rmax=1R_ =1 when K=10K=10, Rmax=3R_ =3 when K=100K=100. Figure 3 shows the superior performance of LB-SGB w.r.t. the competitors, which are not able to learn the optimal policy. (a) K=10,Rmax=1K=10,~R_ =1 (b) K=100,Rmax=3K=100,~R_ =3 Figure 3: Comparison between LB-SGB, ENT and NPG with K=10,100K=\10,100\ and Δ∗=0.1 ^*=0.1 (100100 runs ±95%± 95\% C.I.). 8 Conclusions, Limitations, and Future Work In this work, we proposed LB-SGB, a PG algorithm that structurally enforces exploration through log-barrier regularization. By regularizing the objective with a log-barrier, we enforce a minimum level of exploration, preventing the policy from collapsing toward the simplex boundary. Our analysis shows that LB-SGB is significantly more robust than unregularized methods, matching state-of-the-art sample complexity under the same assumptions, but, unlike vanilla SGB, it maintains global convergence guarantees in worst-case scenarios where the sampling probability of the optimal action might otherwise vanish. Furthermore, we established a fundamental connection between log-barrier regularization and Natural Policy Gradient, showing that LB-SGB exploits the Fisher information without exhibiting “over-committal” behaviors. While matching state-of-the-art sample complexity in the gradient bandit setting under assumptions on the optimization landscape, the method exhibits larger sample complexity in worst-case scenarios. Furthermore, LB-SGB lacks anytime regret guarantees, as the hyperparameters are chosen based on the knowledge of the time horizon T. These limitations suggest several directions for future research, such as improving the algorithm with adaptive hyperparameters, potentially leading to lower rates and anytime regret. Furthermore, this work should be seen as a theoretical foundation for PG methods in RL with improved exploration capabilities. Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. References A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan (2021) On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: Appendix A, §B.2, §1. S. Agrawal and N. Goyal (2012) Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, p. 39–1. Cited by: §1. A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün, and S. Hooker (2024) Back to basics: revisiting reinforce-style optimization for learning from human feedback in llms. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, p. 12248–12267. Cited by: §1. Z. Ahmed, N. Le Roux, M. Norouzi, and D. Schuurmans (2019) Understanding the impact of entropy on policy optimization. In International conference on machine learning, p. 151–160. Cited by: §1. S. Amari (1998) Natural gradient works efficiently in learning. Neural computation 10 (2), p. 251–276. Cited by: §6. P. Auer, N. Cesa-Bianchi, and P. Fischer (2002) Finite-time analysis of the multiarmed bandit problem. Machine learning 47 (2), p. 235–256. Cited by: §1. D. Baudry, E. Johnson, S. Vary, C. Pike-Burke, and P. Rebeschini (2025) Does stochastic gradient really succeed for bandits?. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: Appendix A, Appendix A, §C.2, §1, §3, §3, §3, footnote 1. J. Baxter and P. L. Bartlett (2001) Infinite-horizon policy-gradient estimation. journal of artificial intelligence research 15, p. 319–350. Cited by: §1. A. Bolland, G. Lambrechts, and D. Ernst (2025) Behind the myth of exploration in policy gradients. External Links: 2402.00162, Link Cited by: §1. S. Boyd and L. Vandenberghe (2004) Convex optimization. Cambridge university press. Cited by: §4. S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi (2022) Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research 70 (4), p. 2563–2578. Cited by: Table 2, Appendix A. W. Chung, V. Thomas, M. C. Machado, and N. Le Roux (2021) Beyond variance reduction: understanding the true impact of baselines on policy optimization. In International conference on machine learning, p. 1999–2009. Cited by: §B.3, §6, §6. Y. Ding, J. Zhang, and J. Lavaei (2022) On the global optimum convergence of momentum-based policy gradient. In International Conference on Artificial Intelligence and Statistics, p. 1910–1934. Cited by: Table 2, Appendix A, §5.3, Table 1, §6, §6, §6, §6. Y. Ding, J. Zhang, H. Lee, and J. Lavaei (2025) Beyond exact gradients: convergence of stochastic soft-max policy gradient methods with entropy regularization. IEEE Transactions on Automatic Control. Cited by: Table 2, Appendix A. L. Fan and P. W. Glynn (2025) The fragility of optimized bandit algorithms. Operations Research 73 (6), p. 3173–3198. Cited by: §3. I. Fatkhullin, A. Barakat, A. Kireeva, and N. He (2023) Stochastic policy gradient methods: improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning, p. 9827–9869. Cited by: §6. T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, et al. (2018) Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905. Cited by: §1, §1. S. M. Kakade (2001) A natural policy gradient. Advances in neural information processing systems 14. Cited by: Appendix A, §B.3, 4th item, §6. T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §1. T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra (2015) Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971. Cited by: §1. Y. Liu, K. Zhang, T. Basar, and W. Yin (2020) An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems 33, p. 7624–7636. Cited by: §6. J. Mei, W. Chung, V. Thomas, B. Dai, C. Szepesvari, and D. Schuurmans (2022) The role of baselines in policy gradient optimization. Advances in Neural Information Processing Systems 35, p. 17818–17830. Cited by: Appendix A, 4th item, §6. J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj, C. Szepesvári, and D. Schuurmans (2024) Small steps no more: global convergence of stochastic gradient bandits for arbitrary learning rates. Advances in Neural Information Processing Systems 37, p. 74487–74527. Cited by: Appendix A. J. Mei, B. Dai, C. Xiao, C. Szepesvári, and D. Schuurmans (2021a) Understanding the effect of stochasticity in policy optimization. In NeurIPS, p. 19339–19351. Cited by: §1. J. Mei, Y. Gao, B. Dai, C. Szepesvari, and D. Schuurmans (2021b) Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, p. 7555–7564. Cited by: §B.4, §C.1, §C.2, §4. J. Mei, C. Xiao, B. Dai, L. Li, C. Szepesvári, and D. Schuurmans (2020a) Escaping the gravitational pull of softmax. Advances in Neural Information Processing Systems 33, p. 21130–21140. Cited by: Appendix A. J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans (2020b) On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, p. 6820–6829. Cited by: Appendix A, Appendix A, §B.2, §1, §1, §4, §4. J. Mei, Z. Zhong, B. Dai, A. Agarwal, C. Szepesvari, and D. Schuurmans (2023) Stochastic gradient succeeds for bandits. In International Conference on Machine Learning, p. 24325–24360. Cited by: Table 2, Table 2, Table 2, Appendix A, Appendix A, §B.1, §C.1, §1, §2, §3, §3, §3, §5.1, §5.1, §5.1, §5.3, Table 1, §5, §5, footnote 1. A. M. Metelli, G. Manneschi, and M. Restelli (2022) Policy space identification in configurable environments. Machine Learning 111 (6), p. 2093–2145. Cited by: §6. A. Montenegro, M. Mussi, A. M. Metelli, and M. Papini (2024) Learning optimal deterministic policies with stochastic policy gradients. In Proceedings of the International Conference on Machine Learning (ICML), Cited by: §C.4, §5.1. B. O’Donoghue, I. Osband, and C. Ionescu (2020) Making sense of reinforcement learning and probabilistic inference. arXiv preprint arXiv:2001.00805. Cited by: §1. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe (2022) Training language models to follow instructions with human feedback. In NeurIPS, Cited by: §1. H. Robbins and S. Monro (1951) A stochastic approximation method. The annals of mathematical statistics, p. 400–407. Cited by: Appendix A. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §1. Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, M. Zhang, Y. K. Li, Y. Wu, and D. Guo (2024) DeepSeekMath: pushing the limits of mathematical reasoning in open language models. CoRR abs/2402.03300. External Links: Link, Document, 2402.03300 Cited by: §1. R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour (1999) Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12. Cited by: §1. R. S. Sutton and A. G. Barto (2018) Reinforcement learning: an introduction. A Bradford Book, Cambridge, MA, USA. External Links: ISBN 0262039249 Cited by: §1, §1, §2. R. J. Williams (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8 (3), p. 229–256. Cited by: §1. R. Yuan, R. M. Gower, and A. Lazaric (2022) A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, p. 3332–3380. Cited by: Table 2, Appendix A, §1. J. Zhang, J. Kim, B. O’Donoghue, and S. Boyd (2021) Sample efficient reinforcement learning with reinforce. In Proceedings of the AAAI conference on artificial intelligence, p. 10887–10895. Cited by: Table 2, Appendix A, §5.3, Table 1. K. Zhang, A. Koppel, H. Zhu, and T. Basar (2020) Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization 58 (6), p. 3586–3612. Cited by: Appendix A. Appendix A Detailed Related Works Table 2: Comparison of convergence rates and learning rates for different PG algorithms. We note that, under the same assumptions, our algorithm matches the optimal sample complexity of (ϵ−1)O (ε^-1 ) of Mei et al. (2023), achieving a lower rate without any additional assumptions. † We define c∗≔supt[πt(a∗)−2]c^* _tE [ _ θ_t(a^*)^-2 ]. Reference Sample Complexity Learning Rate α Method Assumptions Mei et al. (2023) (ϵ−1)O (ε^-1 ) (1)O (1 ) Vanilla PG (SGB) No ties, c∗<∞†c^*<∞ Yuan et al. (2022) ~(ϵ−3) O (ε^-3 ) (1/t)O (1/t ) Vanilla PG ABC, Weak gradient domination Ding et al. (2025) (ϵ−2)O (ε^-2 ) (1/t)O (1/t ) Entropy regularization inftminaπ(a)>0 _t _a _ θ(a)>0 Cen et al. (2022) (ϵ−2)O (ε^-2 ) (1/logt)O (1/ t ) Entropy regularized NPG Generative model Zhang et al. (2021) (ϵ−6)O (ε^-6 ) (1/logt)O (1/ t ) Log-barrier, Clipping Ding et al. (2022) (ϵ−4.5)O (ε^-4.5 ) (1/t)O (1/ t ) Log-barrier, Momentum This work ~(ϵ−) O (ε^-1 ) () O (1 ) Log-barrier No ties, c∗<∞ c^*<∞ This work (ϵ−) O (ε^-7 ) (ϵ−) O (ε^-3 ) Log-barrier No ties In this section, we review the most relevant literature, focusing on sample-complexity and regret results for MABs and Markov Decision Processes (MDPs). In Table 2, we compare some of the works discussed in this section. Sample Complexity of SGB. The core analytical difficulty of SGB lies in the geometry of the softmax policy, which, while satisfying smoothness assumptions, only satisfies a weak version of the Łojasiewicz inequality (Mei et al., 2020b). Furthermore, while it is standard practice to establish convergence to a stationary point under the assumption of bounded estimator variance and employing a decaying learning rate (Robbins and Monro, 1951; Zhang et al., 2020), converging to a stationary point is a weak requirement in the context of bandits. Since the gradient of the objective vanishes for any deterministic policy, the set of stationary points includes all vertices of the policy simplex, including all suboptimal deterministic policies (Mei et al., 2023). This property implies that the gradient signal is not globally well-behaved and, as the sampling probability of the optimal arm approaches zero, the gradient signal vanishes, converging to a suboptimal policy (Mei et al., 2020a). Despite these difficulties, convergence to a global optimum is guaranteed (Mei et al., 2023), even with no requirements on the learning rate α (Mei et al., 2024), establishing that SGB needs (ϵ−1)O (ε^-1 ) iterations to learn an ϵε-optimal policy. However, as noted by Baudry et al. (2025), this sample complexity guarantee may become vacuous due to a hidden assumption, as the constant governing the (ϵ−1)O (ε^-1 ) term depends on the inverse second moment of the probability assigned to the optimal arm. Furthermore, Mei et al. (2022) showed that Natural PG (NPG, Kakade (2001)) with an appropriate baseline also achieves (ϵ−1)O (ε^-1 ) sample complexity. Regret of SGB. Unlike the theoretical analysis of traditional bandit algorithms, which exploit arm-specific statistics, SGB is usually analysed via trajectories determined by the global history of the reward received by the algorithm, and providing regret guarantees requires significant effort. Recently, Mei et al. (2023) showed that with a constant learning rate α, the SGB algorithm can achieve (logT)O ( T ) regret. The robustness of this result has been questioned by Baudry et al. (2025), who point out the existence of low-probability events that may make the regret linear under the current analysis. Consequently, Baudry et al. (2025) provided an alternative proof of logarithmic regret in the 22-armed case, conjecturing an extension to the K-armed setting. Sample Complexity of PG in MDPs.333Here, we distinguish between iteration complexity, defined as the number of policy updates required to reach an ϵε-optimal policy, and sample complexity, which counts the total number of environment interactions. In the MAB setting, where each iteration involves exactly one sample to compute the stochastic gradient, these two measures are equivalent. MDPs introduce additional complexities since it is necessary to consider the effect of the policy π _ θ on the state distribution. While global convergence results for PG with exact gradient information in a tabular setting have been proved (Mei et al., 2020b; Agarwal et al., 2021), applying these techniques in stochastic environments requires addressing the variance of trajectory-based estimators. Recent literature in the stochastic setting has shown that PG methods can achieve ~(ϵ−2) O (ε^-2 ) sample complexity via entropy regularization and decaying learning rates (Ding et al., 2025). Similarly, entropy-regularized NPG achieves ~(ϵ−2) O (ε^-2 ) sample complexity, provided the regularization parameter is appropriately tuned (Cen et al., 2022). Without regularization, but under additional assumptions, it has been shown that PG achieves ~(ϵ−4) O (ε^-4 ) with decaying learning rates (Yuan et al., 2022). Finally, Zhang et al. (2021) proved ~(ϵ−6) O (ε^-6 ) sample complexity and (T5/6)O (T^5/6 ) regret for the REINFORCE algorithm with log-barrier regularization, and Ding et al. (2022) demonstrated ~(ϵ−9/2) O (ε^-9/2 ) sample complexity for momentum-based PG and log-barrier regularization. Table 2 summarizes the related works, providing a comparison in terms of sample complexity and required assumptions. Appendix B Algorithmic Details B.1 Stochastic Gradient Bandit In this section we report the SGB algorithm as it is reported in (Mei et al., 2023). In particular, we show the pseudo-code (Algorithm 1) in its basic version without baseline. Algorithm 1 Stochastic Gradient Bandit (SGB) 1: Input: Iterations T; step size α>0α>0; action set ⟦K⟧ K 2: Initialize: Parameters (a)←0 θ(a)← 0 for all a∈⟦K⟧a∈ K , t←1t← 1 3: for t∈⟦T⟧t∈ T do 4: Compute policy πt(a)←et(a)∑b∈⟦K⟧et(b) _t(a)← e θ_t(a) _b∈ K e θ_t(b) for all a∈⟦K⟧a∈ K 5: Select action at∼πta_t _t 6: Observe reward Rt(at)R_t(a_t) 7: for a∈⟦K⟧a∈ K do 8: if a=ata=a_t then 9: (a)←(a)+α⋅(1−πt(a))Rt(at) θ(a)← θ(a)+α·(1- _t(a))R_t(a_t) 10: else 11: (a)←(a)−α⋅πt(a)Rt(at) θ(a)← θ(a)-α· _t(a)R_t(a_t) 12: end if 13: end for 14: end for B.2 Stochastic Gradient Bandit with Entropy Regularization In this section we present the SGB algorithm with entropy regularization (Mei et al., 2020b; Agarwal et al., 2021). The algorithm augments the instantaneous reward Rt(at)R_t(a_t) with the entropy regularization term −τlogπt(at)-τ _ θ_t(a_t), where τ is an hyper-parameter, which acts as an intrinsic exploration bonus. Algorithm 2 shows the pseudocode for SGB with entropy regularization. Algorithm 2 SGB with Entropy Regularization 1: Input: Iterations T; step size α>0α>0; temperature τ≥0τ≥ 0; action set ⟦K⟧ K 2: Initialize: Parameters (a)←0 θ(a)← 0 for all a∈⟦K⟧a∈ K , t←1t← 1 3: for t∈⟦T⟧t∈ T do 4: Compute policy πt(a)←at _t(a) _a_t for all a∈⟦K⟧a∈ K 5: Select action at∼πta_t _t 6: Observe reward Rt(at)R_t(a_t) 7: Compute regularized reward r^t←Rt(at)−τlogπt(at) r_t← R_t(a_t)-τ _ θ_t(a_t) 8: for a∈⟦K⟧a∈ K do 9: if a=ata=a_t then 10: (a)←(a)+α⋅(1−πt(a))r^t θ(a)← θ(a)+α·(1- _t(a)) r_t 11: else 12: (a)←(a)−α⋅πt(a)r^t θ(a)← θ(a)-α· _t(a) r_t 13: end if 14: end for 15: end for B.3 Natural Stochastic Gradient Bandit In this section, we present the NPG algorithm for SGB, following the derivation of (Chung et al., 2021). The NPG (Kakade, 2001) updates the policy parameters θ along the steepest direction by precoditionig the standard gradient with the inverse Fisher Information Matrix, F()−1()F( θ)^-1J( θ), where F()F( θ) serves as a metric tensor which accounts for the curvature of the policy space. In SGB, the fisher is defined as: F()=a∼π[∇logπ(a)∇logπ(a)⊤]=diag(π)−ππ⊤, F( θ)=E_a _ θ [ _ θ _ θ(a) _ θ _ θ(a) ]=diag( _ θ)- _ θ _ θ , which is singular, hence not invertible. Hence, we cannot directly compute the update direction inverting the FIM, but we can solve the linear system, F()⋅x=atπ F( θ)· x=e_a_t _ θ obtaining: x=1π(at)at+β, x= 1 _ θ(a_t)e_a_t+β 1, where ate_a_t is an indicator vector defined as the ata_t-th standard basis vector, and 1 is the ones vector, t e_t is a standard basis vector, and β∈ℝβ is a scalar parameter representing the null space of F()F( θ). Since the softmax parametrization is shift-invariant, the choice of β does not affect the resulting policy, hence we can select β=0β=0 without loss of generality. Substituting the natural gradient direction x into the stochastic gradient ascent update, we obtain: t+1←t+αRt(at)(1πt(at)at). θ_t+1← θ_t+α R_t(a_t) ( 1 _ θ_t(a_t)e_a_t ). Algorithm 3 shows the pseudo-code for Natural SGB. Unlike the standard SGB update, which updates all arms at every step, increasing the probability of the selected arm and decreasing the others, the NPG update is sparse, updating only the selected arm. Algorithm 3 Natural Policy Gradient Bandit (NPG) 1: Input: Iterations T; step size α>0α>0; action set ⟦K⟧ K 2: Initialize: Parameters (a)←0 θ(a)← 0 for all a∈⟦K⟧a∈ K , t←1t← 1 3: for t∈⟦T⟧t∈ T do 4: Compute policy πt(a)←et(a)∑b∈⟦K⟧et(b) _t(a)← e θ_t(a) _b∈ K e θ_t(b) for all a∈⟦K⟧a∈ K 5: Select action at∼πta_t _t 6: Observe reward Rt(at)R_t(a_t) 7: (at)←(at)+α⋅Rt(at)πt(at) θ(a_t)← θ(a_t)+α· R_t(a_t) _t(a_t) 8: end for B.3.1 FIM as Covariance Matrix In the following proposition, we show that we can interpret the FIM as a covariance matrix of action features. See 6.1 Proof. First, observe that the expected value of the feature vectors ae_a is the policy vector itself: a∼π[a]=∑a∈π(a)a=π. _a _ θ[e_a]= _a _ θ(a)e_a= _ θ. For the softmax parametrization, the score function is given by the centered feature vector: ∇logπ(a)=a−π. _ θ _ θ(a)=e_a- _ θ. Substituting this into the definition of the Fisher Information Matrix, we obtain: F() F( θ) =a∼π[∇logπ(a)∇logπ(a)⊤] =E_a _ θ [ _ θ _ θ(a) _ θ _ θ(a) ] =a∼π[(a−π)(a−π)⊤] =E_a _ θ [(e_a- _ θ)(e_a- _ θ) ] =a∼π[(a−[a])(a−[a])⊤]. =E_a _ θ [(e_a-E[e_a])(e_a-E[e_a]) ]. This coincides with the definition of the covariance matrix Covπ(a)Cov_ _ θ(e_a). ∎ B.3.2 Log-Determinant of the FIM To explicitly connect the spectral constraint to the log-barrier formulation, we compute the determinant of the Fisher Information Matrix in the reparametrized space. Using the softmax policy with the parameter ¯∈ℝK−1 θ ^K-1, hence, π¯(a)=eθ¯(a)1+∑beθ¯(b)if a≠aK1−∑i=1K−1π¯(ai)otherwise, _ θ(a)= cases e θ(a)1+ _be θ(b)&if a≠ a_K\\ 1- _i=1^K-1 _ θ(a_i)&otherwise cases, (4) the FIM is a (K−1)×(K−1)(K-1)×(K-1) matrix given by F(¯)=diag(π¯)−π¯π¯⊤F( θ)=diag( _ θ)- _ θ _ θ . We compute the determinant using the Matrix Determinant Lemma, which states that for a diagonal matrix D and vector v, det(−⊤)=det()(1−⊤−1) (D-vv )= (D)(1-v D^-1v). Setting =diag(π¯)D=diag( _ θ) and =π¯v= _ θ, we obtain: det(F(¯)) (F( θ)) =det(diag(π¯))(1−π¯⊤diag(π¯)−1π¯) = (diag( _ θ)) (1- _ θ diag( _ θ)^-1 _ θ ) =(∏i=1K−1πi)(1−∑i=1K−1πiπiπi) = ( _i=1^K-1 _i ) (1- _i=1^K-1 _i _i _i ) =(∏i=1K−1πi)(1−∑i=1K−1πi). = ( _i=1^K-1 _i ) (1- _i=1^K-1 _i ). Then, the term in the second parenthesis simplifies exactly to the probability of the last arm, 1−∑i=1K−1πi=πK1- _i=1^K-1 _i= _K since ∑i=1Kπi=1 _i=1^K _i=1. Consequently, the determinant becomes the product of the probabilities of all arms: det(F(¯))=(∏i=1K−1πi)⋅πK=∏i=1Kπi. (F( θ))= ( _i=1^K-1 _i )· _K= _i=1^K _i. Finally, substituting this result into the log-determinant term yields: logdet(F(¯))=∑i=1K−1logπ¯(ai)+log(1−∑i=1K−1π¯(ai)). (F( θ))= _i=1^K-1 _ θ(a_i)+ (1- _i=1^K-1 _ θ(a_i) ). If we rewrite this regularization term with the softmax parametrization in Equation (1), we obtain exactly the objective function in Equation (3). This derivation confirms that constraining the log-determinant of the FIM is mathematically equivalent to the sum-log-barrier regularization employed in LB-SGB. B.4 Log-barrier Stochastic Gradient Bandit In this section, we present the details of the LB-SGB algorithm, whose pseudocode is shown in Algorithm 4. Algorithm 4 Log-barrier Stochastic Gradient Bandit (LB-SGB) 1: Input: Iterations T; step size α>0α>0; barrier parameter η>0η>0; action set ⟦K⟧ K 2: Initialize: Parameters (a)←0 θ(a)← 0 for all a∈⟦K⟧a∈ K , t←1t← 1 3: for t∈⟦T⟧t∈ T do 4: Compute policy πt(a)←et(a)∑b∈⟦K⟧et(b) _t(a)← e θ_t(a) _b∈ K e θ_t(b) for all a∈⟦K⟧a∈ K 5: Select action at∼πta_t _t 6: Observe reward Rt(at)R_t(a_t) 7: for a∈⟦K⟧a∈ K do 8: if a=ata=a_t then 9: (a)←(a)+α⋅((1−πt(a))Rt(at)+1η(1−K⋅πt(a))) θ(a)← θ(a)+α· ((1- _t(a))R_t(a_t)+ 1η(1-K· _t(a)) ) 10: else 11: (a)←(a)−α⋅(πt(a)Rt(at)+1η(1−K⋅πt(a))) θ(a)← θ(a)-α· ( _t(a)R_t(a_t)+ 1η(1-K· _t(a)) ) 12: end if 13: end for 14: end for In the following, we derive the gradient and Hessian of the LB-SGB objective. We recall the regularized performance index defined in Equation (3): Φη()≔()+1η∑a∈⟦K⟧lnπ(a). _η( θ) ( θ)+ 1η _a∈ K _ θ(a). (5) To compute the gradient of the barrier term, we first need to compute the following quantities: ∇logπ(ai) _ θ _ θ(a_i) =∇logeθi∑j=1Keθj=i−π = _ θ e _i _j=1^Ke _j=e_i- _ θ ∇(∑i=1Klogπ(ai)) _ θ ( _i=1^K _ θ(a_i) ) =∑i=1K(i−π)=−Kπ, = _i=1^K (e_i- _ θ )=1-K _ θ, where ie_i is the vector with all zeros and a one in the i-th position, and 1 is the K-dimensional ones vector. Then, the gradient of the barrier function is: ∇Φη()=(diag(π)−ππ⊤)+1η(−Kπ)=A()+1ηB(). _ θ _η( θ)=(diag( _ θ)- _ θ _ θ ) r+ 1η (1-K _ θ )=A( θ)+ 1ηB( θ). Let’s now consider the Hessian of the barrier function: H()=∂(A()+1ηB()), H( θ)= ∂ θ (A( θ)+ 1ηB( θ) ), where we consider the two terms separately. For the first term, we follow the proof of Lemma 2 in (Mei et al., 2021b), obtaining: [∂A()]i,j=δijπi(ri−π⊤r)−πiπj(ri−π⊤r)−πiπj(rj−π⊤r), [ ∂ θA( θ) ]_i,j= _ij _i(r_i- _ θ r)- _i _j(r_i- _ θ r)- _i _j(r_j- _ θ r), (6) where δij=1,ifi=j0,otherwise _ij= cases&1, ~i=j\\ &0, cases is the Kronecker’s delta. The second term, representing the Jacobian of the restorative force B()B( θ), can be written as: [∂B()]i,j=∂θj(1−Kπi)=−K(δijπi−πiπj). [ ∂ θB( θ) ]_i,j= ∂ _j (1-K _i )=-K( _ij _i- _i _j). (7) Finally, the ijij-th entry of the Hessian of the regularized objective is: [H()]i,j=δijπi(ri−π⊤r)−πiπj(ri+rj−2π⊤r)−Kη(δijπi−πiπj). [H( θ) ]_i,j= _ij _i(r_i- _ θ r)- _i _j(r_i+r_j-2 _ θ r)- Kη ( _ij _i- _i _j ). (8) Appendix C Proofs In this appendix, the proofs for the Lemmas and Theorems presented in Sections 4 and 5 are provided. C.1 Proofs for Section 4 Here, we provide the proofs for the properties of the LB-SGB algorithm provided in Section 4. Lemma 4.1 describe the boundedness of the spectral radius of the barrier’s Hessian, and Lemma C.2 generalizes the notion of non-uniform smoothness of the barrier between consecutive learning iterates. Lemma C.1 provides an upper-bound for the sample gradient norm. Finally, Lemma 4.2 provides the notion of non-uniform Łojasiewicz for our objective Φη() _η( θ). See 4.1 Proof. Let H()H( θ) be the Hessian matrix of the barrier function Φη() _η( θ), where each entry of this matrix is described by line (8). To show that Φη() _η( θ) is non-uniformly smooth, we need to show that the spectral radius of H()H( θ) is upper bounded. For this purpose, pick y∈ℝKy ^K. Then |y⊤H()y| |y H( θ)y | =∑i=1K∑j=1Kyi[H()]i,jyj = _i=1^K _j=1^Ky_i [H( θ) ]_i,jy_j =∑i=1K∑j=1Kyi([A()]i,j+1η[B()]i,j)yj = _i=1^K _j=1^Ky_i ( [A( θ) ]_i,j+ 1η [B( θ) ]_i,j )y_j Where the terms A()A( θ) and B()B( θ) are defined as: A()≔δijπi(ri−π⊤)−πiπj(ri+rj−2π⊤),B()=−Kη(δijπi−πiπj), A( θ) _ij _i(r_i- _ θ r)- _i _j(r_i+r_j-2 _ θ r), B( θ)=- Kη ( _ij _i- _i _j ), See Appendix B for a detailed derivation of the Hessian of the barrier function Φη() _η( θ). Now, analyzing the two terms separately: ∑i=1K∑j=1Kyi[A()]i,jyj=(F()⊤)(y⊙y)−2(F()⊤)y(π⊤y), _i=1^K _j=1^Ky_i [A( θ) ]_i,jy_j= (F( θ) r )(y y)-2 (F( θ) r )y( _ θ y), from the proof of Lemma 2 in (Mei et al., 2021b). Considering the second term: ∑i=1K∑j=1Kyi[B()]i,jyj _i=1^K _j=1^Ky_i [B( θ) ]_i,jy_j =∑i=1K∑j=1Kyi[−K(δijπi−πiπj)]i,jyj = _i=1^K _j=1^Ky_i [-K( _ij _i- _i _j) ]_i,jy_j =−Ky⊤F()y =-Ky F( θ)y =−Ky⊤(diag(π)−ππ⊤)y =-Ky (diag( _ θ)- _ θ _ θ )y =−K(y⊤diag(π)y−y⊤ππ⊤y) =-K (y diag( _ θ)y-y _ θ _ θ y ) =−K(π⊤(y⊙y)−π⊤yπ⊤y) =-K ( _ θ (y y)- _ θ y _ θ y ) Putting all together: |y⊤H()y| |y H( θ)y | =|(F()⊤)(y⊙y)−2(F()⊤)y(π⊤y)−Kη(π⊤(y⊙y)−π⊤y(π⊤y))| = | (F( θ) r )(y y)-2 (F( θ) r )y( _ θ y)- Kη ( _ θ (y y)- _ θ y( _ θ y) ) | =|((F()⊤)−Kηπ⊤)(y⊙y)−(2(F()⊤)+Kηπ⊤)y(π⊤y)| = | ( (F( θ) r )- Kη _ θ )(y y)- (2 (F( θ) r )+ Kη _ θ )y( _ θ y) | =|((F()⊤)+1η(−Kπ⊤)−1η)(y⊙y) = | ( (F( θ) r )+ 1η ( 1-K _ θ )- 1η 1 )(y y) −(2(F()⊤)+2η(−Kπ⊤)−1η+3Kηπ⊤)y(π⊤y)| - (2 (F( θ) r )+ 2η ( 1-K _ θ )- 1η 1+ 3Kη _ θ )y( _ θ y) | ≤‖(F()⊤)+1η(−Kπ⊤)‖∞‖y⊙y‖+1η‖∞‖y⊙y‖1 ≤ \| (F( θ) r )+ 1η ( 1-K _ θ ) \|_∞ \|y y \|+ 1η\| 1\|_∞\|y y\|_1 +2‖(F()⊤)+1η(−Kπ⊤)‖‖y‖2‖π‖1‖y‖∞ +2 \| (F( θ) r )+ 1η ( 1-K _ θ ) \|\|y\|_2\| _ θ\|_1\|y\|_∞ +1η(2‖2+3K‖π‖2)‖y‖2‖π‖1‖y‖∞ + 1η (2\| 1\|_2+3K\| _ θ\|_2 )\|y\|_2\| _ θ\|_1\|y\|_∞ ≤3‖(F()⊤)+1η(−Kπ⊤)‖2‖y‖22+1η(1+2‖2+3K‖π‖2)‖y‖22 ≤ 3 \| (F( θ) r )+ 1η ( 1-K _ θ ) \|_2\|y\|_2^2+ 1η (1+2\| 1\|_2+3K\| _ θ\|_2 )\|y\|_2^2 ≤3‖(F()⊤)+1η(−Kπ⊤)‖2‖y‖22+3K+2K+1η‖y‖22 ≤ 3 \| (F( θ) r )+ 1η ( 1-K _ θ ) \|_2\|y\|_2^2+ 3K+2 K+1η\|y\|_2^2 ≤3‖(F()⊤)+1η(−Kπ⊤)‖2‖y‖22+5Kη‖y‖22 ≤ 3 \| (F( θ) r )+ 1η ( 1-K _ θ ) \|_2\|y\|_2^2+ 5Kη\|y\|_2^2 ≤3(‖∇Φη()‖2+5Kη)‖y‖22, ≤ 3 (\| _ θ _η( θ)\|_2+ 5Kη )\|y\|_2^2, where 1 is the K-dimensional ones vector and the Cauchy-Schwarz theorem ad Holder’s inequalities have been employed. ∎ Lemma C.1 (Upper Bound on the Sample Gradient Norm). Given ∈[−Rmax,Rmax] r∈[-R_ ,R_ ], K>1K>1, and η>0η>0, the sample gradient of the barrier function is upper bounded by ‖∇^Φη(t)‖2≤2Rmax(1−πt(at))+2ηK \| ∇_ θ _η( θ_t)\|_2≤ 2R_ (1- _ θ_t(a_t))+ 2ηK (9) Proof. We have, ‖∇^Φη(t)‖2 \| ∇_ θ _η( θ_t)\|_2 ≤‖∇(πt⊤^)‖2+1η‖−Kπt⊤‖2 ≤\| _ θ( _ θ_t r)\|_2+ 1η \| 1-K _ θ_t \|_2 (10) ≤2Rmax(1−πt(at))+1η(‖+K‖πt‖) ≤ 2R_ (1- _ θ_t(a_t))+ 1η (\| 1\|+K\| _ θ_t\| ) (11) ≤2Rmax(1−πt(at))+1η(K+K) ≤ 2R_ (1- _ θ_t(a_t))+ 1η ( K+K ) ≤2Rmax(1−πt(at))+2ηK ≤ 2R_ (1- _ θ_t(a_t))+ 2ηK (12) where, in line (10), the triangle inequality has been applied and the analytic gradient has been substituted, in line (11), a bound for the sampled gradient’s performance derived from line (54) of Proposition 3.1 of Mei et al. (2023) has been used. ∎ Since Lemma 4.1 alone is not sufficient to guarantee convergence, we need to prove that the LB-SGB algorithm is able to control the variation of the objective between consecutive iterates using the learning rate α. Lemma C.2 (Non-uniform Smoothness Between Iterates). Using the LB-SGB algorithm with learning rate α∈(0,16(2Rmax+2ηK)))α∈ (0, 16 ( 2R_ + 2ηK) ) ), we have, for all t≥1t≥ 1, |Φη(t+1)−Φη(t)−⟨∇Φη(t),t+1−t⟩| | _η( θ_t+1)- _η( θ_t)- _ θ _η( θ_t), θ_t+1- θ_t | ≤(3‖∇Φη(t)‖22−6α(2Rmax+2ηK)+15Kη)‖t+1−t‖22. ≤ ( 3\| _ θ _η( θ_t)\|_22-6α ( 2R_ + 2ηK )+ 15Kη )\| θ_t+1- θ_t\|_2^2. Proof. Denote ζ≔t+ζ(t+1−t) θ_ζ θ_t+ζ( θ_t+1- θ_t), with ζ∈[0,1]ζ∈[0,1]. According to Taylor’s theorem, we have, |Φη(t+1)−Φη(t)−⟨‖∇Φη(t)‖2,t+1−t⟩| | _η( θ_t+1)- _η( θ_t)- \| _ θ _η( θ_t)\|_2, θ_t+1- θ_t | =12|(t+1−t)⊤H(ζ)(t+1−t)| = 12 |( θ_t+1- θ_t) H( θ_ζ)( θ_t+1- θ_t) | ≤32(‖∇ζΦη(ζ)‖2+5Kη)‖t+1−t‖22, ≤ 32 (\| _ θ_ζ _η( θ_ζ)\|_2+ 5Kη )\| θ_t+1- θ_t\|_2^2, (13) where Lemma 4.1 has been applied in the last step. Now, we need to control the gradient at ζ θ_ζ with the gradient at t θ_t. Denote ζ1≔t+ζ1(ζ−t) θ_ _1 θ_t+ _1( θ_ζ- θ_t) with some ζ1∈[0,1] _1∈[0,1]. We have, ‖∇θζΦη(θζ)−∇Φη(t)‖2 \| _ _ζ _η( _ζ)- _ θ _η( θ_t)\|_2 =‖∫01⟨∇t2Φη(t),ζ−t⟩ζ‖2 = \| _0^1 ∇^2_ θ_t _η( θ_t), θ_ζ- θ_t dζ \|_2 (14) ≤∫01‖H(ζ1)‖2‖ζ−t‖2ζ ≤ _0^1\|H( θ_ _1)\|_2\| θ_ζ- θ_t\|_2dζ (15) ≤∫013(‖∇Φη()‖2+5Kη)‖ζ−t‖2ζ ≤ _0^13 (\| _ θ _η( θ)\|_2+ 5Kη )\| θ_ζ- θ_t\|_2dζ (16) =∫013(‖∇Φη()‖2+5Kη)ζ‖t+1−t‖2ζ = _0^13 (\| _ θ _η( θ)\|_2+ 5Kη )ζ\| θ_t+1- θ_t\|_2dζ (17) ≤∫013(‖∇Φη()‖2+5Kη)α‖∇^Φη(t)‖2ζ, ≤ _0^13 (\| _ θ _η( θ)\|_2+ 5Kη )α\| ∇_ θ _η( θ_t)\|_2dζ, (18) where in line (14) the fundamental theorem of calculus is invoked, line (15) applies Cauchy–Schwarz, line (16) applies Lemma 4.1, line (17) substitutes the definition of ζ θ_ζ, and finally, line (18) substitutes the update rule and uses ζ∈[0,1]ζ∈[0,1]. Therefore, we have: ‖∇ζΦη(ζ)‖2 \| _ θ_ζ _η( θ_ζ)\|_2 ≤‖∇Φη(t)‖2+‖∇θζΦη(θζ)−∇Φη(t)‖2 ≤\| _ θ _η( θ_t)\|_2+\| _ _ζ _η( _ζ)- _ θ _η( θ_t)\|_2 (19) ≤‖∇Φη(t)‖2+∫013(‖∇ζ1Φη(ζ1)‖2+5Kη)α‖∇^Φη(t)‖2ζ1 ≤\| _ θ _η( θ_t)\|_2+ _0^13 (\| _ θ_ _1 _η( θ_ _1)\|_2+ 5Kη )α\| ∇_ θ _η( θ_t)\|_2d _1 =‖∇Φη(t)‖2+3α5ηK‖∇^Φη(t)‖2+3α‖∇^Φη(t)‖2∫01‖∇ζ1Φη(ζ1)‖2ζ1, =\| _ θ _η( θ_t)\|_2+3α 5ηK\| ∇_ θ _η( θ_t)\|_2+3α\| ∇_ θ _η( θ_t)\|_2 _0^1\| _ θ_ _1 _η( θ_ _1)\|_2d _1, (20) where line (19) follows from the triangle inequality and line (20) is obtained applying line (18). Denote ζ2≔t+ζ2(ζ1−t) _2 θ_t+ _2( θ_ _1- θ_t), with ζ2∈[0,1] _2∈[0,1]. Using similar calculation in line (14), we have, ‖∇ζ1Φη(ζ1)‖2 \| _ θ_ _1 _η( θ_ _1)\|_2 ≤‖∇Φη(t)‖2+‖∇θζ1Φη(θζ1)−∇Φη(t)‖2 ≤\| _ θ _η( θ_t)\|_2+\| _ _ _1 _η( _ _1)- _ θ _η( θ_t)\|_2 ≤‖∇Φη(t)‖2+∫013(‖∇ζ2Φη(ζ2)‖2+5Kη)α‖∇^Φη(t)‖2ζ2 ≤\| _ θ _η( θ_t)\|_2+ _0^13 (\| _ θ_ _2 _η( θ_ _2)\|_2+ 5Kη )α\| ∇_ θ _η( θ_t)\|_2d _2 =‖∇Φη(t)‖2+3α5ηK‖∇^Φη(t)‖2+3α‖∇^Φη(t)‖2∫01‖∇ζ2Φη(ζ2)‖2ζ2,. =\| _ θ _η( θ_t)\|_2+3α 5ηK\| ∇_ θ _η( θ_t)\|_2+3α\| ∇_ θ _η( θ_t)\|_2 _0^1\| _ θ_ _2 _η( θ_ _2)\|_2d _2,. (21) Combining line (20) and line (21), we have, ‖∇ζΦη(ζ)‖2 \| _ θ_ζ _η( θ_ζ)\|_2 ≤(1+3α‖∇^Φη(t)‖2)(‖∇Φη(t)‖2+3α5ηK‖∇^Φη(t)‖2) ≤ (1+3α\| ∇_ θ _η( θ_t)\|_2 ) (\| _ θ _η( θ_t)\|_2+3α 5ηK\| ∇_ θ _η( θ_t)\|_2 ) +(3α‖∇^Φη(t)‖2)2∫01∫01‖∇ζ2Φη(ζ2)‖2ζ2ζ1, + (3α\| ∇_ θ _η( θ_t)\|_2 )^2 _0^1 _0^1\| _ θ_ _2 _η( θ_ _2)\|_2d _2d _1, which, by recursion, becomes, ‖∇ζΦη(ζ)‖2≤(‖∇Φη(t)‖2+3α5ηK‖∇^Φη(t)‖2)∑i=0∞(3α‖∇^Φη(t)‖2)i \| _ θ_ζ _η( θ_ζ)\|_2≤ (\| _ θ _η( θ_t)\|_2+3α 5ηK\| ∇_ θ _η( θ_t)\|_2 ) _i=0^∞ (3α\| ∇_ θ _η( θ_t)\|_2 )^i (22) Now, we need to make the infinite series to converge. To this purpose, we have to select the learning rate α and the barrier parameter η such that the argument of the series is less than 1. Hence, following Lemma C.1, we have to select α such that, 3α(2Rmax(1−πt(at))+2ηK))≤3α(2Rmax+2ηK))<1⇒α≤13(2Rmax+2ηK)) 3α ( 2R_ (1- _ θ_t(a_t))+ 2ηK) )≤ 3α ( 2R_ + 2ηK) )<1 α≤ 13 ( 2R_ + 2ηK) ) As η→∞η→∞, the learning rate α approaches its limit value. We can then select α to be an half its limit value, hence α≤16(2Rmax+2ηK))α≤ 16 ( 2R_ + 2ηK) ), making the series in line (22) to converge to 11−3α‖∇^Φη(t)‖2 11-3α\| ∇_ θ _η( θ_t)\|_2. Hence, we have, ‖∇ζΦη(ζ)‖2 \| _ θ_ζ _η( θ_ζ)\|_2 ≤11−3α‖∇^Φη(t)‖2(‖∇Φη(t)‖2+3α5ηK‖∇^Φη(t)‖2) ≤ 11-3α\| ∇_ θ _η( θ_t)\|_2 (\| _ θ _η( θ_t)\|_2+3α 5ηK\| ∇_ θ _η( θ_t)\|_2 ) ≤11−3α(2Rmax+2ηK))(∥∇Φη(t)∥2+3α5ηK(2Rmax+2ηK))) ≤ 11-3α ( 2R_ + 2ηK) ) (\| _ θ _η( θ_t)\|_2+3α 5ηK ( 2R_ + 2ηK) ) ) ≤11−3α(2Rmax+2ηK))‖∇Φη(t)‖2+5ηK3α(2Rmax+2ηK)1−3α(2Rmax+2ηK) ≤ 11-3α ( 2R_ + 2ηK) )\| _ θ _η( θ_t)\|_2+ 5ηK 3α ( 2R_ + 2ηK )1-3α ( 2R_ + 2ηK ) ≤11−3α(2Rmax+2ηK))‖∇Φη(t)‖2+5ηK, ≤ 11-3α ( 2R_ + 2ηK) )\| _ θ _η( θ_t)\|_2+ 5ηK, (23) where line (23) follows from the fact that 3α(2Rmax+2ηK)<123α ( 2R_ + 2ηK )< 12 due to the choice of α. Finally, combining line (13) with line (23), we have, |Φη(t+1)−Φη(t)−⟨∇Φη(t),t+1−t⟩| | _η( θ_t+1)- _η( θ_t)- _ θ _η( θ_t), θ_t+1- θ_t | ≤32(11−3α(2Rmax+2ηK))‖∇Φη(t)‖2+10Kη)‖t+1−t‖22 ≤ 32 ( 11-3α ( 2R_ + 2ηK) )\| _ θ _η( θ_t)\|_2+ 10Kη )\| θ_t+1- θ_t\|_2^2 =(32−6α(2Rmax+2ηK))‖∇Φη(t)‖2+15Kη)‖t+1−t‖22 = ( 32-6α ( 2R_ + 2ηK) )\| _ θ _η( θ_t)\|_2+ 15Kη )\| θ_t+1- θ_t\|_2^2 ∎ See 4.2 Proof. Using the definition of the Jacobian of the barrier function, we have, ‖∇Φη()‖2 \| _ θ _η( θ)\|_2 =‖(F()⊤)+1η(−Kπ⊤)‖2 = \|(F( θ) r)+ 1η ( 1-K _ θ ) \|_2 =(∑a∈⟦K⟧(π(a)(r(a)−π⊤)+1η(1−Kπ(a)))2)12 = ( _a∈ K ( _ θ(a)(r(a)- _ θ r)+ 1η(1-K _ θ(a)) )^2 ) 12 ≥(π(a∗)(r(a∗)−π⊤)−1η|1−Kπ(a∗)|)+ ≥ ( _ θ(a^*)(r(a^*)- _ θ r)- 1η |1-K _ θ(a^*) | )^+ ≥(π(a∗)(r(a∗)−π⊤)−1η(K−1))+. ≥ ( _ θ(a^*)(r(a^*)- _ θ r)- 1η(K-1) )^+. ∎ C.2 Proofs for Section 5.1 Here, we provide the proofs for the Lemmas and Theorems provided in Section 5.1. We start showing the self-bounding property of the barrier function in Lemma 5.1. Then, after analysing the difference of the log-barrier between iterates in Lemma C.3, we show why LB-SGB converges with constant learning rates in Lemma C.5. Finally, after providing an upper bound on the true gradient norm in Lemma C.6, we provide the convergence rate of our algorithm in Theorem 5.2. See 5.1 Proof. Considering the expectation of ‖∇^Φη(t)‖22\| ∇_ θ _η( θ_t)\|_2^2, we have, t[‖∇^Φη(t)‖22] _t [\| ∇_ θ _η( θ_t)\|_2^2 ] =t[‖∇(πt⊤^)+1η∇∑a∈⟦K⟧logπt(a)‖22] =E_t [ \| _ θ ( _ θ_t r)+ 1η _ θ _a∈ K _ θ_t(a) \|_2^2 ] =t[‖∇(πt⊤^)‖22]+t[‖1η∇∑a∈⟦K⟧logπt(a)‖22] =E_t [ \| _ θ ( _ θ_t r) \|_2^2 ]+E_t [ \| 1η _ θ _a∈ K _ θ_t(a) \|_2^2 ] +2t[‖∇(πt⊤^)‖2]t[‖1η∇∑a∈⟦K⟧logπt(a)‖2] +2E_t [ \| _ θ ( _ θ_t r) \|_2 ]E_t [ \| 1η _ θ _a∈ K _ θ_t(a) \|_2 ] (24) ≤2t[‖∇(πt⊤^)‖22]+2t[‖1η∇∑a∈⟦K⟧logπt(a)‖22] ≤ 2E_t [ \| _ θ ( _ θ_t r) \|_2^2 ]+2E_t [ \| 1η _ θ _a∈ K _ θ_t(a) \|_2^2 ] (25) ≤16Rmax3K3/2Δ2‖∇(πθt⊤)±1η∇∑a∈⟦K⟧logπt(a)‖2+8(1ηK)2 ≤ 16R_ ^3K^3/2 ^2\| _ θ( _ _t r)± 1η _ θ _a∈ K _ θ_t(a)\|_2+8 ( 1ηK )^2 (26) ≤16Rmax3K3/2Δ2‖∇Φη(t)‖2+2ηK(4ηK+16Rmax3K3/2Δ2), ≤ 16R_ ^3K^3/2 ^2\| _ θ _η( θ_t)\|_2+ 2ηK ( 4ηK+ 16R_ ^3K^3/2 ^2 ), where line (24) follows from Cauchy-Swartz, line (25) follows from the Young’s inequality, and line (26) is obtained applying Lemma 4.3 from (Mei et al., 2021b) and bounding the deterministic term similarly as Lemma C.1. ∎ Lemma C.3 (Difference Between Barriers Among Iterates). Given the learning rate α>0α>0 and K arms, considering the update ′←+α∇Φη() θ ← θ+α _ θ _η( θ), the difference between the barrier terms among two consecutive iterates is ∑a∈⟦K⟧(logπ′(a)−logπ(a))≤2αK‖∇^Φη()‖2≤2αK(2Rmax+2ηK) _a∈ K ( _ θ (a)- _ θ(a) )≤ 2α K\| ∇_ θ _η( θ)\|_2≤ 2α K ( 2R_ + 2ηK ) (27) Proof. ∑a∈⟦K⟧(logπ′(a)−logπ(a)) _a∈ K ( _ θ (a)- _ θ(a) ) =∑a∈⟦K⟧logπ′(a)π(a) = _a∈ K _ θ (a) _ θ(a) =∑a∈⟦K⟧logeθ′(a)∑beθ′(b)eθ(a)∑beθ(b) = _a∈ K e^θ (a) _be^θ (b) e^θ(a) _be^θ(b) =∑a∈⟦K⟧logeθ′(a)eθ(a)∑beθ(b)∑beθ′(b) = _a∈ K e^θ (a)e^θ(a) _be^θ(b) _be^θ (b) =∑a∈⟦K⟧(θ′(a)−θ(a))+Klog∑beθ(b)∑beθ′(b) = _a∈ K (θ (a)-θ(a))+K _be^θ(b) _be^θ (b) =α∑a∈⟦K⟧∂^∂θ(a)Φη(θ(a)) =α _a∈ K ∂θ(a) _η(θ(a)) +K(log(∑beθ(b))−log(∑beθ′(b))) +K ( ( _be^θ(b) )- ( _be^θ (b) ) ) ≤α⟨∇^Φη(),⟩+K⟨−′,π()⟩ ≤α ∇_ θ _η( θ), 1 +K θ- θ ,π( θ) (28) =α⟨∇^Φη(),⟩+K⟨α∇^0Φη(),π()⟩ =α ∇_ θ _η( θ), 1 +K α ∇_ θ_0 _η( θ),π( θ) ≤α‖∇^Φη()‖2‖2+αK‖∇^Φη()‖2‖π‖2 ≤α\| ∇_ θ _η( θ)\|_2\| 1\|_2+α K\| ∇_ θ _η( θ)\|_2\| _ θ\|_2 ≤αK‖∇^Φη()‖2+K‖∇^Φη()‖2 ≤α K\| ∇_ θ _η( θ)\|_2+K\| ∇_ θ _η( θ)\|_2 ≤2αK‖∇^Φη()‖2, ≤ 2α K\| ∇_ θ _η( θ)\|_2, where line (28) follows from the convexity of the LogSumExp, and π()π( θ) is the respective policy. Finally, applying Lemma C.1, ∑a∈⟦K⟧(logπ′(a)−logπ(a)) _a∈ K ( _ θ (a)- _ θ(a) ) ≤2αK‖∇^Φη()‖2 ≤ 2α K\| ∇_ θ _η( θ)\|_2 ≤2αK(2Rmax+2ηK) ≤ 2α K ( 2R_ + 2ηK ) ∎ In order to show the global convergence of the LB-SGB with constant learning rate, we need to provide a descent lemma leveraging the non-smoothness and self-bounding properties. Lemma C.4 (Descent Lemma). We have, for all t≥1t≥ 1, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 r] ≤(α2803Rmax3K3/2Δ2−α)‖∇Φη(t)‖22+β(t,1η) ≤ (α^2 803 R_ ^3K^3/2 ^2-α )\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ) (30) where the bias term β is defined as, β(t,1η)≤αηK(2‖∇Φη(t)‖2+4K) β ( θ_t, 1η )≤ αηK (2\| _ θ _η( θ_t)\|_2+4K ) Proof. According to Lemma C.2, we have, |Φη(t+1)−Φη(t)−⟨∇Φη(t),t+1−t⟩| | _η( θ_t+1)- _η( θ_t)- _ θ _η( θ_t), θ_t+1- θ_t | ≤(32−6α(2Rmax+2ηK)‖∇Φη(t)‖2+15ηK)‖t+1−t‖22 ≤ ( 32-6α ( 2R_ + 2ηK )\| _ θ _η( θ_t)\|_2+ 15ηK )\| θ_t+1- θ_t\|_2^2 ≤(53‖∇Φη(t)‖2+15ηK)‖t+1−t‖22, ≤ ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )\| θ_t+1- θ_t\|_2^2, (31) where line (31) follows from the bound on learning rate α in line (40). We have, Φη(t)−Φη(t+1)=(πt⊤)−(πt+1⊤)−1η∑a∈⟦K⟧(logπt+1(a)−logπt(a)), _η( θ_t)- _η( θ_t+1)=( _ θ_t r)-( _ θ_t+1 r)- 1η _a∈ K ( _ θ_t+1(a)- _ θ_t(a) ), (32) and, applying Lemma C.3 with b(t,1η)≔2αKη‖∇^Φη()‖2b ( θ_t, 1η ) 2α Kη\| ∇_ θ _η( θ)\|_2 and applying Lemma C.2 and line (31), we have, (πt⊤)−(πt+1⊤) ( _ θ_t r)-( _ θ_t+1 r) ≤−α⟨∇Φη(t),t+1−t⟩+(53‖∇Φη(t)‖2+15ηK)‖t+1−t‖22+b(t,1η) ≤-α ∇ _η( θ_t), θ_t+1- θ_t + ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )\| θ_t+1- θ_t\|_2^2+b ( θ_t, 1η ) ≤−α⟨∇Φη(t),∇^Φη(t)⟩ ≤-α ∇ _η( θ_t), ∇ _η( θ_t) +(53‖∇Φη(t)‖2+15ηK)α2‖∇^Φη(t)‖22+b(t,1η), + ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )α^2\| ∇_ θ _η( θ_t)\|_2^2+b ( θ_t, 1η ), (33) where in line (33) the update rule has been used. Taking the expectation, we have, (πt⊤)−t[(πt+1⊤)] ( _ θ_t r)-E_t [( _ θ_t+1 r) ] ≤−α⟨‖∇Φη(t)‖2,[∇^Φη(t)]⟩ ≤-α \| _ θ _η( θ_t)\|_2,E [ ∇ _η( θ_t) ] +(53‖∇Φη(t)‖2+15ηK)α2t[‖∇^Φη(t)‖22]+t[b(t,1η)] + ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )α^2E_t [\| ∇_ θ _η( θ_t)\|_2^2 ]+E_t [b ( θ_t, 1η ) ] =−α‖∇Φη(t)‖22 =-α\| _ θ _η( θ_t)\|_2^2 +(53‖∇Φη(t)‖2+15ηK)α2t[‖∇^Φη(t)‖22]+t[b(t,1η)], + ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )α^2E_t [\| ∇_ θ _η( θ_t)\|_2^2 ]+E_t [b ( θ_t, 1η ) ], (34) where line (34) follows from the unbiasedness of the gradient estimator of the barrier function. Let’s denote A=‖∇Φη(t)‖2A=\| _ θ _η( θ_t)\|_2, A^=‖∇^Φη(t)‖2 A=\| ∇_ θ _η( θ_t)\|_2, c=2ηKc= 2ηK, and d=2ηK(4ηK+16Rmax3K3/2Δ2)d= 2ηK ( 4ηK+ 16R_ ^3K^3/2 ^2 ). Now, we have, (πt⊤)−t[(πt+1⊤)] ( _ θ_t r)-E_t [( _ θ_t+1 r) ] ≤−α‖A‖22+(53‖A‖2+c)α2t[‖A^‖22]+t[b(t,1η)] ≤-α\|A\|_2^2+ ( 53\|A\|_2+c )α^2E_t[\| A\|_2^2]+E_t [b ( θ_t, 1η ) ] ≤−α‖A‖22+(53‖A‖2+c)α2(16Rmax3K3/2Δ2‖A‖2+d)+t[b(t,1η)] ≤-α\|A\|_2^2+ ( 53\|A\|_2+c )α^2 ( 16R_ ^3K^3/2 ^2\|A\|_2+d )+E_t [b ( θ_t, 1η ) ] (35) =−α‖A‖22+α2803Rmax3K3/2Δ2‖A‖22+α253‖A‖2⋅d+α216Rmax3K3/2Δ2⋅c⋅‖A‖2 =-α\|A\|_2^2+α^2 803 R_ ^3K^3/2 ^2\|A\|_2^2+α^2 53\|A\|_2· d+α^2 16R_ ^3K^3/2 ^2· c·\|A\|_2 +α2⋅c⋅d+t[b(t,1η)] +α^2· c· d+E_t [b ( θ_t, 1η ) ] =−α‖A‖22+α2803Rmax3K3/2Δ2‖A‖22+β(t,1η) =-α\|A\|_2^2+α^2 803 R_ ^3K^3/2 ^2\|A\|_2^2+β ( θ_t, 1η ) =(−α+α2803Rmax3K3/2Δ2)‖A‖22+β(t,1η), = (-α+α^2 803 R_ ^3K^3/2 ^2 )\|A\|_2^2+β ( θ_t, 1η ), (36) where line (35) follows from the application of Lemma 5.1 We now have to characterize the bias term β. Let’s analyse each component. The term α253‖A‖2⋅dα^2 53\|A\|_2· d is (η−2)O(η^-2) by definition of d, hence it can be upper-bounded by, α253‖A‖2⋅d≤αηK‖A‖2. α^2 53\|A\|_2· d≤ αηK\|A\|_2. The term α216Rmax3K3/2Δ2⋅cα^2 16R_ ^3K^3/2 ^2· c is (η−1)O(η^-1) and being α216Rmax3K3/2Δ2<1α^2 16R_ ^3K^3/2 ^2<1 we can upper-bound it as, α216Rmax3K3/2Δ2⋅c⋅‖A‖2≤αηK‖A‖2. α^2 16R_ ^3K^3/2 ^2· c·\|A\|_2≤ αηK\|A\|_2. The term α2⋅c⋅dα^2· c· d is (η−2)O(η^-2) and can be upper-bounded as, α2⋅c⋅d≤αη2K2, α^2· c· d≤ αη^2K^2, when α≤Δ216Rmax3K3/2α≤ ^216R_ ^3K^3/2 Finally, it is necessary to bound the term t[b(t,1η)]E_t [b ( θ_t, 1η ) ], t[b(t,1η)] _t [b ( θ_t, 1η ) ] ≤2αKη‖∇Φη(t)‖2 ≤ 2α Kη\| _ θ _η( θ_t)\|_2 (37) Finally, putting all the bias terms together, we obtain, β(t,1η)≤αηK(4‖∇Φη(t)‖2+Kη) β ( θ_t, 1η )≤ αηK (4\| _ θ _η( θ_t)\|_2+ Kη ) ∎ In the following lemma, we show that, with a proper choice of the learning rate α, we can prove that applying the LB-SGB update rule, we are progressing toward the optimal policy, up to a constant bias term, which is partly dependent on the true gradient norm of the objective function, controllable choosing the barrier parameter η. Furthermore, Lemma C.5 provides a mechanism to chose the learning rate α coherent with the requirement from Lemma C.2. Lemma C.5 (Constant Learning Rates). Selecting the learning rate α=Δ230K3/2Rmax2(2Rmax+2ηK)α= ^230K^3/2R_ ^2( 2R_ + 2ηK), we have, for all t≥1t≥ 1, πt⊤−t[πt+1⊤]≤−Δ232K3/2Rmax2(2Rmax+2ηK)‖∇Φη(t)‖22+β(t,1η), _t r-E_t[ _t+1 ]≤- ^232K^3/2R_ ^2 ( 2R_ + 2ηK )\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ), (38) where the bias term β is defined as, β(t,1η)≤αηK(2‖∇Φη(t)‖2+4K) β ( θ_t, 1η )≤ αηK (2\| _ θ _η( θ_t)\|_2+4K ) Proof. Using the learning rate, α α =Δ230K3/2Rmax2(2Rmax+2ηK) = ^230K^3/2R_ ^2 ( 2R_ + 2ηK ) =130(2Rmax+2ηK)⋅Δ2Rmax2⋅1K3/2 = 130 ( 2R_ + 2ηK )· ^2R_ ^2· 1K^3/2 ≤130(2Rmax+2ηK)⋅4⋅122 ≤ 130 ( 2R_ + 2ηK )· 4· 12 2 (39) ≤130(2Rmax+2ηK), ≤ 130 ( 2R_ + 2ηK ), (40) where line (39) follows from Δ≤2Rmax ≤ 2R_ and K>2K>2, we have that α∈(0,16(2Rmax+2ηK)))α∈ (0, 16 ( 2R_ + 2ηK) ) ). Now, plugging the selected learning rate α in the result of Lemma C.4, we have, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 ] ≤(α2803Rmax3K3/2Δ2−α)‖∇Φη(t)‖22+β(t,1η) ≤ (α^2 803 R_ ^3K^3/2 ^2-α )\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ) ≤−Δ232K3/2Rmax2(2Rmax+2ηK)‖∇Φη(t)‖22+β(t,1η) ≤- ^232K^3/2R_ ^2 ( 2R_ + 2ηK )\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ) ∎ Lemma C.6 (Upper Bound on Gradient Norm). The norm of the gradient function ‖∇Φη(t)‖2\| _ θ _η( θ_t)\|_2 is upper bounded by, ‖∇Φη(t)‖2≤r(a∗)−πt⊤+2ηK, \| _ θ _η( θ_t)\|_2≤ r(a^*)- _ θ_t r+ 2ηK, (41) where r(a∗)r(a^*) is the reward of the optimal arm. Proof. Let ∇B(t)=∇1η∑a∈⟦K⟧logπt(a) _ θB( θ_t)= _ θ 1η _a∈ K _ θ_t(a)e have, ‖∇Φη(t)‖2 \| _ θ _η( θ_t)\|_2 =‖∇(πt⊤)+∇B(t)‖2 = \| _ θ ( _ θ_t r )+ _ θB( θ_t) \|_2 ≤‖∇(πt⊤)‖2+‖∇B(t)‖2 ≤\| _ θ ( _ θ_t r )\|_2+\| _ θB( θ_t)\|_2 ≤‖∇(πt⊤)‖2+2ηK, ≤\| _ θ ( _ θ_t r )\|_2+ 2ηK, where the triangle inequality and similar calculations as Lemma C.1 have been used. Focusing only on the first term, we have, ‖∇(πt⊤)‖ \| _ θ ( _ θ_t r )\| =∑a∈⟦K⟧πt(a)2(r(a)−πt⊤)2 = _a∈ K _ θ_t(a)^2 (r(a)- _ θ_t r )^2 ≤∑a∈⟦K⟧πt(a)2(r(a∗)−πt⊤)2 ≤ _a∈ K _ θ_t(a)^2(r(a^*)- _ θ_t r)^2 =(r(a∗)−πt⊤)∑a∈⟦K⟧πt(a)2 = (r(a^*)- _ θ_t r ) _a∈ K _ θ_t(a)^2 ≤r(a∗)−πt⊤. ≤ r(a^*)- _ θ_t r. Hence, we have, ‖∇Φη(t)‖2≤r(a∗)−πt⊤+2ηK. \| _ θ _η( θ_t)\|_2≤ r(a^*)- _ θ_t r+ 2ηK. ∎ See 5.2 Proof. From Lemma C.4, we have, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 ] ≤(α2803Rmax3K3/2Δ2−α)‖∇Φη(t)‖22+β(t,1η) ≤ (α^2 803 R_ ^3K^3/2 ^2-α )\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ) (42) Since we want to progress toward the optimal policy, we need the first term of the right-hand side to be negative. Letting α=3Δ2160K3/2Rmax2(2Rmax+2ηK)α= 3 ^2160K^3/2R_ ^2 ( 2R_ + 2ηK ), similarly to Lemma C.5, we have, (α2803Rmax3K3/2Δ2−α)≤−α2, (α^2 803 R_ ^3K^3/2 ^2-α )≤- α2, which implies, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 ] ≤−α2‖∇Φη(t)‖22+β(t,1η) ≤- α2\| _ θ _η( θ_t)\|_2^2+β ( θ_t, 1η ) ≤−α2(r(a∗)−πt−K−1η)2+β(t,1η) ≤- α2 (r(a^*)- _ θ_t- K-1η )^2+β ( θ_t, 1η ) (43) where line (43) follows from Lemma 4.2. Now, recalling that, from Lemma C.5, β(t,1η) β ( θ_t, 1η ) ≤αηK(4‖∇Φη(t)‖2+1η) ≤ αηK (4\| _ θ _η( θ_t)\|_2+ 1η ) ≤αηK(4r(a∗)−4πt⊤+8ηK+Kη) ≤ αηK (4r(a^*)-4 _ θ_t r+ 8ηK+ Kη ) (44) where in line (44) Lemma C.6 has been used and α=Δ230K3/2Rmax2(2Rmax+2ηK)α= ^230K^3/2R_ ^2 ( 2R_ + 2ηK ) from Lemma C.5. Hence, we have, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 ] ≤−α2⋅πt(a∗)2(r(a∗)−πt⊤)2−α2η2(K−1)2 ≤- α2· _ θ_t(a^*)^2 (r(a^*)- _ θ_t r )^2- α2η^2(K-1)^2 +α(r(a∗)−πt⊤)1η(K−1)+β(t,1η) +α (r(a^*)- _ θ_t r ) 1η(K-1)+β ( θ_t, 1η ) ≤−α2⋅πt(a∗)2(r(a∗)−πt⊤)2−α2η2(K−1)2 ≤- α2· _ θ_t(a^*)^2 (r(a^*)- _ θ_t r )^2- α2η^2(K-1)^2 +α⋅πt(a∗)(r(a∗)−πt⊤)1η(K−1) +α· _ θ_t(a^*) (r(a^*)- _ θ_t r ) 1η(K-1) +αηK(4r(a∗)−4πt⊤+8ηK+Kη). + αηK (4r(a^*)-4 _ θ_t r+ 8ηK+ Kη ). (45) Rearranging the terms, and letting B=α(πt(a∗)2(K−1)+K)B=α ( _ θ_t(a^*)2(K-1)+K ) and C=α(4K(8ηK+1η)−12η(K−1)2)C=α (4K ( 8ηK+ 1η )- 12η(K-1)^2 ), we have, πt⊤−t[πt+1⊤] _t r-E_t[ _t+1 ] ≤−α2⋅πt(a∗)2(r(a∗)−πt⊤)2+1ηB(r(a∗)−πt⊤)+1ηC ≤- α2· _ θ_t(a^*)^2 (r(a^*)- _ θ_t r )^2+ 1ηB (r(a^*)- _ θ_t r )+ 1ηC =−α2⋅πt(a∗)2(r(a∗)−πt⊤)2+1ηB(r(a∗)−πt⊤)+1ηC =- α2· _ θ_t(a^*)^2 (r(a^*)- _ θ_t r )^2+ 1ηB (r(a^*)- _ θ_t r )+ 1ηC ≤−α2πt(a∗)2(r(a∗)−πt⊤)2+1ηB(r(a∗)−πt⊤)+1ηC, ≤- α2 _ θ_t(a^*)^2 (r(a^*)- _ θ_t r )^2+ 1ηB (r(a^*)- _ θ_t r )+ 1ηC, with the terms α,B,Cα,B,C being independent on the iteration t. Denoting the sub-optimality gap as δ(t)≔(π∗−πt)⊤δ( θ_t) (π^*- _ θ_t) r, we have, [δ(t+1)]−δ(t) [δ( θ_t+1) ]-δ( θ_t) =[(π∗−πt+1)⊤]−(π∗−πt)⊤ =E [(π^*- _ θ_t+1) r ]-(π^*- _ θ_t) r =πt⊤−t[πt+1⊤] = _t r-E_t[ _t+1 ] ≤−α2⋅πt(a∗)2⋅δ(t)2+1ηB⋅δ(t)+1ηC. ≤- α2· _ θ_t(a^*)^2·δ( θ_t)^2+ 1ηB·δ( θ_t)+ 1ηC. Taking the expectation, we have, [δ(t+1)]−[δ(t)] [δ( θ_t+1) ]-E [δ( θ_t) ] ≤−α2[πt(a∗)2⋅δ(t)2]+[1ηB⋅δ(t)]+1ηC ≤- α2E [ _ θ_t(a^*)^2·δ( θ_t)^2 ]+E [ 1ηB·δ( θ_t) ]+ 1ηC (46) ≤−α2[δ(t)]2[1πt(a∗)2]+[1ηB⋅δ(t)]+1ηC ≤- α2 E [δ( θ_t) ]^2E [ 1 _ θ_t(a^*)^2 ]+E [ 1ηB·δ( θ_t) ]+ 1ηC (47) ≤−α2ct∗[δ(t)]2+1ηB⋅[δ(t)]+1ηC ≤- α2c_t^*E [δ( θ_t) ]^2+ 1ηB·E [δ( θ_t) ]+ 1ηC where line 47 follows from Baudry et al. (2025) Appendix B.1, and ct∗≔[1πt(a∗)2]c_t^* [ 1 _ θ_t(a^*)^2 ]. Letting rt≔[δ(t)]r_t [δ( θ_t) ], and noting that B≤α(3K−1)=α⋅B~B≤α (3K-1 )=α· B since πt(a∗)≤1 _ θ_t(a^*)≤ 1, and letting C=α(K(8ηK+1η)−1η1516(K−1))≤α(4K(8ηK+1η)−12η(K−1)2)=αC~C=α (K ( 8ηK+ 1η )- 1η 1516(K-1) )≤α (4K ( 8ηK+ 1η )- 12η(K-1)^2 )=α C we can then rewrite the previous inequality as follows: rt+1 r_t+1 ≤rt−α2ct∗rt2+α1ηB~⋅rt+α1ηC~ ≤ r_t- α2c_t^*r_t^2+α 1η B· r_t+α 1η C ≤rt−α2ct∗rt2+α(1ηB~⋅Rmax+1ηC~) ≤ r_t- α2c_t^*r_t^2+α ( 1η B· R_ + 1η C ) ≤rt−α2supt≥0ct∗rt2+αη(B~⋅Rmax+C~) ≤ r_t- α2 _t≥ 0c_t^*r_t^2+ αη ( B· R_ + C ) Where the second inequality holds since rt≤Rmaxr_t≤ R_ . Letting b≔(B~⋅Rmax+C~)b ( B· R_ + C ) and c∗≔supt≥0ct∗c^* _t≥ 0c_t^*, following the analysis of the recurrence as done in Section C.4, and choosing the learning rate α as, α=min3Δ2160K3/2Rmax2(2Rmax+2ηK),c∗r0,ηc∗2b. α= \ 3 ^2160K^3/2R_ ^2( 2R_ + 2ηK), c^*r_0, η c^*2b \. (48) We can derive the convergence rate setting T←t+1T← t+1: [δ(T)] [δ( θ_T) ] ≤(1−122α2bηc∗)T[δ(0)]+2bc∗η ≤ (1- 12 2α^2bη c^* )^TE [δ( θ_0) ]+ 2bc^*η ≤CT[δ(0)]+β ≤ C^TE [δ( θ_0) ]+β To find the iteration complexity, let δ0≔[δ(0)] _0 [δ( θ_0) ]. First, we need to choose η to achieve [δ(T)]≤ϵE [δ( θ_T) ]≤ε assuming c∗≥0c^*≥ 0 is small and known. We have, 2bc∗η≤ϵ2⇒η≥8bc∗ϵ−2 2bc^*η≤ ε2 η≥ 8bc^*ε^-2 (49) Then, we have, (1−122α2bηc∗)T[δ(0)]≤ϵ2⇒T≥log2δ0ϵlog11−122α2bηc∗≥2ηc∗α2blog2δ0ϵ, (1- 12 2α^2bη c^* )^TE [δ( θ_0) ]≤ ε2 T≥ 2 _0ε 11- 12 2α^2bη c^*≥ 2η c^*α^2b 2 _0ε, (50) where the fact that log11−x≥x 11-x≥ x has been used. Now, substituting line (49) in the iteration complexity, we have, T≥2ηc∗αblog2δ0ϵ=4c∗ϵ−1αlog2δ0ϵ. T≥ 2η c^*α b 2 _0ε= 4c^*ε^-1α 2 _0ε. (51) Now, we need to substitute in line (51) the constraints on the learning rate α in line (48) to get the iteration complexity. Case 1. Let α=3Δ2160K3/2Rmax2(2Rmax+2ηK)=ΓK−3/2α= 3 ^2160K^3/2R_ ^2( 2R_ + 2ηK)= K^-3/2, where Γ≔3Δ2160Rmax2(2Rmax+2ηK) 3 ^2160R_ ^2 ( 2R_ + 2ηK ). Then, we have, T≥4c∗ϵ−1αlog2δ0ϵ=4c∗K3/2ϵ−1Γlog2ηϵ−1. T≥ 4c^*ε^-1α 2 _0ε= 4c^*K^3/2ε^-1 2ηε^-1. (52) Case 2. Let α≔c∗δ0α c^* _0. Since c∗≥1c^*≥ 1, this choice of learning rate is for sure greater than α=Δ230K3/2Rmax2(2Rmax+2ηK)α= ^230K^3/2R_ ^2( 2R_ + 2ηK). Case 3. Let α=ηc∗2bα= η c^*2b. Also, in this case, ηc∗>1η c^*>1 and, since η is chosen to be big in order to contrast the bias, this choice of learning rate is for sure greater than the first requirement. ∎ C.3 Proof for Section 5.2 Here, we provide the proofs for the Theorems presented in Section 5.2, providing a connection between πt(a∗) _ θ_t(a^*) and the gradient norm ‖∇Φη(t)‖2\| _ θ _η( θ_t)\|_2 in Lemma 5.3, showing the convergence guarantees of LB-SGB to a stationary point of Φη() _η( θ) in Theorem 5.4, and providing the sample complexity to learn an ϵε-optimal policy in Theorem 5.5. See 5.3 Proof. Assume πt(a∗)≤1/K _ θ_t(a^*)≤ 1/K and let ‖∇Φη(t)‖2≤gt\| _ θ _η( θ_t)\|_2≤ g_t. Our goal is to study the curvature of πt(a∗) _ θ_t(a^*) w.r.t. gtg_t. We have, ∂Φη(θt(a∗)θt(a∗)≥πt(a∗)δ(t)+1η(1−Kπt(a∗))≥1η(1−Kπt(a∗)), ∂ _η( _t(a^*) _t(a^*)≥ _ θ_t(a^*)δ( θ_t)+ 1η (1-K _ θ_t(a^*) )≥ 1η (1-K _ θ_t(a^*) ), where δ(t)≔(π∗−πt)⊤tδ( θ_t) (π^*- _ θ_t) r_t is positive under our assumption. Hence, we obtain, πt(a∗)≥max0,1K(1−ηgt), _ θ_t(a^*)≥ \0, 1K(1-η g_t) \, where the max is required to ensure πt(a∗) _ θ_t(a^*) is a probability. ∎ See 5.4 Proof. Considering the descent lemma in line 31, for any t∈⟦T⟧t∈ T , we have, Φη(t+1) _η( θ_t+1) ≥Φη(t)+⟨∇Φη(t),t+1−t⟩−(53‖∇Φη(t)‖2+15ηK)‖t+1−t‖22 ≥ _η( θ_t)+ _ θ _η( θ_t), θ_t+1- θ_t - ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )\| θ_t+1- θ_t\|_2^2 ≥Φη(t)+α⟨∇Φη(t),∇^Φη(t)⟩−α2(53‖∇Φη(t)‖2+15ηK)‖∇^Φη(t)‖22, ≥ _η( θ_t)+α _ θ _η( θ_t), ∇_ θ _η( θ_t) -α^2 ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )\| ∇_ θ _η( θ_t)\|_2^2, where the last inequality follows from the fact that the parameter update is t+1←t+α∇^Φη(t) θ_t+1← θ_t+α ∇_ θ _η( θ_t). In the following, we use the notation t[⋅]E_t[·] to denote the conditional expectation with respect to the history up to the t-th time step not included. Formally, consider the filtration defined by the σ-algebra ℱt=σ(0,0,1,…,t)F_t=σ( θ_0,D_0,D_1,…,D_t) encoding the stochasticity up to time step t included. The stochasticity comes from the samples, excluded the initial parameter 0 θ_0, and the parameter t θ_t is deterministically determined by the realization of the samples collected in the fist t−1t-1 time steps: t[⋅]=t[⋅|ℱt−1]E_t[·]=E_t[·|F_t-1]. We will use the fact that t[X]=XE_t[X]=X for ℱt−1F_t-1-measurable X. Now, for any t∈⟦T⟧t∈ T : Φη(t+1) _η( θ_t+1) ≥Φη(t)+αt[⟨∇Φη(t),∇^Φη(t)]⟩]−α2t[(53∥∇Φη(t)∥2+15ηK)∥∇^Φη(t)∥22] ≥ _η( θ_t)+ _t [ _ θ _η( θ_t), ∇_ θ _η( θ_t)] ]-α^2E_t [ ( 53\| _ θ _η( θ_t)\|_2+ 15ηK )\| ∇_ θ _η( θ_t)\|_2^2 ] ≥Φη(t)+αt[‖∇Φη(t)‖2]2 ≥ _η( θ_t)+ _t [\| _ θ _η( θ_t)\|_2 ]^2 −α2(53‖∇Φη(t)‖2+15ηK)[16Rmax3K3/2Δ2‖∇Φη(t)‖2+2ηK(4ηK+16Rmax3K3/2Δ2)] -α^2 ( 53\| _ θ _η( θ_t)\|_2+ 15ηK ) [ 16R_ ^3K^3/2 ^2\| _ θ _η( θ_t)\|_2+ 2ηK ( 4ηK+ 16R_ ^3K^3/2 ^2 ) ] ≥Φη(t)+α‖∇Φη(t)‖22−α2(53‖∇Φη(t)‖2+15ηK)[16Rmax3K3/2Δ2‖∇Φη(t)‖2+Sη] ≥ _η( θ_t)+α\| _ θ _η( θ_t)\|_2^2-α^2 ( 53\| _ θ _η( θ_t)\|_2+ 15ηK ) [ 16R_ ^3K^3/2 ^2\| _ θ _η( θ_t)\|_2+ Sη ] =Φη(t)+α(1−80Rmax3K3/23Δ2α)‖∇Φη(t)‖22 = _η( θ_t)+α (1- 80R_ ^3K^3/23 ^2α )\| _ θ _η( θ_t)\|_2^2 −[(53Sη+240Rmax3K5/2ηΔ2)‖∇Φη(t)‖2+15η2KS]α2 - [ ( 53 Sη+ 240R_ ^3K^5/2η ^2 )\| _ θ _η( θ_t)\|_2+ 15η^2KS ]α^2 ≥Φη(t)+α(1−80Rmax3K3/23Δ2α)‖∇Φη(t)‖22 ≥ _η( θ_t)+α (1- 80R_ ^3K^3/23 ^2α )\| _ θ _η( θ_t)\|_2^2 −[(53Sη+240Rmax3K5/2ηΔ2)(2Rmax+2ηK)+15η2KS]α2 - [ ( 53 Sη+ 240R_ ^3K^5/2η ^2 ) (2R_ + 2ηK )+ 15η^2KS ]α^2 =Φη(t)+α(1−80Rmax3K3/23Δ2α)‖∇Φη(t)‖22−Wηα2 = _η( θ_t)+α (1- 80R_ ^3K^3/23 ^2α )\| _ θ _η( θ_t)\|_2^2- Wηα^2 where in the second inequality Lemma 5.1 has been exploited, S≔2K(4ηK+16Rmax3K3/2Δ2)S 2K ( 4ηK+ 16R_ ^3K^3/2 ^2 ), the last inequality follows from Lemma C.6, and finally W≔(53S+240Rmax3K5/2Δ2)(2Rmax+2ηK)+15KSηW ( 53S+ 240R_ ^3K^5/2 ^2 ) (2R_ + 2ηK )+ 15KSη. Now, applying the law total expectation and telescopic sum for all t≤Tt≤ T and letting L≔80Rmax3K3/23Δ2αL 80R_ ^3K^3/23 ^2α, we have, Φη(θ∗)−Φη(θ0) _η(θ^*)- _η( _0) ≥Φη(θT)−Φη(θ0) ≥ _η( _T)- _η( _0) =∑t=0T[Φη(t+1)−Φη(t)] = _t=0^TE [ _η( θ_t+1)- _η( θ_t) ] ≥∑t=0Tα(1−Lα)[‖∇Φη(t)‖22]−WTηα2. ≥ _t=0^Tα (1-Lα )E [\| _ θ _η( θ_t)\|_2^2 ]- WTηα^2. (53) Now, isolating the sum of the squared gradient norms and dividing everything by T, we have, 1T∑t=0T[‖∇Φη(t)‖22]≤Φη(θT)−Φη(θ0)T+Wηα2α(1−Lα), 1T _t=0^TE [\| _ θ _η( θ_t)\|_2^2 ]≤ _η( _T)- _η( _0)T+ Wηα^2α (1-Lα ), which requires the learning rate to be α<1L=3Δ280Rmax3K3/2α< 1L= 3 ^280R_ ^3K^3/2 in order to converge. Now, we want to prove that, after some warm-up time, it holds: 1T∑t=0T[‖∇Φη(t)‖22]≤(Wαη). 1T _t=0^TE [\| _ θ _η( θ_t)\|_2^2 ] ( Wαη ). Noting that when α≤1/2Lα≤ 1/2L, we have α(1−Lα)=α/2α(1-Lα)=α/2, we want to find T0T_0 such that, 2(Φη(θT)−Φη(θ0))αT<Wαη, 2 ( _η( _T)- _η( _0) )α T< Wαη, which holds when: T0>(ΨηWα2), T_0>O ( ηWα^2 ), where Ψ≔Φη(θT)−Φη(θ0) _η( _T)- _η( _0). ∎ See 5.5 Proof. Let us start from the recurrence in line (46) from Theorem 5.2. Denoting the sub-optimality gap as δ(t)≔(π∗−πt)⊤δ( θ_t) (π^*- _ θ_t ) r and taking the expectation, we have, [δ(t+1)]−[δ(t)]≤−α2[πt(a∗)2δ2(t)]+αηK⋅[t]+αη2K2 [δ( θ_t+1) ]-E [δ( θ_t) ]≤- α2E [ _ θ_t(a^*)^2δ^2( θ_t) ]+ αηK·E [ θ_t ]+ αη^2K^2 (54) Our goal is to study the behaviour of πt(a∗) _ θ_t(a^*) in the worst case scenario. Let xt≔πt(a∗)x_t _ θ_t(a^*) and gt≔‖∇Φη(t)‖2g_t \| _ θ _η( θ_t)\|_2. Assuming xt<1/Kx_t<1/K, we have, gt≥xtδt+1η(1−Kxt)≥1η(1−Kxt), g_t≥ x_t _t+ 1η (1-Kx_t )≥ 1η (1-Kx_t ), since under our condition of xtx_t, we have xtδt>0x_t _t>0. Taking the square of gtg_t, we obtain, gt2≥1η2(1−Kxt)2≥1η2(1−2Kxt), g_t^2≥ 1η^2 (1-Kx_t )^2≥ 1η^2 (1-2Kx_t ), which follows from the Bernoulli inequality. Now, isolating xtx_t, we have, xt≥12K(1−η2gt2)⇒xt2≥14K2(1−η2gt2)2≥14K2(1−2η2gt2), x_t≥ 12K (1-η^2g_t^2 ) x_t^2≥ 14K^2 (1-η^2g_t^2 )^2≥ 14K^2 (1-2η^2g_t^2 ), which, again, follows from the Bernoulli inequality. Now, plugging the lower bound for πt(a∗) _ θ_t(a^*) in line 54, we have, [δ(t+1)]−[δ(t)] [δ( θ_t+1) ]-E [δ( θ_t) ] ≤−α8K2[(1−2η2gt2)δ(t)]+αηK⋅[t]+αη2K2 ≤- α8K^2E [ (1-2η^2g_t^2 )δ( θ_t) ]+ αηK·E [ θ_t ]+ αη^2K^2 ≤α8K2[δ2(t)]+αηK⋅[δ(t)]+αη24K2Rmax2[gt2]+αη2K2. ≤ α8K^2E [δ^2( θ_t) ]+ αηK·E [δ( θ_t) ]+ αη^24K^2R_ ^2E [g_t^2 ]+ αη^2K^2. Letting rt≔[δ(t)]r_t [δ( θ_t) ] and completing the square, we obtain, rt+1−rt r_t+1-r_t ≤−α8K2rt2+αηK⋅rt+αη24K2Rmax2[gt2]+αη2K2±2αη2K4 ≤- α8K^2r_t^2+ αηK· r_t+ αη^24K^2R_ ^2E [g_t^2 ]+ αη^2K^2± 2 αη^2K^4 ≤−α(rt22K−2K2η)2+αη24K2Rmax2[gt2]+3αη2K4. ≤-α ( r_t2 2K- 2 K^2η )^2+ αη^24K^2R_ ^2E [g_t^2 ]+3 αη^2K^4. Now, using the telescopic sum from t=1t=1 to T, we obtain, 1T∑t=1T(rt22K−2K2η)2≤r0−rTαT+η24K2Rmax21T∑t=1T[gt2]+3K4η2. 1T _t=1^T ( r_t2 2K- 2 K^2η )^2≤ r_0-r_Tα T+ η^24K^2R_ ^2 1T _t=1^TE [g_t^2 ]+3 K^4η^2. (55) Now, we need to isolate the term 1T∑t=1Trt 1T _t=1^Tr_t. Let us rewrite line 55 as follows: 1T∑t=1T(art−b)2≤cT. 1T _t=1^T (ar_t-b )^2≤ cT. Applying Jensen’s inequality, we have, 1T∑t=1T(art−b)≤cT. 1T _t=1^T(ar_t-b)≤ cT. Finally, isolating the term we are interested in, we have: 1T∑t=1Trt≤1a(cT+b). 1T _t=1^Tr_t≤ 1a ( cT+b ). Substituting the values of a, b and c, we have, 1T∑t=1Trt 1T _t=1^Tr_t ≤8K2r0−rTαT+η24K2Rmax21T∑t=1T[gt2]+3K4η2+82K4η ≤ 8K^2 r_0-r_Tα T+ η^24K^2R_ ^2 1T _t=1^TE [g_t^2 ]+3 K^4η^2+8 2 K^4η ≤27RmaxK2αT+27η2Rmax21T∑t=1T[gt2]+3⋅26K6η2+82K4η. ≤ 2^7R_ K^2α T+2^7η^2R_ ^2 1T _t=1^TE [g_t^2 ]+3· 2^6 K^6η^2+8 2 K^4η. Now, we have to study the term 1T∑t=1T[gt2] 1T _t=1^TE [g_t^2 ]. From Theorem 5.4, we have 1T∑t=1T[gt2]≤(K5/2αΔ2η) 1T _t=1^TE [g_t^2 ] ( K^5/2α ^2η ) (56) which holds after the warm-up time T0T_0, defined as: T0=(2RmaxηΔ2K5/2α2). T_0=O ( 2R_ η ^2K^5/2α^2 ). (57) Now, plugging line (56) in line (55) we obtain: 1T∑t=1Trt≤27RmaxK2αT+27ηRmax2K5/2αΔ2+3⋅26K6η2+82K4η 1T _t=1^Tr_t≤ 2^7R_ K^2α T+ 2^7η R_ ^2K^5/2α ^2+3· 2^6 K^6η^2+8 2 K^4η (58) Our goal is to select the parameters to have 1T∑t=1Trt≤ϵ 1T _t=1^Tr_t≤ε. Hence, we have, 82K4η≤ϵ2, 8 2 K^4η≤ ε2, (59) which implies η=(K4ϵ−1)η=O (K^4ε^-1 ). Now, letting the first term of the right-hand side of line (58) to be less than or equal to ϵ/2ε/2, we want each term inside the square root to be less than or equal to ϵ2/12ε^2/12. Starting with a requirement on the barrier parameter η, we have, 3⋅26K6η2≤ϵ212, 3· 2^6 K^6η^2≤ ε^212, which implies η=(K3ϵ−1)η=O (K^3ε^-1 ), which is dominated by the requirement in line (59). To obtain a requirement on the learning rate α, we let, 27ηRmax2K5/2αΔ2≤ϵ212, 2^7η R_ ^2K^5/2α ^2≤ ε^212, which implies α=(K−11/2Δ2ϵ3)α=O (K^-11/2 ^2ε^3 ). Finally, we find the sample complexity T letting, 27RmaxK2αT≤ϵ212, 2^7R_ K^2α T≤ ε^212, which implies T=(K15/2Δ−2ϵ−5)T=O (K^15/2 ^-2ε^-5 ). We can now compute the warm-up time from line (57): T0=(K17/2Δ−2ϵ−7), T_0=O (K^17/2 ^-2ε^-7 ), which dominates T, hence being the sample complexity of LB-SGB. ∎ See 5.6 Proof. We define the requirements for the smoothing parameter α and the learning rate η based on the relationship T=(Δ−2ϵ−7)T=O( ^-2ε^-7). This implies that ϵ=(Δ−2/7T−1/7)ε=O( ^-2/7T^-1/7). Substituting this into the requirements α=(Δ2ϵ3)α=O( ^2ε^3) and η=(ϵ−1)η=O(ε^-1), we obtain: α=(Δ8/7T−3/7),η=(Δ2/7T1/7). α=O ( ^8/7T^-3/7 ), η=O ( ^2/7T^1/7 ). (60) Now, starting from line (58) of Theorem 5.5, we evaluate the expression for the regret: [∑t=1T(π∗−πθt)⊤t]≤(Tα+αηT+Tη2+Tη). [ _t=1^T (π^*- _ _t ) r_t ] ( Tα+αη T+ Tη^2+ Tη ). Substituting the requirements from (60) into each term, we track the dependence on T and Δ : [∑t=1T(π∗−πθt)⊤t] [ _t=1^T (π^*- _ _t ) r_t ] ≤(TΔ8/7T−3/7+(Δ8/7T−3/7)(Δ2/7T1/7)T+T(Δ2/7T1/7)2+TΔ2/7T1/7) ( T ^8/7T^-3/7+( ^8/7T^-3/7)( ^2/7T^1/7)T+ T( ^2/7T^1/7)^2+ T ^2/7T^1/7 ) =(Δ−8/7T10/7+Δ10/7T5/7+Δ−4/7T5/7+Δ−2/7T6/7) =O ( ^-8/7T^10/7+ ^10/7T^5/7+ ^-4/7T^5/7+ ^-2/7T^6/7 ) =(Δ−8/7T10/7+Δ−2/7T6/7) =O ( ^-8/7T^10/7+ ^-2/7T^6/7 ) =(Δ−4/7T5/7+Δ−2/7T6/7). =O ( ^-4/7T^5/7+ ^-2/7T^6/7 ). Since T6/7T^6/7 asymptotically dominates T5/7T^5/7, the final expression of the regret is: [∑t=1T(π∗−πθt)⊤t]≤(Δ−2/7T6/7). [ _t=1^T (π^*- _ _t ) r_t ] ( ^-2/7T^6/7 ). (61) ∎ C.4 Recurrences The goal of this section is to study the recurrence, rt+1≤rt−αa2rt2+αbη, r_t+1≤ r_t-α a2r_t^2+α bη, (62) following the analysis proposed by Montenegro et al. (2024). For this purpose, we define the following helper sequence: ρ0=r0ρt+1=ρt−αa2ρt2+αbη,if t≥0 cases _0=r_0\\ _t+1= _t-α a2 _t^2+α bη, t≥ 0 cases (63) It is possible to show that, under a condition on the step size α, the sequence ρt _t upper bounds the recurrence rtr_t. Lemma C.7. If α≤1aρtα≤ 1a _t, for every t≥0t≥ 0 we have ρt≥rt _t≥ r_t. Proof. By induction on t. For t=0t=0, the statement is true since ρ0=r0 _0=r_0. Suppose the statement holds for j≤tj≤ t. Then, for t+1t+1, we have: ρt+1 _t+1 =ρt−αa2ρt2+αbη = _t-α a2 _t^2+α bη ≥rt−αa2rt2+αbη ≥ r_t-α a2r_t^2+α bη ≥rt+1 ≥ r_t+1 Where the first inequality holds from the inductive hypothesis and by the fact that the function f(x)=x−αa2x2f(x)=x-α a2x^2 is non-decreasing when α is chosen properly. Indeed, we need to study the sign of the derivative of f(x)f(x): f′(x)=1−αax≥0⇒x≤1αa f (x)=1-α ax≥ 0 x≤ 1α a Hence, we need α≤1αρtα≤ 1α _t to ensure ρt _t is non-decreasing, and so is rtr_t by the inductive hypothesis. ∎ Thus, it is possible to study the convergence of ρt _t as a surrogate for rtr_t. If ρt _t is convergent, than it converges to a fixed point ρ¯ ρ as follows: ρ¯=ρ¯−αa2ρ¯2+αbη⇒ρ¯=2bηa ρ= ρ-α a2 ρ^2+α bη ρ= 2bη a (64) In which only the positive solution of the second-order equation is considered, since rt≥0r_t≥ 0 by definition and ρt≥rt _t≥ r_t. It is now necessary to study the monotonicity of ρt _t. The following lemma states that, under a specific choice of the learning rate, initializing ρ0=r0 _0=r_0 above the fixed point ρ¯ ρ, the sequence will be non-increasing, remaining in the interval [ρ¯,r0][ ρ,r_0]. Symmetrically, initializing ρ0 _0 below the fixed point, the sequence will be non-decreasing, remaining in the interval [r0,ρ¯][r_0, ρ]. Lemma C.8. The following statements hold: • if r0≥ρ¯r_0≥ ρ and α≤1αr0α≤ 1α r_0 it holds that ρ¯≤ρt+1≤ρt ρ≤ _t+1≤ _t. • if r0≤ρ¯r_0≤ ρ and α≤1αρ¯α≤ 1α ρ it holds that ρ¯≥ρt+1≤ρt ρ≥ _t+1≤ _t. Proof. Let’s start with the first statement, by induction on t. The inductive hypothesis is: ρt+1≤ρt _t+1≤ _t and ρt+1≤ρ¯ _t+1≤ ρ. For t=0t=0, for the first inequality, we have, ρ1 _1 =ρ0−αa2ρ02+αb2≤ρ0−αa2ρ¯2+αb2=ρ0, = _0-α a2 _0^2+α b2≤ _0-α a2 ρ^2+α b2= _0, where the fact that ρ0≥ρ¯≥0 _0≥ ρ≥ 0 and the definition of ρ¯ ρ has been used. For the second inequality, we have, ρ1 _1 =ρ0−αa2ρ02+αb2≤ρ¯−αa2ρ¯2+αb2=ρ¯, = _0-α a2 _0^2+α b2≤ ρ-α a2 ρ^2+α b2= ρ, since the function x−αa2x2x-α a2x^2 is non-decreasing in x for x≤ρ0x≤ _0 since α≤1aρ0α≤ 1a _0 and by definition of ρ¯ ρ. Suppose now the statements hold for j≤tj≤ t. Under the inductive hypothesis ρt≤ρ0 _t≤ _0, the choice of the learning rate α≤1aρ0α≤ 1a _0 implies α≤1aρtα≤ 1a _t. Thus, for the first inequality, we have, ρt+1 _t+1 =ρt−αa2ρt2+αb2≤ρt−αa2ρ¯2+αb2=ρt, = _t-α a2 _t^2+α b2≤ _t-α a2 ρ^2+α b2= _t, where the inductive hypothesis and the definition of ρ¯ ρ have been used. For the second inequality, we have, ρt+1 _t+1 =ρt−αa2ρt2+αb2≤ρ¯−αa2ρ¯2+αb2=ρ¯, = _t-α a2 _t^2+α b2≤ ρ-α a2 ρ^2+α b2= ρ, where the inductive hypothesis and the fact that x−αa2x2x-α a2x^2 is non-decreasing in x for x≤ρtx≤ _t, since α≤1aρtα≤ 1a _t. For the second statement, we can proceed analogously as for the first one, switching the signs of the inequalities and recalling that, in this case, ρt _t is upper-bounded by ρ¯ ρ. ∎ We can now focus on the case r0≥ρ¯r_0≥ ρ, since the second case is irrelevant for the convergence. In this case, we can show that ρt _t converges to ρ¯ ρ with a certain rate. To this end, we can study the following auxiliary sequence: ν0=ρ0νt+1=(1−αa2ρ¯)νt+αbη,if t≥0, cases _0= _0\\ _t+1= (1-α a2 ρ ) _t+α bη, t≥ 0, cases (65) for which we need to prove that νt _t upper bounds ρt _t. Lemma C.9. If r0≥ρ¯r_0≥ ρ and α≤1ar0α≤ 1a~r_0, then it holds that, for t≥0t≥ 0, νt≥ρt _t≥ _t. Proof. By induction on t. For t=0t=0, we have that ν0=ρ0 _0= _0, so the statement holds. Suppose the statement holds for j≤tj≤ t. Then, for t+1t+1, we have, νt+1 _t+1 =(1−αa2ρ¯)νt+αbη = (1-α a2 ρ ) _t+α bη ≥(1−αa2ρ¯)ρt+αbη ≥ (1-α a2 ρ ) _t+α bη ≥(1−αa2ρt)ρt+αbη=ρt+1, ≥ (1-α a2 _t ) _t+α bη= _t+1, where the first inequality holds by inductive hypothesis, and the second inequality holds since ρt≥ρ¯ _t≥ ρ and by the fact that 1−αa2ρt≥01-α a2 _t≥ 0 whenever α≤2aρtα≤ 2a _t, which is entailed by the requirement α≤1aρ0α≤ 1a _0, recalling that ρk≥0 _k≥ 0 since ρ¯≥0 ρ≥ 0. ∎ It is now possible to study the convergence rate of the sequence νt _t, which can be obtained by unrolling the recursion: νt+1 _t+1 =(1−αa2ρ¯)t+1ρ0+αbη∑j=0t(1−αa2ρ¯)j = (1-α a2 ρ )^t+1 _0+α bη _j=0^t (1-α a2 ρ )^j (66) ≤(1−αa2ρ¯)t+1ρ0+αbη∑j=0∞(1−αa2ρ¯)j ≤ (1-α a2 ρ )^t+1 _0+α bη _j=0^∞ (1-α a2 ρ )^j =(1−αa2ρ¯)t+1ρ0+2bηaρ¯ = (1-α a2 ρ )^t+1 _0+ 2bη a ρ (67) =(1−122α2abη)t+1ρ0+2bηa, = (1- 12 2α^2abη )^t+1 _0+ 2bη a, where Equation (67) follows from choosing the learning rate α such that the series converges, namely, α≤η2abα≤ η2ab Putting all the conditions on the learning rate together, we have, α=min1ar0,η2ab α= \ 1a~r_0, η2ab \ Appendix D Experimental Details In this section, we present the details of the experiments provided in Section 7, with additional results regarding the comparison of LB-SGB with SGB, SGB with entropy regularization (ENT), and Natural Policy Gradient (NPG). Both SGB and ENT have been described in Appendix B. In the experiments, we focus on the convergence dynamics of the policy πt _ θ_t toward the optimal action a∗a^*. D.1 Setting To evaluate the convergence of the algorithms, we exploit a stationary K-armed Gaussian bandit environment. Each action a∈⟦K⟧a∈ K is associated with a fixed expected value r(a)r(a) which remains constant through the time horizon T. The reward Rt(at)R_t(a_t) observed by the agent at time t upon selecting action ata_t is sampled according to, rt∣at=a∼(r(a),1), r_t a_t=a (r(a),1 ), implying that the noise ϵt=Rt(at)−r(at) _t=R_t(a_t)-r(a_t) is i.i.d. following a standard distribution (0,1)N(0,1). The vector of true means ∈ℝK r ^K is built to ensure the mean reward vector has support in [−Rmax,Rmax][-R_ ,R_ ], with a specified Δ∗ ^* with the second-best arm. D.2 On the Barrier Parameter η The selection of the hyper-parameter η is driven by a trade-off identified in our theoretical analysis. First, η must be chosen sufficiently large to minimize the bias of the converged solution relative to the optimal policy. Since the true optimal policy is deterministic, lower values of η induce excessive stochasticity, preventing the policy from approximating the optimal distribution. However, η cannot be arbitrarily large. As η→∞η→∞, the regularization term vanishes relative to the reward signal, and the objective function recovers the standard SGB formulation. This would reintroduce the issues inherent to standard policy gradients, such that vanishing gradients or premature convergence, that our regularization aims to mitigate. D.3 Sensitivity to the Number of Arms K In these experiments, we focus on the stability of the algorithms under varying learning rates α and their scalability as the number of arms K increases. We conducted experiments on bandit instances with K=10,100,1000K=\10,100,1000\ and, for each setting, used learning rates α=0.01,0.1α=\0.01,0.1\. All the results are averaged over 100100 independent runs, and the plots show the 95%95\% confidence intervals. Table 3 shows the details on the hyperparameters used in the experiments. Parameters for α=0.01α=0.01 !20 K 10 100 1000 Δ∗ ^* 0.10.1 RmaxR_ 1.01.0 33 η 10001000 20002000 40004000 Parameters for α=0.01α=0.01 !20 K 10 100 1000 Δ∗ ^* 0.10.1 RmaxR_ 1.01.0 33 η 10001000 500500 50005000 Table 3: Experimental details for the sensitivity to the number of arms. The left table shows the parameters when α=0.01α=0.01, the right table shows the parameters when α=0.1α=0.1. The results are presented in Figure 4 (K=10K=10), Figure 5 (K=100K=100), and Figure 6 (K=1000K=1000). The experiments show that LB-SGB, when the learning rate is low (α=0.01α=0.01), matches or exceeds the performance of the baselines. Furthermore, as the number of arms grows, LB-SGB achieves significantly higher performance than SGB and ENT, showing that the log-barrier regularization effectively scales to high-dimensional problems. When the learning rate is more aggressive (α=0.1α=0.1), standard PG methods often converge prematurely to suboptimal arms, failing to learn the optimal action. In contrast, LB-SGB successfully learns the optimal action. (a) K=10K=10, α=0.01α=0.01, and η=1000η=1000 (b) K=10K=10, α=0.1α=0.1, and η=1000η=1000 Figure 4: Comparison between SGB, LB-SGB and entropy-regularized SGB (ENT) with K=10K=10 and different learning rates α (100100 runs ±95%± 95\% C.I.). (a) K=100K=100, α=0.01α=0.01, and η=500η=500 (b) K=100K=100, α=0.1α=0.1, and η=2000η=2000 Figure 5: Comparison between SGB, LB-SGB and entropy-regularized SGB (ENT) with K=100K=100 and different learning rates α (100100 runs ±95%± 95\% C.I.). (a) K=1000K=1000, α=0.01α=0.01, and η=4000η=4000 (b) K=1000K=1000, α=0.1α=0.1, and η=5000η=5000 Figure 6: Comparison between SGB, LB-SGB and entropy-regularized SGB (ENT) with K=1000K=1000 and different learning rates α (100100 runs ±95%± 95\% C.I.). D.4 Sensitivity to the Sub-optimality Gap Δ∗ ^* In these experiments, we focus on the stability of the algorithms under varying learning rates α and their scalability as the sub-optimality gap Δ∗ ^* decreases. We conducted experiments in bandit instances with K=100K=100 arms, and different sub-optimality gaps Δ∗=0.05,0.005 ^*=\0.05,0.005\ using the learning rates α=0.01,0.1α=\0.01,0.1\. Table 4 shows the details on the hyperparameters used in the experiments. Parameters for α=0.01α=0.01 !20 ∗ ^* 0.050.05 0.0050.005 K 100100 RmaxR_ 33 η 70007000 30003000 Parameters for α=0.1α=0.1 !20 ∗ ^* 0.050.05 0.0050.005 K 100100 RmaxR_ 33 η 10410^4 20002000 Table 4: Experimental details for the sensitivity to the sub-optimality gap. The left table shows the parameters when α=0.01α=0.01, and the right table shows the parameters when α=0.1α=0.1. The results are presented in Figure 2(a) (Δ∗=0.05 ^*=0.05) and Figure 2(b) (Δ∗=0.005 ^*=0.005). The experiments show that, while with a small learning rate (α=0.01α=0.01) the results are comparable, with higher learning rates the LB-SGB learns the optimal policy, whereas SGB and ENT fail. (a) K=100K=100, Δ∗=0.05 ^*=0.05, α=0.01α=0.01, and η=7000η=7000 (b) K=100K=100, Δ∗=0.05 ^*=0.05, α=0.1α=0.1, and η=3000η=3000 Figure 7: Comparison between SGB, LB-SGB and entropy-regularized SGB (ENT) with K=100K=100, Δ∗=0.05 ^*=0.05, and different learning rates α (100100 runs ±95%± 95\% C.I.). (a) K=100K=100, Δ∗=0.005 ^*=0.005, α=0.01α=0.01, and η=104η=10^4 (b) K=100K=100, Δ∗=0.005 ^*=0.005, and α=0.1α=0.1, and η=2000η=2000 Figure 8: Comparison between SGB, LB-SGB and entropy-regularized SGB (ENT) with K=100K=100, Δ∗=0.005 ^*=0.005, and different learning rates α (100100 runs ±95%± 95\% C.I.). D.5 Comparison Between LB-SGB and NPG In these experiments, we compare LB-SGB and NPG under varying learning rates α as the number of arms K increases. We conducted experiments on bandit instances with K=10,100K=\10,100\ and, for each setting, used learning rates α=0.01,0.1α=\0.01,0.1\. All the results are averaged over 100100 independent runs, and the plots show the 95%95\% confidence intervals. Table 5 shows the details on the hyperparameters used in the experiments. Parameters for α=0.01α=0.01 !20 K 10 100 Δ∗ ^* 0.10.1 RmaxR_ 11 33 η 10001000 500500 Parameters for α=0.1α=0.1 !20 K 10 100 Δ∗ ^* 0.10.1 RmaxR_ 11 33 η 10001000 20002000 Table 5: Experimental details for the comparison of LB-SGB an NPG. The left table shows the parameters when α=0.01α=0.01, and the right table shows the parameters when α=0.1α=0.1. The results are presented in Figure 9 (K=10K=10) and 10 (K=100K=100). The experiments show that while both algorithms exploit the geometry of the policy space by controlling the Fisher information (see Section 6), NPG converges to a suboptimal arm, especially when a large number of arms are considered. (a) α=0.01α=0.01, η=1000η=1000 (b) α=0.1α=0.1, η=1000η=1000 Figure 9: Comparison between SGB, and NPG with K=10K=10, Δ∗=0.1 ^*=0.1, and different learning rates α (100100 runs ±95%± 95\% C.I.). (a) α=0.01α=0.01, η=500η=500 (b) α=0.1α=0.1, η=2000η=2000 Figure 10: Comparison between SGB, and NPG with K=100K=100, Δ∗=0.1 ^*=0.1, and different learning rates α (100100 runs ±95%± 95\% C.I.).