Abstract
We will survey some ways that linear programming relaxations can capture optimal strategies in (discrete) stochastic optimization
problems. These problems are often NP-hard or worse, and we will discuss techniques used to develop approximation algorithms for
them. Examples include stochastic knapsack and some budgeted multi-armed bandit problems.