CS Paper Radar

Regret Bounds for Market Making with Persistent Orders

Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak

cs.GT cs.LG ·submitted 2026-11-04 08:39 UTC · v1

Abstract

We study adversarial market making with orders that remain active until execution. The maker operates on two markets: a primary market where orders are made and a secondary market where the resulting positions are hedged. In each round, the maker posts a quote on the primary market before observing both primary and secondary market prices. An order executes when the primary price reaches its quote, and the resulting position is immediately offset at the secondary price. When both price sequences are chosen by an adversary over $T$ rounds, we give a simple deterministic policy with regret of order $\log T$ against the best fixed quote (static comparator) and $\sqrt T$ against the best quote for each submission date (dynamic comparator), plus two terms measuring exposure to future primary and secondary prices. These rates remain optimal even when both exposure terms vanish and lower bounds show that the exposure terms are necessary. Our policy naturally extends to simultaneous bids and asks, where we show that static and dynamic regret are both characterized (up to constant factors) by the exposures terms (where the primary price exposure $V_T^{\mathrm{two}}$ now accounts for both bids and asks) and a term of order $\sqrt{V_T^{\mathrm{two}}\log T}$. Our policy is simple, efficient and fully parameterless. We extend this setting by demonstrating how natural assumptions on the price processes lead to improved guarantees without changing the policy.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Regret for Online Market Making with Limit Order Book

cs.GT cs.LG ·2026-10-07 ·Maria Elena Vischi, Francesco Emanuele Stradi, Alberto Marchesi
hot direction similarity 0.72
Abstract

We study online learning in market making, where, at each round, a market maker posts bid and ask prices before observing the market price and the private valuation of an incoming trader. In this setting, Maran et al. 2026 introduce a feedback model motivated by limit order books, in which the trader's valuation is revealed only if no transaction occurs. Assuming that trader valuations are drawn i.i.d. from an unknown distribution while market prices are chosen adversarially, they establish an expected regret bound of $\widetilde{\mathcal{O}}(T^{2/3})$. In this work, we improve upon this guarantee by establishing a high-probability regret bound of $\widetilde{\mathcal{O}}(\sqrt{T})$. As a warm-up, we first consider the full-feedback setting. We introduce a discretization of the bid-ask space based on two coupled grids and combine it with Hedge to achieve the desired regret rate. Building on these ideas, we then address the substantially weaker feedback induced by a limit order book and develop an algorithm that achieves the same guarantee. Finally, we investigate the limits of learnability in fully adversarial environments, where the valuations may vary arbitrarily as well. Perhaps surprisingly, we show that when both market prices and trader valuations are chosen adversarially, sublinear regret is impossible even under full feedback, thereby motivating our stochastic assumption on the valuations.

0.28

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism

cs.GT cs.DScs.LG ·2026-11-05 ·Johannes Brüstle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi
similarity 0.66
Abstract

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a $\tilde O(T^{\frac 23})$ regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight $\tilde{O}(\sqrt{T})$ regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is $\tilde Θ(T^{\frac 35})$. This last result contrasts with the $\tilde{O}(\sqrt{T})$ regret bound that can be obtained for one-sided pricing with regular distributions.

0.15

Impossibility of No-Regret in Multi-Agent Bidding

cs.GT cs.CCcs.LG ·2026-10-27 ·Zongjun Yang, Rachitesh Kumar, Christian Kroer
theory similarity 0.65
Abstract

We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.

0.08

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

cs.LG ·2026-09-26 ·Mengxiao Zhang, Yingfei Wang, Haipeng Luo
benchmarktheory similarity 0.64
Abstract

We study online dynamic pricing with censored demand, where an arbitrary inventory level is revealed before pricing and may adapt to past observations, while demand follows an unknown, price-dependent distribution that is stationary over time. For a horizon of $T$ rounds, Xu et al. [2026] achieved $\widetilde{\mathcal{O}}(\sqrt{T})$ regret under restrictive structural assumptions including linear demand, price-independent additive noise, and conditions relating inventory levels to the noise support. Our first contribution is to extend this framework to a substantially more general and statistically harder nonparametric setting, requiring only the natural assumption that expected sales are nonincreasing in price and allowing nonlinear demand curves and price-dependent noise. For this model, we first propose a simple baseline, Double-Grid-UCB, which discretizes both price and inventory and achieves $\widetilde{\mathcal{O}}(T^{3/4})$ expected regret using separate revenue estimates for each price-inventory grid pair. Then, we develop Threshold-UCB, which improves the expected regret to $\widetilde{\mathcal{O}}(T^{2/3})$. Unlike Double-Grid-UCB, Threshold-UCB reuses sales observations across inventory levels through shared estimates of demand-tail probabilities, allowing the same data to support revenue upper bounds for multiple inventories rather than a single inventory bin. We also complement this upper bound with an $Ω(T^{2/3})$ lower bound via a reduction from stochastic posted pricing, establishing its minimax optimality. Finally, extensive experiments across inventory processes, demand functions, and noise models demonstrate consistently superior performance of Threshold-UCB over benchmark algorithms.

0.23

Spreads Don't Price a Rival Market Maker's Information

cs.GT ·2026-11-14 ·Oliver James Oberle, Damien Berriaud, Roger Wattenhofer
publishedbenchmark similarity 0.64
Abstract · 9 pages, 2 figures. Published in the proceedings of ICAIF '26

When one market maker becomes better informed, do its competitors widen their bid-ask spreads? Adverse-selection reasoning suggests that they should, because the better-informed maker avoids toxic order flow and leaves more of it to the others, and the closest model of competition with an informed dealer predicts more conservative quotes by the uninformed dealers. We study this question in a stochastic quoting game in which one maker receives a private signal of varying precision about a persistent state that drives order flow. Strategies are learned with independent reinforcement learning, which we benchmark against an exact dynamic-programming solution of the single-agent case. In none of the configurations we examine does the average spread of the uninformed makers increase with the rival's precision. Where competition for order flow is weak, the slope of their spread in precision is statistically equivalent to zero within half an action tick; where competition is strong, their spread tightens. The informed maker's own spread tightens markedly in every configuration and serves as a positive control. These results hold with two, three and four makers, across an eightfold variation in the depth of the background liquidity, with a background quote that reprices after toxic fills, and under price-time priority. Our measurements point to a competitive trade-off. In the model the total toxicity of the flow does not depend on any maker's information. A better-informed maker avoids more of it, and where this leaves more toxic flow to its competitors, it also quotes more tightly, so that a wider quote would cost them more order flow than it would save in adverse selection. The uninformed makers adjust the skew of their quotes and their inventory instead, and the rival's information changes the distribution of profits across makers while quoted spreads remain nearly unchanged.

0.38

Optimal Regret for Profit Maximization in Bilateral Trade

cs.GT cs.LG ·2026-11-06 ·Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
theory similarity 0.64
Abstract

Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{2/3})$ against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of whether this absence of a curse of dimensionality extends to arbitrarily high dimensions.

0.13

Online Resource Allocation with Replenishable Budgets

cs.GT ·2026-09-28 ·Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Alberto Marchesi
similarity 0.63
Abstract

Online Resource Allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints. Classical ORA models typically assume that resources are monotonic, meaning that selecting actions can only decrease the available budget. In this work, we study a more general setting with replenishable budgets, in which actions may either consume or replenish resources over time. This extension is necessary to capture scenarios such as inventory systems or energy markets in which capacity can be actively recovered. We develop a dual-based algorithm that recovers best-of-both-worlds guarantees for standard ORA when the replenishment factor $β= 0$, and improves them when $β> 0$. In particular, our algorithm attains $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic setting and $\widetilde{\mathcal O}(\sqrt{T})$ $α$-regret in the adversarial setting, where $α$ depends on the per-round budget and on the replenishment factor of the void action. Moreover, the algorithm ensures strict satisfaction of the budget constraints.

0.12

No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints

cs.LG ·2026-10-17 ·Davide Maran, Marcello Restelli, Francesco Emanuele Stradi
theorycode/data similarity 0.63
Abstract

Market makers keep trading efficient by setting bid and ask prices for buyers and sellers. In sequential market making, trades happen independently based on price thresholds, requiring the market maker to maintain balanced, low-risk inventory over T rounds. This paper studies how to maximize revenue with unknown buyer and seller valuations using regret minimization. When the market maker only sees trade success or failure, an algorithm achieves regret and inventory bounds proportional to T to the power of 2/3. When full order book data is available for failed trades, regret and inventory limits improve significantly to the square root of T. We also establish a fundamental trade-off via a lower bound, by proving that tighter round-by-round inventory limits strictly force higher minimum regret.

0.29