02/02/2021

Loop Estimator for Discounted Values in Markov Reward Processes

Falcon Z. Dai, Matthew R. Walter

Keywords:

Abstract Paper Similar Papers

Abstract: At the working heart of policy iteration algorithms commonly used and studied in the discounted setting of reinforcement learning, the policy evaluation step estimates the value of states with samples from a Markov reward process induced by following a Markov policy in a Markov decision process. We propose a simple and efficient estimator called loop estimator that exploits the regenerative structure of Markov reward processes without explicitly estimating a full model. Our method enjoys a space complexity of O(1) when estimating the value of a single positive recurrent state s unlike TD with O(S) or model-based methods with O(S^2). Moreover, the regenerative structure enables us to show, without relying on the generative model approach, that the estimator has an instance-dependent convergence rate of O~(\sqrt{\tau_s/T}) over steps T on a single sample path, where \tau_s is the maximal expected hitting time to state s. In preliminary numerical experiments, the loop estimator outperforms model-free methods, such as TD(k), and is competitive with the model-based estimator.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949140
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 8:44 
 0
 0
 0
 0
 14:45 
 0
 0
 0
 0
 17:58 
 0
 0
 0
 0
 12:29 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 14:10 
 0
 0
 0
 0
 3:09 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 13:28 
 0
 0
 0
 0
 4:29 
 0
 0
 0
 0
 14:36 
 1
 0
 0
 0
 13:50 
 0
 0
 0
 0
 14:58 
 0
 0
 0
 0
 8:57 
 0
 0
 0
 0
 2:57 
 0
 0
 0
 0
 14:43 
 0
 0
 0
 0
 13:11 
 0
 0
 0
 0
 4:23 
 0
 0
 0
 0
 5:43 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 3:34 
 0
 0
 0
 0
 20:01 
 0
 0
 0
 0
 13:47 
 0
 0
 0
 0
 15:21 
 0
 0
 0
 0
 11:00 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 3:42 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 3:14 
 0
 0
 0
 0
 18:34 
 0
 0
 0
 0
 14:41 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 0
 4:12 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 3:04