# User-Perceived Capacity: Theory, Computation, and Achievable Policies
## 5 The Structure of the Optimal Policy
According to the threshold-based structure, illustrated by Equations (38) and (39), we have  
\[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,\]4  
This way, four potential cases for the values of \(s^{*}\), \(\tilde{s}\), and \(\tilde{s}\) are listed as follows: (1) \(\tilde{s}=s^{*}\) and \(\tilde{s}=s^{*}\); (2) \(\tilde{s}=s^{*}+1\) and \(\tilde{s}=s^{*}\); (3) \(\tilde{s}=s^{*}\) and \(\tilde{s}=s^{*}-1\); and (4) \(\tilde{s}=s^{*}+1\) and \(\tilde{s}=s^{*}-1\). For the first three cases, we prove Equation (45) by establishing an upper bound of its left-hand side, i.e.,  
\[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,\]5 \[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,\]6  
Meanwhile, we have  
\[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,\]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),\ \ \ m=0,1,\dots,T-1,\]8  
Based on the convexity of \(V^{*}_{m+1}(q,l)\), we have  
\[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,\]9  
when \(\tilde{s}\geq\tilde{s}-1\). For the last case, i.e., \(\tilde{s}=s^{*}+1\) and \(\tilde{s}=s^{*}-1\), we prove Equation (45) by  
\[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),\]0 \[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),\]1 \[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),\]2 \[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),\]3  
The equality is given by substituting the definition of \(V^{*}_{m}(q,l)\) in Equation (45). Meanwhile, the inequality holds due to the convexity of \(P(s,l)\) over \(s\). Overall, we first assumed the convexity of the value function and proved that the optimal policy has a threshold structure. Then, we established the convexity of the value function through mathematical induction. Consequently, we have completed the proof that the optimal policy from the perspective of the queue state possesses a threshold structure. Then, we reveal the threshold structure from over the time index \(m[t]\) as follows. Lemma 2: \(V^{*}_{m}(q,l)\) _monotonically increases over \(q\)._  
Proof: We assume \(V^{*}_{m+1}(q+1,l)\geq V^{*}_{m+1}(q,l)\) inductively. It is true for \(m=T-1\) since \(V^{*}_{T}(q,l)=0\). Next, we have  
\[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),\]4 \[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),\]5where \(s=s^{*}_{m}(q+1,l)\). As such, the first equality holds since \(V^{*}_{m}(q+1,l)=Q^{*}_{m}(q+1,l,s)\) and \(V^{*}_{m}(q,l)\leq Q^{*}_{m}(q,l,s)\). This way, we prove this lemma. Theorem 4: _The thresholds of the optimal scheduling policy under different times satisfy_  
\[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),\]6  
Proof: We indicate that the optimal transmission rate increases with time-slot \(m\) in this theorem, i.e., \(s^{*}_{m}(q,l)\leq s^{*}_{m+1}(q,l)\). Furthermore, we give an intuitive explanation of how the optimal transmission rate is selected.