Online advertising opportunities are bought and sold in automated auctions driven by real-time bidding. In the case of contextual advertising, the size of a bid is informed by the media context in which the ad will be displayed. In contrast to personalised advertising, contextual advertising is better aligned with privacy acts such as GDPR and CCPA. We investigate how reinforcement learning with human feedback can help optimise contextual advertising under budget constraints. We propose a dynamic epsilon-greedy algorithm that considers the rate of budget consumption during a finite transaction time. The goal is to maximise long-term rewards in a sustainable manner. Our comparative evaluation of fundamental reinforcement learning algorithms on real data suggests that the approach is feasible and efective.
Act [
RTB optimisation is a central topic in advertising literature. To maximise the impact of advertising
within budget constraints, accurately predicting click-through rates (CTR) is crucial. Previous studies
have largely treated CTR prediction as a static problem and resulted in algorithms such as LIN [
CEUR
ceur-ws.org processes of recommending and bidding on ads are all dynamic in nature. For this reason, RTB is more accurately modelled as a dynamic optimisation problem. The algorithms RLB [8] and DRLB [9] aim to address such dynamic bidding problems with budget constraints. While DRLB addresses the limitation of model-based RLB, making it more applicable to real-world scenarios using Deep Q-Network, the ifxed set of bid scaling parameters that spans its action space still restricts its adaptability. Therefore, we reframe RTB as a dynamic optimisation problem and train a bidding agent to spend a limited budget as efectively as possible, to maximise long-term returns in a more sustainable manner.
This paper explores the application of reinforcement learning to contextual advertising with budget constraints. The main contributions are: (1) A dynamic epsilon-greedy reinforcement learning mechanism that adaptively adjusts the rate of advertising spend and maximises long-term rewards. (2) Realistic parameter values, derived from real-world data, including costs and rewards. (3) Ofline evaluations on real-world data, under a holistic simulation workflow that combines RTB, contextual advertising, and reinforcement learning.
In our experiments, we use real-world data to simulate RTB auctions. The dataset consists of pairs of impressions and information about whether the user clicked on the ad, that is, the ground truth that the agent is trying to predict. To train the agent, it is shown the impression part of one data item at a time and has to decide whether or not to bid. It bases its decision on contextual features of the impression, as well as on prior knowledge from previous attempts at bidding. If it chooses to bid and, according to the historical data, the user clicked on the ad, then it receives a positive reward. This bidding process is then repeated until the agent has depleted its budget, or a maximum number of bidding opportunities have been ofered. This means that the agent needs to assess not only the value of the impression currently at hand, but also how to maximise the cumulative return of the entire episode with a limited budget. To this end, it must ration its available budget over time, rather than bidding on every opportunity which would exhaust the budget prematurely, or being too conservative and eventually running out of bidding opportunities. This reflects real-world applications, where campaigns are set to run over periods of days, weeks, or even months, so it is not desirable that the agent spends its entire budget in the first few hours or even minutes.
There are three main components in our simulated bidding process, inspired by RecSim [10]: a document model, a user model, and an agent model. The agent receives a stream of bid requests, each of them generated by sampling the document model to retrieve a candidate advertisement characterised by some contextual feature. For each such document it decides whether or not to bid. If it decides to bid, it is informed if the user clicks on the ad. The agent then computes its gains and losses and updates its bidding strategy. The interaction is illustrated in Figure 1. The training data consists of recorded RTB auctions of individual impressions1, aggregated from multiple US publisher sites in the period June 14 – 28, 2016. Each impression is represented by a reference ID, a topic ID, and a binary user response: 1 means that they clicked, and 0 that they did not.
We model the interaction between the agent and the external environment (that is, the user model and the document model) at each time step as a Markov Decision Process (MDP). We denote by the bidding action taken by the agent at time step , by the state of the environment at that time, and by +1 the immediate reward received at time step + 1 . Each time an agent makes a bidding decision, it triggers a subsequent change in the environment state, and the updated state is evaluated by the agent in preparation for the next time step. In our simulated bidding process, each episode is an ordered sequence of several such interactions. We thus obtain the following sequential trajectory at the end of an episode with time steps: 0, 0, 1, 1, 1, 2, … , −1 , −1 , . The goal of the agent is to maximise the cumulative return = Σ ∈{1,…,} under a constrained budget. The central concepts in the chosen approach are listed below, followed by an explanation of our choice of parameter values. • A state is a tuple = ⟨ tpc, ⟩ , consisting of contextual features that describe the essential information of the external environment, where tpc is a topic ID of the document and is a figure denoting the remaining budget. The total budget for each episode in the experiments is $120, and if the agent chooses to bid, then a bidding price of $1.5 is deduced from the available budget only if it receives a click. • An action ∈ = {0, 1} represents the agent’s bidding decision at time step . • A reward from the transition → +1 . In the experiments, if the agent chooses to bid and receives a click from the user, then the reward is $5. In all other cases, there is no reward. • The episode length is a non-zero integer parameter . In the experiments presented here, we let = 500 . In the extreme scenario where the agent chooses to bid on almost every impression, the episode will end around = 80 when the budget is exhausted. However, we would like to encourage the agent to be more selective with its bids, and learn how to identify impressions that are likely to lead to clicks.
To make our experiments as realistic as possible, we derive key parameters from Amazon’s report on Advertising Cost of Sale (ACoS)2. ACoS is a measure of the ratio of advertising expenditure to revenue and should be around 20% – 30%, calculated by:
ACoS =
TotalAdSpend
TotalSales
CPC = UnitPrice × CVR Here, CVR denotes the conversion rate, that is, the relative proportion of users that click on an ad that also take some desired action when arriving at the landing site. The Cost Per Click (CPC) is generally 70 – 150 cents, and CVR should be in the range of 2% – 8%.
We compare two fundamental classes of RL algorithms: the Monte Carlo (MC) family and the Temporal Diference Learning (TD) family. They are represented by first-visit MC, every-visit MC, Q-Learning, and SARSA [11]. As previously mentioned, the agent evaluates whether to bid based on the state, and the diferent actions result in diferent feedback. Thus, for each state-action pair, we obtain a score to measure its value, denoted as ⟨ , ⟩. Once our agent has taken the action at the state and received a reward, the value ⟨ , ⟩ can be calculated based on the Bellman equation [11] and used for future policy guidance. 1https://www.kaggle.com/competitions/outbrain-click-prediction/data 2https://advertising.amazon.com/library/guides/acos-advertising-cost-of-sales
One of the most important problems in reinforcement learning is to balance exploration and exploitation. Exploitation is when the agent selects the option it expects to yield the highest reward based on the information it has collected thus far. Exploration, on the other hand, is when the agent ignores previous knowledge to investigate unknown (and potentially highly rewarding) options. In the real world, users are not a heterogeneous group, and even individual users change their behaviours over time and in response to external factors. So, if the agent is only guided by prior experiences, it is likely to overlook opportunities for higher rewards and become trapped in sub-optimal choices. In contrast, if the agent varies its interaction with the environment, it gains a more comprehensive understanding of the underlying dynamics.
As previously mentioned, we want the agent to economise with its budget throughout the episode.
So, for the agent to better maximise the benefit in a changing environment, we add a ratio =
BudgetLeft /TimeLeft to dynamically adjust the intensity of exploration, making it reflect the rate at
which the budget is spent. In this way, if there is an ample budget left and the episode is almost finished,
then the agent can boldly explore all opportunities. Conversely, if the budget is consumed too fast, we
can reduce to throttle the rate of exploration, so that the agent makes greedy choices according to the
previously obtained information. However, it is not practical to use this ratio directly as a value of ,
because this ratio obeys a right-skewed distribution, is unevenly distributed, and most of the values
are outside the [
Intuitively, the strategy for dealing with the exploration and exploitation trade-of is as follows: at = { argmax ( , ) random with probability 1 − mt′, with probability mt′.
This section reports on the simulated interactions results3. We run 1 000 episodes for each algorithm to train our agent. There are 500 time steps, i.e. 500 bidding interactions, per episode, and each episode starts with a total budget of $120.
Figure 3 shows the cumulative rewards obtained by the diferent algorithms. We begin by noting that the returns increase as more episodes are trained, which indicates that our agent is constantly 3The experiment code is available at https://github.com/JingWen17/Budget-Constrained_RTB_Optimisation improving its ability to recognise promising impressions. Secondly, the TD methods (Q-Learning and SARSA) perform better than the MC methods. This is likely because the TD approaches update their policies much faster, whereas the MC approaches need to wait until the end of each episode and then calculate the value of each encounter by reviewing the interaction trajectory. The most obvious example is that in a few beginning episodes, the agent is likely to be in a situation where nothing is known about most states, because it has not had enough opportunities to interact with the environment. At this point, the agent makes decisions primarily through random selection. If it happens to receive positive feedback in an interaction, the MC agent can only update its policy once the entire episode is finished. If this feedback points it in the wrong direction, then the MC agent may have to go through many more episodes to make up for the mistake. This is not the case with the TD approach, where the TD agent does not have to wait until the end of an episode before calibrating its knowledge of the environment, but instead adjusts its policy at every time step of the interaction.
Next, we compare our proposed algorithm with baselines in a dynamic environment, where the baseline Q-Learning and Sarsa algorithms consistently choose actions that yield the highest reward based on the estimated ⟨ , ⟩, focusing solely on exploitation. In this experiment, the reward associated with a specific topic varies over time, and reaches its highest values towards the end of an episode, when the agent’s budget might be running low. This reflects real-world fluctuations linked to, for example, time of day, season, and global events. The results are reported in Figure 4.
By incorporating our proposed dynamic epsilon, both Q-Learning and Sarsa achieve higher total (a) (b) returns compared to the baseline algorithms. The dynamic epsilon stimulates exploration while the learner has a suficient budget left to leverage new findings. In contrast, the baseline algorithms always take the currently optimal action. In addition, Q-Learning and Sarsa with ′ prove to be more efective and sustainable than the baselines. Figure 4(b) shows that four algorithms all achieve a good ACoS of around 24% to 26%. However, our proposed algorithms stand out by having a lower ACoS, which is valuable when budgets are limited.
In summary, our findings indicate that compared to MC methods, Q-Learning and SARSA are better able to adapt their strategies through interactive learning. In addition, our proposed dynamic epsilon method outperforms the baselines by more eficiently and sustainably learning in a dynamic environment. In the specific problem we simulated, characterised by a relatively small state space, limited unexpected events, and constrained time and budget, SARSA exhibited greater stability overall.
We model contextual RTB as a dynamic interaction process under budget constraints, define a suitable set of parameters to reflect real-world applications of contextual advertising, propose a dynamic epsilon-greedy algorithm to maximise long-term rewards sustainably, and compare the performance of diferent model-free reinforcement learning methods. Through experiments on real-world data, we can ifnd that Q-Learning and SARSA outperform MC-based approaches to the problem. In addition, our proposed dynamic epsilon approach performs better in a changing environment. Future work includes the exploration of more advanced contextual features, for example, the semantic congruence between webpages and ads. This may involve further studies assessing the state-of-the-art text retrieval techniques and similarity measurement methods. Furthermore, we will also extend our bidding experiment to include several competing bidders. Recommender Systems, RecSys ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 169–177. URL: https://doi.org/10.1145/3298689.3347043. doi:10.1145/3298689.3347043. [8] H. Cai, K. Ren, W. Zhang, K. Malialis, J. Wang, Y. Yu, D. Guo, Real-time bidding by reinforcement learning in display advertising, in: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM ’17, Association for Computing Machinery, New York, NY, USA, 2017, p. 661–670. URL: https://doi.org/10.1145/3018661.3018702. doi:10.1145/3018661.3018702. [9] D. Wu, X. Chen, X. Yang, H. Wang, Q. Tan, X. Zhang, J. Xu, K. Gai, Budget constrained bidding by model-free reinforcement learning in display advertising, CIKM ’18, Association for Computing Machinery, New York, NY, USA, 2018, p. 1443–1451. URL: https://doi.org/10.1145/3269206.3271748. doi:10.1145/3269206.3271748. [10] E. Ie, C.-w. Hsu, M. Mladenov, V. Jain, S. Narvekar, J. Wang, R. Wu, C. Boutilier, Recsim: A configurable simulation platform for recommender systems, 2019. URL: https://arxiv.org/abs/1909. 04847. doi:10.48550/ARXIV.1909.04847. [11] R. S. Sutton, A. G. Barto, Reinforcement learning: An introduction, IEEE Transactions on Neural Networks 16 (2005) 285–286. doi:10.1109/TNN.2004.842673.