Computational Intractability of Strategizing against Online Learners

Angelos Assos, Yuval Dagan, Nived Rajaraman · 2025

Read Computational Intractability of Strategizing against Online Learners by Angelos Assos, Yuval Dagan, Nived Rajaraman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-04202.txt.

Introduction

Angelos Assos, Yuval Dagan, and Nived Rajaraman prove hardness for planning against online learners in two thousand twenty-five. Online learners adapt their play over time in games and markets. A rival may ask how to best reply for long term gain. Fast replies are known for narrow cases like auctions.

The team shows no fast general method exists, barring a collapse of known classes. Their bound is strong, on the order of the full time span. Past work had a far weaker bound for a distinct learner type. Their learner is a standard no regret method in wide use. The bar is thus basic to game settings at large.

Catalog record

CREATORAngelos Assos, Yuval Dagan, Nived Rajaraman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-04202

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Intractability of Strategizing against Online Learners Angelos Assos, Yuval Dagan, Nived Rajaraman Abstract 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 ) \Omega(T) hardness bound, significantly strengthening previous work that only showed an additive Θ ⁡ ( 1 ) \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. 1 Introduction Online learning algorithms are often used in scenarios containing other learning agents. This includes repeated auctions where a seller and buyers learn how to construct auctions and to bid, respectively ( Nekipelov et al., 2015 ; Noti and Syrgkanis, 2021 ) ; Repeated contracts where a contractor learns how to set up contracts and agents learn how to take actions which maximize their revenue given these contracts ( Guruganesh et al., 2024 ) ; competing retailers that learn how to set prices and to adapt to the demand ( Du and Xiao, 2019 ; Calvano et al., 2020 ) ; Information design, where a principle wants to persuade an agent to take actions by deciding which information to share ( Chen and Lin, 2023 ) ; and many more examples exist. In all these scenarios, the agents are operating in the same environment and influence each other’s utilities. In this paper we assume that there are two agents, a learner and an optimizer , and we ask: Given that the learner is using a well-known learning algorithm to decide on his course of action, what is the best strategy for the optimizer to maximize her own reward (a.k.a. utility)? We formalize this setting under the lens of game theory : we assume that there exists some finite normal-form game between a learner and an optimizer, as explained below. Concretely, this means that the optimizer can take actions from some finite set \mathcal{A} , the learner can take actions from some finite set \mathcal{B} , and there are functions A and B which determine the reward of the agents: if the optimizer plays action {\bm{x}}\in\mathcal{A} and the learner plays action \bm{y}\in\mathcal{B} , the optimizer receives the reward A({\bm{x}},\bm{y})\in[-1,1] and the learner receives the reward B({\bm{x}},\bm{y})\in[-1,1] . We assume repeated game playing : this means that in every iteration t=1,\dots,T , the optimizer chooses an action {\bm{x}}(t) , the learner chooses an action \bm{y}(t) , and the agents receives reward A({\bm{x}}(t),\bm{y}(t)) and B({\bm{x}}(t),\bm{y}(t)) , respectively. The goal of each agent is to maximize their cumulative reward, summed over all the T iterations. For this purpose, the learner is using a standard online learning algorithm which determines which action to take in each iteration, whereas the optimizer’s goal is to play according to a strategy that maximizes her cumulative reward given the learner’s algorithm. Perhaps the most fundamental notion by which online learning algorithms are measured is regret . That is, the difference between the cumulative reward of the learner and the reward that they would gain if they played a fixed action and if the optimizer played the same sequence of actions, which is defined as \sum_{t=1}^{T}B({\bm{x}}(t),\bm{y}(t))-\max_{\bm{y}\in\mathcal{B}}\sum_{t=1}^{T}B({\bm{x}}(t),\bm{y})~. (1) A learning algorithm is no-regret if its regret behaves as o(T) and no-regret is a desirable property. A comprehensive theory has been developed around no-regret learning algorithms, and this includes the fundamental Hedge algorithm, also known as Multiplicative Weights Update (MWU), which is a simple algorithm that attains the asymptotically-optimal regret ( Littlestone and Warmuth, 1994 ; Freund and Schapire, 1997 ; Arora et al., 2012 ) . A disadvantage of the notion of regret is that it does not take into account scenarios where the other agent (optimizer, in our case) utilizes an adaptive algorithm. In spite of that, standard no-regret learners are still commonly used. This raises the question of how an optimizing agent can behave in environments where other agents use no-regret learning algorithms to make decisions, to maximize its reward. Braverman et al. (2018) showed that in the context of repeated auctions between one seller and one buyer, if the buyer is using a mean-based no-regret learning algorithm (such as Multiplicative Weights Update) then the seller can extract full welfare, which is more than what they could get if the learner was strategic. This line of work has been generalized in scenarios with one ( Deng et al., 2019a ; Rubinstein and Zhao, 2024 ) or multiple no-regret buyers ( Cai et al., 2023 ) . Beyond mechanism design, similar interactions between a learner and an optimizer were studied in repeated contracts ( Guruganesh et al., 2024 ) and in repeated information design (Bayesian Persuation) ( Lin and Chen, 2024 ) . In all these scenarios, an asymptotically-optimal strategy for the optimizer was developed. However, the solution in each instance was limited to the special game structure at hand. In general games, Deng et al. (2019b) show that the general optimization problem is essentially equivalent to solving a high-dimensional optimal control problem, however they do not provide an efficient algorithm. In this paper we show, in fact, that this is no coincidence: there is no efficient algorithm for the optimizer in general games, thereby resolving an open question of Guruganesh et al. (2024) . 1.1 Our Contribution Unlike prior work that we discussed above that has provided efficient algorithms only in structured settings or restricted cases, we establish a general computational hardness result. We prove that unless \mathsf{P}=\mathsf{NP} , no polynomial-time optimizer can compute a near-optimal strategy against a learner that uses a standard no-regret algorithm, specifically Hedge/MWU. This formally establishes that no general efficient strategy exists for the optimizer in repeated game settings. We formalize the optimization problem that we study. We assume that the learner’s algorithm is Hedge (MWU), and it is parameterized by a step-size \eta\geqslant 0 (cf. Definition 2.1 ). Any sequence of optimizer’s actions {\bm{x}}(1),\dots,{\bm{x}}(T) together with the learning rate \eta determine the learner’s actions. This determines the optimizer’s reward: R(\{{\bm{x}}(t):t\geqslant 1\})=\sum_{t=1}^{T}A({\bm{x}}(t),\bm{y}(t)) . The optimizer’s objective is stated below. Task 1 . Given T\in\mathbb{N} , given truth tables of the reward functions A,B\colon\mathcal{A}\times\mathcal{B}\to[-1,1] and given a step-size \eta for the learner, find a sequence of actions for the optimizer x(1),\dots,x(T)\in\mathcal{B} which approximately maximize its reward R(\{{\bm{x}}(t):t\geqslant 1\}) . Theorem 1.1 . Fix absolute constants \alpha,\beta\in(0,1] . Let T denote the horizon, suppose the learner plays Hedge with learning rate parameterized as \eta=1/T^{1-\alpha} (cf. Definition 2.1 ) and suppose that the number

Read the complete text