Approximation Algorithms for Stochastic Optimization: An Overview
Approximation Algorithms for
Stochastic Optimization
Anupam Gupta
Carnegie Mellon University
stochastic optimization
Question:
How to model uncertainty in the inputs?
data may not yet be available
obtaining exact data is difficult/expensive/time-consuming
but we do have some
stochastic
predictions about the inputs
Goal:
make (near)-optimal decisions given some predictions (probability
distribution on potential inputs).
Prior work:
Studied since the 1950s, and for good reason:
many practical applications…
approximation algorithms
We’ve seen
approximation algorithms
for many such
stochastic optimization problems over the past decade
Several different models, several different techniques.
I’ll give a quick sketch of three different themes here:
1.
weakening the adversary (stochastic optimization online)
2.
two stage stochastic optimization
3.
stochastic knapsack and adaptivity gaps
❶stochastic optimization online
the worst-case setting is sometimes too pessimistic
so if we know that the “adversary” is just a stochastic process,
things should be easier
(weakening the adversary)
[E.g., Karp’s algorithm for stochastic geometric TSP]
the Steiner tree problem
Input
: a metric space
a root vertex
r
a subset
R of terminals
Output
: a tree
T connecting R to
r
of minimum length/cost.
Facts
: NP-hard and APX-hard
MST is a 2-approximation
cost(MST(R
[
r)) ≤
2 OPT(R)
[Byrka et al. STOC ’10]
give a
1.39-approximation
the online greedy algorithm
[Imase Waxman ’91]
in the standard online setting, the greedy
algorithm is
O(log k)
competitive for sequences of length
k
.
and this is tight.
model
❶
: stochastic online
Measure of Goodness:
Usual measure is competitive ratio
Here we consider
one can also consider:
Suppose demands are nodes in V drawn
uniformly
at random,
independently
of previous demands.
uniformity
: not important
could be given probabilities
p
1
,
p
2
, …,
p
n
which sum to 1
independence
: important, lower bounds otherwise
Measure of goodness:
Assume for this talk:
know the length
k
of the sequence
≤ 4
model
❶
: stochastic online
Augmented greedy
1.
Sample
k
vertices
S = {s
1
,
s
2
, …,
s
k
}
independently.
2.
Build an MST
T
0
on these vertices
S
[
root r
.
3.
When actual demand points
x
t
(for 1
·
t
·
k) arrives,
greedily connect
x
t
to the tree
T
t-1
[Garg G. Leonardi Sankowski]
Augmented greedy
Augmented greedy
1.
Sample
k
vertices
S = {s
1
,
s
2
, …,
s
k
}
independently.
2.
Build an MST
T
0
on these vertices
S
[
root r
.
3.
When actual demand points
x
t
(for 1
·
t
·
k) arrives,
greedily connect
x
t
to the tree
T
t-1
Proof for augmented greedy
Let X = {x
1
,
x
2
, …,
x
k
} be the actual demands
Claim 1:
E[
cost(T
0
)
]
≤
2
£
E[
OPT(X)
]
Claim 2:
E[
cost of k augmentations in Step 3
] ≤ E[
cost(T
0
)
]
Proof:
E[
OPT(S)
] = E[
OPT(X)
]
Proof for augmented greedy
Let X = {x
1
,
x
2
, …,
x
k
} be the sample
Claim 2:
E
S,X
[
augmentation cost
] ≤ E
S
[
MST(S
[
r)
]
Claim 2a:
E
S,X
[
x
2
X
d(x, S
[
r)
] ≤ E
S
[
MST(S
[
r)
]
Claim 2b:
E
S,x
[
d(x, S
[
r)
] ≤ (1/k) E
S
[
MST(S
[
r)
]
Proof for augmented greedy
Claim 2b:
E
S,x
[
d(x, S
[
r)
] ≤ (1/k) E
S
[
MST(S
[
r)
]
Consider the
MST(S
[
x
[
r)
Proof for augmented greedy
Claim 2b:
E
S,x
[
d(x, S
[
r)
] ≤ (1/k) E
S
[
MST(S
[
r)
]
= E[ distance from
one random point
to
(k random points
[
r)
]
≥ (1/k) * k * E
y, S-y
[ distance(y, (
S-y)
[
r)
]
≥ E[ distance from
one random point
to
(k-1 random points
[
r)
]
≥ E[ distance from
one random point
to
(k random points
[
r)
]
Proof for augmented greedy
Let X = {x
1
,
x
2
, …,
x
k
} be the actual demands
Claim 1:
E[
cost(T
0
) ]
≤
2
£
E[ OPT(X) ]
Claim 2:
E[ cost of k augmentations in Step 3 ] ≤ E[
cost(T
0
) ]
summary for stochastic online
other problems in this i.i.d. framework
facility location, set cover [Grandoni+], etc.
Other measures of goodness:
O(log log n)
known for expected ratio
stochastic arrivals have been previously studied
k-server/paging under “nice” distributions
online scheduling problems [see, e.g., Pinedo, Goel Indyk, Kleinberg Rabani Tardos]
the “random-order” or “secretary” model
adversary chooses the demand set, but appears in random order
[cf. Aranyak and Kamal’s talks on online matchings]
the secretary problem and its many variants are very interesting
algorithms for facility location, access-network design, etc in this model
[Meyerson, Meyerson Munagala Plotkin]
but does not always help:
(log n) lower bound for Steiner tree
❷ two-stage stoc. optimization
today things are cheaper, tomorrow prices go up by
¸
but today we only know the distribution
¼
,
tomorrow we’ll know the real demands (drawn from
¼
)
such stochastic problems are (potentially) harder
than their deterministic counterparts
model
❷
: “two-stage” Steiner tree
The Model
:
Instead of one set R, we are
given
probability distribution
¼
over subsets of nodes.
E.g., each node v independently
belongs to R with probability
p
v
Or, may be explicitly defined
over a small set of “scenarios”
p
A
= 0.6
p
B
= 0.25
p
C
= 0.15
Stage I
(“Monday”)
Pick some set of edges
E
M
at
cost(e
)
for each edge e
Stage II
(“Tuesday”)
Random set R is drawn from
¼
Pick some edges
E
T,R
so that
E
M
[
E
T,R
connects R to root
but now pay
¸
cost(e
)
Objective Function:
cost
M
(
E
M
) +
E
¼
[
¸
cost
(
E
T,R
) ]
p
A
= 0.6
p
B
= 0.25
p
C
= 0.15
model
❷
: “two-stage” Steiner tree
the algorithm
Algorithm is similar to the online case:
1.
sample
¸
different scenarios from distribution
¼
2.
buy approximate solution connecting these scenarios to
r
3.
on day 2, buy any extra edges to connect actual scenario
the analysis more involved than online analysis
needs to handle scenarios instead of single terminals
extends to other problems via “strict cost shares”
devise and analyse primal-dual algorithms for these problems
these P-D algorithms have no stochastic element to them
just allow us to assign “appropriate” share of the cost to each terminal
[G. Pál Ravi Sinha]
a comment on representations of
¼
“
Explicit scenarios
”
model
Complete listing of the sample space
“
Black box
” access to probability distribution
generates an independent
random sample
from
¼
Also,
independent decisions
Each vertex
v
appears with probability
p
v
indep. of others.
Sample Average Approximation Theorems
[e.g., Kleywegt SHdM, Charikar Chekuri Pal, Shmoys Swamy]
Sample poly(
¸
, N,
²
,
±
) scenarios from black box for
¼
Good approx on this explicit list is (1+
²
)-good for
¼
with prob (1-
±
)
stochastic vertex cover
Explicit scenario model:
M
scenarios explicitly listed.
Edge set
E
k
appears with prob.
p
k
Vertex costs
c(v
) on Monday,
c
k
(v
) on
Tuesday if scenario k appears.
Pick
V
0
on Monday,
V
k
on Tuesday
such that (
V
0
[
V
k
) covers
E
k
.
Minimize
c(V
0
)
+
E
k
[
c
k
(V
k
)
]
p
1
= 0.1
p
2
= 0.6
p
3
= 0.3
[Ravi Sinha, Immorlica Karger Mahdian Mirrokni, Shmoys Swamy]
Boolean variable
x(v
) = 1
iff vertex v chosen in the vertex cover
minimize
v
c(v
)
x(v
)
subject to
x(v
)
+
x(w
)
≥ 1
for each edge (v,w) in edge set E
and
x’s are in {0,1}integer-program formulation
Boolean variable
x(v
) = 1
iff v chosen on Monday,
y
k
(v
) = 1
iff v chosen on Tuesday if scenario k realized
minimize
v
c(v
)
x(v
)
+
k
p
k
[
v
c
k
(v
)
y
k
(v
)
]
subject to
[
x(v
) +
y
k
(v
)
] + [
x(w
) +
y
k
(w
)
] ≥ 1
for each k, edge (v,w) in
E
k
and
x’s, y’s are Boolean
integer-program formulation
minimize
v
c(v
)
x(v
)
+
k
p
k
[
v
c
k
(v
)
y
k
(v
)
]
subject to
[
x(v
) +
y
k
(v
)
] + [
x(w
) +
y
k
(w
)
] ≥ 1
for each k, edge (v,w) in
E
k
Now choose
V
0
= { v | x(v
) ≥ ¼ }, and
V
k
= { v | y
k
(v
) ≥ ¼ }
We are increasing variables by factor of 4
we get
a 4-approximation
linear-program relaxation
summary of two-stage stoc. opt.
most algos have been of the two forms
combinatorial / “primal-dual”
[Immorlica Karger Mahdian Mirrokni, G. Pál Ravi Sinha]
LP rounding-based
[Ravi Sinha, Shmoys Swamy, Srinivasan]
LP based usually can handle more general inflation factors etc.
can be extended to k-stages of decision making
more information available on each day 2,3,…, k-1
actual demand revealed on day k
both P-D/LP-based algos
[G. Pál Ravi Sinha, Swamy Shmoys]
runtimes usually exponential in k, sampling lower bounds
can we improve approximation factors
can we close these gaps? (when do we need to lose more than deterministic approx?)
better algorithms for k stages?
better understanding when the distributions are “simple”?
❸stoc. problems and adaptivity
the input consists of a collection of random variables
we can “probe” these variables to get their actual value,
but each probe “costs” us in some way
can we come up with good strategies to solve the
optimization problem?
optimal strategies may be adaptive,
can we do well using just non-adaptive strategies?
stochastic knapsack
A knapsack of size
B
, and a set of
n
items
item i has fixed reward
r
i
and a
random
size
S
i
What are we allowed to do?
We can try to add an item to the knapsack
At that point we find out the actual size
If this causes the knapsack to overflow, the process ends
Else, you get the reward
r
i
, and go on
Goal:
Find the strategy that maximizes the expected reward.
(we know the distribution of r.v. S
i
)
optimal strategy (decision tree) may be exponential sized!
[Dean Goemans Vondrák]
stochastic knapsack
A knapsack of size
B
, and a set of
n
items
item i has fixed reward
r
i
and a
random
size
S
i
Adaptive strategy:
(potentially exponentially sized) decision tree
Non-adaptive strategy:
e.g.:
w.p. ½, add item with highest reward
w.p. ½, add items in increasing order of
E[S
i
]/
r
i
What is the “adaptivity” gap for this problem?
(Q: how do you get a handle on the best adaptive strategies?)
(A: LPs, of course.)
[Dean Goemans Vondrák]
In fact, this non-adaptive algo is within O(1) of best adaptive algo.
provided you first “truncate”
the distribution of
S
i
to lie in [0,B]
O(1) approximation, also adaptivity gap of O(1).
extension: budgeted learning
0.99
0.01
0.1
0.9
0.4
0.6
1.0
$1
$1
$10
$0
…
½
½
2/3
1/3
1/3
2/3
$½
$2/3
$1/3
$3/4
$1/2
$1/4
that chain’s token moves according to the probability distribution
At each step, choose one of the Markov chains
after k steps, look at the states your tokens are on
get the highest payoff among all those states’ payoffs
extension: budgeted learning
0.99
0.01
0.1
0.9
0.4
0.6
1.0
$1
$1
$10
$0
…
½
½
2/3
1/3
1/3
2/3
$½
$2/3
$1/3
$3/4
$1/2
$1/4
Lots of machine learning work, approx algos work very recent, v. interesting
O(1)-approx:
[Guha Munagala, Goel Khanna Null]
for martingale case, non-adaptive
[G. Krishnaswamy Molinaro Ravi]
for non-martingale case, need adaptivity
If you can play for
k
steps, what is the best policy?
many extensions and directions
stochastic packing problems: budgeted learning
a set of state machines, which evolve each time you probe them
after k probes, get reward associated with the best state
satisfy a martingale condition
[Guha Muhagala, Goel Khanna Null]
stochastic knapsacks where rewards are correlated with sizes
or can cancel jobs part way: O(1) approx
[G. Krishnaswamy Molinaro Ravi]
these ideas extend to non-martingale budgeted learning.
stochastic orienteering
“how to run your chores and not be late for dinner, if all you know is the distribution
of each chore’s length”:
[Guha Munagala, G. Krishnaswamy Molinaro Nagarajan Ravi]
stochastic covering problems: set cover/submodular maximization/TSP
[Goemans Vondrak, Asadpour Oveis-Gharan Saberi, G. Nagarajan Ravi]
thank you!
This piece discusses approximation algorithms for stochastic optimization problems, focusing on modeling uncertainty in inputs, adapting to stochastic predictions, and exploring different optimization themes. It covers topics such as weakening the adversary in online stochastic optimization, two-stage stochastic optimization, and stochastic knapsack problems. The exploration includes the Steiner tree problem and the online greedy algorithm, shedding light on measuring algorithm performance in stochastic online settings.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximation Algorithms for Stochastic Optimization Anupam Gupta Carnegie Mellon University
stochastic optimization Question: How to model uncertainty in the inputs? data may not yet be available obtaining exact data is difficult/expensive/time-consuming but we do have some stochastic predictions about the inputs Goal: make (near)-optimal decisions given some predictions (probability distribution on potential inputs). Prior work: Studied since the 1950s, and for good reason: many practical applications
approximation algorithms We ve seen approximation algorithms for many such stochastic optimization problems over the past decade Several different models, several different techniques. I ll give a quick sketch of three different themes here: 1. weakening the adversary (stochastic optimization online) 2. two stage stochastic optimization 3. stochastic knapsack and adaptivity gaps
stochastic optimization online (weakening the adversary) the worst-case setting is sometimes too pessimistic so if we know that the adversary is just a stochastic process, things should be easier [E.g., Karp s algorithm for stochastic geometric TSP]
the Steiner tree problem Input: a metric space a root vertex r a subset R of terminals Output: a tree T connecting R to r of minimum length/cost. Facts: NP-hard and APX-hard MST is a 2-approximation cost(MST(R [r)) 2 OPT(R) [Byrka et al. STOC 10] give a 1.39-approximation
the online greedy algorithm [Imase Waxman 91] in the standard online setting, the greedy algorithm is O(log k) competitive for sequences of length k. and this is tight.
model : stochastic online Measure of Goodness: Usual measure is competitive ratio EA [ cost of algorithm A on ] OPT(set ) max Here we consider E ,A [ cost of algorithm A on ] E [ OPT(set ) ] one can also consider: cost of algorithm A on E ,A OPT(set )
model : stochastic online Suppose demands are nodes in V drawn uniformly at random, independently of previous demands. uniformity: not important could be given probabilities p1, p2, , pn which sum to 1 independence: important, lower bounds otherwise Measure of goodness: E ,A [ cost of algorithm A on ] E [ OPT(set ) ] 4 Assume for this talk: know the length k of the sequence
Augmented greedy 1. Sample k vertices S = {s1, s2, , sk} independently. 2. Build an MST T0 on these vertices S [ root r. 3. When actual demand points xt (for 1 t k) arrives, greedily connect xt to the tree Tt-1 [Garg G. Leonardi Sankowski]
Augmented greedy 1. Sample k vertices S = {s1, s2, , sk} independently. 2. Build an MST T0 on these vertices S [ root r. 3. When actual demand points xt (for 1 t k) arrives, greedily connect xt to the tree Tt-1
Proof for augmented greedy 1. 2. 3. Sample k vertices S = {s1, s2, , sk} independently. Build an MST T0 on these vertices S [ root r. When actual demand points xt (for 1 t k) arrives, greedily connect xt to the tree Tt-1 Let X = {x1, x2, , xk} be the actual demands Claim 1: E[ cost(T0) ] 2 E[ OPT(X) ] Proof: E[ OPT(S) ] = E[ OPT(X) ] Claim 2: E[ cost of k augmentations in Step 3 ] E[ cost(T0) ] Ratio of expectations 4
Proof for augmented greedy 1. 2. 3. Sample k vertices S = {s1, s2, , sk} independently. Build an MST T0 on these vertices S [ root r. When actual demand points xt (for 1 t k) arrives, greedily connect xt to the tree Tt-1 Let X = {x1, x2, , xk} be the sample Claim 2: ES,X[ augmentation cost ] ES[ MST(S [ r) ] Claim 2a: ES,X[ x2X d(x, S [ r) ] ES[ MST(S [ r) ] Claim 2b: ES,x[ d(x, S [ r) ] (1/k) ES[ MST(S [ r) ]
Proof for augmented greedy = E[ distance from one random point to (k random points [ r) ] (1/k) * k * Ey, S-y[ distance(y, (S-y) [ r) ] E[ distance from one random point to (k-1 random points [ r) ] E[ distance from one random point to (k random points [ r) ] Claim 2b: ES,x[ d(x, S [ r) ] (1/k) ES[ MST(S [ r) ]
Proof for augmented greedy 1. 2. 3. Sample k vertices S = {s1, s2, , sk} independently. Build an MST T0 on these vertices S [ root r. When actual demand points xt (for 1 t k) arrives, greedily connect xt to the tree Tt-1 Let X = {x1, x2, , xk} be the actual demands Claim 1: E[ cost(T0) ] 2 E[ OPT(X) ] Claim 2: E[ cost of k augmentations in Step 3 ] E[ cost(T0) ] Ratio of expectations 4
summary for stochastic online other problems in this i.i.d. framework facility location, set cover [Grandoni+], etc. Other measures of goodness: O(log log n) known for expected ratio stochastic arrivals have been previously studied k-server/paging under nice distributions online scheduling problems [see, e.g., Pinedo, Goel Indyk, Kleinberg Rabani Tardos] the random-order or secretary model adversary chooses the demand set, but appears in random order [cf. Aranyak and Kamal s talks on online matchings] the secretary problem and its many variants are very interesting algorithms for facility location, access-network design, etc in this model [Meyerson, Meyerson Munagala Plotkin] but does not always help: (log n) lower bound for Steiner tree
two-stage stoc. optimization today things are cheaper, tomorrow prices go up by but today we only know the distribution , tomorrow we ll know the real demands (drawn from ) such stochastic problems are (potentially) harder than their deterministic counterparts
model : two-stage Steiner tree The Model: Instead of one set R, we are given probability distribution over subsets of nodes. E.g., each node v independently belongs to R with probability pv Or, may be explicitly defined over a small set of scenarios pA = 0.6 pB = 0.25 pC = 0.15
model : two-stage Steiner tree Stage I( Monday ) Pick some set of edges EM at cost(e) for each edge e Stage II ( Tuesday ) Random set R is drawn from Pick some edges ET,R so that EM[ ET,R connects R to root but now pay cost(e) Objective Function: costM (EM) + E [ cost (ET,R) ] pA = 0.6 pB = 0.25 pC = 0.15
the algorithm Algorithm is similar to the online case: 1. 2. 3. sample different scenarios from distribution buy approximate solution connecting these scenarios to r on day 2, buy any extra edges to connect actual scenario the analysis more involved than online analysis needs to handle scenarios instead of single terminals extends to other problems via strict cost shares devise and analyse primal-dual algorithms for these problems these P-D algorithms have no stochastic element to them just allow us to assign appropriate share of the cost to each terminal [G. P l Ravi Sinha]
a comment on representations of Explicit scenarios model Complete listing of the sample space Black box access to probability distribution generates an independent random sample from Also, independent decisions Each vertex v appears with probability pv indep. of others. Sample Average Approximation Theorems [e.g., Kleywegt SHdM, Charikar Chekuri Pal, Shmoys Swamy] Sample poly( , N, , ) scenarios from black box for Good approx on this explicit list is (1+ )-good for with prob (1- )
stochastic vertex cover Explicit scenario model: M scenarios explicitly listed. Edge set Ek appears with prob. pk Vertex costs c(v) on Monday, ck(v) on Tuesday if scenario k appears. Pick V0 on Monday, Vk on Tuesday such that (V0[ Vk) covers Ek. Minimize c(V0) + Ek [ ck(Vk) ] p1 = 0.1 p2 = 0.6 p3 = 0.3 [Ravi Sinha, Immorlica Karger Mahdian Mirrokni, Shmoys Swamy]
integer-program formulation Boolean variable x(v) = 1 iff vertex v chosen in the vertex cover minimize v c(v) x(v) subject to x(v) + x(w) 1 and x s are in {0,1} for each edge (v,w) in edge set E
integer-program formulation Boolean variable x(v) = 1 iff v chosen on Monday, yk(v) = 1 iff v chosen on Tuesday if scenario k realized minimize v c(v) x(v) + k pk [ v ck(v) yk(v) ] subject to [ x(v) + yk(v) ] + [ x(w) + yk(w) ] 1 for each k, edge (v,w) in Ek and x s, y s are Boolean
linear-program relaxation minimize v c(v) x(v) + k pk [ v ck(v) yk(v) ] subject to [ x(v) + yk(v) ] + [ x(w) + yk(w) ] 1 for each k, edge (v,w) in Ek Now choose V0= { v | x(v) }, and Vk = { v | yk(v) } We are increasing variables by factor of 4 we get a 4-approximation
summary of two-stage stoc. opt. most algos have been of the two forms combinatorial / primal-dual [Immorlica Karger Mahdian Mirrokni, G. P l Ravi Sinha] LP rounding-based [Ravi Sinha, Shmoys Swamy, Srinivasan] LP based usually can handle more general inflation factors etc. can be extended to k-stages of decision making more information available on each day 2,3, , k-1 actual demand revealed on day k both P-D/LP-based algos [G. P l Ravi Sinha, Swamy Shmoys] runtimes usually exponential in k, sampling lower bounds can we improve approximation factors can we close these gaps? (when do we need to lose more than deterministic approx?) better algorithms for k stages? better understanding when the distributions are simple ?
stoc. problems and adaptivity the input consists of a collection of random variables we can probe these variables to get their actual value, but each probe costs us in some way can we come up with good strategies to solve the optimization problem? optimal strategies may be adaptive, can we do well using just non-adaptive strategies?
stochastic knapsack [Dean Goemans Vondr k] A knapsack of size B, and a set of n items item i has fixed reward ri and a random size Si (we know the distribution of r.v. Si) What are we allowed to do? We can try to add an item to the knapsack At that point we find out the actual size If this causes the knapsack to overflow, the process ends Else, you get the reward ri, and go on Goal: Find the strategy that maximizes the expected reward. optimal strategy (decision tree) may be exponential sized!
stochastic knapsack [Dean Goemans Vondr k] A knapsack of size B, and a set of n items item i has fixed reward ri and a random size Si provided you first truncate the distribution of Si to lie in [0,B] Adaptive strategy: (potentially exponentially sized) decision tree Non-adaptive strategy: e.g.: w.p. , add item with highest reward w.p. , add items in increasing order of E[Si]/ri What is the adaptivity gap for this problem? (Q: how do you get a handle on the best adaptive strategies?) (A: LPs, of course.) O(1) approximation, also adaptivity gap of O(1). In fact, this non-adaptive algo is within O(1) of best adaptive algo.
extension: budgeted learning $1 $ 0.01 0.99 $1 $10 0.1 $1/3 $2/3 0.9 1.0 1/3 2/3 2/3 1/3 0.4 $1/4 $0 $3/4 $1/2 0.6 At each step, choose one of the Markov chains that chain s token moves according to the probability distribution after k steps, look at the states your tokens are on get the highest payoff among all those states payoffs
extension: budgeted learning $1 $ 0.01 0.99 $1 $10 0.1 $1/3 $2/3 0.9 1.0 1/3 2/3 2/3 1/3 0.4 $1/4 $0 $3/4 $1/2 0.6 If you can play for k steps, what is the best policy? Lots of machine learning work, approx algos work very recent, v. interesting O(1)-approx: [Guha Munagala, Goel Khanna Null] for martingale case, non-adaptive [G. Krishnaswamy Molinaro Ravi] for non-martingale case, need adaptivity
many extensions and directions stochastic packing problems: budgeted learning a set of state machines, which evolve each time you probe them after k probes, get reward associated with the best state satisfy a martingale condition [Guha Muhagala, Goel Khanna Null] stochastic knapsacks where rewards are correlated with sizes or can cancel jobs part way: O(1) approx [G. Krishnaswamy Molinaro Ravi] these ideas extend to non-martingale budgeted learning. stochastic orienteering how to run your chores and not be late for dinner, if all you know is the distribution of each chore s length : [Guha Munagala, G. Krishnaswamy Molinaro Nagarajan Ravi] stochastic covering problems: set cover/submodular maximization/TSP [Goemans Vondrak, Asadpour Oveis-Gharan Saberi, G. Nagarajan Ravi]
