Loop Estimator for Discounted Values in Markov Reward Processes

Authors

  • Falcon Z. Dai Toyota Technological Institute at Chicago
  • Matthew R. Walter Toyota Technological Institute at Chicago

DOI:

https://doi.org/10.1609/aaai.v35i8.16881

Keywords:

Reinforcement Learning

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.

Downloads

Published

2021-05-18

How to Cite

Dai, F. Z., & Walter, M. R. (2021). Loop Estimator for Discounted Values in Markov Reward Processes. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 7169-7175. https://doi.org/10.1609/aaai.v35i8.16881

Issue

Section

AAAI Technical Track on Machine Learning I