Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

Technical Summary: Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

Problem Statement
This paper investigates the theoretical properties of the policy gradient (PG) algorithm applied to the Multi-Armed Bandit (MAB) problem within a continuous-time diffusion environment. Unlike traditional discrete-time settings, the environment is modeled using a Stochastic Differential Equation (SDE) where the reward rate of each arm is subject to continuous noise (Brownian motion). The authors focus on the "weak signal regime," where noise dominates the signal incrementally, making learning particularly challenging. The study utilizes the continuous-time reinforcement learning framework established by Wang et al. (2020) and Jia and Zhou (2022b), specifically analyzing the actor-critic PG update where the policy is parameterized via the logit (softmax) function.

Methodology
The core methodological contribution is the construction of a novel Lyapunov function to analyze the stability and convergence of the underlying SDE governing the policy parameters.

1. SDE Formulation: The paper models the evolution of the logit parameters $\boldsymbol{\phi}_t$ as an SDE (Equation 2). This SDE represents the diffusion limit of the discrete-time policy gradient algorithm under high-frequency sampling.
2. Lyapunov Construction: The authors define a specific Lyapunov function $V_{\ell, \boldsymbol{\sigma}}(\boldsymbol{\phi})$ (Equation 15) involving a weighted sum of exponential terms of the logit differences between suboptimal and optimal arms. This function is designed to capture the stabilizing behavior of the process.
3. Analytical Tools: The analysis leverages Itô's calculus to compute the generator of the SDE applied to the Lyapunov function. By bounding the drift and diffusion terms, the authors derive inequalities that demonstrate the decay of the Lyapunov function, which corresponds to the convergence of the policy to the optimal arm.
4. Discrete-Time Extension: The same Lyapunov function is adapted to analyze the conventional discrete-time stochastic gradient algorithm, providing a unified proof framework for both continuous and discrete settings.

Key Results
The paper establishes two primary theoretical results regarding the convergence and regret of the policy gradient method:

1. Almost Sure Convergence (Arbitrary Learning Rate):

   • Theorem 2: The policy gradient update converges almost surely to the optimal arm (i.e., the probability of selecting the best arm approaches 1) for any arbitrary constant learning rate $\ell > 0$, provided the expected reward rates of the arms are distinct. This result holds without the restrictive learning rate conditions often required for regret bounds.

2. Non-Asymptotic Regret Bounds (Small Learning Rate):

   • Theorem 1 (Continuous Time): When the constant learning rate $\ell$ is below a specific time-invariant threshold determined by the gap between arm means and their volatilities, the algorithm achieves a non-asymptotic expected regret upper bound of order $O(\log T)$. The bound is instance-dependent and holds for any finite time horizon $T$.
   • Theorem 3 (Discrete Time): A similar $O(\log N)$ regret bound is derived for the discrete-time algorithm under a learning rate condition $\ell \leq O(1/d)$, where $d$ is the number of arms. This condition aligns with recent conjectures in the literature regarding the maximum stable learning rate.

Comparison with Existing Literature
The paper positions its results against recent works, notably Lattimore (2026a), who analyzed the same SDE using a different method.

• Relaxed Conditions: This paper relaxes the learning rate conditions found in Lattimore (2026a), which required $\ell \leq O(1/\log T)$ for certain results. In contrast, this work proves almost sure convergence for any constant $\ell$ and logarithmic regret for $\ell \leq O(1/d)$.
• Unified Proof: Unlike previous analyses that treated two-arm and multi-arm cases separately, this paper provides a unifying proof for the multi-arm case ($d \geq 2$).
• Transparency: The authors claim that using SDE tools and Lyapunov functions offers a transparent and rigorous way to analyze policy gradient dynamics, simplifying verification compared to discrete-time martingale arguments.

Significance and Claims
The authors claim that this work demonstrates the viability of "model-free" learning in diffusion environments, where the optimization principle (policy gradient) naturally handles the exploration-exploitation trade-off without explicit statistical adjustments (like Upper Confidence Bounds or Thompson Sampling).

• Theoretical Insight: The paper highlights that the same Lyapunov function effective for continuous-time SDEs is also powerful for discrete-time analysis, bridging the gap between the two frameworks.
• Limitations: The authors modestly note that while the regret bound is logarithmic, the order with respect to the number of arms $d$ is larger than typical optimal bounds for MABs. Furthermore, the "instance-free" regret bound (independent of the specific gap $\Delta$) remains an open problem. The convergence results for arbitrary learning rates apply to pathwise convergence but do not guarantee logarithmic expected regret for large $\ell$ due to potential lack of uniform integrability.

In summary, the paper provides a rigorous SDE-based analysis showing that policy gradient methods in diffusion environments can achieve optimal logarithmic regret and almost sure convergence, provided the learning rate is appropriately scaled, utilizing a novel Lyapunov function that unifies the analysis of continuous and discrete-time algorithms.