Research map / Optimization / Nonconvex and smooth optimization
Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the stochastic gradient bandit (softmax policy gradient with IS estimator) converges almost surely to the globally optimal arm under any constant learning rate, via sample-count and progress/noise analysis.
Problem
Convergence of stochastic gradient bandit algorithms with large constant learning rates, where smoothness and noise-control assumptions break down and exploration must be balanced automatically.
Approach
Proves that with any constant learning rate, softmax stochastic gradient bandit never samples a single arm forever and, via sample-count asymptotics and a cumulative progress-versus-noise decomposition, converges almost surely to the optimal arm; the result holds without smoothness or decaying step-size assumptions.
Key results
- Proves almost-sure convergence of pi_{theta_t}(a*) to 1 for any constant eta in Theta(1), for K=2 and general K >= 2 under no-ties assumption.
- Shows O(ln(T)/T) averaged suboptimality rate after a finite burn-in time.
- Simulations with learning rates 1, 10, 100, 1000 (far above the prior threshold ~7e-5) converge in 10^6 steps for most seeds, though some runs get stuck near suboptimal corners for long periods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use any constant learning rate η > 0 | Stochastic gradient bandit · Stochastic multi-armed bandits with no tied mean rewards | almost-sure convergence to the optimal policy | Helped |
| Use the softmax gradient bandit update with any constant learning rate | Stochastic gradient bandit · Stochastic multi-armed bandits | number of actions sampled infinitely often | Helped |
| Use η = 1 or 10 instead of larger learning rates | Gradient bandit · 4-action Gaussian bandit, early convergence | time to enter the final convergence stage | Helped |
| Increase the constant learning rate to η = 100 or 1000 | Gradient bandit · 4-action Gaussian bandit, final convergence stage | log sub-optimality: e^{-14} (η = 1), to e^{-20} (η = 100), and e^{-200} (η = 1000) | Helped |
| Increase the constant learning rate to η = 100 or 1000 | Gradient bandit · 4-action Gaussian bandit, within 10^6 iterations | runs remaining far from zero sub-optimality: 1/10 runs (η = 100) and 3/10 runs (η = 1000) | Hurt |
| Increase the constant learning rate | Gradient bandit · 4-action Gaussian bandit | overall convergence across stages | Mixed |
Surprising findings
- Learning rates as large as 1000 still converge almost surely, far above the previously required threshold (~0.00007).
- Larger learning rates yield faster final-stage convergence but can cause longer plateaus near suboptimal corners.
Limitations
- Assumes no ties in true mean rewards; removing this assumption is left open.
- Analysis restricted to multi-armed bandits and does not directly extend to general RL or function approximation.
- Does not characterize how the learning rate affects convergence speed or stages.
Experimental setup
Datasets: synthetic Gaussian bandit (K=4, means (0.2, 0.05, -0.1, -0.4), std 0.1)
Benchmarks: simulated 4-arm Gaussian bandit 2-arm bandit (appendix)
Metrics: log suboptimality gap r(a*) - pi^T r sampling behavior over iterations
Baselines: Softmax PG with small learning rate (Mei et al.) Natural PG Normalized PG
Builds on: REINFORCE Softmax policy gradient global convergence Mei et al. stochastic policy gradient analysis
Closest papers by meaning
- Stochastic Gradient Succeeds for Bandits (ICML 2023 · similarity 0.98)
- REINFORCE Converges to Optimal Policies with Any Learning Rate (NeurIPS 2025 · similarity 0.92)
- Does Stochastic Gradient really succeed for bandits? (NeurIPS 2025 · similarity 0.92)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.89)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.