探索アルゴリズム

強化学習でいう「探索アルゴリズム」は、エージェントが未知または十分に試していない状態・行動をどのように調べるかを決める方法です。本用語集では、G054「探索と活用」に続く強化学習文脈の語として扱います。したがって、経路探索の幅優先探索（BFS）、A*、木探索など一般的な「search algorithm」を一括して指す項目ではありません。

探索アルゴリズムとは何か

探索と活用が「未知を試すか、既知の最良を使うか」という問題そのものを表すのに対し、探索アルゴリズムはそのうち探索をどう実行するかを具体化します。

最も単純な例：ε-greedy

代表例がε-greedyです。一定確率εでランダムな行動を選び、残りの確率では現在もっとも高い価値を持つと推定される行動を選びます。実装が簡単で、表形式Q学習などの教材でもよく使われます。

しかし、状態空間や行動空間が大きい場合、ランダムに動くだけでは重要な状態へほとんど到達できません。DeepMindのAgent57の説明では、Montezuma’s Revengeのような報酬がまれなゲームでは、単純な無指向性探索が難しいことが示されています。

不確実性を利用する探索

探索すべき場所を「まだよく分かっていないところ」と考える方法があります。行動ごとの価値推定に不確実性を持たせ、その不確実性が大きい選択肢を優先して試します。

multi-armed banditではUpper Confidence Bound（UCB）やThompson samplingなどがこの考え方の代表例です。強化学習では状態遷移が連続するため単純なbanditより複雑ですが、「期待値が高いだけでなく、未知であることにも探索価値がある」という発想は共通しています。

新規性を報酬にする探索

外部報酬がほとんど得られない環境では、未訪問状態や予測しにくい状態へ進んだこと自体に内部報酬を与える方法があります。これはintrinsic motivationやcuriosity-driven explorationと呼ばれる系統です。

BYOL-Exploreの説明では、世界モデルの予測誤差などを利用して新しい情報を求める探索が扱われています。つまり、エージェントに「本来のゲーム得点」とは別に「未知を発見した」という学習用の信号を与えます。

ただし、予測しにくいものが必ずしもタスク達成に役立つとは限りません。ランダムノイズのように永遠に予測しにくい刺激へ引き寄せられる可能性もあるため、内発報酬の設計には注意が必要です。

訪問回数を使う探索

小さな離散状態空間では、各状態や状態・行動対を何回訪れたかを数え、訪問回数が少ない場所へボーナスを与える方法があります。これは「知らない場所＝まだ回数が少ない場所」と定義する考え方です。

大規模・連続空間では同じ状態へ二度と戻らないことも多く、単純なカウントが使えません。そのため、似た状態をまとめる疑似カウントや、ニューラル表現上の新規性を使う方法が研究されてきました。

行動ノイズによる探索

連続制御では、方策が出した行動へノイズを加えて探索することがあります。ロボットの関節トルクや速度指令のように行動が連続値だと、「ランダムに別の離散行動を選ぶ」ε-greedyをそのまま使いにくいためです。

さらに、ニューラルネットワークのパラメータ側へノイズを入れ、一定期間まとまりのある探索行動を生み出す方法もあります。どこへノイズを入れるかによって探索の性質が変わります。

探索アルゴリズムに万能解はない

「最新の探索アルゴリズムを使えば常に良い」というわけではありません。報酬が密に与えられる単純な課題ならε-greedyで十分なことがあります。一方、何百ステップも正しい行動を続けないと報酬が出ないsparse-reward問題では、単純なランダム探索はほとんど成功しません。

また、探索による失敗コストも重要です。シミュレーションのゲームなら大量に失敗できますが、実ロボット、医療、交通では危険な探索を自由に実行できません。この場合はシミュレーション、事前データ、安全制約、human-in-the-loopなどと組み合わせる必要があります。

「探索アルゴリズム」と「探索・計画アルゴリズム」の混同

AIでは「探索」という日本語が複数の英語に対応します。強化学習のexplorationは、未知の経験を得るための行動選択です。一方、A*やMonte Carlo Tree Searchなどのsearchは、既知またはモデル化された候補空間の中で経路や手順を計算する操作です。

モデルベースRLではplanning/searchとexplorationが同じシステム内に登場することがあり、さらに混同しやすくなります。文書中で「exploration algorithm」とあるのか「search algorithm」とあるのかを確認してください。

具体例：鍵を探さないとゴールできないゲーム

ゴールの扉を開けるには、遠く離れた部屋で鍵を取得する必要があるとします。鍵を取るまでは報酬が一切ありません。ε-greedyでたまたま正しい行動列を引く確率が極端に低いと、エージェントは鍵の存在さえ学べません。

新しい部屋へ行くたびに内発報酬を与える探索なら、外部報酬がなくても未訪問エリアを広げやすくなります。鍵の部屋を発見した後にゴール報酬と結びつけば、最終的な方策が学習される可能性が高まります。

元の文脈へ戻ったときの確認ポイント

「exploration algorithm」と書かれていたら、まず何を未知とみなしているかを確認してください。行動価値の不確実性、状態の訪問回数、モデル予測誤差、エピソード内の新規性など、探索信号は方法ごとに異なります。

次に、探索がどの段階で使われるかを見ます。学習時だけなのか、評価時にも残すのか、εやノイズ強度を時間とともに減らすのかが重要です。さらにsparse reward、安全制約、環境の非定常性など、探索が必要な理由も確認します。

探索アルゴリズムの評価では最終報酬だけでなく、どれだけ少ない試行で重要状態へ到達できたか、探索コストや安全性をどう扱ったかまで見ると、元の研究文脈を正しく読みやすくなります。

関連するAI用語

• 探索と活用（G054）
• 状態（強化学習）（G051）
• 価値関数（G053）

注・出典

1. Google DeepMind, Agent57 — epsilon-greedy and directed exploration ↩
2. Google DeepMind, BYOL-Explore — curiosity-driven exploration ↩
3. Google for Developers, Machine Learning Glossary — epsilon greedy policy ↩