Online Market Making and the Value of Observing the Order Book

기술적 요약: 온라인 시장 조성 및 주문 장부 관찰의 가치

문제 정의
본 논문은 단일 자산에 대해 개인적 평가 ($V_t$) 를 가진 거래자들과 상호작용하기 위해 에이전트 (즉, '메이커') 가 순차적으로 매수 호가 ($B_t$) 와 매도 호가 ($A_t$) 를 게시하는 온라인 시장 조성 문제를 다룬다. 해당 자산은 각 라운드 종료 시 객관적인 시장 가치 ($M_t$) 가 실현된다. 에이전트의 목표는 사후에 관찰된 최적의 고정된 매수 - 매도 전략에 비해 후회 (regret) 를 최소화하는 것이다.

핵심적인 어려움은 피드백 구조에 있다. 전통적인 공식화 (예: Cesa-Bianchi et al., 2024) 에서는 피드백이 완전히 검열 (censored) 되어 있어 (밴디트 피드백), 에이전트는 거래가 발생했는지 여부만 관찰할 수 있다. 본 논문은 실제 제한 주문 장부 (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$) 를 관찰한다는 것이다.

이는 즉각적인 보상이 0 일 때 정확히 정보성 피드백이 얻어지는 환경을 조성한다. 에이전트는 수익을 극대화하기 위해 스프레드를 좁히는 것 (이는 정보성 '거래 미발생' 이벤트를 놓칠 위험이 있음) 과 평가 분포에 대한 정보를 수집하기 위해 스프레드를 넓히는 것 사이에서 긴장 관계를 겪게 된다.

방법론 및 알고리즘
저자들은 시장 가격 과정 $M_t$ 에 대한 서로 다른 가정들에 맞춰 세 가지 고유한 알고리즘을 제안한다:

1. 확률적 독립 가격 (알고리즘 1: OPSR):

   • 가정: $M_t$ 는 미지의 평균 $\mu$ 를 가진 i.i.d(독립 동일 분포) 시퀀스이다.
   • 접근법: 낙관적/비관적 연속 거부 (Optimistic/Pessimistic Successive Rejects, 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$ 는 두 가지 조건을 통해 공식화된 광범위한 평균 회귀 과정 클래스를 따른다.
     • 국소적: AR($k$) 과정 (이산 오렌슈타인 - 울렌벡).
     • 전역적: 누적 편차의 역사에 주어진 미래 평균 편차의 기대값이 현재 누적 편차와 음의 상관관계를 가지지 않는 마팅게일 유형의 조건.
   • 접근법: 저자들은 이러한 전역 평균 회귀 조건 하에서 표본 평균에 대한 새로운 집중 부등식을 증명한다. 에이전트의 선택이 가격 시퀀스와 예측 불가능하게 상관관계를 갖는 것을 방지하기 위해 행동 제거를 특정 시간 단계 (이중화 트릭) 로 제한하는 LAZY-OPSR로 OPSR 을 적응시킨다.

3. 적대적 가격 (알고리즘 2: ETP):

   • 가정: $M_t$ 는 임의의 무관심 (oblivious) 시퀀스이다 (확률적 가정 없음).
   • 접근법: 탐색 - 후 교란 (Explore-Then-Perturb, ETP) 알고리즘.
   • 메커니즘:
     • 탐색 단계: 처음 $\kappa$ 라운드 동안 에이전트는 전체 도메인에 걸쳐 CDF $F$ 를 균일하게 추정하기 위해 $B_t=0$ 및 $A_t=1$ 로 설정한다.
     • 활용 단계: 에이전트는 "Perturbed-Leader Follow (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)$ 하한보다 개선된 것이다.
  • 이 상한은 높은 확률이 아닌 기대값으로 성립하며, 이는 교란 노이즈의 두꺼운 꼬리 (heavy-tailed) 특성 때문이다.

의의 및 기여
본 논문은 보상이 0 일 때 정확히 정보성 피드백이 드러나는 특정 행동 의존적 피드백 구조를 온라인 학습에서 공식화한 첫 번째 사례라고 주장한다. 주요 기여점은 다음과 같다:

1. 새로운 피드백 모델: 주문 장부 (특히 거래가 발생하지 않을 때의 미체결 제한 주문) 를 관찰하는 가치를 정량화한다. 결과는 제한된 행동 의존적 피드백조차도 표준 검열 피드백 모델에 비해 이론적 후회 보장을 극적으로 개선할 수 있음을 보여준다.
2. 가정의 완화: 확률적 및 평균 회귀 환경에서의 $\tilde{O}(\sqrt{T})$ 후회는 평가 분포에 대한 매끄러움 가정 없이 달성되었으며, 이는 이전 연속 밴디트 문헌과의 중요한 차별점이다.
3. 새로운 집중 부등식: 누적 편차에 기반한 전역 평균 회귀 조건 하의 표본 평균에 대한 집중 부등식 유도는 독립적인 관심의 결과로 제시된다.
4. 알고리즘 설계: 피드백의 하이브리드 특성 (0 보상에 대한 완전 피드백, 비영점 보상에 대한 밴디트 피드백) 에 맞춰 조정된 제거 기반 및 탐색 - 후 교란 전략의 도입은 금융 시장의 부분 관측성을 처리하는 새로운 프레임워크를 제공한다.

저자들은 모델이 단순화되었지만 시장 조성에서 정보 구조의 결정적 역할을 격리해 보였으며, 미체결 주문을 관찰하는 능력은 효과적이고 후회가 적은 시장 조성 전략의 기본 요구 사항임을 시사한다고 결론지었다.