第5章:確率的最短経路問題 - 静的
章の概要
グラフ上の最短路問題は、輸送、物流、通信で生じる重要な応用分野であると同時に、他の多くの設定でも現れる基本的な問題クラスでもある。最もよく知られた最短路問題は、図 5.1 に示す古典的な決定論的問題であり、ノード1からノード11までの最良経路を、各アークを通過するコストが事前にわかっている状態で見つける必要がある。
本章では、移動時間が既知かつ固定である最短路問題から始める。この決定論的バージョンにより、ベルマン方程式を用いた決定の下し方の特定の手法を示すことができる。その後、非常に特定の方法で不確実性を導入し、近似動的計画法として知られる解法戦略を示す。
ナラティブ
あなたは、混雑したネットワーク上で目的地まで自動運転車両を誘導するナビゲーションシステムを構築しようとしている。このシステムは過去のリンクコストとリアルタイムのリンクコストの両方にアクセスでき、そこからリンクを通過するコストの平均と分散を推定できると仮定する。これは、実際のコストではなく分布を見る最短路問題として考えることができ、図 5.2 に示す通りである。
まずは、これらの分布に基づいてどのリンクを通過するかの決定を下さなければならないと仮定する。$i$から$j$へのリンクを通過した後、その分布からのサンプル実現値を経験する。期待コストを最小化する経路を選びたい。
問題の枠組み
3つの枠組みの質問への回答は以下の通りである。
- 指標: 旅行者の起点から指定された目的地までの期待移動時間を最小化したい。
- 決定: 旅行者が特定のノード$i$にいるとき、最終的な目的地に至るために、どの下流ノード$j$に移動するかを決定する必要がある。
- 不確実性: 不確実性のない決定論的な問題と、移動時間が不確実だが旅行者が特定のリンクを通過することを確定する直前に判明するバージョンの両方を考える。
基本モデル
ノード$q$から始まり、目的地$r$で終わる、図 5.2 のネットワークを通過しようとしていると仮定する。
記法
最短路問題は、基本的な動的計画法の再帰式に基づいている。$\Ncal$をネットワーク内の全ノードの集合(ノード$1, 2, \ldots, 11$)とし、$\Ncal^+_i$をノード$i$から直接到達できる全ノードの集合とし、$\Ncal^-_j$をノード$j$に接続されている全ノードの集合とし、$\Lcal$をネットワーク内の全リンク$(i,j)$の集合とし、$c_{ij}$をリンク$(i,j)$を通過するコストとする。ここで$j$は集合$\Ncal^+_i$に含まれるものと仮定する。
$v_i$をノード$i$から目的地ノード11までの最小コストとする。全てのノード$i\in\Ncal$について、値$v_i$は以下を満たすべきである。
\[\begin{align} v_i = \min_{j\in\Ncal^+_i} (c_{ij} + v_j). \label{eq:shortestpathbellman1} \end{align}\]式$\eqref{eq:shortestpathbellman1}$を実行するには、$v_{11}$をゼロに初期化し、他の全ての値をある大きな数に設定すればよい。全てのノード$i$をループし、式$\eqref{eq:shortestpathbellman1}$を繰り返し用いて$v_i$を計算すると、値$v_i$は最適値に収束する。これは最短路アルゴリズムとしては非常に非効率なバージョンである。
このネットワークを見る別の方法は、各ノード$i$を状態$S$とみなし、$V_t(S_t)$を「時刻」$t$における状態$S_t$にいることの価値とすることである。この最短路問題では、$t$を用いて、ノード1から$S_t$が表すノードまでの経路上で通過したリンク数を添字づける。
状態(ノード)$S_t$から、「$x$」と呼ぶ決定を下すと仮定する。これは、状態$S_t$に対応するノードから出発するリンクを通過するという決定である。この決定の集合を$\Xcal_s$と書くことができ、状態$S_t = s$にいるときに利用可能な決定$x$を表す。
次に、$C(s,x)$を状態$s$にいて決定$x$を選んだ場合のコストとする。これは、上記のネットワークにおけるリンクコスト$c_{ij}$に対応する。最後に、状態$s$にいて行動$x\in\Xcal_s$をとった場合にどの状態に遷移するかを示す「状態遷移関数」を$S^M(s,x)$と表記する。
この記法を用いると、式$\eqref{eq:shortestpathbellman1}$を次のように書き直すことができる。
\[\begin{align} V_t(s) = \min_{x\in\Xcal_s} \big(C(s,x) + V_{t+1}(S_{t+1})\big). \label{eq:shortestpathbellman2} \end{align}\]ここで$S_{t+1} = S^M(s,x)$である。式$\eqref{eq:shortestpathbellman2}$を実行するには、十分大きな値の$T$(すなわち、経路上で通過しうる最大のリンク数)に対して$V_T(s) = 0$を設定すればよい。$T$を大きく設定しすぎる可能性があるため、$\Xcal_s$の選択肢の集合に、時刻$T$において目的地ノードに留まる能力を追加する必要がある。その後、$t=T-1$を設定し、全ての状態$s$について$\eqref{eq:shortestpathbellman2}$を実行する。これを$t=0$に到達するまで繰り返す。このようにシステムを実行すると、時間添字$t$は実質的にこれまで通過したリンク数を数えるカウンタとなる。
式$\eqref{eq:shortestpathbellman2}$は、ベルマン方程式として知られるものの決定論的バージョンである。本章の残りの部分では、ベルマン方程式を用いて最短路問題における不確実性を扱う方法を示す。
状態変数
この基本問題では、状態$S_t=N_t$は$t$回のリンク通過後に位置しているノードである。単に旅行者がノード$N_t$にいると言いたくなるが、拡張のところで見るように、わずかな変更でより豊かな状態変数が生じるため、旅行者の真の状態を正しく認識することが重要である。
決定変数
決定は、ノード$i$にいる際に移動する先のノード$j$としてモデル化する。この問題クラスに取り組む大きなコミュニティが存在し、そこでは決定は行動$a$として表現され、$a$は状態$s$にいるときに集合$\Acal_s$内の離散値のいずれかをとる。
決定を表現する便利な方法は次のように定義することである。
\[x_{tij} = \begin{cases} 1 & \text{if we traverse link } i \text{ to } j \text{ when we are at } i, \\ 0 & \text{otherwise.} \end{cases}\]この記法は、目的関数を書く際に有用であることがわかる。
外生情報
リンク$(i,j)$を通過した後、$\chat_{tij}$を観測する。これは、$t$回目の通過の際に$i$から$j$へ移動する際に経験するコストであり(通過後にのみ観測される)。ここでは、新しい観測値$\chat_{tij}$が非常に大きなデータベースに保存されると仮定する。これらを用いて、リンク$(i,j)$を通過する平均コスト$\cbar_{ij}$を推定できる($\cbar_{ij}$に対する添字$t$を除外しているのは、これがリンク$(i,j)$を通過する時刻に関わらない平均コストであるためである)。
遷移関数
この基本的なグラフ問題では、決定$x_{tij}=1$を下すと、状態$N_t = i$は状態$N_{t+1} = j$へと遷移する。
目的関数
コストを次の記法を用いてモデル化できる。$\chat_{tij}$はノード$i$からノード$j$へ移動するコストを与える確率変数であり、$\cbar_{ij}$は過去の移動コストのデータベースを平均することにより計算される$\chat_{tij}$の期待値の推定値であり、$\sigmabar_{ij}$は履歴データを用いて計算される$\cbar_{ij}$の標準偏差の推定値である。
ノード$i$から出るどのリンクを通過するかの決定は、確率的コスト$\chat_{tij}$の実際の値を見る前に下さなければならないと仮定する。これは、$\chat_{tij}$の最良の推定値、つまり$\cbar_{ij}$を用いて決定を下さなければならないことを意味する。
次を用いて目的関数を書くこともできるだろう。
\[\min_{x_{tij}, (i,j)\in\Lcal} \sum_{t=0}^T \sum_{i\in\Ncal} \sum_{j\in\Ncal^+_i} \chat_{tij}x_{tij},\]しかし、この定式化では実現値$\chat_{tij}$を知っている必要がある。代わりに、期待値を用いることにし、次を得る。
\[\begin{align} \min_{x_{tij}, (i,j)\in\Lcal} \sum_{t=0}^T\sum_{i\in\Ncal} \sum_{j\in\Ncal^+_i} \cbar_{ij}x_{tij}. \label{shortestpathobjective1} \end{align}\]この問題の最適解は全ての$x_{tij} = 0$をゼロにすることであり、これは経路が得られないことを意味する。このため、次の形式の制約を導入する必要がある。
\[\begin{align} \sum_{j\in\Ncal^+_q} x_{tqj} &= 1, \label{shortestpathobjective2}\\ \sum_{i\in\Ncal^-_r} x_{t-1,ir} &= 1, \label{shortestpathobjective3}\\ \sum_{i\in\Ncal^-_j} x_{t-1,ij} - \sum_{k\in\Ncal^+_j} x_{tjk} &= 0, \quad \text{for } j \ne q, r, \label{shortestpathobjective4}\\ x_{tij} &\geq 0, \quad (i,j) \in \Lcal,\ 0 \leq t \leq T. \label{shortestpathobjective5} \end{align}\]式$\eqref{shortestpathobjective1}$–$\eqref{shortestpathobjective5}$は線形計画問題を表しており、この形式で書かれた場合にこの問題を解くための強力なパッケージが存在する。しかし、問題の構造を利用して非常に高速な解を生成する専用アルゴリズム(単に「最短路アルゴリズム」として知られる)も存在する。
しかし、このアプローチは不確実性を扱う方法を提供しない。以下では、方策設計の言語を用いて確率的最短路問題を解く方法を説明し、不確実性への対処の基礎を提供する。
不確実性のモデル化
基本モデルでは、点推定値$\cbar_{ij}$のみを使用しており、これは例えばGPS対応スマートフォンから収集された移動コスト推定値などの過去の観測値の平均であると仮定する。推定値がフィールド観測に基づいている場合、この手法はデータ駆動と呼ばれ、不確実性のモデルを必要とせず、単にそれを観測すればよいことを意味する。
例えば、$\cbar_{ij}$をリンク$(i,j)$の平均移動コストの現在の推定値とし、コスト$\chat_{tij}$を今観測したと仮定する。次を用いて推定値を更新することができる。
\[\cbar_{ij} \leftarrow (1-\alpha) \cbar_{ij} + \alpha \chat_{tij},\]ここで$\alpha$は、1未満の平滑化パラメータ(学習率やステップサイズと呼ばれることもある)である。
このように推定値を更新すると、推定移動時間のベクトル$\cbar$は動的に変化することになるが、更新は旅行中ではなく毎日1回だけ行うかもしれない。本モデリング枠組みでは、コスト推定値のベクトル$\cbar$は初期状態$S_0$に取り込まれる。$n$を旅行の日数の添字とすると、$\cbar^n$は最初の$n$日間のデータを用いたコスト推定値となり、これは日$n+1$の計画時の初期状態$S^n_0$に保持される。
方策の設計
この決定論的問題に対する「方策」は、「状態」(すなわちどのノードにいるか)を行動(どのリンクを移動するか)に写す関数である。式$\eqref{shortestpathobjective1}$–$\eqref{shortestpathobjective5}$で表される線形計画問題を最適化することでこの問題を解くことができ、全てのリンク$(i,j)$に対するベクトル$x^\ast _{ij}$が得られる。これを、状態(ノード$i$)が与えられたときに行動を選ぶ関数として考えることができ、その行動は$x_{ij} = 1$となるリンク$(i,j)$である。この方策を関数$X^\pi(S_t)$として次のように書くことができる。
\[X^\pi(S_t=N_t=i) = j \quad \text{if } x_{ij} = 1.\]あるいは、最初に決定論的最短路問題に対して行ったように、式$\eqref{eq:shortestpathbellman1}$を用いてベルマン方程式を解くこともできる。これにより、各ノード$i$から目的地ノード$r$までの最小移動コストである値$v_i$が得られる。これらの値が計算されれば、次の方策を用いて決定を下すことができる。
\[\begin{align} X^\pi(i) = \argmin_{j\in\Ncal^+_i} (\cbar_{ij} + v_j). \label{eq:shortestpathbellman3} \end{align}\]これは、我々の「確率的」最短路問題が、決定論的問題を解いたのと全く同じように解けることを意味する。以下の拡張では、わずかなひねりを加えることで状況が劇的に変わることを示す。
方策の評価
この問題に対する方策評価は、方策が最適であるため必要ない。リンクコストが確率的であっても、決定を下すまで実際のコストについて何も学ばない限り、最適な決定は決定論的最短路問題を解くことに帰着する。これは本書でこのような問題を見る最後の機会となる。
拡張のところでは、近似動的計画法(強化学習としても知られる)と呼ばれる強力なアルゴリズム戦略を導入できるような形で不確実性を導入する。
拡張 - 適応的確率的最短路
我々は、決定を下す際に利用できる情報を変更していきます。最初の確率的最短路問題では、リンク上の実際の移動コストを観測する前に、次に通過するリンクを選択しなければならないと仮定していました。今度は、リンクコストを観測した後に決定を下すと仮定します。つまり、期待値(あるいは平均)$\cbar_{ij}$ではなく、実際のコスト$\chat_{ij}$を使って決定を下すということです。これを図5.3に示します。ノード6にいる旅行者は、ノード6から出るリンクの実際のコストを見ることができます(分布についての知識だけではありません)。
もし、ノード$j$から目的地ノード$r$までの最小移動コストである値$v_j$を、誰かが我々に与えてくれると仮定するなら、次の下流ノードを選ぶための最適方策は以下のように書けます
\[\begin{align} X^\pi(i) = \argmin_{j\in\Ncal^+_i} (\chat_{ij} + v_j). \label{eq:shortestpathbellman4} \end{align}\]ここでの問題は、以前に式$\eqref{eq:shortestpathbellman1}$を使って行ったのと同じ方法では$v_j$を計算できないということです。実際、決定を下す前にコストを見るという設定への変更は、我々の基本モデルに根本的な変更を要求します。
決定論的モデル、あるいは静的確率モデルでは、「$t$」回の遷移後の状態変数$S_t$は旅行者がいるノード$i$でした。これがその時点で必要な唯一の情報でした。
我々の新しい確率モデルでは、旅行者がいるノードを捉えるだけではもはや十分ではありません。上で、状態変数を「時刻$t$以降のシステムをモデル化するために、履歴から時刻$t$に必要なすべての情報」として導入したことを思い出してください。後で第7章にて、より正確な定義を示しますが、今のところこれで十分です。
我々の新しい確率的最短路問題は、決定を下すために必要な新しい情報――現在いるノードから出るコスト――を導入します。ここで、2種類の状態変数を導入することが便利であるとわかります:通常決定によって直接制御されるシステムの物理状態である$N_t$と、決定を下すために必要なその他の情報である$I_t$です。ネットワーク問題において、物理状態は現在いるノードであり、「その他の情報」変数$I_t$は現在いるノードから出るリンクのコストを捉えるもので、これを以下のように書きます
\[I_t = (\chat_{tij}), i=N_t, j\in\Ncal^+_i.\]時刻$t$において$N_t = i$であると仮定します。リンクコストの添字に時刻$t$を追加します。つまり$\chat_{ij}$を$\chat_{tij}$に置き換えて、時刻$t$に$i$から$j$に移動する際のコストを表します。すると次のように書けます
\[S_t = (N_t, I_t) = \big(i, (\chat_{tij})_{j\in\Ncal^+_i}\big).\]これが我々の以前の最短路問題の解法にどう影響するかを見るために、式$\eqref{eq:shortestpathbellman2}$で最初に導入したベルマン方程式を改めて見てみましょう。これは次のようになります
\[\begin{align} V_t(S_t) = \min_{x_t\in\Xcal_s} \big(C(S_t,x_t) + V_{t+1}(S_{t+1})\big), \label{eq:shortestpathbellman5} \end{align}\]ここで$S_{t+1}$は$S_{t+1} = (N_{t+1}, I_{t+1})$で与えられます。$N_{t+1}$は我々の決定$x$によって生成されるノードであり、例えば$x_{ij} =1$ならば$N_{t+1} = j$となります。また$I_{t+1}$はノード$N_{t+1}$から出た際に観測されるコストであり、これは決定$x_t$に依存します。$x_t$が我々をノード$j$に送るとすると、つまり$N_{t+1} = j$ならば、$I_{t+1} = (\chat_{t+1,jk_1}, \chat_{t+1,jk_2}, \chat_{t+1,jk_3})$となります(ノード$j$から出るリンクが3本あると仮定します)。
$N_t = i$であると仮定します。コスト関数$C(S_t,x)$は次のように与えられます
\[C(S_t,x) = \sum_{j\in\Ncal^+_i} \chat_{tij}x_{ij}.\]$S_t$(ここで$N_t = i$)には、$i$から出るリンク$(i,j)$に対するコスト$\chat_{tij}$が含まれていることを思い出してください。これらは既知であり($S_t$に含まれています)。
式$\eqref{eq:shortestpathbellman5}$は書くのは簡単ですが、状態変数がベクトルになった今、解くのは難しくなっています(これが状態数を爆発的に増加させます)。まず2つの計算上の課題を説明します。次に、事後決定状態というアイデアを導入し、2つの課題のうち1つを解決します。最後に、近似動的計画法(しかし多くの場合強化学習と呼ばれる)として知られる手法の一群を簡単に紹介し、2つ目の課題に対処します。
計算上の課題
まず2つの計算上の課題を確認します:
- 下流ノード$N_{t+1}$(決定$x$によって決まる)から出るリンクコスト$I_{t+1}$は未知です。言い換えれば、$I_{t+1}$は時刻$t$における確率変数であり、これは$V_{t+1}(S_{t+1})$をそもそも計算できないということを意味します。これを解決するために期待値を取り、次のように書きます
期待値演算子$\E$は、決定$x$($N_{t+1}$を決定する)を下した後にノード$N_{t+1}$に到達した旅行者が遭遇しうるリンクコストについての平均を取るものと見るべきです。
これをより明示的に書くために、$x_t$が我々をノード$j$に送る(つまり$x_{tij} = 1$である)と仮定し、到着したときに$I_{t+1} = (\chat_{t+1,jk_1}, \chat_{t+1,jk_2}, \chat_{t+1,jk_3})$を見るとします。これらのコストは時刻$t+1$にノード$j$に到着したときに知ることになりますが、時刻$t$にノード$i$にいて何をすべきか考えている時点では、それらはランダムです。
- 状態空間――コスト$\chat_{t+1,j}$が離散的であると仮定したとしても、状態空間は劇的に増大します。コストを20の値のバケットに離散化したとしましょう。各ノードから出るリンクが3本あるとすると、状態空間はノードの数から、それが$20 \times 20 \times 20 = 8,000$倍大きくなったものへと拡大します。
期待値の計算という課題を説明するために、各コスト$\chat_{t+1,jk}$が確率$p_{jk}(c_{\ell})$で値$c_1, c_2, \ldots, c_L$を取りうると仮定します。例えば、$c_1$は1分、$c_2$は2分などとします。確率$p_{jk}(c_{\ell})$は$\chat_{t+1,jk} = c_\ell$である確率です。
さて、決定$x$が我々をノード$j$に導き、その後リンク$(j,k_1), (j,k_2)$か$(j,k_3)$を移動する選択に直面するとします。我々は期待値を次のように計算するでしょう
\[\begin{align} \E \{V_{t+1}(S_{t+1})\vert S_t,x\} &= \sum_{\ell_1=1}^L p_{jk_1}(c_{\ell_1}) \sum_{\ell_2=1}^L p_{jk_2}(c_{\ell_2}) \sum_{\ell_3=1}^L p_{jk_3}(c_{\ell_3}) \nonumber \\ & \quad \times V_{t+1}(S_{t+1} = (j, (c_{\ell_1},c_{\ell_2},c_{\ell_3}))). \label{eq:shortestpathexpectation} \end{align}\]はっきり言えば、式$\eqref{eq:shortestpathexpectation}$はかなり醜い形です。あの三重和は計算するのが難しいでしょう。
さらに問題を複雑にしているのは、状態空間のサイズです。式$\eqref{eq:shortestpathbellman6}$(あるいは$\eqref{eq:shortestpathbellman2}$)のベルマン方程式を使うには、あらゆる可能な状態$S_t$について$V_t(S_t)$を計算しなければなりません。状態が単にノードであるだけならば、ノードの数が数千(あるいは数万)であってもそれほど問題はありません。しかし、情報変数$I_t$を状態に加えると、問題は劇的に難しくなります。
これが状態空間をどれほど急速に増大させるかを見るために、各コスト変数$\chat_{tij}$に20の可能な値があると想像してみましょう。すると$I_t$には8,000の可能な値があることになります。我々のネットワークに10,000のノードがある場合(つまり$N_t$が10,000の値を取りうる場合)、$S_t$は今度は$10,000 \times 8,000 = 80,000,000$の値を取ることができます。
これは、状態変数がベクトルになった場合に何が起こるかを初めて垣間見るものです。状態変数の可能な値の数は指数的に増大します。これは一般に次元の呪いとして知られている過程です。
事後決定状態の利用
この問題についてはまだ望みが残されています。この特定の問題に対して次元の呪いを克服できる方法があります。式$\eqref{eq:shortestpathbellman6}$のベルマン方程式における主な計算上の課題は期待値演算子であり、これは逐次決定問題を解く上で最も危険な記法であると言っても間違いありません。
この設定においてこの問題を克服するために(そして他の設定にも使うことになる)強力な2つの戦略を用います。まず、$S^x_t$と表記する事後決定状態というアイデアを導入します。事後決定状態とは、決定を下した直後、そして新しい情報が到着する前のシステムの状態であり、これが我々がそれを$t$で添字付けする理由です。
決定前と決定後の状態を見るために、図5.3に戻りましょう。以前見たように、我々の決定前状態(これを「状態」と呼びます)$S_t$は
\[S_t = (6, (12.7, 8.9, 13.5)).\]決定を下した後も、まだノード6にいますが、下した決定がノード9に行くというものだったと想像してください。我々は物理的な事後決定状態を$R^x_t = 9$と記述するかもしれません。これは「ノード9に行く」と言い換えることもできます。しかし、$(\chat_{t+1,6,5}, \chat_{t+1,6,9}, \chat_{t+1,5,7}) = (12.7, 8.9, 13.5)$で与えられる、ノード6から出るリンクのコストについての厄介な観測はもはや必要ありません。つまり、我々の事後決定状態は
\[S^x_t = (9).\]事後決定状態を使って、ベルマン方程式を2つのステップに分解します。式$\eqref{eq:shortestpathbellman6}$のベルマン方程式で行っているように$S_t$から$S_{t+1}$を経て$S_{t+2}$へと進む代わりに、決定前状態$S_t$から事後決定状態$S^x_t$へとまず1ステップ進みます。これは式$\eqref{eq:shortestpathbellman6}$を次のように書き換えることで行います
\[\begin{align} V_t(S_t) = \min_{x\in\Xcal_s} \big(C(S_t,x) + V^x_t(S^x_t) \big), \label{eq:shortestpathbellman6a} \end{align}\]ここで$V^x_t$は事後決定状態$S^x_t$にいることの価値です。もはや期待値がないことに注意してください。なぜなら構成上、事後決定状態は与えられた決定$x_t$(例えば「ノード9に行く」)を含みますが、新しい情報(ランダムな部分)を含まないからです。この場合、事後決定状態$S^x_t$は単にノードだけから成り、これは$S_t$よりもずっと単純であることに注意してください。
まだ問題は解決していません。依然として$V^x_t(S^x_t)$を計算する必要があり、これは次のようにして行われます
\[\begin{align} V^x_t(S^x_t) = \E \{V_{t+1}(S_{t+1})\vert S_t,x\}. \label{eq:shortestpathbellman6b} \end{align}\]したがって、まだあの期待値を計算しなければならず、それは何も簡単になっていません。決定$x$がノード$j$に行くというもの(つまり$x_{ij}=1$を意味する)と仮定し、$j$から出るリンクコストの集合を$\chat_{t+1,j} = (\chat_{t+1,jk},~k\in\Ncal^+_j)$とします。すると次の決定前状態$S_{t+1}$は
\[S_{t+1} = (j, \chat_{t+1,j}).\]さて、$\chat_{t+1,j}$の可能な値をサンプリングする方法があると仮定します。これは、リンクコストの過去の観測データベースから行うかもしれませんし、過去のデータから確率分布を構築してそこからサンプリングするかもしれません。これを反復的に行うことにし、$i$から$j$へのリンクコストの$n$番目のサンプルを$\chat^n_{t+1,ij}$とします。この標本抽出に基づく戦略を使って、正確な値の代わりに期待値の推定値を作ることができます。これは次の節で行います。
近似動的計画法
事後決定状態変数を使うことで、最良の決定$x_t$を見つける際の期待値計算の問題は解決されますが、依然として大きな状態空間を扱う問題が残っています。このために、近似動的計画法として広く知られる手法に目を向けます。ここでは、事後決定価値関数$V^x_t(S^x_t)$を近似で置き換えます。
ノード$j$にいることの価値の近似$\Vbar^x_t(j)$を構築します。ここで
\[\Vbar^{x,n}_t(S^x_t = j) \approx \E \{V_{t+1}(S_{t+1})\vert S^x_t\}.\]$n$個のサンプルを観測した後の$\E \lbrace V_{t+1}(S_{t+1})\vert S^x_t\rbrace $の近似を$\Vbar^{x,n}_t(j)$としましょう。この近似を構築する1つの方法は、ノード$j$にいることの価値のサンプルを使うことです。前回の反復で得られた近似$\Vbar^{x,n-1}_t(S^x_t)$と、サンプリングされたコスト$\chat^n_{tij}$を使って決定を下しながら、ネットワークを前方に通過していくと想像してください。状態$S_t$にいることの価値の標本推定値を次のようにして得ることができます
\[\begin{align} \vhat^{x,n}_t(i) = \min_{j\in\Ncal^+_i} \big(\chat^n_{tij} + \Vbar^{x,n-1}_t(S^x_t = j)\big). \label{eq:vhatsinglepass} \end{align}\]そして、状態$S_t$(ノード$i$とノード$i$から出るすべての$j$に対するコスト$\chat^n_{tij}$の両方を含む)にいることの価値である$\vhat^{x,n}_t(i)$を使って、以前の事後決定状態$S^x_{t-1}$を更新します。これは次のようにして行います
\[\begin{align} \Vbar^{x,n}_{t-1}(i) = (1-\alpha_n) \Vbar^{x,n-1}_{t-1}(i) + \alpha_n \vhat^{x,n}_t(i). \label{eq:vhatsmoothing} \end{align}\]ここで、$\alpha_n$は平滑化係数または学習率として知られていますが、技術的な理由から「ステップサイズ」としても知られています。$\alpha_n = .1$や$.05$のような定数を使うこともできますが、一般的な戦略は次のような減少公式を使うことです
\[\alpha_n = \frac{\theta^\alpha}{\theta^\alpha + n - 1},\]ここで$\theta^\alpha$は調整可能なパラメータです。例えば、$\theta^\alpha = 1$と設定すると、$\alpha_n = 1/n$が得られます。この場合、式$\eqref{eq:vhatsmoothing}$が値$\vhat^n_t(i)$に対して平均化していることを確認することができます。実際には、この公式はステップサイズが減少しすぎるため、この問題ではうまく機能しない可能性が高いです。
ここで、事後決定状態$S^x_t$の利用について2つの利点を述べておきます:
- ノードから出るリンクの選択を最適化する際に、期待値を扱う必要がもはやありません(式$\eqref{eq:vhatsinglepass}$を参照)。
- 事後決定状態$S^x_t$は今度は単にスカラーであるため、価値関数$\Vbar^{x,n}_t(S^x_t = i)$の近似は非常に単純になります。これは、高次元の関数を推定するよりもはるかに簡単です。
式$\eqref{eq:vhatsinglepass}$に関する課題の一つは、$\Vbar^{x,0}_t(i)$の初期値が必要になることである。自然な選択は、コスト$\chat_{tij}$をその平均の推定値に等しく設定した決定論的バージョンの問題を解き、各ノードから目的地までかかるコストの初期推定値を得ることである。
別の方法として、推定値$\Vbar^{x,n-1}(i)$を用いて次式により決定を行うことができる。
\[\begin{align} x^n_t(i) = \argmin_{j\in\Ncal^+_i} \big(\chat^n_{tij} + \Vbar^{x,n-1}_t(j)\big). \label{eq:stochasticpath} \end{align}\]決定$i^n_t = x^n_t(i)$は、サンプリングされたコスト$\chat^n_{tij}$と、ノード$j$から目的地ノード$r$までのコスト$\Vbar^{x,n-1}_t(j)$の推定値に基づいて、ノード$i$の次のノードを与える。$r$に到達したとき、我々は以下のノードから構成される一つの完全な経路を得ている。
\[(q, i^n_1, i^n_2, \ldots, r).\]また、経路全体にわたるサンプリングされたコスト$\chat^n_{t,i^n_t,i^n_{t+1}}$も得られる。経路中に$T$本のリンクがあるとする。次に、$\vhat^n_T(r) = 0$から始めて経路を逆方向にたどりながら、以下を計算する。
\[\begin{align} \vhat^n_t(i^n_t) = \chat^n_{t,i^n_t,i^n_{t+1}} + \vhat^n_{t+1}(i^n_{t+1}). \label{eq:vhatdoublepass} \end{align}\]そして、これらの推定値を式$\eqref{eq:vhatsmoothing}$における平滑化プロセスで用いる。
この手法は近似動的計画法（あるいは強化学習とも呼ばれる）の一形態である。より具体的には、時間を通じて前向きに進行するため、前向き近似動的計画法の一形態である。ここでは、ネットワークを一回だけ通過する式$\eqref{eq:vhatsinglepass}$を用いた純粋な前向きパス手法と、まずグラフを前向きにたどって決定をシミュレートし、その後後ろ向きにたどって各状態にいることの価値を更新する式$\eqref{eq:vhatdoublepass}$を用いた二重パス手法の両方を示した。
この方法は、複雑な決定前状態に対して非常にロバストである。例えば、各ノードから出ているリンクの数がいくつであろうと気にする必要はないが、これは、我々の決定後状態変数が比較的単純である（この場合、単に現在いるノードにすぎない）という事実を活用しているためである。
何を学んだか
- これは、逐次決定問題に対して最適方策を見つけることができる問題に初めて（そして唯一）出会う例である。確率的なネットワークを最適化しているにもかかわらず、旅行者はリンクを通過する前にそのリンクに関する事前情報を一切受け取らないため、期待コストに基づいて選択を行わなければならない。
- 基本モデルは決定論的な最短路問題に帰着するため、これを最適に解くことができる。これは、基本問題を最適に解くことができる稀な例である（実際、本書ではこれが唯一の機会である）。
- 続いて、旅行者がリンクを通過する前にコストが明らかになるという次元を導入した。問題を再定式化し、状態変数が旅行者のいるノードとそのノードから出るリンクのコストから構成される、はるかに複雑なものになることを示した。この問題はもはや動的計画法で厳密に解くことはできない。
- 決定後状態変数の概念を用いた近似動的計画法アルゴリズムを導入し説明した。この概念はベルマン方程式に含まれる期待値を排除し、状態空間をノードの集合のみに縮小する。
- これはVFA方策の一例である。価値関数を厳密に計算できないため、それが最適方策であることを保証することはできない。
演習問題
復習問題
- リンクを通過した後にのみ実際のコストを観測する元の確率的最短路問題において、これが単純な決定論的最短路問題として厳密に解けることを説明せよ。
- どちらの方向に移動するかを選択する前にリンク上の実際のコストを観測するバージョンについて、決定前状態変数と決定後状態変数を示せ。
- 式$\eqref{eq:vhatsmoothing}$では、状態$S_t$にいることのサンプリングされた値$\vhat^{x,n}_t(i)$を用いて、$\Vbar^{x,n}_{t-1}(i)$で与えられる前の決定後状態にいることの推定値を更新する。この式を説明するための小さな数値例を作成せよ。
問題解決演習
- 旅行者が図5.4に示されているグラフをノード1からノード11まで横断する必要がある。各リンクを通過できる確率がグラフ上に示されている（これらの確率は事前に既知である）。旅行者がノード$i$に到着すると、ノード$i$から出ているどのリンクが（もしあれば）通過可能かを見ることができる。通過可能なリンクがない場合、旅は失敗して終了する。目標は、これらの確率の積を最大化する経路を選択することであるが、利用可能なリンクのみを移動することに限定される。
- この問題に適切な状態変数を（表記法とともに）記述せよ。
- 旅行者が経路1-2-6をたどってノード6に到達し、リンク6-9と6-10が利用可能であるが6-8は利用不可能であると分かったとする。彼女の（決定前）状態は何か。(a)で与えた状態変数の数値を示すこと。
- 旅行者がノード9に移動できて、そうすることを決定したとする。この決定を行った後の決定後状態は何か。
- 経路1-2-6をたどった後の決定前状態にいることの価値を、下流の決定前状態を用いて特徴づけるベルマン方程式を書き出せ。1-2-6をたどり、6-9と6-10が利用可能で6-8が利用不可能であると分かった後の状態にいることの価値を数値的に計算せよ。
図5.4. 経路完遂の確率を最大化する最短路問題。 - （この問いは上記の適応的確率的最短路の拡張に関するものである。）決定後状態に対する価値関数近似を適合させる手順を、以下の問いに答えることによって書き出せ。
- 決定前状態と決定後状態を書き出せ。ネットワークに$N$個のノードがあり、各リンク上のコストが20個の値に離散化されているとすると（任意のノードから出るリンクは最大$L$本と仮定する）、決定前状態空間と決定後状態空間の大きさはどれくらいか。
- $\vhat^n_t(i)$を計算するための式を示せ。これは決定前状態にいることの推定値か、それとも決定後状態にいることの推定値か。説明せよ。
- 「時間」インデックス$t$は何を指しているか。
- 決定後状態にいることの価値を更新するための更新式を示せ。
- なぜ決定前状態ではなく決定後状態にいることの価値が必要なのか。
- 図5.5は、Uberドライバーが直面するであろう選択肢を示している。ノード1において、彼女はトリップ(2-4)と(3-5)の選択肢を持つ。トリップは少なくとも15分かかり、10分以内に対応されなければ失われるものとする。これは、ノード6、7、8から出るトリップが、トリップ(2-4)と(3-5)が完了した時点で初めて明らかになることを意味する。
図5.5. Uberドライバーが直面する選択肢を示す決定木。 - 彼女が最初にノード1にいるとき、彼女の（決定前）状態は何か。トリップ(3-5)を受け入れることを決めた後の彼女の決定後状態は何か。
- トリップ(3-5)にサービスした後の（決定前）状態を$s_1$とする。状態$s_1$にいることの価値を$\vhat_1(s_1)$とする。$\vhat_1(s_1)$は何か。
- $s_1$の直前の決定後状態を$s^x_0$とし、$s^x_0$にいることの価値を$\vhat^x_0(s^x_0)$とする。$\vhat^x_0(s^x_0)$は何か。
- 方策を計算する上で、決定前状態よりも決定後状態を用いる計算上の利点は何か。これは一文での回答とすること。
プログラミング演習
これらの演習では、tinyurl.com/sdagithubにあるPythonモジュールStochasticShortestPath_Staticを使用する。
- （この問いは上記の適応的確率的最短路の拡張に関するものである。）現在のアルゴリズムは、拡張で修正された問題を解く際に価値関数近似を推定するための固定された平滑化因子を持っている。以下のように、減少するステップサイズを実装せよ。 $$ \alpha_n = \frac{\theta^{step}}{\theta^{step} + n-1}. $$ $\theta^{step} = (1, 5, 10, 20, 50)$についてPythonモジュールを100回反復実行し、収束速度と最終解の両方の観点から性能を比較せよ。どちらを選ぶか。