# 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.

• If you are interested in answering to this question, you can have a look at these slides: cs.cmu.edu/afs/cs/academic/class/15780-s16/www/slides/mdps.pdf (p. 29 onwards). You may also need to have a look at The Linear Programming Approach to Approximate Dynamic Programming (by D. P. de Farias, B. Van Roy) and Linear Programming for Large-Scale Markov Decision Problems (by Yasin Abbasi-Yadkori et al, Peter L. Bartlett and Alan Malek). – nbro Mar 14 '19 at 21:14
• Hello nbro. It's nice to read a question from you. Especially because the topic is a markov decision process. To answer if linear programming can be used in that context we have to first separate between a model-predictive control optimization problem and a model-free version. The needed algorithm is very different. Unfortunately, the question isn't specific enough in that point. A model-based MDP process means, that the agent can predict future outcome while in the model-free version he will need a direct policy. – Manuel Rodriguez Mar 14 '19 at 21:25
• @ManuelRodriguez Hi Manuel. You can assume that you are given the model of the MDP (that is, you are given the transition and reward functions). In fact, in the slides that I linked you to above, the author compares this LP formulation to the value and policy iterations algorithms (which also assume that these functions are given). – nbro Mar 14 '19 at 21:27

This question seems to be addressed directly in slides 29-31 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 \arg\max_{a \in A}\sum_{s' \in S} P(s' | s,a)*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: $$minimize\ V(s)$$ subject to the constraints: $$\forall a\in A, V(s) \geq r + \gamma\sum_{s' \in S} P(s' | s,a)*V(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.

Hope that helps some.

• 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. – John Doucette 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