Efficient Φ-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
CoRR(2024)
摘要
Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich
[2023] and Peng and Rubinstein [2023] established an efficient algorithm
attaining at most ϵ swap regret over extensive-form strategy spaces of
dimension N in N^Õ(1/ϵ) rounds. On the other extreme,
Farina and Pipis [2023] developed an efficient algorithm for minimizing the
weaker notion of linear-swap regret in 𝗉𝗈𝗅𝗒(N)/ϵ^2 rounds. In
this paper, we take a step toward bridging the gap between those two results.
We introduce the set of k-mediator deviations, which generalize the untimed
communication deviations recently introduced by Zhang, Farina and Sandholm
[2024] to the case of having multiple mediators. We develop parameterized
algorithms for minimizing the regret with respect to this set of deviations in
N^O(k)/ϵ^2 rounds. This closes the gap in the sense that k=1
recovers linear swap regret, while k=N recovers swap regret. Moreover, by
relating k-mediator deviations to low-degree polynomials, we show that regret
minimization against degree-k polynomial swap deviations is achievable in
N^O(kd)^3/ϵ^2 rounds, where d is the depth of the game, assuming
constant branching factor. For a fixed degree k, this is polynomial for
Bayesian games and quasipolynomial more broadly when d = 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 N
– the usual balancedness assumption on the game tree.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要