提出新算法，让领导者在有信息条件下更快学好策略。
Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
- 将问题转为线性上下文贝叶斯，通过逆推得领导者策略
- 实现O(T^1/2)遗憾，优于之前的O(T^2/3)
- 适用于拍卖竞价与在线说服场景，实测效果更好
我们研究领导者与一系列追随者之间的在线学习问题，其中领导者在每轮中观察上下文信息并选择混合策略，随后追随者进行最优回应。我们为领导者设计了学习算法，在仅获得赌博反馈的情况下实现了O(T^{1/2})的遗憾，优于此前最优的O(T^{2/3})。算法核心是将问题转化为效用空间中的线性上下文贝叶斯问题：每轮由线性上下文贝叶斯算法推荐一个效用向量，我们的算法将其反演以确定领导者的混合策略。我们还将算法扩展至领导者效用函数未知的情形，并应用于带侧信息的第二价格拍卖出价和具有公共与私有状态的在线贝叶斯说服问题。最后，我们在数值模拟中观察到，该算法性能显著优于已有方法。
原文摘要 · Abstract (English)
We study the problem of online learning in Stackelberg games with side information between a leader and a sequence of followers. In every round the leader observes contextual information and commits to a mixed strategy, after which the follower best-responds. We provide learning algorithms for the leader which achieve $O(T^{1/2})$ regret under bandit feedback, an improvement from the previously best-known rates of $O(T^{2/3})$. Our algorithms rely on a reduction to linear contextual bandits in the utility space: In each round, a linear contextual bandit algorithm recommends a utility vector, which our algorithm inverts to determine the leader's mixed strategy. We extend our algorithms to the setting in which the leader's utility function is unknown, and also apply it to the problems of bidding in second-price auctions with side information and online Bayesian persuasion with public and private states. Finally, we observe that our algorithms empirically outperform previous results on numerical simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。