We study a specific case of personalized advertisement recommendation (PAR) problem, 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. The policy space in large scale PAR systems 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 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 create deterministic and stochastic policy spaces and conduct extensive experiments on public and proprietary datasets to illustrate the improvement in click-through-rate (CTR) obtained by using the ranker-based policy over classifier-based policy.