Sequential Learning under Probabilistic Constraints

Amirhossein Meisami, Henry Lam, Chen Dong, Abhishek Pani
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:620-630, 2018.

Abstract

We provide the first study on online learn- ing 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 decisions probabilistically satisfy some given safety conditions. The distribu- tions that govern these conditions are learned through the collected observations. Under a Bayesian framework, we introduce a scheme that provides statistical feasibility guarantees through the time horizon, by using posterior Monte Carlo samples to form sampled con- straints which leverage the scenario generation approach in chance-constrained programming. We demonstrate how our scheme can be inte- grated into Thompson sampling and illustrate it with an application in online advertisement.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-meisami18a, title = {Sequential Learning under Probabilistic Constraints}, author = {Meisami, Amirhossein and Lam, Henry and Dong, Chen and Pani, Abhishek}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {620--630}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/meisami18a/meisami18a.pdf}, url = {https://proceedings.mlr.press/r16/meisami18a.html}, abstract = {We provide the first study on online learn- ing 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 decisions probabilistically satisfy some given safety conditions. The distribu- tions that govern these conditions are learned through the collected observations. Under a Bayesian framework, we introduce a scheme that provides statistical feasibility guarantees through the time horizon, by using posterior Monte Carlo samples to form sampled con- straints which leverage the scenario generation approach in chance-constrained programming. We demonstrate how our scheme can be inte- grated into Thompson sampling and illustrate it with an application in online advertisement.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Sequential Learning under Probabilistic Constraints %A Amirhossein Meisami %A Henry Lam %A Chen Dong %A Abhishek Pani %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-meisami18a %I PMLR %P 620--630 %U https://proceedings.mlr.press/r16/meisami18a.html %V R16 %X We provide the first study on online learn- ing 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 decisions probabilistically satisfy some given safety conditions. The distribu- tions that govern these conditions are learned through the collected observations. Under a Bayesian framework, we introduce a scheme that provides statistical feasibility guarantees through the time horizon, by using posterior Monte Carlo samples to form sampled con- straints which leverage the scenario generation approach in chance-constrained programming. We demonstrate how our scheme can be inte- grated into Thompson sampling and illustrate it with an application in online advertisement. %Z Reissued by PMLR on 04 October 2026.
APA
Meisami, A., Lam, H., Dong, C. & Pani, A.. (2018). Sequential Learning under Probabilistic Constraints. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:620-630 Available from https://proceedings.mlr.press/r16/meisami18a.html. Reissued by PMLR on 04 October 2026.

Related Material