Sequential Learning under Probabilistic Constraints

We provide the first study on online learning problems under stochastic constraints that are "soft", i.e., need to be satisfied with high probability. These constraints are imposed on all or some stages of the time horizon so that the stage decision probabilistically satisfies a safety condition that is realized after the decision is made. The distributions that govern these conditions are learned through the collected observations. Under a Bayesian framework, we study a scheme that provides statistical feasibility guarantees through the time horizon, by using posterior Monte Carlo samples to form sampled constraints that leverage the scenario generation approach in chance-constrained programming. We demonstrate how our scheme can be integrated into Thompson sampling and illustrate it with an application in online advertisement.