# Energy Efficient Policies for Data Transmission in Disruption Tolerant Heterogeneous IoT Networks
## 4 Transmission Policy
```
0:\(\mu\in\mathcal{M}\)
1: Initialize \(J_{\mu}(\cdot)\) arbitrarily
2:\(r\gets 0\)
3:Function policy_evaluation(\(\mu\), \(J_{\mu}\), \(r\))
4:if\(r<r_{\max}\)then
5:\(J_{\mu}^{\prime}(i)\gets g(i,\mu(i))+\gamma\sum_{i=0}^{n}p_{ij}(\mu(i))J_{ \mu}(j)\), for all \(i\in S\)
6: policy_evaluation(\(\mu\), \(J_{\mu}^{\prime}\), \(r+1\))
7:else
8: {\(r\) is equal to \(r_{\max}\)}
9: Return \(J_{\mu}\)
10:endif
```  
**Algorithm 1** Approximate Policy Evaluation  
The OPI algorithm is presented in Algorithm 2. The major operation of the OPI algorithm, besides calling APE, is presented in Line 3 and is typically called the _policy improvement_ step because its execution results in an a policy that has a smaller horizon cost. The intuition behind the policy improvement step is that we can improve the current policy by finding a control \(u\), available at the current state \(i\), that reduces the immediate transition cost \(g(i,u)\) as well as the expected future cost, which, however involves \(J_{q}\), i.e., it has been estimated with the previous, non-improved policy. According to the [PERSON]'s optimality principle [32; 33], unless policy \(\mu_{q}\) is the optimal policy, the policy improvement step will result in a better control for at least one state. Formally, Algorithm 2 will converge to \(\mu^{*}\) as \(q_{\max}\) goes to infinity, even if the Policy Evaluation algorithm is executed for a finite value of \(q_{\max}\). However, similar to the APE algorithm, analysis and computational experience [30] suggest that heuristically selected finite values of \(q_{\max}\) approximate \(\mu^{*}\) and its corresponding optimal cost \(J^{*}\) with adequate accuracy. ```
1:Initialize \(J_{1}\) arbitrarily and \(r\gets 0\). 2:for\(q=1\) to \(q_{\max}\)do
3:\(\mu_{q}(i)=\arg\min_{u\in U(i)}[g(i,u)+\gamma\sum_{j=0}^{n}p_{ij}(u)J_{q}(j)]\), \(\forall i\in S\)
4:\(J_{\mu_{q}}=\) policy_evaluation(\(\mu_{q}\), \(J_{q}\), \(r\))
5:\(J_{q+1}=J_{\mu_{q}}\)
6:endfor
7:Return \(\mu_{q}\) and \(J_{\mu_{q}}\)
```  
**Algorithm 2** Optimistic Policy Iteration  
A significant drawback of Algorithm 2 is that its computational complexity is polynomial in \(|S|\times|U|\times q_{\max}\), where \(|\cdot|\) represents the cardinality of the enclosed set. The number of states \(|S|\) for the problem at hand is \(X\times Y\times M\), i.e., the number of states increases exponentially with the number of cells and the size of the backlog. The resulting exponential growth in computational complexity is typically referred to as the curse of dimensionality and plagues all dynamic programming problems. Thus, to tackle larger instances of the problem at hand we have to resort to computationally efficient albeit suboptimal algorithms. To this end we utilize the Rollout Algorithm [30; 34], a limited lookahead algorithm, that is based on the OPI algorithm presented above. In the Rollout algorithm, instead of initializing \(J_{0}\) arbitrarily we begin with a heuristic policy \(\mu_{h}\in\mathcal{M}\) and derive its cost \(J_{h}\). A widely used heuristic policy is the myopic policy that selects control \(u\) at state \(i\) so that \(g(i,u)\) is minimized and completely disregards the expected cost due to future state transitions as expressed by \(\sum_{j=0}^{n}p_{ij}(u)J_{\mu}(j)\), i.e.,  
\[\mu_{h}(i)=\arg\min_{u\in U(i)}g(i,u),\text{ for all }i\in S. \tag{8}\]  
Following the estimation of \(J_{h}\) one or more policy improvement steps are applied to produce an improved policy. The Rollout Algorithm is presented in Algorithm 3. ```
1: Define heuristic policy \(\mu_{h}\in\mathcal{M}\); \(r\gets 0\)
2:\(J_{h}\) = policy_evaluation(\(\mu_{h}\), \(J_{h}\), \(r\))
3:\(J_{1}=J_{h}\)
4:for\(q=1\) to \(q_{\max}\)do
5: \(\{\,q_{\max}\) is typically small, e.g., 1 or 2}
6: \(\mu_{q}(i)=\arg\min_{u\in U(i)}[g(i,u)+\gamma\sum_{j=0}^{n}p_{ij}(u)J_{q}(j)]\), \(\forall i\in S\)
7: \(J_{\mu_{q}}\) = policy_evaluation(\(\mu_{q}\), \(J_{q}\))
8:\(J_{q+1}=J_{\mu_{q}}\)
9:endfor
10: Return \(\mu_{q}\) and \(J_{\mu_{q}}\)
```  
**Algorithm 3** Rollout Algorithm