No-regret Algorithms for Capturing Events in Poisson Point Processes

Mojmir Mutny, Andreas Krause
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7894-7904, 2021.

Abstract

Inhomogeneous Poisson point processes are widely used models of event occurrences. We address \emph{adaptive sensing of Poisson Point processes}, namely, maximizing the number of captured events subject to sensing costs. We encode prior assumptions on the rate function by modeling it as a member of a known \emph{reproducing kernel Hilbert space} (RKHS). By partitioning the domain into separate small regions, and using heteroscedastic linear regression, we propose a tractable estimator of Poisson process rates for two feedback models: \emph{count-record}, where exact locations of events are observed, and \emph{histogram} feedback, where only counts of events are observed. We derive provably accurate anytime confidence estimates for our estimators for sequentially acquired Poisson count data. Using these, we formulate algorithms based on optimism that provably incur sublinear count-regret. We demonstrate the practicality of the method on problems from crime modeling, revenue maximization as well as environmental monitoring.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-mutny21a, title = {No-regret Algorithms for Capturing Events in Poisson Point Processes}, author = {Mutny, Mojmir and Krause, Andreas}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7894--7904}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/mutny21a/mutny21a.pdf}, url = {https://proceedings.mlr.press/v139/mutny21a.html}, abstract = {Inhomogeneous Poisson point processes are widely used models of event occurrences. We address \emph{adaptive sensing of Poisson Point processes}, namely, maximizing the number of captured events subject to sensing costs. We encode prior assumptions on the rate function by modeling it as a member of a known \emph{reproducing kernel Hilbert space} (RKHS). By partitioning the domain into separate small regions, and using heteroscedastic linear regression, we propose a tractable estimator of Poisson process rates for two feedback models: \emph{count-record}, where exact locations of events are observed, and \emph{histogram} feedback, where only counts of events are observed. We derive provably accurate anytime confidence estimates for our estimators for sequentially acquired Poisson count data. Using these, we formulate algorithms based on optimism that provably incur sublinear count-regret. We demonstrate the practicality of the method on problems from crime modeling, revenue maximization as well as environmental monitoring.} }
Endnote
%0 Conference Paper %T No-regret Algorithms for Capturing Events in Poisson Point Processes %A Mojmir Mutny %A Andreas Krause %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-mutny21a %I PMLR %P 7894--7904 %U https://proceedings.mlr.press/v139/mutny21a.html %V 139 %X Inhomogeneous Poisson point processes are widely used models of event occurrences. We address \emph{adaptive sensing of Poisson Point processes}, namely, maximizing the number of captured events subject to sensing costs. We encode prior assumptions on the rate function by modeling it as a member of a known \emph{reproducing kernel Hilbert space} (RKHS). By partitioning the domain into separate small regions, and using heteroscedastic linear regression, we propose a tractable estimator of Poisson process rates for two feedback models: \emph{count-record}, where exact locations of events are observed, and \emph{histogram} feedback, where only counts of events are observed. We derive provably accurate anytime confidence estimates for our estimators for sequentially acquired Poisson count data. Using these, we formulate algorithms based on optimism that provably incur sublinear count-regret. We demonstrate the practicality of the method on problems from crime modeling, revenue maximization as well as environmental monitoring.
APA
Mutny, M. & Krause, A.. (2021). No-regret Algorithms for Capturing Events in Poisson Point Processes. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7894-7904 Available from https://proceedings.mlr.press/v139/mutny21a.html.

Related Material