Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Wenshuo Guo;Kumar Krishna Agrawal;Aditya Grover;Vidya Muthukumar;A. Pananjady
中科院分区：
文献类型：
--
作者：
Wenshuo Guo;Kumar Krishna Agrawal;Aditya Grover;Vidya Muthukumar;A. Pananjady
我们介绍了“逆土匪”的问题，估计奖励的多臂土匪的情况下，从观察学习过程中的低遗憾演示。现有的方法，逆强化学习的相关问题假设的最优策略的执行，从而遭受可识别性问题。相比之下，我们建议利用演示的行为途中的最优性，特别是探索阶段，奖励估计。我们开始通过建立一个一般的信息理论的下界下，这种范式适用于任何演示算法，其特征是奖励估计和演示的探索量之间的基本权衡。然后，我们开发了简单而有效的奖励估计的上置信度为基础的演示算法，达到最佳的权衡，特别是一致的奖励估计-免费的可识别性问题-在我们的范例是可能的。大量的模拟合成和半合成数据证实了我们的理论结果。
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.