Computational Geometry Meets Multi-Armed Bandits

Computational geometry deals with the design and analysis of algorithms for problems which are geometric in nature. Unlike the traditional computational geometry problems where the weight and the location of points are fixed and known a-priori, in many applications some of the parameters are stochastic (think of uncertainty in GPS locations) and unknown (the quality of a worker/restau-rant).

This motivates the study of problems at the intersection of computational geometry and multi-armed bandits. An important distinction in these problems is the focus on optimising the number of samples (and not the typical measure of optimising the running time). In our work, we study the problem of answering range queries over multi-dimensional stochastic data.

In its simplest form, the input is a set of points on the real line and a collection of intervals. Each point is associated with a random variable and the weight of the points corresponds to the mean of the random variable. The goal is to find the optimal point (a.k.a. arm) within each interval.

Link: https://arxiv.org/abs/2105.01390

Reference 

Siddharth Barman, Ramakrishnan Krishnamurthy, Saladi Rahul, “Optimal Algorithms for Range Searching over Multi-Armed Bandits.” 30th International Joint Conference on Artificial Intelligence (IJCAI-21).