提出高效算法求解重复博弈中的局部斯塔克尔伯格均衡
Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
- 在平滑分析框架下设计多项式时间近似算法
- 运行时间与动作空间大小多项式相关，与精度反比指数相关
- 适用于主方与学习型代理长期互动的场景
为解决主方如何在与学习型代理的重复互动中最大化自身收益的问题，本文研究了主方与采用均值基础学习算法的代理之间的重复博弈。已有研究表明，在类似设定中计算或近似全局斯塔克尔伯格值可能需要随代理动作空间规模呈指数增长的轮次，导致计算上不可行。相比之下，本文转而关注局部斯塔克尔伯格均衡的计算，提出一种在平滑分析框架下的多项式时间近似方案（PTAS），可求得ε-近似的局部斯塔克尔伯格均衡。值得注意的是，该算法的运行时间在代理动作空间大小上为多项式，但在(1/ε)上为指数级——我们证明这一依赖关系是不可避免的。
原文摘要 · Abstract (English)
Motivated by the question of how a principal can maximize its utility in repeated interactions with a learning agent, we study repeated games between an principal and an agent employing a mean-based learning algorithm. Prior work has shown that computing or even approximating the global Stackelberg value in similar settings can require an exponential number of rounds in the size of the agent's action space, making it computationally intractable. In contrast, we shift focus to the computation of local Stackelberg equilibria and introduce an algorithm that, within the smoothed analysis framework, constitutes a Polynomial Time Approximation Scheme (PTAS) for finding an epsilon-approximate local Stackelberg equilibrium. Notably, the algorithm's runtime is polynomial in the size of the agent's action space yet exponential in (1/epsilon) - a dependency we prove to be unavoidable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。