Research map / Optimization / Nonconvex and smooth optimization
Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, Karthikeyan Shanmugam
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a constant rather than diminishing stepsize | Contractive SA · Contractive SA | convergence behavior: exponentially fast ... to a ball with radius proportional to the stepsize | Mixed |
| Choose the smoothing norm and μ to yield logarithmic dimension dependence | V-trace finite-sample analysis · Off-policy policy evaluation | state-space dimension dependence: log |S| | Improved |
| Increase n when c̄<1/β | V-trace · Off-policy policy evaluation | contraction parameter | Improved |
| Choose c̄≥1/β | V-trace · Off-policy policy evaluation | noise bound A: 32ρ̄²n²; 32ρ̄²(βc̄)²ⁿ/(βc̄-1)² | Hurt |
| Increase ρ̄ | V-trace · Off-policy policy evaluation | noise bound A: ρ̄² | Hurt |
| Increase n | On-policy TD(n) · On-policy policy evaluation | initial convergence rate: (1-(1-βⁿ)ε)^k | Improved |
| Increase n | On-policy TD(n) · On-policy policy evaluation | asymptotic mean square error | Hurt |
| Use the proposed analysis instead of the cited prior constant-stepsize Q-learning bound | Q-learning · Synchronous Q-learning | state-action-space dimension dependence: (|S||A|)^2 -> log (|S||A|) | Improved |
Closest papers by meaning
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.91)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.87)
- Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization (ICML 2024 · similarity 0.86)
- Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence (AAAI 2025 · similarity 0.86)
- Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set (ICML 2025 · similarity 0.85)
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.85)
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.
