A Converse Result on Convergence Time for Opportunistic Wireless Scheduling

This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multiple access and broadcast systems. Every time slot an access point observes the current channel states for each user and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of O(log(T )/T ), where T is the time the algorithm has been running. An existing Ω(1/T ) converse is known. The current paper improves the converse to Ω(log(T )/T ), which matches the known achievability result. It does this by constructing a particular (simple) system for which no algorithm can achieve a better performance. The proof uses a novel reduction of the opportunistic scheduling problem to a problem of estimating a Bernoulli probability p from independent and identically distributed samples. Along the way we refine a regret bound for Bernoulli estimation to show that, for any sequence of estimators, the set of values p ∈ [0, 1] under which the estimators perform poorly has measure at least 1/6.

This paper establishes the fundamental learning rate for network utility maximization in wireless opportunistic scheduling systems, such as multiple access systems and broadcast systems. The recent work [2] shows that a stochastic Frank-Wofe algorithm with a vanishing stepsize achieves a utility optimality gap that decays like O(log(T )/T ), where T is the time the algorithm is in operation. It does this without a-priori knowledge of the channel state probabilities. This paper establishes a matching converse. A simple example system is constructed for which all algorithms have an error gap of at least Ω(log(T )/T ). Specifically, we construct a system with channel states parameterized by an unknown probability q ∈ [0, 1] such that for any algorithm, there is a set Q ⊆ [0, 1] with measure at least 1/6 under which the algorithm performs poorly. This is done by a novel reduction of the opportunistic scheduling problem to a problem of estimating a Bernoulli probability p from independent and identically distributed (i.i.d.) Bernoulli samples. Along the way, a refined statement regarding the regret of Bernoulli estimation is developed.

A general structure for the class of opportunistic scheduling systems is as follows: The system is assumed to operate over slotted time t ∈ 0, 1, 2, . . .. There are n users. Every slot t ∈ 0, 1, 2, . . . an access point allocates a vector X[t] = (X 1 [t], . . . , X n [t]) for transmission of independent data belonging to each user. In the case of wireless multiple access systems, the n users transmit their data over uplink channels to the access point. It is assumed they use a coordinated scheme that allows successful decoding of all transmissions at the scheduled bit rates X[t]. In the case of wireless broadcast systems, the access point transmits data for each user over downlink channels at the scheduled bit rates X [t].

The set of all transmission rate vectors that are available on a particular slot t can change from one slot to the next. This can arise from time-varying connection properties such as channel states that vary due to device mobility. We model this time-variation by a random state vector S[t] ∈ R m that is observed by the access point at the start of every slot t (where m is a positive integer that can be different from n). Assume that S[t] ∞ t=0 is i.i.d. over slots with some distribution F S (s) = P [S[0] ≤ s] for all s ∈ R m (where inequality is taken entrywise). The distribution function F S (s) is unknown. Define D(S[t]) as the decision set for slot t, being the set of all (X 1 [t], . . . , X n [t]) vectors that can be chosen on slot t when the channel state vector is S[t].

The structure of D(S[t]) depends on the network. For example, a multiple access network might allow only one user to transmit per slot. In this case we can define S[t] = (S 1 [t], . . . , S n [t]) as a vector of channel states, where S i [t] represents the transmission rate available to user i on slot t if that user is selected for transmission. Then D(S[t]) is a set that contains n vectors: D(S[t]) = (S 1 [t], 0, 0, ..., 0), (0, S 2 [t], 0, ..., 0), ..., (0, 0, ..., 0, S n [t))

where the ith vector in this set corresponds to choosing user i for transmission. More sophisticated wireless signaling schemes can allow the set D(S[t]) to contain vectors with multiple positive components. The set D(S[t]) can be uncountably infinite A partial version of this work was accepted for presentation at the IEEE INFOCOM conference, 2020 [1].