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?


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.

  • $\begingroup$ thanks for the response. On reflection, if a state was unrepresented, and you assign the same transition values for every action, then the MDP solver will inevitably assign the default action no matter what (since the actions in that state are indistinguishable). So it doesn't matter what set of states you transition to or even what probabilities are assigned. So in fact, my 4 approaches and yours will all result in default actions being specified. (assuming every action for the unrepresented state was assigned the same artificial transition values!) $\endgroup$ – Brendan Hill Jan 31 '17 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.