On optimality of myopic policy in multi-channel opportunistic access

We consider the channel access problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and server scheduling. The multi-channel communication system consists of N channels. Each channel evolves as a time-nonhomogeneous multi-state Markov process. At each time instant, a user chooses M channels to transmit information. Some reward depending on the states of the chosen channels is obtained for each transmission. The objective is to design an access policy that maximizes the expected accumulated discounted reward over a finite or infinite horizon. The considered problem can be cast into a restless multi-armed bandit (RMAB) problem with PSPACE-hardness. A natural alternative is to consider the easily implementable myopic policy. In this paper, we perform an theoretical analysis on the considered RMAB problem, and establish a set of closed-form conditions to guarantee the optimality of the myopic policy.