ε-greedyとは｜探索と活用の基本・実装・理論的性質を徹底解説

2025年12月13日 最終更新日時 : 2025年12月13日 エバープレイ編集部

ε-greedyとは

ε-greedy（イプシロン・グリーディー）は、強化学習やマルチアームドバンディット問題における最も基本的な探索（exploration）と活用（exploitation）のポリシーの一つです。直感的には「大半の時間は既知の最良行動を選ぶが、確率εでランダムに行動を試して未知の情報を得る」といった方針です。実装が非常に簡単で、実践でもよく用いられるため、強化学習入門として不可欠な考え方です。

基本アルゴリズム（概念と手順）

ε-greedy の基本的な手順は次の通りです。

  • 各行動（アーム）iについて、現在の価値推定 Q(i) を保持する。
  • 毎ステップ、確率1−εで argmax_i Q(i)（現在の推定で最も良い行動）を選択する。
  • 確率εで均等に（あるいは別の確率分布で）ランダムな行動を選択して探索を行う。
  • 行動を実行して得られた報酬で Q(i) を更新する（例：サンプル平均や定率学習率）。

この方針は単純ですが、探索と活用のトレードオフを確率的に制御でき、実装の容易さから多くの応用で使われています。

εの決め方と実装上のコツ

εの選び方は性能に大きく影響します。典型的な選択肢は以下のとおりです。

  • 固定ε：εを一定値（例：0.1）に固定する。実装が簡単で非定常環境には強いが、定常環境では長期的に最適行動を見つけられない可能性がある（線形後悔）。
  • ε-first：最初のNステップはε=1（完全探索）、その後ε=0にする方式。初期探索を集中して行いたい場合に有効。
  • 減衰スケジュール（ε-decreasing）：時間に応じてεを小さくする。線形減衰や指数減衰、または1/t型の減衰がよく使われる。理論的には適切に減衰させると長期後悔を改善できる場合がある（後述）。
  • 環境が非定常な場合は、小さいが非ゼロの定常εや、突然の変化検出に応じてεを一時的に増やす手法が有効。

さらに、価値推定の更新法も重要です。定常環境ではサンプル平均（Q_{n+1} = Q_n + (1/n)(r - Q_n)）が有効ですが、非定常環境では定率学習率α（Q ← Q + α (r − Q)）を使い、過去の報酬に適度な忘却を導入することが一般的です。

理論的性質（後悔と収束）

ε-greedy の理論的な性質をまとめると次の点が重要です。

  • 固定εでは、長期的に一貫して探索が行われるため、平均報酬に対する後悔（regret）は時間に線形に増加する。つまり最適ポリシーに比べて累積報酬の差が時間とともに増える。
  • 減衰εを用いると、適切なスケジュールのもとで後悔を対数オーダー（log t）に抑えられることが示されています。Auerら（2002）などの解析では、ε_tを時間とともに減らす簡単な戦略でも有限時間で良好な性能が得られることが示唆されています。ただし、減衰率や定数は問題依存であり、実際の性能は環境や報酬差（ギャップ）に敏感です。
  • より強い理論保証を求める場合、UCB（Upper Confidence Bound）やThompson Samplingのようなアルゴリズムがより良い後悔上界（多くの場合対数オーダーで最小定数に近い）を与えることが知られています。ε-greedyは簡潔で扱いやすい反面、最悪ケースでの保証は劣ることがあります。

実践での利用例

ε-greedyはその単純さから様々な分野で利用されています。

  • オンラインA/Bテストやウェブ推薦：新しいコンテンツを一定の確率で試すことで未知の好みを探索する。
  • 強化学習（深層強化学習を含む）：DQN（Deep Q-Network）などでは学習初期に高いεから徐々に低くするε-減衰戦略がよく用いられる。
  • ロボティクスや制御：安全制約のある環境では探索確率を小さく抑えつつ段階的に試行する。
  • 推薦・広告配信システム：既知の高報酬候補を優先しつつ、一定確率で多様な候補を提示して長期の発見を行う。

バリエーションと代替手法

ε-greedyにはいくつかの改良・拡張があり、用途に応じて使い分けられます。

  • ε-greedy + 楽観的初期値（optimistic initialization）：未知のアクションに高い初期Q値を与え、自然に探索を促す。
  • Softmax（Boltzmann）探索：行動を確率分布（exp(Q/τ)）に基づいて選ぶ方法。差が小さい場合により滑らかな探索が可能。
  • UCB（Upper Confidence Bound）：不確実性の評価に基づいて行動を選択し、理論的保証が強い。
  • Thompson Sampling：ベイズ的なサンプリングにより探索・活用を効率良く行う。実務での性能が高い場合が多い。

実装時の注意点・落とし穴

実運用でしばしば見られる注意点を挙げます。

  • ランダム探索の方法：探索時に「均等ランダム」か「未試行優先」かで挙動が変わる。全アーム均等に探索すると既に良好なアームを再検証しにくい場合がある。
  • 初期値の扱い：初期Q値が低すぎると最初の誤判定で不利になりやすい。楽観的初期値は簡単で有効だが、問題に応じて調整が必要。
  • 学習率の設定：非定常環境では定率学習率αを使って古い情報を忘却することが重要。サンプル平均は定常環境向け。
  • 評価の偏り：オフラインデータで性能評価するとき、既存のバイアスにより探索の有効性を正確に評価できないことがある（オフポリシー評価の問題）。

実例：深層強化学習における実装例（概念）

DQNのような深層強化学習では、ε-greedyが典型的な行動選択戦略として使われます。一般的な設定は次の通りです。

  • 学習開始時にε=1.0（完全ランダム）にして十分に探索を行う。
  • 数万～数百万ステップかけて線形または指数的にεを減衰させ、最終的に小さい値（例：0.01）に落ち着かせる。
  • 経験再生（replay buffer）やターゲットネットワークを併用し、安定した学習を行う。
  • 環境が変化する場合は、εを再度増やすスケジュールや、非ゼロの最小εを保持する方針が使われる。

まとめ

ε-greedyは、探索と活用の基本を理解する上で非常に有益な手法です。単純で実装が容易な反面、固定εは長期的な性能保証が弱く、より良い理論的性質を求めるならUCBやThompson Samplingといった代替手段を検討する必要があります。実務では、環境の定常性や目的（短期の報酬最大化か、長期の知識獲得か）に応じて、減衰スケジュール、学習率、初期化、探索の種類を設計することが重要です。

参考文献

カテゴリー
IT
前の記事
ファイナルファンタジーXV 完全解説：開発史・ゲームデザイン・物語の深掘り
2025年12月13日
次の記事
XBシリーズ完全ガイド：エクストラベースの設計、音質評価、選び方と使いこなし
2025年12月13日