How can we use linear programming to solve an MDP?

Question

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.

Answer 1

This question seems to be addressed directly in these slides.

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.