@InCollection{RS90, author = { Ronald L. Rivest and Robert E. Schapire }, title = { A New Approach to Unsupervised Learning in Deterministic Environments }, pages = { 670--684 }, booktitle = { Machine Learning: An Artificial Intelligence Approach }, volume = { III }, editor = { Yves Kodratoff and Ryszard Michalski }, publisher = { Morgan Kaufmann }, date = { 1990 }, OPTyear = { 1990 }, abstract = { We present a new approach to the problem of inferring the structure of a deterministic finite-state environment by experimentation. The learner is presumed to have no \emph{a priori} knowledge of the environment other than knowing how to perform a set of basic actions and knowing what elementary sensations are possible. The actions affect the state of the environment and the sensations of the learner according to deterministic rules that are to be learned. The goal of the learner is to construct a perfect model of his environment----one that enables him to predict perfectly the result of any proposed sequence of actions. \par Our approach is based on the notion of a ``test'': a sequence of actions followed by a predicted sensation. The value (true or false) of a test at the current state can be easily determined by executing it. We define two tests to be ``equivalent'' if they have the same value at any global state. Our procedure uses systematic experimentation to discover the equivalence relation on tests determined by the environment, and produces a set of ``canonical'' tests. \par The equivalence classes produced correspond in many cases to a natural decomposition of the structure of the environment; one may say that our procedure discovers the appropriate set of ``hidden state variables'' useful for describing the environment. \par Our procedure has been implemented and appears to be remarkably effective in practice. For example, it has successfully inferred, in a few minutes each, the structure of Rubik's Cube (over $10^{19}$ global states and a simple ``grid world'' environment (over $10^{11}$ global states); these examples are many orders of magnitude larger than what was possible with previous techniques. } , }