Intelligent agents can cope with complexity by abstracting away irrelevant details. Prior work in abstraction typically relied on users to provide abstractions manually. We propose an alternative approach built around the idea of emphpolicy irrelevance, in which we abstract away a feature if it is possible to behave optimally without it. We show how this approach permits statistical inference methods to discover policy irrelevant state variables, and we give two such methods that optimize respectively for computational complexity and sample complexity. However, although policy irrelevance guarantees the ability to represent an optimal policy, a naive application possibly loses the ability to learn an optimal policy. We demonstrate that encapsulating a state abstraction inside an abstract action preserves optimality while offering the possibility of learning more efficiently. Finally, since our approach currently discovers abstractions post hoc, we show how abstractions discovered in an easy problem can help learn difficult related problems.

PDF, PS, HTML

In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pp. 752-757, August 2005.

@InProceedings{IJCAI05, title={State Abstraction Discovery from Irrelevant State Variables}, author={Nicholas K. Jong and Peter Stone}, booktitle={Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence}, month={August}, pages={752-757}, url="http://www.cs.utexas.edu/users/ai-lab?IJCAI05", year={2005} }