%0 Journal Article
%T Censored Exploration and the Dark Pool Problem
%A Kuzman Ganchev
%A Michael Kearns
%A Yuriy Nevmyvaka
%A Jennifer Wortman Vaughan
%J Computer Science
%D 2012
%I arXiv
%X We introduce and analyze a natural algorithm for multi-venue exploration from censored data, which is motivated by the Dark Pool Problem of modern quantitative finance. We prove that our algorithm converges in polynomial time to a near-optimal allocation policy; prior results for similar problems in stochastic inventory control guaranteed only asymptotic convergence and examined variants in which each venue could be treated independently. Our analysis bears a strong resemblance to that of efficient exploration/ exploitation schemes in the reinforcement learning literature. We describe an extensive experimental evaluation of our algorithm on the Dark Pool Problem using real trading data.
%U http://arxiv.org/abs/1205.2646v1