Sequential Learning under Probabilistic Constraints

Amirhossein Meisami
Adobe, Inc.
San Jose, CA 95110

Henry Lam
Columbia University
New York, NY 10027

Abstract
We provide the first study on online learning problems under stochastic constraints thatare “soft”, i.e., need to be satisfied with highprobability. These constraints are imposedon all or some stages of the time horizon sothat the stage decisions probabilistically satisfy
some given safety conditions. The distributions that govern these conditions are learned
through the collected observations. Under aBayesian framework, we introduce a schemethat provides statistical feasibility guarantees
through the time horizon, by using posterior
Monte Carlo samples to form sampled constraints which leverage the scenario generation
approach in chance-constrained programming.
We demonstrate how our scheme can be integrated into Thompson sampling and illustrate
it with an application in online advertisement.

1

INTRODUCTION

Most of the literature in stochastic online learning focuses on performances measured by optimality achievement. Common examples include the minimization of
cumulative regret in the multi-arm bandit setting (e.g.,
Auer et al. (2002); Lai and Robbins (1985)), best arm
selection (e.g., Audibert and Bubeck (2010)) and theclosely related ranking and selection (e.g., Boesel et al.
(2003)) in the simulation literature. In many situations,however, the uncertainty or the stochasticity appears not
only in the objective function, but also in the constraintsof the problem whose feasibility can be of utmost importance. The focus of this paper is to design sequential
methodologies that maintain probabilistic feasibility requirements with rigorous statistical guarantees.
Our study is motivated from a rich set of problems where

Chen Dong
Adobe, Inc.
San Jose, CA 95110

Abhishek Pani
Adobe, Inc.
San Jose, CA 95110“budgets” or “resources” are limited for various operational or commercial reasons, and these constraints arein a sense “soft”, i.e., the capacities placed on these constraints, while preferred to be satisfied, are allowed to
be violated with a small probability. Such consideration is common among applications. For example, in
online advertisement problems encountered by our coauthors when optimizing spending for large advertisers,
the task involves sequentially picking items (e.g., keywords, targets) to maximize revenues, while adhering toa specified marketing budget for a duration. The marketer in general expects to meet the budget goals. However, if occasionally the budget is exceeded the campaign
is still acceptable as long as the revenue performance issustained. Other similar settings include clinical trials,
where the costs of competing treatments are substantial
and noisy, and over-budget is undesired but sometimes
allowable. Whereas past work in stochastic sequential
learning has focused on rewards (with hard constraints
if needed), this paper provides the first study on a classof problems that not just include the rewards but also
stochastic constraints that need to be satisfied with highprobability.
Our framework can be viewed as a sequential problem under so-called probabilistic or chance constraints(Prékopa, 2003), which has been widely used in stochastic programming under limited and uncertain resources(e.g., Shi et al. (2015); Lejeune and Ruszczynski (2007)).
A generic representation of a chance constraint is
P ((x, ξ) satisfies a given safety condition) ≥ 1−α (1)where x is a decision variable and ξ denotes some randomness distributed under P . Satisfying the safety condition means that (x, ξ) lies in a desirable deterministic
region, which can be represented by, e.g., a set of inequalities. The given parameter α is the tolerance levelthat represents the allowable probabilistic violation.
In the sequential setting, x would denote a sequence ofdecisions. The safety condition could include individualrequirements on all or some stages. In many applicationsof interest, P needs to be learned as complete distributional knowledge on ξ is not available. Along the vein of
conventional online problems that focus on optimality, ateach stage we may observe some components of ξ so that
we can update our belief on P .
As our main methodological contribution, we analyze an
online strategy that provides guarantees on (1) with ahigh confidence, under a statistical framework that weshall describe. On a high level, it means we can guarantee, with our proposed policy, that
P (P ((x, ξ) satisfies a given safety condition)≥ 1 − α) ≥ 1 − β(2)where the outer probability now refers to the randomnessof x induced by the sequential observations, and 1−β is aconfidence level (90% for instance). Our methodology isbased on a combination of two ideas. First is a Bayesian
extension of the so-called scenario generation or constraint sampling (Calafiore and Campi, 2005; De Farias
and Van Roy, 2004) approach in approximating chanceconstrained optimization problems. This approach replaces the unknown or difficult chance constraint with acollection of sampled constraints that come from data orfrom numerical simulation. Viewing such an approachin a Bayesian manner allows it to be blended naturally
into popularly used online learning algorithms such as
Thompson sampling (Agrawal and Goyal, 2012; Russo
and Van Roy, 2016) that also operates via Bayesian updating. Second, by capitalizing results on scenario generation in the static setting, we can derive the precise number of samples required at each stage of the sequential
process such that (2) holds throughout the horizon. As
far as we know, our formulation and analysis of chanceconstraint guarantees in an online setting is new to theliterature.
After presenting our theoretical investigation on feasibility guarantees, we illustrate the integration of our scheme
into a variant of Thompson sampling in an online advertisement setting. We then numerically demonstrate how
this chance-constrained Thompson sampling performs
competitively, in achieving feasibility but also maintaining good objective values.

2

RELATED WORKThe earliest work in chance constraints dated back toCharnes et al. (1958) and Miller and Wagner (1965). Exact solution techniques for such problems are notoriously
difficult due to non-convexity, and are only available infew instances even when P is known; e.g., Lagoa et al.
(2005). Several lines of approximation methodologies

have been proposed. A conventional method is to use
so-called safe convex approximation that replaces the
chance constraint with more conservative convex constraints (Ben-Tal and Nemirovski, 2000). Rossi et al.
(2011, 2015) used policy trees and confidence interval
construction to obtain the so-called (α, ϑ)-solution. Scenario generation (Calafiore and Campi, 2006; Campi andGaratti, 2008), which we leverage on in this work, uses
sampled constraints to populate the feasible region. Thisapproach has several extensions, such as sampling-anddiscarding (Campi and Garatti, 2011) and multi-phase
schemes (Carè et al., 2014; Calafiore, 2017; Chamanbaz
et al., 2016), and relates to sample average approximation (Luedtke et al., 2010). Other data-driven methods
include distributionally robust optimization (Calafiore
and El Ghaoui, 2006; Zymler et al., 2013) and datadriven robust optimization (Bertsimas et al., 2013).
Our work focuses on chance-constrained problem in an
online fashion, under the broad umbrella of sequential
decision-making. In the later part of this paper, wedemonstrate our proposed strategy in a variant of thestochastic multi-arm bandit problem (Auer et al., 2002)
used to address the well-known exploration-exploitation
tradeoff. In budgeted bandits, Ding et al. (2013) consider the presence of random costs and an overall budget,where learning and revenue accumulation stops when
the budget runs out. Xia et al. (2015) study Thompson sampling for a similar setting; in this work we integrate our strategy into Thompson sampling, especiallythe one considered in Ferreira et al. (2016) motivatedfrom network revenue management. Other related work
include those in the framework of “bandits with knapsacks” (Badanidiyuru et al., 2013; Tran-Thanh et al.,2012; Besbes and Zeevi, 2012) that have been appliedin pricing and supply chain management (Wang et al.
(2014)) and healthcare (Villar et al. (2015)). The works
closest to our online advertisement example are TranThanh et al. (2014) and Amin et al. (2012) that study the
problem of item bidding under a budget, but they do notconsider probabilistic violation of the constraints that we
focus on.

3

CHANCE-CONSTRAINED ONLINELEARNING

Consider a sequence of decision variables xt ∈ Rd , t =1, . . . , T , and a sequence of random variables ξt ∈Ξt , t = 1, . . . , T assumed independent among the steps
t in a given horizon T . For convenience, denote ξ1:t =(ξ1 , . . . , ξt ) and x1:t = (x1 , . . . , xt ) as the cumulative
randomness and decisions up to t. Consider a sequenceof safety conditions that we write as ft (x1:t , ξ1:t ) ∈ At ,where each function ft maps to some space Yt such that

At ⊂ Yt (for example, ft (x1:t , ξ1:t ) ∈ At can be a
set of inequalities so that Yt = Rm for some m and
At = {y ∈ Rm : y ≤ 0}.
We are interested in a sequential problem with horizonT:max

x1 ,...,xT

h(x1 , . . . , xT )subject to P (ft (x1:t , ξ1:t ) ∈ At |Ft−1 ) ≥ 1 − α ∀t ∈ S,
(3)
where the decisions x1 , . . . , xT are sequential, i.e., xt+1
depends on the past observations of ξ1:t and past decisions x1:t , S ⊂ {1, . . . , T } is a given set, and h(·) is theobjective function. Note that the function ft and the set
At can depend on the time step t. For convenience, let
Ft = {ξ1:t , x1:t } be the information up to time t. In eachprobability P in (3), the function ft (x1:t , ξ1:t ) can be
expressed as ft (x1:(t−1) , xt , ξ1:(t−1) , ξt ) where x1:(t−1)
and ξ1:(t−1) belong to the past information Ft−1 .
Consistent with the introduction, α is a tolerance parameter on the violation of the safety condition. This parameter is assumed constant across t for convenience, but
our analysis can be easily adapted to the case where it
varies. Note that S determines how many chance constraints need to be maintained throughout the horizon.
For example, S = {1, . . . , T } means there is a budget
requirement for each step, and S = {T } means there
is only one overall budget requirement across the wholehorizon.
3.1

SCENARIO GENERATION FOR STATICPROBLEMS

We first discuss a well-studied approach to approximatea static version of (3). Suppose T = 1. In this setting we
can simplify notation and write the formulation as
max
x

h(x)

subject to P (f (x, ξ) ∈ A) ≥ 1 − α(4)Suppose we can simulate or collect data for ξ to obtain,
say, i.i.d. ξ 1 , . . . , ξ N . We consider replacing the constraint in (4) by sampled constraints, so that the optimization program becomes
max
x

h(x)

subject to f (x, ξ n ) ∈ A, ∀ n = 1, . . . , N(5)

We call (5) a sampled program, which serves as a reasonable approximation to (4) when N is large. However,since ξ n ’s are randomly generated, the solution obtained
from (5) is subject to statistical noise and cannot be guaranteed feasible for (4). The following celebrated result
from (Calafiore and Campi, 2006; Campi and Garatti,

2008) gives the sample size needed to guarantee feasibility for (4) with a certain confidence by solving (5).
Condition 1. An optimization program is said to be inclass R if: 1) It is feasible and the feasible region has a
non-empty interior; 2) Its optimal solution exists and is
unique.
Theorem 1. (Adopted from Theorem 2.4, Campi andGaratti (2008)) Suppose for each ξ, f (x, ξ) ∈ A is aconvex set in x ∈ Rd , and h is concave. Suppose alsothat any instance of (5) belongs to R. Fix real numbers
α, β ∈ [0, 1]. Then for N chosen such thatd−1  XN
i=0i

αi (1 − α)N −i ≤ β

the optimal solution of the sampled stochastic program(5) is feasible for (4) with probability no smaller than1 − β.
It is known that this result can be improved, e.g., by using sampling-and-discarding (Campi and Garatti, 2011)and multi-stage or iterative schemes (Carè et al., 2014;
Calafiore, 2017; Chamanbaz et al., 2016). In this paper
we stick with the requirement in Theorem 1 to illustrate
our proposed strategies; improvements can be made accordingly by modifying the use of Theorem 1 to better
results available in the literature.
3.2

SCENARIO GENERATION UNDERUNKNOWN DISTRIBUTION: A BAYESIANPERSPECTIVE

The scenario generation approach depicted in Theorem
1 requires direct observations on ξ or the capacity to obtain Monte Carlo samples for ξ. In problems with learning, the distribution of ξ is not fully known, and Theorem 1 does not apply directly. We shall adopt a Bayesian
perspective that naturally integrates to many online algorithms (e.g., Thompson sampling). Suppose ξ follows aparametric distribution G|µ with unknown parameter µ.
After specifying a prior distribution for µ and collectingsome data historically, we have a posterior distribution
for µ denoted by F . We seek to use Monte Carlo sampling to conduct an analog of scenario generation so thata posterior credibility guarantee
Pµ (Pξ|µ (f (x, ξ) ∈ A) ≥ 1 − α) ≥ 1 − β(6)is achieved, where Pµ denotes the posterior probability
distribution on µ, and Pξ|µ denotes the distribution of ξ
given a parameter value of µ. In other words, we want
the chance constraint to hold with a posterior credibility
level 1 − β. Note that this is a natural Bayesian analog
of the frequentist result in Theorem 1. In the setting ofTheorem 1, P is not known but data are available, so thata 1 − β confidence is attained. In our current Bayesian
investigation, P is not known but subject to a posterior
belief summarized by the distribution of µ, and we want
this posterior credibility to be 1 − β.
Directly sampling ξ using any particular value of µ does
not sufficiently capture the posterior uncertainty. To
blend the latter into a scenario generation, we can use
a two-level sampling, where in the first level we generate a posterior sample for µ, and in the second level wegenerate ξ conditional on µ. This sampling procedure is
described in Algorithm 1.
Algorithm 1 Posterior Constraint Sample Generator(PCSG)
1. Repeat N times:(a) Generate µn ∼ F .
(b) Generate ξ n ∼ G|µn .
2. Impose the constraints f (x, ξ n ) ∈ A, n =1, . . . , N and solve the sampled program
max
x

h(x)

subject to f (x, ξ n ) ∈ A, ∀ n = 1, . . . , N(7)

In PCSG we encounter two different sources of randomness. First is the statistical noise from the uncertainty ofµ, captured by the posterior credibility level 1 − β. The
second source is the Monte Carlo error, and we denoteby 1 − δ the confidence level induced from this error. By
choosing a suitable sample size N in terms of α, β, δ,
PCSG turns out to achieve a guarantee below.
Theorem 2. Suppose f (x, ξ) ∈ A is a convex set in x ∈Rd , and h(x) is concave. Suppose also that any instanceof (7) belongs to R. Fix real numbers δ, α, β ∈ [0, 1]
and choose
d−1  XN(αβ)i (1 − αβ)N −i ≤ δ
i
i=0

(8)

Consider a solution x obtained from the sampled program in PCSG. Then,
1. x satisfies (6) with a Monte Carlo confidence 1 − δ,i.e.,
PM C (Pµ (Pξ|µ (f (x, ξ) ∈ A) ≥ 1−α) ≥ 1−β) ≥ 1−δ
(9)where the outermost PM C denotes the probability
with respect to the N Monte Carlo samples.

2. x satisfies
EM C [Pµ (Pξ|µ (f (x, ξ) ∈ A) ≥ 1−α)] ≥ (1−β)(1−δ)(10)
where EM C [·] denotes the expectation with respect to
the N Monte Carlo samples.
Theorem 2 Part 1 stipulates that choosing N in (8)achieves chance-constraint feasibility with a Bayesiancredibility 1 − β, under a Monte Carlo confidence 1 − δ.
Part 2 will be useful in generalizing to the multi-stage
setting presented next.
3.3

SEQUENTIAL POLICIES

We now move our analysis to the sequential problem depicted in (3). We generalize PCSG, with the posterior update occurring at every step of the horizon and the sample
size required at each step modified in order to achieve achance constraint guarantee over the whole horizon. Let
Nt be the sample size used in step t, which depends on α
and also the confidence-level parameters βt and δt . We
denote F0 as the prior distribution of µ and Ft as theposterior distribution of µ at step t. We denote Gt |µ as
the distribution of ξt given µ. Note that µ is a parameter
shared among the ξt at different steps so that information
can be learned over time. To distinguish the real datafrom the Monte Carlo samples, we use ξ˜1:(t−1) to denotethe actual data of ξ coming from steps 1 to t − 1.
We have the following procedure:
Algorithm 2 Dynamic PCSG
Set F0 as the prior distribution of µ. For t = 1, . . . , T :While t ∈ S, and given Ft and the realized x1:(t−1) andξ˜1:(t−1) :1. Repeat Nt times:(a) Generate µn ∼ Ft .
(b) Generate ξ n ∼ Gt |µn .
2. Impose the constraints
ft (x1:(t−1) , xt , ξ˜1:(t−1) , ξ n ) ∈ At , ∀ n = 1, . . . , Nt
(11)
at stage t.

It is understood that in the second step of Dynamic
PCSG, the constraints are imposed together with an appropriate objective function (typically the cost-to-go informulation (3)) to form a stepwise optimization with decision variable xt . The following result gives the choiceof Nt and the resulting guarantee:

Theorem 3. Suppose the stepwise safety conditions are
all convex sets, the objective function at every step is concave, and xt ∈ Rd . Suppose also that any instance of the
optimization resulted from imposing (11) belongs to R.
Suppose 0 ≤ βt , δt ≤ 1 are constants such that
d−1 
X
i=0

2η 1−1/ρ +Nt(αβt )i (1 − αβt )Nt −i ≤ δt
i

(12)

X
(βt + δt − βt δt ) ≤ βλ

(13)

and

Then the policy obtained from Dynamic PCSG is feasible for (3) under the updated posterior distribution withprobability at least 1 − β, with overall Monte Carlo confidence 1 − λ, i.e.,
PM C (Pµ1:T (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 ) ≥ 1 − α∀t ∈ S) ≥ 1 − β) ≥ 1 − λ

η2
2
1
− 1/ρ
1/ρ
ρ−1
ρ − 1 (1/η
− 1)
η
+1
1
1
−
≤ βλ
2ρ − 1 (1/η 1/ρ + 1)2ρ−1(15)then (14) holds regardless of |S|.

t∈S

(14)

where Pµ1:T denotes the probability with respect toµ1 , . . . , µt , where each µt ∼ Ft , the posterior distribution of µ at step t, and Pξt |µt denotes the probability
with respect to ξt given a realized parameter of µt .
Theorem 3 asserts that the round-specific statistical parameters, namely the posterior credibility 1 − βt and theMonte Carlo confidence level 1 − δt , which determine
the constraint sample size, can be chosen to satisfy a local condition (12) and a global condition (13) to achieve
an overall statistical guarantee.
For convenience we can set βt = δt and both equal tosome constant, say γt . This γt can be set to be stageindependent or dependent. The following subsection
shows two choices of γt .
3.4

Proposition 2. If we let βt = δt = γt for all t ∈ S suchthat γt = (1/ζ(t)ρ ) ∧ η, where ρ > 1, 0 < η < 1, andζ(t) = ]{s ∈ S : s ≤ t} (i.e., ζ(t) is the “counter” of tin S) such thatTWO EXPLICIT STRATEGIESWe demonstrate two choices of {Nt } in terms of {γt }.
The first choice is a simple one that requires knowledge of the horizon length T , by setting γt to be a constant. The second choice uses a decaying γt , consequently an increasing sample size Nt , which does not
require knowledge of T a priori. For convenience, wedenote |S| as the size of the set S. For the first strategy,
we have:
Proposition 1. Given a time horizon T , p
if we let βt =δt = γ for all t ∈ S such that γ ≤ 1 − 1 − βλ/|S|,then (14) holds.
The following describes our second strategy that is stagedependent such that (14) holds without knowing the horizon T or |S| a priori:√
For example, if ρ is set to be 2, then (15) becomes 2 η +√√√√2 η/(1− η)−η 2 /( η+1)−η 3/2 /(3(1+ η)3 ) ≤ βλ.

4

INTEGRATION INTO THOMPSONSAMPLING

We illustrate the integration of our strategies with
Thompson sampling, which also operates via Bayesian
updating, by an example of revenue maximization in online advertising (Pani et al., 2017). The advertiser isinterested in maximizing the expected revenue across a
portfolios of keywords or biddable ad units while ensuring that the budget constraint is not violated. When theadvertiser selects a bid value for a keyword it results in
ad clicks, the volume of which is stochastic. The distribution of clicks and the associated revenue is not initiallyknown to the decision-maker and needs to be learned
over time. Further, the cost associated with the choiceof a bid is also unknown and hence, there is uncertainty
regarding how the budget will be affected.
To be more concrete, consider a set of K bid values{κ1 , ..., κK }, for M items labeled {π1 , ..., πM }, overthe campaign horizon T . Bidding value j on item
i will induce an average revenue rij and cost cij respectively. These quantities are assumed to follow independent Poisson distributions with initially unknown
parameters (the Poisson assumptions come from theclick count nature). In each period t = 1, . . . , T , theadvertiser picks a bid value j from every item, observes the outcome, i.e., the realizations of rij , cij , i =PM PK
1, . . . , M . She gains i=1 j=1 rij xij and consumes
PM PK
i=1
j=1 cij xij from the budget, where xij is the allocation portion for bid value j of item i (i.e., the fractionof time or the probability in a randomized scheme that isallocated to this particular bid value and item).
The advertiser’s goal is to maximize the total revenue
while maintain a budget constraint with high probability. In other words, letting rij (t) and cij (t) be the realized revenue and cost for a bid at time t, and xij (t)be the corresponding
variables, she wants to
PT Pallocation
M PK
maximize E[ t=1 i=1 j=1 rij (t)xij (t)]. A typicalbudget constraint is a bound given by the remaining budget averaged over the remaining horizon. Specifically,
let the overall budget be B. Denoting B(t − 1) =Pt−1 PM PK
B − u=1 i=1 j=1 cij (u)xij (u) as the remaining
budgetPt before
PM epoch
PK t ∈ S, the advertiser wants to keep
P ( u=1 i=1 j=1 cij (u)xij (u) ≤ B(t−1)/(T −t+1)) ≥ 1 − α ∀t ∈ S. This type of dynamically updated
per-round budgets is common in practice and is argued
to be more effective than fixed per-round budgets. In thefollowing, we will concentrate on the particular choicedescribed above as the feasibility requirement.
4.1

Algorithm 3 Budgeted Thompson Sampling for deterministically constrained problems adopted from Ferreira
et al. (2016)
Given a total budget B(0) = B. For t = 1, ..., T , do thefollowing:
1: For each bid value j and each item i, sample θij from
Gamma(Wijr (t − 1) + 1, Xij (t − 1) + 1) and µij from
Gamma(Wijc (t − 1) + 1, Xij (t − 1) + 1).
2: Solve the following linear program:
K X
M
X

max
x

A BUDGETED ALGORITHM

θij xij

j=1 i=1
K X
M
X

subject toµij xij ≤j=1 i=1

The setting of this problem resembles a recent study (Ferreira et al., 2016) on a network revenue management
problem. They developed a Thompson sampling algorithm to sequentially assign a price vector to items underresource constraints, where each step involves a knapsack optimization problem. Here we present a variant of
their algorithm to suit our setting (Algorithm 3). This initial algorithm does not take into account the possibilityof constraint violation; the idea is to later illustrate how
our Dynamic PCSG strategy can be integrated.
Denote by Xij (t − 1) the allocation units on bid value
j for item i cumulated in the first t − 1 rounds, and denote by Wijr (t − 1) and Wijc (t − 1) the total revenue andcost generated by assigning bid value j to item i during
these periods respectively. In Algorithm 3, the advertiser
samples from the joint posterior distributions of θij , theunknown Poisson rate of the revenue, and µij , the rateof the cost, corresponding to bid value j for item i. We
put independent Gamma prior distributions for these parameters and hence the posterior distributions are also
independent. The posterior samples of these parameters
are then used in a linear program to decide the allocation. This algorithm follows quite intuitively from standard Thompson sampling, in which one generates posterior samples for the unknown parameters, and use themas “plug-in” to solve stage-wise optimization problems.
4.2

CHANCE-CONSTRAINED BUDGETED
THOMPSON SAMPLING
Pt PM PKWe want to ensure P ( u=1 i=1 j=1 cij (u)xij (u) ≤B(t − 1)/(T − t + 1)) ≥ 1 − α ∀t ∈ S holds withposterior credibility 1 − β. To achieve this, we integrate
our Dynamic PCSG into Step 2 of Algorithm 3 byrestructuring the involved optimization program. Algorithm 4 shows Dynamic PCSG in this particular setting.
The output of this procedure is a set of constraints,
which will be used in the linear program of the budgetedKX

B(t − 1)
T −t+1xij ≤ 1, ∀ i = 1, . . . , M

j=1

xij ≥ 0, ∀ i = 1, . . . , M, j = 1, . . . , K
to obtain (x∗ij (t))i=1,...,M,j=1,...,K .
3: The revenue, rij (t), and the cost, cij (t), generated by assigning bid value j on item i are revealed. We update
Xij (t) = Xij (t − 1) + x∗ij (t), Wijr (t) = Wij (t − 1) +rij (t)x∗ij (t), Wijc (t) = Wijc (t − 1) + cij (t)x∗ij (t) andP
PM∗
B(t) = B(t − 1) − K
j=1
i=1 cij (t)xij (t).
4: If B(t) ≤ 0, the algorithm terminates.

Thompson sampling. Algorithm 5 shows how Dynamic
PCSG can be integrated into Algorithm 3. The following
is an immediate consequence of Theorem 3:
Corollary 4. Suppose that any instance of the sampled
program in (16) belongs to R. Suppose 0 ≤ βt , δt ≤ 1
are chosen to satisfy
KM
X−1 
i=0


Nt
(αβt )i (1 − αβt )Nt −i ≤ δtiandX(βt + δt − βt δt ) ≤ βλt∈SConsider a modification of Algorithm 5 such that at any
point of time, if the total budget B is fully depicted, we
refill the shortfall and add extra budget B (so that the
total remaining budget in the next step returns to the fulllevel B). Then the sequence of decisions obtained will
satisfy


t X
M X
K
X
B(t − 1) Pµ Pct |µt 
cij (u)xij (u) ≤T−t+1
u=1 i=1 j=1!
≥ 1 − α ∀t ∈ S≥1−β

Algorithm 4 Dynamic PCSG for the Bidding Problem
1. Set Fij (0), i = 1, . . . , M, j = 1, . . . , K as the prior distribution of µij . For t = 1, . . . , T : Given B(t − 1) andFij (t − 1), the posterior distribution of µij given Ft−1 ,(a) Repeat Nt times:
i. Generate µn
ij ∼ Fij (t − 1) independently foreach item i = 1, . . . , M and bid value j =1, . . . , K.
nii. Generate ξij∼ P oisson(µnij ) for each item
i = 1, . . . , m and bid value j = 1, . . . , K.
(b) Form the constraints
K X
MX
B(t − 1)
n
ξij
xij ≤
, ∀ n = 1, . . . , Nt
T
−t+1
j=1 i=1

Algorithm 5 Chance-constrained Thompson Sampling(CCTS)
Initialize α, βt , δt ∈ [0, 1] satisfying (13). Given a total budget
B(0) = B. For t = 1, ..., T , do the following:
1: For each bid value j and each item i, sample θij from
Gamma(Wijr (t − 1) + 1, Xij (t − 1) + 1) and µij from
Gamma(Wijc (t − 1) + 1, Xij (t − 1) + 1).
2: Run Dynamic PCSG using Nt samples to get the constraints
M
K X
X
B(t − 1)
n
ξij
xij ≤
, ∀ n = 1, . . . , Nt
T
−t+1
j=1 i=1

3: Solve the following linear program:maxxwith Monte Carlo confidence level at least 1 − λ. Pµdenotes the probability of {µt }t=1,...,T , where µt is thecollection (µij )i,j and each element is distributed independently according to the posterior distribution Fij (t −1), and Pct |µt denotes the probability with respect to thecollection (cij )i,j given the realization of (µij )i,j .
We mention that the “modification of Algorithm 5” introduced in Corollary 4 is only a technicality that takes careof the unusual situation when the entire available budget
is prematurely depleted. Since we divide the remaining
budget by the remaining horizon (a common practice toset per-round budgets) to form our constraint at each step,
the scenario of total budget depletion before the last step
rarely happens.
4.3

NUMERICAL RESULTS

We examine the empirical performance of our proposed
strategy on a synthetic dataset with two items and threebid values (M = 2, K = 3) over the time horizon
T = 100. The cost and revenue of each item-bid value
pair follow Poisson distributions with parameters taken
uniformly from an interval that is calibrated from a real
data set owned by a prominent tech firm (blinded forpeer-review purpose). We test with
PMfive different values of the overall budget B = (a i=1 ρ̄i ) × T wherea ∈ [0.5, 0.75, 1, 1.25, 1.5] and ρ̄i is the average cost ofitem i over the K bid values. The choice of B roughlymatches the scale of the total cost over the time. The perround budget is defined as the remainder of the overallbudget divided by the remaining number of rounds.
To test our chance-constrained Thompson sampling(CCTS) in Algorithm 5, we use three different settings
for S, i.e. S1 = {25, 50, 75}, S2 = {20, 40, 60, 80, 100}and S3 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}. We
enforce α = 0.1, β = λ = 0.3, and βt = δt = γ where

subject to

K X
M
X

θij xij

j=1 i=1
K X
MX
B(t − 1)
n
ξij
xij ≤
, ∀ n = 1, . . . , Nt
T
−t+1
j=1 i=1
KX

xij ≤ 1, ∀ i = 1, . . . , M

j=1

xij ≥ 0, ∀ i = 1, . . . , M, j = 1, . . . , K(16)
to obtain (x∗ij (t))i=1,...,M,j=1,...,K .
4: The revenue, rij (t), and the cost, cij (t), generated by assigning bid value j on item i are revealed. We update
Xij (t) = Xij (t − 1) + x∗ij (t), Wijr (t) = Wij (t − 1) +rij (t)x∗ij (t), Wijc (t) = Wijc (t − 1) + cij (t)x∗ij (t) andP
PM∗
B(t) = B(t − 1) − K
j=1
i=1 cij (t)xij (t).
5: If B(t) ≤ 0, the algorithm terminates.

γ is taken as the upper bound depicted in Proposition 1.
With these configurations, the number of constraints in
the involved linear programs are typically in the rangeof thousands, which gives a run-time of a few minutes
in solving the decisions for the whole horizon using oursever machine. Note that, if we consider our online problem a daily problem (common in practice) then this solution time is quite acceptable as we have hours to solve
the problem at each stage. Moreover, the number of constraints and hence the run-time can be further reduced byusing more recent advances in the constraint sampling
literature as depicted at the end of Section 3.1.
For each considered setting, we conduct 500 simulation
runs. For each run, we estimate the proportion of violation of the decision using 100 inner repetitions of ξt , ateach step t ∈ S. Figure 1 depicts the box-plots showing the distribution of the proportion of violation. For
all the tested budget levels and choices of S, CCTS wasable to maintain the proportion of budget violation well
below the 10% tolerance at the relevant steps. This implies, moreover, that the overall violation (i.e., at least

one violation at a step in S) is also below 10%.
Note that the theoretical guarantees studied in the previous sections focus on the feasibility in maintaining thechance constraints. In practice, the objective value performance is also important. To test this, we compare
the performance of CCTS, both regarding budget violation and revenue attainment, against the following algorithms: 1) a hypothetical algorithm that assumes the
distributions of the costs and revenues are all known anddraws Monte Carlo samples from it, otherwise the sameas CCTS; 2) the deterministically constrained Thompson sampling (DCTS) in Algorithm 3; 3) the algorithm
in Badanidiyuru et al. (2013) that uses reward-to-cost ratios; and 4) Besbes and Zeevi (2012) that uses an initial learning phase (in our experiment we set the learning
phase to 50 steps). Figure 2 shows the distributions of
the proportion of violations at t ∈ S2 based on 500 simulation runs, for the five described budget levels. We seethat only CCTS and the hypothetical algorithm maintains
the proportion of violation to well below 10%, whereas
the other three algorithms fluctuate around 20-40%, asthey do not account for the chance constraint on the perround budget. On the other hand, Figure 3 shows theaverage cumulative revenue achieved through the horizon (the bar depicts one standard deviation around theaverage). DCTS appears the best in terms of cumulative
rewards, and Badanidiyuru et al. (2013) and Besbes andZeevi (2012) perform similarly. CCTS achieves less rewards (around 15%), which can be viewed as the priceof maintaining the chance constraint. The hypotheticalalgorithm performs better than CCTS, not surprisingly
given the full distributional knowledge. This behavior
persists for S1 and S3 as well as for several priors wehave tested (similar to plots Figures 2 and 3). Thus, inview of achieving overall performances in terms of bothcontrolling violation proportions and attaining cumulative rewards, our CCTS appears to be superior to all theother considered methods.
The above experiments all used the budget violations calculated using the true underlying distribution of the cost.
In Table 1, we compare with the calculation based on the
evolving posterior distributions, in terms of the averageof all the proportions of violations for t ∈ S1 , S2 andS3 at the five described budget levels. The average proportion of violation based on the posterior distribution isconsistently lower than the one based on the true distribution for all budget levels and S. This is expected since
our chance constraint is maintained under the posterior
distribution (as Theorem 3 states). However, the proportion of violations is maintained below 10% under the true
distribution, thanks to the relatively robust performanceof our approach in abiding with the chance constraint.

Table 1: Comparison of the average proportions of violations based on the true distribution and the updated
posterior distributions over 500 simulation runs
Budget

S1

S2

S3

B1

True Dist.
Posterior Dist.

0.018
0.011

0.019
0.012

0.018
0.009

B2

True Dist.
Posterior Dist.

0.016
0.01

0.015
0.01

0.014
0.008

B3

True Dist.
Posterior Dist.

0.014
0.008

0.013
0.009

0.013
0.007

B4

True Dist.
Posterior Dist.

0.013
0.009

0.011
0.007

0.01
0.005

B5

True Dist.
Posterior Dist.

0.008
0.006

0.008
0.005

0.007
0.004

Alternatively, we also investigated the amount of budget
violation at t ∈ S. Figure 4 depicts the distributions of
the total amounts of budget violation in S1 , S2 and S3 forthe five budget levels over 500 simulation runs. Similar
to the proportion of budget constraint violations, the average amounts of violation for CCTS and DTS tend to bemuch lower than the other three algorithms, with at most
25% of those of the other three algorithms in the samesetting. This suggests a strong dependence between the
proportion and the amount of violation which substantiates the use of CCTS in maintaining over-spending evenin the monetary scale.

5

CONCLUSION

We studied sequential learning subject to constraints thatneed to be satisfied with high probability. We investigated a methodology to obtain posterior statistical guarantees for the feasibility of these constraints, by generalizing the constraint sampling approach in chanceconstraint programming to a two-level Monte Carlo procedure and analyzing the sample size needed in achieving overall feasibility through the learning horizon. We
further incorporated our scheme into Thompson sampling using an online advertisement example, and numerically demonstrated how it led to desirable performancesin both feasibility and optimality. As far as we know,
this work represents the first methodological investigation of “soft” stochastic constraints in sequential learning. In subsequent work, we will investigate the tightening of the requirements in sampled constraints, via for instance analyzing the correlation among decisions at different stages, and will also study the scalability of thisapproach to higher-dimensional problems.

Figure 1: Estimated proportion of violation at each step in S, for S = S1 , S2 , S3 and five different budget levels, using
500 simulation runs under CCTS.

Figure 2: Estimated proportion of violation at each step in S2 , with 500 simulation runs for different algorithms

Figure 3: Average cumulative revenue over T = 100 achieved by different algorithms under S2Figure 4: Total Amount of budget violations occurred over S1 , S2 and S3 for different algorithms
Acknowledgements

References

Support from the Adobe Faculty Research Award isgratefully acknowledged.

Agrawal, S. and Goyal, N. (2012). Analysis of thompson sampling for the multi-armed bandit problem. In

COLT, pages 39.1–39.26.
Amin, K., Kearns, M., Key, P., and Schwaighofer,
A. (2012).
Budget optimization for sponsoredsearch: Censored learning in mdps. arXiv preprint
arXiv:1210.4847.
Audibert, J.-Y. and Bubeck, S. (2010). Best arm identification in multi-armed bandits. In COLT, pages 41–53.
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finitetime analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235–256.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. (2013).
Bandits with knapsacks. In Foundations of Computer
Science (FOCS), 2013 IEEE 54th Annual Symposiumon, pages 207–216. IEEE.
Ben-Tal, A. and Nemirovski, A. (2000). Robust solutions of linear programming problems contaminatedwith uncertain data. Mathematical programming,
88(3):411–424.
Bertsimas, D., Gupta, V., and Kallus, N. (2013).
Data-driven robust optimization.
arXiv preprint
arXiv:1401.0212.
Besbes, O. and Zeevi, A. (2012). Blind network revenue
management. Operations Research, 60(6):1537–1550.
Boesel, J., Nelson, B. L., and Kim, S.-H. (2003). Using ranking and selection to clean up after simulation
optimization. Operations Research, 51(5):814–825.
Calafiore, G. and Campi, M. C. (2005). Uncertain convex programs: randomized solutions and confidence
levels. Mathematical Programming, 102(1):25–46.
Calafiore, G. C. (2017). Repetitive scenario design. IEEE
Transactions on Automatic Control, 62(3):1125–1137.
Calafiore, G. C. and Campi, M. C. (2006). The scenario
approach to robust control design. IEEE Transactions
on Automatic Control, 51(5):742–753.
Calafiore, G. C. and El Ghaoui, L. (2006). On distributionally robust chance-constrained linear programs.
Journal of Optimization Theory and Applications,130(1):1–22.
Campi, M. C. and Garatti, S. (2008). The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3):1211–
1230.
Campi, M. C. and Garatti, S. (2011). A sampling-anddiscarding approach to chance-constrained optimization: feasibility and optimality. Journal of Optimization Theory and Applications, 148(2):257–280.
Carè, A., Garatti, S., and Campi, M. C. (2014). Fastfast algorithm for the scenario technique. Operations
Research, 62(3):662–671.

Chamanbaz, M., Dabbene, F., Tempo, R., Venkataramanan, V., and Wang, Q.-G. (2016). Sequential randomized algorithms for convex optimization in thepresence of uncertainty. IEEE Transactions on Automatic Control, 61(9):2565–2571.
Charnes, A., Cooper, W. W., and Symonds, G. H. (1958).
Cost horizons and certainty equivalents: an approachto stochastic programming of heating oil. Management Science, 4(3):235–263.
De Farias, D. P. and Van Roy, B. (2004). On constraint
sampling in the linear programming approach to approximate dynamic programming. Mathematics ofOperations Research, 29(3):462–478.
Ding, W., Qin, T., Zhang, X.-D., and Liu, T.-Y. (2013).
Multi-armed bandit with budget constraint and variable costs. In AAAI, pages 232–238.
Ferreira, K. J., Simchi-Levi, D., and Wang, H. (2016).
Online network revenue management using thompson
sampling. Working paper.
Lagoa, C. M., Li, X., and Sznaier, M. (2005). Probabilistically constrained linear programs and risk-adjusted
controller design. SIAM Journal on Optimization,
15(3):938–951.
Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in appliedmathematics, 6(1):4–22.
Lejeune, M. A. and Ruszczynski, A. (2007). An efficient trajectory method for probabilistic productioninventory-distribution problems.
Operations Research, 55(2):378–394.
Luedtke, J., Ahmed, S., and Nemhauser, G. L. (2010).
An integer programming approach for linear programswith probabilistic constraints. Mathematical Programming, 122(2):247–272.
Miller, B. L. and Wagner, H. M. (1965). Chance constrained programming with joint constraints. Operations Research, 13(6):930–945.
Pani, A., Raghavan, S., and Sahin, M. (2017). Largescale advertising portfolio optimization in online marketing.
Prékopa, A. (2003). Probabilistic programming. Handbooks in operations research and management science, 10:267–351.
Rossi, R., Hnich, B., Tarim, S. A., and Prestwich, S.
(2011). Finding (α,ϑ)-solutions via sampled scsp. In
IJCAI, pages 2172–2177.
Rossi, R., Hnich, B., Tarim, S. A., and Prestwich, S.
(2015). Confidence-based reasoning in stochastic constraint programming. Artificial Intelligence, 228:129–
152.

Russo, D. and Van Roy, B. (2016). An informationtheoretic analysis of thompson sampling. The Journalof Machine Learning Research, 17(1):2442–2471.
Shi, Y., Zhang, J., and Letaief, K. B. (2015). Optimal
stochastic coordinated beamforming for wireless cooperative networks with csi uncertainty. IEEE Transactions on Signal Processing, 63(4):960–973.
Tran-Thanh, L., Chapman, A., Rogers, A., and Jennings,
N. R. (2012). Knapsack based optimal policies forbudget-limited multi-armed bandits. In AAAI, pages
1134–1140.
Tran-Thanh, L., Stavrogiannis, L., Naroditskiy, V., Robu,
V., Jennings, N. R., and Key, P. (2014). Efficient regretbounds for online bid optimisation in budget-limited
sponsored search auctions. In UAI, pages 809–818.
Villar, S. S., Bowden, J., and Wason, J. (2015). Multiarmed bandit models for the optimal design of clinical
trials: benefits and challenges. Statistical science: areview journal of the Institute of Mathematical Statistics, 30(2):199.
Wang, Z., Deng, S., and Ye, Y. (2014). Close the gaps:
A learning-while-doing algorithm for single-productrevenue management problems. Operations Research,
62(2):318–331.
Xia, Y., Li, H., Qin, T., Yu, N., and Liu, T.-Y. (2015).
Thompson sampling for budgeted multi-armed bandits. In IJCAI, pages 3960–3966.
Zymler, S., Kuhn, D., and Rustem, B. (2013). Distributionally robust joint chance constraints with secondorder moment information. Mathematical Programming, pages 1–32.

Supplemental Materials: Missing Proofs

Proof of Theorem 3. From Theorem 2 part 2, if we use
βt , δt and Nt satisfying (12), we have

Proof of Theorem 2. Part 1.

EM C [Pµt (Pξt |µt (f (x; ξt ) ∈ At |Ft−1 ) < 1 − α)]Note that (6) is equivalent to≤ 1 − (1 − βt )(1 − δt )Pµ (Pξ|µ (f (x, ξ) ∈/ A) ≥ α) ≤ β(17)

We want to show (14), which is equivalent to

By the Markov inequality,
Pµ (Pξ|µ (f (x, ξ) ∈/ A) ≥ α) ≤(21)

PM C (Pµ1:T (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 ) < 1 − α
Eµ [Pξ|µ (f (x, ξ) ∈
/ A)]
α

So
Eµ [Pξ|µ (f (x, ξ) ∈
/ A)]
≤β
α

for some t ∈ S) > β) ≤ λ(22)Note that the left hand side of (22) is bounded from above
as

(18)

PM C (Pµ1:T (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 ) < 1 − αfor some t ∈ S) > β)X
≤ PM CPµ1:T (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 )guarantees (17). Note that (18) is equivalent toEµ [Pξ|µ (f (x, ξ) ∈ A)] ≥ 1 − αβ

t∈S

!

or
Pµ,ξ (f (x, ξ) ∈ A) ≥ 1 − αβ

< 1 − α) > β(19)where Pµ,ξ denotes the joint probability with respect tothe posterior distribution of µ and the stochasticity of ξ
given µ. The Monte Carlo scheme in PCSG precisely
generates samples according to Pµ,ξ . Theorem 1 implies
that choosing N satisfying (8) in the sampled program(7) to obtain x guarantees (19), and consequently (6),with probability at least 1 − δ. This concludes the proofof Part 1.
Part 2. Let M be the event

≤

"
X
1
EM C
Pµ1:T (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 )βt∈S#< 1 − α)=(by the Markov inequality)

1X
EM C [Pµt (Pξt |µt (ft (xt , ξt ) ∈ At |Ft−1 )
β
t∈S

≤

< 1 − α)]1X
(1 − (1 − βt )(1 − δt )) (by using (21))β
t∈SPµ (Pξ|µ (f (x; ξ) ∈ A) ≥ 1 − α) ≥ 1 − βin the sample space under the Monte Carlo sample generation (that obtains x). Let IM be the indicator function
on the occurrence of M. Then we have
EM C [IM ]=PM C (Pµ (Pξ|µ (f (x; ξ) ∈ A) ≥ 1 − α) ≥ 1 − β)

≥

1−δ

(20)

by (9). Now, consider
EM C [Pµ (Pξ|µ (f (x; ξ) ∈ A) ≥ 1 − α)]≥ EM C [Pµ (Pξ|µ (f (x; ξ) ∈ A) ≥ 1 − α)IM ]≥ EM C [(1 − β)IM ]≥ (1 − β)(1 − δ)by using (20) in the last inequality. This concludes theproof.

Hence
1X(1 − (1 − βt )(1 − δt )) ≤ λ
β

(23)

t∈S

guarantees that (22) holds. Noting that (23) is equivalentto (13), we conclude our theorem.
Proof of Proposition
1. Let s = |S|. Setting βt = δt =Pγ, we have t∈S (βt + δt − βt δt ) = s(2γ − γ 2 ). We
want s(2γ − γ 2 ) ≤ βλ, or equivalently
γ 2 − 2γ + βλ/s ≥ 0(24)

Since the left hand side of (24) is a convex quadratic
function, (24) holds if and only ifppγ ≥ 1 + 1 − βλ/s or γ ≤ 1 − 1 − βλ/s
The first condition is never satisfied since γ must be ≤ 1.
The second condition is valid and gives (14).

Proof of Proposition 2. Without loss of generality, welabel t as the counter in S for convenience (i.e., assume that t = ζ(t) by relabeling βt and δt ). We wantP∞
t=1 (βt + δt − βt δt ) ≤ βλ holds so that (14) holds
regardless of T . Note that
∞
∞
∞
X
X
X
(βt + δt − βt δt ) = 2
γt −
γt2
t=1

t=1

(25)

t=1

We analyze the two terms of the right hand side of (25).
By definition γt = η if and only if t ≤ 1/η 1/ρ . Thus, forthe first term, we have


∞
∞
X
X
1
1

2
γt = 2 b 1/ρ c · η +tρη
t=1
t=b1/η 1/ρ c+1
!
Z ∞
1
1−1/ρ
+
≤2 η
du
ρ
b1/η 1/ρ c u11≤ 2 η 1−1/ρ +ρ − 1 (1/η 1/ρ − 1)ρ−1(26)
For the second term in (25), we have
∞
X

∞
X
1
1
γt2 = b 1/ρ c · η 2 +
2ρ
t
η
t=1
t=b1/η 1/ρ c+1
Z ∞
2
η
1
+
du
≥ 1/ρ
2ρ
η
+1
b1/η 1/ρ c+1 u≥η2
η 1/ρ + 1

+

1
1
(27)
2ρ − 1 (1/η 1/ρ + 1)2ρ−1

Therefore, combining(26)Pand (27) into (25), we haveP∞∞(15) implies 2 t=1 γt − t=1 γt2 ≤ βλ or (14).
Proof of Corollary 4. The corollary follows immediately by noticing that the linear program (16) is triviallyconvex, and applying Theorem 3.