High-probability sample complexities for policy evaluation with linear function approximation

• URL: http://arxiv.org/abs/2305.19001v2
• Date: Thu, 2 May 2024 07:49:00 GMT
• Title: High-probability sample complexities for policy evaluation with linear function approximation
• Authors: Gen Li, Weichen Wu, Yuejie Chi, Cong Ma, Alessandro Rinaldo, Yuting Wei,
• Abstract summary: We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms. We establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level.
• Score: 88.87036653258977
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the off-policy setting, where samples are drawn from a behavior policy potentially different from the target policy, we establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level. We also exhihit an explicit dependence on problem-related quantities, and show in the on-policy setting that our upper bound matches the minimax lower bound on crucial problem parameters, including the choice of the feature maps and the problem dimension.

Related papers

• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
  We develop a deterministic policy gradient primal-dual method to find an optimal deterministic policy with non-asymptotic convergence. We prove that the primal-dual iterates of D-PGPD converge at a sub-linear rate to an optimal regularized primal-dual pair. To the best of our knowledge, this appears to be the first work that proposes a deterministic policy search method for continuous-space constrained MDPs.
  arXiv  Detail & Related papers  (2024-08-19T14:11:04Z)
• Full error analysis of policy gradient learning algorithms for exploratory linear quadratic mean-field control problem in continuous time with common noise [0.0]
  We study policy gradient (PG) learning and first demonstrate convergence in a model-based setting. We prove the global linear convergence and sample complexity of the PG algorithm with two-point gradient estimates in a model-free setting. In this setting, the parameterized optimal policies are learned from samples of the states and population distribution.
  arXiv  Detail & Related papers  (2024-08-05T14:11:51Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  We study the problem of computing an optimal policy of an infinite-horizon discounted Markov decision process (constrained MDP) We develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.
  arXiv  Detail & Related papers  (2023-06-20T17:27:31Z)
• Provable Offline Preference-Based Reinforcement Learning [95.00042541409901]
  We investigate the problem of offline Preference-based Reinforcement Learning (PbRL) with human feedback. We consider the general reward setting where the reward can be defined over the whole trajectory. We introduce a new single-policy concentrability coefficient, which can be upper bounded by the per-trajectory concentrability.
  arXiv  Detail & Related papers  (2023-05-24T07:11:26Z)
• Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization [18.072051868187934]
  We analyze the convergence rate of the unregularized natural policy algorithm with log-linear policy parametrizations. We show that the algorithm enjoys the same linear guarantees as in the deterministic case up to an error term.
  arXiv  Detail & Related papers  (2022-09-30T11:17:44Z)
• Sample Complexity of Policy-Based Methods under Off-Policy Sampling and Linear Function Approximation [8.465228064780748]
  off-policy sampling and linear function approximation are employed for policy evaluation. Various policy update rules, including natural policy gradient (NPG), are considered for policy update. We establish for the first time an overall $mathcalO(epsilon-2)$ sample complexity for finding an optimal policy.
  arXiv  Detail & Related papers  (2022-08-05T15:59:05Z)
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs [21.347689976296834]
  We employ the natural policy gradient method to solve the discounted optimal optimal rate problem. We also provide convergence and finite-sample guarantees for two sample-based NPG-PD algorithms.
  arXiv  Detail & Related papers  (2022-06-06T04:28:04Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  We consider off-policy policy evaluation with function approximation in average-reward MDPs. bootstrapping is necessary and, along with off-policy learning and FA, results in the deadly triad. We propose two novel algorithms, reproducing the celebrated success of Gradient TD algorithms in the average-reward setting.
  arXiv  Detail & Related papers  (2021-01-08T00:43:04Z)
• 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.