# 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

## 1 Answer

Linearly solvable MDPs are a continuous relaxation of normal MDPs. The differ from normal MDPs in that they don't use a traditional notion of an "action" variable and replace "action" with a next-state distribution u(x'|x). Normally in MDPs there is an action variable that indexes a distribution over next states. In LMDPs, however, the optimal policy is not a mapping of states to action variables, it is a next-state distribution which minimizes the accumulated state costs, q(x), of the agent traversing the state-space while minimizing a divergence cost between the distributions of the optimal policy, u(x'|x), and the passive uncontrolled dynamics of the agent p(x'|x) through the state space.

The linear bellman equation looks like this

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

which can be solved in polynomial time as a largest eigenvector problem. It has many other nice properties. You can also do inverse control with them or embed traditional MDPs inside of them.