1行定義
UCB方策とは、行動ごとの報酬の平均に、見積もりの不確かさに応じた上乗せ分を加え、その値が最大の行動を選ぶことで、探索と活用の釣り合いをとる方策のことです。
くわしく
UCB方策は、バンディット問題などで行動を選ぶ方法の1つです。UCBはUpper Confidence Bound（信頼区間の上限）の略です。「よくわからないものは、可能性を高めに見積もって試す」という考え方です。
選び方の式
全体の試行回数をtとして、次の値が最大の行動aを選びます。
Q(a) + c × √(ln t ÷ N(a))
Q(a)：行動aでこれまでに得た報酬の平均（活用の部分）N(a)：行動aをこれまでに選んだ回数c：探索の強さを決める正の定数
第2項が、見積もりの不確かさに応じた上乗せ分です。ある行動を選ぶたびにN(a)が増え、上乗せは小さくなります。ほかの行動を選んでいる間はtだけが増え、上乗せは少しずつ大きくなります。そのため、どの行動もいずれは試されます。N(a) = 0の行動は値が最大とみなし、最初に一通り試します。
計算例
c = 1、t = 100とします。ln 100（自然対数）は約4.6です。行動Aは80回選んで平均0.5、行動Bは20回選んで平均0.4です。
- A：
0.5 + √(4.6 ÷ 80)は約0.5 + 0.24 = 0.74 - B：
0.4 + √(4.6 ÷ 20)は約0.4 + 0.48 = 0.88
平均ではAが上でも、試した回数が少ないBが選ばれます。
ε-greedy方策との違い
ε-greedy方策は、探索のときにすべての行動を同じ確率で選ぶため、見込みの薄い行動も試し続けます。UCB方策は、不確かさが大きい行動に絞って試すので、探索の無駄を減らせます。理論面でも、εが一定のε-greedy方策ではリグレット（取り逃した報酬）が試行回数にほぼ比例して増えるのに対し、UCB1では対数のペースに抑えられることが示されています。
使われる場面
2006年には、UCB1を探索木の枝の選択に応用したUCTが提案され、モンテカルロ木探索で広く使われるようになりました。一方、状態が膨大な問題や、報酬の傾向が変わっていく問題には、そのままでは使いにくいとされます。
G検定での出題
出題のされ方
平均報酬に不確かさの補正を加えて選ぶ仕組み、試行回数が少ない行動ほど選ばれやすくなる理由、確率εで無作為に探索するε-greedy方策との違いが、バンディット問題の文脈で問われます。
混同しやすい用語
| 用語 | 意味 |
|---|---|
| UCB方策このページの用語 | 行動ごとの報酬の平均に、見積もりの不確かさに応じた上乗せ分を加え、その値が最大の行動を選ぶことで、探索と活用の釣り合いをとる方策 |
| ε-greedy方策 | 確率εでランダムに行動を選んで探索し、残りの確率1−εでその時点で価値が最も高いと推定される行動を選ぶ方策 |
◯×チェック
次の文が正しいか、誤りかを選んでください。
-
UCB方策では、まだ一度も選んでいない行動があれば、ほかの行動より先にその行動を選ぶ。
答えを見る
答え ◯ 正しい
試した回数が0回の行動は、見積もりの不確かさが最大とみなされます。そのため、最初にすべての行動を一通り試してから、補正を加えた値で比べ始めます。
-
UCB方策は、ε-greedy方策と同じように、あらかじめ決めた確率εで行動を無作為に選ぶことで探索を行う。
答えを見る
答え × 誤り
UCB方策は、平均と補正項の合計で行動を決めます。確率εで無作為に選ぶ仕組みはなく、不確かな行動を優先して試すことで探索します。
-
UCB方策で、ある行動を長い間選ばずにいると、全体の試行回数が増えるにつれて、その行動の補正項は少しずつ大きくなる。
答えを見る
答え ◯ 正しい
補正項の分子には全体の試行回数の対数が入り、分母のその行動の試行回数は増えません。そのため、選ばれずにいた行動も、いずれ再び試されます。
この用語の練習問題
出典
- G検定 試験出題範囲（シラバス2024）第1.4版 （技術分野 項目9 強化学習）
- Richard S. Sutton, Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press (2018) （2.7 Upper-Confidence-Bound Action Selection）
- Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning 47(2–3), 235–256 (2002)
- Levente Kocsis, Csaba Szepesvári, Bandit Based Monte-Carlo Planning, ECML 2006, LNCS 4212, 282–293