Online Wireless Scheduling for Throughput Maximization under Unknown Channel Statistics

We consider a wireless scheduling problem in downlink wireless networks with unknown channel statistics. Scheduling performance relies heavily on accurate channel state information (CSI), which is often costly to acquire. In this study, CSI is obtained from ACK/NACK feedback, only after each scheduled transmission. Due to limited channel resources, all users cannot be scheduled for transmission simultaneously. Hence, the most recently observed CSI can be outdated. The traditional approach to solving scheduling problems using outdated CSI is to utilize belief states, which are calculated using the time correlation statistics of channels. However, channel statistics are often unknown; consequently, belief states can be uncountable and this approach becomes infeasible. In this paper, we introduce a new sufficient statistic-the latest observed CSI and its Age of Channel State Information (AoCSI), which characterizes the CSI staleness, to make the scheduling decisions. Accordingly, we are able to significantly reduce the state space. We develop an online Maximum Gain First (Online-MGF) policy which achieves sub-linear regret on the number of episodes. Numerical results demonstrate that Online-MGF policy converges to MGF and Whittle index policies with known channel statistics within a very few episodes. In addition, Online-MGF outperforms Maximum AoCSI First (MAF) and random policies.