To Send or Not to Send - Learning MAC Contention

The exponential back-off mechanism, proposed for reducing MAC- layer contention in the 802.11 standard, is sub-optimal in terms of the network throughput. This back-off mechanism and its improved variants are especially inefficient under unknown dynamics such as packet arrivals and user entry/exit. In this paper, we formulate the problem of optimizing this back-off mechanism as a Markov decision process, and propose online learning algorithms to learn the optimal back-off schemes under unknown dynamics. By exploiting the fact that some components of the system dynamics (such as protocol states) are known because the users follow the common 802.11 protocol, we propose a post-decision state (PDS)- based learning algorithm to speed up the learning process. Compared to traditional Q-learning algorithms, the advantages of the proposed online learning algorithm are that 1) it exploits partial information about the system so that less information needs to be learned in comparison to other learning algorithms, and 2) it removes the necessity for action exploration which usually impedes the learning process of conventional learning algorithms (such as Q-Learning). We prove the optimality of the proposed PDS-based learning algorithm and via numerical results demonstrate the improvement over existing protocols and Q-learning in terms of throughput and convergence speed. We first address this problem from a single-user perspective and later describe the challenges involved and present new insights into the multi-user learning scenarios, especially in cases where the MDP models of the users are coupled with each other.