# Is Online Linear Optimization Sufficient for Strategic Robustness?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 29 references that are in the map.
- First posted on arXiv 12 Feb 2026.

## Builds on (most cited first, 27 of 27)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Auto-bidding and Auctions in Online Advertising: A Survey](https://mlsanity.com/paper/2408.07685/) (2024)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [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)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Gradient Equilibrium in Online Learning: Theory and Applications](https://mlsanity.com/paper/2501.08330/) (2025)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions](https://mlsanity.com/paper/2402.07363/) (2024)
- [Generalized Principal-Agent Problem with a Learning Agent](https://mlsanity.com/paper/2402.09721/) (2024)
- [Online Conformal Prediction via Universal Portfolio Algorithms](https://mlsanity.com/paper/2602.03168/) (2026)
- [Computational Aspects of Bayesian Persuasion under Approximate Best Response](https://mlsanity.com/paper/2402.07426/) (2024)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Calibrated Forecasting and Persuasion](https://mlsanity.com/paper/2406.15680/) (2024)

## Abstract (arXiv)

We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the seller's manipulation remains relatively underexplored. Bidding algorithms based on no-swap-regret algorithms achieve both desirable properties, but are suboptimal in terms of statistical and computational efficiency. In contrast, online gradient ascent is the only algorithm that achieves O(√TK) regret and strategic robustness [KSS24], where T denotes the number of auctions and K the number of bids. In this paper, we explore whether simple online linear optimization (OLO) algorithms suffice for bidding algorithms with both desirable properties. Our main result shows that sublinear linearized regret is sufficient for strategic robustness. Specifically, we construct simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm, in both known and unknown value distribution settings. For the known value distribution case, our reduction yields a bidding algorithm that achieves O(√T log K) regret and strategic robustness (with exponential improvement on the K-dependence compared to [KSS24]). For the unknown value distribution case, our reduction gives a bidding algorithm with high-probability O(√T (log K+log(T/δ)) regret and strategic robustness, while removing the bounded density assumption made in [KSS24].