Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation

• URL: http://arxiv.org/abs/2502.05706v2
• Date: Tue, 20 May 2025 23:53:42 GMT
• Title: Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation
• Authors: Anupama Sridhar, Alexander Johansen,
• Abstract summary: Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
• Score: 49.1574468325115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning, yet its finite-sample behavior under non-i.i.d. data and nonlinear approximation remains unknown. We provide the first high-probability, finite-sample analysis of vanilla TD(0) on polynomially mixing Markov data, assuming only Holder continuity and bounded generalized gradients. This breaks with previous work, which often requires subsampling, projections, or instance-dependent step-sizes. Concretely, for mixing exponent $\beta > 1$, Holder continuity exponent $\gamma$, and step-size decay rate $\eta \in (1/2, 1]$, we show that, with high probability, \[ \| \theta_t - \theta^* \| \leq C(\beta, \gamma, \eta)\, t^{-\beta/2} + C'(\gamma, \eta)\, t^{-\eta\gamma} \] after $t = \mathcal{O}(1/\varepsilon^2)$ iterations. These bounds match the known i.i.d. rates and hold even when initialization is nonstationary. Central to our proof is a novel discrete-time coupling that bypasses geometric ergodicity, yielding the first such guarantee for nonlinear TD(0) under realistic mixing.

Related papers

• Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes [43.68309224776421]
  We analyze the gap between the training and test errors when training a potentially over-parametrized model.<n>We have no dependence on either training time or reliance on mixing, nor a dependence on dimensionality, gradient norms, or any other properties of the loss or model.
  arXiv  Detail & Related papers  (2025-05-25T10:49:09Z)
• Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation [21.999445060856278]
  We show that the sample complexity of linear distributional TD learning matches that of the classic linear TD learning. Our findings provide new insights into the statistical efficiency of distributional reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2025-02-20T00:53:22Z)
• Adversarial Dependence Minimization [78.36795688238155]
  This work provides a differentiable and scalable algorithm for dependence minimization that goes beyond linear pairwise decorrelation.<n>We demonstrate its utility in three applications: extending PCA to nonlinear decorrelation, improving the generalization of image classification methods, and preventing dimensional collapse in self-supervised representation learning.
  arXiv  Detail & Related papers  (2025-02-05T14:43:40Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
  Temporal Difference (TD) learning, arguably the most widely used for policy evaluation, serves as a natural framework for this purpose. In this paper, we study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation, and obtain three significant improvements over existing results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  We study high-probability convergence in online learning, in the presence of heavy-tailed noise.<n>We provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments.
  arXiv  Detail & Related papers  (2024-10-17T18:25:28Z)
• The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize [22.917692982875025]
  We take a new perspective and examine the simultaneous presence of Markovian dependency of data and nonlinear update rules. We develop a fine-grained analysis of the correlation between the SA iterates $theta_k$ and Markovian data $x_k$. We present a precise characterization of the bias of the SA iterates, given by $mathbbE[theta_infty]-thetaast=alpha(b_textm+b_textn+b_textc)+
  arXiv  Detail & Related papers  (2024-05-27T00:23:42Z)
• Identifiable Feature Learning for Spatial Data with Nonlinear ICA [18.480534062833673]
  We introduce a new nonlinear ICA framework that employs latent components which apply naturally to data with higher-dimensional dependency structures. In particular, we develop a new learning and algorithm that extends variational methods to handle the combination of a deep neural network mixing function with the TP prior inducing computational efficacy.
  arXiv  Detail & Related papers  (2023-11-28T15:00:11Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  We show that wetailed high-prob convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. We demonstrate analytically and that $ta$ can be used to the preferred choice of setting for a given problem.
  arXiv  Detail & Related papers  (2023-10-28T18:53:41Z)
• Joint Distributional Learning via Cramer-Wold Distance [0.7614628596146602]
  We introduce the Cramer-Wold distance regularization, which can be computed in a closed-form, to facilitate joint distributional learning for high-dimensional datasets. We also introduce a two-step learning method to enable flexible prior modeling and improve the alignment between the aggregated posterior and the prior distribution.
  arXiv  Detail & Related papers  (2023-10-25T05:24:23Z)
• Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
  We propose an oracle-efficient algorithm, dubbed Pessimistic Least-Square Value Iteration (PNLSVI) for offline RL with non-linear function approximation. Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation.
  arXiv  Detail & Related papers  (2023-10-02T17:42:01Z)
• Efficient Interpretable Nonlinear Modeling for Multiple Time Series [5.448070998907116]
  This paper proposes an efficient nonlinear modeling approach for multiple time series. It incorporates nonlinear interactions among different time-series variables. Experimental results show that the proposed algorithm improves the identification of the support of the VAR coefficients in a parsimonious manner.
  arXiv  Detail & Related papers  (2023-09-29T11:42:59Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Learning Linear Causal Representations from Interventions under General Nonlinear Mixing [52.66151568785088]
  We prove strong identifiability results given unknown single-node interventions without access to the intervention targets. This is the first instance of causal identifiability from non-paired interventions for deep neural network embeddings.
  arXiv  Detail & Related papers  (2023-06-04T02:32:12Z)
• Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data [22.59079286063505]
  We study the statistical inference of nonlinear approximation algorithms utilizing a single trajectory of Markovian data. Our methodology has practical applications in various scenarios, such as Gradient Descent (SGD) on autoregressive data and asynchronous Q-Learning.
  arXiv  Detail & Related papers  (2023-02-15T14:31:11Z)
• Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
  offline reinforcement learning, which aims at optimizing decision-making strategies with historical data, has been extensively applied in real-life applications. We take a step by considering offline reinforcement learning with differentiable function class approximation (DFA) Most importantly, we show offline differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning algorithm.
  arXiv  Detail & Related papers  (2022-10-03T07:59:42Z)
• On Hypothesis Transfer Learning of Functional Linear Models [8.557392136621894]
  We study the transfer learning (TL) for the functional linear regression (FLR) under the Reproducing Kernel Space (RKHS) framework. We measure the similarity across tasks using RKHS distance, allowing the type of information being transferred tied to the properties of the imposed RKHS. Two algorithms are proposed: one conducts the transfer when positive sources are known, while the other leverages aggregation to achieve robust transfer without prior information about the sources.
  arXiv  Detail & Related papers  (2022-06-09T04:50:16Z)
• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  We show a new high probability generalization bound of order $O(frac1n + fracL2n2sum_t=1T(gamma_t/varepsilon_t)2)$ for gradient Langevin Dynamics (GLD) We can also obtain new bounds for certain variants of SGD.
  arXiv  Detail & Related papers  (2022-05-27T07:23:01Z)
• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
  The paper concerns the $d$-dimensional recursion approximation, $$theta_n+1= theta_n + alpha_n + 1 f(theta_n, Phi_n+1) The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3) An example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometrical
  arXiv  Detail & Related papers  (2021-10-27T13:38:25Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

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.