# User-Perceived Capacity: Theory, Computation, and Achievable Policies
## 5 The Structure of the Optimal Policy
In particular, 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),\]7  
where  
\[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),\]8  
Given the values of \(q\) and \(l\), we note that \(P(s,l)\) is increasing and convex over \(s\), while \(\bar{V}^{*}_{m+1}(q-s)\) is decreasing and convex over \(s\) based on Theorem 1 and Lemma 2. This way, we can represent the optimal transmission rate as  
\[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),\]9  
As a result, we have \(s^{*}_{m+1}(q,l)\geq s^{*}_{m}(q,l)\) when  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]0  
This statement holds based on two observations: (1) \(\mathcal{S}_{m}(q)\) removes the lower transmission rates when \(m\) is increasing, which is due to the monotonicity of \(q^{\text{ub}}_{m}\); (2) for each \(s\) satisfying \(P(s,l)-P(s-1,l)\leq\bar{V}^{*}_{m+1}(q-s+1)-\bar{V}^{*}_{m+1}(q-s)\), we have \(P(s,l)-P(s-1,l)\leq\bar{V}^{*}_{m+2}(q-s+1)-\bar{V}^{*}_{m+2}(q-s)\) as per (57). Since \(\bar{V}^{*}_{m}(q)=\sum_{l=1}^{L}\eta_{l}V^{*}_{m}(q,l)\), we show (57) by the following sufficient condition:  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]1 \[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]2 \[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]3  
where we recall that \(s^{*}=s^{*}_{m}(q,l)\). Meanwhile, the last inequality holds due to the convexity of \(V^{*}_{m+1}(q,l)\) over \(q\). Then, we reveal the threshold structure from over the channel state \(h[t]\) as follows. Theorem 5: _If the power consumption function \(P(s,h)\) satisfies_  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]4  
_for the case when \(l^{+}>l^{-}\), the order relation of thresholds over different channel states is_  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]5  
Proof: We start the proof by noticing that \(q^{\text{th}}_{m}(l^{+},s)\leq q^{\text{th}}_{m}(l^{-},s)\) means that a larger transmission rates is obtained for queue length \(q\) when the system suffers a higher channel gain. That is, \(s^{*}_{m}(q,l^{+})\geq s^{*}_{m}(q,l^{-})\). To prove this, we represent \(\tilde{s}=s^{*}_{m}(q,l^{+})\) and \(\tilde{s}=s^{*}_{m}(q,l^{-})\) and give an equivalent expression of \(\tilde{s}\geq\tilde{s}\) as  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]6  
This implies that the optimal transmission rate for the state \((q,l^{+})\) shall be selected from the set \(\mathcal{S}_{m}(q)\cap\{\tilde{s},\tilde{s}+1,\dots,\tilde{s}\}\), i.e., \(\tilde{s}\geq\tilde{s}\). We next show (61) by considering its sufficient condition:  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]7 \[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]8  
where the inequality holds due to (59). By exploiting Theorems 3-5, we finally develop an efficient method in Algorithm 3 to search thresholds for the optimal transmission policy. As presented in Algorithm 3, we can reduce the running time to update the optimal transmission rate based on the monotonicity of \(s^{*}_{m}(q,l)\) over \(q\) in line 5. Similarly, given \(q^{\text{th}}_{m}(l,s)\) for specific \(l\) and \(m\), we can constrain the transmission rates of states with \(\tilde{l}<l\) and \(\tilde{m}<m\) in lines 9 and 11. As such, the complexity of Algorithm 3 is \(\mathcal{O}(S+1)\) in the best case, while it is equal to \(\mathcal{O}((B+1)^{2}L^{2}(S+1)T)\) in the worst case, the same as that in Algorithm 2.