Research map / Bandits and online learning / RL theory and MDPs
Imitation Learning in Discounted Linear MDPs without exploration assumptions
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.
Proposes ILARL, an imitation learning algorithm for infinite-horizon linear MDPs with expert demonstrations that reduces to adversarial-loss online learning, removing persistent excitation and improving the MDP-interaction bound's epsilon dependence from epsilon^-5 to epsilon^-4; also BRIG for finite horizon.
Problem
Imitation learning from a fixed set of expert demonstrations in infinite-horizon linear MDPs, where prior work required a persistent excitation assumption and had worse sample complexity in epsilon.
Approach
Connects imitation learning to full-information online learning in adversarial linear MDPs: a projected OGD player updates the cost weights while a policy-iteration-style mirror descent player with optimistic on-policy evaluation controls policy regret, yielding the first adversarial infinite-horizon linear MDP result without exploration assumptions.
Key results
- ILARL improves over PPIL in MDP-trajectory efficiency and matches the expert performance with a stochastic expert in the continuous gridworld experiments (qualitative, from figures).
- Theoretical sample complexity for infinite-horizon ILARL is O(d^3/((1-gamma)^8 eps^4)) MDP trajectories versus O(d^2/(beta^6 (1-gamma)^9 eps^5)) for PPIL.
- Finite-horizon BRIG improves MDP trajectory complexity to O(H^4 d^3 eps^-2), versus O(H^6 d^3 eps^-4) from the adversarial-MDP baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ILARL instead of PPIL | Infinite-horizon Linear MDP imitation learning · Infinite-horizon Linear MDP | MDP trajectory sample-complexity dependence on ε: \mathcal{O}(\epsilon^{-5}) -> \mathcal{O} (\epsilon^{-4}) | Helped |
| Remove the persistent excitation requirement | ILARL · Infinite-horizon Linear MDP | validity of the sample-complexity guarantee | Helped |
| Use BRIG with a greedy best-response policy update and the next cost revealed in advance | Finite-horizon imitation learning · Episodic Linear MDP | MDP trajectory sample-complexity dependence on ε: \widetilde{\mathcal{O}}(H^6 \log \abs{\mathcal{A}} d^3 \epsilon^{-4} \log^2(1/ \delta)) -> \widetilde{\mathcal{O}}(H^4 d | Helped |
| Use ILARL instead of behavioural cloning | Imitation learning with a stochastic expert · Continuous gridworld, τ_E=1 | normalized return | Helped |
| Use ILARL instead of behavioural cloning | Imitation learning with a stochastic expert · Continuous gridworld, τ_E=2 | normalized return | Helped |
| Use ILARL instead of other evaluated algorithms | Imitation learning · Continuous gridworld, MDP trajectories | MDP trajectory efficiency | Helped |
| Use greedy best-response policies in the infinite-horizon setting | ILARL · Infinite-horizon Linear MDP | ability to control the regret term | Hurt |
Surprising findings
- ILARL matches or exceeds expert performance with a stochastic expert, while REIRL and ILARL are the only methods that beat behavioural cloning at tau_E=2.
- Best-response (greedy) policy updates help finite horizon but the same idea cannot be used in the infinite horizon case.
Limitations
- Infinite-horizon bound depends on the regularized policy update and the best-response trick cannot be used there.
- Bound still has worse dependence on (1-gamma) and d than the finite horizon result.
- Experiments are small continuous gridworld with a single stochastic expert setting.
Experimental setup
Datasets: expert demonstrations collected from a stochastic expert on a continuous gridworld
Benchmarks: continuous gridworld
Metrics: normalized return
Baselines: Behavioural cloning PPIL GAIL AIRL REIRL IQLearn
Builds on: PPIL LSVI-UCB OGAIL
Closest papers by meaning
- Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning (NeurIPS 2024 · similarity 0.88)
- IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic (ICML 2025 · similarity 0.87)
- Zero-Shot Offline Imitation Learning via Optimal Transport (ICML 2025 · similarity 0.86)
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.86)
- Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms (ICML 2024 · similarity 0.86)
- Imitation Learning from Observation with Automatic Discount Scheduling (ICLR 2024 · similarity 0.86)
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.