  We study the problem of personalized advertisement recommendation (PAR),
which consist of a user visiting a system (website) and the system displaying
one of $K$ ads to the user. The system uses an internal ad recommendation
policy to map the user's profile (context) to one of the ads. The user either
clicks or ignores the ad and correspondingly, the system updates its
recommendation policy. PAR problem is usually tackled by scalable
\emph{contextual bandit} algorithms, where the policies are generally based on
classifiers. A practical problem in PAR is extreme click sparsity, due to very
few users actually clicking on ads. We systematically study the drawback of
using contextual bandit algorithms based on classifier-based policies, in face
of extreme click sparsity. We then suggest an alternate policy, based on
rankers, learnt by optimizing the Area Under the Curve (AUC) ranking loss,
which can significantly alleviate the problem of click sparsity. We conduct
extensive experiments on public datasets, as well as three industry proprietary
datasets, to illustrate the improvement in click-through-rate (CTR) obtained by
using the ranker-based policy over classifier-based policies.
