Apprenticeship learning using linear programming
Umar Syed, Michael Bowling, Robert E. Schapire · International Conference on Machine Learning · 2008
In apprenticeship learning, the goal is to learn a policy in a Markov decision process that is at least as good as a policy demonstrated by an expert. The difficulty arises in that the MDP's true reward function is assumed to be unknown. We show how to frame apprenticeship learning as a linear programming problem, and show that using an off-the-shelf LP solver to solve this problem results in a substantial improvement in running time over existing methods---up to two orders of magnitude faster in our experiments. Additionally, our approach produces stationary policies, while all existing methods for apprenticeship learning output policies that are "mixed", i.e. randomized combinations of stationary policies. The technique used is general enough to convert any mixed policy to a stationary policy.
Cited by 186 works. doi:10.1145/1390156.1390286
Authors
References
- Matrix Analysis
- Markov Decision Processes: Discrete Stochastic Dynamic Programming.
- Apprenticeship learning via inverse reinforcement learning
- Proof of Theorem 2
- Maximum margin planning
- Linear Optimization and Extensions: Theory and Algorithms
- A Game-Theoretic Approach to Apprenticeship Learning
- Handbook of Markov decision processes : methods and applications
- Computing Robust Counter-Strategies
- Stable Dual Dynamic Programming