The majority of the formal sections of this paper will explore the phenomenon of factoring. In particular, we will explore how policies for factorable environments can be composed from policies for the factors. In state-machine models of environments, factorization is the factorization of the state-space; the environment's state-space is a Cartesian product of other state-spaces. The environment, as a whole, is ``factorable'' into its component sub-environments. For example, the position of the king on a chess board has row and column components. It can be thought of as the ``product'' of those components, each if which is isomorphic to (since there are eight rows and eight columns). If we consider an environment in which a car drives through an grid of city blocks, we see that it too is a kind of product of with itself. Both environments have grids as state spaces, but the car environment only allows one component to change at a time, whereas the king environment allows both to change.
We must therefore distinguish different kinds of factorization. We will call the chessboard case the parallel product of with itself, while the car case is its serial product. We will focus on another kind of factorization later. Let the Cartesian product of two functions f and g be , and let i be the identity function. For two environments and , we will define the parallel product to be
and the serial product to be
The products of DCPs are defined in the obvious way:
The state diagram for is shown in Figure 1.
We will say that an environment or DCP is parallel (or serial) separable if it is isomorphic to a product of environments or DCPs.