2023/10/27 by Artin Tajdini, Lalit Jain, Tajdini, Artin +3 · 1 citation
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Distributed Sensor Networks and Detection Algorithms
paper · pdf · doi:10.48550/arxiv.2310.18465
We consider maximizing an unknown monotonic, submodular set function f: 2[n] → [0,1] with cardinality constraint under stochastic bandit feedback. At each time t=1,…,T the learner chooses a set St ⊂ [n] with |St| ≤ k and receives reward f(St) + ηt where ηt is mean-zero sub-Gaussian noise. The objective is to minimize the learner's regret with respect to an approximation of the maximum f(S_*) with |S_*| = k, obtained through robust greedy maximization of f. To date, the best regret bound in the literature scales as k n1/3 T2/3. And by trivially treating every set as a unique arm one deduces that √ n \choose k T is also achievable using standard multi-armed bandit algorithms. In this work, we establish the first minimax lower bound for this setting that scales like Ω(minL ≤ k(L1/3n1/3T2/3 + √n \choose k - LT)). For a slightly restricted algorithm class, we prove a stronger regret lower bound of Ω(minL ≤ k(Ln1/3T2/3 + √n \choose k - LT)). Moreover, we propose an algorithm Sub-UCB that achieves regret O(minL ≤ k(Ln1/3T2/3 + √n \choose k - LT)) capable of matching the lower bound on regret for the restricted class up to logarithmic factors.