Online Market Making and the Value of Observing the Order Book

Technical Summary: Online Market Making and the Value of Observing the Order Book

Problem Formulation
This paper addresses the online market-making problem, where an agent (the "maker") sequentially posts bid ($B_t$) and ask ($A_t$) prices for a single asset to interact with traders holding private valuations ($V_t$). The asset has an objective market value ($M_t$) realized at the end of each round. The agent's goal is to minimize regret relative to the best fixed bid-ask strategy in hindsight.

The core challenge lies in the feedback structure. In traditional formulations (e.g., Cesa-Bianchi et al., 2024), feedback is fully censored (bandit feedback): the agent only observes whether a trade occurred. This paper introduces a novel action-dependent feedback model inspired by real Limit Order Books (LOB). The feedback mechanism is defined as follows:

• Trade Occurs: If $V_t \le B_t$ (Maker buys) or $V_t \ge A_t$ (Maker sells), a trade happens. The agent observes the market price $M_t$ but not the trader's private valuation $V_t$.
• No Trade: If $B_t < V_t < A_t$, no transaction occurs. Crucially, the agent observes the trader's valuation $V_t$ (and $M_t$).

This creates a regime where informative feedback is obtained precisely when the instantaneous reward is zero. The agent faces a tension between narrowing the spread to maximize profit (which risks missing informative "no-trade" events) and widening the spread to gather information about the distribution of valuations.

Methodology and Algorithms
The authors propose three distinct algorithms tailored to different assumptions about the market price process $M_t$:

1. Stochastic Independent Prices (Algorithm 1: OPSR):

   • Assumption: $M_t$ is an i.i.d. sequence with unknown mean $\mu$.
   • Approach: The Optimistic/Pessimistic Successive Rejects (OPSR) algorithm. It maintains a discrete set of candidate bid-ask prices.
   • Mechanism: It utilizes an elimination strategy. At each step, it constructs optimistic and pessimistic confidence intervals for the cumulative distribution function (CDF) of $V_t$ and the mean of $M_t$.
   • Estimation: Even though $V_t$ is only observed when no trade occurs, the algorithm constructs a surrogate estimator for the CDF using "clipped" observations ($V^{clip}_t$). It eliminates sub-optimal actions only when confidence intervals certify their sub-optimality, ensuring the optimal pair is not discarded prematurely.
   • Complexity: The base algorithm has $O(\sqrt{T})$ per-step complexity. A variant, LAZY-OPSR, updates estimates only at powers of two to achieve $O(\log T)$ amortized complexity.

2. Mean-Reverting Prices (Algorithm: LAZY-OPSR):

   • Assumption: $M_t$ follows a broad class of mean-reverting processes, formalized via two conditions:
     • Local: An AR($k$) process (discrete Ornstein-Uhlenbeck).
     • Global: A martingale-type condition where the expected future deviation from the mean, given the history of cumulative deviations, has a non-positive correlation with the current cumulative deviation.
   • Approach: The authors prove a new concentration inequality for the sample mean under these global mean-reverting conditions. They adapt OPSR to LAZY-OPSR, which restricts action eliminations to specific time steps (doubling trick) to prevent the agent's choices from correlating unpredictably with the price sequence.

3. Adversarial Prices (Algorithm 2: ETP):

   • Assumption: $M_t$ is an arbitrary, oblivious sequence (no stochastic assumptions).
   • Approach: The Explore-Then-Perturb (ETP) algorithm.
   • Mechanism:
     • Exploration Phase: For the first $\kappa$ rounds, the agent sets $B_t=0$ and $A_t=1$ to ensure a uniform estimate of the CDF $F$ across the entire domain.
     • Exploitation Phase: The agent switches to a "Follow-the-Perturbed-Leader" (FTPL) strategy. Instead of perturbing the cumulative reward directly, the algorithm adds random noise $\varepsilon$ to the estimated mean price $\hat{\mu}_t$. This stabilizes the optimizer's decisions in the non-convex setting, preventing volatility in the chosen bid-ask pairs.

Key Results
The paper establishes high-probability regret bounds that significantly improve upon standard bandit feedback limits:

• Stochastic & Mean-Reverting Settings: The proposed algorithms achieve a regret bound of $\tilde{O}(\sqrt{T})$ with high probability.
  • This result holds without requiring smoothness (e.g., Lipschitz continuity) assumptions on the distribution of trader valuations $F$.
  • In contrast, standard bandit feedback models in the stochastic setting typically require Lipschitz assumptions to achieve $\tilde{O}(\sqrt{T})$; without them, or in adversarial settings, lower bounds are $\Omega(T^{2/3})$ or $\Omega(T)$.
• Adversarial Setting: The ETP algorithm guarantees an expected regret of $\tilde{O}(T^{2/3})$.
  • This is an improvement over the $\Omega(T)$ lower bound for bandit feedback in adversarial settings (unless Lipschitz conditions are met).
  • The bound holds in expectation, not with high probability, due to the heavy-tailed nature of the perturbation noise.

Significance and Contributions
The paper claims to be the first formalization of this specific action-dependent feedback structure in online learning, where informative feedback is revealed exactly when the reward is zero. The primary contributions are:

1. Novel Feedback Model: It quantifies the value of observing the order book (specifically, resting limit orders when no trade occurs). The results demonstrate that even limited, action-dependent feedback can dramatically improve theoretical regret guarantees compared to standard censored feedback models.
2. Relaxation of Assumptions: The $\tilde{O}(\sqrt{T})$ regret in stochastic and mean-reverting settings is achieved without smoothness assumptions on the valuation distribution, a significant departure from prior continuous bandit literature.
3. New Concentration Inequality: The derivation of a concentration inequality for sample means under a global mean-reverting condition (based on cumulative deviations) is presented as a result of independent interest.
4. Algorithmic Design: The introduction of elimination-based and explore-then-perturb strategies tailored to the hybrid nature of the feedback (full feedback on zero reward, bandit feedback on non-zero reward) provides a new framework for handling partial observability in financial markets.

The authors conclude that while the model is stylized, it isolates the critical role of information structure in market making, suggesting that the ability to observe unexecuted orders is a fundamental requirement for effective, low-regret market making strategies.