10 May 2022 in IEEE Transactions on Mobile Computing
There have been studies that consider optimizing applications in an online learning context using multi-armed bandit models. However, existing frameworks are problematic as they only consider finding the optimal decisions to minimize the regret, but neglect the constraints (or guarantee) requirements that may be excessively violated. In this paper, we formulate the stochastic constrained multi-armed bandit model with either ‘`time-varying’' or ‘`stochastic’' multi-level rewards for network application optimizations with guarantee by taking both regret and violation into consideration. Alongside this model, we design two constrained multi-armed bandit policies, Learning with Guarantee with time-Varying rewards (LG-V) and Learning with Guarantee with Stochastic rewards (LG-S), with provable sub-linear regret and violation bounds. Moreover, we illustrate how our policies can be applied to several emerging network application optimizations, namely, opportunistic multichannel selection, data-guaranteed mobile crowdsensing, and stability-guaranteed crowdsourced transcoding. To show the effectiveness of LG-V and LG-S in optimizing these applications with different requirements, we also conduct extensive simulations by comparing both LG-V and LG-S with existing state-of-the-art policies. We also show the impact of parameter variations, namely, the variations of the guarantee threshold and the number of selected arms, on the regrets and violations of LG-V and LG-S.
6 March 2025 in Proceedings of the ACM on Measurement and Analysis of Computing Systems
We study the cooperative asynchronous multi-agent multi-armed bandits problem, where each agent's active (arm pulling) decision rounds are asynchronous. That is, in each round, only a subset of agents is active to pull arms, and this subset is unknown and time-varying. We consider two models of multi-agent cooperation, fully distributed and leader-coordinated, and propose algorithms for both models that attain near-optimal regret and communications bounds, both of which are almost as good as their synchronous counterparts. The fully distributed algorithm relies on a novel communication policy consisting of accuracy adaptive and on-demand components, and successive arm elimination for decision-making. For leader-coordinated algorithms, a single leader explores arms and recommends them to other agents (followers) to exploit. As agents' active rounds are unknown, a competent leader must be chosen dynamically. We propose a variant of the Tsallis-INF algorithm with low switches to choose such a leader sequence. Lastly, we report numerical simulations of our new asynchronous algorithms with other known baselines.
11 October 2024 in IEEE Transactions on Network and Service Management
Effective resource allocation in sensor networks, IoT systems, and distributed computing is essential for applications such as environmental monitoring, surveillance, and smart infrastructure. Sensors or agents must optimize their resource allocation to maximize the accuracy of parameter estimation. In this work, we consider a group of sensors or agents, each sampling from a different variable of a multivariate Gaussian distribution and having a different estimation objective. We formulate a sensor or agent’s data collection and collaboration policy design problem as a Fisher information maximization (or Cramer-Rao bound minimization) problem. This formulation captures a novel trade-off in energy use, between locally collecting univariate samples and collaborating to produce multivariate samples. When knowledge of the correlation between variables is available, we analytically identify two cases: (1) where the optimal data collection policy entails investing resources to transfer information for collaborative sampling, and (2) where knowledge of the correlation between samples cannot enhance estimation efficiency. When knowledge of certain correlations is unavailable, but collaboration remains potentially beneficial, we propose novel approaches that apply multi-armed bandit algorithms to learn the optimal data collection and collaboration policy in our sequential distributed parameter estimation problem. We illustrate the effectiveness of the proposed algorithms, DOUBLE-F, DOUBLE-Z, UCB-F, UCB-Z, through simulation.
16 June 2025 in ACM SIGMETRICS Performance Evaluation Review
We study the cooperative asynchronous multi-agent multi-armed bandits problem, where each agent's active (arm pulling) decision rounds are asynchronous. That is, in each round, only a subset of agents is active to pull arms, and this subset is unknown and time-varying. We consider two models of multi-agent cooperation, fully distributed and leader-coordinated, and propose algorithms for both models that attain near-optimal regret and communications bounds, both of which are almost as good as their synchronous counterparts. The fully distributed algorithm relies on a novel communication policy consisting of accuracy adaptive and on-demand components, and successive arm elimination for decision-making. For leader-coordinated algorithms, a single leader explores arms and recommends them to other agents (followers) to exploit. As agents' active rounds are unknown, a competent leader must be chosen dynamically. We propose a variant of the Tsallis-INF algorithm with low switches to choose such a leader sequence. Lastly, we report numerical simulations of our new asynchronous algorithms with other known baselines.