# User-Perceived Capacity: Theory, Computation, and Achievable Policies
## 5 The Structure of the Optimal Policy  
In this section, we develop a series of theoretical results for the structural properties of the optimal scheduling policy. Note that \(B\) packets arriving at the beginning of each period must be transmitted within one arrival period. Thus, we only need to consider the data transmission for one period, i.e., \(T\) time-slots. Within one period, we first represent the constraint on the user-perceived capacity, i.e., Equation (25b) by introducing the upper and lower bounds of the queue length. In particular, they are expressed as  
\[ \begin{cases}q[m]\leq\left\lfloor B-\frac{Bm}{T}\right\rfloor&\text{upper bound},\\ q[m]\geq(B-Sm)^{+}&\text{lower bound},\end{cases}  \tag{33}\]through which we define \(q^{\text{lb}}_{m+1}=(B-S(m+1))^{+}\) and \(q^{\text{ub}}_{m+1}=\left\lfloor B-\frac{B(m+1)}{T}\right\rfloor\). Consequently, the feasible region of the transmission rate in time-slot \(m\) is given by  
\[\mathcal{S}_{m}(q[m])=\Big{\{}s[m]\in\{0,1,\dots,S\}\mid\max\{q[m]-q^{\text{ub} }_{m+1},0\}\leq s[m]\leq\min\{q[m],S\}\Big{\}}. \tag{34}\]  
Furthermore, we represent the data transmission as a finite horizon Markov decision process, which is constructed as follows:  
* **State:** The pair of the queue length and channel state \((q[m],h[m])\), where \(q^{\text{lb}}_{m}\leq q[m]\leq q^{\text{ub}}_{m}\) and \(h[m]\in\{h_{1},\dots,h_{L}\}\) with \(h_{1}<h_{2}<\dots<h_{L}\). * **Action:** The transmission rate \(s[m]\in\mathcal{S}_{m}(q[m])\). * **Transition:** The queue length evolves according to Equation (6) and the channel state is _i.i.d._ over time, following the probability distribution \(\{\eta_{1},\dots,\eta_{L}\}\). * **Value function:** \[V^{*}_{m}(q,l)=\min_{s\in\mathcal{S}_{m}(q)}P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{* }_{m+1}(q-s,l),\ \ \ m=0,1,\dots,T-1,\] (35) where \(V^{*}_{T}(q,l)=0\) for each \(q\) and \(l\). * **Scheduling policy:** \[s^{*}_{m}(q,l)=\arg\min_{s\in\mathcal{S}_{m}(q)}Q^{*}_{m}(q,l,s)=\arg\min_{s\in \mathcal{S}_{m}(q)}P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{*}_{m+1}(q-s,l),\] (36) where the item \(P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{*}_{t}(q-s,l)\) is referred to as the Q-value function, denoted by \(Q^{*}_{m}(q,l,s)\). According to theoretical results for finite horizon MDPs [66], considering the scheduling policy in (36) will not lose the optimality for the average minimizing problem (12). Furthermore, the policy in (36) can be re-written in the form of the probabilistic policy \(\mathbf{F}\) in Section 3.1 by setting \(f^{s}_{q,m,j}=\mathds{1}\{s=s^{*}_{m}(q,l)\}\). Then, we solve the finite horizon MDP by the dynamic programming in Algorithm 2 with the complexity \(\mathcal{O}((B+1)^{2}L^{2}(S+1)T)\). By analyzing Algorithm 2, we further have the following theorem. ```
1:\(m\gets T-1\)
2:for\(q^{\text{lb}}_{m}\leq q[m]\leq q^{\text{ub}}_{m}\), \(h[m]\in\{h_{1},\dots,h_{L}\}\)do
3:\(V^{*}_{m}(q,l)=\min_{s\in\mathcal{S}_{m}(q)}P(s,l)\)
4:endfor
5:Recursion: For each time step \(m\) from \(T-2\) to \(0\), the value function \(V^{*}_{m}(q,l)\) is updated using the Bellman equation. 6:for\(m\in\{T-2,T-3,\dots,0\}\)do
7:\(V^{*}_{m}(q,l)=\min_{s\in\mathcal{S}_{m}(q)}P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{* }_{m+1}(q-s,l)\)
8:endfor
9:Policy Extraction: After computing the value functions for all time steps, the optimal policy can be extracted by choosing the action that maximizes the value function at each state and time step. 10:for\(m\in\{T-1,T-2,\dots,0\}\)do
11:for\(q^{\text{lb}}_{m}\leq q[m]\leq q^{\text{ub}}_{m}\), \(h[m]\in\{h_{1},\dots,h_{L}\}\)do
12:for\(s\in\mathcal{S}_{m}(q)\)do
13:\(Q^{*}_{m}(q,l,s)\gets P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{*}_{m+1}(q-s,l)\)
14:endfor
15:\(s^{*}_{m}(q,l)\leftarrow\arg\min_{s\in\mathcal{S}_{m}(q)}Q^{*}_{m}(q,l,s)\)
16:endfor
17:endfor
```  
**Algorithm 2** Dynamic programming for finite horizon Markov decision processes  
**Theorem 3**. : _The optimal scheduling \(s^{*}_{m},\ m=0,\ldots,T-1\), can be re-written as a series of thresholds \(q^{th}_{m}(l,s),\ \forall m,h,s\).