acceptodds
Under review as a conference paper at ICLR 2027

Optimal Regret for Online Market Making with Limit Order Book

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 and Restelli 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 . In this work, we improve upon this guarantee by establishing a high-probability regret bound of . 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.

Primary area:
learning theory
Keywords:
online market making, online learning, limit order book

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_sA1KOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies regret minimization in the sequential market-making problem. Consider a market maker who offers an ask price (AtA_t) and a bid price (BtB_t) for a financial asset to a trader, who holds a private valuation VtV_t for that asset. The trader’s valuation, VtV_t, is stochastic and unknown to the market maker. If a transaction occurs (a purchase or a sale), the market maker then offsets the position by trading with the broader market at a price MtM_t. The market maker’s utility is the price difference between the transaction with the trader and the offsetting transaction with the market. Cumulative regret is defined as the gap between the utility obtained from the sequence of quotes (AtA_t,BtB_t)t_t and the utility that would have been achieved by the optimal decision (a∗,b∗)(a^\ast,b^\ast).

The paper studies this game within a full-feedback framework, where the market maker observes (VtV_t,MtM_t) after each round. Based on a discretization of the set of price pairs (A,B), the authors propose an algorithm with a regret bounded by O~(T)\tilde{\mathcal{O}}(\sqrt{T}). The algorithm estimates the probabilities of prices aa and bb that maximize utility, learning from past observations; it consists of two parallel instances of the Hedge algorithm. Furthermore, the paper establishes that if the VtV_t values are no longer i.i.d. but instead adversarial, the regret cannot be sublinear, meaning that learning is not possible.

In the second part, the paper considers a different setting, referred to as a "limit order book" feedback model. After each round t, the market maker observes MtM_t. The trader’s valuation, VtV_t, is an i.i.d. stochastic variable; it is revealed at the end of the round only if no transaction has taken place between the market maker and the trader. The authors note that, for valuations VtV_t falling between AtA_t and BtB_t, the utility remains estimable even without knowing the exact value of VtV_t. They propose an algorithm similar to the previous one and establish a regret bound of the order of O~(T)\tilde{\mathcal{O}}(\sqrt{T}).

Critical strengths
  • This paper substantially enriches the existing literature on the online market maker problem. It provides new results across several settings. Specifically, in the limit order book feedback setting, it improves upon the result obtained by Maran & Restelli (2026) which featured a regret of O(T2/3)\mathcal{O}(T^{2/3}) by presenting an algorithm with an optimal regret of O(T)\mathcal{O}(\sqrt{T}) (optimal up to a logarithmic factor). It also establishes an analogous result for the full feedback setting which wasn't previously studied and demonstrates that, in the adversarial case, learning is not possible. Cesa-Bianchi et al. (2024) highlighted a similar result, but within the context of bandit feedback.

  • The paper is well written and explained. It reads smoothly overall, and the intuitions behind the solutions are clear. The topic is interesting. It's situated at the intersection of learning and game theory thus covering topics of broader interest.

Critical weaknesses
  • The novelty of the technical contributions is not sufficiently clear. Both algorithms is based on Hedge and the analysis is also classic for the bandit problems. It seemed to be an application of result already known on bandit for a new setting rather than a resolution of a new problem. The paper does not adequately explain which parts of the analysis are new or how they differ from existing approaches. This makes it difficult to assess the extent of the technical advance beyond the narrow scope of this particular problem. A conclusion with a discussion about further applications would have been very useful.
Questions for authors
  1. Could you point out which technical parts represent substantial new contributions or ideas in the study of regret?

  2. I am struggling to determine whether this paper introduces a new theoretical bandit framework or if it is an application of the "partial monitoring bandit" setting. What are the crucial differences between these two paradigms?

1 comment

We thank the Reviewer for the positive evaluation of our work.

  1. The novelty of the technical contributions is not sufficiently clear. Both algorithms is based on Hedge and the analysis is also classic for the bandit problems. It seemed to be an application of result already known on bandit for a new setting rather than a resolution of a new problem. The paper does not adequately explain which parts of the analysis are new or how they differ from existing approaches. This makes it difficult to assess the extent of the technical advance beyond the narrow scope of this particular problem. Could you point out which technical parts represent substantial new contributions or ideas in the study of regret?

We thank the Reviewer for the opportunity to clarify this aspect. The purpose of this work is to close the regret-rate gap in the LOB feedback model introduced by [1], but we believe there are many other technical novelties in the proofs that need to be stressed.

We use a variant of EXP3-IX, but obtaining our guarantees requires the interval feedback reconstruction (Lemma 4.1), its logarithmic observation cost bound (Lemma 4.2), and the continuous optimum approximation (Lemma 3.2). This suggests that one could potentially apply the same reasoning beyond market making in problems where additional observations are implicitely given, although our established results concern the model studied here.

More specifically, Lemma 4.2 bounds the aggregate importance-weighting cost logarithmically in the grid size, improving over the polynomial dependence associated with treating grid points as ordinary bandit arms. This is the main novelty of our approach and allows us to improve on previous results. In Lemma 3.2 we transfer the discrete action guarantee to the continuous space, despite potentially discontinuous utilities. Lemma 3.2 establishes an O(1/K)O(1/K) approximation of the optimal cumulative expected utility under stochastic valuations and adversarial prices, without assuming a Lipschitz valuation CDF or concavity of the utility.

We also believe that a more straightforward reduction for the full-feedback setting can itself be viewed as a contribution, particularly at a time when overcomplication is becoming increasingly common.

  1. I am struggling to determine whether this paper introduces a new theoretical bandit framework or if it is an application of the "partial monitoring bandit" setting. What are the crucial differences between these two paradigms?

Our problem can be formulated within the general partial monitoring framework, as LOB feedback provides additional, action-dependent information beyond the learner’s realized payoff. Our contribution concerns the regret guarantees and limits of learnability in this particular market making model.

We believe it is necessary to distinguish between this general formulation and the applicability of existing finite actions results. Our bid–ask action space is continuous, while the utility can be discontinuous. Discretization therefore requires both a controlled approximation of the continuous benchmark and a learning guarantee with sufficiently mild dependence on the grid size. The standard partial monitorning bandit alone does not establish these properties [2]. We use the ordered structure of prices and the information revealed throughout the interval between the sampled quotes in the results. In particular, the analysis of Lemma 4.2 is closely related to methods for graph-structured feedback [3], but requires a specific observation cost bound for the interval induced by two independently sampled endpoints, which is novel.

We will surely include this discussion in the final version of the paper.

[1] Maran & Restelli, 2026. Online market making and the value of observing the order book

[2] Bartók, G., Foster, D. P., Pál, D., Rakhlin, A., & Szepesvári, C. (2014). Partial Monitoring—Classification, Regret Bounds, and Algorithms. Mathematics of Operations Research, 39(4), 967–997. http://www.jstor.org/stable/24540997

[3] Alon, N., Cesa-Bianchi, N., Dekel, O., & Koren, T. (2015, June). Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory (pp. 23-35). PMLR.

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

This paper investigates a classical market-making scenario in which a learner (market maker) must design an optimal bid–ask pricing scheme to optimise the platform's profits. The authors study two cases: full feedback and the limit order book. The authors provide a sublinear regret guarantee for the full-feedback setting and an impossibility condition for achieving sublinear regret in the full-feedback setting with two-sided adversarial feedback. To accomplish the regret bounds, regret is decomposed into two components and analysed geometrically on a 2D grid – via a gradual discretisation argument.

Critical strengths

Clear mission statement of their contributions, and of what the paper is addressing. The writing and clarity are very good.

The impossibility condition regarding two sided adverarial feedback is very pertinent to understand learning in market making.

Critical weaknesses

In the canonical market-making example, the valuation of the trader is typically not observed by the market maker... but here it is. I am not sure whether this algorithm reflects a real trading environment.

Questions for authors

A very interesting concept is "market maker immediately offloads its position on a perfectly" this is almost never possibly in high volumes. How would this affect the authors model.

Any justification why valuation of the trader is revealed to the algorithm? (See weakness)

Regarding parameter K seems like one could make this arbitrarily large such that Lem 3.2 can hold. Could the authors explain how K is selected exactly (perhaps I misread).

Consider a portfolio of assets, where gains from one financial asset could offset losses of another. Here we study the bid ask of one asset, what if we consider a collection of assets, could we take more risk with the learning algorithm - and possible address the impossibility condition of the full adversarial environment?

2 comments

We thank the Reviewer for the positive evaluation of our work.

A very interesting concept is "market maker immediately offloads its position on a perfectly" this is almost never possibly in high volumes. How would this affect the authors model.

We thank the Reviewer for raising this point. In our idealized setting, we do not assume any transaction cost nor liquidity loss. We could think of a different utility incorporating also these aspects, for example: utc(a,b,Mt,Vt)=I(Vt≤b)(Mt−b−cB)+I(Vt>a)(a−Mt−cA),u_t^c(a,b,M_t,V_t)= \mathbb I(V_t \leq b)(M_t-b-c_B) + \mathbb I(V_t > a)(a - M_t-c_A), where cB,cA≥0c_B,c_A \geq 0 represent fixed commission costs. By using this utility in the algorithm we expect the same results as the ones presented in the paper, as our construction is up to constant shifts. In the same way, liquidity loss would change our utility function, for example similarly to [1] by an additional convex component. While this might be an interesting future direction for our work, additional considerations regarding inventory and states of the system would be necessary, which go beyond the present scope.

We finally point out that the present model relying on immediate liquidation is standard in related literature [2][3].

In the canonical market-making example, the valuation of the trader is typically not observed by the market maker... but here it is. I am not sure whether this algorithm reflects a real trading environment. Any justification why valuation of the trader is revealed to the algorithm?

As already noted in [3], this assumption captures a fundamental aspect of real markets with a limit order book, which is price volatility in response to demand. In a limit order book the market maker observes the placed orders that have not been executed yet. We assume that true private valuations are observed only when we do not trade. That is because after a trade these valuations may change rapidly as the market reacts, so that the real valuation, if made public, is truly observable only when no trade occurred. This provides an economic interpretation of our modeling assumption.

From a theoretical perspective, our assumption interpolates between bandit feedback and full feedback, as described in the warm-up section. While bandit feedback is insufficient to achieve sublinear regret even for iid prices without additional hypotheses [2], we prove that LOB feedback provides stronger guarantees even under adversarial market prices.

Regarding parameter K seems like one could make this arbitrarily large such that Lem 3.2 can hold. Could the authors explain how K is selected exactly (perhaps I misread).

The parameter KK is chosen to balance the exploration cost and the approximation accuracy. Specifically, setting K=TK=\sqrt{T} is sufficient to achieve the desired regret rate. Lemma 3.2 holds for any KK, while Theorem 3.3 shows that discretization contributes 5T2K\frac{5T}{2K} to the regret. We could also choose K=O(Tα)K=\mathcal{O}(T^\alpha) for any α≥1/2\alpha\geq 1/2, but the Hedge component would still yield O(T)\mathcal{O}(\sqrt{T}) cumulative regret [4].

We surely include this discussion in the final version of the paper.

Consider a portfolio of assets, where gains from one financial asset could offset losses of another. Here we study the bid ask of one asset, what if we consider a collection of assets, could we take more risk with the learning algorithm - and possible address the impossibility condition of the full adversarial environment?

The extension to multiple assets is an interesting open direction. In our setting, however, even assuming just one adversarial price process is enough to incurring linear regret, as our result highlights an intrinsic difficulty of the problem. For instance, let us consider dd assets indexed by i=1,…,di=1,\dots,d, as you describe. For asset i=1i=1, let the market follow the process {(Mt1,Vt1)}t=1T\{(M_t^1,V_t^1)\}_{t=1}^T described in Theorem 5.1. For all other assets j∈{2,…,d}j\in\{2,\dots,d\}, let Vtj=Mtj=1/2V_t^j=M_t^j=1/2 for every t=1,…,Tt=1,\dots,T. These additional processes provide no information about the first asset, so we still incur linear regret.

Nevertheless, additional structure, such as contextual information, could lead to substantially different learning scenarios. We thank the Reviewer for suggesting this new perspective.

[1] Barzykin, A., Bergault, P., & Guéant, O. (2023). Algorithmic market making in dealer markets with hedging and market impact. Mathematical Finance.

[2] Nicolo Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, and Vinayak Pathak, (2025). Market making without regret

[3] Maran & Restelli, (2026). Online market making and the value of observing the order book

[4] Francesco Orabona, (2025). A modern introduction to online learning

I thank the authors for their response, I've read the rebuttal and I am satisfied with the response. My assessment remains the same.

Reviewer_fJnkOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The authors consider online learning in market making in T rounds,to derive a high-probability regret bound of O(√T) improving an expected regret bound of O(T2/3) of Maran & Restelli (2026)。 The reliance on a fixed horizon TT T reduces the work to a theoretical exercise, sacrificing the algorithmic novelty required for continuous, non-stationary trading environments. Validity The validation is likely compromised by artificial "cold start" assumptions and a lack of robustness checks against misspecified time horizons, failing to prove real-world trading efficacy.

Critical strengths

The paper's value lies in its pedagogical clarity, demonstrating that a standard method is sufficient and thereby preventing the unnecessary over-engineering of complex solutions.

Critical weaknesses

The paper's reliance on a fixed, known time horizon T is unrealistic for continuous market-making operations, severely limiting its practical applicability. Furthermore, the lack of comparative empirical analysis against domain-specific baselines makes it impossible to verify whether the theoretical guarantees translate into superior real-world performance.

Questions for authors
  1. Robustness to Indefinite Horizons: Given that the theoretical analysis relies on a fixed, known time horizon T T, can you provide a theoretical justification or empirical evidence demonstrating that the regret bounds remain valid if the trading session is indefinite or if T is unknown? 2. Comparison with Domain-Specific Baselines: Can you provide a comparison of your method against standard financial market-making models (e.g., Avellaneda-Stoikov) or recent Reinforcement Learning baselines? This is necessary to confirm that the theoretical guarantees translate into competitive empirical performance against state-of-the-art strategies.
1 comment

We thank the Reviewer for the effort in evaluating our work.

  1. The paper's reliance on a fixed, known time horizon TT is unrealistic for continuous market-making operations, severely limiting its practical applicability. Given that the theoretical analysis relies on a fixed, known time horizon TT, can you provide a theoretical justification or empirical evidence demonstrating that the regret bounds remain valid if the trading session is indefinite or if TT is unknown?

We believe there is a possible misunderstanding here. Relying on a fixed time horizon is a standard assumption in online learning [1][2][3]. In finite-time regret analysis, TT denotes the length of the period over which performance is evaluated against an appropriate hindsight benchmark, even when the algorithm operates indefinitely. Specifying such an evaluation period should be distinguished from requiring the learner to know its length in advance.

As concerns the knowldege of TT, we use it to properly discretize the decision space. To sidestep the issue, it is possible to have an extension without knowledge of TT through a variant of a doubling trick, as explained in [4]. Specifically, we might instantiate successive epochs of planned lengths Hj=2j+1H_j=2^{j+1}, j=0,1,…j=0,1,\dots. At the beginning of each epoch jj, one can initialize Algorithm 3 (or Algorithm 2) with Kj=⌈Hj⌉K_j=\lceil\sqrt{H_j}\rceil and parameters calibrated to HjH_j. The guarantees proven in Appendix A and B hold true for each epoch and the high probability result follows summing over the epochs, given that the confidence bounds are adequatly selected.

We finally remark that both the assumptions are standard in related works [5][6], which were published in a top conference such as COLT.

  1. Comparison with Domain-Specific Baselines: Can you provide a comparison of your method against standard financial market-making models (e.g., Avellaneda-Stoikov) or recent Reinforcement Learning baselines? This is necessary to confirm that the theoretical guarantees translate into competitive empirical performance against state-of-the-art strategies.

We believe that providing a comparison between our methods and existings ones would not be well-posed. Indeed, existing methods as the ones pointed out by the Reviewer are not completely online, as they are not made to minimize the regret. Additionally, our work addresses a different question, which is characterizing the regret achievable under limit order book feedback when market prices are chosen by an adaptive adversary, while the original Avellaneda–Stoikov framework optimizes a risk sensitive terminal-wealth objective [7]. Compared to that, our guarantees require neither a specified stochastic model for market prices nor prior knowledge of volatility or a parametric valuation distribution, allowing for arbitrary price sequences. An empirical comparison with financial or RL strategies could be informative under a suitably harmonized protocol, as the feedback assumptions and objectives are substantially different from the ones in [7], but would address a complementary question to our theoretical characterization.

Since these aspects are crucial, please let us know if further discussion is necessary.

[1] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, Learning, and Games.

[2] Luo, H. & Schapire, R.. (2014). Towards Minimax Online Learning with Unknown Time Horizon. Proceedings of the 31st International Conference on Machine Learning.

[3] Tor Lattimore and Csaba Szepesvari. Bandit algorithms, (2020).

[4] Besson, L., & Kaufmann, E. (2018). What doubling tricks can and can't do for multi-armed bandits. arXiv preprint arXiv:1803.06971.

[5] Maran & Restelli, (2026). Online market making and the value of observing the order book

[6] Nicolo Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, and Vinayak Pathak, (2025). Market making without regret

[7] Avellaneda, M., & Stoikov, S. (2008). High-frequency trading in a limit order book. Quantitative Finance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.