2022/06/06 by Mitra, Aritra, Adibi, Arman, Pappas, George J. +1
#FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2206.02834
We consider a linear stochastic bandit problem involving M agents that can collaborate via a central server to minimize regret. A fraction α of these agents are adversarial and can act arbitrarily, leading to the following tension: while collaboration can potentially reduce regret, it can also disrupt the process of learning due to adversaries. In this work, we provide a fundamental understanding of this tension by designing new algorithms that balance the exploration-exploitation trade-off via carefully constructed robust confidence intervals. We also complement our algorithms with tight analyses. First, we develop a robust collaborative phased elimination algorithm that achieves O(α+ 1/√(M)) √(dT) regret for each good agent; here, d is the model-dimension and T is the horizon. For small α, our result thus reveals a clear benefit of collaboration despite adversaries. Using an information-theoretic argument, we then prove a matching lower bound, thereby providing the first set of tight, near-optimal regret bounds for collaborative linear bandits with adversaries. Furthermore, by leveraging recent advances in high-dimensional robust statistics, we significantly extend our algorithmic ideas and results to (i) the generalized linear bandit model that allows for non-linear observation maps; and (ii) the contextual bandit setting that allows for time-varying feature vectors.