BANDIT-STYLE ALGORITHMS FOR WIRELESS NETWORK SELECTION

Abstract

We explore the use of multi-armed bandit online learning techniques to solve distributed resource selection problems. As an example, we focus on the network selection problem. Mobile devices often have several wireless networks at their disposal. While choosing the right network is vital for good performance, a decentralized solution remains a challenge. The impressive theoretical properties of multi-armed bandit algorithms, like EXP3, suggest that it should work well for this type of problem. Yet, its real word performance lags far behind. It incurs high switching cost, is slow to stabilize, fails to deal with transient behaviors, and does not provide good guarantees for periodic behaviors. We develop (a) Smart EXP3, a novel bandit-style algorithm that retains the good properties of EXP3 while compensating for its shortcomings, (b) Co-Bandit, a collaborative bandit-style algorithm with improved rate of stabilization, and (c) Smart Periodic EXP4, that effectively learns periodic patterns in network data rates.