# Decomposing the non-deterministic transition functions in non-Markov decision processes into several deterministic transition functions

Problems in reinforcement learning are commonly modeled as Markov decision processes (MDPs). One essential part of MDPs is the transition function $T: S \times A \times S \rightarrow [0, 1] \in \mathbb{R}$. This function states that the probability of state $s_{t+1}$ is dependent only on the previous state $s_t$ and the action $a_t$ that has been performed in it. This works straight-forwardly if the environment is fully observable, e.g. if the task is to navigate in a stationary grid world and the perceived state is the absolute position within this grid world. (To some degree this also works in partially observable and non-stationary MDPs.)

Conventional Q- or SARSA-learning is able to learn a policy that enables to navigate in a grid world like the one illustrated below. Actions displace an agent by one step in each direction (north, south, east, and west), starting from any one of the free cells (randomly chosen) until it reaches the goal state.

~ 0 1 2 3 4 5 6 7
0 x x x x x x x x
1 x . . . . . . x
2 x . . . . g . x
3 x . . . . . . x
4 x . . . . . . x
5 x . . . . . . x
6 x . . . . . . x
7 x x x x x x x x

This works as long as the perception of the state transitions remains unambiguous, i.e., as long as the problem is Markov-decidable. If the agent does not receive its absolute position but only the four neighboring cells as a state, it does not make much sense to describe it as a (probabilistic) MDP. The new problem might instead be described in terms of partially observable MDPs.

From the observer's perspective, however, such a partially observable MDP can be decomposed into several deterministic MDPs. These MDPs have different transition functions $T$. (Deterministic in this case also means that $T \rightarrow \{0, 1\} \in \mathbb{Z}$. ) The picture below roughly illustrates the regions in a grid world where such deterministic MDPs might be applied. It shows one possible decomposition into six MDPs with different transition functions.

Other decompositions are equally possible/correct. The transition functions of these deterministic MDPs are as follows. (The four-tuple (n, e, s, w) denotes the perceived content of each single cell in the respective direction. Single letters denote the performed movement in the respective direction. Those two components represent $S$ and $A$ in the transition function $T$.)

Transitions in first MDP:
$(.,~.,~.,~.) \stackrel{n \vee e \vee s \vee w}{\longleftrightarrow} (.,~.,~.,~.)$

Transitions in second MDP:
$(.,~.,~.,~.) \stackrel{n}{\longrightarrow} (x,~.,~.,~.) \stackrel{s}{\longrightarrow} (.,~.,~.,~.)$ $(.,~.,~.,~.) \stackrel{e}{\longrightarrow} (.,~x,~.,~.) \stackrel{w}{\longrightarrow} (.,~.,~.,~.)$ $(.,~.,~.,~.) \stackrel{s}{\longrightarrow} (.,~.,~x,~.) \stackrel{n}{\longrightarrow} (.,~.,~.,~.)$ $(.,~.,~.,~.) \stackrel{w}{\longrightarrow} (.,~.,~.,~x) \stackrel{e}{\longrightarrow} (.,~.,~.,~.)$

Transitions in third MDP:
$(.,~.,~.,~x) \stackrel{n}{\longrightarrow} (x,~.,~.,~x) \stackrel{s}{\longrightarrow} (.,~.,~.,~x)$ $(x,~.,~.,~.) \stackrel{w}{\longrightarrow} (x,~.,~.,~x) \stackrel{e}{\longrightarrow} (x,~.,~.,~.)$

Transitions in fourth MDP:
$(.,~.,~.,~x) \stackrel{s}{\longrightarrow} (.,~.,~x,~x) \stackrel{n}{\longrightarrow} (.,~.,~.,~x)$ $(.,~.,~x,~.) \stackrel{w}{\longrightarrow} (.,~.,~x,~x) \stackrel{e}{\longrightarrow} (.,~.,~x,~.)$

Transitions in fifth MDP:
$(.,~x,~.,~.) \stackrel{s}{\longrightarrow} (.,~x,~x,~.) \stackrel{n}{\longrightarrow} (.,~x,~.,~.)$ $(.,~.,~x,~.) \stackrel{e}{\longrightarrow} (.,~x,~x,~.) \stackrel{w}{\longrightarrow} (.,~.,~x,~.)$

Transitions in sixth MDP:
$(x,~.,~.,~.) \stackrel{e}{\longrightarrow} (x,~x,~.,~.) \stackrel{w}{\longrightarrow} (x,~.,~.,~.)$ $(.,~x,~.,~.) \stackrel{n}{\longrightarrow} (x,~x,~.,~.) \stackrel{s}{\longrightarrow} (.,~x,~.,~.)$

It can be seen that MDP 2 is incompatible with any other MDP. MDP 1, 3, 4, 5, 6, on the other hand, might be unified in one unambiguous MDP as none of the contained transitions are in conflict. Therefore we arrive at two MDPs with different and non-overlapping transition functions. The problem is: until we know all of the transitions, we cannot know whether any two MDPs are compatible or not.

Now to the actual question: Do you know of any machine learning algorithm that enables to successively determine compositions of deterministic transitions from a indeterministic transition graph? If not, maybe there are related problems?

The first things that come to mind are graph component analysis (wikipedia "Connected_component_(graph_theory)") and the method to translate non-deterministic finite automata into deterministic finite automata (an example here). Data in reinforcement learning, however, only becomes available successively. An effective decomposition must be possible with partial information about all possible samples. (This problem is also known as the exploration-exploitation trade-off.)

tl;dr: How can you compose transitions effectively and efficiently (not optimally), such that resulting groups of transitions remain deterministic as a whole. Efficient means no exponential space or run-time complexity, effective means that switching between different sets of transitions is minimized over the life-time of a reinforcement learning agent. Sample transitions become available only over time. The transitions provide a model for the agent.

E.g.: $A \rightarrow B$ and $C \rightarrow A$ might be in the same group, while $B \rightarrow C$ and $B \rightarrow A$ may never be in the same group. Temporal closeness should increase the possibility to group two transitions together.

Edit: The answer must be applicable not only to spatial domains such as the grid world example but to any environment that agents can interact with.

Edit: Related question