Symbolic Generalization for On-line Planning

Zhengzhu Feng, Eric A. Hansen, Shlomo ZilbersteinUAI 2003

TL;DR

This paper introduces Symbolic Real-Time Dynamic Programming (SRTDP), a novel on-line planning algorithm for Markov Decision Processes (MDPs). SRTDP leverages symbolic model-checking techniques to generalize experience across abstract states, significantly accelerating convergence and reducing real-world interactions compared to traditional on-line methods.

What Problem Does This Paper Address?

Markov Decision Processes (MDPs) are a powerful framework for decision-theoretic planning, but their state spaces can grow exponentially with the number of features, leading to a "state explosion" problem. While symbolic representations have been successfully used to tackle this in off-line planning (where the entire model is known beforehand), applying these techniques to on-line planning (where the agent interacts with an environment and learns as it goes) has been challenging. On-line planners like RTDP update values state-by-state, which can be inefficient and require many interactions, especially in large state spaces or when real-world actions are costly. This paper aims to bridge this gap by developing an on-line planning algorithm that benefits from symbolic generalization.

Methods

The core innovation is Symbolic Real-Time Dynamic Programming (SRTDP), an extension of the existing RTDP algorithm. SRTDP enhances RTDP by:

  • Symbolic Representation: It uses Algebraic Decision Diagrams (ADDs) to represent the MDP's value function and transition models, allowing for compact representation of large state spaces.
  • Generalization via Abstract States: Instead of updating the value of a single visited state, SRTDP identifies an "abstract state" that groups the current state with other structurally similar states. This generalization is performed using symbolic model-checking techniques.
  • Two Generalization Heuristics:
    • Value-based generalization: Groups states with similar estimated value functions.
  • Reachability-based generalization: Groups states that share similar sets of one-step reachable successor states.
  • Masked DP Update: SRTDP applies the dynamic programming update to this identified abstract state, effectively generalizing the update across multiple states simultaneously. This is achieved using a "masked" update operation, similar to that used in symbolic LAO*.

The paper also introduces an Adaptive SRTDP (AsRTDP) which extends SRTDP to scenarios where the MDP model is not fully known and needs to be learned on-line.

Datasets

The paper does not introduce new datasets. Instead, it evaluates its algorithms on four challenging test problems adapted from the "widget-processing problem" used in prior work (Hoey et al., 1999). The primary problem reported on (problem a1) has 20 Boolean state variables and 25 actions.

Key Insights and Ideas

  • Structural Similarity is Key for Generalization: The authors argue that generalizing based on "structural similarity" (value estimates or reachability) is more effective for on-line planning than simply generalizing based on input similarity. This is because structural similarity better captures the underlying value function of the MDP.
  • Symbolic Model Checking as a Generalization Tool: The paper highlights the power of symbolic model-checking techniques for efficiently identifying abstract states and performing generalized updates without enumerating the entire state space.
  • Trade-off Between Generalization Overhead and Benefit: While SRTDP incurs some overhead in identifying abstract states and performing masked DP, this is offset by the ability to update multiple states in a single step. For problems with large state spaces and regular structures, the benefits of generalization can significantly outweigh the overhead.
  • Value vs. Reachability Generalization: The paper explores two heuristic approaches for generalization. While both improve performance over non-generalized RTDP, their relative effectiveness can depend on the problem and the stage of learning. Value-based generalization tends to perform better when initial value estimates are accurate, while reachability-based generalization can be more robust when estimates are initially poor.

Key Results

  • Significant Speedup: SRTDP algorithms (both non-adaptive and adaptive) consistently outperform non-symbolic RTDP in terms of both CPU time and the number of interactions required to reach a desired value function.
  • Faster Convergence: SRTDP reaches near-optimal values much faster than RTDP. For problem a1, SRTDP achieved a value within 0.1 of symbolic LAO*'s converged value after about 20 trials, while RTDP was still more than 2.1 away after 100 trials.
  • Adaptive Performance: AsRTDP significantly outperforms adaptive RTDP (ARTDP), especially in large state spaces where ARTDP struggles due to insufficient sample coverage. AsRTDP's generalization allows it to learn effectively from limited experience.
  • Symbolic LAO* vs. SRTDP: While symbolic LAO* eventually converges to a better solution, SRTDP achieves a good solution much earlier, making it preferable when rapid improvement is critical or when full convergence is not feasible.

Limitations and Future Work

  • Generalization Heuristic Choice: The paper notes that the relative performance of value-based and reachability-based generalization depends on the problem. They suggest that a "mixed strategy" that applies different forms of generalization at different stages of learning could be beneficial, leaving this as future work.
  • Model Learning in AsRTDP: For AsRTDP, the paper assumes the reward function is given and the structure of the transition ADD is known, simplifying the model learning aspect. Future work could explore more comprehensive on-line model learning.
  • Approximation with SRTDP: While SRTDP uses exact symbolic representations, the paper mentions that grouping similar but not identical states can be seen as a form of approximation. This could be further explored for potential benefits in efficiency, similar to work on approximate dynamic programming.

Summary updated

BibTeX
@inproceedings{feng2003symbolic,
  author = {Zhengzhu Feng and Eric A. Hansen and Shlomo Zilberstein},
  title = {{Symbolic Generalization for On-line Planning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure