Model Acquisition for Markov Decision Problems

Abstract

In this research, we developed new models and techniques for representing stochastic processes that enabled us to compactly represent problems that couldn't be represented at all with previous techniques. We also developed new algorithms for efficiently solving such problems by directly exploiting the structure in the representations. Our models achieved efficiency in representation by factoring the state and action spaces of a dynamical system using a set of features (variously called state variables or fluents). We were able to explain the sources of combinatorial leverage in our and other structured models such as those of Boutilier et al. We found that the structure was due to certain symmetries in the dynamics that, in certain cases, could be exploited to significantly reduce computation time. Using these insights, we developed new algorithms that realized these reductions in computation time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 31, 1998
Accession Number
ADA373795

Entities

People

  • Thomas L. Dean

Organizations

  • Brown University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Acquisition
  • Algorithms
  • Artificial Intelligence
  • Causal Reasoning
  • Computations
  • Computer Science
  • Dynamics
  • Efficiency
  • Hidden Markov Models
  • Information Processing
  • Markov Models
  • Models
  • Reasoning
  • Stochastic Processes
  • Symmetry

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.

Technology Areas

  • Space