Abstract 
Learning generative policy models can be seen as analogous to the general problem of learning contextsensitive grammars. This paper provides theoretical contributions in the areas of contextsensitive grammars (CSGs) and related machine learning. Specifically, we introduce a new class of CSGs, called Answer Set Grammars (ASGs), which extend contextfree grammars by allowing annotations on production rules, written in Answer Set Programming (ASP). We investigate the complexity of various classes of ASG with respect to deciding wether (i) a given string belongs to the language of an ASG and (ii) the language of an ASG is nonempty. We introduce an algorithm for learning the annotations of an ASG.
To scale up the applicability of our learning algorithm we also present a notion of domainspecific scoring functions applicable to logicbased machine learning in general. We present an efficient mechanism for constructing a small subset of the search space that is guaranteed to contain at least one optimal solution with respect to a given scoring function. We show that our FastLAS algorithm, which uses this efficient mechanism, outperforms stateoftheart logicbased machine learning systems in terms of running time, and is able to find the optimal solution of a task with respect to a given scoring function.
