What are Linearly Solvable MDPs?

Markov Decision Process (MDP) is a formalism mainly used in artificial intelligence on the structure of decision making of a learner/agent. The aim is to find a suitable policy that maximizes the expected discounted reward that an agent gets. (Or in control theory, minimize the cost.)

I have seen this paper written by Todorov and Dvijotham (Inverse Optimal Control with Linear Solvable MDPs).

I am not sure what the words 'linearly solvable MDP' means. Do you have any insights? Any examples?

• Sometimes you can solve the MDP for the optimal policy in a matrix form. When this is not possible (matrix is non-invertible), you need to solve it iteratively. Check this out on page 10 (my AI prof's notes when I took the class):cs.mcgill.ca/~jpineau/comp424/Lectures/23MDP-preliminary.pdf – FisherDisinformation May 5 '16 at 17:32
• Essentially, systems of equation? Thanks, that was quick. – cgo May 5 '16 at 17:53
• @FisherDisinformation Pls note that the link is broken. – horaceT Jun 5 '17 at 16:33

$v(x) = \min_{u(x'|x)} \Big[q(x) + KL(u||p) + \mathop{\mathbb{E}}_{x'\sim u}[v(x')]\Big]$