# Computational Intractability of Strategizing against Online Learners

arXiv: https://arxiv.org/abs/2503.04202 · HTML: https://mlsanity.com/paper/2503.04202/

## 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 (most cited first, 25 of 25)

- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Selling to Multiple No-Regret Buyers](https://mlsanity.com/paper/2307.04175/) (2023)
- [Pareto-Optimal Algorithms for Learning in Games](https://mlsanity.com/paper/2402.09549/) (2024)
- [Bid Prediction in Repeated Auctions with Learning](https://mlsanity.com/paper/2007.13193/) (2020)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Persuading a Behavioral Agent: Approximately Best Responding and Learning](https://mlsanity.com/paper/2302.03719/) (2023)
- [Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions](https://mlsanity.com/paper/2402.07363/) (2024)
- [Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games](https://mlsanity.com/paper/2306.05216/) (2023)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [The Optimal Strategy against Hedge Algorithm in Repeated Games](https://mlsanity.com/paper/2312.09472/) (2023)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)

## Built on by (most cited first, 2 of 2)

- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent](https://mlsanity.com/paper/2510.22471/) (2025)

## 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.