Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection

Contextual bandit problems receive significant attention over the past years in different communities, such as statistics, operations research, and computer science. This class of problems studies how to make optimal sequential decisions with new information in different settings, where we aim to maximize our accumulative reward, and we iteratively improve our policy given newly observed results. It finds many important modern applications such as personalized recommendation [Li et al., 2010, 2011], online advertising [Krause and Ong, 2011], cost-sensitive classification [Agarwal et al., 2014], and personalized medicine [Goldenshluger and Zeevi, 2013, Bastani and Bayati, 2015, Keyvanshokooh et al., 2019]. In most contextual bandit problems, at each iteration, we first obtain some new information. Then, we take action based on a certain policy and observe a new reward. Our goal is to maximize the total reward, where we iteratively improve our policy. This paper is concerned with the linear stochastic bandit model, one of the most fundamental models in contextual bandit problems. We model the expected reward at each time period as a linear function of some random information depending on our action. This model receives considerable attention [Auer, 2002, Abe et al., 2003, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010, Chu et al., 2011], and as we will discuss in more detail, it naturally finds applications in optimal sequential treatment regimes.