Optimal Regret for Online Market Making with Limit Order Book

arXiv:2610.09691 · cs.GT, cs.LG · Submitted 2026-10-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Optimal Regret for Online Market Making with Limit Order Book".

Jane: The gist The authors study online learning in market making, where at each round,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at the paper "Optimal Regret for Online Market Making with Limit Order Book". The main idea is studying online learning in market making where you post bid and ask prices before you see the actual market price and a trader's private valuation. It sets out to improve on existing expected regret bounds, moving from something like Oe(T squared over three) to a high-probability bound of Oe(root of T).

Jane: That sounds really technical for someone just listening in. So what are they actually claiming about this online learning in market making? What's the big picture here?

Tom: They're looking at two main feedback models. First, the full-feedback setting where you see both the market price and the trader's valuation every single round. And second, a more realistic one called a limit order book feedback model, where you only find out about the trader's valuation if no transaction happens.

Lu: In essence, they tackle how much regret we can expect when we don't know exactly what the market price will be or what the incoming trader values everything before we act. They establish a high-probability regret bound of Oe(root of T) in both settings.

Meng: I wonder what that means for someone trying to actually deploy this in production. If you're dealing with these kinds of unknown valuations, how much learning do you really get for your money?

Lalam: The paper shows that even with the less informative limit order book feedback, they can achieve a regret bound of Oe(root of T) even when the market prices are chosen adversarially. This is an improvement over previous expected regret bounds like Oe(T squared over three) which only held in expectation and assumed you were playing against someone who wasn't trying to help you.

Tom: That sounds like a solid jump from an expected bound to a high-probability one, which is what matters when you're actually running a system. But they also found some impossibility results when things get really adversarial.

Jane: Impossibility results sound heavy for driving around or cooking, but they show the limits of what we can learn in these systems. What kind of limits are they finding?

Lu: They prove that sublinear regret is impossible when both the market prices and trader valuations are chosen adversarially in a full-feedback setting. Specifically, they prove a linear regret lower bound of RT greater than or equal to T to the sixth power in that case.

Meng: A linear lower bound sounds bad for learning; it means you can't do much better than just guessing the best move every time. So what's the practical implication there?

Tom: It shows that if the environment is truly adversarial, you can't rely on a learning algorithm to get much better than random play. But they also showed that this impossibility result doesn't hold even when you observe all the valuations at the very end of each round.

Paper summary: Jane: So, it seems like there are some conditions where learning is possible, but when those conditions break down, it becomes fundamentally unlearnable in a certain sense. What about the limit order book feedback model they focused on?

Lalam: For that specific case, the analysis shows they can achieve a high-probability regret bound of Oe(root of T) even against an adaptive adversary. The paper uses a technique where it exploits the feedback structure to reconstruct losses for the time interval between those sampled quotes.

Tom: That reconstruction idea sounds like a clever way to get more information from less frequent feedback events. What's the concrete result they got there?

Jane: They find that with K equal to root of T and eta equal to p over T, they get a regret bound of RT equal to O(root of T log T delta) with probability at least one minus delta. That's pretty tight for what they achieved.

Lu: That result is optimal up to logarithmic factors, matching the standard lower bound for the multi-armed bandit problem. They are saying that this level of performance is what you can expect in these stochastic environments when you have that kind of feedback structure.

Meng: If we were deploying an actual market making system, would we use the full-feedback method or stick with the limit order book model? What are the trade-offs between those two approaches?

Tom: The paper compares them in Table one <ref:2610.09691#pg3>. The full feedback setting, even with adversarial prices and valuations, doesn't guarantee sublinear regret, it gets Omega of T. But the limit order book setting gives us that Oe(root of T) we talked about earlier.

Jane: So the main message for us is that the type of information you get—full feedback versus limit order book feedback—really dictates how well you can learn in this online market making scenario. This paper, "Optimal Regret for Online Market Making with Limit Order Book", shows that we can achieve a high-probability regret of Oe(root of T) in the latter setting.

Lu: And it also clarifies the limits when you assume full feedback and adversarial conditions, showing that sublinear regret is impossible under those strong assumptions.

Meng: It's interesting how much the feedback structure matters when we think about real-world constraints like transaction costs or latency affecting that information flow. That's what makes this paper relevant for deployment concerns.

Lalam: I'm pretty sure of this answer because it comes from a deep dive into the mathematical structure of the problem, and it shows how assumptions on the environment and feedback directly affect market making learnability.

Tom: Alright, so we've covered the main claims about regret bounds in both full feedback and limit order book settings, including those impossibility results. That wraps up our look at "Optimal Regret for Online Market Making with Limit Order Book".

Conclusion: Tom: So we're wrapping up our look at "Optimal Regret for Online Market Making with Limit Order Book." The core idea is that they found ways to get better performance in online trading when you don't have perfect information about everything happening.

Jane: It boils down to them showing that even if the feedback is less detailed, like only knowing about a trade if one actually happens, you can still learn pretty well.

Tom: Yeah, they established these high-probability regret bounds of Oe(root of T) in that specific limit order book setting. That's a big improvement over older expected regret bounds which were much worse.

Lu: What's really interesting is how they handle the structure of that feedback loop, because it lets them reconstruct losses for the time between those quotes. It’s a clever way to get more information from less frequent events.

Meng: From a deployment standpoint, Oe(root of T) sounds like something we could actually aim for if we can manage that estimation part without adding too much overhead. But what about the worst-case scenarios?

Lalam: The paper also tackles those impossibility results, showing that in a fully adversarial environment with full feedback, you hit a linear regret lower bound of RT greater than or equal to T to the sixth power.

Jane: That means if you're playing against someone who is actively trying to make your life as hard as possible, sublinear regret just isn't achievable under those strong conditions.

Tom: It highlights that the quality of the feedback model really dictates what kind of learning you can expect in these market-making scenarios.

Lu: And they also showed that even with full feedback, if things are completely adversarial, you still face those high regret bounds when using Yao's minimax principle. It’s a strong statement about the fundamental limits of learnability there.

Meng: So it seems like the paper gives us two paths: optimize for a more realistic limit order book setup to get good regret, or understand the hard walls when you try to play against an optimal opponent with perfect info.

Jane: Exactly. It shows that understanding how much information you get from your environment is just as important as choosing the right learning algorithm itself.

Tom: And that leads us nicely into what happens next—we're going to look at those specific mathematical constructions they use to prove those bounds and see how they work in practice.

Maria Elena Vischi, Francesco Emanuele Stradi, Alberto Marchesi

Politecnico di Milano

cs.GT, cs.LG

Submitted: 2026-10-07

Updated: 2026-10-07

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: The gist The authors 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

Key concepts

Full-Feedback Setting: This setting occurs when the market maker observes both the current market price and the trader's private valuation at every round. The algorithm uses two independent Hedge instances, one for bid prices and one for ask prices, to manage these combined pieces of information effectively.
Limit Order Book Feedback: In this weaker setting, the trader's valuation is only revealed if no transaction occurs. The authors show that even with this limited feedback from the limit order book, they can achieve a high-probability regret bound of $O(\sqrt{T})$, which is an improvement over previous expectation-based bounds.
Impossibility Results: These results demonstrate that in fully adversarial environments, sublinear regret is impossible. By constructing specific random sequences of prices and valuations, they prove a linear lower bound on the regret ($RT \geq T^6$), meaning the market maker cannot learn efficiently against an intelligent opponent.

Terminology

Regret — 1× in this paper · explained in 3 episodes

Summary

The gist The authors 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.

Optimal Regret Guarantees

The work establishes optimal regret bounds under different feedback models for online market making <ref:2610.09691#pg3> The authors improve upon an expected regret bound of Oe(T 2/3) to a high-probability regret bound of Oe(√T) <ref:2610.09691#pg3> They first consider the full-feedback setting, where the learner observes both the market price and the trader’s valuation at each round <ref:2610.09691#pg7> The algorithm combines two Hedge instances, one for bid prices and one for ask prices <ref:2610.09691#pg7> This approach achieves a regret bound of RT ≤ O(p T log(T) + p T log(1/δ) + log(1/δ)) with probability at least 1 − δ when using K = ⌈√T⌉ and η = q/log(T) <ref:2610.09691#pg7>

Limit Order Book Feedback Analysis

The paper addresses the substantially weaker feedback induced by a limit order book, where the trader’s valuation is revealed only if no transaction occurs <ref:2610.09691#pg3> The authors establish a high-probability regret bound of Oe(√T) for this setting even against an adaptive adversary <ref:2610.09691#pg7> This improves upon the previous Oe(T 2/3) bound which held in expectation and assumed an oblivious adversary <ref:2610.09691#pg3> The analysis exploits the feedback structure, allowing the learner to reconstruct losses for the interval between sampled quotes <ref:2610.09691#pg7> The regret bound in this case is RT = O(√T log T δ), with probability at least 1 − δ when selecting K = ⌈√T⌉ and η = β = p/T <ref:2610.09691#pg7>

Impossibility Results

The paper investigates the limits of learnability in fully adversarial environments, showing that sublinear regret is impossible when both market prices and trader valuations are chosen adversarially <ref:2610.09691#pg6> Specifically, they prove a linear regret lower bound RT ≥ T 6 for the full-feedback setting under adversarial sequences <ref:2610.09691#pg11> This impossibility result holds even when the entire valuations are observed at the end of each round <ref:2610.09691#pg11>

Key Contributions and Methodology

The main contributions include establishing optimal regret under full feedback, showing that sublinear regret is impossible in fully adversarial environments, and proving optimal high-probability regret under limit order book feedback <ref:2610.09691#pg2> The algorithm for the full-feedback case uses two independent instances of Hedge <ref:2610.09691#pg7> For the limit order book case, Algorithm 3 employs two parallel instances of an EXP3-based algorithm to estimate losses using observed feedback <ref:2610.09691#pg9> Lemma 4.2 bounds the ratios between sampling probabilities and observation probabilities, yielding a dependence of O(log K) in the regret bound <ref:2610.09691#pg10> The final result for Algorithm 3 is RT = O(√T log T δ), with probability at least 1 − δ <ref:2610.09691#pg9>

Impossibility in Full Feedback

The impossibility result for the full-feedback, fully adversarial case shows that there exists a sequence where expected regret RT ≥ T 6 <ref:2610.09691#pg11> This is proven using Yao’s minimax principle by constructing a random instance of the problem where the relevant price interval shrinks at random in each round <ref:2610.09691#pg11> The construction involves setting (Lt, Ut) = (Lt-1, Ut-1 - 2Dt-1/3) with probability 1/2 and (Lt, Ut) = (Lt-1 + 2Dt-1/3, Ut-1) with probability 1/2 <ref:2610.09691#pg10> This leads to the conclusion that the expected utility for a deterministic algorithm playing (At, Bt) ∈ U is E [ut(At, Bt)] ≤ 1/3 <ref:2610.09691#pg10>

Optimal Bounds for LOB

The analysis for Algorithm 3 demonstrates that by selecting K = ⌈√T⌉ and η = β = p/T, the regret attains RT = O(√T log T δ), which is optimal up to logarithmic factors <ref:2610.09691#pg9> The proof relies on bounding the difference between the estimated losses and the realized mean loss using supermartingale properties <ref:2610.09691#pg14> The final bound derived is RT ≤ O˜(√T) <ref:2610.09691#pg9>

Impossibility Result Summary

The impossibility result for fully adversarial environments, even under full feedback, shows that market making is unlearnable in this setting <ref:2610.09691#pg11> This is proven by constructing a sequence where the learner cannot anticipate which part of the interval will remain <ref:2610.09691#pg11> The construction involves setting (Vt, Mt) = (Lt, 1) with probability 1/2 and (Vt, Mt) = (Ut, 0) with probability 1/2 <ref:2610.09691#pg10> This leads to the conclusion that for any probabilistic algorithm, RT ≥ T 6 <ref:2610.09691#pg10> The overall findings clarify how assumptions on the environment and feedback affect market making learnability <ref:2610.09691#pg2>

Impossibility Result Summary

The final section provides a proof of the unlearnability result for market making under full feedback and an oblivious adversary <ref:2610.09691#pg11> This is done by relying on Yao’s minimax principle <ref:2610.09691#pg10> The construction involves setting (Lt, Ut) = (Lt-1, Ut-1 - 2Dt-1/3) with probability 1/2 and (Lt, Ut) = (Lt-1 + 2Dt-1/3, Ut-1) with probability 1/2 <ref:2610.09691#pg10> This leads to the conclusion that for any deterministic sequence of prices, the expected utility is E [ut(At, Bt)] ≤ 1/3 <ref:2610.09691#pg10> Therefore by Yao’s principle, RT ≥ T 6 <ref:2610.09691#pg10> The paper concludes that sublinear regret is impossible in fully adversarial environments <ref:2610.09691#pg6>

Impossibility Result Summary

The impossibility result for fully adversarial environments, even under full feedback, shows that market making is unlearnable in this setting <ref:2610.09691#pg11> This is done by relying on Yao’s minimax principle <ref:2610.09691#pg10> The construction involves setting (Lt, Ut) = (Lt-1, Ut-1 - 2Dt-1/3) with probability 1/2 and (Lt, Ut) = (Lt-1 + 2Dt-1/3, Ut-1) with probability 1/2 <ref:2610.09691#pg10> This leads to the conclusion that for any deterministic sequence of prices, the expected utility is E [ut(At, Bt)] ≤ 1/3 <ref:2610.09691#pg10> Therefore by Yao’s principle, RT ≥ T 6 <ref:2610.09691#pg10> The paper concludes that sublinear regret is impossible in fully adversarial environments <ref:2610.09691#pg6>

Impossibility Result Summary

Improvements for AI systems

textbfIncreased Regret Guarantee under Limit Order Book Feedback (LOB): The improved system can maintain a high-probability regret bound of Oe(√T) even when facing an adaptive adversary choosing market prices, which is superior to the previous expected regret bound of Oe(T2 / 3) established in Maran and Restelli [2026]. This allows the AI to perform more robustly in real-world trading environments where full information is not always available at every step, as it improves upon this guarantee.
textbfOptimal Strategy Selection via Discretization: The system employs a discretization of the bid–ask space based on two coupled grids and combines it with Hedge to achieve the desired regret rate, specifically maintaining an O(√T) regret bound under full feedback. This enables the AI to select optimal quotes by sampling from these distributions, as detailed in Algorithm 2, which combines two Hedge instances.
textbf Enhanced Information Utilization in LOB Setting: The system leverages the structure of limit order book feedback to reconstruct losses at every grid point between sampled quotes, allowing it to achieve the same regret rate as under full feedback. This is achieved because each round allows the learner to reconstruct losses for the interval between the sampled quotes.
textbf Adaptive Learning Against Adversarial Valuations: The system establishes that sublinear regret is impossible in fully adversarial environments, even under full feedback, motivating a stochastic assumption on valuations and preventing sublinear regret when both market prices and trader valuations are chosen adversarially. This informs the AI about the limits of learnability in highly competitive or malicious market settings.
textbf Linear Regret Lower Bound for Full Feedback Adversarial Settings: The system provides a linear regret lower bound of RT ≥ T6 when facing adversarial sequences under full feedback, demonstrating that market making is unlearnable in a fully adversarial environment, even when the entire valuations are observed at the end of each round. This result sets a theoretical ceiling on performance in perfectly adversarial learning scenarios.

Optimal Regret for Online Market Making with Limit Order Book

Listen

Transcript

Key concepts

Terminology

Summary

Improvements for AI systems

Sources

Related papers