Monte Carlo Matrix Inversion Policy Evaluation
This work addresses policy evaluation in reinforcement learning, offering incremental improvements in efficiency and accuracy for researchers and practitioners in the field.
The paper tackles reinforcement learning policy evaluation by introducing an algorithm based on Monte Carlo matrix inversion (MCMI), which improves runtime over maximum likelihood model-based approaches and outperforms temporal differencing in both runtime and accuracy, with further enhancements via importance sampling to reduce variance.
In 1950, Forsythe and Leibler (1950) introduced a statistical technique for finding the inverse of a matrix by characterizing the elements of the matrix inverse as expected values of a sequence of random walks. Barto and Duff (1994) subsequently showed relations between this technique and standard dynamic programming and temporal differencing methods. The advantage of the Monte Carlo matrix inversion (MCMI) approach is that it scales better with respect to state-space size than alternative techniques. In this paper, we introduce an algorithm for performing reinforcement learning policy evaluation using MCMI. We demonstrate that MCMI improves on runtime over a maximum likelihood model-based policy evaluation approach and on both runtime and accuracy over the temporal differencing (TD) policy evaluation approach. We further improve on MCMI policy evaluation by adding an importance sampling technique to our algorithm to reduce the variance of our estimator. Lastly, we illustrate techniques for scaling up MCMI to large state spaces in order to perform policy improvement.