A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning

• URL: http://arxiv.org/abs/2501.01774v2
• Date: Thu, 13 Feb 2025 03:29:50 GMT
• Title: A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning
• Abstract summary: We focus on linear value function approximation and offer a new perspective.<n>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.<n>This unifying perspective also simplifies the analyses of the convergence conditions for these algorithms.
• Score: 6.827423171182153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Traditionally, TD and FQI are viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number, such as the use of a target network in Deep Q-Networks (DQN) in the OPE setting. This perspective, however, fails to capture the convergence connections between these algorithms and may lead to incorrect conclusions, for example, that the convergence of TD implies the convergence of FQI. In this paper, we focus on linear value function approximation and offer a new perspective, unifying TD, FQI, and PFQI as the same iterative method for solving the Least Squares Temporal Difference (LSTD) system, but using different preconditioners and matrix splitting schemes. TD uses a constant preconditioner, FQI employs a data-feature adaptive preconditioner, and PFQI transitions between the two. Then, we reveal that in the context of linear function approximation, 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 and clarifies many issues. Consequently, we fully characterize the convergence of each algorithm without assuming specific properties of the chosen features (e.g., linear independence). We also examine how common assumptions about feature representations affect convergence, and discover new conditions on features that are important for convergence. These convergence conditions allow us to establish the convergence connections between these algorithms and to address important questions.

Related papers

• Periodic Regularized Q-Learning [9.333190920811626]
  We propose a new algorithm, periodic regularized Q-learning (PRQ)<n>We provide a rigorous theoretical analysis that proves finite-time convergence guarantees for PRQ under linear function approximation.
  arXiv  Detail & Related papers  (2026-02-03T09:28:06Z)
• iFSQ: Improving FSQ for Image Generation with 1 Line of Code [40.61338660155903]
  We show how to replace the activation function in FSQ with a distribution-matching mapping to enforce a uniform prior.<n>This simple strategy requires just one line of code yet mathematically guarantees both optimal bin utilization and reconstruction precision.<n>We extend our analysis by adapting Representation Alignment (REPA) to AR models, yielding LlamaGen-REPA.
  arXiv  Detail & Related papers  (2026-01-23T19:00:35Z)
• Provable In-Context Learning of Nonlinear Regression with Transformers [66.99048542127768]
  In-context learning (ICL) is the ability to perform unseen tasks using task specific prompts without updating parameters.<n>Recent research has actively explored the training dynamics behind ICL, with much of the focus on relatively simple tasks.<n>This paper investigates more complex nonlinear regression tasks, aiming to uncover how transformers acquire in-context learning capabilities.
  arXiv  Detail & Related papers  (2025-07-28T00:09:28Z)
• A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity [11.513419525702924]
  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 $widetildemathcalO(frac||theta)$, even in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2025-06-01T15:39:00Z)
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [56.805574957824135]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• 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)
• Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation [47.08004958269403]
  We prove a weaker convergence condition for bootstrapped value estimation in certain cases, even with off-policy data. We extend our results to learning with truncated trajectories, showing that convergence is achievable for all tasks with minor modifications.
  arXiv  Detail & Related papers  (2024-05-31T17:36:16Z)
• Implicit Bias and Fast Convergence Rates for Self-attention [26.766649949420746]
  We study the fundamental optimization principles of self-attention, the defining mechanism of transformers. We analyze the implicit bias of gradient-baseds in a self-attention layer with a decoder in a linear classification.
  arXiv  Detail & Related papers  (2024-02-08T15:15:09Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  We develop a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems. Second, we propose a variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average iterate.
  arXiv  Detail & Related papers  (2022-09-29T14:44:40Z)
• Contrastive Conditional Neural Processes [45.70735205041254]
  Conditional Neural Processes(CNPs) bridge neural networks with probabilistic inference to approximate functions of Processes under meta-learning settings. Two auxiliary contrastive branches are set up hierarchically, namely in-instantiation temporal contrastive learning(tt TCL) and cross-instantiation function contrastive learning(tt FCL) We empirically show that tt TCL captures high-level abstraction of observations, whereas tt FCL helps identify underlying functions, which in turn provides more efficient representations.
  arXiv  Detail & Related papers  (2022-03-08T10:08:45Z)
• Distributed gradient-based optimization in the presence of dependent aperiodic communication [4.34720256795424]
  Iterative distributed optimization algorithms involve multiple agents that communicate with each other, over time, in order to minimize/maximize a global objective. In the presence of unreliable communication networks, the Age-of-Information (AoI), which measures the freshness of data received, may be large and hence hinder algorithmic convergence. We show that convergence is guaranteed provided the random variables associated with the AoI processes areally dominated by a random variable with finite first moment.
  arXiv  Detail & Related papers  (2022-01-27T06:44:04Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria.
  arXiv  Detail & Related papers  (2021-05-27T06:10:24Z)
• The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
  We introduce a new convergence indicator that can be used to calculate whether the particles will finally converge to a single point or diverge. Using this convergence indicator we provide the actual bounds completely characterizing parameter regions that lead to a converging swarm.
  arXiv  Detail & Related papers  (2020-06-06T19:08:05Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)

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.