Neural networks (NN) implementing heuristic functions (see Appendix for the full structure) were adopted from [1]} and [2]}, where the latter is, to our best knowledge the state-of-the-art architecture for maze domains. It contains seven convolution layers \(P_1, \ldots P_7\)  followed by four convolution-attention-position blocks, which allow correlating information from distant parts of the maze. The output tensor of the fourth CoAt block is "flattened" by global average pooling over the \(x\)  and \(y\)  dimension to a vector, which is then fed to a fully connected layer (\(\mathrm {FC}\) ) which outputs a scalar estimating the heuristic value. For more details on the network, we refer the reader to the original publication [2]}. This network is further called "CoAt" after the CoAt blocks. We also studied the network of [1]} (without policy head), which has a similar structure, but instead of four CoAt blocks it has seven CNN layers. We refer to this network as to CNN. Both networks are by design scale-free, which means that they can be used on mazes of various sizes, as is shown below on the mazes with teleport domain. Since the \(\mathrm {L}^*\) loss as defined in Equation REF  is not differentiable, the Iverson bracket is replaced by a logistic loss function \(\mathrm {L}_l(x) = \log (1 + \exp (-x)).\)
