We study the Bandit Clustering (BC) problem under the fixed confidence setting, where the objective is to group a collection of data sequences (arms) into clusters through sequential sampling from adaptively selected arms at each time step while ensuring a fixed error probability at the stopping time. We consider a setting where arms in a cluster may have different distributions. Unlike existing results in this setting, which assume Gaussian-distributed arms, we study a broader class of vector-parametric distributions that satisfy mild regularity conditions. Existing asymptotically optimal BC algorithms require solving an optimization problem as part of their sampling rule at each step, which is computationally costly. We propose an Efficient Bandit Clustering algorithm (EBC), which, instead of solving the full optimization problem, takes a single step toward the optimal value at each time step, making it computationally efficient while remaining asymptotically optimal. We also propose a heuristic variant of EBC, called EBC-H, which further simplifies the sampling rule, with arm selection based on quantities computed as part of the stopping rule. We highlight the computational efficiency of EBC and EBC-H by comparing their per-sample run time with that of existing algorithms. The asymptotic optimality of EBC is supported through simulations on the synthetic datasets. Through simulations on both synthetic and real-world datasets, we show the performance gain of EBC and EBC-H over existing approaches.

We consider the problem of person-in-bed detection using accelerometer measurements in the segmented as well as streaming setting. For the segmented problem, we identify frequency domain features (4 features for each acceleration coordinate) that can be used to model the in-bed and not-in-bed hypotheses. We estimate the model parameters from the training data and apply the Generalized Likelihood Ratio (GLR) test. Using the same form as the GLR test statistic, we also propose an improvement using quadratic logistic regression. For the streaming problem, we model it as a sequential change detection problem using the models that we obtained for the in-bed and not-in-bed hypotheses and propose a GLRT-based Cumulative Sum (CuSum) algorithm.

In this paper, we address the problem of best arm identification (BAI) with arm erasures in a multi-armed bandit setting with finitely many arms. A learner who seeks to identify the best arm-the arm with the largest mean reward-samples arms sequentially, one at each time instant, and communicates the sampled arm to an agent through an erasure channel with a known erasure probability$\epsilon\in(0,1)$• The learner does not receive any erasure feedback, and hence does not know whether the transmitted arm was erased by the channel. In instances where erasure does not occur, and the transmitted arm is successfully received by the agent, the agent promptly pulls the received arm. On the contrary, when erasure occurs, we analyse the following two distinct scenarios: (a) the agent randomly selects an arm, and (b) the agent selects the most recent successfully received arm. We assume that the instantaneous reward from the pulled arm is available to the learner, whose objective is to find the best arm as quickly as possible, subject to an upper bound on the error probability. Given$\delta\in(0,1)$, we derive a problem-dependent lower bound on the expected stopping time of any algorithm whose error probability is within$\delta$. We also propose two successive elimination algorithms for each of the aforementioned scenarios (a), (b), and provide upper bounds on their stopping times that hold with probability$1-\delta$• To our best knowledge, this is the first work on BAI with arm erasures.

We study the well-known coded caching problem in an online learning framework, wherein requests arrive sequentially, and an online policy can update the cache contents based on the history of requests seen thus far. We introduce a caching policy based on the Follow-The-Perturbed-Leader principle and show that for any time horizon$\mathcal{T}$and any request sequence, it achieves a sub-linear regret of$\mathcal{O}(\sqrt{T})$with respect to an oracle that knows the request sequence beforehand. Our study marks the first examination of adversarial regret in the coded caching setup. Furthermore, we also address the issue of switching cost by establishing an upper bound on the expected number of cache updates made by our algorithm under unrestricted switching and also provide an upper bound on the regret under restricted switching when cache updates can only happen in a pre-specified subset of timeslots. Finally, we validate our theoretical insights with numerical results using a real-world dataset.

We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients. Each client is associated with a multi-armed bandit in which each arm yields i.i.d. rewards following a Gaussian distribution with an unknown mean and known variance. The set of arms is assumed to be the same at all the clients. We define two notions of best arm local and global. The local best arm at a client is the arm with the largest mean among the arms local to the client, whereas the global best arm is the arm with the largest average mean across all the clients. We assume that each client can only observe the rewards from its local arms and thereby estimate its local best arm. The clients communicate with a central server on uplinks that entail a cost of C>=0 units per usage per uplink. The global best arm is estimated at the server. The goal is to identify the local best arms and the global best arm with minimal total cost, defined as the sum of the total number of arm selections at all the clients and the total communication cost, subject to an upper bound on the error probability. We propose a novel algorithm FedElim that is based on successive elimination and communicates only in exponential time steps and obtain a high probability instance-dependent upper bound on its total cost. The key takeaway from our paper is that for any C>=0 and error probabilities sufficiently small, the total number of arm selections (resp. the total cost) under FedElim is at most 2 (resp. 3) times the maximum total number of arm selections under its variant that communicates in every time step. Additionally, we show that the latter is optimal in expectation up to a constant factor, thereby demonstrating that communication is almost cost-free in FedElim. We numerically validate the efficacy of FedElim on two synthetic datasets and the MovieLens dataset.

We consider the multi-access coded caching problem, which contains a central server with N files, K caches with M units of memory each and K users where each one is connected to L(≥ 1) consecutive caches, with a cyclic wrap-around. Caches are populated with content related to the files and each user then requests a file that has to be served via a broadcast message from the central server with the help of the caches. We aim to design placement and delivery policies for this setup that minimize the central servers’ transmission rate while satisfying an additional linear sub-packetization constraint. We propose policies that satisfy this constraint and derive upper bounds on the achieved server transmission rate, which upon comparison with the literature establish the improvement provided by our results. To derive our results, we map the multi-access coded caching problem to variants of the well-known index coding problem. In this process, we also derive new bounds on the optimal transmission size for a ‘structured’ index coding problem, which might be of independent interest.

We study best arm identification in a variant of the multi-armed bandit problem where the learner has limited precision in arm selection. The learner can only sample arms via certain exploration bundles, which we refer to as boxes. In particular, at each sampling epoch, the learner selects a box, which in turn causes an arm to get pulled as per a box-specific probability distribution. The pulled arm and its instantaneous reward are revealed to the learner, whose goal is to find the best arm by minimising the expected stopping time, subject to an upper bound on the error probability. We present an asymptotic lower bound on the expected stopping time, which holds as the error probability vanishes. We show that the optimal allocation suggested by the lower bound is, in general, non-unique and therefore challenging to track. We propose a modified tracking-based algorithm to handle non-unique optimal allocations, and demonstrate that it is asymptotically optimal. We also present non-asymptotic lower and upper bounds on the stopping time in the simpler setting when the arms accessible from one box do not overlap with those of others.

We study the problem of identifying the best arm in a multi-armed bandit environment when each arm is a time-homogeneous and ergodic discrete-time Markov process on a common, finite state space. The state evolution on each arm is governed by the arm’s transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. The decision entity selects one arm at a time sequentially, and all the unselected arms continue to undergo state evolution (restless arms). For this problem, we derive the first-known problem instance-dependent asymptotic lower bound on the growth rate of the expected time required to find the index of the best arm, where the asymptotics is as the error probability vanishes. Further, we propose a sequential policy that, for an input parameter$R$, forcibly selects an arm that has not been selected for$R$consecutive time instants. We show that this policy achieves an upper bound that depends on$R$and is monotonically non-increasing as$R\to \infty $. The question of whether, in general, the limiting value of the upper bound as$R\to \infty $matches with the lower bound, remains open. We identify a special case in which the upper and the lower bounds match. Prior works on best arm identification have dealt with (a) independent and identically distributed observations from the arms, and (b) rested Markov arms, whereas our work deals with the more difficult setting of restless Markov arms.

We study the problem of best arm identification in multi-armed bandits when each arm is an ergodic Markov process that evolves whether or not the arm is selected (restless arms). The evolution of each arm’s Markov process is governed by its transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. We derive an asymptotic lower bound on the expected time required to find the best arm, where the asymptotics is as the error probability vanishes. Also, we design a policy that, for an input parameter R, forcibly selects an arm that has not been selected for R consecutive time instants, and achieves an upper bound that is monotonically non-increasing in R. Showing that, in general, the lower bound and the limiting value of the upper bounds as R→∞ match, appears to be difficult and remains open. These bounds are, however, shown to match in the special case when the TPM of each arm has identical rows, i.e., the arms yield independent and identically distributed observations.

An Index Coding Problem (ICP) has a central server that possesses files and is connected to multiple users through a shared link. Each user demands a subset of files and possesses another subset of files as side-information. The files which are neither demanded nor possessed as side-information by a user are called its interference files. In a symmetric ICP, the relative positions of side-information and interference files are the same for all the users. In this paper, a general representation for symmetric ICPs is proposed, and using this representation, we give bounds on the optimal transmission rate for a general symmetric ICP. We identify two broad categories of symmetric ICPs: Neighboring Interference ICP (NI-ICP) and Neighboring Side-information ICP (NS-ICP). For a particular class of NI-ICP, we find the optimal transmission rate, and for another class, an order-optimal transmission rate is derived. An upper bound on the optimal transmission rate is established for NS-ICP. Furthermore, for a particular class of NS-ICP, a lower bound for the optimal transmission rate is also derived.

We consider the problem of identifying the subset$S$γPof elements in the support of an underlying distribution$P$whose probability value is larger than a given threshold γ, by actively querying an oracle to gain information about a sequence$X$1,$X$2, … of i.i.d. samples drawn from P. We consider two query models: (a) each query is an index$i$and the oracle return the value Xiand (b) each query is a pair of indices (i, j) and the oracle gives a binary answer confirming if Xi= Xjor not. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire history of responses, or decide to stop and output an estimate of$S$γP, which is required to be correct with some prespecified large probability. We provide upper bounds on the query complexity of the algorithms for any distribution$\mathcal{P}$and also derive lower bounds on the optimal query complexity under the two query models. We also consider noisy versions of the two query models and propose robust estimators which can effectively counter the noise in the oracle responses. A full version of this paper is accessible at: https://arxiv.org/pdf/2005.14425.pdf

Index coding and coded caching are two active research topics in information theory with strong ties to each other. Motivated by the multi-access coded caching problem, we study a new class of structured index coding problems (ICPs) which are formed by the union of several symmetric ICPs. We derive upper and lower bounds on the optimal server transmission rate for this class of ICPs and demonstrate that they differ by at most a factor of two. Finally, we apply these results to the multi-access coded caching problem to derive better bounds than the state of the art.

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of N files, K caches with limited memory M, and K users such that each user has access to L consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size R over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was studied previously by Hachem et al., where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree L and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory tradeoff R*(M) over all uncoded placement policies. In particular, we derive a new achievable rate for any L ≥ 1 and a new lower bound, which works for any uncoded placement policy and L ≥ K/2. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most 2 independent of all parameters, thus establishing an order-optimal characterization of R*(M) for any L ≥ K/2. This is a significant improvement over the previously known gap result, albeit under the restriction of uncoded placement policies. Finally, we also characterize R*(M) exactly for a few special cases.

Content delivery networks are a key infrastructure component used by Video on Demand (VoD) services to deliver content over the Internet. We study a content delivery system consisting of a central server and multiple co-located caches, each with limited storage and service capabilities. This work evaluates the performance of such a system as a function of the storage capacity of the caches, the content replication strategy, and the service policy. This analysis can be used for a system-level optimization of these design choices. The focus of this work is on understanding the benefits of allowing caches to pool their resources to serve user requests. We show that the benefits of resource pooling depend on the popularity profile of the contents offered by the VoD service. More specifically, if the popularity does not vary drastically across contents, then resource pooling leads to an order wise reduction in central server transmission rate as the system size grows. On the other hand, if the content popularity is skewed, the central server transmission rate is of the same order with and without resource pooling.

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of N files, K caches with limited memory M, and K users such that each user has access to L consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size R over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was proposed in [1] where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree L and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory trade-off R*(M) over all uncoded placement policies. In particular, we derive a new achievable rate for any L ≥ 1 and a new lower bound, which works for any uncoded placement policy and L ≥ K/2. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most 2 independent of all parameters, thus establishing an order-optimal characterization of R*(M) for any L ≥ K/2. This is in significant improvement over the gap result in [1], albeit under the restriction of uncoded placement policies. Finally, we also characterize R*(M) exactly for a few special cases.

In this work, we focus on distributed cache systems with non-uniform storage capacity across caches. We compare the performance of our system with the performance of a system with the same cumulative storage distributed evenly across the caches. We characterize the extent to which the performance of the distributed cache system deteriorates due to storage heterogeneity. The key takeaway from this work is that the effects of heterogeneity in the storage capabilities depend heavily on the popularity profile of the contents being cached and delivered. We analytically show that compared to the case where contents popularity is comparable across contents, lopsided popularity profiles are more tolerant to heterogeneity in storage capabilities. We validate our theoretical results via simulations.