TD(0) Learning converges for Polynomial mixing and non-linear functions

• URL: http://arxiv.org/abs/2502.05706v1
• Date: Sat, 08 Feb 2025 22:01:02 GMT
• Title: TD(0) Learning converges for Polynomial mixing and non-linear functions
• Authors: Anupama Sridhar, Alexander Johansen,
• Abstract summary: We present theoretical findings for TD learning under more applicable assumptions. This is the first proof of TD(0) convergence on Markov data under universal and-independent step sizes. Our results include bounds for linear models and non-linear under generalized gradients and H"older continuity.
• Score: 49.1574468325115
• License:
• Abstract: Theoretical work on Temporal Difference (TD) learning has provided finite-sample and high-probability guarantees for data generated from Markov chains. However, these bounds typically require linear function approximation, instance-dependent step sizes, algorithmic modifications, and restrictive mixing rates. We present theoretical findings for TD learning under more applicable assumptions, including instance-independent step sizes, full data utilization, and polynomial ergodicity, applicable to both linear and non-linear functions. \textbf{To our knowledge, this is the first proof of TD(0) convergence on Markov data under universal and instance-independent step sizes.} While each contribution is significant on its own, their combination allows these bounds to be effectively utilized in practical application settings. Our results include bounds for linear models and non-linear under generalized gradients and H\"older continuity.

Related papers

• 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. 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]
  We study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation. First, we derive a novel high-dimensional probability convergence guarantee that depends explicitly on the variance and holds under weak conditions. We further establish refined high-dimensional Berry-Esseen bounds over the class of convex sets that guarantee faster rates than those in the literature.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• 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)
• 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)
• 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)
• 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)

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.