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.
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:
- 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.
- 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.
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