ε-greedy 方策

ほとんどは貪欲に、確率εでランダムに選ぶ

ε-greedy方策(ε-greedy法)は、強化学習で行動を選ぶときの単純な方法です。Sutton & Barto の教科書 Reinforcement Learning: An Introduction 第2版(2018年)の第2章§2.2では、次のように説明されています。

ほとんどの場合は貪欲に行動します。つまり、各行動の価値の推定値Qt(a)を比べて、推定値が最大の行動を選びます。ただし、ときどき小さい確率εで、推定値とは無関係に、すべての行動の中から等確率でランダムに1つを選びます。教科書では、このようにほぼ貪欲な行動選択の規則を使う方法をε-greedy法と呼んでいます。

貪欲な行動選択とε-greedyの違い

貪欲な行動選択は、式で書くと At = argmax_a Qt(a) です(教科書の式2.2)。時刻tで、推定値Qt(a)が最大になる行動aを行動Atとして選びます。

ε-greedy方策は次の2つの場合を組み合わせます。

• 確率 1 - ε で、貪欲な行動 At = argmax_a Qt(a) を選ぶ
• 確率 ε で、すべての行動から等確率でランダムに1つを選ぶ

2つ目の場合、ランダムに選ぶ候補には貪欲な行動自身も含まれます。そのため、貪欲な行動が選ばれる確率は 1 - ε ちょうどではなく、それより少し大きくなります。

数値例: 2つの行動でε=0.5のとき

教科書の章末の演習問題(Exercise 2.1)には、2つの行動でε=0.5のとき、貪欲な行動が選ばれる確率はいくらか、という設問があります。上の2つの場合に分けて計算します。

行動を a1 と a2 の2つとし、推定値が大きいほうの a1 が貪欲な行動だとします。

1. 貪欲に選ぶ場合: 確率 1 - ε = 1 - 0.5 = 0.5 で a1 が選ばれます。
2. ランダムに選ぶ場合: 確率 ε = 0.5 でこちらになり、2つの行動から等確率で選ぶので、a1 が選ばれる確率は 0.5 × 1/2 = 0.25 です。

したがって、貪欲な行動 a1 が選ばれる確率は 0.5 + 0.25 = 0.75 です。

もう一方の a2 が選ばれるのはランダムに選ぶ場合だけなので、確率は 0.5 × 1/2 = 0.25 です。合計は 0.75 + 0.25 = 1 になります。

同じ考え方で、行動がk個あるときは次のようになります。

• 貪欲な行動が選ばれる確率: (1 - ε) + ε / k
• それ以外の各行動が選ばれる確率: ε / k

k = 2、ε = 0.5 を入れると、(1 - 0.5) + 0.5 / 2 = 0.75 となり、上の計算と一致します。

収束の保証と、その限界

ε-greedy法では、ステップ数が増えるにつれて、すべての行動が無限回選ばれるようになります。そのため、すべての推定値Qt(a)が、それぞれの行動の真の価値q*(a)に収束することが保証されます。つまり、最適な行動を選ぶ確率は 1 - ε より大きい値に収束し、ほぼ確実になります。

ただし教科書は、これはあくまで漸近的な保証であり、実際の有効性についてはあまり多くを語らない、とも述べています。ステップ数を増やしていった極限での性質であり、有限のステップ数でどれだけ役立つかまでは言っていません。

UCB方策との関係

G検定シラバス2024の中項目9 強化学習のキーワードには、ε-greedy方策が、バンディットアルゴリズムやUCB方策などと並んで挙げられています。ε-greedy方策は、推定値と無関係に等確率でランダムに行動を選ぶ方法です。行動の選び方(探索の仕方)が異なる別の手法として、UCB方策があります。