leader在不知对手类型时，仍能通过学习实现无悔策略
Learning in Bayesian Stackelberg Games With Unknown Follower's Types
- 设计新算法应对未知对手类型下的博弈学习问题
- 证明仅知对手行动时无法实现无悔，需获知对手类型才能做到
- 提出新算法，在类型反馈下实现√T量级的后悔值
我们研究贝叶斯斯塔克尔伯格博弈中的在线学习问题，其中领导者与一个私有类型未知的追随者反复交互，且每轮其类型独立从未知分布中抽取。目标是设计算法使领导者相对于已知游戏情况下的最优承诺策略，实现最小化后悔。本文首次考虑最现实的情形：领导者对追随者类型（即可能的收益）一无所知，这比通常假设已知追随者类型的情况带来更大挑战。首先，我们证明了一个强负面结果：仅通过行动反馈（即领导者仅观察到追随者的最佳响应）时，无法实现无悔。因此，我们转向更易处理的类型反馈模型（即追随者类型也可见）。在此设定下，我们提出一种无悔算法，其后悔值为$ ilde{O}(\ oot\of{T})$（忽略其他参数依赖）。
原文摘要 · Abstract (English)
We study online learning in Bayesian Stackelberg games, where a leader repeatedly interacts with a follower whose unknown private type is independently drawn at each round from an unknown probability distribution. The goal is to design algorithms that minimize the leader's regret with respect to always playing an optimal commitment computed with knowledge of the game. We consider, for the first time to the best of our knowledge, the most realistic case in which the leader does not know anything about the follower's types, i.e., the possible follower payoffs. This raises considerable additional challenges compared to the commonly studied case in which the payoffs of follower types are known. First, we prove a strong negative result: no-regret is unattainable under action feedback, i.e., when the leader only observes the follower's best response at the end of each round. Thus, we focus on the easier type feedback model, where the follower's type is also revealed. In such a setting, we propose a no-regret algorithm that achieves a regret of $\widetilde{O}(\sqrt{T})$, when ignoring the dependence on other parameters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。