Multi-Agent Best Arm Identification in Stochastic Linear Bandits

The multi-armed bandit problem (MAB) is a classic framework in sequential decision making, capturing the exploration-exploitation trade off faced in many real-world domains, for example, recommendation systems [Gentile et al., 2014, Li et al., 2010, Li et al., 2016], clinical trials [Durand et al., 2018, Wang, 1991], online advertising [Tao et al., 2018], adaptive routing [Awerbuch and Kleinberg, 2008] and so on. An instance of MAB problem consists of a set of possible choices called arms. The learning agent sequentially chooses an arm and receives a reward related to the chosen arm. The goal of the agent is to either maximize the cumulative reward (equivalently, minimize the regret) over the time, referred as regret minimization problem [Bubeck et al., 2012, Cesa-Bianchi et al., 2013, Lattimore and Szepesvári, 2020] or, to identify the best arm within a specified constraint. The latter variant is known as the best-arm identification or pure exploration problem, which is studied in two different settings based on the specific constraint: (1) fixed-budget [Audibert and Bubeck, 2010, Bubeck et al., 2009, Karnin et al., 2013] and (2) fixed-confidence [Chen et al., 2017, Garivier and Kaufmann, 2016, Mannor and Tsitsiklis, 2004]. While the fixed-budget setting aims to identify the best arm with smallest error probability within the allocated time budget, the goal in fixed-confidence setup is to identify the best arm with the given confidence level using minimum arm pulls. In this paper, we study fixed-budget best-arm identification in stochastic linear bandit (SLB) [Auer, 2002, Abbasi-Yadkori et al., 2011].