# Learning Optimal Bidding Strategy: Case Study in E-Commerce Advertising

Danil Provodin  Jérémie Joudioux  Steering Team, Performance marketing,
Traffic Platform Applied Science and Analytics, Zalando SE, Berlin,Germany
Eduard Duryev  Steering Team, Performance marketing, Traffic Platform Applied
Science and Analytics, Zalando SE, Berlin,Germany

###### Abstract

Although the bandits framework is a classical and well-suited approach for
optimal bidding strategies in sponsored search auctions, industrial attempts
are rarely documented. This paper outlines the development process at Zalando,
a leading fashion e-commerce company, and describes the promising outcomes of
a bandits-based approach to increase profitability in sponsored search
auctions. We discuss in detail the technical and theoretical challenges that
were overcome during the implementation, as well as the mechanisms that led to
increased profitability.

##  1 Introduction

Search engine advertising is essential for e-commerce companies, and bidding
algorithms have significantly improved their efficiency by enabling more
precise ad targeting. In the context of online advertising, a bidding problem
typically refers to the challenge faced by advertisers in optimizing bids in
sponsored search auctions for maximum profitability or conversions. To achieve
this goal, advertisers must carefully balance the cost of bidding with the
potential value of gaining clicks or conversions from their ad.

As a leading European company for clothing and beauty products (cosmetics),
Zalando made efficient marketing investments a key objective. This paper
documents a promising attempt at Zalando to optimize bids in sponsored search
auctions for maximum profitability using the bandits approach. Bandits is a
reinforcement learning (RL) approach that provides a formal framework for
sequential decision-making in repeated interactions with an environment.
Despite the extensive theoretical research on bandits (and RL in general) in
the past decade and their widespread usage in content placement,
recommendations, and e-commerce, there are only a few documented instances of
their industrial applications for bid optimization. Our work proves that
maximizing profitability through the RL approach can yield substantial value,
but it requires overcoming significant challenges that have yet to be
encountered in popular RL benchmarks.

As of independent interest, we introduce a computationally efficient bid
placement system and a substantial data collection mechanism that are prone to
the most challenges encountered in real-life scenarios (described in Section
1.2). Furthermore, the developed infrastructure is versatile and can be
readily adapted to any contextual decision-making setting.

###  1.1 Background and framework

Pay-per-click sponsored search auctions emerged in the late 1990s as a
quintessential example of auction theory and have become an indispensable part
of the business model of web hosts. Typically, the host (the seller) runs a
separate auction for each search query, and at each auction, the entity being
sold is the right to place an ad in a slot. Advertisers (bidders) repeatedly
bid for slots on a search engine and pay the seller only if their ad gained a
click. There is a fixed number of slots for advertisements, and the
advertisers have different valuations for these slots. The complexity of the
underlying auction mechanism of sponsored search engines and the large volume
of repeated auctions has given rise to an abundance of automated bidding
tools, where bidders were constantly changing their bids in response to new
information and changing information from other bidders [1].

In this paper, we take the bidder’s perspective and aim to develop an
algorithm that maximizes total profitability. Using a sequential decision-
making paradigm, we model repeated interactions between the seller (Google
Ads) and the bidder (Zalando). Specifically, we take an online learning
perspective and formulate a problem using adversarial bandits [2]. At each
iteration, the bidder has some (unknown) private value $v_{t}$ and submits a
bid $b_{t}$, based on the empirical importance-weighted performance of the
bids. The auction mechanism then outputs an outcome $r_{t}$. Using the bandit
language, the bidder selects action $b_{t}$ and consequently observes reward
$r_{t}$.

###  1.2 Challenges of learning in sponsored search auctions

In sponsored search auctions, the business goal is to optimize bids for
maximum profitability. It causes practitioners to focus on a complex and long-
term event, typically a conversion such as a sale. As such, learning in
sponsored search auctions poses a unique interplay between challenges from
various disciplines, including auctions and online advertising.

  * •

Blackbox auction mechanism. Most of the theoretical work assumes a structured
underlying auction mechanism, with some papers positing a generalized second-
price auction lying at the heart of the allocation process, while others
describe it as a first-price auction. However, for bidders participating in
Google Ads sponsored search auctions, the underlying auction mechanism remains
a black box, as Google does not disclose the type of auction mechanism being
used [3, 4].

  * •

Unknown valuation of the goods at sale. A standard assumption in the
literature on auction theory is that participants arriving in the market have
a clear assessment of their valuation for the goods at sale (see, e.g., [5, 6,
7, 8]). However, this assumption is severely violated in online advertising
where the high-frequency auction mechanism is subject to changing market
conditions and user behavior. This can amend the balance between exploration
and exploitation and complicate learning behavior [9].

  * •

Delayed feedback. While clicks can be observed shortly after an ad is
displayed, it may take hours or even days for the corresponding sale to occur.
This delay in feedback can make it challenging to optimize bids or other
decisions in online advertising, as the true value of action may take time to
be apparent [10].

  * •

Batch update. In sponsored search auctions, a large volume of multiple-item
auctions takes place per iteration, where bidders typically submit a batch of
bids. Consequently, bidders have access only to information aggregated over a
certain period, leading to batched feedback - where the rewards for a group of
actions are revealed together and observed at the end of the batch. In
contrast to traditional online feedback, where the reward for each action is
immediately revealed after it is chosen, learning from batched feedback can be
more efficient when obtaining feedback is costly or time-consuming but comes
at the cost of learning performance [11].

  * •

Reward sparsity. Sparse reward refers to a situation where the reward signal
provided to the learner is infrequent or incomplete. This is especially
cumbersome in marketing applications, where conversion rates are typically low
and observational data does not capture behavioral patterns. This scarcity of
information makes it difficult for advertisers to make informed decisions,
and, as a result, the optimization process becomes more challenging. RL
algorithms that depend on frequent and informative feedback to learn tend to
struggle in such settings.

  * •

Clicks attribution. After observing a desired outcome (a single conversion
event), it is challenging to attribute credit to a specific action in a
coherent way: a customer clicking on an advertisement might delay ordering or
buy another product if they buy a product at all. A user might furthermore
have been exposed to different ads at other points before the order conversion
happened, and assigning credit to a specific bid that was active at the
conversion time, can lead to an inability to evaluate its effectiveness
accurately.

  * •

Measurement. Beyond the click attribution to order, a company might be
interested in favoring clicks that lead, for instance, to recurring orders or
new customer acquisitions. This purpose is usually incorporated in a complex
mechanism, which measures which clicks led to such events. Hence, the click
value can be a complex quantity, making the measurement challenging.
Furthermore, the data we incorporate into learning are subject to various
biases, such as normalization or selection bias. It is crucial to be able to
construct an unbiased estimate of a desired metric to achieve reliable
results. This is particularly important in repeated interactions, where the
goal is to establish a causal relationship between the action and outcome
[12].

This list is incomplete, and there are many more challenges in real-life. We
focus on the successful resolution of the most pressing, in our view,
challenges.

###  1.3 Contribution

Addressing the aforementioned challenges requires a synthesis of RL techniques
as well as a bidding system. In this paper, we develop a systematic and
practical approach that explicitly optimizes bids for maximum profitability
and addresses most of the challenges. Our RL methodology captures Blackbox
auction mechanism, Unknown valuation of the goods at sale, Batch update, and
Measurement challenges. It does not, however, fully addresses the Clicks
attribution nor the data collection issues caused by Batched and Delayed
feedback, which we incorporate by a bid placement system on the deployment
side. Thus, only Reward sparsity issues remain unaddressed by our approach,
which we elaborate on in Sections 4.2 and 5.2.

The evaluation of our solution demonstrates an increase in partial profit
during the test duration. The mechanism by which this profit increase occurs
is nonetheless complex and varies depending on the product at sale. The main
source of profitability improvement comes from reduced costs: the algorithm
stopped advertising a certain number of low-profitable products to favour more
efficient bid values for a small selection of high-profitable products.

In summary, the paper makes the following contributions to the literature:

  * •

We document a successful attempt to learn optimally and efficiently in complex
sponsored search auctions.

  * •

We introduce an extension of the EXP3 algorithm to the batched and delayed
feedback setting, which we call Batch EXP3.

  * •

We develop a computationally efficient bid placement system that is, in
combination with the methodology, robust against many challenges arising in
real life. Moreover, the developed system is versatile and can be readily
adapted to any contextual decision-making setting.

  * •

To the best of our knowledge, we are the first to present an RL-based bidding
system, which is deployed in a live environment system.

###  1.4 Outline

Section 2 briefly recalls previous relevant work. Section 3 is devoted to the
methodological setup and contains problem definition (Section 3.1) and
translating it into the bandit setting (Section 3.2). The bidding system
deployment and live test design are given in Section 4. In Section 5, we
evaluate our solution and elaborate on mechanisms by which the profitability
is improved (Section 5.1). Consequently, in Section 6, we discuss the
limitations of our work and future directions. Finally, we conclude with
Section 7.

##  2 Related work

#### Auctions

The majority of auction theory research has focused on designing truthful
auction mechanisms to maximize the seller’s revenue by optimizing a reserve
price (a price below which no transaction occurs) [13, 14, 15]. A more
traditional approach takes a game-theoretic view, where the seller has perfect
or partial knowledge of bidders’ private valuations modeled as probability
distributions [16]. However, this approach has a major limitation as it relies
on perfect knowledge of the bidders’ value distribution which is unlikely to
be known to the seller in practice [5, 6].

In recent years the ubiquitous collection of data has presented new
opportunities where unknown quantities, such as the bidders’ value
distributions, may potentially be learned from past observations [17]. This
has led to the emergence of the online learning approach in repeated auctions
from both seller’s and bidder’s perspectives. Sellers usually seek to set a
reserve price to optimize revenues [18, 19, 20, 21, 22, 23]. In fact, this is
the main mechanism by which a seller can influence the auction revenue in
today’s electronic markets [18]. By contrast, bidders try to maximize their
reward while simultaneously learning the value of a good sold repeatedly [17,
24]. In particular, this triggered the emergence of a large number of various
RL approaches, which we describe below in more detail.

#### RL for bid optimization.

Unlike much of the mechanism design literature, RL approaches for bid
optimization are not searching for the optimal revenue under a truthful
auction mechanism. Rather, they focus on maximizing either seller’s or
bidder’s revenue. The existing research to optimize bidding strategy falls
into two main categories: methods based on the bandits formulation and methods
based on the full RL formulation.

The origin of the full RL methods in application to auctions can be traced
back to [25]. In this paper, the authors modeled a budget-constrained bidding
problem as a finite Markov Decision Process (MDP). The authors utilize a
model-based RL setting for the optimal action selection assuming the perfect
knowledge of the MDP. This work led to various improvements, such as proposing
model-free RL algorithms [26, 27], where the learner cannot obtain perfect
information, and considering continuous action space using policy gradient
methods [28]. However, this line of work has two major limitations: first, it
lacks theoretical guarantees, and, second, it does not tackle the real-life
challenges described in Section 1.2. For example, most of these papers rely
heavily on simulation and replay of datasets and focus on simpler impression-
based reward definitions. Additionally, their high complexity makes them
difficult to apply in real-life scenarios due to weak debuggability.

On the other hand, bandit-based methods have proved to be effective in
optimizing bidding strategies for the second-price auctions [17, 18, 29],
first-price auctions [7, 8, 30], and generalized auction mechanisms [9]. Due
to the truthfulness of second-price auctions, methods developed for such a
mechanism are based on optimism in the face of uncertainty principle [17, 18,
29], whereas first-price and generalized auction mechanisms leverage the
adversarial nature of the problem 111First-price and generalized auctions are
known to be untruthful, making the environment from the bidders’ perspective
adversarial. and use exponential weighting methods [7, 8, 9, 30].

One paper that we found particularly relevant to our approach is [9]. In this
paper, a general auction mechanism is considered, where the product valuation
$v_{t}$ is unknown, evolving in an arbitrary manner and observed only if the
bidder wins the auction. The authors decompose the reward of placing bid
$b_{t}$ at iteration $t$ as $r_{t}(b_{t})=rev_{t}(b_{t})x_{t}(b_{t})$, where
$x_{t}(\cdot)$ is the allocation function and $rev_{t}(\cdot)$ is the revenue
function. Consequently, they assume that while $rev_{t}(\cdot)$ is subject to
bandit feedback, $x_{t}(\cdot)$ is subject to online feedback, i.e., the
learner gets to observe $x_{t}(\cdot)$ for each bid $b$ and not only for the
placed bid $b_{t}$. Based on this, they develop an exponentially faster
algorithm (in action space) than a generic bandit algorithm ($O(\sqrt{T\lvert
B\rvert})\to O(\sqrt{T\log\lvert B\rvert})$, where $T$ is a horizon and
$\lvert B\rvert$ is the cardinality of a bid space). Unfortunately, due to the
complexity of our setting, we could not make use of their assumption and had
to recover to a more classical bandit approach in our solution [2].

##  3 Learning in sponsored search auctions

In this section, we formulate the learning problem in repeated sponsored
search auctions, with discussions on various assumptions. Subsequently, we
describe our approach from a methodological perspective.

###  3.1 Problem setup

#### Online advertising

The user journey starts in a search engine with a keywords query. The search
engine analyses the query and presents the user with a selection of
advertisements for products by different bidders. From the bidder’s
perspective, it means presenting a large number of products to a large amount
of customers simultaneously. The corresponding bidding model is developed in
steps of increasing complexity to simplify the exposition.

#### Single item single auction per iteration

We start with a single auction per iteration first. In this situation, the
bidder bids sequentially on one product. We focus on a single bidder in a
large population of bidders during a time horizon of $T$, where $T$ is unknown
and possibly infinite. At the beginning of each iteration $t$, $t=1,2,...,T$,
the bidder has a value $v_{t}\in\mathbb{R}$ per unit of a good and, based on
the past observations, submits a bid $b_{t}\in B$, where $B$ is a finite set
of bids (will be specified later). The outcome of the auction is as follows:
if $x_{t}(b_{t})=1$ (click occurred), the bidder gets a good and pays
$p_{t}(b_{t})$; if $x_{t}(b_{t})=0$ (no click occurred) the bidder does not
get the good and pays nothing. Consequently, the instantaneous profitability
of the bidder is

$r(b_{t},v_{t};p_{t},x_{t})=(v_{t}-p_{t}(b_{t}))x_{t}(b_{t}).$ (1)

In general, the allocation function $x_{t}(\cdot)$ and the payment function
$p_{t}(\cdot)$ depend on the underlying auction mechanism as well as the bid
profile of other bidders, and for formulating the problem from an auction
perspective should take these dependencies into account. However, as we
mentioned in Section 1.2, Google Ads does not explicitly specify what kind of
auction mechanism is being used in reality, nor does it provide the auctions
contexts to the bidder (numbers of bidders, winning bids, etc.). Therefore, we
take an online learning perspective and formulate the problem as stated in
(1), assuming that the bidder gets to observe $b_{t},v_{t},p_{t}(b_{t}),$ and
$x_{t}(b_{t})$ if auction $t$ is won; and observes only $b_{t}$ is auction $t$
is lost. Note that $v_{t}$ is unknown to the bidder before auction $t$ starts
and is only revealed if the auction is won.

The goal of the bidder, therefore, is to maximize the total profitability:

$\max_{b_{t}\in B}\sum_{t=1}^{T}r(b_{t},v_{t};p_{t},x_{t}).$ (2)

In real life, additional subtleties arise. Further, we describe practical
nuances in more detail, gradually complicating the setting and, after all,
reaching the real-life formulation that we address in this paper.

#### Single item multiple auctions per iteration

First, the sponsored search engine runs multiple auctions per iteration, and
only aggregated information is available to the bidder. Formally, every
iteration $t$ is associated with a set of reward contests $I_{t}$. The bidder
picks a bid $b_{t}$, which is used at all reward contests. 222Note, changing a
bid within the reward contest $I_{t}$ would not make any sense, as the bidder
does not have access to granular information about every single auction. At
the end of iteration $t$, the bidder observes aggregated values of gain
$\sum_{\tau\in I_{t}}v_{\tau}x_{\tau}(b_{t})$, payment $\sum_{\tau\in
I_{t}}p_{\tau}(b_{t})x_{\tau}(b_{t})$, and click-through-rate $\frac{1}{\lvert
I_{t}\rvert}\sum_{\tau\in I_{t}}x_{\tau}(b_{t})$ in the reward contest
$I_{t}$. Since only aggregated information is revealed to the bidder, this
makes learning in the multiple auctions per iteration setting more complex.

We denote $v^{\prime}_{t}=\sum_{\tau\in I_{t}}v_{\tau}x_{\tau}(b_{t})$,
$p^{\prime}_{t}(b_{t})=\sum_{\tau\in I_{t}}p_{\tau}(b_{t})x_{\tau}(b_{t})$ and
define the instantaneous aggregated profitability as follows:

$r(b_{t},v^{\prime}_{t};p^{\prime}_{t})=\sum_{\tau\in
I_{t}}\left(v_{\tau}-p_{\tau}(b_{t})\right)x_{\tau}(b_{t})=v^{\prime}_{t}-p^{\prime}_{t}(b_{t}),$

and the bidder’s goal becomes to maximize the total aggregated profitability

$\max_{b_{t}\in B}\sum_{t=1}^{T}r(b_{t},v^{\prime}_{t};p^{\prime}_{t}).$ (3)

Since we are solely working with aggregated data, we omit ′ and write $v_{t}$
and $p_{t}(b_{t})$ instead of $v^{\prime}_{t}$ and $p^{\prime}_{t}(b_{t})$.

######  Remark 1.

$\lvert I_{t}\rvert$ is a random variable which distribution is unknown to the
learner. Moreover, different allocation and payment functions might be used
for different auctions, i.e., $x_{\tau}(\cdot)$ and $p_{\tau}(\cdot)$ depend
on $\tau$ as opposed to [9].

#### Single item multiple auctions per iteration under delayed batched
feedback

Next, due to the complex reward definition, the bidder does not observe the
outcome of bid $b_{t}$ immediately after reward contest $I_{t}$ ends. Instead,
the outcomes are batched in groups and observed after some delay. To define it
formally, we borrow notations from [31]. Let $\mathcal{T}=t_{1},...,t_{M}$ be
a grid of integers such that $1<t_{1}<...<t_{M}=T$. It defines a partition
$\mathcal{S}=\\{S_{1},...,S_{M}\\}$ where $S_{1}=[1:t_{1}]$ and
$S_{k}=(t_{k-1},t_{k}]$ for $k\in[2:M]$. The set $S_{k}$ is the $k$-th batch.
Next, for each $t\in[T]$, let $J(t)\in M$ be the index of the current batch
$S_{J(t)}$. Then, for each $t\in S_{J(t)}$, the bidder observes the outcome of
reward contest $I_{t}$ only after batch $S_{J(t)+\Delta}$ ends, for some
positive integer $\Delta$.

Although the bidder’s goal (3) remains unchanged in the batched feedback
setting, we emphasize that the complexity of the problem increases greatly, as
the decision at round $t$ can only depend on observations from $\Delta$
batches ago. In fact, [11] shows that, in the worst case, the performance of
the batch learning deteriorates linearly in the batch size for stochastic
linear bandits.

#### Multiple items multiple auctions per iteration under batched feedback

Finally, bidders are rarely presented with a single item, and in real life,
they strive to optimize bids for multiple items simultaneously. Let
$\mathcal{C}$ be a finite set of possible contexts. Every iteration $t$ is
associated with a unique set of contexts $C_{t}\in\mathcal{C}$. Given $C_{t}$,
the bidder selects a vector of bids $\textit{{b}}_{t}\in B^{\lvert
C_{t}\rvert}$, one for each context, and observes vectors of aggregated values
$\textit{{v}}_{t}$ and $p_{t}(\textit{{b}}_{t})$, where $p_{t}$ is vector
functions from $\mathbb{R}^{\lvert C_{t}\rvert}$ to $\mathbb{R}^{\lvert
C_{t}\rvert}$. The instantaneous profitability, in this case, is defined as
the inner product between the vector of profits
$\textit{{v}}_{t}-p_{t}(\textit{{b}}_{t})$ and vector of ones 1:

$\displaystyle
r(\textit{{b}}_{t},\textit{{v}}_{t};p_{t})=\left\langle\textit{{v}}_{t}-p_{t}(\textit{{b}}_{t}),\textbf{1}\right\rangle.$
(4)

and the goal becomes to maximize the total profitability for multiple items

$\max_{\textit{{b}}_{t}\in B^{\lvert
C_{t}\rvert}}\sum_{t=1}^{T}r(\textit{{b}}_{t},\textit{{v}}_{t};p_{t}).$ (5)

The instantaneous profitability (4) and the goal (5) correspond to the most
general setting of learning in sponsored search auction when the bidder aims
to optimize bids for multiple items simultaneously under the batched feedback.
This is the problem that we are addressing in this paper.

#### Assumptions

######  Assumption 1 (Independence of goods at sale).

A set of possible contexts is represented by $n$ unit vectors,
$C_{t}=\\{e_{1},...,e_{n}\\}$ for every $t=1,...,T$.

Such context set definition corresponds to the situation when the bidder is
presented with $n$ items to bid for, and the bidder treats these items
independently from each other. In this case, we can consider $n$ instances of
the learner, each solving a single-item problem (3).

Alternatively, [7] and [30] propose to use valuation $v_{t}$ or its estimate
as a context. However, we consider a stricter setting, assuming that $v_{t}$
is unknown for the bidder, nor data is available for its estimation.
Nevertheless, we emphasize that Assumption 1 is not critical, as a simple
partition of private valuations $v_{t}$ to groups and considering separate
instances for each group reduces to our approach. We will discuss it further
in Section 6.

######  Assumption 2 (Fixed batch size and delay).

Grid $\mathcal{T}$ divides the horizon $T$ in equal partitions, i.e., for all
$S_{k}$ in $\mathcal{S}$, $\lvert S_{k}\rvert=q$, for some positive integer
$q$, and delay $\Delta$ is fixed for all rounds. Moreover, values of $q$ and
$\Delta$ are known to the bidder in advance.

Although restrictive from the problem formulation perspective, the batch size
and delay are controlled by our bidding system and can be wholly justified in
practice (see Section 4). Moreover, our algorithm, which we introduce in
Section 3.3, is adaptable to unknown and random batch sizes and delays.

###  3.2 Bandit formulation

We formalize the goal (3) using the adversarial bandits setting and assume
that the bidder (learner) is presented with a discrete set of bids (actions)
$B$. At each auction (round) $t$, the learner picks an action $b_{t}$ and the
adversary constructs reward $r_{t}$ by secretly choosing reward components
$v_{\tau}$, payment functions $p_{\tau}(\cdot)$, and allocation functions
$x_{\tau}(\cdot)$, which is further observed by the learner. 333In the
subsequent sections, we will use pairs bidder-learner, bid-action, and
outcome-reward interchangeably, depending on the context.

The advantage of the adversarial setting is that it avoids imposing any
assumptions on the reward components (except that $r_{t}\in[0,1]$), which is
perfectly combined with the black-box nature of Google Ads sponsored search
auctions. Moreover, as we mentioned in Section 2, the adversarial setting
allows accounting for the untruthfulness of the underlying auction mechanism.

######  Remark 2.

Note, restricting the bid space to a discrete set $B$ is justified as in
Google Ads, the bids are integer numbers of cents and take values between
0.01$ and 2$ [32].

The bandit formulation, therefore, accounts for Blackbox auction mechanism and
Unknown valuation of the goods at sale challenges.

###  3.3 Algorithm

We introduce an adaptation of the EXP3 algorithm to the batch setting, which
we call Batch EXP3. Batch EXP3 enables strong theoretical guarantees by
building on top of the basic algorithm and extensions to more complex settings
with batched and delayed feedback. Specifically, Batch EXP3 maintains $n$
instances of the learner, each instance for a separate item, and performs
$\Delta$-steps delayed update at the end of each batch. Importantly, the
update mechanism of Batch EXP3 preserves the importance-weighted unbiased
estimator of rewards, thus, making our adaptation resilient to Batch update
and Measurement challenges. Algorithm 1 formalizes the description above.

#### Theoretical guarantees

Theoretical guarantees of the Batch EXP3 algorithm follow from a classical
analysis of the EXP3 algorithm (see, e.g., [2]). For completeness and
theoretical rigor, we formulate a separate statement on Batch EXP3 theoretical
performance. In order to do that, we start with the definition of the
theoretical success metric called regret. Regret is the difference between the
learner’s total reward and reward obtained by any fixed vector of bids in
hindsight:

$\textstyle R(T,n)=\sup_{\textit{{b}}\in
B^{n}}\mathbb{E}\left[\sum_{t=1}^{T}\left(r_{t}(\textit{{b}},\textit{{v}}_{t};p_{t})-r_{t}(\textit{{b}}_{t},\textit{{v}}_{t};p_{t})\right)\right].$

######  Theorem 3 (Regret of Batch EXP3).

The regret of the Batch EXP3 algorithm with the learning rate
$\sqrt{\frac{\log\lvert B\rvert}{T\lvert B\rvert}}$ is:
$\mathcal{O}\left(n\sqrt{qT\lvert B\rvert\log\lvert B\rvert}+n\Delta\right)$.

Algorithm 1 Batch EXP3 algorithm for learning in sponsored search auctions

1:bid set $B$, learning rate $\eta$, number of items $n$, grid $\mathcal{T}$,
delay $\Delta$

2:Set $X^{j}_{0,i}=0$ for all $i\in[B]$ and $j\in[n]$

3:Set $t\leftarrow 1$

4:for $t=1,2,\dots$ do

5: (Policy update) Calculate the sampling distributions
$\pi_{t}=(\pi^{j}_{t})_{j=1}^{n}$:  $\pi^{j}_{t}(b_{i})=\frac{\exp{(\eta
X^{j}_{t-1,i})}}{\sum_{l\in[B]}\exp{(\eta X^{j}_{t-1,l})}}$

6: (Bid generation) Sample $\textit{{b}}_{t}\sim\pi_{t}(\cdot)$

7: $X^{j}_{t,i}\leftarrow X^{j}_{t-1,i}$

8: if $t\in\mathcal{T}$ and $J(t)>\Delta$ then

9: for $s\in S_{J(t)-\Delta}$ do

10: Observe $\textit{{v}}_{s},p_{s}(\textit{{b}}_{s})$

11: Calculate
$r(\textit{{b}}_{s})=\langle\textit{{v}}_{s}-p_{s}(\textit{{b}}_{s}),\textbf{1}\rangle$

12: Calculate $X^{j}_{t,i}$:
$X^{j}_{t,i}=X^{j}_{t,i}+1-\frac{\mathbb{I}\\{b^{j}_{s}=b_{i}\\}(1-r^{j}(\textit{{b}}_{s}))}{\pi^{j}_{t}(b_{i})}$
(6)

13: $t\leftarrow t+1$

###### Proof.

We start analyzing regret for $n=1$, $R(T,1)$:

$\displaystyle R(T,1)$ $\displaystyle=\sup_{b\in
B}\mathbb{E}\left[\sum_{t=1}^{T}\left(r(b,v_{t};p_{t})-r(b_{t},v_{t};p_{t})\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{b\in
B}\mathbb{E}\left[\sum_{k=1}^{M}\sum_{t\in
S_{k}}\left(r(b,v_{t};p_{t})-r(b_{t},v_{t};p_{t})\right)\right]+\Delta$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}q\sup_{b\in
B}\mathbb{E}\left[\sum_{k=1}^{M}\left(r(b,v_{t};p_{t})-r(b_{t},v_{t};p_{t})\right)\right]+\Delta$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2q\sqrt{M\lvert
B\rvert\log\lvert B\rvert}+\Delta=2\sqrt{qT\lvert B\rvert\log\lvert
B\rvert}+\Delta,$

where $(a)$ is due to batch execution of Batch EXP3 and the fact that the
first $\Delta$ steps no update is happening, $(b)$ is because of Assumption 2,
and $(c)$ follows from standard analysis of EXP3. Then, summing $R(T,1)$ over
$n$ gives $\mathcal{O}\left(n\sqrt{qT\lvert B\rvert\log\lvert
B\rvert}+n\Delta\right)$. ∎

##  4 Deployment

While our RL methodology accounts for Blackbox auction mechanism, Unknown
valuation of the goods at sale, Batch update, and Measurement challenges, it
takes system support to fully address Clicks attribution and the data
collection issues caused by Batched and Delayed feedback. For example,
Algorithm 1 simply assumes $\textit{{v}},p(\textit{{b}})$ data is correctly
provided as input, but this is nontrivial in practice.

To provide a systematic solution that explicitly optimizes bids for maximum
profitability, we fill these gaps on the deployment side. Subsequently, we
describe the live test design for our bidding system.

###  4.1 Bidding system architecture

#### Clicks attribution

It is rarely the case when a single click leads to a desired outcome. Usually,
a customer journey starts with a single click, but it is a chain of clicks
that results in a conversion event. Identifying click chains and attributing
credit to a single click in each click chain is a complex independent task
that requires great engineering efforts. At Zalando, the performance
measurement pipeline takes up these challenges and measures the performance of
online marketing at scale. In short, the pipeline sources all marketing
clicks, sales, as well as more complex conversion events such as customer
acquisitions, and creates the customers’ journeys across all their devices,
from first ad interaction to conversion. Then, an attribution module comes
into play and determines how much incremental value was created by every ad
click by iterating many different attribution models. We refer the interested
reader to [33] for more details.

#### Bidding system architecture

Our solution is designed to match the modularity of the RL methodology in an
efficient way, including the bid generation and policy update components and
the performance measurement pipeline. The bidding system contains two streams:
the first stream is responsible for bid placement in Google Ads; the second
stream unifies the performance measurement pipeline and the policy update
component.

Ideally, both streams are to be synchronized and run as frequently as
possible, one right after the other. However, the performance measurement
pipeline is subject to daily execution due to its compoundness and complexity,
making any attempt to increase the frequency of the second stream meaningless.
Keeping the same frequency for the first stream would admit placing one bid a
day, which slows down the learning process considerably.

To account for this limitation, we desynchronize two streams and execute the
first stream with a higher frequency, updating bids every 3 hours. Such
improvement allowed us to speed up the learning process substantially.
Therefore, the first stream runs every 3 hours and samples bids from the
latest policy (3-hour time period corresponds to round $t$), while the second
stream is subject to daily execution and performs an update based on batched
feedback (scheduled by grid $\mathcal{T}$). 444The first stream is scheduled
at midnight, 3am, 6am, etc. The second stream runs at midnight. The
architecture is illustrated in Figure 1.

Figure 1: Bidding system architecture

###  4.2 Live test design and unfolding

#### Test scope

The test took place from December 16th, 2022 (date of deployment) to January
29th, 2023, in a large European country. A list of 180 ($n=180$) clothing
products was selected to be steered by the bandits algorithm. Because of the
data sparsity, we chose to focus for this test on products for which the
traffic was deemed high enough. The selection criterion was that they should
meet a threshold of ten average daily clicks over a period of six months. The
products selected for the test were randomly sampled amongst those satisfying
this traffic threshold.

#### Profit metric

In Section 3, we defined the reward as the aggregated difference between the
valuation $v_{t}$ and costs $p_{t}$. While costs $p_{t}$ causes no problems
and correspond to the expenditure during the round $t$ (which is (almost)
immediately available to the bidder), the valuation $v_{t}$ is abstract and
requires special attention.

We assumed that the valuation $v_{t}$ is unknown to the bidder before auction
$t$ starts. In fact, it is difficult to evaluate $v_{t}$ even when auction $t$
is over. Typically, the ground truth of valuation $v_{t}$ is assumed to be the
gain auction $t$ has generated over $d$ days, where $d$ might correspond to
several months due to return and cancellation policies. Therefore, it is
impractical to learn a bidding system when $d$ is too big.

Although a vast literature on bandits with delayed feedback provides solutions
with delay-corrected estimations, these solutions are not infallible and
cannot completely eliminate delay. Therefore, there are primarily two
practical ways of dealing with delays: shortening the feedback loop by
decreasing $d$ or developing a delay-free method by substituting $v_{t}$ with
some approximation. Due to the lack of historical data, we have taken a more
pragmatic approach and shortened the delay to 2 days (we will discuss this
further in Section 6). As a result, we focus on maximizing the 2 days partial
profit, i.e., profit attributed within 2 days conversion window after the bid
placement.

#### Profit metric normalization

We apply two normalization steps to the 2 days partial profit. The first
normalization step is a naive yet pragmatic way of incorporating side
information into the modeling, and it eliminates the difference between time
periods. Since users’ activity is different during the nighttime and daytime,
rewards that we observe from 3am - 6am are incomparable to rewards that we
observe from 3pm - 6pm. We reduce rewards to a common medium of expression by
normalization:

$r(b_{t},v_{t};p_{t})\coloneqq\alpha_{t-qS_{J(t)}}r(b_{t},v_{t};p_{t}),$

where $t-qS_{J(t)}$ is the time period number within the batch $S_{J(t)}$, and
$\alpha_{l}$ is the ratio of average traffic during time period $l$ to the
average traffic of the most active time period, $l=1,\dots,q$.

Next, the bandit formulation requires rewards to be in the $[0,1]$ range,
which is far from the truth in a real-life application. In order to account
for that, we apply minimax normalization to rewards by

$r(b_{t},v_{t};p_{t})\coloneqq\frac{r(b_{t},v_{t};p_{t})-r_{min}}{r_{max}-r_{min}},$

where $r_{min}$ and $r_{max}$ are the 5-th and 95-th quantities of the
historical 2 days partial profit.

The coefficients $\alpha_{l}$ were calculated on the market level and remain
constant for all products $i=1,\dots,n$; whereas the coefficients $r_{min}$
and $r_{max}$ are product-dependent and were calculated individually for each
product.

#### Bid space

The bandit formulation described in Section 3.2 supports a discrete and finite
set of bids. The conducted analysis of historical data demonstrated that bids
higher than 40 cents are unprofitable, which, due to Remark 2, narrows the
potential bid space values to range from 1 cent to 40 cents. To trade off the
total number of bids and coverage of the bid space, we decided to include more
options for lower bids (with step 2 cents) and fewer options for higher bids
(with steps 3-5 cents). The final bid space $B$ consists of 14 possible bids
and is

$B=\left\\{1,\,3,\,5,\,7,\,9,\,11,\,13,\,15,\,17,\,20,\,25,\,30,\,35,\,40\right\\}.$
(7)

#### Test reset

We started the experiment with a generic value of the learning rate $\eta=1$.
After we rolled out the solution, we spotted unstable learning behavior in the
bidding system. On December 30, we decided to reset the test with the learning
rate $\eta=0.1$, which corresponds to less aggressive exploitation by the
learner. While this adjustment did not resolve the issue completely, it
mitigated the level of instability and facilitated the learning process. We
will detail this phenomenon in the next section.

##  5 Evaluation

Figure 2: Dynamics of the 2 days partial profit (top), gain (middle), and
costs (bottom) summarized over 180 products.

#### Profitability behavior

Figure 2 presents the 2 days partial profit (top), gain (middle), and costs
(bottom) dynamics over 180 products during the test period. To protect
business-sensitive information, we have concealed the $y$ axis and only report
the relative behavior. As of January 5, we can see a strong upward trend of 2
days partial profit, which suggests the bandit bidding system indeed increases
the total profitability. Taking a closer look at the reward components, see
Figure 2, we see that both total gain and costs are decreasing, but overall
the decrease in costs covers the decrease in gain, which allows profitability
to grow.

While it is consistent with the logic at the global level, it is necessary to
explain how profitability is increasing at the product level. Two mechanisms
are available to increase profits: selecting bids to increase gains and
selecting bids to decrease costs. These mechanisms can either complement each
other or compete with each other. In order to understand the mechanism by
which the profitability is increasing at the product level, a more thorough
analysis is required to identify the products which are driving cost reduction
while maintaining a sufficiently high level of gain.

###  5.1 Detailed analysis

Figure 3: Slopes of linear functions fitted to cost behavior (left) and gain
behavior (right) between January 5 and January 29 among three groups:
profitable products (blue), unprofitable products (green), and low-traffic
products (red).

First, we concentrate on products with high traffic by removing 60 products
(33%) with a low number of clicks (we will revisit low-traffic products
later). Further, we split high-traffic products into a profitable sample and
an unprofitable sample. The profitable sample is a group of 23 products (13%)
with the highest gain-to-cost ratio. The unprofitable sample is the rest high-
traffic product which numbered 97 products (54%). Table 1 presents statistics
for each group.

Figure 3 demonstrates this split and outlines the mechanisms by which the
algorithm increases profitability. Specifically, it shows that the costs of
the profitable sample decrease faster than the costs of the unprofitable
sample. Simultaneously, the gains for the profitable sample decrease slower
than the gain of the unprofitable sample. In other words, the algorithm is
driving the increasing profitability by spending the budget more efficiently
for the profitable sample, while, for the unprofitable sample, it is just
decreasing costs. To support this even stronger, we provide individual
examples of both profitable and unprofitable samples.

Table 1: Percentage of clicks, costs, and gain partitioned by product groups Product group | % products | % clicks | % costs | % gain
---|---|---|---|---
profitable | 12.8% | 51.3% | 45.7% | 57.1%
unprofitable | 53.9% | 41.6% | 46.9% | 34.8%
low-traffic | 33.3% | 7.4% | 7.4% | 8.1%

#### High-traffic products: profitable sample

(a) Example of profitable product 1.

(b) Example of profitable product 2.

(c) Example of profitable product 3.

Figure 4: Profitable sample behavior. Left: The profit heatmap shows the
average profit for each (bid value, day) - pair for 3 products (4(a), 4(b),
4(c)) from the profitable sample. The $y$-axis represents bid numbers (lower
bid number corresponds to lower bid value), and the $x$-axis represents day
numbers (starting from December 30). The color bar is normalized between
$[1,-1]$ to hide the actual profitability. Right: The bid placement heatmap
shows the number of times bids were placed for each (bid value, day) - pair
for 3 products (4(a), 4(b), 4(c)) from the profitable sample. The $y$-axis
represents bid numbers (lower bid number corresponds to lower bid value), and
the $x$-axis represents day numbers (starting from December 30). Since there
are 8 3-hour periods in a day, maximum value in each cell is 8.

Figure 4 illustrates individual behavior of profit and bid placement for 3
different products. We can clearly see that policies concentrate around the
optimal bid value exploring other options from time to time. These examples
demonstrate a meaningful learning behavior by spending the budget more
efficiently and optimizing bids for maximum profitability.

#### High-traffic products: unprofitable sample

Figure 5: Unprofitable sample behavior. The profit heatmap (left) and bids
placement heatmap (right) across the bid numbers (y-axis) and day numbers
(x-axis) starting from December 30 aggregated over 97 products from the
unprofitable sample. The left color bar is normalized between $[1,-1]$ to hide
the actual profitability. Lower bid number corresponds to lower bid value.

Unlike the profitable sample, products from the unprofitable sample follow the
same pattern, and it is easier to visualize them on an aggregated level.
Figure 5 shows the profit (left) and the bids placement (right) heatmaps
aggregated over 97 products from the unprofitable sample. We can see that the
aggregated policy strongly concentrates around lower bid values due to the
high unprofitability of the higher bid values. While this is a desired
behavior, this shift to lower bid values does not seem to be as profitable as
in the example before, suggesting that this sample contributes to increasing
profitability mostly due to the lowering costs.

#### Low traffic products

Figure 6: Low-traffic behavior. The profit heatmap (left) and bids placement
heatmap (right) across the bid numbers (y-axis) and day numbers (x-axis)
starting from December 30 aggregated over 60 low-traffic products. The left
color bar is normalized between $[1,-1]$ to hide the actual profitability.
Lower bid number corresponds to lower bid value.

Lastly, we return to the low-traffic products, which include 60 products (33%)
with the lowest number of clicks in January. Heatmaps for the low-traffic
group (Figure 6) illustrate similar behavior to what we saw in the
unprofitable sample behavior. Nevertheless, we emphasize that the low-traffic
products have very little data, which might suggest that, due to the low
exploration, the algorithm switched to lower bid values a little bit early and
could have given more chance to high bid values in this case. This group
requires fine-tuning of the hyperparameters and further monitoring.

###  5.2 Example of counterintuitive behavior

One product from the profitable sample demonstrates counterintuitive behavior,
which deserves special attention. As we can see in Figure 7, after starting
with lower bid values, it switched to higher bid values on days 5-6.
Intuitively, we would expect the policy to switch back after it verifies that
higher bid values performing worse, but this is not happening. Instead, it
chooses an unprofitable bid more intensively, and things get even worse.

The answer to this behavior lies in the update rule (6). According to (6), the
incremental score gain at round $t$

$X_{t,i}-X_{t-1,i}=1-\frac{\mathbb{I}\\{b_{t}=b_{i}\\}(1-r(b_{t}))}{\pi_{t}(b_{i})}$
(8)

is equal to 1 for bids that were not placed to encourage exploration and is
equal to $1-\frac{(1-r(b_{t}))}{\pi_{t}(b_{i})}$ for a placed bid to punish
bids for poor performance. The latter is a loss-driven mechanism that might
take values in $(-\infty,1]$ depending on the values of $r(b_{t})$ and
$\pi_{t}(b_{i})$. There are two intermediate conclusions can be made: (1) due
to the loss-driven approach, bids that were not placed in a round never get
punished more than the bid that was placed in that round, no matter how well
it performed, and (2) due to importance-weighted sampling, bids with low
probabilities experience more severe punishment than bids with high
probabilities for providing the same reward value.

Both these observations are theoretically reasonable. However, in combination
with Reward sparsity, it led to a snowballing effect of being unreasonably
confident in bids that did not happen to be placed at the very beginning.
Indeed, because of observation 1, higher bid values (that the model didn’t
place for the first 5-6 days) appeared more appealing as other bids
experienced some punishment. Next, because of observation 2, the higher bids
were flourishing, perhaps even producing worse outcomes, as other bids had a
lower probability.

Although theoretically the system will eventually recover from such behavior,
it highlights the risk associated with the algorithm in environments with
sparse rewards due to the sensitivity of the learning behavior. At the
beginning of the live test, the learning rate parameter was misspecified with
respect to reward sparsity. This led to a high sensitivity of the learning
system, such that omitting placing a bid for 1-2 days resulted in a massive
degeneration of policies. That was the reason for the test reset and the
learning rate decrease.

Figure 7: Counterintuitive behavior. The profit heatmap (left) and bids
placement heatmap (right) across the bid numbers (y-axis) and day numbers
(x-axis) starting from December 30 for 1 product from the profitable sample.
The left color bar is normalized between $[1,-1]$ to hide the actual
profitability. Lower bid number corresponds to lower bid value.

##  6 Discussion and further work

One challenge that our solution does not address directly relates to the
sparse reward signal. We have seen that the same reward definition led to
conceptually different behaviors for various products/groups of products,
making the system highly susceptible to imbalances between exploration and
exploitation. Moreover, the marketing nature and the blackbox auction
mechanism further complicate the problem due to the low conversion rate and
complex reward structure.

A potential solution to deal with the reward sparsity issue is to compensate
for it by exploring more aggressively. Different methods exist to achieve
this, such as decreasing the learning rate, using EXP3-IX algorithm [34], or
mixing policies with uniform distribution. However, we believe that these
remedies only mitigate the snowballing effect and do not completely solve it.
As we discussed in Sections 5.1 and 5.2, the sparse reward signal can cause
the system to exhibit trivial behavior or destabilize the system at all.

We believe the essence of the problem lies in the loss-driven update rule (6).
More precisely, in environments where the positive outcomes are gems, the
system should distinguish between punishment for losses and encouragement due
to lack of exploration. But in reality, these outcomes are taken for granted.
While this line of thought has something in common with the reward shaping
techniques, which usually require additional hand-crafted reward functions, it
is highly unclear how to extend these techniques to the auction domain.
Somewhat surprisingly, this issue remains unaddressed in the theoretical
literature, nor are practical approaches known.

Alternatively, one can overcome the reward sparsity issue by modeling the
reward signal. That is, instead of waiting for the true outcome to appear, one
could substitute it with an approximation modeled by an independent supervised
learning module, which, in its term, is trained based on the true outcome with
delay $d$. If an accurate enough approximation can be developed, this method
can mitigate two limitations of our current approach, which include a large
number of products $n$ and a long delay $d$. While the larger values of $n$
can be modeled as context using approximate valuation $v_{t}$ (as suggested in
[7, 30]), the delay $d$ should not be as critical for supervised learning as
it is for reinforcement learning. Studying how to integrate these two modules
is an interesting direction for future work.

##  7 Conclusion

In this paper, we introduced a systematic solution to learning optimal bidding
strategies in a complex auction problem. Our solution relies on the
adversarial bandit framework: to optimize the exploration-exploitation trade-
off by maintaining empirical importance-weighted rewards of the actions.
Alternatively to classical bandit algorithms that rely on immediate online
feedback, the developed Batch EXP3 is robust to batched and delayed feedback.
The theoretical appeal of our solution can be motivated by the relationship of
Batch EXP3 to the classical EXP3 algorithm. We have outlined the theoretical
guarantees of the underlying algorithm in Theorem 3.

On the deployment side, we introduced a bidding architecture that complements
the RL techniques. Although the technical infrastructure was heavy and
incorporated the non-trivial implementation of the clicks attribution
pipeline, the practical appeal of our solution is motivated by its
computational advantages: the resulting system is computationally efficient,
reliable, and debuggable. Furthermore, it can be readily applied to many more
contextual decision problems.

Our solution has demonstrated its effectiveness in increasing the partial
profit at the group level. Additionally, our system optimizes bids for maximum
profitability at the product level, particularly for a group of high-traffic
products. However, we acknowledge that finer tuning is needed for low-traffic
products. Overall, the live test has yielded promising results indicating that
many real-life challenges can be addressed pragmatically within a
reinforcement learning system.

#### Acknowledgments

We wish to thank Joshua Hendinata and Aleksandr Borisov for their engineering
support. Furthermore, we would like to thank Amin Jamalzadeh, head of the
Traffic Platform Applied Science and Analytics at Zalando, for guidance,
support with administrative processes related to the project, and the review
of the final draft. Danil Provodin would like to thank Maurits Kaptein and
Mykola Pechenizkiy, whose thoughts influenced his ideas.

## References

  * [1] Michelle Morgan.  Bid management tools, 2023.  Accessed on March 10, 2023.
  * [2] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire.  The nonstochastic multiarmed bandit problem.  SIAM Journal on Computing, 32(1):48–77, 2002.
  * [3] Google.  Auction, 2023.  Accessed on March 10, 2023.
  * [4] Google.  About ad rank, 2023.  Accessed on March 10, 2023.
  * [5] Jason D. Hartline and Tim Roughgarden.  Simple versus optimal mechanisms.  In Proceedings of the 10th ACM Conference on Electronic Commerce, EC ’09, page 225–234, New York, NY, USA, 2009. Association for Computing Machinery.
  * [6] Hu Fu, Jason Hartline, and Darrell Hoy.  Prior-independent auctions for risk-averse agents.  In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC ’13, page 471–488, New York, NY, USA, 2018. Association for Computing Machinery.
  * [7] Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman.  Optimal no-regret learning in repeated first-price auctions, 2020.
  * [8] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman.  Learning to bid optimally and efficiently in adversarial first-price auctions, 2020.
  * [9] Zhe Feng, Chara Podimata, and Vasilis Syrgkanis.  Learning to bid without knowing your value.  Proceedings of the 2018 ACM Conference on Economics and Computation, 2018.
  * [10] Claire Vernade, Olivier Cappé, and Vianney Perchet.  Stochastic bandit models for delayed conversions.  In Proceedings of the 2017 Conference on Uncertainty in Artificial Intelligence, page 1–10, 2017.
  * [11] Danil Provodin, Pratik Gajane, Mykola Pechenizkiy, and Maurits Kaptein.  The impact of batch learning in stochastic linear bandits.  In IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28 - Dec. 1, 2022, pages 1149–1154.
  * [12] Kelly Zhang, Lucas Janson, and Susan Murphy.  Inference for batched bandits.  In Advances in Neural Information Processing Systems, volume 33, pages 9818–9829, 2020.
  * [13] Roger B. Myerson.  Optimal auction design.  Mathematics of Operations Research, 6(1):58–73, 1981.
  * [14] John G. Riley and William F. Samuelson.  Optimal auctions.  The American Economic Review, 71(3):381–392, 1981.
  * [15] Robert B. Wilson.  Competitive bidding with disparate information.  Management Science, 15(7):446–448, 1969.
  * [16] Robert B. Wilson.  Game-theoretic analysis of trading processes.  1985\.
  * [17] Jonathan Weed, Vianney Perchet, and Philippe Rigollet.  Online learning in repeated auctions.  In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1562–1583, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * [18] Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour.  Regret minimization for reserve prices in second-price auctions.  IEEE Transactions on Information Theory, 61(1):549–564, 2015.
  * [19] Shuchi Chawla, Jason Hartline, and Denis Nekipelov.  Mechanism design for data science.  In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC ’14, page 711–712, New York, NY, USA, 2014. Association for Computing Machinery.
  * [20] Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth.  Online learning and profit maximization from revealed preferences.  In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, page 770–776, 2015.
  * [21] Avrim Blum, Yishay Mansour, and Jamie Morgenstern.  Learning valuation distributions from partial observations.  In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, page 798–804, 2015.
  * [22] Mehryar Mohri and Andres Munoz Medina.  Learning theory and algorithms for revenue optimization in second price auctions with reserve.  In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 262–270, Bejing, China, 22–24 Jun 2014. PMLR.
  * [23] Kareem Amin, Afshin Rostamizadeh, and Umar Syed.  Repeated contextual auctions with strategic buyers.  In Advances in Neural Information Processing Systems, volume 27, 2014.
  * [24] R. Preston McAfee.  The design of advertising exchanges.  Review of Industrial Organization, 39(3):169–185, 2011.
  * [25] Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo.  Real-time bidding by reinforcement learning in display advertising.  In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM ’17, page 661–670, New York, NY, USA, 2017. Association for Computing Machinery.
  * [26] Di Wu, Xiujun Chen, Xun Yang, Hao Wang, Qing Tan, Xiaoxun Zhang, Jian Xu, and Kun Gai.  Budget constrained bidding by model-free reinforcement learning in display advertising.  CIKM ’18, page 1443–1451, New York, NY, USA, 2018. Association for Computing Machinery.
  * [27] Mengjuan Liu, Jinyu Liu, Zhengning Hu, Yuchen Ge, and Xuyun Nie.  Bid optimization using maximum entropy reinforcement learning.  Neurocomputing, 501:529–543, 2022.
  * [28] Mengjuan Liu, Li Jiaxing, Zhengning Hu, Jinyu Liu, and Xuyun Nie.  A dynamic bidding strategy based on model-free reinforcement learning in display advertising.  IEEE Access, 8:213587–213601, 2020.
  * [29] Arthur Flajolet and Patrick Jaillet.  Real-time bidding with side information.  In Advances in Neural Information Processing Systems, volume 30, 2017.
  * [30] Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman.  Leveraging the hints: Adaptive bidding in repeated first-price auctions, 2022.
  * [31] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.  Batched bandit problems.  In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1456–1456, Paris, France, 03–06 Jul 2015. PMLR.
  * [32] Google.  Maximum cpc bid: Definition, 2023.  Accessed on March 10, 2023.
  * [33] Mathias Deschamps, Anael Quevrin, and Stefan Haase.  On the effectiveness of online marketing, 2019.  Accessed on March 20, 2023.
  * [34] Tomáš Kocák, Gergely Neu, Michal Valko, and Remi Munos.  Efficient learning by implicit exploration in bandit problems with side observations.  In Advances in Neural Information Processing Systems, volume 27, 2014.