# Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting

Jun Wang
University College London
<EMAIL_ADDRESS>

Weinan Zhang
Shanghai Jiao Tong University
<EMAIL_ADDRESS>

Shuai Yuan
MediaGamma Ltd
<EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
    1. 1.1 A short history of online advertising
      1. 1.1.1 The birth of sponsored search and contextual advertising
      2. 1.1.2 The arrival of ad exchange and real-time bidding
    2. 1.2 The major technical challenges and issues
      1. 1.2.1 Towards information general retrieval (IGR)
    3. 1.3 The organisation of this monograph
  2. 2 How RTB Works
    1. 2.1 RTB ecosystem
    2. 2.2 User behavioural targeting: the steps
    3. 2.3 User tracking
    4. 2.4 Cookie syncing
  3. 3 RTB Auction & Bid Landscape
    1. 3.1 The second price auction in RTB
      1. 3.1.1 Truthful bidding is the dominant strategy
    2. 3.2 Winning probability
    3. 3.3 Bid landscape forecasting
      1. 3.3.1 Tree-based log-normal model
      2. 3.3.2 Censored linear regression
      3. 3.3.3 Survival Model
  4. 4 User Response Prediction
    1. 4.1 Data sources and problem statement
    2. 4.2 Logistic regression with stochastic gradient descent
    3. 4.3 Logistic regression with follow-the-regularised-leader
    4. 4.4 Bayesian probit regression
    5. 4.5 Factorisation machines
    6. 4.6 Decision trees
    7. 4.7 Ensemble learning
      1. 4.7.1 Bagging (bootstrap aggregating)
      2. 4.7.2 Gradient boosted regression trees
      3. 4.7.3 Hybrid Models
    8. 4.8 User lookalike modelling
    9. 4.9 Transfer learning from Web browsing to ad clicks
    10. 4.10 Deep learning over categorical data
    11. 4.11 Dealing with missing data
    12. 4.12 Model comparison
    13. 4.13 Benchmarking
  5. 5 Bidding Strategies
    1. 5.1 Bidding problem: RTB vs. sponsored search
    2. 5.2 Concept of quantitative bidding in RTB
    3. 5.3 Single-campaign bid optimisation
      1. 5.3.1 Notations and preliminaries
      2. 5.3.2 Truth-telling bidding
      3. 5.3.3 Linear bidding
      4. 5.3.4 Budget constrained clicks and conversions maximisation
      5. 5.3.5 Discussions
    4. 5.4 Multi-campaign statistical arbitrage mining
    5. 5.5 Budget pacing
    6. 5.6 Benchmarking
  6. 6 Dynamic Pricing
    1. 6.1 Reserve price optimisation
      1. 6.1.1 Optimal auction theory
      2. 6.1.2 Game tree based heuristics
      3. 6.1.3 Exploration with a regret minimiser
    2. 6.2 Programmatic direct
    3. 6.3 Ad options and first look contracts
  7. 7 Attribution Models
    1. 7.1 Heuristic models
    2. 7.2 Shapley value
    3. 7.3 Data-driven probabilistic models
      1. 7.3.1 Bagged logistic regression
      2. 7.3.2 A simple probabilistic model
      3. 7.3.3 An extension to the probabilistic model
    4. 7.4 Other models
    5. 7.5 Applications of attribution models
      1. 7.5.1 Lift-based bidding
      2. 7.5.2 Budget allocation
  8. 8 Fraud Detection
    1. 8.1 Ad fraud types
    2. 8.2 Ad fraud sources
      1. 8.2.1 Pay-per-view networks
      2. 8.2.2 Botnets
      3. 8.2.3 Competitors’ attack
      4. 8.2.4 Other sources
    3. 8.3 Ad fraud detection with co-visit networks
      1. 8.3.1 Feature engineering
    4. 8.4 Viewability methods
    5. 8.5 Other methods
  9. 9 The Future of RTB
  10. A RTB Glossary

## Abstract

The most significant progress in recent years in online display advertising is
what is known as the Real-Time Bidding (RTB) mechanism to buy and sell ads.
RTB essentially facilitates buying an individual ad impression in real time
while it is still being generated from a user’s visit. RTB not only scales up
the buying process by aggregating a large amount of available inventories
across publishers but, most importantly, enables direct targeting of
individual users. As such, RTB has fundamentally changed the landscape of
digital marketing. Scientifically, the demand for automation, integration and
optimisation in RTB also brings new research opportunities in information
retrieval, data mining, machine learning and other related fields. In this
monograph, an overview is given of the fundamental infrastructure, algorithms,
and technical solutions of this new frontier of computational advertising. The
covered topics include user response prediction, bid landscape forecasting,
bidding algorithms, revenue optimisation, statistical arbitrage, dynamic
pricing, and ad fraud detection.

##  Chapter 1 Introduction

An advertisement is a marketing message intended to encourage potential
customers to purchase a product or to subscribe to a service. Advertising is
also a way to establish a brand image through the repeated presence of an
advertisement (ad) associated with the brand in the media. Television, radio,
newspaper, magazines, and billboards are among the major channels that
traditionally place ads, however, the advancement of the Internet enables
users to seek information online. Using the Internet, users are able to
express their information requests, navigate specific websites and perform
e-commerce transactions. Major search engines have continued to improve their
retrieval services and users’ browsing experience by providing relevant
results. Since many more businesses and services are transitioning into the
online space, the Internet is a natural choice for advertisers to widen their
strategy, reaching potential customers among Web users [Yuan et al., 2012].

As a result, online advertising is now one of the fastest advancing areas in
the IT industry. In display and mobile advertising, the most significant
technical development in recent years is the growth of Real-Time Bidding
(RTB), which facilitates a real-time auction for a display opportunity. Real-
time means the auction is per impression and the process usually occurs less
than 100 milliseconds before the ad is placed. RTB has fundamentally changed
the landscape of the digital media market by scaling the buying process across
a large number of available inventories among publishers in an automatic
fashion. It also encourages _user behaviour targeting_ , a significant shift
towards buying focused on user data rather than contextual data [Yuan et al.,
2013].

Scientifically, the further demand for automation, integration and
optimisation in RTB opens new research opportunities in the fields such as
Information Retrieval (IR), Data Mining (DM), Machine Learning (ML), and
Economics. IR researchers, for example, are facing the challenge of defining
the relevancy of underlying audiences given a campaign goal, and consequently,
developing techniques to find and filter them out in the real-time bid request
data stream [Zhang et al., 2016a, Perlich et al., 2012]. For data miners, a
fundamental task is identifying repeated patterns over the large-scale
streaming data of bid requests, winning bids and ad impressions [Cui et al.,
2011]. For machine learners, an emerging problem is telling a machine to react
to a data stream, i.e., learning to bid cleverly on behalf of advertisers and
brands to maximise conversions while keeping costs to a minimum [Xu et al.,
2016, Kan et al., 2016, Cai et al., 2017].

It is also of great interest to study learning over multi-agent systems and
consider the incentives and interactions of each individual learner (bidding
agent). For economics researchers, RTB provides a new playground for micro
impression-level auctions with various bidding strategies and macro multiple
marketplace competitions with different pricing schemes, auction types and
floor price settings, etc.

More interestingly, per impression optimisation allows advertisers and
agencies to maximise effectiveness based on their own, or the 3rd party, user
data across multiple sources. Advertisers buy impressions from multiple
publishers to maximise certain Key Performance Indicators (KPIs) such as
clicks or conversions, while publishers sell their impressions through
multiple advertisers to optimise their revenue [Yuan and Wang, 2012]. This
brings the online advertising market a step closer to the financial markets,
where marketplace unity is strongly promoted. A common objective, such as
optimising clicks or conversions across webpages, advertisers, and users,
calls for significant multi-disciplinary research that combines statistical
Machine Learning, Data Mining, Information Retrieval, and behavioural
targeting with game theory, economics and optimisation.

Despite its rapid growth and huge potential, many aspects of RTB remain
unknown to the research community for a variety of reasons. In this monograph,
we aim to offer insightful knowledge of real-world systems, to bridge the gaps
between industry and academia, and to provide an overview of the fundamental
infrastructure, algorithms, and technical and research challenges of the new
frontier of computational advertising.

###  1.1 A short history of online advertising

The first online ad appeared in 1994 when there were only around 30 million
people on the Web. The Web version of the Oct. 27, 1994 issue of _HotWired_
was the first to run a true banner ad for AT&T.

####  1.1.1 The birth of sponsored search and contextual advertising

Online advertising has been around for over a decade. The sponsored search
paradigm was created in 1998 by Bill Gross of Idealab with the founding of
Goto.com, which became Overture in October 2001, was acquired by Yahoo! in
2003 and is now Yahoo! Search Marketing [Jansen, 2007]. Meanwhile, Google
started its own service AdWords using Generalized Second Price Auction (GSP)
in February 2002, adding quality-based bidding in May 2002 [Karp, 2008]. In
2007, Yahoo! Search Marketing followed, added quality-based bidding as well
[Dreller, 2010]. It is worth mentioning that Google paid 2.7 million shares to
Yahoo! to solve the patent dispute, as reported by [The Washington Post,
2004], for the technology that matches ads with search results in sponsored
search. Web search has now become an integral part of daily life, vastly
reducing the difficulty and time once associated with satisfying an
information necessity. Sponsored search allows advertisers to buy certain
keywords to promote their business when users use such a search engine and
greatly contributes to its continuing a free service.

On the other hand, in 1998, _display_ advertising began as a concept
contextual advertising [Anagnostopoulos et al., 2007, Broder et al., 2007].
Oingo, started by Gilad Elbaz and Adam Weissman, developed a proprietary
search algorithm based on word meanings and built upon an underlying lexicon
called WordNet. Google acquired Oingo in April 2003 and renamed the system
AdSense [Karp, 2008]. Later, Yahoo! Publish Network, Microsoft adCenter and
Advertising.com Sponsored Listings amongst others were created to offer
similar services [Kenny and Marshall, 2001]. The contextual advertising
platforms evolved to adapt to a richer media environment, including video,
audio and mobile networks with geographical information. These platforms
allowed publishers to sell blocks of space on their webpages, video clips and
applications to make money. Usually such services are called an advertising
network or a display network and are not necessarily run by search engines, as
they can consist of huge numbers of individual publishers and advertisers.
Sponsored search ads can also be considered a form of contextual ad that
matches with simple context: query keywords; but it has been emphasised due to
its early development, large market volume and research attention.

####  1.1.2 The arrival of ad exchange and real-time bidding

Around 2005, new platforms focusing on real-time bidding (RTB) based buying
and selling impressions were created. Examples include ADSDAQ, AdECN,
DoubleClick Advertising Exchange, adBrite, and Right Media Exchange, which are
now known as ad exchanges. Unlike traditional ad networks, these ad exchanges
aggregate multiple ad networks together to balance the demand and supply in
marketplaces and use auctions to sell an ad impression in real time when it is
generated by a user visit [Yuan et al., 2013]. Individual publishers and
advertising networks can both benefit from participating in such businesses.
Publishers sell impressions to advertisers who are interested in associated
user profiles and context while advertisers, on the other hand, can contact
more publishers for better matching and buy impressions in real-time together
with their user data. At the same time, other similar platforms with different
functions emerged [Graham, 2010] including (i) demand side platform (DSP),
which serves advertisers managing their campaigns and submits real-time
bidding responses for each bid request to the ad exchange via algorithms, and
(ii) supply side platform (SSP), created to serve publishers managing website
ad inventory. However, real-time bidding (RTB) and multiple ad networks
aggregation do not change the nature of such marketplaces (where buying and
selling impressions happen), but only make the transactions in real-time via
an auction mechanism. For simplicity, we may use the term “ad exchange” in
this monograph to better represent the wider platforms where trading happens.

###  1.2 The major technical challenges and issues

Real-time advertising generates large amounts of data over time. Globally, DSP
Fikisu claims to process 32 billion ad impressions daily [Zhang et al., 2017]
and DSP Turn reports to handle 2.5 million per second at peak time [Shen et
al., 2015]. The New York Stock Exchange, to better envision the scale, trades
around 12 billion shares daily.111According to Daily NYSE group volume,
http://goo.gl/2EflkC, accessed: 2016-02. It is fair to say the volume of
transactions from display advertising has already surpassed that of the
financial market. Perhaps even more importantly, the display advertising
industry provides computer scientists and economists a unique opportunity to
study and understand the Internet traffic, user behaviour and incentives, and
online transactions. Only this industry aggregates nearly all the Web traffic,
in the form of ads transactions, across websites and users globally.

With real-time per-impression buying established together with the cookie-
based user tracking and syncing (the technical details will be explained in
Chapter 2), the RTB ecosystem provides the opportunity and infrastructure to
fully unleash the power of user behavioural targeting and personalisation
[Zhang et al., 2016a, Wang et al., 2006, Zhao et al., 2013] for that
objective. It allows machine driven algorithms to automate and optimise the
relevance match between ads and users [Raeder et al., 2012, Zhang et al.,
2014a, Zhang and Wang, 2015, Kan et al., 2016].

RTB advertising has become a significant battlefield for Data Science
research, acting as a test bed and application for many research topics,
including user response (e.g. click-through rate, CTR) estimation [Chapelle et
al., 2014, Chapelle, 2015, He et al., 2014, Kan et al., 2016], behavioural
targeting [Ahmed et al., 2011, Perlich et al., 2012, Zhang et al., 2016a],
knowledge extraction [Ahmed et al., 2011, Yan et al., 2009], relevance
feedback [Chapelle, 2014], fraud detection [Stone-Gross et al., 2011, Alrwais
et al., 2012, Crussell et al., 2014, Stitelman et al., 2013], incentives and
economics [Balseiro et al., 2015, Balseiro and Candogan, 2015], and
recommender systems and personalisation [Juan et al., 2016, Zhang et al.,
2016a].

####  1.2.1 Towards information general retrieval (IGR)

A fundamental technical goal in online advertising is to automatically deliver
the right ads to the right users at the right time with the right price agreed
by the advertisers and publishers. As such, RTB based online advertising is
strongly correlated with the field of Information Retrieval (IR), which
traditionally focuses on building relevance correspondence between information
needs and documents [Baeza-Yates et al., 1999]. The IR research typically
deals with textual data but has been extended to multimedia data including
images, video and audio signals [Smeulders et al., 2000]. It also covers
categorical and rating data, including Collaborative Filtering and Recommender
Systems [Wang et al., 2008]. In all these cases, the key research question of
IR is to study and model the relevance between the queries and documents in
the following two distinctive tasks: retrieval and filtering. The retrieval
tasks are those in which information needs (queries) are _ad hoc_ , while the
document collection stays relatively static. By contrast, information
filtering tasks are defined when information needs stay static, whereas
documents keep entering the system. A rich literature can be found from the
probability ranking principle [Robertson, 1977], the RSJ and BM25 model [Jones
et al., 2000], language models of IR [Ponte and Croft, 1998], to the latest
development of learning to rank [Joachims, 2002, Liu, 2009], results diversity
[Wang and Zhu, 2009, Agrawal et al., 2009, Zhu et al., 2009a] and novelty
[Clarke et al., 2008], and deep learning of information retrieval [Li and Lu,
2016, Deng et al., 2013].

We, however, argue that IR can broaden its research scope by going beyond the
applications of Web search and enterprise search, turning towards _general
retrieval_ problems derived from many other applications. Essentially, as long
as there is concern with building a correspondence between two information
objects, under various objectives and criteria [Gorla et al., 2013], we would
consider it a general retrieval problem. Online advertising is one of the
application domains, and we hope this monograph will shed some light on new
information general retrieval (IGR) problems. For instance, the techniques
presented on real time advertising are built upon the rich literature of IR,
data mining, machine learning and other relevant fields, to answer various
questions related to the relevance matching between ads and users. But the
difference and difficulty, compared to a typical IR problem, lies in its
consideration of various economic constraints. Some of the constraints are
related to incentives inherited from the auction mechanism, while others
relate to disparate objectives from the participants (advertisers and
publishers). In addition, RTB also provides a useful case for relevance
matching that is bi-directional and unified between two matched information
objects [Robertson et al., 1982, Gorla, 2016, Gorla et al., 2013]. In RTB,
there is an inner connection between ads, users and publishers [Yuan et al.,
2012]: advertisers would want the matching between the underlying users and
their ads to eventually lead to conversions, whereas publishers hope the
matching between the ads and their webpage would result in a high ad payoff.
Both objectives, among others, require fulfilment when the relevancy is
calculated.

###  1.3 The organisation of this monograph

The targeted audience of this monograph is academic researchers and industry
practitioners in the field. The intention is to help the audience acquire
domain knowledge and to promote research activities in RTB and computational
advertising in general.

The content of the monograph is organised in four folds. Firstly, chapters 2
and 3 provide a general overview of the RTB advertising and its mechanism.
Specifically, in Chapter 2, we explain how RTB works, as well as the
mainstream user tracking and synchronising techniques that have been popular
in the industry; In Chapter 3 we introduce the RTB auction mechanism and the
resulting forecasting techniques in the auction market. Next, we cover the
problems from the view of advertisers: in Chapter 4, we explain various user
response models proposed in the past to target users and make ads more fit to
the underlying user’s patterns, while in Chapter 5, we present bid
optimisation from advertisers’ viewpoints with various market settings. After
that, in Chapter 6, we focus on the publisher’s side and explain dynamic
pricing of reserve price, programmatic direct, and new type of advertising
contracts. The monograph then concludes with attribution models in Chapter 7
and ad fraud detection in Chapter 8, two additional important subjects in RTB.

There are several read paths depending on reader’s technical backgrounds and
interests. For academic researchers, chapters 2 and 3 shall help them
understand the real-time online advertising systems currently deployed in the
industry. The later chapters shall help industry practitioners grasp the
research challenges, the state of the art algorithms and potential future
systems in this field. As these later chapters are on specialised topics, they
can be read in independently at a deeper level.

##  Chapter 2 How RTB Works

In this chapter, we explore how real-time bidding functions. We start with an
introduction of the key players in the ecosystem and then illustrate the
mechanism for targeting individual users. We then introduce common user
tracking and cookie synchronising methods that play an important role in
aggregating user behaviour information across the entire Web. This chapter
focuses more on engineering rather than scientific aspects, but nonetheless it
serves to provide domain knowledge and context of the RTB system necessary for
the mathematical models and algorithms introduced in later chapters. For
readability, the complete terminology is enumerated in Appendix A.

###  2.1 RTB ecosystem

Apart from four major types of players: advertisers, publishers, ad
networks/ad exchanges and users, RTB has created new tools and platforms which
are unique and valuable. Figure 2.1 illustrates the ecosystem:

  * •

Supply side platforms (SSP) serve publishers by registering their inventories
(impressions) from multiple ad networks and accepting bids and placing ads
automatically;

  * •

Ad exchanges (ADX) combine multiple ad networks together [Muthukrishnan,
2009]. When publishers request ads with a given context to serve users, the
ADX contacts candidate Ad Networks (ADN) in real-time for a wider selection of
relevant ads;

  * •

Demand side platforms (DSP) serve advertisers or ad agencies by bidding for
their campaigns in multiple ad networks automatically;

  * •

Data exchanges (DX), also called Data Management Platforms (DMP), serve DSP,
SSP and ADX by providing user historical data (usually in real-time) for
better matching.

The emergence of DSP, SSP, ADX and DX resulted from the presence of thousands
of ad networks available on the Internet, a barrier for advertisers as well as
publishers entering the online advertising business. Advertisers had to create
and edit campaigns frequently for better coverage as well as analyse data
across many platforms for better impact. Publishers had to register with and
compare several ad networks carefully to achieve optimal revenue. The ADX
arose as an aggregated marketplace of multiple ad networks for the purpose of
alleviating such problems. Advertisers could then create their campaigns and
set desired targeting a single time and analyse the performance data stream in
a single place, while publishers could register with ADX and collect optimal
profit without any manual interference.

Figure 2.1: The various players of online display advertising and the
ecosystem: 1. The advertiser creates campaigns in the market. 2. The market
trades campaigns and impressions to balance the demand and supply for better
efficiency. 3. The publisher registers impressions with the market. 4. The
user issues queries or visits webpages. 5. The markets can query data
exchanges, a.k.a. data management platform (DMP), user profiles in real-time.
Source: [Yuan et al., 2012].

The ADX is normally connected with two platforms — DSP and SSP — for their
different emphases on customers. The DSP works as the agency of advertisers by
bidding and tracking in selected ad networks, while the SSP works as the
agency of publishers by selling impressions and selecting optimal bids.
However, the goal of these platforms is the same: they attempt to create a
uniform marketplace for customers. On one hand, this reduces human labour, and
on the other hand, balances demand and supply in various small markets for
better economic efficiency.

Due to the opportunities for profit in such business, the line between these
platforms is becoming less tangible. In this monograph, we choose to use the
term “ad exchange” to boardly describe the marketplace where impression
trading happens.

The DX collects user data and sells it anonymously to DSP, SSP, ADX and
sometimes to advertisers directly in real-time bidding (RTB) for better
matching between ads and users. This technology is usually referred to as
behavioural targeting. Intuitively, if a user’s past data shows interest in an
advertiser’ products or services, then the advertiser would have a higher
chance of securing a transaction by displaying its ads, which results in
higher bidding for the impression. Initially the DX was a component of other
platforms, but more individual DXs are now operating alongside analysing and
tracking services.

Figure 2.2: How RTB works for behavioural targeting. Source: [Zhang et al.,
2014b].

###  2.2 User behavioural targeting: the steps

With the new RTB ecosystem, advertisers can target the underlying users based
on their previously observed behavior. Here we explain how RTB works with
behavioural targeting — from a user visiting a website, a bid request sent, to
the display of the winning ad usually within 100ms, as illustrated in Figure
2.2:

  1. 0.

When a user visits a webpage, an impression is created on publisher’s website.
While the page loads,

  2. 1.

An ad request is sent to an ad exchange through an ad network or a SSP;

  3. 2.

The ad exchange queries DSPs for advertisers’ bids;

  4. 3.

The DSP can contact data exchanges for the 3rd party user data;

  5. 4.

If the advertiser decides to bid, the bid is generated and submitted (for
example, the user is interested in travel, a travel related advertiser, e.g.
booking.com, could expect the user to convert to their campaign and may be
willing to bid higher);

  6. 5.

The winner is selected at ad exchanges (largely based on the second price
auction), then selected at SSP if the SSP sends the bid request to multiple ad
exchanges;

  7. 6.

The winning notice is sent to the advertiser;

  8. 7.

Following the reversed path, the winner’s ad (creative, i.e., the text,
picture, or video that the advertiser wants to show to users) is displayed on
the webpage for the specific user;

  9. 8.

The tracker collects the user’s feedback, determining whether the user clicked
the ad and whether the ad led to any conversion.

The above process marks a fundamental departure from contextual advertising
[Anagnostopoulos et al., 2007, Broder et al., 2007] as it puts more focus on
the underlying audience data rather than the contextual data from the webpage
itself. In the simplest form of behavioural targeting, advertisers (typically
e-commerce merchandisers) would _re-target_ users who have previously visited
their websites but have not initially converted. As illustrated in Figure 2.3,
suppose that you run a Web store www.ABC.com, and user abc123 comes and saves
a pair of $150 shoes to their shopping cart but never checks out. You can
trace and serve them an ad when they visit other websites later, directing
them back to your store to close the sale.

One of the reasons to employ the impression level per audience buying is to
make _retargeting_ such users possible. However, the problem of identifying
users across the Internet remains, e.g, recognising in other domains
(websites) from the RTB exchange the exact user abc123 the advertiser recorded
in their own domain.

Figure 2.3: Personalised, retargeting ads: keep ads in front of the users even
after they leave the advertiser’s website.

###  2.3 User tracking

A user is typically identified by an HTTP cookie, designed to allow websites
to remember the status of an individual user, including remembering shopping
items added in the cart in an online store or recording the user’s previous
browsing activities for generating personalised and dynamical content. A
cookie, in the form of a small piece of data, is sent from a website and
stored in the user’s Web browser the first time the user browses a website.
Every time the user loads that website again, the browser sends the cookie
back to the server to identify the user. Note that a cookie is tied to a
specific domain name. If a browser makes an HTTP request to www.ABC.com,
www.ABC.com can place a cookie in the user’s browser, specifying their own
user ID, say, abc123. In a later session, when the browser makes another HTTP
request to www.ABC.com, www.ABC.com can read the cookie and determine the ID
of the user is abc123. Another domain, DEF.com for example, cannot read a
cookie set by ABC.com. This behaviour is the result of cross-origin policy set
in [Barth, 2011] to protect user privacy.

In the context of display advertising, each service provider (including ad
exchanges, DSP bidders or DMP user trackers) would act as a single domain to
build up their own user ID systems across a number of their client websites
(either for advertisers or publishers). The service provider would insert
their code snippet111Usually called tracking code for DSP bidders, and ad
serving code or ad tags for SSPs or ad exchanges. under their own domain name
to the HTML code of a managed webpage. In fact, there are quite a few third
parties who drop cookies to track users. For instance, in a single webpage
from _New York Times_ , there are as many as sixteen user trackers, as
reported in Figure 2.4.

As all these tracking systems only have a local view of their users, and there
are enormous numbers of Web users and webpages, the observed user behaviours
within individual domains would not adequately create effective targeting. For
example, suppose when a browser requests an ad from an ad exchange, it only
passes along the cookie data that’s stored inside that domain name, say
ad.exchange.com.222ad.exchange.com is just a toy example of a domain name
here. This means that the exchange has no knowledge about whatever data the
bidder, as well as other third party cookie systems, might have collected
under ad.bidder.com, and vice versa. Therefore, when the exchange sends a bid
request to a bidder with the ad exchange’s own user ID, the bidder has no
knowledge about that ID and thus cannot accurately decide what ad to serve.
Their ID systems need to be linked together in order to identify users across
the entire Internet. This is done by a technique called _Cookie Syncing_ ,
which shall be covered next.

Figure 2.4: The _New York Times_ frontpage referred to as many as 16 third
parties that delivered ads and installed cookies, as reported by Ghostery.

###  2.4 Cookie syncing

Cookie syncing, a.k.a. cookie matching or mapping, is a technical process
enabling user tracking platforms to link separate IDs given to the same user.
[Acar et al., 2014] shows that nearly 40% of all tracking IDs are synced
between at least two entities in the Internet. A study of Web search queries
in [Gomer et al., 2013] showed a 99.5% chance that a user will be tracked by
all top 10 trackers within 30 clicks on search results. A network analysis
from the study further indicated that a network constructed by third party
tracking exhibits the property of small world, implying it is efficient in
spreading the user information and delivering targeted ads.

Cookie syncing is commonly achieved by employing _HTTP 302 Redirect_
protocol333An HTTP response with this 302 status code is a common way of
performing URL redirection. The Web server also provides a URL in the location
header field. This code invites the user agent (e.g. a web browser) to make a
second, otherwise identical, request to the new URL specified in the location
field. to make a webpage available under more than one URL address. The
process begins when a user visits a marketer’s website, such as ABC.com, which
includes a _tag_ from a third-party tracker such as ad.bidder.com. The tag is
commonly implemented through an embedded 1x1 image (known as pixel tags, 1x1
pixels, or web bugs). Pixel tags are typically single pixel, transparent GIF
images that are added to a webpage by, for instance,

<img src="http://ad.bidder.com/pixel?parameters=xxx"/>.

Even though the pixel tag is virtually invisible, it is served just like any
other image online. The difference is the webpage is served from the site’s
domain while the image is served from the tracker’s domain. This allows the
user tracker to read and record the cookie’s unique ID and the extended
information it needs. The trick of cookie sync using a pixel is that, instead
of returning the required 1x1 pixel immediately, one service redirects the
browser to another service to retrieve the pixel. During the redirect process,
the two services exchange the information and sync the user’s ID.

Figure 2.5: Cookie syncing in a marketer’s website managed by ad.bidder.com.

As illustrated in Figure 2.5, in step (1), the browser makes a request from
the pixel tag to ad.bidder.com and includes in this request any tracking
cookies set by ad.bidder.com. If the user is new to ad.bidder.com, it sets its
ad.bidder.com cookie. In step (2), the tracker from ad.bidder.com retrieves
its tracking ID from the cookie and, instead of returning the required 1x1
pixel, redirects the browser to ad.exchange.com using http 302 redirect and
encoding the tracking ID into the URL as a parameter. (3) The browser then
makes a request to ad.exchange.com, which includes the full URL ad.bidder.com
redirected to as well as ad.exchange.com’s own tracking cookie (if one
exists). (4) ad.exchange.com returns the required 1x1 pixel and can now link
its own ID associated with the user to ad.bidder.com’s ID and create a record
in its match table.

The above cookie sync takes place when ad.bidder.com is managing its Web
properties, but the cookie sync process can also be completed alongside served
ads when the bidder wins an impression in RTB. If the sync is bidirectional,
the ad.exchange.com makes the redirect back to the ad.bidder.com, passing its
own ID in the URL parameter. The ad.bidder.com receives this request, reads
its own cookie, and stores the ad exchange user ID along with its own ID in
the cookie-matching table.

Using cookies to track users does have drawbacks. Only applicable to browsers,
cookies can also be easily deleted by clearing the browser’s cache. Users can
even choose to disable cookies completely (i.e., private or incognito mode).
This makes alternative tracking techniques preferable. For example, device or
browser fingerprinting uses information collected about the remote computing
device for the purpose of identifying the user. Fingerprints can be used to
fully or partially identify individual users or devices even when cookies are
turned off. One example, canvas fingerprinting, uses the browser’s Canvas API
to draw invisible images and extract a persistent, long-term fingerprint
without the user’s knowledge. [Acar et al., 2014] found that over 5% of the
top 100,000 websites have already employed canvas fingerprinting. Trackers can
also abuse Flash cookies for regenerating previously removed HTTP cookies, a
technique referred to as respawning or Flash cookies [Boda et al., 2011]. A
study by [Eckersley, 2010] showed 94.2% of browsers with Flash or Java were
unique, while [Soltani et al., 2010] found 54 of the 100 most popular sites
stored Flash cookies.

##  Chapter 3 RTB Auction Mechanism and Bid Landscape Forecasting

In online advertising, sellers (typically publishers) may gain access to
partial information about the market demand of their ad impressions from
historic transactions. However, they do not usually have knowledge about how
much an individual ad impression is worth on the market. Different advertisers
may have different (private) valuations of a given ad impression. The
valuation is typically based on the prediction of the underlying user’s
likelihood to convert should their ad be placed in the impression.

In such a situation, _auction_ is generally regarded as a fair and transparent
way for advertisers and publishers to agree with a price quickly, whilst
enabling the best possible sales outcome. Specifically, an auction is the
process of selling an item by offering it up for bids, taking bids, and then
selling it to the highest bidder. As demonstrated in sponsored search by
[Edelman et al., 2005], auctions have become an effective tool to sell search
impressions by posting a bid for underlying query keywords — for a general
introduction and discussion about keyword auction and ad exchange, we refer to
[McAfee, 2011]. Subsequently, display advertising has followed suit and
employed auctions in real-time to sell an ad impression each time when it is
being generated from a user’s visit [Yuan et al., 2013]. In this chapter, we
briefly introduce the auction mechanisms in RTB display advertising,
explaining how the second price auction has been utilised. It is worth
mentioning that the second price auction is a sealed-bid auction and
advertisers are notified of the winning price only if they have actually won
the auction. Thus, each advertiser only presents a local view of the market
data. At the end of this chapter, we address the unique data censorship
problem and explain how to estimate the winning probability in an unbiased way
in the RTB auction market.

###  3.1 The second price auction in RTB

As introduced in Chapter 2 (also see Figure 2.2), in RTB, advertisers would be
able to bid an individual impression immediately when it is still being
generated from a user visit. RTB exchanges typically employ the second price
auction. In this type of auction, instead of paying for the bid offered, the
bidder pays the price calculated from the second highest bid.

The reason behind paying the second highest bid is that impressions with same
or similar user profiles will continuously appear in ad exchanges. If
advertisers pay what they bid (i.e., the first price auction), they would not
state their true valuations, but rather keep adjusting their bids in response
to other bidders’ behaviours. Unstable bidding behaviours have been well
observed in continuously repeated first price auctions, such as in the search
markets [Edelman and Ostrovsky, 2007]. To understand this in RTB, suppose
there are two advertisers and the impressions associated with the same
targeted user group are worth $6 CPMs (cost per mille impressions, with
_mille_ being Latin for thousand) to the first advertiser and $8 CPMs to the
second. The floor price (the lowest acceptable bid) is assumed to be $2 CPMs.
Thus, when they bid between $2 CPMs and $6 CPMs, each of them tries to outbid
each other with a small amount. As a result, the winning price increases
continuously until reach $6 CPMs where the second advertiser stops the
bidding. Then, without the competition from the second advertiser, the first
advertiser would drop back to the minimum bid $2 CPMs. At that point, the
second advertiser comes back and the competition restarts again and the
_cycling_ behaviour will continue indefinitely.

Thus, our focus in this chapter will be on the second price auction. Figure
3.1 illustrates a simple second price auction for an ad impression offered to
four advertisers. When receiving the bid requests (consisting of features to
describe the impression), advertisers will have their own assessment about the
value of the impression. For direct targeting campaigns, it is estimated based
on the likelihood the user is going to convert and also the value of that
conversion. For branding campaigns, it is mostly bounded by the average budget
per targeted impression. Note that the valuation is private, as it relies on
the direct sales or advertising budget, which is only known by advertisers
themselves. Suppose Advertisers A, B, C, and D, based on their valuations,
place bids as $10, $8, $12, $6 CPMs respectively. Advertiser C would win the
auction with the actual payment price $10 CPM.111The actual cost for this
impression is $\$10\text{CPM}/1000=\$0.01$. It is worth noticing that unlike
sponsored search where CPC (cost per click) is typically used for the payment,
RTB mainly employs CPM. Thus, it is the advertisers’ responsibility to
optimise the effectiveness of the campaigns such as clicks or conversions on
top of the CPM costs. This makes sense in RTB as advertisers typically have
more information about their campaigns and the user intents (e.g., via their
own data collection or a third party DMP etc) and as such know better about
the potential conversions and clicks.

Figure 3.1: A simple illustration of the second price auction in RTB exchange.

In practice, RTB auctions are done in a hierarchical manner because the
auction process may start from SSPs (supply side platforms) who manage the
inventory by auctioning off and gathering the best bids from their connected
ad exchanges and ad networks. Those connected ad exchanges and ad networks
then subsequently run their own auctions in order to pick up the highest bids
to send over. By the same token, the DSPs (demand side platforms) that further
follow up the auction may also have an internal auction to pick up the highest
bids from their advertisers and send it back to the connected ad exchanges or
ad networks.

####  3.1.1 Truthful bidding is the dominant strategy

An auction, as a market clearing mechanism, imposes competition among
advertisers. We intend to incentivise them to reveal their private valuations
when placing their bids. The second price auction would ensure that
advertisers are better off when they tell the truth by specifying their bid
exactly as their private value [Milgrom, 2004].

To see this, we follow a simplified case in [Menezes and Monteiro, 2005]:
suppose an ad impression, represented by its vectorised feature
$\boldsymbol{x}$, is to be sold to one of $n$ advertisers (bidders) in an ad
exchange. Advertisers submit their bids simultaneously without observing the
bids made by others. Each advertiser $i$, $i=\\{1,...,n\\}$, privately,
estimates its click-through rate as $c_{i}(x)$.

Without loss of generality, we assume the value of a click for all the
advertisers is the same and set it as 1. The private valuation $v_{i}$ is thus
equal to $c_{i}(x)$ for each advertiser $i$. We also consider that all the
advertisers are _risk-neutral_. In other words, they are indifferent between
an expected value from a random event and receiving the same value for
certain.

Each advertiser knows his own private valuation $c_{i}$, but does not know
their opponent advertisers’ valuations. They however can have a belief, and
therefore an estimation about these valuations. The belief is commonly
represented by a distribution. To make our discussion simple, the opponent’
valuations are assumed to be drawn independently from the cumulative
distribution function $F(\cdot)$ with its density $f(\cdot)$ in the interval
$[0,+\infty]$. That is, $F_{V}(v)=P(V\leq v)$ denotes the probability that the
random variable $V$ is less than or equal to a certain value $v$. For
simplicity, we assume that the ad exchange (the seller) sets the reserve price
at zero (we will discuss the reserve price in Chapter 6).

Without loss of generality, we look at bidder 1, who has a value equal to
$v_{1}$, and chooses a bid $b_{1}$ to maximise his expected profits given that
bidders $2,...,n$ follow some strategy $b(\cdot)$. Assume bidder $i$ places
the highest bid among bidders $2,...,n$. Bidder 1’s expected profit $\pi_{1}$
can be written as

$\displaystyle\pi_{1}(v_{1},b_{i},b(\cdot))=\hfill\begin{cases}v_{1}-b_{i}&\text{if
}b_{1}>b_{i}>\max\\{b(v_{2}),...,\\\ &\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ b(v_{i-1}),b(v_{i+1}),...,b(v_{n})\\}\\\ 0&\text{if
}b_{1}<\max\\{b(v_{2}),...,b(v_{n})\\},\\\ \end{cases}$ (3.1)

where $b_{1}>b_{i}>\max\\{b(v_{2}),...,b(v_{i-1}),b(v_{i+1}),...,b(v_{n})\\}$
holds with probability
$\int_{0}^{b_{1}}dF(x)^{n-1}=\int_{0}^{b_{1}}(n-1)f(x)F(x)^{n-2}dx$. As such,
we have

$\displaystyle\pi_{1}(v_{1},b_{i},b(\cdot))=\int_{0}^{b_{1}}(v_{1}-x)(n-1)f(x)F(x)^{n-2}dx.\hfill$
(3.2)

The advertiser 1 is to choose $b_{1}$ in such a way that the above expected
reward is maximised. When $b_{1}>v_{1}$, we have

$\displaystyle\pi_{1}(v_{1},b_{i},b(\cdot))=\int_{0}^{v_{1}}(v_{1}-x)(n-1)f(x)F(x)^{n-2}dx+$
$\displaystyle\int_{v_{1}}^{b_{1}}(v_{1}-x)(n-1)f(x)F(x)^{n-2}dx,\hfill$ (3.3)

where the second integration is negative. Thus, the expected revenue will
increase when $b_{1}$ reaches $v_{1}$. By the same token, when $b_{1}<v_{1}$,
the second integration is positive. If $b_{1}$ reaches $v_{1}$, the expected
reward will increase by the amount:

$\displaystyle\int_{b_{1}}^{v_{1}}(v_{1}-x)(n-1)f(x)F(x)^{n-2}dx.\hfill$ (3.4)

Thus, the expected reward is maximised when $b_{1}=v_{1}$. So truth-telling is
a _dominant_ strategy, where dominance occurs when one strategy is better than
another strategy for one bidder (advertiser), no matter how other opponents
may bid.

In practice, however, advertisers might join the auction with a fixed budget
and be involved in multiple second-price auctions over the lifetime of a
campaign. As such, the truth-telling might not be a dominant strategy.
[Balseiro et al., 2015] studied a fluid mean-field equilibrium (FMFE) that
approximates the rational behaviours of the advertisers in such a setting.

While a game theoretical view provides insights into the advertisers’ and
publishers’ strategic behaviours, a practically more useful approach is to
take a statistical view of the market price and the volume, which will be
introduced next.

###  3.2 Winning probability

A bid request can be represented as a high dimensional feature vector [Lee et
al., 2012]. As before, we denote the vector as $\boldsymbol{x}$, which encodes
much information about the impression. An example feature vector includes,

Gender=Male && Hour=18 && City=London &&
Browser=firefox && URL=www.abc.com/xyz.html.

Without loss of generality, we regard the bid requests as generated from an
i.i.d. (independent and identical distribution) $\boldsymbol{x}\sim
p_{x}(\boldsymbol{x})$, where the time-dependency is modelled by considering
week/time as one of the features. Based on the bid request $\boldsymbol{x}$,
the ad agent (or demand-side platform, a.k.a. DSP) will then provide a bid
$b_{\boldsymbol{x}}$ following a bidding strategy. If such bid wins the
auction, the corresponding labels, i.e., user response $y$ (either click or
conversion) and market price $z$, are observed. Thus, the probability of a
data instance $(\boldsymbol{x},y,z)$ being observed relies on whether the bid
$b_{x}$ would win or not and we denote it as
$P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})$. Formally, this generative
process of creating observed training data $D=\\{(\boldsymbol{x},y,z)\\}$ is
summarised as:

$\displaystyle\underbrace{q_{x}(\boldsymbol{x})}_{\text{winning
impression}}\equiv\underbrace{P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})}_{\text{prob.
of winning the auction}}\cdot\underbrace{p_{x}(\boldsymbol{x})}_{\text{bid
request}},$ (3.5)

where probability $q_{x}(\boldsymbol{x})$ describes how feature vector
$\boldsymbol{x}$ is distributed within the training data. The above equation
indicates the relationship (bias) between the p.d.f. of the pre-bid full-
volume bid request data (prediction) and the post-bid winning impression data
(training); in other words, the predictive models would be trained on $D$,
where $\boldsymbol{x}\sim q_{x}(\boldsymbol{x})$, and be finally operated on
prediction data $\boldsymbol{x}\sim p_{x}(\boldsymbol{x})$.

As explained, the RTB display advertising uses the second price auction
[Milgrom, 2004, Yuan et al., 2013]. In the auction, the market price $z$ is
defined as the second highest bid from the competitors for an auction. In
other words, it is the lowest bid value one should have in order to win the
auction. The form of its distribution is unknown unless one has a strong
assumption as given in the previous section for theoretical analysis. In
practice, one can assume the market price $z$ is a random variable generated
from a fixed yet unknown p.d.f. $p_{z}^{\boldsymbol{x}}(z)$; then the auction
winning probability is the probability when the market price $z$ is lower than
the bid $b_{\boldsymbol{x}}$:

$\displaystyle w(b_{\boldsymbol{x}})\equiv
P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})=\int_{0}^{b_{\boldsymbol{x}}}p_{z}^{\boldsymbol{x}}(z)dz,$
(3.6)

where to simplify the solution and reduce the sparsity of the estimation, the
market price distribution (a.k.a., the bid landscape) is estimated on a
campaign level rather than per impression $\boldsymbol{x}$ [Cui et al., 2011].
Thus, for each campaign, there is a $p_{z}(z)$ to estimate, resulting in the
simplified winning function $w(b_{\boldsymbol{x}})$, as formulated in [Amin et
al., 2012]. [Zhang et al., 2016e] proposed a solution of estimating the
winning probability $P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})$ and then
using it for creating bid-aware gradients to solve CTR estimation and bid
optimisation problems.

###  3.3 Bid landscape forecasting

Estimating the winning probability and the volume (bid landscape forecasting)
is a crucial component in online advertising framework. However, it is paid
less attention than the components of user response prediction (Chapter 4) and
bid optimisation (Chapter 5). Researchers proposed several heuristic forms of
functions to model the winning price distribution. [Zhang et al., 2014a]
provided two forms of winning probability w.r.t. the bid price, which is based
on the observation of an offline dataset. However, this derivation has many
drawbacks since the winning price distribution in real world data may deviate
largely from a simple functional form. [Cui et al., 2011] proposed a log-
normal distribution to fit the winning price distribution. [Chapelle, 2015]
used a Dirac conditioned distribution to model the winning price under the
condition of given historical winning price. The main drawback of these
distributional methods is that they may lose the effectiveness of handling
various dynamic data and they also ignore the real data divergence [Cui et
al., 2011].

Basically, from an advertiser’s perspective, given the winning price
distribution $p_{z}(z)$ and the bid price $b$, the probability of winning the
auction is

$\displaystyle w(b)=\int_{0}^{b}p_{z}(z)dz,$ (3.7)

If the bid wins the auction, the ad is displayed and the utility and cost of
this ad impression are then observed. The expected cost of winning with the
bid $b$ is denoted as $c(b)$. With the second price auction, the expected cost
is given as

$\displaystyle c(b)=\frac{\int_{0}^{b}zp_{z}(z)dz}{\int_{0}^{b}p_{z}(z)dz},$
(3.8)

In summary, estimating the winning price distribution (p.d.f. $p(z)$) or the
winning probability given a bid (c.d.f. $w(b)$) is the key for bid landscape
forecasting, which will be explained next.

####  3.3.1 Tree-based log-normal model

In view of forecasting, a template-based method can be used to to fetch the
corresponding winning price distribution w.r.t. the given auction request, as
demonstrated by [Cui et al., 2011].

The targeting rules of different advertising campaigns may be quite different.
As such, the bid requests received by each campaign may follow various
distributions. [Cui et al., 2011] proposed to partition the campaign targeting
rules into mutually exclusive _samples_. Each sample refers to a unique
combination of targeted attributes, such as Gender=Male && Hour=18 &&
City=London. Then the whole data distribution following the campaign’s
targeting rules, e.g. Gender=Male && Hour=18-23 && Country=UK, is aggregated
from the samples. Thus the campaign’s targeting rules can be represented as a
set of samples $S_{c}=\\{s\\}$.

Furthermore, for the bid landscape modelling of each sample $s$, [Cui et al.,
2011] first assumed the winning price $z$ follow a log-normal distribution

$p_{s}(z;\mu,\sigma)=\frac{1}{z\sigma\sqrt{2\pi}}e^{\frac{-(\ln
z-\mu)^{2}}{2\sigma^{2}}},$ (3.9)

where $\mu$ and $\sigma$ are two parameters of the log-normal distribution.

[Cui et al., 2011] proposed to adopt gradient boosting decision trees (GBDT)
[Friedman, 2002] to predict the mean $\mathbb{E}[s]$ and standard deviation
$\text{Std}[s]$ of winning prices of each sample $s$ based on the features
extracted from the targeting rules of the sample, and then with a standard
transformation the (predicted) log-normal distribution parameters are obtained

$\displaystyle\mu_{s}$
$\displaystyle=\ln\mathbb{E}[s]-\frac{1}{2}\ln\Big{(}1+\frac{\text{Std}[s]^{2}}{\mathbb{E}[s]^{2}}\Big{)},$
(3.10) $\displaystyle\sigma_{s}^{2}$
$\displaystyle=\ln\Big{(}1+\frac{\text{Std}[s]^{2}}{\mathbb{E}[s]^{2}}\Big{)}.$
(3.11)

With the winning price distribution $p_{s}(z;\mu_{s},\sigma_{s})$ of each
sample $s$ modelled, the campaign-level $c$ winning price distribution is
calculated from the weighted summation of its targeting samples’
$p_{s}(z;\mu,\sigma)$

$p_{c}(z)=\sum_{s\in
S_{c}}\pi_{s}\frac{1}{z\sigma_{s}\sqrt{2\pi}}e^{\frac{-(\ln
z-\mu_{s})^{2}}{2\sigma_{s}^{2}}},$ (3.12)

where $\sum_{s\in S_{c}}\pi_{s}=1$ and $\pi_{s}$ is the prior probability
(weight) of sample $s$ in the campaign’s targeting rules $S_{c}$, which can be
defined as the proportion of the sample instances in the campaign’s whole
instances.

####  3.3.2 Censored linear regression

The drawback of the log-normal model above is that the feature vector of a bid
request is not fully utilised. A simple way for estimating the winning price
from the feature vector is to model it as a regression problem, e.g., linear
regression

$\hat{z}=\boldsymbol{\beta}^{T}\boldsymbol{x},$ (3.13)

where $\boldsymbol{x}$ is the feature vector of the bid request and
$\boldsymbol{\beta}$ is the model coefficient vector. [Wu et al., 2015]
learned the regression model using a likelihood loss function with a white
Gaussian noise

$z=\boldsymbol{\beta}^{T}\boldsymbol{x}+\epsilon,$ (3.14)

where $\epsilon\sim\mathcal{N}(0,\sigma^{2})$.

Furthermore, since the winning price of a bid request can be observed by the
DSP only if it wins the auction, the observed $(\boldsymbol{x},z)$ instances
are right-censored and, therefore, biased.

[Wu et al., 2015] adopt a censored linear regression [Greene, 2005] to model
the winning price w.r.t. auction features. For the observed winning price
$(\boldsymbol{x},z)$, the data log-likelihood is

$p(z)=\log\phi\Big{(}\frac{z-\boldsymbol{\beta}^{T}\boldsymbol{x}}{\sigma}\Big{)},$
(3.15)

where $\phi$ is the p.d.f. of a standard normal distribution, i.e., with 0
mean and 1 standard deviation.

For the losing auction data $(\boldsymbol{x},b)$ with the bid price $b$, we
only know the underlying winning price is higher than the bid, i.e., $z>b$,
the partial data log-likelihood is defined as the probability of the predicted
winning price being higher the bid, i.e.,

$P(\hat{z}>b)=\log\Phi\Big{(}\frac{\boldsymbol{\beta}^{T}\boldsymbol{x}-b}{\sigma}\Big{)},$
(3.16)

where $\Phi$ is the c.d.f. of a standard normal distribution.

Therefore, with the observed data $W=\\{(\boldsymbol{x},z)\\}$ and censored
data $L=\\{\boldsymbol{x},b\\}$, the training of censored linear regression is

$\min_{\boldsymbol{\beta}}-\sum_{(\boldsymbol{x},z)\in
W}\log\phi\Big{(}\frac{z-\boldsymbol{\beta}^{T}\boldsymbol{x}}{\sigma}\Big{)}-\sum_{(\boldsymbol{x},b)\in
L}\log\Phi\Big{(}\frac{\boldsymbol{\beta}^{T}\boldsymbol{x}-b}{\sigma}\Big{)}.$
(3.17)

####  3.3.3 Survival Model

[Amin et al., 2012] and [Zhang et al., 2016e] went further from a counting
perspective to address the problem of censored data. To see this, suppose
there is no data censorship, i.e., the DSP wins all the bid requests and
observes all the winning prices. The winning probability
$w_{o}(b_{\boldsymbol{x}})$ can be obtained directly from the observation
counting:

$\displaystyle
w_{o}(b_{\boldsymbol{x}})=\frac{\sum_{(\boldsymbol{x}^{\prime},y,z)\in
D}\delta(z<b_{\boldsymbol{x}})}{|D|},$ (3.18)

where $z$ is the historic winning price of the bid request
$\boldsymbol{x}^{\prime}$ in the training data, the indicator function
$\delta(z<b_{\boldsymbol{x}})=1$ if $z<b_{\boldsymbol{x}}$ and 0 otherwise.
This is a baseline of $w(b_{\boldsymbol{x}})$ modelling.

However, the above treatment is rather problematic. In practice there are
always a large portion of the auctions the advertiser loses ($z\geq
b_{\boldsymbol{x}}$),222For example, in the iPinYou dataset [Liao et al.,
2014], the overall auction winning rate of 9 campaigns is 23.8%, which is
already a very high rate in practice. in which the winning price is not
observed in the training data. Thus, the observations of the winning price are
_right-censored_ : when the DSP loses, it only knows that the winning price is
higher than the bid, but does not know its exact value. In fact,
$w_{o}(b_{\boldsymbol{x}})$ is a biased model and overestimates the winning
probability. One way to look at this is that it ignores the counts for losing
auctions where the historic bid price is higher than $b_{\boldsymbol{x}}$ (in
this situation, the winning price should have been higher than the historic
bid price and thus higher than $b_{\boldsymbol{x}}$) in the denominator of Eq.
(3.18).

[Amin et al., 2012] and [Zhang et al., 2016e] used survival models [Johnson,
1999] to handle the bias from the censored auction data. Survival models were
originally proposed to predict patients’ survival rate for a given time after
certain treatment. As some patients might leave the investigation, researchers
do not know their exact final survival period, but only know the period is
longer than the investigation period. Thus the data is right-censored. The
auction scenario is quite similar, where the integer winning price333The
mainstream ad exchanges require integer bid prices. Without a fractional
component, it is reasonable to analogise bid price to survival days. is
regarded as the patient’s underlying survival period from low to high and the
bid price as the investigation period from low to high. If the bid $b$ wins
the auction, the winning price $z$ is observed, which is analogous to the
observation of the patient’s death on day $z$. If the bid $b$ loses the
auction, one only knows the winning price $z$ is higher than $b$, which is
analogous to the patient’s left from the investigation on day $b$.

Specifically, [Amin et al., 2012] and [Zhang et al., 2016e] leveraged the non-
parametric Kaplan-Meier Product-Limit method [Kaplan and Meier, 1958] to
estimate the winning price distribution $p_{z}(z)$ based on the observed
impressions and the losing bid requests.

Suppose there is a campaign that has participated $N$ RTB auctions. Its
bidding log is a list of $N$ tuples $\langle
b_{i},w_{i},z_{i}\rangle_{i=1\ldots N}$, where $b_{i}$ is the bid price of
this campaign in the auction $i$, $w_{i}$ is the boolean value of whether this
campaign won the auction $i$, and $z_{i}$ is the corresponding winning price
if $w_{i}=1$. The problem is to model the probability of winning an ad auction
$w(b_{\boldsymbol{x}})$ with bid price $b_{\boldsymbol{x}}$.

If the data is transformed into the form of $\langle
b_{j},d_{j},n_{j}\rangle_{j=1\ldots M}$, where the bid price $b_{j}<b_{j+1}$.
$d_{j}$ denotes the number of ad auction winning cases with the winning price
exactly valued $b_{j}-1$ (in analogy to patients die on day $b_{j}$). $n_{j}$
is the number of ad auction cases which cannot be won with bid price $b_{j}-1$
(in analogy to patients survive to day $b_{j}$), i.e., the number of winning
cases with the observed winning price no lower than $b_{j}-1$444Assume that
the campaign will not win if it is a tie in the auction. plus the number of
losing cases when the bid is no lower than $b_{j}-1$. Then with bid price
$b_{\boldsymbol{x}}$, the probability of losing an ad auction is

$\displaystyle
l(b_{\boldsymbol{x}})=\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}},$
(3.19)

which just corresponds to the probability a patient survives from day 1 to day
$b_{\boldsymbol{x}}$. Thus the winning probability will be

$\displaystyle
w(b_{\boldsymbol{x}})=1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}.$
(3.20)

Table 3.1: An example of data transformation of 8 instances with bid price
between 1 and 4. Left: tuples of bid, win and cost $\langle
b_{i},w_{i},z_{i}\rangle_{i=1\ldots 8}$. Right: transformed survival model
tuples $\langle b_{j},d_{j},n_{j}\rangle_{j=1\ldots 4}$ and the calculated
winning probabilities. Here we also provide a calculation example of $n_{3}=4$
shown as blue in the right table. The counted cases of $n_{3}$ in the left
table are 2 winning cases with $z\geq 3-1$ and the 2 losing cases with $b\geq
3$, shown highlighted in blue colour. Source [Zhang et al., 2016e].

$b_{i}$ | $w_{i}$ | $z_{i}$
---|---|---
2 | win | 1
3 | win | 2
2 | lose | $\times$
3 | win | 1
3 | lose | $\times$
4 | lose | $\times$
4 | win | 3
1 | lose | $\times$

$b_{j}$ | $n_{j}$ | $d_{j}$ | $\frac{n_{j}-d_{j}}{n_{j}}$ | $w(b_{j})$ | $w_{o}(b_{j})$
---|---|---|---|---|---
1 | 8 | 0 | 1 | $1-1=0$ | 0
2 | 7 | 2 | $\frac{5}{7}$ | $1-\frac{5}{7}=\frac{2}{7}$ | $\frac{2}{4}$
3 | 4 | 1 | $\frac{3}{4}$ | $1-\frac{5}{7}\frac{3}{4}=\frac{13}{28}$ | $\frac{3}{4}$
4 | 2 | 1 | $\frac{1}{2}$ | $1-\frac{5}{7}\frac{3}{4}\frac{1}{2}=\frac{41}{56}$ | $\frac{4}{4}$

Table 3.1 gives an example of transforming the historic $\langle
b_{i},w_{i},z_{i}\rangle$ data into the survival model data $\langle
b_{j},d_{j},n_{j}\rangle$ and the corresponding winning probabilities
calculated by Eqs. (3.20) and (3.18). It can be observed that the Kaplan-Meier
Product-Limit model, which is a non-parametric maximum likelihood estimator of
the data [Dabrowska, 1987], makes use of all winning and losing data to
estimate the winning probability of each bid, whereas the observation-only
counting model $w_{o}(b_{\boldsymbol{x}})$ does not. As we can see in the
table $w_{o}(b_{\boldsymbol{x}})$ is consistently higher than
$w(b_{\boldsymbol{x}})$.

While developing accurate bid landscape forecasting models is a worthwhile
research goal, [Lang et al., 2012], however, pointed out that in practice it
can be more effective to handle the forecasting error by frequently rerunning
the offline optimisation, which updates the landscape model and the bidding
strategy with the real-time information. This would link to the feedback
control and pacing problems, which will be discussed in Section 5.5.

##  Chapter 4 User Response Prediction

Learning and predicting user response is critical for personalising tasks,
including content recommendation, Web search and online advertising. The goal
of the learning is to estimate the probability that the user will respond
with, e.g. clicks, reading, conversions in a given context [Menon et al.,
2011]. The predicted probability indicates the user’s interest on the specific
information item, such as a news article, webpage, or an ad, which shall
influence the subsequent decision making, including document ranking and ad
bidding. Taking online advertising as an example, click-through rate (CTR)
estimation has been utilised later for calculating a bid price in ad auctions
[Perlich et al., 2012]. It is desirable to obtain an accurate prediction not
only to improve the user experience, but also to boost the volume and profit
for the advertisers. For the performance-driven RTB display advertising, user
response prediction, i.e. click-through rate (CTR) and conversion rate (CVR)
prediction [Lee et al., 2012, Ahmed et al., 2014], is a crucial building box
directly determining the follow-up bidding strategy to drive the performance
of the RTB campaigns.

This chapter will start with a mathematical formulation of user response
prediction. We will then discuss the most widely used linear models including
logistic regression and Bayesian probit regression, and then move it to non-
linear models including factorisation machines, gradient tree models, and deep
learning. Our focus will be on the techniques that have been successful in
various CTR prediction competitions for RTB advertising.111Some CTR prediction
models, such as FTRL logistic regression [McMahan et al., 2013] and Bayesian
profit regression [Graepel et al., 2010], though are originally proposed for
sponsored search, are sufficiently generic for user response prediction in
various scenarios, which are also presented in this chapter.

###  4.1 Data sources and problem statement

Figure 4.1: An example of multi-field categorical data instance of ad display
context and its click label and CTR prediction.

Figure 4.1 provides an illustration of a data instance of user response
prediction problem. A data instance can be denoted as a $(\boldsymbol{x},y)$
pair, where $y$ is the user response label, usually binary, such as whether
there is a user click on the ad (1) or not (0), $\boldsymbol{x}$ is the input
feature vector describing the user’s context and the candidate ad. As shown in
the figure, the raw data of feature $\boldsymbol{x}$ is normally in a multi-
field categorical form. For example, the field Weekday consists of 7
categories, i.e. Monday, Tuesday,…, Sunday; the field Browser consists of
several categories, e.g. Chrome, IE, Firefox etc.; the field City consists of
tens of thousands of cities such as London, Paris, Amsterdam.

Advertisers or DSPs collect billions of such data instances daily to learn
user response patterns. They may also collect information forming extra fields
to extend the representation of the training data, such as joining and syncing
with user’s demographic data from a third-party data provider by the user
cookie or device ID etc.

Typical feature engineering over such multi-field categorical data is _One-Hot
encoding_ [He et al., 2014]. In One-Hot encoding, each field is modelled as a
high dimensional space and each category of this field is regarded as one
dimension. Only the dimension with the field category is set as 1, while all
others are 0. The encoded binary vectors for an example with three fields will
be like

$\underbrace{[0,1,0,0,0,0,0]}_{\texttt{Weekday=Tuesday}},\underbrace{[1,0,0,0,0]}_{\texttt{Browser=Chrome}},\underbrace{[0,0,1,0,\ldots,0,0]}_{\texttt{City=London}}.$

The binary encoded vector of the data instance is then created by
concatenating the binary vectors of the field as

$\boldsymbol{x}=[\underbrace{0,1,0,0,0,0,0}_{\texttt{Weekday=Tuesday}},\underbrace{1,0,0,0,0}_{\texttt{Browser=Chrome}},\underbrace{0,0,1,0,\ldots,0,0}_{\texttt{City=London}}].$

Since the dimension of each field depends on the number of categories of this
field, the resulted binary vector $\boldsymbol{x}$ is extremely sparse. In
some practical applications, the hash tricks are applied to reduce the vector
dimensions [Chapelle et al., 2014, Weinberger et al., 2009]

###  4.2 Logistic regression with stochastic gradient descent

We denote $\boldsymbol{x}\in\mathbb{R}^{N}$ to describe the binary bid request
features as discussed previously. A straightforward solution, the logistic
regression model, to predict the CTR is given as

$\displaystyle\hat{y}=P(y=1|\boldsymbol{x})=\sigma(\boldsymbol{w}^{T}\boldsymbol{x})=\frac{1}{1+e^{-\boldsymbol{w}^{T}\boldsymbol{x}}},$
(4.1)

and the non-click probability is

$\displaystyle
1-\hat{y}=P(y=0|\boldsymbol{x})=\frac{e^{-\boldsymbol{w}^{T}\boldsymbol{x}}}{1+e^{-\boldsymbol{w}^{T}\boldsymbol{x}}},$
(4.2)

where $\boldsymbol{w}\in\mathbb{R}^{N}$ is the model coefficient vector, which
represents a set of parameters to be learned over training data.

The cross entropy loss function is commonly used for training the logistic
regression model:

$\displaystyle L(y,\hat{y})=-y\log\hat{y}-(1-y)\log(1-\hat{y}).$ (4.3)

In addition, the loss function is normally with a regularisation term to help
the model avoid overfitting. With L2-norm regularisation, the loss function
becomes:

$\displaystyle
L(y,\hat{y})=-y\log\hat{y}-(1-y)\log(1-\hat{y})+\frac{\lambda}{2}\|\boldsymbol{w}\|_{2}^{2}.$
(4.4)

Taking the derivation leads to the gradient on the efficient vector
$\boldsymbol{w}$

$\displaystyle\frac{\partial
L(y,\hat{y})}{\partial\boldsymbol{w}}=(\hat{y}-y)\boldsymbol{x}+\lambda\boldsymbol{w},$
(4.5)

and with the learning rate $\eta$, the stochastic gradient descent (SGD)
update of $\boldsymbol{w}$ is

$\displaystyle\boldsymbol{w}\leftarrow(1-\eta\lambda)\boldsymbol{w}+\eta(y-\hat{y})\boldsymbol{x},$
(4.6)

for an instance $\boldsymbol{x}$ randomly sampled from the training data. Note
that the input bid request $\boldsymbol{x}$ is a sparse vector and only
contains a small number of non-zero entries that equals the number of the
fields ($M$). Both the calculation of $\hat{y}$ and the update of coefficients
$\boldsymbol{w}$ are very fast as they are only involved with the non-zero
entries.

In SGD learning, the learning rate $\eta$ can be a fixed value, or a decayed
value depending on the application. The decayed value of $\eta_{t}$ at $t$-th
iteration can be updated as

$\displaystyle\eta_{t}=\frac{\eta_{0}}{\sqrt{t}},$ (4.7)

in order to fine-tune the parameters in the later stage. [He et al., 2014]
provided several practical updating schemes of $\eta$, and the optimal
implementation of $\eta$ updating depends on the specific training data.

###  4.3 Logistic regression with follow-the-regularised-leader

To bypass the problem of tuning the learning rate $\eta$ with various
strategies, [McMahan et al., 2013] proposed an online learning algorithm of
logistic regression, called _follow-the-regularised-leader proximal_ (FTRL-
proximal).

In the $t$-th iteration, FTRL calculates the new coefficients $\boldsymbol{w}$
as

$\displaystyle\boldsymbol{w}_{t+1}=\operatorname*{arg\,min}_{\boldsymbol{w}}\Big{(}\boldsymbol{w}^{T}\boldsymbol{g}_{1:t}+\frac{1}{2}\sum_{s=1}^{t}\sigma_{s}\|\boldsymbol{w}-\boldsymbol{w}_{s}\|^{2}_{2}+\lambda_{1}\|\boldsymbol{w}\|_{1}\Big{)},$
(4.8)

where $\boldsymbol{g}_{1:t}=\sum_{s=1}^{t}\boldsymbol{g}_{s}$ and
$\boldsymbol{g}_{s}$ is the $s$-th iteration logistic regression gradient as
in Eq. (4.5) and $\sigma_{s}$ is defined as
$\sigma_{s}=\frac{1}{\eta_{t}}-\frac{1}{\eta_{k-1}}$.

The solution of Eq. (4.8) is in fact very efficient in time and space: only
one parameter per coefficient needs to be stored. Eq. (4.8) can be rewritten
as

$\displaystyle\boldsymbol{w}_{t+1}=\operatorname*{arg\,min}_{\boldsymbol{w}}\boldsymbol{w}^{T}\Big{(}\boldsymbol{g}_{1:t}-\sum_{s=1}^{t}\sigma_{s}\boldsymbol{w}_{s}\Big{)}+\frac{1}{\eta_{t}}\|\boldsymbol{w}\|^{2}_{2}+\lambda_{1}\|\boldsymbol{w}\|_{1}.$
(4.9)

Let $\boldsymbol{z}_{t}$ be the number stored in memory at the beginning of
each iteration $t$:

$\displaystyle\boldsymbol{z}_{t}=\boldsymbol{g}_{1:t}-\sum_{s=1}^{t}\sigma_{s}\boldsymbol{w}_{s}=\boldsymbol{z}_{k-1}+\boldsymbol{g}_{t}+\Big{(}\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}\Big{)}\boldsymbol{w}_{t},$
(4.10)

where the closed form solution for each dimension $i$ of $\boldsymbol{w}$ is

$\displaystyle
w_{t+1,i}=\left\\{\begin{array}[]{ll}0&\text{if\leavevmode\nobreak\
}|z_{t,i}|\leq\lambda_{1}\\\
-\eta_{t}(z_{t,i}-\text{sign}(z_{t,i})\lambda_{1})&\text{otherwise}\end{array}\right.$
(4.13)

where $\text{sign}(z_{t,i})=1$ if $z_{t,i}$ positive and $-1$ otherwise, which
is normally used in parameter updating with L1 regularisation. Practically, it
has been shown that logistic regression with FTRL works better than that with
SGD. The experiments on RTB and non-RTB advertising user response prediction
have demonstrated the efficiency and effectiveness of the FTRL training
[McMahan et al., 2013, Ta, 2015].

###  4.4 Bayesian probit regression

[Graepel et al., 2010] proposed a Bayesian learning model called Bayesian
probit regression. In order to deal with the uncertainty of the parameter
estimation, the coefficients $\boldsymbol{w}$ is regarded as a random variable
with p.d.f. defined as Gaussian distribution

$\displaystyle
p(\boldsymbol{w})=\mathcal{N}(\boldsymbol{w};\boldsymbol{\mu},\boldsymbol{\Sigma}).$
(4.14)

The prediction function is thus modelled as a conditional distribution222In
this section, for mathematical convenience, the binary label is denoted as
$y=-1$ for non-click cases and $y=1$ for click cases.

$\displaystyle
P(y_{i}|\boldsymbol{x}_{i},\boldsymbol{w})=\Phi(y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{w}),$
(4.15)

where the non-linear function
$\Phi(\theta)=\int_{-\infty}^{\theta}\mathcal{N}(s;0,1)ds$ is the c.d.f. of
the standard Gaussian distribution. The model parameter $w$ is assumed to be
drawn from a Gaussian distribution, which originates from a prior and updated
with the posterior distribution by data observation.

$\displaystyle p(\boldsymbol{w}|\boldsymbol{x}_{i},y_{i})\propto
P(y_{i}|\boldsymbol{x}_{i},\boldsymbol{w})\mathcal{N}(\boldsymbol{w};\boldsymbol{\mu}_{i-1},\boldsymbol{\Sigma}_{i-1})$
(4.16)

The posterior is non-Gaussian and it is usually solved via variational methods
in practice. Let
$\mathcal{N}(\boldsymbol{w};\boldsymbol{\mu}_{i},\boldsymbol{\Sigma}_{i})$ be
the posterior distribution of $\boldsymbol{w}$ after observing the case
$(y_{i},\boldsymbol{x}_{i})$. The variational inference aims to minimise the
Kullback-Leibler divergence by finding the optimal distribution parameters
$\boldsymbol{\mu}_{i}$ and $\boldsymbol{\Sigma}_{i}$.

$\displaystyle(\boldsymbol{\mu}_{i},\boldsymbol{\Sigma}_{i})=\operatorname*{arg\,min}_{(\boldsymbol{\mu},\boldsymbol{\Sigma})}\mathbf{KL}\Big{(}\Phi(y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{w})\mathcal{N}(\boldsymbol{w};\boldsymbol{\mu}_{i-1},\boldsymbol{\Sigma}_{i-1})\|\mathcal{N}(\boldsymbol{w};\boldsymbol{\mu}_{i},\boldsymbol{\Sigma}_{i})\Big{)}$
(4.17)

Considering up to the second-order factors gives the closed form solution of
this optimisation problem as

$\displaystyle\mu_{i}$
$\displaystyle=\mu_{i-1}+\alpha\boldsymbol{\Sigma}_{i-1}\boldsymbol{x}_{i}$
(4.18) $\displaystyle\Sigma_{i}$
$\displaystyle=\Sigma_{i-1}+\beta(\boldsymbol{\Sigma}_{i-1}\boldsymbol{x}_{i})(\boldsymbol{\Sigma}_{i-1}\boldsymbol{x}_{i})^{T},$
(4.19)

where

$\displaystyle\alpha$
$\displaystyle=\frac{y_{i}}{\sqrt{\boldsymbol{x}_{i}^{T}\boldsymbol{\Sigma}_{i}\boldsymbol{x}_{i}+1}}\frac{\mathcal{N}(\theta)}{\Phi(\theta)}$
(4.20) $\displaystyle\beta$
$\displaystyle=\frac{1}{\sqrt{\boldsymbol{x}_{i}^{T}\boldsymbol{\Sigma}_{i}\boldsymbol{x}_{i}+1}}\frac{\mathcal{N}(\theta)}{\Phi(\theta)}\Big{(}\frac{\mathcal{N}(\theta)}{\Phi(\theta)}+\theta\Big{)},$
(4.21)

where

$\displaystyle\theta=\frac{y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{\mu}_{i-1}}{\sqrt{\boldsymbol{x}_{i}^{T}\boldsymbol{\Sigma}_{i-1}\boldsymbol{x}_{i}+1}}.$
(4.22)

Note that [Graepel et al., 2010] assumed the independence of features and only
focused on the diagonal elements in $\boldsymbol{\Sigma}_{i}$ in practice.

To sum up, the above sections have introduced several linear models and their
variations for the response prediction problem. Linear models are easy to
implement with high efficiency. However, the regression methods can only learn
shallow feature patterns and lack the ability to catch high-order patterns
unless an expensive pre-process of combining features is conducted [Cui et
al., 2011]. To tackle this problem, non-linear models such as factorisation
machines (FM) [Menon et al., 2011, Ta, 2015] and tree-based models [He et al.,
2014] are studied to explore feature interactions.

###  4.5 Factorisation machines

[Rendle, 2010] proposed the factorisation machine (FM) model to directly
explore features’ interactions by mapping them into a low dimensional space:

$\hat{y}_{\text{FM}}(\boldsymbol{x})=\sigma\Big{(}w_{0}+\sum_{i=1}^{N}w_{i}x_{i}+\sum_{i=1}^{N}\sum_{j=i+1}^{N}x_{i}x_{j}\boldsymbol{v}_{i}^{T}\boldsymbol{v}_{j}\Big{)},$
(4.23)

where each feature $i$ is assigned with a bias weight $w_{i}$ and a
$K$-dimensional vector $\boldsymbol{v}_{i}$; the feature interaction is
modelled as their vectors’ inner products between $\boldsymbol{v}_{i}$. The
activation function $\sigma()$ can be set according to the problem. For CTR
estimation, the sigmoid activation function, as in Eq. (4.1), is normally
used. Note that Eq. (4.23) only involves the second-order feature
interactions. By naturally introducing tensor product, FM supports higher-
order feature interactions.

FM is a natural extension of matrix factorisation that has been very
successful in collaborative filtering based recommender systems [Koren et al.,
2009]. Specifically, when there are only two fields in the data: user ID $u$
and item ID $i$, the factorisation machine prediction model will be reduced to

$\displaystyle\hat{y}_{\text{MF}}(\boldsymbol{x})=\sigma\Big{(}w_{0}+w_{u}+w_{i}+\boldsymbol{v}_{u}^{T}\boldsymbol{v}_{i}\Big{)},$
(4.24)

which is the standard matrix factorisation model.

The inner product of feature vectors practically works well to explore the
feature interactions, which is important in collaborative filtering. With the
success of FM in various recommender systems [Rendle and Schmidt-Thieme, 2010,
Rendle et al., 2011, Chen et al., 2011a, Loni et al., 2014], it is natural to
explore FM’s capability in CTR estimation.

[Menon et al., 2011] proposed to use collaborative filtering via matrix
factorisation for the ad CTR estimation task. Working on the mobile ad CTR
estimation problem, [Oentaryo et al., 2014b] extended FM into a hierarchical
importance-aware factorisation machine (HIFM) by incorporating importance
weights and hierarchical learning into FM. [Ta, 2015] borrowed the idea of
FTRL in [McMahan et al., 2013] and applied this online algorithm onto FM and
reported significant performance improvement on ad CTR estimation.

###  4.6 Decision trees

Decision tree is a simple non-linear supervised learning method [Breiman et
al., 1984] and can be used for CTR estimation. The tree model that predicts
the label of a given bid request is done by learning a simple sequential, tree
structured (binary), decision rule from the training data. As illustrated in
Figure 4.2, a bid request instance $\boldsymbol{x}$ is parsed through the tree
on the basis of its attributes, and at the end arrived at one of the leaves.
The weight assigned to the leaf is used as the prediction. Mathematically, a
decision tree is a function, denoted as $f(\boldsymbol{x})$ below:

$\displaystyle\hat{y}_{\text{DT}}(\boldsymbol{x})=f(\boldsymbol{x})=w_{I(\boldsymbol{x})},\quad
I:R^{d}\to\\{1,2,...,T\\},$ (4.25)

where a leaf index function $I(\boldsymbol{x})$ is introduced to map an
instance bid request $\boldsymbol{x}$ to a leaf $t$. Each leaf is assigned a
weight $w_{t}$, $t=1,...,T$, where $T$ denotes the total number of leaves in
the tree, and the prediction is assigned as the weight of the mapped leaf
$I(\boldsymbol{x})$.

Figure 4.2: An example decision tree, where a given bid request
$\boldsymbol{x}$ is mapped to a leaf, and the weight $w$ at the leaf produces
the prediction value.

###  4.7 Ensemble learning

A major problem of decision trees is their high variance — a small change in
the data could often lead to very different splits in the tree [Friedman et
al., 2001]. To reduce the instability and also help avoiding over-fitting the
data, in practice, multiple decision trees can be combined together. Our
discussion next focuses on _bagging_ and _boosting_ , the two most widely-used
ensemble learning techniques.

####  4.7.1 Bagging (bootstrap aggregating)

_Bagging_ (Bootstrap aggregating) is a technique averaging over a set of
predictors that have been learned over randomly-generated training sets
(bootstrap samples) [Breiman, 1996].

More specifically, given a standard training set $D$ of $n$ training examples,
first generate $K$ new training sets $D_{k}$, each of size $n$, by sampling
from $D$ uniformly and with replacement (some examples may be repeated in each
dataset). The $K$ (decision tree) models are then fitted using the $K$
bootstrapped training sets. The bagging estimate is obtained by averaging
their outputs:

$\displaystyle\hat{y}_{\text{bag}}(\boldsymbol{x})=\frac{1}{K}\sum_{k=1}^{K}\hat{f}^{\text{bag}}_{k}(\boldsymbol{x}).$
(4.26)

A good bagging requires the basis decision trees to be as little correlated as
possible. However, if one or a few features (e.g, the field Weekday, Browser,
or City) are strong predictors for the target output, these features are
likely to be selected in many of the trees, causing them to become correlated.
_Random Forest_ [Breiman, 2001] solves this by only selecting a random subset
of the features as a node to split (the tree), leading to more stable and
better performance in practice.

####  4.7.2 Gradient boosted regression trees

By contrast, _boosting_ methods aim at combining the outputs of many _weak_
predictors (in an extreme case, perform just slightly better than random
guessing) to produce a single _strong_ predictor [Friedman, 2002, Friedman,
2001]. Unlike bagging where each basis predictor (e.g., decision tree) is
independently constructed using a bootstrap sample of the data set, boosting
works in an iterative manner; it relies on building the successive trees that
continuously adjust the prediction that is incorrectly produced by earlier
predictors. In the end, a weighted vote is taken for prediction. More
specifically, for a boosted decision tree:

$\displaystyle\hat{y}_{\text{GBDT}}(\boldsymbol{x})=\sum_{k=1}^{K}f_{k}(\boldsymbol{x}),$
(4.27)

where the prediction is a linear additive combination of the outputs from $K$
numbers of basis decision trees $f_{k}(\boldsymbol{x})$. For simplicity,
consider the weight of each predictor is equal.

Thus, the tree learning is to find right decision $f_{k}$ so that the
following objective is minimised:

$\displaystyle\sum_{i=1}^{N}L(y_{i},\hat{y}_{i})+\sum_{k=1}^{K}\Omega(f_{k}),$
(4.28)

where the objective consists of a loss function $L$ of the predicted values
$\hat{y}_{i}$, $i=1,...,N$, against the true labels $y_{i}$, $i=1,...,N$, and
a regularisation term $\Omega$ controlling the complexity of each tree model.
One can adopt _Forward Stagewise Additive_ training by sequentially adding and
training a new basis tree without adjusting the parameters of those that have
already been added and trained [Friedman et al., 2001]. Formally, for each
$k=1,...,M$ stage

$\displaystyle\hat{f}_{k}=\operatorname*{arg\,min}_{f_{k}}\sum_{i=1}^{N}L\big{(}y_{i},F_{k-1}(\boldsymbol{x}_{i})+f_{k}(\boldsymbol{x}_{i})\big{)}+\Omega(f_{k})$
(4.29)

where

$\displaystyle F_{0}(\boldsymbol{x})$ $\displaystyle=0,$ (4.30) $\displaystyle
F_{k}(\boldsymbol{x})$
$\displaystyle=F_{k-1}(\boldsymbol{x})+\hat{f}_{k}(\boldsymbol{x}),$ (4.31)

and the training set is denoted as $\\{y_{i},\boldsymbol{x}_{i}\\},i=1,...,N$.
The complexity of a tree is defined as

$\displaystyle\Omega(f_{k})=\gamma
T+\frac{1}{2}\lambda\sum_{t=1}^{T}w^{2}_{t},$ (4.32)

where $\lambda$ and $\gamma$ are the hyper-parameters. $t$ is the index of the
features and there are $T$ number of features.

To solve Eq. 4.29, one can consider the objective as the function of
prediction $\hat{y}_{k}$ and make use of Taylor expansion of the objective:

$\displaystyle\sum_{i=1}^{N}L\big{(}y_{i},F_{k-1}(\boldsymbol{x}_{i})+f_{k}(\boldsymbol{x}_{i})\big{)}+\Omega(f_{k})$
$\displaystyle\simeq$
$\displaystyle\sum_{i=1}^{N}\Big{(}L^{k-1}+\frac{\partial
L^{k-1}}{\partial\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})+\frac{1}{2}\frac{\partial^{2}L^{k-1}}{\partial^{2}\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})^{2}\Big{)}+\Omega(f_{k})$
$\displaystyle\simeq$ $\displaystyle\sum_{i=1}^{N}\Big{(}\frac{\partial
L^{k-1}}{\partial\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})+\frac{1}{2}\frac{\partial^{2}L^{k-1}}{\partial^{2}\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})^{2}\Big{)}+\Omega(f_{k}),$
(4.33)

where define
$L^{k-1}=L\big{(}y_{i},\hat{y}_{i}^{k-1}\big{)}=L\big{(}y_{i},F_{k-1}(\boldsymbol{x}_{i})\big{)}$,
which can be safely removed as it is independent of the added tree
$f_{k}(\boldsymbol{x}_{i})$. Replacing Eqs. (4.25) and (4.32) into the above
gives:

$\displaystyle\sum_{i=1}^{N}\Big{(}\frac{\partial
L^{k-1}}{\partial\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})+\frac{1}{2}\frac{\partial^{2}L^{k-1}}{\partial^{2}\hat{y}_{i}^{k-1}}f_{k}(\boldsymbol{x}_{i})^{2}\Big{)}+\Omega(f_{k})$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{N}\Big{(}\frac{\partial
L^{k-1}}{\partial\hat{y}_{i}^{k-1}}w_{I(\boldsymbol{x}_{i})}+\frac{1}{2}\frac{\partial^{2}L^{k-1}}{\partial^{2}\hat{y}_{i}^{k-1}}w_{I(\boldsymbol{x}_{i})}^{2}\Big{)}+\gamma
T+\frac{1}{2}\lambda\sum_{t}^{T}w^{2}_{t}$ (4.34) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\Big{(}(\sum_{i\in I_{t}}\frac{\partial
L^{k-1}}{\partial\hat{y}_{i}^{k-1}})w_{t}+\frac{1}{2}(\sum_{i\in
I_{t}}\frac{\partial^{2}L^{k-1}}{\partial^{2}\hat{y}_{i}^{k-1}}+\lambda)w_{t}^{2}\Big{)}+\gamma
T,$ (4.35)

where $I_{t}$ denotes the set of instance indexes that have been mapped to
leaf $t$. The above is the sum of $T$ independent quadratic functions of the
weights $w_{t}$. Taking the derivative and making it to zero obtains the
optimal weights for each leaf $t$ as:

$\displaystyle w_{t}=-\frac{\sum_{i\in I_{t}}(\partial
L^{k-1})/(\partial\hat{y}_{i}^{k-1})}{\Big{(}\sum_{i\in
I_{t}}(\partial^{2}L^{k-1})/(\partial^{2}\hat{y}_{i}^{k-1})+\lambda\Big{)}}.$
(4.36)

Placing back the weights give the optimal objective function as

$\displaystyle-\frac{1}{2}\sum_{t=1}^{T}\frac{\big{(}\sum_{i\in
I_{t}}(\partial
L^{k-1}/\partial\hat{y}_{i}^{k-1})\big{)}^{2}}{\Big{(}\sum_{i\in
I_{t}}(\partial^{2}L^{k-1})/(\partial^{2}\hat{y}_{i}^{k-1})+\lambda\Big{)}}+\gamma
T.$ (4.37)

The above solution is a general one where one can plugin many loss functions.
Let us consider a common squared-error loss:

$\displaystyle
L\Big{(}y_{i},F_{k-1}(\boldsymbol{x}_{i})+f_{k}(\boldsymbol{x}_{i})\Big{)}=$
$\displaystyle\Big{(}y_{i}-F_{k-1}(\boldsymbol{x}_{i})-f_{k}(\boldsymbol{x}_{i})\Big{)}^{2}$
(4.38) $\displaystyle=$
$\displaystyle\Big{(}r_{ik}-f_{k}(\boldsymbol{x}_{i})\Big{)}^{2};$ (4.39)
$\displaystyle L^{k-1}=L\Big{(}y_{i},F_{k-1}(\boldsymbol{x}_{i})\Big{)}=$
$\displaystyle\Big{(}y_{i}-F_{k-1}(\boldsymbol{x}_{i}))\Big{)}^{2}=(r_{ik})^{2},$
(4.40)

where $r_{ik}$ is simply the residual of the previous model on the $i$-th
training instance. Replacing the first and second derivatives of $L^{k-1}$
into Eq. (4.36) gives:

$\displaystyle w_{t}=\frac{\sum_{i\in
I_{t}}y_{i}-F_{k-1}(\boldsymbol{x}_{i})}{\Big{(}|I_{t}|+\lambda/2\Big{)}}=\frac{\sum_{i\in
I_{t}}r_{ik}}{\Big{(}|I_{t}|+\lambda/2\Big{)}},$ (4.41)

where one can see that the optimal weight at leaf $t$ is the one that best
fits the previous residuals in that leaf when the regularisation $\lambda$ is
not considered.

With the optimal objective function in Eq. (4.37), one can take a greedy
approach to grow the tree and learn its tree structure: for each tree node,
all features are enumerated. For each feature, sort the instances by feature
value. If it is real-valued, use a linear scan to decide the best split along
that feature. For categorical data in our case, one-hot-encoding is used. The
best split solution is judged based on the optimal objective function in Eq.
(4.37) and take the best split solution along all the features. A distributed
version can be found at [Tyree et al., 2011].

####  4.7.3 Hybrid Models

All the previously mentioned user response prediction models are not mutually
exclusive and in practice they can be fused in order to boost the performance.
Facebook reported a solution that combines decision trees with logistic
regression [He et al., 2014]. The idea was to non-linearly transform the input
features by gradient boosted regression trees (GBRTs) and the newly
transformed features were then treated as new categorical input features to a
sparse linear classifier. To see this, suppose there is an input bid request
with features $\boldsymbol{x}$. Multiple decision trees are learned from
GBRTs. If the first tree thinks $\boldsymbol{x}$ belong to node 4, the second
node 7, and the third node 6, then the features 1:4, 2:7, 3:6 are generated
for this bid request and then hash it in order to feed to a regressor. A
follow-up solution from the Criteo Kaggle CTR contest also reported that using
a field-aware factorisation machine [Juan et al., 2016] rather than logistic
regression as the final prediction from GBRTs features had also led to
improved accuracy of the prediction.

###  4.8 User lookalike modelling

Compared with sponsored search or contextual advertising, RTB advertising has
the strength of being able to directly target specific users — _explicitly_
build up user profiles and detect user interest segments via tracking their
online behaviours, such as browsing history, clicks, query words, and
conversions.333Note that in sponsored search, user-level targeting is still
possible, namely remarketing lists for search ads (RLSA), but it is more
emphasised and more widely used in RTB display advertising. More details about
RLSA: https://support.google.com/adwords/answer/2701222?hl=en.

Thus, when estimating the user’s response (rate), the advertiser would be able
to, on the basis of the learned user profiles, identify and target unknown
users who are found in ad exchanges and have the similar interests and
commercial intents with the known (converted) customers. Such technology is
referred as user _look-alike modelling_ [Zhang et al., 2016a, Mangalampalli et
al., 2011], which in practice has proven to be effective in providing high
targeting accuracy and thus bringing more conversions to the campaigners [Yan
et al., 2009].

The current user profiling methods include building keyword and topic
distributions [Ahmed et al., 2011] or clustering users onto a (hierarchical)
taxonomy [Yan et al., 2009]. Normally, these inferred user interest segments
are then used as target restriction rules or as features leveraged in
predicting users’ ad response [Zhang et al., 2014a], where those regression
techniques introduced previously, e.g., logistic regression, matrix
factorisation, boosted decision trees, can be incorporated.

However, a major drawback of the above solutions is that the user interest
segments building, is performed independently and has little attention of its
use of ad response prediction. In the next section, we shall introduce a
particular technique, transfer learning that implicitly transfers the
knowledge of user browsing pattens to that of the user response prediction
[Zhang et al., 2016a].

###  4.9 Transfer learning from Web browsing to ad clicks

Transfer learning deals with a learning problem where the training data of the
target task is expensive to get, or easily outdated; the training is helped by
transferring the knowledge learned from other related tasks [Pan and Yang,
2010]. Transfer learning has been proven to work on a variety of problems such
as classification [Dai et al., 2007], regression [Liao et al., 2005] and
collaborative filtering [Li et al., 2009]. It is worth mentioning that there
is a related technique called multi-task learning, where the data from
different tasks are assumed to drawn from the same distribution [Taylor and
Stone, 2009]. By contrast, transfer learning methods may allow for arbitrary
source and target tasks. In real time bidding based advertising, [Dalessandro
et al., 2014] proposed a transfer learning scheme based on logistic regression
prediction models, where the parameters of ad click prediction model were
restricted with a regularisation term from the ones of user Web browsing
prediction model. [Zhang et al., 2016a] extended it by considering matrix
factorisation to fully explore the benefit of collaborative filtering.

Specifically, in RTB advertising, there are commonly two types of observations
about underlying user behaviours: one from their browsing behaviours (the
interaction with webpages) and one from their ad responses, e.g., conversions
or clicks, towards display ads (the interactions with the ads) [Dalessandro et
al., 2014]. There are two predictions tasks for understanding user behaviours:

Web Browsing Prediction (CF Task). Each user’s online browsing behaviour is
logged as a list containing previously visited publishers (domains or URLs). A
common task of using data is to leverage collaborative filtering (CF) [Wang et
al., 2006, Rendle, 2010] to infer the users’ profile, which is then used to
predict whether the user is interested in visiting any given new publisher.
Formally, denote the dataset for CF as $D_{\text{c}}$, which contains
$N_{\text{c}}$ users and $M_{\text{c}}$ publishers and an observation is
denoted as $(\boldsymbol{x}_{\text{c}},y_{\text{c}})$, where
$\boldsymbol{x}_{\text{c}}$ is a feature vector containing the attributes from
users and publishers and $y_{\text{c}}$ is the label indicating whether the
user visits the publisher or not.

Ad Response Prediction (CTR Task). Each user’s online ad feedback behaviour is
logged as a list of pairs of rich-data ad impression event and the
corresponding feedback (e.g., click or not). The task is to build a click-
through rate (CTR) prediction model [Chapelle et al., 2014] to estimate how
likely it is that the the user will click a specific ad impression in the
future. Each ad impression event consists of various information, such as user
data (cookie ID, location, time, device, browser, OS etc), publisher data
(domain, URL, ad slot position etc), and advertiser data (ad creative,
creative size, campaign etc.). Mathematically, denote the ad CTR dataset as
$D_{\text{r}}$ and its data instance as
$(\boldsymbol{x}_{\text{r}},y_{\text{r}})$, where $\boldsymbol{x}_{\text{r}}$
is a feature vector and $y_{\text{r}}$ is the label indicating whether the
user clicks a given ad or not.

Although they are different prediction tasks, two tasks share a large
proportion of users and their features. Thus a user interest model can be
built jointly from the two tasks. Typically there are large amount of
observations about user browsing behaviours and it may be promising to use the
knowledge learned from publisher CF recommendation to help infer display
advertising CTR estimation.

In the solution proposed by [Zhang et al., 2016a], the prediction models on
the CF task and CTR task are learned jointly. Specifically, the authors build
a joint data generation framework by the two prediction tasks.For both
predictions, the labels are considered to be binary. More detailed
implementation of the CF and CTR prediction modules are provided in [Zhang et
al., 2016a].

###  4.10 Deep learning over categorical data

Deep neural networks have demonstrated their superior performance on various
tasks ranging from image recognition [He et al., 2015], speech recognition
[Hinton et al., 2012], and machine translation [Bahdanau et al., 2014] to
natural language processing [Collobert and Weston, 2008]. In some of tasks,
the prediction accuracy has arguably reached a comparable human-level [Mnih et
al., 2015, He et al., 2015].

A notable similarity among those tasks is that visual, aural, and textual
signals are known to be spatially and/or temporally correlated. The newly
introduced unsupervised training on deep structures [Bengio et al., 2007] or
embedding the knowledge as prior would be able to explore such _local_
dependency and establish a _sparse_ representation of the feature space,
making neural network models effective in learning high-order features
directly from the raw feature input. For instance, convolutional neural
networks employ local filters to explore local dependencies among pixels
[LeCun et al., 1998, LeCun and Bengio, 1995].

With such learning ability, deep learning would be a good candidate to
estimate online user response rate such as ad CTR. However, there are two
difficulties: firstly, most input features in CTR estimation are discrete
categorical features, e.g., the user location city, device type, publisher
website, ad category, and their local dependencies (thus the sparsity in the
feature space) are unknown. Thus how deep learning improves the CTR estimation
via learning feature representation on such large-scale multi-field discrete
categorical features. Secondly, training deep neural networks (DNNs) on a
large input feature space requires tuning a huge number of parameters, which
is computationally expensive. For instance, unlike the image and video cases,
there are about 1 million binary input features and 100 hidden units in the
first layer; then it requires 100 million links to build the first layer
neural network.

[Zhang et al., 2016b] studied deep learning over a large multi-field
categorical feature space by using embedding methods in both supervised and
unsupervised fashions. Two types of deep learning models were introduced:
Factorisation Machine supported Neural Network (FNN) and Sampling-based Neural
Network (SNN). Specifically, FNN with a supervised-learning embedding layer
using factorisation machines [Rendle, 2012] is proposed to efficiently reduce
the dimension from sparse features to dense continuous features. The second
model SNN is a deep neural network powered by a sampling-based restricted
Boltzmann machine or a sampling-based denoising auto-encoder with a proposed
negative sampling method. Based on the embedding layer, multiple layers neural
nets with full connections were built to explore non-trivial data patterns.
Later, inspired by FNN and FM, [Qu et al., 2016] proposed a product-based
feature-interaction layer between the feature embedding layer and the full
connection layers to induce the feature interaction learning.

In the context of sponsored search, [Zhang et al., 2014c] argued that user’s
behaviours on ads are highly correlated with historical events of the user’s
activities, such as what queries they submitted, what ads they clicked or
ignored in the past, and how long they spent on the landing pages of clicked
ads. They used recurrent neural networks (RNN) to directly model the
dependency on user’s sequential behaviours into the click prediction process
through the recurrent structure in the network.

###  4.11 Dealing with missing data

As discussed in Chapter 3, the training data (observed clicks/non-clicks for a
bid request) for user response estimation is biased and contains missing data.
Only when a bid wins the auction, are the corresponding labels, i.e., user
response $y$ (either click or conversion) and market price $z$, observed.
Thus, the probability of a data instance (contains bid request feature,
labels, market price) $(\boldsymbol{x},y,z)$ being observed relies on whether
the bid $b_{\boldsymbol{x}}$ would win or not. Following Chapter 3, we denote
it as $P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})$. As before, the
generative process of creating observed training data
$D=\\{(\boldsymbol{x},y,z)\\}$ is summarised as:

$\displaystyle\underbrace{q_{x}(\boldsymbol{x})}_{\text{winning
impression}}\equiv\underbrace{P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})}_{\text{prob.
of winning the auction}}\cdot\underbrace{p_{x}(\boldsymbol{x})}_{\text{bid
request}},$ (4.42)

where probability $q_{x}(\boldsymbol{x})$ describes how feature vector
$\boldsymbol{x}$ is distributed within the training data. As discussed in
Chapter 3, the above equation indicates the relationship (bias) between the
p.d.f. (probabilistic density function) of the pre-bid full-volume bid request
data (prediction) and the post-bid winning impression data (training); in
other words, the predictive models would be trained on $D$, where
$\boldsymbol{x}\sim q_{x}(\boldsymbol{x})$, and be finally operated on
prediction data $\boldsymbol{x}\sim p_{x}(\boldsymbol{x})$.

In Chapter 3, we have presented an unbiased estimation of the winning
probability $P(\text{win}|\boldsymbol{x},b_{\boldsymbol{x}})$ using a non-
parametric survival model. Here we shall introduce a solution of using it for
creating bid-aware gradient descent to solve CTR estimation for both logistic
regression and factorisation machine as well as neural networks [Zhang et al.,
2016e].

Generally, given a training dataset $D=\\{(\boldsymbol{x},y,z)\\}$, where the
data instance $\boldsymbol{x}$ follows the training data distribution
$q_{x}(\boldsymbol{x})$, (the red data distribution in Figure 4.3), an
_unbiased_ supervised learning problem, including previously mentioned
logistic regression, matrix factorisation and deep learning, can be formalised
into a loss-minimisation problem on prediction data distribution
$p_{x}(\boldsymbol{x})$ (the blue data distribution in Figure 4.3):

$\displaystyle\min_{\boldsymbol{\theta}}\leavevmode\nobreak\
\leavevmode\nobreak\ \mathbb{E}_{\boldsymbol{x}\sim
p_{x}(\boldsymbol{x})}[\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))]+\lambda\Phi(\boldsymbol{\theta}),$
(4.43)

where $f_{\boldsymbol{\theta}}(\boldsymbol{x})$ is
$\boldsymbol{\theta}$-parametrised prediction model to be learned;
$\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))$ is the loss function
based on the ground truth $y$ and the prediction
$f_{\boldsymbol{\theta}}(\boldsymbol{x})$; $\Phi(\boldsymbol{\theta})$ is the
regularisation term that penalises the model complexity; $\lambda$ is the
regularisation weight. With Eqs. (3.5) and (3.6), one can use importance
sampling to reduce the bias of the training data:

$\displaystyle\mathbb{E}_{\boldsymbol{x}\sim
p_{x}(\boldsymbol{x})}[\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))]=\int_{\boldsymbol{x}}p_{x}(\boldsymbol{x})\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\int_{\boldsymbol{x}}q_{x}(\boldsymbol{x})\frac{\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))}{w(b_{\boldsymbol{x}})}d\boldsymbol{x}=\mathbb{E}_{\boldsymbol{x}\sim
q_{x}(\boldsymbol{x})}\Big{[}\frac{\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))}{w(b_{\boldsymbol{x}})}\Big{]}$
(4.44) $\displaystyle=$
$\displaystyle\frac{1}{|D|}\sum_{(\boldsymbol{x},y,z)\in
D}\frac{\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))}{w(b_{\boldsymbol{x}})}=\frac{1}{|D|}\sum_{(\boldsymbol{x},y,z)\in
D}\frac{\mathcal{L}(y,f_{\boldsymbol{\theta}}(\boldsymbol{x}))}{1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}}.$

Figure 4.3: From an advertiser perspective, the ad auction selection acts as a
dynamic data filter based on bid value, which leads to distribution
discrepancy between the post-bid training data (red, right) and pre-bid
prediction data (blue, left). Source: [Zhang et al., 2016e].

Based on this framework, if the auction winning probability
$w(b_{\boldsymbol{x}})$, e.g., Eq. (3.20), is obtained, one can eliminate the
bias for each observed training data instance. Let us look at the case of CTR
estimation with logistic regression

$\displaystyle
f_{\boldsymbol{\theta}}(\boldsymbol{x})=\frac{1}{1+e^{-\boldsymbol{\theta}^{T}\boldsymbol{x}}}.$
(4.45)

With the cross entropy loss between the binary click label $\\{0,1\\}$ and the
predicted probability and L2 regularisation, the framework of Eq. (4.44) is
written as

$\displaystyle\min_{\boldsymbol{\theta}}\frac{1}{|D|}\sum_{(\boldsymbol{x},y,z)\in
D}\frac{-y\log
f_{\boldsymbol{\theta}}(\boldsymbol{x})-(1-y)\log(1-f_{\boldsymbol{\theta}}(\boldsymbol{x}))}{1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}}+\frac{\lambda}{2}\|\boldsymbol{\theta}\|_{2}^{2},$
(4.46)

where the winning probability
$w(b_{\boldsymbol{x}})=1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}$
is estimated for each observation instance, which is independent from the CTR
estimation parameter $\boldsymbol{\theta}$.444In this section we use
$\boldsymbol{\theta}$ to denote the weights of logistic regression instead of
$\boldsymbol{w}$ in order to avoid the term conflict with the winning
probability $w(b_{\boldsymbol{x}})$. The update rule of $\boldsymbol{\theta}$
is routine using stochastic gradient descent. The derived _Bid-aware Gradient
Descent_ (BGD) calculation of Eq. (4.46) is555The term $|D|$ is merged into
$\lambda$ for simplicity.

$\displaystyle\boldsymbol{\theta}\leftarrow(1-\eta\lambda)\boldsymbol{\theta}+\frac{\eta}{1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}}\Big{(}y-\frac{1}{1+e^{-\boldsymbol{\theta}^{T}\boldsymbol{x}}}\Big{)}\boldsymbol{x}.$
(4.47)

From the equation above, one can observe that with a lower winning bid
$b_{\boldsymbol{x}}$, the probability
$1-\prod_{b_{j}<b_{\boldsymbol{x}}}\frac{n_{j}-d_{j}}{n_{j}}$ of seeing the
instance in the training set is lower. However, the corresponding gradient
from the data instance is higher and vice versa as it is in the denominator.

This is intuitively correct as when a data instance $\boldsymbol{x}$ is
observed with low probability, e.g., 10%, one can infer there are 9 more such
kind of data instances missed because of auction losing. Thus the training
weight of $\boldsymbol{x}$ should be multiplied by 10 in order to recover
statistics from the full-volume data. By contrast, if the winning bid is
extremely high, which leads 100% auction winning probability, then such data
is observed from the true data distribution. Thus there will be no gradient
reweighting on this data. Such non-linear relationship has been well captured
in the bid-aware learning update in the gradient updates.

###  4.12 Model comparison

As discussed in this chapter, there are various user response prediction
models. From the modeling perspective, these models can be generally
categorised as linear and non-linear models.

Linear models, including logistic regression [Lee et al., 2012, McMahan et
al., 2013] and Bayesian probit regression (with diagonal covariance matrix)
[Graepel et al., 2010], directly build the model based on the feature
independence assumption. For linear models, the feature interaction patterns
are generally captured by building large-scale feature space with combining
multi-field features, which could consume much human effort. However, thanks
to its high efficiency and high parallelization capability, linear models are
able to be fed in much more training data instances (and higher dimensional
features) during the same training period, which makes them still highly
comparable with the non-linear models in many industrial environments.

Non-linear models, including factorisation machine [Rendle, 2010, Juan et al.,
2016], tree models [He et al., 2014] and recently emerged (deep) neural
networks models [Zhang et al., 2016b, Qu et al., 2016], provide model capacity
of automatically learning feature interaction patterns without the need of
designing combining features. These non-linear models generally need much more
computation resources than the linear ones, and some of them may require
multiple stages of model training, as demostrated in [He et al., 2014]. With
the fast development high performance computing (HPC) and the explosion of
data volume, non-linear models are more and more applied in commercial
platforms for practical user response prediction.

###  4.13 Benchmarking

There are some real-world benchmark datasets that are publicly avaiable for
the research of user response prediction in RTB display advertising.

iPinYou

dataset [Liao et al., 2014] comes from the company hosted global RTB algorithm
competition during over 10 days in 2013, including 3 seasons. Normally the
data of season 2 and 3 are used because of the same data schema, with 24 semi-
hashed fields and the user click/conversion responses. Download link:
http://data.computational-advertising.org.

Criteo 1TB Click Log

is a realistic industry-defining benchmark release by Criteo. The dataset
contains 24 days of ad click logs, and the data has been cleaned and hashed,
including 13 numerical and 26 categorical fields, labeled with the user click
responses. Download link: http://labs.criteo.com/downloads/download-terabyte-
click-logs/.

Criteo Conversion Log

is another dataset from Criteo focusing on conversion prediction [Chapelle,
2014]. Download link: http://labs.criteo.com/2013/12/conversion-logs-dataset/.

YOYI

runs a major DSP focusing on multi-device display advertising in China. YOYI
dataset [Kan et al., 2016] contains 402M impressions, 500K clicks and 428K CNY
expense during 8 days in Jan. 2016. Download link: http://goo.gl/xaao4q.

Avazu

releases its 11-day online ad click data for its Avazu Click Prediction
competition on Kaggle. Download link: https://www.kaggle.com/c/avazu-ctr-
prediction/data.

Note that iPinYou and YOYI datasets further contain bidding and auction
winning price information, which supports the research of bidding strategy
optimisation as will be discussed in Chapter 5.

Since there are different settings of user response prediction, thus it could
be more feasible to list some benchmarking references [Zhang et al., 2014b, He
et al., 2014, Lee et al., 2012, Zhang et al., 2016b, Qu et al., 2016, Ren et
al., 2016] than conducting a specific setting of experiments in this survey.

##  Chapter 5 Bidding Strategies

Once it is able to estimate the effectiveness of an ad impression from the
previous chapter by estimating user’s response rates (e.g., the click-through
rate or the conversion rate), the next step is to use it for optimising the
bidding. A bidding strategy refers to the logic of deciding a bid price given
an ad display opportunity. Good bidding strategy directly leads to effective
and accurate RTB ad delivery. Thus designing an optimal bidding strategy is
regarded as one of the most important problems in RTB display advertising.

There are two types of approaches towards optimal bidding strategies. A game-
theoretical view assumes the rationality of the players (advertisers and
publishers) in making decisions [Osborne and Rubinstein, 1994, Milgrom, 2004,
Gummadi et al., 2012] and formulates the incentives and the impact of the
interplays among the players, whereas a statistical view assumes no or less
interplay among the advertisers and publishers and studies decision-making
under uncertainty [Berger, 1985].

This chapter takes the latter approach as assuming advertisers are strategic
and rational is questionable in practice [Yuan et al., 2013] and the
statistical approach is likely to lead to practically useful solutions, which
are indeed the majority solutions for industrial RTB platforms.

In the formulation stated in this chapter, the bidding strategy is abstracted
as a function which takes in the information of a specific ad display
opportunity, i.e., the bid request, and outputs the corresponding bid price
for each qualified ad, as illustrated in Figure 5.1. How this bidding function
should be designed involves multiple factors, including the auction volume
during the campaign’s lifetime, the campaign budget and the campaign-specific
key performance indicator (KPI), such as the number of clicks or conversions,
or advertising revenue.

Figure 5.1: A bidding strategy can be abstracted as a function mapping from
the given bid request (in a high dimensional feature space) to a bid price (a
non-negative real or integer number).

###  5.1 Bidding problem: RTB vs. sponsored search

Bid optimisation is a well-studied problem in online advertising [Feldman et
al., 2007, Hosanagar and Cherepanov, 2008, Ghosh et al., 2009, Perlich et al.,
2012]. Nonetheless, most research has been so far limited to keyword auction
in the context of sponsored search (SS) [Edelman et al., 2005, Animesh et al.,
2005, Mehta et al., 2007a]. Typically, under the scenario of pre-setting the
keyword bids (not impression level), the keyword utility, cost and volume are
estimated and then an optimisation process is performed to optimise the
advertisers’ objectives (KPIs) [Borgs et al., 2007, Zhou et al., 2008, Kitts
and Leblanc, 2004, Zhang et al., 2014e]. Given a campaign budget as the cost
upper bound, optimising the advertiser performance is defined as a budget
optimisation problem [Feldman et al., 2007, Muthukrishnan et al., 2010].
Furthermore, [Broder et al., 2011] and [Even Dar et al., 2009] focused on the
bid generation and optimisation on broad matched keywords, where query
language features are leveraged to infer the bid price of related keywords.
[Zhang et al., 2012] proposed to jointly optimise the keyword-level bid and
campaign-level budget allocation under a multi-campaign sponsored search
account. Some recent work focuses on periodically changing the pre-setting
keyword auction price, taking into account the remaining budget and lifetime.
For instance, in [Amin et al., 2012, Gummadi et al., 2011], Markov decision
process was used to perform online decision in tuning the keyword bid price,
where the remaining auction volume and budget act as states and the bid price
setting as actions. [Kitts and Leblanc, 2004] proposed to calculate a bid
allocation plan during the campaign lifetime, where the bid price on each
keyword is set in different discrete time units by considering the market
competition and the CTR on different ad positions. However, none of the work
evaluates per-impression auction in SS; all the bids are associated with
keywords while impression level features are seldom considered, especially for
advertisers and their agencies. Moreover, in SS bid optimisation, search
engines play two roles: setting the keyword bids as well as hosting the
auctions. The objective function could be diverted to optimise the overall
revenue for the search engine [Abrams, 2006, Radlinski et al., 2008, Devanur
and Hayes, 2009, Zhu et al., 2009b], rather than the performance of each
individual advertiser’s campaigns.

The bid optimisation for RTB display advertising is fundamentally different.
First, the bids are not determined by pre-defined keywords [Yuan et al.,
2013], but are based on impression level features. Although in general,
advertisers (or DSPs) are required to set up their target rules, they need to
estimate the value of each ad impression that is being auctioned in real time
and return the bid price per auction. Second, in RTB, CPM pricing is generally
used. Winning an impression directly results in the cost, despite the fact
clicks and conversions can now be directly optimised by advertisers and DSPs.
Thus, the dependencies over various effectiveness measures such as
eCPC,111Effective cost per click (eCPC) - The cost of a campaign divided by
the total number of clicks delivered. CPM and the budget constraints need to
be studied in a single framework. [Ghosh et al., 2009] proposed an algorithm
that learns winning bids distribution from full or partial information of
auctions in display advertising. The algorithm then makes bidding decisions to
achieve the best delivery (number of impressions) within the budget
constraint. In [Chen et al., 2011b], the bid price from each campaign can be
adjusted by the publisher side in real time and the target is to maximise the
publisher side revenue.

Other relevant problems in RTB have also been studied. [Lee et al., 2013]
focused on the pacing problem, where the target is to smoothly deliver the
campaign budget. From the SSP perspective, the reserve price setting in RTB ad
auctions is studied in [Yuan et al., 2014]. In [Lee et al., 2012] the sparsity
problem of conversion rate estimation is handled by modelling the conversions
at different selected hierarchical levels. [Dalessandro et al., 2015]
investigated the evaluation measures of the display advertising performance
and they found the site visit turns out to be a better proxy than the user
click. In addition, there is some work on the ad exchange communication
problem [Chakraborty et al., 2010, Muthukrishnan, 2009].

###  5.2 Concept of quantitative bidding in RTB

In a performance-driven advertising scenario, each ad display opportunity,
i.e., bid request, is _quantified_ where its _utility_ , e.g., the probability
of a user clicking on the displayed ad [Oentaryo et al., 2014b] or the
expected revenue from this ad impression [Ahmed et al., 2014, Lee et al.,
2012], and _cost_ , e.g., the cost of winning this ad impression in the
auction [Cui et al., 2011], are carefully estimated. Based on the estimated
utility and cost of each bid request, [Zhang et al., 2014a] proposed the
concept of quantitative bidding. This means that the logic of the bidding
function should only depend on two factors: the estimated utility of the ad
display opportunity and the estimated cost to win it. All other information
can be regarded as independent with the bid price conditioned only by these
two factors,222All the information needed to determine the bid has been
reflected in the utility and cost factors, just like the conditional
independence in probabilistic graphic models. as illustrated in Figure 5.2.
For example, a sneakers advertiser would like to bid high on users with ages
between 15 and 30. This is motivated by the fact that users in such a segment
are more likely to be converted to purchase the sneakers after seeing the ads.
This is quantified as a higher conversion rate. This is analogous with a high
frequency trading strategy in a stock/option market where the trading action
is wholly based on the quantified risks and the returns for each asset,
regardless of the specific asset attributes or fundamentals [Durbin, 2010].

Figure 5.2: The quantitative bidding: the logic of the bidding function only
depends on two (sets of) factors, i.e., the estimated utility and the cost of
the ad display opportunity.

Using the estimated utility and cost, the optimal bidding function to maximise
the specific KPI under the target campaign budget and auction volume
constraints can be derived.

The research frontier and implementations of the utility estimation module and
cost estimation module in Figure 5.2 have been well investigated in Chapter 4
and Section 3.3, respectively. In the later sections of this chapter, various
bidding strategies and their connections will be discussed.

###  5.3 Single-campaign bid optimisation

With the modules of CTR/CVR estimation (Chapter 4) and bid landscape
forecasting (Section 3.3) ready, bid optimisation techniques seek an optimal
bidding strategy to maximise a certain objective (with possible constraints).

In this section, the derivation of different bidding strategies under the
presumed settings will be discussed.

####  5.3.1 Notations and preliminaries

Define the bidding function as $b(r)$ which returns the bid price given the
estimated click-through rate (CTR) $r$ of an ad impression. Various machine
learning models for predicting CTR have been introduced in Chapter 4.

Winning probability. From an advertiser’s perspective, given the market price
distribution $p_{z}(z)$ and the bid price $b$, the probability of winning the
auction is

$\displaystyle w(b)=\int_{0}^{b}p_{z}(z)dz.$ (5.1)

If the bid wins the auction, the ad is displayed and the utility and cost of
this ad impression are then observed.

Utility. The utility function given the CTR is denoted as $u(r)$. The specific
form of $u(r)$ depends on the campaign KPI. For example, if the KPI is click
number, then

$\displaystyle u_{\text{clk}}(r)=r.$ (5.2)

If the KPI is the campaign’s profit, with the advertiser’s true value on each
click is $v$, then

$\displaystyle u_{\text{profit}}(r,z)=vr-z.$ (5.3)

Cost. If the advertiser wins the auction with a bid $b$, the expected cost is
denoted as $c(b)$. In the RTB context there could be first price auctions

$\displaystyle c_{1}(b)=b,$ (5.4)

and second price auctions

$\displaystyle
c_{2}(b)=\frac{\int_{0}^{b}zp_{z}(z)dz}{\int_{0}^{b}p_{z}(z)dz}.$ (5.5)

Different market settings and campaign strategies define different cost
functions. If the auction is a first price auction, then $c_{1}(b)$ should be
used. For second price auctions, $c_{2}(b)$ is reasonably adopted, but [Zhang
et al., 2014a] still used $c_{1}(b)$ to conservatively model the upper bound
of the second price auctions with possible soft floor prices. Here it is
feasible to first use the abstract cost function $c(b)$ in the framework and
then specify the implementation of the cost function in specific tasks.

Campaign settings. Each campaign is set with specific targeting rules,
lifetime and budget. Generally, the targeting rules differentiate the volume,
leading to different bid landscapes $p(z)$ and utility (CTR/CVR)
distributions. The campaign’s targeting rules and lifetime determine the
auction volume $T$ it could receive. The campaign’s budget $B$ defines the
upper bound of its cost during the lifetime.

####  5.3.2 Truth-telling bidding

For non-budget bid optimisation, only $u_{\text{profit}}(r)$ utility function
is meaningful333If there are no cost-related factors in the utility, one will
bid as high as possible to win every impression as there is no budget
constraint.

$\displaystyle U_{\text{profit}}(b(\cdot))$
$\displaystyle=T\int_{r}\int_{z=0}^{b(r)}u_{\text{profit}}(r,z)p_{z}(z)dz\cdot
p_{r}(r)dr$ (5.6)
$\displaystyle=T\int_{r}\int_{z=0}^{b(r)}(vr-z)p_{z}(z)dz\cdot p_{r}(r)dr.$
(5.7)

Take the gradient of net profit $U_{\text{profit}}(b(\cdot))$ w.r.t. the
bidding function $b(r)$ and set it to 0,

$\displaystyle\frac{\partial U_{\text{profit}}(b(\cdot))}{\partial
b(\cdot)}=(vr-b(r))\cdot p_{z}(b(r))\cdot p_{r}(r)=0,$ (5.8)

for all $r$, which derives

$\displaystyle b_{\text{true}}(r)=vr,$ (5.9)

i.e., the optimal bid price is set as the impression value. Thus the truth-
telling bidding is the optimal strategy when there is no budget considered.

The truth-telling property of $b_{\text{true}}(r)$ is inherited from the
classic second price auctions and the widely adopted VCG auctions in sponsored
search [Edelman et al., 2005], which makes this bidding strategy quite
straightforward and widely adopted in industry [Lee et al., 2012, Chen et al.,
2011b]. However, the truth-telling bidding strategy is optimal only when the
budget and auction volume are not considered.

####  5.3.3 Linear bidding

With the campaign lifetime auction volume and budget constraints, the optimal
bidding strategies are probably not truth-telling. Extending from the truth-
telling bidding strategy, [Perlich et al., 2012] proposed the generalised
bidding function with a linear relationship to the predicted CTR for each ad
impression being auctioned:

$\displaystyle b_{\text{lin}}(r)=\phi vr,$ (5.10)

where $\phi$ is a constant parameter to tune to fit the market competitiveness
and the volume. Specifically, the optimal value of $\phi$ should just maximise
the objective with the budget constraint on the training data.

[Perlich et al., 2012] proved that the linear bidding function
$b_{\text{lin}}(r)$ practically works well in various settings. However, from
a scientific perspective, [Perlich et al., 2012] did not provide any theoretic
soundness as to why the optimal bidding function should be linear as in Eq.
(5.10).

####  5.3.4 Budget constrained clicks and conversions maximisation

[Zhang et al., 2014a, Zhang et al., 2016c] proposed a general bid optimisation
framework to incorporate different utility and cost functions.

Assuming one wants to find the optimal bidding function $b()$ to maximise the
campaign-level KPI $r$ across its auctions over the lifetime, with total bid
requests volume $T$ and budget $B$

$\displaystyle\max_{b()}\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle T\int_{r}u(r)w(b(r))p_{r}(r)dr$ (5.11) subject to
$\displaystyle T\int_{r}c(b(r))w(b(r))p_{r}(r)dr=B.$

The Lagrangian of the optimisation problem Eq. (5.11) is

$\displaystyle\mathcal{L}(b(r),\lambda)=$
$\displaystyle\int_{r}u(r)w(b(r))p_{r}(r)dr-\lambda\int_{r}c(b(r))w(b(r))p_{r}(r)dr+\frac{\lambda
B}{T},$ (5.12)

where $\lambda$ is the Lagrangian multiplier.

Solving $b()$. Based on calculus of variations, the Euler-Lagrange condition
of $b(r)$ is

$\displaystyle\frac{\partial\mathcal{L}(b(r),\lambda)}{\partial b(r)}=0,$
(5.13)

which is

$\displaystyle u(r)p_{r}(r)\frac{\partial w(b(r))}{\partial b(r)}-\lambda
p_{r}$ $\displaystyle(r)\Big{[}\frac{\partial c(b(r))}{\partial
b(r)}w(b(r))+c(b(r))\frac{\partial w(b(r))}{\partial b(r)}\Big{]}=0$ (5.14)
$\displaystyle\Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \lambda\frac{\partial c(b(r))}{\partial b(r)}w(b(r))=$
$\displaystyle\Big{[}u(r)-\lambda c(b(r))\Big{]}\frac{\partial
w(b(r))}{\partial b(r)}.$ (5.15)

Eq. (5.15) is a general condition of the optimal bidding function, where the
specific implementations of winning function $w(b)$, utility function $u(r)$
and cost function $c(b)$ are needed to derive the corresponding form of
optimal bidding function.

Solving $\lambda$. To solve $\lambda$, the bidding function can be explicitly
written as $b(r,\lambda)$, and the solution involves to solve

$\displaystyle\frac{\mathcal{L}(b(r,\lambda),\lambda)}{\partial\lambda}$
$\displaystyle=0,$ (5.16) $\displaystyle\Rightarrow
T\int_{r}c(b(r,\lambda))w(b(r,\lambda))p_{r}(r)dr$ $\displaystyle=B,$ (5.17)

which is to find the $\lambda$ to just exhaust the budget at the same time of
running out the auction volume. In practice, Eq. (5.17) has no analytic
solution but its numeric solution is very easy to obtain because $c(b)$ and
$w(b)$ monotonously increase w.r.t. $b$.

Later the analytic solution of $\lambda$ and $b(r,\lambda)$ under some special
setting of $w(b)$ and $p_{r}(r)$ will be shown.

##### First-price auction

With cost function $c_{1}(b)=b$ as in Eq. (5.4), Eq. (5.15) is written as

$\displaystyle\lambda\int_{0}^{b(r)}p_{z}(z)dz=(u(r)-\lambda b(r))\cdot
p_{z}(b(r))$ (5.18)

which still depends on the detailed form of market price distribution
$p_{z}(z)$ to solve the $b()$. [Zhang et al., 2014a] tried an implementation
in their paper:

$\displaystyle p_{z}(z)$ $\displaystyle=\frac{l}{(l+z)^{2}},$ (5.19)
$\displaystyle\Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ w(b)$
$\displaystyle=\frac{b}{b+l}.$ (5.20)

Taking Eq. (5.20) and click utility Eq. (5.2) into Eq. (5.18):

$\displaystyle\lambda\frac{b(r)}{b(r)+l}$ $\displaystyle=(u(r)-\lambda
b(r))\cdot\frac{b(r)}{(b(r)+l)^{2}}$ (5.21)
$\displaystyle\Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\
b_{\text{ortb}}(r)$ $\displaystyle=\sqrt{\frac{u(r)l}{\lambda}+l^{2}}-l,$
(5.22)

which is the derived optimal bidding function in [Zhang et al., 2014a]. The
analytical solution Eq. (5.22) shows that an optimal bidding function should
be non-linear. The non-linearity is closely related to the probability of
auction winning, but is loosely correlated with the prior distribution of the
impression features.

If the market price $z$ follows a uniform distribution in $[0,l]$, i.e.,

$\displaystyle p_{z}(z)=\frac{1}{l},$ (5.23)

Eq. (5.18) is rewritten as

$\displaystyle\lambda\frac{b(r)}{l}$ $\displaystyle=\frac{(u(r)-\lambda
b(r))}{l}$ (5.24) $\displaystyle\Rightarrow b(r)$
$\displaystyle=\frac{u(r)}{2\lambda}.$ (5.25)

Taking Eq. (5.25) into Eq. (5.17):

$\displaystyle T\int_{r}\frac{u(r)}{2\lambda}\cdot\frac{u(r)}{2\lambda
l}p_{r}(r)dr=B.$ (5.26)

Taking $u_{\text{clk}}(r)=r$ as in Eq. (5.2) and the special case of uniform
CTR distribution $p_{r}(r)=1$ into Eq. (5.26):

$\displaystyle T\int_{0}^{1}\frac{r^{2}}{4\lambda^{2}l}dr=B$ (5.27)
$\displaystyle\Rightarrow\lambda=\frac{1}{2}\sqrt{\frac{T}{3Bl}}.$ (5.28)

Thus the analytic form of the optimal bidding function is

$\displaystyle b(r)=r\sqrt{\frac{3Bl}{T}}.$ (5.29)

##### Second-price auction

Taking the definition of winning function Eq. (5.1) and the second-price cost
function Eq. (5.5) into Eq. (5.15):

$\displaystyle\lambda\frac{b(r)p_{z}(b(r))w(b(r))-p_{z}(b(r))\int_{0}^{b}zp_{z}(z)dz}{w(b(r))^{2}}w(b(r))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\