arXiv cs.AI· Asr{\i}n Efe Yorulmaz, Tamer Ba\c{s}ar·· 12 小时前AI 评分26
在不完全信息博弈中学习并引导智能体：Learn-Compute-Steer 算法研究
Learning and Steering in Incomplete-Information Games
AI 导读
研究者提出 halving 类算法，可在仅获轨迹级结果反馈、不知智能体效用的情况下学习正规式博弈的效用差与扩展式博弈的条件延续价值差，样本复杂度为 Õ(ε⁻²)，与最坏情况下界在忽略对数因子时匹配。将其与拉格朗日形式结合形成的在线 Learn-Compute-Steer 算法交替执行学习、均衡计算与引导，以高概率达到 Õ(T⁻¹/⁴) 的直接性差距与最优性差距，时间平均支付为 Õ(T⁻¹/⁸)。
正文 · 原文
Abstract:In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of $\widetilde O(\varepsilon^{-2})$ that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of $\widetilde O(T^{-1/4})$, while time-average payments are of $\widetilde O(T^{-1/8})$.
| Comments: | 57 pages, 5 figures |
| Subjects: | Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Systems and Control (eess.SY); Optimization and Control (math.OC) |
| Cite as: | arXiv:2611.07589 [cs.GT] |
| (or arXiv:2611.07589v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2611.07589 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Asrin Efe Yorulmaz [view email]
[v1]
Thu, 5 Nov 2026 07:40:05 UTC (306 KB)
来源：arXiv cs.AI · arxiv.org