Adapting to Dynamic LEO-B5G Systems : Meta-Critic Learning Based Efficient Resource Scheduling

This is a self-archived version of an original article. This version may differ from the original in pagination and typographic details. Author(s): Title: Year: Version: Copyright: Rights: Rights url: Please cite the original version: CC BY 4.0 https://creativecommons.org/licenses/by/4.0/ Adapting to Dynamic LEO-B5G Systems : Meta-Critic Learning Based Efficient Resource Scheduling © Authors, 2022 Published version Yuan, Yaxiong; Lei, Lei; Vu, Thang X.; Chang, Zheng; Chatzinotas, Symeon; Sun, Sumei Yuan, Y., Lei, L., Vu, T. X., Chang, Z., Chatzinotas, S., & Sun, S. (2022). Adapting to Dynamic LEOB5G Systems : Meta-Critic Learning Based Efficient Resource Scheduling. IEEE Transactions on Wireless Communications, 21(11), 9582-9595. https://doi.org/10.1109/TWC.2022.3178171 2022 Adapting to Dynamic LEO-B5G Systems: Meta-Critic Learning Based Efficient Resource Scheduling Yaxiong Yuan, Student Member, IEEE, Lei Lei, Member, IEEE, Thang X. Vu, Member, IEEE, Zheng Chang, Senior Member, IEEE, Symeon Chatzinotas, Senior Member, IEEE, and Sumei Sun, Fellow, IEEE Abstract—Low earth orbit (LEO) satellite-assisted communications have been considered as one of the key elements in beyond 5G systems to provide wide coverage and cost-efficient data services. Such dynamic space-terrestrial topologies impose an exponential increase in the degrees of freedom in network management. In this paper, we address two practical issues for an over-loaded LEO-terrestrial system. The first challenge is how to efficiently schedule resources to serve a massive number of connected users, such that more data and users can be delivered/served. The second challenge is how to make the algorithmic solution more resilient in adapting to dynamic wireless environments. We first propose an iterative suboptimal algorithm to provide an offline benchmark. To adapt to unforeseen variations, we propose an enhanced meta-critic learning algorithm (EMCL), where a hybrid neural network for parameterization and the Wolpertinger policy for action mapping are designed in EMCL. The results demonstrate EMCL’s effectiveness and fast-response capabilities in over-loaded systems and in adapting to dynamic environments compare to previous actor-critic and meta-learning methods. Index Terms—LEO satellites, resource scheduling, reinforcement learning, meta-critic learning, dynamic environment. I. INTRODUCTION In beyond 5G networks (B5G), the massive number of connected users and their increasing demands for high-datarate services can lead to overloading of terrestrial base stations (BSs), which in turn results in degraded user experience, e.g., longer delay in requesting data services or lower data rate [1]. In order to improve the network performance and user experience, the integration of satellites, e.g., low earth orbit (LEO) satellites, and terrestrial systems is considered as a promising solution to provide cost-efficient data services [2]. The solutions for terrestrial network optimization The work has been supported by the ERC project AGNOSTIC (742648), by the FNR CORE projects ROSETTA (C17/IS/11632107), FlexSAT (C19/IS/13696663), SmartSpace (C21/IS/16193290), and by the FNR bilateral project LARGOS (12173206). (Corresponding author: Lei Lei) Yaxiong Yuan, Thang X. Vu, and Symeon Chatzinotas are with the Interdisciplinary Centre for Security, Reliability and Trust, Luxembourg University, 1855 Kirchberg, Luxembourg (e-mail: [email protected]; [email protected]; [email protected]). Lei Lei is with the School of Information and Communications Engineering, Xi’an Jiaotong University, Xi’an 710049, China (e-mail: [email protected]). Zheng Chang is with the School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China, and also with the Faculty of Information Technology, University of Jyv¨ askyl¨ a, FI-40014 Jyv¨ askyl¨ a, Finland (e-mail: [email protected]). S. Sun is with the Institute for Infocomm Research, Agency for Science, Technology, and Research, Singapore 138632 (e-mail: [email protected]). and resource management might not be suitable for direct application to integrated satellite-terrestrial systems [3]. In the literature, tailored schemes have been investigated to improve the networks’ performance. In [4], the authors proposed a user scheduling scheme to maximize the sum-rate and the number of accessed users by utilizing the LEO-based backhaul. In [5], a joint power allocation and user scheduling scheme was proposed to maximize the network throughput in hierarchical LEO systems with the constraint of transmission delay. In [6], the authors developed a joint resource block allocation and power allocation algorithm to maximize the total transmission rate for LEO systems. It is worth noting that the resource optimization problems in LEO-terrestrial networks are typically combinatorial and non-convex. The conventional iterative optimization methods, e.g., in [4]–[6], are unaffordable for real-time operations due to their high computational complexity. A. Related Works: State-of-the-art and Limitations Towards an efficient solution, various learning techniques have been studied. Compared to supervised learning, reinforcement learning (RL) learns the optimal policy from observed samples without preparing labeled data. As one of the promising RL methods, deep reinforcement learning (DRL) adopts deep neural networks (DNNs) for parameterization and rapid decision making. Recent works have applied RL/DRL for resource management in LEO-terrestrial systems [7]–[9]. In [7], to maximize the achievable rate in LEO-assisted relay networks, a DQN-based algorithm was proposed to make the online decisions for link association. The authors in [8] adopted multi-agent reinforcement learning to minimize the average number of handovers and improve the efficiency of channel utilization for LEO satellite systems. In [9], the authors applied an actor-critic (AC) algorithm to LEO resource allocation, such as beam allocation and power control. The above RL algorithms in practical LEO systems are limited by the following issue. That is, the performance of a learning model largely depends on the data originated from the experienced samples or the observed environment, but the wireless environment is highly complex and dynamic. When network parameters vary dramatically, the performance of the learning models can be degraded. To remedy this, one has to re-collect a large number of training data and re-train the learning models, which is time-consuming and inefficient to adapt to fast variations [10]. 1 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ To address this issue, a variety of studies focus on how to make the learning models quickly respond to dynamic environments. Transfer learning applies the knowledge acquired from a source learning task to a target learning task to speed up the re-training process and reduce the volume of the collected new data sets [11]. The performance of transfer learning is limited by finding correlated tasks. Another approach, joint learning, aims at obtaining a single model that can be adapted to dynamic environments by optimizing the loss function over multiple tasks [12]. Besides, continual learning can also accelerate the adaptation to the new learning task by adding the experienced data from the previous tasks to the re-training data set, thus avoiding completely forgetting previously learned models [13]. Joint learning and continual learning might have good learning performance on average but have limited generalization abilities when different tasks are highly diversified [14]. In contrast, meta-learning extracts meta-knowledge and achieves good performance for specific tasks without requiring the related source tasks. The authors in [15] proposed a model-agnostic meta-learning algorithm (MAML) to obtain the model’s initial parameters as meta-knowledge to quickly adapt to new tasks. In [16], an algorithm combining actorcritic with MAML (AC-MAML) was developed to learn a new task from fewer experience data sets. In [17], the authors proposed a promising meta-critic learning framework with better performance than conventional AC and AC-MAML. In [18], a meta-learning-based adaptive sensing algorithm was proposed, which determines the next most informative sensing location in wireless sensor networks. In [19], meta-learning was applied to find a common initialization vector that enables fast training of an autoencoder for the fading channels. Most of the meta-learning methods were applied in the areas of pattern recognition [15], robotics [16], [17], and physical layer communications [19], which typically address simple learning tasks with limited action space. However, when the learning techniques, e.g., DRL, AC-MAML, or meta-critic learning, are applied to address combinatorial optimization problems in a dynamic LEO-terrestrial network, the action space can be huge and the input-output relationships can become more complex. These may degrade the efficiency of the above learning methods. B. Motivations and Contributions Moving beyond the state-of-the-art, this paper intends to address the following questions: •How to make the learning solutions more adaptive to dynamic LEO-terrestrial networks? •How to deal with the huge action space and improve the learning efficiency? In this study, we design an enhanced meta-critic learning algorithm (EMCL) to enable efficient resource scheduling for dynamic LEO-terrestrial systems, and emphasize the solutions to deal with non-ideal dynamic environments. The major contributions are summarized as follows: •We design a tailored metric for over-loaded LEO systems with dense user distribution, aiming at serving more users and delivering a higher volume of requested data. •We formulate the resource scheduling problem as a quadratic integer programming (QIP) and provide two offline optimization-based benchmarks, i.e., optimal branch and bound (B&B) algorithm and suboptimal alternating direction method of multipliers-based heuristic algorithm (ADMM-HEU). •Due to the combinatorial nature and the high complexity of the offline solutions, we solve the problem from the perspective of DRL by reformulating a Markov decision process (MDP) to make online decisions with the identical objective as the original problem. •To adapt to dynamic environments, we propose an EMCL algorithm based on a meta-critic framework. Compared to conventional meta learning, the novelty stems from that: 1) The critic has good generalization abilities to evaluate any new task such that the learning agent can adjust the policy timely when the environment changes; 2) The tailored design of a hybrid neural network extracts the features from the current and historical samples; 3) the integrated Wolpertinger policy allows the actor to make decisions more efficiently in an exponentially increasing action space. •We evaluate the proposed EMCL with other benchmarks in three practical dynamic scenarios, i.e., bursty user demands, dramatically fluctuated channel states, and user departure/arrival. The numerical results verify EMCL’s effectiveness and fast-response capabilities in adapting to dynamic environments. The rest of the paper is organized as follows. The system model is presented in Section II. We formulate a resource scheduling problem and develop optimal and suboptimal solutions for performance benchmarks in Section III. In Section IV, we model the problem as an MDP and develop an EMCL algorithm. Numerical results are demonstrated and analyzed in Section V. Finally, Section VI concludes the paper. II. SYSTEM MODEL AND PROBLEM FORMULATION A. LEO-Terrestrial Network In practice, terrestrial BSs can become over-loaded and congested. This common issue has received considerable attention from academia, industry, and standardization bodies, e.g., 3GPP Release 17 [20]. In this work, we address this challenging issue via developing satellite-aided solutions. As shown in Fig. 1, the BSs with limited resources might not be able to serve all the users and deliver all the requested data demands within a required transmission or queuing delay. To relieve the burden of the terrestrial BSs, LEO satellites are introduced to offload traffic from BSs or provide backhauling services. The LEO employs a transparent payload. For spectrum usage, the system keeps consistent with currently deployed space and ground systems. That is, the LEO satellites operate at the Kaband to provide broadband services to advanced terminals, e.g., equipped with very small aperture terminals (VSAT), while the 5G terrestrial system adopts sub-6GHz at the Cband to serve normal mobile devices, e.g., smartphones [21]. We consider two types of mobile terminals (MTs) in the system. The first type is the normal cellular terminals, e.g., 2 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ Data transmission at t (Ka band) Data transmission at t (C band) LEO BS Cellular terminals Gateway GatewayLEO link Fiber link Data transmission at t+1 (C band) Data transmission at t+1 (Ka band) TST Core Network Dual-mode terminals Centralized Controller Fig. 1. An illustrative LEO-terrestrial communication system cell phones, that can be served by BSs or terrestrial-satellite terminals (TSTs), but cannot be served by LEO due to the size limitation of dish antennas. The other is the dual-mode terminals, e.g., vehicular terminals, which are equipped with a 3GPP terrestrial-non-terrestrial network (TN-NTN) compliant dual-mode that can be either served by LEO via Ka-band (in rural areas) or by BS/TST through C-band (in urban areas) [22]. Compared to conventional cellular BS, TST is a smallsize terminal that acts as a flexible and cost-saving access point, e.g., Starlink ground terminals. A TST can receive backhauling services from LEO over Ka-band and transmit data to MTs over C-band [4]. The terrestrial BSs can request data from the core network through optical fiber links or from the LEO satellites through the BS-LEO link. We remark that Fig. 1 can be extended to a large-scale network with a massive number of MTs. Specifically, an MT in Fig. 1 can represent a cluster of densely-deployed devices. Due to the proximity, the channel states of the devices within a cluster can be assumed identical. When a cluster is scheduled, all the devices within the cluster will be scheduled by the TDMA (or FDMA) mode to avoid intra-cluster interference. We denote S,B,Mand Las the set of TSTs, BEs, MTs, and LEOs, respectively, where Mis the union of set M1 (all the cellphone MTs) and M2(all the dual-mode MTs). Thus, the union of receivers, i.e., ground devices (GDs), can be expressed as K=S ∪ B ∪ M ={1, ..., k, ..., K}, where K=|S| +|B| +|M|. Similarly, the union of transmitters is written by N=S ∪ B ∪ L ={1, ..., n, ..., N}, where N= |S|+|B|+|L|. The time domain is divided by time slots, i.e., T={1, ..., t, ..., T}. In data transmission, each transmitter nserves a GD in unicast mode, i.e., no joint transmission and no multi-cast transmission. Within a time slot, multiple transmitter-GD links can be activated, forming a link group. We denote G={1, ..., g, ..., G}as a set by enumerating all the valid link groups. To coordinate the link scheduling between terrestrial and satellite parts, a centralized controller is deployed in the system [23]. With the centralized controller, the information from the ground and satellite can be collected and exchanged, which facilitates the implementation of scheduling decisions. In addition, efficient synchronization approaches can be implemented on the transmitters and receivers to guarantee that the resource scheduling updates are performed accurately in LEO satellite systems [24]. B. Channel Modeling We consider time-varying channels for both satellite and terrestrial communication. At time slot t, the channel state between receiver kand transmitter ncan be modeled as: hk,n,t =(G(T) leo ·G(C) k,n,t ·G(R), n ∈ L, G(T) ter ·G(C) k,n,t ·G(R), n ∈ N \L,(1) where G(T) leo and G(T) ter are the transmit antenna gain of LEO and terrestrial BS/TST, respectively. We assume that all the GDs are equipped with a single receiving antenna, so that their receive antenna gains G(R)are uniform. G(C) k,n,t represents the channel fading between transmitter nand GD kat time slot t. For LEO-to-GD channel, a widely used channel fading model in [4], [6], [25] is adopted, which includes free-space path loss, pitch angle fading, atmosphere fading, and Rician small-scale fading: G(C) k,n,t =c 4πdk,n,tfleo 2 ·G(P) k,n ·A(Ω) ·ϕ, (2) where cis the speed of light, dk,n,t is the propagation distance between LEO and the terminals, fleo is the carrier frequency of LEO, G(P) k,n is the pitch angle fading gain, and ϕis the Rician fading gain. The atmospheric fading gain A(Ω) is the function of the angle Ω, where sin Ω = H/dk,n,t, and His the altitude of LEO. A(Ω) = 10(3χ 10 sin Ω ),(3) where χ, in dB/km, is the attenuation through the clouds and rain. In downlink transmission, we assume that Doppler shift caused by the high mobility of LEO can be perfectly pre(post)-compensated in the gateway based on the predictable satellite motion and speed [26]. For terrestrial channels, i.e., TST/BS-to-MT, G(C) k,n,t consists of the path loss and Rayleigh small-scale fading [27], which is given by: G(C) k,n,t =c 4πdk,n,tfter 2 ·φ, (4) where fter is the carrier frequency of TST/BS and φis the Rayleigh fading factor. Based on the adopted channel fading models (2) and (4), we further model the time-varying channel as the finite state Markov channel (FSMC) to capture the time-correlation characteristics and conduct mathematically tractable analysis. To form an FSMC, we first discretize the channel state hk,n,t into Llevels, i.e., H={h1, ..., hL}, where the thresholds hl, ..., hLare determined by the equal-probability method [28]. Then the transition probability matrix is defined as: P=   P1,1· · · P1,L . . ..... . . PL,1· · · PL,L   ,(5) 3 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ where the transition probability Pl,l0can be written as: Pl,l0=Prob [hk,n,t+1=hl0|hk,n,t=hl], hl, hl0∈ H.(6) That is, at a given time slot t, if hk,n,t =hl,Pl,l0refers to the probability of channel state at the next time slot hk,n,t+1 transiting from hlto hl0, which can be approximated by the ratio between the level crossing rate and the average number of symbol per second [28]. C. Optimization Problem We formulate a resource scheduling problem for the considered over-loaded LEO-5G systems. We use binary indicators αk,n,g to represent the activated links in group g∈ G, where αk,n,g = 1 if the transmitter-GD link (n, k)is included in group gand will be activated when group gis scheduled, otherwise, 0. Set Gand indicators αk,n,g are the necessary input parameters for the optimization problem P1. Following the principles in (7)-(10), we enumerate valid links and candidate groups. In implementation, every enumerated link or group will undergo a feasiblity-check step to ensure that no links or groups violate (7)-(10). αk,n,g = 0,∀k∈ K\M,∀n∈ N \L,∀g∈ G,(7) αk,n,g = 0,∀k∈ M1,∀n∈ L,∀g∈ G,(8) Xn∈N αk,n,g ≤1,∀k∈ K,∀g∈ G,(9) Xk∈K αk,n,g ≤1,∀n∈ N ,∀g∈ G.(10) (7) and (8) exclude certain types of links, i.e., BS-BS, TST-TST, BS-TST, TST-BS, and LEO-cellphone. (9) means that each GD kin group greceives data from at most one transmitter, and (10) represents each transmitter nin group g serves no more than one GD. For example, consider a simple system with 1 LEO, 1 TST, 1 BS, and 2 MTs (an MT1 in M1, and an MT2 in M2). There are four possible receivers, i.e., TST, BS, MT1, and MT2, indexed by K={1,2,3,4}, respectively, and three possible transmitters, i.e., TST, BS, and LEO, indexed by N={1,2,3}. Filtered by (7)-(8), all the valid links are (1,3) (TST to MT1), (1,4) (TST to MT2), (2,3) (BS to MT1), (2,4) (BS to MT2), (3,1) (LEO to TST), (3,2) (LEO to BS), and (3,4) (LEO to MT2). Confined by (9)-(10), a combination of the above links can be a valid group g, e.g, a group {(3,4),(1,3)}contains two links. Enumerating all the valid groups forms set G= {{(1,3),(2,4)},{(1,3),(3,4)}, ....., {(1,3),(2,4),(3,1)}}, which is served as the input set for decision making. Note that filtered by constraints (7)-(10), a large number of invalid links and groups have been excluded. For even larger networks, we remark that a full enumeration of groups might be unaffordable in implementation. To deal with this issue, some heuristic enumeration approaches can be adopted in pre-process stage to reduce the complexity to an affordable level [29]. Confined by (7) and (8), the SINR and the volume of transmitted data of GD kin group gat time slot tare expressed in (11) and (12), respectively. γk,g,t =Pn∈L hk,n,tαk,n,gpk,g Pj∈K\kPn∈L hj,n,tαj,n,gpk,g +σ2 +Pn∈N\L hk,n,tαk,n,gpk,g Pj∈K\kPn∈N\L hj,n,tαj,n,gpk,g +σ2,(11) and Rk,g,t = ΦBk,g log2(1 + γk,g,t),(12) where pk,g is the transmit power to GD kin group gand Φis the duration of each time slot. We denote Bleo and Bter are the fixed bandwidth for LEO and BS/TST, respectively, such that the used bandwidth Bk,g for GD kin group gcan be calculated by Bleo Pn∈L αk,n,g +Bter Pn∈N\L αk,n,g. We define the decision variables as x= [x1,1, ..., xg,t, ..., xG,T ] where xg,t =1,if group gis scheduled at time slot t, 0,otherwise. In a practical over-loaded scenario, not all the terminals can be timely served and their actual demands may not be fully delivered in time due to massive access requests competing for limited resources. Under this undesirable scenario, the optimization task may shift from “serving all the terminals and satisfying all the demands” to “serving as many terminals (and their demands) as possible”. On this basis, we denote Dkand D0 k(< Dk)as the actual demand (in bits) and the threshold, respectively. In the objective design, we consider a composite utility function in (13), and define that GD kis served, i.e., fk(x) = 1, when a threshold D0 kis satisfied. fk(x) =1 X t∈T X g∈G Rk,g,txg,t −D0 k ,(13) where 1(·)is an indicator function such that 1(β) = 1,if β > 0 0,if β≤0. We introduce a threshold D0 kin (13) since in an over-loaded scenario with densely deployed users, the system may not be able to satisfy all the actual demand Dk within one scheduling cycle. In implementation, we predefine D0 k=εDk, where 0≤ε≤1. The value of εis selected from the middle segment of [0,1] to avoid too high or low value, such that D0 khas a considerable impact on the optimization results and the trade-off effect. We convert the non-linear function fk(x)to a linear function by introducing auxiliary variables y= [y1, ..., yk, ..., yK]and linear constrains (14d), where yk=fk(x). The optimization problem is formulated as: P1 : min xg,t,yk f(x,y) = η0 X k∈K yk−K!2 + X k∈K ηk X t∈T X g∈G Rk,g,txg,t −Dk  2 (14a) s.t. ¯γk−γk,g,t ≤V 1−xg,t X n∈N αk,n,g!, 4 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ ∀k∈ K, g ∈ G, t ∈ T ,(14b) X g∈G xg,t ≤1,∀t∈ T ,(14c) D0 kyk≤X t∈T X g∈G Rk,g,txg,t,∀k∈ K,(14d) xg,t ∈ {0,1},∀g∈ G, t ∈ T ,(14e) yk∈ {0,1},∀k∈ K,(14f) where ¯γkis the SINR threshold of GD k,Vis a positive sufficiently large value, and η0, ..., ηKare the weight factors. Considering the users’ fairness and resource utilization in an over-loaded system, we design a tailored utility function (14a) consisting of two components. The first term encourages serving more users and meeting their minimum requirement D0 ksince satisfying low-traffic users are more likely to have rewards in the objective. The second term aims at minimizing the supply-demand gap such that the scheduler tends to serve the users with higher demand Dkor higher weights ηk(k= 1, ..., K). The priority or importance of the two parts can be adjusted by pre-defined weight values according to different scenarios. For example, when a large number of delay-sensitive and low-traffic users enter the network, the scheduler may give more priority by increasing η0to serve this type of users as many as possible, while the delay-tolerate services with high data demand may have lower priority (with decreased ηk) in this scheduling cycle. •The constraints (14b) represent the SINR requirement in practical satellite and 5G systems. If GD kin group gis scheduled at time slot t, i.e., xg,t Pn∈N αk,n,g = 1, the SINR of GD kshould be higher than the threshold ¯γkto guarantee the link quality. This also implies that scheduling many links with strong co-channel interference may not be a wise option in the optimal solution. The setting of ¯γkrefers to the standard of DVB-S2X [31] and 3GPP Release 16 [32]. •The constraints (14c) represent no more than one group can be scheduled in a time slot. •In constraints (14d), we define that if GD kis served, i.e., yk= 1, the received data should be larger than D0 k. III. CHARACTERIZATION ON SOLUTION DEVELOPMENT In this section, we propose an optimal method and a heuristic approach as the offline benchmarks for small-medium and large-scale instances, respectively. In addition, we outline conventional online-learning solutions and their limitations. A. The Proposed Optimal and Sub-optimal Solutions Towards the optimum of P1, we first identify the convexity of P1 when the binary variables are relaxed. Lemma 1. The relaxation problem of P1 is convex. Proof. See Appendix A. Based on Lemma 1, we conclude that P1 is an integer convex optimization problem. The optimum can be obtained by B&B that solves a convex relaxation problem at each node, with the complexity O(2G×T+K)[33]. Although the complexity increases exponentially, the B&B-based approach can provide a performance benchmark at least for smallmedium instances. To reduce the complexity in solving large-scale problems, we develop a suboptimal algorithm. We observe that P1 has a variable-splitting structure, which motivates the development of ADMM based approaches [34]. The algorithm is summarized in Alg. 1, first solving the convex relaxation problem of P1 based on ADMM (in lines 2-8), followed by a rounding operation (in lines 9-13). In ADMM, we divide the relaxed variables into T+ 1 blocks ˆ x1, ..., ˆ xT,ˆ y, where ˆ xt= [ˆx1,t, ..., ˆxG,t], and introduce auxiliary variables z= [z1, ..., zK], where zk=D0 kˆyk−X g∈G X t∈T Rk,g,t ˆxg,t,∀k∈ K.(15) The inequality constraints (14d) are replaced by: zk≤0,∀k∈ K.(16) The augmented Lagrangian function is expressed as: L(ˆ x1, ..., ˆ xT,ˆ y,z,λ) =f(ˆ x,ˆ y) + X k∈K λk zk−D0 kˆyk+X g∈G X t∈T Rk,g,t ˆxg,t  +ρ 2X k∈K kzk−D0 kˆyk+X g∈G X t∈T Rk,g,t ˆxg,tk2,(17) where ρ > 0is the penalty parameter and λ= [λ1, ..., λK]are the lagrangian multipliers. We define Iiter as the total number of iterations of the algorithm. In each iteration i, ADMM updates each variable block as follows (in line 5) and update multipliers (in line 6): ˆ xi+1 t= argmin ˆ xt∈Xt L(ˆ xi 1, ..., ˆ xi T,ˆ yi,zi,λi),∀t∈ T ,(18) ˆ yi+1 = argmin ˆ y∈Y L(ˆ xi 1, ..., ˆ xi T,ˆ yi,zi,λi),(19) zi+1 = argmin z∈Z L(ˆ xi 1, ..., ˆ xi T,ˆ yi,zi,λi),(20) where Xt={xt|(14b), (14c), (14d)},Y={y|0≤yk≤1} and Z={z|zk≤0}. When ADMM terminates, the continuous solution ˆxg,t is obtained in line 8. The rounding process is then carried out in lines 10-13 to convert the largest ˆxg,t in each time slot to 1 (selecting the most promising group gfor each t) and keep others 0. The developed ADMM-HEU can provide sub-optimal benchmarks within an acceptable time span, since the subproblems in (18)-(20) can be solved in a parallel manner and with a smaller size than the original problem. However, ADMM-HEU requires O(1/2)iterations to achieve -optimality, where  is set as µ T(T+3) [35]. At each iteration, we can solve the T+ 2 variable blocks by B&B with the time complexity of O(T·2G+ 2 ·2K). Thus, the total complexity is given by O(T5·2G+T4·2K), which might not sufficient for fast adaptation to network variations. 5 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ Algorithm 1 ADMM-HEU 1: input: Dk,D0 kand Rk,n,t. 2: Relax P1 to a continuous problem P10. 3: Initialize ˆ x0 t,ˆ y0,z0,λ0and i= 0. 4: for i= 0, ..., Iiter do 5: Update ˆ xt,ˆ yand zby Eq. (18), (19) and (20). 6: λi+1 k=λi k+ρ zi k−D0 kˆyi k+P g∈G P t∈T Rk,g,t ˆxi g,t!. 7: end for 8: Obtain relaxed solution ˆxg,t. 9: for t∈ T do 10: Find g†= argmax g∈G {ˆx1,t, ..., ˆxG,t}. 11: Set x∗ g†,t = 1 and x∗ g,t = 0,∀g6=g†. 12: end for 13: Calculate y∗ kbased on Eq. (13). 14: output: x∗ g,t and y∗ k B. Conventional Online-Learning Solutions and Limitations To enable an intelligent and online solution, we address the problem from an RL perspective. Firstly, we briefly introduce actor-critic and meta-critic learning approaches as a basis to present the proposed EMCL. AC is an RL algorithm that takes advantage of both value-based methods, e.g., Q-learning, and policy-based methods, e.g., REINFORCE, with fast convergent properties and the capability to deal with continuous action spaces [36]. The learning agent in AC contains two components, where the actor is responsible for making decisions while the critic is used for evaluating the decisions by the value functions. Specifically, at each learning step t1, the actor takes action based on a stochastic policy, i.e., at∼π(a|st), where π(a|st)is the probability of taking an action under state st, typically following the Gaussian distribution [37]. The critic is to generate a Q-value function Q(st, at) = Eπ[¯rt|st, at], where ¯rtis the accumulated reward at step t, and Eπ[β]is the expected value of βover the policy π. The goal of the learning agent is to find a policy to maximize the expected accumulated reward (or Q-value). A critical issue in conventional learning approaches, including AC, is that the performance of a learning model largely depends on the adopted training or observed data sets. To illustrate the dynamic environment and its impacts, we consider two types of environmental changes. The first is “foreseen variations”. A typical example is a time-varying channel with certain time correlation and statistical characteristics. In this case, a general machine learning algorithm can capture the regular patterns effectively to resolve the mapping from the environment to the desired decision variables. The second is “unforeseen variations”, which is much more challenging to address. These changes are usually unexpected and inclined to break the statistical distribution of the original environment. The practical LEO-5G systems are highly complex and dynamic, such as fast and dramatic variations in channel states, user demands, user arrival/departure, and network topologies. This typically causes the new inputs to no longer be relevant to the statistical properties of the historical data [38]. As a consequence, the scheduling decisions made from the previous 1In this paper, a learning step corresponds to a time slot. learning model can become invalid and the model may need to be re-trained to adapt to the new environment. To illustrate this impact, we use Fig. 2, as an example, to depict a typical evolution of AC’s loss value over time-varying demands. From 0 to 100 time slots, the demand is time-varying but follows historical statistical properties, e.g., fluctuating within a certain range or following a certain distribution, leading to a well-adapted AC with low and stable loss values. When a surged demand is generated at the 100-th time slot, the new input deviates from the statistics. The AC model becomes inapplicable to the new environment, evidenced by the rapidly deteriorating loss values. When the agent in AC consumes a considerable amount of time in new data collection and retraining, the performance can return to the previous level. 0 50 100 150 200 250 Tim e 0.0 0.2 0.4 0.6 0.8 1.0 Loss Value Learning perform ance w.o. ret raining Learning perform ance w. retraining Fig. 2. Evolution of loss over time-varying demands. To address this issue of “unforeseen change”, meta-criticbased approaches become an emerging technique that takes advantage of a variety of previously observed tasks to infer the meta-knowledge, such that a new learning task can be quickly trained with few observations [15]. Meta-critic learning combines meta-learning with an AC framework to enhance the generalization ability. However, conventional meta-critic learning is not effective in dealing with the large discrete space in P1. In addition, there is no uniform standard to parameterize the learning model and extract meta-knowledge in dynamic environments. Thus, we propose an EMCL algorithm to enable an efficient dynamic-adaptive solution. IV. THE PROPOSED EMCL ALGORITHM In this section, we elaborate the proposed EMCL algorithm, firstly starting from outlining the EMCL framework, then detailing the tailored design. A. EMCL Framework 1) MDP Reformulation: First, we reformulate the original problem P1 as an MDP by defining action, state and reward. •As the actor is to select a group from set Gat each time slot t, the action is defined as an assigned link group, at=g∈ G.(21) •The state consists of the channel coefficients hk,n,t, modeled as FSMC with the transition probability defined 6 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ in (6), and the delivered data for user kup to time slot t, where bk,t =bk,t−1+Rk,at,t. st={h1,1,t, ..., hK,N,t, b1,t, ..., bK,t}.(22) All possible states are included in the state space S. The next state only depends on the current state and action but is irrelevant to the past, which means the state transition from stto ss+1 follows the Markov property [36]. •The reward is closely related to the objective of P1. We define the reward as (23). rt= K X k=0 ηk(∆2 k,t−1−∆2 k,t),(23) where ∆k,t =   K P k=1 1(bk,t −D0 k)−K, k = 0, bk,t −Dk, k 6= 0. Then, the accumulated reward at step tis given by ¯rt=PT t0=tγt0−trt0, where γ∈[0,1] is a discounted factor. Under the designed MDP, we verify the consistency between the goals of the RL algorithm and the original optimization problem such that the policy provided by the learning agent can minimize the objective in P1. Lemma 2. When γ= 1, the objective of the learning agent is equivalent to that of the optimization problem P1. Proof. See Appendix B 2) Meta Critic and Task-Specific Actor: As shown in Fig. 3, we design a hierarchical structure in EMCL containing a meta critic2and multiple actors. Meta-learning uses data from previously observed multiple tasks, J(1), ..., J(I), to infer a “meta-knowledge” with good generalization ability and accelerate the training for a new task. In the proposed EMCL, the “meta-knowledge” is the meta critic which can evaluate the task with a Q-value, like the role of the critic in traditional AC, and possesses a strong generalization ability to guide any task-specific actor to provide a policy. At time step t,s(i) t,a(i) t, and r(i) trepresent the state, action, and reward for task i, respectively. An episode D(i)={s(i) 1, a(i) 1, r(i) 1..., s(i) T, a(i) T, r(i) T}can be sampled from the first step to the terminal step T. We denote D(i) [u,w] as a segment of D(i)from step uto w, i.e., D(i) [u,w]= {s(i) u, a(i) u, r(i) u, ..., s(i) w, a(i) w, r(i) w}. Since the explicit meta critic and actors are difficult to obtain, we adopt the function approximation method. The meta critic is parameterized as a neural network (NN) with the weights ω, i.e., Q(s(i) t, a(i) t,D(i) [t−¯ t,t−1];ω). We note that, in addition to s(i) t and a(i) t, the input includes the most recent ¯ tsamples D(i) [t−¯ t,t−1]. Each task-specific actor is modeled as an NN π(a|s(i) t;θ(i))with the weights θ(i). To optimize the weights, we minimize the loss functions by gradient descent. The loss function of the meta critic L(ω)is 2In this paper, “meta-critic learning” refers to an algorithm that combines AC and meta-learning while “meta critic” refers to the critic in the framework. Task 1 Task I ... st (i)at (i) D[u,w] (i) LTSM LTSM LTSM LTSM LTSM LTSM ... ... st (1) ... Wolpertinger mapping st (I) Wolpertinger mapping at (1) at (I) meta critic actor 1 actor I Task-specific Q-value Update meta critic ωt+1 = ωt-ρ׏ωL(ω) Update actor θt+1 (1) = θt+1 (1)-ρ׏θJ(θt+1 (1)) Update actor I θt+1 (I) = θt+1 (I)-ρ׏θJ(θt+1 (I)) π(a|st (1); θ(1)) π(a|st (I); θ(I)) Memory New Task st Wolpertinger mapping at actor Update actor θt+1 = θt+1-ρ׏θJ(θt+1) π(a|st; θ) meta critic ω* Memory extract well-trained meta critic asĀmeta-knowledgeā Meta training phase Online learning phase On Q-value Task i General Q-value task identification embedding Fig. 3. The proposed EMCL framework. defined as the average temporal difference (TD) error over all tasks: L(ω) =1 I I X i=1 Eπ(θ(i))h(Q(s(i) t+1, a(i) t+1,D(i) [t−¯ t+1,t];ω)−rt −γQ(s(i) t, a(i) t,D(i) [t−¯ t,t−1];ω)i2,(24) where the TD error reflects the similarity between the estimated Q-value and actual Q-value. For the task-specific actor, the loss function J(θ(i))is the negative Q-value: J(θ(i)) = Eπ(θ(i))h−Q(s(i) t, a(i) t,D(i) [t−¯ t,t−1];ω)i,(25) such that minimizing J(θ(i))is equivalent to maximizing the expected accumulated reward. The update rules are given by: ωt+1 =ωt−ρ∇ωL(ω),(26) θ(i) t+1 =θ(i) t−ρ∇θ(i)J(θ(i)).(27) Based on the fundamental results of the policy gradient theorem [36], the gradients of L(ω)and J(θ(i))are: ∇ωL(ω) = 1 I I X i=1 h2L(ω)∇ω(Q(s(i) t+1, a(i) t+1,D(i) [t−¯ t+1,t];ω) −Q(s(i) t, a(i) t,D(i) [t−¯ t,t−1];ω))i,(28) ∇θ(i)J(θ(i)) = −Q(s(i) t, a(i) t,D;ω)∇θ(i)log π(a|s(i) t;θ(i)). (29) 3) Algorithm Summary: We summarize the proposed EMCL in Alg. 2, which includes two phases: the meta training 7 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ phase and the online learning phase. For the former, the meta critic is trained over different learning tasks. At each learning episode, we sample Ilearning tasks. We obtain the approximated Q-value (in line 6) and stochastic policy (in line 7) by the approximation functions. The final actions are determined by the Wolpertinger approach in line 8, which will be elaborated in the following subsection. In line 9, the memory is used to store the experienced learning tuples {s(i) t, s(i) t+1, a(i) t, r(i) t}. At each step, we extract a batch of tuples from the memory as the training data for updating ω and θ(i)by (26) and (27) in line 10 and 12, respectively. In the online learning phase, given a new task, the well-trained meta critic ω∗can be directly used to estimate the Q-value and only the actor needs to be re-trained. We note that the adaptation ability of the meta-learning algorithm depends on the completeness of the tasks provided in the meta-training phase. In general, it is not practical to collect all the possible environments. As an alternative, the selected tasks in the metatraining phase should keep the diversity and representativeness to achieve higher sampling efficiency. Algorithm 2 EMCL Meta training phase: 1: input: Multiple task samples; initial ω0. 2: for each learning episode do 3: Sample Itasks and initialize ω0,θ(1) 0, ..., θ(I) 0. 4: for each learning step tdo 5: for each task ido 6: Obtain Q-value by the meta critic in (32). 7: Obtain stochastic policy by the actor in (34). 8: Take actions a(i) tby the Wolpertinger approach. 9: Store tuples {s(i) t, s(i) t+1, a(i) t, r(i) t}in the memory. 10: Take a batch of data and update θ(i)by (27). 11: end for 12: Update ωby (26). 13: end for 14: end for 15: output: The well-trained meta critic ω∗. Online learning phase: 16: input: A new task; initial θ0; well-trained meta critic ω∗. 17: for each learning episode do 18: for each learning step tdo 19: Obtain Q-value by the meta critic in (32). 20: Obtain stochastic policy by the actor in (34). 21: Take an action atby the Wolpertinger approach. 22: Store tuples {st, st+1, at, rt}in the memory. 23: Take a batch of data and update θby (27). 24: end for 25: end for 26: output: The optimal actor θ∗. B. Tailored Designs in EMCL 1) Parameterization with Hybrid Neural Networks: There is no uniform standard for parameterization in conventional meta-critic learning. Considering dynamic environments, the distribution of the new input data and the previous observations may deviate. Towards fast adaptation to the dynamic environment, the critic should be able to identify different tasks, where the information for task identification can be refined from the experienced data, which usually forms time-related series [17]. The widely used DNN might have limitations in efficiency and in mining features from time-series data due to the massive number of weights and feed-forward structure. In the proposed EMCL, we design tailored neural networks to enable the meta critic and the actors to fit the complex nonlinear relationships and extract the meta-knowledge from historical data. As shown in Fig. 3, for the meta critic, a hybrid neural network (HNN) combing convolutional neural network (CNN), long-short term memory (LSTM), and artificial neural network (ANN) is applied to learn the features from the current stateaction pairs and historical trajectories [39]. Thereinto, CNN is computation-efficient via adopting the parameter sharing and pooling operations, and is effective to extract spatial features from the input data. These advantages enable CNN to reduce the parameters of the model and alleviate the problem of overfitting. LSTM, as a type of recurrent neural network, has advantages in extracting features from time-related sequential data. Thus, in the designed meta critic, the CNN is used to evaluate the decisions made by the actor from the current action-state pair s(i) t, a(i) t. The LSTM is adopted to identify the task based on the time-series data D(i) [t−¯ t,t−1], such that the meta critic can accurately criticize any actor in changing environment and adapt to the dynamic networks. We denote fcnn(x;w),flstm(x;w)and fann(x;w)as the outputs of CNN, LSTM, and ANN, respectively, which are the functions of input xand weight w. The features output from CNN and LSTM are: ξ1=fcnn(s(i) t, a(i) t;ωcnn),(30) ξ2=flstm(D(i) [t−¯ t,t−1];ωlstm),(31) where ξ1and ξ2physically mean the general Q-value and the task identification embedding, respectively, which can be represented by scalars [17]. Then, we take the features as inputs and pass them through a fully-connected ANN to obtain the task-specific Q-value: Qπ(s(i) t, a(i) t,D(i) [t−¯ t,t−1];ω) = fann(ξ1, ξ2;ωann).(32) For the task-specific actors, we adopt CNN as the approximator which takes the current state as the input and outputs the mean µand variance ϑ2of the stochastic policy. We assume the stochastic policy follows Gaussian distribution N(µ, ϑ2), such that [µ, ϑ2] = fcnn(s(i) t;θ(i)),(33) π(a|s(i) t;θ(i)) = N(µ, ϑ2).(34) 2) Action Mapping with the Wolpertinger Policy: The decision variables in P1 are discrete such that we need to map the action from the stochastic policy to a discrete action space. However, the previous action mapping policies in meta-critic learning are not efficient since the action space is large for P1. Thus, in EMCL, the Wolpertinger policy is adopted for faster convergence [40]. Following the stochastic policy π, the actor first produces an action ˆawith continuous value, i.e., fπ:S → ˆ A, fπ(s) = ˆa, (35) 8 This article has been accepted for publication in IEEE Transactions on Wireless Communications. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TWC.2022.3178171 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/