Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
arXiv:2106.14866
Abstract
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.
arXiv commentProceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022
References in corpus (9)
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- Reinforcement Learning from Imperfect Demonstrations
- Repeated Inverse Reinforcement Learning
- Are sample means in multi-armed bandits positively or negatively biased?
- Why Adaptively Collected Data Have Negative Bias and How to Correct for It
- Best arm identification in multi-armed bandits with delayed feedback
- On-Policy Robot Imitation Learning from a Converging Supervisor
- Bandits with adversarial scaling
- Inverse Reinforcement Learning from a Gradient-based Learner