设计算法让领导者在未知类型分布下，高效学习多跟随者博弈策略并最小化损失。
Learning to Play Multi-Follower Bayesian Stackelberg Games
- 通过类型或动作反馈，设计可适应不同信息条件的在线学习算法
- 类型反馈下实现近似与参与者数无关的次线性后悔上界
- 适用于竞标、定价等需应对不确定对手的场景
在多跟随者贝叶斯斯塔克尔伯格博弈中，领导者在 $L$ 个动作中选择混合策略，$n\ge1$ 个具有 $K$ 种私有类型的跟随者分别最优响应。领导者的最优策略依赖于跟随者类型分布。我们研究该问题的在线学习版本：领导者在 $T$ 轮中与 $n$ 个类型每轮从未知分布采样的跟随者交互。目标是最小化累积效用与最优策略之差的后悔值。在类型反馈（每轮观测到跟随者类型）下，设计算法实现独立类型分布时 $O\big(\sqrt{\min(L\log(nKA T), nK ) \cdot T}\big)$ 的后悔界，一般类型分布时 $O\big(\sqrt{\min(L\log(nKA T), K^n ) \cdot T}\big)$；有趣的是，这些上界不随 $n$ 多项式增长。在动作反馈（仅观测跟随者行动）下，算法后悔为 $O( \min(\sqrt{ n^L K^L A^{2L} L T \log T}, K^n\sqrt{ T } \log T ) )$。同时提供 $Ω(\sqrt{\min(L, nK)T})$ 的下界，几乎匹配类型反馈的上界。
原文摘要 · Abstract (English)
In a multi-follower Bayesian Stackelberg game, a leader plays a mixed strategy over $L$ actions to which $n\ge 1$ followers, each having one of $K$ possible private types, best respond. The leader's optimal strategy depends on the distribution of the followers' private types. We study an online learning version of this problem: a leader interacts for $T$ rounds with $n$ followers with types sampled from an unknown distribution every round. The leader's goal is to minimize regret, defined as the difference between the cumulative utility of the optimal strategy and that of the actually chosen strategies. We design learning algorithms for the leader under different feedback settings. Under type feedback, where the leader observes the followers' types after each round, we design algorithms that achieve $O\big(\sqrt{\min(L\log(nKA T), nK ) \cdot T} \big)$ regret for independent type distributions and $O\big(\sqrt{\min(L\log(nKA T), K^n ) \cdot T} \big)$ regret for general type distributions. Interestingly, those bounds do not grow with $n$ at a polynomial rate. Under action feedback, where the leader only observes the followers' actions, we design algorithms with $O( \min(\sqrt{ n^L K^L A^{2L} L T \log T}, K^n\sqrt{ T } \log T ) )$ regret. We also provide a lower bound of $Ω(\sqrt{\min(L, nK)T})$, almost matching the type-feedback upper bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。