# Selective Sampling and Imitation Learning via Online Regression

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 11 Jul 2023.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Inverse Preference Learning: Preference-based RL without a Reward Function](https://mlsanity.com/paper/2305.15363/) (2023)
- [Behavior Retrieval: Few-Shot Imitation Learning by Querying Unlabeled Datasets](https://mlsanity.com/paper/2304.08742/) (2023)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Active Imitation Learning with Noisy Guidance](https://mlsanity.com/paper/2005.12801/) (2020)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [On the Sample Complexity of Reinforcement Learning with Policy Space Generalization](https://mlsanity.com/paper/2008.07353/) (2020)
- [Masked Imitation Learning: Discovering Environment-Invariant Modalities in Multimodal Demonstrations](https://mlsanity.com/paper/2209.07682/) (2022)
- [Active Imitation Learning from Multiple Non-Deterministic Teachers: Formulation, Challenges, and Algorithms](https://mlsanity.com/paper/2006.07777/) (2020)

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

- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [System-Aware Unlearning Algorithms: Use Lesser, Forget Faster](https://mlsanity.com/paper/2506.06073/) (2025)
- [Contextual Bandits and Imitation Learning via Preference-Based Active Queries](https://mlsanity.com/paper/2307.12926/) (2023)
- [Online Learning with Unknown Constraints](https://mlsanity.com/paper/2403.04033/) (2024)
- [Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning](https://mlsanity.com/paper/2412.07057/) (2024)
- [Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms](https://mlsanity.com/paper/2312.16860/) (2023)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Active Learning via Regression Beyond Realizability](https://mlsanity.com/paper/2506.00316/) (2025)
- [The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification](https://mlsanity.com/paper/2510.01020/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design](https://mlsanity.com/paper/2608.01378/) (2026)

## Abstract (arXiv)

We consider the problem of Imitation Learning (IL) by actively querying noisy expert for feedback. While imitation learning has been empirically successful, much of prior work assumes access to noiseless expert feedback which is not practical in many applications. In fact, when one only has access to noisy expert feedback, algorithms that rely on purely offline data (non-interactive IL) can be shown to need a prohibitively large number of samples to be successful. In contrast, in this work, we provide an interactive algorithm for IL that uses selective sampling to actively query the noisy expert for feedback. Our contributions are twofold: First, we provide a new selective sampling algorithm that works with general function classes and multiple actions, and obtains the best-known bounds for the regret and the number of queries. Next, we extend this analysis to the problem of IL with noisy expert feedback and provide a new IL algorithm that makes limited queries. Our algorithm for selective sampling leverages function approximation, and relies on an online regression oracle w.r.t.~the given model class to predict actions, and to decide whether to query the expert for its label. On the theoretical side, the regret bound of our algorithm is upper bounded by the regret of the online regression oracle, while the query complexity additionally depends on the eluder dimension of the model class. We complement this with a lower bound that demonstrates that our results are tight. We extend our selective sampling algorithm for IL with general function approximation and provide bounds on both the regret and the number of queries made to the noisy expert. A key novelty here is that our regret and query complexity bounds only depend on the number of times the optimal policy (and not the noisy expert, or the learner) go to states that have a small margin.