Another important kind of structure is when one environment can be considered an abstraction of another [28, 34, 20]. The abstract environment retains the fundamental structure of the concrete environment but removes unimportant distinctions among states. An abstract state corresponds to a set of concrete states and abstract actions correspond to complicated sequences of concrete actions.
Figure 2: A simple reduction from an environment E' to E. Here s and s' are corresponding states from the reduced and unreduced environments respectively and a and a' are corresponding actions. A projection is a simple reduction if it ``commutes'' with actions, so that , or alternatively, . Thus regardless of whether we take the projection before or after the action, we will achieve the same result.
We will say that a projection from an environment E' to another environment E is a mapping from the state space of E' to that of E. We will say that is a simple reduction of E' to E if for every action a of E, there is a corresponding action a' of E' such that for any state s'
or equivalently, that
where is the function composition operator. We will say that a' is a -implementation of a and we will use to denote the function mapping E-actions to their implementations in E'.
It is possible to define a much more powerful notion of reduction in which implementations are allowed to be arbitrary policies. It requires a fair amount of additional machinery, however, including the addition of state to the agent. Since simple reduction will suffice for our purposes, we will simply assert the following lemma, which is a direct consequence of the more general reduction lemma :