強化学習の勉強をしていて、ε-greedy法という手法に出会った。仕組みは単純で、基本的には今のところ一番良さそうな選択(greedy)を取り続けるが、確率εで、あえて今まで試したことのない行動を取る、というだけのルールだ。

説明を読んだ瞬間、これって人生っぽいなと思った。

普段は自分にとって「良い」と分かっている方針で行動する。仕事のやり方、休日の過ごし方、付き合う人。基本的には、今までの経験から「これが良い」と分かっているものを選び続ける方が効率がいい。

でも、たまに、今まで選んだことのない行動を取ってみる。行ったことのない店に入る、誘われなかった集まりに顔を出す、専門外の分野の本を読む。多くの場合は空振りに終わる。でも、ときどき「これは良かった」という発見があって、それが次からの「基本方針」を書き換えてくれる。

これが単なる感想で終わるのはもったいないので、実際にε-greedy法をPythonで実装し、「たまに冒険する」ことが本当に良い結果につながるのか、数値で確認してみることにした。

探索と活用のジレンマ

ε-greedy法を理解するには、まず探索(exploration)と活用(exploitation)のトレードオフという考え方を知る必要がある。

強化学習のエージェントは、いくつかの選択肢(行動)の中から一つを選び、その結果として報酬を得る。それぞれの行動がどれくらいの報酬をもたらすかは、最初は分からない。何度か試してみて、初めて「この行動は良さそうだ」という見積もりができる。

ここでジレンマが生まれる。

• 活用: 今まで試した中で一番良かった行動を選び続ければ、少なくともその時点で分かっている中では最善の結果が得られる。
• 探索: でも、まだ試していない行動の中に、実はもっと良いものが隠れているかもしれない。試さなければ、それは永遠に分からないままだ。

活用ばかりしていると、たまたま最初に試した行動がそこそこ良かった場合、それ以上の選択肢があるかもしれないのに気づかず、その場に留まり続けてしまう。かといって探索ばかりしていると、いつまで経っても「分かっていることを使って着実に得をする」ことができない。

ε-greedy法は、このジレンマに対する、かなり素朴だが効果のある解答だ。

ε-greedy法のルール

ルールは次の1行に尽きる。

• 確率 1 - ε で、今のところ一番価値が高いと推定されている行動を選ぶ(活用)
• 確率 ε で、ランダムに行動を選ぶ(探索)

例えばε=0.1なら、90%はこれまでの経験に基づくベストな選択をし、10%は完全にランダムな行動を試す。

各行動 $a$ の価値の推定値 $Q(a)$ は、実際にその行動を取って得られた報酬の平均で更新していく。

$$Q_{n+1}(a) = Q_n(a) + \frac{1}{n}\left(R_n - Q_n(a)\right)$$

$R_n$ は $n$ 回目にその行動を取ったときに得られた報酬、$Q_n(a)$ はそれまでの推定値だ。新しい報酬と今の推定値との差分を、試行回数で割った分だけ推定値に足し込んでいく。試行回数が増えるほど、1回の結果が推定値に与える影響は小さくなり、推定値は徐々に本当の期待値に収束していく。

これはQ学習(Q-learning)で状態を持たない特殊ケースと考えるとイメージしやすい。Q学習は「状態×行動」ごとに価値 $Q(s, a)$ を学習し、次の行動を選ぶときにε-greedy法で探索と活用のバランスを取る、という構成になっていることが多い。今回試す多腕バンディット問題は、状態が常に1つしかないQ学習と考えれば、Q学習の中核部分だけを取り出した最小構成と言える。

多腕バンディット問題で実験する

ε-greedy法の効果を確認するのに定番の題材が、多腕バンディット問題だ。

複数のスロットマシン(腕)が並んでいて、どれを引いても報酬がもらえるが、その期待値は腕ごとに違う。しかもプレイヤーはその期待値を知らない。何度も引きながら「どの腕が一番当たりそうか」を推定し、なるべく多くの報酬を稼ぐことを目指す。

Sutton & Barto の強化学習の教科書で使われる設定にならい、次のような環境を作る。

import numpy as np

K = 10          # 腕(選択肢)の数
STEPS = 1000    # 1回の試行あたりのステップ数
RUNS = 2000     # 独立試行の回数(平均を取ってならす)

def run_bandit(epsilon, steps=STEPS, seed=None, decay=False):
    local_rng = np.random.default_rng(seed)
    q_true = local_rng.normal(0, 1, size=K)   # 各腕の本当の期待報酬(エージェントには非公開)
    optimal_action = np.argmax(q_true)

    q_est = np.zeros(K)     # 推定価値
    n_pulls = np.zeros(K)   # 各腕を引いた回数

    rewards = np.zeros(steps)
    is_optimal = np.zeros(steps)

    for t in range(steps):
        eps = epsilon / (1 + t / 200) if decay else epsilon

        if local_rng.random() < eps:
            action = local_rng.integers(K)        # 探索
        else:
            action = np.argmax(q_est)              # 活用

        reward = local_rng.normal(q_true[action], 1)

        n_pulls[action] += 1
        q_est[action] += (reward - q_est[action]) / n_pulls[action]

        rewards[t] = reward
        is_optimal[t] = (action == optimal_action)

    return rewards, is_optimal

10本の腕それぞれに、標準正規分布からランダムに決めた「本当の期待報酬」を割り当てる。エージェントはこの値を知らない状態からスタートし、1000ステップかけて推定していく。これを2000回の独立試行で繰り返し、平均を取ってならす。

epsilonの値をいくつか変えて比較した。

settings = [
    ("epsilon = 0 (完全greedy)", 0.0, False),
    ("epsilon = 0.01", 0.01, False),
    ("epsilon = 0.1", 0.1, False),
    ("epsilon = 0.3", 0.3, False),
    ("epsilon = 0.3 -> 減衰", 0.3, True),
]

「epsilon = 0.3 -> 減衰」は、最初はε=0.3から始めて、ステップが進むにつれてεを小さくしていく設定だ。最初はよく探索し、経験が増えるにつれて活用の比重を上げていく。

結果:何もしない(ε=0)のが一番悪い

2000試行の平均を取った結果が次のグラフだ。

そして、各ステップで「本当に一番良い腕」を選べていた割合を示したのが次のグラフだ。

最後の100ステップだけを見た数値は次のようになった。

epsilon = 0 (完全greedy)   final_avg_reward=1.0355  final_optimal_rate=35.95%
epsilon = 0.01           final_avg_reward=1.3245  final_optimal_rate=60.43%
epsilon = 0.1            final_avg_reward=1.3601  final_optimal_rate=79.31%
epsilon = 0.3            final_avg_reward=1.0707  final_optimal_rate=67.42%
epsilon = 0.3 -> 減衰      final_avg_reward=1.4433  final_optimal_rate=84.57%

一番印象的だったのは、完全greedy(ε=0)が最下位だったことだ。「今分かっている中で一番良い選択を常にする」のが、直感的には一番賢く見える。でも1000ステップ経っても、本当に最適な腕を選べていたのはわずか35.95%。3回に1回以下しか正解にたどり着けていない。

理由は単純で、序盤にたまたま「そこそこ良い」結果を出した腕を早々に選び続けてしまい、他の腕を試す機会が二度と訪れないからだ。一方でε=0.1は、たまに探索を挟むおかげで最終的に79.31%まで最適行動の選択率を上げている。

ε=0.3はε=0.1より探索の頻度が高いのに、成績はε=0.1より悪かった。探索し過ぎると、せっかく最適な腕を見つけても30%の確率でわざわざ別の(おそらく劣った)腕を選んでしまうので、活用の恩恵を十分に受けられない。探索は「多ければ多いほど良い」わけではなく、活用とのバランスが重要になる。

そして一番成績が良かったのは「ε=0.3から減衰」の設定だった。最初は積極的に探索して情報を集め、経験が溜まってきたら活用に比重を移す。これが、探索と活用の両方の恩恵を一番効率よく受け取れる戦略だった。

たった1回の「序盤運」で人生が固定される

平均を取った結果だけでは実感が湧きにくいので、単一の試行を1つ取り出して、完全greedy(ε=0)がどうやって「ハズレ」に固執するのかを具体的に見てみる。

found = None
for seed in range(0, 2000):
    trial_rng = np.random.default_rng(seed)
    q_true = trial_rng.normal(0, 1, size=K)
    optimal = np.argmax(q_true)

    chosen, avg, _, q_est = run_bandit(q_true, epsilon=0.0, seed=seed + 5000)
    late_choice = chosen[100:]
    stuck_action = np.bincount(late_choice, minlength=K).argmax()
    stuck_rate = np.mean(late_choice == stuck_action)

    if stuck_action != optimal and stuck_rate > 0.99 and (q_true[optimal] - q_true[stuck_action]) > 0.8:
        found = seed
        break

「完全greedyが、真の最適解ではない腕にほぼ100%固執してしまう」ケースを2000パターンの中から探すと、seed=3で次のような環境が見つかった。

q_true: [ 2.04 -2.56  0.42 -0.57 -0.45 -0.22 -2.02 -0.23 -0.87  3.32]
optimal action: 9   true value: 3.32

10本の腕のうち、本当に一番良いのは9番目の腕(期待値3.32)。しかし0番目の腕も期待値2.04とそこそこ悪くない。この環境で完全greedyを動かすと、序盤に0番目の腕でたまたま良い結果が出たせいで、そのまま0番目の腕を選び続け、最後の300ステップでは一度も9番目の腕(本当の正解)を選ぶことがなかった。

greedy locked onto action: 0   true value: 2.04
greedy final running avg reward: 2.068
epsilon-greedy final running avg reward: 2.46
greedy picked optimal action in last 300 steps: 0.0 %
eps-greedy picked optimal action in last 300 steps: 64.0 %

同じ環境でε=0.1のエージェントを動かすと、たまに他の腕を試すうちに9番目の腕(本当の正解)を発見し、最後の300ステップでは64%の確率でその腕を選べるようになった。平均報酬も2.068から2.46まで伸びている。

グラフにすると違いは一目瞭然だ。

完全greedyの青い線は、序盤で一度2.1あたりに落ち着いたあと、ずっとそこから動かない。橙色のε=0.1の線は、しばらく青い線より下にいる(探索している分、無駄も多い)が、300ステップを過ぎたあたりから、本当の最適解を見つけて一気に伸びていく。真の最適値である3.32(グラフの点線)にはまだ届いていないが、明らかにその方向に向かっている。

この2本の線を見たとき、正直かなりドキッとした。「そこそこ良い」を早めに見つけてしまったせいで、「もっと良い」があることに気づかないまま、それを一生やり続ける。 これは多腕バンディット問題の話であると同時に、自分にも心当たりのある話だった。

新卒で入った会社のやり方、最初に選んだ勉強法、20代前半で決めた「自分はこういう人間だ」という自己認識。それが本当に自分にとって最適かどうかを検証しないまま、ただ「最初にそこそこうまくいったから」という理由で、何年も同じ方針を取り続けてしまうことがある。完全greedyのエージェントが0番目の腕に固執するのと、構造としてはまったく同じだ。

εは大きければ良いわけでもない、という部分も含めて人生っぽい

今回の実験でもう一つ面白かったのは、探索の量(ε)が多ければ多いほど良いわけではない、という結果だった。ε=0.3はε=0.1より探索を頑張っているのに、最終成績はε=0.1に負けている。

これも人生に置き換えるとしっくりくる。何にでも手を出し、何も定着させない生き方は、それはそれで「せっかく見つけた良いもの」を活かしきれない。ずっと新しいことに首を突っ込み続けていると、一つひとつの選択から得られる恩恵を回収する前に、また次の探索に移ってしまう。

一方で、一番成績が良かったのは「最初は多く探索し、だんだん活用に寄せていく」減衰スケジュールだった。εを一定にせず、時間とともに小さくしていく。これは「若いうちはいろいろ試して、経験が溜まってきたら、その中で一番良かったものに比重を移していく」という、割とよく聞かれるライフステージの話にかなり近い形をしている。

もちろんこれは都合の良い後付けの解釈で、人間の人生を10本腕のバンディット問題に単純化するのは無理がある。人生の選択は報酬の分布が時間とともに変わるし(非定常な問題という)、一度選んだら後戻りできない選択も多い。それでも、「基本方針を持ちつつ、確率的に外れ値を試す」という設計そのものは、思っていた以上に汎用性のある考え方なのかもしれないと、実際にコードを動かしてみて思った。

まとめ

ε-greedy法は、確率1-εで今分かっている中の最善を選び、確率εでランダムに探索するという、驚くほど単純なルールだった。だが多腕バンディット問題で実験してみると、このシンプルなルールの効果は数値としてはっきり現れた。

• 完全greedy(ε=0)は、序盤の「そこそこ良い」結果に固執し、1000ステップ経っても最適行動の選択率は35.95%止まり
• ε=0.1は、たまの探索のおかげで79.31%まで選択率を伸ばす
• ε=0.3は探索し過ぎて、逆にε=0.1より成績が落ちる
• 探索量を徐々に減らす減衰スケジュールが、今回試した中では最も成績が良かった(84.57%)

そして単一の試行を追ってみると、完全greedyがたった1回の序盤の運の良さに引きずられて、本当の最適解に一度も気づかないまま終わるケースを、実際に自分の目で確認できた。

コードを書き始めたときは「これって人生っぽいよね」というただの思いつきだった。でも実際に手を動かして数字とグラフを見た後だと、思いつき以上の実感が残っている。基本の方針を大事にしつつ、たまに、少しだけ確率を割いて、今まで選んだことのない行動を試してみる。それだけで、たどり着ける場所は結構変わるのかもしれない。

• 実践記
• 機械学習

関連記事

• 二重降下を実験で再現した。補間閾値でテスト誤差が76.8倍に跳ね上がり、そこから64分の1まで下がったが、シンプルな次数5モデルには最後まで届かなかった
• 「破局的忘却」を実際に起こしてみたら、Task A精度は0.9834から0.0000まで消えた。10%のリハーサルでも一度は9.9%まで沈んでから戻ってきた
• 自分のブログ53記事をUMAPで並べてみたら、「実践記」と「Claude入門」はきれいには分かれなかった