# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Methods
#### 3.1.2 Reinforcement Learning  
As pointed out by [PERSON] et al. [85], training strategies for COPs with supervised learning require a large number of labels, while the optimal labels for many COPs are not easy to obtain. However, it is relatively easy to evaluate the quality of a given solution. Therefore, [PERSON] et al. proposed to use evaluation as a reward feedback in an RL paradigm to solve the labeling problem, which is another milestone work. More other works follow the same structure and shape the parameterization of the policy network as shown in Table 3, which is the similar concept of an encoder in supervised learning. [PERSON] et al. [85] modeled the 2D Euclidean TSP problem as a sequential decision problem. At each step, a distribution over the next city to visit in the tour is output by the policy, which forms the travel strategy by the chain rule at the terminal step, and the objective is to shorten the travel distance. The policy model is based on Ptr-Net proposed by [PERSON] et al. [76] without glimpse, which reads the state \(s\) (the city sequence, one city at a time), encodes it as a \(d\)-dimensional embedding with an LSTM, and decodes it with an LSTM to obtain the action (the distribution of the next city). [PERSON] et al. used the travel distance to indicate the reward and train the policy with an actor-critic method. [PERSON] et al. [238] applied [85] to the 3D BPP problem to learn the order of packing items into bins, and proved that it outperforms the well-designed heuristic approach. A major limitation of [85] is that it assumes the problem is static over time, thus it cannot be used to solve problems, such as VRP, where the properties of the input sequence keep changing. To solve this problem, [PERSON] et al. [239] proposed a new policy model which leaves out the encoder RNN. They dealt with the static elements and dynamic elements in the input separately, that is, the embeddings of the static elements are input to the RNN decoder and then input to an attention mechanism with glimpses similar to Ptr-Net together with the embeddings of the dynamic elements. Finally, the probability vector of the next destination is output. For another typical form of CO problem-graph structure, [PERSON] et al. [95] proposed a training method combining GNNs with reinforcement learning to remove the dependence on sample labels, called S2V-DQN. [PERSON] et al. presented a partial solution as an ordered list \(S\) (a decision-making sequence). At each time step, a node is greedily selected to join \(S\) so that the evaluation value \(Q\) is maximized. The embedding of each node in list \(S\) is obtained by Structure2 Vec [242] according to its graph structure (the properties of the node and its neighbor), and \(Q\) depends on the embeddings of the candidate nodes and the embedding of the whole graph. Parameters are trained using n-step Q-learning \begin{table}
\begin{tabular}{c c c} \hline \hline
**Reference** & **Year** & **Advantage or Novelty** \\ \hline [PERSON] et al. [85] & 2016 &
\begin{tabular}{c} used evaluation as reward \\ feedback in RL paradigm \\ solved the 3D BPP problem \\ using RL \\ the properties of the input \\ sequence is not static \\ formulated partial solutions \\ as decision sequence \\ improved scalability on larger \\ testing graph than training set \\ billion-sized graphs \\ combined information \\ from both graph-based \\ representation and ILP-form \\ representation \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Works on policy network of reinforcement learning. and fitted Q-iteration. [PERSON] et al. tested S2V-DQN on MVC, MC, and 2-D TSP, showing its applicability to multiple different problems, graph types, and graph sizes. [PERSON] et al. [240] focused on the scalability of methods on graph structure problem: can a graph neural network trained at a certain scale perform well on orders-of-magnitude larger graphs [240]? To address this problem, [PERSON] et al. proposed G2S-RNN.