  We address the problem of opportunistic multiuser scheduling in downlink
networks with Markov-modeled outage channels. We consider the scenario in which
the scheduler does not have full knowledge of the channel state information,
but instead estimates the channel state information by exploiting the memory
inherent in the Markov channels along with ARQ-styled feedback from the
scheduled users. Opportunistic scheduling is optimized in two stages: (1)
Channel estimation and rate adaptation to maximize the expected immediate rate
of the scheduled user; (2) User scheduling, based on the optimized immediate
rate, to maximize the overall long term sum-throughput of the downlink. The
scheduling problem is a partially observable Markov decision process with the
classic 'exploitation vs exploration' trade-off that is difficult to quantify.
We therefore study the problem in the framework of Restless Multi-armed Bandit
Processes (RMBP) and perform a Whittle's indexability analysis. Whittle's
indexability is traditionally known to be hard to establish and the index
policy derived based on Whittle's indexability is known to have optimality
properties in various settings. We show that the problem of downlink scheduling
under imperfect channel state information is Whittle indexable and derive the
Whittle's index policy in closed form. Via extensive numerical experiments, we
show that the index policy has near-optimal performance.
  Our work reveals that, under incomplete channel state information, exploiting
channel memory for opportunistic scheduling can result in significant
performance gains and that almost all of these gains can be realized using an
easy-to-implement index policy.
