Abstract
This paper addresses the challenge of data collection for policy evaluation in Markov decision processes (MDPs). While on-policy sampling is a common baseline, it is often suboptimal when certain actions exhibit high variance or significant downstream impact. We introduce ReVar (Reduced Variance Sampling), an adaptive algorithm that minimizes the Mean Squared Error (MSE) of the value estimate by strategically sampling actions based on their immediate and downstream uncertainty. Theoretical analysis shows that ReVar achieves $O(n^{-3/2})$ regret relative to an optimal oracle, and empirical results demonstrate significant performance gains over standard baselines in both tree-structured and gridworld environments.
Introduction
In Reinforcement Learning (RL), policy evaluation is the task of estimating the expected total reward of a specific "target policy." This is a critical step before deploying systems in high-stakes domains like autonomous driving or healthcare. Traditionally, the default approach has been on-policy sampling—simply executing the target policy to collect data. However, this intuition is often flawed. If a target policy rarely selects an action that has highly unpredictable rewards, on-policy sampling will fail to gather enough data to stabilize the estimate, leading to high variance and poor accuracy.
Problem Formulation
The goal is to find a "behavior policy" for data collection that minimizes the Mean Squared Error (MSE) of the target policy's value estimate. The challenge lies in the fact that environments are often non-uniform; some regions are "noisier" than others. In an MDP, an action's importance for evaluation depends not only on its immediate reward variance but also on the variance of the future states it leads to. Effective data collection must therefore "look ahead" to account for downstream uncertainty.
The ReVar Algorithm
The researchers first derive an Oracle Strategy for tree-structured MDPs. If the exact variance of every reward were known, this strategy would provide the optimal proportion of samples for each action to minimize final estimate variance.
Since these variances are unknown in practice, the authors propose ReVar. The algorithm employs several key mechanisms:
- Adaptive Variance Estimation: ReVar uses Upper Confidence Bounds (UCB) to estimate reward variances from observed data, adding a "bonus" to account for uncertainty in these estimates.
- Recursive Uncertainty Accounting: It calculates the "downstream" variance contribution of each action, ensuring that actions leading to highly uncertain future states are sampled more frequently.
- Deterministic Selection: Rather than random sampling, ReVar uses a deterministic rule to select the action that is most under-sampled relative to its current estimated optimal proportion.
While the theory is grounded in tree structures, the authors extend the approach to Directed Acyclic Graphs (DAGs) using a value-iteration-like method to handle states reachable via multiple paths.
Experimental Evaluation
The algorithm was evaluated in two primary simulated environments:
- 4-Depth, 2-Action Tree MDP: A synthetic environment designed to highlight the limitations of on-policy sampling, particularly when high-variance actions are rarely taken by the target policy.
- 4x4 Stochastic Gridworld: A more complex DAG MDP that tests the algorithm's ability to generalize beyond simple tree structures.
Key Results
Empirical results confirm that ReVar significantly outperforms standard on-policy sampling and competitive baselines like CB-Var (adapted from multi-armed bandits).
In the Tree MDP, ReVar achieved an MSE orders of magnitude lower than on-policy sampling. In the Gridworld experiment, ReVar's adaptive nature allowed it to even outperform the static tree-based Oracle, as it better handled the dependencies inherent in the DAG structure. Furthermore, the theoretical $O(n^{-3/2})$ regret bound was supported by the rapid convergence of ReVar toward oracle-level performance as the number of episodes increased.
Conclusion
ReVar demonstrates that strategic, variance-aware data collection is essential for efficient policy evaluation. By accounting for both immediate and downstream uncertainty, it provides a principled alternative to on-policy sampling. Future work includes extending these theoretical guarantees to general MDPs with cycles and scaling the algorithm to continuous state spaces using function approximation techniques like neural networks.
Summary updated