Abstract: Online planning in complex, stochastic environments requires balancing search depth with model accuracy. We present Progressive Abstraction Refinement for Sparse Sampling (PARSS), an algorithm that manages this trade-off by dynamically refining state abstractions. PARSS begins with a coarse model to enable deep exploration and progressively splits abstract states into finer representations as the sample budget allows. Our evaluation across several domains, including a custom "Saving Problem" and Spanish Blackjack, demonstrates that PARSS effectively "hugs" the performance envelope of various fixed abstraction levels, achieving high performance across a wide range of computational budgets.
Introduction: The Challenge of Planning at Scale
In artificial intelligence, planning involves simulating future outcomes to inform current decisions. However, in unpredictable environments like financial markets or complex games, the branching factor of possible futures leads to the "curse of dimensionality." Standard techniques like Monte Carlo Tree Search (MCTS) or Sparse Sampling can become shallow and ineffective when the state space is too detailed.
State abstraction—grouping similar states—is a common remedy. Yet, choosing the right level of abstraction is difficult. Coarse abstractions allow for deep searches but may ignore critical nuances (unsoundness), while fine-grained models are accurate but computationally prohibitive for long-term planning. The optimal granularity depends on the available sample budget, a parameter often unknown or variable in real-time applications.
The PARSS Algorithm: Dynamic Granularity
PARSS addresses this by integrating abstraction management directly into the search process. Built upon Forward Search Sparse Sampling (FSSS), PARSS utilizes a "wrap-around" loop to manage model complexity:
- Initial Coarse Abstraction: Search begins with a "top" abstraction where all states at the same depth are treated as identical (essentially open-loop planning).
- Iterative Refinement: If the search budget permits and convergence is not reached, the algorithm identifies nodes for refinement.
- State Splitting: Abstract groups are split into more specific subgroups. This can be done randomly or via a decision-tree approach (REFINEDT) that uses state features to identify significant value differences.
- Tree Update: The search tree is updated with the new granularity, and the process repeats.
This approach allows the agent to act as a fast, simplified planner under tight time constraints while converging toward an optimal, detailed plan given sufficient resources.
Experimental Evaluation
The researchers benchmarked PARSS against several Markov Decision Process (MDP) domains:
- The Saving Problem: A diagnostic task requiring a balance between saving, high-variance investing, and short-term borrowing. It punishes planners that are either too simple or too slow.
- Spanish Blackjack: A complex card game variant with a massive state space.
- Racetrack & Academic Advising: Classic and competition-level planning tasks involving stochastic transitions and complex constraints.
Results and Discussion
PARSS demonstrated a significant "anytime" advantage, matching the early performance of coarse models and the asymptotic performance of detailed ones. In the Saving Problem, PARSS was the only algorithm to navigate the trade-offs successfully; coarse models failed to see the value of investing, while ground-truth models were too slow to avoid the "debt trap" of borrowing.
A key insight from the experiments is that "unsound" coarse abstractions often outperform ground-truth models for moderate budgets because they permit greater search depth. PARSS leverages this by starting coarse and only refining when necessary. In complex domains like Spanish Blackjack, PARSS consistently outperformed fixed-abstraction baselines by adapting its model to the available samples.
Interestingly, the study found that the specific refinement logic (random vs. tree-based REFINEDT) was less critical than the act of refinement itself. Furthermore, refining nodes closer to the root state proved most effective for immediate decision quality.
Conclusion
PARSS provides a robust framework for online planning by treating state abstraction as a dynamic resource. By progressively refining its worldview, the algorithm overcomes the limitations of fixed-granularity models. Future work will explore extending these principles to continuous state and action spaces, potentially leveraging deep learning for more sophisticated refinement strategies.
Reference: Hostetler, J., Fern, A., & Dietterich, T. Progressive Abstraction Refinement for Sparse Sampling. Oregon State University.
Summary updated