Exhaustive Enumeration Method for MDPs

Topics: Markov Decision Process - Optimisation

---

Given an MDP, we can find the optimal policy with the exhaustive enumeration method. This method is one of the simplest for this purpose.

Algorithm §

The exhaustive enumeration method consists of the following steps.

Step 1 §

Enumerating exhaustively all of the viable policies for the MDP.

• When every decision (with $k$ total) can be made in every state (with $m+1$ total), then the total amount of viable policies is $k^{m+1}$ (permutations with repetitions).

Step 2 §

Calculating the expected long term cost for every policy $r$:

$$\mathbb{E}[C_r]=\sum _{i=0}^m{C}_{ik}{\pi }_i$$

…where $C_{ik}$ denotes the cost incurred for making the decision $k$ (defined according to the policy) in the state $i$, while ${\pi }_i$ denotes the steady state probability of the state $i$ given the policy.

Don’t forget to take the policy into consideration in this step. It defines the decision $k$ we’ll be taking in each state $i$, as well as the transition matrix that is used to obtain the steady state probabilities. We can obtain the latter by (1) selecting the column that corresponds to the state $i$ in the transition matrix for the decision $k$, and then (2) splicing them together in a new matrix.

Step 3 §

Select the optimal policy based on its cost.

If we’re dealing with classical costs, then we’ll select the policy that has the smallest expected cost. If our “costs” are actually earnings, then we’ll select the policy that has the largest expected “cost” (earning).