betaFeedback

WorksComputer Science

Learning vs. Optimizing Players in Budgeted Games

Abstract

We study repeated general games over TT rounds between a utility-maximizing optimizer and a learning agent, where budget constraints couple the players' decisions across rounds. Without budgets, low swap regret simultaneously guarantees the learner sublinear regret and caps the optimizer at its Stackelberg value. Budgets break this picture: adversarial no-regret becomes impossible, so the natural goals are non-manipulability—no adaptive optimizer earns more than BSE⋅T+o(T)\mathtt{BSE} \cdot T + o(T), where BSE\mathtt{BSE} is its Budgeted Stackelberg Equilibrium value—and low stochastic regret when the optimizer plays a fixed mixed strategy. We give an efficient, budget-feasible learning algorithm that achieves both goals in every budgeted game: any adaptive optimizer, budgeted or not, earns at most BSE⋅T+O(T)\mathtt{BSE} \cdot T + O(\sqrt{T}) in expectation, and if the optimizer plays a fixed mixed strategy on each of a constant number of intervals, the learner has O(T)O(\sqrt{T}) regret on each such interval. Our learner best responds to forecasts of the optimizer's play that are calibrated in two novel senses, since under budgets the calibration that prevents manipulation no longer yields low stochastic regret. Response calibration, which conditions on the learner's own mixed response by embedding its continuous mixing weight as a step function in L2([−1,1])L^2([-1,1]), prevents manipulation without discretizing responses; dual-weighted Lagrangian calibration ensures low regret. Although low calibration error requires randomized forecasts—distributions over a continuous space that need not have a succinct representation or be directly computable—we construct such forecasts in polynomial time by simulating online gradient ascent.

Introduction

Learning algorithms increasingly act on behalf of agents in repeated strategic interactions: they bid in ad auctions, set prices, and allocate computing resources. The party on the other side is often not another learner but a forward-looking optimizer that knows how the learner behaves and plans against it. The learner’s predictability then becomes a liability, which raises two basic questions [5, 20, 31, 55]: How much can an optimizer extract from a learner? And which learning algorithms are non-manipulable, in the sense that their predictability gives the optimizer no advantage?

In standard (unbudgeted) repeated games, these questions have a clean answer. The natural benchmark is the optimizer’s Stackelberg Equilibrium value SE: the best payoff it can obtain by committing to a mixed strategy to which the learner best responds. Against any no-regret learner, the optimizer can secure (essentially) SE per round by committing to its Stackelberg strategy, and against common no-regret algorithms, such as multiplicative weights, it can, in some games, earn strictly more [20, 31]. A learner is protected when it has low swap regret: low swap regret caps the optimizer at SE⋅T+o(T)\mathrm{SE} \cdot T + o(T) [31], and it is, in a precise sense, also necessary [5, 55]. Since best responding to calibrated forecasts guarantees low swap regret [40], a single principle—calibration—delivers both robustness to manipulation and good learning performance.

This theory treats the rounds as decoupled. Yet in many of the interactions that motivate it—such as autobidding in online advertising [2, 10, 27, 28], but also cloud resource allocation and repeated procurement—agents operate under long-term budgets that couple their decisions across rounds. This motivates the study of repeated budgeted games. For TT rounds, an optimizer with nOn_{\mathrm{O}} actions and a learner with nLn_{\mathrm{L}} actions play a stage game with utility matrices UO,UL∈[0,1]nO×nLU_{\mathrm{O}}, U_{\mathrm{L}} \in[0,1]^{n_{\mathrm{O}}\times n_{\mathrm{L}}} and cost matrices CO,CL∈[0,1]nO×nLC_{\mathrm{O}}, C_{\mathrm{L}} \in[0,1]^{n_{\mathrm{O}}\times n_{\mathrm{L}}}: in round tt the optimizer plays it∈[nO]i_t \in[n_{\mathrm{O}}], the learner plays jt∈[nL]j_t \in[n_{\mathrm{L}}], and each player wants to maximize its total utility while keeping its total cost within its budget—ρOT\rho_{\mathrm{O}}T for the optimizer and ρLT\rho_{\mathrm{L}}T for the learner. Budgets change both sides of the interaction:

  • The optimizer may want to switch strategies. A budgeted optimizer can do strictly better than commit to a single mixed strategy: because its value need not be concave in its spending, it may profit from time-multiplexing—for instance, by spending aggressively for qTqT rounds and frugally for the remaining (1−q)T(1-q)T rounds. The resulting benchmark is the Budgeted Stackelberg Equilibrium (BSE) (defined in our recent work [36]): the optimizer commits to (at most) two phases, each met by the learner’s budgeted best response. When the optimizer is unbudgeted, one phase suffices, and the BSE value is simply the value of the stage game in which the follower best responds subject to its budget.

  • The learner can no longer guarantee low regret. Against an adversarial sequence of actions, no budgeted learner can guarantee sublinear regret [49, 54], let alone low swap regret, due to facing the spend or save dilemma. So the swap-regret characterization above has no direct budgeted analog.

What, then, should a budgeted learner aim for? We ask for two properties:

  1. Non-manipulability: no adaptive optimizer earns more than BSE⋅T+o(T)\mathrm{BSE} \cdot T + o(T) in expectation.3

  1. Low interval stochastic regret4: if the optimizer’s play is piecewise stationary—i.i.d. from a fixed mixed strategy within each of a few intervals, unknown to the learner—then on every interval, the learner’s utility is within o(T)o(T) of the utility from the best budget-feasible response to the corresponding mixed strategy.

Since adversarial no-regret is out of reach, the second property is the natural learning goal: it is the standard benchmark for learning under budgets in stochastic environments [3, 7], applied to every stationary stretch of play and it also provides a sanity check, that the learner is not just trying to harm the optimizer. Without budgets, a single property—low swap regret—yields both non-manipulability and low regret (Table 1). With budgets, the calibration that prevents manipulation no longer yields low regret (Challenge 3 in § 1.2), so each property needs its own tool. The central question of this paper is:

Guarantee for the learnerWithout budgetsWith budgets
Low regret against every sequence✓× [49, 54]
Low swap regret✓ [18]×
Low regret against a stationary optimizer✓✓ [3, 7]
Non-manipulability, plus the previous row✓ via swap regret [31]✓ this paper

Table 1. What a learner can guarantee, without and with budgets.

Is there an efficient learning algorithm that, in every repeated budgeted game, is non-manipulable and has low interval stochastic regret?

Our results. We answer this question in the affirmative. We assume full-information feedback about the learner’s own payoffs and costs: after round, the learner observes the utility and cost of each of its actions, i.e., the vector (UL[it,:],CL[it,:])∈[0,1]2nL(U_L[i_t,:], C_L[i_t,:]) \in[0,1]^{2n_L}. It observes neither iti_t nor the optimizer’s payoffs, and it does not know in advance which utility-cost vectors can arise. Each player has a null action that incurs no cost.

Theorem 1.1 (Informal version of Theorems 6.7 and 7.2). There is a learning algorithm that never exceeds the learner’s budget, runs in poly⁡(T,nL)\operatorname{poly}(T,n_L) time per round, and in every repeated budgeted game simultaneously guarantees:

  1. Non-manipulability: against every adaptive optimizer,

E[∑t=1TUO[it,jt]]≤BSE⋅T+O(T),\mathbb{E}\left[\sum_{t=1}^{T} U_O[i_t,j_t]\right] \le\mathrm{BSE}\cdot T + O\left(\sqrt{T}\right),

*where O(⋅)O(\cdot) hides factors polynomial in nOn_O, nLn_L, and 1/ρL1/\rho_L.5 If the optimizer is also budgeted, the same holds relative to its two-phase BSE, with an additional factor of 1/ρO1/\rho_O in the error term.*

  1. Low interval stochastic regret: if [T][T] is partitioned into SS intervals, unknown to the learner, such that within each interval I\mathcal{I} the optimizer draws its actions i.i.d. from a mixed strategy xIx_{\mathcal{I}}, then on every interval,

E[∑t∈IUL[it,jt]]≥∣I∣⋅xITULyI⋆−O(SnLTρL),\mathbb{E}\left[\sum_{t\in\mathcal{I}} U_L[i_t,j_t]\right] \ge|\mathcal{I}|\cdot x_{\mathcal{I}}^{\mathsf{T}}U_Ly_{\mathcal{I}}^\star- O\left(\frac{\sqrt{S n_L T}}{\rho_L}\right),

where yI⋆y_{\mathcal{I}}^\star is a best response to xIx_{\mathcal{I}} subject to the learner’s per-round budget.

Three features of Theorem 1.1 are worth highlighting. First, the regret bound is independent of the number of the optimizer’s actions: it holds even if no utility-cost vector is ever observed twice. Second, the first guarantee is essentially tight: against our learner, an optimizer that plays a fixed mixed strategy in each of (at most) two phases secures the weak BSE value (Theorem 7.4). Thus, up to the usual gap between weak and strong Stackelberg values, the BSE is the value of the interaction. Third, the algorithm needs no prior knowledge of the game.

Comparison With Budgeted Auctions

Budgeted auctions: simplicity from structure. In earlier work [36], we studied these questions for repeated budgeted auctions in a Bayesian setting, where in each round the two bidders’ values are drawn from a joint distribution. Here, the algorithm used in practice is remarkably simple. In a second-price auction, the learner’s best response to any fixed competition is to bid its value scaled by a single pacing multiplier, so the learner only needs to track one number, and large advertising platforms adjust it with simple feedback (PID-style) controllers: raise the multiplier after underspending, lower it after overspending [27, 43, 60]. [36] shows that the simplest such controller—a deterministic, one-line proportional update—is non-manipulable: under a mild assumption on the value distribution (some such assumption is necessary), the optimizer earns at most BSE · TT + O(T2/3)O(T^{2/3}).

General games: universality without structure. Given the previous results, a natural question arises. Is robustness to manipulation an artifact of the special structure of auctions, or can it be achieved in every budgeted game? In a general game, no scalar parameterizes the learner’s best responses: a budget-constrained best response is the solution of a linear program—often a strict mixture of two actions—and it jumps discontinuously as the environment changes. The learner does not know the optimizer’s payoffs. And there is no Bayesian structure to lean on: everything the learner faces is chosen adaptively by the optimizer. In fact, no deterministic learner is non-manipulable in every game: in matching pennies (with zero costs), an optimizer that simulates the learner always mismatches it, earning 1 per round, twice its Stackelberg value of 1/21/2. In auctions, structure makes determinism harmless; general games have no such structure.

Why both settings. Our work on budgeted auctions [36] and this paper answer on general games complementary questions—is the algorithm used in practice robust? and is robustness achievable in every budgeted game?—and neither result implies the other (Table 2 in Appendix § 9 compares them in detail). The controller of [36] has no counterpart in general games, where no deterministic learner is robust. The same pattern is familiar without budgets: against a revenue-maximizing seller, simple no-regret bidding algorithms (in the right parameterization) are already robust [Cai-26; KSS24; Zha26], whereas in general games, robustness requires low swap regret [55]. As often in algorithm design, the special case admits a strikingly simple algorithm, while the general case requires more complex algorithms.

Budgeted auctions [36]General budgeted games (this paper)
Stage gameSecond-price auctions (and first-price, with pacing bids)Any game with utility and cost matrices
EnvironmentBayesian: values drawn i.i.d. from a joint distribution; adaptive optimizerAdversarial: no distributional assumptions; adaptive optimizer
Learner’s strategiesBids as a function of values (a continuum)nLn_L actions
Learner’s feedbackIts value and its realized paymentThe utility and cost of every action
StructureBest responses are pacing: bid = λ⋅\lambda\cdot valueNone: best responses mix up to two actions
AlgorithmDeterministic proportional controller for λ\lambdaRandomized best responses to calibrated forecasts
GuaranteeBSE ⋅T+O(T2/3)\cdot T + O(T^{2/3}) (under a mild (necessary) assumption on values), plus low interval stochastic regretBSE ⋅T+O(T)\cdot T + O(\sqrt{T}), plus low interval stochastic regret
AnalysisDynamic programming over a scalar state, with a potential built from Lagrangian dualityCalibration in L2([−1,1])L^2([-1,1]); dual-weighted calibration; forecaster via simulated OGD

Table 2. This paper and [36] at a glance.

Why the techniques differ. Beyond the BSE benchmark and Lagrangian duality, the two analyses share very little. In [36], the learner is a fixed, deterministic dynamical system with a one-dimensional state, and the proof bounds the value of the optimizer’s control problem over this state with a potential function built from Lagrangian duality. Here, there is no small state to control, and the learner must randomize: our learner best responds to forecasts that are calibrated in two new senses—conditionally on its own mixed response (which prevents manipulation), and weighted by its dual variable (which yields low regret)—and computes them by simulating a no-regret dynamic (see challenges and techniques in § 1.2 and § 1.3).

Why General Budgeted Games Are Hard: Three Challenges

Three challenges rule out natural approaches and shape our solution.

1. Interval no-regret does not prevent manipulation. Since adversarial regret is impossible, one might combine steady spending of budget with an online learning algorithm that has low regret on every interval. This fails even without budgets: projected online gradient ascent has O(T)O(\sqrt{T}) regret on every interval against every sequence, yet in a simple 3×33 \times3 game, an optimizer that switches actions whenever the learner’s mixed strategy reaches a corner of the simplex earns T/2−o(T)T/2 - o(T), compared with SE⋅T=T/3\mathrm{SE} \cdot T = T/3 (see [36], also included for completeness in Appendix § 11). Robustness in general games requires guarantees conditioned on the learner’s own responses, as in swap regret and calibration [55].

2. Budgeted best responses are mixed and discontinuous. Following Foster and Vohra [40], the learner could forecast the utility-cost vector that the optimizer will induce, and best respond to the forecast. Merely unbiased forecasts are not enough: since best responses are discontinuous, forecasts with zero cumulative error can lie on opposite sides of a discontinuity and induce opposite actions, which the optimizer can exploit (see Appendix § 12 for an example). Full calibration, which conditions on the forecast itself, avoids this but needs exponentially (in the dimension of forecasts) many buckets. Without budgets, the efficient remedy is to condition only on the learner’s response, and since best responses can be taken to be pure, nLn_L “buckets” suffice. With a budget, however, the best response solves a linear program with two constraints (the simplex and the budget), so when the budget binds, it is generically a strict mixture of two actions (j1,j2)(j_1, j_2), with a mixing weight q∈[0,1]q \in[0, 1] that varies continuously. Conditioning on the exact response would require infinitely many buckets, while coarser conditioning—ignoring the weight, or tracking the two actions separately—can be exploited; the latter because several optimizer actions may induce the same feedback for the learner but have different value for the optimizer (see Appendix § 13 for an example).

3. Non-manipulability no longer implies low regret. Unlike in unbudgeted games, response calibration does not yield low regret: there are forecasters with zero response-conditioned calibration error—so the learner cannot be manipulated—under which the learner suffers Ω(T)\Omega(T) regret against an i.i.d. optimizer (Appendix § 14). The reason is that two different forecasts can induce the same conservative action, so their errors cancel, and the learner never discovers an action that is affordable only on average.

Our Techniques

Forecast, then best respond—safely. Our learner keeps a small reserve: in any round tt in which its past spending exceeds tP−1tP - 1, it plays its null action, so it never exceeds its budget. In every other (active) round, it draws a forecast ff—a mixture of the utility-cost vectors observed so far—from a distribution FtF_t of such forecasts, and plays a budget-constrained best response ψ(f)\psi(f) to the forecast, supported on (at most) two actions J⃗(f)=(j1,j2)\vec{J}(f) = (j_1, j_2) with probability Q(f)Q(f) on j1j_1. Everything then hinges on the quality of the forecasts, which we measure with two new calibration errors.

Response calibration in a function space. To bound the optimizer’s gain over the BSE, forecasts must be calibrated conditionally on the learner’s response (J⃗(f),Q(f))(\vec{J}(f), Q(f)). Instead of discretizing the weight Q(f)Q(f), we represent it by the step function q↦1q≤Q(f)q \mapsto\mathbf{1}_{q \le Q(f)} in the Hilbert space L2([−1,1])L^2([-1, 1]). The response-calibration error RtR_t has one coordinate for each outcome kk (a possible utility-cost vector) and each pair (j1,j2)(j_1, j_2); in each round, coordinate (k,J⃗(f))(k, \vec{J}(f)) accumulates the forecast error 1kt=k−f(k)\mathbf{1}_{k_t=k} - f(k) times this step function. Two facts make this representation work. First, step functions have the closed-form inner product ⟨1≤q,1≤q′⟩=1+min⁡{q,q′}\langle\mathbf{1}_{\le q}, \mathbf{1}_{\le q'} \rangle= 1 + \min\{q, q'\}, so RtR_t can be stored and manipulated efficiently. Second, the optimizer’s best payoff against the mixed response (j1,j2,q)(j_1, j_2, q), among its actions that induce outcome kk, is a 1-Lipschitz piecewise-linear function g(q)g(q), which can be written as the inner product ⟨g′,1≤q⟩\langle g',1_{\leq q}\rangle with its derivative (working on [−1,1][-1,1] rather than [0,1][0,1] to accommodate affine functions). By linearity and the Cauchy–Schwarz inequality, the optimizer’s total gain over the BSE in active rounds is at most ⟨g′,RT⟩≤∥g′∥∥RT∥\langle g',R_T\rangle\leq\lVert g'\rVert\lVert R_T\rVert, simultaneously for all optimizer payoff matrices (which the learner does not know).

Lagrangian calibration. To obtain low stochastic regret and keep spending on track, we maintain a second error LtL_t. The best response y(f)y(f) maximizes the Lagrangian u(f)⊤y+λ(f)(ρL−c(f)⊤y)u(f)^\top y+\lambda(f)(\rho_L-c(f)^\top y), where u(f)u(f) and c(f)c(f) are the forecast utility and cost vectors and λ(f)∈[0,1/ρL]\lambda(f)\in[0,1/\rho_L] is the optimal dual multiplier of the learner’s budget constraint. When comparing the learner with a budget-feasible comparator y⋆y^\star, the troublesome term is the cost misprediction weighted by the dual variable, λ(f)(ct−c(f))⊤y⋆\lambda(f)(c_t-c(f))^\top y^\star, where ctc_t is the realized cost vector: a forecast that overestimates the cost of y⋆y^\star makes it look unaffordable exactly when the budget is tight, as in Challenge 3 in § 1.2 (see example in Appendix § 14). The Lagrangian-calibration error LtL_t tracks this dual-weighted cost error, together with the utility error and the gaps between the learner’s realized and forecast utility and cost. A small ∥Lt∥\lVert L_t\rVert bounds both the number of non-active rounds and the learner’s regret on every stationary interval.

References

  1. [1]Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. “No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints”. In: Proceedings of the ACM on Web Conference 2025, WWW 2025, Sydney, NSW, Australia, 28 April 2025- 2 May 2025. ACM, 2025, pp. 1398–1415.arxiv.org/abs/2404.09832
  2. [2]Gagan Aggarwal et al. “Auto-Bidding and Auctions in Online Advertising: A Survey”. In: SIGecom Exch. 22.1 (2024), pp. 159–183.arxiv.org/abs/2408.07685
  3. [3]Shipra Agrawal and Nikhil R. Devanur. “Linear Contextual Bandits with Knapsacks”. In: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. 2016, pp. 3450–3458.arxiv.org/abs/1507.06738
  4. [4]Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson, Haipeng Luo, and Jon Schneider. “Swap Regret Minimization through Response-Based Approachability”. In: Proceedings of the Thirty-Ninth Conference on Learning Theory. Vol. 336. Proceedings of Machine Learning Research. 2026, pp. 195–223.arxiv.org/abs/2602.06264
  5. [5]Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. “Swap Regret and Correlated Equilibria Beyond Normal-Form Games”. In: Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025. ACM, 2025, pp. 130–157.arxiv.org/abs/2502.20229
  6. [6]Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. “Pareto-Optimal Algorithms for Learning in Games”. In: Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024. ACM, 2024, pp. 490–510.arxiv.org/abs/2402.09549
  7. [7]Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. “Bandits with Knapsacks”. In: J. ACM 65.3 (2018), 13:1–13:55.
  8. [8]Santiago R. Balseiro, Omar Besbes, and Gabriel Y. Weintraub. “Repeated Auctions with Budgets in Ad Exchanges: Approximations and Design”. In: Manag. Sci. 61.4 (2015), pp. 864–884.DOI
  9. [9]Santiago R. Balseiro, Kshipra Bhawalkar, Zhe Feng, Haihao Lu, Vahab Mirrokni, Balasubramanian Sivan, and Di Wang. “A Field Guide for Pacing Budget and ROS Constraints”. In: Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21–27, 2024. Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2024, pp. 2607–2638. URL: https://proceedings.mlr.press/v235/balseiro24a.html.arxiv.org/abs/2302.08530
  10. [10]Santiago R. Balseiro and Yonatan Gur. “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium”. In: Management Science 65.9 (2019), pp. 3952–3968.
  11. [11]Santiago R. Balseiro, Christian Kroer, and Rachitesh Kumar. “Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees”. In: Manag. Sci. 69.11 (2023), pp. 6837–6854.
  12. [12]Santiago R. Balseiro, Rachitesh Kumar, Vahab Mirrokni, Balasubramanian Sivan, and Di Wang. “Robust Budget Pacing with a Single Sample”. In: International Conference on Machine Learning, ICML 2023, 23–29 July 2023, Honolulu, Hawaii, USA. Proceedings of Machine Learning Research. PMLR, 2023, pp. 1636–1659. URL: https://proceedings.mlr.press/v202/balseiro23a.html.arxiv.org/abs/2302.02006
  13. [13]Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. “The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems”. In: Oper. Res. 71.1 (2023), pp. 101–119. DOI: 10.1287/OPRE.2021.2242. URL: https://doi.org/10.1287/opre.2021.2242.
  14. [14]Santiago R. Balseiro, Haihao Lu, Vahab S. Mirrokni, and Balasubramanian Sivan. “From Online Optimization to PID Controllers: Mirror Descent with Momentum”. In: CoRR abs/2202.06152 (2022). arXiv: 2202.06152. URL: https://arxiv.org/abs/2202.06152.
  15. [15]Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. “Bandits with Replenishable Knapsacks: the Best of both Worlds”. In: The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7–11, 2024. OpenReview.net, 2024.
  16. [16]Andrey Bernstein and Nahum Shimkin. “Response-Based Approachability with Applications to Generalized No-Regret Problems”. In: Journal of Machine Learning Research 16.24 (2015), pp. 747–773.
  17. [17]David Blackwell. “An Analog of the Minimax Theorem for Vector Payoffs”. In: Pacific Journal of Mathematics 6.1 (1956), pp. 1–8.DOI
  18. [18]Avrim Blum and Yishay Mansour. “From External to Internal Regret”. In: Learning Theory, 18th Annual Conference on Learning Theory, COLT 2005. Lecture Notes in Computer Science. Springer, 2005, pp. 621–636.
  19. [19]Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, and Eric Xue. “A New Benchmark for Online Learning with Budget-Balancing Constraints”. In: CoRR abs/2503.14796 (2025). DOI: 10.48550/ARXIV.2503.14796. arXiv: 2503.14796. URL: https://doi.org/10.48550/arXiv.2503.14796.
  20. [20]Mark Braverman, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. “Selling to a No-Regret Buyer”. In: Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18–22, 2018. ACM, 2018, pp. 523–538.arxiv.org/abs/1711.09176
  21. [21]William Brown, Jon Schneider, and Kiran Vodrahalli. “Is Learning in Games Good for the Learners?” In: Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10–16, 2023. 2023.arxiv.org/abs/2305.19496
  22. [22]Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. “Is Online Linear Optimization Sufficient for Strategic Robustness?” In: Proceedings of the 27th ACM Conference on Economics and Computation, EC 2026. ACM, 2026.arxiv.org/abs/2602.12253
  23. [23]Modibo K. Camara, Jason D. Hartline, and Aleck Johnsen. “Mechanisms for a No-Regret Agent: Beyond the Common Prior”. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE, 2020, pp. 259–270.arxiv.org/abs/2009.05518
  24. [24]Matteo Castiglioni, Andrea Celli, and Christian Kroer. “Online Learning with Knapsacks: the Best of Both Worlds”. In: International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA. Proceedings of Machine Learning Research. PMLR, 2022, pp. 2767–2783.
  25. [25]Matteo Castiglioni, Andrea Celli, and Christian Kroer. “Online Learning under Budget and ROI Constraints via Weak Adaptivity”. In: Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2024, pp. 5792–5816.
  26. [26]Xi Chen, Christian Kroer, and Rachitesh Kumar. “The Complexity of Pacing for Second-Price Auctions”. In: Math. Oper. Res. 49.4 (2024), pp. 2109–2135.
  27. [27]Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolás E. Stier-Moses, Eric Sodomka, and Christopher A. Wilkens. “Pacing Equilibrium in First Price Auction Markets”. In: Management Science 68.12 (2022), pp. 8515–8535.
  28. [28]Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolás E. Stier-Moses. “Multiplicative Pacing Equilibria in Auction Markets”. In: Operations Research 70.2 (2022), pp. 963–989.arxiv.org/abs/1706.07151
  29. [29]Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. “Pseudonorm approachability and applications to regret minimization”. In: International Conference on Algorithmic Learning Theory. PMLR, 2023, pp. 471–509.arxiv.org/abs/2302.01517
  30. [30]Yuan Deng, Jon Schneider, and Balasubramanian Sivan. “Prior-Free Dynamic Auctions with Low Regret Buyers”. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada. 2019, pp. 4804–4814. URL: https://proceedings.neurips.cc/paper/2019/hash/f15eda31a2da646eea513b0f81a5414d-Abstract.html.
  31. [31]Yuan Deng, Jon Schneider, and Balasubramanian Sivan. “Strategizing against No-regret Learners”. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019. 2019, pp. 1577–1585.arxiv.org/abs/1909.13861
  32. [32]Rick Durrett. Probability: Theory and Examples. Vol. 49. Cambridge University Press, 2019.
  33. [33]Zhe Feng, Swati Padmanabhan, and Di Wang. “Online Bidding Algorithms for Return-on-Spend Constrained Advertisers”. In: Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023. ACM, 2023, pp. 3550–3560.arxiv.org/abs/2208.13713
  34. [34]Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus, Raunak Kumar, Yishay Mansour, and Éva Tardos. “Learning in Budgeted Auctions with Spacing Objectives”. In: Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025. ACM, 2025, p. 158.
  35. [35]Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus, Yishay Mansour, and Éva Tardos. Robust Temporal Guarantees in Budgeted Sequential Auctions. 2026. arXiv: 2602.17916. URL: https://arxiv.org/abs/2602.17916.
  36. [36]Giannis Fikioris, Balasubramanian Sivan, and Éva Tardos. “Learning vs. Optimizing Bidders in Budgeted Auctions”. In: CoRR abs/2604.08517 (2026). arXiv: 2604.08517.arxiv.org/abs/2604.08517
  37. [37]Giannis Fikioris and Éva Tardos. “Approximately Stationary Bandits with Knapsacks”. In: The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India. Proceedings of Machine Learning Research. PMLR, 2023, pp. 3758–3782.arxiv.org/abs/2302.14686
  38. [38]Giannis Fikioris and Éva Tardos. “Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions”. In: Mathematics of Operations Research 50.2 (2025), pp. 1233–1249.
  39. [39]Dean P. Foster and Sergiu Hart. “Forecast Hedging and Calibration”. In: Journal of Political Economy 129.12 (2021), pp. 3447–3490.
  40. [40]Dean P. Foster and Rakesh V. Vohra. “Calibrated Learning and Correlated Equilibrium”. In: Games and Economic Behavior 21.1–2 (1997), pp. 40–55.
  41. [41]Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. “Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence”. In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 52:1–52:1.arxiv.org/abs/2205.08674
  42. [42]Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. “Pricing against a Budget and ROI Constrained Buyer”. In: International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain. Vol. 206. Proceedings of Machine Learning Research. PMLR, 2023, pp. 9282–9307.
  43. [43]Google. Power your business by taking control of your budget and advertising cost. 2021. URL: https://business.google.com/en-all/google-ads/campaign-budget/.
  44. [44]Guru Gurug anesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua R. Wang, and S. Matthew Weinberg. “Contracting with a Learning Agent”. In: Neural Information Processing Systems 2024, NeurIPS 2024. 2024.
  45. [45]Nika Haghtalab, Chara Podimata, and Kunhe Yang. “Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents”. In: Advances in Neural Information Processing Systems 36 (2023).arxiv.org/abs/2306.02704
  46. [46]Sergiu Hart and Andreu Mas-Colell. “A simple adaptive procedure leading to correlated equilibrium”. In: Econometrica 68.5 (2000), pp. 1127–1150.
  47. [47]Elad Hazan. “Introduction to Online Convex Optimization”. In: Foundations and Trends in Optimization 2.3–4 (2016), pp. 157–325.
  48. [48]Lunjia Hu and Yifan Wu. “Predict to Minimize Swap Regret for All Payoff-Bounded Tasks”. In: 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024. IEEE, 2024, pp. 244–263.DOI
  49. [49]Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, and Aleksandrs Slivkins. “Adversarial Bandits with Knapsacks”. In: J. ACM 69.6 (2022), 40:1–40:47.
  50. [50]Thomas Kesselheim and Sahil Singla. “Online Learning with Vector Costs and Bandits with Knapsacks”. In: Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. PMLR, 2020, pp. 2286–2305.arxiv.org/abs/2010.07346
  51. [51]Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. “U-Calibration: Forecasting for an Unknown Agent”. In: Conference on Learning Theory, COLT 2023. Vol. 195. Proceedings of Machine Learning Research. PMLR, 2023.arxiv.org/abs/2307.00168
  52. [52]Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. “Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions”. In: Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024. ACM, 2024, p. 893.
  53. [54]Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. “Online Learning with Sample Path Constraints”. In: Journal of Machine Learning Research 10.20 (2009), pp. 569–590.DOI
  54. [55]Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. “Strategizing against Learners in Bayesian Games”. In: Conference on Learning Theory, 2-5 July 2022, London, UK. Proceedings of Machine Learning Research. PMLR, 2022, pp. 5221–5252.arxiv.org/abs/2205.08562
  55. [56]Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. “High-Dimensional Prediction for Sequential Decision Making”. In: International Conference on Machine Learning, ICML 2025. Vol. 267. Proceedings of Machine Learning Research. 2025.
  56. [57]Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Chido Onyeze, Erald Sinanaj, and Éva Tardos. “Improved Multi-Dimensional Forecasting for Swap Regret”. In: Proceedings of the 27th ACM Conference on Economics and Computation, EC 2026. ACM, 2026.arxiv.org/abs/2606.29533
  57. [58]Aaron Roth and Mirah Shi. “Forecasting for Swap Regret for All Downstream Agents”. In: Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024. ACM, 2024, pp. 466–488.arxiv.org/abs/2402.08753
  58. [59]Aviad Rubinstein and Junyao Zhao. “Strategizing against no-regret learners in first-price auctions”. In: Proceedings of the 25th ACM Conference on Economics and Computation. 2024, pp. 894–921.arxiv.org/abs/2402.08637
  59. [60]Twitter. How we built Twitter’s highly reliable ads pacing service. 2021. URL: https://blog.x.com/engineering/en_us/topics/infrastructure/2021/how-we-built-twitter-s-highly-reliable-ads-pacing-service.
  60. [61]Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. “Learning to Bid in Repeated First-Price Auctions with Budgets”. In: International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA. Proceedings of Machine Learning Research. PMLR, 2023, pp. 36494–36513.arxiv.org/abs/2304.13477
  61. [62]Junyao Zhao. “From No-Regret to Strategically Robust Learning in Repeated Auctions”. In: Proceedings of the 27th ACM Conference on Economics and Computation, EC 2026. ACM, 2026.arxiv.org/abs/2601.03853
  62. [63]Shengjia Zhao, Michael P. Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. “Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration”. In: Neural Information Processing Systems, NeurIPS 2021. 2021.arxiv.org/abs/2107.05719

Paper details

vlnc:W_642dup3a
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare), Astra 6, Gemini 4 Argon

View statement
Looking for related papers…
Contents