Opportunistic Multichannel Access with Imperfect Observation: A Fixed Point Analysis on Indexability and Index-based Policy

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 his aggregated utility (e.g., the expected transmission throughput) given that the observation of channel state is error-prone. The problem can be cast into a restless multiarmed bandit problem which is proved to be PSPACE-Hard. An alternative approach, given the problem hardness, is to look for simple channel access policies. Whittle index policy is a very popular heuristic for restless bandits, which is provably optimal asymptotically and has good empirical performance. In the case of imperfect observation, the traditional approach of computing the Whittle index policy cannot be applied because the channel state belief evolution is no more linear, thus rendering the indexability of our problem open. In this paper, we mathematically establish the indexability and establish the closed-form Whittle-index, based on which index policy can be constructed. The major technique in our analysis is a fixed point based approach which enable us to 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.