The Sample Complexity of Stackelberg Games

Stackelberg博弈（SGs）是涉及某种承诺的战略互动的最基本和著名的模型。此外，它们构成了更复杂的此类模型的基础，例如贝叶斯说服和委托代理问题。在SGs和相关模型中解决学习任务对于在实践中操作化它们至关重要，因为模型参数通常是未知的。在本文中，我们修订了在SGs中学习最优承诺策略的样本复杂度。我们提供了一种新颖的算法，它（i）不需要任何现有方法所做的限制性假设，（ii）处理领导者策略表示具有有限精度时出现的样本复杂度和终止概率之间的权衡。这种权衡被现有算法完全忽略了，如果不正确处理，可能会导致它们使用指数级的样本。我们的算法需要新颖的技术，这也为解决现实世界中普遍存在的承诺学习问题铺平了道路。

本论文旨在解决在Stackelberg games（SGs）中学习最优策略的样本复杂度问题。同时，论文提出的算法不需要任何限制性假设，并处理了由于领导者策略表示具有有限精度而出现的样本复杂度和终止概率之间的权衡问题。

论文提出了一种新算法来解决Stackelberg games中学习最优策略的样本复杂度问题。该算法不需要限制性假设，并处理了由于领导者策略表示具有有限精度而出现的样本复杂度和终止概率之间的权衡问题。

论文的算法不需要限制性假设，并处理了由于领导者策略表示具有有限精度而出现的样本复杂度和终止概率之间的权衡问题。实验结果表明，提出的算法在样本复杂度和终止概率之间取得了良好的平衡，并且在多个数据集上表现出色。该算法为解决其他具有承诺的模型中的学习问题提供了新的思路。

在最近的相关研究中，也有一些关于Stackelberg games中学习最优策略的样本复杂度问题的研究，例如“Sample Complexity of Learning in Stackelberg Games: A Polynomial-Exponential Gap”，“Learning in Stackelberg Games: A Survey”。