※本記事は、Stanford University講師のJoshua Ott氏による大学院講座AA228/CS238: Decision Making under Uncertaintyの講義内容を基に作成されています。この講義は、不確実性下での意思決定を計算的な観点から紹介し、自律システムと意思決定支援システムの構築に必要なツールの概要を提供するものです。講義の詳細情報はStanfordのコースウェブサイト（https://aa228.stanford.edu/ ）でご覧いただけます。

本記事では、講義の内容を要約しております。なお、本記事の内容は原著作者の見解を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義資料をご参照いただくことをお勧めいたします。

【登壇者紹介】 Joshua Ott氏は、Stanford Universityの講師として、確率的モデルと意思決定理論、動的計画法、強化学習、部分観測可能なマルコフ決定過程などの分野で教鞭を執っています。航空管制、航空監視システム、自律走行車、ロボットによる惑星探査など、幅広い応用分野における研究と教育に携わっています。Stanford University School of Engineeringのプロフィールページ（https://profiles.stanford.edu/joshua-ott ）で、より詳細な経歴や研究内容をご覧いただけます。

1. オンラインプランニングとオフラインプランニングの違い

オフラインプランニングとオンラインプランニングの基本的な違いは、状態空間の取り扱い方にあります。オフラインポリシーは、行動を実行する前に全状態空間における行動を事前計算します。一方、オンラインポリシーは、現在の状態から到達可能な状態空間のみを考慮し、その範囲で合理的な行動を決定します。

1.1 到達可能な状態空間の概念

到達可能な状態空間を理解するために、身近な例として人生の選択を考えてみましょう。あなたの人生において、今日から未来に向かって取りうる全ての選択肢が、到達可能な状態空間となります。例えば、特定の仕事のオファーを受けるか、別の都市に引っ越すかといった選択は、あなたの将来の状態を決定する要因となります。

一方で、12歳の時に行った行動や選択は、もはや到達不可能な状態です。ここでスタンフォード大学の学生の多くは高い達成者であることは承知していますが、12歳の時点での選択は、現在の状態からは変更することができません。

チェスゲームを例にとると、現在の盤面から考えられる全ての合法手とその結果として生じる盤面が、到達可能な状態空間となります。例えば、現在の盤面からポーンをd5に動かすことで新しい状態に遷移し、そこから更に新しい状態が広がっていきます。これが到達可能な状態空間です。一方、ゲーム開始時の盤面や序盤の手順は、すでに過去のものとなり、現在の状態からは到達不可能です。

このように、到達可能な状態空間は現在の状態から将来に向かって展開される可能性のある状態の集合として定義され、オンラインプランニングはこの空間に焦点を当てて効率的な意思決定を行います。

1.2 リーディングホライズン計画法の説明

リーディングホライズン計画法は、到達可能な状態空間に基づいて計画を立てる手法です。この手法では、現在の状態から一定の深さまたは地平線（horizon）Dまで先を見て計画を立て、実行に移します。

具体的な手順としては、まず現在の状態から深さDまでの可能な状態遷移を考慮して計画を立てます。次に、その計画に基づいて最初の行動を実行します。例えば、チェスの場合、現在の盤面から複数手先までを読んで、最初の一手を実行することになります。

重要なのは、一つの行動を実行した後の新しい状態から、再び深さDまでの計画を立て直すという点です。これは反復的なプロセスとなり、毎回の行動実行後に新しい計画が立てられます。このように計画の地平線は常に現在の状態から一定の距離を保ちながら先に移動していくため、「リーディング（後退する）ホライズン」と呼ばれています。

このプロセスでは、実際にその地平線まで到達することはありません。なぜなら、一つの行動を実行するたびに新しい状態に移動し、そこから再び同じ深さまでの計画を立て直すからです。つまり、地平線は常に現在の状態から一定の距離を保ちながら先に移動し続けるのです。

このアプローチは、新しい情報が得られるたびに計画を更新できる柔軟性を持っており、動的な環境での意思決定に特に適しています。次のセクションで説明するWaymoの自動運転システムは、このリーディングホライズン計画法の実践的な応用例となっています。

1.3 実世界での応用例 - Waymoの自動運転

リーディングホライズン計画法の実世界での優れた応用例として、Waymoの自動運転システムを紹介します。このシステムでは、車両の現在の計画が緑色の経路として可視化されています。この計画は、新しい情報が入手可能になるたびにリアルタイムで更新されます。

例えば、他の車両が交差点に進入してくるのを検知した場合、システムは即座に計画を修正します。具体的には、まず新しい情報を取り入れ、その情報に基づいて計画を更新し、更新された計画を実行に移します。そして、さらに新しい情報が入手されると、このプロセスを継続的に繰り返します。

この例は、リーディングホライズン計画法がどのように動的な環境で機能するかを示しています。システムは一定の距離（ホライズン）先まで計画を立て、その計画に基づいて行動を実行し、新しい情報が得られるたびに計画を更新します。この継続的な計画の更新と実行のサイクルにより、動的に変化する交通環境に適応することができます。

このように、Waymoの事例は、リーディングホライズン計画法が実世界の複雑な問題に対してどのように適用され、効果的に機能するかを示す良い例となっています。

2. ポリシーロールアウト

オンラインプランニングの基本的な手法の一つとして、ポリシーロールアウトがあります。システム1とシステム2の思考方式に例えると、より多くの時間を探索と計画に費やすほど、より良いポリシーが得られるという共通のテーマがあります。

2.1 ロールアウトに必要な要素(ポリシーとモデル)

ポリシーロールアウトを実行するためには、2つの重要な要素が必要です。

まず1つ目は、ポリシーそのものです。ポリシーπ(s)は、状態sにおいてどのような行動を取るべきかを規定します。ロールアウトに使用されるポリシーは通常確率的なものとなります。つまり、ある状態が与えられたとき、取りうる行動の確率分布として表現されます。このポリシーから行動をサンプリングすることで、実際の行動を決定します。

2つ目に必要な要素は、モデルです。具体的には遷移モデルと報酬モデルの2つが必要となります。遷移モデルは、ある状態で特定の行動を取った場合に、次にどの状態に移行する可能性があるかを定義します。これにより、遷移モデルから次の状態をサンプリングすることができます。また、報酬モデルR(s,a)は、状態sで行動aを取った際に得られる報酬を定義します。

これらの要素が揃うことで、ポリシーロールアウトを実行することができます。ロールアウトでは、現在の状態からポリシーに従って行動をサンプリングし、その行動に基づいて遷移モデルから次の状態をサンプリングし、報酬を得るというプロセスを繰り返します。このプロセスは指定された深さまで継続され、得られた報酬の系列からポリシーの効用を推定することができます。

このように、ポリシーロールアウトは、ポリシーと環境モデルを用いて将来の可能性を探索し、ポリシーの性能を評価するための基本的な手法となっています。

2.2 チェスゲームでのロールアウト例

チェスゲームを例にとって、ポリシーロールアウトの具体的な実施方法を説明します。まず、初期盤面から始めて、私たちのロールアウトポリシーを使用します。このロールアウトポリシーは、単純なランダムな行動選択であっても、チェス専用にオフラインで学習された洗練されたポリシーであっても構いません。

例として、ある盤面状態からロールアウトを開始する場合を考えましょう。まず、私たちのロールアウトポリシー（確率的な方策）から行動をサンプリングします。例えば、「ナイトをe4に移動する」という行動が選択されたとします。次に、遷移モデルから状態遷移をサンプリングします。

ここで重要な点として、対戦相手の戦略も遷移モデルに組み込まれています。対戦相手は完全にランダムに行動を選択するモデルかもしれませんし、より洗練された戦略を持つモデルかもしれません。このモデルを使って、状態遷移をサンプリングし、報酬を受け取り、新しい状態に移行します。

具体例として、ナイトをe4に移動した後、対戦相手がポーンをd5に動かしたとします。この新しい状態から、再びロールアウトポリシーから行動をサンプリングします。今度は「ビショップをd5に移動する」という行動が選択されたとします。その後、遷移モデルから新しい状態をサンプリングすると、対戦相手がクイーンをd5に移動してビショップを取る手が選択され、私たちは負の報酬を受け取ることになります。

このプロセスは、設定された深さまたは地平線dに到達するまで継続されます。このロールアウトの結果として、私たちは状態と行動の軌跡τを得ることができ、その軌跡に沿って受け取った報酬の合計を計算することができます。これにより、特定のロールアウトにおけるポリシーの性能を評価することができます。

このプロセスを複数回実行することで、様々な可能性のある未来を評価し、ポリシーの効用をより正確に推定することができます。各ロールアウトから得られる報酬は、次のセクションで説明する方法で集計され、ポリシーの全体的な効用を推定するために使用されます。

2.3 ポリシーの効用推定方法

特定の軌跡τに沿って得られる報酬は、ロールアウト深さdまでの割引報酬の総和として計算されます。具体的には、時刻t=1からdまでの各時点での報酬に対して割引率γを適用し、それらを合計することで算出されます。

ロールアウトポリシーの効用U(πr)を推定するために、私たちはm回のポリシーロールアウトを実行します。各ロールアウトで得られた軌跡に沿った報酬を平均することで、効用の推定値を得ることができます。数式で表すと、この推定値は1/m multiplied by the sum of rollout trajectoriesとして表現され、m個のロールアウト軌跡から得られた報酬の平均値となります。

この方法では、ロールアウトの回数mを増やすことで推定の精度を向上させることができますが、同時に計算コストも増加します。そのため、推定精度と計算効率のトレードオフを考慮してmの値を適切に設定する必要があります。

このポリシーロールアウトによる効用推定は、次のセクションで説明するオンラインプランニングアルゴリズムの基礎となる重要な要素です。特に、ロールアウトを用いた先読みや、モンテカルロ木探索などのアルゴリズムにおいて、この効用推定方法が活用されています。

3. オンラインプランニングアルゴリズム

オンラインプランニングアルゴリズムには様々な種類があり、それぞれが異なるアプローチで計画を立てます。これから説明する各アルゴリズムは、計算効率と探索の深さのトレードオフに対して異なるアプローチを取っています。

3.1 ロールアウトを用いた先読み

ロールアウトを用いた先読みは、従来の先読み式探索を拡張したアルゴリズムです。従来の先読み方程式は、即時の報酬に割引率を掛けた値と、可能な次の状態への遷移確率と、その状態での効用の積の総和で表されます。この方程式から、状態sでの行動を決定するポリシーを導出することができます。

しかし、この先読み方程式では効用Uを正確に計算する必要があります。ロールアウトを用いた先読みでは、この効用の値をm回のポリシーロールアウトを用いて推定します。具体的には、ある状態s'からロールアウトポリシーを使用してm回のシミュレーションを実行し、その平均値を効用の推定値として使用します。

このアプローチの利点は、完全な効用計算を行う代わりに、ロールアウトによる近似値を使用することで計算効率を改善できる点です。しかし、この手法にも制限があります。まず、すべての可能な行動と次状態の組み合わせに対してm回のロールアウトを実行する必要があるため、状態空間や行動空間が大きい場合は計算コストが高くなります。また、ロールアウトポリシー自体の質が結果に大きく影響します。例えばランダムなロールアウトポリシーを使用した場合、その方策を上回る性能は期待できても、実際の問題に対して十分な性能が得られない可能性があります。

これらの制限を克服するために、次のセクションで説明する前方探索や分枝限定法などの手法が開発されています。

3.2 前方探索と計算量の課題

前方探索は、ロールアウトを使用した近似ではなく、ある深さまでの可能な状態と行動の遷移をすべて探索する手法です。現在の状態から始めて、可能なすべての状態と行動の遷移を木構造として構築していきます。

この手法の計算量を理解するために、3つの状態と2つの行動を持つ例を深さ2まで考えてみましょう。前方探索における分岐係数は、状態空間のサイズと行動空間のサイズの積によって決定されます。この例では、各ステップで状態と行動の組み合わせによって木が分岐していきます。

計算量は、ビッグO記法を用いて O((|S| × |A|)^d) と表現されます。ここで|S|は状態空間のサイズ、|A|は行動空間のサイズ、dは探索の深さを表します。この式からわかるように、前方探索の計算量は探索の深さに対して指数関数的に増加します。私は「SAD」（S times A to the d）という語呂合わせを使って説明することがありますが、これは実際に「悲しい」状況を表しています。なぜなら、探索木が急速に巨大化するためです。

具体例を挙げると、深さ1では3×2=6個のノードが生成され、深さ2では(3×2)^2=36個のノードが必要になります。このように、探索の深さが増えるごとに必要なノード数が指数関数的に増加していきます。この特性により、実世界の大規模な問題、特に状態空間や行動空間が大きい場合には、前方探索の実用性が著しく制限されます。

これらの制約を克服するために、次のセクションで説明する分枝限定法やスパースサンプリングなどの手法が開発されました。これらの手法は、探索空間を効率的に削減したり、サンプリングによって近似したりすることで、計算量の課題に対処しています。

3.3 分枝限定法による改善

分枝限定法は、前方探索の指数的な計算量の課題に対処するために開発されたアルゴリズムです。この手法は、価値関数の上下限に関する情報を利用して探索空間を効率的に削減します。

具体的には、分枝限定法は価値関数の下限と行動価値関数（Q関数）の上限を必要とします。枝刈りは、ある状態における行動の上限値が、既に探索済みの別の行動から得られた下限値よりも低い場合に実行されます。これは直感的には、「最良の場合でもすでに見つかっている解よりも悪い結果しか得られない探索経路は、それ以上探索する価値がない」という考えに基づいています。

例えば、探索木の左側をすでに探索し、そこである効用の最良値（Ubest）を得たとします。次に木の右側を探索する際、その部分木の上限値がUbestより低いことが分かれば、その部分木全体を探索から除外できます。これにより、大幅な計算コストの削減が可能になります。

しかし、分枝限定法には重要な課題があります。それは、価値関数の上下限をどのように設定するかという問題です。ゲーム環境のような場合は、合理的な上下限の推定が比較的容易かもしれませんが、実世界の問題では、特に報酬関数自体をデータから学習する必要がある場合、適切な上下限の設定が困難になります。

もし上下限の設定が適切でない（緩すぎる）場合、枝刈りがほとんど行われず、結果として前方探索と同じO((|S|×|A|)^d)の計算量になってしまいます。このため、分枝限定法の効果は、上下限の設定の質に大きく依存することになります。

実装上は、探索木の構築時に各ノードで上下限のチェックを行い、枝刈りの条件を満たした場合はそれ以上の探索を打ち切ります。このプロセスはダイスローリングゲームなどの具体例で詳しく説明されており、オンラインで公開されているコード例でその実装を確認することができます。

3.4 スパースサンプリング手法

スパースサンプリングは、前方探索の計算量の課題をサンプリングベースのアプローチで解決しようとする手法です。この手法の主なアイデアは、すべての可能な状態遷移を考慮する代わりに、限られた数のサンプルだけを考慮することで計算量を削減することです。

前方探索では状態空間のサイズS×行動空間のサイズAの分岐係数を持っていましたが、スパースサンプリングではこれをm×Aに削減します。ここでmは各状態行動対からサンプリングする状態遷移の数です。この変更により、計算の複雑さはO(m×A^d)となり、状態空間のサイズSに依存しない形に改善されます。

具体的な例を見てみましょう。元の前方探索の探索木では、各行動に対してすべての可能な状態遷移を考慮していました。一方、スパースサンプリングでは、各行動に対して例えば2つの状態遷移だけをサンプリングします。これらのサンプルは点線で表されるように、可能な状態遷移の一部を表現します。

ただし、この手法には重要な考慮点があります。サンプル数mを状態空間のサイズSと同じにしても、前方探索と同じ結果は得られません。なぜなら、同じ状態を複数回サンプリングする可能性があるためです。特に状態空間が大きい場合、すべての可能な状態遷移を網羅的にサンプリングすることは極めて困難です。

したがって、サンプル数mの選択は重要なトレードオフとなります。mが小さすぎると、状態遷移の特性を十分に捉えることができず、精度が低下します。一方、mが大きすぎると計算コストが増加し、スパースサンプリングの利点が失われてしまいます。このトレードオフは問題の性質や要求される精度に応じて適切に調整する必要があります。

3.5 モンテカルロ木探索(MCTS)の詳細

モンテカルロ木探索（MCTS）は、現在の状態からm回のシミュレーションを実行することで、指数的な計算量の問題に対処する実用的なアルゴリズムです。MCTSを実行するためには、前述のポリシーロールアウトと同様に、遷移関数と報酬関数のモデルが必要です。

MCTSでは、探索中に2つの重要な情報を追跡します。1つ目はQ関数の推定値で、もう1つは状態sで行動aを選択した回数Nsa、および状態sを訪れた回数Nsです。

MCTSの実行プロセスは以下の4つのステップで構成されます：

1. 選択：どの行動を更に探索するかを決定します。この選択には上限信頼区間（UCB）指標を使用します。UCB値は行動価値関数Q(s,a)に探索ボーナス項を加えたもので、探索ボーナスは定数C×√(log(Ns)/Nsa)として計算されます。これにより、まだあまり試していない行動に対する探索が促進されます。
2. 拡張：選択した行動に基づいて状態遷移をサンプリングします。
3. シミュレーション：新しい状態からロールアウトを実行します。これは必ずしもランダムな行動選択である必要はなく、オフラインで学習した評価関数を使用することも可能です。
4. 更新：シミュレーションの結果を使って、訪問回数と価値推定値を木の上方向に更新します。

具体例として、2048ゲームでのMCTSの実装を見てみましょう。初期状態から始めて、例えば左に移動する行動を選択した場合、2か4のタイルがランダムに配置された新しい状態に遷移します。その後、その状態から10回のランダムな行動をシミュレーションし、得られた報酬（72）を使って価値推定を更新します。

100回のシミュレーション後の探索木を可視化すると、青い部分が高いQ値、赤い部分が低いQ値を示します。この例では探索木の深さが3程度に留まっていますが、これは2048の状態空間が大きく、同じ状態を再訪問する確率が低いためです。

探索の深さを改善するには、UCBの探索定数Cを調整したり、プログレッシブワイデニング（状態や行動の分岐を制限する手法）を使用したりするなどの工夫が可能です。

UCBを用いた行動選択により、MCTSは探索（まだ十分に試していない行動を試す）と活用（これまでに良い結果を示した行動を選ぶ）のバランスを取ることができます。この特性により、MCTSは大規模な状態空間を持つ問題に対しても実用的なアルゴリズムとなっています。

4. ハイブリッドプランニング手法

オンラインとオフラインのプランニング手法を組み合わせることで、それぞれの利点を活かしながら、より効果的な意思決定が可能になります。この組み合わせアプローチは、特に複雑な問題において優れた性能を示しています。

4.1 AlphaGo Zeroのアーキテクチャ

AlphaGo Zeroは、囲碁においてDeepMindが開発した画期的なシステムです。このシステムは、ニューラルネットワークとモンテカルロ木探索（MCTS）を組み合わせ、さらに自己対戦による学習を導入することで、超人的な性能を達成しました。

システムの動作プロセスは以下の通りです。まず初期状態S1から始まり、エージェントはオフラインで学習したニューラルネットワークとMCTSを使用して探索を行います。この探索から得られたポリシーに基づいて行動をサンプリングし実行します。次の状態では、対戦相手（同じエージェント）が同じニューラルネットワークとMCTS設定を用いて探索を行い、同様にポリシーから行動をサンプリングします。このプロセスはゲームが終了するまで続きます。

ゲーム終了時には、勝者を示す変数Zが得られます。このデータを用いて、ニューラルネットワークの更新を行います。ネットワークは生の盤面状態を入力として受け取り、2つの出力を生成します：行動確率を表すベクトルP1と、現在のプレイヤーが勝利する確率を示す値の推定値です。

実験結果では、AlphaGo Zeroは従来のAlphaGoバージョンと比較して大幅な性能向上を示しました。Eloレーティングによる評価では、生のニューラルネットワークのみを使用した場合と比べて、MCTSを組み合わせたハイブリッドアプローチが著しく高いパフォーマンスを達成しました。これは、直感的な判断（システム1）と深い思考（システム2）を組み合わせることの重要性を示唆しています。

現在でも、生のニューラルネットワークだけで囲碁において超人的な性能を達成した例はありません。DeepMindは2024年初めにサーチを使用せずにチェスでグランドマスターレベルを達成する論文を発表しましたが、囲碁ではまだそのような成果は報告されていません。ただし、これは不可能というわけではなく、将来的には実現される可能性があります。

4.2 システム1とシステム2の思考アナロジー

オンラインプランニングにおける思考プロセスを理解するために、人間の認知システムで知られるシステム1とシステム2の思考アナロジーを用いて説明します。

システム1は、素早い直感的な思考を表します。チェスでの具体例として、ブリッツチェス（bullet chess）を挙げることができます。この形式では、各プレイヤーは1分間という極めて短い持ち時間でゲーム全体を進める必要があります。そのため、プレイヤーは直感と事前に記憶したパターンに頼って、素早く決定を下す必要があります。これは、ニューラルネットワークだけを使用してプレイする場合に似ています。

一方、システム2は、より熟考的で分析的な思考を表します。チェスの文脈では、「もし私がポーンをd5に動かしたら、相手はどう応答するだろうか？その後、私はどう応答すべきか？」というように、複数手先までじっくりと考えを巡らせる思考プロセスです。これは、モンテカルロ木探索のような探索ベースのアプローチに相当します。

AlphaGo Zeroの実験結果が示すように、生のニューラルネットワーク（システム1）だけの場合と比べて、MCTSを組み合わせた場合（システム1＋システム2）の方が大幅に性能が向上します。このことは、直感的な即時判断と深い分析的思考を組み合わせることの重要性を示唆しています。

このシステム1とシステム2の組み合わせは、後述する言語モデルへの応用や、より広範な意思決定問題にも適用可能な重要な概念となっています。

4.3 言語モデルへの応用可能性

現在の言語モデルの構造は、基本的に自己回帰的な次トークン予測に基づいています。入力テキストをトークンに分割し、それまでの系列に基づいて次のトークンを予測するという方式です。これはシステム1的な即時的な判断に相当し、現在の言語モデルはこの直感的な予測に主に依存しています。

しかし、このアプローチをハイブリッドプランニングの観点から拡張することができます。AlphaZero形式のアプローチと同様に、単純な次トークン予測だけでなく、将来の可能なトークン系列を探索することで、より洗練された戦略を構築できる可能性があります。

この分野は現在、急速に発展しています。私が強調したいのは、これが非常に活発な研究領域であり、今この瞬間も多くの研究者がこの方向性で取り組んでいるということです。探索ベースのアプローチを言語モデルに統合することで、より深い思考プロセスを実現できる可能性があります。

ただし、言語モデルへの探索の導入には独自の課題があります。テキスト生成の場合、状態空間は離散的で巨大であり、また「良い」テキストの評価基準も明確に定義することが難しい場合があります。これらの課題に対して、効率的な探索戦略の開発が重要な研究課題となっています。

このように、言語モデルへのハイブリッドプランニングの応用は、システム1とシステム2の思考を組み合わせる新しいアプローチとして、大きな可能性を秘めています。

4.4 訓練時と推論時の計算コストトレードオフ

Andy Jonesによるhexゲームでの研究から、ハイブリッドプランニングにおける訓練時と推論時の計算コストのトレードオフについて、興味深い知見が得られています。この研究では、x軸に訓練時の計算コスト、y軸にテスト時（推論時）の計算コストをとり、特定のEloレーティングを達成するために必要な最小の計算コストの組み合わせを分析しています。

研究結果は、訓練時と推論時の計算コストの間に明確なトレードオフ関係があることを示しています。具体的には、訓練時の計算コストを10分の1に削減した場合、同じ性能を維持するためには推論時の計算コストを15倍に増やす必要があることが分かりました。つまり、10:15の比率でトレードオフが発生します。

この知見は実践的な応用に重要な示唆を与えます。例えば、オフラインでのニューラルネットワークの訓練に多大な投資をしている場合、その一部を推論時の計算リソースに振り替えることで、全体的なコストを最適化できる可能性があります。

このように、ハイブリッドプランニング手法では、オフライン学習とオンライン計算の間で計算リソースをどのように配分するかが重要な設計上の決定となります。システムの要件や利用可能なリソースに応じて、この配分を適切に調整することで、コスト効率を最適化することができます。

5. ポリシー探索

ポリシー探索は、価値関数を直接計算することなく、ポリシーを改善していく手法です。これは、状態空間を直接探索するのではなく、ポリシーのパラメータ空間で探索を行うことで、より効率的な最適化を目指すアプローチです。

5.1 パラメータ化されたポリシーの概念

パラメータ化されたポリシーでは、ポリシーをパラメータベクトルθで表現します。このθは、θ1からθnまでのn個のパラメータで構成されます。パラメータはニューラルネットワークの重みやバイアス、線形関数のパラメータ、その他任意の関数のパラメータとなり得ます。

このパラメータ化されたポリシーは、πθ(s)と表記され、従来のポリシーと同様に状態sを入力として受け取り、その状態での行動を出力します。ただし、このポリシーは特定のパラメータθによって特徴付けられています。

ポリシーの効用（ある意味でポリシーの性能指標）は、U(πθ)またはより簡潔にU(θ)と表現されます。これは、パラメータθで特徴付けられたポリシーの効用を表しています。この効用は、先に説明したポリシーロールアウトを使用して推定することができます。具体的には、現在のパラメータθを持つポリシーを使用してm回のロールアウトを実行し、それらの報酬の平均を取ることで効用を推定します。

このアプローチの利点は、ポリシーのパラメータ空間が、多くの場合、状態空間よりも低次元であり、より効率的に探索できることにあります。ただし、このアプローチを効果的に実装するためには、適切なパラメータ表現の選択と、効率的な探索戦略の設計が重要となります。これらについては、次のセクションで説明する局所探索法や交差エントロピー法などの具体的な手法で対処していきます。

5.2 局所探索法とその限界

局所探索は、現在のポリシーパラメータから小さな変更を加えることで、より良いパラメータを見つけ出す手法です。二つのパラメータθ1とθ2を持つポリシーを例に説明しましょう。

局所探索では、まず中心点（現在のパラメータ）から始めて、各パラメータ方向にプラスとマイナスのステップを取ります。具体的には、ステップサイズαを用いて、θ1方向に+αと-α、θ2方向に+αと-αの変化を加えた点を評価します。これにより、各パラメータ次元について2つ、合計2n個（nはパラメータ数）の候補点が生成されます。

背景には真の効用関数が存在しますが、これは私たちには未知です。各候補点でm回のポリシーロールアウトを実行し、その効用を推定します。最も高い効用を示した点に移動し、そこから再び同じプロセスを繰り返します。

このプロセスは、周囲の点がすべて現在の点よりも悪い効用を示すまで続きます。その時点で、ステップサイズαを縮小し、より細かい探索を行います。これを収束条件を満たすまで繰り返します。

しかし、この手法には重要な制限があります。各候補点について複数回のロールアウトを実行する必要があるため、パラメータ数が多い場合は計算コストが非常に高くなります。例えば、ニューラルネットワークのような数百万のパラメータを持つモデルでは、現実的ではありません。

また、初期のステップサイズαの設定も課題となります。大きすぎると重要な領域を見落とす可能性があり、小さすぎると局所的な改善に時間がかかりすぎます。

これらの制限を克服するために、次のセクションで説明する交差エントロピー法のような、より効率的な探索手法が開発されています。

5.3 交差エントロピー法による改善

交差エントロピー法は、局所探索の弱点を改善するために探索分布pθ(ψ)を導入します。ここでθはポリシーのパラメータベクトルです。例えばガウス分布を使用する場合、この分布は平均と共分散によってパラメータ化されます。

具体的なプロセスを説明しましょう。まず、探索分布から複数のサンプルを取得します。これらは白い点として可視化できます。次に、各サンプルに対してポリシーロールアウトを実行して効用を推定します。最も高い効用を示したサンプル（赤い点で表示）に基づいて、探索分布を更新します。

この例では、初期の探索分布（白い等高線で表示）からkサンプルを取得し、それらを評価した後、最も性能の良かったサンプルに基づいて分布を再フィットします。この過程を繰り返すことで、探索分布は徐々により良い領域に収束していきます。

ただし、ここで重要なトレードオフが存在します。最良のサンプルをどれだけ保持するかという選択です。多すぎると探索分布の更新が遅くなり、少なすぎると分布が早すぎる収束を起こしてしまいます。このバランスは問題の性質に応じて適切に調整する必要があります。

この手法は局所探索と比べて、複数のパラメータを同時に更新でき、探索分布を通じて不確実性も考慮できるという利点があります。また、サンプル数kを調整することで、計算リソースと探索の効率性のバランスを取ることができます。

Stanford AA228/CS238 Decision Making Under Uncertainty I Online Planning and Policy Search

October 22, 2024 Joshua Ott: https://profiles.stanford.edu/joshua-ott This lecture is from the Stanford graduate course AA228/CS238: Decision Making under Uncertainty This course introduces decision making under uncertainty from a computational perspective and provides an overview of the necessary tools for building autonomous and decision-support systems. Following an introduction to probabilistic models and decision theory, the course will cover computational methods for solving decision problems with stochastic dynamics, model uncertainty, and imperfect state information. Topics include Bayesian networks, influence diagrams, dynamic programming, reinforcement learning, and partially observable Markov decision processes. Applications cover air traffic control, aviation surveillance systems, autonomous vehicles, and robotic planetary exploration. Guest Lecture Slides: https://drive.google.com/file/d/19OVXd6oQfbaUMTTM1JbToIpCkBf9plh1/view View the course website: https://aa228.stanford.edu/ Enroll in the course: https://online.stanford.edu/courses/aa228-decision-making-under-uncertainty

youtu.be