On the optimality of a myopic policy in multi-state channel probing

We consider the channel probing problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and resource constrained jamming. The communication system consists of N channels. Each channel is modeled as a multi-state Markov chain (M.C.). At each time period a user selects one channel to probe and uses it to transmit information. A reward depending on the state of the selected channel is obtained for each transmission. The objective is to design a channel probing policy that maximizes the expected total reward collected over a finite or infinite horizon. This problem can be viewed as an instance of a restless bandit problem, to which the form of optimal policies is unknown in general. We discover conditions sufficient to guarantee the optimality of a myopic probing policy.