How to fill in missing transitions when sampling an MDP transition table?

Question

I have a simulator modelling a relatively complex scenario. I extract ~12 discrete features from the simulator state which forms the basis for my MDP state space.

Suppose I am estimating the transition table for an MDP by running a large number of simulations and extracting feature transitions as the state transitions.

While I can randomize the simulator starting conditions to increase the coverage of states, I cannot guarantee all states will be represented in the sample, i.e. states which are possible but rare.

Is there a rigorous approach to "filling in the gaps" of the transition table in this case?

For example:

1. For each state that was unrepresented in the sample, simply transition to all other states with equal probability, as a "neutral" way to fill in the gap?

2. As above, but transition only to represented states (with equal probability)?

3. Transition to the same state with probability 1.0?

4. Ignore unrepresented states during MDP solving entirely, and simply have a default action specified?

Answer 1

I assume you use the 12 discrete features as state variables, and, for each of these variables, you will have at least two values. So, the minimum number of states will be $2^{12} = 4096$, which gives $(2^{12})^{2} = 16777216$ possible transitions. In order to reach this, you will need a huge amount of simulations, also taking into account that this number is a minimum since you might have more values per state variable, and you probably have more than one action per state transition.

How to fill the gaps depends on your problem, in a problem where I did this, I filled the gaps using a uniformly random transition to its neighbor states. However, since I had to fill in such a a large amount, there was no significant difference between using this estimated transitions probabilities with a predefined transition table.

In your case, it might be better to use Q-Learning, which is a model-free method that does not require the transition probabilities and uses directly the rewards and states obtained.