Whittle Index Policy for Opportunistic Scheduling: Heterogeneous Multistate Channels

We consider the multichannel opportunistic access problem, in which a user decides, at each time slot, which channel to access among multiple Gilbert-Elliot channels in order to maximize the expected transmission throughput, given that the imperfect observation of channel state. The problem can be cast into a RMAB problem, and the index policy is a very popular heuristic which is provably optimal asymptotically and has good empirical performance. For imperfect observation, the traditional approach computing the index policy cannot be directly applied because of nonlinear evolution of state belief information. Based on the fixed point approach, we divide the belief information space into a series of regions and then establish a set of periodic structures of the underlying nonlinear dynamic evolving system, based on which we devise the linearization scheme for each region to establish indexability and compute the Whittle index for each region.