Research map / Bandits and online learning / RL theory and MDPs

REINFORCE Converges to Optimal Policies with Any Learning Rate

NeurIPS 2025 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that REINFORCE converges to globally optimal policies in finite-horizon MDPs with any constant learning rate, using a new exploration property and a stochastic bandit analysis extended to MDPs.

Problem

Classic REINFORCE stochastic policy gradient convergence to globally optimal policies usually requires small or decaying learning rates; the paper targets removing this requirement in finite-horizon MDPs.

Approach

Identifies a new exploration property in the stochastic bandit setting, which enables convergence with any constant learning rate; the analysis is then extended from bandits to finite-horizon MDPs.

Key results

• REINFORCE converges to globally optimal policies in finite-horizon MDPs with any constant learning rate.

Experimental setup

Builds on: REINFORCE

Closest papers by meaning

• Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates (NeurIPS 2024 · similarity 0.92)
• On the Convergence of Success Conditioning for Policy Optimization (NeurIPS 2026 · similarity 0.91)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients (ICML 2024 · similarity 0.90)
• Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.90)
• Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.89)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.89)