Empirical Policy Evaluation With Supergraphs

Daniel Vial, Vijay G. Subramanian

In the world of Reinforcement Learning (RL), figuring out "how good" a policy is usually involves a lot of trial and error. Traditionally, we drop an agent into every possible state, let it run forward, and see what costs it racks up. But what if we only care about a few "disaster" states or high-cost goals?

In their paper "Empirical Policy Evaluation with Supergraphs," Daniel Vial and Vijay Subramanian propose a way to evaluate policies by working backward from high-cost outcomes, potentially slashing the amount of data needed by orders of magnitude.

TL;DR

This paper introduces algorithms that evaluate Reinforcement Learning policies by exploring backward from high-cost states rather than forward from all states. By leveraging a "supergraph" (side information about possible transitions), they reduce the average-case sample complexity from a linear dependence on the number of states $O(S \log S)$ to as low as $O(\log S)$.

What Problem Does This Paper Address?

The core challenge is Empirical Policy Evaluation (EPE). In RL, to improve a policy, you first need to estimate its "value function"—the expected long-term cost of starting in any given state.

Standard "forward" approaches are data-hungry. They require sampling trajectories starting from every state in the environment. If your environment has millions of states, this is prohibitively expensive. This "linear" scaling with the state space size is a major bottleneck.

The authors noticed that in many real-world scenarios (like games or robot navigation), high costs are concentrated in just a few states (e.g., falling off a ledge or losing a game). If we know where the costs are, why spend time sampling trajectories from "safe" states that are nowhere near the danger?

Methods

The authors bridge the gap between network science and RL by adapting PageRank estimation algorithms to policy evaluation. 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 do this without knowing the exact transition probabilities, they assume the agent has access to a Supergraph.
  2. The Supergraph ($A$): This is a piece of side information (an adjacency matrix) that acts as a "map of possibilities." It tells the agent which transitions are possible, even if it doesn't know the exact probabilities.
  3. Bidirectional-EPE: This combines the backward approach with a limited amount of forward sampling. This hybrid method provides a "pseudo-relative error" guarantee, ensuring that the estimated values are accurate relative to the actual values, which is crucial for ranking which actions are better than others during policy iteration.

Datasets

The paper focuses on theoretical analysis and uses synthetic, randomly generated Markov Decision Processes (MDPs) for evaluation.

  • The authors generate random transition matrices ($Q$) and cost vectors ($c$).
  • They vary the "sparsity" of the environment (how many states lead to others) to test how the algorithms scale.
  • They compare their methods against the standard "forward" sampling approach used in existing literature (e.g., Haskell et al., 2016).

Key Insights and Ideas

  • The PageRank Connection: The mathematical structure of a value function in RL is strikingly similar to PageRank (the algorithm used to rank web pages). This allows RL researchers to "borrow" highly efficient local graph exploration tools.
  • Exploiting Sparsity: Backward exploration is only efficient if the costs and transitions are sparse. If every state is high-cost, backward exploration is just as slow as forward exploration.
  • The Utility of the Supergraph: The supergraph doesn't need to be perfect; it just needs to be a "superset" of the real transitions. This makes it a realistic piece of domain knowledge (e.g., in a maze, we know you can't walk through walls, even if we don't know exactly how a robot's wheels might slip).

Key Results

  • Sample Complexity Win: While the worst-case performance matches forward approaches, the average-case sample complexity is significantly better. It drops from $O(S \log S)$ to $O(\bar{d} \frac{\|c\|_1}{\|c\|_\infty} \log S)$, where $\bar{d}$ is the average degree of the graph. In sparse settings, this effectively moves from linear to logarithmic scaling.
  • Empirical Speedup: In simulations, Backward-EPE showed sublinear complexity. As the number of states ($S$) increased, the number of samples required by the backward approach grew much more slowly than the forward approach.
  • Ordering Preservation: Bidirectional-EPE was shown to be more efficient at maintaining the correct "ranking" of states by value, which is the most important factor for an agent trying to choose the best move.

Limitations and Future Work

  • The Supergraph Requirement: The biggest hurdle is obtaining the supergraph. While the authors argue it can come from domain knowledge, in complex, high-dimensional environments (like raw video pixels), defining a supergraph is non-trivial.
  • Fixed Policy: This work focuses on evaluating a fixed policy. Integrating this efficiently into a full Policy Iteration loop (where the policy changes constantly) remains a task for future research.
  • Finite Horizons: The current analysis focuses on infinite-horizon discounted costs. The authors suggest that adapting these techniques for finite-horizon tasks (tasks with a specific end time) is a promising next step.

Summary updated

Abstract

We devise algorithms for the policy evaluation problem in reinforcement learning, assuming access to a simulator and certain side information called the supergraph. Our algorithms explore backward from high-cost states to find high-value ones, in contrast to 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 logS) to as low as O(logS). Analytically, we adapt tools from the network science literature to provide a new methodology for reinforcement learning problems.
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},
}

Loading related content...

Figure