Remark 1 We point out that under an i.i.d. or restedIn the rested model the Markov chain \(P^{i,k}\)  makes a state transition only when user \(i\)  accesses channel \(k\) . Markovian channel model, the optimal policy is to transmit on the same channels that achieves the optimal centralized allocation in terms of the sum expected rate. However, the optimal policy in the restless Markovian setting has been shown to be P-SPACE hard even under known Markoivan dynamics [1]}. Therefore, a commonly adopted approach in this setting is to use a weaker definition of the regret, first introduced in [2]} and used later; e.g., in [3]}, [4]}, [5]}, [6]}, where the policy is compared to a "partially informed" genie who knows the expected rates of the channels, instead of the complete system dynamics. In this paper we adopt this approach as well.

