## 3 Multi-Armed Bandit Algorithms Using Logarithmic Rates
### KL-UCB Using Logarithmic Rates  
We first introduce an MAB algorithm for the transmission rate control in CSMA/CA wireless networks using the logarithmic values of the transmission rates based on KL-UCB. We call it KL-UCB-logR. We assume that there are \(K\) MCS levels, of which one can be selected for each (physical) transmission. Each transmission can be for aggregated (multiple) packets if the frame aggregation is enabled; otherwise, it is for one packet. Algorithm 1 shows the pseudocode of the algorithm.  
At the initial stage of Algorithm 1, an empty list \(R_{i}\) is assigned for each MCS level \(i\) to record the rewards obtained when the MCS level is used for transmissions. After the initial \(K\) steps, for each transmission at time \(t\), the algorithm computes the total number of transmitted packets \(N\) that occurred during the sliding window time \(\tau\). The time interval defined by the sliding window \(\tau\) is between \(t-\tau\) and \(t\), i.e., \([t-\tau,t)\) if time \(t\) is greater than \(\tau\); otherwise it is \([0,t)\). Note that if \(\tau\) is set as \(\tau\geq t\), the sliding window is disabled and the time interval of interest is always \([0,t)\).  
In addition, the algorithm computes the sum of the rewards (\(S_{i}\)) and number of packets transmitted (\(N_{i}\)) with each of the MCS level \(i\) during \(\tau\). Subsequently, they are used to estimate the success probability \(p_{i}(t)\) of each MCS level, as shown in line 1. The configuration parameter \(c\) in line 1 is set to one by default. The function \(d(\cdot,\cdot)\) computes the Bernoulli KL divergence as in Equation (3). Line 1 shows that the expected throughput of each \(i\) is computed using the logarithmic value of its transmission rate.  
Then, an MCS level \(i\) with the maximum expected throughput is selected for transmission. Ties are broken arbitrarily.  
After each transmission, if the data sender receives an ACK or BAck frame before the timeout period expires, the transmission is considered a success and the number of successfully delivered packets in the transmission is appended to \(R_{i}\); otherwise, 0 is appended. Finally, the time at which the outcome is observed is recorded using a separate list (not shown in the pseudocode) to keep track of all the events during the sliding window time.  
If the nominal transmission rates are used directly without the logarithm for computing the expected throughput in line 15, we call the algorithm KL-UCB-R for performance comparison. KL-UCB-R may appear similar to the KL-R-UCB algorithm in [36]. However, KL-UCB-R uses a slightly different formula to compute \(p_{i}(t)\) in line 13, and KL-UCB-R explicitly describes how the sliding window is used. In addition, KL-UCB-R accommodates the use of the frame aggregation.  
```
1:for each MCS level \(i\in\{0,...,K-1\}\)do
2:\(R_{i}\leftarrow[]\)\(\triangleright\) Prepare empty lists
3:endfor
4:\(step\gets 0\)
5:for each transmission at time \(t\)do
6:if\(step\leq K-1\)then
7: use\(i=step\) for transmission and wait for the outcome.
8:else
9:\(N\) = number of all the transmitted packets during \([\max(0,t-\tau),t)\).
10:for each \(i\)do
11:\(S_{i}=\) sum(\(R_{i}\) during \([\max(0,t-\tau),t)\)).
12:\(N_{i}\) = number of the transmitted packets using \(i\) during \([\max(0,t-\tau),t)\).
13:\(p_{i}(t)=\max\{q\in[0,1]\): \(d(S_{i}/N_{i},q)\leq(\log(N)+c\cdot\log(\log(N)))/N_{i}\}\).
14:endfor
15: use \(i=\) argmax\({}_{i}(\log(r_{i})\cdot p_{i}(t))\) for transmission and wait for the outcome.
16:endif
17:if success then
18: append the number of successfully delivered packets to \(R_{i}\).
19:else
20: append 0 to \(R_{i}\).
21:endif
22: record the time at which the outcome is observed.
23:\(step\gets step+1\)
24:endfor
```  
**Algorithm 1** KL-UCB-logR algorithm