Text

Simple and Optimal Methods for Stochastic Variational Inequalities, II : Markovian Noise and Policy Evaluation in Reinforcement Learning

The focus of this paper is on stochastic variational inequalities (VI) under Markovian noise. A prominent application of our algorithmic developments is the stochastic policy evaluation problem in reinforcement learning. Prior investigations in the literature focused on temporal difference (TD) learning by employing nonsmooth finite time analysis motivated by stochastic subgradient descent leading to certain limitations. These limitations encompass the requirement of analyzing a modified TD algorithm that involves projection to an a priori defined Euclidean ball, achieving a nonoptimal convergence rate and no clear way of deriving the beneficial effects of parallel implementation. Our approach remedies these shortcomings in the broader context of stochastic VIs and in particular when it comes to stochastic policy evaluation. We developed a variety of simple TD learning type algorithms motivated by its original version that maintain its simplicity, while offering distinct advantages from a nonasymptotic analysis point of view. We first provide an improved analysis of the standard TD algorithm that can benefit from parallel implementation. Then we present versions of a conditional TD algorithm (CTD), that involves periodic updates of the stochastic iterates, which reduce the bias and therefore exhibit improved iteration complexity. This brings us to the fast TD (FTD) algorithm which combines elements of CTD and the stochastic operator extrapolation method of the companion paper. For a novel index resetting step size policy FTD exhibits the best known convergence rate. We also devised a robust version of the algorithm that is particularly suitable for discounting factors close to 1.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.2 April-June 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1120-1155

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

VARIATIONAL INEQUALITY
REINFORCEMENT LEARNING
ACCELERATION
TEMPORAL DIFFERENCE LEARNING
OPERATOR EXTRAPOLATION
STOCHASTIC POLICY EVALUATION

Info Detail Spesifik

https://doi.org/10.1137/20M1381691

Pernyataan Tanggungjawab

Georgios Kotsalis, Guanghui Lan, Tianjiao Li

Versi lain/terkait

Lampiran Berkas

Komentar