How do you generate the transition probabilities of a non-trivial MDP?

Question

I understand an MDP (Markov Decision Process) model is a tuple of $\{S, A, P, R \}$ where:

• $S$ is a discrete set of states
• $A$ is a discrete set of actions
• $P$ is the transition matrix ie. $P(s' \mid s, a) \rightarrow [0,1]$
• $R$ is the reward function id. $R(s, a, s') \rightarrow \mathbb{R}$

For a non-trivial MDP, say $1000$ states and $10$ actions, the transition matrix has theoretically $S \times A \times S = 10,000,000$ entries (though many entries will be $0$).

I understand that one way of generating the $P$ matrix is to estimate it via Monte Carlo sampling, by simulating the environment. However, with non-trivial state space and simulation costs, this could be prohibitively expensive.

In practice, when a non-trivial MDP is being formulated, what are the different ways an accurate $P$ matrix can be produced?

Answer 1

1. In non-trivial cases, the transition matrix is (generally) not maintained in the traditional tabular form. If the representation used factored notation (Factored MDP) then Dynamic Bayesian networks can be used.

2. Another approach would be to abstract state spaces so that you have reduced number of states in the representation of P. These can be roughly classified as model minimization techniques.

3. Hierarchical representations can be adopted if some tasks can be split. E.g., the classical "taxi problem" has an explicit Get-passenger and Put-passenger task, that form the hierarchy. Now each of the smaller tasks can possibly have a well formed transition function.

4. It may also be prudent to use model free learning methods in such cases.