Consider N devices that transmit packets for T time slots, where device n uses transmission power$P_{n}\left ({{t}}\right)$at time slot t. Independently at each time slot, a packet arrives at device n with probability$\lambda _{n}$. The probability of successfully transmitting a packet$\mu _{n}\left ({{\boldsymbol {P}}}\right)$is a function of the transmission powers of all devices$\boldsymbol {P}$and the channel gains$\left \{{{ g_{m,n}}}\right \} $between them. This function is unknown to the devices that only observe binary reward$r_{n}\left ({{\boldsymbol {P}}}\right)$of whether the transmission was successful (ACK/NACK). All packets of device n that were not successfully transmitted yet at time slot t wait in a queue$Q_{n}\left ({{t}}\right)$. The centralized max-weight scheduling (MWS) can stabilize the queues for any feasible$\boldsymbol {\lambda }$(i.e., throughput optimality). However, MWS for power control is intractable even as a centralized algorithm, let alone in a distributed network. We design a distributed yet asymptotically throughput optimal power control for the wireless interference channel, which has long been recognized as a major challenge. Our main observation is that the interference$I_{n}\left ({{t}}\right)=\sum g_{m,n}^{2}P_{m}\left ({{t}}\right)$can be leveraged to evaluate the weighted throughput if we add a short pilot signal with power$P_{m}\propto Q_{m}\left ({{t}}\right)r_{m}\left ({{\boldsymbol {P}}}\right)$after transmitting the data. Our algorithm requires no explicit communication between the devices and learns to approximate MWS, overcoming its intractable optimization and the unknown throughput functions. We prove that, for large T, our algorithm can achieve any feasible$\boldsymbol {\lambda }$. Numerical experiments show that our algorithm outperforms the state-of-the-art distributed power control, exhibiting better performance than our theoretical bounds.

Identifying disease carriers is a key barrier to effectively control an epidemic outbreak, especially when many carriers are asymptomatic, have minor symptoms, or have a delayed symptom onset. Current isolation policies largely operate at the two ends of the spectrum: isolate almost everyone (lock-down) or isolate only those with severe symptoms. This leads to high misclassification costs. To address this issue, we develop an active learning approach. Active learning is useful when labeling is expensive and there is a limited budget; an active learning algorithm selects which data points to label in order to build the best training dataset for machine learning. We present the novel Active Testing protocol to combine 1) an online, disease-carrier classification model trained on symptom data paired with 2) an active learning based disease testing policy, that results in lower misclassification costs than either of the two extreme isolation policies. Coupling these two components enables our protocol to pick the best testing kit allocation policy to train the carrier classification model and minimize the total decision-theoretic, isolation misclassification cost. We accomplish this with a novel, cost-aware active learning algorithm, and demonstrate its effectiveness compared to existing algorithms in the class-imbalanced setting of disease-carrier classification.

Abstract Consider $N$ cooperative agents such that for $T$ turns, each agent n takes an action $a_{n}$ and receives a stochastic reward $r_{n}\left(a_{1},\ldots,a_{N}\right)$. Agents cannot observe the actions of other agents and do not know even their own reward function. The agents can communicate with their neighbors on a connected graph $G$ with diameter $d\left(G\right)$. We want each agent $n$ to achieve an expected average reward of at least $\lambda_{n}$ over time, for a given quality of service (QoS) vector $\boldsymbol{\lambda}$. A QoS vector $\boldsymbol{\lambda}$ is not necessarily achievable. By giving up on immediate reward, knowing that the other agents will compensate later, agents can improve their achievable capacity region. Our main observation is that the gap between $\lambda_{n}t$ and the accumulated reward of agent $n$, which we call the QoS regret, behaves like a queue. Inspired by this observation, we propose a distributed algorithm that aims to learn a max-weight matching of agents to actions. In each epoch, the algorithm employs a consensus phase where the agents agree on a certain weighted sum of rewards by communicating only $O\left(d\left(G\right)\right)$ numbers every turn. Then, the algorithm uses distributed successive elimination on a random subset of action profiles to approximately maximize this weighted sum of rewards. We prove a bound on the accumulated sum of expected QoS regrets of all agents, that holds if $\boldsymbol{\lambda}$ is a safety margin $\varepsilon_{T}$ away from the boundary of the capacity region, where $\varepsilon_{T}\rightarrow0$ as $T\rightarrow\infty$. This bound implies that, for large $T$, our algorithm can achieve any $\boldsymbol{\lambda}$ in the interior of the dynamic capacity region, while all agents are guaranteed an empirical average expected QoS regret of $\tilde{O}\left(1\right)$ over $t=1,\ldots,T$ which never exceeds $\tilde{O}\left(\sqrt{t}\right)$ for any $t$. We then extend our result to time-varying i.i.d. communication graphs.

Consider a scenario where a player chooses an action in each round $t$ out of $T$ rounds and observes the incurred cost after a delay of $d_{t}$ rounds. The cost functions and the delay sequence are chosen by an adversary. We show that in a non-cooperative game, the expected weighted ergodic distribution of play converges to the set of coarse correlated equilibria if players use algorithms that have “no weighted-regret” in the above scenario, even if they have linear regret due to too large delays. For a two-player zero-sum game, we show that no weighted-regret is sufficient for the weighted ergodic average of play to converge to the set of Nash equilibria. We prove that the FKM algorithm with $n$ dimensions achieves an expected regret of $O\left(nT^{\frac{3}{4}}+\sqrt{n}T^{\frac{1}{3}}D^{\frac{1}{3}}\right)$ and the EXP3 algorithm with $K$ arms achieves an expected regret of $O\left(\sqrt{\log K\left(KT+D\right)}\right)$ even when $D=\sum_{t=1}^{T}d_{t}$ and $T$ are unknown. These bounds use a novel doubling trick that, under mild assumptions, provably retains the regret bound for when $D$ and $T$ are known. Using these bounds, we show that FKM and EXP3 have no weighted-regret even for $d_{t}=O\left(t\log t\right)$. Therefore, algorithms with no weighted-regret can be used to approximate a CCE of a finite or convex unknown game that can only be simulated with bandit feedback, even if the simulation involves significant delays.

Consider N players that each uses a mixture of K resources. Each of the players’ reward functions includes a linear pricing term for each resource that is controlled by the game manager. We assume that the game is strongly monotone, so if each player runs gradient descent, the dynamics converge to a unique Nash equilibrium (NE). Unfortunately, this NE can be inefficient since the total load on a given resource can be very high. In principle, we can control the total loads by tuning the coefficients of the pricing terms. However, finding pricing coefficients that balance the loads requires knowing the players’ reward functions and their action sets. Obtaining this game structure information is infeasible in a large-scale network and violates the users’ privacy. To overcome this, we propose a simple algorithm that learns to shift the NE of the game to meet the total load constraints by adjusting the pricing coefficients in an online manner. Our algorithm only requires the total load per resource as feedback and does not need to know the reward functions or the action sets. We prove that our algorithm guarantees convergence in L2 to a NE that meets target total load constraints. Simulations show the effectiveness of our approach when applied to smart grid demand-side management or power control in wireless networks.

Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, representable as an NxM matrix. These utilities are unknown to the players. In each turn players receive noisy observations of their utility for their selected arm. However, if any other players selected the same arm that turn, they will all receive zero utility due to the conflict. No other communication or coordination between the players is possible. Our goal is to design a distributed algorithm that learns the matching between players and arms that achieves max-min fairness while minimizing the regret. We present an algorithm and prove that it is regret optimal up to a \log\log T factor. This is the first max-min fairness multi-player bandit algorithm with (near) order optimal regret.

Consider a team of cooperative players that take actions in a networked-environment. At each turn, each player chooses an action and receives a reward that is an unknown function of all the players' actions. The goal of the team of players is to learn to play together the action profile that maximizes the sum of their rewards. However, players cannot observe the actions or rewards of other players, and can only get this information by communicating with their neighbors. We design a distributed learning algorithm that overcomes the informational bias players have towards maximizing the rewards of nearby players they got more information about. We assume twice continuously differentiable reward functions and constrained convex and compact action sets. Our communication graph is a random time-varying graph that follows an ergodic Markov chain. We prove that even if at every turn players take actions based only on the small random subset of the players' rewards that they know, our algorithm converges with probability 1 to the set of stationary points of (projected) gradient ascent on the sum of rewards function. Hence, if the sum of rewards is concave, then the algorithm converges with probability 1 to the optimal action profile.

On-device learning promises collaborative training of machine learning models across edge devices without the sharing of user data. In state-of-the-art on-device learning algorithms, devices communicate their model weights over a decentralized communication network. Transmitting model weights requires huge communication overhead and means only devices with identical model architectures can be included. To overcome these limitations, we introduce a distributed distillation algorithm where devices communicate and learn from soft-decision (softmax) outputs, which are inherently architecture-agnostic and scale only with the number of classes. The communicated soft-decisions are each model's outputs on a public, unlabeled reference dataset, which serves as a common vocabulary between devices. We prove that our algorithm converges with probability 1 to a stationary point where all devices in the communication network distill the entire network's knowledge on the reference data, regardless of their local connections. Our analysis assumes smooth loss functions, which can be non-convex. Simulations support our theoretical findings and show that even a naive implementation of our algorithm significantly reduces the communication overhead while achieving an overall comparable performance to state-of-the-art, depending on the regime. By requiring little communication overhead and allowing for cross-architecture training, we remove two main obstacles to scaling on-device learning.

Consider an epidemic that propagates in a network of N individuals. The dynamics of the infection are governed by the N-intertwined SIR model, which is a non-linear model. Our goal is to prevent the epidemic by removing (vaccinating) nodes and removing (closing) links. Since vaccinating nodes and closing links are costly, we want to minimize this cost under the constraint of preventing the outbreak. We first show that preventing the outbreak can be guaranteed by ensuring that the maximal eigenvalue \lambda_{1} of a specific linear system is negative. This induces a well posed, but highly complex, combinatorial optimization problem. We propose a greedy algorithm that at each step picks the approximately best link to close or the best node to vaccinate, and proceeds to break the network until \lambda_{1}<; 0. We prove that running our algorithm on a coarser and smaller graph of regions, as opposed to individuals, still guarantees that the epidemic is prevented in the large network of size N. We tested our algorithm on an N-intertwined SIR model that was calibrated using real data that includes measles outbreaks and contact frequencies. The contact network was generated based on raw cellular localization data of 17 billion records from Radio Network Controllers that cover 1.8 million users over 2 months. Our encouraging results demonstrate that algorithms that consider the topology of the network can offer great value even in practical scenarios, where the decisions and computations can only be made on the regional level.

Consider a distributed network with N devices and K channels. Each device chooses a single channel and controls its transmission power on that channel. Our goal is to minimize the total transmission power while maintaining reliable communication between devices. Minimizing the total power consumption involves both the combinatorial optimization aspect of assigning channels to devices and the continuous optimization aspect of finding the optimal transmission powers. We present a distributed algorithm that solves the multichannel power control problem, and prove that it converges to the optimal solution. The algorithm is based on exploring new channel allocations by trial and error and running the best-response power control algorithm on the explored channel allocation. Using a novel wireless consensus phase, where devices use their transmission power as a consensus variable, all devices learn if the explored allocation is better than the current one. If the new allocation is better, all devices start using this allocation until the next trial and error. Finally, we provide simulations that support our analytical findings.

We consider a microgrid that consists of N providers and B consumers. Each provider has a certain supply and each consumer has a certain demand. The efficiency of transmitting energy between providers and consumers is modeled using a bipartite graph G. Our goal is to maximize the amount of utilized energy using a distributed algorithm that each provider runs locally. We propose a non-cooperative energy allocation game, and adopt the best-response dynamics for this game as our distributed algorithm. We prove that the best-response dynamics converge in no more than N steps to one of at most N! pure Nash equilibria of our game. Despite the fact that some of these Nash equilibria are suboptimal, we are able to prove that our algorithm achieves near-optimal performance in “almost all” games. We do so by analyzing the best-response dynamics in a random game, where the network is generated using a random model for the graph G. We prove that the ratio between the utilized energy of our algorithm and that of the optimal solution converges to one in probability as B increases (and N is any function of B). Using numerical simulations, we demonstrate that our asymptotic analysis is valid even for B = 10 consumers.

Consider a player that in each of T rounds chooses one of K arms. An adversary chooses the cost of each arm in a bounded interval, and a sequence of feedback delays \left{ d_{t}\right} that are unknown to the player. After picking arm a_{t} at round t, the player receives the cost of playing this arm d_{t} rounds later. In cases where t+d_{t}>T, this feedback is simply missing. We prove that the EXP3 algorithm (that uses the delayed feedback upon its arrival) achieves a regret of O\left(\sqrt{\ln K\left(KT+\sum_{t=1}^{T}d_{t}\right)}\right). For the case where \sum_{t=1}^{T}d_{t} and T are unknown, we propose a novel doubling trick for online learning with delays and prove that this adaptive EXP3 achieves a regret of O\left(\sqrt{\ln K\left(K^{2}T+\sum_{t=1}^{T}d_{t}\right)}\right). We then consider a two player zero-sum game where players experience asynchronous delays. We show that even when the delays are large enough such that players no longer enjoy the “no-regret property”, (e.g., where d_{t}=O\left(t\log t\right)) the ergodic average of the strategy profile still converges to the set of Nash equilibria of the game. The result is made possible by choosing an adaptive step size \eta_{t} that is not summable but is square summable, and proving a “weighted regret bound” for this general case.

Channel allocation is the task of assigning channels to users such that some objective (e.g., sum-rate) is maximized. In centralized networks such as cellular networks, this task is carried by the base station (BS) which gathers the channel state information (CSI) from the users and computes the optimal solution. In distributed networks such as ad-hoc and device-to-device (D2D) networks, no BS exists and conveying global CSI between users is costly or simply impractical. When the CSI is time varying and unknown to the users, the users face the challenge of both learning the channel statistics online and converging to a good channel allocation. This introduces a multi-armed bandit (MAB) scenario with multiple decision makers. If two or more users choose the same channel, a collision occurs and they all receive zero reward. We propose a distributed channel allocation algorithm that each user runs and converges to the optimal allocation while achieving an order optimal regret of O (log T ), where T denotes the length of time horizon. The algorithm is based on a carrier sensing multiple access (CSMA) implementation of the distributed auction algorithm. It does not require any exchange of information between users. Users need only to observe a single channel at a time and sense if there is a transmission on that channel, without decoding the transmissions or identifying the transmitting users. We demonstrate the performance of our algorithm using simulated LTE and 5G channels.

We consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. Our proposed algorithm is a modified Fictitious Play algorithm that can be implemented distributedly, and its stable points are the pure Nash equilibria of a given game. Our goal is to design a utility function for a non-cooperative game, such that all of its pure Nash equilibria have close to optimal global performance. This will make the algorithm close to optimal while requiring no communication between users. We propose a novel technique to analyze the Nash equilibria of a random interference game, determined by the random channel gains. Our analysis is asymptotic in the number of users. First, we present a natural non-cooperative game where the utility of each user is his achievable rate. It is shown that, asymptotically in the number of users and for strong enough interference, this game exhibits many bad equilibria. Then, we propose a novel non-cooperative M frequency-selective interference channel game as a slight modification of the former, where the utility of each user is artificially limited. We prove that even its worst equilibrium has asymptotically optimal weighted sum rate for any interference regime and even for correlated channels. This is based on an order statistics analysis of the fading channels that is valid for a broad class of fading distributions (including Rayleigh, Rician, m-Nakagami, and more). We carry out simulations that show fast convergence of our algorithm to the proven asymptotically optimal pure Nash equilibria.

Consider a channel allocation problem over a frequency-selective channel. There are K channels (frequency bands) and N users such that K = bN for some positive integer b. We want to allocate b channels (or resource blocks) to each user. Due to the nature of the frequency-selective channel, each user considers some channels to be better than others. The optimal solution to this resource allocation problem can be computed using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains, which makes this approach impractical for large networks. We suggest a suboptimal approach that only requires knowing what the M-best channels of each user are. We find the minimal value of M such that there exists an allocation where all the b channels each user gets are among his M-best. This leads to the feedback of significantly less than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami, and others, this suboptimal approach leads to both an asymptotically (in K) optimal sum rate and an asymptotically optimal minimal rate. Our non-opportunistic approach achieves (asymptotically) full multiuser diversity as well as optimal fairness in contrast to all other limited feedback algorithms.

We consider a multi-armed bandit game where N players compete for K arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed. Performance is measured using the expected sum of regrets, compared to the optimal assignment of arms to players. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-O\left(\log^{2}T\right). This is the first algorithm to achieve a poly-logarithmic regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.

Consider a channel allocation problem over a frequency-selective channel. There are K channels (frequency-bands) and N users such that K = bN for some positive integer b. We want to allocate b channels (or resource blocks) for each user. Due to the nature of the frequency-selective channel, each user considers some channels to be better than others. Allocating each user only good channels will result in better performance than an allocation that ignores the selectivity of the channel. The optimal solution for this resource allocation problem can be computed using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains, which makes this approach impractical for large networks. We suggest a suboptimal approach, that only requires knowing what the M-best channels of each user are. We find the minimal value of M such that there exists an allocation where all the b channels each user gets are among his M-best. This leads to a feedback of significantly less than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami and more, this suboptimal approach leads to both an asymptotically (in K) optimal sum-rate and asymptotically optimal minimal rate. Our non-opportunistic approach achieves asymptotically full multiuser diversity and optimal fairness, in contrast to all existing limited feedback algorithms.

In this paper we consider the problem of channel allocation for users who access a common channel using OFDMA. The spectrum is divided into subchannels and we assume that the bandwidth of each subchannel is smaller than the coherence bandwidth. This leads to correlations between the channel coefficients for each user. We model these correlated channels as an m-dependent sequence and generate an interference game at random, according to some marginal fading distribution. Performance is measured by the sum of achievable rates. Using a novel analysis of the random pure NE of the game, we prove that even for correlated channels the M-frequency selective interference game, suggested in previous work, has only Nash equilibria that exhibit good performance with high probability, asymptotically with the number of users. This game is the basis for an asymptotically optimal and fully distributed OFDMA channel allocation algorithm, presented in simulations.