# How can we use linear programming to solve an MDP?

Apparently, we can solve an MDP (that is, we can find the optimal policy for a given MDP) using a linear programming formulation. What's the basic idea behind this approach? I think you should start by explaining the basic idea behind a linear programming formulation and which algorithms can be used to solve such constrained optimisation problems.

This question seems to be addressed directly in the slides of the deck you linked to in the comment under your question.

The basic idea is:

• Assume you have a complete model of the MDP (transitions, rewards, etc.).
• For any given state, we have the assumption that the state's true value is reflected by:

$$V^*(s) = r + \gamma \max_{a \in A}\sum_{s' \in S} P(s' | s,a) \cdot V^*(s')$$

That is, the true value of the state is the reward we accrue for being in it, plus the expected future rewards of acting optimally from now until infinitely far into the future, discounted by the factor $$\gamma$$, which captures the idea that reward in the future is less good than reward now.

• In Linear Programming, we find the minimum or maximum value of some function, subject to a set of constraints. We can do this efficiently if the function can take on continuous values, but the problem becomes NP-Hard if the values are discrete. You would usually do this using something like the Branch & Bound algorithm. These are widely available in fast implementations. GLPK is a decent free library. IBM's CPLEX is faster, but expensive.
• We can represent the problem of finding the value of a given state as: $$\text{minimize}_V \ V(s)$$ subject to the constraints: $$V(s) \geq r + \gamma\sum_{s' \in S} P(s' | s,a)*V(s'),\; \forall a\in A, s \in S$$ It should be apparent that if we find the smallest value of $$V(s)$$ that matches this requirement, then that value would make exactly one of the constraints tight.

• If you formulate your linear program by writing a program like the one above for every state and then minimize $$\sum_{s\in S} V(s)$$, subject to the union of all the constraints from all these sub-problems you have reduced the problem of learning a value function to solving the LP.
• Why can't we also maximise $V(s)$? The constraints could still be satisfied. Maybe it is because, intuitively, it captures the fact that we want to act as little as possible. Also, why do we want to minimise the sum of the value of all states? Maybe for the same reason.
– nbro
Mar 15 '19 at 10:02
• @nbro You could write an LP formulation that maximizes $V(s)$, but the problem is that there is not a unique solution to that formulation (in fact, by making V(s) ever larger, we could increase our objective function ever more). In contrast, this formulation should have a unique value for $V(s)$, at least if we hold the values assigned to the other states constant. This property is really what lets us solve LPs in general: unique solutions because of the constraints. Mar 15 '19 at 13:51
• Yes, that makes sense. Here's apparently an implementation of an algorithm that solves an MDP using linear programming: https://github.com/sawcordwell/pymdptoolbox/blob/master/src/mdptoolbox/mdp.py.
– nbro
Mar 15 '19 at 13:57