온라인 마켓 메이킹과 호가창(Order Book) 관찰의 가치

우리는 학습자가 개인적인 가치 평가(private valuations)를 가진 트레이더들과 상호작용하며 단일 자산에 대해 매수(bid) 및 매도(ask) 가격을 순차적으로 제시하는 온라인 마켓 메이킹 (online market-making) 문제를 연구합니다. 피드백이 완전히 검열되었다고 가정하는 기존의 온라인 학습 (online learning) 공식과 달리, 우리는 실제 지정가 호가창 (limit order books)에서 영감을 얻은 행동 의존적 피드백 (action-dependent feedback) 모델을 도입합니다. 즉, 거래가 발생하면 트레이더의 가치 평가는 숨겨진 상태로 유지되지만, 거래가 발생하지 않으면 수요와 공급에 관한 정보가 담긴 피드백이 공개됩니다. 우리는 이러한 추가 정보가 문제의 학습 가능성 (learnability)을 근본적으로 변화시킨다는 것을 보여줍니다. 독립 항등 분포 (i.i.d.) 시장 가격을 갖는 확률적 설정 (stochastic setting)에서, 우리는 트레이더 가치 분포에 대한 어떠한 매끄러움 (smoothness) 가정 없이도 높은 확률로 $O(\sqrt T)$ 후회 (regret)를 달성하는 제거 기반 알고리즘 (elimination-based algorithm)을 제안합니다. 그런 다음, 국소적 자기회귀 역학 (local, autoregressive dynamics)과 평균으로부터의 누적 편차에 기반한 더 약한 전역적 드리프트 (global drift) 조건을 모두 고려함으로써, 이 결과를 광범위한 평균 회귀 가격 프로세스 (mean-reverting price processes) 클래스로 확장합니다. 두 가정 하에서, 우리는 독립적인 관심사인 새로운 집중 부등식 (concentration inequality)에 의존하여 높은 확률의 $O(\sqrt T)$ 후회 상한을 확립합니다. 마지막으로, 망각적 가격 (oblivious prices)을 갖는 적대적 설정 (adversarial setting)에서, 우리는 기대값 기준으로 $O(T^{2/3})$ 후회를 보장하는 탐색 후 섭동 (explore-then-perturb) 알고리즘을 설계합니다. 우리의 결과는 온라인 마켓 메이킹에서 호가창 (order book)을 관찰하는 것의 가치를 정량화하며, 제한적이고 행동에 의존적인 피드백만으로도 표준 밴딧 피드백 (bandit feedback) 모델에 비해 후회 보장치를 실질적으로 개선할 수 있음을 입증합니다.