UCB 方策

UCB方策が選ぶ行動を決める式

UCB方策(UCBは上側信頼区間の略)は、Sutton & Barto の教科書 Reinforcement Learning: An Introduction 第2版(2018年)の第2章2.7節で、行動を選ぶ次の式として定義されています(式2.10)。

At = argmax_a[Qt(a) + c*sqrt(ln t / Nt(a))]

時刻tで選ぶ行動Atは、行動ごとに計算した Qt(a) + c*sqrt(ln t / Nt(a)) が最大になる行動aです。

式の各記号の意味

• Qt(a): 時刻tの時点での、行動aの価値の推定値です。
• t: 時刻tまでに経過したステップ数です。ln t はその自然対数です。
• Nt(a): 時刻tまでに行動aが選ばれた回数です。
• c: 探索の度合いを制御する正の定数です(c>0)。
• sqrt(ln t / Nt(a)): ln t を Nt(a) で割った値の平方根です。行動aの価値の推定がどれだけ不確かか(分散)を表す尺度です。cはこの項にかかり、信頼水準を決めます。

Nt(a)=0、つまりまだ一度も選ばれていない行動aは、式を最大にする行動とみなします。

不確実性の項が大きくなるときと小さくなるとき

平方根の項は、どの行動が選ばれたかで次のように動きます。

• 行動aが選ばれると、Nt(a)が増えるので、行動aの不確実性の項は小さくなります。
• 別の行動が選ばれると、行動aのNt(a)は変わらずtだけが増えるので、行動aの不確実性の項は大きくなります。

分子が t ではなく自然対数の ln t なので、項が大きくなる速さは時間がたつほど遅くなります。それでも ln t に上限はないので、選ばれていない行動の項はいつまでも大きくなり続けます。そのため、すべての行動がいずれ選ばれます。一方で、価値の推定が低い行動や、すでに何度も選ばれた行動は、選ばれる頻度がしだいに減っていきます。

数値を当てはめた計算例

行動Aと行動Bの2つから選ぶ場合を考えます。条件は次のとおりです。

• 経過ステップ数 t = 100
• 定数 c = 2
• 行動A: Qt(A) = 0.6、Nt(A) = 80
• 行動B: Qt(B) = 0.4、Nt(B) = 20

ln 100 は約 4.605 です。

行動Aの値:

• ln t / Nt(A) = 4.605 / 80 = 約 0.0576
• sqrt(0.0576) = 約 0.240
• c * 0.240 = 2 * 0.240 = 0.480
• Qt(A) + 0.480 = 0.6 + 0.480 = 1.080

行動Bの値:

• ln t / Nt(B) = 4.605 / 20 = 約 0.2303
• sqrt(0.2303) = 約 0.480
• c * 0.480 = 2 * 0.480 = 0.960
• Qt(B) + 0.960 = 0.4 + 0.960 = 1.360

1.360 は 1.080 より大きいので、このステップでは行動Bが選ばれます。価値の推定値だけを比べると行動A(0.6)のほうが高いのに、行動Bは選ばれた回数が20回と少なく不確実性の項が大きいので、合計で上回ります。行動Bが選ばれるとNt(B)が増えて行動Bの不確実性の項は小さくなり、選ばれなかった行動Aの不確実性の項はtが増える分だけ大きくなります。

探索の仕方が異なる手法

G検定シラバス2024の中項目9 強化学習では、UCB方策がバンディットアルゴリズムやε-greedy方策と並んでキーワードに挙げられています。ε-greedy方策は探索の仕方が異なる別の手法です。