# Linear Program with expectations

I am trying to implement the Linear Programming Inverse Reinforcement Learning Algorithm 2 from Section 4, page 5 of Ng, A.Y. and Russell, S.J. 2000. Algorithms for inverse reinforcement learning. Proceedings of the 17th International Conference on Machine Learning (2000), 663–670.

A more straightforward formulation of the same algorithm can be found on this blog post in the section Linear programming for infinite state spaces. The linear programming problem is;

$$\text{maximize} \sum_{s\in \mathcal{S}_0} \text{min}_{a \in \mathcal{A}\setminus \pi(s)}p(\mathbb{E}_{s' \sim T(s'|s, \pi(s))}[V^\pi(s')] - \mathbb{E}_{s' \sim T(s'|s, a)}[V^\pi(s')]) \\ \text{such that } |\alpha_i| \leq 1, i = 1, \ldots d$$

Given that

$$V^\pi = \alpha_1V_1^\pi + \ldots + \alpha_dV_d^\pi$$

and

$$p(x) = x \text{ if } x \geq 0 \text{ else } p(x) = c \cdot x$$

I'm struggling to figure out how to transform this into standard form for a Linear Programming problem.

• I understand that the constraints on the $\alpha_i$ are simple to implement.
• I also understand how to deal with the $\text{min}()$ operator (by adding one extra optimisation variable per thing inside the brackets), and extra constraints to enforce the minimum condition).
• I believe the penalty function $p(x)$ can be implemented by creating two optimisation variables, one for each piece-wise part, and then adding extra constraints to ensure the function holds.

What I don't understand is how to combine the above three points, as well as the expectation operator. Can anyone provide any guidance on how to do this?

All the Linear Programming guides I could find online or at my library deal only with trivial cases (e.g. a min operator by itself, with no other complex nested functions). I don't understand how to combine multiple different functions when composing the LP problem.

The only implementation I could find of this online is at this GitHub repo, and they seem to make several simplifying assumptions not in the original algorithm, hence I am asking for help to implement this as the authors intended.

Thank you,

Update: @LinAlg thank you so much for the AIMMS textbook link - that book is so well written and easy to follow! I think I understand now that $p(x)$ can be replaced with $p(x) = min\{x, cx\}$ provided $c >= 1$. E.g. for $c = 2$ (the value used in the paper), I get;

Given this re-formulation, if I consider just one $a_m$ value, for $m \ne 1$, then everything inside the $p( \cdot )$ is just a vector of numbers that can be pre-computed to find the Linear Programming cost coefficients (of course, a hyper-parameter needs to be chosen to empirically calculate the expectation)... I will update again once I make some more progress.

• Whether the penalty function can be modeled depends on the value of $c$; you need $p(x)=\min\{x,cx\}$ (i.e., $c<1$). Otherwise you need binary variables, which makes the problem considerably harder. It should not be too hard to combine the different tricks you mention. Maybe you can show a very small example to show where you struggle. A package that could help you is YALMIP. – LinAlg Apr 18 '18 at 11:57
• @LinAlg thank you for your comment. Unfortunately the value of $c$ used in the paper is 2. Can you elaborate on what binary variables are? I have not heard of this concept in this context. The solver I've been using so far is cvxopt. I will see about expanding my question with a small example. – aaronsnoswell Apr 18 '18 at 12:51
• Binary variables can only take the value 0 or 1 (i.e., are discrete and not continuous). Section 7.6 of AIMMS Optimization Modeling has the reformulation you need. – LinAlg Apr 18 '18 at 12:56
• Thank you! I will have a look at that resource! – aaronsnoswell Apr 18 '18 at 13:59