# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Methods
#### 3.1.2 Reinforcement Learning
Instead of mapping the graph structure to a fixed-length vector to obtain the embeddings of the vertices, G2S-RNN uses a discrete-time dynamical system to process the graph structure. The nodes' embeddings are updated by multiple rounds of convolution, and finally, the entire time-series vector is used as the embedding of the graph, which makes the embeddings' length variable (related to the number of convolution layers). Then, Seq2 Vec takes the embedding as input to obtain the vector representation of each node, and Q-learning is used to update the policy. [PERSON] et al. [241] focused on larger graph structures. They tested [95] on MC and show that S2V-DQN fails on graphs beyond 2000 nodes. Based on the observation that, although the graph may be large, only a small percentage of the nodes are likely to contribute to the solution set [241], [PERSON] et al. proposed a two-stage method called GCOMB, which uses supervised learning to prune poor nodes and learns the node's embedding with GCN, and searches for solutions on good nodes with Q-learning. The experiment results show that the efficiency is successfully improved on billion-sized graphs. [PERSON] et al. [243] proposed CoPiEr which uses information from both graph-based representation and ILP-form representation. The trajectories are generated by algorithms using two kinds of representations, respectively, following an exchange between two trajectories. Specifically, two trajectories are evaluated by the reward function, and the one with a higher reward is used as a demonstration for the algorithm based on the other trajectory. Reinforcing Methods  
Some works pay more attention to improving the optimization process rather than designing the policy network, which is shown in Table 4.  
Based on [PERSON] et al. [85], [PERSON] et al. [86] proposed a policy network with only attention mechanism and enhanced the framework with 2-opt. Instead of using LSTM, the decoder maps three last sampled actions (visited cities) to a vector, and 2-opt is used to improve the output solution. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Reference** & **Year** & **Advantage or Novelty** \\ \hline [PERSON] et al. [86] & 2018 & enhanced the framework with 2-opt \\  & & learned permutation instead \\ [PERSON] et al. [87] & 2018 & of decision sequences point by \\  & & re-designed the baseline \\  & & of REINFORCE algorithm \\  & & as the cost of a solution \\  & & from the policy defined by \\  & & the best model \\ [PERSON] et al. [244] & 2019 & solved COPs with constraints \\ [PERSON] et al. [245] & 2019 & AlphaGo Zero to replace \\  & & Q-learning \\ [PERSON] & 2020 & explored the solution space \\  & & during test time \\ [PERSON] et al. [246] & 2020 & handled equally optimal \\  & & solutions \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Works on reinforcing methods of reinforcement learning. The previous idea of using reinforcement learning to solve COPs is usually to generate decision sequences point by point, which is a greedy heuristic. On the contrary, [PERSON] et al. [87] proposed the Sinkhorn policy gradient (SPG) algorithm to learn permutation so that in addition to TSP-type problems, it can also solve other issues, for example, maximum weight matching. The state of SPG is a permutation instance of size \(N\), and the action is an \(N\times N\) permutation matrix. To use a deterministic policy gradient method, such as DDPG, [PERSON] et al. used Sinkhorn layers to approximate the permutation matrix and added a term to the critic loss to de-bias the policy gradient. [PERSON] et al. [88] improved [85] on two aspects: (1) They used an attention mechanism instead of LSTM for encoding, which introduces invariance to the node input order and enables parallel computation. (2) They designed the baseline of REINFORCE algorithm as the cost of a solution from the policy defined by the best model, which is similar to self-play that improves itself by comparing with the previous solutions. [PERSON] et al.