Author name cluster

Don Towsley

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AAAI Conference 2025 Conference Paper

Quantum Best Arm Identification with Quantum Oracles

Xuchuang Wang
Yu-Zhen Janice Chen
Matheus Guedes de Andrade
Jonathan Allcock
Mohammad Hajiesmaili
John C.S. Lui
Don Towsley

Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1<= m<= K) simultaneously, we propose an algorithm with an upper bound of O((K/(Delta x sqrt(m))) log(1/delta)), improving by a factor of sqrt(m) compared to the m=1 case. We also provide query complexity lower bounds for both scenarios, which match the upper bounds up to logarithmic factors, and validate our theoretical results with Qiskit-based simulations.

PDF Details DOI

ICLR Conference 2023 Conference Paper

Achieving Near-Optimal Individual Regret & Low Communications in Multi-Agent Bandits

Xuchuang Wang
Lin Yang 0013
Yu-Zhen Janice Chen
Xutong Liu 0002
Mohammad Hajiesmaili
Don Towsley
John C. S. Lui

Cooperative multi-agent multi-armed bandits (CM2AB) study how distributed agents cooperatively play the same multi-armed bandit game. Most existing CM2AB works focused on maximizing the group performance of all agents---the accumulation of all agents' individual performance (i.e., individual reward). However, in many applications, the performance of the system is more sensitive to the ``bad'' agent---the agent with the worst individual performance. For example, in a drone swarm, a ``bad'' agent may crash into other drones and severely degrade the system performance. In that case, the key of the learning algorithm design is to coordinate computational and communicational resources among agents so to optimize the individual learning performance of the ``bad'' agent. In CM2AB, maximizing the group performance is equivalent to minimizing the group regret of all agents, and minimizing the individual performance can be measured by minimizing the maximum (worst) individual regret among agents. Minimizing the maximum individual regret was largely ignored in prior literature, and currently, there is little work on how to minimize this objective with a low communication overhead. In this paper, we propose a near-optimal algorithm on both individual and group regrets, in addition, we also propose a novel communication module in the algorithm, which only needs $O(\log (\log T))$ communication times where $T$ is the number of decision rounds. We also conduct simulations to illustrate the advantage of our algorithm by comparing it to other known baselines.

Details

UAI Conference 2023 Conference Paper

Exploration for Free: How Does Reward Heterogeneity Improve Regret in Cooperative Multi-agent Bandits?

Xuchuang Wang
Lin Yang 0013
Yu-Zhen Janice Chen
Xutong Liu 0002
Mohammad Hajiesmaili
Don Towsley
John C. S. Lui

This paper studies a cooperative multi-agent bandit scenario in which the rewards observed by agents are heterogeneous—one agent’s meat can be another agent’s poison. Specifically, the total reward observed by each agent is the sum of two values: an arm-specific reward, capturing the intrinsic value of the arm, and a privately-known agent-specific reward, which captures the personal preference/limitations of the agent. This heterogeneity in total reward leads to different local optimal arms for agents but creates an opportunity for \textit{free exploration} in a cooperative setting—an agent can freely explore its local optimal arm with no regret and share this free observation with some other agents who would suffer regrets if they pull this arm since the arm is not optimal for them. We first characterize a regret lower bound that captures free exploration, i. e. , arms that can be freely explored have no contribution to the regret lower bound. Then, we present a cooperative bandit algorithm that takes advantage of free exploration and achieves a near-optimal regret upper bound which tightly matches the regret lower bound up to a constant factor. Lastly, we run numerical simulations to compare our algorithm with various baselines without free exploration.

Details

EWRL Workshop 2023 Workshop Paper

On-Demand Communication for Asynchronous Multi-Agent Bandits

Yu-Zhen Janice Chen
Lin Yang
Xuchuang Wang
Xutong Liu
Mohammad Hajiesmaili
John C. S. Lui
Don Towsley

This paper studies a cooperative multi-agent multi-armed stochastic bandit problem where agents operate $\textit{asynchronously}$ -- agent pull times and rates are unknown, irregular, and heterogeneous -- and face the same instance of a $K$-armed bandit problem. Agents can share reward information to speed up the learning process at additional communication costs. We propose $\texttt{ODC}$, an on-demand communication protocol that tailors the communication of each pair of agents based on their empirical pull times. $\texttt{ODC}$ is efficient when the pull times of agents are highly heterogeneous, and its communication complexity depends on the empirical pull times of agents. $\texttt{ODC}$ is a generic protocol that can be integrated into most cooperative bandit algorithms without degrading their performance. We then incorporate $\texttt{ODC}$ into the natural extensions of $\texttt{UCB}$ and $\texttt{AAE}$ algorithms and propose two communication-efficient cooperative algorithms. Our analysis shows that both algorithms are near-optimal in regret.

PDF

NeurIPS Conference 2021 Conference Paper

Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback

Lin Yang
Yu-Zhen Janice Chen
Stephen Pasteris
Mohammad Hajiesmaili
John C. S. Lui
Don Towsley

This paper studies a cooperative multi-armed bandit problem with $M$ agents cooperating together to solve the same instance of a $K$-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i. e. , agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local. The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any $\textit{suboptimal}$ arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called $\texttt{CO-LCB}$ algorithm, whose regret is a function of aggregate action frequency of agents containing the $\textit{optimal}$ arm. We also show that the regret of $\texttt{CO-LCB}$ matches the regret lower bound up to a small factor.

PDF Details

NeurIPS Conference 2016 Conference Paper

Diffusion-Convolutional Neural Networks

James Atwood
Don Towsley

We present diffusion-convolutional neural networks (DCNNs), a new model for graph-structured data. Through the introduction of a diffusion-convolution operation, we show how diffusion-based representations can be learned from graph-structured data and used as an effective basis for node classification. DCNNs have several attractive qualities, including a latent representation for graphical data that is invariant under isomorphism, as well as polynomial-time prediction and learning that can be represented as tensor operations and efficiently implemented on a GPU. Through several experiments with real structured datasets, we demonstrate that DCNNs are able to outperform probabilistic relational models and kernel-on-graph methods at relational node classification tasks.

PDF Details

I&C Journal 2013 Journal Article

Signal-flow-based analysis of wireless security protocols

Çağatay Çapar
Dennis Goeckel
Kenneth G. Paterson
Elizabeth A. Quaglia
Don Towsley
Murtaza Zafer

Security protocols operating over wireless channels can incur significant communication costs (e. g. , energy, delay), especially under adversarial attacks unique to the wireless environment such as signal jamming, fake signal transmission, etc. Since wireless devices are resource constrained, it is important to optimize security protocols for wireless environments by taking into account their communication costs. Towards this goal, we first present a novel application of a signal-flow-based approach to analyze the communication costs of security protocols in the presence of adversaries. Our approach models a protocol run as a dynamic probabilistic system and then utilizes Linear System theory to evaluate the moment generating function of the end-to-end cost. Applying this technique to the problem of secret key exchange over a wireless channel, we quantify the efficiency of existing families of key exchange cryptographic protocols, showing, for example, that an ID-based approach can offer an almost 10-fold improvement in energy consumption when compared to a traditional PKI-based protocol. We then present a new key exchange protocol that combines traditional cryptographic methods with physical-layer techniques, including the use of “ephemeral” spreading codes, cooperative jamming, and role-switching. Utilizing signal flow analysis, we demonstrate that this new protocol offers performance advantages over traditional designs.

Details DOI