## 5 Algorithm Design
### The Trained Algorithm  
We adopt the policy gradient to train the prediction model, and the training algorithm is shown in Algorithm 1. ```
0:action network \(\pi(a|s,w),\textit{critic network}\)\(\vtheta(s,w_{v})\)
1:Random policy parameter \(w\) and critic parameter \(w_{v}\)
2:for\(epoch=1,2...\)do
3: reset \(d^{{}^{{}^{\prime}}}\gets 0\)
4:\(s_{j}\sim SampleInput(S)\)\(forj\in\{1,...,B\}\)
5:\(p_{j}\sim SampleSolution(\pi_{w}(\cdot|s))\)\(forj\in\{1,...,B\}\)
6:\(b_{j}\gets b_{w_{v}}(s_{j})\)\(forj\in\{1,...,B\}\)
7:\(compute\)\(cost\)\(function:L(p_{j})\)\(forj\in\{1,...,B\}\)
8:\(g_{w}=1/B\cdot\sum_{j=1}^{B}(L(p_{j})-b(s_{j}))\cdot\
abla_{w}log_{\pi_{w}}(p_ {j}|s_{j})\)
9:\(\mathcal{L}(w_{v})=1/B\cdot\sum_{j=1}^{B}||b_{w_{v}}(s_{j})-L(p_{j}|s_{j})||^{2}\)
10:\(w\gets [PERSON](w,g_{w})\)
11:\(w\gets [PERSON](w_{v},\mathcal{L}(w_{v}))\)
12:endfor
13:return\(w\) and \(w_{v}\)
```  
**Algorithm 1****Train Agent Network**  
The algorithm model is divided into three parts: agent, environment, and state. The agent includes the sequence-to-sequence model and value evaluator. The environment is the network system constructed in this article, and the state includes SFC and the resource situation of each host and link. After receiving the SFC, the agent selects the VNF placement policy according to the current state. Then, the environment places the VNF according to the specific location and generates a new state, and gives back the corresponding reward value to the agent so as to guide the agent to constantly explore a better placement policy. The specific algorithm model is shown in Figure 6.  
We suppose that the VNF placement problem in SAGIN has \(n\) states, and its state space is \(S=\{s_{1},s_{2},...,s_{n}\}\). The size of the state space is closely related to the number of underlying network resources and the type of VNF. When n compute nodes are considered, the set of compute resources of these compute nodes is \(R_{c}=\{r_{1},r_{2},...,r_{n}\}\). Meanwhile, the bandwidth resources connecting these compute nodes are \(R_{b}=\{b_{1},b_{2},...,b_{n}\}\). If there are \(m\) VNF types, then \(m\cdot\sum_{i=0}^{n}r_{i}\cdot b_{i}\) states are formed. The action space is related to the number of computing nodes, assuming that the underlying network has n computing nodes. Then, the agent has \(n\) actions, and its action space is \(A=\{a_{1},a_{2},...,a_{n}\}\). The agent interacts with the environment \(t\) times to obtain the trajectory and deployment scenario can be represented as: \(\tau=\{(s_{1},a_{1}),(s_{2},a_{2}),...,(s_{t},a_{t})\}\), \(p=\{a_{1},a_{2},...,t_{t}\}\). After the configuration according to deployment scenario \(p\), the environment evaluates whether the network resource constraints, delay constraints, and energy consumption magnitude are met and offers a feedback value. Subsequently, the neural network updates the policy based on this feedback value. We need to find strategy \(\pi(a|s)\) that enables optimal placement of the SFC. Therefore, this strategy cannot be used directly; we set policy function \(\pi_{\theta}(a|s)\), and its relationship with \(\pi(a|s)\) is shown below. \[\pi(a|s)\approx\pi_{\theta}(a|s)=P(a|s,\theta). \tag{20}\]  
\(\pi_{\theta}(a|s)\) approximate to strategy \(\pi(a|s)\) using a function with \(\theta\) to present the probability of performing action \(a\) in state \(s\). Then, the optimal strategy is constantly approximated by updating \(\theta\). Therefore, according to the guidelines of this function, we need to set an objective function so that policy function \(\pi_{\theta}(a|s)\) can optimize \(\theta\). When \(\theta\) is determined, we can express the energy consumption of SFC as Equation (15). \[J_{E}^{\pi}(\theta|s)=\sum_{\tau}E(\tau)P_{\theta}(\tau)=\mathop{\mathbb{E}} \limits_{p\sim\pi(\cdot|S)}[E(\tau)], \tag{21}\]  
where \(E(\tau)\) is the energy consumption of the network system at trajectory \(\tau\).