Empirical Policy Evaluation with Supergraphs

Daniel Vial, Vijay G. Subramanian

Abstract

We devise and analyze algorithms for the empirical policy evaluation problem in reinforcement learning. Our algorithms explore backward from high-cost states to find high-value ones, in contrast to forward approaches that work forward from all states. While several papers have demonstrated the utility of backward exploration empirically, we conduct rigorous analyses which show that our algorithms can reduce average-case sample complexity from $O(S \log S)$ to as low as $O(\log S)$.

Introduction

In Reinforcement Learning (RL), policy evaluation is the fundamental task of estimating the "value function"—the expected long-term cost starting from any given state. Traditionally, this is approached through "forward" sampling: an agent is placed in various states and allowed to run forward to observe accumulated costs. However, this method is often prohibitively expensive because it scales linearly with the number of states $S$, requiring $O(S \log S)$ samples to achieve accuracy across the entire state space.

In many real-world scenarios, such as safety-critical robotics or game environments, high costs are concentrated in a small subset of states. This paper introduces a paradigm shift: instead of exploring forward from all states, we can evaluate policies more efficiently by working backward from these high-cost "disaster" states. By leveraging side information about possible transitions, we can drastically reduce the data required for accurate evaluation.

Methodology

The authors bridge network science and RL by adapting PageRank estimation algorithms to the policy evaluation problem. They introduce two primary algorithms:

  1. Backward-EPE: This algorithm starts at states with known high costs and "pushes" that cost information backward to neighboring states. To facilitate this without knowing exact transition probabilities, the agent utilizes a Supergraph ($A$). The supergraph is an adjacency matrix representing a map of possible transitions; it acts as a superset of the actual transitions, allowing the algorithm to identify which states could potentially lead to high-cost outcomes.
  2. Bidirectional-EPE: This hybrid method combines backward exploration with limited forward sampling. It provides a "pseudo-relative error" guarantee, ensuring that estimated values are accurate relative to one another, which is critical for ranking actions during policy iteration.

Theoretical and Empirical Results

The core contribution of this work is the rigorous analysis of sample complexity. While worst-case performance remains comparable to forward approaches, the average-case sample complexity is significantly improved. Specifically, the complexity is reduced to $O(\bar{d} \frac{\|c\|_1}{\|c\|_\infty} \log S)$, where $\bar{d}$ is the average degree of the graph. In sparse environments where costs are concentrated, this moves the scaling from linear to logarithmic.

Empirical performance of Backward-EPE across different state space sizes (S). The middle plot shows the sample requirement relative to forward sampling, demonstrating significant efficiency gains as the state space grows.

As shown in the empirical simulations (Figure 1), the number of samples required by Backward-EPE relative to forward sampling decreases sharply as the number of states ($S$) increases. This confirms the sublinear complexity predicted by the theoretical analysis. Furthermore, the $l_\infty$ error remains comparable to standard forward methods, indicating that the efficiency gains do not come at the cost of accuracy.

Key Insights

  • PageRank Connection: The mathematical structure of RL value functions mirrors PageRank, allowing the use of efficient local graph exploration tools.
  • Exploiting Sparsity: The efficiency of backward exploration is tied to the sparsity of costs and transitions. If high costs are ubiquitous, the advantages of backward exploration diminish.
  • The Supergraph Utility: The supergraph does not need to be an exact model of the environment; it only needs to contain the true transitions. This makes it a realistic form of domain knowledge in many engineering applications.

Conclusion and Future Work

By "flipping the script" and working backward from costs, this research provides a path toward evaluating policies in environments with massive state spaces that were previously computationally unreachable. The primary requirement is the availability of a supergraph, which can often be derived from physical constraints or domain expertise. Future research directions include integrating these backward exploration techniques into full policy iteration loops and adapting the framework for finite-horizon tasks.

Summary updated

Abstract

We devise and analyze algorithms for the empirical policy evaluation problem in reinforcement learning. Our algorithms explore backward from high-cost states to find high-value ones, in contrast to forward approaches that work forward from all states. While several papers have demonstrated the utility of backward exploration empirically, we conduct rigorous analyses which show that our algorithms can reduce average-case sample complexity from $O(S \log S)$ to as low as $O(\log S)$.
BibTeX
@article{vial2021empirical,
  author = {Daniel Vial and Vijay G. Subramanian},
  title = {{Empirical Policy Evaluation with Supergraphs}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=80oHlSfDi7},
}
Figure