Cascading Bandits with Two-Level Feedback

Motivated by the engineering application of efficient mobility management in ultra-dense wireless networks, we propose a novel cost-aware cascading bandit model with two-level actions. Compared with the standard cascading bandit model with a single-level action, this new model captures the real-world action sequence in mobility management, where the base station not only decides on an ordered neighbor cell list before measurement, but also executes the final handover decision to the target base station. We first analyze the optimal offline policy when the arm statistics are known beforehand. An online learning algorithm coined two-level Cost-aware Cascading UCB (CC-UCB) is then proposed to exploit the structure of the optimal offline policy with estimated arm statistics. Theoretical analysis shows that the cumulative regret under two-level CC-UCB scales logarithmically in time, which coincides with the asymptotic lower bound, thus is order-optimal. Simulation results corroborate the theoretical results and validate the effectiveness of two-level CC-UCB for mobility management.