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

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?