In online advertising, maximizing user engagement and advertiser performance hinges on efective ad selection algorithms. Algorithms that tackle Multi-armed bandit problems, such as Thompson Sampling, excel in exploration, but their utilization of contextual information remains limited. Conversely, contextual bandit approaches personalize ad selection by leveraging user and ad-specific features. However, they perform poorly in contexts with limited data and often encounter cold start problems for new ad groups. To address this dilemma, we propose a novel bandit framework that combines context-free and context-aware rewards and is augmented with historical predicted performance, for which we use predicted click-through rate (pCTR) scores. We will refer to this bandit framework as the Augmented Two-Stage Bandit Framework. Our bandit framework is comprised of two stages. In the first stage, the framework applies context-free Thompson Sampling augmented by historical pCTR scores for initial exploration. The non-contextual bandit algorithm and generalized patterns recognized by our pCTR model allow for efective mitigation of the cold start problem. In the second stage, the framework shifts to a contextual bandit algorithm for refined exploration and exploitation. We demonstrate the eficacy of our proposed method using extensive simulation and experiments conducted on a real-world ads marketplace at Reddit. Compared to traditional bandit algorithms, our historical pCTR augmented Two-Stage Bandit framework achieves significant improvements in click-through rate. These findings underscore the ability of an Augmented Two-Stage Bandit Framework to enhance online ad selection and improve key performance metrics.
This paper introduces a novel Augmented Two-Stage Bandit Framework that improves click-through-rate prediction. Our framework aims to optimize ad performance while handling the inherent data sparsity that is introduced by newly formed ads. Our framework brings two major novelties: a two-stage approach and pCTR (predicted click-through rate) augmentation. The former helps performance in datasparse environments while the latter further helps with data-sparsity and improves overall outcomes.
In the initial stage, we leverage a context-free bandit algorithm enhanced by historical pCTR scores to efectively explore candidate ads, even with limited data. The contextfree bandit algorithm we use is Thompson Sampling, but the general framework is adaptable to any context-free bandit algorithm. This mitigates the cold start problem for new ads, allowing them to quickly learn and adapt to user preferences.
As data accumulates, the framework transitions to a contextual bandit algorithm. We use Linear Thompson Sampling to incorporate user and ad-specific features for refined exploration and exploitation. This ensures personalized ad selection that maximizes click-through rates and improves overall campaign performance.
Our proposed two-stage approach efectively addresses data sparsity and imbalance while reaping the benefits of personalized, context-aware selection with prior knowledge about predicted performance. We demonstrate the eficacy of this method through extensive simulations and real-world experiments on a large-scale ads marketplace. Compared to traditional contextual bandit algorithms, the proposed Augmented Two-Stage Bandit Framework achieves significant improvements in click-through rate and other key performance metrics, underscoring its potential to improve online ad selection.
We delve into the challenges of data sparsity and cold starts, showcase the benefits of our pCTR-augmented approach, and present the compelling results of our experiments. By bridging the gap between exploration and exploitation, while enabling personalization and contextawareness, the proposed method solves a significant issue in intelligent ad selection today, ultimately benefiting both users and advertisers in the online advertising landscape.
Extensive research exists on exploration versus exploitation algorithms.
Multi-Armed Bandit Algorithms (MABs): Many
solutions to the online ad selection problem fall squarely within
the domain of bandit algorithms. Traditional algorithms that
address the Multi-Armed Bandit problem, like Thompson
Sampling, ofer eficient exploration-exploitation trade-ofs
for selecting ads in dynamic environments. However, the
lack of context-awareness limits their ability to personalize
recommendations based on user and ad-specific features
[
Contextual Bandit Algorithms: Recognizing the
limitations of MABs, contextual bandit solutions, such as LinUCB
and Linear Thompson Sampling, are able to leverage
additional information, such as user demographics and ad
context, for personalized selection[
Cold Start Solutions: Various approaches have been
explored to address the cold start problem in bandit problem
formulations[
Deep Learning Integration: Recently, the integration
of deep neural networks (DNNs) with bandit algorithms
has shown promising results for improving ad selection
performance [
Our proposed Augmented Two-Stage Bandit Framework combines the strengths of context-free bandits for exploration and historical pCTR scores for cold start mitigation, and we aim to: • Bridge the gap between exploration and exploitation: Our approach efectively explores the ad space in the initial phase with minimal data, while seamlessly transitioning to context-aware decisionmaking as data accumulates [13]. • Address the cold start problem: The two-stage approach with pCTR augmentation mitigates the data sparsity issue for new agents, enabling them to quickly learn and adapt to user preferences. • Improve overall ad performance: By personalizing recommendations based on user and ad features, our framework seeks to achieve significant improvements in click-through rates and other key performance metrics compared to existing approaches. We selected features with a total cardinality of less than 101 across all features, based on ofline feature importance analysis and online experimentation.
The proposed bandit framework also has some drawbacks to consider. It does not solve the problem that bandit algorithms, in general, do not scale well with a large number of features. Another thing to consider is that it’s more dificult to do an unbiased ofline evaluation of bandit performance, compared to prediction models. This might lead to more work to develop a trustworthy ofline evaluation framework or run more online experimentation, which comes with a cost.
We apply an ad selection model as part of our ad auction funnel. Its primary function is to select a subset of candidate ads that will proceed to lower-funnel steps, including inference by a heavy ranking (pCTR) model and final auction ranking. The ad selection stage is necessary due to infrastructure constraints and the amount of computation resources necessary to complete the lower-funnel steps. It is not cost-eficient or technically feasible to apply the pCTR model to all candidate ads. As such, the ad selection model is an important component of our ad auction framework and requires a unique modeling solution.
Ad selection can be formulated as a contextual bandit problem. At time t, an ad impression is requested by a user. The decision-making agent of the bandit will observe the feature vector of the impression, which is considered as context ∈ , and be presented with a set of eligible ads to choose from action space . The chosen ad, , is the action taken by the agent, where ∈ . The agent uses the learned selection policy to choose an ad = () for the ad impression at time to maximize the expected click. The system collects the clicks generated by the agent’s chosen ad, denoted as reward (, ). The given policy’s expected reward is denoted as (, ) = [(, )]. For each observation at time agent improves its selection policy based on the observation tuple < , , (, ) >.
The objective is to find an optimal policy that maximizes the expected total reward [∑︀ =1 (, )]. During ad selection, the agent will select an ad that maximizes the expected reward given the observed context of an impression: := arg max∈ [∑︀ =1 (, )] . The subsequent sections will delve into the methodologies employed to enhance the policy, ultimately aiming for improved click performance.
One notable constraint of contextual bandit algorithms is high variance at the initial stages of learning and, as a result, can over-emphasize exploration. Excessive exploration is costly in an ads marketplace, resulting in sub-optimal ad performance.
To tackle this challenge, we introduce a two-stage bandit framework that optimizes (, ). The framework consists of a context-free reward () at the initial stage, and a context-aware reward (, ), which it switches to as data is accumulated. The motivation behind this approach is that in ad selection, the best performing ad for the overall marketplace is likely a better-than-average candidate under diferent contexts. By initially relying on the context-free policy’s rewards when the context information is sparse, and then transitioning to the context-aware policy’s rewards once it outperforms the context-free bandit policy, our proposed method aims to improve the performance at the early stage while preserving the advantages of personalized recommendations in the long run.
In order to switch between the context-free and contextual reward, the variance is introduced to the framework as a measure of uncertainty and a degree of exploration. We utilize variance of the expected contextual rewards collected from the first observation through time − 1: (, ) = 1≤ ≤ − 1,(,)=(,)( (, )). This yields the variance of the contextual rewards for the given state-action pair up to time − 1.
The (, ) uses context-free reward until (, )) is below a threshold, denoted as . In practice, the threshold was tuned using ofline evaluation and online experimentation, such that it maximized the total reward of the TwoStage framework. We started with a wide range of testable values and narrowed down to values that indicated stability. From that point, we conducted online experiments which tested smaller adjustments in to find an optimally tuned value.
(, ) = {︃ ()
if (, ) > (, ) otherwise
Our ad auction pipeline relies on the pCTR model to predict click-through rates, which has a deep neural network (DNN) model architecture. This architecture allows us to capture complex interactions between user and ad features and adapt to changing user behavior to enhance the accuracy of click-through rate predictions.
In the heavy ranking stage, the pCTR model is used because it can achieve higher accuracy with suficient data and features. It is more eficient at incorporating contexts, such as user-specific and interaction features. However, a complex model like pCTR has its drawbacks, including latency and cost, as it requires more time and computational resources to train, maintain, and use for inference. Inference with the pCTR model in real-time for all ads entering the auction pipeline is computationally infeasible, given the latency constraints.
In the ad selection stage of the early auction pipeline, the pCTR models — as well as other non-bandit algorithms — can sufer from feedback loops and selection bias [ 14]. Bandit algorithms are well-suited for ad selection in this early stage, where exploration is crucial, due to their emphasis on exploration versus exploitation. Additionally, bandit algorithms are advantageous in ad marketplaces where ads can be created or changed at any time, due to their real-time adaptability. These reasons are what lead us to utilizing a bandit algorithm, while incorporating some key strengths of the pCTR model.
To address this limitation, we explored an alternative approach that augments our two-stage framework with the pCTR model. We observed a remarkably high correlation (r-squared = 0.9907) between pCTR and the estimated CTR of the following day, suggesting that the pCTR scores from the previous day can still efectively capture the underlying patterns and trends in user behavior. By incorporating pCTR scores as weights in our ad selection bandit framework, we harness the strengths of both models to improve the accuracy and eficiency of our ad auction pipeline.
We introduce the previous day’s, pre-computed pCTR scores as weights to the policy’s reward with a multiplicative application for the context-free stage. Once the variance of the contextual bandit agent crosses the threshold , the framework switches to the context-aware stage. pCTR augmentation is no longer used at this stage in order to reduce infrastructure cost and improve latency.
The final reward function of our pCTR-augmented twostage bandit framework, denoted − (, ) is defined as: − () = () * () (2) − (, ) = {︃− () if (, ) > (, ) otherwise (3)
Establishing an online Reinforcement Learning environment for linear bandit algorithms is a significant infrastructure investment that is dificult to balance with serving latency constraints at scale. To mitigate these risks, we opted for a mini-batch training approach, with a training intervals of one hour. This training interval was decided based on an ofline simulation.
The ofline simulation compares the performance of agents that are retrained at diferent frequencies. Figure 1 below shows the normalized average reward, i.e. the simulated reward of the given agents divided by the simulated reward of an agent that is retrained at real-time. One hour provided the best performance-to-cost balance, showing marginal drop-of from 15 minutes but a large improvement over daily retraining. (1)
In order to evaluate the impact of our proposed method in a real-world setting, we conduct an online experiment. Our control variant is the Contextual Bandit algorithm without alterations. We have three treatment variants: Two-Stage Bandit, Augmented Contextual Bandit, and Augmented TwoStage Bandit. All of the models are initialized from a coldstart and are updated at an hourly cadence. The details of each model are illustrated in the next section.
We use data collected in real-time from Reddit’s ad impressions. To handle business logic within the auction system, the model is designed to evaluate at the ad group level; the model chooses an ad with the highest expected reward within an ad group for all ad groups passing through this part of the ad funnel. As such, we only include ad groups with more than one ad for the analysis. Then we evaluate the lift in click-through rate (CTR) of proposed methods versus control variant.
The A/B experiment occurred over 7 days to achieve statistical power and significance on the key metrics and to account for weekly seasonality.
The following models are included in the online experiment.
Contextual Bandit: In the control variant, a contextual bandit algorithm, specifically, Linear Thompson Sampling [15], is used to select one ad per ad group for the ad selection requests. The control model has the same contextual awareness features and click-based reward compared to the following treatment variants, but it does not apply two-stage framework or augmentation.
Two-Stage Bandit: This is the bandit framework introduced in Section 4.1 Equation 4.1. It relies on Thompson Sampling during the initial stage and transitions to Linear Thompson Sampling as the variance of the contextual reward is below the threshold .
Augmented Contextual Bandit: This is the Linear Thompson Sampling algorithm, with rewards that are augmented by pCTR.
− (, ) = (, ) * () (4)
Augmented Two-Stage Bandit: This is the proposed bandit framework introduced in Section 4.3 Equation 3. This framework applies the pCTR augmentation to context-free Thompson Sampling and switches to Linear Thompson Sampling when the variance of the contextual reward is below the threshold .
Notably, our proposed method, which integrates the twostage bandit framework and pCTR augmentation, achieves the highest overall performance across all ad groups. Our bandit framework efectively mitigates the cold-start problem, enabling better CTR performance even during early exploration. In contrast, the Augmented Contextual Bandit exhibited slight negative lift, highlighting the significance of integrating the two-stage bandit framework in achieving these gains. Ultimately, the combination of historical pCTR augmentation and the two-stage bandit framework demonstrates a combined efect that surpasses the performance of either approach in isolation.
In addition to the lift in click-through rate, Figure 4 presents a comparative analysis of click volume across the diferent variants, further reinforcing the benefits of the proposed approach. Our proposed strategy has consistently generated the highest click volume throughout the experiment. The increase in click volume, coupled with the lift in CTR underscores the holistic performance improvement achieved by the proposed solution.
In this paper, we define a framework for improving upon linear contextual bandit algorithms for online ad selection, particularly by focusing on performance in cold-start and data-scarce scenarios. The Augmented Two-Stage Bandit Framework is a novel approach to selecting personalized ads while leveraging exploration to address the cold-start problem present in many personalized recommendation models. Our framework showed a significant CTR lift in experiments, with especially large improvements in ad groups with fewer impressions. Our framework ofers practical application to online serving with low-latency requirements significantly improving key performance metrics in our ad marketplace.
Thank you to Bee Massi, Simon Kim, and Josh Cherry for reviewing and advising on the underlying two-stage and augmentation approaches that are utilized in this paper. (Eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 11492–11502. URL: https://proceedings.mlr.press/ v119/zhou20a.html. [10] Q. Shi, F. Xiao, D. Pickard, I. Chen, L. Chen, Deep neural network with linucb: A contextual bandit approach for personalized recommendation, in: Companion Proceedings of the ACM Web Conference 2023, WWW ’23 Companion, Association for Computing Machinery, New York, NY, USA, 2023, p. 778–782. URL: https://doi.org/10.1145/3543873.3587684. doi:10. 1145/3543873.3587684. [11] M. Collier, H. U. Llorens, Deep contextual multi-armed bandits, CoRR abs/1807.09809 (2018). URL: http://arxiv. org/abs/1807.09809. arXiv:1807.09809. [12] M. Unger, A. Tuzhilin, A. Livne, Context-aware recommendations based on deep learning frameworks, ACM Trans. Manage. Inf. Syst. 11 (2020). URL: https: //doi.org/10.1145/3386243. doi:10.1145/3386243. [13] S. Groman, B. Massi, S. Mathias, D. Lee, J. Taylor, Model-free and model-based influences in addictionrelated behaviors, Biological Psychiatry 85 (2019). doi:10.1016/j.biopsych.2018.12.017. [14] J. Chen, H. Dong, X. Wang, F. Feng, M. Wang, X. He, Bias and debias in recommender system: A survey and future directions, CoRR abs/2010.03240 (2020). URL: https://arxiv.org/abs/2010. 03240. arXiv:2010.03240. [15] S. Agrawal, N. Goyal, Thompson sampling for contextual bandits with linear payofs, CoRR abs/1209.3352 (2012). URL: http://arxiv.org/abs/1209. 3352. arXiv:1209.3352.