Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery

N. Kemal Ure, Alborz Geramifard, Girish Chowdhary, Jonathan P. How

In robotics and autonomous systems, effective planning requires an accurate model of the environment. However, real-world "rules" are often uncertain and vary based on the agent's state. For instance, a drone's GPS reliability might depend on its proximity to specific structures. This paper introduces a framework to learn these transition models online using Incremental Feature Dependency Discovery (iFDD), enabling high performance in massive state spaces with minimal samples.

The Adaptive Planning Framework

The core of the proposed approach is an iterative loop that bridges real-world interaction and internal simulation. The agent starts with an approximate model, plans a policy within a simulator, executes that policy in the real world, and uses the resulting observations to refine its model parameters.

The adaptive planning loop integrating model estimation, simulation, and real-world execution.

As shown in Figure 1, the process involves four main components: the Environment, the Parameter Estimator, the Simulator, and the Planner. The Parameter Estimator uses $n$ samples from the environment to update model parameters. The Simulator then uses these parameters to provide $N_{plan}$ interactions for the Planner, which finally executes $N_{exec}$ actions in the real world to close the loop.

Incremental Feature Dependency Discovery (iFDD)

To handle large state spaces without the exponential growth of tabular methods, the authors utilize iFDD integrated with Stochastic Gradient Descent (SGD). Instead of pre-defining all possible state dependencies, iFDD starts with basic atomic features. When the agent observes consistent estimation errors where multiple features are active simultaneously, iFDD automatically creates "conjunctive" features. This allows the model to grow its representation only where necessary, balancing early generalization with late-stage resolution.

Efficient Planning via TBVI

For planning within the simulator, the framework employs Trajectory-Based Value Iteration (TBVI). Unlike standard Value Iteration, TBVI focuses updates on states the agent is actually likely to visit. This focus is critical for scaling to complex domains like Persistent Search and Track (PST), which contains approximately 19 million state-action pairs. By focusing computational power on reachable states, TBVI makes massive problems tractable.

Experimental Evaluation and Results

The framework was evaluated across three increasingly complex simulated environments:

  • Gridworld Navigation: Successfully learned localized spatial "danger zones" where GPS failure rates were high.
  • Block Building: Outperformed tabular methods by quickly mastering non-linear collapse probabilities based on tower height and support blocks.
  • Persistent Search and Track (PST): In this 19-million-state domain, iFDD was roughly 2.5 times more sample-efficient than tabular estimation. It achieved near-optimal performance using only 10,000 features—a 70x reduction in model size compared to a tabular format.

Conclusion

By leveraging the sparsity of complex dependencies in the real world, iFDD provides a scalable solution for model-based Reinforcement Learning in uncertain environments. While the current implementation focuses on state-dependent uncertainties, the framework's success in high-fidelity simulations demonstrates its potential for complex, real-world autonomous missions where environment dynamics are not fully known a priori.

Summary updated

Abstract

Solving large scale sequential decision making problems without prior knowledge of the state transition model is a key problem in the planning literature. One approach to tackle this problem is to learn the state transition model online using limited observed measurements. We present an adaptive function approximator (incremental Feature Dependency Discovery (iFDD)) that grows the set of features online to approximately represent the transition model. The approach leverages existing feature-dependencies to build a sparse representation of the state transition model. Theoretical analysis and numerical simulations in domains with state space sizes varying from thousands to millions are used to illustrate the benefit of using iFDD for incrementally building transition models in a planning framework.
BibTeX
@inproceedings{ure2012adaptive,
  author = {N. Kemal Ure and Alborz Geramifard and Girish Chowdhary and Jonathan P. How},
  title = {{Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery}},
  booktitle = {ECML/PKDD},
  year = {2012},
  doi = {10.1007/978-3-642-33486-3\_7},
}
Figure