How Log-Barrier Helps Exploration in Policy Optimization

This paper introduces Log-Barrier Stochastic Gradient Bandit (LB-SGB), a new algorithm designed to fix structural flaws in standard policy optimization methods. While traditional gradient bandits often prematurely converge to suboptimal actions because they lack an explicit exploration mechanism, the authors use log-barrier regularization to force the policy away from the boundary of the probability simplex. This approach ensures that the probability of selecting any action, specifically the optimal one, never vanishes during the learning process. The researchers prove that this method matches state-of-the-art sample complexity while providing more robust global convergence guarantees without relying on unrealistic assumptions. Additionally, the study identifies a significant theoretical link between log-barrier regularization and Natural Policy Gradient methods through the geometry of Fisher information. Empirical simulations confirm that LB-SGB outperforms standard entropy-regularized and vanilla gradient methods, especially as the number of available actions increases.