Learning Rate Based Branching Heuristic for SAT Solvers https://cs.uwaterloo.ca/~ppoupart/publications/sat/learning-rate-branching-heuristic-SAT.pdf
CDCL SATソルバにおける変数選択を多腕バンディット問題でという話。 自分もそういうことを考えたことはあって、報酬をどう定義するのが良いかが難しいと思っていたのだけど、 この論文はその変数の割り当てられている間の学習で学習節に貢献した回数の比率(learning rate)を報酬にしてて、ナルホドと思った。
一方でこういう問題設定は、強化学習の手法を援用できるという利点はあっても、リグレットの解析とかみたいな強化学習的に面白い議論は出来なそうで、プラクティカルな性能向上を示せなければ辛そう（この論文はちゃんと性能向上を示せてるが）。