Adaptive Algorithms for Automatic Link Selection in Multiple Access with Link Failures

Abstract

This paper focuses on the problem of automatic link selection in multi-channel multiple access control using bandit feedback. In particular, a controller assigns multiple users to multiple channels in a time slotted system, where in each time slot at most one user can be assigned to a given channel and at most one channel can be assigned to a given user. Given that user $i$ is assigned to channel $j$, the transmission fails with a fixed probability $f_{i,j}$ . The failure probabilities are not known to the controller. The assignments are made dynamically using success/failure feedback. The goal is to maximize the time average utility, where we consider an arbitrary (possibly nonsmooth) concave and entrywise nondecreasing utility function. The problem of merely maximizing the total throughput has a solution of always assigning the same user-channel pairs and can be unfair to certain users, particularly when the number of channels is less than the number of users. Instead, our scheme allows various types of fairness, such as proportional fairness, maximizing the minimum, or combinations of these by defining the appropriate utility function. We propose an algorithm for this task that is adaptive and gets within $O(log(T)/T^{1/3} )$ of optimality over any interval of $T$ consecutive slots over which the success probabilities do not change. This performance is improved to $O(1/\sqrt{ T})$ for single-channel problems with a minimum constraint on the rate of transmission attempts per user.

Recommended citation: Wijewardena M. & Neely, M.J. (2025, May). Adaptive Algorithms for Automatic Link Selection in Multiple Access with Link Failures. In 23rd International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks
Download Paper