Computational Hardness of Near-Optimal Steering Against Known Learning Dynamics

We study the computational complexity of determining an optimal strategy sequence over a horizon $T$ for an optimizer playing against a fixed, public online learner in repeated general-sum games. We show that, unless $\mathsf{P} = \mathsf{NP}$, no polynomial-time optimizer can approximate the best strategy sequence within a sufficiently small additive error, even when the optimizer is permitted to output explicitly encoded mixed strategies at every round. Our result resolves an open question posed by Assos et al. (2025) and substantially generalizes prior hardness bounds to encompass the dominant benchmark algorithms in the online learning literature. Specifically, our framework establishes computational inapproximability across setwise mean-based learning, Multiplicative Weights Update (MWU), and separable Follow-the-Regularized-Leader (FTRL) under standard learning-rate regimes.