How Log-Barrier Helps Exploration in Policy Optimization

Leonardo Cesani; Matteo Papini; Marcello Restelli

cs.LGMar 16, 2026

How Log-Barrier Helps Exploration in Policy Optimization

Authors: Leonardo Cesani, Matteo Papini, Marcello Restelli

Organizations: Politecnico di Milano, Milan, Italy · Università degli Studi di Milano, Milan, Italy

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.

Figures & tables

Reference	Sample Complexity	Method	Assumption on $c^{*\dagger}$
Mei et al. [15]	$\mathcal{O}\left(\epsilon^{-1}\right)$	Vanilla PG ( SGB )	✓
Mei et al. [24]	$\mathcal{O}\left(\epsilon^{-1}\right)$	NPG with Baseline	✓
This work	$\bm{\widetilde{\mathcal{O}}\left(\epsilon^{-1}\right)}$	Log-barrier ( LB-SGB )	✓
Zhang et al. [35]	$\mathcal{O}\left(\epsilon^{-6}\right)$	Log-barrier, Clipping	✗
Yuan et al. [13]	$\mathcal{O}\left(\epsilon^{-6}\right)$	Log-barrier	✗
This work	$\bm{\mathcal{O}\left(\epsilon^{-5}\right)}$	Log-barrier ( LB-SGB )	✗

Table 1: Comparison of sample complexities for different PG algorithms in the MAB framework. † We define

c^{*}\coloneqq\sup_{t}\mathbb{E}\left[\pi_{\bm{\theta}_{t}}(a^{*})^{-2}\right]

Panel of Figure 1 — Figure 1: Comparison between algorithms across $K=\{10,100,1000\}$ . The top row uses a learning rate $\alpha=0.01$ , and the bottom row uses $\alpha=0.1$ . All experiments use $\Delta^{*}=0.1$ (100 runs $\pm$ 95% C.I.).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Reference	Sample Complexity	Learning Rate $\alpha$	Method	Assumptions
Mei et al. [15]	$\mathcal{O}\left(\epsilon^{-1}\right)$	$\mathcal{O}\left(1\right)$	Vanilla PG ( SGB )	No ties, $c^{*}<\infty^{\dagger}$
Lu et al. [36]	$\mathcal{O}\left(\epsilon^{-3}\right)^{\ddagger}$	$\mathcal{O}\left(\alpha^{t}\right)$	Vanilla PG	$c^{*}<\infty$
This work	$\bm{\widetilde{\mathcal{O}}\left(\epsilon^{-1}\right)}$	$\bm{\mathcal{O}\left(1\right)}$	Log-barrier	No ties, $\bm{c^{*}<\infty}$
Ding et al. [37]	$\mathcal{O}\left(\epsilon^{-2}\right)$	$\mathcal{O}\left(1/t\right)$	Entropy regularization	$\inf_{t}\min_{a}\pi_{\bm{\theta}}(a)>0$
Cen et al. [38]	$\mathcal{O}\left(\epsilon^{-2}\right)$	$\mathcal{O}\left(1/\log t\right)$	Entropy regularized NPG	Generative model
Zhang et al. [35]	$\mathcal{O}\left(\epsilon^{-6}\right)$	$\mathcal{O}\left(1/\log t\right)$	Log-barrier, Clipping

Appendix

Table 2: Comparison of convergence rates and learning rates for different PG algorithms. † We define

c^{*}\coloneqq\sup_{t}\mathbb{E}\left[\pi_{\bm{\theta}_{t}}(a^{*})^{-2}\right]

. ‡ In Lu et al. [36] , the authors show that SGB achieves

\mathcal{O}\left(\epsilon^{-1}\right)

\mathcal{O}\left(\epsilon^{-3}\right)

depending on whether the initial learning rate is tuned to meet the strong growth condition or not. Nonetheless, it seems that their analysis has a flaw when computing the learning rate in the proof of their Theorem 5.

$\bm{K}$	$\bm{\alpha=0.01}$	$\bm{\alpha=0.1}$
$10$	$1000$
$100$	$2000$
$1000$	$10000$	$5000$

Appendix

Table 3: Choice of the barrier parameter

\eta

for LB-SGB and ENT across different action spaces

K

and learning rates

\alpha

Panel of Figure 2 — Figure 2: Comparison between algorithms across $K=\{10,100,1000\}$ . The top row uses a learning rate $\alpha=0.01$ , and the bottom row uses $\alpha=0.1$ . All experiments use $\Delta^{*}=0.1$ (100 runs $\pm$ 95% C.I.). For presentation purposes, these experiments are the same as the ones presented in Figure 1 .

Panel of Figure 3 — Figure 3: Comparison between LB-SGB , NPG with baseline, and LB-SGB with clipping, across different MAB instances with $K=\{10,100,1000\}$ . All experiments utilize $\Delta^{*}=0.1$ , $R_{\max}=1$ , and aggregate $100$ independent runs ( $\pm 95\%$ C.I.).

Panel of Figure 4 — Figure 4: Performance, minimum action probability and regret for SGB and LB-SGB with different choices for $\eta$

Explore similar work

May 26, 2026

Sample Complexity of Policy Gradient for Log-Growth Control

We study the sample complexity of policy gradient for log-growth control -- the problem of learning, from observed state transitions, a feedback gain that optimally stabilizes a scalar linear system driven through a multiplicative-noise actuation channel. The objective

J(K) = \mathbb{E}[\log|1+BK|]

is the top Lyapunov exponent of the closed loop. This problem carries a structural difficulty we call the cusp obstruction: the optimal gain

K^*

always places the noise singularity

b_{\rm sing}(K) = -1/K

in the interior of the support. At this singular optimum the policy gradient exists only as a Cauchy principal value, not as a Lebesgue integral, and the natural single-sample gradient estimator has infinite variance. Standard first-order stochastic-optimization analysis is thus inapplicable at the optimum, and merely smoothing the objective does not resolve the difficulty. The obstruction, however, has an exploitable symmetry: the Cauchy kernel is an odd function of the displacement from the moving pole, so pairing each observation with its reflection through the pole cancels the divergent part. This one cancellation simultaneously controls the population curvature, the gradient-estimator variance, and the bias incurred when the noise density is estimated. Combining these bounds with a closed-form single-transition gradient oracle, we prove that projected mini-batch policy gradient, initialized in any compact subset of the stabilizing region, attains total sample complexity

\tilde{O}(1/η)

when the noise density is known and

\tilde{O}(η^{-(2s+1)/(2s)})

when it must be estimated, for

C^s

noise densities with

s \geq 2

Qiuhua Pan, Yukai Shen, Liwei Zhang +2

State Key Laboratory of Submarine Geoscience, School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China · Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai 200240, China · Shanghai Key Laboratory of Perception and Control in Industrial Network Systems, Shanghai 200240, China +1

Stochastic Linear Dynamical Systems Stochastic Optimal Control Policy Gradient Methods Optimal Control Sample-Efficient RL

Ask PDF

May 6, 2025

Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits

Policy gradient (PG) methods have played an essential role in the empirical successes of reinforcement learning. In order to handle large state-action spaces, PG methods are typically used with function approximation. In this setting, the approximation error in modeling problem-dependent quantities is a key notion for characterizing the global convergence of PG methods. We study Softmax PG with linear function approximation (referred to as

\texttt{Lin-SPG}

) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even in the bandit setting. Consequently, we rethink the effect of approximation error in the standard stochastic multi-armed bandit problem. We first identify the conditions on the policy feature representation that can guarantee the asymptotic global convergence of

\texttt{Lin-SPG}

. Under these feature conditions, we further prove that

T

iterations of

\texttt{Lin-SPG}

with a problem-specific learning rate result in an

O(1/T)

convergence to the optimal policy. Moreover, we prove that

\texttt{Lin-SPG}

with an arbitrary constant learning rate can ensure asymptotic convergence to the optimal policy.

Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6

Simon Fraser University · Google DeepMind · Google Research +1

Multi-Armed Bandits Policy Gradient Policy Gradient Methods Stochastic Optimization Convergence Policy Learning Linear Function Approximation

Ask PDF

Mar 27, 2026

A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

We adapt the analysis of policy gradient for continuous time

k

-armed stochastic bandits by Lattimore (2026) to the standard discrete time setup. As in continuous time, we prove that with learning rate

η= O(Δ_{\min}^2/(Δ_{\max} \log(n)))

the regret is

O(k \log(k) \log(n) / η)

where

n

is the horizon and

Δ_{\min}

and

Δ_{\max}

are the minimum and maximum gaps.

Tor Lattimore

Google DeepMind

Multi-Armed Bandits Policy Gradient Policy Gradient Methods

Ask PDF