TL;DR
Standard policy gradient methods often fail because they "forget" to explore, causing the probability of the optimal action to vanish before it can be identified. This paper introduces Log-Barrier Stochastic Gradient Bandit (LB-SGB), which adds a logarithmic penalty to the objective function to structurally prevent action probabilities from hitting zero. The authors prove that this simple fix guarantees global convergence even in worst-case scenarios where traditional methods collapse, and they reveal a deep mathematical link between log-barrier regularization and Natural Policy Gradients.
What Problem Does This Paper Address?
In the world of Reinforcement Learning, the Stochastic Gradient Bandit (SGB) algorithm—a simplified version of the famous REINFORCE algorithm—is a foundational tool. Recent theory suggested SGB converges quickly to an optimal policy, but there was a catch: those proofs relied on the "hidden" assumption that the probability of choosing the best action never gets too small.
In practice, this assumption is often false. As a policy gradient algorithm learns, it pushes the policy toward the edges of the "probability simplex" (the space of all possible action distributions). If the algorithm prematurely commits to a sub-optimal action, the gradient for the optimal action effectively vanishes. Without an explicit mechanism to force exploration, the agent gets stuck. While practitioners often use entropy regularization to encourage diversity, recent research suggests entropy doesn't provide enough "push" to prevent the policy from collapsing near the boundaries in difficult problems.
Methods
The authors propose a new objective function that regularizes the standard expected reward with a log-barrier function: $$\Phi_\eta(\theta) := J(\theta) + \frac{1}{\eta} \sum_{a \in [K]} \log \pi_\theta(a)$$ Here, $\eta$ is a barrier parameter. As any action probability $\pi_\theta(a)$ approaches zero, the $\log$ term approaches negative infinity, creating a "barrier" that the gradient ascent algorithm cannot cross.
This approach is inspired by Interior Point Methods from classical optimization. By keeping the policy strictly away from the boundary of the simplex, the algorithm ensures a minimum level of exploration is maintained throughout the entire learning process.
Datasets
As this is a theoretical paper focused on fundamental algorithm behavior, the authors evaluate their method using Stationary $K$-armed Gaussian Bandits.
- Scalability: They tested environments with up to $K=1000$ arms.
- Difficulty: They varied the "sub-optimality gap" ($\Delta^*$), testing scenarios where the best arm is only slightly better than the second-best, making exploration much harder.
- Baselines: They compared LB-SGB against vanilla SGB, SGB with Entropy Regularization (ENT), and Natural Policy Gradient (NPG).
Key Insights and Ideas
- The "Safety Net" of Log-Barriers: Unlike entropy, which encourages a broad distribution, the log-barrier specifically penalizes the vanishing of any single action. This provides a much stronger structural guarantee for exploration.
- The NPG Connection: One of the most elegant findings is that log-barrier regularization is mathematically equivalent to constraining the Fisher Information Matrix (FIM). Specifically, the authors show that the log-barrier objective is the same as maximizing reward while regularizing the log-determinant of the FIM.
- LB-SGB as "Stable NPG": Natural Policy Gradient (NPG) is known for being aggressive and sometimes converging prematurely to bad actions. LB-SGB can be viewed as a version of NPG that exploits the same underlying geometry but stays within the "safe" region where the Fisher geometry is non-degenerate.
- Removing Unrealistic Assumptions: The authors prove that while vanilla SGB needs the $c^* < \infty$ assumption (that the optimal action probability stays bounded away from zero) to guarantee convergence, LB-SGB converges regardless of the starting conditions or reward trajectories.
Key Results
- Matching State-of-the-Art: Under the standard (optimistic) assumptions, LB-SGB matches the optimal $O(\epsilon^{-1})$ sample complexity of vanilla SGB.
- Worst-Case Robustness: In the "worst-case" where no assumptions are made about the learning process, LB-SGB still converges with a sample complexity of $O(\epsilon^{-7})$. While slower, this is a significant theoretical milestone as it provides a global guarantee where others provide none.
- Empirical Superiority: In simulations with 1,000 arms, vanilla SGB and Entropy-regularized SGB frequently failed to find the optimal arm, plateauing at sub-optimal rewards. LB-SGB consistently found the optimal policy, demonstrating much better scalability to high-dimensional action spaces.
Limitations and Future Work
- Sample Complexity Gap: There is a large gap between the $O(\epsilon^{-1})$ and $O(\epsilon^{-7})$ bounds. The authors suspect their $O(\epsilon^{-7})$ analysis is conservative and that the true worst-case complexity might be tighter.
- Hyperparameter Sensitivity: The current proofs require choosing the barrier parameter $\eta$ and learning rate $\alpha$ based on the total time horizon $T$. This means the algorithm isn't "anytime"—you need to know how long you're running it for at the start.
- Extension to MDPs: This work focuses on the "bandit" setting (single-state RL). Extending these log-barrier guarantees to full Markov Decision Processes (MDPs) with deep neural networks is the next major frontier.
Summary updated