arXiv:2412.16318cs.LGstat.ML2024-12ICML被引 3

让会探索的学习型代理在激励下玩老虎机,设计新算法降低长期损失。

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

  • 用新消除框架+搜索算法应对代理学习带来的不确定性
  • 在独立同分布奖励下实现约 $T^{2/3}$ 的后悔上界
  • 适用于在线市场等需自主探索的激励场景

我们研究重复的主-代理老虎机博弈,其中主方通过设定激励间接与未知环境交互。现有工作通常假设代理完全知晓奖励均值并始终贪婪行为,但在许多在线市场中,代理需学习环境且会进行探索。为此,我们建模一个自利且具探索行为的学习代理:其迭代更新奖励估计,并以一定概率随机探索或选择估计奖励加激励最大化的臂。作为基础,我们先考虑无探索的自利学习代理,在 i.i.d. 和线性奖励设置下分别实现 $ ilde{O}( oot T floor)$ 与 $ ilde{O}(T^{2/3})$ 的后悔界。核心是基于新颖的消除框架与新设计的搜索算法,适应代理学习带来的不确定性。随后,我们将框架扩展至处理探索行为代理,在 i.i.d. 奖励下设计算法达到 $ ilde{O}(T^{2/3})$ 后悔界,增强消除框架对代理探索的鲁棒性。最后,当将代理行为还原为 (Dogan et al., 2023a) 所研究情形时,基于该鲁棒框架提出算法,实现 $ ilde{O}( oot T floor)$ 后悔界,显著优于其 $ ilde{O}(T^{11/12})$ 的结果。

原文摘要 · Abstract (English)

We study the repeated principal-agent bandit game, where the principal indirectly interacts with the unknown environment by proposing incentives for the agent to play arms. Most existing work assumes the agent has full knowledge of the reward means and always behaves greedily, but in many online marketplaces, the agent needs to learn the unknown environment and sometimes explore. Motivated by such settings, we model a self-interested learning agent with exploration behaviors who iteratively updates reward estimates and either selects an arm that maximizes the estimated reward plus incentive or explores arbitrarily with a certain 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 $\widetilde{O}(\sqrt{T})$ and $\widetilde{O}( T^{2/3} )$, respectively. Specifically, these algorithms are established upon a novel elimination framework coupled with newly-developed search algorithms which accommodate the uncertainty arising from the learning behavior of the agent. We then extend the framework to handle the exploratory learning agent and develop an algorithm to achieve a $\widetilde{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 reducing our agent behaviors to the one studied in (Dogan et al., 2023a), we propose an algorithm based on our robust framework, which achieves a $\widetilde{O}(\sqrt{T})$ regret bound, significantly improving upon their $\widetilde{O}(T^{11/12})$ bound.

强化学习博弈论在线学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。