Analysis of Off-Policy $n$-Step TD-Learning with Linear Function Approximation

• URL: http://arxiv.org/abs/2502.08941v2
• Date: Fri, 14 Feb 2025 05:46:10 GMT
• Title: Analysis of Off-Policy $n$-Step TD-Learning with Linear Function Approximation
• Authors: Han-Dong Lim, Donghwan Lee,
• Abstract summary: This paper analyzes multi-step temporal difference (TD)-learning algorithms within the deadly triad'' scenario. In particular, we prove that $n$-step TD-learning algorithms converge to a solution as the sampling horizon $n$ increases sufficiently. Two $n$-step TD-learning algorithms are proposed and analyzed, which can be seen as the model-free reinforcement learning counterparts of the model-based deterministic algorithms.
• Score: 6.663174194579773
• License:
• Abstract: This paper analyzes multi-step temporal difference (TD)-learning algorithms within the ``deadly triad'' scenario, characterized by linear function approximation, off-policy learning, and bootstrapping. In particular, we prove that $n$-step TD-learning algorithms converge to a solution as the sampling horizon $n$ increases sufficiently. The paper is divided into two parts. In the first part, we comprehensively examine the fundamental properties of their model-based deterministic counterparts, including projected value iteration, gradient descent algorithms, which can be viewed as prototype deterministic algorithms whose analysis plays a pivotal role in understanding and developing their model-free reinforcement learning counterparts. In particular, we prove that these algorithms converge to meaningful solutions when $n$ is sufficiently large. Based on these findings, in the second part, two $n$-step TD-learning algorithms are proposed and analyzed, which can be seen as the model-free reinforcement learning counterparts of the model-based deterministic algorithms.

Related papers

• Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation [5.152147416671501]
  This paper analyzes multi-step TD-learning algorithms characterized by linear function approximation, off-policy learning, and bootstrapping. Two n-step TD-learning algorithms are proposed and analyzed, which can be seen as the model-free reinforcement learning counterparts of the gradient and control theoretic algorithms.
  arXiv  Detail & Related papers  (2024-02-24T10:42:50Z)
• Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging [18.843097436906618]
  We introduce a lightweight OGD algorithm that does not require the independence of examples and generalizes to kernel pairwise learning. Our algorithm builds the gradient based on a random example and a moving average representing the past data, which results in a sub-linear regret bound with a complexity of $O(T)$. Several experiments with real-world datasets show that the complexity technique outperforms kernel and linear gradient in offline and online scenarios.
  arXiv  Detail & Related papers  (2024-02-02T05:21:50Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms. Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
  arXiv  Detail & Related papers  (2023-08-17T08:34:58Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Algorithms to estimate Shapley value feature attributions [11.527421282223948]
  Feature attributions based on the Shapley value are popular for explaining machine learning models. We disentangle this complexity into two factors: (1)the approach to removing feature information, and (2)the tractable estimation strategy.
  arXiv  Detail & Related papers  (2022-07-15T17:04:41Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Learning-to-learn non-convex piecewise-Lipschitz functions [44.6133187924678]
  We analyze the meta-learning of the algorithms for piecewise-Lipschitz functions, a non-task with applications to both machine learning algorithms. We propose a practical meta-learning procedure that learns both the step-size of the algorithm from multiple online learning tasks.
  arXiv  Detail & Related papers  (2021-08-19T16:22:48Z)
• Finite-Sample Analysis of Proximal Gradient TD Algorithms [43.035055641190105]
  We analyze the convergence rate of the gradient temporal difference learning (GTD) family of algorithms. Two revised algorithms are also proposed, namely projected GTD2 and GTD2-MP. The results of our theoretical analysis show that the GTD family of algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.
  arXiv  Detail & Related papers  (2020-06-06T20:16:25Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  We develop a new theoretical framework to provide convergence guarantee for the general multi-step MAML algorithm. In particular, our results suggest that an inner-stage step needs to be chosen inversely proportional to $N$ of inner-stage steps in order for $N$ MAML to have guaranteed convergence.
  arXiv  Detail & Related papers  (2020-02-18T19:17:54Z)

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.