# Online Bidding Algorithms for
Return-on-Spend Constrained Advertisers

Zhe Feng
Google Research
<EMAIL_ADDRESS>Swati Padmanabhan
University of Washington, Seattle
<EMAIL_ADDRESS>Work done as a student researcher in the Market Algorithms team
at Google Research. Di Wang
Google Research
<EMAIL_ADDRESS>
###### Abstract

Online advertising has recently grown into a highly competitive and complex
multi-billion-dollar industry, with advertisers bidding for ad slots at large
scales and high frequencies. This has resulted in a growing need for efficient
“auto-bidding” algorithms that determine the bids for incoming queries to
maximize advertisers’ targets subject to their specified constraints. This
work explores efficient online algorithms for a single value-maximizing
advertiser under an increasingly popular constraint: Return-on-Spend (RoS). We
quantify efficiency in terms of _regret_ relative to the optimal algorithm,
which knows all queries a priori.

We contribute a simple online algorithm that achieves near-optimal regret in
expectation while always respecting the specified RoS constraint when the
input sequence of queries are i.i.d. samples from some distribution. We also
integrate our results with the previous work of Balseiro, Lu, and Mirrokni
[BLM20] to achieve near-optimal regret while respecting _both_ RoS and fixed
budget constraints.

Our algorithm follows the primal-dual framework and uses online mirror descent
(OMD) for the dual updates. However, we need to use a non-canonical setup of
OMD, and therefore the classic low-regret guarantee of OMD, which is for the
adversarial setting in online learning, no longer holds. Nonetheless, in our
case and more generally where low-regret dynamics are applied in algorithm
design, the gradients encountered by OMD can be far from adversarial but
influenced by our algorithmic choices. We exploit this key insight to show our
OMD setup achieves low regret in the realm of our algorithm.

##  1 Introduction

With the explosive growth of online advertising into a billion-dollar
industry111See eMarketer, auto-bidding — the practice of using optimization
algorithms to generate bids for ad slots on behalf of advertisers — has
emerged as a predominant tool in online advertising [ABM19, BG19, BCHIL21,
GJLM21, DMMZ21, BDMMZ21, BDMMZ21a]. Unlike manual CPC (“cost-per-click”)
bidding, which requires advertisers to manually update bids for new search
queries, auto-bidding requires advertisers to specify only their high-level
objectives and constraints. The advertising platform then deploys its auto-
bidding agent, which, based on its underlying optimization algorithms,
transforms these inputs into fine-grained bids. Thus, designing an efficient
bidding algorithm for advertisers to achieve their targets under constraints
constitutes a central problem in the auto-bidding domain.

Throughout this paper, we focus on the return-on-spend (RoS) constrained
bidding problem for a single learner (auto-bidder). In this problem, the RoS
constraint requires that the ratio of total value of the advertiser to its
total payment exceed at least some specified target ratio. In practice, the
RoS constraint may capture other similar constraints, e.g., target cost-per-
acquisition (tCPA) and target return-on-ad-spend (tROAS).222See Google ads
support page Additionally, we investigate the well-studied total budget
constraint, which specifies an upper bound on the auto-bidder’s total
expenditure; our proposed algorithm, though tailored to the RoS constraint,
easily adapts to the budget constraint, as well.

We study the online bidding algorithm for a single auto-bidder (learner) in
the stochastic setting: In each round, an ad query (request) and auction are
generated i.i.d. from an unknown distribution, after which the learner submits
a bid to compete for the ad query in the auction. Given all bids for this
query, the auction mechanism specifies which advertiser wins the opportunity
to show its ad to the user and how much it needs to pay. Before placing its
bid, the learner observes only the value of this ad query; after placing the
bid, it receives its bid’s auction outcome (i.e., the allocation and payment).
From the perspective of auto-bidding, the platform needs to design an online
bidding algorithm for the learner to maximize its target subject to the RoS
and budget constraints.

For theoretical simplicity, we focus only on the value-maximizing auto-bidder,
i.e., the learner aims to maximize the total realized value (or conversions)
for $T$ i.i.d. randomly drawn ad queries subject to RoS and budget
constraints. Our results can be easily extended to handle other types of auto-
bidders (e.g., utility maximization or a hybrid of value maximization and
utility maximization [BDMMZ21]).

###  1.1 Results and Techniques

Our main result is as follows.

######  Theorem 1.1 (Informal version; see Theorem 5.2).

We provide an algorithm (Algorithm 5.2) for value maximization under RoS and
budget constraints. For a $T$-length input i.i.d. sequence of ad queries, our
algorithm provably attains $O(\sqrt{T}\log T)$ regret while respecting both
the budget and RoS constraints.

To the best of our knowledge, ours is the first algorithm to attain near-
optimal regret while satisfying _both_ budget and RoS constraints in any
outcome. In doing so, we improve upon the prior work of [BLM20], which obtains
similar guarantees under only budget constraints. Our result holds for i.i.d.
input sequences and under an additional mild technical assumption on the input
distribution.

We build to our result by first obtaining a $O(\sqrt{T})$-regret algorithm
(LABEL:alg:tcpa-truthful-soft) for value maximization under _approximate_ RoS
constraints (i.e., allowing for an at most $O(\sqrt{T}\log T)$ violation of
this constraint). A simple modification to this algorithm yields Algorithm
4.1, which obtains a $O(\sqrt{T}\log T)$ regret guarantee under a _strict_ RoS
constraint (Theorem 4.1). We then combine LABEL:alg:tcpa-truthful-soft with
ideas from [BLM20] to design LABEL:alg:combined-truthful-soft, which attains a
$O(\sqrt{T})$-regret under _two_ constraints: strict budget constraints and
approximate RoS constraints (with a $O(\sqrt{T}\log T)$ violation cap).
Finally, unifying ideas from Algorithm 4.1 and LABEL:alg:combined-truthful-
soft yields our main result.

Underlying all the algorithms we propose in this paper is a primal-dual
framework similar to that used by [BLM20]. Such a framework allows our
algorithms to adapt to the changing values and prices of input queries while
respecting the advertisers’ specified constraints and goals over the entire
time horizon. In particular, the dual variable (which tracks the constraint
violation) is updated via online mirror descent (OMD) using the generalized
cross-entropy function, which imposes a large (exponential) penalty on
constraint violation.

An immediate technical challenge in attempting to use generalized cross-
entropy as the mirror map is its lack of strong convexity on the non-negative
orthant. While this is an issue in [BLM20] as well, in this case, the fixed
budget constraint bounds the corresponding dual variable by a constant, which
in turn implies the desired strong convexity on the space over which their
algorithm operates. In our case (with the RoS constraint), there exist example
inputs on which no such bound exists, which necessitates a novel analysis that
circumvents the lack of strong convexity.

Our key insight is that while the low-regret guarantee of OMD with a strongly
convex mirror map holds even when the gradients seen by OMD are adversarial,
when we use OMD in our algorithm to update the dual variable, the gradients
used in the update are controlled by how our algorithm sets the primal
variables (i.e., bids); this connection is sufficient to give our algorithm
the low-regret guarantee despite not using a strongly convex mirror map. We
use this connection in a white-box adaptation of the OMD analysis tailored to
our algorithm, as well as properties of the generalized cross-entropy function
from the (offline) positive linear programming literature [AO14].

As a final remark on our technique, to turn an algorithm that only
_approximately_ satisfies a constraint to one that _strictly_ satisfies it, we
propose a simple strategy: We first submit a sequence of bids that lets us
accumulate a slack on the RoS constraint, followed by the existing algorithm,
which suffers some bounded constraint violation (c.f. Section 4). The first
phase builds up enough slack (at the cost of bidding sub-optimally) to
compensate for the constraint violation from the later iterations. This allows
us to trade off the violation on the RoS constraint with the objective value.
We anticipate that this simple idea might be applicable in other contexts but
note that such a trade-off is typically easier in offline optimization via
retrospectively modifying the solution (e.g., by scaling or truncating).

###  1.2 Related Work

The work most closely related to ours is [GJLM21], which investigates the same
problem we do but with the RoS and budget constraints holding _only in
expectation over the distribution of the nature_ ; in contrast, our
constraints hold for any realization of samples. Additionally, our primal-dual
based algorithm is easily implementable in practice using the existing pacing
controller [CKPSSSW22, CKSS22]. As previously noted, our primal-dual approach
is similar to [BLM20]; however, the RoS constraint is not a packing-type
constraint as studied in their work. In particular, while the classic low-
regret analysis of OMD can be directly applied in their case, we need to
develop customized techniques to address the RoS constraint. Another related
work is [AD14], which considers general online optimization with combinatorial
constraints; however, it requires the dual variables to belong to a bounded
feasibility set, an assumption our work does not impose.

Our work is also related to the _learning to bid in repeated auctions_
literature, e.g. [BCIJEM07, WPR16, FPS18, BG19, BFG21, NCKP22, NS21, HZFOW20].
However, these papers focus on utility-maximizing agents with at most one
constraint, e.g., [BG19] considers a budget constraint. Finally, loosely
related work includes the AdWords problem [MSVV07, DH09], which focuses on
budget management for multiple bidders to maximize the seller’s revenue; in
contrast, we focus on the design of online bidding algorithms for a single
auto-bidder with RoS and budget constraints.

##  2 Preliminaries

We consider an online bidding model for a single learner (auto-bidder): At
each time step $t$, nature stochastically generates for the learner an ad
query associated with a value $v_{t}\in[0,1]$ and an auction mechanism
$(x_{t},p_{t})$, where $x_{t}:\mathbb{R}_{\geq 0}\mapsto[0,1]$ is an
allocation function and $p_{t}:\mathbb{R}_{\geq 0}\mapsto[0,1]$ the expected
payment rule.333Our algorithm’s regret guarantee depends linearly on the
scales of the valuation and payment, and the assumed bounds on these
quantities are for theoretical simplicity. We assume the following stochastic
model: $(v_{t},x_{t},p_{t})$ are drawn independently and identically (i.i.d.)
from an unknown distribution. At each time step $t$, the value $v_{t}$ is
known to the learner before making a bid, and the learner decides its bid
$b_{t}$ given $v_{t}$ and historical information. At the end of time step $t$,
the learner observes the realized outcome from the auction mechanism, i.e.,
$x_{t}(b_{t})$ and $p_{t}(b_{t})$.

We focus only on auctions that are truthful. This requires that the allocation
function $x_{t}(b)$ be non-decreasing with the input bid $b$ and the payment
function $p_{t}$ be characterized by the pioneering work of [Mye81] as

$p_{t}(b)=b\cdot x_{t}(b)-\int_{z=0}^{b}x_{t}(z)dz.$

For instance, the well-known second-price auction for a single item is
truthful, and its payment function satisfies Section 2. Note the payment must
be zero when the allocation is zero, and the payment is also at most the bid.
This work also assumes $v_{t}\cdot x_{t}(b_{t})$ to be the realized value of
the learner in each round.

We design online bidding algorithms to maximize the learner’s total realized
value subject to an RoS constraint. Formally, the optimization problem under
RoS constraint we study is

$\begin{array}[]{ll}\underset{b_{t}:t=1,\cdots,T}{\mbox{maximize}}&\sum_{t=1}^{T}v_{t}\cdot
x_{t}(b_{t})\\\ \mbox{subject to
}&\mathsf{RoS}\cdot\sum_{t=1}^{T}p_{t}(b_{t})\leq\sum_{t=1}^{T}v_{t}\cdot
x_{t}(b_{t}),\end{array}$

where $\mathsf{RoS}>0$ is the target ratio of the RoS bidder. Throughout the
paper we assume without loss of generality444For any $\mathsf{RoS}\neq 1$, we
can scale the values to be $v_{t}:=\mathsf{RoS}\cdot v_{t}$. that
$\mathsf{RoS}=1$. As noted in Section 1, our results can be extended to handle
different learner objectives, e.g., a hybrid version between utility
maximizing and value maximizing $\sum_{t=1}^{T}v_{t}\cdot x_{t}(b_{t})-\tau
p_{t}(b_{t})$ for some $\tau\in[0,1]$.

To simplify the notation, we denote the difference between value and price in
iteration $t$ as

$g_{t}(b):=v_{t}\cdot x_{t}(b)-p_{t}(b),$

and using this notation, the RoS constraint in Section 2 may be stated as

$\sum_{t=1}^{T}g_{t}(b_{t})\geq 0.$

Our algorithm also extends to the bidding problem subject to an additional
budget constraint.

$\begin{array}[]{ll}\underset{b_{t}:t=1,\cdots,T}{\mbox{maximize}}&v_{t}\cdot
x_{t}(b_{t})\\\ \mbox{subject
to}&\sum_{t=1}^{T}p_{t}(b_{t})\leq\sum_{t=1}^{T}v_{t}\cdot x_{t}(b_{t}),\\\
&\sum_{t=1}^{T}p_{t}(b_{t})\leq\rho T.\end{array}$

where $\rho T$ is the budget and $\rho>0$ (assumed a fixed constant) measures
the limit of the average expenditure over $T$ rounds (ad queries).

To collect notation, we denote the sample (ad query and auction) at time $t$
as a tuple $\gamma_{t}=(v_{t},p_{t},x_{t})$ and assume
$\gamma_{t}\sim\mathcal{P}$ for all $t\in[T]$. We denote the sequence of $T$
samples by
$\overrightarrow{\gamma}:=\\{\gamma_{1},\gamma_{2},\dots,\gamma_{T}\\}\sim\mathcal{P}^{T}$
and sequences of length $\ell\neq T$ by $\overrightarrow{\gamma}_{\\!\ell}$
where needed.

#### Analysis setup.

We use the notions of regret and constraint violation to measure the
performance of our algorithms. To define the regret, we first define the
reward of $\mathsf{Alg}$ for a sequence of requests $\overrightarrow{\gamma}$
over a time horizon $T$ as

$\mathsf{Reward}(\mathsf{Alg},\overrightarrow{\gamma}):=\sum_{t=1}^{T}v_{t}\cdot
p_{t}(b_{t}).$

Next, we define the optimal value in the same setup as for $\mathsf{Alg}$ as

$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}):=\mbox{maximum}_{b_{t}\in\mathcal{B}}\sum_{t=1}^{T}v_{t}\cdot
p_{t}(b_{t}),$

where $\mathcal{B}$ is the exact set of constraints. These definitions lead to
the definition of regret of $\mathsf{Alg}$ in this setup as

$\mathsf{Regret}(\mathsf{Alg},\mathcal{P}^{T}):=\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})-\mathsf{Reward}(\mathsf{Alg},\overrightarrow{\gamma})\right].$

We remark that we define $\mathsf{Reward}$ for some specific input sequence,
whereas $\mathsf{Regret}$ is defined with respect to a distribution.

Finally, we use online mirror descent as a technical component in our
analysis. In this regard, we use
$V_{h}(y,x)=h(y)-h(x)-h^{\prime}(x)\cdot(y-x)$ to denote the Bregman
divergence of $y$ in reference to $x$, measuring with the distance-generating
function (“mirror map”) $h$. We brief review online mirror descent in Appendix
D.

##  3 Bidding Under an Approximate RoS Constraint

In this section, we design and analyze an algorithm for Section 2 allowing for
bounded _sublinear violation_ of the RoS constraint. To this end, we first
rewrite Section 2 as the equivalent problem

$\mbox{maximize}_{\\{b_{i}\\}}\left\\{\sum_{i=1}^{T}v_{i}\cdot
x_{i}(b_{i})+\min_{\lambda\geq 0}\lambda\cdot\sum_{i=1}^{T}\left[v_{i}\cdot
x_{i}(b_{i})-p_{i}(b_{i})\right]\right\\},$

in which the inner minimization strictly enforces
$\sum_{i=1}^{T}\left[v_{i}\cdot x_{i}(b_{i})-p_{i}(b_{i})\right]\geq 0$ via
the variable $\lambda$ that applies an unbounded penalty for the constraint
violation. Our algorithm iteratively updates, in each iteration $t$, the bid
$b_{t}$ and a dual variable $\lambda_{t}$ that captures the current best
penalizing (dual) variable $\lambda$, described shortly.

#### Updating the bid.

Based on the formulation in Section 3, our algorithm chooses the bid $b_{t}$
as the maximizer of the penalty-adjusted reward of the _current round_ , with
the penalty applied by the current dual variable $\lambda_{t}$:

$b_{t}=\arg\max_{b\geq 0}\left[\frac{1+\lambda_{t}}{\lambda_{t}}\cdot
v_{t}\cdot x_{t}(b)-p_{t}(b)\right]=v_{t}+\frac{v_{t}}{\lambda_{t}},$

where the final step is because of the truthful nature of the
auction.555Because it is a truthful auction, we have $\nabla_{b}x_{t}(b)\geq
0$, which, when used in the definition of $b_{t}$, gives the claimed final
step. The final expression for $b_{t}$ is consistent with the setting that we
first observe only the value $v_{t}$ before making the bid.

#### Updating the dual variable.

To maintain a meaningful dual variable, we relax the penalty on the constraint
violation in Section 3 by adding a scaled regularization function
$h(\lambda)$. This regularizer prevents $\lambda$ from getting too large:

$\mbox{maximize}_{\\{b_{i}\\}}\left\\{\sum_{i=1}^{T}v_{i}\cdot
x_{i}(b_{i})+\min_{\lambda\geq
0}\left[\lambda\cdot\sum_{i=1}^{T}\left[v_{i}\cdot
x_{i}(b_{i})-p_{i}(b_{i})\right]+\alpha^{-1}h(\lambda)\right]\right\\},$

where $\alpha>0$ is the scaling factor of the regularizer to be set later. At
any iteration $t$, the value of $\lambda_{t+1}$ is chosen to be the minimizer
of the inner constrained minimization problem (until iteration $i=t$). While
there exist a number of valid regularization functions, in this paper, we
choose the generalized negative entropy $h(u)=u\log u-u$, which gives the
following expression for $\lambda_{t+1}$.

$\lambda_{t+1}=\arg\min_{\lambda\geq
0}\left[g_{t}(b_{t})\cdot\lambda+\frac{1}{\alpha}V_{h}(\lambda,\lambda_{t})\right]=\lambda_{1}\cdot\exp\left[-\sum_{i=1}^{t}\alpha\cdot
g_{i}(b_{i})\right].$

Through this rule, a net constraint violation (i.e.,
$\sum_{i=1}^{t}g_{i}(b_{i})\leq 0$) makes the next dual variable exponential
in the net violation, which in turn shrinks the next bid (in Section 3); on
the other hand, an accumulated buffer in the net constraint violation (i.e.,
$\sum_{i=1}^{t}g_{i}(b_{i})>0$) encourages the next dual variable to be small,
allowing the next bid to grow. We demonstrate in Section A.1 that the use of
another valid mirror map on this domain, $h(u)=\frac{1}{2}u^{2}$, does not
provide a sufficiently strong regret or constraint violation guarantee.
Intuitively, the reason for this is that the squared penalty is simply not as
strong as the exponential.

The final algorithm with these choices of $b_{t}$ and $\lambda_{t}$ is stated
in LABEL:alg:tcpa-truthful-soft.

Algorithm 3.1 Bidding algorithm of the RoS agent operating under approximate
constraints in truthful auctions (i.i.d. inputs), with mirror map $h(u)=u\log
u-u$.

alg]alg:tcpa-truthful-soft

1:Input: Total time horizon $T$ and requests $\overrightarrow{\gamma}$ from
the distribution $\mathcal{P}^{T}$.

2:Initialize: Initial dual variable $\lambda_{1}=1$ and dual mirror descent
step size $\alpha=\frac{1}{\sqrt{T}}$.

3:for $t=1,2,\cdots,T$ do

4: Observe the value $v_{t}$, and set the bid
$b_{t}=\frac{1+\lambda_{t}}{\lambda_{t}}v_{t}$.

5: Observe the price $p_{t}$ and allocation $x_{t}$ at $b_{t}$, and compute
$g_{t}(b_{t})=v_{t}\cdot x_{t}({b}_{t})-p_{t}(b_{t})$.

6: Update the dual variable as $\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha
g_{t}(b_{t})\right]$.

7:end for

8:return The sequence $\\{b_{t}\\}_{t=1}^{T}$ of generated bids.

###  3.1 Analysis of LABEL:alg:tcpa-truthful-soft

The main export of this section is the following theorem of LABEL:alg:tcpa-
truthful-soft for Section 2. The proof of the theorem is a straightforward
application of our chief technical results Lemma 1 and Lemma 2 (with
$\lambda=1/T$), which provide guarantees on the constraint violation and
regret, respectively. We focus our discussion on these two lemmas, deferring
the proof of the theorem to Appendix A.

######  Theorem 3.1.

With i.i.d. inputs from a distribution $\mathcal{P}$ over a time horizon $T$,
the regret of LABEL:alg:tcpa-truthful-soft on Section 2 is bounded by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-
soft},\mathcal{P}^{T})\leq O(\sqrt{T}).$

Further, the violation of the RoS constraint is at most $2\sqrt{T}\log T$.

###  3.2 Bound On Constraint Violation of LABEL:alg:tcpa-truthful-soft

To conclude that the constraint described by Section 2 is violated by only a
small amount in LABEL:alg:tcpa-truthful-soft, we observe that when the
cumulative violation is (non-trivially) larger than $1/\alpha$, the
exponential function quickly makes $\lambda_{t}$ huge; in turn, our bid
$b_{t}=v_{t}+\frac{v_{t}}{\lambda_{t}}$ prevents us from over-bidding.
Formally, we show the following result, later used in Theorem 3.1 to obtain
the stated constraint violation bound. (The bound could possibly be sharpened
to get rid of the $\log$.)

######  Lemma 1.

Consider the sequence $\\{\lambda_{t}\\}_{t=1}^{T}$ starting at
$\lambda_{1}=1$ and evolving as $\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha
g_{t}(b_{t})\right]$ where $g_{t}(b_{t})$ satisfies
$g_{t}(b_{t})\geq-\frac{1}{\lambda_{t}}$ and $\alpha=\frac{1}{\sqrt{T}}$.
Then,

$-\sum_{t=1}^{T}g_{t}(b_{t})\leq 2\sqrt{T}\log T.$

###### Proof.

Based on the update rule for $\lambda_{t}$, we know
$\lambda_{t+1}=\exp\left[-\alpha\sum_{t^{\prime}=1}^{t}g_{t^{\prime}}(b_{t^{\prime}})\right]$.
If $-\sum_{t=1}^{T}g_{t}(b_{t})\leq\sqrt{T}\log T$, we are done. If this is
not the case, let $T^{\prime}$ be the last time that
$-\sum_{t=1}^{T^{\prime}}g_{t}(b_{t})\leq\sqrt{T}\log T$, so we know for any
$t>T^{\prime}$, the dual variable $\lambda_{t}$ must be larger than $T$ since

$\lambda_{t}=\exp\left[-\alpha\sum_{t^{\prime}=1}^{t}g_{t^{\prime}}(b_{t^{\prime}})\right]>\exp\left[\alpha\sqrt{T}\log
T\right]=T,$

which suggests

$-g_{t}(b_{t})\leq\frac{1}{\lambda_{t}}\leq\frac{1}{T}\qquad\forall
t>T^{\prime}.$ (3.6)

Thus,

$-\sum_{t=1}^{T}g_{t}(b_{t})=\sum_{t=1}^{T^{\prime}}-g_{t}(b_{t})+\sum_{t>T^{\prime}}-g_{t}(b_{t})\leq\sqrt{T}\log
T+1\leq 2\sqrt{T}\log T,$

where the second step used Equation 3.6 to bound the terms after iteration
$T^{\prime}$ and the fact that there are at most $T$ such iterations. ∎

###  3.3 Bound On Regret of LABEL:alg:tcpa-truthful-soft

We first state the following technical upper bound on the regret, and our
effort in the rest of the section is devoted to bounding the right-hand side
of this result. The proof of the following result (provided in Appendix A)
follows the primal-dual framework in the proof of Theorem 1 in [BLM20].

######  Proposition 3.1.

With i.i.d. inputs from a distribution $\mathcal{P}$ over a time horizon $T$,
the regret of LABEL:alg:tcpa-truthful-soft on Section 2 is bounded by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-
soft},\mathcal{P}^{T})\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\sum_{t\in[T]}\lambda_{t}\cdot
g_{t}(b_{t})\right],$

where $g_{t}$ and $\lambda_{t}$ are as defined in 5 and 6 of LABEL:alg:tcpa-
truthful-soft. We note that the bound on the right-hand side can be negative
since LABEL:alg:tcpa-truthful-soft does not guarantee
$\sum_{t=1}^{T}g_{t}(b_{t})\geq 0$, but we do show a bound on the worst-case
constraint violation in Lemma 1.

Computing a bound on the regret then requires bounding
$\sum_{t=1}^{T}\lambda_{t}\cdot g_{t}(b_{t})$, which we do in the following
lemma (and this is where a major chunk of our technical contribution lies).

######  Lemma 2.

For any input sequence $\overrightarrow{\gamma}$ of length $T$, running
LABEL:alg:tcpa-truthful-soft on Section 2 generates sequences
$\\{b_{t}\\}_{t=1}^{T}$, $\\{g_{t}\\}_{t=1}^{T}$ and
$\\{\lambda_{t}\\}_{t=1}^{T}$ such that for any $\lambda\geq 0$, we have

$\sum_{t=1}^{T}g_{t}(b_{t})\cdot(\lambda_{t}-\lambda)\leq\frac{V_{h}(\lambda,\lambda_{1})}{\alpha}+(1-\lambda_{T})+O(\sqrt{T}),$

where $V_{h}(\cdot,\cdot)$ is the Bregman divergence with $h(u)=u\log u-u$.

###### Proof.

In order to bound the quantity
$\sum_{t\in[T]}g_{t}(b_{t})\cdot(\lambda_{t}-\lambda)$ for any $\lambda\geq
0$, we first write

$\displaystyle\alpha g_{t}(b_{t})\cdot(\lambda_{t}-\lambda)$
$\displaystyle=\alpha g_{t}(b_{t})\cdot(\lambda_{t}-\lambda_{t+1})+\alpha
g_{t}(b_{t})\cdot(\lambda_{t+1}-\lambda).$ (3.7)

From 6 in LABEL:alg:tcpa-truthful-soft, we have

$g_{t}(b_{t})={\alpha}^{-1}\log(\lambda_{t}/\lambda_{t+1}).$

For $h(u)=u\log u-u$, the Bregman divergence
$V_{h}(y,x)=h(y)-h(x)-h^{\prime}(x)\cdot(y-x)$ is

$V_{h}(y,x)=y\log(y/x)-y+x.$

Applying Section 3.3 and Section 3.3 to Equation 3.7 gives

$\displaystyle\alpha g_{t}(b_{t})\cdot(\lambda_{t}-\lambda)$
$\displaystyle=\left[V_{h}(\lambda,\lambda_{t})-V_{h}(\lambda,\lambda_{t+1})\right]+\alpha
g_{t}(b_{t})\cdot(\lambda_{t}-\lambda_{t+1})-V_{h}(\lambda_{t+1},\lambda_{t})$
(3.10)
$\displaystyle\leq\left[V_{h}(\lambda,\lambda_{t})-V_{h}(\lambda,\lambda_{t+1})\right]+\left\\{\alpha
g_{t}(b_{t})\cdot(\lambda_{t}-\lambda_{t+1})-\frac{(\lambda_{t}-\lambda_{t+1})^{2}}{2\max(\lambda_{t},\lambda_{t+1})}\right\\}$
$\displaystyle\leq\left[V_{h}(\lambda,\lambda_{t})-V_{h}(\lambda,\lambda_{t+1})\right]+\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\cdot\max(\lambda_{t},\lambda_{t+1}),$
(3.11)

where the second step follows from the local strong convexity of $V_{h}$ as
shown in [AO14] (for completeness, we prove this fact in Appendix D), and the
final step is by Cauchy-Schwarz inequality. We now bound the term
$\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\cdot\max(\lambda_{t},\lambda_{t+1})$ in
a case-wise manner.

  1. C.1

Assume $g_{t}(b_{t})\geq 0$. Then, the inequality $g_{t}(b_{t})\leq 1$ (from
Proposition A.1) and our choice of $\alpha\leq\frac{1}{\sqrt{T}}$ imply
$\alpha g_{t}(b_{t})\leq\frac{1}{\sqrt{T}}$, which in turn implies

$\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha
g_{t}(b_{t})\right]\leq\lambda_{t}\cdot(1-\alpha
g_{t}(b_{t})/2)=\lambda_{t}-\frac{1}{2}\alpha\lambda_{t}\cdot g_{t}(b_{t}),$

where we used $\exp(-x)\leq 1-x/2$ for $x\in[0,1.5]$. Finally, we use $0\leq
g_{t}(b_{t})\leq 1$ and Item C.1 to obtain:

$\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\max(\lambda_{t},\lambda_{t+1})=\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\lambda_{t}=\alpha\cdot\frac{\alpha
g_{t}(b_{t})\lambda_{t}}{2}\leq\alpha(\lambda_{t}-\lambda_{t+1}).$

  2. C.2

Assume $g_{t}(b_{t})<0$. Then by invoking Proposition A.1, we have $0\geq
g_{t}(b_{t})\geq\max(-1,-1/\lambda_{t})$. This gives

$\alpha^{2}g_{t}(b_{t})^{2}\max(\lambda_{t},\lambda_{t+1})=\alpha^{2}g_{t}(b_{t})^{2}\lambda_{t+1}\leq\frac{1}{T}\cdot\frac{1}{\lambda_{t}}\cdot\lambda_{t+1}.$

Since $g_{t}(b_{t})\geq-1$ and $\alpha=\frac{1}{\sqrt{T}}$, we have $-\alpha
g_{t}(b_{t})\leq 1$. This implies

$\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha g_{t}(b_{t})\right]\leq
e\lambda_{t}.$

Plugging Item C.2 back into Item C.2 gives

$\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\max(\lambda_{t},\lambda_{t+1})\leq\frac{e}{2T}.$

Using $-\alpha g_{t}(b_{t})\leq 1$ again allows us to claim
$\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha
g_{t}(b_{t})\right]\leq\lambda_{t}(1-2\alpha g_{t}(b_{t}))$, where we used
$\exp(x)\leq 1+2x$ for $x\in[0,1]$. Again applying
$\lambda_{t}g_{t}(b_{t})\geq-1$ gives

$\lambda_{t+1}-\lambda_{t}\leq 2\alpha.$

Thus, in all cases, we have

$\frac{1}{2}\alpha^{2}g_{t}(b_{t})^{2}\max(\lambda_{t},\lambda_{t+1})\leq\alpha(\lambda_{t}-\lambda_{t+1})+2\alpha^{2}+\frac{e}{2T}.$

Plug this back in our previous bound in Equation 3.11, we get

$\displaystyle\alpha g_{t}(\lambda_{t}-\lambda)$
$\displaystyle\leq\left[V_{h}(\lambda,\lambda_{t})-V_{h}(\lambda,\lambda_{t+1})\right]+\alpha(\lambda_{t}-\lambda_{t+1})+2\alpha^{2}+\frac{e}{2T}.$

Dividing throughout by $\alpha$ and summing over $t=1,2,\dots,T$, enables
telescoping; plugging in the chosen values of $\lambda_{1}$ and $\alpha$ from
LABEL:alg:tcpa-truthful-soft then yields the claimed bound. ∎

##  4 Bidding Under a Strict RoS Constraint

In this section, we introduce a simple technique that turns an algorithm with
non-zero (but bounded) violation of the RoS constraint into one _strictly_
obeying it. As noted in Section 5, this technique extends to the problem with
_both_ RoS and budget constraints. Our idea is as follows.

Suppose we have an algorithm (say, $\mathsf{Alg}$), which can guarantee an at
most $v_{\mathsf{RoS}}$ violation of the RoS constraint on any sequence
$\overrightarrow{\gamma}$ of input requests. We start by bidding the true
value $b_{t}=v_{t}$ in the initial iterations
$t=1,\ldots,K(\overrightarrow{\gamma})$ for some $K(\overrightarrow{\gamma})$
— we call this sequence of iterations the _first phase_. In a truthful
auction, this choice of bids guarantees $g_{t}(b_{t})=v_{t}\cdot
x_{t}(b_{t})-p_{t}(b_{t})\geq 0$ for all $t\leq K(\overrightarrow{\gamma})$.
In other words, the bidder builds up a buffer on the RoS constraint. We
continue until the cumulative buffer
$\sum_{t=1}^{K(\overrightarrow{\gamma})}g_{t}(b_{t})$ increases to at least
$v_{\mathsf{RoS}}$. Starting at iteration $K(\overrightarrow{\gamma})+1$, we
run $\mathsf{Alg}$ afresh (i.e. without accounting for the first phase);
recall, this violates the RoS constraint by at most $v_{\mathsf{RoS}}$ over
the remaining iterations. We refer to this run of $\mathsf{Alg}$ as the
_second phase_. Since the buffer from the first phase is enough to offset
$\mathsf{Alg}$’s violation in the second phase, there is no violation of the
RoS constraint at the end. We display this idea in Algorithm 4.1.

Algorithm 4.1 Bidding algorithm of the RoS agent operating under strict
constraints in truthful auctions (i.i.d. inputs)

1:Input: Total time horizon $T$ and requests $\overrightarrow{\gamma}$ from
the data distribution $\mathcal{P}^{T}$.

2:Initialize: Set $v_{\mathsf{RoS}}=2\sqrt{T}\log T$ and $t=1$.

3:while $\sum_{i=1}^{t-1}g_{i}(b_{i})\leq v_{\mathsf{RoS}}$ do
$\triangleright$ First phase

4: Observe the value $v_{t}$, and set the bid $b_{t}=v_{t}$.

5: Observe the price $p_{t}$ and the allocation $x_{t}$ at $b_{t}$, and
compute $g_{t}(b_{t}):=v_{t}\cdot x_{t}(b_{t})-p_{t}(b_{t})$.

6: Increment the iteration count $t=t+1$.

7:end while

8:Run LABEL:alg:tcpa-truthful-soft with time horizon $T-t$ and the remaining
$T-t$ requests from $\overrightarrow{\gamma}$ as input. $\triangleright$
Second phase

9:return The sequence $\\{b_{t}\\}_{t=1}^{T}$ of generated bids from both
phases.

###  4.1 Analysis of Algorithm 4.1

The high-level idea to guarantee a low regret for Algorithm 4.1 is to start
with the observation that the reward collected by Algorithm 4.1 for any
$\overrightarrow{\gamma}$ in $T$ steps is at least that collected by
LABEL:alg:tcpa-truthful-soft in the second phase (i.e., the last
$T-K(\overrightarrow{\gamma})$ steps). The second phase suffers (in
expectation) a regret bounded by the guarantee of Theorem 3.1. We then use the
i.i.d. assumption on the input sequence to bound the gap between the expected
reward collected by $\mathsf{Opt}$ in a sequence of length
$T-K(\overrightarrow{\gamma})$ to that in a sequence of length $T$, which
naturally depends on the expected length of $K(\overrightarrow{\gamma})$;
finally, we show this expected length is at most $O(\sqrt{T}\log T)$ under a
mild technical assumption on the input distribution; this bounds the
additional regret accrued over the first phase and completes the analysis.

To formally see this, we need two simple technical tools (proved in Appendix
B) as follows. First, we make the following assumption on the distribution
$\mathcal{P}$ and state a corresponding result.

######  Assumption 3.

Define the parameter $\beta$ of a distribution $\mathcal{P}$ as follows

$\beta=\mathbb{E}_{v,p,x\sim\mathcal{P}}\left[\max(0,v\cdot x(v)-p(v)\right].$

We assume in our problem $\beta$ is an absolute constant bounded away from $0$
and independent of $T$.

The parameter $\beta$ is the expected amount of buffer we accrue per iteration
during the first phase. The assumption of $\beta$ being a constant bounded
away from $0$ captures the more interesting scenarios of bidding under RoS.
For example, when the allocation and price functions of each query arise from
a single-item second-price auction, the essence of the problem becomes how
best to spend the extra slack $v_{t}-p_{t}(v_{t})$ gained from queries with
$v_{t}>p(v_{t})$. If $\beta$ is tiny, or in the extreme case of $\beta=0$,
there is nothing to optimize for, and the optimal solution would simply be
$b_{t}=v_{t}$ all the time.

Since we need to only accrue a buffer of size $O(\sqrt{T}\log T)$, and the
expected increment of the buffer is a constant $\beta$ per iteration, we can
show the first phase finishes in $O(\sqrt{T}\log T)$ iterations in
expectation.

######  Proposition 4.1.

Under Assumption 3 for the distribution $\mathcal{P}$, let
$K(\overrightarrow{\gamma})$ be the number of iterations in the first phase of
Algorithm 4.1 for some input sequence $\overrightarrow{\gamma}$. Then, we have

$\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}[K(\overrightarrow{\gamma})]\leq
O(\sqrt{T}\log T).$

We also need the following technical statement on the difference in reward
collected by LABEL:alg:tcpa-truthful-soft and $\mathsf{Opt}$ for various
lengths of input sequences.

######  Proposition 4.2.

Let $\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}$ and
$\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}$ be sequences of lengths
$\ell$ and $r$, respectively, with $\ell\leq r$, of i.i.d. requests each from
a distribution $\mathcal{P}$. Then the following inequality holds.

$\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:tcpa-
truthful-
soft},\overrightarrow{\gamma}_{\\!\ell})\right]\geq\frac{\ell}{r}\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!r})\right]-O(\sqrt{r}).$

The above two results help us bound the regret from the first phase, and we
can use the guarantee from Theorem 3.1 to bound the regret due to the second
phase. Altogether we get the main result below.

######  Theorem 4.1.

With i.i.d. inputs from a distribution $\mathcal{P}$ over a time horizon $T$,
the regret of Algorithm 4.1 on Section 2 is bounded by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:meta-strictconstraints-
tcpa},\mathcal{P}^{T})\leq O(\sqrt{T}\log T).$

Further, there is no violation of the RoS constraint in Section 2.

###### Proof.

The claim on constraint violation follows by design of the algorithm: we
collect a constraint violation buffer of at least $v_{\mathsf{RoS}}$ before
starting the second phase, in which we are guaranteed to violate the
constraint by an additive factor of at most $v_{\mathsf{RoS}}$.

We now prove the claimed regret bound by combining a lower bound on the
expected reward and an upper bound on the expected optimum. To lower bound the
algorithm’s reward, we note that it is at least the reward from the second
phase.

Let $K(\overrightarrow{\gamma})$ be the random variable that represents the
last iteration of the first phase, after which we run LABEL:alg:tcpa-truthful-
soft. In this proof, we use $\overrightarrow{\gamma}_{\\!\\!a:b}$ to denote
the sequence $\overrightarrow{\gamma}$ from time steps $a$ through $b$; when
these end points do not matter, we simply denote a length $T$ sequence as
$\overrightarrow{\gamma}$. With this notation, we have for any sequence
$\overrightarrow{\gamma}$:

$\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:meta-strictconstraints-
tcpa},\overrightarrow{\gamma})\geq\sum_{t=K(\overrightarrow{\gamma})+1}^{T}v_{t}\cdot
x_{t}(b_{t}).$

Then taking expectations on both sides and using conditional expectations
gives

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:meta-
strictconstraints-tcpa},\overrightarrow{\gamma})\right]$
$\displaystyle\geq\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}\mid
K(\overrightarrow{\gamma})=k}\left[\sum_{t=k+1}^{T}v_{t}\cdot x_{t}(b_{t})\mid
K(\overrightarrow{\gamma})=k\right]\right]$
$\displaystyle=\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:tcpa-
truthful-soft},\overrightarrow{\gamma}_{\\!\\!k+1:T})\right]\right]$
$\displaystyle\geq\mathbb{E}_{k}\left[\frac{T-k}{T}\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})\right]\right]-O(\sqrt{T}),$
(4.1)

where the third step is due to the requests all being i.i.d. and the fact that
we start running LABEL:alg:tcpa-truthful-soft fresh in the second phase, and
the fourth step is by Proposition 4.2. Finally, plugging Equation 4.1 into the
definition of $\mathsf{Regret}$ from Section 2 and simplifying gives

$\displaystyle\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:meta-
strictconstraints-tcpa},\mathcal{P}^{T})$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[K(\overrightarrow{\gamma})\right]\cdot\frac{\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})\right]}{T}+O(\sqrt{T})$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[K(\overrightarrow{\gamma})\right]+O(\sqrt{T})=O(\sqrt{T}\log
T),$

where in the third step we use
$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})\leq T$, and in the last
step we use Proposition 4.1 and Assumption 3 that $\beta$ is a constant. ∎

Although we structure the algorithm as the first phase followed by the second
phase for the purpose of the analysis, the value of $v_{\mathsf{RoS}}$ can be
a pessimistic bound and make us run the first phase for an unnecessarily long
time. A more practical implementation can break the first phase into smaller
chunks and intermingle them with the execution of LABEL:alg:tcpa-truthful-soft
on demand. That is, whenever we are about to violate the RoS constraint during
LABEL:alg:tcpa-truthful-soft, we put it on hold and bid exactly the value
$v_{t}$ for some iterations until we build up a certain amount of buffer and
then resume the execution of LABEL:alg:tcpa-truthful-soft, where these special
iterations are ignored (i.e., won’t affect the dual variable updates).
Intuitively this can perform better than Algorithm 4.1, although without a
rigorous regret guarantee.

##  5 Bidding Under Both RoS and Budget Constraints

In this section, we combine our techniques from Section 3 and Section 4 with
those of [BLM20] to obtain bidding algorithms that satisfy _both_ the RoS and
budget constraints (i.e., Section 2). More specifically, we propose
LABEL:alg:combined-truthful-soft to solve Section 2 under a strict imposition
of the budget constraint and only an approximate one on the RoS constraint and
Algorithm 5.2 to strictly satisfy _both_ the RoS and budget constraints.

###  5.1 Approximate RoS and Strict Budget Constraints

We start with a bidding algorithm that satisfies the budget constraint exactly
and the RoS constraint up to some small violation in the worst case. Similar
to the bidding rule in Section 3, the candidate bid for this algorithm is the
one maximizing the price-adjusted reward, with one dual variable for each
constraint:

$\displaystyle b_{t}=\arg\max_{b\geq 0}\left\\{v_{t}\cdot
x_{t}(b)+\lambda_{t}\cdot(v_{t}\cdot x_{t}(b)-p_{t}(b))-\mu_{t}\cdot
p_{t}(b)\right\\}$
$\displaystyle=\frac{1+\lambda_{t}}{\mu_{t}+\lambda_{t}}\cdot v_{t},$ (5.1)

where the solution to the maximization holds by the definition of a truthful
auction. Since we are in the setting where the budget constraint is strict,
the candidate bid given by Equation 5.1 is used as the final bid in this
iteration only if we are not close to exhausting the total budget, as
formalized in 4 of LABEL:alg:combined-truthful-soft. Similar to
LABEL:alg:tcpa-truthful-soft, the Lagrange multipliers $\lambda_{t}$ and
$\mu_{t}$ serve to enforce the RoS and budget constraints respectively.

We remark that LABEL:alg:combined-truthful-soft may be interpreted as
combining our LABEL:alg:tcpa-truthful-soft with Algorithm 1 of [BLM20]. The
analysis of the regret bound also follows the outline of the main proof of
[BLM20], integrating it with our regret bound for LABEL:alg:tcpa-truthful-soft
from Theorem 3.1. Intuitively the integration is straightforward since the
analyses of both methods are linear in nature, allowing us to easily decompose
the intermediate regret bound from the primal-dual framework into two
components corresponding to the two constraints. We then bound them
respectively with the same techniques from earlier sections to handle the RoS
constraint and the techniques from [BLM20] to address the budget constraint.

As for the constraint violation guarantees, the budget constraint is always
satisfied by design, and the RoS violation bound follows from a simple
corollary of Lemma 1, which applies here since the extra budget constraint
makes our bid only _more_ conservative than that of LABEL:alg:tcpa-truthful-
soft. We formally collect and state these results in Theorem 5.1, proving it
in Section C.1.

Algorithm 5.1 Bidding algorithm of the agent operating under approximate RoS
constraints and strict budget constraints in a truthful auction (i.i.d.
inputs)

alg]alg:combined-truthful-soft

1:Input: Total time horizon $T$, requests $\overrightarrow{\gamma}$ i.i.d.
from the distribution $\mathcal{P}^{T}$, total budget $\rho T$.

2:Initialize: Initial dual variable $\lambda_{1}=1$, $\mu_{1}=0$, total
initial budget $B_{1}:=\rho T$, dual mirror descent step size
$\alpha=\frac{1}{\sqrt{T}}$ and $\eta=\frac{1}{(1+\rho^{2})\sqrt{T}}$.

3:for $t=1,2,\cdots,T$ do

4: Observe the value $v_{t}$, and set the bid
$b_{t}=\left\\{\begin{array}[]{ll}\frac{1+\lambda_{t}}{\mu_{t}+\lambda_{t}}\cdot
v_{t}&\mbox{if }B_{t}\geq 1\\\ 0&\mbox{if
}\text{otherwise}\end{array}\right.$.

5: Compute $g_{t}(b_{t})=v_{t}\cdot x_{t}({b}_{t})-p_{t}(b_{t})$.

6: Update the dual variable of the RoS constraint as
$\lambda_{t+1}=\lambda_{t}\exp\left[-\alpha\cdot g_{t}(b_{t})\right]$.

7: Compute $g_{t}^{\prime}(b_{t})=\rho-p_{t}(b_{t})$.

8: Update the dual variable of the budget constraint as
$\mu_{t+1}:=\mathrm{Proj}_{\mu\geq 0}(\mu_{t}-\eta\cdot
g_{t}^{\prime}(b_{t}))$.

9: Update the leftover budget $B_{t+1}=B_{t}-p_{t}(b_{t})$.

10:end for

11:return The sequence $\\{b_{t}\\}_{t=1}^{T}$ of bids.

######  Theorem 5.1.

With i.i.d. inputs from a distribution $\mathcal{P}$ over a time horizon $T$,
the regret of LABEL:alg:combined-truthful-soft on Section 2 is bounded by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:combined-truthful-
soft},\mathcal{P}^{T})\leq O(\sqrt{T}).$

Further, LABEL:alg:combined-truthful-soft incurs a violation of at most
$O(\sqrt{T}\log T)$ of the RoS constraint and no violation of the budget
constraint.

###  5.2 Strict RoS and Strict Budget Constraints

In the case when we impose both strict RoS and strict budget constraints, we
essentially combine the key ideas from Algorithm 4.1 and LABEL:alg:combined-
truthful-soft: We keep bidding the value until we accumulate a sufficient
buffer on the RoS constraint; following this phase, we run LABEL:alg:combined-
truthful-soft, which, as explained in the preceding section, imposes strict
budget and approximate RoS constraints.

By the same reasoning as for Algorithm 4.1, the RoS constraint is not
violated; the budget constraint is also respected via 8 of Algorithm 5.2. The
regret analysis follows a strategy similar to that of the proofs of Theorem
5.1 and Theorem 4.1. Our main result of this section is in Theorem 5.2, with
its proof in Section C.2.

Algorithm 5.2 Bidding algorithm of the agent operating under strict RoS and
strict budget constraints in truthful auctions (i.i.d. inputs)

1:Input: Total time horizon $T$, requests $\overrightarrow{\gamma}$ i.i.d.
from the distribution $\mathcal{P}^{T}$, total budget $\rho T$.

2:Initialize: Set the initial buffer $g_{0}(b_{0})=0$,
$v_{\mathsf{RoS}}=2\sqrt{T}\log T$, initial total budget $B_{1}=\rho T$, and
iteration $t=1$.

3:while $\sum_{i=0}^{t-1}g_{i}(b_{i})\leq v_{\mathsf{RoS}}$ do
$\triangleright$ First phase

4: Observe the value $v_{t}$, and set the bid $b_{t}=v_{t}$.

5: Observe the price $p_{t}$ and the allocation $x_{t}$ at $b_{t}$, and
compute $g_{t}(b_{t}):=v_{t}\cdot x_{t}(b_{t})-p_{t}(b_{t})$.

6: Update the total budget to $B_{t+1}=B_{t}-p_{t}(b_{t})$.

7: Increment the iteration count $t=t+1$.

8: if $t\geq\rho T$ then

9: Exit algorithm.

10: end if

11:end while

12:Run LABEL:alg:combined-truthful-soft with time horizon $T-t$ and the
remaining $T-t$ requests from $\overrightarrow{\gamma}$ as input and initial
total budget $B_{t}$. $\triangleright$ Second phase

13:return The sequence $\\{b_{t}\\}_{t=1}^{T}$ of generated bids.

######  Theorem 5.2.

With i.i.d. inputs from a distribution $\mathcal{P}$ over a time horizon $T$,
the regret of Algorithm 5.2 on Section 2 is bounded by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:combined-truthful-
strict},\mathcal{P}^{T})\leq O(\sqrt{T}\log T).$

Further, Algorithm 5.2 suffers no constraint violation of either the RoS or
budget constraint.

## Acknowledgement

We thank Aranyak Mehta for suggesting and help formulating the problem. We are
grateful to Santiago Balseiro, Kshipra Bhawalkar Lane, Haihao Lu, Vahab
Mirrokni, and Balasubramanian Sivan for helpful discussions throughout the
project.

## References

  * [ABM19] Gagan Aggarwal, Ashwinkumar Badanidiyuru and Aranyak Mehta  “Autobidding with constraints”  In _International Conference on Web and Internet Economics_ , 2019, pp. 17–30  Springer
  * [AD14] Shipra Agrawal and Nikhil R Devanur  “Fast algorithms for online stochastic convex programming”  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , 2014, pp. 1405–1424  SIAM
  * [AO14] Zeyuan Allen-Zhu and Lorenzo Orecchia  “Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel”  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , 2014, pp. 1439–1456  SIAM
  * [BCHIL21] Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica and Brendan Lucier  “Non-Quasi-Linear Agents in Quasi-Linear Mechanisms”  In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_ , 2021  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [BCIJEM07] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami and Mohammad Mahdian  “Dynamics of bid optimization in online advertisement auctions”  In _Proceedings of the 16th international conference on World Wide Web_ , 2007, pp. 531–540
  * [BDMMZ21] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni and Song Zuo  “Robust Auction Design in the Auto-bidding World”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 17777–17788
  * [BDMMZ21a] Santiago R Balseiro, Yuan Deng, Jieming Mao, Vahab S Mirrokni and Song Zuo  “The landscape of auto-bidding auctions: Value versus utility maximization”  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 2021, pp. 132–133
  * [BFG21] Ashwinkumar Badanidiyuru, Zhe Feng and Guru Guruganesh  “Learning to Bid in Contextual First Price Auctions”  In _CoRR_ abs/2109.03173, 2021  arXiv:2109.03173
  * [BG19] Santiago R Balseiro and Yonatan Gur  “Learning in repeated auctions with budgets: Regret minimization and equilibrium”  In _Management Science_ 65.9 INFORMS, 2019, pp. 3952–3968
  * [BLM20] Santiago Balseiro, Haihao Lu and Vahab Mirrokni  “Dual Mirror Descent for Online Allocation Problems”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 613–628
  * [Bub+15] Sébastien Bubeck  “Convex optimization: Algorithms and complexity”  In _Foundations and Trends® in Machine Learning_ 8.3-4 Now Publishers, Inc., 2015, pp. 231–357
  * [CKPSSSW22] Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka and Christopher A Wilkens  “Pacing Equilibrium in First Price Auction Markets”  In _Management Science_ INFORMS, 2022
  * [CKSS22] Vincent Conitzer, Christian Kroer, Eric Sodomka and Nicolas E Stier-Moses  “Multiplicative pacing equilibria in auction markets”  In _Operations Research_ 70.2 INFORMS, 2022, pp. 963–989
  * [DH09] Nikhil R Devanur and Thomas P Hayes  “The adwords problem: online keyword matching with budgeted bidders under random permutations”  In _Proceedings of the 10th ACM conference on Electronic commerce_ , 2009, pp. 71–78
  * [DMMZ21] Yuan Deng, Jieming Mao, Vahab Mirrokni and Song Zuo  “Towards efficient auctions in an auto-bidding world”  In _Proceedings of the Web Conference 2021_ , 2021, pp. 3965–3973
  * [FPS18] Zhe Feng, Chara Podimata and Vasilis Syrgkanis  “Learning to Bid Without Knowing Your Value”  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , 2018, pp. 505–522
  * [GJLM21] Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang and Vahab Mirrokni  “Bidding and Pricing in Budget and ROI Constrained Markets”  In _arXiv preprint arXiv:2107.07725_ , 2021
  * [HZFOW20] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich and Tsachy Weissman  “Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions”  In _CoRR_ abs/2007.04568, 2020  arXiv:2007.04568
  * [MSVV07] Aranyak Mehta, Amin Saberi, Umesh Vazirani and Vijay Vazirani  “Adwords and generalized online matching”  In _Journal of the ACM (JACM)_ 54.5 ACM New York, NY, USA, 2007, pp. 22–es
  * [Mye81] Roger B Myerson  “Optimal auction design”  In _Mathematics of operations research_ 6.1 INFORMS, 1981, pp. 58–73
  * [NCKP22] Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui and Vianney Perchet  “Learning in Repeated Auctions”  In _Foundations and Trends® in Machine Learning_ 15.3, 2022, pp. 176–334  DOI: 10.1561/2200000077
  * [NS21] Gali Noti and Vasilis Syrgkanis  “Bid Prediction in Repeated Auctions with Learning”  In _Proceedings of the Web Conference 2021_ , WWW ’21  Ljubljana, Slovenia: Association for Computing Machinery, 2021, pp. 3953–3964
  * [WPR16] Jonathan Weed, Vianney Perchet and Philippe Rigollet  “Online learning in repeated auctions”  In _Conference on Learning Theory_ , 2016, pp. 1562–1583  PMLR

In this section, we provide all the proofs that have been omitted from the
main body. The proofs appear here in the order in which the corresponding
results are stated in the main body and are organized by sections
corresponding to the main body.

##  Appendix A Proofs of the Approximate RoS Constraint

######  Proposition A.1.

Let $g_{t}$ be as defined in Section 2 and $p_{t}$ be as defined in Section 2.
Let $b_{t}\leq\frac{1+\lambda_{t}}{\lambda_{t}}\cdot v_{t}$. Then we have

$\max(-1/\lambda_{t},-1)\leq g_{t}(b_{t})\leq v_{t}\cdot x_{t}(b_{t}).$

###### Proof.

The non-negativity of $v_{t}$ and $x_{t}$ along with the bound $p_{t}(b)\leq
1$ immediately give $g_{t}(b_{t})\geq-1$. Further, the non-negativity of
$p_{t}$ from Section 2 gives the upper bound $g_{t}(b_{t})\leq v_{t}\cdot
x_{t}(b_{t})$. Using the exact expression for $p_{t}$ from Section 2, along
with non-negativity of $x_{t}$, the stated assumption on $b_{t}$, and
$v_{t},x_{t}\leq 1$ gives gives

$\displaystyle g_{t}(b_{t})$ $\displaystyle=(v_{t}-b_{t})\cdot
x_{t}(b_{t})+\int_{z=0}^{b}x_{t}(z)dz\geq(v_{t}-b_{t})\cdot
x_{t}(b_{t})\geq-\frac{v_{t}}{\lambda_{t}}\cdot
x_{t}(b_{t})\geq-\frac{1}{\lambda_{t}}.$

∎

See 3.1

The proof of this result essentially follows the outline in [BLM20]. We prove
it in two parts: an upper bound on the expected optimal value followed by a
lower bound on the expected reward of LABEL:alg:tcpa-truthful-soft. To prove
the former, we go through the primal-dual framework, for which need the
following technical definitions.

######  Definition A.1.

We define the following dual variables.

  * •

Let $f_{t}(b):=v_{t}\cdot x_{t}(b)$, recall $g_{t}$ from Section 2, for some
fixed $\lambda\geq 0$, define

$f_{t,\mathsf{RoS}}^{\star}(\lambda):=\max_{b\geq
0}\left[f_{t}(b)+\lambda\cdot g_{t}(b)\right].$ (A.1)

  * •

Let $f^{\star}$ be defined as in Equation A.1. Then we define the following
dual variable parametrized by the input distribution $\mathcal{P}$.

$\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P}):=\mathbb{E}_{(v,p)\sim\mathcal{P}}\left[f^{\star}_{\mathsf{RoS}}(\lambda)\right].$
(A.2)

The proof outline is to first show an upper bound on the expected optimal
reward via weak duality then a lower bound on the expected reward collected by
our algorithm.

######  Proposition A.2.

Recall $\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P})$ as defined
in Equation A.2. Then the optimum value
$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})$ for Section 2 defined
for a sequence $\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}$ of
$\ell$ requests satisfies the inequality

$\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell})\right]\leq\ell\cdot\min_{\lambda\geq
0}\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P}).$

###### Proof.

We have, by the definition of
$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})$ in Section 2 and the
definition of $g_{t}$ in Section 2 that

$\displaystyle\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell})$
$\displaystyle=\max_{\\{b_{t}\\}:\sum_{t=1}^{\ell}g_{t}(b_{t})\geq
0}\sum_{t=1}^{\ell}f_{t}(b_{t})$
$\displaystyle=\max_{\\{b_{1},b_{2},\dots,b_{\ell}\\}}\left\\{\sum_{t=1}^{\ell}f_{t}(b_{t})+\min_{\lambda\geq
0}\lambda\cdot\left[\sum_{t=1}^{\ell}g_{t}(b_{t})\right]\right\\}$
$\displaystyle=\max_{\\{b_{1},b_{2},\dots,b_{\ell}\\}}\min_{\lambda\geq
0}\left\\{\sum_{t=1}^{\ell}\left[f_{t}(b_{t})+\lambda\cdot
g_{t}(b_{t})\right]\right\\}.$

By Sion’s min-max theorem and by the definition of
$f_{t,\mathsf{RoS}}^{\star}$ in Equation A.1, we have that

$\displaystyle\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell})$
$\displaystyle\leq\min_{\lambda\geq
0}\max_{\\{b_{1},b_{2},\dots,b_{\ell}\\}}\left\\{\sum_{t=1}^{\ell}\left[f_{t}(b_{t})+\lambda\cdot
g_{t}(b_{t})\right]\right\\}$ $\displaystyle\leq\min_{\lambda\geq
0}\left\\{\sum_{t=1}^{\ell}\max_{b_{t}}\left[f_{t}(b_{t})+\lambda\cdot
g_{t}(b_{t})\right]\right\\}$ $\displaystyle=\min_{\lambda\geq
0}\left\\{\sum_{t=1}^{\ell}f_{t,\mathsf{RoS}}^{\star}(\lambda)\right\\}\leq\sum_{t=1}^{\ell}f_{t,\mathsf{RoS}}^{\star}(\lambda^{\prime}),\text{
for any $\lambda^{\prime}\geq 0$}.$ (A.3)

Now taking expectations666The expectation is over the randomness in the
sequence of requests $\overrightarrow{\gamma}_{\\!\ell}$ over the time horizon
$\ell$. on both sides of Equation A.3 and using the definition of
$\overline{\mathcal{D}}_{\mathsf{RoS}}$ from Equation A.2 gives, for any fixed
$\lambda^{\prime}\geq 0$,

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell})\right]\leq\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\sum_{t=1}^{\ell}f_{t,\mathsf{RoS}}^{\star}(\lambda^{\prime})\right]=\sum_{t=1}^{\ell}\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[f_{t,\mathsf{RoS}}^{\star}(\lambda^{\prime})\right]$
$\displaystyle=\ell\cdot\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda^{\prime}|\mathcal{P}).$

where the final equation crucially uses the fact that all $t$ requests are
drawn i.i.d. from the same distribution $\mathcal{P}$ and the argument
$\lambda^{\prime}>0$ is fixed. Therefore, in particular, the preceding
inequality holds for the specific $\lambda^{\prime}$ that minimizes the right-
hand side, thus finishing the proof. ∎

######  Proposition A.3.

For some fixed number $r$, let
$\overline{\lambda}_{r}:=\frac{1}{r}\sum_{t=1}^{r}\lambda_{t}$, where
$\lambda_{t}$ are the dual iterates in LABEL:alg:tcpa-truthful-soft. Then, the
reward (see Section 2) of LABEL:alg:tcpa-truthful-soft is lower bounded as

$\displaystyle\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-
soft},\overrightarrow{\gamma}_{\\!r})$
$\displaystyle\geq\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[r\cdot\overline{\mathcal{D}}_{\mathsf{RoS}}(\overline{\lambda}_{r}|\mathcal{P})\right]-\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\sum_{t=1}^{r}\lambda_{t}\cdot
g_{t}(b_{t})\right].$

###### Proof.

Recall we have by 4 in LABEL:alg:tcpa-truthful-soft and by the definition of
$f_{t,\mathsf{RoS}}^{\star}$ in Equation A.1,

$f_{t}(b_{t})=f_{t,\mathsf{RoS}}^{\star}(\lambda_{t})-\lambda_{t}\cdot
g_{t}(b_{t}).$

Taking expectations on both sides by conditioning on the randomness until (and
including) iteration $t-1$, we have,

$\displaystyle\mathbb{E}\left[f_{t}(b_{t})|\sigma_{t-1}\right]$
$\displaystyle=\mathbb{E}\left[f_{t,\mathsf{RoS}}^{\star}(\lambda_{t})|\sigma_{t-1}\right]-\mathbb{E}\left[\lambda_{t}\cdot
g_{t}(b_{t})|\sigma_{t-1}\right]$
$\displaystyle=\mathbb{E}_{(v,p)\sim\mathcal{P}}\left[f^{\star}_{\mathsf{RoS}}(\lambda_{t})\right]-\mathbb{E}\left[\lambda_{t}\cdot
g_{t}(b_{t})|\sigma_{t-1}\right]$
$\displaystyle=\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda_{t}|\mathcal{P})-\mathbb{E}\left[\lambda_{t}\cdot
g_{t}(b_{t})|\sigma_{t-1}\right],$

where the second step used the fact that in LABEL:alg:tcpa-truthful-soft, the
$\lambda_{t}$ is fixed when $\sigma_{t-1}$ is, and the final step used the
definition of $\overline{\mathcal{D}}_{\mathsf{RoS}}$ in Equation A.2. Summing
over $t=1,2,\dotsc,r$ and taking expectations (this is a valid operation since
$r$ is a fixed number) gives,

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\sum_{t=1}^{r}f_{t}(b_{t})\right]$
$\displaystyle=\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\sum_{t=1}^{r}\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda_{t}|\mathcal{P})\right]-\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\sum_{t=1}^{r}\lambda_{t}\cdot
g_{t}(b_{t})\right],$

and we may finish the proof by invoking convexity of
$f^{\star}_{\mathsf{RoS}}$. ∎

###### Proof of Proposition 3.1.

We begin by restating the result from Proposition A.2 for an input sequence of
length $T$:

$\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})\right]\leq
T\cdot\min_{\lambda\geq
0}\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P}).$

The minimum on the right-hand side of the preceding inequality can be further
bounded as follows for any $\lambda(\overrightarrow{\gamma})\geq 0$.

$T\cdot\min_{\lambda\geq
0}\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P})\leq
T\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda(\vec{\gamma})|\mathcal{P})\right].$

In particular, then, we may choose
$\lambda(\overrightarrow{\gamma})=\frac{1}{T}\sum_{t=1}^{T}\lambda_{t}:=\overline{\lambda}_{T}$
on the right-hand side of Appendix A and combine with Appendix A to obtain

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma})\right]\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[T\cdot\overline{\mathcal{D}}_{\mathsf{RoS}}(\overline{\lambda}_{T}|\mathcal{P})\right].$
(A.6)

Combining this with Proposition A.3 applied to an input sequence of length $T$
finishes the proof. ∎

See 3.1

###### Proof.

For any outcome of the drawing of
$\overrightarrow{\gamma}\sim\mathcal{P}^{T}$, we can use $\lambda=1/T$ in
Lemma 2, and get

$\displaystyle\sum_{t=1}^{T}\lambda_{t}\cdot
g_{t}(b_{t})\leq\sum_{t=1}^{T}g_{t}(b_{t})/T+V_{h}(1/T,1)/\alpha+O(\sqrt{T})\leq
O(\sqrt{T}),$ (A.7)

using that $\sum_{t=1}^{T}g_{t}(b_{t})\leq\sum_{t=1}^{T}v_{t}\cdot
x_{t}(b_{t})\leq T$, and $V_{h}(1/T,1)\leq 1$ for $h(u)=u\log u-u$, and
$\alpha=1/\sqrt{T}$. Plugging this into Proposition 3.1 gives the regret
bound.

To see the claim on constraint violation, we first note from Proposition A.1
that the gradients $g_{t}$ in LABEL:alg:tcpa-truthful-soft satisfy
$g_{t}(b_{t})\geq-1/\lambda_{t}$. Therefore, the result of Lemma 1 applies;
note that constraint violation of LABEL:alg:tcpa-truthful-soft corresponds
precisely to $-\sum_{t=1}^{T}g_{t}(b_{t})$. ∎

###  A.1 Approximate RoS Constraints Using the Squared Mirror Map

Algorithm A.1 Algorithm for bidding under a RoS constraint in truthful
auctions with squared regularizer

1:Input: Total time horizon $T$ and requests $\overrightarrow{\gamma}$ from
the data distribution $\mathcal{P}^{T}$

2:Initialize: Dual variable $\lambda_{1}=1$, step size for dual update
$\alpha$, and mirror map $h({}\cdot{})=\frac{1}{2}\|{}\cdot{}\|^{2}_{2}$.

3:for $t=1,2,\cdots,T$ do

4: Observe the realization of the valuation $v_{t}$, and set the bid:
$b_{t}=\frac{v_{t}}{\lambda_{t}}+v_{t}$.

5: Observe $p_{t}$ and $x_{t}$ evaluated at the chosen bid $b_{t}$ and compute
$g_{t}(b_{t})=v_{t}\cdot x_{t}({b}_{t})-p_{t}({b}_{t}).$

6: Update the dual variable corresponding to the RoS constraint:
$\lambda_{t+1}=(\lambda_{t}-\alpha g_{t}(b_{t}))_{+}$

7:end for

8:return The sequence $\\{b_{t}\\}_{t=1}^{T}$ of generated bids.

######  Lemma 4.

The regret, as defined in Section 2, of Algorithm A.1, run on Section 2, with
i.i.d. inputs from distribution $\mathcal{P}$ over a time horizon $T$ is
bounded from above by $2\alpha T+\alpha^{-1}$.

###### Proof.

We observe that the regularizer $h(u)=\frac{1}{2}u^{2}$ is $1$-strongly convex
on the non-negative orthant, which implies we can use Proposition 3.1 and
mirror descent error bounds (Lemma 6) to bound the average regret as

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-soft-
squared},\mathcal{P}^{T})\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\sum_{t=1}^{T}\lambda^{*}\cdot
g_{t}(b_{t})\right]+2\alpha
T+\frac{V_{h}(\lambda^{\ast},\lambda_{1})}{\alpha}.$

By choosing $\lambda^{\ast}=0$ (and using $\lambda_{1}=1$) in this bound
yields the claimed regret bound. ∎

######  Lemma 5.

Running Algorithm A.1 on Section 2 yields a constraint violation of at most
$\frac{T^{c}}{\alpha}+T^{1-c}$ for some parameter $c>0$.

###### Proof.

Based on the dual update rule in Algorithm A.1,
$\lambda_{t+1}\geq\lambda_{t}-\alpha g_{t}(b_{t})$, as a result of which
$g_{t}(b_{t})\geq\frac{1}{\alpha}(\lambda_{t}-\lambda_{t+1})$. Let $c>0$. Let
$T^{\prime}$ be the last time step at which $\lambda_{T^{\prime}}\leq T^{c}$.
Then, $\sum_{t=1}^{T^{\prime}}g_{t}(b_{t})\geq-{T}^{c}/\alpha$ and applying
$g_{t}(b_{t})\geq-1/\lambda_{t}$ (which comes from Proposition A.1) with
$\lambda_{t}\geq T^{c}$ for $t\geq T^{\prime}$ gives
$\sum_{t=T^{\prime}}^{T}g_{t}(b_{t})\geq-T^{1-c}$. Therefore, we have
$\sum_{t=1}^{T}g_{t}(b_{t})\geq-T^{c}/\alpha-T^{1-c}$. ∎

######  Corollary A.1.

The regret, defined in Section 2, of Algorithm A.1 run on Section 2, with
i.i.d.i̇nputs from a distribution $\mathcal{P}$ over a time horizon $T$ is
bounded from above by

$\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-soft-
squared},\mathcal{P}^{T})\leq O(T^{2/3}).$

Further, the violation of the RoS constraint in Section 2 is at most
$O(T^{2/3})$.

###### Proof.

By picking $\alpha=T^{-1/3}$ in Lemma 4 yields a regret bound of $O(T^{2/3})$
and picking $c=1/3$ in Lemma 5 along with the same $\alpha$ gives a maximum
constraint violation of $O(T^{2/3})$. ∎

##  Appendix B Proofs of the Strict RoS Constraint

See 4.2

###### Proof.

We have by Proposition A.3, Proposition A.2, and Equation A.7:

$\displaystyle\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:tcpa-truthful-
soft},\overrightarrow{\gamma}_{\\!\ell})$
$\displaystyle\geq\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\ell\cdot\overline{\mathcal{D}}_{\mathsf{RoS}}(\overline{\lambda}_{\ell}|\mathcal{P})\right]-\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\sum_{t=1}^{\ell}\lambda_{t}\cdot
g_{t}(b_{t})\right]$ $\displaystyle\geq\ell\cdot\min_{\lambda\geq
0}\overline{\mathcal{D}}_{\mathsf{RoS}}(\lambda|\mathcal{P})-\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\sum_{t=1}^{\ell}\lambda_{t}\cdot
g_{t}(b_{t})\right]$
$\displaystyle\geq\frac{\ell}{r}\cdot\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!r})\right]-\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\sum_{t=1}^{\ell}\lambda_{t}\cdot
g_{t}(b_{t})\right],$
$\displaystyle\geq\frac{\ell}{r}\cdot\mathbb{E}_{\overrightarrow{\gamma}_{\\!r}\sim\mathcal{P}^{r}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!r})\right]-O(\sqrt{r}).$

∎

See 4.1

###### Proof.

Let $z_{t}=\max(0,v_{t}\cdot x_{t}(b_{t})-p_{t}(b_{t}))$ be the reward
collected at iteration $t$ (in the first phsae). Let
$z_{t}^{\prime}:=\frac{\beta}{2}\mathbf{1}_{z_{t}\geq\beta/2}$. By
construction, $z_{t}^{\prime}\leq z_{t}$ for all $t$. For any given sequence
$\overrightarrow{\gamma}$, let $K(\overrightarrow{\gamma})$ and
$K^{\prime}(\overrightarrow{\gamma})$, respectively, be the first time such
that $\sum_{t=1}^{K(\overrightarrow{\gamma})}z_{t}\geq R$ and
$\sum_{t=1}^{K^{\prime}(\overrightarrow{\gamma})}z_{t}^{\prime}\geq R$ for
some reward $R$. Then, for every $\overrightarrow{\gamma}$, we have
$K(\overrightarrow{\gamma})\leq K^{\prime}(\overrightarrow{\gamma})$.

By the boundedness assumption on $z_{t}$, we have

$\mathrm{Prob}(z_{t}^{\prime}=\beta/2)=\mathrm{Prob}(z_{t}\geq\beta/2)\geq\mathbb{E}\left[z_{t}\right]-\mathrm{Prob}(z_{t}\leq\beta/2)\cdot\mathbb{E}\left[z_{t}|z_{t}\leq\beta/2\right]\geq\beta/2.$

Then, by Hoeffding bound,

$\mathrm{Prob}(K(\overrightarrow{\gamma})\geq
q)\leq\mathrm{Prob}(K^{\prime}(\overrightarrow{\gamma})\geq q)\leq
e^{-O(q\beta^{2})}.$

Picking $q=O(R/\beta^{2})$ where $R=2\sqrt{T}\log T$ gives the claimed bound
on $\mathbb{E}\left[K(\overrightarrow{\gamma})\right]$. ∎

##  Appendix C Proofs for Both RoS and (Strict) Budget Constraints

###  C.1 Lemmas for Approximate RoS and Strict Budget Constraints

The following definition generalizes Definition A.1.

######  Definition C.1.

We need the following technical definitions of dual variables.

  * •

For some $\lambda\geq 0$ and $\mu\geq 0$, let $f_{t}(b):=v_{t}\cdot x_{t}(b)$,
define $g_{t}$ as in Section 2, and define

$f_{t,\mathsf{combined}}^{\star}(\mu,\lambda):=\max_{b}\left[f_{t}(b)+\lambda\cdot
g_{t}(b))-\mu\cdot p_{t}(b)\right].$ (C.1)

  * •

The following dual variable parametrized by $\rho$ and $\mathcal{P}$; the
quantity $f^{\star}$ is defined in the same way as in Equation C.1.

$\overline{\mathcal{D}}_{\mathsf{combined}}(\mu,\lambda|\mathcal{P},\rho):=\mu\cdot\rho+\mathbb{E}_{(v,p)\sim\mathcal{P}}\left[f^{\star}_{\mathsf{combined}}(\mu,\lambda)\right].$
(C.2)

######  Proposition C.1.

For some $\rho^{\prime}\geq 0$, let
$\overline{\mathcal{D}}_{\mathsf{combined}}(\mu,\lambda|\mathcal{P},\rho^{\prime})$
be as defined in Equation C.2. Then the optimum value
$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell},\rho)$ for
Section 2 with a total initial budget of $\rho\ell$ over a sequence
$\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}$ of $\ell$ requests
satisfies the inequality

$\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell},\rho)\right]\leq\ell\cdot\min_{\mu\geq
0,\lambda\geq
0}\left[\overline{\mathcal{D}}_{\mathsf{combined}}(\mu,\lambda|\mathcal{P},\rho^{\prime})+(\rho-\rho^{\prime})\cdot\mu\right].$

###### Proof.

In this proof, we essentially repeat the ideas in the proof of Proposition
A.2. First, by definition, we have

$\displaystyle\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell},\rho)$
$\displaystyle:=\max_{\left\\{b_{t}\right\\}:\sum_{t=1}^{\ell}g_{t}(b_{t})\geq
0,\sum_{t=1}^{\ell}p_{t}(b_{t})\leq\rho\ell}\left[\sum_{t=1}^{\ell}v_{t}\cdot
x_{t}(b_{t})\right]$
$\displaystyle=\max_{\left\\{b_{t}\right\\}}\min_{\lambda\geq 0,\mu\geq
0}\left[\sum_{t=1}^{\ell}v_{t}\cdot
x_{t}(b_{t})+\lambda\cdot\sum_{t=1}^{\ell}g_{t}(b_{t})+\mu\cdot(\ell\rho-\sum_{t=1}^{\ell}p_{t}(b_{t}))\right]$

By application of Sion’s minimax theorem and the definition of
$f_{t,\mathsf{combined}}^{\star}$, we get

$\displaystyle\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell},\rho)$
$\displaystyle\leq\min_{\lambda\geq 0,\mu\geq
0}\sum_{t=1}^{\ell}\mu\cdot\rho+\max_{b_{t}}\left[v_{t}\cdot
x_{t}(b_{t})+\lambda\cdot g_{t}(b_{t})-\mu\cdot p_{t}(b_{t})\right]$
$\displaystyle=\min_{\lambda\geq 0,\mu\geq
0}\sum_{t=1}^{\ell}\left[\rho\cdot\mu+f_{t,\mathsf{combined}}^{\star}(\mu,\lambda)\right]\leq\sum_{t=1}^{\ell}\left[\rho\cdot\mu^{\prime}+f_{t,\mathsf{combined}}^{\star}(\mu^{\prime},\lambda^{\prime})\right],$
(C.3)

for some fixed $\mu^{\prime}\geq 0$ and $\lambda^{\prime}\geq 0$. Then, taking
the expectations on both sides of Equation C.3 and using the fact that
$v_{t},x_{t},p_{t}$ are all drawn from i.i.d. distributions, we get

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!\ell}\sim\mathcal{P}^{\ell}}[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma}_{\\!\ell},\rho)]$
$\displaystyle\leq\sum_{t=1}^{\ell}\left[\rho\cdot\mu^{\prime}+\mathbb{E}_{(v,p)\sim\mathcal{P}}\left[f^{\star}_{\mathsf{combined}}(\mu^{\prime},\lambda^{\prime})\right]\right]$
$\displaystyle=\ell\cdot\overline{\mathcal{D}}_{\mathsf{combined}}(\mu^{\prime},\lambda^{\prime}|\mathcal{P},\rho^{\prime})+\ell(\rho-\rho^{\prime})\cdot\mu^{\prime}.$

Therefore, in particular, the preceding inequality holds for the
$\lambda,\mu\geq 0$ that minimize the bound, thus finishing the proof. ∎

Next, to analyze the reward collected by LABEL:alg:combined-truthful-soft,
similar to [BLM20], which gives an algorithm for a strict budget constraint,
we need the following notion of stopping time.

######  Definition C.2.

The stopping time $\tau$ of LABEL:alg:combined-truthful-soft, with a total
initial budget of $B$ is the first time $\tau$ at which

$\sum_{t=1}^{\tau}p_{t}(b_{t})+1\geq B.$

Intuitively, this is the first time step at which the total price paid almost
exceeds the total budget.

To prove our main regret bound in Theorem 5.1, we first prove Proposition C.2,
which gives the minimum expected reward of LABEL:alg:combined-truthful-soft.
The proof follows along the lines of that in [BLM20] and Proposition A.3.

######  Proposition C.2.

Let $\tau$ be a stopping time as defined in Definition C.2 for some initial
budget $\rho^{\prime}k$. Then the expected reward (see Section 2) of
LABEL:alg:combined-truthful-soft over a sequence of length $k$ with i.i.d.
input requests from distribution $\mathcal{P}^{k}$ is lower bounded as

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-soft},\overrightarrow{\gamma},\rho^{\prime})\right]$
$\displaystyle\geq\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\tau\cdot\overline{\mathcal{D}}_{\mathsf{combined}}(\overline{\mu}_{\tau},\overline{\lambda}_{\tau}|\mathcal{P},\rho^{\prime})\right]$
$\displaystyle\quad-\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\sum_{t=1}^{\tau}\mu_{t}\cdot(\rho^{\prime}-p_{t}(b_{t}))-\sum_{t=1}^{\tau}\lambda_{t}\cdot
g_{t}(b_{t})\right],$

where $\overline{\mu}_{\tau}=\frac{1}{\tau}\sum_{i=1}^{\tau}\mu_{i}$ and
$\overline{\lambda}_{\tau}=\frac{1}{\tau}\sum_{i=1}^{\tau}\lambda_{i}$.

###### Proof.

By 4 in LABEL:alg:combined-truthful-soft, we have, until the stopping time
$t=\tau$,

$f_{t,\mathsf{combined}}^{\star}(\mu_{t},\lambda_{t}):=v_{t}\cdot
x_{t}(b_{t})+\lambda_{t}\cdot g_{t}(b_{t})-\mu_{t}\cdot p_{t}(b_{t}).$

Rearranging the terms and taking expectations conditioned on the randomness up
to step $t-1$,

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[v_{t}\cdot
x_{t}(b_{t})|\sigma_{t-1}\right]$
$\displaystyle=\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[f_{t,\mathsf{combined}}^{\star}(\mu_{t},\lambda_{t})+\mu_{t}\cdot
p_{t}(b_{t})-\lambda_{t}\cdot g_{t}(b_{t})|\sigma_{t-1}\right].$ (C.4)

Per 7 in LABEL:alg:combined-truthful-soft that once we fix the randomness up
to $t-1$, the dual variables are all fixed, which gives us

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[f_{t,\mathsf{combined}}^{\star}(\mu_{t},\lambda_{t})|\sigma_{t-1}\right]$
$\displaystyle=\mathbb{E}_{(v,p)\sim\mathcal{P}}\left[f^{\star}_{\mathsf{combined}}(\mu_{t},\lambda_{t})\right]$
(C.5)

Combining Equation C.5 with the definition of
$\overline{\mathcal{D}}_{\mathsf{combined}}$ in Equation C.2 and plugging back
into Equation C.4 then gives

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{T}}\left[v_{t}\cdot
x_{t}(b_{t})|\sigma_{t-1}\right]$
$\displaystyle=\overline{\mathcal{D}}_{\mathsf{combined}}(\mu_{t},\lambda_{t}|\mathcal{P},\rho^{\prime})-\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\mu_{t}\cdot(\rho^{\prime}-p_{t}(b_{t}))+\lambda_{t}\cdot
g_{t}(b_{t})|\sigma_{t-1}\right]$

Summing over $t=1,2,\dots,\tau,$ and using the Optional Stopping Theorem, we
get

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\sum_{t=1}^{\tau}v_{t}\cdot
x_{t}(b_{t})\right]$
$\displaystyle=\mathbb{E}_{\overrightarrow{\gamma}_{\\!k}\sim\mathcal{P}^{k}}\left[\sum_{t=1}^{\tau}\left(\overline{\mathcal{D}}_{\mathsf{combined}}(\mu_{t},\lambda_{t}|\mathcal{P},\rho^{\prime})-\mu_{t}\cdot(\rho^{\prime}-p_{t}(b_{t}))-\lambda_{t}\cdot
g_{t}(b_{t})\right)\right].$

We finish the proof by using the convexity of
$\overline{\mathcal{D}}_{\mathsf{combined}}$ in the preceding equation. ∎

Our bound on regret requires the following technical result bounding one of
the terms arising in Proposition C.2.

######  Proposition C.3.

Consider a run of LABEL:alg:combined-truthful-soft with initial total budget
$\rho\ell$ and the total time horizon $\ell$. We define the corresponding
stopping time (as defined in Definition C.2) as the time $\tau$ at which
$\sum_{t=1}^{\tau}p_{t}(b_{t})\geq\rho\ell-1$. Then, the dual variable
$\\{\mu_{t}\\}$ that evolves as per 8 in LABEL:alg:combined-truthful-soft
satisfies the following inequality.

$\sum_{t=1}^{\tau}\mu_{t}\cdot(\rho-
p_{t}(b_{t}))\leq(\tau-\ell)+1/\rho+O(\sqrt{\ell}).$

###### Proof.

To bound $\sum_{t=1}^{\tau}\mu_{t}\cdot(\rho-p_{t}(b_{t})),$ we observe that
the mirror descent guarantee of Lemma 6 applies to give, for any $\mu\geq 0$,

$\sum_{t=1}^{\tau}\mu_{t}\cdot(\rho-
p_{t}(b_{t}))\leq\sum_{t=1}^{\tau}\mu\cdot(\rho-
p_{t}(b_{t}))+\mathsf{Err}(\tau,\eta),$

where $\mathsf{Err}(R,\eta):=\frac{1}{\sigma}(1+{\rho}^{2})\eta
R+\frac{1}{\eta}V_{h}(\mu,\mu_{1})$, where $h(u)=\frac{1}{2}u^{2}$,
$\sigma=1$, and $\mu_{1}=0$. To finish the proof, we choose $\mu=1/\rho$, use
$\sum_{t=1}^{\tau}p_{t}(b_{t})\geq\rho\ell-1$, and choose
$\eta=\frac{1}{(1+\rho^{2})\sqrt{\ell}}$ in $\mathsf{Err}(\tau,\eta)$ ∎

See 5.1

###### Proof.

Recall that $\tau$ is the stopping time of LABEL:alg:combined-truthful-soft as
defined in Definition C.2. Then,

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]$
$\displaystyle=\frac{\tau}{T}\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]+\frac{T-\tau}{T}\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]$
$\displaystyle\leq\frac{\tau}{T}\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]+(T-\tau),$
(C.7)

where the final step is because
$\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\leq T$ (due to the
value capped at one). Combining Equation C.7, Proposition C.1, and the lower
bound on $\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-truthful-
soft},\overrightarrow{\gamma},\rho)$ from Proposition C.2 in the definition of
$\mathsf{Regret}$ in Section 2 gives

$\displaystyle\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:combined-truthful-
soft},\overrightarrow{\gamma})$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[(T-\tau)+\sum_{t=1}^{\tau}\mu_{t}\cdot(\rho-
p_{t}(b_{t}))+\sum_{t=1}^{\tau}\lambda_{t}\cdot g_{t}(b_{t})\right].$ (C.8)

We invoke Proposition C.3 with a total initial budget $\rho T$ and total time
horizon $T$ to get

$\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\sum_{t=1}^{\tau}\mu_{t}(\rho-
p_{t}(b_{t}))\right]\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\tau-T\right]+\frac{1}{\rho}+O(\sqrt{T}).$

Finally, we invoke Lemma 2 to conclude $\sum_{t=1}^{R}\lambda_{t}g_{t}\leq
O(\sqrt{R})$, which lets us conclude

$\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\sum_{t=1}^{\tau}\lambda_{t}g_{t}\right]\leq
O(\sqrt{T}).$

Combining Equation C.8, Section C.1, and Section C.1 yields the claimed bound.

We now finish with the proof of maximum constraint violation. By design of
LABEL:alg:combined-truthful-soft, the budget constraint is never violated
throughout the run of the algorithm. To see the claimed maximum violation of
the RoS constraint, we note by Proposition A.1 that the gradient $g_{t}$
satisfies $g_{t}(b_{t})\geq-1/\lambda_{t}$, as a result of which, Lemma 1
applies. ∎

###  C.2 Proofs for Strict RoS and Strict Budget Constraints

We need the following technical result on the bound on $\mu_{t}$ in
LABEL:alg:combined-truthful-soft. The proof is similar in spirit to
Proposition 2 of [BLM20], but needs some bounds specific to our setting.

######  Proposition C.4.

The dual variable $\mu_{t}$ in LABEL:alg:combined-truthful-soft with initial
budget $\rho T$ for a time horizon of $T$ satisfies the bound $\mu_{t}\leq
2/\rho+1$ for all $t\in[T]$.

###### Proof.

Recall, by assumption, we have $p_{t}(b_{t})\leq 1$. Further, by definition of
$b_{t}$ in LABEL:alg:combined-truthful-soft, we have $0\leq v_{t}\cdot
x_{t}(b_{t})-\lambda_{t}g_{t}(b_{t})-\mu_{t}p_{t}(b_{t})$, which upon
rearranging and using $\lambda_{t}g_{t}(b_{t})\geq-1$ (from Proposition A.1),
gives $p_{t}(b_{t})\leq 1/\mu_{t}-\lambda_{t}\cdot g_{t}(b_{t})/\mu_{t}\leq
2/\mu_{t}$. Therefore, we have

$p_{t}(b_{t})\leq\min(1,2/\mu_{t}).$

If $\rho\geq\min(1,2/\mu_{t})$, then $\mu_{t+1}\leq\mu_{t}$. Otherwise,
suppose that $\mu_{t+1}\neq 0$; then the result holds since

$\mu_{t+1}=\mu_{t}-\eta(\rho-p_{t}(b_{t}))\leq
2/\rho+\eta(-\rho+p_{t}(b_{t}))\leq 2/\rho+\eta\leq 2/\rho+1.$

∎

See 5.2

###### Proof.

The fact that the RoS constraint is not violated may be seen by the fact that
the first phase accumulates the exact buffer that is the guaranteed cap on
constraint violation by the second phase. The budget constraint is not
violated by design: the first phase (which lasts at most $\rho T$ iterations)
pays at most unit price per iteration, followed by the second phase, which, by
the guarantee of LABEL:alg:combined-truthful-soft, strictly respects the
budget constraint.

To bound the regret, we note that the total expected reward is at least as
much as is collected in the second phase

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-strict},\overrightarrow{\gamma},\rho)\right]$
$\displaystyle\geq\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left(\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-
soft},\overrightarrow{\gamma}_{\\!k+1:T},\widehat{\rho}\right)\right],$ (C.12)

where the notation on the right-hand side captures the reduced time horizon of
$T-K(\overrightarrow{\gamma})$ as well as reduced initial budget of $\rho
T-K(\overrightarrow{\gamma})$ for running LABEL:alg:combined-truthful-soft and
$\widehat{\rho}=\frac{\rho
T-K(\overrightarrow{\gamma}))}{T-K(\overrightarrow{\gamma})}$. Conditioning on
the event high-probability event that $k\leq\rho T$ (by Appendix B coupled
with the assumption that $\rho$ is a fixed constant), we have

$\displaystyle\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left(\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-
soft},\overrightarrow{\gamma}_{\\!k+1:T},\widehat{\rho}\right)\right]$
$\displaystyle\quad\geq(1-e^{-O(T)})\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left(\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-soft},\overrightarrow{\gamma}_{\\!k+1:T},\widehat{\rho}\right)\mid
k\leq\rho T\right].$ (C.13)

Applying Proposition C.2 with the reduced budget and time horizon gives:

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\mathsf{Reward}(\lx@cref{creftype~refnum}{alg:combined-
truthful-soft},\overrightarrow{\gamma}_{\\!k+1:T},\widehat{\rho}\right]$
$\displaystyle\geq\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\tau\cdot\overline{\mathcal{D}}_{\mathsf{combined}}(\overline{\mu}_{\tau},\overline{\lambda}_{\tau}|\mathcal{P},\widehat{\rho})\right]$
$\displaystyle\quad-\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\sum_{t=1}^{\tau}\mu_{t}\cdot(\widehat{\rho}-p_{t}(b_{t}))\right]$
$\displaystyle\quad-\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\sum_{t=1}^{\tau}\lambda_{t}\cdot
g_{t}(b_{t})\right],$ (C.14)

Next, by Proposition C.1, we have:

$\overline{\mathcal{D}}_{\mathsf{combined}}(\overline{\mu}_{\tau},\overline{\lambda}_{\tau}|\mathcal{P},\widehat{\rho})+(\rho-\widehat{\rho})\cdot\overline{\mu}_{\tau}\geq\frac{1}{T}\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right].$

We can now repeat the trick in the proof of Theorem 5.1:

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]$
$\displaystyle\leq\frac{\tau}{T}\cdot\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Reward}(\mathsf{Opt},\overrightarrow{\gamma},\rho)\right]+(T-\tau),$
(C.16)

Combining Equation C.12, Equation C.13, Equation C.14, Section C.2, and
Equation C.16 then gives

$\displaystyle\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\mathsf{Regret}(\lx@cref{creftype~refnum}{alg:combined-
truthful-strict},\overrightarrow{\gamma})\right]$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}(T-\tau)+\frac{T}{e^{O(T)}}$
$\displaystyle\quad+\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\sum_{t=1}^{\tau}\mu_{t}\cdot(\widehat{\rho}-p_{t}(b_{t}))\right]\mid
k\leq\rho T\right]$
$\displaystyle\quad+\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\sum_{t=1}^{\tau}\lambda_{t}\cdot
g_{t}(b_{t})\right]\mid k\leq\rho T\right]$
$\displaystyle\quad+\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\tau\overline{\mu}_{\tau}(\rho-\widehat{\rho})\right]\mid
k\leq\rho T\right].$ (C.17)

By applying Proposition C.3 and Proposition 4.1 and under the conditional
expectation, we have

$\displaystyle\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\sum_{t=1}^{\tau}\mu_{t}\cdot(\widehat{\rho}-p_{t}(b_{t}))\right]\mid
k\leq\rho T\right]$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[(\tau-T)+K(\overrightarrow{\gamma})\right]+O(\sqrt{T})$
$\displaystyle\quad+\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}}(1/\widehat{\rho})\mid
k\leq\rho T\right]$
$\displaystyle\leq\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}(\tau-T)+O(\sqrt{T}\log
T).$ (C.18)

We invoke Lemma 2 to conclude $\sum_{t=1}^{R}\lambda_{t}g_{t}\leq O(\sqrt{R})$
for all $R\leq T$, which lets us conclude

$\mathbb{E}_{\overrightarrow{\gamma}\sim\mathcal{P}^{T}}\left[\sum_{t=1}^{\tau}\lambda_{t}g_{t}\right]\leq
O(\sqrt{T}).$

To bound the final term in Equation C.17, we observe that
$\rho-\widehat{\rho}=\frac{(1-\rho)K(\overrightarrow{\gamma})}{T-K(\overrightarrow{\gamma})}$
by definition of $\widehat{\rho}$. Combining this with $\tau\leq T$, the bound
on $\mu_{t}$ from Proposition C.4, the result of Proposition 4.1, and the
conditional expectation, we get

$\mathbb{E}_{k}\left[\mathbb{E}_{\overrightarrow{\gamma}_{\\!k+1:T}\sim\mathcal{P}^{T-k}}\left[\tau\overline{\mu}_{\tau}(\rho-\widehat{\rho})\right]\mid
k\leq\rho T\right]\leq O(\sqrt{T}).$

Combining Equation C.17, Equation C.18, Section C.2, and Section C.2 finishes
the proof. ∎

##  Appendix D Online Mirror Descent

######  Lemma 6 ([Bub+15], Theorem $4.2$).

Let $h$ be a mirror map which is $\rho$-strongly convex on
$\mathcal{X}\cap\mathcal{D}$ with respect to a norm $\|{}\cdot{}\|$. Let $f$
be convex and $L$-Lipschitz with respect to $\|{}\cdot{}\|$. Then, mirror
descent with step size $\alpha$ satisfies

$\sum_{s=1}^{t}\left(f(x_{s})-f(x)\right)\leq\frac{1}{\alpha}V_{h}(x,x_{1})+\alpha\frac{L^{2}t}{2\rho}.$

######  Lemma 7 ([AO14]).

The Bregman divergence of the generalized negative entropy satisfies “local
strong convexity”: for any $x,y>0$,

$V_{h}(y,x)=y\log(y/x)+x-y\geq\frac{1}{2\max(x,y)}\cdot(y-x)^{2}.$

###### Proof.

The claimed inequality is equivalent to

$t\log t\geq(t-1)+\frac{1}{2\max(1,t)}\cdot(t-1)^{2}$

for $t>0$. Suppose $t\geq 1$. Then, choosing $u=1-1/t$, Appendix D is
equivalent to

$-\log(1-u)\geq u+\frac{1}{2}u^{2},$

for $u\in[0,1)$, which holds by Taylor series. Suppose $0<t\leq 1$. Then
Appendix D is equivalent to

$\log t-\frac{1}{2}\left(t-\frac{1}{t}\right)\geq 0,$

which may be checked by observing that the function is decreasing and equals
zero at $t=1$. This completes the proof of the claim. ∎