ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling
This work addresses data efficiency in policy evaluation for reinforcement learning, offering a method to reduce variance in estimates, but it is incremental as it builds on existing theory for tree-structured MDPs.
The paper tackles the problem of data collection for policy evaluation in Markov decision processes by developing an optimal oracle strategy and introducing the ReVar algorithm to approximate it when reward variances are unknown, showing empirically that ReVar achieves mean squared error comparable to the oracle and significantly lower than running the target policy.
This paper studies the problem of data collection for policy evaluation in Markov decision processes (MDPs). In policy evaluation, we are given a target policy and asked to estimate the expected cumulative reward it will obtain in an environment formalized as an MDP. We develop theory for optimal data collection within the class of tree-structured MDPs by first deriving an oracle data collection strategy that uses knowledge of the variance of the reward distributions. We then introduce the Reduced Variance Sampling (ReVar) algorithm that approximates the oracle strategy when the reward variances are unknown a priori and bound its sub-optimality compared to the oracle strategy. Finally, we empirically validate that ReVar leads to policy evaluation with mean squared error comparable to the oracle strategy and significantly lower than simply running the target policy.