# Non-Mypopic Beam Scheduling for Multiple Smart-Target Tracking in Phased Array Radar Networks
## 2 Model Description and Problem Formulation
### Computing the Lower Bound \(V^{\mathrm{D}}(\mathbb{P}_{0},\mathbb{X}_{0})\)  
In the one-dimensional case with scalar state space for a single bandit process, scalar TEV state updates are deterministic. The lower bound \(V^{\mathrm{D}}\big{(}(P_{n,0})_{n=1}^{N}\big{)}\) is defined without dynamic state estimations \((\hat{x}_{n,0})_{n=1}^{N}\). \(V^{\mathrm{D}}\big{(}(P_{n,0})_{n=1}^{N}\big{)}\) can be calculated through the value iteration approach [39], where \(P_{n,0}\) is the initial TEV state of target \(n\).  
In the multi-dimensional case, consider the lower bound \(V^{\mathrm{D}}(\mathbb{P}_{0},\mathbb{X}_{0})\) in (17), which is the optimal value of the Lagrangian dual problem. Based on the Bellman equation, the optimal value function is firstly derived for the processes \(\{\mathbf{P}_{n,t},t=0,1,\ldots\}\) and \(\{\hat{\mathbf{x}}_{n,t},t=0,1,\ldots\}\) of target \(n\) in (18). Given the Lagrange multiplier \(\lambda\), the optimal value function \(v_{n}^{\lambda,*}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t})\) with the detection probability \(p_{\mathrm{d}}\) is  
\[v_{n}^{\lambda,*}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t})=\min_{a_{n,t} \in\{0,1\}}\Bigg{\{} C_{n}(\mathbf{P}_{n,t},a_{n,t})+\lambda a_{n,t}+\beta\mathrm{E} \bigg{[}\mathbb{I}_{a_{n,t}=0}\;v_{n}^{\lambda,*}\Big{(}\phi_{n}^{0}(\mathbf{P}_{n,t},\mathbf{u}_{n}^{0}),\hat{\mathbf{x}}_{n,t+1}\Big{)}\bigg{]}\] \[+\beta\mathrm{E}\bigg{[}\mathbb{I}_{a_{n,t}=1}\bigg{[}p_{\mathrm{d }}v_{n}^{\lambda,*}\Big{(}\psi_{n}^{1}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t},\mathbf{u}_{ n}^{1}),\hat{\mathbf{x}}_{n,t+1}\Big{)} \tag{26}\]  
Subsequently, given the Lagrange multiplier \(\lambda\) in (16), the optimal value of the Lagrangian relaxation \(V^{\mathrm{L}}(\mathbb{P}_{0},\mathbb{X}_{0};\lambda)\) can be derived by substituting (26) into it, as given by  
\[V^{\mathrm{L}}(\mathbb{P}_{0},\mathbb{X}_{0};\lambda)=\sum_{n=1}^{N}v_{n}^{ \lambda,*}(\mathbf{P}_{n,0},\hat{\mathbf{x}}_{n,0})-\frac{K\lambda}{1-\beta}. \tag{27}\]Based on the established value function and a given \(\lambda\), the \(k\)-th iteration of value function \(v^{\lambda}_{n,k}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t})\) is defined as  
\[v^{\lambda}_{n,k}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t})=\min_{a_{n, t}\in\{0,1\}}\Bigg{\{} C_{n}(\mathbf{P}_{n,t},a_{n,t})+\lambda a_{n,t}+\beta\text{E}\bigg{[} \mathbb{I}_{\hat{\mathbf{x}}_{n,t}=0}v^{\lambda}_{n,k-1}\Big{(}\phi^{0}_{n}(\mathbf{ P}_{n,t},\mathbf{u}^{0}_{n}),\hat{\mathbf{x}}_{n,t+1}\Big{)}\bigg{]}\] \[+\beta\text{E}\bigg{[}\mathbb{I}_{\hat{\mathbf{x}}_{n,t}=1}\Big{[}p_{ d}\sigma^{\lambda}_{n,k-1}\Big{(}\psi^{1}_{n}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t},\mathbf{u}^{1}_{n}),\hat{\mathbf{x}}_{n,t+1}\Big{)} \tag{28}\] \[+(1-p_{d})v^{\lambda}_{n,k-1}\Big{(}\phi^{0}_{n}(\mathbf{P}_{n,t},\mathbf{u}^{1}_{n}),\hat{\mathbf{x}}_{n,t+1}\Big{)}\bigg{]}\bigg{]}\Bigg{\}}.\]  
Then, the value iteration approach continues the iterative process over the state space until convergence of values on diverse joint states \(\mathbf{P}_{n,t}\) and \(\hat{\mathbf{x}}_{n,t}\). Finally, the optimal value \(v^{\lambda,s}_{n}(\mathbf{P}_{n,t},\hat{\mathbf{x}}_{n,t})\) in (26) is obtained. Given the initial joint states \(\mathbb{P}_{0}\), \(\mathbb{X}_{0}\) and a given \(\lambda\), the minimum cost \(V^{\text{L}}(\mathbb{P}_{0},\mathbb{X}_{0};\lambda)\) can be computed by (27). The lower bound \(V^{\text{D}}(\mathbb{P}_{0},\mathbb{X}_{0})\) of the dual problem in (17) can be computed by searching a \(\lambda\in[0,\infty)\) to satisfy (17).  
Above all, this paper regards the lower bound of problem (17) as the optimal cost of the original problem (13) to further compare discounted cost per target performances of policies, given a constant scale ratio \(K/N\).