Cooperative Policy Learning with Pre-trained Heterogeneous Observation Representations

As aforementioned, the vertices heterogeneity together with the intricate interactions between them prevents vanilla GNN to effectively learn the informative representations from the complex interaction graph. The EncGAT model is designed to solve these problems.

The encoder-decoder based attention procedure is shown in the figure 2. For vertex (agent) $v_{i}\in\mathcal{V^{*}}$ with feature vector $x_{i}$, its neighbor set with type $d$ is denoted as $\mathcal{N}_{d}(v_{i})$ and the corresponding feature matrix is $\mathbf{x}_{i}^{d}$. The calculation procedure of the encoder is based on self-attention, which is similar to the transformer block and shown below:

where Att is the scaled dot product attention which is the same as that in Transformer Vaswani et al. (2017), $W^{\mathcal{Q}}_{ec}$,$W^{\mathcal{K}}_{ec}$ and $W^{\mathcal{V}}_{ec}$ are the projection matrices of query, key and value in the attention function, $W_{1}$ and $W_{2}$ are the square matrices of the linear layers, $b_{1}$ and $b_{2}$ are the bias parameters, LN is the layer norm and ReLU is the ReLU activation function. The final embedding $o_{i}^{d}$ is already transformed into the same vector space with $x_{i}$ in case that $v_{i}$ is not of type $d$. We the whole encoder process as the function Enc. Through the function Enc, the feature of each neighboring vertex of $v_{i}$ is represented by considering other neighbors’ information in the Att function.

The aggregation among the same type of neighbors is conducted through the decoder attention as is shown in the left part of the figure 2. In decoder attention, another scaled dot product attention is applied, which uses the feature vector of $v_{i}$, i.e. $x_{i}$, as the query, and the encoded neighbors’ features matrix $\mathbf{o_{i}^{d}}$ as the keys and values. To align the dimension, the feature vector $x_{i}$ is first expanded as a matrix $\mathbf{x_{i}}$. The mathematical description is shown as follows:

where $W^{\mathcal{Q}}_{dc}$, $W^{\mathcal{Q}}_{dc}$ and $W^{\mathcal{Q}}_{dc}$ are the projection matrices of query, key and value in the attention function, $W_{3}$ and $W_{4}$ are the square matrices of linear layers and $b_{3}$ and $b_{4}$ are the bias parameters. Then we squeeze the expanded dimension of $\mathbf{h}_{i}$ into the vector $h_{i}$

Finally, as the neighbors of vertex $v_{i}$ may have different types, we simply concatenate all the output $h_{i}^{d}$ as the final feature of vertex $v_{i}$. The expression is as $h_{i}=\left\|{\left\{h_{i}^{d}|d\in\dot{\mathcal{N}}_{\psi}\left(v_{i}\right)\right\}}.\right.$

A crucial challenge of training the EncGAT lies in that a direct optimization towards the global reward may lead to insufficient observation understanding, which will slow down the convergence and even erode the performance of the learned cooperative policy. In this paper, we manage to address this problem by proposing the pre-training with the local actor-critic (PreLAC) algorithm.

In the local actor-critic task, each agent is trained to maximize its own interest, that is the discounted sum of its local reward $\left\{r^{\textsc{loc}}_{i,t}\,|\,1\leq i\leq|\mathcal{V}^{*}|\right\}$, where $t$ is the time-step. It encourages each agent to learn the concrete business logic about how the local reward is generated and how the neighborhood interactions affect the reward generation.

As is shown in figure 1, the EncGAT network is used as a shared embedding module for the actor and critic networks in the pre-training task. It receives the vertex-level training signals from the local actor and local critic headers. The Formula (3) shows the training loss in this stage.

where $r_{i,t}^{\textsc{loc}}$ denotes the local reward of agent $v_{i}$ at time step $t$, while $k$ refers to the interval from current state to the next state, following the Semi-POMDP setting in Section 3; $V^{\pi_{i}}(\cdot)$ is the local value function under the local policy $\pi_{i}$ of $v_{i}$; $A_{i,t}^{\textsc{loc}}$ is the action of agent $v_{i}$; and the hyper-parameter $\lambda_{l}^{\textsc{loc}}$ is the weight of the critic loss. As we can see, the policy loss $\phi_{i,t}^{\textsc{loc}}$ and the critic loss $\delta_{i,t}^{\textsc{loc}}$ are computed based on the advantage function $\hat{A}_{i,t}^{\textsc{loc}}$ derived from the local critic. The training follows the vanilla Actor-Critic algorithm, thus the $\hat{A}_{i,t}^{\textsc{loc}}$ in the third formula are detached in back-propagation and hence will not affect the update of the critic headers.

In the fine-tuning stage, we reinitialize the local actor headers for each agent and create a new global critic header, while the parameters of EncGAT and local critic headers are inherited from the pre-trained part. Different from the pre-training, the global reward $r_{t}$ is used as a training signal for the local actors’ network (including the shared EncGAT and actor header of each agent) and the global critic network, which encourages cooperation towards the global goal. Meanwhile, to prevent the training collapse and avoid the interference of random initialed parameters, we keep using the local critic loss in this stage to supervising the update of the shared EncGAT part with the agent-level local loss derived from local critics. Therefore, the loss function can be formally defined as the linear combination of three parts: the local critic loss $\delta_{t}^{\textsc{loc}}$, the global critic loss $\delta_{t}$ and the actor loss $\phi_{t}$. That is

where $r_{t}$ denotes the global reward, $\hat{A}_{t}$ represents the global state advantage, $V^{\boldsymbol{\pi}}$ is the global value function under the joint policy $\boldsymbol{\pi}$ and the hyper-parameter $\lambda_{l}$ and $\lambda_{g}$ are the weights of the local critic loss and the global critic loss. Similar to the pre-training stage, the gradient of the advantage $\hat{A}_{t}$ is detached in the training and will not affect the update of the global critic header.

The whole EncGAT-PreLAC framework can be summarized as Algorithm 1. For simplicity of description, we assume all agents belong to the same type while other vertices in the interaction graph can be heterogeneous in the algorithm. Meanwhile, the actor header and critic header are shared among all agents, which can be overwritten according to actual demand. In addition, our framework supports both the synchronous and asynchronous decision of agents, thus we denote $\mathcal{V}^{*}_{t}$ as the set of actionable agents at the time step $t$ in both the pre-training and the training procedure.

Empty containers are the core resource used to load goods in ocean transportation. The serious imbalance of import and export among countries and regions all around the world results in extreme imbalance of supply and demand (SnD) for empty containers. With reposition operation, some ports will stack large amount of containers with high storage cost while some other ports have no containers to satisfy customers’ shipping requirements. Obviously, both cases will cause serious losses for the shipping companies and hinder the global trade. Empty container repositioning is to leverage the remaining capacity in vessels to explicitly transfer empty containers between deficit ports and surplus ports. Each vessel sails around a route and the travel time is influenced by unpredictable factors such as weather and ocean current. When a vessel arrives at a port, it first loads and discharges cargoes, and then triggers the repositioning action of the port to load to or discharge from the vessel a certain amount of empty containers.

We model the ECR problem as a MAS as follows. We assign an agent to each port to manage the containers. When a vessel arrives at the port, the corresponding agent is triggered to make a repositioning decision, which is in fact an event-driven reinforcement learning Menda et al. (2019); Li et al. (2019b). The repositioning action space is $\{0,1,\cdots,21\}$ where action 0 means discharging all empty containers on the vessel and action 21 means loading all empty containers of the port on board. Other actions are evenly distributed with a step of 10 percent. The observation of an agent is its own information and that of related ports and vessels. The optimization goal is to minimize the total shortage of empty containers to fulfill the transportation needs because of the SnD imbalance among ports, which is, on the contrary, to maximize the amount of the fulfilled demand. Therefore, we define the global reward as a homogeneous linear function of the number of empty containers used to fulfill transportation orders at a certain time period, that is $r_{t}=k\cdot\sum_{i}^{n}{a_{i,t}}$, where $k$ is a positive scale factor, $n$ is the number of ports and $a_{i,t}$ is the quantity of consumed containers in port $v_{i}$ at the time period $t$. At the same time, the most straightforward definition of the local reward for the port $v_{i}$ is the value $k\cdot a_{i,t}$.

To realize the efficient repositioning, the agents should have the ability to extract useful information from the observation on the heterogeneous interaction graph. As the interactions happen when a vessel arrives at a port, the arrival time of the vessels from different routes plays an important role in decision making. For example, suppose there are two routes, the first one is in lack of containers and the second is rich in containers, namely the demand route and supply route. Two vessels from these routes will arrive at a port in particular time steps. Obviously, whether the vessel in the demand route arrives first or second will substantially affect the optimal repositioning decision of this port, e.g, reserving containers for the incoming vessel or using them out. Such a relative order of two vessels actually poses the requirements for our model to learn the complicate interactions among neighbors, which the vanilla pooling functions like averaging and maximizing will fail to capture as we state in Section 1. Another necessary feature for the agents is the cooperation between agents based on agents’ comprehensive understanding of the observations. A common phenomenon is that the demand routes and supply routes are not necessarily connected and agents should learn to play as brokers to conduct the multi-hop repositioning.

To build the simulator for the ECR problem, we employ the public routes of an international transportation company, including 22 ports located in main trading countries, 13 routes connecting these ports, and 46 vessels sailing on the routes. The concrete settings of the route topology are attached in the supplementary material. The shipment data between any two ports is generated based on the inter-country trading statistics released by WTO in 2019. Because only the yearly statistics are available while the temporal resolution of the simulation is daily, we distribute the total transportation amount into each time-step by two alternative rules. The first is the simple average, the game setting of which is called ‘normal’ and the second is to distribute the amount by a trend function, which is the multiplication of two trigonometric functions with different periods, i.e., 112 time-steps and 28 time-steps, the game setting of which is called ‘hard’. The transportation time between two ports is computed by their sea distance. At last, noises are added in both transportation time and trading amount to include the environmental uncertainty in each episode.

In the ECR problem, there are two kinds of vertices in the interaction graph, ports and vessels denoted as $\left\{\boldsymbol{v}_{i}^{p}\right\}$ and $\left\{\boldsymbol{v}_{j}^{s}\right\}$ respectively. We establish edges from one port to other ports and vessels in the same route, which represents the transportation interactions. For the port, the input features include the quantities of the empty containers, the reserved empty containers, the laden, the laden on board, transportation orders, the capacity, and the remaining space. The statistical information is also included such as the quantities of the total orders, the fulfilled orders, the failed orders, and their accumulated values in the past 5 time-steps. The input features of the vessel are 7 variables which are the quantities of the empty containers, the laden, the capacity, the remaining space, the accumulated quantities of empty containers, laden, and their difference. As each agent has to learn to predict trend of the inventory and plan for the future, it can hardly determine the strategy with only the input of the current information. Therefore, we let each agent look back a period. We denote the input features of each vertex over the time period $\left[t-n:t\right]$ as $\boldsymbol{x}_{i,\left[t-n:t\right]}$.

The network structure is shown in Figure 6. It follows the general design of the proposed framework, but we add three features based on the characteristics of the ECR problem. The first one is the temporal attention, which is used to capture the temporal information of the temporally sequential input, is added before the EncGAT module. For example for vertex $v_{i}$, the temporal embedding is computed as follows:

where $W_{s}^{\mathcal{Q}}$, $W_{s}^{\mathcal{K}}$ and $W_{s}^{\mathcal{V}}$ are the projection matrices for the query, key and value respectively. In the experiment, the lookback period $n$ is set to 20. The second one is that to consider the edge feature like the arriving time and the distance, we concatenate it with the features of the corresponding neighbor before feeding it to EncGAT. The third one is that the representations of both the port and the current vessel are fed into the actor header since the vessel situation is important for decision making.

Finally, we stack two encoder-decoder attentions in the EncGAT and residual connections are used to prevent over-smoothing. The actor and critic headers consist of two fully-connected layers also with residual connections. We share the headers of actor and local critic between agents, which makes the overall framework inductive (Hamilton et al., 2017). Empirical studies show the generality of policy with the parameter sharing, which is illustrated in the supplemental file.

In this section, we compare our framework with existing baseline methods with the total fulfillment ratio, that is the ratio of fulfilled demands to all demands, as the evaluation metric. To keep fairness, we search the learning rate for all deep learning algorithms and fix other hyper-parameters. We run 5 times for each one with the best learning rate. The results are shown in Table 1. It should be pointed out that since most of the ports play the roles of exporter and importer at the same time, the total ratio is around 80 percent if no repositioning is done.

Online linear programming (LP). In this method, the ECR problem is modeled as an integer linear programming (ILP) problem with mathematical definitions. Here, we use the baseline method in (Li et al., 2019b), which applies the rolling horizon policy to do periodic planning. It solves the ILP problem for a long period and only takes the first few plans into action, which prevents the deviation of planning from reality. The planning results are largely influenced by the unpredictable noise in the environment, which is the reason why it underperforms our method. Besides, the online computational cost of searching ILP solutions is much larger than our method.

DGN in A2C version. We chose one of the recent GNN based MARL frameworks called DGN as another baseline and adapt their key contributions into the multi-agent A2C framework, i.e., the network structure and temporal relation regularization. DGN directly uses the local reward to train, under the latent assumption that the local reward encourages cooperation, which is not always held in many real-world problems such as ECR. Therefore, we train it with artificially designed local reward, which is a combination of the global and the local reward. As you can see, we also outperform them in both normal and hard mode.

The ablation studies are used to answer two questions: (1). Does the encoder-decoder attention in EncGAT help heterogeneous information aggregation and intricate interaction understanding? (2). Does PreLAC improve learning performance of cooperative policy?

Encoder-Decoder Attention. We compare our encoder-decoder attention with alternative aggregation functions, i.e. single decoder attention, GAT (Veličković et al., 2018) and LSTM (Hamilton et al., 2017). The single decoder attention directly puts the neighborhood sequence to the attention function in the decoder network introduced in Section 4.1. In the task of the normal mode, its performance is close to our method, but in the task of hard mode, the performance drops by 2%. The reason is that in the hard mode, the increased noise in the simulation data like the vessels’ sailing time and the quantity of orders requires agents to cooperate against uncertainty, making the interactions more complicated. GAT is different from the single decoder attention in the computation of the attention coefficients. In the original implementation of GAT, the attention coefficients are calculated with a single-layer feedforward network. The result underperforms the dot-product based single decoder attention, which indicates that the way to calculate the attention coefficients may significantly influence the result. We also try the LSTM aggregator introduced in (Hamilton et al., 2017). Although LSTM also has the ability to consider the inter-correlated influence from neighborhood sequence on an agent, the result is relatively poor. We think the reason is that the recurrent structure makes it difficult to learn with weak signals.

Pre-training with local actor-critic. To analyze how the pre-training algorithm improves learning performance, we first train the model directly with the global reward (Normal GC). It yields a poor performance especially in the hard mode, which is nearly the same as no repositioning at all. To further understand the result, we visualize the learned embedding of each port by mapping the output vector after EncGAT to the two-dimension space with principal component analysis(PCA). As is shown in Figure 4 where the data points of the same port are painted in the same color, we see that with the enhancement of pre-training, the data points regularly gather to several clusters compared to the mass without pre-training in the left picture. This indicates that without the local actor-critic task, the graph layers fail to learn distinguishable vertex embeddings, which will puzzle the succeeding actor and critic headers. An interesting experiment is also conducted to see the performance if we do not share the actor header between agents (separate actors normal GC), which leads to a little improvement. The reason is that the separate actor headers learn simple but different policies for agents regardless of the poor embedding input. Finally, we also try not to share actor headers in our framework (separate actors PreLAC). The result shows about a 2% drop in performance, which indicates that the parameter sharing, as a space to share experience between agents, helps train a better policy.

Inductiveness and generality. The inductiveness in the field of GNNs means the ability to generalize to unseen graph structures. Because the EncGAT itself is inductive and we share the actor headers among agents, the policy should be inductive too. Henceforth, we further conduct experiments to analyze the generality of the learned policy when the interaction graph changes, e.g., the changes of the topology and the trading distribution in the ECR problem. In particular, we first merge two ports into one port that takes the roles of the original two ports in their own route. Then, we randomly generate the trading distribution, which is different from the distribution generated from the WTO’s data. We plot the heat-map based on the trading quantity in the right of Figure 5 and compare it with the original one in the left of Figure 5. As the distribution completely differs from the original one, the role each port plays and the interactions between agents are different. The normal and hard modes are also defined in this setting. We test the performance of the model trained on the original setting on this new topology directly. The result in Table 2 shows significant improvements in the fulfillment ratio compared to that with no repositioning.

We attach the source code under the folder ‘code/’. The simulator we use is open-sourced, whose link is ‘github.com/microsoft/maro’. All the configurations of experiments are listed in the YAML file ‘config.yml’ and all the configurations of the ECR simulation are listed in four YAML files, which are ‘normal.yml’, ‘hard.yml’, ‘shuffle_normal.yml’ and ‘shuffle_hard.yml’ corresponding to two modes in the original topology and two modes in the derived topology. To reproduce the result, you should first download the simulator project from the github, subsitute the configuration file of the ECR simulation, then set the ‘model:setting’ field in ‘config.yml’ with the experiment name. For example, if you want to reproduce result of the EncGAT-PreLAC framework in the hard setting of the original topology, you should choose the file ‘hard.yml’ and change the field ‘model:setting’ to ‘encgat’.

There are $22$ ports located in main trading countries, $13$ routes and $46$ vessels in the transportation topology. The overall topology is shown in Figure 6, where each node is a port and the edges of the same color form a route, whose directions are the sailing order of each vessel in the route. In addition, the two ports painted in blue are the merged ports in the derived topology we introduce in the main text.

As we stated in the main text, the yearly trading amount are distributed into daily resolution by two rules, e.g., the simple average and the trend function. We plot the trading distribution as well as the total amount of transportation orders at each time-step in Figure 7 and Figure 8. Suppose the total amount at the time-step $t$ is $\hat{O}_{t}$, transportation amount between port $v_{i}$ and port $v_{j}$ are calculated as a random proportion of $\hat{O}_{t}$, as is shown in Formula:

where $\mathcal{N}$ is the Gaussian distribution and $\mu_{<i,j>}$ and $\sigma_{<i,j>}$ are the constant defined in the configuration file.

The fulfillment curves of each configuration listed in the result table of the main text are shown in Figure 9.