Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation

• URL: http://arxiv.org/abs/2405.21043v2
• Date: Fri, 04 Oct 2024 18:04:33 GMT
• Title: Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation
• Authors: Fengdi Che, Chenjun Xiao, Jincheng Mei, Bo Dai, Ramki Gummadi, Oscar A Ramirez, Christopher K Harris, A. Rupam Mahmood, Dale Schuurmans,
• Abstract summary: 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.
• Score: 47.08004958269403
• License:
• Abstract: We prove that the combination of a target network and over-parameterized linear function approximation establishes a weaker convergence condition for bootstrapped value estimation in certain cases, even with off-policy data. Our condition is naturally satisfied for expected updates over the entire state-action space or learning with a batch of complete trajectories from episodic Markov decision processes. Notably, using only a target network or an over-parameterized model does not provide such a convergence guarantee. Additionally, we extend our results to learning with truncated trajectories, showing that convergence is achievable for all tasks with minor modifications, akin to value truncation for the final states in trajectories. Our primary result focuses on temporal difference estimation for prediction, providing high-probability value estimation error bounds and empirical analysis on Baird's counterexample and a Four-room task. Furthermore, we explore the control setting, demonstrating that similar convergence conditions apply to Q-learning.

Related papers

• 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)
• Model Free Prediction with Uncertainty Assessment [7.524024486998338]
  We propose a novel framework that transforms the deep estimation paradigm into a platform conducive to conditional mean estimation. We develop an end-to-end convergence rate for the conditional diffusion model and establish the normality of the generated samples. Through numerical experiments, we empirically validate the efficacy of our proposed methodology.
  arXiv  Detail & Related papers  (2024-05-21T11:19:50Z)
• Absolute convergence and error thresholds in non-active adaptive sampling [0.27624021966289597]
  Non-active adaptive sampling is a way of building machine learning models from a training data base. Proposal for calculating absolute convergence and error thresholds is described. Tests meet our expectations and illustrate the proposal in the domain of natural language processing.
  arXiv  Detail & Related papers  (2024-02-04T15:10:34Z)
• Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Framework [8.572441599469597]
  We study high-confidence off-policy evaluation in the context of infinite-horizon Markov decision processes. The objective is to establish a confidence interval (CI) for the target policy value using only offline data pre-collected from unknown behavior policies. We show that our algorithm is sample-efficient, error-robust, and provably convergent even in non-linear function approximation settings.
  arXiv  Detail & Related papers  (2023-09-23T06:35:44Z)
• Approximate Conditional Coverage via Neural Model Approximations [0.030458514384586396]
  We analyze a data-driven procedure for obtaining empirically reliable approximate conditional coverage. We demonstrate the potential for substantial (and otherwise unknowable) under-coverage with split-conformal alternatives with marginal coverage guarantees.
  arXiv  Detail & Related papers  (2022-05-28T02:59:05Z)
• Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization [52.7137956951533]
  We argue that devising simpler methods for learning predictors on existing features is a promising direction for future research. We introduce Domain-Adjusted Regression (DARE), a convex objective for learning a linear predictor that is provably robust under a new model of distribution shift. Under a natural model, we prove that the DARE solution is the minimax-optimal predictor for a constrained set of test distributions.
  arXiv  Detail & Related papers  (2022-02-14T16:42:16Z)
• Robust Learning via Persistency of Excitation [4.674053902991301]
  We show that network training using gradient descent is equivalent to a dynamical system parameter estimation problem. We provide an efficient technique for estimating the corresponding Lipschitz constant using extreme value theory. Our approach also universally increases the adversarial accuracy by 0.1% to 0.3% points in various state-of-the-art adversarially trained models.
  arXiv  Detail & Related papers  (2021-06-03T18:49:05Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient.
  arXiv  Detail & Related papers  (2020-11-08T16:48:02Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)
• Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning [70.01650994156797]
  Off- evaluation of sequential decision policies from observational data is necessary in batch reinforcement learning such as education healthcare. We develop an approach that estimates the bounds of a given policy. We prove convergence to the sharp bounds as we collect more confounded data.
  arXiv  Detail & Related papers  (2020-02-11T16:18:14Z)

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.