# Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising
in Online Optimization

Liang Dai1, Kejie Lyu1, Chengcheng Zhang1, Guangming Zhao2, Zhonglin Zu1,
Liang Wang2, Bo Zheng2

###### Abstract

Guaranteed display (GD) advertising is a critical component of advertising
since it provides publishers with stable revenue and enables advertisers to
target specific audiences with guaranteed impressions. However, smooth pacing
control for online ad delivery presents a challenge due to significant budget
disparities, user arrival distribution drift, and dynamic change between
supply and demand. This paper presents robust risk-constrained pacing
(RCPacing) that utilizes Lagrangian dual multipliers to fine-tune
probabilistic throttling through monotonic mapping functions within the
percentile space of impression performance distribution. RCPacing combines
distribution drift resilience and compatibility with guaranteed allocation
mechanism, enabling us to provide near-optimal online services. We also show
that RCPacing achieves $O(\sqrt{T})$ dynamic regret where $T$ is the length of
the horizon. RCPacing’s effectiveness is validated through offline evaluations
and online A/B testing conducted on Taobao brand advertising platform.

## Introduction

According to a report by the Internet Advertising Bureau, online display
advertising generated a remarkable revenue of $63.5 billion in 2022,
demonstrating a substantial year-over-year increase of 12.0% (IAB 2023). Ad
exposures in display markets are sold through both guaranteed and non-
guaranteed (like real-time bidding or RTB) selling channels. Within the
guaranteed display (GD) selling channel, an advertiser (demand side) and
publisher (supply side) negotiate a fixed price (cost-per-mille or CPM) for ad
placement, including details such as when, where, and how the ad campaigns
will be displayed. These contractual arrangements guarantee the delivery of a
specified number of impressions that meet specific targeting criteria during a
specified period.

In addition to contractual agreements, advertisers usually expect their ad
campaigns to be delivered smoothly and steadily during the purchased period
for various reasons, including making campaign performance as good as
possible, reaching a wider audience, increasing the display ratio of the
target audience, and maintaining stable online viewership for live streaming
events. However, smooth and robust pacing control for hundreds or thousands of
GD advertisements on a brand advertising platform that deals with billions of
daily requests is a challenging task. To summarize, the main challenges are as
follows:

  * •

Significant differences among campaigns: the guaranteed daily impressions
range from thousands to millions, the targeted audience size also vary
greatly. Moreover, different campaigns have different optimization goals, such
as click-through rate (CTR) or conversion rate (CVR).

  * •

Drastic changes in traffic environment: these changes include significant
fluctuations in overall traffic, dynamic shifts in the distribution of user
arrival over time, and the impact of other campaigns going online or offline.

The existing smooth pacing techniques have primarily focused on RTB ads (Nuara
et al. 2022; Liu et al. 2020), which is incompatible with GD allocation.
Although some research has considered the smoothness or representativeness in
online optimal allocation of GD ads, it is often not optimized and evaluated
as a separate key metric. In this paper, we consider smooth pacing for GD ads
from the perspective of a publisher. Our contributions can be summarized as
follows:

  * •

We introduce a novel framework called RCPacing, which employs Lagrangian dual
multipliers to adjust probabilistic throttling based on monotonic functions
within the percentile space, allowing us to effectively manage risk and ensure
optimal ad delivery performance.

  * •

We also show that RCPacing attains regret of order $O(\sqrt{T})$ when the
length of the horizon $T$ and the initial number of resources are scaled
proportionally.

  * •

As there exists a tradeoff between smooth and optimal allocation in online
matching problems, RCPacing offers flexible control over this balance.

  * •

We implement RCPacing in our online display advertising system and conduct
extensive online/offline experimental evaluations. The results demonstrate
that RCPacing is highly effective in improving both the performance and
smoothness of online delivery for GD campaigns.

## Related Work

In the past few years, the allocation of GD advertising has received
significant attention from researchers (Wu et al. 2021; Wang et al. 2022). It
is typically modeled as an online matching problem, intending to achieve the
maximum match between impressions and contracts(Chen et al. 2012). While the
primary objective is to provide each advertiser with a predetermined number of
display opportunities, it is also necessary to consider the smoothness of
budget consumption. Some researchers include a fixed representative term in
objectives (Fang et al. 2019; Dai et al. 2023; Bharadwaj et al. 2012), which
aims to minimize the deviation between the allocation probability and its
corresponding supply-demand ratio for each contract. However, the
representative term is fixed without consideration of dynamic adjustment.

Another research direction is to achieve budget pacing through feedback
control, which can be further categorized into bid modification (Mehta et al.
2007; Zhou et al. 2021) and probabilistic throttling (Agarwal et al. 2014; Xu
et al. 2015; Lee, Jalali, and Dasdan 2013). Bid modification influences the
budget spending of an ad by adjusting its bidding price. Mehta et al. (Mehta
et al. 2007) modify the bid by multiplying it with a value that reflects the
proportion of unused budget, and the impression would be allocated to the ad
with the highest modified bid. Balseiro et al. (Balseiro, Lu, and Mirrokni
2020) and Zhou et al. (Zhou et al. 2021) utilize a dual multiplier to form a
virtual bid, which is consistently updated based on the variance between the
actual and expected budget consumption. These methods adhere to the same
principle of decreasing an ad’s bid when the budget is being spent too
rapidly. However, both the dramatic change in the bid win-rate curve and bid
landscape make it challenging to control the budget through bid modification.

On the other hand, probabilistic throttling methods decouple spending control
from bid calculation, they directly impact the participating likelihood based
on its budget consumption speed. Agarwal et al. (Agarwal et al. 2014) set a
global pass-through rate (PTR), which is decreased when the budget consumption
speed exceeds the expectation, and increased when the consumption speed falls
below. Although this method demonstrates good budget control capability, it
heavily relies on the accuracy of traffic forecasting.

To further consider performance optimization while achieving budget control,
Xu et al. (Xu et al. 2015) group requests with similar response rates (e.g.
CTR) together and share a PTR among them. When the PTRs need to be adjusted,
the average response rate of each group determines the priority of that group.
While effective in budget control, relying solely on PTR regulation is
insufficient to ensure guaranteed display for GD allocation.

## Preliminaries

### Problem Formulation

We formulate the GD allocation problem as the following optimization problem:

$\begin{split}\max_{x^{(t)}\in\mathcal{X}}\sum_{t=0}^{T-1}f_{t}(x^{(t)})=\sum_{t=0}^{T-1}{v^{(t)}}^{\top}x^{(t)}\\\
\text{s.t.}\sum_{t=0}^{T-1}x^{(t)}\leq B\end{split}$ (1)

where $x^{(t)}\in\mathcal{X}\subseteq\mathbb{R}^{M}$ is the one-hot decision
vector at time $t\in\left[1,\;T\right]$, $M$ is the total number of campaigns
and the impression arrived at time $t$ would be allocated to the $j$-th
campaign if the $j$-th component of $x^{(t)}$ is 1, $v^{(t)}\in R^{M}$ denotes
the impression quality between the impression and the campaigns,
$f_{t}\left(x^{(t)}\right)={v^{(t)}}^{\top}x^{(t)}\in\mathbb{R}$ is the
revenue obtained at time $t$, $B\in\mathbb{R}^{M}$ is the positive budget
vector which represents the campaign budgets.

Following Balseiro et al (Balseiro, Lu, and Mirrokni 2020)., we define the
offline dual problem as

$\displaystyle\min_{\alpha\geq 0}D\left(\alpha\right)$
$\displaystyle=\sum_{i=1}^{n}p_{i}f_{i}^{*}\left(\alpha\right)+\alpha^{\top}\rho$
(2)
$\displaystyle=\sum_{i=1}^{n}p_{i}\max_{x\in\mathcal{X}}\left\\{v^{(i)\top}x-\alpha^{\top}x\right\\}+\alpha^{\top}\rho$

where
$f_{i}^{*}\left(\alpha\right):=\max_{x\in\mathcal{X}}\left\\{f_{i}\left(x\right)-\alpha^{\top}x\right\\}$
is the conjugate function of $f_{i}\left(x\right)$ (restricted in
$\mathcal{X}$ ), $p_{i}$ is the probability that the $i\text{-th}$ impression
has a quality vector of $v^{(i)}$ , n is the total number of impressions,
$\rho=B/T$ is the average budget for each time period, $\alpha$ is the dual
variable, and the $j$-th element of $\alpha$ (denoted as $\alpha_{j}$ )
reflects the additional revenue generated by allowing one unit of resources to
be added to the $j$-th campaign’s budget.

### Dual Mirror Descent Algorithm

Our method is built upon the Dual Mirror Descent (DMD) algorithm (Balseiro,
Lu, and Mirrokni 2020), which addresses the general online allocation problem
with budget constraint. At time $t$, DMD filters out campaigns that have
exhausted their budget and assigns the request to the campaign that offers the
highest premium among the remaining campaigns (equation 3). The dual variable
is then updated according to the online mirror descent (equation 6). More
details about DMD is given in Algorithm 1.

Algorithm 1 Dual Mirror Descent Algorithm

0: Time period $T$, remaining resources $B^{(0)}=T\rho$, reference function
$h\left(\cdot\right):\mathbb{R}^{M}\rightarrow\mathbb{R}$, and step-size
$\eta$.

1: $\alpha^{(0)}=0$

2: for $t=0$ to $T-1$ do

3: Receive $v^{(t)}\sim\mathcal{P}$

4: Make the decision $\tilde{x}^{(t)}$ and update the remaining resources
$B^{(t+1)}$, where  $\tilde{x}_{j}^{(t)}=\left\\{\begin{aligned} 1,&\;\text{if
}j=\mathop{\arg\max}\limits_{B_{j}^{(t)}\geq
1}\left\\{v_{j}^{(t)}-\alpha_{j}^{(t)}\right\\}\\\ 0,&\;\text{otherwise.}\\\
\end{aligned}\right.$ (3) $B^{(t+1)}=B^{(t)}-x^{(t)}$ (4)

5: Obtain a stochastic sub-gradient of $D\left(\alpha^{(t)}\right)$
$\tilde{g}^{(t)}:=-\tilde{x}^{(t)}+\rho$ (5)

6: Update the dual variable by mirror descent
$\displaystyle\alpha^{(t+1)}=\mathop{\arg\min}\limits_{\alpha\geq
0}\left<\tilde{g}^{(t)},\alpha\right>+\frac{1}{\eta}V_{h}\left(\alpha,\alpha^{(t)}\right)$
(6) $\displaystyle\text{where
}V_{h}\left(\alpha,\alpha^{(t)}\right)=h\left(\alpha\right)-h\left(\alpha^{(t)}\right)-$
$\displaystyle\left<\nabla h\left(\alpha\right),\alpha-\alpha^{(t)}\right>$

7: end for

## Motivation

### Assumptions

In this paper, we adopt the following assumptions:

  * •

The small bids assumption. Each impression has only one slot available for
displaying ads, which is significantly lower than the demand for campaigns and
the supply of publishers (Mehta 2012).

  * •

The known IID assumption. The known Independent and Identically Distributed
(IID) assumption implies that impressions arrive online according to a known
probability distribution with repetition (Huang and Shu 2021), which is a
realistic assumption in our problem.

### Motivation

Upon receiving a user’s online request, the ad engine retrieves GD campaigns
with recall rate (RR) that meet the targeting criteria and employs real-time
prediction models such as deep neural networks (DNN) to estimate performance
scores for each campaign (Zhou et al. 2019; Gao et al. 2021). The decision-
maker then determines whether and which campaign to display based on the
scores. The detailed processing flow is illustrated in figure1. The campaign
$j$ passes the pacing control module with the pass-through rate (PTR) before
the calculation of the “price premium”. It will only win out if it has the
highest positive price compared to all other campaigns. The positive ratio of
price and the win-out ratio are referred to as the participation ratio (PR)
and win rate (WR). Without loss of generality, we use CTR as performance score
in the following paragraph. The cost for campaign $j$ can be denoted as:

$\mathbb{E}\left[Cost_{j}\right]=\mathbb{E}\left[RR_{j}\right]\sum
PTR_{j}PR_{j}WR_{j}$ (7)

Figure 1: Online process for GD campaign $j$.

It is worth noting that the primary risk GD campaigns is over-spend of the
budget because it is irreversible once the budget is over-spent. Apart from
PTR, the delivery of GD campaign is primarily determined by PR and WR. Let’s
consider two GD campaigns Ad1 and Ad2, with identical impression budgets,
performance distributions, and similar competitive environments, but with
different supply amounts (Ad1 $>$ Ad2). When the online allocation reaches a
stable state, the dual variable of Ad1 is located at a higher percentile than
Ad2 in performance distribution.

  * •

Risk analysis under stable conditions: A higher percentile indicates a greater
potential available traffic for Ad1, which makes it more vulnerable to over-
spending. Moreover, Ad1 is more challenging to initialize dual variables
because a higher percentile implies higher uncertainty especially before the
start of delivery.

  * •

Risk analysis under dynamic conditions: Higher percentile results in a smaller
bid price, making the campaign more susceptible to over-acceleration if other
campaigns suddenly go offline. Moreover, as shown in the figure 2, the PR of
Ad1 generates greater fluctuations if the dual variable shifts the same
distance, and is more sensitive to distribution drift in user arrival or
switching of online prediction models, which can be deduced by the proof of
Theorem 2 and Theorem 3 in appendix.

Figure 2: Different changes of PR when adjusting for dual variables or
distribution drift with the same magnitude.

Based on the above risk analysis, RCPacing is designed to adjust the dual
variables in the dual percentile space, while constraining dual variables
within the low-risk region through the pacing module using probabilistic
throttling method.

## Risk-Constrained Pacing Algorithm

The factor dependency of RCPacing is illustrated in figure 3. The dual
variables and PTRs are adjusted in the dual percentile space of performance
distributions. These two factors jointly determine the final win-out of each
request. Although RCPacing adjusts the dual variables in percentile space
rather than dual space, the Theorem 1 in appendix shows that it attains regret
of order $O(\sqrt{T})$ when the length of the horizon $T$ and the initial
number of resources are scaled proportionally.

Figure 3: Factor dependency graph of RCPacing.

### Parametric Percentile Transformation

#### Forward Transformation

RCPacing converts the CTR into the percentile space, which is called forward
transformation, to assess the non-smooth risk and standardize the range of
dual variables. Specifically, the CTR is first subjected to statistical Box-
Cox transformation to achieve a normal shape, after which it is converted into
the percentile space using the normal cumulative distribution function
$\Phi(x)$. The parameter $\lambda_{j}^{*}$ of campaign $j$ can be estimated
from global or campaign’s historical logs using the maximum-likelihood method
(Sakia 1992):

$\lambda_{j}^{*}=\underset{\lambda_{j}}{\operatorname{argmax}}MLE\left(\lambda_{j},v_{ij}\right)$
(8)

And Box-Cox transformation can be denoted as:

$v_{ij}^{boxc}=BoxCox(\lambda_{j}^{*},v_{ij})=\begin{cases}\frac{v^{\lambda_{j}^{*}}_{ij}-1}{\lambda_{j}^{*}}&\text{
if }\lambda_{j}^{*}\neq 0\\\ \ln\left(v_{ij}\right)&\text{ if
}\lambda_{j}^{*}=0\end{cases}$ (9)

The mean $\mu_{j}$ and standard deviation $\sigma_{j}$ can be estimated:

$\mu_{j}=\mathbb{E}(v_{ij}^{boxc}),\
\sigma_{j}=\sqrt{\mathbb{E}\left[(v_{ij}^{boxc}-\mu_{j})^{2}\right]}$ (10)

To improve the robustness of drifts in the user arrival distribution, RCPacing
skews the transformation towards the middle percentile region by a factor
$\epsilon$:

$\bar{v}_{ij}=\Phi\left(\frac{BoxCox(\lambda_{j}^{*},v_{ij})-\mu_{j}}{\sigma_{j}+\epsilon\sigma_{j}}\right),where\
\epsilon\geq 0$ (11)

Figure 4: The transformation process from beta distribution to percentile
uniform distribution and the different skewness of the distribution under
different $\epsilon$.

#### Backward Transformation

RCPacing periodically updates the dual variables in the percentile space
through feedback and then performs a backward transformation of the percentile
variables $\bar{\alpha}_{j}$ into the original dual space $\alpha_{j}$ for
online service. It guarantees that RCPacing approaches the optimal solution in
the original space rather than percentile space. Here is the backward process:

$\alpha_{j}=BoxCox^{-1}\left(\lambda_{j}^{*},\mu_{j}+\Phi^{-1}(\bar{\alpha}_{j})*(\sigma_{j}+\epsilon\sigma_{j})\right)$
(12)

### Pacing Rate Factor Decoupling

The pacing rate serves multiple functions in RCPacing, including constraining
the percentile of dual variables within the safety region and addressing
unexpected environmental changes and cold-start problem. RCPacing decouples
the pacing rate into different factors to achieve optimal performance, for the
campaign $j$ retrieved in request $i$:

$\overline{PTR}_{ij}=PTR^{base}_{j}\cdot fp\left(\bar{\alpha}_{j}\right)\cdot
fv\left(\bar{\alpha}_{j},\bar{v}_{ij}\right)$ (13)

where $PTR^{base}_{j}$ is the basic statistical PTR, $f(\cdot)$ and
$fv(\cdot)$ are the fine-tune factors. Given a safe upper bound of percentile
threshold $P_{ub}$ (such as 90%), the expected PTR can be calculated based on
its targeted audience $TA_{j}$ without considering the competition from other
campaigns:

$PTR^{exp}_{j}=\frac{B_{j}}{(1.0-P_{ub})TA_{j}}$ (14)

The initial value of $\bar{\alpha}_{j}$ can be expressed as:

$\bar{\alpha}^{(0)}_{j}=\left\\{\begin{array}[]{l}\begin{aligned}
P_{ub}&,\text{if }PTR^{exp}_{j}\leq 1\\\
1-(1-P_{ub})PTR^{exp}_{j}&,\text{otherwise.}\end{aligned}\end{array}\right.$
(15)

Given the global hyper-parameter $WR_{glb}$ (such as 0.2), the basic PTR
considering the competition of $WR$ can be expressed as:

$PTR^{base}_{j}=\min\left\\{1.0,PTR^{exp}_{j}/WR_{glb}\right\\}$ (16)

During the dynamic update in RCPacing, $PTR_{j}$ should be gradually increased
to enhance traffic supply if $\bar{\alpha}_{j}<P_{ub}$. Conversely, it should
be quickly decayed to reduce the non-smooth risk. It is illustrated in
equation 17 and figure 5:

$fp\left(\bar{\alpha}_{j}\right)=\left\\{\begin{array}[]{l}\begin{aligned}
50^{(P_{ub}-\bar{\alpha}_{j})/P_{ub}}&,\text{if }\bar{\alpha}_{j}\leq
P_{ub}\\\ 0.2^{(P_{ub}-\bar{\alpha}_{j})/(P_{ub}-1)}&,\text{
otherwise.}\end{aligned}\end{array}\right.$ (17)

Taking inspiration from smart pacing, RCPacing assigns a higher PTR to traffic
with higher performance scores. Instead of employing discrete layered pacing,
RCPacing utilizes linear functions to achieve non-uniform pacing:

$fv\left(\bar{\alpha}_{j},\bar{v}_{ij}\right)=10(\bar{v}_{ij}-\bar{\alpha}_{j})+1$
(18)

Figure 5: Functions of $fp$ and $fv$ in percentile space.

### Emergence Control and Cold Start Problem

Despite RCPacing’s adaptive adjustment of the PTR, it cannot completely
mitigate the risks of non-smooth delivery caused by unpredictable factors,
such as sharp increases in user traffic, significant distribution changes due
to the switch of online real-time prediction models, offsets caused by updates
of Box-Cox parameters, and modifications of budgets. Additionally, due to the
absence of historical logs, there is also a risk of non-smoothness during the
cold start phase. To address the these risks, RCPacing incorporates an
emergent PTR intervention module (ePTR) that can be activated in emergency
situations. The final PTR can be denoted as:

$PTR_{ij}=\min\\{1,\overline{PTR}_{ij}\\}\times ePTR_{j}$ (19)

The motivation behind ePTR is to limit the consumption speed within a certain
range when a campaign is over-accelerated while maintaining the gradient
direction of dual variables. The ratio of the actual cost to the expected cost
can represent the spending speed of campaign $j$ during period $t$:

$spd_{j}^{(t)}=\frac{Cost_{j}^{(t)}}{eCost_{j}^{(t)}}$ (20)

RCPacing uses proportional control instead of gradient methods to quickly
control the risks. Given a safe upper ratio 2.0, the update of ePTR is:

$ePTR_{j}^{(t+1)}=\min\\{1,ePTR_{j}^{(t)}*\min\\{2,\frac{2}{spd_{j}^{(t)}}\\}\\}$
(21)

An initial trial rate is usually set for each campaign at the start of
delivery to reduce the risks of the cold start problem.

### Adaptive Gradient Clipping

Stable online iterative update of dual variables is also a critical factor for
smooth delivery. However, choosing inappropriate learning rates can result in
significant fluctuations and may have a cascading effect on the overall
competitive environment. A simple and direct method is to restrict the change
range into $\hat{\alpha}$ by gradient clipping (Chen, Wu, and Hong 2020).
Given the updated dual variables $\tilde{\alpha}^{(t+1)}_{j}$, gradient
clipping can be denoted as:

$\bar{\alpha}^{(t+1)}_{j}=\max\left\\{\bar{\alpha}^{(t)}_{j}-\hat{\alpha},\min\left\\{\tilde{\alpha}^{(t+1)}_{j},\bar{\alpha}^{(t)}_{j}+\hat{\alpha}\right\\}\right\\}$
(22)

Suppose that $spd_{j}^{(t)}<1.0$ , which indicates that the campaign’s
spending is lower than expected. The feedback control method will decrease the
value of $\alpha_{j}^{(t)}$ to $\alpha_{j}^{(t+1)}$, leading to an increase in
the bid price. Assuming that the competition remains the same, which indicates
that $WR_{ij}^{(t+1)}\geq WR_{ij}^{(t)},\text{ if
}v_{ij}^{(t+1)}=v_{ij}^{(t)}$. Suppose the expected spending speed in the next
period is equal to 1, it can be deduced that:

$\displaystyle
1.0=\frac{Cost_{j}^{(t+1)}}{eCost_{j}^{(t+1)}}=\frac{Cost_{j}^{(t+1)}}{eCost_{j}^{(t)}}=spd_{j}^{(t)}\frac{Cost_{j}^{(t+1)}}{Cost_{j}^{(t)}}$
(23)
$\displaystyle=spd_{j}^{(t)}\frac{\mathbb{E}\left[RR_{j}^{(t+1)}\right]\sum
PTR_{j}^{(t+1)}PR_{j}^{(t+1)}WR_{j}^{(t+1)}}{\mathbb{E}\left[RR_{j}^{(t)}\right]\sum
PTR_{j}^{(t)}PR_{j}^{(t)}WR_{j}^{(t)}}$ $\displaystyle\geq spd_{j}^{(t)}\sum
PTR_{j}^{(t+1)}PR_{j}^{(t+1)}/\sum PTR_{j}^{(t)}PR_{j}^{(t)}$
$\displaystyle=spd_{j}^{(t)}\mathbb{E}\left[PTR_{j}^{(t+1)}PR_{j}^{(t+1)}\right]/\mathbb{E}\left[PTR_{j}^{(t)}PR_{j}^{(t)}\right]$

Without consideration the effect of $ePTR$, $PTR$ and $PR$ are determined and
have a monotonic decreasing relationship with $\bar{\alpha}$. We can calculate
the expectation using the importance sampling method in uniform percentile
space:

$\displaystyle\psi_{j}(\bar{\alpha}_{j}^{(t)})$
$\displaystyle=\mathbb{E}\left[PTR_{j}^{(t)}PR_{j}^{(t)}\right]=\int_{0}^{1}PTR_{j}^{(t)}(\bar{\alpha}_{j}^{(t)},$
(24) $\displaystyle x)\cdot PR_{j}(\bar{\alpha}_{j}^{(t)},x)\mathrm{d}x,\text{
}\ x\sim\text{uniform}(0,1)$

The lower bound of $\alpha_{j}^{(t+1)}$ can be represented as:

$\bar{\alpha}_{j}^{(t+1)}\geq\psi_{j}^{-1}\left(\psi_{j}(\bar{\alpha}_{j}^{(t)})/spd_{j}^{(t)}\right)=\psi_{j}^{-1}$
(25)

where $y=\psi_{j}^{-1}(\bar{\alpha}_{j},x)$ can be approximated through an
iterative process by solving the equation $\psi_{j}(\bar{\alpha}_{j},y)=x$
based on the bisection method illustrated in figure 6. To include
$spd_{j}^{(t)}\geq 1.0$, $\bar{\alpha}_{j}^{(t+1)}$ should satisfy the
following conditions:

$\bar{\alpha}^{(t+1)}_{j}=\left\\{\begin{array}[]{l}\begin{aligned}
\max\left\\{\tilde{\alpha}^{(t+1)}_{j},\bar{\alpha}^{(t)}_{j}-\hat{\alpha},\psi_{j}^{-1}\right\\}&,\text{
if }\tilde{g}_{j}^{(t)}\geq 0\\\
\min\left\\{\tilde{\alpha}^{(t+1)}_{j},\bar{\alpha}^{(t)}_{j}+\hat{\alpha},\psi_{j}^{-1}\right\\}&,\text{
otherwise.}\end{aligned}\end{array}\right.$ (26)

Figure 6: The areas of the color section represent the value of
$\psi_{j}(\bar{\alpha}_{j}^{(t)})$ under different variables
$\alpha_{j}^{(t)}$.

### Bregman Divergence Selection

Algorithm 1 presents the basic decision process based on Bregman divergence
with respect to a given convex reference function. It is obvious that if we
use the squared loss function and the dual update becomes:

$h(\alpha)=\alpha^{2}\Rightarrow\tilde{\alpha}^{(t+1)}_{j}=\bar{\alpha}_{j}^{(t)}-\eta\tilde{g}_{j}^{(t)},\forall
j$ (27)

However, due to the higher fluctuation of PR in the high percentile region
with the same shift, the variation magnitude of dual variables should be
smaller to minimize non-smooth risk. It means that as $\bar{\alpha}_{j}$
approaches 1.0, the $\eta$ should become smaller. We propose a modified
Itakura-Saito divergence (Banerjee et al. 2005) to achieve this objective:

$\displaystyle h(\alpha)=-ln(1.5-\alpha)\Rightarrow$ (28)
$\displaystyle\tilde{\alpha}^{(t+1)}_{j}=\bar{\alpha}^{(t)}_{j}-\frac{(1.5-\bar{\alpha}^{(t)}_{j})^{2}}{1-\eta\tilde{g}_{j}^{(t)}(1.5-\bar{\alpha}^{(t)}_{j})}\eta\tilde{g}_{j}^{(t)},\forall
j$ $\displaystyle\text{ where
}\eta\tilde{g}_{j}^{(t)}(1.5-\bar{\alpha}^{(t)}_{j})<1$

The overall processing details of RCPacing are described in Algorithm 2.

Algorithm 2 RCPacing

0: Budget of the campaigns $\boldsymbol{B}$, safe upper bound $P_{ub}$, global
win rate $WR_{glb}$, skew factor $\epsilon$, step size $\eta$, static gradient
clipping $\hat{\alpha}$, total time period $T$

1: Budget exhausted campaign set $\mathcal{G}=\emptyset$

2: Calculate $\boldsymbol{PTR}^{base}$ and $\boldsymbol{\bar{\alpha}}^{(0)}$
with eq. 14 $\sim$ 16

3: for $t=0$ to $T-1$ do

4: Estimate $\boldsymbol{\lambda}^{*}$, $\boldsymbol{\mu}$, and
$\boldsymbol{\sigma}$ from historical logs with eq. 8 $\sim$ 10

5: Obtain $\boldsymbol{\alpha}^{(t)}$ from $\boldsymbol{\bar{\alpha}}^{(t)}$
by backward transformation in eq. 12

6: Receive $\boldsymbol{v}^{(t)}$ from online requests

7: Obtain $\boldsymbol{\bar{v}}^{(t)}$ from $\boldsymbol{v}^{(t)}$ by forward
transformation in eq. 11

8: Calculate $\boldsymbol{PTR}^{(t)}$ with eq. 13 and eq. 17 $\sim$ 19

9: $\boldsymbol{bid}^{(t)}=\boldsymbol{v}^{(t)}-\boldsymbol{\alpha}^{(t)}$

10: Element-wise randomly set ${bid}^{(t)}_{ij}=0$ with probability
$1-{PTR}^{(t)}_{ij}$ and set ${bid}^{(t)}_{ij}=0$ if ${j}\in\mathcal{G}$

11:
$\boldsymbol{j}^{*}=\mathop{\arg\max}\left\\{\boldsymbol{bid}^{(t)}\right\\}$

12: Make the decision $\tilde{\boldsymbol{x}}^{(t)}$, where
$\tilde{{x}}^{(t)}_{ij}=\left\\{\begin{aligned} 1,&\;\text{if
}{bid}^{(t)}_{ij}>0\text{ and }j=\boldsymbol{j}^{*}_{i}\\\
0,&\;\text{otherwise.}\\\ \end{aligned}\right.$ (29)

13: $\boldsymbol{B}=\boldsymbol{B}-\sum_{i}\tilde{\boldsymbol{x}}^{(t)}$

14: Add budget exhausted campaign to $\mathcal{G}$

15: Calculate $\tilde{\boldsymbol{\alpha}}^{(t+1)}$ with eq. 28

16: Update $\bar{\boldsymbol{\alpha}}^{(t+1)}$ by clipping
$\tilde{\boldsymbol{\alpha}}^{(t+1)}$ with eq. 26

17: Update $\boldsymbol{ePTR}^{(t+1)}$ with eq. 21

18: end for

## Experimental Results

This section begins with an introduction to the evaluation metrics and the
baseline methods, and compares RCPacing to the baselines through offline and
online experiments.

### Evaluation Metrics

  * •

Delivery rate is defined as the ratio of allocated impressions to the total
budgets of the advertisers:

$delivery\;rate=\frac{\sum_{t}\sum_{j}\tilde{x}_{j}^{(t)}}{\sum_{j}B_{j}}$
(30)

  * •

Unsmoothness index (UI) measures the deviation between the actual and expected
budget consumption:

$unsmoothness=\frac{1}{M}\sum_{j=1}^{M}\sqrt{\frac{1}{T}\sum_{t=0}^{T-1}\left(\tilde{x}_{j}^{(t)}-\rho_{j}\right)^{2}}$
(31)

  * •

Average CTR reflects the quality of impressions, is calculated as the ratio of
clicks to the total impressions:

$CTR_{avg}=\frac{\sum_{t}\sum_{j}v_{j}^{(t)}\tilde{x}_{j}^{(t)}}{\sum_{t}\sum_{j}\tilde{x}_{j}^{(t)}}$
(32)

### Baseline Methods

We compare RCPacing with the following four methods: 1) DMD (Balseiro, Lu, and
Mirrokni 2020) is a Lagrangian dual-based online allocation framework that
maximizes revenue while adhering to resource constraints by adjusting their
virtual bids. 2) Smart Pacing (Xu et al. 2015) is a control-based method
proposed to achieve smooth delivery and optimal performance by probabilistic
throttling. 3) AUAF (Cheng et al. 2022) is a dual-based method that optimizes
delivery rate and impression quality with a fixed smoothness term. The dual
variables are updated by feedback control algorithm to ensure fairness. 4)
PDOA (Zhou et al. 2021) solves online matching in dynamic environments with
experts and meta-algorithm. It achieves smoothness by bid modification.

### Offline Evaluation

Table 1: Optimal values for the important hyper-parameters parameter | value | description
---|---|---
$\epsilon$ | 0.1 | skew factor
$\eta$ | 0.2 | step size
$\hat{\alpha}$ | 0.05 | static gradient clipping
$P_{ub}$ | 90% | safe percentile upper bound
$WR_{glb}$ | 15% | global win rate

#### Datasets

We construct a large-scale industrial dataset111Dataset and the code for all
methods are available in https://github.com/danifree/RCPacing. by collecting
real-world ad-serving data from our display advertising system, which consists
of 600K impressions and 300 GD ads. The impressions are evenly distributed
across 50 time periods. The CTR values predicted by a DNN are reserved to
measure the impression quality.

#### Implementation Details

Table 1 provides a summary of the optimal values for the important hyper-
parameters.

#### Evaluation Results

In order to exclude the influence of accidental factors, we randomly scale the
budget of GD ads by a factor ranging from 0.8 to 1.2, and calculate the mean
and standard deviation across 50 rounds. As shown in Table 2, Smart Pacing
achieves the highest average CTR, but its low delivery rate is inappropriate
for GD allocation, which results in publishers being penalized for unsatisfied
demand. RCPacing demonstrates a significant reduction in UI, with a 59.4% and
50.8% improvement compared to PDOA and AUAF, respectively. Furthermore, it
delivers superior CTR performance, achieving a 23.1% and 45.1% increase
compared to PDOA and AUAF.

Table 2: Offline evaluation results

Method | Unsmoothness | Delivery Rate (%) | CTR (%)
---|---|---|---
DMD | $15.71\pm 1.46$ | $\mathbf{100.0\pm 0.0}$ | $5.39\pm 0.02$
Smart | $10.52\pm 1.04$ | $95.9\pm 0.9$ | $\mathbf{7.88\pm 0.37}$
AUAF | $12.95\pm 1.29$ | $100.0\pm 0.0$ | $5.14\pm 0.01$
PDOA | $15.70\pm 2.27$ | $100.0\pm 0.0$ | $6.06\pm 0.27$
RCPacing | $\mathbf{6.37\pm 0.72}$ | $99.8\pm 0.1$ | $7.46\pm 0.44$

Figure 7: The ablative analysis.

#### Ablative Analysis

We focus on UI and CTR since the delivery rates of the variants are very close
to 100%.

  * •

The impact of percentile upper bound: A higher safety percentile upper bound
($P_{ub}$) allows advertisers to filter low-quality impressions more
effectively, but it also raises the risk of fluctuations. As demonstrated in
figure 7, RCPacing has higher CTR when using a larger $P_{ub}$, but there is a
4.14% increase in unsmoothness when $P_{ub}$ is changed from 90% to 95%
(Itakura-Saito divergence).

  * •

The impact of different divergence: As mentioned earlier, a modified Itakura-
Saito divergence helps alleviate the issue of high fluctuations in the high
percentile range. Figure 7 illustrates that the proposed Itakura-Saito
divergence provides better UI especial when $P_{ub}$ is high (e.g., a 3.74%
improvement in smoothness when $P_{ub}$ equals 90%), while the average CTR is
comparable to that of the Euclidean divergence.

Additional ablative analysis can be found in the appendix.

### Online Evaluation

Figure 8: The online evaluation results.

#### Implementation Details

In order to evaluate the performance of RCPaing in an online environment, we
conduct A/B testing on our Taobao brand advertising platform for a continuous
period of two weeks. Since the delivery rate for Smart pacing is too low for
GD allocation, we only compare our method with DMD, AUAF, and PDOA.

#### Evaluation Results

As the delivery rates of all methods exceed 99.5%, we concentrate on the other
two metrics in figure 8, RCPacing outperforms all the baselines. For example,
compared with PDOA, our method achieves a 35.3% and 23.4% improvement in UI
and CTR, respectively.

## Conclusion

GD contracts are a crucial source of revenue for large publishers. This paper
presents a robust percentile risk-constrained pacing framework designed from
the perspective of a publisher. RCPacing achieves smooth and optimal
allocation for GD campaigns by leveraging its compatibility with the
guaranteed allocation mechanism. Our analysis presents the relationship
between non-smooth risks and percentile of dual variables, and RCPacing is
designed to constrain dual variables within the low-risk region. Adaptive
gradient clipping and modified Bregman divergence techniques are also employed
to achieve more stable update of dual variables. We also illustrate the trade-
off and flexible control over smooth and optimal allocation in online
matching. Our experimental evaluations on real-world A/B testing demonstrate
that RCPacing outperforms other compared methods and it has been widely
deployed in Taobao display advertising system.

## References

  * Agarwal et al. (2014) Agarwal, D.; Ghosh, S.; Wei, K.; and You, S. 2014.  Budget pacing for targeted online advertisements at linkedin.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 1613–1619.
  * Balseiro, Lu, and Mirrokni (2020) Balseiro, S.; Lu, H.; and Mirrokni, V. 2020.  Dual mirror descent for online allocation problems.  In _International Conference on Machine Learning_ , 613–628. PMLR.
  * Banerjee et al. (2005) Banerjee, A.; Merugu, S.; Dhillon, I. S.; Ghosh, J.; and Lafferty, J. 2005.  Clustering with Bregman divergences.  _Journal of machine learning research_ , 6(10).
  * Bharadwaj et al. (2012) Bharadwaj, V.; Chen, P.; Ma, W.; Nagarajan, C.; Tomlin, J.; Vassilvitskii, S.; Vee, E.; and Yang, J. 2012.  Shale: an efficient algorithm for allocation of guaranteed display advertising.  In _Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 1195–1203.
  * Chen et al. (2012) Chen, P.; Ma, W.; Mandalapu, S.; Nagarjan, C.; Shanmugasundaram, J.; Vassilvitskii, S.; Vee, E.; Yu, M.; and Zien, J. 2012.  Ad serving using a compact allocation plan.  In _Proceedings of the 13th ACM Conference on Electronic Commerce_ , 319–336.
  * Chen, Wu, and Hong (2020) Chen, X.; Wu, S. Z.; and Hong, M. 2020.  Understanding gradient clipping in private SGD: A geometric perspective.  _Advances in Neural Information Processing Systems_ , 33: 13773–13782.
  * Cheng et al. (2022) Cheng, X.; Liu, C.; Dai, L.; Zhang, P.; Fang, Z.; and Zu, Z. 2022.  An Adaptive Unified Allocation Framework for Guaranteed Display Advertising.  In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_ , 132–140.
  * Dai et al. (2023) Dai, L.; Zu, Z.; Wu, H.; Wang, L.; and Zheng, B. 2023.  Fairness-aware Guaranteed Display Advertising Allocation under Traffic Cost Constraint.  In _Proceedings of the ACM Web Conference 2023_ , 3572–3580.
  * Fang et al. (2019) Fang, Z.; Li, Y.; Liu, C.; Zhu, W.; Zheng, Y.; and Zhou, W. 2019.  Large-scale personalized delivery for guaranteed display advertising with real-time pacing.  In _2019 IEEE International Conference on Data Mining (ICDM)_ , 190–199. IEEE.
  * Gao et al. (2021) Gao, C.; Lei, W.; He, X.; de Rijke, M.; and Chua, T.-S. 2021.  Advances and challenges in conversational recommender systems: A survey.  _AI Open_ , 2: 100–126.
  * Huang and Shu (2021) Huang, Z.; and Shu, X. 2021.  Online stochastic matching, poisson arrivals, and the natural linear program.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 682–693.
  * IAB (2023) IAB. 2023.  Internet Advertising Revenue Report.  https://www.iab.com/wp-content/uploads/2023/04/IAB˙PwC˙Internet˙Advertising˙Revenue˙Report˙2022.pdf.  Accessed: 2023-04.
  * Lee, Jalali, and Dasdan (2013) Lee, K. C.; Jalali, A.; and Dasdan, A. 2013.  Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising.  _arXiv e-prints_.
  * Liu et al. (2020) Liu, M.; Yue, W.; Qiu, L.; and Li, J. 2020.  An effective budget management framework for real-time bidding in online advertising.  _IEEE Access_ , 8: 131107–131118.
  * Mehta (2012) Mehta, A. 2012.  Online Matching and Ad Allocation.  _Foundations and trends in theoretical computer science_ , (8-4).
  * Mehta et al. (2007) Mehta, A.; Saberi, A.; Vazirani, U.; and Vazirani, V. 2007.  Adwords and generalized online matching.  _Journal of the ACM (JACM)_ , 54(5): 22–es.
  * Nuara et al. (2022) Nuara, A.; Trovò, F.; Gatti, N.; and Restelli, M. 2022.  Online joint bid/daily budget optimization of internet advertising campaigns.  _Artificial Intelligence_ , 305: 103663.
  * Sakia (1992) Sakia, R. M. 1992.  The Box-Cox transformation technique: a review.  _Journal of the Royal Statistical Society Series D: The Statistician_ , 41(2): 169–178.
  * Wang et al. (2022) Wang, X.; Tan, B.; Guo, Y.; Yang, T.; Huang, D.; Xu, L.; Freris, N. M.; Zhou, H.; and Li, X.-Y. 2022.  CONFLUX: A Request-level Fusion Framework for Impression Allocation via Cascade Distillation.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 4070–4078.
  * Wu et al. (2021) Wu, D.; Chen, C.; Chen, X.; Pan, J.; Yang, X.; Tan, Q.; Xu, J.; and Lee, K.-C. 2021.  Impression Allocation and Policy Search in Display Advertising.  In _2021 IEEE International Conference on Data Mining (ICDM)_ , 749–756. IEEE.
  * Xu et al. (2015) Xu, J.; Lee, K.-c.; Li, W.; Qi, H.; and Lu, Q. 2015.  Smart pacing for effective online ad campaign optimization.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , 2217–2226.
  * Zhou et al. (2019) Zhou, G.; Mou, N.; Fan, Y.; Pi, Q.; Bian, W.; Zhou, C.; Zhu, X.; and Gai, K. 2019.  Deep interest evolution network for click-through rate prediction.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, 5941–5948.
  * Zhou et al. (2021) Zhou, Y.-H.; Hu, P.; Liang, C.; Xu, H.; Huzhang, G.; Feng, Y.; Da, Q.; Wang, X.; and Zeng, A.-X. 2021.  A Primal-Dual Online Algorithm for Online Matching Problem in Dynamic Environments.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 11160–11167.

## Appendix

Table 3: The impact of slope $k$

$k$ | Unsmoothness | Delivery Rate (%) | CTR (%)
---|---|---|---
0 | $6.54\pm 0.65$ | $99.8\pm 0.1$ | $7.17\pm 0.39$
1 | $6.68\pm 0.65$ | $99.8\pm 0.1$ | $7.36\pm 0.37$
10 | $6.37\pm 0.72$ | $99.8\pm 0.1$ | $7.46\pm 0.44$
100 | $6.84\pm 0.61$ | $99.9\pm 0.0$ | $7.71\pm 0.35$
1000 | $7.07\pm 0.72$ | $99.9\pm 0.1$ | $7.77\pm 0.42$

Table 4: The impact of gradient clipping

Method | $\eta$ | Unsmoothness | Delivery Rate (%) | CTR (%)
---|---|---|---|---
w/o clip | 0.2 | $6.57\pm 0.59$ | $99.8\pm 0.1$ | $7.44\pm 0.39$
0.4 | $7.68\pm 0.82$ | $99.7\pm 0.1$ | $7.30\pm 0.39$
0.8 | $11.54\pm 1.13$ | $99.7\pm 0.0$ | $7.41\pm 0.41$
w/ clip | 0.2 | $6.37\pm 0.72$ | $99.8\pm 0.1$ | $7.46\pm 0.44$
0.4 | $7.16\pm 0.79$ | $99.8\pm 0.1$ | $7.32\pm 0.43$
0.8 | $8.26\pm 0.72$ | $99.9\pm 0.1$ | $7.36\pm 0.39$

### Supplementary experiments

This subsection presents additional experimental results that further
demonstrate the efficacy of RCPacing’s design strategies.

#### The impact of performance-based pacing

The performance-based pacing ($fv=k(\bar{v}_{ij}-\bar{\alpha}_{j})+1$) assigns
a higher PTR to traffic with higher performance scores, and the slope $k$
determines how significant this non-uniform is. As shown in Table 3,
deactivating the performance-based pacing by setting $k=0$ yields the lowest
average CTR. The average CTR increases with the increase in $k$, but it will
eventually reach saturation since the PTR cannot exceed 1.

#### The impact of gradient clipping

During iterative updates of the dual variables, gradient clipping is an
effective technique that restricts the range of changes to prevent significant
fluctuations caused by inappropriate learning rates. Table 4 demonstrates that
when the learning rate is excessively large, gradient clipping aims in
maintaining a smooth and stable allocation.

### Theoretical proof

#### Assumption 1

(Assumptions on constraint set $\mathcal{X}$). We assume that: (i)
$0\in\mathcal{X}$, and (ii) for each $x_{t}\in\mathcal{X}\text{ and }x_{t}\neq
0$, $x_{t}$ is a one-hot vector indicating which campaign the impression is
assigned to.

The above assumption implies that we can only assign an impression to one
campaign at a time. Moreover, we can always take the void action by choosing
$x_{t}=0$ in order to make sure we do not exceed the budget constraints. This
guarantees the existence of a feasible solution.

#### Assumption 2

(Assumptions on revenue function $f$).

  * •

$f\left(x\right)=v^{\top}x=\sum_{j=1}^{M}v_{j}x_{j}$, $v_{j}$ is the
impression quality and follows a beta distribution:

$v_{j}\sim Beta(m,n),\quad m\geq 2,n\geq 2$ (33)

  * •

There exists a positive constant $\bar{f}$ such that
$f\left(x\right)\leq\bar{f}$ is satisfied in all cases.

#### Assumption 3

(Assumptions on dual variable $\alpha$). We assume that $\alpha_{j}\in[0,1]$
is satisfied for any campaign $j$. Since campaign $j$ will not participate in
the auction when $v_{j}\leq\alpha_{j}$, it doesn’t make sense for $\alpha_{j}$
to be greater than 1. Moreover, from the definition of the dual problem
(equation 2), we have $\alpha_{j}\geq 0$.

#### Assumption 4

(Assumptions on budget parameter $\rho$). We assume there exist positive
constants $\bar{\rho}$ and $\underline{\rho}$ such that
$\underline{\rho}\leq\rho_{j}\leq\bar{\rho}$ is satisfied for any campaign
$j$.

#### Assumption 5

(Assumptions on reference function $h\left(\cdot\right)$). We assume

  * •

$h\left(\bar{\alpha}\right)$ is coordinate-wisely separable, i.e.,
$h\left(\bar{\alpha}\right)=\sum_{j}h_{j}\left(\bar{\alpha}_{j}\right)$ where
$h_{j}\left(\cdot\right)$ is a convex univariate function.

  * •

$h\left(\bar{\alpha}\right)$ is $\sigma_{1}$-strongly convex in $l_{1}$-norm
in $[0,1]$, i.e., $h\left(\bar{\alpha}_{1}\right)\geq
h\left(\bar{\alpha}_{2}\right)+\left<\nabla
h\left(\bar{\alpha}_{2}\right),\bar{\alpha}_{1}-\bar{\alpha}_{2}\right>+\frac{\sigma_{1}}{2}||\bar{\alpha}_{1}-\bar{\alpha}_{2}||^{2}_{1}$
for any $\bar{\alpha}_{1},\bar{\alpha}_{2}\in[0,1]$

  * •

$h\left(\bar{\alpha}\right)$ is $\sigma_{2}$-strongly convex in $l_{2}$-norm
in $[0,1]$, i.e., $h\left(\bar{\alpha}_{1}\right)\geq
h\left(\bar{\alpha}_{2}\right)+\left<\nabla
h\left(\bar{\alpha}_{2}\right),\bar{\alpha}_{1}-\bar{\alpha}_{2}\right>+\frac{\sigma_{2}}{2}||\bar{\alpha}_{1}-\bar{\alpha}_{2}||^{2}_{2}$
for any $\bar{\alpha}_{1},\bar{\alpha}_{2}\in[0,1]$

#### Definition 1

We define $\alpha^{max}\in\mathbb{R}^{M}$ such that
$\alpha^{max}_{j}:=\frac{\bar{f}}{\rho_{j}}+1$, where $M$ is the total number
of campaigns.

#### Definition 2

We define the stopping time $\tau_{j}$ of campaign $j$ as the first time less
than $T$ that satisfies

$\sum_{t=1}^{\tau_{j}}x_{tj}+1\geq\rho_{j}T$ (34)

$\tau_{j}$ is a random variable, and campaign $j$ will adhere to its budget
constraint until the stopping time $\tau_{j}$. To prevent campaign $j$ from
participating in any auctions after its budget is exhausted, we set $v_{tj}$
to be $0$ after $\tau_{j}$.

Moreover, we define the stopping time $\tau_{A}$ of the algorithm as

$\tau_{A}=\max_{j}\\{\tau_{j}\\}$ (35)

#### Definition 3

We define the expected revenue of an algorithm $A$ as

$R(A)=\mathbb{E}\left[\sum_{t=1}^{T}f_{t}\left(x_{t}\right)\right]$ (36)

where $x_{t}$ is the allocation decision made by the algorithm at time $t$. We
take the offline problem as the baseline for comparison, which determines the
optimal allocation under complete information of all requests and then
calculates the expected revenue across all possible outcomes:

$\operatorname{OPT}=\mathbb{E}\left[\begin{split}\max_{x_{t}\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x_{t})=\sum_{t=1}^{T}v_{t}^{\top}x_{t}\\\
\text{s.t.}\sum_{t=1}^{T}x_{t}\leq B=T\rho\end{split}\right]$ (37)

Moreover, the regret of algorithm $A$ is defined as:

$\operatorname{Regret}\left(A\right):=\operatorname{OPT}-R\left(A\right)$ (38)

#### Lemma 1

Suppose $\alpha_{j}\in[0,1],\forall j$, then there exists a constant $K_{1}$
such that $\bar{\alpha}_{j}\leq K_{1}\alpha_{j},\forall j$ always holds.

Proof. Denote the ratio $\bar{\alpha}_{j}/\alpha_{j}$ as

$\mathcal{R}_{1}\left(\alpha_{j}\right)=\frac{\int^{\alpha_{j}}_{0}\frac{1}{B\left(m,n\right)}s^{m-1}\left(1-s\right)^{n-1}ds}{\alpha_{j}}$
(39)

its derivative is obtained by

$\mathcal{R}^{\prime}_{1}\left(\alpha_{j}\right)=\frac{\alpha^{m}_{j}\left(1-\alpha_{j}\right)^{n-1}-\int^{\alpha_{j}}_{0}s^{m-1}\left(1-s\right)^{n-1}ds}{\alpha^{2}_{j}B\left(m,n\right)}$
(40)

Let

$\mathcal{G}_{1}\left(\alpha_{j}\right)=\alpha^{m}_{j}\left(1-\alpha_{j}\right)^{n-1}-\int^{\alpha_{j}}_{0}s^{m-1}\left(1-s\right)^{n-1}ds$
(41)

its derivative is obtained by

$\mathcal{G}^{\prime}_{1}\left(\alpha_{j}\right)=\alpha^{m-1}_{j}\left(1-\alpha_{j}\right)^{n-2}\left[m-1-\left(m+n-2\right)\alpha_{j}\right]$
(42)

Let $\alpha^{\prime}_{j}=\left(m-1\right)/\left(m+n-2\right)$,
$\mathcal{G}_{1}\left(\alpha_{j}\right)$ monotonically increases on
$\left[0,\alpha^{\prime}_{j}\right]$, and monotonically decreases on
$\left[\alpha^{\prime}_{j},1\right]$. Since $\mathcal{G}_{1}\left(0\right)=0$,
$\mathcal{G}_{1}\left(\alpha^{\prime}_{j}\right)>0$,
$\mathcal{G}_{1}\left(1\right)=-\int^{1}_{0}s^{m-1}\left(1-s\right)^{n-1}$,
there must be an
$\alpha^{\prime\prime}_{j}\in\left[\alpha^{\prime}_{j},1\right]$ to make
$\mathcal{G}_{1}\left(\alpha^{\prime\prime}_{j}\right)=0$. Thus
$\mathcal{R}^{max}_{1}=\mathcal{R}_{1}\left(\alpha^{\prime\prime}_{j}\right)$.
Let $K_{1}=\mathcal{R}^{max}_{1}$, we have
$\bar{\alpha}_{j}=\mathcal{R}_{1}\left(\alpha_{j}\right)\alpha_{j}\leq\mathcal{R}^{max}_{1}\alpha_{j}=K_{1}\alpha_{j}$,
and the lemma is proved.

#### Lemma 2

Suppose the update of dual variables in the original space is satisfied that
$0<\Delta_{m}\leq\Delta\leq 1$, then the percentile update must be satisfied
that $\bar{\Delta}\geq K_{2}\Delta$, where $K_{2}$ is a positive constant.

Proof. Denote the ratio $\bar{\Delta}/\Delta$ as

$\mathcal{R}_{2}\left(\alpha_{j},\Delta\right)=\frac{\int^{\alpha_{j}+\Delta}_{\alpha_{j}}\frac{1}{B\left(m,n\right)}s^{m-1}\left(1-s\right)^{n-1}ds}{\Delta}>0$
(43)

Since $\mathcal{R}_{2}\left(\alpha_{j},\Delta\right)$ is continuous when
$\Delta\in[\Delta_{m},1]$ and $\alpha_{j}\in\left[0,1\right]$, there must be a
positive constant $K_{2}$ satisfying
$K_{2}\leq\min_{\alpha_{j},\Delta}\left\\{\mathcal{R}_{2}\left(\alpha_{j},\Delta\right)\right\\}$.
Thus we have
$\bar{\Delta}=\mathcal{R}_{2}\left(\alpha_{j},\Delta\right)\Delta\geq
K_{2}\Delta$, and the lemma is proved.

#### Lemma 3

Let $\tilde{g}=\nabla f^{*}\left(\alpha\right)+\rho$ with
$f\left(x\right)=v^{\top}x$ and $v\in\left\\{v_{1},\cdots,v_{n}\right\\}$, and
$\bar{\alpha}^{+}=\mathop{\arg\min}_{\bar{\alpha}^{*}\geq
0}\left<\tilde{g},\bar{\alpha}^{*}\right>+\frac{1}{\eta}V_{h}\left(\bar{\alpha}^{*},\bar{\alpha}\right)$.
Suppose $\alpha\leq\alpha^{max}$and $\eta\leq K_{1}\sigma_{2}$, then it holds
that $\bar{\alpha}^{+}\leq\bar{\alpha}^{max}=K_{1}\alpha^{max}$.

Proof. Denote $J:=\left\\{j|\bar{\alpha}^{+}_{j}>0\right\\}$, then we just
need to show that $\bar{\alpha}^{+}_{j}\leq K_{1}\alpha^{max}$ holds for any
$j\in J$. Since we update the dual variables in the percentile space as

$\bar{\alpha}^{+}=\mathop{\arg\min}_{\bar{\alpha}^{*}\geq
0}\left<\tilde{g},\bar{\alpha}^{*}\right>+\frac{1}{\eta}V_{h}\left(\bar{\alpha}^{*},\bar{\alpha}\right)$
(44)

$V_{h}\left(\bar{\alpha}^{*},\bar{\alpha}\right)=h\left(\bar{\alpha}^{*}\right)-h\left(\bar{\alpha}\right)-\left<\nabla
h\left(\bar{\alpha}\right),\bar{\alpha}^{*}-\bar{\alpha}\right>$ (45)

it holds for any $j\in J$ that

$\dot{h}_{j}\left(\bar{\alpha}^{+}_{j}\right)=\dot{h}_{j}\left(\bar{\alpha}_{j}\right)-\eta\tilde{g}_{j}=\dot{h}_{j}\left(\bar{\alpha}_{j}\right)-\eta\left(\nabla
f^{*}\left(\alpha\right)\right)_{j}-\eta\rho_{j}$ (46)

Define
$h^{*}_{j}\left(c\right)=\max_{\bar{\alpha}}\left\\{c\bar{\alpha}_{j}-h_{j}\left(\bar{\alpha}_{j}\right)\right\\}$
as the conjugate function of $h_{j}\left(\bar{\alpha}_{j}\right)$, then by the
property of conjugate function it holds that $h_{j}^{*}\left(\cdot\right)$ is
a $\frac{1}{\sigma_{2}}$-smooth univariate convex function. Furthermore,
$\dot{h}^{*}_{j}\left(\cdot\right)$ is increasing, and
$\dot{h}^{*}_{j}\left(\dot{h}_{j}\left(\bar{\alpha}_{j}\right)\right)=\bar{\alpha}_{j}$.

Now define
$\tilde{x}:=\mathop{\arg\max}_{x\in\mathcal{X}}\left\\{f\left(x\right)-\alpha^{\top}x\right\\}=-\nabla
f^{*}\left(\alpha\right)$. Then it holds that $0=f\left(0\right)\leq
f\left(\tilde{x}\right)-\alpha^{\top}\tilde{x}\leq\bar{f}-\alpha^{\top}\tilde{x}$,
whereby $\alpha^{\top}\tilde{x}\leq\bar{f}$. Since $\alpha\geq
0,\tilde{x}_{j}\in\left\\{0,1\right\\}$, it holds for any $j\in J$ that
$\tilde{x}_{j}\leq\min\left(\frac{\bar{f}}{\alpha_{j}},1\right)$. Together
with equation 46, it holds that

$\dot{h}_{j}\left(\bar{\alpha}^{+}_{j}\right)\leq\dot{h}_{j}\left(\bar{\alpha}_{j}\right)+\eta\min\left(\frac{\bar{f}}{\alpha_{j}},1\right)-\eta\rho_{j}$
(47)

If $\frac{\bar{f}}{\rho_{j}}\leq\alpha_{j}\leq\alpha_{j}^{max}$, we have
$\min\left(\frac{\bar{f}}{\alpha_{j}},1\right)-\rho_{j}\leq 0$, thus it holds
that $\bar{\alpha}_{j}^{+}\leq\bar{\alpha}_{j}\leq K_{1}\alpha_{j}\leq
K_{1}\alpha_{j}^{max}$ by utilizing equation 47, Lemma 1, and convexity of
$\dot{h}_{j}$. Otherwise, $\alpha_{j}\leq\frac{\bar{f}}{\rho_{j}}$, and
furthermore,

$\displaystyle\bar{\alpha}^{+}_{j}$
$\displaystyle=\dot{h}^{*}_{j}\left(\dot{h}_{j}\left(\bar{\alpha}^{+}_{j}\right)\right)\leq\dot{h}^{*}_{j}\left(\dot{h}_{j}\left(\bar{\alpha}_{j}\right)+\eta\right)$
(48)
$\displaystyle\leq\dot{h}^{*}_{j}\left(\dot{h}_{j}\left(\bar{\alpha}_{j}\right)\right)+\frac{\eta}{\sigma_{2}}\leq
K_{1}\alpha_{j}+\frac{\eta}{\sigma_{2}}$ $\displaystyle\leq
K_{1}\left(\frac{\bar{f}}{\rho_{j}}+1\right)=K_{1}\alpha_{j}^{max}$

where the first inequality is from equation 47 and the monotonicity of
$\dot{h}^{*}_{j}\left(\cdot\right)$, the second inequality is from
$\dot{h}^{*}_{j}\left(\dot{h}_{j}\left(\bar{\alpha}_{j}\right)\right)=\bar{\alpha}_{j}$
and the $\frac{1}{\sigma_{2}}$-smoothness of $h^{*}_{j}\left(\cdot\right)$,
the third inequality is from Lemma 1, and the last equality follows from
Definition 1. This finishes the proof of the lemma.

#### Proposition 1

It holds for any $\alpha\geq 0$ that

$\operatorname{OPT}\leq TD\left(\alpha\right).$ (49)

Proof. Notice that for any $\alpha\geq 0$, it holds that

$\displaystyle\operatorname{OPT}$ (50)
$\displaystyle=\mathbb{E}\left[\begin{array}[]{cl}\max_{x_{t}\in\mathcal{X}}&\sum_{t=1}^{T}f_{t}\left(x_{t}\right)\\\
\text{ s.t. }&\sum_{t=1}^{T}x_{t}\leq T\rho\end{array}\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{x_{t}\in
X}\sum_{t=1}^{T}f_{t}\left(x_{t}\right)+T\alpha^{\top}\rho-\alpha^{\top}\sum_{t=1}^{T}x_{t}\right]$
$\displaystyle=T\mathbb{E}\left[\max_{x\in
X}f(x)-\alpha^{\top}x+\alpha^{\top}\rho\right]$
$\displaystyle=T\left(\sum_{i=1}^{n}p_{i}\max_{x\in\mathcal{X}}\left\\{f_{i}(x)-\alpha^{\top}x\right\\}+\alpha^{\top}\rho\right)$
$\displaystyle=T\left(\sum_{i=1}^{n}p_{i}f_{i}^{*}\left(\alpha\right)+\alpha^{\top}\rho\right)$

where the first inequality is because of the feasibility of $x$ and
$\alpha\geq 0$ and the last equality is due to the definition of $f_{i}^{*}$.
This finishes the proof.

#### Proposition 2

Consider Algorithm 2 with step-size $\eta\leq K_{1}\sigma_{2}$. Then it holds
that $\bar{\alpha}_{t}\leq\bar{\alpha}^{max}=K_{1}\alpha^{max}$ for any $t\leq
T$. Furthermore, it holds with probability 1 that

$T-\tau_{A}\leq\frac{1}{\eta\underline{\rho}}||\nabla
h\left(K_{1}\alpha^{max}\right)-\nabla
h\left(\bar{\alpha}_{0}\right)||_{\infty}+\frac{1}{\underline{\rho}}.$ (51)

Proof. First, a direct application of Lemma 3 shows that for any $t\leq T$,
$\bar{\alpha}_{t}\leq\bar{\alpha}^{max}=K_{1}\alpha^{max}$. Next, it follows
by the definition of $\tau_{A}$ that
$\sum_{t=1}^{\tau_{A}}x_{tj}+1\geq\rho_{j}T$ is satisfied for all $j$. By the
definition of $\tilde{g}_{t}$, we have

$\sum_{t=1}^{\tau_{A}}\tilde{g}_{tj}=\rho_{j}\tau_{A}-\sum_{t=1}^{\tau_{A}}x_{tj}\leq\rho_{j}\tau_{A}-\rho_{j}T+1$
(52)

thus

$T-\tau_{A}\leq\frac{1-\sum_{t=1}^{\tau_{A}}\tilde{g}_{tj}}{\rho_{j}},\forall
j$ (53)

On the other hand, it follows the update rule (equation 44 and 45) that for
any $t\leq\tau_{A}$,

$\dot{h}_{j}\left(\bar{\alpha}_{\left(t+1\right)j}\right)\geq\dot{h}_{j}\left(\bar{\alpha}_{tj}\right)-\eta\tilde{g}_{tj}$
(54)

Thus,

$\displaystyle\sum_{t=1}^{\tau_{A}}-\tilde{g}_{tj}$
$\displaystyle\leq\frac{1}{\eta}\left[\dot{h}_{j}\left(\bar{\alpha}_{\left(\tau_{A}+1\right)j}\right)-\dot{h}_{j}\left(\bar{\alpha}_{0j}\right)\right]$
(55)
$\displaystyle\leq\frac{1}{\eta}\left[\dot{h}_{j}\left(K_{1}\alpha_{j}^{max}\right)-\dot{h}_{j}\left(\bar{\alpha}_{0j}\right)\right]$

where the last inequality is due to the monotocity of
$\dot{h}^{*}_{j}\left(\cdot\right)$. Combining equation 53 and 55, we reach

$T-\tau_{A}\leq\frac{\dot{h}_{j}\left(K_{1}\alpha_{j}^{max}\right)-\dot{h}_{j}\left(\bar{\alpha}_{0j}\right)}{\eta\rho_{j}}+\frac{1}{\rho_{j}},\forall
j$ (56)

This finishes the proof by noticing that $\rho_{j}\geq\underline{\rho}$ and
$\dot{h}_{j}\left(K_{1}\alpha_{j}^{max}\right)-\dot{h}_{j}\left(\bar{\alpha}_{0j}\right)\leq||\nabla
h\left(K_{1}\alpha^{max}\right)-\nabla
h\left(\bar{\alpha}_{0}\right)||_{\infty}$.

#### Proposition 3

Consider the Algorithm 2 with given step size $\eta$ under Assumptions 1-5.
Let $\tau_{A}$ be the stopping time defined in Definition 2. Denote is
$\hat{\alpha}_{\tau_{A}}=\frac{\sum_{t=1}^{\tau_{A}}\alpha_{t}}{\tau_{A}}$.
Then the following inequality holds:

$\displaystyle\mathbb{E}\left[\tau_{A}D\left(\hat{\alpha}_{\tau_{A}}\right)-\sum_{t=1}^{\tau_{A}}f_{t}\left(x_{t}\right)\right]$
(57)
$\displaystyle\leq\frac{2\left(1+\bar{\rho}^{2}\right)}{K_{2}\sigma_{1}}\eta\mathbb{E}\left[\tau_{A}\right]+\frac{V_{h}\left(0,\bar{\alpha}_{0}\right)}{K_{2}\eta}$

Proof. Before proving Proposition 3, we first introduce some new notations
which are used in the proof. By the definition of conjugate function, we can
rewrite the dual problem (equation 2) as the following saddle-point problem:

$(S):\min_{0\leq\alpha}\max_{y\in
p\mathcal{X}}L(y,\alpha):=\sum_{i=1}^{n}p_{i}f_{i}\left(y_{i}/p_{i}\right)-\alpha^{\top}By+\alpha^{\top}\rho$
(58)

where $y:=\left[y_{1},\ldots,y_{n}\right]\in\mathbb{R}^{nM}$,
$B:=\left[I_{1};\ldots;I_{n}\right]\in\mathbb{R}^{M\times nM}$,
$p\mathcal{X}:=\left\\{y\mid y_{i}\in
p_{i}X\right\\}\subseteq\mathbb{R}^{nM}_{+}$, and $I_{i}\in\mathbb{R}^{M\times
M}$ is an identity matrix. By minimizing over $\alpha$ in equation 58, we
obtain the following primal problem:

$\begin{gathered}(P):\max_{y}P(y):=\sum_{i=1}^{n}p_{i}f_{i}\left(y_{i}/p_{i}\right)\\\
\text{ s.t. }By\leq\rho\\\ y\in p\mathcal{X}\end{gathered}$ (59)

The decision variable $y_{i}/p_{i}\in\mathcal{X}$ can be interpreted as the
expected action to be taken when a request of type $i$ arrives. Therefore, (P)
can be interpreted as a deterministic optimization problem in which resource
constraints can be satisfied in expectation. Moreover, we define an auxiliary
primal vari- able sequence $\left\\{z_{t}\right\\}_{{t=1},\ldots,T}$:

$z_{t}=\arg\max_{z\in p\mathcal{X}}L\left(z,\alpha_{t}\right)$ (60)

As a direct consequence of equation 58 and 60, we obtain:

$g_{t}:=-Bz_{t}+\rho=\nabla_{\alpha}L\left(z_{t},\alpha_{t}\right)\in\partial_{\alpha}D\left(\alpha_{t}\right)$
(61)

From the definition of $\tilde{g}_{t}$ and $\bar{\rho}$, we have

$\mathbb{E}_{\gamma_{t}}\left\|\tilde{g}_{t}\right\|_{\infty}^{2}\leq
2\left(\mathbb{E}_{\gamma_{t}}\left\|x_{t}\right\|_{\infty}^{2}+\|\rho\|_{\infty}^{2}\right)\leq
2\left(1+\bar{\rho}^{2}\right)$ (62)

Note that $\bar{\alpha}_{t}\in\sigma\left(\xi_{t-1}\right)$,
$g_{t}\in\sigma\left(\xi_{t-1}\right)$, and
$\tilde{g}_{t}\in\sigma\left(\xi_{t}\right)$, where $\sigma(X)$ denotes the
sigma algebra generated by a stochastic process $X$. Notice
$\mathbb{E}_{\gamma_{t}}\tilde{g}_{t}=g_{t}$, thus it holds for any
$\bar{\alpha}\in[0,1]$ that

$\displaystyle\left\langle g_{t},\bar{\alpha}_{t}-\bar{\alpha}\right\rangle$
(63) $\displaystyle=$
$\displaystyle\left\langle\mathbb{E}_{\gamma_{t}}\left[\tilde{g}_{t}\mid\bar{\alpha}_{t}\right],\bar{\alpha}_{t}-\bar{\alpha}\right\rangle$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\gamma_{t}}{\left[\left\langle\tilde{g}_{t},\bar{\alpha}_{t}-\bar{\alpha}_{t+1}\right\rangle+\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t}\right)\right.}$
$\displaystyle\left.\quad-\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t+1}\right)-\frac{1}{\eta}V_{h}\left(\bar{\alpha}_{t+1},\bar{\alpha}_{t}\right)\mid\bar{\alpha}_{t}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\gamma_{t}}\left[\left\langle\tilde{g}_{t},\bar{\alpha}_{t}-\bar{\alpha}_{t+1}\right\rangle+\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t}\right)\right.$
$\displaystyle\left.\quad-\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t+1}\right)-\frac{\sigma_{1}}{2\eta}\left\|\bar{\alpha}_{t+1}-\bar{\alpha}_{t}\right\|_{1}^{2}\mid\bar{\alpha}_{t}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\gamma_{t}}\left[\frac{\eta}{\sigma_{1}}\left\|\tilde{g}_{t}\right\|_{\infty}^{2}+\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t}\right)-\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t+1}\right)\mid\bar{\alpha}_{t}\right]$
$\displaystyle\leq$
$\displaystyle\frac{2\eta}{\sigma_{1}}\left(1+\bar{\rho}^{2}\right)+\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t}\right)-\mathbb{E}_{\gamma_{t}}\left[\frac{1}{\eta}V_{h}\left(\bar{\alpha},\bar{\alpha}_{t+1}\right)\mid\bar{\alpha}_{t}\right]$

where the first inequality follows from Three-Point Property, the second
inequality is by strongly convexity of $h$, the third inequality uses that
$a^{2}+b^{2}\geq 2ab$ for $a,b\in\mathbb{R}$ and Cauchy-Schwarz to obtain

$\displaystyle\frac{\sigma_{1}}{2\eta}\left\|\bar{\alpha}_{t+1}-\bar{\alpha}_{t}\right\|_{1}^{2}+\frac{\eta}{\sigma_{1}}\left\|\tilde{g}_{t}\right\|_{\infty}^{2}$
$\displaystyle\geq\left\|\bar{\alpha}_{t+1}-\bar{\alpha}_{t}\right\|_{1}\left\|\tilde{g}_{t}\right\|_{\infty}$
(64)
$\displaystyle\geq\left|\left\langle\tilde{g}_{t},\bar{\alpha}_{t}-\bar{\alpha}_{t+1}\right\rangle\right|$

and the last inequality follows from equation 62. Taking expectation with
respect to $\xi_{t-1}$ and multiplying by $\eta$ on both sides of equation 64
yields:

$\displaystyle\mathbb{E}_{\xi_{t-1}}\left[\eta\left\langle
g_{t},\bar{\alpha}_{t}-\bar{\alpha}\right\rangle\right]$ (65)
$\displaystyle\leq\frac{2\left(1+\bar{\rho}^{2}\right)}{\sigma_{1}}\eta^{2}+\mathbb{E}_{\xi_{t-1}}\left[V_{h}\left(\bar{\alpha},\bar{\alpha}_{t}\right)\right]-\mathbb{E}_{\xi_{t}}\left[V_{h}\left(\bar{\alpha},\bar{\alpha}_{t+1}\right)\right]$

Consider the process $Q_{t}=\sum^{t}_{s=1}\eta\left\langle
g_{s},\bar{\alpha}_{s}-\bar{\alpha}\right\rangle-\mathbb{E}_{\xi_{s-1}}\left[\left\langle
g_{s},\bar{\alpha}_{s}-\bar{\alpha}\right\rangle\right]$, which is martingale
with respect to $\xi_{t}$ (i.e., $Q_{t}\in\sigma\left(\xi_{t}\right)$ and
$\mathbb{E}\left[Q_{t+1}\mid\xi_{t}\right]=Q_{t}$) with increments bounded by

$\displaystyle\left|Q_{t}-Q_{t-1}\right|$
$\displaystyle\leq\eta\left(\left\|g_{t}\right\|_{\infty}+\mathbb{E}_{\xi_{t-1}}\left\|g_{t}\right\|_{\infty}\right)\left\|\bar{\alpha}_{t}-\bar{\alpha}\right\|_{1}$
(66) $\displaystyle\leq
2(1+\bar{\rho})M\left\|\bar{\alpha}_{t}-\bar{\alpha}\right\|_{\infty}$
$\displaystyle\leq 4M(1+\bar{\rho})\left\|K_{1}\alpha^{\max}\right\|_{\infty}$
$\displaystyle=4MK_{1}(1+\bar{\rho})\left(\frac{\bar{f}}{\underline{\rho}}+1\right)<\infty$

where the first inequality is Cauchy-Schwarz, the second inequality is from
$\left\|g_{t}\right\|_{\infty}\leq 1+\bar{\rho}$ almost surely, and the last
inequality utilize Lemma 3. Since $\tau_{A}$ is a stopping time with respect
to $\xi_{t}$ and $\tau_{A}$ is bounded, the Optional Stopping Theorem implies
that $\mathbb{E}\left[M_{\tau_{A}}\right]=0$. Therefore,

$\begin{gathered}\mathbb{E}\left[\sum_{t=1}^{\tau_{A}}\eta\left\langle
g_{t},\bar{\alpha}_{t}-\bar{\alpha}\right\rangle\right]=\mathbb{E}\left[\sum_{t=1}^{\tau_{A}}\mathbb{E}_{\xi_{t-1}}\left[\eta\left\langle
g_{t},\bar{\alpha}_{t}-\bar{\alpha}\right\rangle\right]\right]\\\
\leq\frac{2\left(1+\bar{\rho}^{2}\right)}{\sigma_{1}}\eta^{2}\mathbb{E}\left[\tau_{A}\right]+V_{h}\left(\bar{\alpha},\bar{\alpha}_{0}\right)\end{gathered}$
(67)

where the inequality follows from summing up equation 65 from $t=1$ to
$t=\tau$, telescoping, and using that the Bregman divergence is non-negative.
On the other hand, it holds that by choosing $\bar{\alpha}=\alpha=0$

$\displaystyle\sum_{t=1}^{\tau_{A}}\eta\left\langle
g_{t},\bar{\alpha}_{t}-\bar{\alpha}\right\rangle$ (68) $\displaystyle\geq$
$\displaystyle\sum_{t=1}^{\tau_{A}}\eta\left\langle
g_{t},K_{2}\left(\alpha_{t}-\alpha\right)\right\rangle$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{\tau_{A}}\eta
K_{2}\left\langle\nabla_{\alpha}L\left(z_{t},\alpha_{t}\right),\alpha_{t}-\alpha\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{t=1}^{\tau_{A}}\eta
K_{2}\left(L\left(z_{t},\alpha_{t}\right)-L\left(z_{t},\alpha\right)\right)$
$\displaystyle=$ $\displaystyle\sum_{t=1}^{\tau_{A}}\eta
K_{2}\left(L\left(z_{t},\alpha_{t}\right)-P\left(z_{t}\right)-\alpha\left(\rho-
Bz_{t}\right)\right)$ $\displaystyle=$ $\displaystyle\sum_{t=1}^{\tau_{A}}\eta
K_{2}\left(D\left(\alpha_{t}\right)-P\left(z_{t}\right)-\alpha\left(\rho-
Bz_{t}\right)\right)$ $\displaystyle\geq$ $\displaystyle\tau_{A}\eta
K_{2}\left(D\left(\hat{\alpha}_{\tau_{A}}\right)-\frac{\sum_{t=1}^{\tau_{A}}P\left(z_{t}\right)}{\tau_{A}}\right)-\sum_{t=1}^{\tau_{A}}\alpha\left(\rho-
Bz_{t}\right)$ $\displaystyle=$ $\displaystyle\tau_{A}\eta
K_{2}\left(D\left(\hat{\alpha}_{\tau_{A}}\right)-\frac{\sum_{t=1}^{\tau_{A}}P\left(z_{t}\right)}{\tau_{A}}\right)$

where the first inequality uses Lemma 2, the first equality uses equation 61,
the second equality is because $L\left(z,\alpha\right)$ is linear in $\alpha$,
the third equality is from
$z_{t}=\mathop{\arg\min}_{z}L\left(z,\alpha_{t}\right)$, the second inequality
uses convexity of $D\left(\cdot\right)$ over $\alpha$, and the last equality
is because $\alpha=0$. Combining equation 67 and 68 and choosing
$\bar{\alpha}=\alpha=0$, we obtain:

$\displaystyle\mathbb{E}\left[\tau_{A}D\left(\hat{\alpha}_{\tau_{A}}\right)-\sum_{t=1}^{\tau_{A}}P\left(z_{t}\right)\right]$
(69)
$\displaystyle\leq\frac{2\left(1+\bar{\rho}^{2}\right)}{K_{2}\sigma_{1}}\eta\mathbb{E}\left[\tau_{A}\right]+\frac{V_{h}\left(0,\bar{\alpha}_{0}\right)}{K_{2}\eta}$

Notice that $\alpha_{t}$ and $z_{t}$ are measurable given the sigma algebra
$\sigma\left(\xi_{t-1}\right)$. From the update of $x_{t}$ and $z_{t}$, we
know that if a request of type $i$-th is realized in the $t$-th iteration,
then $x_{t}=(z_{t})_{i}/p_{i}$. Thus it holds for any $t\leq\tau_{A}$ that

$\mathbb{E}_{\gamma_{t}}\left[f_{t}\left(x_{t}\right)\mid\xi_{t-1}\right]=\sum_{i=1}^{n}p_{i}f_{i}\left(\left(z_{t}\right)_{i}/p_{i}\right)=P\left(z_{t}\right)$
(70)

Therefore, another martingale argument yields that

$\mathbb{E}\left[\sum_{t=1}^{\tau_{A}}f_{t}\left(x_{t}\right)\right]=\mathbb{E}\left[\sum_{t=1}^{\tau_{A}}P\left(z_{t}\right)\right]$
(71)

Combining equation 69 and 71 finishes the proof.

#### Theorem 1

Consider Algorithm 2 with step-size $\eta\leq K_{1}\sigma_{2}$ and initial
dual solution $\alpha_{0}\leq\alpha^{max}$. Suppose Assumption 1-5 are
satisfied. Then it holds for any $T\geq 1$ that

$\displaystyle\text{Regret}\left(A\right)\leq$
$\displaystyle\frac{2\left(1+\bar{\rho}^{2}\right)}{K_{2}\sigma_{1}}\eta
T+\frac{V_{h}\left(0,\bar{\alpha}_{0}\right)}{K_{2}\eta}$ (72)
$\displaystyle+\frac{\bar{f}}{\underline{\rho}\eta}\left\|\nabla
h\left(K_{1}\alpha^{\max}\right)-\nabla
h\left(\bar{\alpha}_{0}\right)\right\|_{\infty}+\frac{\overline{f}}{\underline{\rho}}.$

When choosing $\eta=O\left(1/\sqrt{T}\right)$, we obtain that
$\text{Regret}\left(A\right)\leq O\left(\sqrt{T}\right)$ when $T$ is
sufficiently large, and, therefore, our algorithm yields sublinear regret.

Proof. For any $\tau_{A}\leq T$, we have

$\displaystyle\mathrm{OPT}$
$\displaystyle=\frac{\tau_{A}}{T}\mathrm{OPT}+\frac{T-\tau_{A}}{T}\mathrm{OPT}$
(73)
$\displaystyle\leq\tau_{A}D\left(\hat{\alpha}_{\tau_{A}}\right)+\left(T-\tau_{A}\right)\bar{f}$

where the inequality uses equation 49 and the fact that
$\mathrm{OPT}\leq\bar{f}$ . Therefore,

$\displaystyle\operatorname{Regret}(A)$ (74) $\displaystyle=$
$\displaystyle\operatorname{OPT}-R(A)$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\mathcal{P}}\left[\tau_{A}D\left(\hat{\alpha}_{\tau_{A}}\right)+\left(T-\tau_{A}\right)\bar{f}-\sum_{t=1}^{T}f_{t}\left(x_{t}\right)\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\mathcal{P}}\left[\left(\tau_{A}D\left(\hat{\alpha}_{\tau_{A}}\right)-\sum_{t=1}^{\tau_{A}}f_{t}\left(x_{t}\right)\right)\right]$
$\displaystyle+\mathbb{E}_{\mathcal{P}}\left[\left(T-\tau_{A}\right)\bar{f}\right]$
$\displaystyle\leq$
$\displaystyle\frac{2\left(1+\bar{\rho}^{2}\right)}{K_{2}\sigma_{1}}\eta\mathbb{E}_{\mathcal{P}}\left[\tau_{A}\right]+\frac{V_{h}\left(0,\bar{\alpha}_{0}\right)}{K_{2}\eta}$
$\displaystyle+\frac{\bar{f}}{\underline{\rho}\eta}\left\|\nabla
h\left(K_{1}\alpha^{\max}\right)-\nabla
h\left(\bar{\alpha}_{0}\right)\right\|_{\infty}+\frac{\overline{f}}{\underline{\rho}}$
$\displaystyle\leq$
$\displaystyle\frac{2\left(1+\bar{\rho}^{2}\right)}{K_{2}\sigma_{1}}\eta
T+\frac{V_{h}\left(0,\bar{\alpha}_{0}\right)}{K_{2}\eta}$
$\displaystyle+\frac{\bar{f}}{\underline{\rho}\eta}\left\|\nabla
h\left(K_{1}\alpha^{\max}\right)-\nabla
h\left(\bar{\alpha}_{0}\right)\right\|_{\infty}+\frac{\overline{f}}{\underline{\rho}}$

where the second inequality is because $\tau_{A}\leq T$ and
$f_{t}\left(x_{t}\right)\geq 0$, the third inequality uses Proposition 2 and
Proposition 3, and the last inequality is from $\tau_{A}\leq T$ almost surely.
Moreover, equation 74 holds for any $\mathcal{P}\in\mathcal{J}$, which
finishes the proof of Theorem 1.

#### Theorem 2

When the dual variable shifts the same distance, a higher percentile will make
the participation rate of a campaign generate greater fluctuations.

Proof. According to Assumption 2, the impression quality (or CTR in this
paper) follows a beta distribution, whose probability density function can be
expressed as

$Beta\left(v|m,n\right)=\frac{1}{B\left(m,n\right)}v^{m-1}\left(1-v\right)^{n-1}$
(75)
$B\left(m,n\right)=\int^{1}_{0}v^{m-1}\left(1-v\right)^{n-1}dv=\frac{\Gamma\left(m\right)\Gamma\left(n\right)}{\Gamma\left(m+n\right)}$
(76)

where $v\in[0,1]$ denotes the impression quality, $m\geq 2$ and $n\geq 2$ are
parameters of the beta distribution.

Suppose the dual variable of a campaign is $\alpha$, then its participation
rate can be obtained by

$\displaystyle\operatorname{PR}_{\alpha}$
$\displaystyle=\int^{1}_{\alpha}Beta\left(v|m,n\right)dv$ (77)
$\displaystyle=\frac{1}{B\left(m,n\right)}\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv$

When the dual variable shifts by a distance of $\delta\in(0,\alpha]$, the
resulting fluctuation in the participation rate is

$\mathcal{F}_{\delta}\left(\alpha\right)=\frac{\operatorname{PR}_{\alpha-\delta}}{\operatorname{PR}_{\alpha}}=\frac{\int^{1}_{\alpha-\delta}v^{m-1}\left(1-v\right)^{n-1}dv}{\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv}$
(78)

Let $g\left(\alpha\right)=\alpha^{m-1}\left(1-\alpha\right)^{n-1}$ and
$h\left(\alpha\right)=\int^{1}_{\alpha}g\left(v\right)dv$, the original
problem can be formulated as the task of demonstrating
$\mathcal{F}_{\delta}\left(\alpha\right)$ is monotonically increasing when
$0<\delta\leq\alpha<1$. The derivative of
$\mathcal{F}_{\delta}\left(\alpha\right)$ is

$\displaystyle\mathcal{F}^{\prime}_{\delta}\left(\alpha\right)$
$\displaystyle=\frac{g\left(\alpha\right)h\left(\alpha-\delta\right)-g\left(\alpha-\delta\right)h\left(\alpha\right)}{h^{2}\left(\alpha\right)}$
(79)
$\displaystyle=\frac{1}{h^{3}\left(\alpha\right)h\left(\alpha-\delta\right)}\cdot\left[\frac{g\left(\alpha\right)}{h\left(\alpha\right)}-\frac{g\left(\alpha-\delta\right)}{h\left(\alpha-\delta\right)}\right]$

Since $h\left(\alpha\right)>0$ when $0\leq\alpha<1$, the problem can be
converted to demonstrating that
$\phi\left(\alpha\right)=\frac{g\left(\alpha\right)}{h\left(\alpha\right)}$ is
monotonically increasing. The derivative of $\phi\left(\alpha\right)$ is

$\displaystyle\phi^{\prime}\left(\alpha\right)$
$\displaystyle=\frac{g^{\prime}\left(\alpha\right)h\left(\alpha\right)-g\left(\alpha\right)h^{\prime}\left(\alpha\right)}{h^{2}\left(\alpha\right)}$
(80)
$\displaystyle=\frac{g^{\prime}\left(\alpha\right)h\left(\alpha\right)+g^{2}\left(\alpha\right)}{h^{2}\left(\alpha\right)}$

We only need to prove that
$\Phi\left(\alpha\right)=g^{\prime}\left(\alpha\right)h\left(\alpha\right)+g^{2}\left(\alpha\right)\geq
0$ when $0\leq\alpha<1$. Let

$\displaystyle
a_{i}=\alpha+\frac{1-\alpha}{k},\;b_{i}=\alpha+\frac{1-\alpha}{k}i$ (81)
$\displaystyle
c_{i}=\alpha,\;d_{i}=\alpha+\frac{1-\alpha}{k}i+\frac{1-\alpha}{k}$

where $i=1,2,\cdots,n-1$. We have

$a_{i}+b_{i}=c_{i}+d_{i}=2\alpha+\frac{1-\alpha}{k}(i+1)=\mathcal{M}_{i}$ (82)

where $0\leq c_{i}\leq a_{i}\leq\mathcal{M}_{i}/2\leq b_{i}\leq
d_{i}\leq\mathcal{M}_{i}$.

Let $q_{i}\left(\alpha\right)=\alpha\left(\mathcal{M}_{i}-\alpha\right)$,
since $q\left(\alpha\right)$ is monotonically increasing on
$\left[0,\mathcal{M}_{i}/2\right]$ and $0\leq c_{i}\leq
a_{i}\leq\mathcal{M}_{i}/2$, we have $a_{i}b_{i}=q_{i}\left(a_{i}\right)\geq
q_{i}\left(c_{i}\right)=c_{i}d_{i}$, and

$\displaystyle
g\left(\alpha+\frac{1-\alpha}{k}\right)g\left(\alpha+\frac{1-\alpha}{k}i\right)$
(83)
$\displaystyle\quad-g\left(\alpha\right)g\left(\alpha+\frac{1-\alpha}{k}+\frac{1-\alpha}{k}i\right)$
$\displaystyle=g\left(a_{i}\right)g\left(b_{i}\right)-g\left(c_{i}\right)g\left(d_{i}\right)$
$\displaystyle=\left(a_{i}b_{i}\right)^{m-1}\cdot\left(1-\mathcal{M}_{i}+a_{i}b_{i}\right)^{n-1}$
$\displaystyle\quad-\left(c_{i}d_{i}\right)^{m-1}\cdot\left(1-\mathcal{M}_{i}+c_{i}d_{i}\right)^{n-1}\geq
0$

From the definition of derivative and integration, we can obtain

$\displaystyle\Phi\left(\alpha\right)=g^{\prime}\left(\alpha\right)h\left(\alpha\right)+g^{2}\left(\alpha\right)$
(84)
$\displaystyle=\lim_{k\rightarrow\infty}\frac{g\left(\alpha+\frac{1-\alpha}{k}\right)-g\left(\alpha\right)}{\frac{1-\alpha}{k}}\sum^{k}_{i=0}\frac{1-\alpha}{k}g\left(\alpha+\frac{1-\alpha}{k}i\right)$
$\displaystyle\quad+g^{2}\left(\alpha\right)$
$\displaystyle=\lim_{k\rightarrow\infty}\left[g\left(\alpha+\frac{1-\alpha}{k}\right)-g\left(\alpha\right)\right]\sum^{k}_{i=0}g\left(\alpha+\frac{1-\alpha}{k}i\right)$
$\displaystyle\quad+g^{2}\left(\alpha\right)$
$\displaystyle=\lim_{k\rightarrow\infty}\sum^{k}_{i=1}g\left(\alpha+\frac{1-\alpha}{k}\right)g\left(\alpha+\frac{1-\alpha}{k}i\right)-$
$\displaystyle\quad\lim_{k\rightarrow\infty}\sum^{k-1}_{i=1}g\left(\alpha\right)g\left(\alpha+\frac{1-\alpha}{k}+\frac{1-\alpha}{k}i\right)$
$\displaystyle=\lim_{k\rightarrow\infty}\sum^{k-1}_{i=1}{\left[g\left(\alpha+\frac{1-\alpha}{k}\right)g\left(\alpha+\frac{1-\alpha}{k}i\right)\right.}$
$\displaystyle\quad\left.-g\left(\alpha\right)g\left(\alpha+\frac{1-\alpha}{k}+\frac{1-\alpha}{k}i\right)\right]$
$\displaystyle\quad+\lim_{k\rightarrow\infty}g\left(\alpha+\frac{1-\alpha}{k}\right)g\left(1\right)$
$\displaystyle=\lim_{k\rightarrow\infty}\sum^{k-1}_{i=1}{\left[g\left(\alpha+\frac{1-\alpha}{k}\right)g\left(\alpha+\frac{1-\alpha}{k}i\right)\right.}$
$\displaystyle\quad\left.-g\left(\alpha\right)g\left(\alpha+\frac{1-\alpha}{k}+\frac{1-\alpha}{k}i\right)\right]\geq
0,$

where the last equality is because $g\left(1\right)=0$, and the last
inequality uses equation 83. This finishes the proof of Theorem 2.

#### Theorem 3

When the distribution of impression quality drifts (assume $m$ and $n$ do not
change simultaneously), a higher percentile will make the participation rate
of a campaign generate greater fluctuations.

Proof. Denote the participation rate of a campaign as

$\displaystyle\operatorname{PR}_{\alpha}\left(m,n\right)$
$\displaystyle=\int^{1}_{\alpha}Beta\left(v|m,n\right)dv$ (85)
$\displaystyle=\frac{\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv}{\int^{1}_{0}v^{m-1}\left(1-v\right)^{n-1}dv}$

To demonstrate its monotonicity with regard to $m$, the partial derivative of
$\operatorname{PR}_{\alpha}\left(m,n\right)$ with respect to $m$ is deduced as

$\frac{\partial PR_{\alpha}}{\partial
m}=\frac{h\left(0\right)\cdot\hat{h}\left(\alpha\right)-\hat{h}\left(0\right)\cdot
h\left(\alpha\right)}{h^{2}\left(0\right)}$ (86)

where $h\left(\alpha\right)=\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv$
and $\hat{h}\left(\alpha\right)=\int^{1}_{\alpha}\ln v\cdot
v^{m-1}\left(1-v\right)^{n-1}dv$. Let
$\mathcal{H}\left(\alpha\right)=h\left(0\right)\cdot\hat{h}\left(\alpha\right)-\hat{h}\left(0\right)\cdot
h\left(\alpha\right)$, its derivative with respect to $\alpha$ is

$\mathcal{H}^{\prime}\left(\alpha\right)=\alpha^{m-1}\left(1-\alpha\right)^{n-1}\left[\hat{h}\left(0\right)-h\left(0\right)\ln\alpha\right]$
(87)

It is obvious that $\mathcal{H}^{\prime}\left(\alpha\right)$ is positive on
$\left[0,\alpha_{0}\right]$ and negative on $\left[\alpha_{0},1\right]$, where
$\alpha_{0}=\hat{h}\left(0\right)/h\left(0\right)$. Thus,
$\mathcal{H}\left(\alpha\right)$ increases on $\left[0,\alpha_{0}\right]$ and
decreases on $\left[\alpha_{0},1\right]$. Since
$\mathcal{H}\left(0\right)=\mathcal{H}\left(1\right)=0$, it can be deduced
that $\mathcal{H}\left(\alpha\right)\geq 0$ when $\alpha\in\left[0,1\right]$.
Together with equation 86, it can be proved that
$\operatorname{PR}_{\alpha}\left(m,n\right)$ increases monotonically with
respect to $m$. Similarly, we can prove that
$\operatorname{PR}_{\alpha}\left(m,n\right)$ decreases monotonically with
respect to $n$.

When $m$ has an increase of $\delta$, the resulting fluctuation in the
participation rate is

$\displaystyle\mathcal{F}_{\delta}\left(\alpha\right)$
$\displaystyle=\frac{\operatorname{PR}_{\alpha}\left(m+\delta,n\right)}{\operatorname{PR}_{\alpha}\left(m,n\right)}$
(88)
$\displaystyle=V\left(m,n,\delta\right)\cdot\frac{\int^{1}_{\alpha}v^{m+\delta-1}\left(1-v\right)^{n-1}dv}{\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv}$

Our target is to prove that $\mathcal{F}_{\delta}\left(\alpha\right)$ is
monotonically increasing with respect to $\alpha$ for any $\alpha\in[0,1)$.
The derivative of $\mathcal{F}_{\delta}\left(\alpha\right)$ is obtained by

$\displaystyle\mathcal{F}_{\delta}^{\prime}\left(\alpha\right)$ (89)
$\displaystyle=\frac{\alpha^{m-1}\left(1-\alpha\right)^{n-1}\int^{1}_{\alpha}\left(v^{\delta}-\alpha^{\delta}\right)v^{m-1}\left(1-v\right)^{n-1}dv}{\left[\int^{1}_{\alpha}v^{m-1}\left(1-v\right)^{n-1}dv\right]^{2}}$
$\displaystyle\geq 0$

which indicates that a greater $\alpha$ will result in a more pronounced
fluctuation in the participation rate as $m$ varies. Through a similar
process, we can also prove that when $n$ changes, a greater $\alpha$ will
result in a more pronounced fluctuation in the participation rate, which is
omitted here.