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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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

ReferenceSample ComplexityMethodAssumption on c∗†c^{*\dagger}
Mei et al. [15]O(ϵ−1)\mathcal{O}\left(\epsilon^{-1}\right)Vanilla PG ( SGB )✓
Mei et al. [24]O(ϵ−1)\mathcal{O}\left(\epsilon^{-1}\right)NPG with Baseline✓
This workO~(ϵ−1)\bm{\widetilde{\mathcal{O}}\left(\epsilon^{-1}\right)}Log-barrier ( LB-SGB )✓
Zhang et al. [35]O(ϵ−6)\mathcal{O}\left(\epsilon^{-6}\right)Log-barrier, Clipping✗
Yuan et al. [13]O(ϵ−6)\mathcal{O}\left(\epsilon^{-6}\right)Log-barrier✗
This workO(ϵ−5)\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∗≔sup⁡tE[πθt(a∗)−2]c^{*}\coloneqq\sup_{t}\mathbb{E}\left[\pi_{\bm{\theta}_{t}}(a^{*})^{-2}\right] .
Figure 1: Comparison between algorithms across K={10,100,1000}K=\{10,100,1000\} . The top row uses a learning rate α=0.01\alpha=0.01 , and the bottom row uses α=0.1\alpha=0.1 . All experiments use Δ∗=0.1\Delta^{*}=0.1 (100 runs ±\pm 95% C.I.).
Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

ReferenceSample ComplexityLearning Rate α\alphaMethodAssumptions
Mei et al. [15]O(ϵ−1)\mathcal{O}\left(\epsilon^{-1}\right)O(1)\mathcal{O}\left(1\right)Vanilla PG ( SGB )No ties, c∗<∞†c^{*}<\infty^{\dagger}
Lu et al. [36]O(ϵ−3)‡\mathcal{O}\left(\epsilon^{-3}\right)^{\ddagger}O(αt)\mathcal{O}\left(\alpha^{t}\right)Vanilla PGc∗<∞c^{*}<\infty
This workO~(ϵ−1)\bm{\widetilde{\mathcal{O}}\left(\epsilon^{-1}\right)}O(1)\bm{\mathcal{O}\left(1\right)}Log-barrierNo ties, c∗<∞\bm{c^{*}<\infty}
Ding et al. [37]O(ϵ−2)\mathcal{O}\left(\epsilon^{-2}\right)O(1/t)\mathcal{O}\left(1/t\right)Entropy regularizationinf⁡tmin⁡aπθ(a)>0\inf_{t}\min_{a}\pi_{\bm{\theta}}(a)>0
Cen et al. [38]O(ϵ−2)\mathcal{O}\left(\epsilon^{-2}\right)O(1/log⁡t)\mathcal{O}\left(1/\log t\right)Entropy regularized NPGGenerative model
Zhang et al. [35]O(ϵ−6)\mathcal{O}\left(\epsilon^{-6}\right)O(1/log⁡t)\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∗≔sup⁡tE[πθt(a∗)−2]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 O(ϵ−1)\mathcal{O}\left(\epsilon^{-1}\right) or O(ϵ−3)\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.
K\bm{K}α=0.01\bm{\alpha=0.01}α=0.1\bm{\alpha=0.1}
101010001000
10010020002000
10001000100001000050005000
Appendix
Table 3: Choice of the barrier parameter η\eta for LB-SGB and ENT across different action spaces KK and learning rates α\alpha .
Figure 2: Comparison between algorithms across K={10,100,1000}K=\{10,100,1000\} . The top row uses a learning rate α=0.01\alpha=0.01 , and the bottom row uses α=0.1\alpha=0.1 . All experiments use Δ∗=0.1\Delta^{*}=0.1 (100 runs ±\pm 95% C.I.). For presentation purposes, these experiments are the same as the ones presented in Figure 1 .
Figure 3: Comparison between LB-SGB , NPG with baseline, and LB-SGB with clipping, across different MAB instances with K={10,100,1000}K=\{10,100,1000\} . All experiments utilize Δ∗=0.1\Delta^{*}=0.1 , Rmax⁡=1R_{\max}=1 , and aggregate 100100 independent runs ( ±95%\pm 95\% C.I.).
Figure 4: Performance, minimum action probability and regret for SGB and LB-SGB with different choices for η\eta

Explore similar work

CardsList

  1. Sample Complexity of Policy Gradient for Log-Growth Control

    May 26, 2026Qiuhua Pan, Yukai Shen, Liwei Zhang +2Stochastic Linear Dynamical SystemsStochastic Optimal Control

    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

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

    May 6, 2025Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6Multi-Armed BanditsPolicy Gradient

    Simon Fraser University · Google DeepMind · Google Research +1

  3. A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

    Mar 27, 2026Tor LattimoreMulti-Armed BanditsPolicy Gradient

    Google DeepMind