Improvements and Generalizations of Stochastic Knapsack and
Markovian Bandits Approximation Algorithms
Will Ma∗

arXiv:1306.1149v4 [cs.DS] 13 Sep 2016

September 14, 2016

Abstract
We study the multi-armed bandit problem with arms which are Markov chains with rewards.
In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution
is intractable. We provide approximation algorithms for a more general model which includes
Markov decision processes and non-unit transition times. When preemption is allowed, we
provide a ( 12 −ε)-approximation, along with an example showing this is tight. When preemption
1
4
isn’t allowed, we provide a 12
-approximation, which improves to a 27
-approximation when
transition times are unity. Our model encompasses the Markovian Bandits model of Gupta et
al, the Stochastic Knapsack model of Dean, Goemans, and Vondrak, and the Budgeted Learning
model of Guha and Munagala, and our algorithms improve existing results in all three areas. In
our analysis, we encounter and overcome to our knowledge a novel obstacle—an algorithm that
provably exists via polyhedral arguments, but cannot be found in polynomial time.

∗

Operations Research Center, Massachusetts Institute of Technology, willma@mit.edu.

1

1

Introduction.

We are interested in a broad class of stochastic control problems: there are multiple evolving systems
competing for the attention of a single operator, who has limited time to extract as much reward
as possible. Classical examples include a medical researcher allocating his time between different
clinical trials, or a graduate student shifting her efforts between different ongoing projects. Before
we describe our model in detail, we introduce the three problems in the literature which are special
cases of our problem, and motivated our avenues of generalization.

1.1

Markovian Bandits.

The Markovian multi-armed bandit problem is the following: there are some number of Markov
chains (arms), each of which only evolve to the next node1 and return some reward when you play
(pull ) that arm; the controller has to allocate a fixed number of pulls among the arms to maximize
expected reward. The reward returned by the next pull of an arm depends on the current node
that arm is on. When an arm is pulled, the controller observes the transition taken before having
to choose the next arm to pull. Multi-armed bandit (MAB) problems capture the tradeoff between
exploring arms that could potentially transition to high-reward nodes, versus exploiting arms that
have the greatest immediate payoff.
The infinite-horizon version of this problem with discounted rewards can be solved by the
celebrated index policy of Gittins; see the book [GGW11] for an in-depth treatment of Gittins
indices. However, all of this theory is crucially dependent on the time horizon being infinite (see
[GGW11, sect. 3.4.1]). The Gittins index measures the asymptotic performance of an arm, and
does not apply when there is a discrete number of time steps remaining.
Also, when we refer to multi-armed bandit in this paper, it is not to be confused with the
popular Stochastic Bandits model, where each arm is an unknown reward distribution, playing
that arm collects a random sample from its distribution, and the objective is to learn which arm
has the highest mean in a way that minimizes regret. For a comprehensive summary on Stochastic
Bandits and related bandit models, we refer the reader to the survey of Bubeck and Cesa-Bianchi
[BCB12]. The main difference with our problem is that despite its stochastic nature, all of the
transition probabilities are given as input and we can define an exact optimization problem (and
the challenge is computational), whereas in Stochastic Bandits there is uncertainty in the parameter
information (and the challenge is to compete with an omniscient adversary).
The finite-horizon Markovian Bandits problem is intractable even in special cases (see Goel et
al. [GGM06], and the introduction of Guha and Munagala [GM13]), so we turn to approximation
1
-approximation2 by Gupta et al. [GKMR11].
algorithms. The state of the art is an LP-relative 48
4
Our results improve this bound by providing an LP-relative 27
-approximation for a more general
problem.
1

We use the word node instead of state to avoid confusion with the notion of a state in dynamic programming.
All of the problems we discuss will be maximization problems, for which an α-approximation refers to an algorithm
that attains at least α of the optimum.
2

2

1.1.1

Martingale Reward Bandits and Bayesian Bandits.

While Markovian Bandits is a different problem from Stochastic Bandits, it is a generalization of
the closely related Bayesian Bandits, where each arm is an unknown reward distribution, but we
have prior beliefs about what these distributions may be, and we update our beliefs as we collect
samples from the arms. The objective is to maximize expected reward under a fixed budget of
plays.
For each arm, every potential posterior distribution can be represented by a node in a Markov
chain, and the transitions between nodes correspond to the laws of Bayesian inference. However,
the resulting Markov chain is forced to satisfy the martingale condition, ie. the expected reward at
the next node must equal the expected reward at the current node, by Bayes’ law. This condition is
not satisfied by Stochastic Knapsack with correlated rewards, as well as certain natural applications
of the bandit model. For instance, in the marketing problems studied by Bertsimas and Mersereau
[BM07], the arms represent customers who may require repeated pulls (marketing actions) before
they transition to a reward-generating node.
Nonetheless, fruitful research has been done in the Bayesian Bandits setting — Guha and
Munagala [GM13] show that constant-factor approximations can be obtained even under a variety
of side constraints. The complexity necessary for a policy to be within a constant factor of optimal is
much lower under the martingale assumption. For the basic bandit problem with no side constraints,
Farias and Madan [FM11] observe that irrevocable policies — policies which cannot start an arm,
stop pulling it at some point, and resume it later — extract a constant fraction of the optimal
(non-irrevocable) reward. Motivated by this, [GM13] obtains a ( 21 − ε)-approximation for Bayesian
Bandits that is in fact a irrevocable policy.
1.1.2

Irrevocable Bandits.

The above can be contrasted with the work of Gupta et al., who construct a non-martingale
instance where irrevocable policies (they refer to these policies as non-preempting) can only extract
an arbitrarily small fraction of the optimal reward [GKMR11, appx. A.3]. Therefore, without the
martingale assumption, we can only hope to compare irrevocable policies against the irrevocable
optimum. We provide a ( 21 − ε)-approximation for this problem, which we refer to as Irrevocable
Bandits.

1.2

Stochastic Knapsack.

The Stochastic Knapsack (SK) problem was introduced by Dean et al. in 2004 [DGV04] (see
[DGV08] for the journal version). We are to schedule some jobs under a fixed time budget. Each
job has a stochastic reward and processing time whose distribution is known beforehand. We
sequentially choose which job to perform next, only discovering its length and reward in real-time
as it is being processed. The objective is to maximize the expected reward before the time budget is
spent. A major focus of their work is on the benefit of adaptive policies (which can make dynamic

3

choices based on the instantiated lengths of jobs processed so far) over non-adaptive policies (which
must fix an ordering of the jobs beforehand), but in our work all policies will be adaptive.
Throughout [DGV08], the authors assume uncorrelated rewards — that is, the reward of a job is
independent of its length. The state of the art for this setting is a ( 12 −ε)-approximation by Bhalgat
[Bha11]; a ( 12 − ε)-approximation is also obtained for the variant where jobs can be canceled at
any time by Li and Yuan [LY13]. [GKMR11] provides a 18 -approximation for Stochastic Knapsack
1
with potentially correlated rewards, and a 16
-approximation for the variant with cancellation. We
improve these bounds by providing an LP-relative ( 12 − ε)-approximation for a problem which
generalizes both variants with correlated rewards. Furthermore, we construct an example where
the true optimum is as small as 21 + ε of the optimum of the LP relaxation. Therefore, our bound
is tight in the sense that one cannot hope to improve the approximation ratio using the same LP
relaxation.
However, it is important to mention that our results, as well as the results of [GKMR11], require
the job sizes and budget to be given in unary, since these algorithms use a time-indexed LP. It
appears that this LP is necessary whenever correlation is allowed — the non-time-indexed LP can
be off by an arbitrarily large factor (see [GKMR11, appx. A.2]). Techniques for discretizing the
time-indexed LP if the job sizes and budget are given in binary are provided in [GKMR11], albeit
losing some approximation factor. Nonetheless, in this paper, we always think of processing times
as discrete hops on a Markov chain, given in unary. Note that stronger hardness results than those
aforementioned can be obtained when the sizes are given in binary (see Dean et al. [DGV05], and
the introduction of [DGV08]).

1.3

Futuristic Bandits and Budgeted Bandits.

Starting with [GM07a, GM07b], Guha and Munagala have studied many variants of budgeted learning problems — including switching costs, concave utilities, and Lagrangian budget constraints.
See [GM08] for an updated article that also subsumes some of their other works. Their basic setting, which we refer to as Futuristic Bandits, is identical to Bayesian Bandits (ie. there are Markov
chains satisfying the martingale condition), except no rewards are dispensed during the execution
of the algorithm. Instead, once the budget3 is spent, we pick the arm we believe to be best, and
only earn the (expected) reward for that arm. A 14 -approximation is provided in [GM08], and this is
improved by the same authors to a ( 13 − ε)-approximation in [GM13]. Our algorithm works without
4
the martingale assumption, but the approximation guarantee is only 27
.

1.4

MAB superprocess with multi-period actions.

Motivated by these examples, we now introduce our generalized problem, which we call MAB
superprocess with multi-period actions. Consider the Markovian Bandits setting, except we allow
for a more general family of inputs, in two ways.
3

In some variants, there is a cost budget instead of a time budget, and exploring each arm incurs a different cost.
We explain in Section 2 why our model also generalizes this setting, which they refer to as Budgeted Bandits.

4

First, we allow transitions on the Markov chains to consume more than one pull worth of budget.
We can think of these transitions as having a non-unit processing time. The processing times can
be stochastic, and correlated with the node transition that takes place. The rewards can be accrued
upon pulling the node, or only accrued if the processing time completes before the time budget
runs out. The applications of such a generalization to US Air Force jet maintenance have recently
been considered in Kessler’s thesis [Kes13], where it is referred to as multi-period actions.
The second generalization is that we allow each arm to be a Markov decision process; such a
problem is referred to as MAB superprocess in Gittins et al. [GGW11]. Now, when the controller
pulls an arm, they have a choice of actions, each of which results in a different joint distribution
on reward, processing time, and transition taken.
The purpose of the first generalization is to allow MAB to model the jobs from Stochastic
Knapsack which have rewards correlated with processing time and can’t be canceled. The purpose
of the second generalization is to allow MAB to model Futuristic Bandits, where exploiting an
arm corresponds to a separate action. The details of our reductions, along with examples, will be
presented throughout Section 2, once we have introduced formal notation.
We consider two variants under our general setting: the case with preemption (ie. we can start
playing an arm, not play it for some time steps, and resume playing it later), and the case without
preemption. The variant without preemption is necessary to generalize Stochastic Knapsack and
Irrevocable Bandits. The variant with preemption generalizes Markovian Bandits and Futuristic
Bandits.

1.5

Outline of results.

Our main results can be outlined as follows:
• Reductions from earlier problems to MAB superprocess with multi-period actions [sect. 2]
• Polynomial-sized LP relaxations for both variants of MAB superprocess with multi-period
actions, and polyhedral proofs that they are indeed relaxations [sect. 2.5]
• A ( 21 − ε)-approximation for MAB superprocess with multi-period actions—no preemption,
with runtime polynomial in the input and 1ε [sect. 3]
• A matching upper bound where it is impossible to obtain more than
the LP relaxation [sect. 3.1]
• A

4
27 -approximation

• A

1
12 -approximation

1
2

+ ε of the optimum of

for MAB superprocess (with preemption) [sect. 4]
for MAB superprocess with multi-period actions (and preemption) [sect. 4.3]

The way in which these approximation ratios improve previous results on SK and MAB is
summarized in Tables 1 and 24 .
4

Some of these results have appeared in a preliminary conference version of this article [Ma14].

5

Table 1: Comparison of results for SK.

Problem

Previous
Result

Binary SK
Binary SK w/ Cancellation
Unary Correlated SK
Unary Correlated SK w/ Cancellation

1
2 − ε [Bha11]
1
2 − ε [LY13]
1
8 [GKMR11]
1
16 [GKMR11]

Result as a Special
Case of Our Problems

1
2

− ε [thm. 2.4], [Ma14]
1
2 − ε [thm. 2.4]

Table 2: Comparison of results for MAB.

Problem

Previous
Result

Markovian Bandits
Irrevocable Bandits
Futuristic Bandits
Budgeted Bandits

1.6

1
48

-

Result as a Special
Case of Our Problems
4
27

[thm. 2.5], [Ma14]
1
2 − ε [thm. 2.4]
4
27 [thm. 2.5]
1
12 [thm. 2.6]

Result with
Martingale Assumption
1
2
1
2
1
3
1
4

−ε
−ε
−ε
−ε

[GM13]
[GM13]
[GM13]
[GM08]

Sketch of techniques.

In the variant without preemption, we show that given any feasible solution to the LP relaxation,
there exists a policy which plays every node with half the probability it is played in the LP solution.
This would yield a 12 -approximation, but the policy cannot be specified in polynomial time, because
the previous argument is purely existential. Instead, we show how to approximate the policy via
sampling, in a way that doesn’t cause error propagation.
In the variant with preemption, we provide a priority-based approximation algorithm which
intuitively achieves the same goals as the algorithm of Gupta et al. [GKMR11]. However, our
algorithm, which has eliminated the need for their convex decomposition and gap filling operations,
allows for a tighter analysis. Furthermore, it grants the observation that we can get the same result
for the more general model of Markov decision processes and non-unit transition times. Finally,
our analysis makes use of Samuels’ conjecture [Sam66] for n = 3 (which is proven), and this helps
us bound the upper tail.

1.7

Related work.

Most of the related work on bandits, stochastic knapsack/packing, and budgeted learning have
already been introduced in the earlier subsections, so we only mention the neglected results here.
One such result for stochastic knapsack is the bi-criteria (1 − ε)-approximation of Bhalgat et al.
[BGK11] that uses 1 + ε as much time; such a result is also obtained via alternate methods by Li
and Yuan [LY13] and generalized to the setting with both correlated rewards and cancellation. A
new model that adds geometry to SK by associating jobs with locations in a metric space is the
6

stochastic orienteering problem introduced by Gupta et al. [GKNR14]. The benefit of adaptive
policies for this problem is also addressed by Bansal and Nagarajan [BN14].
Another example of a stochastic optimization problem where adaptive policies are necessary is
the stochastic matching problem of Bansal et al. [BGL+ 12] — in fact we use one of their lemmas in
our analysis. Recently, the setting of stochastic matching has been integrated into online matching
problems by Mehta and Panigrahi [MP12].
All of the problems described thus far deal only with expected reward. Recently, Ilhan et al.
[IID11] studied the variant of SK where the objective is to maximize the probability of achieving
a target reward; older work on this model includes Carraway et al. [CSW93]. Approximation
algorithms for minimizing the expected sum of weighted completion times when the processing
times are stochastic are provided in Möhring et al. [MSU99], and Skutella and Uetz [SU01]. SK
with chance constraints — maximizing the expected reward subject to the probability of running
overtime being at most p — is studied in Goel and Indyk [GI99], and Kleinberg et al. [KRT00].
Looking at more comprehensive synopses, we point the reader interested in infinite-horizon
Markovian Bandits to the book by Gittins et al. [GGW11]. Families of bandit problems other
than Markovian, including Stochastic and Adversarial, are surveyed by Bubeck and Cesa-Bianchi
[BCB12]. For an encyclopedic treatment of using dynamic programming to solve stochastic control problems, we refer the reader to the book by Bertsekas [Ber95]; for stochastic scheduling in
particular, we refer the reader to the book by Pinedo [Pin12].

2

Fully generalized model.

We set out to define notation for the MAB superprocess with multi-period actions problem described
in Subsection 1.4. Let n ∈ N denote the number of arms, which are Markov decision processes with
rewards. There is a budget of B ∈ N time steps over which we would like to extract as much reward
in expectation as possible. The arms could also have multi-period actions, which are transitions
that take more than one time step to complete.
Formally, for each arm i, let Si denote its finite set of nodes, with the root node being ρi . To
play an arm i that is currently on node u ∈ Si , we select an action a from the finite, non-empty
action set A, after which the arm will transition to a new node v ∈ Si in t time steps, accruing
reward over this duration. We will also refer to this process as playing action a on node u, since
for each pair (u, a), we are given as input the joint distribution of the destination node, transition
time, and reward. Specifically, for all a ∈ A, u, v ∈ Si , and t ∈ [B]5 , let pau,v,t denote the probability
of transitioning to node v in exactly t time steps, when action a is played on node u. We will
a
refer to this transition by the quadruple (u, a, v, t), and when it occurs, let ru,v,t,t
0 ∈ [0, ∞) denote
the reward accrued t0 time steps from the present, for all t0 = 0, . . . , t − 1. We will impose that
P
PB a
v∈Si
t=1 pu,v,t = 1 for all i ∈ [n], u ∈ Si , and a ∈ A.
5

For any positive integer m, [m] refers to the set {1, . . . , m}.

7

2.1

Simple reductions.

We would like to explain why some of the presumptions in the preceding paragraph are WOLOG:
• We assumed that all nodes across all arms have the same set A of feasible actions. This can
be easily achieved by taking unions of action sets, and defining inadmissible actions to be
duplicates of admissible ones.
• We assumed that all transitions take time t ≤ B, with B being the time budget. Indeed, all
transitions (u, a, v, t) with t > B can be amalgamated into the transition (u, a, v, B), since
a
0
the exact value of t will never be relevant, and all of the rewards ru,v,t,t
0 for t ≥ B will never
be accrued.
a
• We assumed that each reward ru,v,t,t
0 is deterministic. Had they been random with known
distributions instead, our problem does not change if we replace each reward with its certainty
equivalent, since the objective value only cares about expected reward. Furthermore, even if
the rewards over t0 = 0, . . . , t − 1 were correlated, ie. a low reward at t0 = 0 could warn us of
lower rewards later on, we cannot interrupt the transition once it begins, so this information
is irrelevant. Note that we do still need to split up the expected reward over t0 = 0, . . . , t,
since our time budget B may run out in the middle of the transition.

PB a
P
• We assumed that
t=1 pu,v,t = 1, ie. the arm always transitions onto a new node
v∈Si
instead of stopping. This clearly loses no generality since we can always add unit-time selfloop transitions with zero reward.
Next, we perform a more complicated reduction to eliminate all transitions with non-unit processing times. For any transition (u, a, v, t) with t > 1:
1. Add dummy nodes w1 , . . . , wt−1 .
2. Set transition probability pau,w1 ,1 = pau,v,t , and change pau,v,t to be 0.
3. Set transition probabilities pbw1 ,w2 ,1 = . . . = pbwt−1 ,v,1 = 1 for all b ∈ A.
4. Set all other transition probabilities involving w1 , . . . , wt−1 to be 0.
a
a
b
a
b
a
5. Set rewards ru,w
= ru,v,t,0
, rw
= ru,v,t,1
, . . . , rw
= ru,v,t,t−1
for all b ∈ A.
1 ,1,0
1 ,w2 ,1,0
t−1 ,v,1,0

We call w1 , . . . , wt−1 bridge nodes. So long as we enforce the bridge nodes must be played as soon
as they are reached, it is clear that the new problem is equivalent to the old problem. Repeat this
process over all transitions (u, a, v, t) with t > 1. We will eliminate the subscripts t, t0 and just
a now that all transitions with t > 1 have been reduced to occur with probability 0.
write pau,v , ru,v
a now that there are no more
It will also be convenient to eliminate the v subscript from ru,v
P
a , and consider the
processing times. For all i ∈ [n], u ∈ Si , and a ∈ A, define rua = v∈Si pau,v · ru,v
Markov decision process that earns deterministic reward rua every time action a is played on node

8

a that depends on the destination node v. Under the objective of
u, instead of a random reward ru,v
maximizing expected reward, the two models are equivalent, as explained in the third bullet above.
Finally, we assume we have converted each rooted Markov decision process into a layered acyclic
digraph, up to depth B. That is, there exists a function depth mapping nodes to 0, . . . , B such that
depth(ρi ) = 0 for all i ∈ [n], and all transitions (u, a, v) with pau,v > 0 satisfy depth(v) = depth(u)+1.
This can be done by expanding each node in the original graph into a time-indexed copy of itself
for t = 1, . . . , B—we refer to [GKMR11, appx. E.1] for the standard reduction, which immediately
generalizes to the case of Markov decision processes with bridge nodes.

Remark 2.1. We would like to point out that our reductions and transformations are stated in a way
to maximize ease of exposition. While they are all polynomial-time, it would reduce computational
overhead to remove irrelevant nodes before implementation.

2.2

Problem statement.

S
After all the reductions, let Si denote the set of nodes of arm i, and let S = ni=1 Si . Let B ⊂ S
denote the set of bridge nodes; note that ρi ∈ B for any i is not possible. Let Par(u) = {(v, a) ∈
S × A : pav,u > 0}, the (node, action) combinations that have a positive probability of transitioning
to u.
Each Markov decision process i starts on its root node, ρi . At each time step, we choose an
arm to play along with an action a, getting reward rua , where u is the node that arm was on. We
realize the transition that is taken before deciding the arm and action for the next time step. Of
course, if u transitions onto a bridge node, then we have no decision in the next time step, being
forced to play the same arm again, say with a default action α ∈ A. For convenience, we will also
allow ourselves to play no arm at a time step6 . The objective is to maximize the expected reward
accrued after a budget of B time steps.
Algorithms for this problem are described in the form of an adaptive policy, a specification of
which arm and action to play for each state the system could potentially be in. A state in this case
is determined by the following information: the node each arm is on, and the time step we are at7 .
The optimal policy could theoretically be obtained by dynamic programming, but of course there
are exponentially many states, so this is impractical.
However, we still write the Bellman state-updating equations as constraints to get a linear
program whose feasible region is precisely the set of admissible policies. After adding in the
objective function of maximizing expected reward, solving this exponential-sized linear program
would be equivalent to solving our problem to optimality.
First we need a bit more notation. Let S = S1 × . . . × Sn ; we call its elements joint nodes. For
π ∈ S and u ∈ Si , let π u denote the joint node where the i’th component of π has been replaced by
u. A state can be defined by a joint node π with a time t. Let yπ,t be the probability of having arms
6

Since rewards are non-negative, doing nothing cannot be optimal. However, it makes the analysis cleaner.
Even though we have converted all Markov decision processes into layered acyclic digraphs, we cannot deduce the
time elapsed from the nodes each arm is on, since we allow ourselves to not play any arm at a time step. Therefore,
the time step must be included separately in the state information.
7

9

a
on nodes according to π at the beginning of time t. Let zπ,i,t
be the probability we play arm i at
time t with action a, when the arms are on nodes according to π. Some (π, t) pairs are impossible
states; for example we could never be at a joint node with two or more arms on bridge nodes, and
we could not get an arm on a node of depth 5 at the beginning of time 5. However, we still have
variables for these (π, t) pairs8 .
Our objective is
n X
B
XX
X
a
max
rπai
zπ,i,t
(1)
t=1

π∈S i=1 a∈A

with the following constraints on how we can play the arms:
n X
X

a
zπ,i,t
≤ yπ,t

π ∈ S, t ∈ [B]

(2a)

α
zπ,i,t
= yπ,t

π ∈ S, i : πi ∈ B, t ∈ [B]

(2b)

a
zπ,i,t
≥0

π ∈ S, i ∈ [n], a ∈ A, t ∈ [B]

(2c)

i=1 a∈A

The novel constraint is (2b), which guarantees that we must play a bridge node upon arrival. The
remaining constraints update the yπ,t ’s correctly:
y(ρ1 ,...,ρn ),1 = 1

(3a)
π ∈ S \ {(ρ1 , . . . , ρn )} (3b)

yπ,1 = 0
yπ,t = yπ,t−1 −

n X
X

a
zπ,i,t−1
+

i=1 a∈A

n
X

X

zπau ,i,t−1 · pau,πi

t > 1, π ∈ S

(3c)

i=1 (u,a)∈Par(πi )

Essentially, the only decision variables are the z-variables; there are as many y-variables as
P
equalities in (3a)-(3c). These constraints guarantee π∈S yπ,t = 1 for all t ∈ [B], and combined
with (2a), we obtain
n X
XX

a
zπ,i,t
≤1

t ∈ [B]

(4)

π∈S i=1 a∈A

Let (ExpLP) denote the linear program defined by objective (1) and constraints (2a)-(2c), (3a)(3c) which imply (4). This formally defines our problem, which we will call MAB superprocess with
multi-period actions.

2.3

No preemption variant.

We describe the variant of the problem where preemption is not allowed. For each arm i ∈ [n], we
add a terminal node φi . The arm transitions onto φi if, at a time step, we don’t play it while it’s
on a non-root node.
Now we write the exponential-sized linear program for this problem. Let Si0 = Si ∪ {φi } for all
i ∈ [n]. Let S 0 = S10 × . . . × Sn0 \ {π : πi ∈
/ {ρi , φi }, πj ∈
/ {ρj , φj }, i 6= j}, where we have excluded
8

Once again, we prioritize notational convenience over computational conciseness; see Remark 2.1.

10

the joint nodes with two or more arms in the middle of being processed, since this is impossible
without preemption. For π ∈ S 0 , let I(π) = {i : πi 6= φi }, the indices of arms that could be played
from π.
The objective is
B
X X X
X
a
max
rπai
zπ,i,t
(5)
π∈S 0 i∈I(π) a∈A

with very similar constraints on the z-variables:
X X
a
zπ,i,t
≤ yπ,t

t=1

π ∈ S 0 , t ∈ [B]

(6a)

α
zπ,i,t
= yπ,t

π ∈ S 0 , i : πi ∈ B, t ∈ [B]

(6b)

a
zπ,i,t
≥0

π ∈ S 0 , i ∈ I(π), a ∈ A, t ∈ [B]

(6c)

i∈I(π) a∈A

The only difference from (2a)-(2c) is that arms on terminal nodes cannot be played. However, the
state-updating constraints become more complicated, because now an arm can make a transition
even while it is not being played, namely the transition to the terminal node. Let Ai = {π ∈ S 0 :
πi ∈
/ {ρi , φi }}, the joint nodes with arm i in the middle of being processed. We call arm i the active
S
arm. Let A = ni=1 Ai . For π ∈ S 0 , let P(π) denote the subset of S 0 that would transition to π

S
with no play: if π ∈
/ A, then P(π) = {π} ∪
{π u : u ∈ Si \ {ρi }} ; if π ∈ A, then P(π) = ∅.
i∈I(π)
/
With this notation, we update the y-variables as follows:
y(ρ1 ,...,ρn ),1 = 1

(7a)

yπ,1 = 0
yπ,t =

X 

yπ0 ,t−1 −

π 0 ∈P(π)

yπ,t =



X
a:(ρi ,a)∈Par(πi )

yπ,t =

X

X X

zπa0 ,i,t−1



i∈I(π 0 )

a∈A

X


zπa0 ,i,t−1 · paρi ,πi

π ∈ S 0 \ {(ρ1 , . . . , ρn )}

(7b)

t > 1, π ∈ S 0 \ A

(7c)

t > 1, i ∈ [n], π ∈ Ai , depth(πi ) = 1 (7d)

π 0 ∈P(π ρi )

zπau ,i,t−1 · pau,πi

t > 1, i ∈ [n], π ∈ Ai , depth(πi ) > 1 (7e)

(u,a)∈Par(πi )

(7c) updates yπ,t for π ∈
/ A, ie. joint nodes with no active arms. Such a joint node π can only
be arrived upon by making no play from a joint node in P(π).
(7d), (7e) update yπ,t for π ∈ A. To get to joint node π ∈ Ai , we must have played arm i during
the previous time step and transitioned to node πi . However, the restrictions on the previous joint
node depend on whether depth(πi ) = 1. If so, then arm i was on ρi at time step t−1, so it’s possible
to get to π from any joint node in P(π ρi ). That is, in the previous joint node, there could have
been an active arm that is not i. This is reflected in (7d). On the other hand, if depth(πi ) > 1,
then arm i must have been the active arm at time step t − 1, as described in (7e).
Like before, these equations guarantee that at each time step, we are at exactly one joint node,
P
ie. π∈S 0 yπ,t = 1. Combined with (6a), we obtain
X X X
a
zπ,i,t
≤1
t ∈ [B]
(8)
π∈S 0 i∈I(π) a∈A

11

Let (ExpLP0 ) denote the linear program defined by objective (5) and constraints (6a)-(6c),
(7a)-(7e) which imply (8). This formally defines MAB superprocess with multi-period actions—no
preemption.

2.4

Reductions from SK and MAB.

Before we proceed, let’s describe how this model generalizes the problems discussed in the introduction. The generalization of the setting of Markovian Bandits (and its non-preempting analogue
Irrevocable Bandits) is immediate: define the action set A to only contain some default action α,
and don’t have any bridge nodes.
For all variants of SK, the necessary reductions have already been described in Subsection 2.1,
but the following examples should reiterate the power of our model:
• Consider a job that takes time 5 with probability 31 , and time 2 with probability 23 (and cannot
be canceled once started). If it finishes, the reward returned is 2, independent of processing
time. This can be modeled by fig. 1 where rB = 34 , rE = 2, and B = {B, C, D, E}. Note that
instead of placing reward 2 on arc (B, C 0 ), we have equivalently placed reward 34 on node
B. A corollary of this reduction is that the following reward structure is equivalent to the
original for the objective of maximizing expected reward: a guaranteed reward of 43 after 2
time steps, after which the job may run for another 3 time steps to produce an additional 2
reward.
• Consider the same job as the previous one, except the reward is 4 if the processing time was
5, while the reward is 1 if the processing time was 2 (the expected reward for finishing is still
2). All we have to change in the reduction is setting rB = 32 and rE = 4 instead.
• Consider either of the two jobs above, except cancellation is permitted (presumably on node
C, after observing the transition from node B). All we have to change in the reduction is
setting B = ∅ instead.
• Consider the job from the second bullet that can be canceled, and furthermore, we find out
after 1 time step whether it will realize to the long, high-reward job or the short, low-reward
job. This can be modeled by fig. 2 where rB 0 = 1, rE = 4, and B = ∅.
Whether preemption is allowed is determined at a global level, although this is irrelevant if no job
can be canceled in the first place. We would like to point out that preemption can be necessary
for optimality even under the simplest setting of uncorrelated SK (Appendix A), so disallowing
preemption results in a distinct problem.
For Futuristic Bandits, suppose the exploration phase contains T time steps. Then we set
B = 2T + 1 and add to each node a separate “exploit” action that returns reward ru in processing
time T + 1 (and there is no other way to obtain reward). Clearly, we can explore for at most T time
steps if we are going to earn any reward at all9 . B is chosen to be 2T + 1 so that it is impossible
9

Note that it is never beneficial in a Martingale setting to not make full use of the T exploration steps.

12

Figure 1: A Markov chain representing a SK job with correlated rewards.

Figure 2: Another Markov chain representing a SK job with correlated rewards.

to collect exploitation rewards from more than one arm. Budgeted Bandits can be modeled by
combining the reductions for Stochastic Knapsack and Futuristic Bandits.

2.5

Polynomial-sized LP relaxations.

We now write the polynomial-sized LP relaxations of our earlier problems. We keep track of
the probabilities of being on the nodes of each arm individually without considering their joint
distribution. Let su,t be the probability arm i is on node u at the beginning of time t. Let xau,t be
the probability we play action a on node u at time t.
For both variants of the problem, we have the objective
max

XX
u∈S a∈A

13

rua

B
X
t=1

xau,t

(9)

and constraints on how we can play each individual arm:
X
xau,t ≤ su,t
u ∈ S, t ∈ [B]

(10a)

a∈A

xαu,t = su,t

u ∈ B, t ∈ [B]

(10b)

xau,t ≥ 0

u ∈ S, a ∈ A, t ∈ [B]

(10c)

Furthermore, there is a single constraint
XX
xau,t ≤ 1

t ∈ [B]

(11)

u∈S a∈A

enforcing that the total probabilities of plays across all arms cannot exceed 1 at any time step.
The state-updating constraints differ for the two variants of the problem. If we allow preemption,
then they are:
sρi ,1 = 1
su,1 = 0
su,t = su,t−1 −

X

xau,t−1 +

a∈A

X

xav,t−1 · pav,u

i ∈ [n]

(12a)

u ∈ S \ {ρ1 , . . . , ρn }

(12b)

t > 1, u ∈ S

(12c)

(v,a)∈Par(u)

If we disallow preemption, then an arm can only be on a non-root node if we played the same arm
during the previous time step. This is reflected in (13c)-(13d):
sρi ,1 = 1
su,1 = 0
sρi ,t = sρi ,t−1 −

X

xaρi ,t−1

i ∈ [n]

(13a)

u ∈ S \ {ρ1 , . . . , ρn }

(13b)

t > 1, i ∈ [n]

(13c)

t > 1, u ∈ S \ {ρ1 , . . . , ρn }

(13d)

a∈A

su,t =

X

xav,t−1 · pav,u

(v,a)∈Par(u)

Let (PolyLP) denote the linear program defined by objective (9) and constraints (10a)-(10c),
(11), (12a)-(12c). Similarly, let (PolyLP0 ) denote the linear program defined by objective (9) and
constraints (10a)-(10c), (11), (13a)-(13d). We still have to prove the polynomial-sized linear programs are indeed relaxations of the exponential-sized linear programs. For any linear program LP,
let OPTLP denote its optimal objective value.
a }, {y } to (ExpLP), we can construct a solution to
Lemma 2.2. Given a feasible solution {zπ,i,t
π,t
P
P
a , s
(PolyLP) with the same objective value by setting xau,t = π∈S:πi =u zπ,i,t
u,t =
π∈S:πi =u yπ,t for
all i ∈ [n], u ∈ Si , a ∈ A, t ∈ [B]. Thus the feasible region of (PolyLP) is a projection of that of
(ExpLP) onto a subspace and OPTExpLP ≤ OPTPolyLP .
a }, {y } to (ExpLP0 ), we can construct a solution to
Lemma 2.3. Given a feasible solution {zπ,i,t
π,t
P
P
a , s
(PolyLP0 ) with the same objective value by setting xau,t = π∈S 0 :πi =u zπ,i,t
u,t =
π∈S 0 :πi =u yπ,t
0
for all i ∈ [n], u ∈ Si , a ∈ A, t ∈ [B]. Thus the feasible region of (PolyLP ) is a projection of that of
(ExpLP0 ) onto a subspace and OPTExpLP0 ≤ OPTPolyLP0 .

14

Recall that the feasible regions of the exponential-sized linear programs correspond exactly to
the admissible policies. These lemmas say that the performance of any adaptive policy can be upper
bounded by the polynomial-sized relaxations. Our lemmas are generalizations of similar statements
from earlier works [GKMR11, lem. 2.1—for example], but put into the context of an exponentialsized linear program. The proofs are mostly technical and will be deferred to Appendix B.

2.6

Main results.

Now that we have established the preliminaries, we are ready to state our main results in the form
of theorems.
Theorem 2.4. Given a feasible solution {xau,t }, {su,t } to (PolyLP0 ), there exists a solution to
P
P
1
a
(ExpLP0 ) with π:πi =u zπ,i,t
= 21 xau,t ,
π:πi =u yπ,t = 2 su,t for all i ∈ [n], u ∈ Si , a ∈ A, t ∈ [B],
obtaining reward 12 OPTPolyLP0 . We can use sampling to turn this into a ( 12 − ε)-approximation algorithm for MAB superprocess with multi-period actions—no preemption, with runtime polynomial
in the input and 1ε .
We prove this theorem in Section 3, and also show that it is tight, constructing an instance
under the special case of correlated SK where it is impossible to obtain reward greater than ( 21 +
ε)OPT(PolyLP0 ) .
Theorem 2.5. There is a (PolyLP)-relative
where all processing times are 1.

4
27 -approximation

algorithm for MAB superprocess,

Theorem 2.6. There is a (PolyLP)-relative
with multi-period actions.

1
12 -approximation

algorithm for MAB superprocess

We prove these theorems in Section 4.

3

Proof of Theorem 2.4.

In this section we prove Theorem 2.4. To build intuition, we will first present the upper bound,
OPT
0
showing a family of examples with OPT ExpLP 0 approaching 12 .
PolyLP

3.1

Construction for upper bound.

Let N be a large integer. We will describe our n = 2 arms as stochastic jobs. Job 1 takes N + 1
time with probability 1 − N1 , in which case it returns a reward of 1. It takes 1 time with probability
1
N , in which case it returns no reward. Job 2 deterministically takes 1 time and returns a reward
of 1. The budget is B = N + 1 time steps.
Any actual policy can never get more than 1 reward, since it cannot get a positive reward from
both jobs. To describe the solution to (PolyLP0 ) earning more reward, we need to define some
notation for the Markov chains representing the stochastic jobs. A diagram for this reduction was
shown in Subsection 2.4.
15

Let S1 = {S0 , S1 , . . . , SN , φ1 }, with ρ1 = S0 . There is only one action, and we will omit the
action superscripts. The only uncertainty is at S0 , with pS0 ,S1 = 1 − N1 , pS0 ,φ1 = N1 . The remaining
transitions are pS1 ,S2 = . . . = pSN −1 ,SN = pSN ,φ1 = 1, and self loop on the terminal node pφ1 ,φ1 = 1.
The only reward is a reward of 1 on node Sn . Meanwhile, S2 consists only of nodes {ρ2 , φ2 }, with
pρ2 ,φ2 = pφ2 ,φ2 = 1, rρ2 = 1.
It can be checked that xS0 ,1 = 1, xS1 ,2 = . . . = xSN ,N +1 = 1 − N1 , xρ2 ,2 = . . . = xρ2 ,N +1 = N1 is
a feasible solution for (PolyLP0 ). Its objective value is 2 − N1 , hence as we take N → ∞, we get
OPTExpLP0
OPTPolyLP0

= 12 .
Note that we can put all of S1 \ {ρ1 , φ1 } in B if we want; it doesn’t change the example whether
job 1 can be canceled once started. It also doesn’t matter whether we allow preemption—both
OPTExpLP0
OPTExpLP
1
OPTPolyLP and OPTPolyLP0 are 2 + ε for this example.
Let’s analyze what goes wrong when we attempt to replicate the optimal solution to the LP
relaxation in an actual policy. We start job 1 at time 1 with probability xS0 ,1 = 1. If it does not
terminate after 1 time step, which occurs with probability 1 − N1 , then we play job 1 through to the
end, matching xS1 ,2 = . . . = xSN ,N +1 = 1 − N1 . If it does, then we start job 2 at time 2. This occurs
with unconditional probability xρ2 ,2 = N1 , as planned. However, in this case, we cannot start job 2
again at time 3 (since it has already been processed at time 2), even though xρ2 ,3 = N1 is telling us
to do so. The LP relaxation fails to consider that event “job 1 takes time 1” is directly correlated
with event “job 2 is started at time 2”, so the positive values specified by xρ2 ,3 , . . . , xρ2 ,N +1 are
illegal plays.
Motivated by this example, we observe that if we only try to play u at time t with probability
xu ,t
0
2 , then we can obtain a solution to (ExpLP ) (and hence a feasible policy) that is a scaled copy
of the solution to (PolyLP0 ).

3.2

Technical specification of solution to (ExpLP’).

Fix a solution {xau,t , su,t } to (PolyLP0 ). Our objective in this subsection is to construct a solution
a , y } to (ExpLP0 ) such that
{zπ,i,t
π,t
X

a
zπ,i,t
=

π∈S 0 :πi =u

xau,t
2

i ∈ [n], u ∈ Si , a ∈ A

(14)

obtaining half the objective value of (PolyLP0 ). We will prove feasibility in Subsection 3.3.
P
P
a . We will complete the specifiFor convenience, define xu,t = a∈A xau,t and zπ,i,t = a∈A zπ,i,t
a , y } over B iterations t = 1, . . . , B. On iteration t:
cation of {zπ,i,t
π,t
1. Compute yπ,t for all π ∈ S 0 .
P
a
2. Define ỹπ,t = yπ,t if π ∈
/ A, and ỹπ,t = yπ,t − a∈A zπ,i,t
if π ∈ Ai for some i ∈ [n] (if π ∈ Ai ,
a
then {zπ,i,t : a ∈ A} has already been set in a previous iteration).
3. For all i ∈ [n], define fi,t =

P

π∈S 0 :πi =ρi

ỹπ,t .

16

a
4. For all i ∈ [n], π ∈ S 0 such that πi = ρi , and a ∈ A, set zπ,i,t
= ỹπ,t ·

1
2

·

xa
ρi ,t
fi,t .

5. For all i ∈ [n], and π ∈ S 0 such that πi = ρi and πj ∈ {ρj , φj } for j 6= i, define gπ,i,t =
P
π 0 ∈P(π) zπ 0 ,i,t .
a
6. For all i ∈ [n], u ∈ Si \ {ρi }, π ∈ S 0 such that πi = u, and a ∈ A, set zπ,i,t+depth(u)
=

gπρi ,i,t ·

xa
u,t+depth(u)
.
xρi ,t

The motivation for Step 2 is that we want ỹπ,t to represent the probability we are at joint node π
and looking to start a new arm at time t, abandoning the arm in progress if there is any. In Step 3,
fi,t is the total probability we would be ready to start playing arm i at time t. The normalization
in Step 4 ensures that each arm is started with the correct probability at time t. In Step 5, gπ,i,t
is the probability arm i is started at time t, and other arms are on nodes {πj : j 6= i} while arm i
executes (another arm j could have made a transition to φj during the first time step t). Step 6
specifies how to continue playing arm i in subsequent time steps if it is started at time t. Note that
gπρi ,i,t is guaranteed to be defined in this case, since πi ∈
/ {ρi , φi } and π ∈ S 0 implies πj ∈ {ρj , φj }
for all j 6= i.
This completes the specification of the solution to (ExpLP0 ). Every yπ,t is set in Step 1, and
a
every zπ,i,t
is set in either Step 4 or Step 6.
Using the definition of fi,t , Step 4 guarantees that for i ∈ [n], a ∈ A,
X

X

a
zπ,i,t
=

π∈S 0 :πi =ρi

=

ỹπ,t ·

π∈S 0 :πi =ρi
xaρi ,t

1 xaρi ,t
·
2 fi,t

2

Meanwhile, Step 6 guarantees that for i ∈ [n], u ∈ Si \ {ρi }, a ∈ A,
X

a
zπ,i,t+depth(u)

X

=

π∈S 0 :πi =u

=
=

gπ,i,t ·

xau,t+depth(u)

π∈S 0 :πi =u
a
xρi ,t xu,t+depth(u)

2

xρi ,t

·

xρi ,t
a
xu,t+depth(u)
2

We explain the second equality. Since u 6= ρi implies arm i is the active arm in all of {π ∈
S 0 : πi = u}, this set is equal to {ρ1 , φ1 } × · · · × u × · · · × {ρn , φn }. Summing gπ,i,t over all the
possibilities for {πj : j 6= i} yields the total probability arm i is started at time t. This is equal to
P
P
xρi ,t
a
π∈S 0 :πi =ρi
a∈A zπ,i,t , which by the first calculation is equal to 2 .
The proof of (14) is now complete.

3.3

Proof of feasibility.

We will inductively prove feasibility over iterations t = 1, . . . , B. Suppose all of the variables
a
0
{zπ,i,t
0 , yπ,t0 } with t < t have already been set in a way that satisfies constraints (6a)-(6c), (7a)17

a
0
(7e). Some of the variables zπ,i,t
0 with t ≥ t may have also been set in Step 6 of earlier iterations;
if so, suppose they have already been proven to satisfy (6c).
On iteration t, we first compute in Step 1 yπ,t for all π ∈ S 0 ; these are guaranteed to satisfy
(7a)-(7e) by definition. To complete the induction, we need to show that (6a)-(6c) hold after setting
a
0
the z-variables in Step 4, and furthermore, (6c) holds for any zπ,i,t
0 (with t > t) we set in Step 6.
We first prove the following lemma:

Lemma 3.1. Suppose π ∈ Ai for some i ∈ [n]. Let u = πi (which is neither ρi nor φi ). Then
P
a
α
a∈A zπ,i,t ≤ yπ,t , and furthermore if u ∈ B, then zπ,i,t = yπ,t .
P

Proof. Proof. First suppose depth(u) = 1. (7d) says yπ,t =

paρi ,u . Every π 0 in the sum has πi0 = ρi , so zπa0 ,i,t−1 was set in Step 4 of iteration
Substituting into (7d), we get


X

yπ,t =

a:(ρi ,a)∈Par(u)

=



X
π 0 ∈P(π ρi )


ỹπ0 ,t−1 ·

X

ỹπ0 ,t−1 ·

π 0 ∈P(π ρi )

1
2fi,t−1

a
π 0 ∈P(π ρi ) zπ 0 ,i,t−1 ) ·
xa ,t−1
i
.
t−1 to ỹπ0 ,t−1 · 21 · fρi,t−1

P

a:(ρi ,a)∈Par(u) (

1 xaρi ,t−1  a
·
· pρi ,u
2 fi,t−1
X

·

xaρi ,t−1 · paρi ,u

a:(ρi ,a)∈Par(u)

a
Meanwhile, for all a ∈ A, zπ,i,t
was set in Step 6 of iteration t − 1 to gπρi ,i,t−1 ·

a
zπ,i,t

= g

π ρi ,i,t−1

X

=

·

X

xρi ,t−1

zπ0 ,i,t−1 ·

=

X

xau,t
xρi ,t−1

ỹπ0 ,t−1 ·

π 0 ∈P(π ρi )

b∈A




ỹπ0 ,t−1 ·

X

Hence

xau,t

π 0 ∈P(π ρi )

=

xa
u,t
xρi ,t−1 .

π 0 ∈P(π ρi )

1 xbρi ,t−1  xau,t
·
·
2 fi,t−1
xρi ,t−1
1

2fi,t−1

· xau,t

where the second equality is by the definition of gπρi ,i,t−1 , and the third equality uses the fact
P
a
that zπb 0 ,i,t−1 was set in Step 4 of iteration t − 1. To prove a∈A zπ,i,t
≤ yπ,t , it suffices to show
P
P
a
a
a
a∈A xu,t ≤
a:(ρi ,a)∈Par(u) xρi ,t−1 · pρi ,u . This follows immediately from combining constraints
α
(10a) and (13d) of (PolyLP0 ). Furthermore, if u ∈ B, then we can use (10b) to get zπ,i,t
= yπ,t .
P
a
a
Now suppose depth(u) > 1. (7e) says yπ,t = (v,a)∈Par(u) zπv ,i,t−1 · pv,u . Since v 6= ρi , zπav ,i,t−1
was set in Step 6 of iteration t0 := t − depth(u) to gπρi ,i,t0 ·

xa
v,t−1
xρ ,t0 .

Substituting into (7e), we get

i

yπ,t =

X

gπρi ,i,t0 ·

(v,a)∈Par(u)

=

gπρi ,i,t0
xρi ,t0

X
(v,a)∈Par(u)

18

xav,t−1 a
· pv,u
xρi ,t0

xav,t−1 · pav,u

P
xa
a
a
Meanwhile, for all a ∈ A, zπ,i,t
was set in Step 6 of iteration t0 to gπρi ,i,t0 · x u,t0 . To prove a∈A zπ,i,t
≤
ρ
,t
i
P
P
a
a
a
yπ,t , it suffices to show a∈A xu,t ≤ (v,a)∈Par(u) xv,t−1 · pv,u . This is again obtained from (10a)
α
and (13d), and if u ∈ B, then we can use (10b) to get zπ,i,t
= yπ,t .
By the lemma, ỹπ,t ≥ 0 if π ∈ Ai for some i ∈ [n]. On the other hand, ỹπ,t ≥ 0 is immediate
from definition if π ∈
/ A. Therefore, ỹπ,t ≥ 0 for all π ∈ S 0 , and (6c) is satisfied by all the z-variables
a
set in Step 4 or Step 6. Furthermore, the lemma guarantees (6b) for the zπ,i,t
with πi ∈ B set in
previous iterations.
It remains to prove (6a). If π ∈ Ai , then the LHS of (6a) is
X

X

zπ,j,t = zπ,i,t +

ỹπ,t ·

j∈I(π)\{i}

j∈I(π)

1 xρj ,t
·
2 fj,t
X

= zπ,i,t + (yπ,t − zπ,i,t ) ·

j∈I(π)\{i}

1 xρj ,t
·
2 fj,t

For the first equality, note that zπ,j,t for j 6= i is set in Step 4 of the current iteration, but zπ,i,t has
already been set in an earlier iteration. The second equality is immediate from the definition of
P
xρj ,t
≤ 1, then we would
ỹπ,t . Note that yπ,t − zπ,i,t ≥ 0, by Lemma 3.1. If we knew j∈I(π)\{i} 12 · fj,t
P
have j∈I(π) zπ,j,t ≤ zπ,i,t + (yπ,t − zπ,i,t )(1) = yπ,t , which is (6a).
P
xρj ,t
On the other hand, if π ∈
/ A, then the LHS of (6a) is yπ,t · j∈I(π) 12 · fj,t
, where in this case
P
xρj ,t
≤ 1,
all of the zπ,j,t are set in Step 4 of the current iteration. Similarly, if we knew j∈I(π) 12 · fj,t
then we would have (6a).
P
xρj ,t
≤ 1 (note that fj,t is always
To complete the proof of feasibility, it suffices to show nj=1 12 · fj,t
non-negative, by its definition and Lemma 3.1). This is implied by the following lemma, which
proves a simpler statement:
P
xρ ,t
Lemma 3.2. fi,t ≥ nj=1 2j for all i ∈ [n].
Proof. Proof. Fix some i ∈ [n]. By the definitions in Step 2 and Step 3,
fi,t =

X

yπ,t −

0

X

X

zπ,j,t

j6=i π∈Aj :πi =ρi

π∈S :πi =ρi

P
Let’s start by bounding π∈S 0 :πi =ρi yπ,t , the total probability arm i is still on ρi at the start of
P
P
time t. This is equal to 1 − t0 <t π∈S 0 :πi =ρi zπ,i,t0 , where we subtract from 1 the total probability
P
x
0
arm i was initiated before time t. By (14), π∈S 0 :πi =ρi zπ,i,t0 = ρ2i ,t for all t0 < t. Furthermore,
X

xρi ,t0 ≤ 1

(15)

t0 <t

from iteratively applying (13c) to (13a), and combining with (10a)10 . Therefore,
1
2.
10

P

π∈S 0 :πi =ρi

yπ,t ≥

Intuitively, we’re arguing that solution to the LP relaxation still satisfies the total probability arm i being played
from its root node not exceeding unity.

19

Now we bound the remaining term in the equation for fi,t :
X
X
X X
X
zπ,j,t =

zπ,j,t

j6=i v∈Sj \{ρj } π:πi =ρi ,πj =v

j6=i π∈Aj :πi =ρi

≤

X

X

X

zπ,j,t

j6=i v∈Sj \{ρj } π:πj =v

=

1X
2

X

xv,t

j6=i v∈Sj \{ρj }
n

≤

1X
2

X

xv,t

j=1 v∈Sj \{ρj }
n

≤

X

1
1−
xρj ,t
2
j=1

The first inequality uses the non-negativity of zπ,j,t in the inductively proven (6c), the second
equality uses (14), the second inequality uses the non-negativity of xv,t in (10c), and the third
inequality uses (11).
P
xρ ,t
Combining the two terms, we get fi,t ≥ nj=1 2j , as desired.

3.4

Approximation algorithm via sampling.

a , y } of (ExpLP0 ) into a polynomial-time policy.
Let’s turn this exponential-sized solution {zπ,i,t
π,t
a
Now we will assume the {xu,t , su,t } we are trying to imitate is an optimal solution of (PolyLP0 ).
Consider the following algorithm, which takes in as parameters a terminal time step t ∈ [B], and
probabilities λi,t0 for each i ∈ [n], t0 ≤ t (which for now should be considered to be fi,t0 to aid in the
comprehension of the algorithm):

Policy(t, {λi,t0 : i ∈ [n], t0 ≤ t})
• Initialize t0 = 1, current = 0.
• While t0 ≤ t:
1. If current = 0, then
x

0

(a) For each arm i that is on ρi , set current = i with probability 12 · λρi ,t0 ; if the sum of
i,t
these probabilities exceeds 1 (ie. this step is inadmissible), then terminate with no
reward.
(b) If current was set in this way, leave t0 unchanged and enter the next if block. Otherwise, leave current at 0 but increment t0 by 1.
2. If current 6= 0, then
(a) Let u denote the node arm current is on. For each a ∈ A, play action a on arm
current with probability

xa
u,t0

xu,t0 .

20

(b) Suppose we transition onto node v as a result of this play. With probability
leave current unchanged. Otherwise, set current = 0.

xv,t0 +1
sv,t0 +1 ,

(c) Increment t0 by 1.

Define the following events and probabilities, which depend on the input passed into Policy:
• For all i ∈ [n], t0 ≤ (t + 1), let Ai,t0 be the event that at the beginning of time t0 , current = 0
and arm i is on ρi . Let Free(i, t0 ) = Pr[Ai,t0 ].
• For all i ∈ [n], t0 ≤ t, let Started(i, t0 ) be the probability that we play arm i from ρi at time t0 .
• For all u ∈ S, a ∈ A, t0 ≤ t, let Played(u, a, t0 ) be the probability that we play action a on
node u at time t0 .
a , y } if we
It is easy to see that Policy is an algorithmic specification of feasible solution {zπ,i,t
π,t
run it on input (B, {fi,t : i ∈ [n], t ∈ [B]}). Indeed, we would iteratively have for t = 1, . . . , B:

• Free(i, t) = fi,t for all i ∈ [n]
• Started(i, t) = Free(i, t) ·

1
2

·

xρi ,t
fi,t

=

xρi ,t
2

for all i ∈ [n]

• Played(u, a, t) = Started(i, t − depth(u)) ·

xa
u,t
xρi ,t−depth(u)

=

xa
u,t
2

for all u ∈ S, a ∈ A

The final statement can be seen inductively:
X
xau,t
Played(u, a, t) =
Played(v, b, t − 1) · pbv,u ·
su,t
(v,b)∈Par(u)

=

X

Started(i, t − 1 − depth(v)) ·

(v,b)∈Par(u)

= Started(i, t − depth(u)) ·

xau,t
xρi ,t−depth(u)

xbv,t−1
xρi ,t−1−depth(v)



·

pbv,u

xau,t
·
su,t
(16)

where the first equality is by Steps 2a-b, the second equality is by the induction hypothesis, and
the final equality is by (13d).
Therefore, we would have a 12 -approximation if we knew {fi,t : i ∈ [n], t ∈ [B]}, but unfortunately computing fi,t requires summing exponentially many terms. We can try to approximate it
by sampling, but we can’t even generate a sample from the binary distribution with probability fi,t
since that requires knowing the exact values of fi,t0 for t0 < t. So we give up trying to approximate
fi,t , and instead iteratively approximate the values of Free(i, t) when Policy is ran on previously
approximated Free(i, t) values.
−1 )
Fix some small ε, δ > 0 that will be determined later. Let µε,δ = 3 ln(2δ
. Change Policy
ε2
2
so that the probabilities in Step 1a are multiplied by (1 − ε) (and change the definitions of
Ai,t0 , Free, Started, Played accordingly).
Sampling Algorithm
21

• Initialize Freeemp (i, 1) = 1 for all i ∈ [n].
• For t = 2, . . . , B:
1. Run Policy(t − 1, {Freeemp (i, t0 ) : i ∈ [n], t0 < t}) a total of M = 8|S|B
· µε,δ times. For
ε
all i ∈ [n], let Ci,t count the number of times event Ai,t occurred.
2. For each i ∈ [n], if Ci,t > µε,δ , set Freeemp (i, t) =
Pn xρj ,t
j=1 2 .

Ci,t
M ;

otherwise set Freeemp (i, t) =

Consider iteration t of Sampling Algorithm. {Freeemp (i, t0 ) : i ∈ [n], t0 < t} have already been
finalized, and we are sampling event Ai,t when (the ε-modified) Policy is ran on those finalized
approximations to record values for {Freeemp (i, t) : i ∈ [n]}. For all i ∈ [n], if Ci,t > µε,δ , then the

C
probability of Mi,t lying in (1 − ε) · Free(i, t), (1 + ε) · Free(i, t) is at least11 1 − δ. As far as when
ε
we have Ci,t > µε,δ , note that if Free(i, t) > 4|S|B
, then E[Ci,t ] > 2µε,δ , so the Chernoff bound says
1

Pr[Ci,t ≤ µε,δ ] = O(δ ε2 ) = O(δ). We have discussed two O(δ) probability events in this paragraph
of sampling/Chernoff yielding an unlikely and undesired result; call these events failures.
By the union bound, the probability of having any failure over iterations t = 2, . . . , B is at most
2(B − 1)n(δ + O(δ)) = O(Bnδ). Assuming no failures, we will inductively prove

xρ ,t
ε
(1 − ε)2 xρi ,t
·
≤ Started(i, t) ≤ max (1 − ε) · i ,
1+ε
2
2 4|S|B

(17)

x

for all i ∈ [n]. This is clear when t = 1 since Started(i, 1) = ρ2i ,1 exactly for all i ∈ [n].
Now suppose t ≥ 2. We will first prove a lemma on the true probabilities Free(i, t), which is the
“approximate” version of Lemma 3.2:
Lemma 3.3. Suppose Policy is ran on input (t − 1, {Freeemp (i, t0 ) : i ∈ [n], t0 < t}) and there were
no failures while obtaining the sample average approximations Freeemp (i, t0 ). Then for all i ∈ [n],
P
Free(i, t) ≥ 12 nj=1 xρj ,t .
Proof. Proof. We know that event Ai,t will occur if at time t, arm i has not yet been started, and no
P
P
P
P
other arm is active. By the union bound, 1−Free(i, t) ≤ t0 <t Started(i, t0 )+ nj=1 u∈Sj \{ρj } a∈A Played(u, a, t).
Assuming (17) holds, we can bound
X

Started(i, t0 ) ≤

t0 <t

X

(1 − ε) ·

t0 <t

xρi ,t0
ε 
+
2
4|S|B

≤

1−εX
ε
xρi ,t0 +
2 0
4|S|

≤

1−ε ε
+
2
4

t <t

11

This is because Freeemp (i, t) is an average over M ≥
probability; see Motwani and Raghavan [MR10].

8
ε

22

· µε,δ runs, which is enough samples to guarantee this

where the final inequality uses (15). Similarly, assuming (17) holds, we can bound
n
X

X

X

Played(u, a, t) =

j=1 u∈Sj \{ρj } a∈A

n
X

X

Started(i, t − depth(u)) ·

j=1 u∈Sj \{ρj }

≤

n
X

X

(1 − ε) ·

j=1 u∈Sj \{ρj }

≤

X

xu,t +

j=1 u∈Sj \{ρj }

xρi ,t−depth(u)

xρi ,t−depth(u)
xu,t
ε 
+
·
2
4|S|B xρi ,t−depth(u)

n

1−εX
2

xu,t

ε
4B

n

≤

 ε
X
1
1−
xρj ,t +
2
4
j=1

where the equality uses (16), the second inequality uses the fact that xu,t ≤ xρi ,t−depth(u) , and the
final inequality uses (11). Combining these bounds completes the proof of the lemma.
By the description in Step 1a of Policy, for all i ∈ [n], we have
Started(i, t) = Free(i, t) ·

xρi ,t
1
·
· (1 − ε)2
2 Freeemp (i, t)

(18)

C

If Ci,t > µε,δ , then Freeemp (i, t) will be set to Mi,t , and furthermore no failures implies (1 − ε) ·
2
xρi ,t
C
Free(i, t) ≤ Mi,t ≤ (1 + ε) · Free(i, t). Substituting into (18), we get (1−ε)
1+ε · 2 ≤ Started(i, t) ≤
x
(1 − ε) · ρ2i ,t which implies (17). On the other hand, if Ci,t ≤ µε,δ , then Freeemp (i, t) will be
Pn xρj ,t
ε
set to
j=1 2 , and assuming no failures it must have been the case that Free(i, t) ≤ 4|S|B .
x
ε
ε
Substituting into (18), we get Started(i, t) ≤ 4|S|B
· 12 · Pn ρix,tρ ,t · (1 − ε)2 ≤ 4|S|B
which implies
j=1
j
the upper bound in (17). For the lower bound, Lemma 3.3 says Free(i, t) ≥ Freeemp (i, t), so
2
xρi ,t
x
Started(i, t) ≥ (1 − ε)2 · ρ2i ,t ≥ (1−ε)
1+ε · 2 .
This completes the induction for (17). The final thing to check is that with these new parameters
{Freeemp (i, t) : i ∈ [n]}, the sum of the probabilities in Step 1a of Policy does not exceed 1.
P
xρ ,t
Freeemp (i, t) will either get set to nj=1 2j , or be at least (1 − ε) · Free(i, t), which is at least
P
Pn xρj ,t
xρ ,t
(1 − ε) · j=1 2 by Lemma 3.3. In either case, Freeemp (i, t) ≥ (1 − ε) · nj=1 2j for all i ∈ [n],
1
so the desired sum in Step 1a is at most 1−ε
· (1 − ε)2 ≤ 1.
We have an algorithm that fails with probability O(Bnδ), and when it doesn’t fail, Started(i, t) ≥
(1−ε)2 xρi ,t
1+ε · 2 for all i ∈ [n], t ∈ [B], which in conjunction with (16) shows that we obtain expected
2

1
0
0
0
reward at least (1−ε)
1+ε · 2 ·OPTPolyLP . Recall from Lemma 2.3 that OPTPolyLP ≥ OPTExpLP . Treating
ε
1
a failed run as a run with 0 reward, we can set δ = Θ( Bn ) to get a ( 2 − ε)-approximation. Finally,
note that the runtime of this approximation algorithm is polynomial in the input, 1ε , and ln( 1δ ),
completing the proof of Theorem 2.4.

4

Proof of Theorem 2.5.

In this section we prove Theorem 2.5, and also show how to modify the proof to prove Theorem 2.6.
23

4.1

Description of algorithm.

The algorithm maintains a priority index12 for each arm, telling us when it will try to play that
arm again. Formally, if an arm is on node u, we say the arm is in status (u, a, t) to represent that
the algorithm will next try to play action a ∈ A on the arm at time t ∈ [B]. We allow t = ∞ to
indicate that the algorithm will never try to play the arm again; in this case we omit the action
parameter.
Fix an optimal solution {xau,t , su,t } to (PolyLP). We initialize each arm i to status (ρi , a, t) with
xa
ρi ,t
C ,

for all a ∈ A and t ∈ [B], where C > 0 is some constant which we optimize later.
P
P
xa
ρi ,t
With probability 1 − a∈A B
t=1 C , the arm is initialized to status (ρi , ∞) and never touched;
note that this probability is at least 1 − C1 .
The statuses also evolve according to the solution of the LP relaxation. If we play an arm and
it transitions to node u, we need to decide what status (u, a, t) to put that arm in. The evolution of
statuses is independent of other arms. For all i ∈ [n], u ∈ Si \ {ρi }, a ∈ A, t ∈ [B], (v, b) ∈ Par(u),
and t0 < t, define qv,b,t0 ,u,a,t to be the probability we put arm i into status (u, a, t), conditioned on
arriving at node u after playing action b on node v at time t0 . The following lemma tells us that
such q’s always exist, and that we can find them in polynomial time:
probability

Lemma 4.1. Suppose we are given the x’s of a feasible solution to (PolyLP). Then we can find
{qv,b,t0 ,u,a,t : u ∈ S \ {ρ1 , . . . , ρn }, a ∈ A, t ∈ [B], (v, b) ∈ Par(u), t0 < t} in polynomial time such that
XX

qv,b,t0 ,u,a,t ≤ 1

u ∈ S \ {ρ1 , . . . , ρn }, (v, b) ∈ Par(u), t0 ∈ [B − 1]

a∈A t>t0

(19a)
X

X

(v,b)∈Par(u)

t0 <t

xbv,t0 · pbv,u · qv,b,t0 ,u,a,t = xau,t

u ∈ S \ {ρ1 , . . . , ρn }, a ∈ A, t ∈ {2, . . . , B}

(19b)

Furthermore, if u ∈ B, then we can strengthen (19a) to qv,b,t0 ,u,α,t0 +1 = 1.
(19a) ensures that the probabilities telling us what to do, when we arrive at node u after
playing action b on node v at time t0 , are well-defined; the case where u is a bridge node will be
needed to prove Theorem 2.6. For all i ∈ [n], u ∈ Si \ {ρi }, (v, b) ∈ Par(u), and t0 ∈ [B − 1],
P
P
define qv,b,t0 ,u,∞ = 1 − a∈A t>t0 qv,b,t0 ,u,a,t , the probability we abandon arm i after making the
transition to u. (19b) will be used in the analysis to provide a guarantee on each status (u, a, t)
ever being reached.
Lemma 4.1 is the replacement for convex decomposition from [GKMR11], and its proof is deferred to Appendix C. Having defined the q’s, the overall algorithm can now be described in two
steps:
1. While there exists an arm with priority not ∞, play an arm with the lowest priority (breaking
ties arbitrarily) until it arrives at a status (u, a, t) such that t ≥ 2 · depth(u) (t = ∞ would
suffice).
12

For mathematical convenience, lower priority indices will mean higher priorities.

24

2. Repeat until all arms have priority ∞.
Of course, we are constrained by a budget of B time steps, but it will simplify the analysis to
assume our algorithm finishes all the arms and collects reward only for plays up to time B. Under
this assumption, the statuses an arm goes through is independent of the outcomes on all other
arms; the inter-dependence only affects the order in which arms are played (and thus which nodes
obtain reward).
Also, note that this is only a valid algorithm because Theorem 2.5 assumes all processing times
are 1, so there are no bridge nodes. If there were bridge nodes, then we may not be allowed to
switch to an arm with lowest priority index, being forced to play the arm on a bridge node.

4.2

Analysis of algorithm.

For all i ∈ [n], u ∈ Si , a ∈ A, t ∈ [B], let time(u, a, t) be the random variable for the time step at
which our algorithm plays arm i from status (u, a, t), with time(u, a, t) = ∞ if arm i never gets in
xa
status (u, a, t). Then Pr[time(ρi , a, t) < ∞] = ρCi ,t for all i ∈ [n], a ∈ A, t ∈ [B]. If u is a non-root
node, then we can induct on depth(u) to prove for all a ∈ A, t ∈ [B] that
X
X
Pr[time(u, a, t) < ∞] =
Pr[time(v, b, t0 ) < ∞] · pbv,u · qv,b,t0 ,u,a,t
(v,b)∈Par(u) t0 <t

X

=
=

X xbv,t0

(v,b)∈Par(u) t0 <t
xau,t

C

· pbv,u · qv,b,t0 ,u,a,t
(20)

C

where the final equality follows from Lemma 4.1.
For an event A, let 1A be the indicator random variable for A. The expected reward obtained
by our algorithm is
B
hXX X
i
a
E
ru
1{time(u,a,t)≤B}
t=1

u∈S a∈A

=

=

XX

rua

B
X

u∈S a∈A

t=1

XX

B
X

u∈S a∈A

rua

E[1{time(u,a,t)≤B} | time(u, a, t) < ∞] · Pr[time(u, a, t) < ∞]
Pr[time(u, a, t) ≤ B | time(u, a, t) < ∞] ·

t=1

xau,t
C

For the remainder of this subsection, we will set C = 3 and prove for an arbitrary i ∈ [n],
u ∈ Si , a ∈ A, t ∈ [B] that Pr[time(u, a, t) ≤ B | time(u, a, t) < ∞] ≥ 49 . It suffices to prove that
Pr[time(u, a, t) ≤ t | time(u, a, t) < ∞] ≥ 49 , since t ≤ B.
Case 1. Suppose t ≥ 2 · depth(u). We prove that conditioned on the event {time(u, a, t) < ∞},
{time(u, a, t) > t} occurs with probability at most 59 .
Note that every node v can have at most one b, t0 such that time(v, b, t0 ) < ∞; let time(v) denote
this quantity (and be ∞ if time(v, b, t0 ) = ∞ for all b ∈ A, t0 ∈ [B]). The nodes v that are played
25

before u are those with time(v) < time(u, a, t). Since our algorithm plays a node at every time step,
time(u, a, t) > t if and only if there are t or more nodes v 6= u such that time(v) < time(u, a, t).
But this is equivalent to there being exactly t nodes v 6= u such that time(v) < time(u, a, t) and
time(v) ≤ t. The depth(u) ancestors of u are guaranteed to satisfy this.
P
Hence the event {time(u, a, t) > t} is equivalent to {depth(u) + v∈S\Si 1{time(v)<time(u,a,t)} ·
P
1{time(v)≤t} = t}. But t ≥ 2 · depth(u), so this implies { v∈S\Si 1{time(v)<time(u,a,t)} · 1{time(v)≤t} ≥
P
t
t
t
2 } =⇒ { v∈S\Si 1{time(v)<time(u,a,t)} ≥ 2 }. Now, whether the sum is at least 2 is unchanged if we
exclude all v such that depth(v) ≥ 2t . Indeed, if any such v satisfies time(v) < time(u, a, t), then
all of its ancestors also do, and its first d 2t e ancestors ensure that the sum, without any nodes of
depth at least 2t , is at least 2t . Thus, the last event is equivalent to
X



1{time(v)<time(u,a,t)} ≥

v∈S\Si :depth(v)< 2t

t
2

(21)

Suppose time(v) = time(v, b, t0 ) for some b ∈ A and t0 ∈ [B]. We would like to argue that in
order for both time(v) < time(u, a, t) and depth(v) < 2t to hold, it must be the case that t0 ≤ t.
Suppose to the contrary that t0 > t. If t0 ≥ 2 · depth(v), then the algorithm can only play (v, b, t0 )
once t0 becomes the lowest priority index, which must happen after (u, a, t) becomes the lowest
priority index, hence time(v, b, t0 ) < time(u, a, t) is impossible. Otherwise, if t0 < 2 · depth(v), then
0
depth(v) > t2 > 2t , violating depth(v) < 2t . Thus indeed t0 ≤ t and
(21)

⇐⇒

t
XX

X



1{time(v,b,t0 )<time(u,a,t)} ≥

v∈S\Si :depth(v)< 2t b∈A t0 =1

=⇒

t
 X XX

1{time(v,b,t0 )<∞} ≥

v∈S\Si b∈A t0 =1

t
2

t
2

We establish that the probability of interest Pr[time(u, a, t) > t | time(u, a, t) < ∞] is at most
Pr

t
h X XX

1{time(v,b,t0 )<∞} ≥

v∈S\Si b∈A t0 =1

= Pr

t
hX X XX

i
t
| time(u, a, t) < ∞
2

1{time(v,b,t0 )<∞} ≥

j6=i v∈Sj b∈A t0 =1

ti
2

where we remove the conditioning due to independence between arms. Now, let
Yj = min

t
 X XX
v∈Sj b∈A t0 =1

26

1{time(v,b,t0 )<∞} ,

t
2

for all j 6= i. The previous probability is equal to Pr[

P

j6=i Yj

≥ 2t ]. Note that

t
hX i
X X XX
E
Yj ≤
Pr[time(v, b, t0 ) < ∞]
j6=i v∈Sj b∈A t0 =1

j6=i

≤

t XX b
X
xv,t0
t0 =1 v∈S b∈A

≤

3

t
3

where the second inequality uses (20), and the final inequality uses (11). We can do better than
P
the Markov bound on Pr[ j6=i Yj ≥ 2t ] because the random variables {Yj }j6=i are independent.
Furthermore, each Yj is non-zero with probability at most 31 (arm j is never touched with probability
at least 32 ), so since is at most 2t when it is non-zero, E[Yj ] ≤ 6t for all j 6= i. We now invoke the
following lemma:
Lemma 4.2. Let t > 0 be arbitrary and Y1 , . . . , Ym be independent non-negative random variables
P
t
with individual expectations at most 6t and sum of expectations at most 3t . Then Pr[ m
j=1 Yj ≥ 2 ]
is maximized when only two random variables are non-zero, each taking value 2t with probability 13
P
t
1 2
5
(and value 0 otherwise). Therefore, Pr[ m
j=1 Yj ≥ 2 ] ≤ 1 − (1 − 3 ) = 9 .
This lemma would complete the proof that Pr[time(u, a, t) > t | time(u, a, t) < ∞] ≤ 59 under
Case 1, where t ≥ 2 · depth(u). We defer the proof of Lemma 4.2 to Appendix C. It uses the
conjecture of Samuels from [Sam66] for n = 3; the conjecture has been proven for n ≤ 4 in [Sam68].
The proof also uses a technical lemma of Bansal et al. from [BGL+ 12].
Case 2. Suppose t < 2 · depth(u). Then depth(u) must be at least 1, so conditioned on
time(u, a, t) < ∞, there must be some (v, b) ∈ Par(u) and t0 < t such that time(v, b, t0 ) < ∞.
Furthermore, the algorithm will play status (u, a, t) at time step time(v, b, t0 ) + 1, so time(u, a, t) ≤ t
will hold so long as time(v, b, t0 ) ≤ t0 , since t0 < t. Thus Pr[time(u, a, t) ≤ t | time(u, a, t) < ∞] ≥
Pr[time(v, b, t0 ) ≤ t | time(v, b, t0 ) < ∞]. We can iterate this argument until the the problem reduces
to Case 1. This completes the proof that Pr[time(u, a, t) ≤ t | time(u, a, t) < ∞] ≥ 94 under Case 2.
P
P
P
Therefore, the expected reward obtained by our algorithm is at least u∈S a∈A rua B
t=1 (1 −
a
4
5 xu,t
9 ) 3 , which is the same as 27 OPTPolyLP , completing the proof of Theorem 2.5.

4.3

Proof of Theorem 2.6.

In this subsection we show how to modify the algorithm and analysis when there are multi-period
actions, to prove Theorem 2.6. As mentioned in Subsection 4.1, we must modify Step 1 of the
algorithm when there are bridge nodes. If we arrive at a status (u, a, t) such that t ≥ 2 · depth(u)
but u ∈ B (and a = α), we are forced to immediately play the same arm again, instead of switching
to another arm with a lower priority index.
The overall framework of the analysis still holds, except now the bound is optimized when
we set C = 6. Our goal is to prove for an arbitrary i ∈ [n], u ∈ Si , a ∈ A, t ∈ [B] that
27

Pr[time(u, a, t) > t | time(u, a, t) < ∞] ≤ 12 . We still have that event {time(u, a, t) > t} implies
(21). Suppose for an arbitrary v ∈ S \ Si that depth(v) < 2t and time(v) < time(u, a, t), where
time(v) = time(v, b, t0 ). We can no longer argue that t0 ≤ t, but we would like to argue that t0 ≤ 3t
2.
3t
0
Suppose to the contrary that t > 2 .
Then t0 > 3 · depth(v), so t0 ≥ 2 · depth(v) ie. we would check priorities before playing (v, b, t0 ).
However, if v ∈ B, then it could be the case that time(v, b, t0 ) < time(u, a, t) even though t0 > t.
If so, consider w, the youngest (largest depth) ancestor of v that isn’t a bridge node. Suppose
time(w) = time(w, b0 , t00 ); it must be the case that t00 ≤ t. By the final statement of Lemma 4.1, the
depth(v)−depth(w) immediate descendents of w, which are bridge nodes, must have priority indices
t00 + 1, . . . , t00 + depth(v) − depth(w), respectively. The youngest of these descendents is v, hence
t0 = t00 + depth(v) − depth(w). But t00 ≤ t and depth(v) < 2t , so t0 < 3t
2 , causing a contradiction.
P
3t
0
Therefore t ≤ 2 . The bound on E[ j6=i Yj ] changes to
3t
2
hX i
X X XX
Pr[time(v, b, t0 ) < ∞]
E
Yj ≤

j6=i v∈Sj b∈A t0 =1

j6=i

3t

≤

2 XX
X
xbv,t0

t0 =1 v∈S b∈A

≤

6

t
4

P
Thus Pr[time(u, a, t) > t | time(u, a, t) < ∞] ≤ Pr[ j6=i Yj ≥ 2t ] ≤ 21 where the final inequality
is Markov’s inequality. Note that we cannot use the stronger Samuels’ conjecture here because we
would need it for n = 5, which is unproven; if we could, then we could get a better approximation
factor (and we would re-optimize C).
The rest of the analysis, including Case 2, is the same as before. Therefore, the expected
a
P
P
P
1 xu,t
reward obtained by our algorithm is at least u∈S a∈A rua B
t=1 (1 − 2 ) 6 , which is the same as
1
12 OPTPolyLP , completing the proof of Theorem 2.6.

5

Conclusion and open questions.

In this paper, we presented a ( 12 − ε)-approximation for the fully general MAB superprocess with
multi-period actions—no preemption problem by following a scaled copy of an optimal solution to
the LP relaxation, and this is tight. However, when preemption is allowed, we were only able to
1
-approximation, using the solution to the LP relaxation mainly for generating priorities,
obtain a 12
and resorting to weak Markov-type bounds in the analysis. It seems difficult to follow a scaled copy
of a solution to the LP relaxation when preemption is allowed, because arms can be paused and
restarted. We do conjecture that our bound of ( 21 + ε) on the gap of the LP is correct in this case
and that it is possible to obtain a ( 12 − ε)-approximation, but this remains an open problem. Also,
we have not explored how our techniques apply to certain extensions of the multi-armed bandit
problem (switching costs, simultaneous plays, delayed feedback, contextual information, etc.).
28

Acknowledgments. The author’s research was partly supported by a Natural Sciences and
Engineering Research Council of Canada (NSERC) Postgraduate Scholarship - Doctoral. The author would like to thank Michel Goemans for helpful discussions and suggestions on the presentation
of the results. A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, and useful remarks from several anonymous referees there have
also improved the presentation of the results.

References
[BCB12]

Sébastien Bubeck and Nicolo Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems, arXiv preprint arXiv:1204.5721 (2012).

[Ber95]

Dimitri P Bertsekas, Dynamic programming and optimal control, Athena Scientific
Belmont, MA, 1995.

[BGK11]

Anand Bhalgat, Ashish Goel, and Sanjeev Khanna, Improved approximation results
for stochastic knapsack problems, Proceedings of the twenty-second annual ACM-SIAM
symposium on Discrete Algorithms, SIAM, 2011, pp. 1647–1665.

[BGL+ 12] Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri
Rudra, When lp is the cure for your matching woes: Improved bounds for stochastic
matchings, Algorithmica 63 (2012), no. 4, 733–762.
[Bha11]

Anand Bhalgat, A (2+eps)-approximation algorithm for the stochastic knapsack problem, Unpublished Manuscript (2011).

[BM07]

Dimitris Bertsimas and Adam J Mersereau, A learning approach for interactive marketing to a customer segment, Operations Research 55 (2007), no. 6, 1120–1135.

[BN14]

Nikhil Bansal and Viswanath Nagarajan, On the adaptivity gap of stochastic orienteering, Integer Programming and Combinatorial Optimization, Springer, 2014, pp. 114–
125.

[CSW93]

Robert L Carraway, Robert L Schmidt, and Lawrence R Weatherford, An algorithm for
maximizing target achievement in the stochastic knapsack problem with normal returns,
Naval Research Logistics (NRL) 40 (1993), no. 2, 161–173.

[DGV04]

Brian C Dean, Michel X Goemans, and J Vondrdk, Approximating the stochastic knapsack problem: The benefit of adaptivity, Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, IEEE, 2004, pp. 208–217.

[DGV05]

Brian C Dean, Michel X Goemans, and Jan Vondrák, Adaptivity and approximation
for stochastic packing problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2005,
pp. 395–404.
29

[DGV08]

, Approximating the stochastic knapsack problem: The benefit of adaptivity,
Mathematics of Operations Research 33 (2008), no. 4, 945–964.

[FM11]

Vivek F Farias and Ritesh Madan, The irrevocable multiarmed bandit problem, Operations Research 59 (2011), no. 2, 383–399.

[GGM06]

Ashish Goel, Sudipto Guha, and Kamesh Munagala, Asking the right questions: Modeldriven optimization using probes, Proceedings of the twenty-fifth ACM SIGMODSIGACT-SIGART symposium on Principles of database systems, ACM, 2006, pp. 203–
212.

[GGW11]

John Gittins, Kevin Glazebrook, and Richard Weber, Multi-armed bandit allocation
indices, John Wiley & Sons, 2011.

[GI99]

Ashish Goel and Piotr Indyk, Stochastic load balancing and related problems, Foundations of Computer Science, 1999. 40th Annual Symposium on, IEEE, 1999, pp. 579–586.

[GKMR11] Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R Ravi, Approximation algorithms for correlated knapsacks and non-martingale bandits, Foundations
of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE, 2011,
pp. 827–836.
[GKNR14] Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, and R Ravi, Running errands in time: Approximation algorithms for stochastic orienteering, Mathematics of Operations Research 40 (2014), no. 1, 56–79.
[GM07a]

Sudipto Guha and Kamesh Munagala, Approximation algorithms for budgeted learning problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of
computing, ACM, 2007, pp. 104–113.

[GM07b]

, Model-driven optimization using adaptive probes, Proceedings of the eighteenth
annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 308–317.

[GM08]

, Sequential design of experiments via linear programming, arXiv preprint
arXiv:0805.2630 (2008).

[GM13]

, Approximation algorithms for bayesian multi-armed bandit problems, arXiv
preprint arXiv:1306.3525 (2013).

[IID11]

Taylan Ilhan, Seyed MR Iravani, and Mark S Daskin, Technical note-the adaptive knapsack problem with stochastic rewards, Operations research 59 (2011), no. 1, 242–248.

[Kes13]

John Michael Kessler, United states air force fighter jet maintenance models: effectiveness of index policies, Ph.D. thesis, Massachusetts Institute of Technology, 2013.

30

[KRT00]

Jon Kleinberg, Yuval Rabani, and Éva Tardos, Allocating bandwidth for bursty connections, SIAM Journal on Computing 30 (2000), no. 1, 191–217.

[LY13]

Jian Li and Wen Yuan, Stochastic combinatorial optimization via poisson approximation, Proceedings of the forty-fifth annual ACM symposium on Theory of computing,
ACM, 2013, pp. 971–980.

[Ma14]

Will Ma, Improvements and generalizations of stochastic knapsack and multi-armed
bandit approximation algorithms, Proceedings of the Twenty-Fifth Annual ACM-SIAM
Symposium on Discrete Algorithms, SIAM, 2014, pp. 1154–1163.

[MP12]

Aranyak Mehta and Debmalya Panigrahi, Online matching with stochastic rewards,
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on,
IEEE, 2012, pp. 728–737.

[MR10]

Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Chapman &
Hall/CRC, 2010.

[MSU99]

Rolf H Möhring, Andreas S Schulz, and Marc Uetz, Approximation in stochastic
scheduling: the power of lp-based priority policies, Journal of the ACM (JACM) 46
(1999), no. 6, 924–942.

[Pin12]

Michael L Pinedo, Scheduling: theory, algorithms, and systems, Springer Science &
Business Media, 2012.

[Sam66]

S. M. Samuels, On a Chebyshev-type inequality for sums of independent random variables, Ann. Math. Stat. 37 (1966), no. 1, 248–259.

[Sam68]

, More on a Chebyshev-type inequality for sums of independent random variables,
Defense Technical Information Center, 1968.

[SU01]

Martin Skutella and Marc Uetz, Scheduling precedence-constrained jobs with stochastic
processing times on parallel machines, Proceedings of the twelfth annual ACM-SIAM
symposium on Discrete algorithms, Society for Industrial and Applied Mathematics,
2001, pp. 589–590.

6

Appendix A: Example showing preemption is necessary for uncorrelated SK.

Consider the following example: there are n = 3 items, I1 , I2 , I3 . I1 instantiates to size 6 with
probability 21 , and size 1 with probability 12 . I2 deterministically instantiates to size 9. I3 instantiates to size 8 with probability 12 , and size 4 with probability 12 . I1 , I2 , I3 , if successfully inserted,
return rewards of 4, 9, 8, respectively. We have a knapsack of size 10.

31

We describe the optimal preempting policy. First we insert I1 . After 1 unit of time, if I1
completes, we go on to insert I2 , which will deterministically fit. If I1 doesn’t complete, we set it
aside and insert I3 to completion. If it instantiates to size 8, then we cannot get any more reward
from other items. If it instantiates to size 4, then we can go back and finish inserting the remaining
5 units of I1 . The expected reward of this policy is 21 (4 + 9) + 12 ( 12 8 + 12 (8 + 4)) = 11.5.
Now we enumerate the policies that can only cancel but not preempt. If we first insert I2 , then
the best we can do is try to insert I1 afterward, getting a total expected reward of 11. Note that
any policy never fitting I2 can obtain reward at most 11, since with probability 14 we cannot fit
both I1 and I3 . This rules out policies that start with I3 , which has no chance of fitting alongside
I2 . Remaining are the policies that first insert I1 . If it doesn’t complete after 1 unit of time, then
we can either settle for the 9 reward of I2 , or finish processing I1 with the hope of finishing I3
afterward. However, in this case, I3 only finishes half the time, so we earn more expected reward
by settling for I2 . Therefore, the best we can do after first inserting I1 is to stop processing it after
time 1 (regardless of whether it completes), and process I2 , earning a total expected reward of 11.
We have shown that indeed, for uncorrelated SK, there is a gap between policies that can preempt versus policies that can only cancel. It appears that this gap is bounded by a constant, contrary to the gap between policies that can cancel versus policies that cannot cancel (see [GKMR11,
appx. A.1]).

7
7.1

Appendix B: Proofs from Section 2.
Proof of Lemma 2.2.

a }, {y } satisfying (2a)-(2c), (3a)-(3c) which imply (4). For all i ∈ [n],
Suppose we are given {zπ,i,t
π,t
P
P
a
for each a ∈ A. We aim to
u ∈ Si , t ∈ [B], let su,t = π∈S:πi =u yπ,t , and let xau,t = π∈S:πi =u zπ,i,t
a
show {xu,t }, {su,t } satisfies (10a)-(10c), (11), (12a)-(12c) and makes (9) the same objective function
P
P
a .
as (1). For convenience, we adopt the notation that xu,t = a∈A xau,t and zπ,i,t = a∈A zπ,i,t
P
Pn P
Pn P
P
P
zπ,i,t . But there is a
(11):
i=1
u∈Si
π:πi =u zπ,i,t =
u∈S xu,t =
P π∈S
Pn i=1 u∈Si :u=πi
unique u ∈ Si such that u = πi , so the sum equals π∈S i=1 zπ,i,t , which is at most 1 by (4).
P
(10a): For u ∈ Si , xu,t = π:πi =u zπ,i,t , and each term in the sum is at most yπ,t by (2a) and
P
(2c), hence xu,t ≤ π:πi =u yπ,t = su,t .
P
α , and each term in the sum is equal to y
(10b): For u ∈ B, xαu,t = π:πi =u zπ,i,t
π,t by (2b), hence
P
α
xu,t = π:πi =u yπ,t = su,t .
(10c), (12a), and (12b) are immediate from (2c), (3a), and (3b), respectively. For (12c), fix

32

t > 1, i ∈ [n], and u ∈ Si . Sum (3c) over {π : πi = u} to get
X

yπ,t =

π:πi =u

X

n
X X

yπ,t−1 −

π:πi =u j=1

π:πi =u

X

su,t = su,t−1 −

zπ,i,t−1 −

X

X

zπav ,j,t−1 · pav,πj

π:πi =u j=1 (v,a)∈Par(πj )

X X

zπ,j,t−1

π:πi =u j6=i

π:πi =u

+

n
X X

zπ,j,t−1 +

X

X X

zπav ,i,t−1 · pav,u +

zπav ,j,t−1 · pav,πj

π:πi =u j6=i (v,a)∈Par(πj )

π:πi =u (v,a)∈Par(u)

X X

su,t = su,t−1 − xu,t−1 −

X

zπ,j,t−1

π:πi =u j6=i

+

X

(

X

zπav ,i,t−1 ) · pav,u +

XXX

(v,a)∈Par(u) π:πi =u

zπav ,j,t−1 · pav,πj

j6=i v∈Sj a∈A {π:πi =u,Par(πj )3(v,a)}

X X

su,t = su,t−1 − xu,t−1 −

X

zπ,j,t−1

π:πi =u j6=i

+

X

(

X

a
zπ,i,t−1
) · pav,u +

X

X X

X

a
zπ,j,t−1
·(

j6=i v∈Sj a∈A π:πi =u,πj =v

(v,a)∈Par(u) π:πi =v

su,t = su,t−1 − xu,t−1 −

XXX

pav,w )

w:pa
v,w >0

zπ,j,t−1

π:πi =u j6=i

+

X

xav,t−1 · pav,u +

XXX

X X

X

zπ,j,t−1 +

j6=i π:πi =u

su,t = su,t−1 − xu,t−1 +

a
zπ,j,t−1
· (1)

j6=i v∈Sj a∈A π:πi =u,πj =v

(v,a)∈Par(u)

su,t = su,t−1 − xu,t−1 −

X

X

(v,a)∈Par(u)

xav,t−1 · pav,u +

X X

zπ,j,t−1

j6=i π:πi =u

xav,t−1 · pav,u

(v,a)∈Par(u)

which is exactly (12c).
PB P
P
Pn P
P
P
P
a
a
z a , and by the same ma(9): u∈S a∈A rua B
a∈A ru
i=1
u∈Si
t=1 xu,t =
PiB=u π,i,t
P
Pn P t=1 a π:π
a . Thus (9) is the same
nipulation we made for (11), this is equal to π∈S i=1 a∈A rπi t=1 zπ,i,t
as (1), completing the proof of Lemma 2.2.

7.2

Proof of Lemma 2.3.

a }, {y } satisfying (6a)-(6c), (7a)-(7e) which imply (8). For all i ∈ [n],
Suppose we are given {zπ,i,t
π,t
P
P
a
u ∈ Si , t ∈ [B], let su,t = π∈S 0 :πi =u yπ,t , and let xau,t = π∈S 0 :πi =u zπ,i,t
for each a ∈ A. We aim to
a
show {xu,t }, {su,t } satisfies (10a)-(10c), (11), (13a)-(13d) and makes (9) the same objective function
P
P
a .
as (5). For convenience, we adopt the notation that xu,t = a∈A xau,t and zπ,i,t = a∈A zπ,i,t
P
Pn P
P
P
Pn P
(11):
u∈S xu,t =
i=1
u∈Si
π:πi =u zπ,i,t =
π∈S 0
i=1
u∈Si :u=πi zπ,i,t . The difference
from the previous derivation of (11) is that there is only a unique u ∈ Si such that u = πi , if
P
P
πi 6= φi . So the sum equals π∈S 0 i∈I(π) zπ,i,t , which is at most 1 by (8).
Using this same manipulation, the equivalence of (9) and (5) follows the same derivation as
before. (10a) and (10b) also follow the same derivations as before; (10c), (13a), and (13b) are

33

immediate. It remains to prove (13c) and (13d).
(13d): Fix t > 1, i ∈ [n], and u ∈ Si \ {ρi }. First consider the case where depth(u) > 1. All
π ∈ S 0 such that πi = u fall under (7e), so we can sum over these π to get
X

X

yπ,t =

π:πi =u

X

zπav ,i,t−1 · pav,u

π:πi =u (v,a)∈Par(u)

X

su,t =

(

X

zπav ,i,t−1 ) · pav,u

(v,a)∈Par(u) π:πi =u

Since depth(u) > 1, v 6= ρi , so {π v : π ∈ S 0 , πi = u} = {π : π ∈ S 0 , πi = v}. Hence the RHS of the
P
above equals (v,a)∈Par(u) xav,t−1 · pav,u which is exactly (13d).
For the other case where depth(u) = 1, all π ∈ S 0 such that πi = u fall under (7d), so we can
sum over these π to get
X

yπ,t =

X

X

(

X

zπa0 ,i,t−1 ) · paρi ,u

π:πi =u a:(ρi ,a)∈Par(u) π 0 ∈P(π ρi )

π:πi =u

su,t =

X

(

X

X

zπa0 ,i,t−1 ) · paρi ,u

a:(ρi ,a)∈Par(u) π:πi =u π 0 ∈P(π ρi )

su,t =

X

(

X

a
zπ,i,t−1
) · paρi ,u

a:(ρi ,a)∈Par(u) π:πi =ρi

su,t =

X

xaρi ,t−1 · paρi ,u

a:(ρi ,a)∈Par(u)

We explain the third equality. Since u 6= ρi implies arm i is the active arm in all of {π ∈ S 0 : πi = u},
this set is equal to {ρ1 , φ1 } × · · · × u × · · · × {ρn , φn }. Thus {π 0 ∈ P(π ρi ) : π ∈ S 0 , πi = u} = {π 0 ∈
P(π) : π ∈ {ρ1 , φ1 } × · · · × ρi × · · · × {ρn , φn }}. Recall that P(π) is the set of joint nodes that
would transition to π with no play. Therefore, this set is equal to {π 0 ∈ S 0 : πi0 = ρi }, as desired.
(13c): Fix t > 1 and i ∈ [n]. Unfortunately, π ∈ S 0 such that πi = ρi can fall under (7c), (7d),
or (7e). First let’s sum over the π falling under (7c):

X
X
X 
X
yπ,t =
yπ0 ,t−1 −
zπ0 ,j,t−1
0
π ∈A:π
/
i =ρi π ∈P(π)

π ∈A:π
/
i =ρi

=

X



j∈I(π 0 )

yπ,t−1 − zπ,i,t−1 −

π∈S 0 :πi =ρi

X

zπ,j,t−1

j∈I(π)\{i}

= sρi ,t−1 − xρi ,t−1 −

X
0

X

π∈S :πi =ρi j∈I(π)\{i}

34

zπ,j,t−1



where the second equality requires the same set bijection explained above. Furthermore,


X
X
X
X
X
X
X
zπ,j,t−1 +
zπ,j,t−1 =
zπ,k,t−1 +
0

k6=i π∈Ak :πi =ρi

π∈S :πi =ρi j∈I(π)\{i}

=

X

=

X



X

k6=i π∈Ak :πi =ρi

X


zπ,j,t−1 +

X

zπ,k,t−1 +

X

X

zπ,j,t−1

π ∈A:π
/
i =ρi j:πj =ρj ,j6=i

j:πj =ρj ,j6=i

X

zπ,k,t−1 +

zπ,j,t−1

π ∈A:π
/
i =ρi j∈I(π)\{i}

j∈I(π)\{i,k}

X

zπ,j,t−1

0

k6=i π∈Ak :πi =ρi

π∈S :πi =ρi j:πj =ρj ,j6=i

Now let’s sum over the π falling under (7e):
X

X

yπ,t =

X

=

X

=

X

=

X

=

X

X

X

zπav ,j,t−1 · pav,πj

j6=i {π:πi =ρi ,depth(πj )>1} (v,a)∈Par(πj )

j6=i {π:πi =ρi ,depth(πj )>1}

X

X

X

zπav ,j,t−1 · pav,πj

j6=i v∈Sj \{ρj } a∈A {π:πi =ρi ,Par(πj )3(v,a)}

X

X

X

a
zπ,j,t−1
·(

X

X

pav,w )

w:pa
v,w >0

j6=i v∈Sj \{ρj } a∈A π:πi =ρi ,πj =v

X

X

a
zπ,j,t−1
· (1)

j6=i v∈Sj \{ρj } a∈A π:πi =ρi ,πj =v

X

zπ,j,t−1

j6=i π∈Aj :πi =ρi

where the third equality uses the fact that v 6= ρj to convert π v to π. Finally, let’s sum over the π
falling under (7d):
X

X

yπ,t

j6=i {π:πi =ρi ,depth(πj )=1}

=

X

=

XX

=

XX

=

XX

X

X

(

X

zπa0 ,j,t−1 ) · paρj ,πj

j6=i {π:πi =ρi ,depth(πj )=1} a:(ρj ,a)∈Par(πj ) π 0 ∈P(π ρj )

X

X

(

zπa0 ,j,t−1 ) · paρj ,πj

j6=i a∈A {π:πi =ρi ,Par(πj )3(ρj ,a)} π 0 ∈P(π ρj )

X

a
zπ,j,t−1
·(

paρj ,w )

w:pa
ρj ,w >0

j6=i a∈A π:πi =ρi ,πj =ρj

X

X

a
zπ,j,t−1
· (1)

j6=i a∈A π:πi =ρi ,πj =ρj

=

X

X

zπ,j,t−1

π:πi =ρi j:πj =ρj ,j6=i

where the third equality requires the same set bijection again. Combining the last four blocks of
equations, we get sρi ,t = sρi ,t−1 − xρi ,t−1 which is exactly (13c), completing the proof of Lemma 2.3.

35

8

Appendix C: Proofs from Section 4.

8.1

Proof of Lemma 4.1.

Finding the q’s is a separate problem for each arm, so we can fix i ∈ [n]. Furthermore, we can
fix u ∈ Si \ {ρi }; we will specify an algorithm that defines {qv,b,t0 ,u,a,t : a ∈ A, t ∈ [B], (v, b) ∈
Par(u), t0 < t} satisfying (19a) and (19b).
P
Observe that by substituting (10a) into (12c), we get su,t0 ≤ (v,b)∈Par(u) xbv,t0 −1 · pbv,u for all
t0 > 1. Summing over t0 = 2, . . . , t for an arbitrary t ∈ [B], and using (10a) again on the LHS, we
P
P
P
P
b
b
get tt0 =2 a∈A xau,t0 ≤ t−1
t0 =1
(v,b)∈Par(u) xv,t0 · pv,u .
Now, for all t0 = 2, . . . , B and a ∈ A, initialize x̃at0 := xau,t0 . For all t0 = 1, . . . , B − 1 and
(v, b) ∈ Par(u), initialize x̃bv,t0 := xbv,t0 · pbv,u . We are omitting the subscript u because u is fixed. The
following B − 1 inequalities hold:
00

t X
X
t0 =2

x̃at0

≤

a∈A

00 −1
tX

X

t0 =1

(v,b)∈Par(u)

x̃bv,t0

t00 = 2, . . . , B

(22)

The algorithm updates the variables x̃at0 and x̃bv,t0 over iterations t = 2, . . . , B, but we will inductively
show that inequality t00 of (22) holds until the end of iteration t00 . The algorithm can be described
as follows:
Decomposition Algorithm
• Initialize all qv,b,t0 ,u,a,t := 0.
• For t = 2, . . . , B:
– While there exists some a ∈ A such that x̃at > 0:
1. Choose any non-zero x̃bv,t0 , where (v, b) ∈ Par(u), with t0 < t.
2. Let Q = min{x̃at , x̃bv,t0 }.
3. Set qv,b,t0 ,u,a,t :=

Q
.
xbv,t0 ·pbv,u

4. Subtract Q from both x̃at and x̃bv,t0 .
Let’s consider iteration t of the algorithm. The inequality of (22) with t00 = t guarantees that
there always exists such a non-zero x̃bv,t0 in Step 1. In Step 4, Q is subtracted from both the LHS
and RHS of all inequalities of (22) with t00 ≥ t, so these inequalities continue to hold. (Q is also
subtracted from the RHS of inequalities of (22) with t0 < t00 < t, so these inequalities might cease
to hold.) This inductively establishes that all inequalities of (22) with t00 ≥ t hold during iteration
t, and thus Step 1 of the algorithm is well-defined.
Now we show that (19b) is satisfied. Suppose on iteration t of the algorithm, we have some
x̃at > 0 and x̃bv,t0 > 0 on Step 1. Note that qv,b,t0 ,u,a,t must currently be 0, since if it was already
36

set, then either x̃at or x̃bv,t0 would have been reduced to 0. Therefore, in Step 3 we are incrementing
the LHS of (19b) by xbv,t0 · pbv,u · xb Q·pb = Q, after which we are subtracting Q from x̃at in Step 4.
v,t0

v,u

Since over iterations t = 2, . . . , B, for every a ∈ A, x̃at gets reduced from xau,t to 0, it must be the
case that every equation in (19b) holds by the end of the algorithm.
For (19a), we use a similar argument. Fix some (v, b) ∈ Par(u) and t0 ∈ [B − 1]. Whenever we
add xb Q·pb to the LHS of (19a), we are reducing x̃bv,t0 by Q. Since x̃bv,t0 starts at xbv,t0 · pbv,u and
v,t0

v,u

cannot be reduced below 0, the biggest we can make the LHS of (19a) is

xbv,t0 ·pbv,u
xbv,t0 ·pbv,u

= 1.

Finally, it is clear that the algorithm takes polynomial time, since every time we loop through
Steps 1 to 4 either x̃at or x̃bv,t0 goes from non-zero to zero, and there were only a polynomial number
of such variables to begin with. Other than the statement for u ∈ B, this completes the proof of
Lemma 4.1.
Now, if u ∈ B, then we can strengthen (22). Indeed, substituting (10b) (instead of (10a)) into
(12c), we get that all inequalities of (22) hold as equality. At the start of iteration t = 2, it is the
P
case that x̃αt = (v,b)∈Par(u) x̃bv,t−1 , and by the end of the iteration, it will be the case that x̃αt = 0,
and x̃bv,t−1 = 0, qv,b,t−1,u,α,t = 1 for all (v, b) ∈ Par(u). As a result, the equalities of (22) with
t00 > t will continue to hold as equality. We can inductively apply this argument to establish that
qv,b,t0 ,u,α,t0 +1 = 1 for all (v, b) ∈ Par(u) and t0 ∈ [B − 1], as desired.

8.2

Proof of Lemma 4.2.

We make use of the following conjecture of Samuels, which is proven for n ≤ 4 (see [Sam66, Sam68]):
Conjecture 8.1. Let X1 , . . . , Xn be independent non-negative random variables with respective
P
P
expectations µ1 ≥ . . . ≥ µn , and let λ > ni=1 µi . Then Pr[ ni=1 Xi ≥ λ] is maximized when the
Xi ’s are distributed as follows, for some index k ∈ [n]:
• For i > k, Xi = µi with probability 1.
• For i ≤ k, Xi = λ −

Pn

`=k+1 µ`

with probability

λ−

Pnµi

`=k+1

µ`

, and Xi = 0 otherwise.

If we have E[Yi ] + E[Yj ] ≤ 6t for i 6= j, then we can treat Yi + Yj as a single random variable
satisfying E[Yi + Yj ] ≤ 6t . By the pigeonhole principle, we can repeat this process until n ≤ 3, since
Pm
t
j=1 E[Yj ] ≤ 3 . In fact, we assume n is exactly 3 (we can add random variables that take constant
value 0 if necessary), so that we can apply Conjecture 8.1 for n = 3, which has been proven to be
true. We get that Pr[Y1 + Y2 + Y3 ≥ 2t ] cannot exceed the maximum of the following (corresponding
to the cases k = 3, 2, 1, respectively):
µ1 
µ2 
µ3 
• 1− 1− t 1− t 1− t
2

• 1− 1−
• 1− 1−

2

t
2

µ1
− µ3

t
2


µ1
− µ2 − µ3



1−

2
t
2

µ2 
− µ3

37

Now we employ Lemma 4 from [BGL+ 12] to bound these quantities:
Lemma 8.2. Let r and pmax be positive real values. Consider the problem of maximizing 1 −
Qt
Pt
i=1 (1 − pi ) subject to the constraints
i=1 pi ≤ r, and 0 ≤ pi ≤ pmax for all i. Denote the
maximum value by β(r, pmax ). Then
bp

β(r, pmax ) = 1 − (1 − pmax )

r
c
max

(1 − (r − b

r
pmax

c · pmax ))

r

≤ 1 − (1 − pmax ) pmax

Recall that µ1 , µ2 , µ3 ≤

t
6

and µ1 + µ2 + µ3 ≤ 3t .

• In the first case k = 3, we get pmax =
1 − (1 − 13 )2 = 59 , as desired.

1
3

and r =

2
3,

so the quantity is at most β( 32 , 31 ) ≤

• In the second case k = 2, for an arbitrary µ3 ∈ [0, 6t ], we get that the quantity is at most
t
t
t

( t −µ3 )/( t )
− µ3
3
6
β 3t
, t 6
. It can be checked that the maximum occurs
≤ 1− 1− t 6
−
µ
−
µ
−
µ
3
3
3
2
2
2
at µ3 = 0, so the quantity is at most 59 for any value of µ3 ∈ [0, 6t ], as desired.
• In the third case k = 1, we get that the quantity is at most
most

1
2

over µ1 ∈ [0, 6t ], as desired.

t
2

µ1
=
− ( 3t − µ1 )

Therefore, Conjecture 8.1 tells us that the maximum value of Pr[
the proof of Lemma 4.2.

38

Pm

j=1 Yj

t
6

µ1
, which at
+ µ1

≥ 2t ] is 59 , completing

