Offline reinforcement learning for ambulance dispatch

id178087   OFFLINE REINFORCEMENT LEARNING FOR AMBULANCE DISPATCH ENRIC LAMARCA FERRÉS Thesis supervisor: STEPHANROBERT(HEIG-VD) Tutor:MARIOMARTÍNMUÑOZ(DepartmentofComputerScience) Degree:MasterDegreeinArtificialIntelligence Master's thesis School of Engineering Universitat Rovira i Virgili (URV) Faculty of Mathematics Universitat de Barcelona (UB) Barcelona School of Informatics (FIB) Universitat Politècnica de Catalunya (UPC) - BarcelonaTech 19/10/2023 Abstract This master’s thesis is focused on applying offline reinforcement learning techniques to the ambulance dispatch problem, which involves selecting the most appropriate ambulance to dispatch when an incident occurs. The research is part of the SIA-REMU project, conducted both in France and Switzerland. An incident has an associated priority level. Incidents of priority 0 are vital emergencies, incidents of priority 1 are non-vital emergencies, and incidents of priority 2 are non-emergencies. The primary objective of the presented work is to train reinforcement learning agents capable of prioritizing incidents appropriately when dispatching ambulances. Initially, a dataset of experiences was constructed using data provided by the Centre de r´egulation du Centre Hospitalier Universitaire Vaudois (CHUV), which contains valuable information about incidents, interventions, and resources. This dataset of experiences served as a static dataset for training reinforcement learning agents in an offline setting, without interacting with an environment. State-of-the-art offline reinforcement learning algorithms were employed to train the agents, and their hyperparameters were tuned performing a Random Search. To evaluate and test the trained agents, a virtual environment was implemented. Finally, the policies learned by the agents were analyzed to draw meaningful conclusions from the obtained results. 3 Acknowledgements I would like to express my gratitude and appreciation to Professor Stephan Robert, the leader of the research group. I am immensely thankful to F´elicien Hˆeche, a dedicated PhD student, for his assistance and valuable advice. I am also sincerely grateful to Anna Garriga, another student engaged in a different approach for the same project. We shared opinions about our different approaches and gave advice to each other. I would like to express my gratitude and appreciation to Mario Mart´ın for his contributions and support. I am indebted to all the individuals who have contributed to this journey, directly or indirectly, and have played a role in shaping the outcome of this thesis. Finally, I would like to express my gratitude to my family and friends. They were always there when I needed them. 4 Contents 1 Introduction and motivation 8 2 State of the art 9 2.1 Reinforcementlearning........................................ 9 2.1.1 Generic Q-Learning algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Offline reinforcement learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Conservative Q-Learning (CQL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.2 Behaviour Regularized Actor-Critic (BRAC) . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Imitationlearning .......................................... 18 2.3.1 BehaviouralCloning(BC).................................. 18 3 Design of the solution 20 4 Experiences from data 22 4.1 Datasets................................................ 22 4.1.1 Incidentsdata ........................................ 22 4.1.2 Interventionsdata ...................................... 25 4.1.3 Resourcehistories ...................................... 27 4.1.4 Resourcesdata ........................................ 29 4.2 Building experiences from the data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2.1 States ............................................. 30 4.2.2 Actions ............................................ 32 4.2.3 Rewardfunction ....................................... 33 4.2.4 Nextstate........................................... 34 4.3 Analysisoftheexperiences ..................................... 34 5 Agents 36 5.1 BCagent ............................................... 36 5.2 CQLagent .............................................. 36 5.3 BRACagent ............................................. 36 6 Experiments 37 6.1 Environment ............................................. 37 6.2 Training................................................ 38 6.2.1 Random Search for hyperparameter tuning . . . . . . . . . . . . . . . . . . . . . . . . 38 6.2.2 Results ............................................ 40 6.3 Testing ................................................ 44 6.3.1 Results ............................................ 44 7 Conclusions 47 7.1 Futurework.............................................. 47 5 List of Figures 1 Interaction between the agent and the environment. . . . . . . . . . . . . . . . . . . . . . . . 9 2 Reinforcementlearningagent..................................... 12 3 Proposed offline reinforcement learning approach. . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Percentage of rows with missing values for each dataset. . . . . . . . . . . . . . . . . . . . . . 23 5 Preprocessed incidents on the map, left: year 2016, right: year 2019. Red for P0 incidents, orange for P1 incidents and green forP2incidents......................... 25 6 Reward function. Red for P0 incidents, orange for P1 incidents and green for P2 incidents. . 33 7 The batch loss for each training step performed during the training of the best-performing BC agent. ................................................. 41 8 The batch loss for each training step performed during the training of the best-performing CQLagent. .............................................. 41 9 The batch loss (critic) for each training step performed during the training of the bestperformingBRACagent. ...................................... 41 10 The batch loss (actor) for each training step performed during the training of the bestperformingBRACagent. ...................................... 41 11 The mean normalized distance between an incident of P0/P1/P2 and the corresponding dispatched ambulance for each evaluation step performed during the training of the bestperformingBCagent. ........................................ 42 12 The mean normalized distance between an incident of P0/P1/P2 and the corresponding dispatched ambulance for each evaluation step performed during the training of the bestperformingCQLagent. ....................................... 42 13 The mean normalized distance between an incident of P0/P1/P2 and the corresponding dispatched ambulance for each evaluation step performed during the training of the bestperformingBRACagent. ...................................... 43 14 The mean number of utilized ambulances in an episode for each evaluation step performed during the training of the best-performing agents. . . . . . . . . . . . . . . . . . . . . . . . . . 43 15 The mean total reward obtained in an episode for each evaluation step performed during the training of the best-performing agents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 16 The departure locations of the dispatched ambulances for P2 incidents during the test episode oftheGreedyagent. ......................................... 46 17 The departure locations of the dispatched ambulances for P2 incidents during the test episode oftheCQLagent. .......................................... 46 List of Tables 1 AnexampleofaQ-table. ...................................... 13 2 Number of instances and attributes for each dataset. . . . . . . . . . . . . . . . . . . . . . . . 22 3 Percentage of incidents of P0, P1 and P2 for each dataset. . . . . . . . . . . . . . . . . . . . . 23 4 Percentage of missing values for each attribute. No missing values is represented as -. . . . . 24 5 Percentage of preprocessed incidents of P0, P1 and P2. . . . . . . . . . . . . . . . . . . . . . . 24 6 Number of instances and attributes for each dataset. . . . . . . . . . . . . . . . . . . . . . . . 25 7 Number of vehicle instances (ResType = ”Vehicle”) for each dataset. . . . . . . . . . . . . . . 26 8 Number of instances and attributes for each dataset. . . . . . . . . . . . . . . . . . . . . . . . 27 9 Completerecordsexamples...................................... 27 10 Number of instances with the logged action ”Demande d’engagement”. . . . . . . . . . . . . . 28 11 Percentage of instances with missing values. No missing values is represented as -. . . . . . . 28 12 Ambulances that have instances with missing values for each dataset. No ambulances with missing values is represented as -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 13 Number of instances and attributes for each dataset. . . . . . . . . . . . . . . . . . . . . . . . 30 14 Percentage of greedy actions taken for incidents of P0, P1 and P2. . . . . . . . . . . . . . . . 34 15 Percentage of almost greedy actions taken for incidents of P0, P1 and P2. . . . . . . . . . . . 35 16 Testresults............................................... 45 6 List of Algorithms 1 GenericQ-Learning.......................................... 14 2 ConservativeQ-Learning....................................... 16 3 Behaviour Regularized Actor-Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 BehaviouralCloning ......................................... 19 5 Findactionsforeachincident.................................... 32 7 1 Introduction and motivation This master’s thesis was conducted at the Haute Ecole d’Ing´enierie et de Gestion du Canton de Vaud (HEIGVD) in Switzerland, specifically in the Statistical Learning Research Group (Sailing). Its main objective is to apply offline reinforcement learning techniques to the ambulance dispatch problem, which involves selecting the most appropriate ambulance to dispatch when an incident occurs. An incident has an associated priority level. Incidents can be divided into three groups: priority 0 (P0), priority 1 (P1), and priority 2 (P2). P0 incidents are vital emergencies, P1 incidents are non-vital emergencies, and P2 incidents are non-emergencies. When someone calls an Emergency Medical Service, the operator has to decide the priority level of the incident. Then, based on its priority and the state of the available resources, the experts determine the most suitable resource (e.g., ambulance) to dispatch. In recent years, the number of calls to the Emergency Medical Services (144 in Switzerland) has drastically increased, while the number of available resources such as ambulances, medical staff, and helicopters has not increased proportionally. Based on this observation, the Syst`eme d’Intelligence Artificielle pour la R´egulation M´edicale des Urgences (SIA-REMU) [3] project was initiated with two main objectives: 1. To develop new Natural Language Processing (NLP) algorithms that will be used to analyze emergency medical calls. This tool will be capable of extracting keywords, detecting anomalies in the patient’s voice, and performing various other tasks. These new algorithms are expected to assist operators in selecting the priority level of the emergency. 2. To develop new tools for efficiently managing the available resources such as ambulances and helicopters. Given an incident with a known priority level, the objective is to determine the most suitable resource to dispatch. The decision will depend on various factors, including the priority, time, and location of the incident, as well as the positions and availability of the resources. Furthermore, it is crucial to ensure that the available resources are distributed across the territory, avoiding regions without any resources available. Several prior studies with a similar objective have been conducted, including the works [11] and [10]. SIA-REMU is an Interreg project, where the research is conducted both in France and Switzerland. It has been decided that the first objective will be studied at the University of Besan¸con (France), while the second objective will be investigated at HEIG-VD (Switzerland). Therefore, this work is focused on the second objective. Two different problems can be defined: •Resource scheduling: This problem involves selecting the best optimal placement of the resources. The definition of optimal placement can be viewed from various perspectives, such as minimizing response time or maximizing coverage of the region. •Resource dispatching: Meanwhile, this problem involves selecting the most suitable resource(s) to dispatch for a given incident. Both the current state of the available resources and the characteristics of the incident need to be considered in order to determine which resource should be dispatched. This master’s thesis focuses on solving the resource dispatching problem, with the aim of ensuring that the most appropriate ambulance is dispatched to respond to a given incident. It presents an offline reinforcement learning approach to address this problem. In order to achieve the described goal, data from the Centre de r´egulation du Centre Hospitalier Universitaire Vaudois (CHUV) [1] has been provided. This center is responsible for the dispatch and management of the ambulances in the canton de Vaud,canton de Neuchˆatel, and part of the canton de Fribourg, covering the main French-speaking region of Switzerland. The center has an overview of all available ambulances and their locations. When they observe that there are not enough ambulances in a certain region, they request an ambulance to move to another ambulance station to achieve better coverage. The implemented code can be found at: https://github.com/Wenry19/OfflineRL_Ambulance_Dispatch. Please note that the data was not included for confidentiality reasons. 8 2 State of the art This section summarizes the state of the art in reinforcement learning, with a focus on the particular case of offline reinforcement learning. Additionally, it introduces the imitation learning approach. 2.1 Reinforcement learning Reinforcement learning [14] is one of the three main categories of machine learning, which are unsupervised learning, supervised learning, and reinforcement learning. On the one hand, unsupervised learning is used to find patterns or hidden structures in datasets that have not been categorized or labeled. On the other hand, in supervised learning, a model learns from labeled training data to make predictions or decisions. Its objective is to build a model that can generalize and accurately predict the correct output labels for new, unseen data. Unlike the other two learning frameworks, which operate using a static dataset, reinforcement learning operates with data from a dynamic environment. Its goal is not to cluster or label data, but to find the best sequence of actions that will produce the optimal outcome. Reinforcement learning tackles this problem by allowing an agent to explore, interact with, and learn from the environment. The agent is the entity or system that interacts with the environment to learn and make decisions in order to achieve specific goals. The environment refers to the external system or context in which the agent operates and learns. It can be either real or simulated. In a simulated environment, simulations can run faster than real time or be parallelized, accelerating a slow learning process. Additionally, it is easier to model situations that would be difficult to test in reality, and there is no risk of hardware damage. However, sometimes it is necessary to train with the real environment if it is constantly changing or difficult to model accurately. Astate is a specific configuration or snapshot of the environment at a particular time step, which contains all the relevant information needed to make decisions and interact with the environment. It is usually represented as a vector s∈Rn. The state space, denoted as S, is the set of all possible states. This space can be either discrete, with a finite number of possible states, or continuous, with an infinite number of possible states. An action refers to a specific move or decision that the agent can take in the environment at a particular time step. Depending on the problem, actions can be discrete or continuous. Discrete actions are used when the agent has a finite set of possible actions to choose from. A discrete action is usually represented as a natural number a∈N. Continuous actions are used when the agent can choose actions from a continuous range of values. A continuous action is usually represented as a vector a∈Rnor a real number a∈R. The action space, denoted as A, is the set of all possible actions that the agent can take in the environment. When the agent takes a specific action in a certain state, it receives a numerical value, called reward. Rewards serve as feedback to guide the agent’s learning process. High rewards encourage the agent to repeat or reinforce the actions that lead to desirable outcomes, while low rewards discourage undesirable actions. Given a state sand an action a, the reward is obtained from the reward function R(s, a). Figure 1: Interaction between the agent and the environment. Figure 1 illustrates the idea of an interaction between the agent and the environment. The agent observes the current state of the environment and decides which action to take. The environment then updates the 9 Where C(B, ϕ) is the penalization term and αis the penalty weight. Different choices for C(B, ϕ) lead to algorithms with different properties. For instance, CQL with the penalty CCQL0(B, ϕ) = Es∼B,a∼µ(a|s)[Qϕ(s, a)] minimizes the Q-values of all the states in the batch B, for actions selected according to the distribution µ(a|s). If µ(a|s) is chosen adversarially, for example, by maximizing the penalty CCQL0(B, ϕ), the effect is that the conservative penalty will push down on high estimated Q-values. A classical choice for CCQL0(B, ϕ) is Es∼B[log Paexp(Qϕ(s, a))] [8] [9]. The log-sum-exp is a smooth approximation of the maximum function [5]. The intuitive interpretation of that expression is that the log-sum-exp is dominated by the action with the largest Q-value, consequently, CQL with this type of penalty tends to minimize the largest Q-value at each state. If α(in Equation 14) is chosen appropriately, CCQL0(B, ϕ) will push down on Q-values for out-of-distribution actions for which the estimated Q-values are (potentially erroneously) high, while the in-distribution actions will be anchored by L(B, ϕ). To avoid an excessive underestimation of the Q-function, a simple modification, shown in Equation 15, can be done. CCQL1(B, ϕ) = Es∼B,a∼µ(a|s)[Qϕ(s, a)] | {z } minimization term −E(s,a)∼B[Qϕ(s, a)] | {z } maximization term (15) CQL with the penalty CCQL1(B, ϕ) minimizes Q-values under the adversarially chosen µ(a|s) distribution and maximizes the Q-values for state-action pairs in the batch B. Notice that when µ(a|s) is equal to the policy used to collect the experiences in the batch, the penalty is zero on average. The CQL algorithm can be found in Algorithm 2. As mentioned before, the Q-function approximator with parameters ϕis usually a neural network. The parameters ϕare updated with a certain learning rate, denoted as ω, every gradient step. Additionally, soft updates (Equation 13) with the temperature parameter τare applied to slowly update ϕ′(the parameters of the target Q-function approximator). Algorithm 2 Conservative Q-Learning 1: Use dataset D={(si, ai, ri, s′ i)}as the replay buffer. 2: Initialize ϕ0. 3: Initialize ϕ′ 0=ϕ0. 4: Ais the set of actions. 5: for gradient step g∈[0, ..., G −1] do 6: Sample batch B⊂D. 7: CCQL1(B, ϕg) = 1 |B| |B| X i=0 log X a∈A exp Qϕg(si, a)! | {z } minimization term −1 |B| |B| X i=0 Qϕg(si, ai) | {z } maximization term 8: ∼ L(B, ϕg) = αCCQL1(B, ϕg) + 1 |B|P|B| i=0    Qϕg(si, ai)−ri+γmax a′Qϕ′ g(s′ i, a′) | {z } target value     2 9: ϕg+1 ←ϕg−ω∇ϕg ∼ L(B, ϕg) 10: ϕ′ g+1 ←τ∗ϕg+1 + (1 −τ)∗ϕ′ g 11: end for 16 2.2.2 Behaviour Regularized Actor-Critic (BRAC) Behaviour Regularized Actor-Critic [15] [9] or BRAC is an algorithm that aims to maintain the learned policy close to the policy used to collect the experiences in dataset D. This ensures that out-of-distribution actions do not have a significant impact when computing the target value. The policy used to collect the experiences in dataset Dis denoted as πβ(a|s), and it is usually unknown. In fact, it is unknown in our problem. However, approaches such as Behavioural Cloning (Section 2.3.1) can be used to estimate πβ(a|s). The actor with parameters θis usually a neural network which learns a stochastic policy and it is denoted as πθ(a|s). Its objective is to maximize J(θ) defined in Equation 16. J(θ) = Es∼D,a∼πθ(·|s)[Qϕ(s, a)] (16) Where Qϕ(s, a) is the critic with parameters ϕ, usually a neural network, that aims to approximate the Q-function under the actor policy πθ(a|s). Therefore, the objective of the critic is to minimize L(ϕ) defined in Equation 17. L(ϕ) = E(s,a,r,s′)∼D,a′∼πθ(·|s′)h(Qϕ(s, a)−(r+γQϕ′(s′, a′)))2i(17) Where Qϕ′(s, a) is the target Q-function approximator with parameters ϕ′(updated less frequently). A penalty term is added to Equation 16 and Equation 17 to ensure that πθ(·|s) does not deviate excessively from πβ(·|s). The penalty term is the Kullback–Leibler divergence [12] (KL-divergence, denoted as DKL) between πθ(·|s) and πβ(·|s), given a state s. The KL-divergence measures how one probability distribution Pis different from another reference probability distribution Q. It is mathematically defined as: DKL(P||Q) = X x∈X P(x)log P(x) Q(x)(18) As a result, we have: ∼ J(θ) = Es∼DEa∼πθ(·|s)[Qϕ(s, a)] −αDKL(πθ(·|s), πβ(·|s))(19) ∼ L(ϕ) = E(s,a,r,s′)∼D,a′∼πθ(·|s′)    Qϕ(s, a)−(r+γ(Qϕ′(s′, a′)−αDKL(πθ(·|s′), πβ(·|s′)))) | {z } target value    2  (20) The parameter αis the penalty weight. It should be appropriately tuned as we aim to closely align with πβ(a|s) while allowing some room for improvement. The penalty term in ∼ J(θ) ensures that the actor policy does not deviate too much from πβ(a|s). Meanwhile, the penalty term in ∼ L(ϕ) ensures that out-of-distribution actions do not have a significant impact when computing the target value. The BRAC algorithm can be found in Algorithm 3. It is important to observe that two different learning rates, denoted as ωfor the critic and ω′for the actor, are utilized. 17 Algorithm 3 Behaviour Regularized Actor-Critic 1: Use dataset D={(si, ai, ri, s′ i)}as the replay buffer. 2: Initialize ϕ0. 3: Initialize θ0. 4: Ais the set of actions. 5: for iteration k∈[0, ..., K −1] do 6: ## CRITIC ## 7: ϕk,0←ϕk 8: for gradient step g∈[0, ..., G −1] do 9: Sample batch B⊂D,B={(si, ai, ri, s′ i)}. 10: ∼ L(B, ϕk,g) = 1 |B|P|B| i=0       Qϕk,g (si, ai)− ri+γ X a′∈A πθk(a′|s′ i)∗Qϕk(s′ i, a′)−αDKL(πθk(·|s′ i), πβ(·|s′ i))!! | {z } target value       2 11: ϕk,g+1 ←ϕk,g −ω∇ϕk,g ∼ L(B, ϕk,g) 12: end for 13: ϕk+1 ←ϕk,G−1 14: ## ACTOR ## 15: θk,0←θk 16: for gradient step g∈[0, ..., G −1] do 17: Sample batch B⊂D,B={(si, ai, ri, s′ i)}. 18: ∼ J(B, θk,g) = 1 |B|P|B| i=0 Pa∈Aπθk,g (a|si)∗Qϕk+1 (si, a)−αDKL(πθk,g (·|si), πβ(·|si)) 19: θk,g+1 ←θk,g +ω′∇θk,g ∼ J(B, θk,g) 20: end for 21: θk+1 ←θk,G−1 22: end for 2.3 Imitation learning In imitation learning [7], instead of trying to learn from the reward function, an expert (typically a human) provides us with a set of demonstrations (D={(si, ai)}). The simplest form of imitation learning is Behavioural Cloning, which focuses on learning the expert’s policy using supervised learning. 2.3.1 Behavioural Cloning (BC) Behavioural Cloning or BC is the simplest form of imitation learning. The BC algorithm can be found in Algorithm 4. It utilizes state-action pairs extracted from the expert data to predict the probability of taking each action given a state. To accomplish this, a neural network (with parameters θ) is trained. The policy represented by this neural network in the gth gradient step is denoted as πθg. For each training step, a batch Bof state-action pairs (si, ai) is sampled from D. For each state siin B, the ground truth probabilities P(a|si)∀a∈Aare obtained through one-hot encoding of its associated action ai. This assigns a probability of 1 to the expert’s action and a probability of 0 to the other actions. The loss function L(πθg, B) is calculated as shown in Algorithm 4 (line 7). It is the mean squared error between the probabilities estimated by the network and the ground truth probabilities. Following that, the neural network parameters θare updated with a specific learning rate ω, aiming to minimize the loss function. 18 Algorithm 4 Behavioural Cloning 1: Use dataset D={(si, ai)}. 2: Initialize θ0. 3: Ais the set of actions. 4: for gradient step g∈[0, ..., G −1] do 5: Sample a batch Bof state-action pairs (si, ai) from D. 6: One-hot encoding of ai, for each (si, ai) in B(ground truth probabilities P(a|si)∀a∈A). 7: L(πθg, B) = 1 |B|∗|A|P|B| i=0 Pa∈Aπθg(a|si)−P(a|si)2 8: θg+1 ←θg−ω∇θgL(πθg, B) 9: end for 19 3 Design of the solution After these general and theoretical considerations about (offline) reinforcement learning and imitation learning, let us return to our specific problem. The data provided by the CHUV contains information about incidents, interventions, and resources (ambulances). This data can be utilized to build the dataset D= {(st, at, rt+1, st+1)}. Therefore, an offline reinforcement learning approach is considered, where the agents are trained using the static dataset of experiences D, without any interaction with an environment. First of all, it is essential to define the terms state and action for our problem: •Astate corresponds to an incident and contains information about the incident itself, along with information about the ambulances at the time of the incident. •The action involves determining which ambulance should be dispatched to respond to the incident. Thus, every new incident is a new step where the corresponding action (which ambulance is dispatched) has to be determined. The action depends on the state, which contains information about the incident and the ambulances. Figure 3: Proposed offline reinforcement learning approach. Figure 3 summarizes the offline reinforcement learning approach to solve the presented problem. Firstly, the data needs to be cleaned and preprocessed. After that, the states can be estimated. For instance, information such as the location and time of the incident, its priority, the placement of ambulances at that moment, and their availability should be represented in the state. The actions taken by the experts can be determined based on the data (for each state, its corresponding action). These actions must be evaluated using a properly designed reward function to ensure that the agents learn the desired behaviour. With all of this, the dataset of experiences Dcan be constructed. Once the dataset Dis constructed, it can be used to train various reinforcement learning agents in an offline setting. Different state-of-the-art offline reinforcement learning algorithms can be employed to train the agents. These training algorithms have specific hyperparameters that need to be tuned. To evaluate the performance of each agent trained with a particular hyperparameter configuration, a simple environment can be implemented. Furthermore, the best-performing agent for each employed algorithm can be tested in the environment. This allows us to draw conclusions about the different training algorithms in the context of our problem. During the training of an agent, episodes can be executed to gain insights into its learning process. It is important to note that the environment is only used to evaluate and test the trained agents and does not affect the training. This is a must in offline reinforcement learning. 20 In Section 2.2 some problems/challenges of offline reinforcement learning have been presented. Regarding the lack of exploration, it is assumed that Dadequately covers the space of high-reward experiences to make learning feasible. Section 4 explains how the dataset Dis constructed using the provided data. Offline reinforcement learning algorithms (Section 2.2.1 and Section 2.2.2) that aim to address the action distribution shift will be used to train the agents in an offline setting, utilizing the previously constructed dataset D. The implemented environment (Section 6.1), used to test the trained agents, generates states with incidents that were not used during the training phase. As a result, the agents are tested in unseen states to assess their robustness against the state distribution shift. The following sections provide a detailed explanation of the described steps, including how they were handled, the encountered challenges, and the obtained results. 21 4 Experiences from data Data from the years 2014 to 2022 was provided for this project. To achieve our objective, it was necessary to extract experiences from this data that closely reflect reality. The state in an experience should accurately represent the actual state when an expert took the corresponding action. As mentioned earlier, offline reinforcement learning algorithms are highly sensitive to the training dataset, as their learning relies entirely on it. It is crucial to have a substantial number of experiences to cover the state and action spaces as extensively as possible and mitigate potential distributional shifts in state and action distributions. Addressing this issue is essential, as it is one of the primary challenges in offline reinforcement learning. This section is focused on describing the provided datasets and explaining all the preprocessing steps that were undertaken to build the dataset of experiences Dused for training the reinforcement learning agents. 4.1 Datasets For each year, three different datasets were provided: one containing incidents data, another containing interventions data, and a final one with the resource history. Additionally, there is data specifying the set of resources during specific intervals of time (not all years had the same set of resources). 4.1.1 Incidents data The provided datasets include incidents data for each year from 2014 to 2022 (the first and the last years are not complete). There is a dataset for each year. However, in 2021, there was a change in the software used by the dispatch center, impacting the construction of the datasets. Consequently, a portion of the data from 2021 and the data from 2022 are stored in a ”new version” dataset. More specifically, data from 18/06/2014 to 23/03/2022 was provided, and the first incident stored in the ”new version” dataset occurred on 23/08/2021. From now on, I will refer to the datasets with the year of the data they contain, and with V6 for the ”new version” dataset. Dataset Number of instances (rows) Number of attributes (columns) 2014 20839 9 2015 53300 9 2016 54956 9 2017 57998 9 2018 62014 9 2019 66964 9 2020 66406 9 2021 44332 9 V6 48930 9 Table 2: Number of instances and attributes for each dataset. In Table 2, the number of instances and attributes for each dataset are presented. The datasets that do not contain incidents data for the entire year are smaller, as expected. All the datasets have the same attributes: •ccCallcardUid: An identifier also present in the interventions data (used to establish the relationship between incidents and interventions). •Identifier: Another identifier. •LocalTime: The time of the incident (e.g., 6/28/2021 5:23:09 PM). •EventText: A text describing the incident. 22 •Priority: The priority of the incident. As previously explained, the incidents were divided into three priorities: priority 0 (P0), priority 1 (P1), and priority 2 (P2). •PlaceName: The location where the incident occurred (e.g., street name). •StreetNumber: The street number where the incident occurred. •PostalCode: The postal code of the city where the incident occurred. •CityName: The name of the city where the incident occurred. Table 3 presents the percentages of incidents of P0, P1 and P2 for each dataset. It is observed that there are more incidents of P1 compared to incidents of P0 or P2, but the distribution is not significantly imbalanced. Dataset P0 P1 P2 2014 36.45 38.62 24.93 2015 33.37 37.19 29.44 2016 29.54 37.13 33.34 2017 27.02 39.23 33.75 2018 26.88 42.45 30.67 2019 27.33 44.04 28.63 2020 26.08 43.20 30.72 2021 25.10 44.78 30.11 V6 26.88 35.91 37.21 Table 3: Percentage of incidents of P0, P1 and P2 for each dataset. Figure 4: Percentage of rows with missing values for each dataset. The datasets contain missing values. Figure 4 shows a histogram of the percentage of rows with missing values for each dataset. Table 4 presents the percentage of missing values for each attribute. 23 Dataset ccCallcardUid Identifier LocalTime EventText Priority PlaceName StreetNumber PostalCode CityName 2014 - - - - - 7.05 30.07 100 0.36 2015 - 0.0019 - - - 4.72 32.55 100 0.18 2016 - - - 0.0036 0.0036 5.56 31.95 88.52 0.12 2017 - - - 0.0086 0.0086 10.60 24.57 0.16 0.038 2018 - - - - - 10.50 24.51 0.11 0.023 2019 - - - 0.0030 0.0030 13.21 27.21 0.13 0.028 2020 - - - - - 14.31 26.31 0.057 0.044 2021 - - - - - 10.58 27.95 0.027 0.023 V6 - - - - - 9.59 27.48 0.049 0.014 Table 4: Percentage of missing values for each attribute. No missing values is represented as -. The following steps were taken in order to preprocess the incidents data: 1. The incidents with missing values in the Priority attribute were discarded. 2. The priority values of incidents with priorities different from 0 and 1 were set to the value of 2. 3. The Nominatim geocoder with OpenStreetMap data [2] was used to transform the addresses (sometimes partial addresses due to the missing values) to GPS (Global Positioning System) coordinates (latitude, longitude). 4. The incidents with locations outside Switzerland were discarded (possible erroneous locations due to partial addresses). Sometimes, ambulances from Switzerland are dispatched to regions in France due to their proximity to the incidents. 5. The incidents with addresses that the geocoder could not find were discarded. 6. The LocalTime was encoded as an integer to facilitate working with it. Firstly, the time was converted from the AM/PM format to the 24-hour time format. Then, Equation 21 was applied to encode the LocalTime as an integer. encoded time =year ∗1010 +month ∗108+day ∗106+hour ∗104+minute ∗102+second (21) 7. The ccCallcardUid, LocalTime encoded as an integer, Priority, and the obtained coordinates were saved. 8. Once all the incidents were preprocessed, they were concatenated and sorted by time. Additionally, incidents with repeated ccCallcardUid were removed from the data (0.5% of the total number of different ccCallcardUid were repeated in the data, indicating possible erroneous data). It is important to note that only the incidents data from 2016 to 2022 was preprocessed. The primary reason for this is the incomplete resource history data for the years 2014 and 2015, which makes it impossible to obtain an accurate estimation of the resource positions when constructing the experiences. A dataset consisting of 335905 preprocessed incidents was obtained. Table 5 shows the percentage of preprocessed incidents of P0, P1 and P2. The distribution is roughly similar to what was observed in Table 3. Figure 5 illustrates the preprocessed incidents on the map for the years 2016 and 2019. Similar incident maps were obtained for the other years. P0 P1 P2 26.98 42.33 30.70 Table 5: Percentage of preprocessed incidents of P0, P1 and P2. Additionally, the preprocessed incidents data was split into two parts: one for building the dataset of experiences Dto train the agents (the first 285905 incidents), and another for the environment to generate new observations (the last 50000 incidents). 24 Figure 5: Preprocessed incidents on the map, left: year 2016, right: year 2019. Red for P0 incidents, orange for P1 incidents and green for P2 incidents. 4.1.2 Interventions data For each dataset containing incidents, the corresponding dataset of interventions was also provided. The interventions data is necessary to determine which action was taken (which ambulance was dispatched) by the experts in response to an incident. Dataset Number of instances (rows) Number of attributes (columns) 2014 26536 6 2015 78416 6 2016 80219 6 2017 80830 6 2018 82720 6 2019 84114 6 2020 77924 6 2021 51978 6 V6 222138 8 Table 6: Number of instances and attributes for each dataset. In Table 6, the number of instances and attributes for each dataset are presented. It is worth noting that, in this case, the dataset V6 contains additional attributes. Moreover, it can be observed that there are more interventions than incidents. This is due to: •Multiple ambulances were dispatched for some incidents. •The interventions data also includes instances for the actors (people) that were dispatched, not just the vehicles. The attributes are the following ones: •CreationUtc: Creation time of the intervention (the same time as LocalTime of the corresponding incident). 25 not available at the incident time were excluded when determining the minimum and maximum distances for performing the min-max normalization. –The integer indicating the availability of the ambulance was min-max normalized, taking into account the availability values in the same state (excluding the values of the ambulances that were not available at the incident time, in these cases the value -1 was preserved). Therefore, a state consists of a list that contains the specified normalized values. Normalizing these values can lead to faster training, better optimization, and improved generalization performance when feeding the states into a deep neural network to predict the Q-values or the probabilities of the actions. 4.2.2 Actions To determine the corresponding action for each state, the attribute ccCallcardUid (found in the incidents and interventions data) was used, as mentioned earlier. This attribute helped establish the relationship between incidents and interventions. As a result, it became possible to determine which action was taken by the experts for each incident (state). Algorithm 5 Find actions for each incident 1: for incident in incidents data do 2: interventions ←interventions with the same ccCallcardUid as the incident. 3: for intervention in interventions do 4: ambulance ←the ambulance that was dispatched in intervention. 5: if the position and availability of ambulance can be estimated then 6: availability ←estimated availability of ambulance at the time of the incident. 7: if availability == 0 then 8: Set ambulance as an action taken for incident. 9: end if 10: end if 11: end for 12: end for Algorithm 5 outlines the steps taken to determine which ambulances were dispatched for each incident. It is worth noting that only interventions involving ambulances with records in the preprocessed resource histories were considered (line 5). This is because certain ambulances were deleted due to missing values, as explained earlier during the preprocessing of the resource histories. Moreover, incomplete records in the resource histories were removed during the preprocessing phase. It is possible that all records of certain ambulances were incomplete, and consequently eliminated, making it impossible to estimate the positions and availability of these ambulances. Additionally, only interventions involving available ambulances were considered (line 7). There are cases where, for certain incidents, an occupied ambulance was chosen to be dispatched. While it is a possible action to wait until the completion of the current service and then dispatch the ambulance directly to the incident, these actions were not allowed in order to simplify the problem and make the learning process of the implemented agents easier. The ideal scenario during an incident would involve having a nearby available ambulance without any waiting time. Therefore, let’s impose a constraint on the agents to always choose an available ambulance. This will allow us to observe if they can learn to optimize the ambulance dispatch system in a way that ensures the available ambulances are well positioned. It is important to mention that during the process described in Algorithm 5, no impossible actions were found. An impossible action would be to choose an ambulance that was not available at the time of the incident. Recall that a not available ambulance is different from an occupied ambulance. Finally, notice that for each incident, multiple experiences can be obtained, one for each valid associated intervention. In other words, multiple pairs of state-action {(s, a),(s, a′),(s, a′′), ...}can be obtained for each incident (depending on the number of ambulances that were dispatched). 32 4.2.3 Reward function The reward function defines the goal or objective of the agent. It assigns a numerical value or score to an action, indicating its desirability or utility in the current state. Thus, it provides immediate feedback to the agent based on its actions. High rewards encourage the agent to repeat or reinforce the actions that lead to desirable outcomes, while low rewards discourage undesirable actions. In the presented problem, the desired behaviour consists of dispatching the most appropriate ambulance to an incident. Incidents of higher priority (emergencies) must take precedence over those of lower priority. As previously explained, the incidents were divided into three priorities: priority 0 (P0), priority 1 (P1), and priority 2 (P2). P0 incidents are vital emergencies, P1 incidents are non-vital emergencies, and P2 incidents are non-emergencies. The reward function should encourage the agents to optimize ambulance dispatching in a manner that ensures a nearby ambulance is available for prompt response when a high-priority incident occurs. With this aim, the min-max normalized distance of the performed action is used as an indicator of the dispatched ambulance’s proximity to the incident. It is important to note that distances of ambulances that were not available were excluded when determining the minimum and maximum distances for the minmax normalization. This ensures that distances associated with impossible actions do not impact the normalization process. However, the distances of occupied ambulances were considered, as they could be dispatched before becoming occupied attending another incidents. As previously explained, the estimated position of an ambulance that was occupied attending to an incident is from where it departed to respond to that incident. This provides insights to the agent regarding alternative actions it could have taken (from where the occupied ambulances would have been dispatched if they were not being used). norm dist reward 1 -10 1 -1 Figure 6: Reward function. Red for P0 incidents, orange for P1 incidents and green for P2 incidents. Furthermore, a penalty that depends on the priority of the incident is applied. Equation 22 presents the different reward functions that are employed depending on the priority of the incident. In this equation, norm dist(s, a) is the min-max normalized distance between the ambulance that is represented with action aand the incident. R(s, a) =      11 ∗(1 −norm dist(s, a)) −10,if P0 incident 2∗(1 −norm dist(s, a)) −1,if P1 incident 1−norm dist(s, a),if P2 incident (22) Figure 6 illustrates the different reward functions presented in Equation 22. For the three priorities, the 33 immediate reward decreases as the normalized distance increases, the difference lies in the slope of the functions. For instance, for P0 incidents, the rate at which the reward decreases is much higher than for P1 or P2 incidents. It can be observed that the maximum immediate reward, which corresponds to sending the nearest ambulance to an incident (norm dist = 0), is 1. Depending on the priority of the incident, the minimum immediate reward, which corresponds to sending the farthest ambulance to an incident (norm dist = 1), can be -10 for P0 incidents, -1 for P1 incidents, and 0 for P2 incidents. Therefore, the distance between the ambulance and the incident is penalized to a greater extent for P0 incidents compared to P1 and P2 incidents. Additionally, the distance is more penalized for P1 incidents compared to P2 incidents. In this way, it is expected that the reward function will guide the agent towards the desired behaviour by prioritizing incidents in the order of P0, P1, and P2. 4.2.4 Next state The next state of an experience is the state that represents the next incident. In some cases, it is possible that the next state does not have the ambulance dispatched in the current state occupied. This happens because ambulances were selected at incident time, but they were demanded at a later time, depending on the priority of the incident. As a result, the record for the ambulance’s departure in the resource history was introduced at a later time. If the next incident occurred before the record was introduced in the resource history, the estimated state of the next incident contains the ambulance as available, instead of occupied. It is possible that an ambulance selected for a low-priority (P2) incident was dispatched hours later, being utilized for other incidents of higher priority (P0 or P1) in the meantime. It is impossible to know because there is not an exact way to establish a direct connection between interventions and records in the resource histories. It is important to mention that the next state obtained when performing an action in the environment always contains the dispatched ambulance as occupied. This is explained in more detail in Section 6.1. 4.3 Analysis of the experiences After all, 335764 experiences (st, at, rt+1, st+1) were obtained from the 285905 preprocessed incidents intended for training. Recall that the 335905 preprocessed incidents were split into two parts: one for building the dataset of experiences Dto train the agents (the first 285905 incidents), and another for the environment to generate new observations (the last 50000 incidents). However, the dataset Donly contains 232084 different incidents. This is because certain incidents were discarded during the process of finding their corresponding interventions, as explained in Section 4.2.2. There are two reasons for discarding an incident: •All the interventions of the incident involved ambulances that were not included in the preprocessed resource histories. Therefore, it was not possible to estimate their location and availability. •All the interventions of the incident involved ambulances that were occupied at the time of the incident. The number of ambulances with a estimable position and availability is 258. Therefore, this is the total number of different actions that can be taken. The state size, which includes all the normalized values mentioned in Section 4.2.1, is 1041. The average number of dispatched ambulances per incident in the constructed dataset Dis 1.45. Additionally, the degree of greediness of the actions in the experiences was studied. In each state, the greedy action involves sending the closest available ambulance to the incident. However, this may not be the optimal policy as it does not consider the proper distribution of available ambulances or the priorities of the incidents. P0 P1 P2 12.17 12.13 7.80 Table 14: Percentage of greedy actions taken for incidents of P0, P1 and P2. Table 14 presents the percentages of greedy actions taken for P0, P1, and P2 incidents. It can be observed that P0 incidents have a higher percentage of greedy actions compared to P1 incidents, and P1 incidents 34 have a higher percentage of greedy actions than P2 incidents. This makes sense considering that P0 incidents are prioritized over P1 incidents, and P1 incidents are prioritized over P2 incidents. Therefore, it is expected that P0 incidents have a larger proportion of greedy actions (the closest available ambulance was sent to the incident, which was a vital emergency) than the other incidents, while P2 incidents have the lowest proportion of greedy actions since they were not emergencies. Despite this, the percentages of greedy actions are quite low. Thus, it was decided to check the percentage of almost greedy actions. An almost greedy action is when the distance between the incident and the dispatched ambulance is at most 2 km greater than the distance between the incident and the closest available ambulance to the incident. P0 P1 P2 65.53 73.01 47.41 Table 15: Percentage of almost greedy actions taken for incidents of P0, P1 and P2. Table 15 presents the percentages of almost greedy actions taken for P0, P1, and P2 incidents. These percentages are higher than those presented in Table 14. However, P1 incidents have a higher percentage of almost greedy actions compared to P0 incidents. This outcome was unexpected and suggests that better actions could have been taken in the estimated states of the constructed dataset D. Moreover, the mean immediate reward was calculated to gain an understanding of the effectiveness of the actions in Dbased on the reward function. A value of 0.91 was obtained, which is good, considering that the maximum immediate reward is 1, as specified in Section 4.2.3. 35 5 Agents Three different algorithms were employed to train agents in an offline setting using the constructed dataset D. This section provides implementation details of the training algorithms that were implemented, which are BC (Section 2.3.1), CQL (Section 2.2.1), and BRAC (Section 2.2.2). Additionally, this section specifies how the trained agents choose the action to perform in a given state during test time. Please refer to Section 6.2.1 for more details about the hyperparameters of each training algorithm. 5.1 BC agent A BC agent is an agent trained with the BC algorithm (Algorithm 4). The implemented algorithm trains a neural network with parameters θ. Its input size is equal to the state size, and its output size is equal to the number of different actions. The softmax activation function is used in the output layer because it allows us to obtain a probability value for each action. It is important to mention that during test time, given a state, the estimated probabilities of impossible actions (actions that involve dispatching an unavailable or occupied ambulance) are set to 0, and the remaining probabilities are renormalized. The action taken by the agent in the given state is sampled from the resulting probability distribution. 5.2 CQL agent A CQL agent is an agent trained with the CQL algorithm (Algorithm 2). The implemented Q-function approximator is a neural network with parameters ϕ. Its input size is equal to the state size, and its output size is equal to the number of different actions. The linear activation function is used in the output layer to obtain the estimated Q-value for each action. It is important to mention that when computing the target value (line 8 of Algorithm 2), only possible actions in s′ iare considered to determine the action a′that has the maximum estimated Q-value. During test time, given a state, the selected action is the possible action with the highest estimated Q-value in that state. 5.3 BRAC agent A BRAC agent is an agent trained with the BRAC algorithm (Algorithm 3). The implemented critic is a neural network with parameters ϕ, and the implemented actor is a neural network with parameters θ. Both networks with the input size equal to the state size, and the output size equal to the number of different actions. On the one hand, the linear activation function is used in the output layer of the critic to obtain the estimated Q-value for each action. On the other hand, the softmax activation function is used in the output layer of the actor to obtain a probability value for each action. It is important to mention that when computing the expected Q-value as Pa∈Aπθ(a|s)·Qϕ(s, a) for a given state s(line 10 and line 18 in Algorithm 3), the impossible actions are not considered. More concretely, the probability πθ(a|s) is set to 0 for all impossible actions, and the remaining probabilities are renormalized. During test time, only the actor is required to decide which action is selected in a given state s. The actor outputs the probability of taking each action. The probabilities of impossible actions in sare set to 0, and the remaining probabilities are renormalized. The action taken by the agent in the given state sis sampled from the resulting probability distribution. 36 6 Experiments The objective of this section is to describe the experiments that were conducted. It provides details about the training and testing of the agents. Firstly, an environment was implemented to evaluate and test the agents. Then, the agents were trained in an offline setting using the training algorithms presented in Section 2.2 and Section 2.3. The hyperparameters of these algorithms were tuned by performing a Random Search, where multiple combinations of hyperparameter values were used to train the agents, keeping the best-performing ones. After that, during the test phase, the learned policies of the best-performing agents were studied. 6.1 Environment A custom gym [6] environment was implemented to evaluate and test the agents. The environment is capable of executing episodes with a certain number of steps (incidents). It utilizes the last 50000 incidents from the preprocessed incidents data (Section 4.1.1), which were not used to train the agents. Recall that the incidents in the preprocessed incidents data are sorted by time. The environment operates as follows: 1. Reset of the environment: •An incident iis randomly selected. •All the available ambulances at the time of incident iare set as not occupied. The ambulances that were not available at the time of incident iare set as unavailable. •The position of each ambulance is sampled from its departure positions in the preprocessed resource histories. •With all this information, the environment constructs the initial state. 2. Performing a step in the environment: •The environment receives action a, representing an available ambulance to dispatch to the current incident i. •It marks the ambulance represented by action aas occupied for a certain amount of time. This time was estimated using the preprocessed resource histories: the mean time an ambulance is occupied when dispatched is 3546 seconds (almost an hour). •It computes the immediate reward rof applying action ain the current state s. •It gets the next incident i′. •It updates the availability information of the ambulances at the time of incident i′. If some occupied ambulance becomes available again, a new position is sampled from its departure positions in the preprocessed resource histories. •With this information, the new state s′and the immediate reward rcan be returned. •It checks if the current episode is terminated. An episode is considered to be terminated when the maximum number of steps in an episode have been reached. If it is the case, the episode will be terminated. The environment is used to evaluate the agents during the training phase and to test the trained agents during the test phase. 37 6.2 Training As previously mentioned, three different training algorithms were implemented: BC (Section 2.3.1), CQL (Section 2.2.1), and BRAC (Section 2.2.2). For each training algorithm, multiple agents with different hyperparameter configurations were trained to determine the best-performing ones, which are those achieving the highest rewards. However, general hyperparameters were fixed for all the different training executions: •num configs = 10: For each algorithm, the number of different hyperparameter configurations to try. •max train steps = 5000: The maximum number of training steps (gradient steps) during a training execution. •episode length = 100: The number of steps performed in one episode. •num train steps eval = 25: The number of training steps to perform before an evaluation step. In other words, after every num train steps eval training steps, an evaluation step is performed. This is only used in BC and CQL. For BRAC, an evaluation step is performed after every iteration since one iteration involves multiple gradient steps (Algorithm 3). •num eval episodes = 3: The number of episodes that are executed to perform an evaluation step. •num episodes save model = 20: The number of episodes that are executed to decide whether the trained model/s (neural network/s) is/are saved or not. The total reward obtained in an episode is the sum of all the obtained immediate rewards during the episode. The mean total reward obtained in an episode is calculated using the total rewards obtained in num episodes save model episodes. •threshold save model = 0.8: Notice that the maximum immediate reward that can be obtained is 1 (Section 4.2.3). Consequently, the maximum total reward that can be obtained in an episode is episode length. If the trained agent achieves a mean total reward (calculated using the total rewards obtained in num episodes save model episodes) greater than threshold save model ∗episode length, its model/s is/are saved. An evaluation step consists of executing num eval episodes episodes to calculate: •The mean total reward obtained in an episode. •The mean number of different ambulances used in an episode. •The mean normalized distance between an incident of P0 and the corresponding dispatched ambulance. •The mean normalized distance between an incident of P1 and the corresponding dispatched ambulance. •The mean normalized distance between an incident of P2 and the corresponding dispatched ambulance. 6.2.1 Random Search for hyperparameter tuning Grid Search and Random Search [4] are two common techniques used for hyperparameter tuning. Both methods aim to find the best combination of hyperparameters that optimize the performance of a given model. On the one hand, Grid Search involves defining a search space as a grid of hyperparameter values and exhaustively evaluate every position in the grid. On the other hand, Random Search involves defining a search space as a bounded domain of hyperparameter values and randomly sample points in that domain. Grid Search ensures an exhaustive exploration of all possible combinations of hyperparameter values within the defined grid. However, it can be computationally expensive since it spends a lot of time evaluating unpromising regions of the search space. In contrast, Random Search explores the search space more effectively, finding a good hyperparameter combination in significantly fewer iterations. Therefore, the Random Search was chosen to perform the hyperparameter tuning of the training algorithms. 38 A bounded domain of hyperparameter values was defined as the search space for each algorithm. Architectures 0, 1, and 2 (represented by the hyperparameter net/net′) refer to different neural network architectures which will be presented later. The search space for BC was defined as: •ω(learning rate): [0.0001,0.0003,0.0005,0.0007]. •bs (batch size): [128,256,512,1024]. •net (architecture of the network): [0,1,2]. The search space for CQL was defined as: •ω(learning rate): [0.0001,0.0003,0.0005,0.0007]. •bs (batch size): [128,256,512,1024]. •γ(discounting factor): [0.9,0.95]. •τ(temperature parameter for soft updates): [0.01]. •α(penalty weight): [0.1,0.3,0.5,0.7,0.9]. •net (architecture of the network): [0,1,2]. The search space for BRAC was defined as: •ω(learning rate critic): [0.0001,0.0003,0.0005,0.0007]. •ω′(learning rate actor): [0.0001,0.0002,0.0003]. •bs (batch size critic): [128,256,512,1024]. •bs′(batch size actor): [128,256,512,1024]. •G(number of gradient steps): [25,50,100]. •γ(discounting factor): [0.9,0.95]. •α(penalty weight): [0.1,0.3,0.5,0.7,0.9]. •net (architecture of the critic network): [0,1,2]. •net′(architecture of the actor network): [0,1,2]. The different neural network architectures (represented by the hyperparameter net/net′): •Architecture 0: –Input layer: input size equal to the state size (1041). –Dense layer 1: 512 units and ReLU as activation function. –Dense layer 2: 512 units and ReLU as activation function. –Dense layer 3: 1024 units and ReLU as activation function. –Dense layer (output): output size equal to the action space (258). Softmax activation function for BC and the actor in BRAC. Linear activation function for CQL and the critic in BRAC. •Architecture 1: –Input layer: input size equal to the state size (1041). –Dense layer 1: 1024 units and ReLU as activation function. –Dense layer 2: 2048 units and ReLU as activation function. –Dense layer 3: 1024 units and ReLU as activation function. 39 –Dense layer 4: 512 units and ReLU as activation function. –Dense layer (output): output size equal to the action space (258). Softmax activation function for BC and the actor in BRAC. Linear activation function for CQL and the critic in BRAC. •Architecture 2: –Input layer: input size equal to the state size (1041). –Dense layer 1: 1024 units and ReLU as activation function. –Dense layer 2: 2048 units and ReLU as activation function. –Dense layer 3: 4096 units and ReLU as activation function. –Dense layer 4: 1024 units and ReLU as activation function. –Dense layer (output): output size equal to the action space (258). Softmax activation function for BC and the actor in BRAC. Linear activation function for CQL and the critic in BRAC. 6.2.2 Results The results of the training phase are presented in this section. As mentioned earlier: •For each training algorithm, 10 agents with different hyperparameter configurations were trained. •Each training execution consisted of 5000 training steps. •In the case of BC and CQL, an evaluation step was performed after every 25 training steps. In the case of BRAC, an evaluation step was performed after every complete iteration. The presented results include plots of the values obtained in each evaluation step. Additionally, they include plots of the batch loss obtained in each training step. The batch loss is computed as line 7 of Algorithm 4 for BC, line 8 of Algorithm 2 for CQL, and for BRAC: •Critic: Line 10 of Algorithm 3. •Actor: For implementation reasons, to maximize the value of ∼ J(B, θk,g) (line 18 of Algorithm 3), it is minimized the value of −∼ J(B, θk,g), which can be seen as a loss. For each training algorithm, the best-performing agent, which is the one achieving the highest mean total reward obtained in an episode, was selected. The best-performing BC agent was trained with the following hyperparameter configuration: ω= 0.0007, bs = 1024, net = 2. The best-performing CQL agent was trained with the following hyperparameter configuration: ω= 0.0001, bs = 256, γ= 0.95, τ= 0.01, α= 0.9, net = 0. The best-performing BRAC agent was trained with the following hyperparameter configuration: ω= 0.0005, ω′= 0.0003, bs = 1024, bs′= 1024, G= 100, γ= 0.95, α= 0.5, net = 1, net′= 0. The policy of the best-performing BC agent was used as an estimation of πβ(a|s). The following results are those obtained during the training of the best-performing agents. 40 Figure 7: The batch loss for each training step performed during the training of the best-performing BC agent. Figure 8: The batch loss for each training step performed during the training of the best-performing CQL agent. Figure 9: The batch loss (critic) for each training step performed during the training of the best-performing BRAC agent. Figure 10: The batch loss (actor) for each training step performed during the training of the bestperforming BRAC agent. Figure 7, 8, 9, and 10 show the batch loss evolution during the training of the agents. In all cases, the loss tends to decrease. Figure 11 shows that, during the training of the BC agent, the mean normalized distance between an incident of P0 and the corresponding dispatched ambulance is similar to that obtained for incidents of P1. However, the mean normalized distance between an incident of P2 and the corresponding dispatched ambulance is higher. This gives insights that the agent tries to prioritize P0 and P1 incidents over P2 incidents. This was expected given the obtained results in Section 4.3, where we saw that the policy used to collect the experiences in dataset Dprioritize P0 and P1 incidents over P2 incidents. 41 based on the solutions of similar past problems (which ambulances were dispatched to similar past incidents). It can be described as a four-step process: 1. Retrieve: Given a target problem (incident), retrieve cases relevant to solving it from a dataset. A case consists of a problem (incident) and its solution (dispatched ambulance). 2. Reuse: Map the solutions from the previous cases to the target problem. This may involve adapting the solution as needed to fit the new situation. 3. Revise: Test the new solution in the real world (or a simulation) and, if necessary, revise. 4. Retain: After the solution has been successfully adapted to the target problem, store the resulting experience as a new case in the dataset. 48 References [1] Centre hospitalier universitaire vaudois. https://www.chuv.ch/fr/chuv-home. [2] Nominatim, open-source geocoding with openstreetmap data. https://nominatim.org/. [3] Syst`eme d’intelligence artificielle pour la regulation m´edicale des urgences. https://www. interreg-francesuisse.eu/beneficiaire/sia-remu/. [4] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. J. Mach. Learn. Res., 13:281–305, feb 2012. [5] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. [6] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. [7] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Comput. Surv., 50(2), apr 2017. [8] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning, 2020. [9] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems, 2020. [10] Cheng Siong Lim, Rosbi Mamat, and Thomas Braunl. Impact of ambulance dispatch policies on performance of emergency medical services. Intelligent Transportation Systems, IEEE Transactions on, 12:624 – 632, 07 2011. [11] Kunpeng Liu, Xiaolin Li, Cliff Zou, Haibo Huang, and Yanjie Fu. Ambulance dispatch via deep reinforcement learning. pages 123–126, 11 2020. [12] David JC MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003. [13] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013. [14] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. [15] Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning, 2019. 49