# User-Perceived Capacity: Theory, Computation, and Achievable Policies
## 5 The Structure of the Optimal Policy
That is,_  
\[s^{*}_{m}(q,l)=s\ \ \text{if}\ q^{th}_{m}(l,s-1)<q\leq q^{th}_{m}(l,s), \tag{37}\]  
_where the thresholds satisfy \(q^{th}_{m}(l,s-1)\leq q^{th}_{m}(l,s)\) for all \(s=0,\ldots,S\). Meanwhile, \(q^{th}_{m}(l,-1)=-1\) and \(q^{th}_{m}(l,S)=B\)._  
Proof. : We prove the threshold-based structure of the optimal policy by induction. Assuming that \(V^{*}_{m+1}(q,l)\) is convex over \(q\), we demonstrate the thresholds of the optimal policy at time-slot \(m\). After that, the threshold-based structure can induce to the convexity of \(V^{*}_{m}(q,l)\). Specifically, the convexity of \(V^{*}_{m+1}(q,l)\) holds for \(m=T-1\) due to \(V^{*}_{T}(q,l)=0\). For time-slot \(m\), we first represent the threshold-based structure by the following two assertions:  
\[Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q,l,s^{*}-\delta)\Rightarrow Q^{*}_{m}(q+1,l,s^{*})\leq Q^{*}_{m}(q+1,h,s^{*}- \delta), \tag{38}\] \[Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q,l,s^{*}+\delta)\Rightarrow Q^{*}_{m}(q+1,l,s^{*}+1)\leq Q^{*}_{m}(q+1,h,s^{*}+1+ \delta), \tag{39}\]  
where \(s^{*}=s^{*}_{m}(q,l)=\arg\min_{s\in\mathcal{S}_{m}(q)}Q^{*}_{m}(q,l,s)\). (For completeness, we set \(Q^{*}_{m}(q,l,s)=+\infty\) for \(s\
otin\mathcal{S}_{m}(q)\) and \(V(q,l)=+\infty\) for \(q<q^{\text{lb}}_{m}\) or \(q>q^{\text{ub}}_{m}\).) Based on the definition of the optimal policy in Equations (36), (38) and (39) implies that the optimal transmission rate \(\tilde{s}=\arg\min_{s\in\mathcal{S}_{m}(q+1)}Q^{*}_{m}(q+1,l,s)\) for the state \((q+1,l)\) satisfies \(s^{*}\leq\tilde{s}\leq s^{*}+1\). That is, the optimal transmission rate is monotonically increasing over \(q\) for each given \(h\) and \(m\), through which we can derive the threshold-based structure in Theorem 1. Next, we prove Equations (38) and (39) based on the convexity of \(V^{*}_{t+1}(q,l)\) and \(P(s,l)\). For Equation (38), it suffices to show that  
\[Q^{*}_{m}(q+1,l,s^{*})-Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q+1,l,s^{*}-\delta)- Q^{*}_{m}(q,l,s^{*}-\delta) \tag{40}\]  
when \(Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q,l,s^{*}-\delta)\). Note that \(Q^{*}(q,l,s)=P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{*}_{m+1}(q-s,l)\) is given based on the expression of \(Q^{*}(q,l,s)\) in (36). As such, we can re-write (38) as  
\[\sum_{l=1}^{L}\eta_{l}\big{[}\big{(}V^{*}_{m+1}(q-s^{*}+1,l)-V^{* }_{m+1}(q-s^{*},l)\big{)}\big{]}\] \[\leq \sum_{l=1}^{L}\eta_{l}\big{[}\big{(}V^{*}_{m+1}(q-s^{*}+\delta+1,l)-V^{*}_{m+1}(q-s^{*}+\delta,l)\big{)}\big{]}. \tag{41}\]  
According to the convexity of \(V^{*}(q,l)\), \(V^{*}_{m+1}(q-s^{*}+1,l)-V^{*}_{m+1}(q-s^{*},l)\leq V^{*}_{m+1}(q-s^{*}+ \delta+1,l)-V^{*}_{m+1}(q-s^{*}+\delta,l)\) holds for any \(l\). Based on this, Equation (38) has been proven. Similarly, we demonstrate Equation (39) by considering its sufficient condition:  
\[Q^{*}_{m}(q+1,l,s^{*}+1)-Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q+1,l,s^{*}+1+ \delta)-Q^{*}_{m}(q,l,s^{*}+\delta). \tag{42}\]  
when \(Q^{*}_{m}(q,l,s^{*})\leq Q^{*}_{m}(q,l,s^{*}+\delta)\). Note that \(Q^{*}(q,l,s)=P(s,l)+\sum_{l=1}^{L}\eta_{l}V^{*}_{m+1}(q-s,l)\) is given based on the expression of \(Q^{*}(q,l,s)\) in (36). As such, we can re-write (39) as  
\[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,\]0 \[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,\]1  
Consequently, it is equivalent to  
\[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,\]2This assertion is true due to the convexity of \(P(s,l)\) over \(s\). Finally, we prove the convexity of \(V^{*}_{m}(q,l)\) over \(q\), 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,\]3  
Recalling that \(s^{*}=s^{*}_{m}(q,l)\), we have \(V^{*}_{m}(q,l)=Q(q,l,s^{*})\). Likewise, we represent \(\tilde{s}=s^{*}_{m}(q+1,l)\) and \(\tilde{s}=s^{*}_{m}(q-1,l)\).