Optimal Regret for Online Market Making with Limit Order Book

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.