# Whats exactly deterministic and non deterministic in deterministic and nondeterministic MDP policies?

Consider below Markov Decision Process:

Blue hexagons are states and orange circles are actions. I have rather simple confusion. What will be nature of deterministic and non deterministic MDPs? This confusion stems from the fact that I don't know if probabilities are specified for actions or for next state. In the diagram, probabilities seem to have specified for next states. For example, from (S3,a1), S4 will be next state with probability 0.6 and S1 will be next state with probability 0.4. Q1. But I was guessing can MDP also specify probabilities with which a1 and a2 are followed from S3.

If answer to Q1 is yes, then

Q2. What deterministic policy will specify, fixed action and next state for given state, or just fixed action? That is, from S3, we can take a1 and go to S4 vs we can take a1 (and go to either S4 or S1 with corresponding probabilities)?

Q3. Similar to Q2, what non deterministic policy will specify?

PS: please note that the title of question is single and self-sufficient. I formed these sub questions to help answerer to better answer by explicitly focusing on them. Answering these three subquestions will completely answer original question in the title.

• I guess your linked post answers Q1 above. But not Q2 and Q3. To be precise, deterministic policy is $\pi_d: S\rightarrow A$. But, what if particular action can lead to two or more different states with different probabilities? For example, in question, taking action a1 from S3 can lead to either S4 and S1. Then what will deterministic policy tell: (q1). "take a1 from S3 and go anywhere S4 or S1 depending on their associated probabilities" or "(q2). take a1 from S3 and go to S4 and not S1 (or S1 and not S4, regardless of associated probabilities)"?
– Rnj
Feb 12, 2021 at 11:15

The MDP don't have to contain the probabilites of an action choice. The policy itself is not a part of the MDP. As an example you're Markov Decision Process would be fully described by the full table:

S S' a p(S'|S,a) Reward
$$S_1$$ $$S_2$$ $$a_1$$ 0.3 1
$$S_1$$ $$S_3$$ $$a_1$$ 0.7 1
$$S_1$$ $$S_1$$ $$a_2$$ 0.3 1
$$S_1$$ $$S_4$$ $$a_2$$ 0.7 1
.... .... .... .... ....

Our goal in RL now is to find an optimal policy, whose aim is always to choose the best action in each step to maximize our return. That means the policy is our goal and not part of the initial MDP respectively the Markov Reward Process in this case. RL is all about methods to find the optimal policy.

So regarding to your Q2 and Q3 a deterministic policy means, that your found policy selects always the same action in a specific state whereas a stochatic (non-deterministic) policy selects actions with a specific probability. But finding these probabilites is not trivial

If you're interested in further information about RL I can strongly recommend this book: http://incompleteideas.net/book/RLbook2020.pdf

• Ok, so there is no such concept as "probability with which action is taken from a state" a part of MDP definition. This is a part of non deterministic policy, right? That is, it makes no sense for MDP to specify probabilities for actions. Rather policies determine which actions to take from state, either deterministically or non deterministically.
– Rnj
Feb 12, 2021 at 12:07
• Yes exact, I think you got the concept. Feb 13, 2021 at 11:23