Timezone: »

 
Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
Wenshuo Guo · Kumar Agrawal · Aditya Grover · Vidya Muthukumar · Ashwin Pananjady

@
in Workshop on Reinforcement Learning Theory »

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, our paradigm leverages the demonstrator's behavior en route to optimality, and in particular, the exploration phase, to obtain consistent reward estimates. We develop simple and efficient reward estimation procedures for demonstrations within a class of upper-confidence-based algorithms, showing that reward estimation gets progressively easier as the regret of the algorithm increases. We match these upper bounds with information-theoretic lower bounds that apply to any demonstrator algorithm, thereby characterizing the optimal tradeoff between exploration and reward estimation. Extensive simulations on both synthetic and semi-synthetic data corroborate our theoretical results.

Author Information

Wenshuo Guo (UC Berkeley)
Kumar Agrawal (UC Berkeley)
Aditya Grover (Stanford University)
Vidya Muthukumar (UC Berkeley)
Ashwin Pananjady (UC Berkeley)

More from the Same Authors