acceptodds
Under review as a conference paper at ICLR 2027

Online Learning in Quota-Constrained Acquisition Games with Transient Impact

Abstract

We study strategic acquisition over a finite horizon when every agent must fill an exact quota, aggregate demand raises the price, and part of this impact persists before decaying. Our question is what an agent can learn from public prices when the competitors' quotas and actions are hidden. Under a natural stability condition, this game is strongly convex and has a unique pure Nash equilibrium. We show that for every fixed transient impact parameter , equilibrium schedules approach the uniform strategy and the price of anarchy approaches as grows. Across repeated episodes, the public price together with an agent's own schedule determine its cost gradient. Hence, decentralized online projected gradient descent achieves regret and mean-square last-iterate convergence without observing the number, quotas or schedules of the other agents. We obtain similar convergence guarantees for a Bayesian setting with (possibly correlated) private quotas. When the impact state is inherited across episodes, we characterize a self-consistent myopic equilibrium and its stochastic analogue. We also study learning within a single episode. We prove an external-regret lower bound against the best schedule in hindsight, which motivates comparison against finite families of bounded-memory scheduling rules. We present a model-free bandit algorithm and show that it achieves policy regret and empirical schedules approach a coarse correlated equilibrium at rate .

Primary area:
learning theory
Keywords:
online learning, learning in games, strategic acquisition games, learning under transient impact

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4SfgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies acquisition games and no-regret learning — an agent must acquire a prescribed quantity of a common resource within a fixed time. The state is endogenous — the market price is determined by past actions. The authors provide a proof of existence of a pure Nash Equilibrium, in addition to convergence guarantees of their learning algorithm. The major contribution is a model-free bandit algorithm demonstrating that it achieves sublinear regret and coarse correlated equilibrium.

Critical strengths

Overall I liked the paper. This paper is well written, well structured, and well motivated, with good, clear exposition.

The authors examine a relevant economic problem, and the guarantees it provides are non-trivial and useful.

The paper is well positioned against previous literature, making non-incremental contributions.

Critical weaknesses

To be honest, I didn't really identify any major weaknesses here. Perhaps one question is why the authors chose convergence to CCE and not something stronger, e.g., CE, MNE, etc., or something like Bayes NE.

Furthermore, some more ablation studies could be conducted here to demonstrate more robustness.

Questions for authors

I would like to know whether this work could extend to other games, like inventory procurement games, Bertrand/Cournot oligopolies, and Newsvendor settings, and if the authors have any insight on the key relationships.

Suppose there is collusion among the players in the system — how would this affect the algorithm if multiple agents collude to avoid the equilibrium solution and attempt a different learning algorithm as a subset?

Soft quota: what if the quota specification is a soft requirement — agents aim to hit the quota but receive a gradual penalty if they don't meet it — how would the results likely change?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 4Sfg: Possible extensions to other games, robustness, agent collusion and soft quota

We thank the reviewer for their careful reading and insightful questions.

Convergence to CCE. Where the structure of the game allows it, we obtain stronger notions. Across episodes, we prove O(1/K)O(1/K) mean-square last-iterate convergence to the unique Nash equilibrium (Theorem 3.1) and, with private random quotas, to the unique Bayesian Nash equilibrium (Theorem 3.2).

CCE appears only in within-episode learning. The quota-constrained acquisition game of Sections 2–4 and the canonical policy game of Section 5 have different information and strategy structures. The latter is a finite game over scheduling policies, where the strong monotonicity behind Nash convergence is lost. PB-Exp3 bounds the regret against every fixed policy in the library, and such no-regret dynamics lead to CCE (Theorem 5.2). We stress that the CCE result is not a weaker replacement for Nash convergence. It concerns a different game defined on the same price dynamics.

Convergence to CE requires bounding swap regret. Since our coupling argument does not depend on how policies are selected, a bandit swap-regret algorithm (Blum & Mansour, 2007) would give convergence to a CE of the policy game. Last-iterate convergence to (mixed) Nash equilibrium would require additional structure on the policy game.

Robustness. Our work is mainly theoretical. We analyze price and state noise (Appendices E.5 and G.7), misspecified impact parameters (Appendix E.5) and estimation of γ\gamma (Appendix E.5.1). Experiments test Bayesian learning with price or state noise (Figure 1(a)); price-oblivious and price-responsive libraries against, respectively, demand with one-period memory and time-varying demand (H.3); fixed-policy sensitivity for γ∈{0.3,0.6,0.9,1}\gamma\in\{0.3,0.6,0.9,1\} (Figure 7); CCE with reset/inherited impact and growing blocks (H.4); tight/wide PB-Exp3 loss intervals (H.3); and omission of the forward term or permanent-impact belief in the correction and step size (Appendix I).

Extensions to other classes of games. For single-period versions of the games mentioned by the reviewer, if losses are convex, the pseudo-gradient is strongly monotone and gradient feedback is available, standard methods for monotone games guarantee convergence to equilibrium (e.g., Mertikopoulos & Zhou, 2019).

We understand that the question concerns their dynamic extensions, in which each player allocates a fixed quota over time and aggregate decisions affect a common state. The standard Cournot, Bertrand and (single-agent) newsvendor models have no intertemporal quota constraints. Inventory-procurement models may have requirements, but rarely an exact requirement constraint over a fixed time horizon. Our repeated-episode argument applies to their dynamic quota-constrained extensions under the same convexity, monotonicity and gradient-observability conditions. This includes multi-period procurement and Cournot-type models with aggregate prices and a transient state. The within-episode technique is model-free and instead requires bounded costs, finite-memory competing responses, and a horizon-independent bound on the difference between realized and counterfactual policy costs.

Classical Bertrand competition may exhibit discontinuous demand and is not covered by our approach. A competitive multi-firm, multi-period newsvendor variant fits our framework if firms allocate fixed requirements over time and their orders affect a common transient price, under the conditions above.

Agent collusion. Across episodes, the O(log⁡K)O(\log K) regret bound holds against arbitrary, even adversarial, competing schedules, and remains valid under agent collusion. Within an episode, the policy-regret bound holds whenever the competitors' demand depends only on the agent's current and last mm actions and their response rule is fixed before the episode.

Regarding convergence to equilibrium, a self-interested coalition SS that minimizes its members' total cost acts as a single agent with accumulated quota. The colluded game is thus an acquisition game with fewer agents. If the coalition, like the other agents, runs Algorithm 1 on its aggregate schedule, learning converges to the equilibrium of the new game (which generally differs from that of the original game).

Soft quotas. Hard quotas are among the most challenging aspects of our work. A convex shortfall penalty preserves strong monotonicity. Hence existence, uniqueness and our repeated-episode guarantees carry over, with the gradient of (5) plus the agent's own penalty derivative. Then, the total volume acquired within an episode becomes a strategic choice, which adds a Cournot-type externality in volumes to the timing externality we study. Within an episode, exploiting the softness would need a separate coupling argument. The Ω(T)\Omega(T) lower bound depends on exact completion. With soft quota, it requires a sufficiently steep penalty and a separate argument.

The revised version includes these remarks.

I thank the authors for their qualifications - the work is clearer.

I encourage the author(s) to add further remarks to the paper regarding:

  • " A competitive multi-firm, multi-period newsvendor variant fits our framework if firms allocate fixed requirements over time and their orders affect a common transient price, under the conditions above."

  • "The colluded game is thus an acquisition game with fewer agents."

  • "... soft quotas" etc.

Perhaps, some additional content in the Appendix to highlight the relation/reduction to soft quotas, multi-period Newsvendor, and collusion would help improve the paper.

My score remains the same - impression positive.

Reviewer_gZByOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors consider an online strategic acquisition game, where each agent fills a quota and the price is demand dependent. The authors show that the equilibrium schedules converge to the uniform strategy. Repeated episodes and single episode settings are further studied, where specific regret analyses are provided.

Critical strengths

I think the paper is in general easy to follow. The problem setting of this particular online game is clear and well-motivated. It is an important and well-structured problem to be studied.

The regret analyses and assumptions are standard; the order of convergences are as expected.

Critical weaknesses

I found the impact state model the price model a bit restrictive. The authors should provide some explanations on why these are two good "abstract" model and potentially use some examples to motivate the two definitions.

Questions for authors

Can we consider more general models as in eq (1). if we have any nonlinearity in the transition model, how would this affect the convergence result? Are your final observations, e.g., uniform schedule and price of anarchy = 1, depending largely on the linear structure of eq(1)?

1 comment
AuthorsOpenReview ↗

Response to Reviewer gZBy: Justification of the model and possible extensions to nonlinear price dynamics

We thank the reviewer for their careful reading and their constructive questions and comments.

Motivation of the model. Our motivation mostly comes from optimal order execution, where linear price impact is a standard model. It underlies the execution models of Bertsimas and Lo (1998) and Almgren and Chriss (2001). Equation (1) is a discrete-time version of the transient-impact model of Obizhaeva and Wang (2013). Related linear price dynamics are used for strategic quota-constrained execution by Strehle (2017), Schied and Zhang (2019), Luo and Schied (2019), and Campbell and Nutz (2026), and, at the permanent-impact endpoint γ=1\gamma=1, for online learning by Kearns and Shi (2025) and Hossain et al. (2026).

Both equations have a simple interpretation in the context of trading. In a limit order book, a purchase consumes the cheapest available offers. The coefficient κ\kappa represents its instantaneous impact on the current price, while part of the purchase enters It+1I_{t+1}, and a fraction γ\gamma of the previous displacement survives as liquidity replenishes. Bouchaud et al. (2004) provide empirical motivation for decaying single-trade impact. In Appendix I, our model fitted on five Nasdaq stocks matches or slightly exceeds the out-of-sample test R2R^2 of a free-lag regression. This comparison evaluates contemporaneous price–volume fit.

Since we adopt a well-studied model, we did not motivate it at length. We have added a summary of this discussion in Section 2.

Extensions beyond linear price dynamics. The repeated-episode proofs use three main properties: strongly convex individual losses; a strongly monotone and bounded pseudo-gradient; and an exact or unbiased gradient available to each agent from its observations. These properties are sufficient for the O(log⁡K)O(\log K) regret and O(1/K)O(1/K) mean-square convergence arguments. A Lipschitz pseudo-gradient is additionally needed for the constant-step geometric rate. Thus, these learning results extend to nonlinear models that satisfy the same properties.

Linearity makes the gradient oracle in our model very simple. Eq. (5) recovers the gradient from public prices and the agent's own schedule, without knowing the competing demand or entering state. For a known nonlinear model, a similar result would require the public observations to identify the aggregate demand and state, and hence the gradient. The exact linear form is also used in our inherited-state, additive-noise and unknown-γ\gamma extensions.

The within-episode results are less tied to linearity. Keeping the same bounded-action and bounded-cost assumptions, and assuming that the response maps are fixed before the episode and have memory mm, Lemma G.4 extends to nonlinear dynamics

It+1=g(It,qt)andPt=f(It,qt),I_{t+1}=g(I_t,q_t)\qquad\text{and}\qquad P_t=f(I_t,q_t),

provided that (a) the market state is contractive in its first argument and Lipschitz in demand, i.e.,

\le \gamma |I-I'|+\lambda |q-q'|\qquad \text{with }\gamma<1,$$ (b) the price map is Lipschitz, and (c) we have feedback stability of costs (Assumption G.2, or G.7 for CCE). For nonlinear dynamics that satisfy (a)–(c), the same coupling arguments and the standard analysis of Exp3 show that Theorems 5.1 and 5.2 hold with the same rates. Both (a) and (c) are necessary for the coupling argument of Lemma G.4. At $\gamma=1$, state differences are never forgotten, and without (c) a discontinuous price-responsive policy can amplify small price differences (Appendix G.3). **Uniform schedule and price of anarchy.** These structural results rely more directly on the linear form of the price dynamics. Similar conclusions may hold for nonlinear models under additional monotonicity and convexity assumptions, together with sufficiently regular transient dynamics ensuring that the nonuniform boundary effects vanish with the horizon. However, the precise assumptions and bounds are model-dependent and beyond the scope of this paper.
Reviewer_2fv5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies a strategic acquisition problem in which agent ii must acquire Bi>0B_i>0 units of a resource over TT periods. Aggregate acquisition qtq_t, which agents do not directly observe, raises the public price PtP_t through a transient impact, with decay factor γ<1\gamma<1. This paper makes several contributions across various model setups and directions. It establishes a unique Nash equilibrium under stability and asymptotic efficiency under symmetry; shows that uniform acquisition is approximately optimal and robust to competitors’ timing; and provides regret and equilibrium-convergence guarantees for price-based learning across episodes. It also analyzes inherited impact, myopic equilibrium, noise, and parameter uncertainty. Within an episode, it proves that external regret can grow linearly with the horizon and develops PB-Exp3 with policy-regret and policy-game CCE guarantees under additional assumptions. Synthetic experiments and market-data simulations illustrate the results.

Critical strengths
  • The paper covers many model variants.
  • It considers a variant with unknown impact parameters.
  • The repeated-episode algorithm guarantees low regret against arbitrary competing schedules and equilibrium convergence when all agents learn.
Critical weaknesses

The paper is difficult to follow. Although I appreciate the breadth of the material, the presentation of many problem variants without sufficiently clear organization is confusing. The authors should prioritize the central contributions and make their relationship clearer. In particular, placing main contributions in the appendices, as noted in the introduction’s “Contributions and Techniques” discussion, makes them difficult to assess. Table 3 should appear in the introduction.

Questions for authors
  • Of the six sets of results summarized in Table 3, which one or two do the authors consider the most important contributions?

  • Could the authors compare PB-Exp3 with BAPS from Lin et al. (2023)? Specifically, can PB-Exp3 be derived from BAPS by augmenting the state with response memory and remaining quota? If not, which assumption fails, and which new lemma resolves that obstruction? Lin, Yiheng, James A. Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. “Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations.” Advances in Neural Information Processing Systems 36 (2023): 53508–53521.

  • For each stock in the experiments, how far above zero is the fitted stability quantity μγ\mu_\gamma, how precisely is it estimated, and does learning remain effective when this quantity is small?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 2fv5: Main contributions, comparison to Lin et al. and fitted stability

We thank the reviewer for their careful reading and constructive questions. We agree that the paper's breadth obscured its organization. The first half of p. 2 states our central objective (i.e., online learning in quota-constrained strategic acquisition) and identifies transient impact and within-episode learning as the two directions motivated by prior work. We added a condensed version of Table 3 to the introduction and identify more clearly the two main contributions below.

Central contributions. First, across repeated episodes, with known impact parameters, an agent recovers its exact cost gradient from public prices and its own schedule, without observing anything else. This yields O(log⁡K)O(\log K) regret against arbitrary competing schedules and O(1/K)O(1/K) mean-square last-iterate convergence to Nash equilibrium under simultaneous learning.

Technically, with private random quotas, the empirical estimator of Section 3.1 gives O(log⁡K)O(\log K) expected realized regret and convergence to the unique Bayesian Nash equilibrium without knowing the quota marginals. With inherited state, we show that under γ<1\gamma<1 and μγ>0\mu_\gamma>0, the linear structure makes the one-episode equilibrium-state map contractive. Hence, repeated equilibrium play converges geometrically to a unique self-consistent myopic equilibrium. The Bayesian analogue is convergence of the inherited-state process to a unique invariant distribution. These do not follow from the standard analysis. The first controls realized regret with empirical type frequencies, the second needs a contraction argument for the equilibrium-state map.

Second, within one episode, the worst-case external regret against the hindsight-optimal schedule is linear, while model-free policy regret against a finite library remains sublinear. Moreover, under synchronized stationary play, the expected empirical distribution approaches a CCE of the finite policy game polynomially fast.

The equilibrium, uniform-policy and price-of-anarchy results are supporting structural results that describe the game being learned and provide benchmarks.

Relation to BAPS. We thank the reviewer for pointing us to Lin et al. (NeurIPS 2023). The sample-one-policy-per-block Exp3 component of PB-Exp3 is the same as BAPS. In fact, the mini-batching reduction for bandit policy regret goes back at least to Arora et al. (2012). Bhatia & Sridharan (2020) give a nonconstructive full-information framework and Li et al. (PMLR 2023) obtain bandit policy regret under incremental exponential stability, which the remaining quota need not satisfy. We now compare to these works.

The linear impact recursion can be expressed in the state-space model of Lin et al. If the full augmented state and policy library satisfy their assumptions 2.1 and 2.2, BAPS applies. Our theorem uses different conditions due to our quota constraints. The projection onto the feasibility interval in (8) is piecewise linear and may be nondifferentiable at its boundaries, so Assumption 2.1 need not hold. Moreover, feedback stability of costs does not imply smoothness of actions. Most importantly, remaining quota need not satisfy their geometric contraction Assumption 2.2. Under uniform completion in a τ\tau-period block, after tt periods and with RtR_t and Rt′R'_t quota remaining,

∣Rt−Rt′∣=τ−tτ∣R0−R0′∣.|R_t-R'_t|=\frac{\tau-t}{\tau}|R_0-R'_0|.

At t=τ/2t=\tau/2, half the initial discrepancy remains, precluding geometric contraction CρtC\rho^t with CC and ρ<1\rho<1 independent of τ\tau.

Assumption G.2 instead bounds the cumulative cost discrepancy after quota and response histories are aligned. E.g., the uniform completion policy satisfies G.2, because aligned copies take identical actions and transient impact allows us to bound the cost discrepancy. Lemma G.4 is the model-specific step. It establishes the required cost-level coupling under exact quota completion, without requiring contraction of the full augmented state. The proof shows an O(1)O(1) actual-versus-counterfactual cost discrepancy per block. The rest is the standard Exp3 analysis. The CCE proof uses an analogous coupling to the canonical policy game. We added this comparison to the main text and Appendix G.

Stability margins. In the market-data experiments, the fitted normalized margins μ^γ/κ^\widehat\mu_\gamma/\widehat\kappa are AAPL 0.5360.536, AMZN 0.4450.445, GOOG 0.4550.455, INTC 0.4650.465, and MSFT 0.5090.509; none is close to zero. We added these margins. We do not report confidence intervals for the fitted parameters. Four of the five γ^\widehat\gamma estimates reach the imposed upper bound 0.99990.9999. Appendix I already notes this and treats the calibration as descriptive.

We did not include a dedicated near-zero-margin experiment, so the present experiments do not establish learning performance in that regime. Holding the other terms in the bounds fixed, the regret and mean-square convergence bounds contain factors proportional to 1/μγ1/\mu_\gamma and 1/μγ21/\mu_\gamma^2, respectively.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised version - summary of the changes

We thank all reviewers for their constructive feedback. We have uploaded a revised version, in which new text is in blue (and corrections are in red, with removed text crossed out). The main changes are:

  • Introduction: a condensed version of the overview table (Table 1; the full table remains in Appendix B), a clearer statement of the two main contributions, and a brief comparison of PB-Exp3 with BAPS (Lin et al., NeurIPS 2023). We also corrected the description of the experiments.

  • Section 2: motivation of the price dynamics from optimal execution, with references and the limit-order-book interpretation.

  • Section 5 and Appendix G.3: relation to BAPS. Its smoothness and geometric-contraction assumptions may fail when the remaining quota is part of the state; Assumption G.2 and Lemma G.4 replace this contraction.

  • Section 6: a summary of the robustness checks in our experiments.

  • Appendix B: an expanded discussion of Bhatia & Sridharan (2020) and of Li et al. (PMLR 2023), which is now cited.

  • Appendix G.8: possible extension to convergence to correlated equilibria via bandit swap regret.

  • Appendix H.3: more details about the policy libraries used in our experiments.

  • Appendix I: the fitted normalized stability margins for each stock.

  • New Appendix J: extensions to nonlinear price dynamics, the uniform schedule and price of anarchy, collusion, and soft quotas.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.