1. はじめに
強化学習やモンテカルロ木探索（MCTS）において、探索（Exploration）と活用（Exploitation）のバランスを取ることは非常に重要です。その中で代表的な手法の一つが**UCB1（Upper Confidence Bound 1）**です。
UCB1は、マルチアーム・バンディット問題（Multi-Armed Bandit Problem）でよく使用される手法であり、各選択肢（アーム）に対して「どれくらい試行すべきか」を決定します。MCTSでも、どのノード（局面）を探索すべきかを決める際に使われます。
2. UCB1の数式と直感的な理解
UCB1のスコアは次の式で計算されます。
[
UCB1 = \frac{w_i}{n_i} + C \sqrt{\frac{\log N}{n_i}}
]
ここで、
- ( w_i ) : アーム ( i ) の累積報酬（勝利回数など）
- ( n_i ) : アーム ( i ) が選ばれた回数
- ( N ) : 全体の試行回数
- ( C ) : 調整パラメータ（探索の強さを決める）
この数式には、以下の2つの要素が含まれています。
- 平均報酬（Exploitation）: ( \frac{w_i}{n_i} ) は、そのアームがこれまでに得た報酬の平均値を表します。
- 探索の重要度（Exploration）: ( \sqrt{\frac{\log N}{n_i}} ) は、そのアームが選ばれていない場合の不確実性を示します。
この2つの要素を足し合わせることで、報酬が高いアーム（手）を活用しながら、まだ十分に試行されていないアーム（手）も探索することができます。
3. UCB1の動作の流れ
- 各アーム（手）を最初に1回ずつ試す。
- 以降、各アームのスコアをUCB1の式で計算する。
- 最もスコアが高いアームを選択する。
- そのアームの報酬を記録し、試行回数を更新する。
- 2〜4を繰り返す。
このアルゴリズムの特長は、試行回数が少ないアームには高いスコアが与えられるため、未知の選択肢を探索しつつ、報酬の高いアームを活用できる点です。
4. UCB1の応用例
① マルチアーム・バンディット問題
カジノのスロットマシンのように、複数の選択肢（アーム）の中から最適なものを選びたい場合に適用できます。
② モンテカルロ木探索（MCTS）
MCTSでは、ゲームの局面を探索する際にUCB1を使って「どのノードをさらに探索するべきか」を決定します。例えば、囲碁や将棋のAIが次の手を選ぶ際に使用されます。
③ オンライン広告の最適化
異なる広告（バナーや動画）を配信し、ユーザーのクリック率を最大化するために、UCB1を利用して最適な広告を選択できます。
5. まとめ
UCB1は、既存の良い選択肢を活用しつつ、新しい選択肢も試すというバランスを取るための手法です。特に、マルチアーム・バンディット問題やMCTSなどの分野で広く使われています。
この手法を活用することで、限られた試行回数の中で効率的に最適な選択肢を見つけることが可能になります。AIや強化学習に興味がある方は、ぜひUCB1を実装して試してみてください！