時間をかかる計算において、最適なパラメータをサーチするのは結構めんどくさい。
Pythonだと、hyperoptとかoptunaとか良いツールが使える訳だが、Python以外の言語においては、代替のものを探すか、パラメータサーチはPythonに任せるか、あるいは自力実装するかということになる。
異なる言語を混ぜるのはシステムが複雑になるし、メンテナンスも面倒になりがちである。 また代替の物を探す場合、簡単に見つかれば良いが実際はなかなか骨が折れる。 今回は実装が簡単で、グリッドサーチよりは頭の良い方法を探ってみる。
マルチアームドバンデッド問題(multi-armed bandit problem)
選択すると報酬が得られるレバーがN本ある時に、一定の試行回数で最大の報酬が得られるように、レバーを選択する問題である。強化学習の教科書などに載っている。
サーチするパラメータが離散的なのであれば、マルチアームドバンデッドとして効率的に解くことができそう。
UCB1アルゴリズム
この問題に対して、期待値が高くなる戦略としてUCB1アルゴリズムが知られているらしい。UCB1アルゴリズムでは、レバーを選択するたびに、全てのレバーに対して以下の評価値を求めて、評価値が最大となるレバーを選択する。（報酬の値のレンジって任意でいいのかなぁ？）
は、レバー全体を選択した回数。
は、レバーiを選択した回数。
は、レバーiで得られた報酬の期待値。
UCB1アルゴリズムの評価値は、理論的には上記が最適らしい？が、実際には定数項を使って、期待値項とボーナス項の比率を補正して使うことも多い。
これくらいなら簡単に実装できる。気が向いたらもう少し調べたい。
