Approximate Online Learning for Passive Monitoring of Multi-channel Wireless Networks

We consider the problem of optimally assigning $p$ sniffers to $K$ channels to monitor the transmission activities in a multi-channel wireless network. The activity of users is initially unknown to the sniffers and is to be learned along with channel assignment decisions. Previously proposed online learning algorithms face high computational costs due to the NP-hardness of the decision problem. In this paper, we propose two approximate online learning algorithms, $\epsilon$-GREEDY-APPROX and EXP3-APPROX, which are shown to have better scalability, and achieve sub-linear regret bounds over time compared to a greedy offline algorithm with complete information. We demonstrate both analytically and empirically the trade-offs between the computation cost and rate of learning.