We consider a class of sequential environments that provide an agent with propositional state descriptions as well as access to facts and objects that may be necessary for carrying out optimal actions. Learning the "state'' portion of these environments is related to gathering experience in sequential decision problems, as considered in the field of reinforcement learning.  However, learning about the schema underlying the facts and objects is more in the vein of concept learning, as considered in the field of Inductive Logic Programming (ILP).  Despite the rich literature on theoretical efficiency in both of these problems, algorithms focused on learning in environments that combine them have produced largely empirical results.  We present an extended review of work in these areas, and then provide a formalism for a restricted class of environments with states, facts, and objects (ESFOs) that facilitates efficient learning.  We provide some example domains and present some introductory results  on the sample complexity of learning in such environments.  Finally, we discuss extensions of the formalism and analysis that are of interest in a continued investigation of these topics.