Answers.Body: <p>This question seems to be addressed directly in <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15780-s16/www/slides/mdps.pdf" rel="nofollow noreferrer">these slides</a>.</p>
  <p>The basic idea is:</p>
  <ul>
  <li>Assume you have a complete model of the MDP (transitions, rewards, etc.).</li>
  <li>For any given state, we have the assumption that the state's true value is reflected by:</li>
  </ul>
  <p><span class="math-container">$$V^*(s) = r + \gamma \max_{a \in A}\sum_{s' \in S} P(s' | s,a) \cdot V^*(s')$$</span></p>
  <p>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 <span class="math-container">$\gamma$</span>, which captures the idea that reward in the future is less good than reward now.</p>
  <ul>
  <li><p>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 <a href="http://web.tecnico.ulisboa.pt/mcasquilho/compute/_linpro/TaylorB_module_c.pdf" rel="nofollow noreferrer">Branch &amp; Bound algorithm</a>. These are widely available in fast implementations. GLPK is a decent free library. IBM's CPLEX is faster, but expensive.</p>
  </li>
  <li><p>We can represent the problem of finding the value of a given state as:
  <span class="math-container">$$\text{minimize}_V \ V(s)$$</span>
  subject to the constraints:
  <span class="math-container">$$V(s) \geq r + \gamma\sum_{s' \in S} P(s' | s,a)*V(s'),\; \forall a\in A, s \in S$$</span>
  It should be apparent that if we find the smallest value of <span class="math-container">$V(s)$</span> that matches this requirement, then that value would make exactly one of the constraints tight.</p>
  </li>
  <li><p>If you formulate your linear program by writing a program like the one above for <em>every</em> state and then minimize <span class="math-container">$\sum_{s\in S} V(s)$</span>, 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.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T02:42:16.287Z
Answers.LastActivityDate: 2022-04-13T11:52:25.717Z
Answers.LastEditDate: 2022-04-13T11:52:25.717Z
Answers.UserDisplayName: John Doucette
Body: <p>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.</p>
  
Tags: <reinforcement-learning><optimization><markov-decision-process><linear-programming>
Title: How can we use linear programming to solve an MDP?
UserDisplayName: nbro
ThreadText: # How can we use linear programming to solve an MDP?
  
  (Asked by: username_0 on 2019-03-14)
  
  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.
  
  **Tags:** reinforcement-learning, optimization, markov-decision-process, linear-programming
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-15. Score: 2 | Accepted answer
  
  This question seems to be addressed directly in [these slides](http://www.cs.cmu.edu/afs/cs/academic/class/15780-s16/www/slides/mdps.pdf).
  
  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](http://web.tecnico.ulisboa.pt/mcasquilho/compute/_linpro/TaylorB_module_c.pdf). 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.
  
  
  ---
  
  