Timezone: »
Poster
On the Correctness and Sample Complexity of Inverse Reinforcement Learning
Abi Komanduru · Jean Honorio
Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #223
Inverse reinforcement learning (IRL) is the problem of finding a reward function that generates a given optimal policy for a given Markov Decision Process. This paper looks at an algorithmic-independent geometric analysis of the IRL problem with finite states and actions. A L1-regularized Support Vector Machine formulation of the IRL problem motivated by the geometric analysis is then proposed with the basic objective of the inverse reinforcement problem in mind: to find a reward function that generates a specified optimal policy. The paper further analyzes the proposed formulation of inverse reinforcement learning with $n$ states and $k$ actions, and shows a sample complexity of $O(d^2 \log (nk))$ for transition probability matrices with at most $d$ non-zeros per row, for recovering a reward function that generates a policy that satisfies Bellman's optimality condition with respect to the true transition probabilities.
Author Information
Abi Komanduru (Purdue University)
Jean Honorio (Purdue University)
More from the Same Authors
-
2021 Spotlight: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio -
2021 Poster: Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees »
Gregory Dexter · Kevin Bello · Jean Honorio -
2021 Poster: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio -
2020 Poster: Fairness constraints can help exact inference in structured prediction »
Kevin Bello · Jean Honorio -
2019 Poster: Learning Bayesian Networks with Low Rank Conditional Probability Tables »
Adarsh Barik · Jean Honorio -
2019 Poster: Exact inference in structured prediction »
Kevin Bello · Jean Honorio -
2018 Poster: Learning latent variable structured prediction models with Gaussian perturbations »
Kevin Bello · Jean Honorio -
2018 Poster: Information-theoretic Limits for Community Detection in Network Models »
Chuyang Ke · Jean Honorio -
2018 Poster: Computationally and statistically efficient learning of causal Bayes nets using path queries »
Kevin Bello · Jean Honorio -
2017 Poster: Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity »
Asish Ghoshal · Jean Honorio