Optimal Algorithms for Range Searching over Multi-Armed Bandits
This paper studies 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. The sample complexities of our algorithms depend, in particular, on the size of the optimal hitting set of the given intervals. Finally, we establish lower bounds proving that the obtained sample complexities are essentially tight. Our results highlight the significance of geometric constructs -- specifically, hitting sets -- in our MAB setting.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Learning-Based Algorithms for Graph Searching Problems
We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ to find a…
Hierarchical Genetic Algorithms with evolving objective functions
We propose a framework of genetic algorithms which use multi-level hierarchies to solve an optimization problem by searching over the space of simpler objective functions. We solve a variant of Travelling Salesman Proble…
regressionHyperparameter Optimization for Tracking With Continuous Deep Q-Learning
Hyperparameters are numerical presets whose values are assigned prior to the commencement of the learning process. Selecting appropriate hyperparameters is critical for the accuracy of tracking algorithms, yet it is diff…
Hyperparameter OptimizationObject TrackingQ-LearningRadar Enhanced Multi-Armed Bandit for Rapid Beam Selection in Millimeter Wave Communications
Multi-arm bandit (MAB) algorithms have been used to learn optimal beams for millimeter wave communication systems. Here, the complexity of learning the optimal beam linearly scales with the number of beams, leading to hi…
Autonomous skill discovery with Quality-Diversity and Unsupervised Descriptors
Quality-Diversity optimization is a new family of optimization algorithms that, instead of searching for a single optimal solution to solving a task, searches for a large collection of solutions that all solve the task i…
Dimensionality ReductionDiversity