# Adaptive Packet Coding for Reliable Underwater Acoustic Communications
## 4 Optimal Solution  
In our problem, the state of the \(i\)-th transmission is dependent on the result of \((i-1)\)-th transmission. Meanwhile, since packet error is a stochastic process, this problem can be seen as a sequential decision-making problem. This problem can be solved by the finite-horizon DP [24; 25; 29] approach.  
Let \(\mathbf{c}_{i}^{(k)}=(h_{i-1}^{(k)},q_{i-1}^{(k)})\) denote the state of the system at the \(i\)-th transmission for the \(k\)-th block, where \(q_{i-1}^{(k)}\) denotes the number of coded packets successfully received in the all \((i-1)\) transmissions. \(h_{i-1}^{(k)}\) is the feedback channel state of the \((i-1)\)-th transmission for the \(k\)-th block. Let \(U(\mathbf{c}_{i}^{(k)})\) denote the feasible set of the _action_\(N_{i}^{(k)}\) given the current state \(\mathbf{c}_{i}^{(k)}\). Then,  
\[U(\mathbf{c}_{i}^{(k)})=[0,B_{i}^{(k)}] \tag{16}\]  
In this case, the upper limit of \(N_{i}^{(k)}\) is constant. Thus, we let \(B_{i}^{(k)}=Q\).  
The probability that the system state \(\mathbf{c}_{i}^{(k)}\) will transfer to state \(\mathbf{c}_{i+1}^{(k)}\) when action \(N_{i}^{(k)}\) is taken is given as  
\[P(\mathbf{c}_{i+1}^{(k)}|\mathbf{c}_{i}^{(k)},N_{i}^{(k)})= P(h_{i}^{(k)},q_{i}^{(k)}|h_{i-1}^{(k)},q_{i-1}^{(k)}N_{i}^{(k)})\] \[= P(q_{i}^{(k)}|h_{i}^{(k)},q_{i-1}^{(k)},N_{i}^{(k)})P(h_{i}^{(k) }|h_{i-1}^{(k)}) \tag{17}\]  
According to (8),  
\[P(q_{i}^{(k)}|h_{i}^{(k)},q_{i-1}^{(k)},N_{i}^{(k)})= \left\{\begin{array}{ll}P_{S}(s_{i}^{(k)},h_{i}^{(k)},N_{i}^{(k)}),&q_{i}^{(k)}\geq q_{i-1}^{(k)}\\ 0,&q_{i}^{(k)}<q_{i-1}^{(k)}\end{array}\right. \tag{18}\]The expected cost incurred from the \(M\)-th transmission is given by  
\[J_{M}(h_{M-1^{*}}^{(k)}q_{M-1}^{(k)})\] \[=\min_{0\leq N_{M}^{(k)}\leq Q}\left\{\gamma^{M}T_{M}^{(k)}+\mathbb{ E}\Big{[}\pi(q_{M}^{(k)})|(h_{M-1^{*}}^{(k)}q_{M-1}^{(k)})\Big{]}\right\} \tag{19}\] \[=\min_{0\leq N_{M}^{(k)}\leq Q}\left\{\gamma^{M}T_{p}N_{M}^{(k)}+ \gamma^{M}T_{\tau}+C\sum_{s_{M}^{(k)}=0}^{u_{M}^{(k)}}\sum_{l=1}^{L}P_{s}(s_{M }^{(k)},h_{M}^{(k)},N_{M}^{(k)})P(h_{M}^{(k)}=\delta_{l}|h_{M-1}^{(k)})\right\} \tag{20}\]  
The first term of (19) is the cost of the \(M\)-th transmission, the second term is the expectation of penalty term due to the incomplete transfer after \(M\) transmissions. It depends on the result of the \(M\)-th transmission according to (14).  
Based on the Bellman equation [29], the optimal solution can be obtained by recursively computing \(J_{M}(c_{M}^{(k)})\), \(J_{M-1}(c_{M-1}^{(k)})\), \(\cdots\), \(J_{1}(c_{1}^{(k)})\). The expected cost incurred from the \(i\)-th transmission to termination is given by  
\[J_{i}(h_{i-1}^{(k)},q_{i-1}^{(k)})\] \[=\min_{0\leq N_{i}^{(k)}\leq Q}\left\{\gamma^{i}T_{i}^{(k)}+ \gamma\mathbb{E}\Big{[}I_{i+1}(h_{i}^{(k)},i,q_{i}^{(k)})|q_{i-1}^{(k)},h_{i-1 }^{(k)}\Big{]}\right\}\] \[=\min_{0\leq N_{i}^{(k)}\leq Q}\left\{\gamma^{i}(T_{p}N_{i}^{(k)} +T_{\tau})+\gamma\sum_{s_{i}^{(k)}=0}^{N_{i}^{(k)}}\sum_{l=1}^{L}P_{s}(s_{i}^{ (k)},h_{i}^{(k)},N_{i}^{(k)})P(h_{i}^{(k)}=\delta_{l}|h_{i-1}^{(k)})I_{i+1}(h_{ i}^{(k)},q_{i}^{(k)})\right\} \tag{21}\]  
The first term in (21) represents the expected cost of current transmission. The second term in (21) is the expected future cost accumulated from the \((i+1)\)-th transmission to the \(M\)-th transmission.  
The DP approach includes two steps. In step 1, the sender calculates the (21) to find the optimal \({N_{i}^{(k)}}^{*}\) for each system state \(c_{i}^{(k)}\) and records it as a lookup table. In step 2, the sender chooses the optimal \({N_{i}^{(k)}}^{*}\) of the current state based on the lookup table.