Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features

• URL: http://arxiv.org/abs/2409.12135v2
• Date: Tue, 15 Oct 2024 18:50:02 GMT
• Title: Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features
• Abstract summary: This work is the first to establish the almost sure convergence of linear TD without requiring linearly independent features. Key to our analysis is a novel characterization of bounded invariant sets of the mean ODE of linear TD.
• Score: 18.326126953667842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Temporal difference (TD) learning with linear function approximation, abbreviated as linear TD, is a classic and powerful prediction algorithm in reinforcement learning. While it is well understood that linear TD converges almost surely to a unique point, this convergence traditionally requires the assumption that the features used by the approximator are linearly independent. However, this linear independence assumption does not hold in many practical scenarios. This work is the first to establish the almost sure convergence of linear TD without requiring linearly independent features. In fact, we do not make any assumptions on the features. We prove that the approximated value function converges to a unique point and the weight iterates converge to a set. We also establish a notion of local stability of the weight iterates. Importantly, we do not need to introduce any other additional assumptions and do not need to make any modification to the linear TD algorithm. Key to our analysis is a novel characterization of bounded invariant sets of the mean ODE of linear TD.

Related papers

• Nonlinear Axiomatic Attribution for Cooperative Games [72.04288767658888]
  We introduce a class of nonlinear attribution methods that retain the remaining necessary axioms.<n>Our experiments demonstrate the potential effectiveness of these methods compared to Shapley value variants.
  arXiv  Detail & Related papers  (2026-07-10T18:02:24Z)
• Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples [0.8594140167290097]
  We study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA)<n>We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k.
  arXiv  Detail & Related papers  (2026-06-04T10:10:29Z)
• Unsupervised Ground Metric Learning [1.2499537119440245]
  We consider both the algorithmic and the modeling part of unsupervised metric learning.<n>In particular, we propose to use the random function algorithm and prove that it converges linearly for our setting.<n>We show how Mahalanobis-like distances fit into our considerations.
  arXiv  Detail & Related papers  (2025-07-17T13:06:24Z)
• A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections nor Strong Convexity [11.117572650083698]
  We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation.<n>We show that the simple projection-free variant converges with a rate of $tildemath||theta*||2sqrtT$, even in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2025-06-01T15:39:00Z)
• Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features [33.19711311247482]
  This paper establishes the first $L2$ convergence rates for linear TD($lambda$) operating under arbitrary features.<n>To address the potential non-uniqueness of solutions resulting from arbitrary features, we develop a novel approximation result featuring convergence rates to the solution set instead of a single point.
  arXiv  Detail & Related papers  (2025-05-27T16:17:49Z)
• Conditional independence testing with a single realization of a multivariate nonstationary nonlinear time series [26.18999528465474]
  We introduce the first framework for conditional independence testing that works with a single realization of a nonstationary nonlinear process.<n>Key technical ingredients of our framework are time-varying nonlinear regression, estimation of local long-run covariance of products of error processes, and a distribution-uniform strong Gaussian approximation.
  arXiv  Detail & Related papers  (2025-04-30T13:51:38Z)
• TD(0) Learning converges for Polynomial mixing and non-linear functions [49.1574468325115]
  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.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning [6.827423171182153]
  We focus on linear value function approximation and offer a new perspective. We show that increasing the number of updates under the same target value function essentially represents a transition from using a constant preconditioner to data-feature adaptive preconditioner. This unifying perspective also simplifies the analyses of the convergence conditions for these algorithms.
  arXiv  Detail & Related papers  (2025-01-03T12:03:21Z)
• Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates [34.81849268839475]
  We study the problem of efficiently computing the derivative of the fixed-point of a parametric nondifferentiable contraction map. We analyze two popular approaches: iterative differentiation (ITD) and approximate implicit differentiation (AID) We establish rates for the convergence of NSID, encompassing the best available rates in the smooth setting.
  arXiv  Detail & Related papers  (2024-03-18T11:37:53Z)
• Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximation [26.97172212786727]
  We investigate the potential for finite-time decoupled convergence in nonlinear two-time-scale approximations. Under a nested local linearity assumption, finite-time decoupled convergence rates can be achieved with suitable step size selection.
  arXiv  Detail & Related papers  (2024-01-08T13:44:35Z)
• 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)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• How catastrophic can catastrophic forgetting be in linear regression? [30.702863017223457]
  We analyze how much the model forgets the true labels of earlier tasks after training on subsequent tasks. We establish connections between continual learning in the linear setting and two other research areas: alternating projections and the Kaczmarz method.
  arXiv  Detail & Related papers  (2022-05-19T14:28:40Z)
• Exploring Linear Feature Disentanglement For Neural Networks [63.20827189693117]
  Non-linear activation functions, e.g., Sigmoid, ReLU, and Tanh, have achieved great success in neural networks (NNs) Due to the complex non-linear characteristic of samples, the objective of those activation functions is to project samples from their original feature space to a linear separable feature space. This phenomenon ignites our interest in exploring whether all features need to be transformed by all non-linear functions in current typical NNs.
  arXiv  Detail & Related papers  (2022-03-22T13:09:17Z)
• Regularized Q-learning [6.663174194579773]
  This paper develops a new Q-learning algorithm that converges when linear function approximation is used. We experimentally show that it converges in environments where Q-learning with linear function approximation has known to diverge.
  arXiv  Detail & Related papers  (2022-02-11T01:29:50Z)
• Learning the Koopman Eigendecomposition: A Diffeomorphic Approach [7.309026600178573]
  We present a novel data-driven approach for learning linear representations of a class of stable nonlinear systems using Koopman eigenfunctions. To our best knowledge, this is the first work to close the gap between the operator, system and learning theories.
  arXiv  Detail & Related papers  (2021-10-15T00:47:21Z)
• Robust Online Control with Model Misspecification [96.23493624553998]
  We study online control of an unknown nonlinear dynamical system with model misspecification. Our study focuses on robustness, which measures how much deviation from the assumed linear approximation can be tolerated.
  arXiv  Detail & Related papers  (2021-07-16T07:04:35Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.