2
$\begingroup$

What does a deterministic Markov Decision Process (MDP) mean? Does it mean that the probability when going from one state to another is 1?

$\endgroup$

2 Answers 2

1
$\begingroup$

A Markov Decision Process is essentially a Markov Chain, where at every point in time, you make a decision that affects the next step in the process, i.e. the process uses a transition matrix that depends on your action for its next step.

A deterministic MDP is one where the decisions you make, given the current state, are deterministic, e.g. if you are in state $1$, you take action $A$, and action $B$ if you are in state $2$.

Compare this with stochastic MDP: if you are in state $1$, take action $A$ with probability $p$ and action $B$ with probability $1-p$, and if in state $2$, do $A$ w.p. $q$ and $B$ w.p. $1-q$ etc.

$\endgroup$
1
$\begingroup$

To add to the above answer of Ken Wei, you can visualize your deterministic MDP as follows:

From a practical computational perspective, when dealing with finite state MDPs, one has an array of same dimension transition matrices. Each of these matrices correspond to and action. Simulation-Based Optimization by Gosavi call this your TPM's. So if actions are given as A = [a0,a1,a2,...an] then TPMs = [P0,P0,P2,...Pn]. So if you perform action a0 at state 0 (s0) in order to move to state 1 (s1) then you can access your probability as TPMs[0][0][1] = p. In a deterministic setting p = 1 and the entire rest of the row would be zero e.g. TPMs[0][0] = [0,1,0,...0]. This row is a probability distribution. So in a stochastic setting TPMs[0][0] = [0.1,0.7,0.1,....0] as an example. What is the purpose of a deterministic MDP when you could just solve the Bellman equations recursively as is? Well, despite it being deterministic, you might still have some graph created by your Transition matrices and MDP setting can expose this. Plus, you can just plug the problem into some MDP solver if you would wish. You can even approach you problem as a shortest path problem. However, despite all this being said, MDP algorithms such as Policy Iteration do make assumptions which are critical such as boundedness of the value function and assumptions on transience and recurrence in the chain. So some deterministic chains might pose a problem if the chain is not irreducible. For deterministic problems I rather recommend solving the Bellman equations recursively.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .