IEEE/ACM TRANSACTIONS ON NETWORKING
1
Efficient User Association and Wireless Scheduling with Shorter Time-Scale Rate Adaptation
arXiv:2609.09387v1 [cs.NI] 8 Sep 2026
Xiaoyi Wu, Graduate Student Member, IEEE, Huacheng Zeng, Senior Member, IEEE, and Bin Li, Senior Member, IEEE
Abstract—Rate adaptation is a crucial mechanism in IEEE 802.11 networks and next-generation cellular systems. Since the time scale for rate adaptation is typically much shorter than that for user association and scheduling, we investigate a joint design of wireless user association and scheduling and rate adaptation across different time scales to maximize cumulative network throughput while ensuring desired fairness among users. We develop a MaxWeight-type user association and scheduling algorithm that integrates virtual queues—tracking each user’s scheduling debt to maintain fairness—and Upper Confidence Bound (UCB) estimates in its weight measure. Each selected user then employs the UCB algorithm for rate adaptation on a short time scale. Our theoretical findings reveal that the proposed algorithm achieves cumulative regret that grows with the square root of the time horizon up to a logarithmic factor and results in zero cumulative fairness violation after a certain number of time frames. Furthermore, since the MaxWeight-type algorithm involves evaluating all the feasible schedules that can be exponential to the number of users due to the interference constraints, leading to high computational complexity, we introduce a low-complexity alternative utilizing the so-called pickand-compare (PC) approach. We demonstrate the effectiveness of both algorithms through simulations based on real-world data traces. Index Terms—User Scheduling, Rate Adaptation, UCB, Fairness, Low-Complexity.
I. I NTRODUCTION Multiple access points (APs) are commonly deployed in high-density areas such as campuses, stadiums, airports, subways, and shopping centers to ensure adequate communication capacity for reliable and fast wireless transmissions. Current APs are equipped with rate adaptation capability, enabling the transmitter to adjust the transmission rate using various channel coding and modulation schemes to accommodate the time-varying wireless channel, significantly enhancing system throughput. Moreover, the rate adaptation will be a key physical-layer mechanism for next-generation millimeterwave (mmWave) communication systems that typically have a large and unpredictable throughput fluctuation (see, e.g., [1]). Rate adaptation typically occurs every 100 ms in IEEE 802.11 systems [2], while in mmWave-based systems, it operates on a much smaller time scale (e.g., less than 10 ms or even 1 ms). Such an operation time scale is typically smaller than each user’s transmission session, necessitating a joint user © 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
association and scheduling design and rate adaptation. This design must determine when and which AP each user can associate with and is scheduled for wireless transmissions, as well as which transmission rate each selected user should choose on a small time scale during its scheduling period. The goal is to maximize network throughput while guaranteeing desired fairness among users (i.e., each user should be at least scheduled for a certain fraction of time on average). User association and scheduling design is important for efficiently managing interference in wireless networks, which has been extensively studied (e.g., [3], [4], [5], [6], [7], [8]). However, the integration of joint user association and scheduling design and rate adaptation with different time scales remains underexplored. In this paper, we consider user association and scheduling decisions are made every T time slots. The user dissociation and association involve disconnection and reconnection, typically incurring non-trivial costs such as communication interruptions and increased network delays. While a small value of T gives APs more flexibility to make association and scheduling decisions, potentially improving network performance, it also causes more frequent dissociation and association, resulting in high handover costs. Although frame-based scheduling designs (e.g., [9], [10]) for deadlineconstrained traffic share some similarities with our problem context, the user scheduling is not fixed within the entire frame and thus is fundamentally different from our problem. On the other hand, rate adaptation is a key mechanism for wireless communication systems to approach wireless channel capacity and has been widely studied in the literature. Earlier works (e.g., [11], [12], [13]) developed heuristic rate selection algorithms to balance exploration and exploitation. In [14], the authors formulated rate adaptation as a Multi-Armed Bandit (MAB) problem, where each arm corresponds to a rate associated with an unknown link successful transmission probability. As such, all classical MAB algorithms, such as Upper Confidence Bound (UCB [15]), Kullback-Leibler UCB (KL-UCB [16]), and Thompson Sampling [17], can be directly applied to develop rate adaptation algorithms with provable performance guarantees. The authors in [14] further developed a KL-UCB-based rate adaptation algorithm by exploiting the unimodal structure of the system throughput with respect to the transmission rate. Subsequent works [18], [19] further developed more efficient rate adaptation algorithms based on Thompson Sampling. However, all these rate adaptation algorithms focused on a single wireless link and have not yet been integrated into the wireless user scheduling design that operates on a much larger time scale.
IEEE/ACM TRANSACTIONS ON NETWORKING
In this paper, we develop a joint wireless user association and scheduling and rate adaptation algorithm with different operating time scales. The goal is to maximize the cumulative throughput over a finite time horizon while guaranteeing the desired fairness among users, i.e., each user is scheduled at least a certain fraction of time on average. This joint algorithm design is similar to the combinatorial bandits with fairness constraints (e.g., [20], [21]), where each arm corresponds to a user and fairness is ensured among users. In particular, [20] introduced the virtual queues to address fairness constraints and incorporated it into the algorithm design that yields a cumulative regret growing with the square root of the time horizon up to a logarithmic factor while guaranteeing longterm fairness among users. [21] developed a pessimisticoptimistic algorithm with regret that grows with the square root of the time horizon and agrees with the state-of-theart instance-independent bound, and zero cumulative fairness violation after a certain time. Our problem setup differs from those works in the following aspects. First, we consider joint user association, scheduling, and rate adaptation with fairness constraints, as opposed to user scheduling in [20], [21]. Second, our user association and scheduling do not rely solely on MAB-based online learning but instead utilize the MaxWeight-type algorithm, embedding an appropriate MAB component for each user in the joint user association and scheduling and rate adaptation framework. Third, user association and scheduling and rate adaptation operate at different time scales, posing unique challenges for algorithm design and theoretical analysis. To the best of our knowledge, this is the first work addressing wireless user association and scheduling and rate adaptation in different time scales. The main contributions of this work are summarized as follows: We develop an online-learning-based joint user association and scheduling and rate adaptation that operate on different time scales (cf. Section IV). In particular, a MaxWeight-type algorithm with the weight combining the virtual queues and UCB estimates is utilized to determine the user association and scheduling, while the UCB algorithm is employed to determine the transmission rate of each selected user. • We show that our proposed algorithm achieves √ O( K log K) regret over K time frames while zero cumulative fairness violation can be achieved after a certain number of time frames independent of K. • We further propose a low-complexity algorithm using the pick-and-compare approach, reducing the computational complexity of the MaxWeight-type joint user association and scheduling and rate adaptation algorithm. • We demonstrate the superior performance of our proposed algorithms via simulations using the experimental data collected in realistic wireless networks. •
While this paper is built upon our prior conference version [22], which was published in Wiopt 2023, we have the following new contributions: (1) we conduct an extensive literature survey related to our research; (2) we adopt the
2
pick-and-compare method to significantly reduce the computational complexity of the MaxWeight-type joint user association and scheduling and rate adaptation algorithm; (3) we add simulations to verify the effectiveness of this low-complexity algorithm using real-world data; (4) more detailed proofs for Proposition 1 and Proposition 2 are included. Note on Notation: We use bold and script font of a variable to denote a vector and a set, respectively. Let ∥x∥1 and ∥x∥ denote the l1 and l2 norm of the vector x, respectively. Let f (x) = O(x) if f (x) ≤ Cx, ∀x ≥ 0 for some positive real number C. II. RELATED WORK In this section, we survey two main areas that are closely related to our work: rate adaptation and MAB, and wireless scheduling with fairness constraints. A. Rate Adaptation and MAB Rate adaptation is a crucial strategy for wireless communication systems, which ensures optimal performance by adapting to time-varying channel conditions, interferences, and other dynamics. This technique has gained significant attention in research. The authors in [14] redefined rate adaptation using the framework of MAB. In this context, each “arm” represents a specific transmission rate, each having an uncertain probability of successful link transmission. Different from traditional unstructured MAB problems, the authors in [14] also explored the unimodal structure of the rate adaptation problem, which can be exploited to identify the optimal rate faster. They further applied a modified version of KL-UCB that takes advantage of this unimodal structure. The authors in [18], [19] developed more efficient rate adaptation algorithms based on Thompson Sampling. Subsequent works (e.g., [23], [24]) introduced contextual learning to the rate adaptation problem under the MAB framework. Authors in [23] proposed a contextual learning algorithm based on KL-UCB, which exploits the unimodality of the expected reward both in the arms and the contexts. Additionally, recent studies (e.g., [25], [26]) have capitalized on the correlations in the rewards associated with different transmission rates to estimate one rate by suitably combining the observed rewards of other rates. Other works, such as [27], [28], considered the rate adaptation jointly with other decision problems using the framework of MAB. However, all these rate adaptation algorithms have not yet been integrated into the wireless user scheduling design that operates on a much larger time scale. B. Wireless Scheduling with Constraints Wireless scheduling involves determining which devices or users get access to the network resources. The design of multiuser wireless schedulers has received substantial attention. For infinitely backlogged user queues, researchers have devised various schedulers that can achieve throughput optimality, such as MaxWeight rule [29], [30], Exp rule [31] and Log rule [32]. Subsequently, the authors in [33] introduced fairness constraints to wireless scheduling, which ensures each user
IEEE/ACM TRANSACTIONS ON NETWORKING
should be served with a fraction of time on average. However, they did not address the algorithm design in an unknown wireless network environment. Max-min fairness has also been studied from a joint rate-control and power-allocation perspective. For example, the authors in [34] characterize the optimal weighted max-min rate fairness under interference coupling via nonlinear Perron-Frobenius theory. In contrast, our work enforces fairness on the scheduling fractions through virtual queues and learns the unknown transmission-success statistics online. The notion of an approximation ratio has a long history in wireless resource allocation, where it quantifies the loss incurred by replacing an exact but computationally expensive allocation rule with a cheaper one. At the physical layer, the authors in [35] develop fast algorithms for sum rate maximization together with performance bounds that certify how close the returned solution is to the optimum, which turns an intractable problem into one with a quantified optimality gap. At the scheduling layer, the authors in [36] show that an imperfect scheduler attaining a constant fraction of the maximum weight stabilizes a correspondingly scaled version of the capacity region, and the pick-and-compare rule of [37] recovers the full region while comparing a single schedule per slot. In all of these results the channel statistics are known in advance, so the approximation ratio is a fixed constant determined by the accuracy of the allocation rule. A related line reaches a finite-horizon guarantee by a different route, either by competitive analysis against the offline optimum [38] or by a controlled approximation of the underlying combinatorial problem [39], where the uncertainty concerns the input rather than the system statistics. What all of these share is that nothing has to be learned, so no exploration cost enters the analysis and the ratio is a horizon-free constant. In our setting the per-link transmission-success statistics are unknown and must be learned online, so the algorithm resolves an exploration-exploitation trade-off whose cost is the cumulative regret, and the approximation ratio is horizon-dependent rather than a fixed constant. We make this connection precise in Discussion 1 and evaluate it on real-world traces in Section VI. Our problem of wireless user scheduling with fairness constraints under unknown system statistics can be analogous to the combinatorial bandits with fairness constraints (e.g., [20], [21], [40], [41], [42]), where each arm should be pulled for at least a certain minimum fraction of times in addition to the objective of maximizing the sum of expected rewards without the knowledge of reward distributions in advance. The authors in [20] introduced virtual queues to track the fairness violation and incorporated them into the algorithm design together with the UCB weight [15] for estimating the rewards. They characterized cumulative regret and long-term fairness performance. Recently, the authors in [21] proposed a pessimistic-optimistic algorithm that achieves state-of-theart regret performance and a zero fairness constraint violation by properly selecting algorithmic parameters. However, none of these works can be directly applied to our context, as our wireless user scheduling should be operated on different time scales, resulting in distinct dynamics for the virtual queue-length and UCB weight. Although there are similarities with frame-based scheduling methods for deadline-constrained
3
Fig. 1: Illustration of the feasible set S = {S(0) , S(1) , . . . , S(12) } for a network with L = 2 APs and N = 3 users, where each user is served by at most one AP per frame. Each element S(i) ∈ S represents a feasible schedule.
traffic (e.g., [9], [10]), the key difference is that user scheduling is not fixed across the entire frame. III. SYSTEM MODEL We consider a wireless system with N users and L APs. As shown in Fig. 2, time is divided into frames, each consisting of T time slots, and the total time horizon spans K such frames. At the beginning of each frame (i.e., at time indices {0, T, 2T, . . . , (K −1)T }), the system determines which user– AP pairs to activate. Each selected user is both associated with and scheduled by the assigned AP for the entire duration of the frame, i.e., for T time slots. These assignments remain fixed within the frame and are updated only at frame boundaries. A smaller frame size T enables the system to reassess user–AP pairings more frequently in response to time-varying channel conditions, thereby allowing users to connect to better APs more often. However, this increased flexibility comes at the cost of more frequent handovers and their associated overhead. Thus, the choice of frame size T reflects a trade-off between network adaptability and handover cost. Due to the wireless interference constraints, only a subset of users can transmit simultaneously in each time frame. We define Sl,n (kT ) = 1 if user n is associated with AP l for wireless transmission in frame k, and Sl,n (kT ) = 0 otherwise. The red dots represent the decision variable Sl,n (kT ), as illustrated in Fig. 2. We refer to S(kT ) ≜ (Sl,n (kT ), ∀l, ∀n) as the feasible schedule, indicating the set of users that can be served by each AP simultaneously in frame k. Let S denote the collection of all feasible schedules that satisfy the access constraints (e.g., each user associates with at most one AP and each AP serves at most a certain number of users per frame), as illustrated in Fig. 1 for a simple example with L = 2 APs and N = 3 users. Within each time slot of a frame, each selected user transmits to the AP at a rate chosen from the set {r1 , r2 , . . . , rM }, where 0 < r1 < r2 < · · · < rM and M is the number of available transmission rates. Let Xl,n,m (t) = 1 indicate that the wireless transmission of user n associated with AP l at rate rm is successful in time slot t, and Xl,n,m (t) = 0 otherwise. Here, rm Xl,n,m (t) represents the throughput when user n associated with AP l transmits at rate rm in time slot t. We assume that
IEEE/ACM TRANSACTIONS ON NETWORKING
4
max q(S)
X
q(S)
L X N X
S∈S
X
s.t.
Fig. 2: An illustrative example of joint user association and scheduling with rate adaptation operating on different time scales. The frame is represented by the blue dash box with length pre-set to T = 5. For each fixed (l, n, m), the red dots denote the decision varible Sl,n (kT ), indicating whether user n is associated and scheduled with AP l at the beginning of the frame k, while the green dots denote the decision varible Il,n,m (t), indicating whether user n transmits to AP l at rate rm in time slot t.
TABLE I: Summary of Key Parameters and MAB Analogies. Parameter
Description
Il,n,m (t)
Rate selection
Xl,n,m (t) Transmission result µl,n,m
Role
MAB Analogy
Decision variable
Arm selection
Observed outcome
Stochastic reward
Success probability Unknown parameter Expected reward
Our goal is to maximize the cumulative expected throughPK−1 put k=0 E[R(kT )] while ensuring fairness among users, indicating each user is scheduled for at least λn ∈ (0, 1) fraction of the time on average. If the statistics of throughput (i.e., µl,n,m , ∀l = 1, 2, · · · , L, ∀n = 1, 2, · · · , N, ∀m = 1, 2, · · · , M ) are known, our objective can be achieved by selecting a randomized stationary schedule2 {q ∗ (S), ∀S ∈ S}, where q ∗ (S) is the probability of selecting a feasible schedule S and solves the following optimization problem: 1 This assumption is standard in the wireless networking literature and has been widely adopted in prior work (e.g., [43]). 2 The existence of such a randomized stationary policy can be shown by using the similar argument in [44] and its proof is omitted for brevity.
l=1
where the optimization is over all feasible schedules in S. Since the access constraints (e.g., each user associates with at most one AP and each AP serves at most a certain number of users per frame) are already encoded in S, they are automatically enforced and do not need to appear as separate constraints. The parameter δ > 0 acts as a tightness margin, ensuring that the constraints are strictly satisfied. This aligns with the notion of Slater’s condition in convex optimization, which requires the existence of a strictly feasible solution. The set of all per-user service-rate vectors achievable by such randomized stationary policies, namely L n X N o X X Λ≜ q(S) Sl,n : q(S) ≥ 0, q(S) = 1 , S∈S
Xl,n,m (t) is independently and identically distributed (i.i.d.) with an unknown mean µl,n,m ∈ [0, 1]. We assume that for −1 each fixed (l, n, m), the sequence {Xl,n,m (t)}Tt=0 is independently and identically distributed (i.i.d.) over time slots t 1 with an unknown mean µl,n,m ∈ [0, 1]. In practice, µl,n,m denotes the probability that a packet transmitted from user n to AP l at rate rm is successfully received and acknowledged. Possible physical-layer effects such as fading, coding, and inter-AP interference are implicitly captured in this average success probability, and users simultaneously served by the same AP are assumed to be interference-free. Let Il,n,m (t) = 1 denote that user n associated with AP l transmits at rate rm in time slot t, and Il,n,m (t) = 0 otherwise. The green dots correspond to the decision variable Il,n,m (t), as illustrated in Fig. 2. Hence, the total received throughput of all users in frame k is P(k+1)T −1 P R(kT ) ≜ t=kT l,n,m Sl,n (kT )rm Xl,n,m (t)Il,n,m (t). Table I summarizes these key parameters and their analogies in the MAB framework.
(1)
m
Sl,n ≥ λn + δ, ∀n = 1, 2, . . . , N, (2)
q(S)
S∈S
Sl,n T max rm µl,n,m
l=1 n=1 L X
l=1
n=1
S∈S
forms the achievable region of the network, which serves as an analogue of the capacity region in our setting. The slackness δ then measures how far λ = (λn )N n=1 lies strictly inside Λ. Here, maxm rm µl,n,m represents the maximum achievable throughput for userPn communicating with AP l in each time slot, and thus l,n Sl,n T maxm rm µl,n,m represents its maximum throughput in one time frame if the schedule S = (Sl,n )l,n is selected. In the rest of the paper, we let S∗ denote the feasible schedule selected by the optimal randomized stationary schedule q ∗ (S). Within each frame, each selected ∗ user n associated with AP l chooses I∗ ≜ (Il,n,m )l,n,m ∈ PM arg maxI m=1 rm µl,n,m Il,n,m , i.e., selecting the rate with the maximum throughput, i.e., maxm rm µl,n,m , in each slot. However, the throughput statistics are unknown a priori in practice. Therefore, each user must learn these statistics (a.k.a. exploration) and select the empirically best transmission rate so far (a.k.a. exploitation). This process inevitably leads to a throughput loss compared to the scenario where the throughput statistics are known in advance. To quantify this throughput loss, we adopt the notion of cumulative regret, defined as the gap between the expected accumulated throughput under the optimal policy with known throughput statistics and that achieved by our algorithm, i.e., (k+1)T −1 M X X X ∗ ∗ Reg(KT ) ≜ E Sl,n rm µl,n,m Il,n,m k,l,n
t=kT
m=1
{z
|
}
≜ OPT(KT )
−
X k,l,n
|
E Sl,n (kT )
(k+1)T −1 M X X
rm µl,n,m Il,n,m (t) .
m=1
t=kT
{z
}
≜ ALG(KT )
Since OPT(KT ) is a fixed constant determined by the throughput statistics (i.e., µl,n,m ), minimizing the cumulative regret is equivalent to maximizing the expected accumulated throughput ALG(KT ) achieved by our algorithm. Our goal is to design a joint user scheduling and rate adaptation algorithm that not only meets the desired fairness requirement but also
IEEE/ACM TRANSACTIONS ON NETWORKING
5
minimizes the cumulative regret over consecutive K time frames. We note that our framework is also relevant to latencysensitive uplink applications. Since the cumulative throughput measures the total data delivered within KT time slots of fixed duration, configuring a shorter time slot duration effectively imposes stricter per-slot delivery deadlines. In this way, the throughput maximization objective naturally translates into a measure of timely delivery performance.
IV. A LGORITHM D ESIGN AND P ERFORMANCE A NALYSIS In this section, we develop an online-learning-based joint user scheduling and rate adaptation algorithm by integrating the key idea of the well-known UCB algorithm and virtual queue techniques while respecting the different time scales of user scheduling and rate adaptation. In particular, in the time scale for user schedule, the virtual queues are introduced to guarantee the desired fairness constraint (see [43] for an overview). In contrast, in the time scale for rate adaptation, the UCB approach is utilized to deal with the fundamental exploitation-exploration tradeoff in online learning for each user to identify the best transmission rate while achieving a minimum cumulative regret. To ensure fairness among users, we maintain a virtual queue for each user that tracks how much scheduling time the user is still owed relative to its fairness requirement. Specifically, each user n is entitled to be scheduled for at least a λn fraction of time on If in a given frame Paverage. L user n is not scheduled (i.e., l=1 Sl,n (kT ) = 0), its virtual queue-length increases, reflecting that the system has underserved PL this user. Conversely, when user n is scheduled (i.e., l=1 Sl,n (kT ) = 1), the virtual queue-length decreases. A larger virtual queue-length thus signals a more urgent need to schedule that user in subsequent frames. In particular, let Qn (kT ) be the virtual queue-length of user n at the beginning of time frame k, and its evolution over time frames is described as follows: L + X Qn ((k + 1)T ) = Qn (kT ) + λn − Sl,n (kT ) + ϵk , l=1
(3) for k = 0, 1, 2, . . ., where (x)+ ≜ max{x, 0} and ϵk > 0 is some control parameter that will be specified later. We set Qn (0) = 0 as the system starts at k = 0. Let Hl,n,m (t) be the number of time slots that user n is associated with AP lP and transmits at rate rm until time t−1 slot t, i.e., Hl,n,m (t) ≜ τ =0 Sl,n (⌊τ /T ⌋T )Il,n,m (τ ), where ⌊x⌋ denotes the maximum integer that is not greater than x. We set Hl,n,m (0) = 0 due to the fact that the system starts at t = 0. We use µl,n,m (t) to denote the fraction of successful transmissions when user n is associated with AP l and transmits at rate rm until time slot t, i.e., Pt−1 Sl,n (⌊τ /T ⌋T )Xl,n,m (t)Il,n,m (t) µl,n,m (t) ≜ τ =0 . Hl,n,m (t)
If Hl,n,m (t) = 0, we set µl,n,m (t) = 1. Let wl,n,m (t) denote the UCB estimate of user n associated with AP l using rate rm in time slot t, which can be defined below: s ) ( 3 log t ,1 , (4) wl,n,m (t) ≜ min µl,n,m (t) + 2Hl,n,m (t) p where 3 log t/(2Hl,n,m (t)) is the exploration bonus term that measures the uncertainty of the sample mean µl,n,m (t). Note that a smaller Hl,n,m (t) implies less exploration on user n using rate rm and thus more inaccuracy in the estimate µl,n,m (t), in which case user n is encouraged to transmit at rate rm for further exploration. In (4), we use the truncated version of the UCB estimate, since the successful transmission probability is at most 1. When Hl,n,m (t) = 0, we set wl,n,m (t) = 1, i.e., if user n has not transmitted at rate rm until time slot t, it should have the highest priority to be served. Algorithm 1 Online-Learning-based Joint User Association and Scheduling and Rate Adaptation (OUTTA) Algorithm At the beginning of frame k, select a feasible schedule b S(kT ) ≜ (Sbl,n (kT ), ∀l, ∀n) satisfying X b S(kT ) ∈ arg max Sl,n Qn (kT ) S∈S
l,n
+ ηk T max rm wl,n,m (kT ) , m
√
where ηk = δ k/T (with η0 = δ/(2T )). Then, update the virtual√queue-lengths according to (3) with ϵk = (4rM LN 1.5 + 1)/(2 k + 1). Within each time slot t in frame k, i.e., t = kT, kT + 1, . . . , (k + 1)T − 1, each selected user n associated with AP l (i.e., Sbl,n (kT ) = 1) chooses the rate index m b n (t) (i.e., b b Il,n,m b n (t)) such that b n (t) (t) = 1 and Il,n,m (t) = 0, ∀m ̸= m m b n (t) ∈ arg max rm wl,n,m (t). m
On one hand, we would like to schedule users with large virtual queue-lengths in each time frame to meet the desired fairness constraint. On the other hand, in order to achieve a low cumulative regret, we prefer to schedule users and select their rates with large UCB weights in each time slot. This motivates the following online-learning-based joint user scheduling and rate adaptation algorithm, as shown in Algorithm 1. In the proposed OUTTA algorithm, the increasing sequence {ηk }k≥0 balances the virtual queue-lengths and the UCB estimates for throughput statistics over time frames. Initially, the OUTTA algorithm puts a larger weight on the virtual queuelengths to quickly guarantee desired fairness while learning the best transmission rate for each user, and then emphasizes more on the UCB weight to ensure a smaller cumulative regret. The parameter ηk requires the exact knowledge of the slackness constant, which is usually unavailable in practice. We will demonstrate that the OUTTA algorithm with inaccurate slackness constants still performs well via simulations in Section VI. Different from prior works on combinatorial bandits with fairness constraints (e.g., [21]), the user scheduling and rate selection have different time scales. This requires carefully manipulating the virtual queue-lengths and UCB weights and
IEEE/ACM TRANSACTIONS ON NETWORKING
decoupling them in an appropriate way in the performance analysis. Next, we characterize the cumulative fairness violation of the proposed OUTTA algorithm. Proposition 1 (Cumulative Fairness Violation): Under the OUTTA algorithm, if ∃k ′ , such that for any k ≥ k ′ , ϵk ≤ δ/2, the cumulative fairness violation over K time frames can be upper bounded below: + N K−1 X X (k+1)T X −1 E (λn − Sn (t)) n=1
k=0
t=kT
√ + K , 2.5 + (4rM L + 3)N 1.5 + where g(N, δ, rM ) = 74Nδ log 18N δ 1.5 2 1.5 1.5 2 N (6+δ ) +1) 1 + 1 + N (4rM LN δ δ δ + 1 is a constant depending on system parameters such as N, δ and rM . Proof: We first select the Lyapunov function V (kT ) ≜ ∥Q(kT )∥, and prove that the Lyapunov function has an expected negative drift when V (kT ) is sufficiently large and its drift is absolutely bounded. Then according to [21, Lemma 11], E [∥Q(kT )∥1 ] can be upper bounded. Finally, we can derive the upper bound of the cumulative fairness violation by combining the dynamics of virtual queue-lengths and the analysis of E [∥Q(kT )∥1 ]. Please see Appendix A for the detailed proof. Remarks 1: Note that k ′ always exists due to the fact that {ϵk }k≥0 is an decreasing sequence. Given the condition, we can also see from Proposition 1 that the OUTTA algorithm achieves zero cumulative fairness violation when K ≥ g 2 (N, δ, rM ). Moreover, the number of frames required for achieving zero cumulative fairness violation is independent of frame size T and thus the required number of time slots for achieving zero cumulative fairness violation linearly increases with the frame size T . Furthermore, the amount of cumulative fairness violation linearly increases with the frame size T . All these observations will be demonstrated via simulations in Section VI. We derive an upper bound on the cumulative regret under the OUTTA algorithm. Proposition 2 (Cumulative Regret): Under the OUTTA algorithm with ϵk ≤ δ, the cumulative regret Reg(KT ) over K time frames can be upper bounded as follows: √ N rM T (4rM LN 1.5 + 1)2 3 Reg(KT ) ≤ + 2 KN T (δ + ) 2 4δ 2δ N T (2δ + 1)2 (4rM LN 1.5 + 1)3 + 4 16δ 5π 2 + (T + 1) log(KT ) + LM N rM T + 3 + 6 p + (T + 4)rM 6LM N Smax KT log(KT ) s 3LM N Smax KT + rM 2 log T √ = O N T K + LM N T log(KT ) p + T LM N KT log(KT ) .
≤ N T g(N, δ, rM ) −
6
Proof: We perform the drift-plus-penalty analysis. Unlike prior work on the regret analysis (e.g., [21]), the different time scales of user scheduling and rate selection impose unique challenges on the corresponding regret bound analysis. In particular, we need to upper bound the regret by carefully decoupling the user decision and rate adaption in different time scales. Please see Appendix B for the detailed proof. Remarks 2: For the impact of the number of frames K on the regret performance, our derived regret upper bound has the √ same order O( K log K) as the instance-independent upper bound for the classical UCB algorithm. While the derived regret upper bound increases with the frame size T , the simulations demonstrate that the frame size has a marginal impact on the regret performance. The reason is that each user has sufficient time to identify its best transmission rate under different frame sizes. Remarks 3: Since the wireless technology enters the analysis only through the feasible set S and the success probabilities µl,n,m , the Lyapunov-drift argument and the resulting guarantees apply unchanged across diverse MAC/PHY layers. Discussion 1: Proposition 2 can be restated as an approximation ratio with respect to the optimal value of (1) and (2). Let ρ(K) ≜ ALG(KT )/OPT(KT ) = 1 − Reg(KT )/OPT(KT ) denote the fraction of that optimal value attained by the OUTTA algorithm over K time frames. Every time frame serves L users at a strictly positive expected rate, so OPT(KT ) = Θ(K) grows linearly in the√number of frames, while Proposition 2pgives Reg(KT ) = O( K log K). Therefore ρ(K) ≥ 1 − O( log K/K) → 1 as K → ∞, that is, OUTTA is a ρ(K)-approximation over any finite horizon, and its gap 1 − ρ(K) = Reg(KT )/OPT(KT ) is determined directly by the regret bound. It is worth being explicit about why this ratio is horizondependent, whereas the approximation and competitive ratios of [35], [36], [38], [39] are constants. In those works the quantity being bounded is the suboptimality of a decision rule evaluated against a known objective, so the ratio is determined once and does not change with the length of the operating period. In our setting the gap between ALG(KT ) and OPT(KT ) arises only because µl,n,m is unknown and has to be estimated by the UCB estimate wl,n,m (t), which is the exploration-exploitation trade-off. Since the exploration p bonus 3 log t/(2Hl,n,m (t)) decays as Hl,n,m (t) grows, the √ accumulated shortfall is O( K log K) rather than linear in K, so the ratio improves with the horizon instead of being fixed. No horizon-free constant can describe this behavior, because the gap is by construction a function of how long the algorithm has been learning. The guarantee is moreover instance-independent, since Proposition 2 is of the same order as the instance-independent bound for the classical UCB algorithm, so the rate holds for every instance and carries no dependence on the gaps. Its numerical value at a given horizon is nevertheless instancespecific, since it involves OPT(KT ) and hence the unknown µl,n,m , and the explicit constants in Proposition 2 are worstcase. We therefore state the guarantee as a rate and report the realized ratio on real-world traces in Section VI.
IEEE/ACM TRANSACTIONS ON NETWORKING
V. LOW- COMPLEXITY ALGORITHM DESIGN The OUTTA algorithm schedules the subset of users with the maximum total weight of virtual queue-length and the UCB estimation in each time frame. Note that |S| can grow exponentially with the number of users due to the existence of interference constraints. Since the OUTTA algorithm necessitates evaluating all feasible schedulers in S to schedule the subset of users with the maximum total weight in each frame, it results in a high computational complexity. To address this, we propose an alternative algorithm that reduces the number of comparison steps in each frame, thereby lowering the computational complexity of the OUTTA algorithm, as shown in Algorithm 2. Algorithm 2 Pick and Compare Online-Learning-based Joint User Association and Scheduling and Rate Adaptation (PCOUTTA) Algorithm At the beginning of frame k, select R(kT ) ∈ S uniformly at random and compare R(kT ) with the previous schedule b PC ((k − 1)T ) ≜ (SbPC ((k − 1)T ), ∀l, ∀n) satisfying S l,n X PC b (kT ) ∈ S arg max Sl,n Qn (kT ) b PC ((k−1)T )} l,n S∈{R(kT ),S
+ ηk T max rm wl,n,m (kT ) , m
√
where ηk = δ k/T (with η0 = δ/(2T )). Then, update the virtual√queue-lengths according to (3) with ϵk = (4rM LN 1.5 + 1)/(2 k + 1). Within each time slot t in frame k, i.e., t = kT, kT + 1, . . . , (k + 1)T − 1, each selected user n associated with PC AP l (i.e., Sbl,n (kT ) = 1) chooses the rate index m b n (t) (i.e., b b Il,n,m (t) = 1 and I (t) = 0, ∀m = ̸ m b (t)) such that l,n,m n b n (t) m b n (t) ∈ arg max rm wl,n,m (t). m
We leverage the idea of the PC algorithm and develop the following PC-OUTTA algorithm that first randomly picks one feasible schedule in each frame and then selects the feasible schedule with the maximum weight among the randomly picked feasible schedule and the selected schedule in the previous frame. We use R(kT ) to denote the feasible schedule randomly picked in frame k. This PC design cuts down the number of comparison steps from |S| in the OUTTA algorithm to one in the PC-OUTTA algorithm. The rest of PC-OUTTA design is similar to OUTTA. To sum up, our PC-OUTTA algorithm design decreases the switching overhead incurred by frequent user handoffs between APs by employing a framebased design for scheduling and association. Additionally, it adopts the pick-and-compare strategy to circumvent evaluating every feasible schedule, as OUTTA does, thereby substantially lowering the computational complexity of the MaxWeight design. The trade-off between computational efficiency and performance has been theoretically analyzed in our recent work [45], where we rigorously studied the cumulative regret, fairness guarantees, and complexity of the PC-based design. We evaluate the performance of PC-OUTTA via simulations based on real-world data in Section VI.
7
Fig. 3: The distribution of 3 APs and 10 users. Fixed mmWave AP
mmWave user device
Fig. 4: Left: Experimental setup in a classroom. Right: A 60GHz mmWave transceiver with phased-array antenna.
VI. S IMULATIONS In this section, we evaluate the performance of our proposed OUTTA algorithm and PC-OUTTA algorithm via simulations based on real-world data. Experimental Setup: We consider a 60 GHz mmWave shortrange communication network (e.g., IEEE 802.11ad [46]) deployed in a classroom environment, where three APs are positioned and 10 user devices are uniformly distributed across the classroom, as shown in Fig. 3. Ideally, commodity off-theshelf (COTS) 802.11ad devices would be used to evaluate our algorithm. However, existing COTS 802.11ad routers do not provide sufficient control over rate adaptation, making them unsuitable for our experimental requirements. To address this limitation, we developed a 60 GHz mmWave testbed to collect end-to-end channel quality traces and conduct trace-driven simulations based on real-world measurements, as illustrated in Fig. 4. In principle, all 30 AP–user links should be measured simultaneously. However, the available hardware does not support concurrent measurements for all links. Therefore, we sequentially measured the 30 links one at a time, which is a common practice known as single-sounder sequential measurement [47]. The testbed consists of a transmitter located at an AP and a receiver located at a user device. Both the transmitter and the receiver are built from a computer for baseband signal processing, a USRP X310 for signal shaping, and Sivers EVK06002 for up/down frequency conversion. Simplified IEEE 802.11ad PHY-layer signal processing modules are implemented at both ends to enable real-time 802.11ad OFDM data packet transmission from the AP to the user device. The receiver demodulates the OFDM signal and records the post–signal-to-noise ratio (postSNR) for each packet. Fig. 5 shows the mmWave receiver diagram, which includes the spectrum display, demodulated signal constellation, and decoded video stream. The post-SNR is computed directly from the demodulated signal constellation. Data Collection: Prior to data collection for each link, we first adjust the beam indices at both the mmWave transmitter
IEEE/ACM TRANSACTIONS ON NETWORKING
Fig. 5: The receiver’s diagram. TABLE II: EVM table specified in IEEE 802.11ad standard [46] (B: BPSK; Q: QPSK; 16Q: 16-QAM). index (m) 1 2 3 4 5 6 7 8 9 postSNR (dB) -7 -9 -10 -11 -12 -14 -15 -16 -17 Modulation B B Q Q Q Q 16Q 16Q 16Q Coding rate 1/2 5/8 1/2 5/8 3/4 13/16 1/2 5/8 3/4 γ (postSNR) 0.5 0.63 1 1.25 1.5 1.63 2 2.5 3 Rate (Gbps) 0.73 0.91 1.46 1.825 2.19 2.37 2.92 3.65 4.38
and receiver to align their directions. This procedure emulates the beam search protocol implemented in 5G and IEEE 802.11ad/ay systems. Once beam alignment is established, we begin recording the postSNR at the receiver. During data collection, both the transmitter and receiver remain stationary with an unobstructed line-of-sight (LOS) path, although human activity occurs in the surrounding environment. For each link, the receiver records the postSNR of decoded signal constellations every 1 ms. The resulting dataset forms a 30 × 30000 matrix, where each entry represents the instantaneous endto-end channel quality (i.e., postSNR) from a given AP to a user device. We will release this dataset publicly to facilitate future research. A representative demonstration of mmWave physical-layer real-time video transmission from our group’s testbed is available online [48]. Interpretation of PostSNR: In communication engineering, postSNR is also referred to as the error vector magnitude (EVM). It serves as a comprehensive indicator of instantaneous link quality. Based on the measured postSNR, the achievable data rate of an IEEE 802.11ad link is computed τof dm as r(postSNR) = f · τgi +τ · NNdata · γ(postSNR), where of dm fft f = 2.64 GHz is the sampling rate, τgi = 36.36 ns is the guard interval duration, τof dm = 194.56 ns is the OFDM symbol duration, Ndata = 336 is the number of data subcarriers, Nf f t = 512 is the FFT size, and γ(postSNR) is given by the second-to-last row of Table II for each value. For example, if the measured postSNR of a link is −13 dB, Table II specifies that the transmitter should select MCS index 5 for packet transmission, resulting in a data rate of 2.19 Gbps. Instead, if MCS index 8 is selected, the receiver would be unable to successfully decode the packet. This MCS look-up method is widely adopted in system-level simulations within the 5G industry. Table II can thus be regarded as a simplified abstraction of the PHY-layer of the communication system. Simulation Setup: We consider N = 10 users and assume L = 3 APs, where each user can associate at most one AP and each AP can schedule multiple users in each time frame. Here, we set the maximum number of users each
8
AP can simultaneously serve to one as a representative example. We set each user’s desired scheduling fraction as λ = 2.1 55 × [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. There are nine rates available for selection, which are shown in the last row of Table II. The data packet transmission result is estimated as follows. Suppose the AP selects rm for a user device in the scheduling phase and the user device measures snr as its postSNR, if r(snr) ≥ rm , the data packet transmission is successful; otherwise, it fails. Since the exact value of the slackness constant δ is unknown in this system, we conduct a robustness evaluation by varying δ across a representative range: δ = [0.05, 0.1, 0.15]. This setup simulates scenarios where the algorithm operates under underestimated, exact, or overestimated slackness assumptions. 1) OUTTA: Fig. 6 shows the performance of the OUTTA algorithm using our collected wireless channel traces. We observe from Fig. 6(a) that each user’s scheduling fraction is larger than its desired value under different frame sizes, which shows that our OUTTA algorithm can guarantee longterm fairness. In addition, as shown in Fig. 6(b), our algorithm can also achieve zero cumulative fairness violation and thus yields short-term fairness. A larger frame size results in a long time to achieve zero cumulative fairness and a larger amount of cumulative fairness violation. Moreover, the OUTTA algorithm can achieve sublinear regret and the frame size has a negligible impact on the regret performance. The impact of the slackness constant δ has a marginal impact on cumulative fairness violation, as shown in Fig. 7. We further report the empirical approximation ratio ρ(K) = ALG(KT )/OPT(KT ) = 1 − Reg(KT )/OPT(KT ). As shown in Fig. 10(a), the approximation ratio of the OUTTA algorithm increases monotonically with the horizon, attaining ρ ≈ 0.74 within the simulated horizon and continuing to grow toward 1 as K increases. 2) PC-OUTTA: Fig. 8 and Fig. 9 show the influence of frame size and slackness constant on the performance of the PC-OUTTA algorithm, respectively, using our collected wireless channel traces. From Fig. 8(a), we observe that each user’s scheduling fraction exceeds its desired value across different frame sizes, demonstrating that our PC-OUTTA algorithm ensures long-term fairness. Additionally, Fig. 8(b) indicates a larger frame size results in a longer time required to achieve zero cumulative fairness violation and a larger amount of cumulative fairness violations. Compared with Fig. 6(b), the low-complexity PC-OUTTA algorithm requires a longer time to achieve zero cumulative fairness violation than the MaxWeight-type OUTTA algorithm. Similarly, as shown in Fig. 8(c), a larger frame size increases cumulative regret. Compared with Fig. 6(c), the low-complexity PCOUTTA algorithm generates larger cumulative regret than the MaxWeight-type OUTTA algorithm. It is also evident that the regret performance of the PC-OUTTA algorithm is more sensitive to frame size than that of the OUTTA algorithm. The influence of the slackness constant δ on cumulative fairness violation and regret performance is marginal in Fig. 9. Fig. 10(b) shows that the low-complexity PC-OUTTA algorithm attains essentially the same empirical approximation ratio (ρ ≈ 0.74 within the simulated horizon) as the MaxWeight-type OUTTA
IEEE/ACM TRANSACTIONS ON NETWORKING
(a) User Scheduling Fraction
9
(b) Cumulative Fairness Violation
(c) Cumulative Regret
Fig. 6: Impact of frame size T for OUTTA in Trace-based simulation.
(a) User Scheduling Fraction
(b) Cumulative Fairness Violation
(c) Cumulative Regret
Fig. 7: Impact of slackness constant δ for OUTTA in Trace-based simulation.
(a) User Scheduling Fraction
(b) Cumulative Fairness Violation
(c) Cumulative Regret
Fig. 8: Impact of frame size T for PC-OUTTA in Trace-based simulation.
(a) User Scheduling Fraction
(b) Cumulative Fairness Violation
(c) Cumulative Regret
Fig. 9: Impact of slackness constant δ for PC-OUTTA in Trace-based simulation.
IEEE/ACM TRANSACTIONS ON NETWORKING
10
(a) OUTTA
(b) PC-OUTTA
Fig. 10: Empirical approximation ratio ρ(K) = 1 − Reg(KT )/OPT(KT ) in trace-based simulation.
algorithm, again increasing toward 1 with the horizon and insensitive to the frame size T . Together with the cumulativefairness-violation results above, this quantifies the complexityperformance trade-off of the pick-and-compare design: PCOUTTA matches OUTTA in throughput approximation ratio at a substantially lower computational cost, at the expense of achieving zero violation point slower. VII. C ONCLUSION In this paper, we studied the joint design of user association and scheduling and rate adaptation with different time scales in wireless networks to maximize cumulative throughput while guaranteeing desired fairness among users. We developed a MaxWeight-type user association and scheduling algorithm that combines both the virtual queues and UCB estimates in its weight measure. Each selected user utilizes the UCB algorithm to determine a transmission rate on a small time√scale. We showed that our proposed algorithm yields O( K log K) cumulative regret over K time frames and achieves zero cumulative fairness violation after a certain number of time frames. Considering the complexity of the MaxWeight-type algorithm, we also give a low-complexity algorithm based on the pick-and-compare design. We performed simulations to demonstrate the efficiency of these two proposed algorithms based on real-world data. A PPENDIX A P ROOF OF P ROPOSITION 1 Select the Lyapunov function V (kT ) ≜ ∥Q(kT )∥, and consider its conditional expected drift given the current state W(kT ) ≜ (Q(kT ), w(kT )). We have the following key lemma. Lemma 1: For any 0 < ϵk ≤ δ/2, if V (kT ) ≥ Wk ≜ (6N + N δ 2 + 4ηk N LT rM )/δ, then δ E [V ((k + 1)T ) − V (kT )|W(kT )] ≤ − . (5) 4 Moreover, the absolute drift of V (kT ) is bounded by 3N , i.e., |V ((k + 1)T ) − V (kT )| ≤ 3N.
(6)
The proof follows a similar line of arguments in [49, Lemma 2] and its proof is available in Appendix C. For any ϵk ≤ δ/2, Lemma 1 satisfies the conditions of [21, Lemma 11] and thus we have h i ′ 8eθ(3N +Wk ) E eθV (kT ) ≤ eθV (k T ) + , (7) θδ 2 ′ where θ = δ/(36N + N δ) and k is the index such that for any k ≥ k ′ , ϵk ≤ δ/2. Note that such k ′ exists due to the fact that {ϵk }k≥0 is an decreasing sequence and Wk is increasing when k ≥ k ′ . According to Jensen’s inequality, for convex function eθx , we have h i ′ 8eθ(3N +Wk ) eθE[V (kT )] ≤ E eθV (kT ) ≤ eθ∥Q(k T )∥ + , (8) θδ which implies that ′ 1 8eθ(3N +Wk ) E[V (kT )] ≤ log eθ∥Q(k T )∥ + . (9) θ θδ Noting that V (kT ) = ∥Q(kT )∥ and ∥Q(kT )∥ ≥ √1 ∥Q(kT )∥1 , we have N √ ′ N 8eθ(3N +Wk ) log eθ∥Q(k T )∥ + E[∥Q(kT )∥1 ] ≤ θ θδ √ 2 θ(3N +Wk ) (a) N ′ 296N e ≤ log eθ∥Q(k T )∥ + θ δ2 √ (b) N 297N 2 θ(3N +Wk +∥Q(k′ T )∥) log e ≤ θ δ2 √ √ N 297N 2 + N (3N + Wk + ∥Q(k ′ T )∥) = log 2 θ δ (c) 74N 2.5 18N ≤ log + 3N 1.5 δ δ N 1.5 (6 + δ 2 + 4ηk LT rM ) + δ √ + N ∥Q(k ′ T )∥, (10) 2 where step (a) uses the fact that 1/θ = (36N + N δ)/δ ≤ 37N 2 /δ since δ < N ; (b) follows from the fact that δ < N ; (c) uses the fact that 297 < 324 = 182 , 1/θ ≤ 37N 2 /δ, and the definition of Wk . According to the dynamics of virtual queues (cf. (3)), we have Qn ((k + 1)T ) ≤ Qn (kT ) + λn + ϵk , ∀τ. (11)
IEEE/ACM TRANSACTIONS ON NETWORKING
11
By summing the above inequality over k = 0, 1, . . . , k ′ − 1 and utilizing the fact that Qn (0) = 0, we have ′ ′ kX −1 kX −1 ′ ′ ′ Qn (k T ) ≤ k λn + ϵk ≤ k + ϵk , (12) k=0
k′ −1
X N 1.5 (6 + δ 2 + 4ηk LT rM ) + + N 1.5 k ′ + N 1.5 ϵk . δ k=0 (13) According to the dynamics of virtual queues (cf. (3)), we have X Qn ((k + 1)T ) ≥ Qn (kT ) + λn − Sl,n (kT ) + ϵk , ∀k. l
(14) By summing the above inequality over k = 0, 1, . . . , K − 1, we have ! K−1 K−1 X X X Qn (KT ) ≥ λn − Sl,n (kT ) + ϵk , ∀n. (15) l
k=0
Noting that the user schedule is fixed within a frame and the virtual queue-lengths are only updated at the beginning of each frame, we have !+ K−1 X T E[Qn (KT )] − T ϵk k=0
!+
K−1 X (k+1)T X −1
≥ E
k=0
λn −
X
t=kT
≤ T E [∥Q(KT )∥1 ] − T 74N 2.5 ≤T log δ +
N
1.5
18N δ
2
t=kT
2.5 where g(N, δ, rM ) = 74Nδ log 18N + (4rM L + 3)N 1.5 + δ 1.5 2 1.5 1.5 2 N (6+δ ) +1) 1 + 1 + N (4rM LN δ δ δ +1 . A PPENDIX B P ROOF OF P ROPOSITION 2 We rewrite the regret of the OUTTA algorithm as follows. (k+1)T −1 M X X X ∗ ∗ Reg(KT ) ≜ E Sl,n rm µl,n,m Il,n,m k,l,n
+ 3N
E Sbl,n (kT )
k,l,n
=
t=kT
K−1 X
m=1
rm µl,n,m Ibl,n,m (t)
m=1
∆R(kT ),
(21)
(k+1)T −1
ϵk
−
X
t=kT (k+1)T −1 M X X
where
!+
∆R(kT ) ≜ +N
1.5 ′
K−1 X
+
1.5
(6 + δ + 4ηk LT rM ) − δ
k +N
1.5
′ kX −1
ϵl
l=0
ϵk
,
(17)
k=0
where the last step utilizes (13). P K−1 We will provide lower bound on k=0 ϵk and upper bound Pk′ −1 on k=0 ϵk , respectively. K−1 K−1 X 4rM LN 1.5 + 1 X 1 √ ϵk = 2 k+1 k=0 k=0 K
4rM LN 1.5 + 1 X 1 √ 2 k k=1 Z K 4rM LN 1.5 + 1 1 √ dx ≥ 2 x 1
=
k=0
k=0
k=0
k′
1.5
+1 X 1 √ k k=1 ! Z k′ +1 1.5 1 4rM LN + 1 √ 1+ dx ≤ 2 x−1 2 4rM LN 1.5 + 1 √ ′ ≤ 2 k −1 2 √ (19) ≤(4rM LN 1.5 + 1) k ′ . ′ We also note that k is the minimum integer such that ϵk ≤ δ/2 and thus we have k ′ ≤ (4rM LN 1.5 + 1)2 /δ 2 . (20) By substituting (18), (19), and (20) into (17), we have + K−1 X (k+1)T X −1 √ (λn − Sn (t)) ≤ T (g(N, δ, rM ) − k)+ ,
l K−1 X
k=0
4rM LN = 2
l
t=kT
k′ −1
1 4rM N 1.5 + 1 X √ ϵk = 2 k+1
Sl,n (t) , ∀n, (16)
where we utilize the fact that the virtual queue-lengths are non-negative. Hence, we have !+ K−1 X (k+1)T X −1 X E λn − Sl,n (t) k=0
′ kX −1
k=0
=
(18)
and
k=0
where the last step follows from the fact that λn ≤ 1. the fact that ∥Q(k ′ T )∥ ≤ ∥Q(k ′ T )∥1 PUtilizing N ′ n=1 Qn (k T ) and (12), (10) becomes 18N 74N 2.5 log + 3N 1.5 E[∥Q(kT )∥1 ] ≤ δ δ
k=0
√ =(4rM LN 1.5 + 1)( K − 1).
X
X
t=kT
l,n,m
∗ ∗ E rm µl,n,m Sl,n Il,n,m
− rm µl,n,m Sbl,n (kT )Ibl,n,m (t) . PN Select the Lyapunov function V1 (Q) ≜ 12 n=1 Q2n and consider its expected drift. In the rest of the proof, we omit the frame index kT associated with virtual queue lengths Q and schedule S without causing ambiguity. E[V1 (Q((k + 1)T ) − V1 (Q(kT ))] !2 N N X X (a) 1 X 1 E Qn + λn − Sbl,n + ϵk − Q2 ≤ 2 n=1 2 n=1 n l " !# N X X = E Qn λn + ϵk − Sbl,n n=1
+
N 1X
2 n=1
l
E λn −
!2 X l
Sbl,n + ϵk
IEEE/ACM TRANSACTIONS ON NETWORKING
N (b) X
≤
E [(λn + ϵk )Qn ] −
n=1
L X N X
12
(a)
h i E Qn Sbl,n + Hk , (22)
≤ k 0 N rM T +
l=1 n=1
k=k0 2
2
Hk 1 V1 (k0 T ) + ηk ηk0
K−1 X
where step (a) uses the fact that (max{x, 0}) ≤ x ; (b) is true for Hk ≜ N 1 + ϵ2k /2 . Adding the term ηk ∆R(kT ) on both sides of (22) and utilizing the fact that the optimal stationary randomized policy S∗ (kT ) is independent of the system state and stabilizes the PL ∗ system, i.e., E[ l=1 Sl,n (kT )] ≥ λn + δ, ∀n, we have
1 X + E Qn + ηk T max rm µl,n,m m ηk l,n k=k0 ∗ b · Sl,n − Sl,n K−1 X X (k+1)T X −1
+
E[V1 (Q((k + 1)T ) − V1 (Q(kT ))] + ηk ∆R(kT ) X X ≤ E[(λn + ϵk )Qn ] − E[Qn Sbl,n ] + Hk n
K−1 X
k=k0 l,n,m
t=kT
·
l,n
E rm µl,n,m
∗ Il,n,m − Ibl,n,m (t)
Sbl,n
(k+1)T −1
+ ηk
X
X
t=kT
l,n,m
∗ ∗ E rm µl,n,m Sl,n Il,n,m
(b)
≤ k 0 N rM T +
k=k0
− rm µl,n,m Sbl,n Ibl,n,m (t) !# X X ∗ E Qn λn + ϵk − = Hk + Sl,n n
l
" +
(k+1)T −1
E Qn + ηk
l,n
X
X
t=kT
m
∗ · Sl,n − Sbl,n
∗ rm µl,n,m Il,n,m
#
k=k0 l,n,m
∗ · Sl,n − Sbl,n
i
X (k+1)T X −1 h E rm µl,n,m l,n,m
i ∗ · Il,n,m − Ibl,n,m (t) Sbl,n ,
(23)
where the last step follows from the fact the optimal stationary randomized policy S∗ (kT ) is independent of the system state and stabilizes the system, i.e., E[Sn∗ (kT )] ≥ λn + δ, ∀n and holds for any k ≥ k0 ≜ (4rM LN 1.5 + 1)2 /4δ 2 such that ϵk0 ≤ δ. Dividing ηk on both sides of (23), we have Hk 1 E[V1 (Q((k + 1)T ) − V1 (Q(kT ))] + ∆R(kT ) ≤ ηk ηk 1 X ∗ b + E Qn + ηk T max rm µl,n,m Sl,n − Sl,n m ηk l,n
Utilizing the scheduling component of the OUTTA algorithm, we have X ∗ Qn + ηk T max rm µl,n,m Sl,n − Sbl,n
X
X
l,n,m
t=kT
m
l,n (a) X
≤
Qn + ηk T max rm µl,n,m Sel,n m
l,n
−
X
Qn + ηk T max rm µl,n,m Sbl,n m
l,n (b) X
≤
Qn + ηk T max rm µl,n,m Sel,n m
l,n
−
X
+
X
Qn + ηk T max rm µl,n,m Sbl,n m
l,n
(k+1)T −1
+
m
l,n
t=kT
h
E rm µl,n,m
i ∗ Il,n,m − Ibl,n,m (t) Sbl,n .
Qn + ηk T max rm wl,n,m (kT ) Sbl,n m
l,n
(24) Summing (24) over k = k0 , k0 + 1, . . . , K − 1 and we have kX K−1 0 −1 X Reg(KT ) = ∆R(kT ) + ∆R(kT ) k=0
t=kT
(25) where step (a) uses the fact that ηk is an increasing sequence; (b) follows from (12). Next, wefocus on the term X ∗ Qn + ηk T max rm µl,n,m Sl,n − Sbl,n .
m
l,n
k=k0
E rm µl,n,m
∗ · Il,n,m − Ibl,n,m (t) Sbl,n ,
m
t=kT
i ∗ · Il,n,m − Ibl,n,m (t) Sbl,n X h ≤ Hk + E Qn + ηk T max rm µl,n,m
+ ηk
K−1 X X (k+1)T X −1
+
X (k+1)T X −1 X h + ηk E rm µl,n,m l,n
Hk ηk
!2 kX 0 −1 1 + N k0 + ϵk 2ηk0 k=0 K−1 X 1 X E Qn + ηk T max rm µl,n,m + m ηk l,n k=k0 ∗ · Sl,n − Sbl,n
"
X
K−1 X
−
X
Qn + ηk T max rm wl,n,m (kT ) Sel,n m
l,n
X =ηk T (max rm wl,n,m (kT ) − max rm µl,n,m )Sbl,n l,n
m
m
IEEE/ACM TRANSACTIONS ON NETWORKING
+
X
(max rm µl,n,m − max rm wl,n,m (kT ))Sel,n m
l,n (c)
≤ ηk T
13
X
+
m
k=0 l,n,m
+
m
l,n (d)
≤ ηk T
X
m
rm (wl,n,m (kT ) − µl,n,m )+ Ibl,n,m (kT ) +T
∗ rm E (µl,n,m − wl,n,m (t)) Il,n,m
t=kT
{z
}
K−1 X X
i h + rm E (wl,n,m (kT ) − µl,n,m ) Ibl,n,m (kT )
k=0 l,n,m
m
{z
|
}
≜G3 (KT )
X
≤ ηk T
}
≜G2 (KT )
max rm (µl,n,m − wl,n,m (kT )) Sel,n
l,n (e)
K−1 X X (k+1)T X −1 k=0 l,n,m
X
{z
|
l,n,m
+
t=kT ≜G1 (KT )
+
(max rm µl,n,m − max rm wl,n,m (kT ))Sel,n
h i rm E (wl,n,m (t) − µl,n,m ) Ibl,n,m (t)
|
(rm wl,n,m (kT ) − rm µl,n,m )Ibl,n,m (kT )Sbl,n
l,n,m
X
K−1 X X (k+1)T X −1
+ rm (wl,n,m (kT ) − µl,n,m ) Ibl,n,m (kT )
+T
l,n,m
+ ηk T
X
K−1 X X
h i + rm E (µl,n,m − wl,n,m (kT )) Sel,n .
(28)
k=0 l,n,m
+ rm (µl,n,m − wl,n,m (kT )) Sel,n ,
(26)
|
{z
}
≜G4 (KT )
l,n,m
e where step P(a) is true for S ≜ (Sel,n )l,n ∈ arg maxS∈S l,n (Qn + ηk T maxm rm µl,n,m ) Sl,n ; (b) follows from the definition of the OUTTA algorithm; (c) uses the fact that maxm rm wl,n,m (kT ) = P r w (kT )Ibl,n,m (kT ) and maxm rm µl,n,m (kT ) = Pm m l,n,m P ∗ b m rm µl,n,m (kT )Il,n,m ≥ m rm µl,n,m (kT )Il,n,m (kT ); (d) follows from the fact that maxm=1,...,M xm − maxm=1,...,M ym ≤ maxm=1,...,M (xm − ym ); (d) uses the fact that maxm=1,...,M xm ≤ maxm=1,...,M (xm )+ ≤ PM + + m=1 (xm ) and (x) = max{x, 0}. For the term (k+1)T −1
X
X
t=kT
m
∗ rm µl,n,m Il,n,m − Ibl,n,m (t) ,
PK−1 For the term k=k0 Hk /ηk , according to the definition of ηk , we can show that K−1 X Hk √ 3 ≤ 2 KN T δ + . (29) ηk 2δ k=k0
Next, we focus on G1 (KT ), G2 (KT ), G3 (KT ) and G4 (KT ), respectively. Recall that Hl,n,m (t) is the number of times that user n is associated with AP l and uses rate rm until time slot t. Let tl,n,m,τ denote the time slot at which user n is associated with AP l and uses rate rm , where τ = 1, 2, . . . , Hl,n,m (KT ). Therefore, we have Hl,n,m (tl,n,m,τ ) = τ − 1. Let Gl,n,m,1 (KT ) ≜
utilizing the rate adaptation component of the OUTTA algorithm, we have
K−1 X −1 X (k+1)T k=0
h E (wl,n,m (t) − µl,n,m )
t=kT
i · Ibl,n,m (t)
(k+1)T −1
X
X
∗ rm µl,n,m Il,n,m − Ibl,n,m (t)
and thus G1 (KT ) =
m t=kT (k+1)T −1
X
≤
rm µl,n,m
X
X
t=kT (k+1)T −1
m
X
=
X (a) K−1
∗ Il,n,m − Ibl,n,m (t)
∗ rm wl,n,m (t) Ibl,n,m (t) − Il,n,m
(k+1)T −1
(b)
h i E (wl,n,m (t) − µl,n,m )Ibl,n,m (t)1Fl,n,m (t)
X
≤
k=0 t=kT Hl,n,m (KT )
≤E
X
(wl,n,m (tl,n,m,τ ) − µl,n,m )
τ =1
X
rm (wl,n,m (t) − µl,n,m )Ibl,n,m (t)
· 1Fl,n,m (tl,n,m,τ )
m t=kT (k+1)T −1
+
l,n,m rm Gl,n,m,1 (KT ). Then, we have
Gl,n,m,1 (KT )
X
m t=kT (k+1)T −1
+
P
X
X
t=kT
m
∗ rm (µl,n,m − wl,n,m (t))Il,n,m .
Hl,n,m X(KT ) ≤1 + E (wl,n,m (tl,n,m,τ ) − µl,n,m )
(c)
(27)
τ =2
· 1Fl,n,m (tl,n,m,τ )
Substituting (26) and (27) into (25), we have Reg(KT ) ≤ k0 N rM T +
K−1 X k=k0
+
1 N 2ηk0
k0 +
Hk ηk
kX 0 −1 k=0
(d)
≤1 +
h i E 1G l,n,m (tl,n,m,τ )
τ =2
!2 ϵk
∞ X
" Hl,n,m (KT ) X +E (wl,n,m (tl,n,m,τ ) − µl,n,m ) τ =2
IEEE/ACM TRANSACTIONS ON NETWORKING
14
#
"
· 1Fl,n,m (tl,n,m,τ )∩Gl,n,m (tl,n,m,τ ) ,
≤
p
Z Hl,n,m (KT )
6 log(KT )E 1 + 1
(30) where step (a) is true for Fl,n,m (t) ≜ {wl,n,m (t) ≥ µl,n,m } and 1{·} being an indicator function; (b) uses the definition of tl,n,m,τ ; (c) follows from the fact that wl,n,m (t) ≤ 1, ∀t ≥ 0; (d) is true for s ( ) 3 log t Gl,n,m (t) ≜ µl,n,m (t) − µl,n,m ≤ , 2Hl,n,m (t) and G l,n,m (t) being the complement of the event Gl,n,m (t). Next, we consider the second term on the right hand side (RHS) of (30).
1 √ dx x
#
q p Hl,n,m (KT ) , ≤ 2 6 log(KT )E
(33)
where step (a) uses the definition of wl,n,m (t) and Gl,n,m (t), and (b) follows from the fact that tl,n,m,τ ≤ KT and the definition of tl,n,m,τ . By substituting (33) and (32) into (30) and using the definition of G1 (KT ), we have π2 G1 (KT ) ≤ LN M rM 1 + 4 X q p E Hl,n,m (KT ) + 2rM 6 log(KT ) l,n,m
h
i
E 1G l,n,m (tl,n,m,τ ) = Pr{G l,n,m (tl,n,m,τ )} s )) ( KT −1 ( [ (a) 3 log ν µl,n,m (ν) − µl,n,m > ≤ Pr 2(τ − 1) ν=τ −1 s ( ) −1 X (b) KT 3 log ν ≤ Pr µl,n,m (ν) − µl,n,m > 2(τ − 1) ν=τ −1 Z ∞ −1 X (d) (c) KT 1 1 3 1 ≤ + dx ≤ , ≤ 3 3 3 ν (τ − 1) 2(τ − 1)2 τ −1 (x − 1) ν=τ −1 where step (a) follows from the fact that KT [−1 G l,n,m (tl,n,m,τ ) ⊂ µl,n,m (ν) − µl,n,m ν=τ −1
s >
3 log ν ; 2(τ − 1)
(b) uses the union bound; (c) follows from the ChernoffHoeffding Bound (see, e.g., [15, Fact 1]), i.e., for X1 , X2 , . . . , Xn be i.i.d. random variables with common range [0, 1] and mean µ, then for any a ≥ 0, we have ( n ) 2 1X Pr Xi ≥ µ + a ≤ e−2na , (31) n i=1 (d) is true for τ ≥ 2. Hence, the third term on the RHS of (30) can be bounded as follows. " # ∞ ∞ X X 3 π2 E 1G l,n,m (tl,n,m,τ ) ≤ , (32) = 2τ 2 4 τ =2 τ =1 P∞ where the last step use the fact that n=1 1/n2 = π 2 /6. With regard to the third term on the RHS of (30), we have " Hl,n,m (KT ) X E (wl,n,m (tl,n,m,τ ) − µl,n,m ) τ =2
3 log t l,n,m,τ ≤ E 2 2H (t ) l,n,m l,n,m,τ τ =2 Hl,n,m (KT ) X (b) p 1 √ ≤ 6 log(KT )E τ − 1 τ =2 Hl,n,m (KT )
π 1+ 4 p + 2LN M rM 6 log(KT ) s X 1 Hl,n,m (KT ) · E LN M l,n,m (b) π2 ≤LN M rM 1 + 4 p + 2rM 6LN M Smax KT log(KT ), (34) where step (a) uses the √ Jensen’s inequality and the concavity of the function x, and (b) is true since P H (KT ) ≤ KT S max and Smax is the maximum l,n,m l,n,m number of users that can be scheduled in each time slot. Next, we consider the term G2 (KT ). First, we note that G2 (KT ) K−1 X X (k+1)T X −1 ≤ rm E (µl,n,m − wl,n,m (t)) k=0 l,n,m
t=kT ∗ · Il,n,m 1F l,n,m (t)
,
(35)
where we recall that Fl,n,m (t) ≜ {wl,n,m (t) ≥ µl,n,m }. Note that for t ≤ tl,n,m,1 , we have wl,n,m (t) = 1 and thus Fl,n,m (t) happens. Therefore, we have G2 (KT ) −1 X KT X ≤rM E (µl,n,m − wl,n,m (t)) l,n,m
t=tl,n,m,1 +1 ∗ · Il,n,m 1F l,n,m (t)
(a)
≤ rM
X
KT −1 X
l,n,m t=tl,n,m,1 +1
· 1Fl,n,m (tl,n,m,τ )Gl,n,m (tl,n,m,τ )
2
≤ LN M rM
#
(a)
(a)
s
Pr µl,n,m (t) − µl,n,m ≤ −
s
X
≤rM
3 log t 2Hl,n,m (t)
−1 X τ X KT X l,n,m τ =1 ν=1 X ν
Pr
r 1 3 log τ X(i) − µl,n,m ≤ − ν i=1 2l
IEEE/ACM TRANSACTIONS ON NETWORKING
15
r X ν 1 3 log τ Pr X(i) − µl,n,m ≤ − ν i=1 2l
−1 X τ X KT X 1
(b)
≤rM
l,n,m τ =1 ν=1
τ3
−1 X KT X 1 (c) LN M rM π 2 =rM ≤ , τ2 6 τ =1
≤rM T
(36)
where step (a) follows from the definition of F l,n,m (t) and ∗ the fact that µl,n,m ≤ 1 and Il,n,m ≤ 1; (b) again uses the Chernoff-Hoeffding Bound (cf. (31)); (c) is true since PKT −1 P∞ 1/τ 2 ≤ τ =1 1/τ 2 = π 2 /6. τ =1 Next, we will derive the upper bound of G3 (KT ) and G4 (KT ). Let K−1 X h + Gl,n,m,3 (KT ) ≜ E (wl,n,m (kT ) − µl,n,m ) k=0
i
P and thus G3 (KT ) = T l,n,m rm Gl,n,m,3 (KT ). Next, we analyze the term Gl,n,m,3 (KT ). Gl,n,m,3 (KT ) K−1 i X h = E (wl,n,m (kT ) − µl,n,m )Ibl,n,m (kT )1Fl,n,m (kT )
=rM T
−1 X KT X 1 l,n,m τ =1
K−1 X (k+1)T X −1 k=0
h i E (wl,n,m (t) − µl,n,m ) Ibl,n,m (t)1Fl,n,m (t)
t=kT 2 p
q π + 2 6 log(KT )E Hl,n,m (KT ) , (37) 4 where the last inequality uses the derived upper bound on Gl,n,m,1 (kT ). Hence, we have π2 T G3 (KT ) ≤ LN M rM 1 + 4 q X p E Hl,n,m (KT ) + 2rM T 6 log(KT ) ≤1+
l,n,m 2
(a)
≤ LN M rM
1+
π 4
p T + 2LN M rM T 6 log(KT ) s X 1 · E Hl,n,m (KT ) LN M l,n,m
(b)
l,n,m k=0
≤rM T
−1 X τ X KT X l,n,m τ =1 ν=1
LN M rM T π 2 , 6
(39)
In the rest of the proof, we omit the frame index kT without introducing any confusion. ∆V (kT ) ≜ E [V ((k + 1)T ) − V (kT )|W(kT )] hp i p =E ∥Q((k + 1)T )∥2 − ∥Q(kT )∥2 W(kT ) 1 ≤ E ∥Q((k + 1)T )∥2 − ∥Q(kT )∥2 W(kT ) , 2∥Q(kT )∥ | {z } ≜∆V1 (kT )
(40) √ where the last step follows from the fact that f (x) = x is concave for x > 0 and thus f (x1 ) − f (x2 ) ≤ f ′ (x2 )(x1 − √ x2 ) = (x1 − x2 )/(2 x2 ) with x1 = ∥Q((k + 1)T )∥2 and x2 = ∥Q(kT )∥2 . Next, we consider the term ∆V1 (kT ). X ∆V1 (kT ) = E Q2n ((k + 1)T ) − Q2n (kT ) W(kT ) n
(a) X
≤
!2
E Qn + λn −
X
n
Sbl,n + ϵk
− Q2n W
l
i X X h N δ2 −2 E Qn Sbl,n W , ≤2 (λn + ϵk )Qn + 3N + 2 n
(b)
l,n
(41) where step (a) follows from the fact that (max{x, 0}) ≤ x2 for any real number x; (b) uses the fact that Sbl,n ≤ 1, λn ≤ 1 and ϵk ≤ 2δ . According to the definition of our proposed OUTTA algorithm, we have X Qn + ηk T max rm wl,n,m Sbl,n 2
m
l,n
· 1F l,n,m (kT )
≤
A PPENDIX C P ROOF OF L EMMA 1
2
π T ≤ LN M rM 1 + 4 p + 2rM T 6LN M Smax KT log(KT ), (38) where P step (a) uses the Jensen’s inequality, and (b) is true since l,m,n Hl,n,m (KT ) ≤ KT Smax and Smax is the maximum number of users that can be scheduled in each time slot. Next, we consider the term G4 (KT ). X K−1 X (a) G4 (KT ) ≤ rM T E (µl,n,m − wl,n,m (kT ))
τ2
where step (a) uses the fact Sel,n ≤ 1, ∀l, ∀n, and other inequalities in (39) are similar to those in (36). Hence, by substituting (29), (34), (36), (38), and (39) into (28), we have the desired result. √ 3 N rM T (4rM LN 1.5 + 1)2 + 2 KN T (δ + ) Reg(KT ) ≤ 2 4δ 2δ LN M rM π 2 (T + 1) N T (2δ + 1)2 (4rM LN 1.5 + 1)3 + + 4 6 16δ 2 π + LN M rM 1 + (T + 1) 4 p + 2rM (T + 1) 6LN M Smax KT log(KT )
k=0
≤
τ3
l,n,m τ =1 ν=1
l,n,m
· Ibl,n,m (kT )
−1 X τ X KT X 1
≥
X
† Qn + ηk T max rm wl,n,m Sl,n m
l,n
≥
X l,n
† Qn Sl,n ,
(42)
IEEE/ACM TRANSACTIONS ON NETWORKING
16
P where S† ≜ (Sn† )l,n ∈ arg maxS l,n Qn Sl,n . Hence, we have X X † Qn Sbl,n ≥ Qn Sl,n − ηk N LT rM , (43) l,n
l,n
where we recall that rM is the largest available rate and use the fact that wl,n,m ≤ 1, ∀n, ∀m. Substituting (43) into (41), we have X N δ2 ∆V1 (kT ) ≤ 2 (λn + ϵk )Qn + 3N + + 2ηk N LT rM 2 n i X h † (44) −2 E Qn (kT )Sl,n (kT ) W(kT ) . l,n
Note that there exists non-negative numbers β(s) with P s∈S β(s) = 1 satisfying X X λn + δ ≤ β(s) sl,n , ∀n. s∈S
l
Hence,X we have X X (λn + δ)Qn (kT ) ≤ β(s) Qn sl,n n
s∈S
≤
X
l,n
β(s) max s∈S
s∈S
=
X
X
Qn sl,n
l,n
† Qn Sl,n .
(45)
l,n
Substituting (45) into (44), we have N X ∆V1 (kT ) ≤ −2(δ − ϵk ) Qn + 3N n=1
N δ2 + 2ηk N LT rM + 2 N δ2 ≤ − 2(δ − ϵk )∥Q∥ + 3N + + 2ηk N LT rM , (46) PN2 where we use the fact that n=1 Qn = ∥Q∥1 ≥ ∥Q∥. Substituting (46) into (40), we have 1 ∆V (kT ) ≤ − 2(δ − ϵk )∥Q∥ + 3N 2∥Q∥ + 2N ϵ2k + 2ηk N LT rM 6N + N δ 2 + 4ηk N LT rM . 4V (kT ) This implies that for any ϵk ≤ δ/2, if V (kT ) ≥ Wk ≜ 6N + N δ 2 + 4ηk N LT rM )/δ, then ∆V (kT ) ≤ −δ/4. In addition, |V ((k + 1)T ) − V (kT )| = −(δ − ϵk ) +
= |∥Q((k + 1)T )∥ − ∥Q(kT )∥| (a)
≤ ∥Q((k + 1)T ) − Q(kT )∥ (b)
≤∥Q((k + 1)T ) − Q(kT )∥1 (c)
≤N max ∥Qn ((k + 1)T ) − Qn (kT )∥ ≤ 3N, n
(47)
where step (a) uses the fact that |∥x∥ − ∥y∥| ≤ ∥x − y∥ for vectors x and P y; (b) is true since ∥x∥ ≤ ∥x∥1 ; (c) is true since λn ≤ 1, l Sbl,n (kT ) ≤ 1, and ϵk ≤ δ/2 ≤ 1. R EFERENCES [1] A. Narayanan, E. Ramadan, R. Mehta, X. Hu, Q. Liu, R. A. Fezeu, U. K. Dayalan, S. Verma, P. Ji, T. Li et al., “Lumos5g: Mapping and
predicting commercial mmwave 5g throughput,” in Proceedings of the ACM Internet Measurement Conference, 2020, pp. 176–193. [2] R. Queiros, E. Almeida, H. Fontes, J. Ruela, and R. Campos, “Wi-fi rate adaptation using a simple deep reinforcement learning approach,” arXiv preprint arXiv:2202.03997, 2022. [3] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and load balancing in wireless lans using association control,” in Proceedings of the 10th annual international conference on Mobile computing and networking, 2004, pp. 315–329. [4] H. Gong and J. Kim, “Dynamic load balancing through association control of mobile users in wifi networks,” IEEE Transactions on Consumer Electronics, vol. 54, no. 2, pp. 342–348, 2008. [5] W. Li, S. Wang, Y. Cui, X. Cheng, R. Xin, M. A. Al-Rodhaan, and A. AlDhelaan, “Ap association for proportional fairness in multirate wlans,” IEEE/ACM Transactions On Networking, vol. 22, no. 1, pp. 191–202, 2013. [6] G. Athanasiou, P. C. Weeraddana, C. Fischione, and L. Tassiulas, “Optimizing client association for load balancing and fairness in millimeterwave wireless networks,” IEEE/ACM Transactions on Networking, vol. 23, no. 3, pp. 836–850, 2014. [7] M. H. Dwijaksara, W. S. Jeon, and D. G. Jeong, “A joint user association and load balancing scheme for wireless lans supporting multicast transmission,” in Proceedings of the 31st Annual ACM Symposium on Applied Computing, 2016, pp. 688–695. [8] L. Sun, L. Wang, Z. Qin, Z. Ma, and Z. Yuan, “A novel on-line association algorithm in multiple-ap wireless lan,” in International Conference on Wireless Algorithms, Systems, and Applications. Springer, 2017, pp. 890–902. [9] I.-H. Hou, “Scheduling heterogeneous real-time traffic over fading wireless channels,” IEEE/ACM Transactions on Networking, vol. 22, no. 5, pp. 1631–1644, 2013. [10] J. J. Jaramillo, R. Srikant, and L. Ying, “Scheduling for optimal rate allocation in ad hoc networks with heterogeneous delay constraints,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 5, pp. 979–987, 2011. [11] J. C. Bicket, “Bit-rate selection in wireless networks,” Ph.D. dissertation, Massachusetts Institute of Technology, 2005. [12] A. Kamerman and L. Monteban, “Wavelan®-ii: a high-performance wireless lan for the unlicensed band,” Bell Labs technical journal, vol. 2, no. 3, pp. 118–133, 1997. [13] M. Lacage, M. H. Manshaei, and T. Turletti, “Ieee 802.11 rate adaptation: a practical approach,” in Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, 2004, pp. 126–134. [14] R. Combes, J. Ok, A. Proutiere, D. Yun, and Y. Yi, “Optimal rate sampling in 802.11 systems: Theory, design, and implementation,” IEEE Transactions on Mobile Computing, vol. 18, no. 5, pp. 1145–1158, 2018. [15] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” Machine learning, vol. 47, no. 2-3, pp. 235–256, 2002. [16] A. Garivier and O. Cappé, “The KL-UCB algorithm for bounded stochastic bandits and beyond,” in Proceedings of the 24th annual conference on learning theory, 2011, pp. 359–376. [17] S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multiarmed bandit problem,” in Conference on learning theory, 2012, pp. 39–1. [18] H. Gupta, A. Eryilmaz, and R. Srikant, “Low-complexity, low-regret link rate selection in rapidly-varying wireless channels,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 2018, pp. 540–548. [19] ——, “Link rate selection using constrained thompson sampling,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 739–747. [20] F. Li, J. Liu, and B. Ji, “Combinatorial sleeping bandits with fairness constraints,” IEEE Transactions on Network Science and Engineering, 2019. [21] X. Liu, B. Li, P. Shi, and L. Ying, “An efficient pessimisticoptimistic algorithm for constrained linear bandits,” arXiv preprint arXiv:2102.05295, 2021. [22] X. Wu, J. Yang, H. Zeng, and B. Li, “Joint user association and wireless scheduling with smaller time-scale rate adaptation,” in 2023 21st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt). IEEE, 2023, pp. 223–230. [23] M. A. Qureshi and C. Tekin, “Fast learning for dynamic resource allocation in ai-enabled radio networks,” IEEE Transactions on Cognitive Communications and Networking, vol. 6, no. 1, pp. 95–110, 2019.
IEEE/ACM TRANSACTIONS ON NETWORKING
[24] ——, “Online bayesian learning for rate selection in millimeter wave cognitive radio networks,” in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 1449–1458. [25] S. S. M. Bharatula and V. Ramaiyan, “Adapting ucb for correlated arms in link rate selection for wireless channels,” in 2023 21st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt). IEEE, 2023, pp. 1–8. [26] Y. Tong, J. Fan, X. Cai, and Y. Chen, “Rate adaptation with correlated multi-armed bandits in 802.11 systems,” in 2023 IEEE/CIC International Conference on Communications in China (ICCC). IEEE, 2023, pp. 1–6. [27] H. Zhu, X. Zhang, H. Qian, and X. Luo, “Joint adaptation of rate and beamwidth for large-scale antenna systems,” in 2019 IEEE Global Communications Conference (GLOBECOM). IEEE, 2019, pp. 1–6. [28] J. Tong, S. Lai, L. Fu, and Z. Han, “Optimal frequency and rate selection using unimodal objective based thompson sampling algorithm,” in ICC 2020-2020 IEEE International Conference on Communications (ICC). IEEE, 2020, pp. 1–7. [29] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting, “Scheduling in a queuing system with asynchronously varying service rates,” Probability in the Engineering and Informational Sciences, vol. 18, no. 2, pp. 191–217, 2004. [30] L. Tassiulas and A. Ephremides, “Dynamic server allocation to parallel queues with randomly varying connectivity,” IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466–478, 1993. [31] S. Shakkottai and A. L. Stolyar, “Scheduling for multiple flows sharing a time-varying channel: The exponential rule,” Translations of the American Mathematical Society-Series 2, vol. 207, pp. 185–202, 2002. [32] B. Sadiq, S. J. Baek, and G. De Veciana, “Delay-optimal opportunistic scheduling and approximations: The log rule,” IEEE/ACM transactions on Networking, vol. 19, no. 2, pp. 405–418, 2010. [33] X. Liu, E. K. P. Chong, and N. B. Shroff, “Opportunistic transmission scheduling with resource-sharing constraints in wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 19, no. 10, pp. 2053–2064, 2001. [34] L. Zheng, D. W. Cai, and C. W. Tan, “Max-min fairness rate control in wireless networks: Optimality and algorithms by perron-frobenius theory,” IEEE Transactions on Mobile Computing, vol. 17, no. 1, pp. 127–140, 2017. [35] C. W. Tan, S. Friedland, and S. H. Low, “Fast algorithms and performance bounds for sum rate maximization in wireless networks,” IEEE/ACM Transactions on Networking, vol. 21, no. 3, pp. 706–719, 2013. [36] X. Lin and N. B. Shroff, “The impact of imperfect scheduling on crosslayer rate control in wireless networks,” in Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., vol. 3. IEEE, 2005, pp. 1804–1814. [37] L. Tassiulas, “Scheduling and performance limits of networks with constantly changing topology,” IEEE transactions on information theory, vol. 43, no. 3, pp. 1067–1073, 1997. [38] M. Lin, A. Wierman, L. L. H. Andrew, and E. Thereska, “Dynamic rightsizing for power-proportional data centers,” IEEE/ACM Transactions on Networking, vol. 21, no. 5, pp. 1378–1391, 2013. [39] M. Chen, S. C. Liew, Z. Shao, and C. Kai, “Markov approximation for combinatorial network optimization,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6301–6327, 2013. [40] V. Patil, G. Ghalme, V. Nair, and Y. Narahari, “Achieving fairness in the stochastic multi-armed bandit problem,” The Journal of Machine Learning Research, vol. 22, no. 1, pp. 7885–7915, 2021. [41] Q. Liu, W. Xu, S. Wang, and Z. Fang, “Combinatorial bandits with linear constraints: Beyond knapsacks and fairness,” in Advances in Neural Information Processing Systems. [42] M. Bernasconi, F. Cacciamani, M. Castiglioni, A. Marchesi, N. Gatti, and F. Trovò, “Safe learning in tree-form sequential decision making: Handling hard and soft constraints,” in International Conference on Machine Learning. PMLR, 2022, pp. 1854–1873. [43] M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” Synthesis Lectures on Communication Networks, vol. 3, no. 1, pp. 1–211, 2010. [44] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocation and routing for time varying wireless networks,” in IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428), vol. 1. IEEE, 2003, pp. 745–755. [45] X. Wu, B. Ji, and B. Li, “On the low-complexity of fair learning for combinatorial multi-armed bandit,” in IEEE INFOCOM 2025-IEEE Conference on Computer Communications. IEEE, 2025, pp. 1–10.
17
[46] “IEEE 802.11ad-2012,” https://standards.ieee.org/ieee/802.11ad/4527/, Accessed: 08-July-2022. [47] A. L. Imoize, A. E. Ibhaze, A. A. Atayero, and K. Kavitha, “Standard propagation channel models for mimo communication systems,” Wireless Communications and Mobile Computing, vol. 2021, no. 1, p. 8838792, 2021. [48] Networked and Information Systems Sciences Laboratory, “mmWave physical-layer real-time video transmission demonstration,” [Online]. Available: https://inss.egr.msu.edu/mmwave.html, accessed: Jun. 2026. [49] A. Eryilmaz and R. Srikant, “Asymptotically tight steady-state queue length bounds implied by drift conditions,” Queueing Systems, vol. 72, no. 3, pp. 311–359, 2012.