Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917674293919744 |
|---|---|
| author | Kamoutsi, Angeliki Schmitt-Förster, Peter Sutter, Tobias Cevher, Volkan Lygeros, John |
| author_facet | Kamoutsi, Angeliki Schmitt-Förster, Peter Sutter, Tobias Cevher, Volkan Lygeros, John |
| contents | This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive epsilon-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15509 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces Kamoutsi, Angeliki Schmitt-Förster, Peter Sutter, Tobias Cevher, Volkan Lygeros, John Optimization and Control Machine Learning This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive epsilon-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples. |
| title | Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2405.15509 |