MDP as a Linear Programming Problem

Topics: Markov Decision Process - Linear Programming Problem

---

Given an MDP, we can find the optimal policy by formulating it as a linear programming problem.

Decision Variables §

As Binary §

Let the following be our decision variables:

$$D_{ik}=\{\begin{array}{ll}1& \text{if the decision }k\text{ is made in the state }i\\ 0& \text{otherwise}\end{array}$$

Once solved, the matrix of the values these variables optimally take characterises the optimal policy.

As Continuous §

Solving binary linear programming problems isn’t as straightforward as it may normally be with continuous ones, so we can reinterpret these decision variables as:

$$D_{ik}=\mathbb{P}(k\mid i)$$

Id est, the probability of making the decision $k$ given that the system is in the state $i$.

Under this reinterpretation, we’ll be actually using other variables in the objective function: $Y_{ik}$. These represent the unconditional steady state probability of being in the state $i$ and taking the decision $k$, satisfying:

$$D_{ik}=\frac{Y_{ik}}{{\sum }_{k=1}^K{Y}_{ik}}$$

Model §

Finally, with these considerations, the linear programming model for an MDP is:

$$\{\begin{array}{llc}& \text{optimise }\mathbb{E}[C]=Z={\sum }_{i=0}^m{\sum }_{k=1}^K{C}_{ik}{Y}_{ik}& \\ & \text{s.t.}& \\ & {\sum }_{i=0}^m{\sum }_{k=1}^k{Y}_{ik}=1& \\ & {\sum }_{k=1}^K{Y}_{jk}-{\sum }_{i=0}^m{\sum }_{k=1}^K{Y}_{ik}{p}_{ij}\{k\}=0\text{for }j=0,1,\dots m& \end{array}$$

…where:

• $C_{ik}$ denotes the cost of making the decision $k$ in the state $i$
• $p_{ij}\{k\}$ denotes the transition probability from state $i$ to $j$ when making the decision $k$

Evidently, we can find the optimal $Y_{ik}$ by solving this linear programming problem through any of the applicable methods (simplex, etc.). Then we can determine the optimal policy by calculating the $D_{ik}$ as established above.