Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation

DOI10.1137/21M1468668MaRDI QIDQ5885838zbMATH OpenFDO

Authors Tianjiao Li, Guanghui Lan, Ashwin Pananjady

Publication date 30 March 2023

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.13109

zbMATH Keywords

accelerationMarkovian noisepolicy evaluationtemporal differencevariance reduction

Mathematics Subject Classification ID

Inference from stochastic processes and prediction (62M20) Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15) Abstract computational complexity for mathematical programming problems (90C60) Estimation and detection in stochastic control theory (93E10)

Recommendations

• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
• Least squares policy evaluation algorithms with linear function approximation
• Concentration bounds for temporal difference learning with linear function approximation: the case of batch data and uniform sampling
• Generalized TD learning
• Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning

Cites work

• A Convergent Incremental Gradient Method with a Constant Step Size
• A proximal stochastic gradient method with progressive variance reduction
• Acceleration of Stochastic Approximation by Averaging
• An analysis of temporal-difference learning with function approximation
• Asymptotics in statistics. Some basic concepts.
• scientific article; zbMATH DE number 5348356 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 3441440 (Why is no real title available?)
• scientific article; zbMATH DE number 3426635 (Why is no real title available?)
• Information-based complexity of linear operator equations
• Instance-Dependent ℓ_∞-Bounds for Policy Evaluation in Tabular Reinforcement Learning
• Introductory lectures on convex optimization. A basic course.
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Minimizing finite sums with the stochastic average gradient
• Mixing time estimation in reversible Markov chains from a single sample path
• On optimality of Krylov's information when solving linear operator equations
• On the Almost Sure Rate of Convergence of Linear Stochastic Approximation Algorithms
• Policy evaluation with temporal differences: a survey and comparison
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning

Cited in

(3)

• Multiscale Q-learning with linear function approximation
• Improved estimation of relaxation time in nonreversible Markov chains
• Accelerated and instance-optimal policy evaluation with linear function approximation

Describes a project that uses

Uses Software

• Saga

This page was built for publication: Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885838)