Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge
読んだ。
グラフ上のNP-hardな問題に対して、MCTSを適用してみたよというお話。
まず、グラフ上のNP-hardな問題をMarkov Decision Processに落とし込む。んで、MCTSを使ってpolicyを学習したいんやが、Inputサイズが可変なので、GNNを使って固定長のGraph Embeddingを生成することで解決してる。あとはAlphaGo Zeroと同じ
結果としてはまあまあといったところ(Supervisedな手法やB&Bには負けるけど、S2V-DQNには勝ってる感じ)
以下、雑感
- Reinforcement Learningは流行ってるのかなぁと思いぱっと読んでみた
- 実際精度も悪くないし、いいのかなぁと思ったり(Unsupervisedっていう点を考えるといいと思う?)
- MDPに落とし込むアイデア自体は [Li et al. 2018] 由来なんだろうなぁ(なんとなく思った
- そこまで学習に時間かかってないのも「いいね〜」となった(なんだかんだこんなもん?)
- ただ、MIS自体がタスクとして簡単な可能性が十分あるんだよなぁ……
- MISはたしかFPT的な計算量クラス(W[1]-hardness的なやつ)だと簡単な部類だったような、違うような(曖昧なのでちゃんと調べる)
- ん〜〜〜でも CPNGNN の論文だと、MISは難しい(正確に言うと、CPNGNNではTrivialなGreedy Algorithmより良いものを学習できない)らしいし……
- GINを使ってるので、自明な貪欲Algorithm(なにがTrivialだ?)を使った結果と比較したいなぁ
- もし、自明な貪欲より良い解だったら、CPNGNNの論文再考する必要あるし(Aggregation、Combine、Readoutの仕組みが思ったより複雑ってこと?かも
- 自明な貪欲と同じくらいだったら、自明な貪欲くらいしか学習できないってことだし(まあそれもそれで面白いような……なんでかって言うと、よくわかってないNP-hard問題に対する貪欲アルゴリズム構築に役立ちそう)(そんな問題なさそうやけど)
強化学習の勉強を……します。(緑の本が研究室にあったので読み始めました)
一応演習やら自分でもやった記憶はあるけどちゃんと理解してない……
Pのイ同期の論文なので読んでいる最中に顔が思い浮かんでしまった(?)