Fast Approximate Bayesian Contextual Cold Start Learning (FAB-COST)
  Cold-start is a notoriously difficult problem which can occur in
recommendation systems, and arises when there is insufficient information to
draw inferences for users or items. To address this challenge, a contextual
bandit algorithm -- the Fast Approximate Bayesian Contextual Cold Start
Learning algorithm (FAB-COST) -- is proposed, which is designed to provide
improved accuracy compared to the traditionally used Laplace approximation in
the logistic contextual bandit, while controlling both algorithmic complexity
and computational cost. To this end, FAB-COST uses a combination of two moment
projection variational methods: Expectation Propagation (EP), which performs
well at the cold start, but becomes slow as the amount of data increases; and
Assumed Density Filtering (ADF), which has slower growth of computational cost
with data size but requires more data to obtain an acceptable level of
accuracy. By switching from EP to ADF when the dataset becomes large, it is
able to exploit their complementary strengths. The empirical justification for
FAB-COST is presented, and systematically compared to other approaches on
simulated data. In a benchmark against the Laplace approximation on real data
consisting of over $670,000$ impressions from autotrader.co.uk, FAB-COST
demonstrates at one point increase of over $16\%$ in user clicks. On the basis
of these results, it is argued that FAB-COST is likely to be an attractive
approach to cold-start recommendation systems in a variety of contexts.
