Symbolic Opportunistic Policy Iteration for Factored-Action MDPs

Aswin Raghavan, Roni Khardon, Alan Fern, Prasad TadepalliNeurIPS 2013 · OpenReview

Automated planning often requires making decisions in environments where both the world state and the possible actions are defined by many moving parts. This paper tackles a major hurdle in this domain: scaling symbolic planning under uncertainty to handle not just factored states, but factored actions.

The authors introduce Symbolic Opportunistic Policy Iteration (OPI), a novel algorithm for solving Markov Decision Processes (MDPs) with exponentially large action spaces. By "opportunistically" enforcing policy constraints only when they do not bloat the underlying data structures, OPI achieves significantly better scalability and memory efficiency than traditional symbolic planning methods.

The Challenge: Factored Action Spaces and Memory Explosion

In many real-world scenarios—such as managing a fleet of robots, controlling traffic lights, or playing real-time strategy games—an agent does not simply choose one action from a small, discrete list. Instead, it chooses a joint action composed of many individual variables (e.g., "Robot A moves north" AND "Robot B stays still" AND "Robot C recharges").

This creates a "factored action space" that grows exponentially. For instance, just 20 binary action variables result in over a million possible joint actions.

A factored representation of a state and action space, illustrating the complexity of joint actions.

Standard "symbolic" planners use Algebraic Decision Diagrams (ADDs) to represent value functions compactly, avoiding the need to explicitly list every single state. However, when attempting to perform Modified Policy Iteration (MPI)—which alternates between improving a policy and evaluating it—the symbolic representation of the policy often becomes much more complex than the value function itself.

The primary bottleneck in symbolic planning is not just the number of states or actions, but the size of the ADD representation. A mathematically "cheaper" update (like policy evaluation) can become computationally disastrous if it makes the ADD overly complex. This leads to "memory explosion," where the planner runs out of RAM before it can find a solution.

The Solution: Opportunistic Policy Iteration

To address these scalability issues, the authors propose two main contributions:

  1. Factored Action MPI (FA-MPI): A symbolic version of MPI explicitly designed for factored actions. It represents the policy as a Binary Decision Diagram (BDD) and treats it as a constraint on the Bellman backup. While functionally sound, it often suffers from the memory explosion issues inherent to strict policy enforcement.
  2. Opportunistic Policy Iteration (OPI): This is the core contribution of the paper. Instead of strictly forcing the agent to follow a specific policy (which might require a massive ADD), OPI uses a novel pruning procedure.

If enforcing the policy would make the value function representation larger, OPI "opportunistically" relaxes the constraint and performs a standard Value Iteration (VI) backup instead.

Comparison of ADD operations showing how the pruning operator prevents the exponential growth caused by standard multiplication.

Traditional symbolic policy evaluation uses multiplication ($\pi \times V$), which can grow the ADD exponentially. OPI’s pruning operator, however, is guaranteed to result in an ADD no larger than the original value function. Sometimes, a full Bellman backup provides a "coarser" (simpler) partition of the state space than a specific policy. OPI exploits this by retaining that simplicity whenever possible. Crucially, the authors prove that this hybrid approach—lying between VI and MPI—is still guaranteed to converge to the optimal policy.

The authors also introduce a Memory-Bounded (MB-OPI) version that allows users to set a hard cap on memory usage, effectively trading off computation time for a smaller memory footprint.

Experimental Results

The algorithms were evaluated on three complex domains described in the Relational Dynamic Influence Diagram Language (RDDL), grounded into Factored-Action MDPs:

  • Inventory Control (IC): Managing multiple shops and delivery trucks.
  • SysAdmin: Maintaining a network of computers in various topologies.
  • Elevator Control: Managing elevators in a building with stochastic passenger arrivals.

Key findings include: * Scalability: In the Inventory Control domain, OPI scaled to much larger action spaces where standard VI and FA-MPI failed completely. * Memory Efficiency: FA-MPI frequently hit the "Exceeded Memory Limit" (EML) threshold. OPI avoided this by keeping the value function representation compact. In the SysAdmin domain, FA-MPI was often 150% slower than OPI or crashed entirely. * Speedup: In the Elevator Control domain, OPI(2) (performing 2 policy evaluation steps) was significantly faster than standard VI, demonstrating that even a small amount of "opportunistic" lookahead yields substantial performance gains. * Compression: The authors demonstrated that ADDs can compress a tabular representation by factors of $10^{-4}$ to $10^{-5}$ in certain domains, though this effectiveness varies based on the problem's topology.

Limitations and Future Work

While highly effective, the performance of OPI still depends heavily on the variable ordering within the ADDs. In some domains, such as the "Unidirectional Ring" topology in SysAdmin, the inherent structure of the problem resists compression regardless of the algorithm used.

Future directions proposed by the authors include integrating approximate value backups (like APRICODD) to further alleviate memory pressure, exploring Affine ADDs for even more compact value function representation, and utilizing initial state information to focus the symbolic search strictly on reachable parts of the state space.

Summary updated

Abstract

We address the scalability of symbolic planning under uncertainty with factored states and actions. Prior work has focused almost exclusively on factored states but not factored actions, and on value iteration (VI) compared to policy iteration (PI). Our first contribution is a novel method for symbolic policy backups via the application of constraints, which is used to yield a new efficient symbolic imple- mentation of modified PI (MPI) for factored action spaces. While this approach improves scalability in some cases, naive handling of policy constraints comes with its own scalability issues. This leads to our second and main contribution, symbolic Opportunistic Policy Iteration (OPI), which is a novel convergent al- gorithm lying between VI and MPI. The core idea is a symbolic procedure that applies policy constraints only when they reduce the space and time complexity of the update, and otherwise performs full Bellman backups, thus automatically adjusting the backup per state. We also give a memory bounded version of this algorithm allowing a space-time tradeoff. Empirical results show significantly improved scalability over the state-of-the-art.
BibTeX
@inproceedings{raghavan2013symbolic,
  author = {Aswin Raghavan and Roni Khardon and Alan Fern and Prasad Tadepalli},
  title = {{Symbolic Opportunistic Policy Iteration for Factored-Action MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=rJVGswb_ZS},
}
Figure