Learning to take actions

Authors
Citation
R. Khardon, Learning to take actions, MACH LEARN, 35(1), 1999, pp. 57-90
Citations number
83
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
MACHINE LEARNING
ISSN journal
08856125 → ACNP
Volume
35
Issue
1
Year of publication
1999
Pages
57 - 90
Database
ISI
SICI code
0885-6125(199904)35:1<57:LTTA>2.0.ZU;2-Y
Abstract
We formalize a model for supervised learning of action strategies in dynami c stochastic domains and show that PAC-learning results on Occam algorithms hold in this model as well. We then identify a class of rule-based action strategies for which polynomial time learning is possible. The representati on of strategies is a generalization of decision lists; strategies include rules with existentially quantified conditions, simple recursive predicates , and small internal state, but are syntactically restricted. We also study the learnability of hierarchically composed strategies where a subroutine already acquired can be used as a basic action in a higher level strategy. We prove some positive results in this setting, but also show that in some cases the hierarchical learning problem is computationally hard.