Multi-armed bandits – on range searching and on slowly-varying non-stationarity

Include bibliographical referrences and index

MTech (Res); 2022; Computer science and automation

Multi-Armed Bandits (MAB) is a popular framework for modelling sequential decision-making problems under uncertainty. This thesis is a compilation of two independent works on MABs. 1. In the first work, we study a multi-armed bandit (MAB) version of the range-searching problem. In its basic form, range searching considers as input a set of points (on the real line) and a collection of (real) intervals. Here, with each specified point, we have an associated weight, and the problem objective is to find a maximum-weight point within every given interval. The current work addresses range searching with stochastic weights: each point corresponds to an arm (that admits sample access), and the point’s weight is the (unknown) mean of the underlying distribution. In this MAB setup, we develop sample-efficient algorithms that find, with high probability, near-optimal arms within the given intervals, i.e., we obtain PAC (probably approximately correct) guarantees. We also provide an algorithm for a generalization wherein the weight of each point is a multi-dimensional vector.