I'm currently implementing a Markov Decision Process using the solver GLPK, I'm following the lecture by Vincent Conitzer, and there is a step I don't understand between the theoretical problem and its implementation.

More precisely, I have a set of states $\Sigma$ and a set of actions $A$, such that given two states $s$ and $s'$, $P(s, a, s')$ denotes the probability of going from the state $s$ to the state $s'$ with the action $a$. Moreover, for each state $s$ and each action $a$, $R(s, a)$ denotes the immediate reward of executing the action $a$ from the state $s$.

A policy is a function $\delta : \Sigma \to A$, which decides which action to perform in each state, and the value of a policy $\delta$ for a given state $s$ is given by

$$ V^\delta(s) = R(s, \delta(s)) + \beta \sum_{s'} P(s, \delta(s), s') \cdot V^\delta(s') $$ where $\beta$ is a discount factor between 0 and 1. The goal is to find to optimal policy $\delta^*$ which maximises the value for each state. In other words, the problem we are trying to solve is to calculate the function $V^*$ (corresponding to the value of $\delta^*$ such that: $$ V^*(s) = \max_{a} \,\,[R(s, a) + \beta \sum_{s'} P(s, a, s') \cdot V^*(s')] $$ Up to this point, I have no problem, but then when I look at how to solve this using linear programming, I find the following (PDF, page 5):

As in the game theory example above, we are confronted with the difficulty that we cannot use the max operator in a linear program. The solution is similar. We use the following linear program:

minimize $\sum_{s} V^*(s)$

subject to $\forall s, a \,\, V^*(s) \geq R(s, a) + \beta \sum_{s'} P(s, a, s') \cdot V^*(s') $

The argument about game theory is the following one (page 6 of the previous PDF):

There is an interesting trick in this linear program. We would like to write $u = max_i \sum^n_{j=1} p_j u_1(i, j)$, but this is not linear because of the max operator. So, instead, the linear program requires that $u$ is at least $\sum^n_{j=1} p_j u_1(i, j)$ for every i, thereby forcing it to be at least $max_i \sum^n_{j=1} p_j u_1(i, j)$. Then, in the optimal solution, u will be set exactly to $max_i \sum^n_{j=1} p_j u_1(i, j)$, because we try to minimize u.

My first problem is that I don't see why we using the max operator make the program non linear, and secondly, although this solution works, I am not sure to exactly understand why.

  • $\begingroup$ Disclaimer: I haven't really studied linear programming formally, so the answer might be obvious. $\endgroup$ – Charles Aug 17 '12 at 12:47

For your first question, consider the function $z = \max(x_1,x_2)$. Fix $x_2=1$ and let $x_1$ range over $[0,2]$. Then it is easy to see that $z$ is non-linear, for it is constant for $x_1 \in [0,1]$, but increasing for $x_2 \in [1,2]$.

As to getting around this problem, when you introduce the dummy variable $u$ with the conditions $u \geq \mathbf p_j^T \cdot \mathbf u \;$, notice that these are the only conditions in which $u$ appears. In other words, if $u$ is greater than all such linear combinations, there is nothing preventing it from being smaller. Therefore, in any optimal solution, $u$ must take on the value of one of the $\mathbf p_j^T \cdot \mathbf u \;$ (specifically, the one with the greatest value). Think of $u$ as a ceiling that drops down and settles on the highest point.

  • $\begingroup$ Many thanks for your answer! Two points though: what's the formal definition of linearity you're using for this? I can't seem to make the formal connection between your argument (which I understand) and this definition: en.wikipedia.org/wiki/Linear_map Also, I get now why we say that u should be greater and we want to minimize it, but I'm not sure to see why we want to minimize the sum of the V*, and not directly each V* ? $\endgroup$ – Charles Aug 18 '12 at 12:13
  • $\begingroup$ My pleasure. The definition of linearity is the same as the one in your link. Fixing $x_2=1$ effectively turns the function in my example into a function of one variable, $f(x_1)=\max(x_1,1)$. If f were linear, then we would have $f(a+b)=f(a)+f(b)$ for all $a,b$; however, $1 = f(0+1) \neq f(0)+f(1) = 1 +1$. $\endgroup$ – Théophile Aug 18 '12 at 17:19
  • $\begingroup$ The reason for taking the sum of the $v^*$ in the Markov decision problem is that you have multiple $\max$ operators. The goal is to choose a set of actions that will minimize the total cost for all states, in other words, the sum of the $v_s^*$, each of which is the maximum of several values. $\endgroup$ – Théophile Aug 18 '12 at 17:28
  • $\begingroup$ Thanks, I didn't think of instantiating one argument for the max function, it makes sense now. As for the sum of $v^*$, I guess my confusion comes from the fact that there might several combinations of $v^*$ that could minimize the sum, but then I realize that if you can minimize independently each $v^*$, then this is necessarily the only way to obtain the minimal sum. $\endgroup$ – Charles Aug 20 '12 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.