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?

  • $\begingroup$ 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 $\endgroup$ – FisherDisinformation May 5 '16 at 17:32
  • $\begingroup$ Essentially, systems of equation? Thanks, that was quick. $\endgroup$ – cgo May 5 '16 at 17:53
  • $\begingroup$ @FisherDisinformation Pls note that the link is broken. $\endgroup$ – horaceT Jun 5 '17 at 16:33

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.

http://www.pnas.org/content/106/28/11478.full https://homes.cs.washington.edu/~todorov/papers/TodorovNIPS06.pdf


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.