enter image description here

The agent has two actions, a0 and a1, whose effects in each state σ0; . . . ; σ3 are described in Figure 1. The edges from actions are labeled with the probability that this transition occurs. For example, Pr[st+1 = σ2 | st = σ0; at = a1] = 1; similarly, Pr[st+1 = σ0 | st = σ1, at = a0] = 1-p. If there is no edge from a state to an action, that action is not allowed in that state. Thus, choosing either a0 or a1 in σ3 is not allowed ,and σ3 is a sink state; similarly, action a1 cannot be taken in state σ1. The rewards in each state are action-independent, and are r(σ0) = r(σ2) = 0; r(σ1) = 1; r(σ3) = 10.
Q1) What are the possible (deterministic) policies are there for this MDP? When counting, ignore “degenerate” actions, i.e. ones that are not allowed in a given state. Doubt - Is the policy choosing a0 at σ0 and a1 at σ2 a deterministic policy? If yes, how do I write it mathematically as we have transition probabilities included with 2 states? Also, how do I write the value function for this policy?


1 Answer 1


You just formulate your state space with your sigmas, name it $S=\{\sigma_0...\sigma_3\}$. Your action space is $A=\{a_0,a_1\}$ Next write the transition probabilities matrix just as you started. You have to decide about your cost functional. To make it most comprehensible, pick the discounted infinite horizon and then write your Bellman equation like this $V(s_i)=max_{k,k\in\{0,1\}}\{\sum_jP(s_j|s_i,a_k)V(s_j)*\gamma+r(s_i,a_k)\}$

So this is the standard Bellman equation. Assume stationary $P$ you will asymptotically converge to the fixed point, and just take the greedy policy then, for each state. Easily done on MATLAB.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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