证明了在在线学习环境下，无法高效找到最优应对策略。
Computational Intractability of Strategizing against Online Learners
- 证明了针对标准无悔算法的优化策略计算困难
- 除非P=NP，否则无法在多项式时间内找到近优解
- 适用于研究博弈论与在线学习交叉问题的研究者
在线学习算法广泛应用于重复拍卖、合同设计和定价竞争等多智能体场景，其中各智能体随时间调整策略。关键问题是：一个优化智能体如何最好地响应学习型智能体以提升自身长期收益？尽管已有研究在特定场景（如结构化拍卖）中提出高效算法，但尚未发现通用高效算法。本文证明：除非P = NP，否则任何多项式时间优化器都无法计算出对抗使用标准无悔算法（即乘法权重更新，MWU）的学习者时的近优策略。该结果建立了Ω(T)的计算难解性下界，显著强于此前仅表明加性Θ(1)不可能性的结果。更重要的是，以往结果针对非无悔算法（如虚构博弈），而本文首次证明了对广泛使用的无悔算法也存在计算障碍，确立了在一般博弈设置中寻找最优策略的根本性计算瓶颈。
原文摘要 · Abstract (English)
Online learning algorithms are widely used in strategic multi-agent settings, including repeated auctions, contract design, and pricing competitions, where agents adapt their strategies over time. A key question in such environments is how an optimizing agent can best respond to a learning agent to improve its own long-term outcomes. While prior work has developed efficient algorithms for the optimizer in special cases - such as structured auction settings or contract design - no general efficient algorithm is known. In this paper, we establish a strong computational hardness result: unless $\mathsf{P} = \mathsf{NP}$, no polynomial-time optimizer can compute a near-optimal strategy against a learner using a standard no-regret algorithm, specifically Multiplicative Weights Update (MWU). Our result proves an $Ω(T)$ hardness bound, significantly strengthening previous work that only showed an additive $Θ(1)$ impossibility result. Furthermore, while the prior hardness result focused on learners using fictitious play - an algorithm that is not no-regret - we prove intractability for a widely used no-regret learning algorithm. This establishes a fundamental computational barrier to finding optimal strategies in general game-theoretic settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。