Adapting UCB For Correlated Arms in Link Rate Selection for Wireless Channels

In this paper, we model the problem of link rate selection in wireless channels as a multi-armed bandit problem with correlated arms. A success/failure in a wireless transmission for a given choice of modulation and coding scheme (MCS, an arm) permits us to efficiently predict (upper bound) the outcome of the transmission for other choice of MCS (other arms). For such a correlated arm scenario, we propose an adaptation to the upper confidence bound (UCB) bandit algorithm to minimize the expected cumulative regret. We propose Min-UCB algorithm that leverages the correlations in the rewards of the different arms to define a better estimate of the upper confidence bound for an arm by suitably combining the observed rewards of other arms. We prove that the proposed Min-UCB algorithm performs better in terms of expected cumulative regret than vanilla UCB and many variants proposed for the correlated arms scenario. We also propose a generalization, called Min-Bandit, for other MAB models, evaluate the proposed algorithm numerically and compare the performance with state-of-the-art bandit agents in a variety of scenarios. We show that the Min-Bandit algorithms achieve a better competitive advantage on the cumulative regret than prior works.