Reinforcement Learning for Multi-Function Radar Resource Management

Keywords: reinforcement learning, radar, scheduling, multi-objective Mots clés : apprentissage par renforcement, radar, ordonnancement, multi-objectif reinforcement learning, radar, scheduling, multi-objective Résumé apprentissage par renforcement, radar, ordonnancement, multi-objectif LIP6

In the wake of recent advances in the field of machine learning, much progress has been accomplished in one of its sub-fields, reinforcement learning, whose aim is to solve sequential decision problems under uncertainty. Radar resource management seems to represent an ideal application case for this type of technique. Indeed, a radar emits signals, called dwells, whose echoes are used to measure the state of surrounding objects; these dwells vary according to numerous parameters (duration, beam width...) and must be executed sequentially. The surveillance strategy of a multi-function radar thus consists in continuously selecting the dwells to perform, with the aim of searching the surrounding space while tracking already detected targets. The methods currently used to address this problem are largely heuristic, and are likely to run into difficulties in a range of complex situations involving hyper-velocity or hyper-maneuvering targets. First, we propose applications of reinforcement learning techniques adapted to the current architecture of multi-function radars. These contributions focus on two aspects : dwell scheduling on the antenna using model-based methods, and active tracking dwell optimization using model-free methods. Secondly, we highlight the limitations of current resource management architectures, which leads us to consider an alternative architecture for which we propose new reinforcement learning algorithms designed to address the problems it raises. These contributions focus both on the multi-objective aspect, which is useful in multi-function radars to reflect the trade-offs to be made between different functions, and on the combinatorial aspect, which is due to the large number of tasks that the radar must carry out in parallel.

Introduction

Radar, short for "radio detection and ranging," is a technology that uses radio waves to detect and track objects. From their inception as an air defense system in the early 20th century, radars have evolved and diversified, finding applications in weather forecasting, air traffic control, navigation, and various other fields. They have become indispensable tools due to their ability to provide accurate measurements of distant objects and phenomena and gather valuable information about the surrounding environment. The past few decades have witnessed remarkable advancements in radar technology, leading to the development of highly sophisticated and intricate systems with enhanced capabilities. These significant strides in radar technology can be attributed to the rapid progress in digitalization and electronic systems. The integration of digital components has paved the way for a multitude of improvements, enabling radars to perform a diverse range of missions more efficiently than ever before. One notable advancement is the utilization of phased array antennas, which use multiple individual radiating elements and controlled phase shifting to steer and focus the transmitted or received electromagnetic waves with precision and flexibility. This has brought about the concept of digital beam forming.

Beam forming is the process of shaping and directing the radar's waves into a specific pattern or direction to achieve desired coverage and angular resolution. Radars can now dynamically adjust their beam pattern electronically, freeing it from traditional mechanical constraints. Digital beam forming enhances the radar's agility and responsiveness by enabling rapid beam scanning and reconfiguration. This capability is particularly crucial in scenarios where a radar needs to monitor multiple targets simultaneously or rapidly switch between different tasks.

In this context, multi-function radars, which are able to manage searching, tracking, and missile guidance in parallel, have come to represent a key component of air defense systems. However, the efficient utilization of resources, including power, computation INTRODUCTION time, and antenna time, poses a significant challenge for these systems. The current resource management strategies, originally designed for earlier generations of radar systems, often fail to fully exploit the potential of these adaptive radars. Consequently, several capabilities inherent in these advanced systems remain underutilized. Furthermore, the optimization of these radars' behavior has become increasingly complex due to the increased number of degrees of freedom of the systems. With a myriad of parameters and variables to consider, achieving optimal radar behavior has become a much more challenging task. In the defense context, the emergence of new threats adds another layer of urgency to the development of advanced radar systems. Of special concern are hypermaneuvering targets, which can change direction exceptionally quickly and frequently, and hypervelocity targets, which travel at extremely high speeds, typically exceeding several kilometers per second. These characteristics are a challenge as they allow the targets to surpass the tracking capabilities of traditional radar systems, underscoring the critical need for advanced radar systems capable of detecting and tracking such elusive targets.

In this context, much effort has been devoted to development of "cognitive radars".

The idea is to obtain a system that can learn through interactions with its surrounding environment and use this feedback to intelligently adapt its illumination of the environment, taking target characteristics into account. Analogously to biological systems, this requires the radar to maintain a "mental model" of its surroundings that it can update continuously. The adaptivity that the radar should display is necessitated by the non-stationarity of its environment, whose causes include weather variation and the appearance of unknown targets. This framework naturally presents a favorable application case for artificial intelligence techniques.

Artificial intelligence has evolved significantly since its inception, witnessing remarkable progress in various fields. AI originated in the 1950s with the goal of developing machines that could simulate human intelligence. Early AI focused on symbolic reasoning and rule-based systems, attempting to replicate human decision-making processes through logical algorithms. However, progress was limited by the complexity of realworld problems and the lack of computational power. Gradually, a shift occurred with the rise of machine learning approaches. Machine learning leverages statistical techniques to enable systems to learn from data and improve performance over time. This marked a turning point in AI development. Initially, machine learning focused on tra-

INTRODUCTION

have been proposed for safe learning: one of them is to cast the problem as multiobjective reinforcement learning, where agents need to balance and optimize multiple conflicting objectives. This allows for the consideration of trade-offs between different criteria such as performance, fairness, and safety.

In the context of the digitization of radars, machine learning techniques represent an alternative worth investigating. However, the scarcity of available data for emerging forms of threat to radar systems constitute an impediment to the application of supervised learning. The interactive nature of radar resource management rather points to reinforcement learning. Given reinforcement learning's ability to handle complex decision-making tasks and adapt to changing conditions, the management of radar resources seems to represent a favorable application framework for this type of technique.

Indeed, the surveillance strategy of a multi-function radar must answer a sequential decision problem in the face of uncertainty. The uncertainty arises from the radar's partial information acquisition mechanism, which can only benefit from localized and noisy observations, the obtaining of which requires active listening phases (called dwells) that consumes energy, computing time and, crucially, antenna time. The radar must therefore continuously choose the dwells it performs in succession, which vary according to numerous parameters (duration, beam width, etc.), in order to track the detected targets while maintaining search over its surveillance space. Reinforcement learning could therefore provide a framework to address the challenges posed by the increased degrees of freedom in modern radar systems. It would allow for the development of intelligent agents that can learn from experience and effectively navigate the complex optimization landscape, optimizing the radar's dynamic resource allocation based on environmental conditions, operational requirements, and mission objectives.

However, the multi-function radar use case is also characterized by the presence of multiple tasks to be performed in parallel. The balance between these tasks and the consideration of their interaction represent a combinatorial problem. Combinatorial aspects have been studied in both model-based and model-free reinforcement learning: they represent a key issue, as their exploitation allows extending reinforcement learning methods to large-scale systems. In addition, the performance of each task can be evaluated by a separate criterion, which lends itself to a multi-objective approach. Multi-objective reinforcement learning addresses these problems by learning from multiple reward functions: this allows the agent to take into account trade-offs between different objectives. This combination of combinatorial and multi-objective aspects represents a convincing perspective for the development of learning agents capable of handling more complex systems.

In this work, we present the following contributions:

• we propose applications of reinforcement learning techniques adapted to the current architecture of multi-function radars. These contributions focus on two aspects: antenna-level scheduling by model-based methods and active tracking optimization by model-free methods. We also highlight the limitations of current resource management architectures, which leads us to consider an alternative architecture and to conclude that current reinforcement learning methods do not immediately solve the problems raised by these alternatives.

• we investigate new reinforcement learning algorithms to address the problems raised by this alternative architecture. These contributions concern both the multiobjective aspect, which is useful in multi-function radars to reflect the trade-offs to be made between the different functions, and the combinatorial aspect, which is due to the large number of tasks that the radar must carry out in parallel.

The first contribution is specifically aimed at the conjunction of multi-objective learning and factorized MDPs, which is a formalism that allows to exploit the internal structure of complex environments. The second contribution focuses only on the multi-objective side: it consists in proposing an algorithm allowing to specify the agent's objective by a non-linear utility function, which would allow to better translate the preferences of the radar operators.

The outline of the dissertation is as follows:

• In chapter 1, we give an overview of the aspects of a multi-function radar system relevant to our work, especially the resource management components.

• In chapter 2, we present the main concepts and algorithms of reinforcement learning.

• In chapter 3, we present our applications of reinforcement learning techniques to current multi-function radars for scheduling and active tracking.

• In chapter 4, we propose multi-objective reinforcement learning algorithms, focusing first on combinatorial environments, and then on stochastic environments

INTRODUCTION

where the objective is defined by non-linear scalarization.

Chapter 1

An overview of multi-function radars

A radar (Radio Detection And Ranging) is a type of sensor that uses electromagnetic wave echoes to detect and locate objects in its environment. While radars have many applications ranging from flight control to weather forecasting, the use case considered in this thesis is that of a land or maritime radar dedicated to air surveillance in a military context. In this context, radars are mainly used to search for objects entering its surveillance space, to identify them, and to track their movement.

Radars are complex systems involving multiple aspects: high-performance hardware is required to deliver electromagnetic signals of sufficient power; signal processing is necessary to extract meaningful detections from raw sensor data; data processing uses these detections to estimate the presence and characteristics of targets in the radar's environment. Multi-function radars (MFR) use electronically steered phased array antennas, which gives them a certain amount of beam agility thanks to which they are able to carry out several functions in parallel, mainly searching and tracking. This adds a further aspect, resource management, as the radar has to balance its resources between each of its different functions. In this chapter we present an overview of MFRs and discuss the components relevant to this thesis.

Radar fundamentals

In our use case, the radar's main role is to produce position and velocity measurement of distant objects. These measurements are obtained by catching radio signals emitted by these objects via a receiving antenna. Passive radars only use a receiving antenna, while active radars additionally employ an emitting antenna which transmits waves of electromagnetic energy. The environment scatters the energy, and some of the scattered energy is subsequently detected by the receiving antenna. In this thesis, we assume an active monostatic radar, i.e. one that uses the same antenna to transmit and receive signals.

In this section, we explain how the radar creates its emissions, how these interact with the environment to determine the signal received by the radar (as modeled by the radar equation), and what measurements can be obtained from these signals.

Dwell model

The radar's emissions are organized by dwells. A dwell is the combination of an illumination law, which dictates the direction and shape of the electromagnetic wave (known as a beam), and a waveform, which corresponds to the structure of the emitted signal.

The idea is to create waveforms with characteristic patterns, so that when the radar receives a signal, it tries to find an echo of this pattern to infer the presence of the target that reflected the signal back. A waveform is composed of one or more bursts; a burst is in turn a series of pulses. Each burst is parameterized by the number N p , frequency 1/T p , and duration τ of its pulses and by the frequency f of the carrier wave used (or alternately, its wavelength λ = c f ). T p is known as the pulse repetition interval (PRI) and τ as the pulse width; together they define the burst's duty cycle D = τ Tp which is the ratio of time spent emitting. These parameters define the observation time T obs which is the effective duration of the emitted signal:

T obs = T p N p D (1.1)
Varying these parameters from one burst to another also allows limiting the losses and the ambiguities in the received signal. The accumulation of these pulses (by integration) makes it possible to obtain a signal strong enough to allow detection. Since this thesis is focused on the downstream resource management aspect, we do not detail the signal processing component and only provide an energetic model.

Figure 1.2: Structure of a burst with N p = 3.

Beamforming

An electronically scanned phased-array antenna, like the ones used in multi-function radars, comprises an array of radiating elements whose phase and amplitude can be controlled. Array control in modern antennas is fast enough to allow for highly-maneuverable and adaptable beamforming. Thanks to these beamforming capabilities, the antenna can focus its emitting power P in a given direction. This concentration of power is modeled by its transmit gain g t :

g t = 4π A e λ 2 (1.2)
where A e = ηA T is the antenna's effective aperture area, with η the aperture efficiency and A T the actual aperture area. The sum of the emissions of each element creates a radiation pattern with a main lobe and several side lobes. The main lobe is characterized by its half-power beamwidth:

θ 3dB = 0.886λ l (1.3)
where l = lη is the length of aperture and l is the length efficiency. As we can see, the wavelength λ and the aperture efficiency η both have opposite effects on the gain and the beamwidth: therefore we cannot increase the beamwidth without decreasing the gain. Phased-array antennas also allow steering the pointing angle of the main beam by applying linear phase increments to each array element. However, when the angle between the center of the beam and the center of the antenna θ b|a increases, this also increases the deflection loss:

L s = cos(θ b|a ) -1 (1.4)
which affects both the effective transmit gain and the half-power beamwidth. Intuitively this makes the beam larger and therefore less "focused", which reduces the gain at the center of the beam:

gt = g t L s (1.5) θ3dB = L s θ 3dB (1.6)
When the target is offset from the center of the beam by an angle θ t|b , the directed power received by the target P is further decreased relative to the antenna's peak power P [START_REF] Blackman | Design and Analysis of Modern Tracking Systems[END_REF]:

P = P exp -F θ t|b 2 θ2 3dB (1.7)
where F is a constant. If the target is offset from the beam by an angle corresponding to the half-power beamwidth, i.e. θ t|b = θ3dB 2 , then by definition P = P 2 , from which we can deduce the value of the constant F = 4 ln 2 [START_REF] Blackman | Design and Analysis of Modern Tracking Systems[END_REF].

The radar equation

Assuming the target is situated at range R, we can model the power P emitted by the antenna as distributed over a sphere of area 4πR 2 . By factoring in the effective transmit gain gt , the antenna power that reaches the target is therefore:

P gt 4πR 2
(1.8)

The "reflectiveness" of a target is characterized by its radar cross section σ. Then, similarly, the fraction of power reflected back to the antenna by the target is given by: σ 4πR 2

(1.9)

Finally, this signal is intercepted by the antenna's effective aperture A e = 4π gt λ 2 . Since the antenna is monostatic, the receive gain g r is equal to the transmit gain g t .

Therefore the deflection loss L s applies twice. The energy received by the radar combines these three terms and the observation time T obs and is expressed by the radar equation [START_REF] Skolnik | Radar Handbook[END_REF]:

E r = P gt 4πR 2 σ 4πR 2 λ 2 gr 4π T obs (1.10)
The radar equation is a fundamental formula that can be used for radar design and performance estimation of a given radar system. In particular, it allows reasoning about the ratio between received signal energy and noise, which determines the radar's detection capabilities and is called the signal-to-noise ratio (SNR):

SN R = 2E r N (1.11)
where N = N 0 B is the noise power. Here B = 1 τ represents the radar's bandwidth and N 0 = kT s is the receiver thermal noise. N 0 depends on the Boltzmann constant k and the effective temperature T s = F n T 0 where F n is the antenna's noise factor and T 0 = 290K is the ideal temperature.

The higher the SNR, the simpler the signal will be to detect and provide accurate information about the target. The radar equation informs us on how we can increase the SNR, namely by decreasing the beam width θ 3dB (which increases the directed power P ) or by increasing the observation time, which both increase the amount of energy emitted at the center of the beam. On the other hand, the larger the offsets θ b|a between the antenna and the beam on one hand and θ t|b between the beam and the target on the other hand, the lower the returned signal, and thus the SNR, will be [START_REF] Barton | Radar System Analysis and Modeling[END_REF].

The radar equation can also be rearranged to express the detection range of a dwell given a required SNR:

R = 4 P gt • σ • λ 2 gr • T obs (4π) 3 • N • SN R
(1.12)

Position and velocity measurements

When the transmitted signal encounters a target, it is reflected and its echo reaches the antenna. The distance R between the target and the radar can be inferred from the time ∆t between transmission and reception, during which the signal makes a round trip at the speed of light c:

∆t = 2R c
(1.13) Figure 1.3: Emitted signal at the top, delayed received echo at the bottom.

Targets can only be distinguished from each other if the radial distance separating them is greater than the radar's range resolution R res . The range resolution corresponds to the distance traveled during the duration of the pulse width τ :

R res = cτ 2 (1.14)
Sending several pulses may create range ambiguities if a pulse is received and its associated original transmit pulse cannot be determined. This can happen for targets beyond the unambiguous range R una , which depends on the pulse repetition interval:

R una = T p c 2 (1.15)
The radial velocity v r of the target causes a shift between the frequencies of the emitted and received signals. This Doppler shift f d can be used to infer v r :

f d = 2v r λ (1.16)
The Doppler resolution is inversely proportional to the duration of the coherent pulse train. Similarly to range ambiguities, Doppler ambiguities happen at high pulse repetition intervals when it is unclear how many multiples of the pulse repetition frequency are contained in the measured Doppler shift.

k s (θ) = ∆(θ) Σ(θ) (1.17)
The sensitivity of the measurement is determined by the gradient of the discrimination slope k ′ s (θ) and is expressed as k m = k ′ s (0), which corresponds to the point where the measurement slope and the measurement axis intersect.

The beamwidth and signal-to-noise ratio affect the receiver's thermal noise, which is reflected in the angular error standard deviation:

σ θ = θ3dB k m √ 2SN R (1.18)
Furthermore, if the target is off the center of the beam by an angle θ t|b , then the effective angular accuracy σθ further decreases as a factor of the beamwidth:

Data processing

The signal processing components of the radar produce raw measurement data. This data must however be further processed to distinguish clutter (i.e. false detections) from real targets and to infer the trajectories of these targets from sequential detections.

Detection

Data obtained in the signal processing phase first goes through a detection phase. The idea is to test the hypothesis H 0 of absence of a target and the hypothesis H 1 of presence of a target in the received echo. This test is not carried out on each pulse of the dwell, since the pulses are individually too weak to allow detection. Instead, the pulses can be combined to improve detection in a process known as integration. The two main types of integration are coherent integration, when the amplitude and phase of the signal are taken into account, and incoherent integration, when only the amplitude is used.

This process entails a trade-off between the probability of detection P d , which is when a real target is correctly detected, and the probability of false alarm P f a , which is when noise in the receiver is incorrectly interpreted as a target. For a desired probability of false alarm, the optimal decision is defined as a threshold T on the likelihood ratio

Λ(x) = p(x | H 1 ) p(x | H 0 ) of an observation x, such that H 1 is chosen if Λ(x)
> T , H 0 otherwise; the probability of false alarm determines the threshold, as P f a = p(x > T | H 0 ). Assuming a square law envelope detector, the probability of false alarm can be written as P f a = e -T .

For a given detection threshold, the probability of detection depends on the fluctuation model of the target. For example, in Swerling models 1 and 2, complex targets are modeled as multiple small scatters, and the associated probability of detection is approximated as a function of SNR and probability of false alarm:

P d = P 1 1+SN R f a (1.20)
As a consequence, to increase the probability of detection, one must increase the detection threshold, yet this will also result in a higher probability of false alarm, so that a trade-off between missed targets and false alarms must be made.

Tracking

When a detection occurs, the information is transmitted to a tracking module. A tracking module is composed of a filtering algorithm, a data associator, and a track manager. The filter's role is to estimate and predict the trajectory of the detected targets. Data association establishes correspondences between received detections and existing tracks.

Finally, track management determines the life cycle of tracks, in particular when to create a track and when to delete it.

Filtering

The most common filtering algorithm for radars is the Kalman filter. Given linear models with Gaussian perturbation describing the target kinematics and its measurement function, the Kalman filter provides a closed-form solution to estimate the target state (position, velocity, possibly acceleration) and the variance of the estimation error (i.e. the tracking accuracy) from the observations collected by the antenna, and to give a prediction on the evolution of this state. In this framework, the evolution of the target's state in Cartesian coordinates x t = [x, ẋ, y, ẏ] ⊤ at time t is described by the linear equation:

x t = A t x t-1 + w t-1 (1.21)
where A t is the transition matrix and w t-1 is the process noise with covariance Q t , which together form the transition model. Similarly, measurements z t are represented as derived from the underlying state by a linear transformation:

z t = H t x t + v t (1.22)
where H t is the measurement matrix and v t is the measurement noise with covariance R t , which together form the measurement model. The value of R t can be readily derived from the range and angle accuracy estimations in section 1.1.4. The mean and covariance are estimated iteratively in three phases, starting with a prediction phase:

x- t = A t xt-1 (1.23a) P - t = A t P t-1 A ⊤ t (1.23b)
This is followed by a measurement phase which uses the measurement z t to determine the innovation covariance matrix S t , the measurement residual δ t and the gain K t :

δ t = z t -H t x- t (1.24a) S t = H t P - t H ⊤ t + R t (1.24b) K t = P - t H ⊤ t S -1 t (1.24c)
Finally, the update phase corrects the estimates:

xt = x- t + K t δ t (1.25a) P t = (I -K t H t )P - t (1.25b)
Variations of this algorithm such as the extended Kalman filter and the unscented Kalman filter allow to take into account non-linear transition models.

Another issue is that most often the target dynamics will evolve over time, which requires switching between different transition models when the target maneuvers. The most effective approach is the Interacting Multiple Model (IMM). On a given track, the IMM applies several filters in parallel, each using a different transition model. The IMM uses the measurements to evaluate the likelihood of each model and assign them a probability, taking into account the a priori transition probability matrix between models. The combined state estimate is a mean over the estimates of the different models, weighted by their respective probabilities.

More formally, an IMM is parameterized by N models (e.g. Kalman filters), where each model i has an initial probability µ i 0 and the probability of transition from model i to j is p ij . The IMM maintains estimated states, covariances, and probabilities (x i t , P i t , µ i t ) for each model i. Similarly to the Kalman filter, the IMM goes through three phases, applied in parallel to each model j. The prediction phase takes the transition probabilities and the current estimated model probabilities to form a prediction for each model j:

μj t = N i=1 μi t-1 p ij (1.26a) μij t = μi t-1 p ij μj t (1.26b) x(j) t-1 , P(j) t-1 = combination((x i t-1 , Pi t-1 , μij t ) 1⩽i⩽N ) (1.26c) xj t , Pj t = prediction(x (j) t-1 , P(j) t-1 ) (1.26d)
where the per-model prediction is that of a Kalman filter as in eq. (1.23) and the combination forms new estimates of the state and covariance based on the updated model probabilities:

x = N i=1 µ i x i (1.27a) P = N i=1 µ i [P i + (x i -x)(x i -x) ⊤ ] (1.27b)
The predicted estimates of each model then go through the measurement phase spe-CHAPTER 1. AN OVERVIEW OF MULTI-FUNCTION RADARS cific to each Kalman filter (cf. eq. (1.24)):

δ j t , S j t , K j t = measurement(x j t , Pj t , z t ) (1.28)
The measurements are used to update the state and covariance according to each model (cf. eq. (1.25)) and the model probabilities according to their likelihoods Λ j t :

xj t , Pj t = update(x j t , Pj t , δ j t , S j t , K j t ) (1.29a) Λ j t = 1 |2πS j t | exp(- 1 2 (δ j t ) ⊤ (S j t ) -1 (δ j t )) (1.29b) μj t = Λ j t μj t N i=1 Λ i t μi t (1.29c)
Finally, the aggregated estimates of the state and covariance are obtained through a combination from each model weighted by their probabilities:

xt , Pt = combination((x j t , Pj t , μj t ) 1⩽j⩽N ) (1.30)

Transition models

The definition of adequate transition models is a major problem for radar systems:

different models are needed to cover all the maneuvers that can be performed by a given type of target. Among the most commonly used models for linear dynamics are constant nth-derivative models, which describe the evolution of an arbitrary position coordinate x by assuming that its nth-derivative x (n) remains approximately constant over time while its (n + 1)th-derivative is represented by a white noise process of strength q. This can be described in terms of stochastic differential equations as:

dx (n-1) = x (n) • dt (1.31a) dx (n) = q • dW t with W t ∼ N (0, q 2 ) (1.31b)
For n = 1, this yields a constant velocity model with white noise acceleration applied to a state x t = [x, ẋ] ⊤ that has the following matrix form:

A t =   1 dt 0 1   (1.32) Q t =   dt 3 3 dt 2 2 dt 2 2 dt   q (1.33)
Similarly, for n = 2, we obtain a constant acceleration model with white noise jerk applied to a state x t = [x, ẋ, ẍ] ⊤ :

A t =      1 dt dt 2 2 0 1 dt 0 0 1      (1.34) Q t =      dt 5 20 dt 4 8 dt 3 6 dt 4 8 dt 3 3 dt 2 2 dt 3 6 dt 2 2 dt      q (1.35)
To describe maneuvers, constant turn models can be used. In these, the target is assumed to move at constant velocity with a constant turn rate ω in an (x, y) plane. For state x t = [x, ẋ, y, ẏ] ⊤ and acceleration noise coefficients q x and q y , the matrix form of a constant turn model is:

A t =         1 sin ωdt ω 0 -1-cos ωdt ω 0 cos ωdt 0 -sin ωdt 0 1-cos ωdt ω 1 sin ωdt ω 0 sin ωdt 0 cos ωdt         (1.36) Q t =         q 2 x dt 3 3 q 2 x dt 2 2 0 0 q 2 x dt 2 2 q 2 x dt 0 0 0 0 q 2 y dt 3 3 q 2 y dt 2 2 0 0 q 2 y dt 2 2 q 2 y dt         (1.37)
Alternative linear models include nth-derivative decay models, where the nthderivative exponentially decays to zero over time. Similarly to before, the (n + 1)thderivative is described by a white noise process of strength q:

CHAPTER 1. AN OVERVIEW OF MULTI-FUNCTION RADARS

dx (n-1) = x (n) • dt (1.38a) dx (n) = -Kx (n) • dt + q • dW t with W t ∼ N (0, q 2 ) (1.38b)
These are called Ornstein-Uhlenbeck models and Singer models for n = 1 and n = 2 respectively.

Data association

Data association is required to determine if a detection corresponds to one of the existing tracks before its tracking filter can be updated. This is necessary to avoid updating tracks with false alarms caused by thermal noise or clutter, or when multiple targets are present in the environment. The problem is compounded when multiple detections occur (near-)simultaneously. This involves considering all association hypotheses between each detection and each track.

The first step is to filter out the most unlikely hypotheses. To do so for a given hypothesis, the gap between the track's predicted measurement and the detection measurement is evaluated with a chosen measure, and the hypothesis is rejected if the distance between the two measurements exceeds a predefined threshold. A common measure is the Mahalanobis distance

δ t S -1 t δ t (1.39)
where S t is the innovation covariance matrix and δ t the measurement residual as defined in 1.25. The advantage of this distance is that it takes into account the uncertainty of the Kalman filter over the actual position of the target.

Once unlikely hypotheses have been excluded, track-detection association can be performed. The simplest method is global nearest neighbor (GNN), which assigns each detection to a track in a way that minimizes the sum of distances between the detections and the track predictions. A more computationally-intensive alternative is probabilistic data association (PDA), where each hypothesis is assigned a probability and tracks are updated with the weighted average of their associated hypotheses.

Track management

The management of a track is generally organized in the form of a life cycle, with logic rules defining the transitions between the different stages of the cycle: when a new target is detected, a certain number of confirmation hits are usually required before initiating the track; the track must then be updated regularly to maintain a desired level of accuracy; if no detection is made at the expected location of the target, a reacquisition procedure can be initiated; finally, after a certain number of missed detections or if a

given track metric such as angular covariance exceeds a given threshold, the target is considered lost and the track is abandoned. More advanced methods make use of Markov chains or estimate the likelihood of the track to determine its status.

Furthermore, due to constraints on the radar's angular and radial resolution, targets that are too close together cannot be distinguished: it may therefore be necessary to merge or split tracks when targets move closer or further apart. Having to perform multiple functions in parallel poses a resource management problem. Radar resource management (RRM) consists in allocating resources such as time, power, and processing between functions according to the radar's mission, which sets the level of priority of each function. Among these resources, time budget is the most critical:

Resource management

it includes the transmission time, the waiting time (before the signal returns) and the reception time associated with each dwell played. The challenge is therefore to generate dwells that fulfill the various functions assigned to the radar with a limited antenna time. Using a rotating antenna (with a fixed rotation frequency) creates an additional constraint on the possible execution dates of the dwells. Since each task is performed by executing a number of dwells (or tasks), it is necessary to continuously schedule these dwells by assigning them order and execution times. All dwells have optimal execution times, and minimizing delays from these is one of the scheduling objectives. More importantly, it may happen that temporal constraints prevent from executing all dwells, which leads to an overload situation and forces the scheduler to drop some of them according to their level of priority.

Resource management also affects dwell optimization. The greater number of degrees of freedom for beamforming in MFRs means that the space of possible dwell configurations is significantly larger. This makes optimizing waveforms more difficult, especially for functions like tracking whose tasks must be dynamically adapted [START_REF] Moo | Adaptive Radar Resource Management[END_REF]. Moreover, the choice of dwell parameters should aim not only to maximize its function's performance, but also to lower resource requirements for the scheduler in order to avoid overload.

Resource management operates on the representation of the tactical situation around the radar in terms of tracks resulting from data processing. Radar resource management is generally divided into three phases, which we detail below: task management, prioritization and scheduling.

Figure 1.7: High-level view of a MFR.

Dwell optimization

Task management consists of generating the dwell parameters for the different functions of the radar.

For the search function, the relevant operational parameters include the detection threshold, the pattern of beams covering the surveillance space, and the revisit interval and observation time for each search dwell. Alert-confirm techniques are enabled by beam agility, where a lowered detection threshold acts as a first stage to produce alerts, followed by a confirmation dwell. The beam pattern over the surveillance space must take into account the spacing between the beams and the beam width, since larger beamwidths create larger losses when the target is offset from the centre of the beam, which can be compensated by a smaller spacing. Each of these correspond to a transmit beam, while the electronically scanned antenna allows to use multiple simultaneous receiving beams (cf. fig. 1.4), enabling higher angular resolution and faster search. Finally, the observation time and revisit interval of each dwell are inversely related and need to be balanced. Heuristic solutions using e.g. triangular search pattern are usually the nom, yet the need for resource management techniques that can adapt to dynamic and uncertain scenarios has prompted research into mathematical optimization applications for search patterns [START_REF] Briheche | Optimization of Search Patterns for Fixed-Panel Tridimensional Scanning Radars[END_REF].

Updating a track can be done in two ways: either by a dedicated dwell, which constitutes active tracking, or by exploiting the detections resulting from search dwells (Track-While-Scan, TWS). TWS is generally reserved for distant or low-threat targets.

Active tracking dwells are centered on the predicted target position, thus more accurate than a search dwell. Besides waveform parameters, which can improve range resolution when dynamically adapted, the critical parameter of active tracking is the track update rate, which must maintain the necessary track accuracy without using too much resource.

The classic approach to update rate selection is Blackman and Van Keuk's method, which selects the next update as the the earliest time after which the filter's angular prediction error surpasses a given fraction of the beamwidth. Tracking dwells length are usually chosen to maintain a desired SNR. Aside these heuristic methods, optimization approaches exist that include Q-RAM (Quality of Service Resource Allocation Method)

and information-theoretic optimization.

Figure 1.8: Maneuvering targets require higher update rates and may require to adapt the beam width.

Task prioritization and scheduling

The request managers corresponding to different radar functions continuously update a list of requested dwells. These dwells must then be assigned a priority level, which reflects how critical the dwell in question is to fulfill the radar's mission. This priority level may depend on mission parameters (e.g. prioritized search versus prioritized tracking), the nature of the associated task, or the threat level of a given target. It comes into play when the radar is overloaded, i.e. not all requested dwells can fit onto the antenna timeline and the system must select which dwells to postpone or abandon. In practice, priority assignment is determined by rule-based systems or by ranking dwells according to heuristically-computed scores.

Finally, the dwell requests and their priorities are transmitted to a scheduler whose goal is to program the order and the execution dates of the various dwells on the antenna, and to reject certain dwells if all the requests cannot be satisfied in the allotted time. The two main approaches are frame-based and best-first schedulers [START_REF] Blackman | Design and Analysis of Modern Tracking Systems[END_REF]. Frame-based methods attempt to fill in a fixed-duration time frame with dwell requests while a previous frame is being performed by the antenna, whereas best-first methods maintain a queue of dwell requests ordered by heuristic criteria and repeatedly retrieve the top dwell to execute it. Frame-based schedulers allow to minimize delays between the dwells' requested and effective execution time, while best-first schedulers are more reactive and ensure greater antenna occupancy.

Chapter 2

Reinforcement learning background

This chapter is intended to provide an overview of the foundations and main approaches in the field of reinforcement learning (RL). RL is one of the three main areas of machine learning, along supervised learning and unsupervised learning. The specificity of RL, in its basic setting, is that a learning agent interacts with an environment in order to discover by trial-and-error a behavior that maximizes a certain reward. RL is a very broad framework for artificial intelligence in general; it is a challenging research field with numerous promising potential applications.

RL was formalized in its modern form in the 1980s, even though it is built on a much longer history, notably tracing its origins back to the study of animal learning in 19th-century psychology and to Richard Bellman's work on optimal control and dynamic programming in the 1950s [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. The deep learning revolution of the early 2010s allowed RL to tackle problems that had seemed out of range before, and led to several high-profile successes in game playing that renewed interest in the field [START_REF] Mnih | Playing Atari with Deep Reinforcement Learning[END_REF][START_REF] Silver | Mastering the game of Go with deep neural networks and tree search[END_REF][START_REF] Vinyals | Grandmaster level in StarCraft II using multi-agent reinforcement learning[END_REF]. As a result, over time, a great variety of approaches have been developed, each with their own strengths and weaknesses.

Given the sequential decision-making problem at the heart of radar resource management, RL provides an appealing alternative to existing techniques. The versatility of RL and the wide range of methods developed for it mean it can be applied in different ways and to different aspects of the radar problems at hand. Our intent here is to present a large gamut of RL approaches, so that we can later discuss their applicability to radar use cases in the context of our work.

First we describe the RL framework, with its formalization, objective and learning process (section 2.1). We then go over the three main families of algorithms designed to solve RL problems in their basic setting: value-based, policy-based, and model-based methods (sections 2.2 to 2.4). We finally discuss a number of specialized techniques, alternative models and extensions to RL; as RL is a growing field with many research directions, we only give a short overview of these, but focus especially on multi-objective RL, as part of our work is dedicated to methods falling in this domain.

The RL framework

This section describes the basics of RL. RL deals with stochastic sequential decisionmaking problems. The learner and decision-maker, called an agent, interacts with an environment, starting from an initial state; at each time step, when the agent selects an action to take, it transitions to a new state and receives a reward. The general objective is to maximize the cumulative sum of rewards [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Francois-Lavet | An Introduction to Deep Reinforcement Learning[END_REF].

Markov Decision Processes

The basic RL setting is usually formalized as a Markov decision process (MDP). An MDP is defined as:

• a finite state space S;

• a finite action space A;

• a transition function T : S × A × S → [0, 1], which gives the conditional probability T (s ′ | s, a) of transition to the next state s ′ given the previous state s and selected action a;

• a reward function R : S × A × S → R that gives the expected reward associated with a transition. We may overload this notation with

R(s, a) = s T (s ′ | s, a) R(s, a, s ′ ).
Note that a reward can be negative and "punish" the agent.

When the agent interacts with the environment, it thus creates a sequence of states, actions, and rewards: starting from an initial state s 0 ∈ S sampled from the distribution of initial states µ 0 , it takes an action a 0 ∈ A, then transitions to a new state s 1 according to T and receives a reward r 1 according to R; this process repeats in every state, yielding a sequence (s 0 , a 0 , r 1 , s 1 , a 1 , r 2 , s 3 , ...).

A distinction is made between continuing and episodic settings. In the episodic setting, there is a terminal state s T : when this terminal state is reached, the agent is brought back to the initial state and starts a new episode.

It is also useful to model problems in which the agent does not have a full view of its environment and may as a consequence be unable to distinguish between similar states. This property is called partial observability. Partially observable MDPs (POMDPs) include an additional function O : S × Ω → [0, 1] which is a conditional probability over the observation ω ∈ Ω made by the agent in the current state. Most real-life applications of RL correspond to POMDPs, which makes partial observability a transversal issue in the field.

The goal of an RL agent is to find a policy that maximizes the sum of its rewards.

A policy determines the action to take according to the current state. Policies can be stochastic: π : S × A → [0, 1] and give a conditional probability over the next action, or they can be deterministic: π : S → A.

In order to keep the sum of rewards finite, a discount factor γ ∈ [0, 1) is usually introduced that makes short-term rewards more valuable than long-term ones. We can then define the state-value function V π , which gives the value of a state s under policy π, that is, the expected return starting in s if the agent follows π:

V π (s) = E π ∞ k=0 γ k R t+1+k | S t = s (2.1)
with R t = R(S t-1 , A t-1 , S t ) a random variable of the reward at step t. State-value functions verify a recurrent relationship known as the Bellman equation:

V π (s) = a∈A π(a|s) s ′ ∈S T (s ′ | s, a)[R(s, a, s ′ ) + γV π (s ′ )] (2.2)
In control tasks, the goal is to find a policy that yields the optimal state-value function:

V * (s) = max π∈Π V π (s) (2.3)
where Π is the policy space. The policy associated with this optimal value function is the optimal policy π * . This optimal state-value function verifies a specific recurrent relationship known as the Bellman optimality equation:

V * (s) = max a∈A s ′ ∈S T (s ′ | s, a)[R(s, a, s ′ ) + γV * (s ′ )] (2.4)
Other value functions are used that are more practical for action selection, namely the action-value function Q and the advantage function A, which follow similar recurrent relationships:

Q π (s, a) = E π ∞ k=0 γ k R t+1+k | S t = s, A t = a (2.5) A π (s, a) = Q π (s, a) -V π (s) (2.6)

Classes of algorithms

An RL agent includes one or more of the following components (Francois-Lavet et al.,

2018):

• a representation of a value function that provides a prediction of how good each state or each state/action pair is (this estimate is denoted by V to distinguish it from the true value function V π );

• a direct representation of the policy;

• a model of the environment (the estimated transition function and the estimated reward function).

This allows to distinguish different approaches to RL problems.

Value-based methods (section 2.2) learn a value-function and derive a policy from it, whereas policy-based methods (section 2.3) directly learn their policy. Actor-critic methods are an intermediate approach where one component, the actor, directly improves the current policy while using value-function estimates provided by the second component, the critic.

Model-free methods are based solely on this kind of learning. Model-based methods (section 2.4), on the other hand, only learn a model of the environment, then use a planning algorithm to find an optimal policy. Again, intermediate algorithms may do both learning and planning. Note that representations of a value function or of the policy are also fundamentally models of the agent's knowledge about its environment; however in the context of RL, "model" usually designates a model of the environment.

During the learning process, once the agent has started gathering knowledge about its environment through experience, it faces a choice in every state: it can either select the action that maximizes the expected return according to current knowledge (the greedy action), or it can select another, a priori suboptimal action which could potentially lead to greater rewards. A trade-off has to be made between exploiting the best strategy found so far, and further exploring the environment to determine if a better strategy is to be found.

This dilemma between exploration and exploitation is especially important when the agent faces sparse, delayed rewards (such rewards give rise to the credit assignment problem). This problem is primarily studied in the context of k-armed bandits, which are MDPs with only one state: the objective is to determine as fast and reliably as possible which action yields the highest rewards. The simplest approach to balancing exploration and exploitation is to choose actions in an ϵ-greedy way: at each step, a random action is chosen with probability ϵ < 1, otherwise the agent takes the greedy action.

Additionally, RL methods are often classified as on-policy or off-policy. According to the definition given in [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], on-policy methods attempt to evaluate or improve the policy that is used to make decisions, whereas off-policy methods evaluate or improve a policy different from that used to generate the data. On-policy methods are unbiased and tend to be more stable. Off-policy methods, by leveraging data from different sources, facilitate exploration, are more data-efficient, and more general: they can learn from demonstrations, only they can be used in the offline setting. However, off-policy methods usually necessitate special means to correct the bias that comes from trying to learn a policy while exploring with another.

Approximation and generalization

The first RL algorithms addressed discrete problems and followed the tabular approach, storing the value of every state or action-state pair. This proved impractical for most applications for several reasons: the number of states increases exponentially in the number of state variables (which is known as the curse of dimensionality), the problem can be set with a continuous state space or action space, or it can be partially observable.

These shortcomings can be overcome with function approximation. In this approach, a parameterized function is used to approximate the components of the learning algo-rithm (cf. section 2.1.2). Initially, the most common choice for approximation was to use linear functions. However, in recent years, major breakthroughs were achieved in high-dimensional problems using non-linear function approximation with deep neural networks [START_REF] Goodfellow | Deep Learning[END_REF], giving birth to deep reinforcement learning. Common neural networks architectures like convolutional neural networks (CNN; [START_REF] Lecun | Convolutional networks for images, speech, and time-series. The handbook of brain theory and neural networks[END_REF], recurrent neural networks (RNN; [START_REF] Hochreiter | Long Short-Term Memory[END_REF],

and Transformers (Vaswani et al., 2017) have been applied successfully to RL problems [START_REF] Mnih | Playing Atari with Deep Reinforcement Learning[END_REF][START_REF] Hausknecht | Deep Recurrent Q-Learning for Partially Observable MDPs[END_REF][START_REF] Zambaldi | Relational Deep Reinforcement Learning[END_REF].

Despite empirical success, function approximation creates additional challenges. For instance, methods employing it in conjunction with bootstrapping and off-policy learning display increased instability and divergence. [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] call this combination the deadly triad. Stabilizing off-policy learning remains a key issue in the field.

Function approximation represents a major step towards agents that can generalize the information obtained about a given state to similar states. One of the main objectives in RL research remains to design agents that generalize better. Generalization is defined as the ability of an agent to perform well in an environment about which it knows little, either because it has gathered limited information in this environment, or because this environment differs slightly (with regard to transition or reward) from the one used for learning [START_REF] Francois-Lavet | An Introduction to Deep Reinforcement Learning[END_REF].

The ability to learn from as little data as possible is also termed sample efficiency.

Sigaud and Stulp (2019) distinguish three aspects of sample efficiency:

• data efficiency consists in extracting as much information as possible from the available data,

• sample choice consists in collecting the most informative data from the environment, and

• sample reuse consists in improving the agent's knowledge several times with the same sample.

To date, state-of-the-art RL algorithms remain significantly sample-inefficient compared to human learners: deep RL especially requires vast amounts of computational power to solve complex tasks. Numerous research directions attempt to alleviate this core difficulty, ranging from multi-task RL [START_REF] Espeholt | IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures[END_REF][START_REF] Hessel | Multitask Deep Reinforcement Learning with PopArt[END_REF][START_REF] Hausman | Learning an Embedding Space for Transferable Robot Skills[END_REF] to meta-RL [START_REF] Duan | RL 2 : Fast Reinforcement Learning via Slow Reinforcement Learning[END_REF][START_REF] Oh | Discovering Reinforcement Learning Algorithms[END_REF] to data-augmentation [START_REF] Kostrikov | Image Augmentation Is All You Need: Regularizing Deep Reinforcement Learning from Pixels[END_REF][START_REF] Wang | VRL3: A Data-Driven Framework for Visual Deep Reinforcement Learning[END_REF] and pre-training techniques [START_REF] Parisi | The Unsurprising Effectiveness of Pre-Trained Vision Models for Control[END_REF][START_REF] Driess | Reinforcement Learning with Neural Radiance Fields[END_REF].

Value-based methods

We begin our overview of RL algorithms with the original approach to the field, valuebased methods. Such methods try to estimate a value function from which they can derive a policy. Under the scheme of generalized policy iteration, the value function estimated from data generated by the current policy is used to improve this policy until both value function and policy converge towards optimality. Value-based methods can be tabular or approximate [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. The methods presented in this section and the next are model-free methods set in the online setting.

Tabular methods

Monte Carlo methods

Monte Carlo methods are the most straightforward way to estimate value functions in the episodic setting. They are based on averaging complete returns in an incremental manner. For example, in the prediction task, a full episode is generated by following the policy π to evaluate; then, the value of every visited state s t is updated:

V (s t ) ← V (s t ) + α[G t -V (s t )], with α = 1 T (s t ) , G t = T -t-1 k=0 γ k r t+1+k = r t+1 + γG t+1 , G T = 0 (2.7)
where T (s t ) is the number of times s t was visited across all episodes and G t is the discounted return from time step t to episode end T . State values are initialized arbitrarily (usually 0). The process is repeated until convergence.

Here G t is the target towards which we correct the estimated value function, and the parameter α is the step size which defines how much the estimate can change at each time step. The step size can also be a constant. This update is an instance of the general update rule used for estimates in RL:

NewEstimator ← OldEstimator + StepSize × [Target -OldEstimate] × Direction (2.8)
The difference [Target -OldEstimate] is called the error.

In the control task, a similar update is performed for the action-value function estimate of each visited state-action pair Q w (s, a) and a simple policy improvement updates the policy: π(s) ← argmax a Q w (s, a) (the policy is also initialized arbitrarily). To ensure exploration, soft policies must be used, i.e. policies that maintain a non-zero probability for all actions. The most common choice is ϵ-greedy policies.

The above applies to the on-policy setting. Monte Carlo methods can also be offpolicy, generating information with a behavior policy b to learn a target policy π. The most common technique for estimating expected values under one policy given samples from another is importance sampling, whereby returns are weighted by an importancesampling ratio:

G ρ t = ρ t:T -1 T -t-1 k=0 γ k r t+1+k , with ρ t:T -1 = T -1 k=t π(a k |s k ) b(a k |s k ) (2.9)
Such techniques, though, usually increase the variance of the target. There are variants that limit this increase in variance, such as per-reward importance sampling, which weights every reward with the adequate ratio, instead of weighting the whole sum of rewards:

G ρ t = T -t-1 k=0 ρ t:t+k γ k r t+1+k = ρ t (r t+1 + γG t+1 ), ρ t = ρ t:t (2.10)
Unfortunately, pure Monte Carlo methods are restricted to the episodic setting and are computationally inefficient. Temporal-difference methods aim to correct these defects.

Pure bootstrapping

Temporal-difference (TD) methods are a blend of Monte Carlo methods and dynamic programming: they learn from samples of experiences yet bootstrap on previous (action-)state values. Updates of the estimate are performed at each time step, in an on-line fashion, which makes TD methods usable in the continuing setting and more sampleefficient than Monte Carlo methods.

For example, the TD(0) algorithm solves the prediction problem by updating the state-value function in the following way at each step (s t , a t , r t+1 , s t+1 ) generated by the policy being evaluated:

V (s t ) ← V (s t ) + α[r t+1 + γV (s t+1 ) -V (s t )]
(2.11)

The update error r t+1 + γV (s t+1 ) -V (s t ), named the TD error in this context, is often noted δ t .

The update for Sarsa, an on-policy control algorithm, is similar, using the sequence (s t , a t , r t+1 , s t+1 , a t+1 ) generated at each step by the policy π being learned; this must be a soft policy, greedy with regard to the action-state function Q:

Q(s t , a t ) ← Q(s t , a t ) + α[r t+1 + γQ(s t+1 , a t+1 ) -Q(s t , a t )]
(2.12)

Another algorithm, Q-learning, adapts the approach to off-policy control. The behavior policy is still a soft policy derived from Q, but the target policy is deterministically greedy with regard to Q. This is reflected in the target of the update:

Q(s t , a t ) ← Q(s t , a t ) + α[r t+1 + γmax a Q(s t+1 , a) -Q(s t , a t )] (2.13)
Finally, Expected Sarsa can be either on-policy or off-policy. The target of the update is expressed as an expectation over the next action according to target policy π.

The soft behavior policy can be identical to π, or it can be derived from Q in another way. Expected Sarsa includes Q-learning as a special case. The update is:

Q(s t , a t ) ← Q(s t , a t ) + α r t+1 + γ a π(a|s t+1 )Q(s t+1 , a) -Q(s t , a t ) (2.14)

Multi-step bootstrapping

A significant improvement to TD methods is brought by n-step bootstrapping. In this scheme, updates are delayed by a number n of steps, and the target of the update includes the (discounted) rewards accumulated during this delay. Multi-step bootstrapping is an intermediate between one-step bootstrapping and Monte Carlo methods, and usually performs better than both by propagating rewards faster. As an example, the update for on-policy n-step Sarsa for time step t becomes:

Q t+n (s t , a t ) ← Q t+n-1 (s t , a t ) + α[G t:t+n -Q t+n-1 (s t , a t )], G t:t+n = t+n-1 k=t γ k-t r k+1 + γ n Q t+n-1 (s t+n , a t+n ) (2.15)
where Q t+n refers to the estimate of Q at time step t + n.

Off-policy n-step bootstrapping can be implemented in two ways. The first one is to use importance sampling. The second one, put forth in the Tree-Backup algorithm, is to generalize Expected Sarsa's target to every step of the delayed update; the resulting target is defined recursively as:

G T B t:t+n = r t+1 + γ a π(a|s t+1 )Q t (s t+1 , a) + γ c t+1 (G t+1:t+n -Q t (s t+1 , a t+1 )) = Q t-1 (s t , a t ) + t+n-1 k=t k i=t+1 γc i r k+1 + γ a π(a|s k+1 )Q k (s k+1 , a) -Q k-1 (s k , a k ) (2.16)
where G t+1:t+1 = Q t (s t+1 , a t+1 ), and c i = π(a i |s i ) is the coefficient that corrects the off-policy discrepancy.

All these algorithms were designed for the tabular setting. This facilitates theoretical analysis, especially regarding proofs of convergence. However, approximate methods, despite being less theoretically grounded, allow application in more complex environments with a large or continuous state space.

Approximate methods

Usually, the goal set for RL algorithms with function approximation is to minimize a loss function, the mean squared value error:

L V (w) = E s∼µ b [(y -V w (s)) 2 ] (2.17)
where µ b (s) is a probability distribution over states, proportional to the time spent in each state while learning with behavior policy b (known as the on-policy distribution), y is the target of the update, and V w (s) (or V (s ; w)) is the value of state s approximated with weight vector (or parameter vector) w. This loss function is in turn optimized by gradient descent, which is another instance of the general update rule (eq. (2.8)), performed at every step t:

w t+1 ← w t - 1 2 α∇ wt L V (w t ) i.e. w t+1 ← w t + αE s∼µ b [(y t -V wt (s t ))∇ wt V wt (s t )]
(2.18)

For practical purposes, stochastic gradient descent (SGD) is used, whereby the expectation is evaluated as a sum over a minibatch of transitions. A similar loss function L Q (w) can be defined for the action-value function.

However, if the target bootstraps (which is desirable for computational efficiency), a bias is introduced, since the target then depends on the current value of w. Such semi-gradient methods have fewer convergence guarantees and are vulnerable to the deadly triad. Alternatives have been studied, such as gradient-TD methods, that use true gradients with other loss functions [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]; however, they do not extend to non-linear control settings.

Deep Q-Networks

Mnih et al. ( 2013) created a breakthrough by achieving RL state-of-the-art performance on Atari games, a reference RL benchmark, with an agent learning only from raw pixels, without hand-crafted features or game-specific hyperparameter tuning. The proposed algorithm, DQN, is a variant of Q-learning with a number of improvements:

• to deal with partial observability, states are represented as a sequence of 4 game frames;

• the SGD minibatch is sampled uniformly from a memory D of the last N transitions, in a process known as experience replay [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF]. This technique avoids the correlations that would come from consecutive states (whereas supervised learning assumes independent samples) and therefore reduces variance; it improves sample efficiency, as each transition is used several times, which is especially important for rare ones; and it avoids risks of divergence or local minima by smoothing learning. Use of experience replay is made possible by the off-policy nature of Q-learning;

• in a subsequent article [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF], the concept of target network is introduced. Two weight vectors w, w -are maintained: at each step, w -is used for target evaluation while w is updated and used for action selection; a parameter update w -← w takes place periodically. This further reduces divergence and oscillations of the Q-values.

• finally, rewards are clipped to [-1, +1] so that their range is the same over all games.

The loss function for DQN summarizes these changes:

L Q (w) = E (s,a,r,s ′ )∼U (D) [(r + γmax a ′ Q(s ′ , a ′ ; w -) -Q(s, a; w)) 2 ] (2.19)
A CNN serves as function approximator: its input is the current sequence s, its output is the vector Q(s, •) of action-state values for all actions. This architecture is computationally efficient as it allows to determine the greedy action in one forward pass of the network.

Despite the empirical stability of the algorithm, there are no theoretical guarantees regarding its convergence. Its success nevertheless prompted a number of proposed improvements.

Improvements to DQN

A known limitation of Q-learning is that it suffers from positive maximization bias:

using the maximum over estimates of the Q-values as an estimate of the maximum Qvalue causes a positive ("optimistic") bias that can lead the Q-value to diverge, creating suboptimal policies. This phenomenon is experimentally demonstrated by van Hasselt et al. (2016) who propose Double DQN to counter it. This technique takes advantage of the presence of the two weight vectors w, w -to stabilize the target value: w is always used to determine the maximizing action and w -to give the value of the associated state-action pair. This reduces overestimation and facilitates convergence:

L Q (w) = E (s,a,r,s ′ )∼U (D) [(r + γQ(s ′ , argmax a ′ Q(s ′ , a ′ ; w); w -) -Q(s, a; w)) 2 ] (2.20)
Another issue with DQN is that it replays transitions at the same frequency that they are originally experienced although some transitions may provide more interesting information than others. [START_REF] Schaul | Prioritized Experience Replay[END_REF] propose prioritized experience replay where transitions with high expected learning progress are replayed more frequently. A level of priority p t is associated with each transition; it is proportional to the TD error δ t , which is a good proxy for how "surprising" a transition is. In order to avoid always replaying the same transitions and thus losing diversity, prioritization is made stochastic.

The probability of replaying the transition from step t is then defined as

P(t) = p η t k p η k
where η determines how much prioritization is used. As the replay distribution doesn't match the uniform distribution we are trying to evaluate, the algorithm risks getting stuck in local optima at the end of the optimization, so there is need for importance sampling:

ρ t = 1 N P(t) β(t)
where N is the replay memory size. ρ t δ t is then used instead of δ t in the DQN loss function. [START_REF] Wang | Dueling Network Architectures for Deep Reinforcement Learning[END_REF] present dueling Q-networks, a network architecture usable with any deep RL value-based algorithm. The specificity of the dueling architecture is to estimate both the state value V π (s) and the vector of advantage value A π (s, a) for all actions, which are then combined to output the estimates of action-state values Q π (s, a). The weights used to compute V and A are shared until the output layer.

Separating the representations of V and A has several benefits. By learning V , the network directly learns which states are valuable, and learning is accelerated since V (and thus Q) is updated at each transition; by contrast, previous architectures learn each Q(s, a) separately. Furthermore, A is sufficient for action selection, and may be irrelevant in situations where the action does not affect the outcome, while V is always important; the values of A also tend to be significantly smaller than the associated V , so separating them stabilizes optimization. If the value of Q was simply computed as Q = V + A, it might result in inaccuracies due to A with regard to the greedy action a * .

In order to always have Q(s, a * ) = V (s), the preferred upgrade is:

Q(s t , a t ) ← V (s t ) + A(s t , a t ) -max a A(s t , a)
(2.21)

However, replacing the max operator with averaging makes the value of Q(s, a) more stable and gives better experimental results.

Another trend of improvements over DQN consists in distributional methods, which essentially aim to learn the distribution of the random return (the value distribution) instead of the expectation of the return (the value). Learning the value distribution helps in a number of ways: it improves stability, especially in the presence of stochasticity, by using smoother target and loss function, and provides auxiliary predictions that ease learning through inductive bias. [START_REF] Bellemare | A Distributional Perspective on Reinforcement Learning[END_REF] proposed the first distributional method, where the value distribution is represented as a discrete distribution over a set of atoms whose probabilities are parameterized by Dirac distributions. Other methods in this direction seek to learn more expressive representations of this distribution, e.g. via quantile functions [START_REF] Dabney | Implicit Quantile Networks for Distributional Reinforcement Learning[END_REF][START_REF] Yang | Fully Parameterized Quantile Function for Distributional Reinforcement Learning[END_REF][START_REF] Nguyen-Tang | Distributional Reinforcement Learning with Maximum Mean Discrepancy[END_REF].

The original DQN deals with partial observability by stacking the N most recent observations. In some environments it may be necessary to give the agent more memory to understand more fragmented observations. [START_REF] Hausknecht | Deep Recurrent Q-Learning for Partially Observable MDPs[END_REF] propose replacing the frame-stacking technique of [START_REF] Mnih | Playing Atari with Deep Reinforcement Learning[END_REF] with a recurrent layer after the convolutional part of the neural network as a more general way to deal with partial observability. The recurrent layer is an LSTM [START_REF] Hochreiter | Long Short-Term Memory[END_REF].

Training the LSTM is done by storing sequences of transitions in the replay memory and initializing the recurrent state to zero before each sequence is used for learning.

The resulting algorithm, Deep Recurrent Q-Networks, increases DQN's resilience to partial observability.

Standard DQN is limited in applicability with regard to action space: since it outputs Q(s, a) for every action a, it cannot be used with continuous action spaces or too large discrete ones. In the continuous case, discretization could be an option, but when applied to N -dimensional actions, this creates a combinatorial explosion in the number of actions. The Q-value Q L of this modified MDP can be learned with standard DQN. However, the increase in the number of states makes training harder and more unstable. In order to mitigate this, the original Q-value Q U is also learned with TD(0), and a soft equality is enforced between Q U and Q L in the states of the modified MDP where no action has yet been chosen. The algorithm is robust for the choice of the number of bins for discretization and ordering of sub-actions. Generating sub-actions one dimension at a time also allows better exploration of the action space, especially when faced with multimodal distributions. Sequential DQN thus manages to outperform DDPG (cf.

section 2.3.3) on several continuous benchmarks.

Policy-based methods

As an alternative to value-based methods, policy-based methods directly learn a policy

π(a | s ; θ) (also noted π θ (a | s))

Policy-gradient methods

Policy-gradient methods attempt to optimize the policy by gradient ascent:

θ t+1 ← θ t + α∇ θt J(θ t ) (2.22)
where J(θ t ) can be defined in two equivalent manners, with a specific definition of the on-policy distribution µ θ in each case [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Silver | Deterministic policy gradient algorithms[END_REF]:

Option a Option b (continuing setting only)

J a (θ) = E s 0 ∼µ 0 [V π θ (s 0 )] = E s∼µ a θ , a∼π θ [R(s, a)] = ∞ t=0 E µ 0 ,π θ γ t R t+1 J b (θ) = E s∼µ b θ , a∼π θ [R(s, a)] = (1 -γ)E s∼µ b θ [V π θ (s)] = lim h→∞ 1 h h t=0 E µ 0 ,π θ [R t+1 ] expected discounted return average reward µ a θ (s) = ∞ t=0 γ t Pr(S t = s | π, µ 0 ) µ b θ (s) = lim t→∞ Pr(S t = s | π, µ 0 ) discounted state distribution stationary state distribution (2.23)
The issue is that the gradient of the performance depends both on the policy and the state distribution induced by the policy, and this state distribution is itself dependant on the usually unknown transition function. Fortunately, the policy gradient theorem [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] conveniently links the gradient of the performance to the gradient of the policy only:

∇ θ J(θ) = s µ θ (s) a Q B (s, a)∇ θ π(a | s; θ) = E s∼µ θ , a∼π θ Q B (s, a) ∇ θ π(a | s; θ) π(a | s; θ) (2.24) with Q B (s, a) = Q(s, a) -B(s)
where B(s) is an arbitrary baseline, used to reduce variance. B(s) may be a constant (like 0) but a better choice is to use the estimate of the state-value function V (s), in which case we obtain the advantage function. [START_REF] Degris | Off-Policy Actor-Critic[END_REF] extend this result to the off-policy setting, by proving that improvement to a local optimum of J(θ) is guaranteed by the following approximation, which differs only by the presence of an importance sampling ratio that compensates the use of a behavior policy b:

∇ θ J(θ) ≈ E st∼µ b , at∼b ρ t Q B (s t , a t ) ∇ θ π(a t | s t ; θ) π(a t | s t ; θ) (2.25)
The ratio

∇ θ π(a | s;θ) π(a | s;θ)
is called the likelihood ratio and is usually computed as ∇ θ ln π(a | s; θ). The right-hand side of eq. ( 2.24) can then be interpreted as the gradient of the following objective function:

L P G Q B (θ) = E s∼µ θ , a∼π θ [Q B (s, a) ln π(a | s; θ)] (2.26)
An entropy regularizer H π (s) =a π(a|s) ln π(a|s) is often added with a coefficient c to force the policy to stay stochastic and maintain exploration [START_REF] O'donoghue | Combining policy gradient and Q-learning[END_REF][START_REF] Francois-Lavet | An Introduction to Deep Reinforcement Learning[END_REF]:

L P G Q B (θ) = E s∼µ θ , a∼π θ [Q B (s, a) ln π(a | s; θ)] + c E s∼µ θ H π θ (s) (2.27)
From this theorem, a simple policy gradient algorithm, REINFORCE [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF]) can be derived that updates θ using episodic returns, in a Monte Carlo fashion;

that is, at the end of every episode, the update for each step t of the episode is:

θ ← θ + αγ t (G t -B(s t ))∇ θ ln π(a t | s t ; θ) (2.28)
REINFORCE is thus an on-policy approximate method with strong convergence properties. Estimates of the expected return obtained by Monte Carlo sampling are unbiased, but also display high variance and sample-inefficiency.

Actor-critic methods

Pure policy-gradient methods need to form an estimate of Q B at each time step, which is achieved in the algorithms presented so far by Monte Carlo sampling. A more sampleefficient approach is to learn a value function parameterized by a vector w, called a critic, in parallel. The critic is used to estimate Q B , at the cost of some bias, while the actor outputs the policy distribution. This is the concept of actor-critic algorithms [START_REF] Konda | Actor-Critic Algorithms[END_REF].

The first prominent actor-critic algorithm in deep RL was Advantage Actor-Critic (A2C) [START_REF] Mnih | Asynchronous Methods for Deep Reinforcement Learning[END_REF][START_REF] Wu | OpenAI Baselines: ACKTR & A2C[END_REF]. This algorithm also innovated in a number of other ways: its neural network architecture contained layers that were shared between the policy and value function; it used multiple actor-learners that ran in parallel on a multi-threaded CPU, generating their own experience and averaging their gradients to update common synchronized network parameters; and it used fixed-length segments of experience to compute estimators of the multi-step returns and advantage function.

A2C did not use a replay buffer, which came at a cost in sample-efficiency. Later actor-critic methods improved on this aspect by incorporating experience replay and importance sampling to enable off-policy learning, like ACER [START_REF] Wang | Sample Efficient Actor-Critic with Experience Replay[END_REF], or by using lower-variance estimators of the policy gradient and learning distributional Q-values, like Reactor [START_REF] Gruslys | The Reactor: A fast and sample-efficient Actor-Critic agent for Reinforcement Learning[END_REF].

Deterministic-policy gradient

Silver et al. ( 2014) adapt policy-gradient methods to the use of a deterministic target policy π(s; θ) in the presence of a continuous action space. This approach is motivated by the fact that the gradient of a stochastic policy integrates over both the state space and the action space, while the gradient of a deterministic policy integrates only over the state space, which means fewer samples to estimate it and more computational efficiency, especially with large action spaces. Furthermore, stochastic-policy gradients display high variance when the stochastic policy converges towards a deterministic policy; using a deterministic policy from the start prevents this and makes learning more stable.

An analog of the policy gradient theorem is provided for the deterministic-policy gradient (DPG):

∇ θ J(θ) ≈ E s∼µ b [∇ θ π(s; θ)∇ a Q π (s, a)| a=π(s;θ) ] (2.29)
where µ b is the state distribution under a policy b. This relation applies to on-policy and off-policy settings. In the on-policy case (b = π), the relation is an equality. The offpolicy case is of greater practical interest since b can then be a stochastic policy which encourages exploration; b is often defined by adding noise to the deterministic target policy so that b(s) ∼ N (π(s; θ), σ 2 ). The fact that the target policy is deterministic means no importance sampling is needed in eq. (2.29). The authors further prove that the deterministic policy gradient is the limiting case of stochastic policy gradient, when the variance of the stochastic policy tends to zero.

The above result can be applied to learn the actor of an actor-critic architecture where the critic provides an estimate of Q π (s, a). In particular, [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF] propose to use DQN's approach (cf. section 2.2.2) to learn the critic, as a way to apply DQN to continuous action spaces, yielding deep deterministic-policy gradient (DDPG).

Trust-region methods

One issue with policy-gradient methods is that they follow the steepest-ascent direction ∇ θ J(θ) in the parameter space. This entails the risk of destructive policy updates, since small changes in parameter space may result in radically different policies in practice.

One possible improvement to this problem is to try to follow the steepest ascent in the policy space. To do so, natural policy gradient [START_REF] Kakade | A natural policy gradient[END_REF][START_REF] Amari | Natural Gradient Works Efficiently in Learning[END_REF] follows the

corrected direction F -1 θ ∇ θ J(θ)
where F θ is the Fisher information matrix. Following the steepest ascent in policy space improves the optimization's stability while keeping vanilla policy gradient's convergence guarantees; the update in fact moves the policy in the direction of a greedy policy improvement. However, computing, inverting and storing the Fisher matrix is very expensive, which makes natural policy gradient unsuitable for large parameter vectors, such as those of deep neural networks.

Trust-Region Policy Optimization [START_REF] Schulman | Trust Region Policy Optimization[END_REF] makes this line of thought more practical by subjecting the gradient of the policy to a constraint on the KLdivergence between the old policy and the updated policy. While this method exhibits strong convergence guarantees and is applicable to neural networks, it requires the use of conjugate gradient descent and line search to enforce the KL constraint. Proximal Policy Optimization [START_REF] Schulman | Proximal Policy Optimization Algorithms[END_REF] improves on TRPO by dropping the KL divergence constraint and clipping the original objective function:

L CLIP (θ) = E s∼µθ, a∼πθ min ÂGAE θ (s, a) π(a|s; θ) π(a|s; θ) , ÂGAE θ (s, a) π(a|s; θ) π(a|s; θ) 1+ϵ 1-ϵ (2.30)
where [x] u l is the value of x clipped in the interval [l, u] and ϵ is a hyperparameter. The clipping of the policy ratio ensures that the next policy is not too different from the current one, which allows to drop the KL constraint. The min operator ensures that the monotonic improvement guarantees of TRPO are maintained. This new formulation is simpler and more generally applicable (e.g. it allows parameter sharing, unlike TRPO).

It is also more sample-efficient thanks to the use of Generalized Advantage Estimation [START_REF] Schulman | High-Dimensional Continuous Control Using Generalized Advantage Estimation[END_REF] which estimates A with low variance. It adapts a common estimator of A, based on n-step returns:

Â(n) (s t , a t ) = n-1 l=0 γ l r t+l + γ n V (s t+n ) -V (s t ) = n-1 l=0 γ l δ t+l (2.31)
where δ t = r t + γV (s t+1 ) -V (s t ) is the TD error. This estimator is unbiased if V is the true state-value function. When using an approximation of V , the bias decreases as n tends to infinity. This motivates the definition of the generalized advantage estimator as an exponentially weighted sum of estimators Â(n) t :

ÂGAE (s t , a t ) = (1 -λ) ∞ n=1 λ n-1 Â(n) t (s t , a t ) = ∞ l=0 (γλ) l δ t+l (2.32)
The value of λ ∈ [0, 1] determines a trade-off between variance (higher as λ increases)

and bias (higher as λ decreases).

Maximum-entropy methods

Policy-gradient algorithms often include an entropy regularizer that helps to keep the policy stochastic so as to maintain exploration. In this case, the objective can be defined as:

π * = argmax π t E s 0 ∼µ 0 ,a 0:t ∼π [R(s t , a t )] + c E s∼µπ H π (s) (2.33)
Another option is to maximize the entropy of the entire trajectory distribution under policy π. This is the objective of maximum entropy RL:

π * H = argmax π t E s 0 ∼µ 0 ,a 0:t ∼π [R(s t , a t ) + c H π (s t )] (2.34)
This can be interpreted as trying to learn not a deterministic optimal behavior, but a stochastic policy that encompasses all quasi-optimal behaviors. This approach can be justified by framing reinforcement learning as a probabilistic inference problem [START_REF] Levine | Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review[END_REF]. A discount parameter γ is usually added for variance reduction.

Maximum entropy methods have a number of benefits. They help exploration, especially in the case of multi-modal objectives (section 2.5.1). They are also robust to model and estimation errors and in adversarial settings. Finally, they are suited for multitask and transfer learning; for example, they can be used to pre-train general-purpose stochastic policies that can then be fine-tuned for specific tasks [START_REF] Haarnoja | Reinforcement Learning with Deep Energy-Based Policies[END_REF].

Besides earlier methods [START_REF] Haarnoja | Reinforcement Learning with Deep Energy-Based Policies[END_REF][START_REF] Nachum | Bridging the Gap Between Value and Policy Based Reinforcement Learning[END_REF][START_REF] Nachum | Trust-PCL: An Off-Policy Trust Region Method for Continuous Control[END_REF], the main maximum-entropy algorithm is Soft actor-critic [START_REF] Haarnoja | Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor[END_REF]. Similarly to policy iteration, SAC alternates between policy evaluation, which is here given by:

Q H (s t , a t ) = r t+1 + γE s t+1 ∼T (st,at) [V H (s t+1 )] V H (s t ) = E at∼π [Q H (s t , a t ) -ln π(a t |s t )]
(2.35) and policy improvement, given for all states s by:

π new = argmin π ′ D KL π ′ (•|s) || exp Q π old H (s, •) Z π old (s) (2.36)
where Z π old is a partition function that can be ignored in optimization. This process is approximated with SGD applied to three neural networks V ψ (not indispensable but improves stability), Q w , and f θ (ϵ t ; s t ) → a t (that induces the actual policy π θ ).

Interestingly, Schulman et al. (2017a) demonstrate that the gradient for a "soft" version of Q-learning is actually the same as the policy gradient for the maximum entropy objective; that is, their expectation is the same even though their variance can be different. In any case, the learning curves of these two algorithms are empirically similar given the right hyperparameters.

Planning and model-based methods

Being able to predict the dynamics of the environment opens a host of opportunities for the learning agent. The ability to predict the next state and reward are a given when a perfect model of the environment can be provided, for example in board games like chess; this case has been extensively studied in the contexts of planning and optimal control. However, in most RL applications, a model of the environment is not available beforehand and instead has to be learned by supervised learning before planning can take place.

The main promise of model-based approaches is to reduce sample complexity, by favoring model sampling over environment sampling, to the expense of increased computational requirements. Another advantage would be improved generalization, as planning methods can reason about previously unseen situations, unlike reactive model-free poli-cies. Planning could also potentially help to locally smooth out function approximation errors associated with value-and policy-based methods, which would result in better performance, provided the model's predictions are accurate enough.

Model learning

Model-based methods make use of a model M of the transition function T : S × A × S → [0, 1] (also called the dynamics of the models). In most cases this model is not initially available and has to be learned. Learning accurate models for complex environments can prove a significant challenge. It is vital, however, as planning over poor models will degrade performance compared to model-free methods, a problem known as model bias [START_REF] Deisenroth | PILCO: A model-based and data-efficient approach to policy search[END_REF]. To limit inaccuracy in predictions, modelbased methods either try to stay close to data, as in guided policy search [START_REF] Levine | End-to-End Training of Deep Visuomotor Policies[END_REF], or directly estimate epistemic uncertainty (i.e. the uncertainty on the model's accuracy, as opposed to aleatoric uncertainty, which is synonymous with stochasticity in the environment). Uncertainty can be evaluated with bootstrapped ensembles or Bayesian neural networks (Chua et al., 2018;[START_REF] Depeweg | Learning and Policy Search in Stochastic Dynamical Systems with Bayesian Neural Networks[END_REF], which both amount to learning separate models of the same environment: the degree of disagreement between models serves as a measure of model uncertainty.

Learning the dynamics of the environment fundamentally is a supervised learning problem. For continuous state spaces, the standard practice in model-based RL is to train the model to predict the change in state ∆s = s t+1 -s t rather than the next state s t+1 , similarly to the concept of residual nets [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]: this allows more accurate predictions in the case of small changes [START_REF] Deisenroth | PILCO: A model-based and data-efficient approach to policy search[END_REF]. In order to scale reasonably, neural networks are the most common approach, even though iteratively refitted linear models have also given excellent results [START_REF] Levine | End-to-End Training of Deep Visuomotor Policies[END_REF].

The most common and obvious issue in model learning is having to deal with a stochastic environment. A first approach is descriptive models, that capture the entire probability distribution of all transitions, for example with Gaussian processes (Deisenroth and Rasmussen, 2011) or probabilistic neural networks (Chua et al., 2018;[START_REF] Hafner | Learning Latent Dynamics for Planning from Pixels[END_REF]. A second approach is generative models, that simply produce samples of the next state (and reward), for example using Bayesian neural networks [START_REF] Depeweg | Learning and Policy Search in Stochastic Dynamical Systems with Bayesian Neural Networks[END_REF][START_REF] Gal | Improving PILCO with Bayesian neural network dynamics models[END_REF]. In this case, a common trick is to reparametrize the model as a function of some stochastic noise ξ: s t+1 = f (s t , a t ; ξ) (Heess et al., 2015).

In the case of a non-stationary environment, the standard approach is partial models:

the agent learns a different model for every environment mode and switches to the relevant model when the mode changes [START_REF] Nagabandi | Deep Online Learning via Meta-Learning: Continual Adaptation for Model-Based RL[END_REF]. This is actually a matter of multi-task learning and meta-learning.

When multi-step prediction is required, the most natural option is to chain one-step model predictions. However this tends to compound one-step errors. Alternatively, one can learn n-step predictions for all steps 1 ⩽ n < N to increase accuracy [START_REF] Hafner | Learning Latent Dynamics for Planning from Pixels[END_REF]. [START_REF] Mishra | Prediction and Control with Temporal Segment Models[END_REF] take the idea further and propose to learn temporal-segment models, which predict the distribution over future state trajectories.

As for partial observability, the same solutions as for model-free methods apply;

that is, the most common are RNNs (Ha and Schmidhuber, 2018) and frame stacking [START_REF] Depeweg | Learning and Policy Search in Stochastic Dynamical Systems with Bayesian Neural Networks[END_REF], although memory-based approaches have also been proposed [START_REF] Gemici | Generative Temporal Models with Memory[END_REF].

Finally, the difficulty of planning increases in high-dimensional state spaces; many papers attempt to perform dimensionality reduction in order to plan at the level of the environment's latent dynamics, especially by extending VAEs to the temporal setting [START_REF] Watter | Embed to control: A locally Linear Latent dynamics model for control from raw images[END_REF][START_REF] Krishnan | Deep Kalman Filters[END_REF][START_REF] Karl | Deep Variational Bayes Filters: Unsupervised Learning of State Space Models from Raw Data[END_REF].

Planning with a learned model

The problem of planning actions in an environment whose model is known has been studied extensively, for example with dynamic programming. Planning has been given many definitions. In its strictest sense, it refers to algorithms that solve decision-making problems without making use of learning. A simple approach to complex decision-making problems, then, is to learn a model of the environment and apply planning methods on it. Note that the model may be learned offline (before planning) or online (at the same time as planning). Discrete actions are suited for look-ahead search methods like MCTS [START_REF] Browne | A Survey of Monte Carlo Tree Search Methods[END_REF]. Continuous actions are tackled with trajectory optimization methods that range from direct optimal control, where trajectories are optimized with metaheuristics like random search or CEM (as in [START_REF] Nagabandi | Neural Network Dynamics for Model-Based Deep Reinforcement Learning with Model-Free Fine-Tuning[END_REF]Chua et al., 2018), to differential planning methods like iLQR, which approximates non-linear systems with linear dynamics and quadratic rewards [START_REF] Todorov | A generalized iterative LQG method for locally-optimal feedback control of constrained nonlinear stochastic systems[END_REF].

These methods can be used for open-loop planning, where a plan is determined at the beginning of an episode and then executed entirely. However, it is usually preferable to use closed-loop planning, where feedback is allowed after the plan has started being executed, especially when the planning is applied to a learned model of a complex, stochastic environment. Most approaches use model predictive control, meaning that planning is repeated at each step, and only the first step of each plan is executed.

Model-based RL

In a broader sense, planning refers to any process that takes a model as input and outputs (or improves) a policy [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Under this definition, planning may be integrated with model-free RL in what is known as model-based RL.

Given a policy, the most direct way of using a model is to generate fictional transitions or trajectories that can then be exploited as additional training data for model-free optimization. This is sometimes termed imagination: the model-free algorithm makes use of both real and imagined transitions for training. This approach was pioneered with Dyna-Q [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], which applied it to the classic Q-learning, with a tabular model. Recent approaches often use model ensembles to maintain model uncertainty [START_REF] Kurutach | Model-Ensemble Trust-Region Policy Optimization[END_REF][START_REF] Clavera | Model-Based Reinforcement Learning via Meta-Policy Optimization[END_REF]. Models can also be used to estimate n-step returns [START_REF] Feinberg | Model-Based Value Estimation for Efficient Model-Free Reinforcement Learning[END_REF][START_REF] Buckman | Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion[END_REF].

Model-free methods may also be used in combination with the pure planning algorithms. This can go two ways: we can plan with learned priors, for example by using value functions and policies learned with model-free RL as the inputs of a planning algorithm, or we can learn with planned targets, by using planning algorithms to determine targets that drive the updates of the policy or value function of a model-free algorithm.

Both approaches can be combined to form a procedure that alternates between planning and learning, where both provide information to improve the other (Silver et al., 2017a[START_REF] Silver | A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play[END_REF][START_REF] Levine | Guided Policy Search[END_REF]Levine and Abbeel, 2014;[START_REF] Levine | End-to-End Training of Deep Visuomotor Policies[END_REF].

Implicit planning

All methods presented so far in this section rest on two fundamental ideas:

• learning a model of the environment's dynamics, i.e. a module that predicts the next environment state (or next observation in the case of a POMDP), via super-vised learning;

• exploiting this model to obtain or improve a policy by applying a predefined planning algorithm: pure planning, imagination, value gradients, etc.

A number of recently proposed algorithms diverge from this process, by training their model differently or by learning how to plan on their model. These approaches are sometimes grouped as implicit planning.

Differentiable planning algorithms use a classic supervised model and focus on learning how to plan. Learning how to plan allows to adapt the planning algorithm to the problem at hand. This adaptable planning algorithm is implemented as a neural network, so that the planning module is differentiable and can be trained by backpropagation.

This approach can be considered a form of meta-learning. One approach in learning how to plan is to learn how to exploit imagination rollouts [START_REF] Pascanu | Learning model-based planning from scratch[END_REF][START_REF] Racanière | Imagination-augmented agents for deep reinforcement learning[END_REF]. However, imagination-based agents do not make use of the very efficient search schemes of classic planning methods like MCTS, and may be unlikely to rediscover them. This is why another line of approach is to use these planning methods, and attempt to learn subcomponents of it. For instance, [START_REF] Guez | Learning to Search with MCTSnets[END_REF] approximate MCTS with learnable operations for evaluation, selection, backup, and final decision.

Over the years, deep learning techniques have been developed that allow almost perfect pixel-level predictions for dynamics models [START_REF] Oh | Action-Conditional Video Prediction using Deep Networks in Atari Games[END_REF]. However, these prediction models often learn a lot of useless information about the environment state/observation (like background noise): this information is useless in the sense that it doesn't help to predict the value of the next states. A possible solution, then, is to train a value function with an embedded transition model to predict the value of future states. The value function is trained with a model-free algorithm, so that the embedded model is trained indirectly via backpropagation, not with supervised learning. This makes it an abstract model, since the states it predicts do not have to correspond to real environment states: only their values must match true state values. This is the origin of the term value-equivalent model. These ideas were pioneered in the Predictron [START_REF] Silver | The Predictron: End-To-End Learning and Planning[END_REF], which was used for value prediction in Markov reward processes. The exact output of the Predictron is a compound of imagined n-step returns, which is trained against real returns. The idea has since been applied to control problems (Oh et al., 2017;[START_REF] Farquhar | TreeQN and ATreeC: Differentiable Tree-Structured Models for Deep Reinforcement Learning[END_REF]Tamar et al., 2016) and proved its usefulness when applied to AlphaZero to obtain MuZero [START_REF] Schrittwieser | Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model[END_REF], that was able to match Al-phaZero's performance on board games without having access to a known environment model and to beat the state-of-the-art performance on Atari. Despite interesting results, it remains unclear whether value-equivalent models are able to learn the most complex environment dynamics accurately without supervised learning.

The most extreme form of implicit planning, proposed by [START_REF] Guez | An Investigation of Model-Free Planning[END_REF], does not rely on any form of model of the environment, and uses black-box recurrent networks of stacked ConvLSTMs (Shi et al., 2015) instead. Surprisingly, when this architecture is trained with the IMPALA actor-critic method, the resulting algorithm still exhibits typical planning-like characteristics (generalization in combinatorial spaces, sample-efficiency, improved performance form additional thinking time) and surpasses other implicit planning algorithms on a benchmark of planning tasks (Sokoban, Pacman...). Based on these results, the authors argue in favor of a behaviorist definition of planning.

Extensions

Exploration

As mentioned in section 2.1, RL agents must explore their environment during learning to try and discover greater sources of reward. However most classic algorithms rely on random exploration, either via an ϵ-greedy strategy like DQN, or by applying a stochastic policy with Gaussian noise and entropy regularization like most policy-based methods. Other random exploration methods include Boltzmann exploration (Cesa-Bianchi et al., 2017), which uses the exponential of the standard Q-function as the probability of an action (and is closely related to maximum entropy methods), and noisy networks [START_REF] Fortunato | Noisy Networks for Exploration[END_REF], which add parametric noise to the network weights.

These techniques hit their limits when applied to environments with sparse and delayed rewards, which instead require a form of directed exploration. This can take the form of temporally-extended exploration, for example via Thompson sampling (Osband et al., 2016) or self-imitation [START_REF] Ecoffet | Go-Explore: A New Approach for Hard-Exploration Problems[END_REF][START_REF] Ecoffet | First return then explore[END_REF][START_REF] Oh | Self-Imitation Learning[END_REF]. A lot of research also focuses on intrinsic motivation (Oudeyer andKaplan, 2007, 2009), that is, on mimicking curiosity and "exploration for the sake of exploration". This notably covers novelty search, which drives the agent towards underexplored states (Bellemare et al., 2016;[START_REF] Ostrovski | Count-based exploration with neural density models[END_REF][START_REF] Tang | #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning[END_REF], and prediction-based exploration, where the agent focuses on exploring transitions whose dynamics it struggles to predict [START_REF] Achiam | Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning[END_REF][START_REF] Pathak | Curiosity-driven exploration by self-supervised prediction[END_REF][START_REF] Burda | Large-Scale Study of Curiosity-Driven Learning[END_REF].

An alternative to advanced exploration methods is to guide the agent with human input. This can take the form of reward shaping [START_REF] Ng | Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping[END_REF], that is, crafting a reward function that doesn't only reflect the end behavior we want the agent to adapt, but also provides intermediate rewards that steer it in this direction. When the reward function is difficult to specify, one can resort to imitation learning, the problem of learning to perform a task from expert demonstrations. One approach is to recover an expert's cost function with inverse reinforcement learning [START_REF] Ng | Algorithms for Inverse Reinforcement Learning[END_REF][START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF]. A more direct way to use demonstrations is to perform behavioral cloning [START_REF] Hester | Deep Q-learning from Demonstrations[END_REF][START_REF] Ho | Generative adversarial imitation learning[END_REF] which learns a policy as a supervised learning problem over state-action pairs from expert trajectories. Behavioral cloning can especially used to initialize policies [START_REF] Silver | Mastering the game of Go with deep neural networks and tree search[END_REF].

Distributed and evolutionary methods

One major impediment to current RL methods is that their training time can be very long: for example, DQN and its variants are commonly trained for more than a week on the standard Atari benchmark. Distributed methods allow to scale up computational resources and speed up learning. Considerable work has also been done to make use of distributed computation in RL [START_REF] Babaeizadeh | Reinforcement Learning 123 through Asynchronous Advantage Actor-Critic on a GPU[END_REF][START_REF] Clemente | Efficient Parallel Methods for Deep Reinforcement Learning[END_REF][START_REF] Stooke | Accelerated Methods for Deep Reinforcement Learning[END_REF][START_REF] Horgan | Distributed Prioritized Experience Replay[END_REF]Barth-Maron et al., 2018;[START_REF] Espeholt | IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures[END_REF][START_REF] Kapturowski | Recurrent Experience Replay in Distributed Reinforcement Learning[END_REF]: research focuses on maximizing GPU occupation time for gradient computation, maximizing multi-threaded CPU usage for experience generation, and synchronizing actor and learner processes. This is especially the case for evolutionary methods, an interesting alternative to solve RL problems. The idea is to apply these techniques to optimize the policy parameters (e.g. neural network weights), using episodic return as the fitness function; this is known as direct policy search [START_REF] Salimans | Evolution Strategies as a Scalable Alternative to Reinforcement Learning[END_REF]. Several classic evolutionary methods have been applied to RL, such as the Cross-entropy method (CEM; de [START_REF] De Boer | A Tutorial on the Cross-Entropy Method[END_REF][START_REF] Szita | Learning Tetris using the noisy cross-entropy method[END_REF], CMA-ES [START_REF] Hansen | The CMA Evolution Strategy: A Tutorial[END_REF]Duan et al., 2016a), and genetic algorithms [START_REF] Such | Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning[END_REF]. Alternatives include neuro-evolution [START_REF] Stanley | A Hypercube-Based Encoding for Evolving Large-Scale Neural Networks[END_REF][START_REF] Kelly | Emergent Solutions to High-Dimensional Multitask Reinforcement Learning[END_REF] and combinations of gradient-based and evolutionary methods [START_REF] Khadka | Evolution-guided policy gradient in reinforcement learning[END_REF][START_REF] Pourchot | CEM-RL: Combining evolutionary and gradient-based methods for policy search[END_REF]. Of note is the ability of evolutionary methods to perform exploration naturally through population-based methods [START_REF] Lehman | Abandoning objectives: Evolution through the search for novelty alone[END_REF][START_REF] Such | Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning[END_REF].

Learning multiple tasks

In its basic setting, the role of an RL agent is to learn to perform a single task. This is unlike natural agents, who possess a repertoire of skills which they can put to use to accomplish a variety of tasks. These temporally-extended behaviors have also been described in terms of options [START_REF] Sutton | Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning[END_REF] and goals [START_REF] Sutton | Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction[END_REF][START_REF] Schaul | Universal value function approximators[END_REF]. Mastering several abilities has many advantages.

First, it allows hierarchization, i.e. the composition of low-level skills to perform a high-level task. Hierarchical RL is long studied approach [START_REF] Dayan | Feudal Reinforcement Learning[END_REF][START_REF] Parr | Reinforcement learning with hierarchies of machines[END_REF][START_REF] Dietterich | Hierarchical reinforcement learning with the MAXQ value function decomposition[END_REF]. The difficulty of building a hierarchical agent revolves around the coordination of its high-level and low-level controllers, and around autonomously learning the subgoals/skills required to solve the top-level task [START_REF] Vezhnevets | Feudal networks for hierarchical reinforcement learning[END_REF][START_REF] Bacon | The option-critic architecture[END_REF][START_REF] Nachum | Data-Efficient Hierarchical Reinforcement Learning[END_REF].

Second, learning different skills "for the sake of it" can enable generalization to similar skills, allowing the agent to rapidly adapt to the most relevant aspects of the actual task. This is the framework of unsupervised (or self-supervised) RL [START_REF] Jaderberg | Reinforcement Learning with Unsupervised Auxiliary Tasks[END_REF][START_REF] Shelhamer | Loss is its own Reward: Self-Supervision for Reinforcement Learning[END_REF]Andrychowicz et al., 2017), which places emphasis on autonomous option discovery [START_REF] Fox | Multi-Level Discovery of Deep Options[END_REF][START_REF] Achiam | Variational Option Discovery Algorithms[END_REF][START_REF] Eysenbach | Diversity is All You Need: Learning Skills without a Reward Function[END_REF].

Finally, when skills are learned in a sequence, with their complexity and difficulty increasing at each step, this forms a curriculum which may ease the agent's learning. The curriculum can consist in giving increasingly difficult goals to the agent, or exposing it to environments of increasing complexity. Of interest is the development of methods that perform automatic curriculum generation, for example via intrinsic motivation [START_REF] Colas | CURIOUS: Intrinsically Motivated Modular Multi-Goal Reinforcement Learning[END_REF][START_REF] Sukhbaatar | Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play[END_REF][START_REF] Florensa | Automatic Goal Generation for Reinforcement Learning Agents[END_REF][START_REF] Jabri | Unsupervised Curricula for Visual Meta-Reinforcement Learning[END_REF].

Unsupervised learning and curriculum learning both rely on a form of transfer learning. Transfer learning can also occur when the same agent is tasked with learning to solve several unrelated environments, for example when trying to play different Atari games with one agent [START_REF] Espeholt | IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures[END_REF]. This multi-task RL can be carried out by training simultaneously on all environments [START_REF] Kelly | Emergent Solutions to High-Dimensional Multitask Reinforcement Learning[END_REF][START_REF] Teh | Distral: Robust Multitask Reinforcement Learning[END_REF][START_REF] Hessel | Multitask Deep Reinforcement Learning with PopArt[END_REF], or learning to solve each environment sequentially [START_REF] Hausman | Learning an Embedding Space for Transferable Robot Skills[END_REF][START_REF] Kansky | Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics[END_REF]. Variants include online and lifelong learning. Both deal with a non-stationary task distribution over time: online learning focuses on fast adaptation, lifelong learning focuses on avoiding catastrophic forgetting [START_REF] Nagabandi | Deep Online Learning via Meta-Learning: Continual Adaptation for Model-Based RL[END_REF].

Meta-RL pushes the idea of transfer learning even further by attempting to train a model to be able to quickly learn a new task from a small amount of new data on a large number of different tasks. This meta-learning ability can involve automating the discovery of model's update rules or to train the model's initial parameters in order to maximize its few-shot performance on new tasks [START_REF] Duan | RL 2 : Fast Reinforcement Learning via Slow Reinforcement Learning[END_REF][START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF][START_REF] Oh | Discovering Reinforcement Learning Algorithms[END_REF].

Recently, there have been proposals to build upon pre-trained large language models to train agents that can display combinatorial generalization across different tasks [START_REF] Li | Pre-Trained Language Models for Interactive Decision-Making[END_REF][START_REF] Wang | Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents[END_REF].

Multi-objective RL

Most research in RL implicitly follows Sutton's reward hypothesis, which states that "all of what we mean by goals and purposes can be well thought of as maximization of the expected value of the cumulative sum of a received scalar reward" (Sutton). This can be understood as a statement on the best way for a user to communicate their intent to the agent. This in turn implies two things: firstly, that the most practical method for a human to express the desired behavior to the agent is to describe it in terms of a single scalar reward function; secondly, that a scalar reward always constitutes a sufficient signal based on which the agent can efficiently optimize its behavior.

Both of these implications can be questioned. The first one, in particular, will probably run counter to the experience of most RL practitioners, who discover early on that it is difficult to specify a reward function that matches the desired behavior: RL algorithms have a tendency to exploit their reward, that is, to maximize it in unintended ways. In many cases, it is more natural to describe a desirable behavior in terms of multiple objectives which may conflict with each other: in most RL applications, the reward ends up begin defined as a scalarization of multiple subrewards corresponding to different criteria. This scalarization, if interpreted as a utility function, must reflect the user's preferences over the criteria; yet in some cases these preferences may be unknown at training time, or they may vary depending on the situation. The second implication is contradicted by the fact that even when a task can be easily described by a scalar reward function, this reward might not prove simple to optimize either because it is sparse or delayed. This is why practitioners often resort to reward shaping, auxiliary skills learning, etc. On the other hand, if many criteria/subrewards are involved, subsuming them into a scalar signal may constitute an information bottleneck: the relationship between an action and the rewards it leads to is less obvious than if the agent received a signal that kept all subrewards intact. In other words, it can make credit assignment more difficult.

These limitations motivate the study of multi-objective RL (MORL) [START_REF] Roijers | A Survey of Multi-Objective Sequential Decision-Making[END_REF]. In MORL, we consider environments with vector-valued reward functions R :

S × A → R n .
Each component of this vector of rewards is associated to one of the agent's objectives. As a consequence, we can define the value function in vector form:

V π (s) = E π,T [ ∞ k=0 γ k R(S t+k , A t+k ) | S t = s] (2.37)
Since V π is a vector, in contrast to the single-objective case, there doesn't necessarily exist a unique optimal value, i.e. a value V that dominates all other values V ′ such that

V i (s) > V ′ i (s) ∀s, i.
This can be replaced with the notion of Pareto-optimal values, that is, values that are not dominated by any other. These form the Pareto front, which represents the set of potentially optimal solutions depending on the user's preferences.

The most common way to represent these preferences is in the form of a scalarization function, which gives a complete ordering over values. Given vector-valued rewards, there are actually three ways we can adapt the standard RL objective to the use of a scalarization. First we can scalarize the rewards directly:

max π∈Π E π,T [ ∞ t=0 γ t u(R(S t , A t ))]
(2.38)

This reduces to a scalar reward and is not considered part of MORL. MORL algorithms instead try to solve for either the scalarization of expected returns (SER):

max π∈Π u( E π,T [ ∞ t=0 γ t R(S t , A t )]) (2.39)
or the expected scalarization of returns (ESR):

max π∈Π E π,T [u( ∞ t=0 γ t R(S t , A t ))]
(2.40) SER scalarizes the expectation over multiple returns, and is therefore more adequate when the associated policy is executed many times; conversely, in ESR, returns do not accumulate across episodes, so that this formulation is a better fit when the policy is run once per user, for example in medical applications where the treatment of one patient corresponds to a single episode. In practice, the most commonly adopted criterion is SER.

Due to its simplicity, the most usual scalarization is the weighted average u(G) = i w i G i , where each objective is attributed a reward weight w i with i w i = 1. However, linear scalarization has limited expressive power as it cannot express preferences for Pareto-optimal solutions outside of the convex hull. As a consequence, non-linear scalarizations, such as the thresholded lexicographic order, have also been studied, but they present more challenges as they make the rewards non-additive [START_REF] Dornheim | gTLO: A Generalized and Non-linear Multi-Objective Deep Reinforcement Learning Approach[END_REF][START_REF] Vamplew | A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions[END_REF]. Note that when using linear scalarization, the three formulations outlined above are all equivalent. However, in the multi-objective setting, the network can approximate the vector-valued action-state function

Q π (s, a, w) = E πw,T [ ∞ k=0 γ k R(S t+k , A t+k ) | S t = s, A t = a]
(2.41)

Scalarizing this Q-value vector instead of directly outputting a scalar value typically yields more accurate estimations of the global Q-value [START_REF] Tajmajer | Modular Multi-Objective Deep Reinforcement Learning with Decision Values[END_REF]. Also, treating the problem as multi-objective is useful when the value of the reward weights at execution is not known in advance. The classic approach in this case is to learn a convex coverage set, which is a subset of undominated policies containing at least one optimal policy for any reward weight vector: the idea of such algorithms is to separately learn the optimal policies of a number of corner weights [START_REF] Mossalam | Multi-Objective Deep Reinforcement Learning[END_REF][START_REF] Nguyen | A Multi-Objective Deep Reinforcement Learning Framework[END_REF].

This approach, however, is impractical in the dynamic weights setting, where the reward weights can change between episodes. In order to generalize over different reward weights, the agent's network can be conditioned on the current weights so it can learn and execute policies corresponding to different overall objectives. This results in an adapted DQN loss function to minimize:

E (s,a,r,s ′ )∼U (D) [(r + γ max a ′ Q θ -(s ′ , a ′ , w) -Q θ (s, a, w)) 2 ] (2.42)
Several extensions of DQN have been proposed using this type of conditioning, dealing in particular with how the reward weights in the above loss function should be chosen. [START_REF] Abels | Dynamic Weights in Multi-Objective Deep Reinforcement Learning[END_REF] modify the loss function and experience replay to avoid forgetting the policies for weight vectors that haven't been experienced recently. [START_REF] Yang | A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation[END_REF] propose a new loss function that lets the agent use information gathered with other policies to update the policy for the current reward weight vector. [START_REF] Wang | Near On-Policy Experience Sampling in Multi-Objective Reinforcement Learning[END_REF] propose near on-policy experience replay, which reduces the extrapolation error caused by data distribution mismatch.

Conclusion

In this chapter, we gave a tour of reinforcement learning. After presenting the field's terminology, we went through a typology of existing algorithms, from value-based and policy-based methods to model-based methods, which each present their own trade-offs.

We concluded on extensions to the domain's core framework, notably multi-task and multi-objective reinforcement learning, which hold the promise of extending the applicability of reinforcement learning by tackling more complex settings that are relevant to real-world applications. Given this state of the art, in the next chapter we set out to apply these techniques to radar resource management.

Chapter 3

Applications of reinforcement learning to multi-function radars

In this chapter, we propose applications of reinforcement learning techniques to current multi-function radar resource management architectures. We focus on two components: task scheduling and active tracking dwell optimization. We tackle scheduling with modelbased methods and active tracking with model-free ones. Improvements over existing resource management methods are highlighted.

Multi-function radar scheduling

Multi-function radars require efficient resource management strategies to fulfill their missions. In particular, task scheduling is crucial to mitigate difficult situations such as when all tasks cannot be accomplished. However, current approaches may prove insufficient in the face of emerging threats. Reinforcement learning could provide a more performant alternative to devise future radar schedulers. In the present chapter, we follow this line of thinking by making several proposals. After an overview of existing methods, we start by giving the scheduling problem a formulation that allows building schedules in a flexible way, which facilitates the discovery of high-value solutions. This opens the way for different resolution methods that we then present: first, a new heuristic that outclasses existing ones while keeping computational cost low; then, an adaptation of Monte Carlo Tree Search that is applicable to this new formulation. We show that our algorithms provide noticeable performance improvement over similar methods proposed previously.

Literature review

Given that a radar runs under constraints of time, power, and processing, the radar's resources must be allocated between its different functions according to the radar's mission, which determines the priority level of each function [START_REF] Moo | Adaptive Radar Resource Management[END_REF][START_REF] Charlish | Array Radar Resource Management[END_REF]). Among these resources, time budget is the most critical, as the time spent performing a given task closely reflects its importance. Each function consists of one or more tasks, that can be fixed, like search tasks, or assigned dynamically, for example tracking a specific target; each task is carried out by performing a number of dwells. Based on the current situation, the radar continuously generates dwell requests corresponding to its different functions. Dwell requests are characterized by requirements in desired execution time, duration, and power, and are assigned priority levels. The resulting list of requests is transmitted to a scheduler, whose role is to decide which dwells should be executed and at what time. Efficient scheduling is crucial in overload situations, which happen when temporal constraints prevent from executing all dwells, forcing the scheduler to drop some of them according to their level of priority.

Prioritization therefore plays a key role in radar schedulers.

As mentioned in chapter 1, radar schedulers fall into two categories. Best-first schedulers execute requests from a heuristically-ordered queue. Common heuristics include earliest start time first (EST), earliest deadline first (EDF), and highest priority first (HPF). It is also usual to combine these simple heuristics into more complex rules [START_REF] Butler | Resource Management For A Rotating Multifunction Radar[END_REF]. The alternative is frame-based schedulers, which pack tasks into fixedduration frames. The advantage of this approach is that by considering a frozen list of tasks to schedule, it allows the problem to be well-defined mathematically, which opens the possibility of optimization methods. However, exact resolution is computationally too expensive for the required time frames, so that in practice heuristics are preferred [START_REF] Orman | Scheduling for a multifunction phased array radar system[END_REF][START_REF] Winter | On scheduling a multifunction radar[END_REF][START_REF] Jeauneau | Scheduling on a fixed multifunction radar antenna with hard time constraint[END_REF]). Yet another advantage of frame-based schedulers over best-first ones is to permit greater control over the task parameters: for example, the task duration can be modeled as a variable, which allows for more flexibility and enhanced utilization of the radar timeline [START_REF] Mir | Variable Dwell Time Task Scheduling for Multifunction Radar[END_REF]. It also enables task interleaving, where during a task's idle time be-tween emission and reception another task may be scheduled, also increasing antenna utilization [START_REF] Orman | Scheduling for a multifunction phased array radar system[END_REF]. Frame-based scheduling has also been approached with tabu-search methods [START_REF] Abdelaziz | An Optimization Model and Tabu Search Heuristic for Scheduling of Tasks on a Radar Sensor[END_REF] and genetic algorithms [START_REF] Zhang | A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar[END_REF].

Despite the appeal of heuristics in terms of low computational load, their performance is usually far below the optimal solution. This has prompted an interest in artificial intelligence techniques that could improve scheduling performance while conforming to real-time computational constraints. Among the first attempts of this kind was Izquierdo-Fuente and Casar-Corredera (1994)'s use of Hopfield networks to learn an interleaving scheduler. More recently, Shaghaghi and Adve (2018) studied the application of deep learning to task scheduling on multi-channel radars, i.e. radars that use different frequencies to execute multiple tasks simultaneously. This kind of radar handles multiple timelines, which improves antenna utilization but makes scheduling harder.

The authors ran a branch-and-bound algorithm on instances of the problem to create a dataset which they used to train a neural network that estimates the value of the nodes of the search tree. These evaluations are then used to prune the search tree by eliminating the least promising nodes, which speeds up the search process. The proportion of pruned nodes is determined by a scaling factor, which controls how robust the algorithm is to estimation errors. The resulting combination of deep neural network and branch-andbound method produces near-optimal solutions with significantly reduced computation, even if it remains too slow for real-time radar scheduling and requires a fixed number of tasks.

To reduce computation, Shaghaghi et al. (2018) address the problem with Monte Carlo Tree Search (MCTS). Along with branch-and-bound bound and dominance rules, they use a neural network to guide MCTS's exploration policy. The network is trained on a dataset similarly obtained from branch-and-bound solutions. This further cuts down time complexity compared to branch-and-bound methods while maintaining high-quality solutions. Their algorithm is applicable to an arbitrary number of active input tasks.

To remove the need for a training dataset generated offline, [START_REF] Shaghaghi | Resource Management for Multifunction Multichannel Cognitive Radars[END_REF] use a similar solution but train the policy network with data produced by the radar's interactions with its environment. The tree search is modified to accommodate several constraints, such as non-homogeneous channels, blocked channels, and periodic tasks.

Similarly, [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] propose a modified MCTS for single-channel radar task scheduling to lower the computational complexity. The modified MCTS notably does not revisit states where all solutions branching from it have already been visited.

The exploration of the search tree is guided by an earliest start time first heuristic.

The authors also propose an RL variant of their algorithm using a scheme similar to AlphaZero (Silver et al., 2017a), whereby a value network and a policy network are trained based on MCTS rollouts and used to guide the exploration.

Framework

We formalize the problem of radar task scheduling similarly to [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]. As we mentioned above, our model of an MFR scheduler processes one fixed set of tasks1 at a time. An updated set of tasks is received at regular intervals. In the meantime, no tasks may be added to the set that is being processed. Each task in a set I = {1, ..., n} is characterized by its temporal constraints and its priority level. The temporal constraints of a task i are defined by its length L i , its start time T i s and drop time T i dr (respectively the earliest and latest date at which it can start executing), and its due time T i du , which is the desired execution time. In this work, for any given instance, these constraints are all held constant over the course of the scheduling process: we do not consider preemptive tasks (e.g. for dwell interleaving) or variable duration time. Our goal is to determine for each task i in I whether to schedule it (x i = 1, else 0), and if so at what execution time t i , or to drop it (y i = 1, else 0). Scheduled tasks must be entirely contained in a temporal frame [0, T max ]. In order to arbitrate between tasks in case of conflicts, each task is ascribed a drop cost C i dr and a delay cost C i de which reflect its priority level.

The drop cost is incurred only when the corresponding task is dropped while the delay cost determines how much the difference between the actual and ideal execution times is penalized; this difference is an absolute value, unlike in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] where due times were not distinct from start times. How to assign relevant values to these costs in an operational context is left to future work. We write instances of the problem as P = {(L i , T i s , T i dr , T i du , C i dr , C i de ) ∀i ∈ I ; T max }, and its (partial) solutions, or schedules, as s = {(x i , y i , t i ) ∀i ∈ I}. The objective is to minimize the sum of costs (or total cost) C P (s). We summarize the problem below, where ⊕ represents an exclusive or:

min C P (s) = i∈I x i t i -T i du C i de + y i C i dr s.t.                      T i s ⩽ t i ⩽ T i dr ∀i ∈ I t i + L i ⩽ T max ∀i ∈ I t i + L i ⩽ t j ⊕ t j + L j ⩽ t i if x i = x j = 1, ∀(i < j) ∈ I 2 t i ∈ R + ∀i ∈ I x i , y i ∈ {0, 1} with x i = 1 -y i , ∀i ∈ I (3.1)
This problem can be solved to optimality with mixed-integer programming (MIP). Unfortunately, since problem (3.1) is in NP 1 , the computation time for MIP grows exponentially with the number of tasks, making it prohibitive for radar applications. The exclusive-or constraint has an interesting implementation in MIP:

               t i + L i ⩽ t j + M (n ij + o ij ) t j + L j ⩽ t i + M (n ij + 1 -o ij )    ∀(i < j) ∈ I 2 n ij ⩽ 2 -x i -x j ∀(i < j) ∈ I 2 n ij , o ij ∈ {0, 1} ∀(i < j) ∈ I 2 (3.2)
In order to give further insight into the structure of the problem, we offer its detailed formulation for MIP with pre-processing:

1 This can be proven via a polynomial reduction with the knapsack problem by setting T i s = C i de = 0 and T i dr = Tmax for all i in I.

min C P (s) = i∈I l i de C i de + (1 -x i )C i dr s.t.                                                                        T i s ⩽ t i ⩽ T i dr t i + L i ⩽ T max l i de ⩾ t i -T i du l i de ⩾ T i du -t i                ∀i ∈ I t i + L i ⩽ t j + M (n ij + o ij ) t j + L j ⩽ t i + M (n ij + 1 -o ij )    ∀(i < j) ∈ V t i + L i ⩽ t j + M n ij ∀(i, j) ∈ U x i + x j ⩽ 1 ∀(i < j) ∈ X n ij = 2 -x i -x j ∀(i < j) ∈ U ∪ V t i , l i de ∈ R + ∀i ∈ I n ij ∈ R + ∀(i < j) ∈ U ∪ V x i ∈ {0, 1} ∀i ∈ I o ij ∈ {0, 1} ∀(i < j) ∈ V (3.3)
We use the following notations:

• n ij : boolean, true if tasks i and j are not both scheduled;

• o ij : boolean, true if task j is executed before task i, false if it is the opposite;

• M : an arbitrarily large number such that M ≫ T max ;

• i → j ≡ T i s + L i ⩽ T j dr ∧ T i s + L i + L j ⩽ T max ; i can precede j iff i and j can both be scheduled with i executing before j;

• (i, j) ∈ X ≡ i ↛ j ∧ j ↛ i ; i and j are incompatible (have incompatible interference) iff it is impossible to schedule both;

• (i, j) ∈ V ≡ i → j ∧ j → i ; i and j are invertible (have bilateral compatible interference) iff they can be scheduled in both orders;

• (i, j) ∈ U ≡ i → j ∧ j ↛ i ∧ T j
s < T i dr + L i ; i and j have unilateral compatible interference iff they can be scheduled in only one order and could overlap.

Of interest in formulation (3.3) is the presence of binary variables o ij in addition to

x i (on the other hand, n ij is an intermediary variable entirely determined by x i and x j ). The values of o ij determine the order in which the scheduled tasks are placed. This highlights the fact that problem (3.1) can be subdivided in three successive sub-problems: 1. inclusion: determine which tasks to schedule; 2. ordering: determine the order in which these tasks should be scheduled; 3. time setting: determine the execution times of these ordered scheduled tasks.

Note that problem (3.1) can also be solved with heuristics like earliest start time first (EST) or earliest deadline first (EDF). These heuristics (and variations thereof) are common in radar resource management because they are fast and easy to implement. However they will often produce poor solutions, for two reasons: first, because they operate on the premise that the schedule must be built by adding tasks in chronological order; second, because they do not account for task priority.

By contrast, we aim to develop approximate algorithms for radar task scheduling that can approach optimal solutions while keeping reasonable computation times. Our first step is to model problem (3.1) as a Markov decision process (MDP), characterized by its state space S, action space A, transition function T and reward function R. Once we have defined a suitable MDP, we will need an algorithm that outputs a strategy for this MDP, which we call the decision algorithm. Following [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], we define a state as a partial schedule, where a number of tasks have been scheduled at certain execution times and a number of others dropped while respecting the constraints of (3.1). The only initial state s 0 for a given instance of the problem is the associated empty schedule, where no tasks are scheduled or dropped. We also define an action as the choice of one task to schedule in the set of available tasks A = {i ∈ I | x i = y i = 0}.

Terminal states are states where no actions are available, that is, complete schedules, where all tasks are scheduled or dropped. We can define the reward as the cost difference between the two states involved in a transition, i.e. R(s, a, s ′ ) = C P (s) -C P (s ′ ). With γ = 1, the value function becomes V π (s 0 ) = E π [C P (s 0 ) -C P (s T )], which corresponds to our initial objective of finding a schedule s that minimizes C P (s). In practice, in our algorithms, we reason directly on costs.

The choice of the transition function is the most crucial aspect of this formalization.

Transitions must deterministically decide what execution times to set and which tasks to drop when a new task is added to a partial schedule.

The simplest option, used in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], is to add tasks chronologically: any newly added task i is assigned an execution time greater than that of all previously scheduled tasks, and tasks that cannot be placed after i are dropped. However, this restricts the range of viable strategies, since the decision algorithm has to solve both the inclusion and the ordering sub-problems at the same time, while the transition function only deals with the time setting sub-problem. Instead, we propose a transition model that allows building schedules in a more flexible way. Our idea is to model the transition function such that it solves both the ordering and the time setting sub-problems at each step. That is, given a set S of scheduled tasks, the transition determines the order of tasks and their execution times by minimizing the total delay cost:

min i∈S l i de C i de s.t.                                                T i s ⩽ t i ⩽ T i dr t i + L i ⩽ T max l i de ⩾ t i -T i du l i de ⩾ T i du -t i                ∀i ∈ S t i + L i ⩽ t j + M o ij t j + L j ⩽ t i + M (1 -o ij )    ∀(i < j) ∈ V ∩ S 2 t i + L i ⩽ t j ∀(i, j) ∈ U ∩ t i , l i de ∈ R + ∀i ∈ S o ij ∈ {0, 1} ∀(i < j) ∈ V ∩ S 2 (3.4)
Given a partial schedule s = {(x i , y i , t i ) ∀i ∈ I}, in order to schedule a new task j ∈ I, we solve sub-problem (3.4) for S = {i ∈ I | x i = 1} ∪ {j}. If there is no solution to the sub-problem, j has to be dropped. After a task is scheduled, all remaining tasks in A can be tested for dropping using this procedure.

Sub-problem (3.4) can also be treated with a MIP solver; however this requires finding the order and execution times of all tasks in S at every transition. This is inefficient, because with this transition model, when we move from a partial schedule s to a new one s ′ by adding a task i, the execution times in s are already optimal with regard to the tasks scheduled in s. This means that if for example i can be placed at its desired execution time without interfering with already scheduled tasks, then there is no need to recompute the execution times of these tasks. To exploit this and a number of other optimizations, we implement a custom solver for sub-problem (3.4) which we do not detail here due to space limitations: the key idea is to recursively generate and evaluate permutations of the scheduled tasks while limiting the number of generated permutations by exploiting temporal constraints. Note that this way, we can check the availability of a task faster, by interrupting the recursion as soon as we find a feasible permutation.

Our transition model allows adding tasks in any order by delegating part of the optimization-ordering and time setting-to the environment. Crucially, for any schedule s reached through this transition model, the execution times are optimal given the tasks scheduled in s. (We can also limit the number of generated permutations to lower the computation time, although we then lose the optimality guarantee.) This opens new possibilities for the choice of the decision algorithm, whose role is to solve the hardest part of the problem: inclusion.

Task selection methods

HCLR

The first decision algorithm we propose is a heuristic that we call highest cost-length ratio first (HCLR), which is similar to some knapsack problem heuristics. It consists in sorting tasks by their ratio between drop cost and length, then scheduling them in decreasing order (if they are still available when their turn comes). Equivalently, at each step, we choose the following action:

a = argmax a∈A C i dr L i
This heuristic empirically performs better than scheduling the task with the highest drop cost first, because it accounts for situations where for example two shorter, lower-priority tasks have a higher total drop cost than one longer, higher-priority task which they are incompatible with. A similar criterion has been proposed for radar resource management by [START_REF] Qu | A Machine Learning Task Selection Method for Radar Resource Management (Poster)[END_REF]; however, the authors used the ratio in a task selection phase that preceded the scheduling itself, which is based on EST. Using our transition model, we can instead directly select and schedule each task in turn.

MCTS

Our next decision algorithm is a version of Monte Carlo Tree Search (MCTS) adapted to task scheduling, which is based in large part on the version of [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]. MCTS uses a search tree where nodes represent MDP states and branches correspond to actions taken in the parent node [START_REF] Browne | A Survey of Monte Carlo Tree Search Methods[END_REF]. The tree is constructed by successive rollouts: starting from the root node, which corresponds to the initial state, we select an action, apply the transition function to get the next node (which is created if needed), and repeat. Once a terminal state is reached, we can compute its total cost C, then backpropagate C up the path we just followed to update the best cost reached from each state-action pair: C(s, a) ← min{C(s, a), C}. This value is then used in the computation of the upper-confidence bound U (s, a) which determines which actions are chosen in the selection phase: a = argmax a ′ U (s, a ′ ) with U (s, a) = P (s,a)

C(s,a) τ (1+N (s,a)) where τ is a temperature, N (s, a) is the number of rollouts where action a was taken in state s, and P (s, a) is a prior probability function over actions. This selection rule is designed to balance exploration of the search tree and exploitation around the best solutions found so far. The prior, especially, plays a prominent role in steering exploration; a simple way to parameterize it is to sort the m available tasks according to a criterion, then assign them a respective prior probability of p(1 -p) m for m ranging from 0 (for the first task) to m -1. For our experiments, we set τ = 2 and p = 0.6, similarly to [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]), but we diverge by using HCLR as our sorting criterion instead of EST. One issue is that when using our transition model, since tasks can be scheduled in any order, it is possible to reach the same terminal state via multiple different rollouts.

In order to prevent this, we structure our search tree similarly to a branch-and-bound (B&B) tree : when a new action is taken in node s, leading to a new node s ′ , all actions explored in s in previous rollouts are made unavailable in s ′ and its descendants. This makes sure there is only one path to each terminal state in the search tree. However, it also means that we may reach terminal nodes that are not complete schedules, when some tasks can still be scheduled, but have all been made unavailable by the previous rule. To limit the number of such situations, at each visit of a node s, we check if there exists a terminal node s ′ descended from s such that all tasks that are unexplored in s are scheduled in s ′ ; if so, these tasks are made unavailable in s. Additionally, to avoid performing the same rollout twice, if a node has no more available actions, the action that led to it is also made unavailable in the parent node, as in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF].

We call this algorithm B&B-MCTS. Usually, in MCTS, when we reach a new state, we want to know which actions are available. With B&B-MCTS, this allows making the most effective use of pruning, according to the above rules. However, with our transition model, it requires partially solving (3.4) for each a priori available task to check if it has to be dropped. In larger instances, this involves significant computation, which reduces the number of rollouts that can be carried out in a given time. We propose two variants of B&B-MCTS: a "safe" one that checks for unavailable tasks to drop when a new node is created, and a "rash" one that attempts to schedule tasks without prior verification, and drops them

Results

To enable comparisons, we run experiments on instances from the same distribution as in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]:

L i ∼ U (2, 15), T i s ∼ U (0, T max -12), T i du = 0, T i dr -T i s ∼ U (2, 12), C i
dr ∼ U (100, 500), C i de ∼ U (1, 15), T max = 100. The difficulty of an instance mostly depends on the density of tasks; by keeping T max fixed, the difficulty can be controlled by setting the number of tasks.

We compare our two methods, HCLR and B&B-MCTS, with the EST heuristic and with the version of MCTS proposed in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]) (which we term EST-MCTS).

The run time of both versions of MCTS is limited to 1 second. All these algorithms are implemented in Python. We compute the optimal solution using MIP on instances where this resolution can be performed in a reasonable amount of time. These five algorithms are run on the same instances, 1000 per number of tasks. We also compare our results to those reported by [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] for a reinforcement learning-based extension of EST-MCTS inspired by AlphaZero (Silver et al., 2017a).

Our results show that our approach provides a significant performance improvement over EST-MCTS, and even surpasses the reinforcement learning algorithm of [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], which used deep learning in conjunction with MCTS. Strikingly, the per- Unlike in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], our approach allows due times distinct from start times, thus reflecting radar requirements more closely. We also run experiments on a similar task distribution but with T i du ∼ U (1, 4) and T i dr -T i s ∼ U (1, 8); our results match those of the first distribution very closely.

Reinforcement learning for active tracking

Electronically-scanned array antennas give multi-function radars more degrees of freedom over the parameters of the dwells they can form. In particular, digital beamforming offers more possibilities to vary the direction and shape of the beam, conferring to the radar a form of beam agility. Dynamic beamwidth adaptation, especially, could help to track more challenging targets, for example when hypermaneuverability and hypervelocity are involved: increasing the beamwidth during maneuvers, for example, would increase the robustness of the track by making the target less likely to go out of beam and avoid detection. However, the ability to vary beamwidth from one dwell to another has so far been underutilized. The reason is that the most common active tracking parameter selection methods assume a fixed beamwidth in order to determine the required update rate of the track. Therefore, if we want to perform dynamic beamwidth adaptation, we also need to make decisions for the update rate. The beamwidth used also has an impact on the dwell's signal-to-noise ratio (SNR), which larger beamwidths decrease, lowering the detection probability and measurement accuracy. To compensate for lower SNR, the duration of the dwell should be increased. More adaptive active tracking resource management methods should therefore control these three parameters of beamwidth, update rate and waveform duration concurrently to optimize track maintenance.

In this chapter we approach this problem through a reinforcement learning lens.

After examining existing methods for active tracking parameter selection, we describe the simulator we implemented to train and test our agents. We first apply our method to single-target tracking, where we do not take into account the radar's global state. We then study a more holistic approach to radar resource management, where we attempt to manage both search and multi-target tracking: in this setting, we uncover limitations of standard reinforcement learning methods, which motivates the development of new algorithms in the next chapter.

Existing methods

Track update rate is a crucial part of target tracking. The track update rate can equivalently be expressed as the revisit interval, which is the duration between update attempts.

The problem of setting track update rates is also known in the literature as beam scheduling, not to be confused with task scheduling which is the placement of the dwell requests on the antenna timeline by the scheduler as studied in section 3.1. Longer revisit intervals mean lower antenna time utilization, but are only suitable for non-maneuvering targets with predictable trajectories. Maneuvering targets, on the other hand, require shorter revisit intervals as predictions on their movement must be updated often. Most algorithms select the update rate based on either the innovation sequence of the tracking filter [START_REF] Baek | An adaptive update-rate control of a phased array radar for efficient usage of tracking tasks[END_REF] or on the predicted error covariance matrix (van Keuk and [START_REF] Van Keuk | On phased-array radar tracking and parameter control[END_REF][START_REF] Daeipour | Adaptive beam pointing control of a phased array radar using an IMM estimator[END_REF].

These methods are computationally efficient and can be deployed in current radars.

However, they are model-sensitive: they especially depend on target models which can be unknown or simplified compared to real target dynamics. Additionally, they determine the update rate on a per-track basis. In practice MFRs may have to track hundreds of targets in parallel: if the radar is overloaded, the prioritization and scheduling modules must arbitrate for which tracks the update must be delayed. Yet this limits the adaptability of track updates and results in a lack of coordination between the different tracks.

The alternative is to consider performing multi-target resource allocation. This problem has in particular been studied as a type of restless bandit problem. Restless bandits are an extension of k-armed bandits where each action is associated to a process that evolves over time. Processes have a default (or passive) transition function, which differs from the active transition that takes place when the process is selected. Unlike in previous methods, the idea isn't to set the revisit interval of each target after its update; instead, this revisit interval emerges from the choice of updating or not a target at each step. Resolution methods for bandit formulations of multi-target tracking use variants of dynamic programming. [START_REF] Krishnamurthy | Hidden Markov model multiarm bandits: A methodology for beam scheduling in multitarget tracking[END_REF] develop optimal and sub-optimal algorithms for optimal beam scheduling in electronically scanned array tracking systems, where the problem is formulated as a multi-arm bandit problem with hidden Markov models. La Scala and Moran ( 2006) study adaptive beam scheduling and propose an algorithm to minimize target tracking error with phased array radars.

The bandit formulation can also be adapted to cover the update of both search and tracking tasks, as proposed in [START_REF] Wintenby | Resource Allocation in Airborne Surveillance Radar[END_REF]. This setting removes the requirement for prioritization and scheduling modules distinct from the dwell generation phase.

Bandit formulations for multi-target resource management is a promising approach as it could allow joint optimization over all radar tasks, foregoing coordination issues with common beam scheduling methods. However, current resolution methods for these formulations use dynamic programming, which is accompanied by high computational complexity owing to the curse of dimensionality, making it impractical to implement in real radar systems. They also require to make a number of theoretical assumptions that do not take into account some of the physical constraints exerted on radar systems.

Given the limitations of current active tracking methods, reinforcement learning provides an appealing alternative. If applied to single-target tracking, it holds the promise of increased adaptability in terms of environment models, target models, and simultaneous optimization of more dwells parameters than previously possible, especially regarding to beamwidth. If applied to multi-target tracking, deep reinforcement learning would allow global resource management optimization while lifting the hurdles posed by dynamic programming methods proposed previously. [START_REF] Pulkkinen | Time Budget Management in Multifunction Radars Using Reinforcement Learning[END_REF] pioneered the application of reinforcement learning to adaptive update rate selection for single-target tracking. Specifically, a tabular Q-learning algorithm with epsilon-greedy exploration is used to adaptively select the revisit interval of the track after each update, and the reward to maximise is defined as the negative ratio between the update's observation time and previous revisit interval. If the target is lost, a negative track loss cost is given as reward instead and the episode ends. Different state spaces are tested: they include either the mode probabilities of the IMM or the innovation, i.e. the change in the filter's angular accuracy after the update; either state can be augmented with the revisit interval selected at the previous step. The performance of the proposed approach is favorably benchmarked against the prediction error covariance matrix-based solution from [START_REF] Daeipour | Adaptive beam pointing control of a phased array radar using an IMM estimator[END_REF] in terms of mean and peak tracking loss and position prediction error values. However, the approach is trained and evaluated on the same data, which is a set of just six trajectories, which limits the paper's claims in terms of generalization.

Furthermore, the use of a tabular algorithm limits the scalability of this method to more informative state spaces or to multi-target scenarios. Finally, this approach is focused only on update rates, whereas our goal is to allow adaptability in beamwidth as well, which forces us to select observation time simultaneously.

Radar simulator

In order to train and evaluate RL methods, we need to implement an environment that simulates the interaction of a radar with its surroundings. This must include trajectory generation as well as a complete radar pipeline, from detection to track management to dwell generation. Most importantly, we need an antenna model that reflects the effects of the dwell parameters we are interested, especially beamwidth and observation time.

We do not aim to maximize physical accuracy as this would severely impact performance and needlessly slow down the learning process. Instead we need a behavioral simulator where our experiments can provide a proof of concept. The environment must then wrap this simulator and provide an interface for reinforcement learning algorithms to interact with it.

We build our simulator as an extension to the Stone Soup framework. Stone Soup provides a testbed for tracking and state estimation algorithms. It is written in Python We extend Stone Soup's framework in a number of ways to make it suitable for our experiments. First, we implement an Interacting Multiple Model (IMM), which is the type of filtering algorithm most adapted to the tracking of maneuvering targets. We also develop a sensor component that models an electronically scanned array antenna along the lines of the description given in chapter 1. Most crucially, we add a resource management component that establishes a feedback loop between the tracks and the dwells generated at the next step. Stone Soup only implements a one-way data flow, from groundtruth to tracks. By contrast, the resource manager takes the current tracks as input and can generate dwells which are transmitted to the sensor The resource manager serves as the interface with which the reinforcement learning algorithms can interact to receive observations corresponding to the tracks and to take actions which will be translated into dwells to send to the antenna. These dwells affect the detection probability and measurement model of the antenna. Finally, we implement an interactive plotter based on Plotly to analyze the results of runs in terms of tracks and metrics.

Single-target tracking

We now turn to our objective to optimize the joint selection of beamwidth, update rate, and observation time for active tracking. We simplify the setting by assuming a single-target scenario. We also ignore the elevation to consider a 2D simulation. Each episode starts with the track begin initialized at the target's initial state; we do not study the role of the search function in the track's initialization as it happens in real systems. The trajectory of the target is generated online with a maneuvering target kinematic model; the target is constrained to remain in a 40km radius around the radar. The target's state consists in its position, velocity, and acceleration in Cartesian coordinates [x, ẋ, ẍ, y, ẏ, ÿ] ⊤ . The antenna is characterized by a reference signal-to-noise ratio SN R ref = 15dB at 50km for a reference dwell with observation time T ref obs = 432µs and beamwidth θ ref 3dB = 4.12 • , and a probability of false alarm P f a = 1 × 10 -5 . The filter algorithm used for the simulation is an IMM estimator that takes three linear Kalman filters, one per target kinematic models: these are a constant velocity, a constant turn, and a constant acceleration models, all with noise coefficient q = 0.01; the constant turn rate is ω = 0.3rad. The transition probability matrix between the three models is given by:

p =      0.6 0.2 0.2 0.3 0.7 0.0 0.2 0.2 0.6      (3.5)
The IMM's target model mirrors the one used to generate the trajectories. Finally, an episode is interrupted if the track is lost, or ends after a time limit of 200s. A track is considered lost if the IMM's standard deviation of the estimated target azimuth exceeds 3°or after 5 consecutive missed detections.

In terms of interaction between the environment and the RL agent, the observations exposed to the agent consist in the state of the target as estimated by the IMM, the IMM's current mode probabilities, and the previous action. The target state information contains the estimated position and velocity in range and azimuth, as well as their estimated variance. Along the previous action, the observation includes information about whether a detection occurred at the previous time step and about the accuracy of this detection in terms of variance in azimuth. We use a discrete action space where each action corresponds to a combination of an observation time and a beamwidth. The available observation times are A T = {1, 2, 3, 4} × T ref obs while the available beamwidths are A θ = {0.25, 0.5, 0.75, 1, 1.25} × θ ref 3dB . The agent's action is converted to a dwell according to these parameters. We also include a no-op action for which no dwell is generated, which gives us a total of 21 possible actions. An environment step corresponds to 1 second of in-simulation time, to mimic the constraints of a antenna rotating at 60 rotations per minute. The update rate is therefore not considered a settable parameter, but emerges implicitly from the alternation of no-ops and dwell actions. The transition function is implemented by the radar simulator based on Stone Soup outlined above. The reward function takes into account the satisfaction of an accuracy window [σ min , σ max ], defined in terms of angular standard deviation in azimuth σ az as computed by the IMM; if the agent takes an action other than no-op, it receives a penalty proportional to the dwell's observation time T obs weighted by a coefficient c obs to discourage increased radar load; in case of track loss, a more significant penalty c loss is incurred. The reward can therefore be described as:

r =      -c loss if track is lost 1[σ min ⩽ σ az ⩽ σ max ] -T obs max A T otherwise (3.6)
In our experiments we set σ min = 1 • , σ max = 2 • , c obs = 1, and c loss = 50. The choice of these parameters determines the trade-off between track accuracy, track loss, and tracking load that the agent is expected to maintain.

We train our agent with PPO. We use two separate neural networks to output the To evaluate our algorithm, we consider the track loss rate and the mean tracking load, which is the ratio between the accumulated observation time over all dwells and the duration of the episode. When evaluated, our RL agent demonstrates a track loss rate of 12.9% for a mean tracking load of 1.96 × 10 -3 . As a point of comparison, we implement the standard update rate selection strategy from (van Keuk and [START_REF] Van Keuk | On phased-array radar tracking and parameter control[END_REF]. This method uses a fixed beamwidth, and schedules dwells such that the angular accuracy of the track doesn't exceed one sixth of this beamwidth. Using the reference beamwidth θ ref 3dB for the Blackman-van Keuk method, we obtain a track loss rate of 29.1% for a mean tracking load of 3.02 × 10 -3 . As we can see, our RL agent greatly reduces the risk of track loss all while maintaining lower antenna utilization.

Multi-target tracking

The single-target approach does not provide a satisfactory answer to all the problems surrounding current resource management systems. The main shortcoming of current methods is that they optimize each task separately according to its own criteria, before instructing the scheduler to arbitrate the execution of task requests according to their respective priorities. This creates two problems in case of overload: on the one hand, the dwell parameters do not take into account or imperfectly take into account the global state of the system, which can lead to vicious circles; on the other hand, it makes the behavior of the system dependent on the prioritization of the tasks while this prioritization is not necessarily adapted to the objectives of the radar.

These limitations lead us to question the conventional resource management architecture to address the problem on a larger scale, by applying reinforcement learning directly at the level of the entire resource management module. The modeling of the problem would be as follows: the state space would correspond to the list of all radar search areas and tracks, with associated information (time since last update, estimated track accuracy); the action would be to choose which of these tasks to update and what dwell parameters to update it with; the reward could be defined based on the desired tracking accuracy thresholds and the actual accuracy on all targets present in the system, including undetected ones, which would encourage maintaining search (alternatively we could include a term in the reward that is directly related to the quality of the search).

This represents an extension to the restless bandit framework, where the choice of task to update is further parameterized. Additionally, we note that our problem is better described as a multi-objective, with one reward function per task: by weighing each reward, we could reflect the priority level of each task. To our knowledge, no existing reinforcement learning method combines the combinatorial and multi-objective aspects required by our use case; this motivates the search for such methods in the next chapter.

We hope, with such an approach, to be able to take full advantage of the flexibility of MFRs to enable system-wide optimization.

Conclusion

In this chapter, We studied two components of radar resource management: scheduling and active tracking.

Through a reformulation of the problem of radar task scheduling, we were able to implement an efficient framework whose algorithmic applications can return quasi-optimal solutions in a limited amount of time. We see potential improvements for this framework, both by optimizing its run time to make it usable by real-world radars, and by increasing its flexibility; for example, being able to remove a task from a partial schedule could allow exploring the solution space more effectively. Furthermore, our B&B-MCTS algorithm could be extended with an AlphaZero-style reinforcement learning procedure which would make it able to adapt to various task distributions.

We apply model-free reinforcement learning to single-target active tracking to learn to adjust the update rate, beamwidth and duration of dwells dynamically. The extension of this type of method to multi-target tracking requires the development of multi-objective algorithms that can deal with combinatorial state spaces, which we approach in th enext chapter.

Chapter 4

Challenges in multi-objective reinforcement learning

The difficulty of resource management in an MFR is to maintain a balance between several competing sub-objectives: each function must be able to be carried out while limiting its use of resources, so as not to interfere with other sub-objectives. These functions are subdivided into tasks: for the search function, a task can correspond to the surveillance of a given area; for the tracking function, it corresponds to one track. To apply end-to-end reinforcement learning to the whole radar resource management module, we therefore need to account for both the multi-objective and the combinatorial aspects of the problem. More specifically, we need algorithms that can tackle environments where the number of objectives may vary between episodes. Moreover, some of the radar's objectives may have strictly higher priorities over others: for example, it is common to specify a minimum required total search time ratio, or to have tracks corresponding to threatening targets take priority over non-threatening ones. These preferences cannot be readily expressed with a linear scalarization over criteria: therefore we are interested in non-linear multi-objective reinforcement learning methods.

In this chapter, we address each of these points to open perspectives toward a fully reinforcement learning-controlled radar resource manager. We review current methods, detail their limitations, and propose novels algorithms for each case.

Multi-objective factored MDPs

Many potential applications of reinforcement learning involve complex, structured environments. Radar resource management is no exception in this regard, as in our framework, it involves a selection phase where the agent must choose the next radar dwell from a list where each dwell updates a given task. Some of these problems can be analyzed as factored MDPs, where the dynamics are decomposed into locally independent state transitions and the reward is rewritten as the sum of local rewards. However, in some scenarios, these rewards may represent conflicting objectives, so that the problem is better interpreted as a multi-objective one, with a weight associated to each reward. To deal with such multi-objective factored MDPs, we propose a method which combines the use of graph neural networks, to process structured representations, and vector-valued Q-learning. We show that our approach empirically outperforms methods that directly learn from the scalarized reward and demonstrate its ability to generalize to different weights and number of entities.

Most research in the field of deep reinforcement learning initially focused on end-toend learning, where the agent starts out with no prior on the task, for example having to learn to play Atari games from pixels [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF]. Standard RL algorithms thus make minimal assumptions about the structure of the task: they typically take monolithic observations as input, which have to be disentangled internally. However, for complex problems, we often have information about the structure of the environment at our disposal. This information can be used to inject priors into the learning process.

Before the advent of deep RL, researchers tackled large Markov decision processes (MDP) by decomposing the states and rewards into locally conditioned elements [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF]; such factored MDPs were more amenable to tabular approaches, which were hardly directly applicable to large state spaces. Even though in recent times function approximation by deep neural networks has alleviated these issues, accounting for the structure of the state space still helps solving complex environments, for example using relational learning. Relational deep learning aims to embed inductive biases into deep learning architectures in order to leverage assumptions on structured representations composed of entities and their relations [START_REF] Battaglia | Relational inductive biases, deep learning, and graph networks[END_REF]. These representations can be processed by graph neural networks (GNN), which have been successfully applied to challenging reinforcement learning environments, enabling agents to generalize to varying numbers of entities, for example in real-time strategy games like StarCraft and combinatorial puzzle games like Sokoban [START_REF] Zambaldi | Relational Deep Reinforcement Learning[END_REF][START_REF] Vinyals | Grandmaster level in StarCraft II using multi-agent reinforcement learning[END_REF][START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF].

In factored MDPs, rewards typically have an additive structure: they represent the sum of locally-scoped rewards. However, some tasks are better described as striking a compromise between several possibly contradicting objectives. Multi-objective reinforcement learning treats such problems where multiple reward functions are used, each associated with a different objective [START_REF] Roijers | A Survey of Multi-Objective Sequential Decision-Making[END_REF]. The overall goal is given by a utility function that depends on these rewards and on their associated weights, which reflect their level of priority. This setting allows easier definitions of the desired compromises between the competing objectives; it also makes it possible to train an agent that adapts to utility functions that may change over time, e.g. when using a linear scalarization whose weights are not constant. Many promising applications of reinforcement learning benefit from a multi-objective specification. For example, self-driving cars should minimize travel time and maximize the comfort and safety of passengers as well as the safety of nearby pedestrians and drivers at the same time [START_REF] Li | Urban Driving with Multi-Objective Deep Reinforcement Learning[END_REF]. Multi-objective reinforcement has also been used to train a video game-playing agent that can adopt a wide variety of play-styles, opening the way to automated game testing (Le Pelletier de [START_REF] Pelletier De Woillemont | Configurable Agent With Reward As Input: A Play-Style Continuum Generation[END_REF].

In this section, we study the case where the problem combines a structured environment with a multi-objective specification. We argue that this is a natural extension of the concept of factored MDP that holds broad applicative implications, including for radar systems. The radar must regularly update these tracks and surveillance areas, but it can only update one of these tasks at a time due to signal processing and antenna constraints. We can view tracks and surveillance areas as tasks with limited mutual dependence. These tasks are given priority levels according to the mission and threat model of the radar. The antenna time and power constraints under which the radar operates may force the system to make compromises between tasks when under heavy load. Approaching this problem from a RL perspective requires designing an agent which can deal with variable state and action spaces (as the number of targets can vary) and takes into account the priority levels of the different tasks it has to fulfill.

Given the characteristics of this type of problems, we claim that they are best approached within both the factored MDP and multi-objective paradigms. Although sig-nificant work has been carried out in each field, to our knowledge their intersection has not received scrutiny yet. We therefore term our framework multi-objective factored MDPs and set out to analyze how to best solve these problems. To do so, we propose a multi-objective version of DQN [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF] that can be applied to structured observations by making use of recent advances in graph neural networks proposed by [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF]. We discuss how our algorithm, factored multi-objective DQN (FMODQN), can be adapted according to the type of action space and to the characteristics of the factored MDP. We test our approach on a multi-objective version of SysAdmin, a classic example of factored MDP [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF], and on a novel multi-objective task featuring multiple independent entities. Comparisons are made with [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF]'s algorithm, that learns from the scalarized reward. We show that our algorithm outperforms this baseline, can generalize to different reward weight vectors and number of entities, and is able to deal with hundreds of objectives.

Structured representations

Factored MDPs

In the default MDP formulation, no information about the structure of the environment is given, forcing the agent to learn from tabula rasa. Yet there are many problems which can be decomposed into smaller parts whose evolution is largely independent of each other: typically when modeling a production line composed of a number of machines, we would know that the next state of each machine is only influenced by its immediate neighbors. Priors about this type of environment structure motivate us to define compact representations that can help learning agents to generalize more easily over complex states.

Factored MDPs are a notable framework for representing structured MDPs compactly via the exploitation of the conditional independence structures of transitions and rewards [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF][START_REF] Osband | Near-optimal Reinforcement Learning in Factored MDPs[END_REF]. More formally, a state s ∈ S is reinterpreted as a set of n state variables (s 1 , s 2 , ..., s n ). From there, we can define a scoped variable as a subset of the state variables, so that for a scope Z ⊆ {1, ..., n}, the corresponding scoped variable is s[Z] = (s i ) i∈Z . We write s[i] instead of s[{i}] or s i for clarity. Given n scopes Z 1 , ..., Z n , the transition probability function can then be factored into n locally-scoped transition functions in the form

T (s ′ | s, a) = n i=1 T i (s ′ [i] | s[Z i ], a) (4.1)
Similarly, the reward function can be factored over m scopes Z r 1 , ..., Z r m , for example as a sum R(s, a) = m i=1 R i (s[Z r i ], a). SysAdmin [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF] is a classic example of factored MDP. This problem is defined by a directed graph between n nodes that represents a network of computers.

Each computer i is characterized by a single state variable s i with value 1 if the computer is online and 0 if it is offline. The scope of each state variable covers the state variable itself and its parents in the graph. At each time step, the agent can either wait or force a single computer to go (or stay) online; the other computers may randomly shutdown if they are online, based on their dependencies, and may reset when offline. The probability for a computer to be online at the next step if it is not acted on at this step is:

T (s t+1 [i] = 1) =      0.9 j∈Z i st[j] |Z i | if s t [i] = 1 0.04 if s t [i] = 0 (4.2)
All computers are online at the beginning of an episode. The agent receives a reward that depends on the number of online computers and includes a penalty p < 0 for manually rebooting a computer:

R(s t , a t ) = 1⩽i⩽n s t [i] + p • 1(a t ̸ = noop) (4.3)

Graph neural networks

Factored MDPs provide structured representations of complex environments. The next question is how an agent can efficiently process such representations. In machine learning, structured representations generally refer to graph data showing the relations between a set of entities, for example between the atoms of a molecule or the bodies of a physical system. These representations have been approached through the prism of graph neural networks (GNN) [START_REF] Battaglia | Relational inductive biases, deep learning, and graph networks[END_REF][START_REF] Zhou | Graph Neural Networks: A Review of Methods and Applications[END_REF]. GNNs take a tuple (V, E, g) a series of network passes. GNNs impose strong inductive biases, since they can process arbitrary relations between entities, are invariant to node permutations, and support combinatorial generalization to different numbers of nodes and edges. They have been successfully applied to reinforcement learning tasks involving reasoning about interacting entities [START_REF] Hamrick | Relational inductive bias for physical construction in humans and machines[END_REF][START_REF] Wang | NerveNet: Learning Structured Policy with Graph Neural Networks[END_REF][START_REF] Zambaldi | Relational Deep Reinforcement Learning[END_REF].

as input, where V = {v i } i is a set of node attributes, E = {(e k , r k , s k )} k a set

Related work

Structured sequential decision problems have long been studied in the frameworks of factored MDPs and relational MDPs [START_REF] Boutilier | Symbolic Dynamic Programming for First-Order MDPs[END_REF]. In most works on the subject, the environment is assumed to have known dynamics, so that it can be described in an influence diagram language like RDDL [START_REF] Sanner | Relational Dynamic Influence Diagram Language (RDDL): Language Description[END_REF] or PPDDL [START_REF] Younes | The First Probabilistic Track of the International Planning Competition[END_REF], for which there is a rich literature of planning methods [START_REF] Bonet | Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming[END_REF][START_REF] Keyder | The HMDP Planner for Planning with Probabilities. 3rd International Probabilistic Planning Competition[END_REF][START_REF] Associates | ReTrASE: Integrating Paradigms for Approximate Probabilistic Planning[END_REF][START_REF] Kolobov | Reverse Iterative Deepening for Finite-Horizon MDPs with Large Branching Factors[END_REF]. Several methods aim to perform generalized planning by constructing plans that transfer across instances [START_REF] Fern | Approximate Policy Iteration with a Policy Language Bias[END_REF]Guestrin et al., 2003a;[START_REF] Natarajan | Imitation Learning in Relational Domains: A Functional-Gradient Boosting Approach[END_REF][START_REF] Bonet | Learning Features and Abstract Actions for Computing Generalized Plans[END_REF]. A series of recent works [START_REF] Toyer | Action Schema Networks: Generalised Policies With Deep Learning[END_REF][START_REF] Bajpai | Transfer of deep reactive policies for MDP planning[END_REF][START_REF] Garg | Size Independent Neural Transfer for RDDL Planning[END_REF][START_REF] Garg | Symbolic network: Generalized neural policies for relational MDPs[END_REF][START_REF] Sharma | SymNet 2.0: Effectively handling Non-Fluents and Actions in Generalized Neural Policies for RDDL Relational MDPs[END_REF] combines planning and neural networks in order to enable transfer learning.

Methods that operate in a pure RL setting without assuming known dynamics are less studied. GRL [START_REF] Karia | Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems[END_REF] uses tabular Q-learning where the Qvalues are initialized by a neural network trained to predict the final Q-values on different problem sizes, meaning it cannot deal with continuous state spaces; it also cannot perform zero-shot adaptation to problems of different sizes without retraining its tabular Q-values.

The method most closely related to ours in the literature is SR-DRL [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF], which combines message-passing neural networks and auto-regressive policies into a neural network trained with A2C [START_REF] Mnih | Asynchronous Methods for Deep Reinforcement Learning[END_REF] that is applicable to problems with variable state and action spaces. The method is tested on three domains, including SysAdmin, and it is shown that the agent is able to generalize to different problem sizes after training on a single problem size.

In contrast to related work, our method, factored multi-objective DQN (FMODQN), can solve multi-objective factored MDPs with model-free reinforcement learning. We hereafter describe it and detail how it can be adapted to different types of multi-objective factored MDPs.

Problem statement

In the context of factored MDPs, the reward structure is decomposed into a number of locally-scoped rewards. The overall reward can then be retrieved by an aggregation of these local rewards, typically through a simple sum. We argue that in many cases however, each local reward can be interpreted as a different objective. These objectives might not all be of equal importance, with a notion of priority dictating compromises between them. For example, it is not a stretch to suppose that some computers in the SysAdmin scenario might play a more critical role than others in the network's infrastructure. We therefore modify the factored MDP formalism to account for this multi-objective component. More specifically, we alter the agent's objective to maximize the scalarization of expected returns over a vector of locally-scoped rewards R(s t , a t ) = (R(s t [Z r i ], a t )) 1⩽i⩽m . In this section, we restrict ourselves to linear scalarizations; therefore, we can rewrite equation 2.39 to express the agent's objective as:

max π∈Π m i=1 w i E π,T [ ∞ t=0 γ t R(S t [Z r i ], A t )] (4.4)
Our focus is on combinatorial generalization, that is, on environments where the number of state variables and local rewards may vary between episodes, and on agents that can generalize to these variations: as a consequence, we only consider cases where the local transitions and rewards are defined the same for all scopes. This is the case in SysAdmin for example, where the evolution of each computer follows the same rules, and where we can associate the same local reward function to each computer, i.e. 1 if the computer is online and 0 otherwise. This is a key difference compared to most of the multi-objective reinforcement learning literature, where the number of objectives is usually a constant of the problem, since each reward corresponds to an objective of a different kind, like maximizing safety and minimizing travel time for self-driving cars. By contrast, in the type of multi-objective factored MDP that we focus on, there is actually a single reward function that gets applied to different local scopes: for example, to reuse the example of the production line, we would define a single reward function that could return a measure of performance of any machine to which it is applied. Encoding the priority of each reward as a weight rather than as the magnitude of the reward has several advantages: all rewards will by definition have the same scale, allowing the agent to generalize to any number of rewards, and we will then be able to condition the agent's neural network on the current reward weights so that it can learn a policy adapted to different preferences over rewards. Besides, since the weights of all rewards in an instance of the problem sum to 1, the reward weights tend to be lower as the number of rewards increases: this makes the priority levels implicitly linked to the number of rewards.

Algorithm

The general approach in multi-objective value-based methods is to train (using eq. 2.42) a Q-value estimator that returns a matrix Q(s, •, w) ∈ R |A|×m from which we can then retrieve the scalarized action-state value Q(s, a, w) = Q(s, a, w) ⊤ • w. The policy is derived by choosing the action that maximizes this scalarized Q-value. The question is how to design an agent that can generate this Q-matrix on problems where the number of rewards m (and possibly the number of actions) may vary from episode to episode.

Feature extraction Inspired by [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF] [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF] to process the state and retrieve features used to compute the action logits and the state value as required by policy-based algorithms.

However, in our case, we need to predict the Q-values for each reward, so we have to integrate information about the reward structure as well. Therefore, we add m additional reward nodes (c r 1 , ..., c r m ) to the graph such that a reward node attribute contains the weight linked to this reward and an edge c i → c r j exists only if i ∈ Z r j . State and reward nodes are distinguished by an additional type feature. With this structure, a GNN is able to predict the influence of each state variable on the rewards that depend on this state variable. Once this graph has been passed through a GNN, we only need to retrieve the updated reward nodes from the output so as to use them as features to compute the Q-value associated with each reward. Using this scheme we can condition the network on the current reward weights and stay invariant to the number of state variables and rewards/weights. A special case of interest is when there is one reward per state variable: in this situation we fuse each pair of state and reward nodes.

Action space Once we have extracted the features of each reward node, we can compute the Q-values. How we do this depends on the action space. If the action space is fixed and doesn't vary in size with the number of state variables, then we can apply a position-wise multi-layer perceptron (MLP) f that maps each reward node output v r′ i to the Q-values of all actions for this reward, so that for all i ∈ {1, ..., m}, f (v r′ i ) = (Q i (s, a, w)) a∈A .

A more difficult case appears when the action space is variable. We focus on the case where there is one action per state variable, for example when one entity has to be selected at each time step. In this case we need to obtain Q(s, a, w) for each action a.

To do so, we augment each state node attribute with an action embedding with value 1 if the action corresponding to this state variable is chosen, 0 otherwise. For a given action a, this augmented graph G a is passed through a GNN; similarly to before, we apply a position-wise MLP f to each reward node output v r′ i that gives the Q-value for action a and reward r i , i.e. f (v r′ i ) = Q i (s, a, w i ). This way for action a we obtain Q(s, a, w). This operation is applied over n augmented graphs, one for each action, to compute (Q(s, a, w)) a∈A . The processing can be parallelized by batching the augmented graphs. We call this version of our algorithm Batch-FMODQN. One potential issue with this approach is its time complexity, which is quadratic in the number of nodes: since the time complexity of a message-passing step is O(kn) for a graph with n nodes and a maximal degree k, repeating the operation over n graphs yields O(kn 2 ) complexity. This may limit the applicability of our method on large instances.

Complete independence However, we note that this complexity can be improved depending on the graph topology. In particular, in some environments the state variables may be entirely independent from each other (i.e. there are no edges in the graph). This type of structure can be seen for example in some radar scenarios where each surveillance area is an independent task that remains unaffected by the update of other areas. In this case, assuming we have one action a i and one reward r i per state variable s[i], we can process each entity separately by applying a position-wise MLP to the list of state variables. This MLP has two outputs for each state variable s[i]: the action-state value relative to reward r i that corresponds to choosing the associated action

Q i (s[i], a i , w i ),
and the same action-state value corresponding to any other action

Q i (s[i], A ̸ = a i , w i ).
Our reasoning is that since each pair of state variable and reward is independent from the others, the only relevant information to predict the evolution of a given reward is whether the corresponding action is chosen at the present time step. We can then recover the scalarized Q-value of each action via the weighted sum of the local Q-values:

Q(s, a i , w) = w i Q i (s[i], a i , w i ) + j̸ =i w j Q j (s[j],
A ̸ = a i , w j ). This way we do not have to directly compute the whole Q-matrix since it would be mostly redundant; instead, the time complexity of the algorithm is O(n). We call this variant of our algorithm Split-FMODQN.

Dynamic weights By conditioning the network on the current reward weights, we aim to make our agent perform well in the dynamic weights setting where the weights vary between episodes. On this side, we expect to experience fewer issues with reward weight variation compared to standard multi-objective reinforcement learning. Indeed, one of the challenges in multi-objective DQN is its tendency to forget the policies it has learned for other reward weight vectors over the course of training as it tends to overfit to the current weight vector instead: [START_REF] Abels | Dynamic Weights in Multi-Objective Deep Reinforcement Learning[END_REF] in particular identifies this issue and proposes to modify the loss function and replay buffer to alleviate it. We argue that in the context of multi-objective factored MDPs, this problem will be less present, as there is actually one reward function applied over the different reward scopes. Since the Q-value associated with each reward will rarely depend on the whole reward weight vector, our understanding is that the Q-value will generalize more easily to different weights.

Experiments

To validate our framework, we test it on two environments: we apply Batch-FMODQN to a multi-objective version of SysAdmin, and Split-FMODQN to a custom environment where all state variables are independent. Our choice of domains was guided by our long-term goal of applying these methods to air surveillance radar resource management, which involves a task maintenance scheduling problem where numerous tasks must be updated sequentially while accounting for their relative importance. We show that our algorithms can generalize to different reward weights and different instance sizes [START_REF] Vincent | Reinforcement Learning for Multi-objective Factored MDPs using Graph Neural Networks[END_REF].

Training details We train the network on GPU using multi-objective DQN loss (equation 2.42). To gather experience, we run a batch of 256 environments distributed over the same as that used by [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF], since at each iteration, we advance one step in each environment and minimize the loss with one mini-batch of 64 transitions uniformly sampled from the replay buffer. We limit the maximal gradient norm to 3.

We use a soft update rate of 0.005 for the target network. The replay buffer size is 10 5 ; learning starts once the buffer contains 1000 transitions. We use ϵ-greedy exploration with ϵ linearly annealed to 0.1 after 4000 iterations. On all the environments we test, we set the discount factor to 0.99. For Batch-FMODQN, the GNN used to extract features is identical to that of [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF], with 5 message-passing steps and embedding size 32. We use Adam optimizer with a learning rate of 10 -4 . Our algorithms are implemented in the SaLinA framework [START_REF] Denoyer | SaLinA: Sequential Learning of Agents[END_REF]. All tests were performed with AMD Ryzen 3600X CPU, 16 GB of RAM and nVidia GTX 1660 Ti GPU.

Multi-objective SysAdmin We test our proposal on a multi-objective version of SysAdmin. The overall reward is defined as a weighted sum of the rewards corresponding to each computer: the local reward of each computer is 1 if the computer is online and 0 otherwise. Since our focus is on the weighing of the different computers, we remove the penalty for rebooting a computer and consequently also remove noop from the action space since it would always be sub-optimal. The scalarized reward is therefore:

R(s t , a t ) = 1⩽i⩽n w i • s t [i] (4.5)
Similarly to [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF], we randomly generate between 1 and 3 dependencies for each computer at the beginning of an episode. Episodes end after 100 steps.

Since in SysAdmin there is one reward per state variable, we model the state as a graph of n nodes, each of whose attribute contains the state of the corresponding machine

(1 or 0 if online or offline respectively) and the weight for this machine's reward. There is one possible action per machine and machines exhibit dependencies, so we will use Batch-FMODQN. We train a Q-matrix as described above, and reuse the GNN structure proposed by [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF]. We compare our approach to the SR-DRL algorithm of [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF], using the same set of hyperparameters as the ones given in [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF]; our only modifications to their algorithm are the presence of the reward weights in the node attributes, so that the network can condition on them, and the absence of a noop action. We normalize our results with a simple baseline policy that selects the offline computer with highest reward weight to reboot.

We test our approach in the dynamic weights setting: a new reward weight vector is generated at the beginning of each episode, both in training and evaluation. We also normalize the average score against the baseline score.

quadratically in the number of nodes, unlike SR-DRL which has linear computation time. We note however that even on the largest instances tested, the resolution time for a problem instance remains in the seconds, while alternative algorithms based on probabilistic planning may require several minutes to solve a single problem [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF]. Again, since we are interested in the multi-objective aspect, we associate a weight to each reward, so that the global reward is the weighted sum of the local rewards. To facilitate comparisons between the scores for different problem sizes N , we limit degradation rates so that i d i = N/10. Degradation rates are uniformly generated with a maximal factor of 10 between the highest and lowest rates. Episodes last for 100 steps.

Our training procedure is the same as for multi-objective SysAdmin, except that we . Score is the average cumulative reward with 95% confidence interval. We include results from a random policy as a baseline.

efficiency of our approach on this specific type of problems.

Discussion

In this section, we proposed to study multi-objective factored MDPs, a domain so far left unexplored, through which many real-world problems can be analyzed. We presented a family of methods that can solve different types of such problems. We distinguished these methods according to the characteristics of the target problem, and proposed benchmarks on which we showed how our approach outperformed existing algorithms.

To extend our approach to more complex domains such as resource management for air surveillance radars we need to allow parameterization of the selected action, e.g. by choosing the antenna parameters most adapted to the selected radar task. Two research directions seem crucial to us in order to develop these applications. The first one is to make our approach compatible with more complex action spaces of the type seen in parameterized MDPs [START_REF] Hausknecht | Deep Reinforcement Learning in Parameterized Action Space[END_REF]. This might be pursued using autoregressive policies. Auto-regressive policies represent a relatively minor modification in policy-based algorithms [START_REF] Janisch | Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks[END_REF][START_REF] Vinyals | Grandmaster level in StarCraft II using multi-agent reinforcement learning[END_REF]; however we need to combine it with value-based learning in order to maintain our method's advantage in dealing with multi-objective problems. Despite having been first proposed as a modification to DQN by [START_REF] Metz | Discrete Sequential Prediction of Continuous Actions for Deep RL[END_REF], auto-regressive policies have seen little use in value-based methods so far, to the point of being ignored in discussions on auto-regressive structures [START_REF] Fu | Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning[END_REF]; this may be due to existing auto-regressive adaptations of DQN being complex to implement properly, which warrants further research into how to simplify such adaptations. The second direction would rely on advances in multi-objective RL with non-linear scalarization, for which a few approaches have been proposed [START_REF] Dornheim | gTLO: A Generalized and Non-linear Multi-Objective Deep Reinforcement Learning Approach[END_REF] even if issues remain on theoretical and practical levels [START_REF] Vamplew | A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions[END_REF].

4.2 Non-linear scalarization in stochastic multi-objective

MDPs

Many sequential decision problems of interest are best described in relation to multiple, possibly conflicting objectives. However, most existing multi-objective reinforcement learning algorithms only apply in cases where the utility over the different criteria is

linear. Yet it is well known in decision theory that in general linear scalarization poorly reflects users' preferences. Non-linear scalarization poses a number of issues in reinforcement learning, with so far little study and no definite solution. In particular, current methods struggle to deal with the most general setting of multi-objective reinforcement learning, where the environment is stochastic and the scalarization of the objectives is non-linear under the scalarization of expected returns criterion. This is an impediment in our case, since radar operators' preferences are typically better represented with nonlinear utility. We approach this issue from a theoretical side and present a value-based algorithm that provides encouraging preliminary results for this type of problems.

Issues with non-linear scalarization

Current MORL methods face a number of limitations. Recent research on the subject has focused on adaptations of DQN where the preferences are given by a linear scalarization of the vector-valued reward [START_REF] Abels | Dynamic Weights in Multi-Objective Deep Reinforcement Learning[END_REF][START_REF] Nguyen | A Multi-Objective Deep Reinforcement Learning Framework[END_REF][START_REF] Mossalam | Multi-Objective Deep Reinforcement Learning[END_REF].

These methods do provide advantages: their learned Q-values can be scalarized; and they are off-policy, meaning they can learn the optimal policies for different scalarization weights over one training. Unfortunately, value-based methods restrict their solutions to deterministic policies, yet when using non-linear preferences, the optimal solution may require a stochastic policy [START_REF] Chatterjee | Markov Decision Processes with Multiple Objectives[END_REF]. Such a policy can be obtained by defining a mixture of deterministic policies; however finding the optimal mixture given a set of Pareto-optimal policies is a NP problem, which requires the use of heuristics at execution [START_REF] Reymond | Pareto-DQN: Approximating the Pareto front in complex multi-objective decision problems[END_REF]. Multi-objective policy search algorithms either approximate the Pareto front and suffer from the same limitation or are constrained in the form of their preferences [START_REF] Uchibe | Constrained reinforcement learning from intrinsic and extrinsic rewards[END_REF][START_REF] Shelton | Importance Sampling for Reinforcement Learning with Multiple Objectives[END_REF]. In addition, when the environment is stochastic, multi-objective value-based methods can even fail to find the optimal deterministic policy, as demonstrated by [START_REF] Vamplew | A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions[END_REF]. to reach the goal state: the associated reward is negative for all transitions. Crucially, the environment is stochastic: for example, when taking action T in state A, there is a probability p = 0.85 that the agent reaches state B, and a probability p = 0.15 that the episode terminates prematurely. Moreover, the agent's objective is not given by a linear scalarization. Instead, the thresholded lexicographic order over expected returns is used, with a threshold of 0.88 over the first objective. This means that a policy whose expected return for the first objective is above this threshold is always preferred to a policy where the threshold isn't reached. If both policies are on the same side of the threshold, the one which maximizes the last objective is preferred. Under this criterion, the optimal deterministic policy is DI, where D is the action taken in state A and I is taken in state B, as shown in fig. 4.5.

The usual idea to apply Q-learning to a non-linear scalarization u is to define the policy derived from the Q-value as π(s t ) . = arg max a∈A u( t-1 i=0 γ i r(s i , a i ) + Q(s t , a)), that is, to take into account the rewards accumulated since the beginning of the episode in the scalarization. However, the resulting algorithm does not reflect the SER objec- ′ is terminal. D is then preferred as it meets the threshold (unlike T ) and gives a higher average reward than I on the second objective. From there, since the algorithm assumes D to be the best action in state B, it then converges to chose action I in state A as the other two possible actions in A would not allow to meet the threshold. The crux of the issue is that the algorithm chooses its action in B under the assumption that the transition from A to B always succeeds, whereas there is actually a possibility that the episode terminates prematurely, failing to reach the threshold, if T or D are chosen in A.

Therefore, there is need for methods that can account for both non-linear scalarizations and stochastic environments.

K-learning

A new notion of value function for SER

We focus on the most common formulation of MORL, where the general objective is the scalarization of expected returns (SER):

max π u E µ,π,P ∞ i=0 γ i r(s i , a i ) (4.6)
where u : R n → R is the scalarization function and r(s, a) ∈ R n is a vector-valued reward, with n the number of objectives. We write µ for the initial state distribution and P for the transition probability function. When an agent finds itself in a given state of a stochastic environment, in order to take the action that maximizes SER with a non-linear scalarization, it needs to take into account the sum of all rewards, both already received so far and expected on the rest of the episode. Since in SER we apply the scalarization over the expectation of rewards, intuitively the rewards received so far in the episode should be re-weighted to reflect the probability of the trajectory followed so far in the episode. Here we will note a trajectory as τ t = ⟨s τ 0 , a τ 0 , s τ 1 , ..., a τ t-1 , s τ t ⟩. Since we are looking for a value-based method, we only consider deterministic policies taking trajectories as input π(τ ). Let Π D be the space of trajectory-based deterministic policies. As usual, we can define the various value functions:

V π . = E µ,π,P ∞ i=0 γ i r(s i , a i ) (4.7) V π (τ t ) . = E π,P ∞ i=t γ i r(s i , a i ) τ t (4.8) Q π (τ t , a t ) . = E π,P ∞ i=t γ i r(s i , a i ) τ t , a t (4.9)
As shown in section 4.2.1, if we want to find a value-based policy that optimizes for SER, we need to define an adequate notion of value function. Our insight here is that Q π (s t , a t ) is the expected future cumulative reward when following policy πexcept in state s t where action a t is chosen. This amounts to following a sort of adjusted policy, which we formally define as:

ρ π (τ t ; τi , a τ i ) . =      a τ t if t ⩽ i and τ t = τt π(τ t ) else (4.10)
We can then rewrite equivalently Q π (τ t , a t ) = E ∞ i=t γ i r(s i , a i ) τ t , ρ π (• ; τ t , a t ) . Note that if τi ∼ π and a τ i = π(τ i ), then ρ π (τ t ; τi , a τ i ) simplifies to π(τ t ).

In order to take into account the rewards received so far, we modify this formulation of the Q-value to remove the conditioning on the current trajectory τ t and take the expectation of the sum of rewards over whole episodes. We call this the K-value, which we formally define given a policy π as:

K π (τ t , a t ) . = E µ,P ∞ i=0 γ i r(s i , a i ) ρ π (• ; τ t , a t ) (4.11)
The greedy policy associated to a K-value K is naturally defined as maximizing the scalarization of this K-value:

π K u (τ ) . = arg max a∈A u(K(τ, a)) (4.12)
Furthermore, the optimal K-value for deterministic policies is:

K * u (τ t , a t ) . = arg K max π∈Π D u(K π (τ t , a t )) (4.13) Indeed, if we apply π K * u u
(thereafter simplified as π * u ), then we always have τ t ∼ π * u , and a t is chosen by π * u , so ρ π * u (• ; τ t , a t ) simplifies to π * u , so that π * u is optimal for the original objective.

The K-value forms the basis of the K-learning algorithm which we present later in this chapter. However, it is worth exploring why it is a useful generalization of existing value function definitions.

Links to existing approaches

We first show that the K-value can be rewritten as a function of Q π and V π . In all our demonstrations we assume a discrete state space. First we note that K π can be separated into two terms based on the probability that the initial state is the trajectory's first state

s τ 0 : K π (τ t , a t ) = s̸ =s τ 0 µ(s) E P ∞ i=0 γ i r(s i , a i ) s 0 = s, ρ π (• ; τ t , a t ) + µ(s τ 0 ) E P ∞ i=0 γ i r(s i , a i ) s 0 = s τ 0 , ρ π (• ; τ t , a t ) (4.14)
In the first term, we can see that since s ̸ = s τ 0 , then ρ π (• ; τ t , a t ) simplifies to π, so that this term can be expressed as a function of V π :

s̸ =s τ 0 µ(s) E P ∞ i=0 γ i r(s i , a i ) s 0 = s, ρ π (• ; τ t , a t ) = s̸ =s τ 0 µ(s) E P ∞ i=0 γ i r(s i , a i ) s 0 = s, π (4.15) = s̸ =s τ 0 µ(s)V π (s) (4.16) = s µ(s)V π (s) -µ(s τ 0 )V π (s τ 0 ) (4.17) = V π -µ(s τ 0 )V π (s τ 0 ) (4.18)
The second term can be rewritten as µ(s τ 0 )K π 0 (τ t , a t ), where for j ⩽ t:

K π j (τ t , a) . = E P   ∞ i=j γ i-j r(s i , a i ) τ j , ρ π (• ; τ t , a)   (4.19)
This value can then be written recursively for j < t:

K π j (τ t , a t ) = E[r(s τ j , a τ j )] + γ s P (s|s τ j , a τ j ) E P   ∞ i=j+1 γ i-j-1 r(s i , a i ) ⟨τ j , a τ j , s⟩, ρ π (• ; τ t , a t )   (4.20) = E[r(s τ j , a τ j )] + γ s̸ =s τ j+1 P (s|s τ j , a τ j ) E P   ∞ i=j+1 γ i-j-1 r(s i , a i ) ⟨τ j , a τ j , s⟩, ρ π (• ; τ t , a t )   + γP (s τ j+1 |s τ j , a τ j ) E P   ∞ i=j+1 γ i-j-1 r(s i , a i ) ⟨τ j , a τ j , s τ j+1 ⟩, ρ π (• ; τ t , a t )   (4.21) = E[r(s τ j , a τ j )] + γ s̸ =s τ j+1 P (s|s τ j , a τ j )V π (⟨τ j , a τ j , s⟩) + γP (s τ j+1 |s τ j , a τ j )K π j+1 (τ t , a t ) (4.22) = E[r(s τ j , a τ j )] + γ E s∼P V π (⟨τ j , a τ j , s⟩) + γP (s τ j+1 |s τ j , a τ j )(K π j+1 (τ t , a t ) -V π (τ j+1 )) (4.23) = Q π (τ j , a τ j ) + γP (s τ j+1 |s τ j , a τ j )(K π j+1 (τ t , a t ) -V π (τ j+1 )) (4.24)
Now, noticing that K π t (τ t , a t ) = Q π (τ t , a t ), we can apply this relation recursively (replacing a t with a τ t for notational convenience):

K π 0 (τ t , a τ t ) = Q π (τ 0 , a τ 0 ) + t i=1 γ i P (τ i )(Q π (τ i , a τ i ) -V π (τ i )) (4.25)
where P (τ i ) . = i-1 k=0 P (s τ k+1 |s τ k , a τ k ).

Equations 4.18 and 4.25 can now be used to simplify equation 4.14:

K π (τ t , a τ t ) = V π + µ(s τ 0 ) Q π (τ 0 , a τ 0 ) -V π (τ 0 ) + t i=1 γ i P (τ i )(Q π (τ i , a τ i ) -V π (τ i )) (4.26) = V π + t i=0 γ i P µ (τ i )(Q π (τ i , a τ i ) -V π (τ i )) (4.27)
where P µ (τ i ) . = µ(s τ 0 )P (τ i ). As we can see, eq. ( 4.27) shows that K π (τ t , a τ t ) can be expressed as the sum of the policy value V π and of the advantages associated to the actions taken in the trajectory τ t , weighted by the probability of reaching these actions as dictated by the environment's stochasticity.

From here, we can establish equivalences between the notion of K-value and the more common uses of the Q-value in multi-objective settings. These equivalences show up when either of the conditions that brought us to define the K-value are absent, that is: when the scalarization is linear or when the environment is deterministic.

First we consider the case where the scalarization u is linear. We can then isolate the Q-value corresponding to action a t when scalarizing K π (τ t , a t ):

u(K π (τ t , a t )) = u(V π + t-1 i=1 γ i P µ (τ i )(Q π (τ i , a τ i ) -V π (τ i )) -γ t P µ (τ t )V π (τ t )) + γ t P µ (τ t )u(Q π (τ t , a t )) (4.28)
As a consequence, in this case, maximizing the scalarized K-value is equivalent to maximizing the scalarized Q-value, as has been done previously [START_REF] Mossalam | Multi-Objective Deep Reinforcement Learning[END_REF][START_REF] Abels | Dynamic Weights in Multi-Objective Deep Reinforcement Learning[END_REF]:

arg max at u(K π (τ t , a t )) = arg max at u(Q π (τ t , a t )) (4.29)
Now we consider the case where the environment is deterministic. If the transitions are deterministic, since τ t has a non-zero probability of occurring, then equation 4.22 simplifies to:

K π j (τ t , a t ) = E[r(s τ j , a τ j )] + γK π j+1 (τ t , a t ) (4.30)
Since µ is also deterministic, s τ 0 is the only possible initial state, so K π (τ t , a t ) = K π 0 (τ t , a t ). Applying equation 4.30 recursively, we get:

u(K π (τ t , a t )) = u t-1 i=0 γ i E[r(s τ i , a τ i )] + γ t Q π (τ t , a t ) (4.31)
which is equivalent to the common solution when rewards are deterministic [START_REF] Vamplew | A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions[END_REF].

In both cases, if the MDP is fully observable, since the transition function is Markovian, the Q-value depends only on the most recent state, i.e. Q π (τ t , a t ) = Q π (s t , a t ).

Optimality operator for the K-value Equation 4.27 could be used as the basis of a control algorithm, where the K-value could be approximated based on a learned Q-value and state value. However, this would require knowing or learning the initialization and transition probabilities of the MDP, which can be difficult to scale up. Instead, we set out to find an algorithm which learns to approximate the K-value itself. To do so, we first need to define H(h | τ t ) the improper probability of deviating from trajectory τ t after h ∈ [0, t] steps while following policy ρ π (• ; τ t , a τ t ) (when the trajectory doesn't deviate, we consider that h = t):

H(h | τ t ) . = prob(∀i < h, s i = s τ i ∧ (h = t ∨ s h ̸ = s τ h ) | s 0 ∼ µ, ∀j s j ∼ P (• | s j-1 , a τ j-1 )) (4.32)
Note that we have h = 0 if s 0 ̸ = s τ 0 . The K-value can now be expressed as:

K π (τ t , a τ t ) = E ∞ i=0 γ i r(s i , a i ) s i ∼ (µ, P ), a i = ρ π (• ; τ t , a τ t ) (4.33) = E h-1 i=0 γ i r(s i , a i ) + ∞ i=h γ i r(s i , a i ) h ∼ H(• ; τ t ), s i ∼ (µ, P ), a i = ρ π (• ; τ t , a τ t ) (4.34) = E h-1 i=0 γ i r(s τ i , a τ i ) + γ h Q π (τ s h , a h ) h ∼ H(• ; τ t ), s h ∼ (µ, P ), a h = ρ π (τ s h ; τ t , a τ t ) (4.35)
where τ s h = ⟨s τ 0 , a τ 0 , s τ 1 , ..., a τ h-1 , s h ⟩. Note that we have a h = a τ t if h = t and s h = s τ h (i.e. there was no deviation), and a h ∼ π otherwise. This way, the probability function H allows us to rewrite the K-value as an expectation over the sum of rewards up to a deviation from the trajectory τ t at step h, plus the Q-value after this deviation.

Recalling that π K u is the greedy policy w.r.t. value K and scalarization u, our proposed optimality operator, defined over a value space Q 2 , where Q = ∞ n=1 ((R m ) S×A ) n , m is the number of objectives and n the length of the trajectory, is therefore

T (K, Q) . = (T K, T Q) for (K, Q) ∈ Q 2 , where: T K(τ t , a τ t ) . = E h-1 i=0 γ i r(s τ i , a τ i ) + γ h Q(τ s h , a h ) h ∼ H(• ; τ t ), s h ∼ (µ, P ), a h = ρ π K u (τ s h ; τ t , a τ t ) (4.36) T Q(τ t , a τ t ) . = E r(s τ t , a τ t ) + γQ(τ s t+1 , a t+1 ) s t+1 ∼ P, a t+1 = π K u (τ s t+1 ) (4.37)
In order to prove the convergence of this operator, we define a value metric:

d((K, Q), (K ′ , Q ′ )) = max{∥K -K ′ ∥, ∥Q -Q ′ ∥} (4.38)
where ∥Q∥ = max τ,a ∥Q(τ, a)∥ ∞ for Q ∈ Q. We now prove that the operator we defined is a contraction on the metric space (Q, d). Let K (i) be the value of K for the ith objective. Then:

∥T K -T K ′ ∥ = max i,τt,a τ t T K (i) (τ t , a τ t ) -T K ′ (i) (τ t , a τ t ) (4.39) = max i,τt,a τ t E γ h Q (i) (τ s h , a h ) -γ h Q ′ (i) (τ s h , a h ) H, µ, P, ρ π K u (• ; τ t , a τ t ) (4.40) ⩽ max i,τt max h,s h ,a h γ h Q (i) (τ s h , a h ) -γ h Q ′ (i) (τ s h , a h ) (4.41) ⩽ max i,h,τ,a γ h Q (i) (τ, a) -γ h Q ′ (i) (τ, a) (4.42) ⩽ max i,τ,a Q (i) (τ, a) -Q ′ (i) (τ, a) (4.43) = ∥Q -Q ′ ∥ (4.44)
Similarly, we can show that our operator constitutes a contraction over Q:

∥T Q -T Q ′ ∥ = max i,τt,a τ t T Q (i) (τ t , a τ t ) -T Q ′ (i) (τ t , a τ t ) (4.45) = max i,τt,a τ t E γQ (i) (τ s t+1 , a t+1 ) -γQ ′ (i) (τ s t+1 , a t+1 ) P, π K u (4.46) ⩽ γ max i,τt,a τ t max s t+1 ,a t+1 Q (i) (τ s t+1 , a t+1 ) -Q ′ (i) (τ s t+1 , a t+1 ) (4.47) ⩽ γ max i,τ,a Q (i) (τ, a) -Q ′ (i) (τ, a) (4.48) = γ∥Q -Q ′ ∥ (4.49)
By using the two previous inequalities, we see that

T 2 (K, Q) is a contraction: d(T 2 (K, Q), T 2 (K ′ , Q ′ )) = max{∥T 2 K -T 2 K ′ ∥, ∥T 2 Q -T 2 Q ′ ∥} (4.50) ⩽ max{∥T Q -T Q ′ ∥, γ∥T Q -T Q ′ ∥} (4.51) ⩽ max{γ∥Q -Q ′ ∥, γ 2 ∥Q -Q ′ ∥} (4.52) = γ∥Q -Q ′ ∥ (4.53) ⩽ γ max{∥K -K ′ ∥, ∥Q -Q ′ ∥} (4.54) = γd((K, Q), (K ′ , Q ′ )) (4.55)
We then show that the fixed point of this operator is the optimal value for (K, Q). state spaces (even though it could potentially be adapted to continuous state spaces by using approximate state comparisons). It is also inapplicable in infinite-horizon settings, with no clear equivalent. Moreover, the learned K-value could have high variance, especially the more stochastic the environment is, which would make it non-trivial to learn. Additionally, both the K-value and Q-value in this scheme depend on the whole trajectory instead of the last state: for tabular implementations, their representation would take memory space exponential in the number of states, while if using neural networks for function approximation, we would probably have to use RNNs, which would make training even more difficult. Finally, one limitation that we had to accept as soon as restricted ourselves to value-based methods is that we can only obtain deterministic policies, even though the optimal policy under SER can be stochastic.

T Q * u (τ t , a τ t ) = E [r(s τ t , a τ t ) + γQ * u (τ s t+1 , a t+1 ) | s t+1 ∼ P, a t+1 = π * u (τ s t+1 )] (4.56) = E r(s τ t , a τ t ) + γ E π * u ,P ∞ i=t+1 γ i r(s i , a i ) τ s t+1 , a t+1 s t+1 ∼ P, a t+1 = π * u (τ s t+1 ) (4.57) = E π * u ,P r(s τ t , a τ t ) + γ ∞ i=t+1 γ i r(s i , a i ) τ t , a τ t (4.58) = E π * u ,P ∞ i=t γ i r(s i , a i ) τ t , a τ t (4.59) = Q * u (τ t , a τ t ) (4.60)

Experiments

We test our method on the Space Traders environment. In order to do this, we implement a tabular version of K-learning, which is possible for this environment given its small state space. In our experiments, we set the learning rate to 0.001 and epsilon to 0.5 and generate N = 100,000 reference trajectories, which means training lasts for 200,000

episodes. Similarly to [START_REF] Vamplew | A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions[END_REF], we apply the thresholded lexicographic order on the two objectives, with a threshold of 0.88 on the first one. Therefore, the optimal deterministic policy we expect to converge to is DI, with a mean return of 0.9 more dwell parameters, especially the duration of the dwells, which we considered fixed in our work. This could attenuate the difficulties posed by the separate optimization of each track. While these extensions of the problem have already been studied and heuristics have been developed for them, adapting MCTS techniques to these cases has the potential to increase the performance and adaptivity of radar schedulers.

There is also room for improvement for radar scheduling in terms of reinforcement learning techniques. One clear extension is to apply algorithms like AlphaZero, which combine MCTS with the learning of a value network and a policy network. These networks are trained with the experience gathered by execution of the tree search, and are used to guide the search, which leads to the mutual optimizing of the search process and the networks. This learning procedure could also help adapt the search to different distributions of tasks. Although it did not provide improvement for the version of the scheduling problem we studied, AlphaZero-style methods could prove useful in addressing more intricate scheduling problems as outlined above. In addition to model-based methods like AlphaZero, combinatorial optimization problems have also been addressed with model-free reinforcement learning algorithms coupled with neural encoders like pointer networks and transformers, with promising results [START_REF] Mazyavkina | Reinforcement Learning for Combinatorial Optimization: A Survey[END_REF]. This perspective has so far seen little study in the case of radar scheduling, apart from [START_REF] George | Deep Q-Network for Radar Task-Scheduling Problem[END_REF]). Yet it is compelling as the resulting algorithms could be able to output high-quality solutions at a fraction of the run time required by search methods, while still allowing for adaptation to different task distributions.

However, all methods focused solely on radar scheduling suffer from a more practical disadvantage in that they require to define the costs associated to each task in order to evaluate the possible schedules. These costs can be derived from the priority levels of the dwells as determined in the prioritization phase, yet this prioritization introduces an intermediate objective that can be difficult to align with the desired radar behavior correctly in practice. This limitation could be circumvented by adopting holistic approaches to radar resource management, as we discuss below.

Our second area of study in chapter 3 was active tracking dwell optimization. We observed that despite the beam agility of electronically scanned array antennae, the beamwidth parameter was underutilized by current resource management techniques as it was usually fixed to a constant value on which the algorithm for update rate selection depended. Given the interplay between beamwidth, revisit interval, and dwell duration in determining the quality of the measurements required to maintain tracks, we set out to apply model-free reinforcement learning to obtain an agent that could dynamically adapt these parameters. We implemented a simulator that reflected the high-level dynamics of the interactions between the radar and its environment and that could interface with reinforcement learning algorithms. Having restricted ourselves to single-target tracking on radars with rotating antennae, we showed that the agent we trained boasted both a lower track loss rate and lower antenna time utilization compared to a fixed-beamwidth method, confirming the benefits for beamwidth adaptivity.

This single-target agent fits into the currently common architectural choice of pertrack dwell optimization. However, a compelling alternative is to develop a multi-target agent that would manage the allocation of antenna time between the different tracks established by the system while also adjusting the same dwell parameters as previously, especially beamwidth. This method could be extended to handle all the radar's tasks, that would mainly include tracks and search tasks. Such an extension would represent a holistic approach, which unlike current architectures would not separate between dwell parameter selection, task prioritization, and task scheduling, and would therefore avoid their pitfalls, where a lack of coordination between these different components may lead to ungraceful degradation in situations of overload. This framework has previously been studied in terms of restless multi-armed bandits, but was hindered by the computational limitations of the algorithms used to solve this problem, which were based on dynamic programming. To apply modern reinforcement techniques, we not only need to deal with the combinatorial aspect of the problem, as the radar's tasks routinely number in the hundreds and the number of tracks varies over time; it is also desirable to introduce multi-objective learning in order for the agent to be able to adapt to the different levels of priority between scenarios and between tasks. To develop the tools necessary to this vision, we had to address more fundamental questions in reinforcement learning.

In chapter 4, we investigated two reinforcement learning topics which hold high potential for radar resource management: the combination of multi-objective learning with factored MDPs, and the use of non-linear scalarizations in multi-objective reinforcement learning (MORL).

On the topic of MORL in combinatorial problems, we identified that factored MDPs as a suitable framework for the optimization of strategies in temporally-extended prob-lems with combinatorial state and action spaces, as the ones faced by multi-function radars. We modified the formulation of factored MDPs to include a multi-objective aspect, where each of the problem's entities have an associated reward and weight, from which the general objective is derived as a linear, weighted scalarization of these rewards.

We leverage recent advances in the use of graph neural networks (GNN) to deal with the combinatorial aspect of the problem, and combine this with a multi-objective version of DQN. Starting from the most general case, we detail how the structure of the network can be simplified based on the characteristics of the problem. Finally, on two custom benchmark environments chosen for their similarity to the our radar use case, we show that our algorithms can handle problems with variable numbers of entities and rewards and that they compare favorably to an existing GNN-based method, with better performance and generalization to dynamic reward weights.

Although encouraging, this approach inherit a number of disadvantages from its value-based aspect. The most pressing issue is that in the most general case, our method has to compute the Q-value of each objective for each possible action: when the number of objectives and the number of actions are both tied to the number of entities in the problem, our method suffers from a quadratic time complexity at each action selection step, which limits its scalability to radar resource management problems. Moreover, unlike the policy-based method against which we made comparisons, our value-based method cannot handle complex action spaces: in particular, it is not suitable for parameterized actions, which policy-based algorithms can manage trivially via auto-regressive networks. This is especially relevant if we have the multi-target scenario in mind, since we want our agent to perform both task selection (choosing a track to update at the present step) and task parameterization (setting the parameters of dwell used to update the track). The last limitation is shared with existing multi-objective value-based methods: only linear scalarizations can be used, since non-linear scalarizations break a number of key assumptions in reinforcement learning. Again, this has implications in terms of applicability to radar systems, as the radar's mission is often specified via strict priority levels: for example, it may be required that the proportion of time spent on search tasks remain above a given threshold to guarantee adequate surveillance even during overload; a dangerous target may be given absolute priority over all the other less threatening targets. These preferences can be difficult, sometimes impossible, to encode using linear scalarizations.

The limitations of linear scalarizations motivate our last contribution, centered on the use of MORL with non-linear scalarizations. It had been established previously that one of the most common approaches to MORL in the scalarization of expected returns (SER) setting, multi-objective DQN, could fail to converge to the optimal solution in stochastic environments under a non-linear scalarization. Given the inherently stochastic nature of the radar's observations, solving this issue could open new perspectives for applications of reinforcement learning in radar systems. By virtue of being off-policy, value-based methods can adapt to varying reward weights and so have been a focus in MORL. Therefore, we attempt to develop a value-based algorithm adapted to non-linear scalarization. To do so we extend the classic notion of Q-value: the resulting K-value can be learned by an algorithm, which we term K-learning, and for which we provide a proof of convergence showing that it can reach the optimal deterministic policy even in stochastic environments. We successfully test our method on a toy problem that was designed to highlight the issues with non-linear scalarizations. Despite its theoretical guarantees, K-learning suffers from many disadvantages that limit its applicability to large-scale problems.

In future work, we hope to apply MORL methods such as those investigated in chapter 4 to develop agents that can optimize multi-function radar resource management end-toend. With the rewards defined at the task level and expressive, non-linear scalarization to translate the radar's intended behavior, we expect to obtain strategies that can efficiently coordinate dwell optimization and antenna scheduling. We also anticipate that this will allow better coordination between search and tracking. Search dwells can be used to update tracks via an process called track-while-scan (TWS). Current systems decide on a per-track basis whether to update the track by search or active tracking dwells depending on e.g. the threat level or priority level of the track. This choice could be delegated to our end-to-end resource management agent, which could decide for each search dwell it selects whether to use it for track updates as well: this would allow to adjust TWS more dynamically.

The idea of an end-to-end resource management agent could be taken further still by giving it control over the beam direction. In our work, we assumed that the role of the agent would be to select a task to update; whether it corresponds to a track or a search zone, the update dwell would be given a beam direction beyond the control of the agent, as this direction can be determined based on the estimated position of the target according to the filtering algorithm in the tracking case, or based on a pre-computed search pattern in the search case. However, we could alternatively remove task selection from the agent's action space, and instead make this action space correspond only to the choice of the dwell's parameters, including the direction of the beam. The agent would then have to also optimize its search pattern. Although this formulation would be harder to solve, it may result in a more versatile agent that would learn new, more agile forms of coordination between search and tracking.

Throughout our work, we restricted ourselves to the case of a single multi-function radar with rotating antenna, which is a common use case nowadays. However, future generations of radar systems will go beyond this model, be it through the use of multipleinput multiple-output (MIMO) antennae or of radar networks. Yet the capabilities of these new systems will pose a challenge in terms of resource management. MIMO radars, for example, will be able to generate several dwells in parallel: this puts into question methods that assume a linear utilization of antenna time. Radars working in network will have to apportion tracks among themselves depending on the disposition of the targets and the load of each radar: the coordination of the radars could be tackled via multiagent reinforcement learning, with each radar learning to communicate and adapt to the behavior of the other radars. Multi-agent reinforcement learning could also be applied to the tracking of autonomous reactive targets. Although most targets can detect when they are being illuminated by a radar, so far only human pilots are susceptible to react and attempt maneuvers to cause the radar to lose their track. In the future, as reactive unmanned targets are bound to be developed, one way to adapt radar strategies would be to train radar resource management agents in environments where the target is also modeled as an agent that learns to escape the radar's sight. Given the host of evolutions to come in radar systems, we hope that the insights gained from the application of reinforcement learning to multi-function radars may be transferred and expanded on to build adaptive, reliable systems.

Finally, we believe multi-objective methods holds broader implications for reinforcement learning in general. We see MORL as a crucial tool to help with one of the most common practical impediments to real-life applications of reinforcement learning, which is reward specification. The expressiveness of non-linear scalarizations opens new possibilities for reward shaping that could feel more intuitive to practitioners. Furthermore, we think non-linear scalarizations like the thresholded lexicographic order could be repurposed to implement a form of curriculum learning: indeed, with this approach, the agent would have to start by learning to reach a first threshold on the expected return for the most important objective, and once this objective is fulfilled, try to reach the second threshold, etc. If the objectives are ordered by increasing difficulty, this could help guide the agent's learning without requiring more complex curriculum methodologies. One disadvantage for this approach is that under SER, each threshold is checked against the expectation of the return for this objective, which doesn't correspond to the intuitive notion of the threshold as a level that the agent can reach at (almost) all episodes. In this context, it could be interesting to take inspiration from distributional reinforcement learning [START_REF] Dabney | Implicit Quantile Networks for Distributional Reinforcement Learning[END_REF]. By learning a distributional value function, we can derive risk-sensitive policies: roughly speaking, we could have the agent consider not the average return, but the mean of the bottom 10% of returns, which would take us closer to putting a threshold on the worst cases. In the long term, MORL also represents a promising perspective towards AI safety and alignment, as it allows practitioners to express complex preferences over conflicting objectives. We hope further progress on multi-objective methods will bolster this vision and permit the development of safe AI systems.

Reinforcement Learning for Multi-Function Radar Resource Management Abstract

In the wake of recent advances in the field of machine learning, much progress has been accomplished in one of its sub-fields, reinforcement learning, whose aim is to solve sequential decision problems under uncertainty. Radar resource management seems to represent an ideal application case for this type of technique. Indeed, a radar emits signals, called dwells, whose echoes are used to measure the state of surrounding objects; these dwells vary according to numerous parameters (duration, beam width...) and must be executed sequentially. The surveillance strategy of a multi-function radar thus consists in continuously selecting the dwells to perform, with the aim of searching the surrounding space while tracking already detected targets. The methods currently used to address this problem are largely heuristic, and are likely to run into difficulties in a range of complex situations involving hyper-velocity or hyper-maneuvering targets. First, we propose applications of reinforcement learning techniques adapted to the current architecture of multi-function radars. These contributions focus on two aspects : dwell scheduling on the antenna using model-based methods, and active tracking dwell optimization using model-free methods. Secondly, we highlight the limitations of current resource management architectures, which leads us to consider an alternative architecture for which we propose new reinforcement learning algorithms designed to address the problems it raises. These contributions focus both on the multi-objective aspect, which is useful in multi-function radars to reflect the trade-offs to be made between different functions, and on the combinatorial aspect, which is due to the large number of tasks that the radar must carry out in parallel.

Keywords: reinforcement learning, radar, scheduling, multi-objective

Résumé

Dans le sillage des avancées récentes dans le champ de l'apprentissage automatique, de nombreux progrès ont été réalisés dans l'un de ses sous-domaines, l'apprentissage par renforcement, dont le but est de résoudre des problèmes de décision séquentielle dans l'incertain. La gestion de ressources radar semble représenter un cadre d'application propice pour ce type de techniques. En effet, un radar émet des signaux, appelés pointages, dont l'écho permet de mesurer l'état des objets alentour ; ces pointages varient selon de nombreux paramètres (durée, largeur de faisceau.

  Figure 1.1: Multi-function radars carry out both search and tracking tasks.

Figure 1 . 4 :

 14 Figure 1.4: Beamforming at emission (left) and at reception (right).

Figure 1 . 5 :

 15 Figure 1.5: Example of error signal response k s (θ).

  radars (MFR) are able to concurrently perform a wide range of functions by varying parameters related to waveform selection and beamforming, such as the observation time and the half-power beamwidth. Radar functions center on searching for new targets and tracking existing ones. Additional functions may include missile guidance, target recognition and calibration. Each function is accomplished by tasks; for example a tracking task refers to the tracking of a single target. A task is performed by a number of dwells.

Figure 1

 1 Figure 1.6: Thales' GF300, an example of multi-function radar.

  [START_REF] Tavakoli | Action Branching Architectures for Deep Reinforcement Learning[END_REF] propose Branching dueling Q-networks, an extension of dueling Q-networks where the advantage value function is predicted independently for each action dimension. However this solution does not allow coordination between the different subactions.[START_REF] Metz | Discrete Sequential Prediction of Continuous Actions for Deep RL[END_REF] overcome this limitation by sequentially generating actions, one dimension at a time. This is done by modifying the original MDP: the original transitions are broken up into a trajectory of intermediate states that consist of the current actual state and the sub-actions chosen so far; one 1-dimensional sub-action is chosen at each step, and the intermediate states do not have rewards or discounting.

  parameterized by a weight vector θ. Therefore, they always use function approximation. Policy-based methods present several advantages. They can represent stochastic policies, as opposed to deterministic policies in value-based methods: for example, this means that policy-based methods can deal with continuous action spaces by expressing π(a | s ; θ) as a probability density function. Additionally, deterministic policies may not be best suited for certain settings, such as POMDPs, adversarial settings, and multi-objective problems. Finally, they are usually more stable than value-based methods, but less sample-efficient.

Fujimoto

  et al. (2018) adapt double learning for actor-critic algorithms and apply it to DDPG to obtain the Twin Delayed Deep Deterministic policy-gradient algorithm (TD3).

Figure 3 . 1 :

 31 Figure 3.1: Schema of a frame-based scheduler.

Figure 3 . 2 :

 32 Figure 3.2: Example of a partial schedule.

Figure 3 . 3 :

 33 Figure 3.3: Example of a chronological transition.

Figure 3 . 4 :

 34 Figure 3.4: Example of a transition processed by the custom solver.

Figure 3

 3 Figure 3.5: Solving the time setting and ordering problem.

Figure 3 . 6 :

 36 Figure 3.6: The steps of MCTS (adapted from Browne et al. (2012)).

Figure 3

 3 Figure 3.7: Example of a B&B MCTS execution on the 5-task instance shown on the left. Node label: 1 if the task is scheduled, 0 if dropped, dash if available, red if disallowed. Solutions are shown in green. Brown nodes can be pruned based on solutions already obtained, which restricts the search tree.

  Figure 3.8: Cost plotted against instance size for identical start and due times.

Figure 3

 3 Figure 3.9: 50 tasks

  Figure 3.10: 50 tasks

  Figure 3.11: Architecture of our simulator based on Stone Soup. Black arrows represent composition relationships between modules. Red arrows represent the original Stone Soup data flow. Green arrows represent the feedback loop added to our simulator.

Figure 3 .

 3 Figure 3.12: Example of the rendering of a run in the simulator.

Figure 3 .

 3 Figure 3.13: Mean and 95% confidence interval of reward (left) and episode length (right) over 5 training runs.

  policy and value function. The policy network is a multi-layer perceptron (MLP) with 2 layers of size 64, while the value network is a 2-layer MLP with size 256; both use tanh activation functions. The clipping parameter ϵ is set to 0.25, and the generalized advantage estimation parameter λ to 0.9. Training takes place over 1.5 million steps; training updates happen every 2000 steps, where each training update is repeated for 10 epochs with minibatch size 256. The learning rate is 3 × 10 -4 .

  of directed edges characterized by attributes e k and indices of receiver r k and sender s k nodes, and g represents the global context. The nodes, edges, and context of the graph are updated by

Figure 4

 4 Figure 4.1: A visualization of a SysAdmin instance. Offline nodes are red, online ones are blue. The probability of a node going online at the next step (unless it is manually reset) is shown in each node. The probability of a node going offline increases with the number of offline parent nodes.

Figure 4

 4 Figure 4.2: High-level view of the Split-FMODQN architecture. The same MLP is applied in parallel to each state variable: the outputs are recombined to obtain the scalarized Q-value of each action. For clarity, on this figure, reward weights are omitted from the input of the MLP and from the scalarization.

Figure 4 . 3 :

 43 Figure 4.3: Evolution of average cumulative reward during training on multi-objective SysAdmin with dynamic weights, N = 10. Mean with standard deviation over 4 runs.

use

  Split-FMODQN to obtain Q-values, since each entity is independent. The network consists of a single MLP with 5 hidden layers of size 32. The agent's observation is the list of state attributes, containing the current level of balance, the degradation rate, and the weight of the corresponding reward. Again, we compare to SR-DRL, which we train with the same set of hyperparameters as for SysAdmin. The agents are trained with problems of size 10 and evaluated on other problem sizes, all in the dynamic weights setting. Training time with N=10 is 5 minutes for Split-FMODQN and 7 minutes for SR-DRL. Resolution time per episode reaches 17ms for Split-FMODQN and 42ms for SR-DRL with N=160.

Figure 4

 4 Figure 4.4: The Space Traders environment, adapted by Vamplew et al. (2022). Displayed next to each transition from a state-action pair to a new state are the reward vector r and the probability p of the transition.

Figure 4

 4 Figure 4.5: Values associated to each objective for every possible deterministic policy. The gray dotted line represents the convex front. Policies represented as a hollow point are Pareto-dominated. DI is the optimal deterministic policy when optimizing under thresholded lexicographic order with threshold 0.88, shown as the red dotted line. (Reproduced from Vamplew et al. (2022).)

Figure 4 . 6 :

 46 Figure 4.6: Policy to which multi-objective Q-learning converges on Space Traders. The Q-value vector learned for each state-action pair is displayed. Red arrows represent the action taken by the policy in a given state.

Figure 4 . 7 :

 47 Figure 4.7: Mean and 95% confidence interval of the returns on both objectives for Space Traders over 10 training runs of K-learning.

  ..) et doivent être exécutés séquentiellement. La stratégie de surveillance d'un radar multi-fonctions revient ainsi à sélectionner en continu les pointages à effectuer dans le but de surveiller l'espace environnant tout en pistant les cibles déjà détectées. Les méthodes utilisées actuellement pour répondre à cette problématique sont en grande partie heuristiques et risquent d'être mises en difficulté dans une gamme de situations complexes impliquant des cibles hyper-véloces ou hyper-manoeuvrantes. Dans un premier temps, nous proposons des applications de techniques d'apprentissage par renforcement adaptées à l'architecture courante des radars multi-fonction. Ces contributions portent sur deux aspects : l'ordonnancement des pointages sur l'antenne par méthodes model-based et l'optimisation des pointages de poursuite active par méthodes model-free. Dans un second temps, nous mettons en avant les limites des architectures de gestion de ressources actuelles, ce qui nous amène à envisager une architecture alternative pour laquelle nous proposons de nouveaux algorithmes d'apprentissage par renforcement destinés à répondre aux problèmes qu'elle soulève. Ces contributions portent à la fois sur un aspect multiobjectif, utile dans les radars multi-fonctions pour refléter les compromis à réaliser entre les différentes fonctions, et sur l'aspect combinatoire qui est dû au grand nombre de tâches que le radar doit mener à bien en parallèle. Mots clés : apprentissage par renforcement, radar, ordonnancement, multi-objectif LIP6 Sorbonne Université -Campus Pierre et Marie Curie -4 place Jussieu -75005 Paris -France

  The filter maintains mean estimates of x t : xt is the a priori state estimate given z t-1 and xt is the a posteriori state estimate given z t . From the estimate errors e -

t = x t -xt and e t = x t -x t , we can express the estimate error covariance matrices P - t = exp[e - t e -⊤ t ] and P t = exp[e t e ⊤ t ].

Table 3 .

 3 1: Detailed statistics on three different instance types.

	Algorithm	Avg. cost	Cost std. dev.	Dropped tasks (%)	Optimal solutions (%)	Avg. runtime (milliseconds)	Avg. number of rollouts
		Number of tasks = 25, identical start and due times
	EST	4658.69	634.65	59.06	0.0	1.93	nan
	EST-MCTS	3716.55	506.0	52.15	0.87	1002.88	727.06
	HCLR	3390.6	551.68	48.2	21.35	13.12	nan
	B&B-MCTS	3299.39	526.16	48.44	57.73	975.32	96.12
	MIP-optimal	3268.43	523.85	48.65	100.0	1730.82	nan
		Number of tasks = 50, identical start and due times
	EST	12031.8	857.18	77.64	nan	2.32	nan
	EST-MCTS	10897.03	758.17	73.23	nan	1004.79	587.63
	HCLR	9130.98	799.9	63.62	nan	36.7	nan
	B&B-MCTS	9080.49	780.86	63.79	nan	991.72	30.1
		Number of tasks = 25, distinct start and due times
	HCLR	3301.15	550.93	47.53	22.0	19.98	nan
	B&B-MCTS	3219.61	524.51	47.61	56.5	994.69	70.96
	MIP-optimal	3185.86	520.0	47.88	100.0	2219.44	nan

  , we use GNNs to process factored state representations. To do so, we need to represent the whole factored MDP state as a graph. For a given factored MDP decomposed into n state variables and m rewards, we define a directed graph G with n state nodes (c 1 , ..., c n ), where each state node's attribute consists of the associated state variable s[i] and where an edge c i → c j exists only if i ∈ Z j . This graph, containing only state information, is the input model proposed by

8

  CPU cores; training takes place over 5000 iterations, so the amount of experience is

	Algorithm	N	Score Normalized Time (s)
		5 76.8 ± 0.5	1.01	0.042
		10 58.6 ± 0.5	1.18	0.099
	B-FMODQN	20 42.8 ± 0.4 40 33.5 ± 0.2	1.28 1.34	0.283 0.997
		80 27.0 ± 0.4	1.31	3.021
		160 22.1 ± 0.2	1.20	12.213
		5 76.0 ± 0.5	1.00	0.019
		10 54.3 ± 0.6	1.09	0.025
	SR-DRL	20 38.9 ± 0.4 40 30.0 ± 0.2	1.16 1.20	0.030 0.042
		80 23.6 ± 0.1	1.15	0.069
		160 19.9 ± 0.1	1.08	0.130

Table 4 .

 4 1: Results of evaluation on multi-objective SysAdmin over 1000 runs in the dynamic weights setting for different problem sizes N . Both algorithms were trained on instances of size N = 10. Score is the average cumulative reward with 95% confidence interval. We also normalize the average score against the baseline score. Resolution time per instance in seconds is shown in the last column.

Table 4 .

 4 2: Results of evaluation on multi-objective SysAdmin over 1000 runs in the fixed weights setting for different problem sizes N . N is the problem size used both for training and evaluation. Score is the average cumulative reward with 95% confidence interval.

	The

  Plate Spinning Next we propose a toy environment where we can study the case where the agent must process a set of entities that are wholly independent from each other: in terms of factored MDPs, this is equivalent to the case where the scope of each state variable is limited to that same state variable, i.e. Z i = {i} for all state variable indices i. This type of problem is similar to having to maintain a number of plates spinning on their poles. Let us suppose that the agent can only correct the balance of one plate at a time to keep it spinning, and that the plates have different values, as if some were made of porcelain and others of terracotta. A penalty is inflicted only when a plate loses its balance and crashes on the ground. When many plates are at risk of falling off, the agent should prioritize the most valued ones. The presence of numerous sparse rewards makes this a challenging problem.More formally, we define the problem as consisting of n plates. Each plate i has two features: a balance level b i and a degradation rate d i . There are n available actions, one for each plate. At the beginning of an episode, a plate starts with a balance level of 1; at each time step, this balance level is reduced by d i , unless the agent selects this plate, in which case the balance level is reset to 1. There is one reward per plate: if the balance level of the plate reaches 0, a reward of -1 is given for this plate, and a new plate of same value replaces it with initial balance level 1; otherwise the reward is 0.

représenter un cadre d'application propice pour ce type de techniques. En effet, un radar émet des signaux, appelés pointages, dont l'écho permet de mesurer l'état des objets alentour ; ces pointages varient selon de nombreux paramètres (durée, largeur de faisceau...) et doivent être exécutés séquentiellement. La stratégie de surveillance d'un radar multi-fonctions revient ainsi à sélectionner en continu les pointages à effectuer dans le but de surveiller l'espace environnant tout en pistant les cibles déjà détectées. Les méthodes utilisées actuellement pour répondre à cette problématique sont en grande partie heuristiques et risquent d'être mises en difficulté dans une gamme de situations complexes impliquant des cibles hyper-véloces ou hyper-manoeuvrantes. Dans un premier temps, nous proposons des applications de techniques d'apprentissage par renforcement adaptées à l'architecture courante des radars multi-fonction. Ces contributions portent sur deux aspects : l'ordonnancement des pointages sur l'antenne par méthodes model-based et l'optimisation des pointages de poursuite active par méthodes model-free. Dans un second temps, nous mettons en avant les limites des architectures de gestion de ressources actuelles, ce qui nous amène à envisager une architecture alternative pour laquelle nous proposons de nouveaux algorithmes d'apprentissage par renforcement destinés à répondre aux problèmes qu'elle soulève. Ces contributions portent à la fois sur un aspect multiobjectif, utile dans les radars multi-fonctions pour refléter les compromis à réaliser entre les différentes fonctions, et sur l'aspect combinatoire qui est dû au grand nombre de tâches que le radar doit mener à bien en parallèle.

In the rest of this chapter, we will use the standard terminology for scheduling, where "task" refers to the basic elements of a schedule-in our case, radar dwells. It should not be confused with the radar tasks mentioned earlier.

Similarly, the fixed point for K is K * u , which can be shown be replacing K π , Q π , π by K * u , Q * u , π * u respectively in equation 4.35. This concludes our proof that T (K, Q) is an optimality operator.

Practical algorithm

Based on our optimality operator, we can define an algorithm that learns both Q and K concurrently. This method, which we call K-learning, is outlined below. We write 1 T (s)

for the characteristic function indicating that state s is terminal.

Algorithm 1 K-learning Require: learning rate α, exploration probability ϵ repeat N times Generate a trajectory τ t using an ϵ-greedy policy over u(K)

Q is learned in a very similar way to Q-learning. K, on the other hand, is learned via a two-step process. We first generate a reference trajectory τ t (which is used to learn Q). Then, a second trajectory is generated, that attempts to replicate the reference trajectory by selecting the same actions as it. K is updated based on the rewards received while on the reference trajectory and the Q-value thereafter. If at any step h the new trajectory deviates from the reference, only the rewards up to h are considered. This way we approximate the expectation over H present in the optimality operator.

However, this algorithm has many disadvantages. First, it only applies to discrete and -14.5 on the first and second objectives respectively.

The learning curves for each objective are shown in fig. 4.7. As can be seen on the left, the agent reliably converges to a policy that respects the threshold on the first objective with a mean return of 0.9. On the other hand, the mean return over 10 episodes for the second objective is -15.66, slightly offset from the optimal value -14.5, as the agent will sometimes converge to policy ID instead, whose mean return on the second objective is -19.9.

Overall, we experimentally confirm that K-learning can converge to the optimal deterministic policy in stochastic environments even when the scalarization function is non-linear.

Perspectives and conclusion

Throughout this dissertation, we have explored a variety of perspectives for future multifunction radar resource management techniques through the prism of reinforcement learning.

In chapter 3, we developed practical applications for two components of resource management: task scheduling and active tracking dwell optimization. In our study of radar task scheduling, we built upon previous work that applied Monte Carlo Tree Search (MCTS) to find low-cost schedules. Through a reformulation of the scheduling problem, we highlighted the crucial role of the choice of transition function when modeling the problem as an MDP, and implemented an efficient transition function. The use of this transition function in MCTS required a number of adjustments inspired by branch-andbound algorithms. We tested this MCTS variant as well as a new heuristic allowed by our transition function, and demonstrated improved performance compared to previous approaches: in particular, our algorithms scale better as the size of the scheduling problem increases and uncover lower-cost solutions faster than existing methods, even when these implemented AlphaZero-style learning on top of MCTS.

We see several avenues of improvement on the topic of radar scheduling. In particular, the problem formulation we studied is actually relatively restricted. For example, it doesn't allow for dwell interleaving. During a dwell, the antenna performs an emitting phase and a receiving phase; between these two phases it has to wait for the signal to travel to the target and back. Dwell interleaving takes advantage of this idle phase to schedule the emitting or receiving phase of another dwell in the meantime. This way antenna utilization can be further increased. Another idea is to consider more variable parameters for the dwells. In our dissertation, we only attempted to set the execution time of each dwell, yet the scheduler could also be tasked with dynamically adapting