Online Market Making and the Value of Observing the Order Book

技術的サマリー：オンライン市場形成と注文帳の観測の価値

問題定式化
本論文は、オンライン市場形成の問題を取り扱います。ここで、エージェント（「メーカー」）は、私的評価（$V_t$）を持つトレーダーと相互作用するために、単一資産に対してバッド（$B_t$）とアスク（$A_t$）の価格を逐次的に提示します。資産は各ラウンドの終了時に客観的な市場価値（$M_t$）が実現します。エージェントの目的は、事後において最良の固定されたビッド・アスク戦略に対するリグレットを最小化することです。

核心的な課題は、フィードバック構造にあります。従来の定式化（例：Cesa-Bianchi et al., 2024）では、フィードバックは完全に検閲されます（バンディットフィードバック）：エージェントは取引が発生したかどうかのみを観測します。本論文は、実際のリミット注文帳（LOB）に触発された、新たな行動依存型フィードバックモデルを導入します。フィードバックメカニズムは以下のように定義されます：

• 取引が発生する場合： $V_t \le B_t$（メーカーが購入）または $V_t \ge A_t$（メーカーが売却）の場合、取引が発生します。エージェントは市場価格 $M_t$ を観測しますが、トレーダーの私的評価 $V_t$ は観測しません。
• 取引が発生しない場合： $B_t < V_t < A_t$ の場合、取引は発生しません。重要なのは、エージェントがトレーダーの評価 $V_t$（および $M_t$）を観測する点です。

これにより、瞬間的な報酬がゼロであるときにのみ、有益なフィードバックが得られるレジームが生まれます。エージェントは、利益を最大化するためにスプレッドを狭めること（これにより有益な「取引なし」イベントを見逃すリスクを伴う）と、評価の分布に関する情報を収集するためにスプレッドを広げることの間に緊張関係に直面します。

手法とアルゴリズム
著者らは、市場価格プロセス $M_t$ に関する異なる仮定に合わせて設計された 3 つの異なるアルゴリズムを提案します：

1. 確率的な独立価格（アルゴリズム 1：OPSR）：

   • 仮定： $M_t$ は未知の平均 $\mu$ を持つ i.i.d. 列である。
   • アプローチ： **楽観的/悲観的逐次棄却（OPSR）**アルゴリズム。これは、離散的な候補ビッド・アスク価格の集合を維持します。
   • メカニズム： 棄却戦略を利用します。各ステップで、$V_t$ の累積分布関数（CDF）と $M_t$ の平均に対する楽観的および悲観的な信頼区間を構築します。
   • 推定： $V_t$ は取引が発生しない場合のみ観測されますが、アルゴリズムは「クリップされた」観測値（$V^{clip}_t$）を用いて CDF の代理推定量を構築します。信頼区間がその非最適性を証明するまで、非最適な行動を排除しないことで、最適なペアが早期に棄却されることを防ぎます。
   • 複雑性： 基本アルゴリズムのステップごとの複雑性は $O(\sqrt{T})$ です。バリアントであるLAZY-OPSRは、推定値を 2 のべき乗の時点でのみ更新することで、平均化複雑性を $O(\log T)$ に達成します。

2. 平均回帰価格（アルゴリズム：LAZY-OPSR）：

   • 仮定： $M_t$ は、以下の 2 つの条件を通じて形式化された、広範なクラスの平均回帰プロセスに従います：
     • 局所的： AR($k$) プロセス（離散オースティン＝ウーレンベック過程）。
     • 全球的： 累積偏差の履歴が与えられたとき、平均からの将来の偏差の期待値が、現在の累積偏差と非正の相関を持つという、マルチンゲール型の条件。
   • アプローチ： 著者らは、これらの全球的な平均回帰条件の下での標本平均に対する新しい集中不等式を証明します。彼らは、エージェントの選択が価格列と予測不可能に相関することを防ぐために、行動の排除を特定の時間ステップ（ダブルトリック）に制限する OPSR をLAZY-OPSRに適応させます。

3. 敵対的価格（アルゴリズム 2：ETP）：

   • 仮定： $M_t$ は任意の、無視（oblivious）な列です（確率的仮定なし）。
   • アプローチ： **探索 - 摂動（ETP）**アルゴリズム。
   • メカニズム：
     • 探索フェーズ： 最初の $\kappa$ ラウンドにおいて、エージェントは $B_t=0$、$A_t=1$ と設定し、ドメイン全体にわたって CDF $F$ の均一な推定を確保します。
     • 活用フェーズ： エージェントは「摂動されたリーダー追随（FTPL）」戦略に切り替えます。累積報酬を直接摂動する代わりに、アルゴリズムは推定された平均価格 $\hat{\mu}_t$ にランダムノイズ $\varepsilon$ を加えます。これにより、非凸設定におけるオプティマイザーの決定が安定化され、選択されたビッド・アスクペアのボラティリティが防止されます。

主要な結果
本論文は、標準的なバンディットフィードバックの限界を大幅に上回る高確率のリグレット限界を確立します：

• 確率的および平均回帰設定： 提案されたアルゴリズムは、高確率で $\tilde{O}(\sqrt{T})$ のリグレット限界を達成します。
  • この結果は、トレーダーの評価分布 $F$ に対する滑らかさ（例：リプシッツ連続性）の仮定を必要とせずに成立します。
  • 対照的に、確率的設定における標準的なバンディットフィードバックモデルは、通常 $\tilde{O}(\sqrt{T})$ を達成するためにリプシッツ仮定を必要とします。それらが存在しない場合、または敵対的設定では、下限は $\Omega(T^{2/3})$ または $\Omega(T)$ です。
• 敵対的設定： ETP アルゴリズムは、期待リグレットが $\tilde{O}(T^{2/3})$ であることを保証します。
  • これは、敵対的設定におけるバンディットフィードバックの $\Omega(T)$ の下限（リプシッツ条件が満たされない限り）に対する改善です。
  • この限界は、摂動ノイズの重尾性のため、高確率ではなく期待値において成立します。

意義と貢献
本論文は、報酬がゼロであるときにのみ有益なフィードバックが明らかにされる、この特定の行動依存型フィードバック構造のオンライン学習における最初の形式化であると主張しています。主な貢献は以下の通りです：

1. 新規フィードバックモデル： 注文帳（特に、取引が発生しないときに残っているリミット注文）を観測することの価値を定量化します。結果は、標準的な検閲されたフィードバックモデルと比較して、限定的な行動依存型フィードバックさえも、理論的なリグレット保証を劇的に改善し得ることを示しています。
2. 仮定の緩和： 確率的および平均回帰設定における $\tilde{O}(\sqrt{T})$ のリグレットは、評価分布に対する滑らかさの仮定なしに達成されます。これは、従来の連続バンディット文献からの重要な転換です。
3. 新しい集中不等式： 累積偏差に基づく全球的な平均回帰条件の下での標本平均に対する集中不等式の導出は、独立した興味を持つ結果として提示されます。
4. アルゴリズム設計： 完全フィードバック（ゼロ報酬時）とバンディットフィードバック（非ゼロ報酬時）というハイブリッドな性質のフィードバックに特化した、排除ベースおよび探索 - 摂動戦略の導入は、金融市場における部分的観測性を処理するための新たな枠組みを提供します。

著者らは結論として、このモデルは様式化されたものであるものの、市場形成における情報構造の決定的な役割を浮き彫りにしており、未執行注文を観測する能力が、効果的で低リグレットな市場形成戦略にとって基本的な要件であることを示唆しています。