## 1 Introduction  
Agile optical satellites (AOSs), as a new generation of optical satellites, have superior attitude maneuverability, which can adjust attitude flexibly and quickly on the three axes of pitch, roll and yaw. Over past years, they have played increasingly significant roles in many fields, such as environmental monitoring, marine development, agricultural production, city planning, and military reconnaissance [1, 2]. The agile characteristics improve the observation capability of AOSs but also lead to a more complex attitude maneuver process. With the surge in earth observation demand, scheduling an agile optical satellite has become a challenging problem. Compared with traditional optical satellites, AOSs can observe the target during a much longer observable period due to its ability to rotate around the pitch axis, as shown in Figure 1. The period during which the satellite can observe the target is called the visible time window (VTW), and the duration of the actual observation event is called the observation window (OW). In this study, the AOS adopts a common push-broom observation mode [3] and adjusts its attitude only by rolling and pitching. In the observation process of an AOS, its pitch angle determines the start time of the OW, and its roll angle is determined by the relative position of the AOS and the target. Thus, in a VTW, the pitch angle is variable but the roll angle can be regarded as a fixed value. When an AOS observes two adjacent targets, a short period is needed for the attitude adjustment, which is called the transition time. The time interval between two successive observation actions must not be less than their required transition time [4]. Only if the observation time of the previous task is determined can the observation time of the next one be determined. Therefore, the observation time of multiple tasks must be determined one by one, which is a sequential decision process. The purpose of the single AOS scheduling problem (SAOSSP) is to reasonably arrange the observation sequence and observation time of tasks [3]. The SAOSSP has been proven as an NP-hard problem [5], exhibiting the characteristics of a combination explosion, and its solving time grows exponentially with the problem scale [6]. The complexity of this problem is mainly reflected in three aspects. First, each target may have several VTWs in different orbits, causing multiple possibilities of the VTW selection, and the observation event can start at any time within the selected VTW, causing various optional possibilities of the OW. Second, owing to the complicated constraints and the considerable solution space, an enormous number of constraint-checking steps and a thorough search in the solution space are needed [7], demanding high computational expenses. Third, this problem is typically an oversubscribed scheduling problem where only partial tasks have the chance to be accomplished [8; 9], and the increase of the problem scale can further expand its computational complexity. Therefore, the SAOSSP is hard and complex to solve, and an efficient scheduling method is badly required to accomplish the more observation tasks and reach the maximum observation profit. Over the past few decades, extensive research has been carried out, and many contributions have been made to solve the agile satellite scheduling problem. Existing approaches can be roughly distributed into three categories: exact algorithms, heuristic algorithms and deep reinforcement learning (DRL) algorithms. Some researchers adopt exact algorithms to solve this problem. [PERSON] et al. [5] gave the general description of the agile satellite scheduling problem for the first time and proposed a dynamic programming algorithm. [PERSON] et al. [10] presented a branch and bound algorithm with a look-ahead method and three pruning strategies to tackle the simplified problem in a small-size instance. [PERSON] et al.