8 Markov Decision Processes

Page 1

8 Markov Decision Processes We want to analyse the existing methods to evaluate the performance of a given policy on a Markov Decision Problem (MDP). Subsequently, we will apply the ones able to find the optimal policy in an MDP . 8.1 Computing Values on a Markov Decision Process Let us consider the following MDP , which models an advertising problem: Figure 8.1: The considered MDP . We would like to model it inMATLAB when we have a fixed policyπ = (d,d,d ), whered corresponds to the action do nothing, and the discount factor isγ = 0.9. We just need to define the transition probabilities matrix Pπ and the immediate expected revenue Rπ for each state: 1 clear 2 clc 3 close all 4 1 8 Markov Decision Processes 5 n_states = 3; 6 gamma = 0.9; 7 R = [0.9*0 + 0.1*20; ... 8 0.4*0 + 0.6*20; ... 9 0.2*0+0.8*50]; 10 11 P = [0.9 0.1 0 ; ... 12 0.4 0.6 0 ; ... 13 0.2 0 0.8 ]; Since we fixed the policy, we reduced the MDP to a Markov Process. At this point we are interested in the computation of the value for each state of the MDP . This could be performed with different tools. For instance, one might resort to the Bellman expecta- tion equation: Vπ = (I −γPπ)−1Rπ. Since Pπ is a stochastic matrix, we have some properties on the eigenvalues of the matrix (I −γPπ). 1 eig(P) 2 eig(gamma*P) 3 eig(eye(n_states) - gamma * P) Clearly we could not consider discount factor γ = 1 otherwise the matrix would be singular and we would not be able to solve the Bellman equations. Thus the solution inMATLAB is: 1 V_eq = inv(eye(n_states) - gamma*P) * R This solution obtained by inverting the matrix is feasible only if the number of the states of the problem is finite and if the it is small enough. In fact, if the number of states is s, we require a computational cost ofs3 for the matrix inversion.…