Multi-Armed Bandit for Species Discovery: A Bayesian Nonparametric Approach

ABSTRACT

Let (P₁, …, P_J) denote J populations of animals from distinct regions. A priori, it is unknown which species are present in each region and what are their corresponding frequencies. Species are shared among populations and each species can be present in more than one region with its frequency varying across populations. In this article, we consider the problem of sequentially sampling these populations to observe the greatest number of different species. We adopt a Bayesian nonparametric approach and endow (P₁, …, P_J) with a hierarchical Pitman–Yor process prior. As a consequence of the hierarchical structure, the J unknown discrete probability measures share the same support, that of their common random base measure. Given this prior choice, we propose a sequential rule that, at every time step, given the information available up to that point, selects the population from which to collect the next observation. Rather than picking the population with the highest posterior estimate of producing a new value, the proposed rule includes a Thompson sampling step to better balance the exploration–exploitation trade-off. We also propose an extension of the algorithm to deal with incidence data, where multiple observations are collected in a time period. The performance of the proposed algorithms is assessed through a simulation study and compared to three other strategies. Finally, we compare these algorithms using a dataset of species of trees, collected from different plots in South America. Supplementary materials for this article are available online.

KEYWORDS:

• Bayesian nonparametric statistic
• Discovery probability
• Hierarchical Pitman–Yor process
• Multi-armed bandit
• Species sampling models
• Thompson sampling

Supplementary Material

Supplementary materials contain proofs of Proposition 1 and Proposition 2, details on the MCMC algorithm for the HPY hyperparameters, and additional numerical results.

Acknowledgments

The authors thank the associate editor and two anonymous referees, whose comments and suggestions helped to improve the article substantially. Special thanks to Sergio Bacallado, Levi Boyles and Lorenzo Trippa for useful discussions, and to Alberto Galvan and Boyu Ren for support in the computational parts of this work.

Additional information

Funding

Stefano Favaro is supported by the European Research Council (ERC) through StG N-BNP 306406. Yee Whye Teh research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 617071.