Asymptotic Optimality for Decentralised Bandits
We consider a large number of agents collaborating on a multi-armed bandit problem with a large number of arms. The goal is to minimise the regret of each agent in a communication-constrained setting. We present a decentralised algorithm which builds upon and improves the Gossip-Insert-Eliminate method of Chawla et al. arxiv:2001.05452. We provide a theoretical analysis of the regret incurred which shows that our algorithm is asymptotically optimal. In fact, our regret guarantee matches the asymptotically optimal rate achievable in the full communication setting. Finally, we present empirical results which support our conclusions
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Gamification of Pure Exploration for Linear Bandits
We investigate an active pure-exploration setting, that includes best-arm identification, in the context of linear stochastic bandits. While asymptotically optimal algorithms exist for standard multi-arm bandits, the exi…
Experimental DesignAchieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
We study the problem of $K$-armed bandits with reward distributions belonging to a one-parameter exponential distribution family. In the literature, several criteria have been proposed to evaluate the performance of such…
Multi-Armed BanditsThompson SamplingOptimal Batched Linear Bandits
We introduce the E$^4$ algorithm for the batched linear bandit problem, incorporating an Explore-Estimate-Eliminate-Exploit framework. With a proper choice of exploration rate, we prove E$^4$ achieves the finite-time min…
Computational EfficiencyMulti-Armed BanditsAchieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption
We consider the infinite-horizon average-reward restless bandit problem. We propose a novel \emph{two-set policy} that maintains two dynamic subsets of arms: one subset of arms has a nearly optimal state distribution and…
Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
We study stochastic structured bandits for minimizing regret. The fact that the popular optimistic algorithms do not achieve the asymptotic instance-dependent regret optimality (asymptotic optimality for short) has recen…