Khardon, Roni2016-04-081995Khardon, Roni. 1995. Learning to take Actions. Harvard Computer Science Group Technical Report TR-28-95.http://nrs.harvard.edu/urn-3:HUL.InstRepos:26506442We formalize a model for supervised learning of action strategies in dynamic 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 representation of strategies is 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.en-USResearch Paper or Report2016-04-08