Abstract
This work addresses the problem of efficiently learning action schemas using a bounded number of samples (interactions with the environment). We consider schemas in two languages— traditional STRIPS, and a new language STRIPS+WS that extends STRIPS to allow for the creation of new objects when an action is executed. This modification allows STRIPS+WS to model web services and can be used to describe web-service composition (planning) problems. We show that general STRIPS operators cannot be ef- ficiently learned through raw experience, though restricting the size of action preconditions yields a positive result. We then show that efficient learning is possible without this restriction if an agent has access to a “teacher” that can provide solution traces on demand. We adapt this learning algorithm to efficiently learn web-service descriptions in STRIPS+WS.