Timezone: »

 
Poster
Decentralized TD Tracking with Linear Function Approximation and its Finite-Time Analysis
Gang Wang · Songtao Lu · Georgios Giannakis · Gerald Tesauro · Jian Sun

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #153
in Poster Session 1 »

The present contribution deals with decentralized policy evaluation in multi-agent Markov decision processes using temporal-difference (TD) methods with linear function approximation for scalability. The agents cooperate to estimate the value function of such a process by observing continual state transitions of a shared environment over the graph of interconnected nodes (agents), along with locally private rewards. Different from existing consensus-type TD algorithms, the approach here develops a simple decentralized TD tracker by wedding TD learning with gradient tracking techniques. The non-asymptotic properties of the novel TD tracker are established for both independent and identically distributed (i.i.d.) as well as Markovian transitions through a unifying multistep Lyapunov analysis. In contrast to the prior art, the novel algorithm forgoes the limiting error bounds on the number of agents, which endows it with performance comparable to that of centralized TD methods that are the sharpest known to date.

Keywords: Learning Theory · Convex Optimization · Theory · Optimization

Author Information

Gang Wang (Beijing Institute of Technology)
Songtao Lu (IBM Research)
Georgios Giannakis (University of Minnesota)
Gerald Tesauro (IBM TJ Watson Research Center)
Jian Sun (Beijing Insitute of Technology)

More from the Same Authors