Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents

This paper studies the repeated principal-agent bandit game, where the principal indirectly explores an unknown environment by incentivizing an agent to play arms. Unlike prior work that assumes a greedy agent with full knowledge of reward means, we consider a self-interested learning agent who iteratively updates reward estimates and may explore arbitrarily with some probability. As a warm-up, we first consider a self-interested learning agent without exploration. We propose algorithms for both i.i.d. and linear reward settings with bandit feedback in a finite horizon T , achieving regret bounds of O( √ T ) and O(T 2 /3 ), respectively. Specifically, these algorithms rely on a novel elimination framework coupled with new search algorithms which accommodate the uncertainty from the agent's learning behavior. We then extend the framework to handle an exploratory learning agent and develop an algorithm to achieve a O(T 2 /3 ) regret bound in i.i.d. reward setup by enhancing the robustness of our elimination framework to the potential agent exploration. Finally, when our agent model reduces to that in Dogan et al. (2023a), we propose an algorithm based on our robust framework, which achieves a O( √ T ) regret bound, significantly improving upon their O(T 11 /12 ) bound.