Computational Intractability of Strategizing against Online Learners
Not on the map. Why?
Abstract (arXiv)
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 mathsfP = mathsfNP, 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 Omega(T) hardness bound, significantly strengthening previous work that only showed an additive Theta(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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 25 of its 41 references that are in the map. First posted on arXiv 6 Mar 2025.
Builds on
25 of 41 references.
References · 25
- 2015Fast Convergence of Regularized Learning in Gamescited by 150
- 2021Near-Optimal No-Regret Learning in General Gamescited by 85
- 2019Strategizing against No-regret Learnerscited by 50
- 2017Selling to a No-Regret Buyercited by 43
- 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
- 2022Strategizing against Learners in Bayesian Gamescited by 34
- 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
- 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
- 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
- 2015Econometrics for Learning Agentscited by 23
- 2024Contracting with a Learning Agentcited by 23
- 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
13 more
- 2023Is Learning in Games Good for the Learners?cited by 20
- 2023Selling to Multiple No-Regret Buyerscited by 19
- 2024Pareto-Optimal Algorithms for Learning in Gamescited by 16
- 2020Bid Prediction in Repeated Auctions with Learningcited by 14
- 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
- 2024Strategizing against No-Regret Learners in First-Price Auctionscited by 8
- 2024Maximizing utility in multi-agent environments by anticipating the behavior of other learnerscited by 8
- 2023Persuading a Behavioral Agent: Approximately Best Responding and Learningcited by 7
- 2024Strategically-Robust Learning Algorithms for Bidding in First-Price Auctionscited by 7
- 2023Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Gamescited by 6
- 2024Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactionscited by 5
- 2023The Optimal Strategy against Hedge Algorithm in Repeated Gamescited by 2
- 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.