Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise

• URL: http://arxiv.org/abs/2409.19546v4
• Date: Mon, 03 Feb 2025 22:14:27 GMT
• Title: Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
• Authors: Ethan Blaser, Shangtong Zhang,
• Abstract summary: This work investigates approximations with merely nonexpansive operators. In particular, we study nonexpansive approximations with Markovian noise. As an application, we prove, for the first time, that the classical average reward temporal difference learning converges to a sample path dependent fixed point.
• Score: 20.474661995490365
• License:
• Abstract: Stochastic approximation is an important class of algorithms, and a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are a few novel bounds of noise terms resulting from the Poisson equation. As an application, we prove, for the first time, that the classical tabular average reward temporal difference learning converges to a sample path dependent fixed point.

Related papers

• Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise [31.241889735283166]
  We provide the first almost sure convergence rate for $Q$-learning with Markovian samples without count-based learning rates. We also provide the first concentration bound for off-policy temporal difference learning with Markovian samples.
  arXiv  Detail & Related papers  (2024-11-20T21:09:09Z)
• Finite Sample and Large Deviations Analysis of Stochastic Gradient Algorithm with Correlated Noise [15.724207170366846]
  We analyze the finite sample regret of a decreasing step size gradient algorithm. We assume correlated noise and use a perturbed Lyapunov function as a systematic approach for the analysis.
  arXiv  Detail & Related papers  (2024-10-11T01:38:27Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
  We develop a framework for non-asymptotic analysis of deterministic samplers used for diffusion generative modeling. We show that one step along the probability flow ODE can be expressed as two steps: 1) a restoration step that runs ascent on the conditional log-likelihood at some infinitesimally previous time, and 2) a degradation step that runs the forward process using noise pointing back towards the current gradient.
  arXiv  Detail & Related papers  (2023-03-06T18:59:19Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
  This paper proposes a thorough theoretical analysis of convex Gradient Descent (SGD) with non-increasing step sizes. First, we show that the SGD can be provably approximated by solutions of inhomogeneous Differential Equation (SDE) using coupling. Recent analyses of deterministic and optimization methods by their continuous counterpart, we study the long-time behavior of the continuous processes at hand and non-asymptotic bounds.
  arXiv  Detail & Related papers  (2020-04-08T18:31:34Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  We present for the first time an convergence analysis of two time-scale approximation driven by "controlled" Markov noise. We analyze the behavior of our framework by relating it to limiting differential inclusions in both time scales. We obtain the first informative error bounds on function approximation for the policy evaluation algorithm.
  arXiv  Detail & Related papers  (2020-04-08T03:59:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  We address the problem of policy evaluation in discounted decision processes, and provide Markov-dependent guarantees on the $ell_infty$error under a generative model. We establish both and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms.
  arXiv  Detail & Related papers  (2020-03-16T17:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.