Research map / Learning theory and algorithms / Sample complexity
Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the inverse feasibility set for discounted continuous-state, continuous-action MDPs via occupation measures and LP duality, then uses the scenario approach with linear function approximators to obtain epsilon-optimal cost recovery with PAC sample-complexity and finite-sample bounds.
Problem
Inverse reinforcement learning in MDPs with continuous state and action spaces: recovering a cost function from optimal expert behavior, with ill-posedness and infinite-dimensional LP formulations and no formal guarantees.
Approach
Characterize inverse feasibility through occupation measures, linear duality and complementary slackness for Lipschitz continuous MDPs, add a linear normalization constraint to avoid trivial solutions, and approximate the resulting infinite-dimensional LP with linear function approximators via the scenario approach, with sampled expert trajectories and a generative model for the sample-based versi
Key results
- Theoretical guarantee: with N >= N(n_c+n_u+1, g(eps/L), delta) scenario samples, with probability at least 1-delta the recovered cost lies in C^{eps_approx+eps}(pi_E).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the linear normalization constraint | inverse feasibility formulation · continuous-state and continuous-action MDPs | constant-cost exclusion | Helped |
| restrict cost and value functions to finite-dimensional basis classes | inverse program · continuous-state and continuous-action MDPs | inverse-feasibility error: ε_approx | Mixed |
| use linearly dense bases and increase n_c, n_u, and θ | inverse program · continuous-state and continuous-action MDPs | inverse-feasibility error: 0 | Helped |
| sample state-action constraints with the scenario approach | inverse program · continuous-state and continuous-action MDPs | inverse-feasibility error: ε_approx+ε | Helped |
| use expert demonstrations and generative-model samples instead of full access to the expert policy and transition law | sample-based inverse program · continuous-state and continuous-action MDPs | inverse-feasibility error: ε_approx+ε | Helped |
| increase the state-action dimension | scenario approach · continuous-state and continuous-action MDPs | sample complexity: ε^{-dim(X×A)} | Hurt |
Surprising findings
- Scenario sample complexity scales as eps^{-dim(X x A)}, i.e. exponential in dimension (curse of dimensionality).
Limitations
- Sample size scales exponentially with state-action dimension
- Requires Lipschitz MDP assumptions and compact spaces
- No empirical experiments reported
Experimental setup
Metrics: sample complexity epsilon-inverse feasibility suboptimality bound
Builds on: LP approach to MDPs scenario approach Lagrangian duality
Closest papers by meaning
- Identifiability in inverse reinforcement learning (NeurIPS 2021 · similarity 0.90)
- On the Correctness and Sample Complexity of Inverse Reinforcement Learning (NeurIPS 2019 · similarity 0.90)
- How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach (NeurIPS 2024 · similarity 0.90)
- Inverse Reinforcement Learning From Like-Minded Teachers (AAAI 2021 · similarity 0.89)
- Recent Advancements in Inverse Reinforcement Learning (AAAI 2024 · similarity 0.88)
- Hybrid Inverse Reinforcement Learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.