Reinforcement learning addresses the problem of learning to select actions in order to maximize one's performance in unknown environments. To scale reinforcement learning to complex real-world tasks, such as typically studied in AI, one must ultimately be able to discover the structure in the world, in order to abstract away the myriad of details and to operate in more tractable problem spaces. This paper presents the SKILLS algorithm. SKILLS discovers skills, which are partially defined action policies that arise in the context of multiple, related tasks. Skills collapse whole action sequences into single operators. They are learned by minimizing the com(cid:173) pactness of action policies, using a description length argument on their representation. Empirical results in simple grid navigation tasks illustrate the successful discovery of structure in reinforcement learning.

As part of our work on agent-oriented programming,1 we are developing an agent description language. We describe an agent's “mental state” in terms of its knowledge, beliefs, desires, commitments, and abilities. Our goal is not to specify human knowledge, beliefs, etc., but rather to devise a more limited, precise language to facilitate programming agents and interagent communication. We believe that borrowing from our intuition about these commonsense terms will simplify the human designer's job. This article describes a preliminary version of our language. We define a temporal language with modal operators representing knowledge, belief, desire, commitment, and ability. This is a propositional language with quantification over time points and agents only.