動的な離散選択

動的離散選択 (DDC) モデルは、動的計画法の離散選択モデル とも呼ばれ、将来に影響を与える離散オプションに対するエージェントの選択をモデル化します。観察された選択が静的効用最大化の結果であると仮定するのではなく、DDC モデルで観察された選択は、離散選択モデルのベースとなる効用理論を一般化して、エージェントの効用の現在価値の最大化の結果であると仮定されます。^[1]

DDC 法の目的は、エージェントの意思決定プロセスの構造パラメータを推定することです。これらのパラメータがわかれば、研究者は推定値を使用して、エージェントが世界の反事実状態でどのように動作するかをシミュレートできます。(たとえば、将来の大学生の入学決定が授業料の値上げに応じてどのように変化するかなど)

エージェントの最大化問題は数学的に次のように記述できます。 ${\displaystyle n}$

${\displaystyle V\left(x_{n0}\right)=\max _{\left\{d_{nt}\right\}_{t=1}^{T}}\mathbb {E} \left(\sum _{t^{\prime }=t}^{T}\sum _{i=1}^{J}\beta ^{t'-t}\left(d_{nt}=i\right)U_{nit}\left(x_{nt},\varepsilon _{nit}\right)\right),}$

どこ

• ${\displaystyle x_{nt}}$は状態変数であり、エージェントの初期状態は${\displaystyle x_{n0}}$
• ${\displaystyle d_{nt}}$離散的な選択肢の中からの決定を表す${\displaystyle n}$${\displaystyle J}$
• ${\displaystyle \beta \in \left(0,1\right)}$割引率
• ${\displaystyle U_{nit}}$は、期間に代替案を選択することで効用者が 受け取るフローであり、状態と観測されない要因の両方に依存する。${\displaystyle n}$${\displaystyle i}$${\displaystyle t}$${\displaystyle x_{nt}}$${\displaystyle \varepsilon _{nit}}$
• ${\displaystyle T}$時間軸は
• 期待値は、 の との両方に引き継がれます。つまり、エージェントは状態の将来の遷移について不確実であり、観測されていない要因の将来の実現についても不確実です。${\displaystyle \mathbb {E} \left(\cdot \right)}$${\displaystyle x_{nt}}$${\displaystyle \varepsilon _{nit}}$${\displaystyle U_{nit}}$

動的決定問題には、次のような単純化された仮定と表記法を適用するのが標準です。

1. フローユーティリティは加法的に分離可能であり、パラメータに対して線形である

フロー効用は、決定論的要素と確率論的要素からなる加法的な合計として表すことができます。決定論的要素は、構造パラメータの線形関数として表すことができます。

${\displaystyle {\begin{alignedat}{5}U_{nit}\left(x_{nt},\varepsilon _{nit}\right)&&\;=\;&&u_{nit}&&\;+\;&&\varepsilon _{nit}\\&&\;=\;&&X_{nt}\alpha _{i}&&\;+\;&&\varepsilon _{nit}\end{alignedat}}}$

2. 最適化問題はベルマン方程式として記述できる

直前の期間の個体の事前価値関数によって定義します。 ${\displaystyle V_{nt}(x_{nt})}$${\displaystyle n}$${\displaystyle t}$${\displaystyle \varepsilon _{nt}}$

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{u_{nit}(x_{nt})+\varepsilon _{nit}+\beta \int _{x_{t+1}}V_{nt+1}(x_{nt+1})\,dF\left(x_{t+1}\mid x_{t}\right)\right\}}$

ここで、期待値演算子は 上で、 は の条件付きでの確率分布を表します。状態遷移の期待値は、この確率分布を積分することで得られます。 ${\displaystyle \mathbb {E} }$${\displaystyle \varepsilon }$${\displaystyle dF\left(x_{t+1}\mid x_{t}\right)}$${\displaystyle x_{t+1}}$${\displaystyle x_{t}}$

決定論的要素と確率論的要素に 分解することが可能です。${\displaystyle V_{nt}(x_{nt})}$

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{v_{nit}(x_{nt})+\varepsilon _{nit}\right\}}$

ここで、時刻における代替案を選択する価値は次のように表される。 ${\displaystyle v_{nit}}$${\displaystyle i}$${\displaystyle t}$

${\displaystyle v_{nit}(x_{nt})=u_{nit}\left(x_{nt}\right)+\beta \int _{x_{t+1}}\mathbb {E} \max _{j}\left\{v_{njt+1}(x_{nt+1})+\varepsilon _{njt+1}\right\}\,dF(x_{t+1}\mid x_{t})}$

ここで、期待は今や引き継がれています。 ${\displaystyle \mathbb {E} }$${\displaystyle \varepsilon _{njt+1}}$

3. 最適化問題はマルコフ決定過程に従う

状態はマルコフ連鎖に従います。つまり、状態の達成は状態のみに依存し、以前の状態には依存しません。 ${\displaystyle x_{t}}$${\displaystyle x_{t}}$${\displaystyle x_{t-1}}$${\displaystyle x_{t-2}}$

前のセクションの価値関数は、期間 に選択肢を選択することを条件とする価値関数であるため、条件付き価値関数と呼ばれます。条件付き価値関数をこのように記述すると、選択確率の式を作成するときに役立ちます。 ${\displaystyle i}$${\displaystyle t}$

選択確率を書き出すには、研究者は の分布について仮定を立てる必要があります。静的離散選択モデルの場合と同様に、この分布は、iidタイプ I 極値、一般化極値、多項プロビット、または混合ロジットであると仮定できます。 ${\displaystyle \varepsilon _{nit}}$

が多項ロジット（つまり、タイプI極値分布から抽出されたiid ）の場合、選択確率の式は次のようになります。 ${\displaystyle \varepsilon _{nit}}$

${\displaystyle P_{nit}={\frac {\exp(v_{nit})}{\sum _{j=1}^{J}\exp(v_{njt})}}}$

動的離散選択モデルの推定は、研究者が構造パラメータの推測ごとに後方再帰問題を解決しなければならないため、特に困難です。

構造パラメータを推定するために使用される最も一般的な方法は、最大尤度推定法とシミュレートモーメント法です。

推定法の他に、解法もあります。問題の複雑さに応じて、異なる解法が採用されます。これらは、完全解法と非解法に分けられます。

完全解法の最も代表的な例は、1987年にジョン・ラストが開発したネストされた固定小数点（NFXP）アルゴリズムです^。[2] NFXPアルゴリズムについては、ドキュメントマニュアルで詳細に説明されています。^[3]

2012 年のChe-Lin Su とKenneth Juddによる最近の研究^[4]では、別のアプローチ (1987 年に Rust によって解決不可能として却下された) を実装しています。このアプローチでは、尤度関数の制約付き最適化を使用します。これは、均衡制約付き数理計画法(MPEC)の特殊なケースです。具体的には、尤度関数はモデルによって課される制約に従って最大化され、モデルの構造を記述する追加の変数で表現されます。このアプローチでは、最適化問題が高次元であるため、 Artelys Knitroなどの強力な最適化ソフトウェアが必要です。このアプローチが解決されると、尤度を最大化する構造パラメータとモデルの解の両方が見つかります。

後の論文^[5]では、Rustと共著者は、NFXPと比較したMPECの速度上の利点はそれほど大きくないことを示しています。しかし、MPECに必要な計算はモデルの構造に依存しないため、その実装ははるかに労力がかかりません。

数多くの候補があるにもかかわらず、NFXP最大尤度推定量はマルコフ決定モデルの主要な推定方法であり続けています。^[5]

完全解決法の代替として、非解決法があります。この場合、研究者は各パラメータ推定の逆再帰問題を完全に解決することなく、構造パラメータを推定できます。非解決法は通常、より多くの仮定を必要としますが、より高速です。ただし、追加の仮定は多くの場合現実的です。

主要な非解法は、V.ジョセフ・ホッツとロバート・A・ミラーによって開発された条件付き選択確率である。^[6]

画期的な論文Rust（1987）で開発されたバスエンジン交換モデルは、実際のデータを使用して推定された離散選択の最初の動的確率モデルの一つであり、この種の問題の古典的な例として今も機能し続けています。^[4]

このモデルは、ウィスコンシン州マディソンのマディソンメトロポリタンバス会社の保守管理者であるハロルド・ザーチャー氏が直面する、単純な再生最適停止確率動的問題です。ハロルド・ザーチャー氏は、各期間に運行されているすべてのバスについて、エンジンを交換して関連する交換費用を負担するか、故障の場合の保険や乗客損失の費用を含む、ますます高くなる運行費用でバスの運行を継続するかを決定する必要があります。

期間 における走行距離計の読み（走行距離）、パラメータのベクトル に依存するバスの運行コスト、エンジン交換コスト、割引率を表すとします。この場合、期間ごとの効用は次のように表されます。 ${\displaystyle x_{t}}$${\displaystyle t}$${\displaystyle c(x_{t},\theta )}$${\displaystyle \theta }$${\displaystyle RC}$${\displaystyle \beta }$

${\displaystyle U(x_{t},\xi _{t},d,\theta )={\begin{cases}-c(x_{t},\theta )+\xi _{t,{\text{keep}}},&\\-RC-c(0,\theta )+\xi _{t,{\text{replace}}},&\end{cases}}=u(x_{t},d,\theta )+{\begin{cases}\xi _{t,{\text{keep}}},&{\textrm {if}}\;\;d={\text{keep}},\\\xi _{t,{\text{replace}}},&{\textrm {if}}\;\;d={\text{replace}},\end{cases}}}$

ここで、 は決定（保持または置換）を表し、 は、 ジョン・ラストではなくハロルド・ザーチャーによって観察された効用 の要素を表します。 およびは独立しており、タイプ I 極値分布と同一に分布し、 の条件付きで から独立していると仮定します。 ${\displaystyle d}$${\displaystyle \xi _{t,{\text{keep}}}}$${\displaystyle \xi _{t,{\text{replace}}}}$${\displaystyle \xi _{t,{\text{keep}}}}$${\displaystyle \xi _{t,{\text{replace}}}}$${\displaystyle \xi _{t,\bullet }}$${\displaystyle \xi _{t-1,\bullet }}$${\displaystyle x_{t}}$

すると、最適な決定はベルマン方程式を満たす。

${\displaystyle V(x,\xi ,\theta )=\max _{d={\text{keep}},{\text{replace}}}\left\{u(x,d,\theta )+\xi _{d}+\iint V(x',\xi ',\theta )q(d\xi '\mid x',\theta )p(dx'\mid x,d,\theta )\right\}}$

ここで、およびはそれぞれ観測された状態変数と観測されない状態変数の遷移密度です。モデルは無限時間設定で定式化されているため、ベルマン方程式の時間インデックスは省略され、未知の最適ポリシーは定常、つまり時間に依存しません。 ${\displaystyle p(dx'\mid x,d,\theta )}$${\displaystyle q(d\xi '\mid x',\theta )}$

の分布仮定を前提とすると、特定の選択の確率は次のように与えられる。 ${\displaystyle q(d\xi '\mid x',\theta )}$${\displaystyle d}$

${\displaystyle P(d\mid x,\theta )={\frac {\exp\{u(x,d,\theta )+\beta EV(x,d,\theta )\}}{\sum _{d'\in D(x)}\exp\{u(x,d',\theta )+\beta EV(x,d',\theta )\}}}}$

ここで関数方程式の唯一の解は${\displaystyle EV(x,d,\theta )}$

${\displaystyle EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta ).}$

後者の関数方程式は、状態空間が有界である場合に収縮マッピングを定義することが示され、したがって任意の に対して一意の解が存在し、さらに暗黙の関数定理が成り立つため、 は各 に対しての滑らかな関数でもあります。 ${\displaystyle x_{t}}$${\displaystyle EV(x,d,\theta )}$${\displaystyle \theta }$${\displaystyle EV(x,d,\theta )}$${\displaystyle \theta }$${\displaystyle (x,d)}$

上記の縮約写像は、任意の与えられた値に対する選択確率を与える 固定点について数値的に解くことができる。対数尤度関数は次のように定式化できる。 ${\displaystyle EV(x,d,\theta )}$${\displaystyle P(d\mid x,\theta )}$${\displaystyle \theta }$

${\displaystyle L(\theta )=\sum _{i=1}^{N}\sum _{t=1}^{T_{i}}\log(P(d_{it}\mid x_{it},\theta ))+\log(p(x_{it}\mid x_{it-1},d_{it-1},\theta )),}$

ここで、およびは、各期間における個々のバスの状態変数（走行距離計の読み取り値）と決定（保持または交換）に関するデータを表します。 ${\displaystyle x_{i,t}}$${\displaystyle d_{i,t}}$${\displaystyle i=1,\dots ,N}$${\displaystyle t=1,\dots ,T_{i}}$

特定のパラメータ値を与えられた固定小数点問題を解き、それに対する対数尤度を最大化する結合アルゴリズムは、ジョン・ラストによってネストされた固定小数点アルゴリズム(NFXP) と名付けられました。 ${\displaystyle \theta }$${\displaystyle L(\theta )}$${\displaystyle \theta }$

Rustのネストされた固定小数点アルゴリズムの実装は、この問題に対して高度に最適化されており、ニュートン・カントロビッチ反復法を使用して計算し、ベルント・ホール・ホール・ハウスマンアルゴリズムなどの準ニュートン法を使用して尤度最大化を行います。^[5]${\displaystyle P(d\mid x,\theta )}$

ネストされた固定小数点アルゴリズムでは、パラメータθの推定値ごとに再計算されます。MPEC法は代わりに制約付き最適化問題を解きます: ^[4]${\displaystyle P(d\mid x,\theta )}$

${\displaystyle {\begin{aligned}\max &\qquad L(\theta )&\\{\text{subject to}}&\qquad EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta )\end{aligned}}}$

この方法は、ネストされた固定小数点アルゴリズムの最適化されていない実装よりも計算が速く、高度に最適化された実装とほぼ同じ時間がかかります。^[5]

HotzとMillerの条件付き選択確率法は、この設定に適用できます。Hotz、Miller、Sanders、Smithは、この方法の計算的に簡単なバージョンを提案し、バスエンジン交換問題の研究でテストしました。この方法は、シミュレーションを使用して条件付き選択確率を推定し、価値関数の暗黙の差異をバックアウトすることで機能します。^{[7] [8]}

• 逆強化学習

• Aguirregabiria, Victor; Mira, Pedro (2010). 「動的離散選択構造モデル: 概観」(PDF) . Journal of Econometrics . 156 (1). Elsevier BV: 38–67. doi :10.1016/j.jeconom.2009.09.007. ISSN  0304-4076.
• Keane, Michael P. ; Wolpin, Kenneth I. (2009). 「離散選択動的計画法モデルの経験的応用」. Review of Economic Dynamics . 12 (1): 1–22. doi :10.1016/j.red.2008.07.001.
• ラスト、ジョン(1987)。「GMC バスエンジンの最適交換:ハロルド・ザーチャーの実証モデル」。エコノメトリカ。55 ( 5): 999–1033。doi : 10.2307 /1911259。ISSN 0012-9682。JSTOR  1911259  。
• ラスト、ジョン (1994)。「第 51 章 マルコフ決定過程の構造推定」。計量経済学ハンドブック。第 4 巻。エルゼビア。pp. 3081–3143。doi :10.1016/s1573-4412(05) 80020-0。ISBN 978-0-444-88766-5. ISSN  1573-4412.