In this paper, we consider a multi-armed bandit (MAB) instance and study how to identify the best arm when arm commands are conveyed from a central learner to a distributed agent over a discrete memoryless channel (DMC). Depending on the agent capabilities, we provide communication schemes along with their analysis, which interestingly relate to the zero-error capacity of the underlying DMC.

We study a distributed multi-armed bandit (MAB) problem over arm erasure channels, motivated by the increasing adoption of MAB algorithms over communication-constrained networks. In this setup, the learner communicates the chosen arm to play to an agent over an erasure channel with probability$\epsilon \in[0,1)$; if an erasure occurs, the agent continues pulling the last successfully received arm; the learner always observes the reward of the arm pulled. In past work, we considered the case where the agent cannot convey feedback to the learner, and thus the learner does not know whether the arm played is the requested or the last successfully received one. In this paper, we instead consider the case where the agent can send feedback to the learner on whether the arm request was received, and thus the learner exactly knows which arm was played. Surprisingly, we prove that erasure feedback does not improve the worst-case regret upper bound order over the previously studied no-feedback setting. In particular, we prove a regret lower bound of$\Omega(\sqrt{K T}+K /(1-\epsilon))$, where$K$is the number of arms and$T$the time horizon, that matches no-feedback lower bound exactly and upper bound (up to logarithmic factors). We note however that the availability of feedback does enable the design of simpler algorithms that may achieve better constants (albeit not better order) regret bounds; we design one such algorithm, and numerically evaluate its performance.

Quantifying the common information between continuous random sources is fundamental to various applications in machine learning and information theory. Recent work introduced the notion of common information dimension (CID) to measure this. In this paper, we propose a new notion, discrete-to-continuous common information dimension (D2CCID), which characterizes the growth rate of the common information between successively finer quantized sources. As compared to existing CID notions, the proposed notion can be easier to approximate, and is well aligned with common practice in information theory to measure information dimensions. We prove that the proposed measure coincides with existing CID measures for two Gaussian random sources.

Standard multimodal self-supervised learning (SSL) algorithms regard cross-modal synchronization as implicit supervisory labels during pretraining, thus posing high requirements on the scale and quality of multimodal samples. These constraints significantly limit the performance of sensing intelligence in IoT applications, as the heterogeneity and the non-interpretability of time-series signals result in abundant unimodal data but scarce high-quality multimodal pairs. This paper proposes InfoMAE, a cross-modal alignment framework that tackles the challenge of multimodal pair efficiency under the SSL setting by facilitating efficient cross-modal alignment of pretrained unimodal representations. InfoMAE achieves efficient cross-modal alignment with limited data pairs through a novel information theory-inspired formulation that simultaneously addresses distribution-level and instance-level alignment. Extensive experiments on two real-world IoT applications are performed to evaluate InfoMAE's pairing efficiency to bridge pretrained unimodal models into a cohesive joint multimodal model. InfoMAE enhances downstream multimodal tasks by over 60% with significantly improved multimodal pairing efficiency. It also improves unimodal task accuracy by an average of 22%.

Quantifying the common information between random variables is a fundamental problem with a long history in information theory. Traditionally, common information is measured in number of bits and thus such measures are mostly informative when the common information is finite. However, the common information between continuous variables can be infinite; in such cases, a real-valued random vectorWmay be needed to represent the common information, and to be used for instance for distributed simulation. In this paper, we propose the concept of Common Information Dimension (CID) and three variants. We compute the common information dimension for jointly Gaussian random vectors in a closed form. Moreover, we analytically prove, under two different formulations, that the growth rate of common information in the nearly infinite regime is determined by the common information dimension, for the case of two Gaussian vectors.

In this paper, we are interested in the regime where the common information between two Gaussian random vectors$(X, Y)$can be (or can approach) infinity. We ask two main questions: what is the rate of growth for common information from a finite to an infinite number of bits, as the dependency between the variables increases? and how well can we “approximately” simulate a pair of random variables$(X, Y)$with infinite common information using a finite number of shared bits? We analytically prove that the answer to both of these questions depends on the common information dimension$d(X, Y)$between$X$and$Y$, that we introduced in our recent work [1]. Our work characterizes in a closed form the asymptotic behaviors, by building a connection to singular values associated with the covariance matrix$\Sigma$of$(X, Y)$. We conclude the paper by providing numerical evaluation results that indicate fast convergence to the asymptotic regime.

In this paper, we address the stochastic contextual linear bandit problem, where a decision maker is provided a context (a random set of actions drawn from a distribution). The expected reward of each action is specified by the inner product of the action and an unknown parameter. The goal is to design an algorithm that learns to play as close as possible to the unknown optimal policy after a number of action plays. This problem is considered more challenging than the linear bandit problem, which can be viewed as a contextual bandit problem with a \emph{fixed} context. Surprisingly, in this paper, we show that the stochastic contextual problem can be solved as if it is a linear bandit problem. In particular, we establish a novel reduction framework that converts every stochastic contextual linear bandit instance to a linear bandit instance, when the context distribution is known. When the context distribution is unknown, we establish an algorithm that reduces the stochastic contextual instance to a sequence of linear bandit instances with small misspecifications and achieves nearly the same worst-case regret bound as the algorithm that solves the misspecified linear bandit instances. As a consequence, our results imply a $O(d\sqrt{T\log T})$ high-probability regret bound for contextual linear bandits, making progress in resolving an open problem in Li et al., 2019b, 2021. Our reduction framework opens up a new way to approach stochastic contextual linear bandit problems, and enables improved regret bounds in a number of instances including the batch setting, contextual bandits with misspecifications, contextual bandits with sparse unknown parameters, and contextual bandits with adversarial corruption.

We consider a novel multi-arm bandit (MAB) setup, where a learner needs to communicate the actions to distributed agents over erasure channels, while the rewards for the actions are directly available to the learner through external sensors. In our model, while the distributed agents know if an action is erased, the central learner does not (there is no feedback), and thus does not know whether the observed reward resulted from the desired action or not. We propose a scheme that can work on top of any (existing or future) MAB algorithm and make it robust to action erasures. Our scheme results in a worst-case regret over action-erasure channels that is at most a factor of $O(1/\sqrt {1 - \varepsilon } )$ away from the no-erasure worst-case regret of the underlying MAB algorithm, where ϵ is the erasure probability. We also propose a modification of the successive arm elimination algorithm and prove that its worst-case regret is $\tilde O(\sqrt {KT} + K/(1 - \varepsilon ))$, which we prove is optimal by providing a matching lower bound.

The exact common information between a set of random variables X1,…, Xnis defined as the minimum entropy of a shared random variable that allows for the exact distributive simulation of X1,…, Xn. It has been established that, in certain instances, infinite entropy is required to achieve distributive simulation, suggesting that continuous random variables may be needed in such scenarios. However, to date, there is no established metric to characterize such cases. In this paper, we propose the concept of Common Information Dimension (CID) with respect to a given class of functions ℱ, defined as the minimum dimension of a random variable W required to distributively simulate a set of random variables X1,…, Xn, such that W can be expressed as a function of X1,⋯, Xnusing a member of ℱ. Our main contributions include the computation of the common information dimension for jointly Gaussian random vectors in a closed form, with ℱ being the linear functions class.

In this paper, we provide the first efficient batched algorithm for contextual linear bandits with large action spaces. Unlike existing batched algorithms that rely on action elimination, which are not implementable for large action sets, our algorithm only uses a linear optimization oracle over the action set to design the policy. The proposed algorithm achieves a regret upper bound $\tilde{O}(\sqrt{T})$ with high probability, and uses $O(\log\log T)$ batches, matching the lower bound on the number of batches (Gao et al., 2019). When specialized to linear bandits, our algorithm can achieve a high probability gap-dependent regret bound of $\tilde{O}(1/\Delta_{\min})$ with the optimal $\log T$ number of batches, where $\Delta_{\min}$ is the minimum reward gap between a suboptimal arm and the optimal. Our result is achieved via a novel soft elimination approach, that entails $\text{``}$shaping$\text{"}$ the action sets at each batch so that we can efficiently identify (near) optimal actions.

The multi-armed bandit (MAB) problem is an active learning framework that aims to select the best among a set of actions by sequentially observing rewards. Recently, it has become popular for a number of applications over wireless networks, where communication constraints can form a bottleneck. Existing works usually fail to address this issue and can become infeasible in certain applications. In this paper we address the communication problem by optimizing the communication of rewards collected by distributed agents. By providing nearly matching upper and lower bounds, we tightly characterize the number of bits needed per reward for the learner to accurately learn without suffering additional regret. In particular, we establish a generic reward quantization algorithm, QuBan, that can be applied on top of any (no-regret) MAB algorithm to form a new communication-efficient counterpart, that requires only a few (as low as 3) bits to be sent per iteration while preserving the same regret bound. Our lower bound is established via constructing hard instances from a subgaussian distribution. Our theory is further corroborated by numerically experiments.

We consider a distributed detection problem where sensors observe dependent observations. We ask, if we can allow the sensors to locally exchange a few bits with each other, whether we can use these bits to "break" the dependency of the sensor observations, and thus reduce the dependent detection problem to the much better-studied and understood case of conditionally independent observations. To this end, we propose an optimization problem that we prove is equivalent to minimizing the dependency between the sensor observations. This problem is in general NP-hard, however, we show that for at least some cases of Gaussian distributions it can be solved efficiently. For general distributions, we propose to use alternating minimization and derive a constant factor approximation algorithm. Numerical evaluations indicate that our approach can offer significant improvement in detection accuracy over alternative schemes.

Contextual linear bandits is a rich and theoretically important model that has many practical applications. Recently, this setup gained a lot of interest in applications over wireless where communication constraints can be a performance bottleneck, especially when the contexts come from a large $d$-dimensional space. In this paper, we consider the distributed contextual linear bandit learning problem, where the agents who observe the contexts and take actions are geographically separated from the learner who performs the learning while not seeing the contexts. We assume that contexts are generated from a distribution and propose a method that uses $\approx 5d$ bits per context for the case of unknown context distribution and $0$ bits per context if the context distribution is known, while achieving nearly the same regret bound as if the contexts were directly observable. The former bound improves upon existing bounds by a $\log(T)$ factor, where $T$ is the length of the horizon, while the latter achieves information theoretical tightness.

This paper considers benefits of coding techniques in recommendation systems operating over wireless channels with erasures. We identify scenarios where coded broadcasting can increase the overall user satisfaction at a fixed channel utilization level. Such opportunities arise both when user preferences are unknown, and must be explored, and when they are known and must be exploited to recommend optimally. We determine the magnitude of the potential gains and show that coding is most beneficial if users have heterogeneous preferences. Finally, we provide inequalities that can be evaluated to determine whether coding would be beneficial for a certain reward structure.

The ability of physical layer relay caching to increase the degrees of freedom (DoF) of a single cell was recently illustrated. In this paper, we extend this result to the case of multiple cells in which a caching relay is shared among multiple non-cooperative base stations (BSs). In particular, we show that a large DoF gain can be achieved by exploiting the benefits of having a shared relay that cooperates with the BSs. We first propose a cache-assisted relaying protocol that improves the cooperation opportunity between the BSs and the relay. Next, we consider the cache content placement problem that aims to design the cache content at the relay such that the DoF gain is maximized. We propose an optimal algorithm and a near-optimal low-complexity algorithm for the cache content placement problem. Simulation results show significant improvement in the DoF gain using the proposed relay-caching protocol.