# Can two states have different actions in a deterministic policy? How to specify states which have probability linked with them in the policy?

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?

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.