# Stochastic convex optimization for provably efficient apprenticeship learning

arXiv: https://arxiv.org/abs/2201.00039 · HTML: https://mlsanity.com/paper/2201.00039/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 5 of its 26 references that are in the map.
- First posted on arXiv 31 Dec 2021.

## Placed in

- Offline RL and imitation learning from data / [Inverse reinforcement learning](https://mlsanity.com/offlinerl/inverse-reinforcement-learning/)

## Builds on (most cited first, 5 of 5)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Model-Free Imitation Learning with Policy Optimization](https://mlsanity.com/paper/1605.08478/) (2016)
- [Linear Programming for Large-Scale Markov Decision Problems](https://mlsanity.com/paper/1402.6763/) (2014)
- [Large-Scale Markov Decision Problems via the Linear Programming Dual](https://mlsanity.com/paper/1901.01992/) (2019)

## Built on by (most cited first, 1 of 1)

- [Cross apprenticeship learning framework: Properties and solution approaches](https://mlsanity.com/paper/2209.02424/) (2022)

## Abstract (arXiv)

We consider large-scale Markov decision processes (MDPs) with an unknown cost function and employ stochastic convex optimization tools to address the problem of imitation learning, which consists of learning a policy from a finite set of expert demonstrations. We adopt the apprenticeship learning formalism, which carries the assumption that the true cost function can be represented as a linear combination of some known features. Existing inverse reinforcement learning algorithms come with strong theoretical guarantees, but are computationally expensive because they use reinforcement learning or planning algorithms as a subroutine. On the other hand, state-of-the-art policy gradient based algorithms (like IM-REINFORCE, IM-TRPO, and GAIL), achieve significant empirical success in challenging benchmark tasks, but are not well understood in terms of theory. With an emphasis on non-asymptotic guarantees of performance, we propose a method that directly learns a policy from expert demonstrations, bypassing the intermediate step of learning the cost function, by formulating the problem as a single convex optimization problem over occupancy measures. We develop a computationally efficient algorithm and derive high confidence regret bounds on the quality of the extracted policy, utilizing results from stochastic convex optimization and recent works in approximate linear programming for solving forward MDPs.