Joint Link Rate Selection and Channel State Change Detection in Block-Fading Channels

In this work, we consider the problem of transmission rate selection for a discrete time point-to-point block fading wireless communication link. The wireless channel remains constant within the channel coherence time but can change rapidly across blocks. The goal is to design a link rate selection strategy that can identify the best transmission rate quickly and adaptively in quasi-static channels. This problem can be cast into the stochastic bandit framework, and the unawareness of time-stamps where channel changes necessitates running change-point detection simultaneously with stochastic bandit algorithms to improve adaptivity. We present a joint channel change-point detection and link rate selection algorithm based on Thompson Sampling (CD-TS) and show it can achieve a sublinear regret with respect to the number of time steps $T$ when the channel coherence time is larger than a threshold. We then improve the CD-TS algorithm by considering the fact that higher transmission rate has higher packet-loss probability. Finally, we validate the performance of the proposed algorithms through numerical simulations.


I. INTRODUCTION
Selecting a proper transmission rate that adapts channel conditions is important efficient communications in the current wireless systems, i.e., devices using IEEE802.11 standards [1], [2]. Considering the fact that precise channel state information (CSI) feedback is supported by few 802.11 devices [3] but ACK/NACKs of the transmission outcomes are always available to the transmitter, rate sampling approaches [4], [5] that select transmission rate based on historical acknowledgments have been widely used. Online sequential decision making frameworks such as stochastic bandit provide efficient solutions to optimize rate sampling methods [6] when the channel statistics remains constant. However, the use of high frequency spectrum (e.g., mmWave) in the 5G wireless communication systems [7] causes CSI to change more frequently than in conventional spectrums. This motivates us to incorporate changepoint detection algorithms into rate sampling link rate selection strategy in order to improve the cumulative link throughput.
Employing stochastic bandit algorithms for link rate selection in slow and fast fading channels have been widely studied previously. Gupta [6]. The algorithm is then applied to the joint selection of modulation and transmission rate [8]. By utilizing the correlations between transmission success probabilities and transmission rates, [9]- [11] designed modified TS algorithms that can further decrease the expected cumulative throughput regret in higher confidence intervals. The aforementioned techniques are useful under the assumption that channel statistics remain constant, which is true for both slow are fast fading scenarios. However, when channels experience abrupt changes in block fading scenarios and the channel statistics become non-stationary, those algorithms may suffer from slow adaptation. Although TS with a sliding window is proposed in [8] to overcome this issue and is shown to achieve a high cumulative throughput empirically, theoretic evaluations on regret performance are not well addressed.
Designing fast adaptive stochastic bandit algorithms in quasistatic environments are studied in [12], [13]. It is shown that by running a simple CD algorithm to control the clearance of historical data, the expected regret of Upper Confidence Bound (UCB) algorithm in the quasi-static environment can be improved. However, these algorithms are designed for general bandit problems and can be improved when applied to link rate selection scenarios.
Employing change-point detection algorithms to design efficient transmission schemes for block-fading and quasi-static channels has recently been considered in [14]. The key is to estimate channel change points accurately from the high dimensional received signals, and then re-estimate the new CSI and re-design beamforming strategies for channel throughput maximization. Notice that their algorithm relies on the sparse structure of the received signal in angular domain subspace, which requires the receiver to possess large-scale uniform antenna arrays. Therefore, the algorithm cannot be applied directly to mobile devices with a small number of antennas.
To overcome the aforementioned challenges, in this work, we investigate the problem of link rate selection in block fading quasi-static channels. The distribution of channel change points and the probabilities of successful transmission are unknown. The goal is to design a transmission strategy that attempts to maximize the cumulative channel throughput by using historical transmission outcomes. We present an efficient change-point and online decision making algorithm, and then derive the corresponding expected regret upper bound. We then improve the empirical performance of the algorithm by constraining the TS posteriors to lay in a set that can characterize the relationship between transmission success probabilities and transmission rates.
The rest of the paper is organized as follows: in Section II we introduce the system model and formulate the overall optimization problem. Section III proposes a joint channel change-point detection and Thompson Sampling based link rate selection algorithm (CD-TS). We then provide theoretic analysis of the expected regret upper bound. Section IV improves the proposed CD-TS by constraining the sampling posteriors. Section V validates the proposed algorithms via numerical simulations and Section VI draws the conclusion.

II. PROBLEM FORMULATION
We consider a communication rate selection problem for a discrete-time point-to-point wireless channel and let t ∈ {1, · · · , T } denote the index of the current slot. The communication channel between the transmitter and the receiver is quantized into Q < ∞ states, and let h(t) ∈ Q = {1, · · · , Q} denote the current quantized channel state. The channel h(t) experiences block fading and during slot [0, T ], there exists M (M ≥ 1) channel state change points, whose timestamps are denoted by {ν 1 , ν 2 , · · · , ν M }. The channel state h(t) remains the same during the interval between two change points, i.e., h(t 1 ) = h(t 2 ), ∀t 1 , t 2 ∈ [ν m , ν m+1 − 1] but changes rapidly before and after the change point, i.e., h(ν m −1) = h(ν m ), ∀m. The difference between two nearby change points is lower bounded by the channel coherence time L, i.e., ν i+1 − ν i ≥ L, where L 1 is predetermined by the physical channel and mobility characteristics.
In each slot t, the transmitter chooses a transmission rate r i(t) ∈ R = {r 1 , · · · , r R } indexed by i(t). The wireless channel is erroneous and let X(t) ∈ {0, 1} be the indicator function of whether the transmission in slot t succeeds: if X(t) = 1, all of the r i(t) transmitted packets will be successfully received by the end of slot t; otherwise, all r i(t) packets will be lost due to decoding error [6], [9]. The transmission success probabilities depend on the current transmission and channel state, since using higher transmission rate will lead to higher packet-loss probabilities. Therefore, we assume that the transmission success probability follows a Bernoulli distribution with parameter E[X(t)] = θ h(t),i(t) . With no loss of generality, assume that transmission rates are arranged in an increasing order, i.e., r 1 < · · · < r R , and therefore 1 > θ q,1 > · · · > θ q,R > 0. The distribution of X(t) is independent of transmission outcome of other slots X(t ), ∀t = t. At the end of slot t, the receiver sends X(t) to the transmitter without error.
The goal of this research is to maximize the cumulative throughput by designing a link rate selection strategy π that chooses i(t) based on historical transmissions. The problem is organized as follows: (1) Maximizing (1) can be cast in the stochastic bandit framework. However, traditional bandit algorithms assume the distribution of reward remains constant across all the slots. Therefore, adopting these algorithms directly to the quasi-static channel link rate selection may cause large regret, because historical data cannot reflect the current best rate after the channel changes. To overcome this issue, we propose to run a change-point detection (CD) algorithm simultaneously with stochastic bandit to control the clearance of historic data and therefore, improve adaptivity in block-fading channels.
AssumeT = {τ 1 ,τ 2 , · · · } is the detected channel change points sequence and let c(t) = max m {τ m |τ m ≤ t} denote the time-stamp of the most recently detected change point before slot t. We use N i (t), s i (t) and f i (t) to denote the recorded number of total transmissions, success and failure times using Channel change points detection algorithms to calculate {τ m } are proposed in Section III-B. The two parts of the algorithm are synthesized in Section III-C.

A. Thompson Sampling for link rate selection
Consider that in slot t, selecting rate i has succeeded for s i (t) and failed for f i (t) times from slot c(t) + 1 to t − 1. If the channel has not changed after c(t), the posterior distribution of transmission success probability λ i = θ h(t),i follows a Beta distribution parameterized by s i (t) and f i (t). The probability density function of such Beta distribution is: where The Thompson Sampling algorithm for link rate selection is as follows: first sampleλ i ∼ Beta(s i (t) + 1, f i (t) + 1) and then choose rate i(t) = arg max iλi r i for transmission.

B. Change-Point Detection
Recall that CSI changes lead to variations in transmission success probabilities of every transmission rate. Therefore, we attempt to detect past channel changes by comparing the empirical transmission success probability of the latest w transmission outcomes and the second latest w transmission outcomes of a transmission rate. We require there is at least a specific transmission rate indexed by i cd that is selected every F slots, so that the change-point detection algorithm can always be run when needed. In this work, we select i cd to be the rate with the highest historical empirical throughput during slot To efficiently implement the change-point detection, we use W i (k) to record the k-th transmission outcome of using rate i. If rate i(t) has been selected more than 2w times, i.e., N i (t) > 2w, we run a CD algorithm by comparing the mean of the latest w outcomes of using rate i(t) (denoted by M 1 ) and the second latest w transmission outcomes (denoted by M 2 ), where M 1 and M 2 can be computed by: If the absolute difference between the two mean values is larger than a predetermined threshold b, i.e., |M 2 − M 1 | > b, we conclude that a channel change point occurs recently and append t to the detected change points setT .

C. Algorithm Design
We then synthesize our proposed algorithm CD-TS by combining the aforementioned CD and TS parts together.
First we initialize the historical transmission records N i (0) = 0, s i (0) = 0, f i (t) = 0, ∀i ∈ R and set c(1) = 0. Then in each slot t, we perform a joint link rate selection and channel change-point detection as follows: • Transmission Rate Selection: If t = c(t) + kF, ∀k ∈ N + , then we should transmit with rate indexed by Ni(c(t)+F ) r i for efficient channel change-point detection; Otherwise, we select transmission rate based on Thompson Sampling. We sampleλ i ∼ Beta(s i (t) + 1, f i (t) + 1) and treat it as an estimation of transmission success probability using rate i. Then we transmit with i(t) = arg max iλi r i , observe the transmission outcome X(t) and update N i (t+

D. Regret Analysis
We evaluate the performance of the proposed CD-TS algorithm via the cumulative expected throughput regret against the optimum link rate selection algorithm when the precise CSI is known. Denote i * (h) arg max i r i θ h,i as the index of optimal rate when the channel state is h. By definition, the cumulative regret in non-stationary environment denoted by R T , is the difference between the expected cumulative throughput of using for {i(t)} T t=1 chosen by our algorithm and the optimum rate using {i * (h(t))} T t=1 , i.e., A lower regret (4) implies a higher expected cumulative throughput and indicates the algorithm adapts faster to the block fading channel. To compute the expected regret of the proposed algorithm, we first introduce the following lemma, the proof is provided in Appendix A: Lemma 1: Consider the channel remains stable during slot 1 ∼ T , i.e., h(t) = h. Let ∆ i = r i * (h) θ h,i * (h) − r i θ h,i be the expected throughput difference between choosing rate i and the optimum rate i * (h), the expected regret of the proposed algorithm for the this time invariant channel, denoted byR T can be upper bounded by the following inequality for any ∈ (0, 1]:R where coefficient B is a constant unrelated to T , and D KL (p, q) = p log p q +(1−p) log 1−p 1−q is the KL divergence. With Lemma 1, we proceed to our main theorem, whose proof is provided in B:

IV. IMPROVING CUMULATIVE THROUGHPUT WITH CONSTRAINED THOMPSON SAMPLING
In this section, we improve the performance of CD-TS by replacing TS with Constrained Thompson Sampling (CoTS) algorithm proposed in [9]. CoTS can achieve a lower regret performance by utilizing the fact that choosing higher transmission rate will have lower success probability. Recall that θ h,i is the transmission success probability if the channel state h(t) = h and r(t) = r i . To exploit the relationship between {θ h,i } N i=1 for better exploration, we first define set Θ, where the element of each vector λ ∈ Θ is monotonically decreasing: Thus, for any fixed channel state h(t) = h, the transmission success probability θ h,: should belong to set Θ due to the fact that transmitting at higher rate is more likely to get packetlosses. Then we sampleλ(t) = [λ 1 , · · · ,λ N ] jointly from: where Z is a normalizing constant.
To implement CoTS during link rate selection, we first sampleλ i ∼ Beta(s i (t) + 1, f i (t) + 1) independently for each rate. Ifλ ∈ Θ we stop and proceed to select the rate i(t) = arg max iλi r i for transmission. Otherwise we keep samplingλ i ∼ Beta(s i (t) + 1, f i (t) + 1) untilλ ∈ Θ.

V. SIMULATION RESULTS
In this section, we provide numerical simulations to validate the performance gain of our proposed algorithms. We consider link rate selection settings in IEEE802.11a/g systems [15], where we can choose from 8 possible transmission rates from set R = [6,9,12,18,24,36,48,54] (in Mbps) [6]. Suppose the channel is quantized into 3 states and the transmission success probabilities are shown in TABLE I. The cumulative regret is computed for T =3000 slots with coherence time L ≥ 750 and M = 3 change points, and the time-stamps of the channel change points are marked in the figure. The expected regret is computed by taking the average of 100 runs.  Fig. 1 plots the expected cumulative regret and Fig. 2 plots the cumulative throughput of the proposed CD-TS, CD-CoTS, CD-UCB [12] and pure Thompson Sampling [9] algorithm with no change-point detection. The expected throughput/regret are computed by taking the average over 100 runs. From the Fig. 1, the proposed CD-TS and CD-CoTS achieve small regret by incorporating change-point detection into stochastic bandit framework. This is because when the channel changes, the proposed CD-TS and CD-CoTS algorithms can efficiently detect the changes, and they can fit quickly to newly changed channel state by throwing away historical data, while the pure TS algorithm without change-point detection algorithm does not clear up historical data and therefore experiences linear regret once the channel changes. Compared with CD-UCB algorithm, the proposed CD-TS and CD-CoTS algorithms can further reduce the cumulative throughput regret. The decrease in cumulative regret implies that the proposed CD-TS and CD-CoTS algorithms can achieve higher cumulative throughput as depicted in Fig. 2. Compared with the CD-TS algorithm, CD-CoTS algorithm achieves a smaller cumulative regret and higher cumulative throughput empirically by taking the non-increasing characteristics of transmission success probabilities into account. In this paper, we study rate sampling based link rate selection problem in block fading channel. We propose a CD-TS algorithm that detects abrupt channel change points by using a sliding window and then choose the best transmission rate based on Thompson Sampling (CD-TS). We show that, theoretically, the proposed CD-TS can achieve a sub-linear regret with respect to the total number of time steps when the channel coherence time is above a certain threshold. We then proceed to improve CD-TS by sampling packet-loss probabilities of different rates from a constrained posterior set, in which higher transmission rates have higher packet-loss probabilities. Simulation results show that, by detecting channel change points and performing adaptive link rate selection jointly, the proposed CD-TS achieves a smaller cumulative regret and higher cumulative throughput. The proposed CD-CoTS algorithm further improves CD-TS empirically by taking the distribution of transmission success probabilities into account.
Future work includes theoretic analysis of the CD-CoTS algorithm and extending both CD-TS/CD-CoTS to multi-users scenario with block fading channels. Moreover, currently the selection of threshold b and window size w depend on time length T and the number of change points M . It will be of interest to design algorithms that can achieve sub-linear regret without knowledge of T and M .

APPENDIX A PROOF OF LEMMA 1
For time invariant channel with fixed channel state h, let ω be a sample path andT = {τ 1 (ω), · · · } are the time slots of detected channel change points on the sample path. For simplicity, denote i * = i * (h) = arg max i r i θ h,i to be the optimum transmission rate. LetR T (ω) be the cumulative expected throughput regret of sample path ω for the timeinvariant channel, i.e., Since there is no channel change points before slot T , event F = {ω :τ 1 (ω) < T } denotes the CD algorithm raises at least one false alarm before T . By conditional expectation, we can decompose R T into: We proceed to bound each item on the RHS respectively. To upper bound the first item Pr(F)E[R T (ω)|F], we introduce Lemma 2 to upper bound the probability of false alarm p FA in each slot. The proof of which is a direct application of Hoeffding bound and is omitted due to space limitations.
Lemma 2: In each slot t, the probability that a false alarm raises can be upper bounded by: Since we can run the change-point detection algorithm for at most T times from slot 1 to T , by union bound we can upper bound Pr(F) by: Plugging the above equations into the first term on the RHS of (8), we have: Next we proceed to upper bound the second item Pr(F c )E[R T (ω)|F c ]. To do this, let policyπ be algorithm without a change-point detection, i.e., in each slot select i(t) based on Thompson Sampling and transmit with rate i cd every F slots. Notice that for ω ∈ F c , transmission strategy obtained by the proposed CD-TS algorithm andπ is exactly the same. Therefore: where (a) is obtained because regret is non-negative. Then according to [6,Theorem 1], the regret caused by TS R TS ) can be upper bounded by: where and D KL (p, q) = p log p q +(1−p) log 1−p 1−q , ∆ i = r i * (h) θ h,i * (h) − r i θ h,i are the KL divergence and difference in expected throughput, respectively. The regret caused by frequent sample i cd can be simply upper bounded by: Plugging the above items into (12) and then into (8) yields Lemma 1.

APPENDIX B PROOF OF THEOREM 1
The change-point detection algorithm guarantees after the latest change point has been detected for 2wF slots, rate i cd can be selected at least 2w times for runnning change point detection algorithm. Denote M m := {ω :τ m > v m + 2wF } to be the event that the proposed algorithm does not detect change point m after 2wF slots. Then by properties of conditional expectation, the regret can be upper bounded by: where δ min min h,h ,i |θ h,i − θ h ,i | is the minimum absolute difference of transmission success probability. The proof is provided in Appendix D Let T m = ν m − ν m−1 be the duration of the m-th stationary period. Notice that for eachτ 1 , the expected regret E[Rτ 1+1:T (ω)|M c 1 ] = R T −τ1 . Repeating the manipulation in (14) for R T −τ1 and finally we have: PluggingR Tm from Lemma 1 into the equation, we have: Next, we discuss parameter tuning problems to achieve a sub-linear expected regret. We simply set b = 1 2 δ min for easy implementations. To guarantee 2M T exp − w(δmin−b) 2 2 ≤ C 1 and 2M T 2 exp − wb 2 2 ≤ C 2 , we require w to satisfy: For simplicity, we choose C 2 = 2 √ M T and let w = 12 δ 2 min log M T so that the first and second item on the RHS of (17) are sub-linear with respect to T . Achieving a total sub-linear regretR T then requires M T /F and M wF to be sub-linear. To achieve this, we set F = (M T ) α (α > 0) so that M T /F is sublinear to T . If the channel coherence time L satisfies: L/2 ≥ 2wF = 24 may happen. By using the union bound we have: where the last inequality is obtained by Hoeffding inequality.

APPENDIX D PROOF OF LEMMA 3
Suppose the channel in the m-th stationary period is h and denote δ = |θ h,i cd − θ h ,i cd |. If event M m happens, i.e., |M 1 − M 2 | > b. Therefore, since change point m is not detected, it can be conducted that either event |M 1 − θ i cd ,h | > δ−b 2 or event |M 2 − θ h,i cd | > δ−b 2 must happen. By using the union bound and Hoeffding inequality we have: Recall that δ min = min h,h ,i |θ h,i − θ h ,i | be the minimum absolute difference of transmission success probability, by taking the minimum on both sides of (20), we have: