Abstraction Pathologies In Markov Decision Processes

Manel Tagorti, Bruno Scherrer, Olivier Buffet2014

TL;DR

This paper reveals a surprising counter-intuitive phenomenon in Markov Decision Processes (MDPs): refining an abstraction, which is typically expected to improve heuristic bounds, can actually lead to worse bounds. The authors demonstrate this "abstraction pathology" in two common methods for creating abstract MDPs, highlighting a critical limitation in how we approach heuristic search in probabilistic planning.

What Problem Does This Paper Address?

In classical AI planning, abstractions are a powerful tool for creating heuristic functions that estimate the cost to reach a goal. An abstraction essentially groups states together, creating a simplified "abstract" planning problem. A key, almost universally accepted, property of these abstractions is that refining them (making them more detailed by splitting groups of states) can only improve the heuristic, meaning it will provide a better (lower) bound on the true cost. This is because a more detailed abstraction leads to a more constrained abstract problem, and thus a more accurate estimate.

The authors of this paper set out to apply this same abstraction refinement technique to Markov Decision Processes (MDPs), which involve probabilistic transitions and rewards. Their initial assumption, based on classical planning, was that refining abstractions would similarly lead to better heuristic bounds for MDPs. However, they discovered that this intuition breaks down in the probabilistic setting. The core problem they address is understanding why and under what conditions this counter-intuitive behavior occurs in MDPs, and how it impacts the computation of value functions and heuristic bounds.

Methods

The paper investigates two primary methods for creating abstract MDPs and their corresponding heuristic bounds:

  1. Average MDPs: In this approach, the transition probabilities and rewards of an abstract state are computed by averaging the probabilities and rewards of the original states within that abstract state. The authors analyze the error introduced by this averaging process and demonstrate that direct refinements can lead to strictly worse bounds.
  2. Bounded-parameter MDPs (BMDPs): This method, building on prior work, represents abstract states with intervals of possible rewards and transition probabilities. This allows for the computation of optimistic and pessimistic bounds on the value function. The paper then examines how refining abstractions affects these bounds. They introduce the concept of "compatible MDPs" to analyze the relationship between an original MDP and its abstract representation.

The core of their methodological contribution lies in constructing counter-examples and proving theorems that demonstrate the "abstraction pathology." They analyze the error introduced by abstractions and their refinements, showing cases where the error increases after refinement.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and constructing illustrative examples of MDPs rather than empirical evaluation on standard datasets.

Key Insights and Ideas

  • Refinement Doesn't Always Improve Bounds in MDPs: This is the central, surprising finding. The intuition from classical planning that finer abstractions always yield better heuristics is demonstrably false for MDPs, even for deterministic MDPs.
  • Stochasticity is Not the Sole Culprit: While stochasticity plays a role, the paper shows that even in deterministic MDPs, abstraction pathologies can occur. This suggests the issue is more fundamental to how probabilistic information is aggregated or bounded.
  • Average MDPs Can Degrade Bounds: The simple approach of averaging transition probabilities and rewards in abstract states can lead to worse heuristic bounds upon refinement.
  • BMDPs Can Also Suffer: Even with more sophisticated bounded-parameter representations, refinement can still lead to wider value function intervals (meaning less precise bounds) or even worse bounds.
  • The "Abstraction Pathology" is Real: The paper provides concrete examples and theoretical arguments to show that it's possible to construct scenarios where a direct refinement of an abstraction leads to a strictly worse approximation of the value function.

Key Results

  • Proposition 1: Demonstrates that for the "average MDP" approach, there exists a deterministic MDP, an abstraction, and a refinement such that the approximation error increases after refinement.
  • Theorem 1: Establishes that for any MDP and abstraction, the true value function lies within the optimistic and pessimistic bounds derived from the BMDP. This is a foundational result for BMDPs.
  • Proposition 2: Provides a sufficient condition for when a finer abstraction does yield better bounds in the BMDP setting: when the set of compatible MDPs for the finer abstraction is a subset of those for the coarser abstraction.
  • Corollary 1: Shows that this sufficient condition holds for deterministic MDPs, meaning refinements in deterministic settings do improve bounds.
  • Proposition 3: Crucially, demonstrates that for stochastic MDPs, the sufficient condition from Proposition 2 is not always met. They provide an example where any direct refinement of a given abstraction strictly increases the approximation error for some states.

Limitations and Future Work

  • Focus on Direct Refinements: The paper primarily examines "direct refinements," where only one block of states is split. It raises the question of whether refining multiple blocks simultaneously or using larger refinement steps might behave differently.
  • Theoretical Focus: The work is largely theoretical, focusing on demonstrating the existence of these pathologies. Practical implications and algorithms for avoiding them are left as open questions.
  • Identifying Sufficient Conditions: While a sufficient condition for improvement in BMDPs is given, the paper acknowledges that it's not always met. A key future direction is to find practical criteria for when refinement is likely to improve bounds, or conversely, when it might degrade them.
  • Generalizing Beyond MDPs: The paper notes that similar pathologies have been observed in other areas like game theory. Further research could explore the universality of these issues.
  • Practical Guidance: The authors hope their work will serve as a guide for practitioners, helping them understand the potential pitfalls of abstraction refinement in MDPs and potentially leading to more informed choices about abstraction strategies.

Summary updated

Abstract

Abstraction is a common method to compute lower bounds in classical planning, imposing an equivalence relation on the state space and deriving the lower bound from the quotient system. It is a trivial and well-known fact that refined abstractions can only improve the lower bound. Thus, when we embarked on applying the same technique in the probabilistic setting, our firm belief was to find the same behavior there. We were wrong. Indeed, there are cases where every direct refinement step (splitting one equivalence class into two) yields strictly worse bounds. We give a comprehensive account of the issues involved, for two wide-spread methods to define and use abstract MDPs.
BibTeX
@misc{tagorti2014abstraction,
  author = {Manel Tagorti and Bruno Scherrer and Olivier Buffet},
  title = {{Abstraction Pathologies In Markov Decision Processes}},
  year = {2014},
}

Loading related content...

Figure