Proceedings

SMDP Homomorphisms: An Algebraic Approach to Abstraction in Semi-Markov Decision Processes

Balaraman Ravindran, Andrew G. Barto

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1011-1017.

Abstract

To operate effectively in complex environments learning agents require the ability to selectively ignore irrelevant details and form useful abstractions. In this article we consider the question of what constitutes a useful abstraction in a stochastic sequential decision problem modeled as a semi-Markov Decision Process (SMDPs). We introduce the notion of SMDP homomorphism and argue that it provides a useful tool for a rigorous study of abstraction for SMDPs. We present an SMDP minimization framework and an abstraction framework for factored MDPs based on SMDP homomorphisms. We also model different classes of abstractions that arise in hierarchical systems. Although we use the options framework for purposes of illustration, the ideas are more generally applicable. We also show that the conditions for abstraction we employ are a generalization of earlier work by Dietterich as applied to the options framework.

Balaraman Ravindran, and Andrew G. Barto. 2003. SMDP Homomorphisms: An Algebraic Approach to Abstraction in Semi-Markov Decision Processes. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1011–1017. https://ijcai.org/proceedings/2003/144
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards