Solving Relational MDPs with Exogenous Events and Additive Rewards

Saket Joshi, Roni Khardon, Prasad Tadepalli, Aswin Raghavan, Alan Fern

TL;DR

This paper introduces a new symbolic planning algorithm, the Template Method, designed to solve Relational Markov Decision Processes (RMDPs) that feature independent, object-centered exogenous events (like customer arrivals in a shop). By leveraging novel reduction techniques for first-order decision diagrams, the authors provide the first relational symbolic algorithm with explicit performance guarantees—specifically, a monotonic lower bound on the optimal value function.

What Problem Does This Paper Address?

In traditional automated planning, we often assume the world only changes when the agent acts. However, real-world "service domains"—such as inventory control, emergency response, or taxi dispatching—are constantly influenced by exogenous events (external service requests).

Modeling these in a Relational MDP (RMDP) is difficult because the number of possible next states grows exponentially with the number of objects in the domain (e.g., every shop in a retail chain might receive a customer simultaneously). This "stochastic branching factor" makes standard grounded planning infeasible. While Symbolic Dynamic Programming (SDP) allows us to reason abstractly without knowing the exact number of objects, existing SDP methods struggled to handle the complexity of simultaneous external events alongside additive rewards.

Methods

The authors propose two major technical contributions:

  1. The Template Method: This is a new symbolic algorithm for a subclass of RMDPs. Instead of trying to calculate every possible combination of exogenous events, it uses a "ground-regress-lift" approach. It grounds a value function using a generic "Skolem constant" (a placeholder object), performs regression for a single generic exogenous action, and then "lifts" the result back into an aggregate form (using averages). Under specific technical assumptions (A1–A4), they prove this method provides a monotonic lower bound on the true value function.
  2. Efficient GFODD Evaluation: To implement this, they use Generalized First Order Decision Diagrams (GFODDs) to represent reward and value functions. They developed a new model evaluation algorithm inspired by Variable Elimination (VE). This replaces "brute force" evaluation by aggregating variables early in the computation tree, significantly speeding up the symbolic manipulation process.
  3. Model Checking Reduction: They use a set of "focus states" (a training set) to simplify complex symbolic diagrams. If a part of a diagram doesn't contribute to the value in the focus states, it is pruned, allowing the algorithm to remain computationally efficient.

Datasets

The researchers evaluated their approach using the Inventory Control (IC) domain:

  • Standard IC: A retail company must maintain inventory across multiple shops. Exogenous events are customer arrivals that deplete stock.
  • Advanced IC (AIC): A more complex version where inventory has three levels (instead of two) and varying consumption rates. This version intentionally violates some of the paper's theoretical assumptions to test the algorithm's robustness.

They compared their system against propositional solvers like SPUDD and MADCAP.

Key Insights and Ideas

  • Independence is Key: By assuming exogenous events are "object-centered" and independent, the authors can model the transition as a sequence of actions rather than one massive joint probability distribution.
  • Provable Bounds: The Template Method isn't just a heuristic; it’s mathematically guaranteed to produce a lower bound. This provides a "certificate of quality" for the resulting policies.
  • Symbolic vs. Grounded: The biggest "aha" moment is the scaling. Propositional solvers (which ground the problem into specific instances) explode in complexity as the number of shops increases. The symbolic approach remains "domain-size agnostic," meaning the time it takes to find a solution doesn't depend on whether there are 5 shops or 500.

Key Results

  • Scalability: Propositional solvers like SPUDD ran out of memory or failed at 4–5 shops. The proposed relational system handled much larger instances with ease because its offline planning time is constant relative to domain size.
  • Speed: The Variable Elimination (VE) method for GFODD evaluation was significantly faster than brute-force evaluation, allowing for many more iterations of Value Iteration.
  • Policy Quality: In the standard IC domain, the approximate symbolic policy was indistinguishable from the optimal policy. In the Advanced IC domain (where assumptions were violated), the policy was slightly sub-optimal but still far outperformed random baselines and scaled where others could not.

Limitations and Future Work

The primary limitation lies in the technical assumptions (A1–A4) required for the proof of the lower bound (e.g., exogenous events only affecting unary properties). While the algorithm works in practice when these are relaxed (as seen in the AIC experiments), the theoretical guarantees no longer strictly hold.

Future work includes:

  • Identifying broader conditions where compact symbolic solutions are guaranteed to exist.
  • Improving the "focus state" selection to ensure reductions are less approximate for very large states.
  • Developing even faster techniques for diagram application and evaluation to handle more complex relational structures.

Summary updated

Abstract

We formalize a simple but natural subclass of service domains for relational planning problems with object-centered, independent exogenous events and additive rewards capturing, for example, problems in inventory control. Focusing on this subclass, we present a new symbolic planning algorithm which is the first algorithm that has explicit performance guarantees for relational MDPs with exogenous events. In particular, under some technical conditions, our planning algorithm provides a monotonic lower bound on the optimal value function. To support this algorithm we present novel evaluation and reduction techniques for generalized first order decision diagrams, a knowledge representation for real-valued functions over relational world states. Our planning algorithm uses a set of focus states, which serves as a training set, to simplify and approximate the symbolic solution, and can thus be seen to perform learning for planning. A preliminary experimental evaluation demonstrates the validity of our approach.
BibTeX
@inproceedings{joshi2013solving,
  author = {Saket Joshi and Roni Khardon and Prasad Tadepalli and Aswin Raghavan and Alan Fern},
  title = {{Solving Relational MDPs with Exogenous Events and Additive Rewards}},
  booktitle = {ECML/PKDD},
  year = {2013},
  doi = {10.1007/978-3-642-40988-2\_12},
}

Loading related content...

Figure