# Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 28 Jun 2021.

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

- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [One-Shot Visual Imitation Learning via Meta-Learning](https://mlsanity.com/paper/1709.04905/) (2017)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Reward-rational (implicit) choice: A unifying formalism for reward learning](https://mlsanity.com/paper/2002.04833/) (2020)
- [Imitation Learning from Imperfect Demonstration](https://mlsanity.com/paper/1901.09387/) (2019)
- [Reinforcement Learning from Imperfect Demonstrations](https://mlsanity.com/paper/1802.05313/) (2018)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [Repeated Inverse Reinforcement Learning](https://mlsanity.com/paper/1705.05427/) (2017)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [Are sample means in multi-armed bandits positively or negatively biased?](https://mlsanity.com/paper/1905.11397/) (2019)
- [The Assistive Multi-Armed Bandit](https://mlsanity.com/paper/1901.08654/) (2019)
- [On-Policy Robot Imitation Learning from a Converging Supervisor](https://mlsanity.com/paper/1907.03423/) (2019)
- [On conditional versus marginal bias in multi-armed bandits](https://mlsanity.com/paper/2002.08422/) (2020)
- [Bandit Models of Human Behavior: Reward Processing in Mental Disorders](https://mlsanity.com/paper/1706.02897/) (2017)
- [Inverse Reinforcement Learning from a Gradient-based Learner](https://mlsanity.com/paper/2007.07812/) (2020)
- [Bandits with adversarial scaling](https://mlsanity.com/paper/2003.02287/) (2020)
- [Deep PQR: Solving Inverse Reinforcement Learning using Anchor Actions](https://mlsanity.com/paper/2007.07443/) (2020)

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

- [Diffusion Models for Black-Box Optimization](https://mlsanity.com/paper/2306.07180/) (2023)
- [Generative Pretraining for Black-Box Optimization](https://mlsanity.com/paper/2206.10786/) (2022)
- [Inverse Contextual Bandits: Learning How Behavior Evolves over Time](https://mlsanity.com/paper/2107.06317/) (2021)
- [Reliable Conditioning of Behavioral Cloning for Offline Reinforcement Learning](https://mlsanity.com/paper/2210.05158/) (2022)
- [Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selection](https://mlsanity.com/paper/2204.11910/) (2022)
- [Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?](https://mlsanity.com/paper/2507.11891/) (2025)
- [Eliciting Risk Aversion with Inverse Reinforcement Learning via Interactive Questioning](https://mlsanity.com/paper/2308.08427/) (2023)
- [MERMAIDE: Learning to Align Learners using Model-Based Meta-Learning](https://mlsanity.com/paper/2304.04668/) (2023)

## Abstract (arXiv)

We introduce the "inverse bandit" problem of estimating the rewards of a multi-armed bandit instance from observing the learning process of a low-regret demonstrator. Existing approaches to the related problem of inverse reinforcement learning assume the execution of an optimal policy, and thereby suffer from an identifiability issue. In contrast, we propose to leverage the demonstrator's behavior en route to optimality, and in particular, the exploration phase, for reward estimation. We begin by establishing a general information-theoretic lower bound under this paradigm that applies to any demonstrator algorithm, which characterizes a fundamental tradeoff between reward estimation and the amount of exploration of the demonstrator. Then, we develop simple and efficient reward estimators for upper-confidence-based demonstrator algorithms that attain the optimal tradeoff, showing in particular that consistent reward estimation -- free of identifiability issues -- is possible under our paradigm. Extensive simulations on both synthetic and semi-synthetic data corroborate our theoretical results.