第13章:血液管理問題

章の概要

血液管理問題は、8種類の異なる血液型を管理しつつ、血液がどれだけの期間保存されているか(冷凍されていない限り)も追跡する必要があるため、多次元の資源配分問題である。これは、各時点で決定を下すために線形計画法のようなツールを利用しなければならない最初の例である。

まず、単純な線形計画問題を解くことを伴う近視眼的方策を説明することから始める。この方策は、現在の決定が将来に与える影響を理解しない決定を無視するものである。血液管理においては、これは万能供血者として知られる$O-$型血液の管理において生じうる――この血液型はどの患者にも使用できる。他の型が不足する場合に備えて$O-$型血液の予備を保持しておくことが役立つ。

続いて、現在の報酬と将来の報酬のバランスを取るための近似動的計画法の利用を実演する。多次元問題にADPを用いるためには、将来の一連の血液在庫の価値の近似を設計する際に、問題の構造を活用する。この考え方は、問題の構造を利用できる場合に有効である。

ナラティブ

血液在庫を管理するという問題は、資源配分問題を特にエレガントに説明する例として役立つ。まずは、単一の病院で在庫を管理していると仮定することから始める。この病院では毎週、翌週に対応すべき需要にどの血液在庫を充てるべきかを決定しなければならない。

血液についていくらか背景知識から始める必要がある。血液在庫の管理という目的のためには、主として血液型と血液の経過週数に関心がある。二人の個人の血液には広範な違いがあるものの、ほとんどの目的において医師は8つの主要血液型――$A+$(“A型陽性”)、$A-$(“A型陰性”)、$B+$、$B-$、$AB+$、$AB-$、$O+$、$O-$――に着目する。異なる血液型を代替できるかどうかは手術の性質に依存し得るが、ほとんどの目的においては表13.1に従って血液を代替することができる。

血液の第二の重要な特性はその経過週数である。血液の保存は6週間に限られ、それを超えると廃棄しなければならない。病院は、その限界に達する前に血液を使用できるかどうかを予測する必要がある。使用できないと判断される場合、その血液は、地域内の各病院の在庫を監視する血液センターに移送することができるからである。病院ができるだけ早期に不要となる血液を特定できれば、その血液を不足している場所へ移送するのに役立つ。

問題の枠組み

3つの枠組み設定の質問に対する答えは以下の通りである。

• メトリクス: ある型の血液を別の型の需要を満たすために割り当てることに対するボーナスからペナルティを差し引いた期待合計を最大化する。
• 決定: ある型の血液を別の型の血液需要にどれだけ割り当てるか、また各血液型についてどれだけ在庫として保持するか。
• 不確実性: 各血液型の将来の需要、および各血液型の献血量。

基本モデル

状態変数

血液問題は、異種資源配分問題としてモデル化することができる。まずはかなり基本的なモデルから始めるが、これはほとんど記法を変えることなく容易に拡張できる。まず、保存された血液1単位の属性を用いて記述する。

そして$\Bcal$をすべての血液属性型の集合とする。年齢は範囲$0 \leq b_2 \leq 6$に限定する。$b_2 = 6$(これはすでに6週間経過した血液を意味する)の血液は、もはや使用できない。決定エポックは1週間刻みで行われると仮定する。血液在庫は$R_{tb}$を用いて表され、これは時刻$t$において割り当てまたは保持が可能な$b$型血液の単位数であり、$R_t = (R_{tb})_{b\in\Bcal}$を満たす。

血液需要の属性は次式で与えられる。

そして$\Acal$を血液需要のすべての属性型の集合とする。属性$a_3$は、医師がいかなる代替も許可しない手術があるという事実を捉えている。一例は出産であり、乳児は許容される代替であっても異なる血液型に耐えられない場合があるためである。この基本モデルでは、ある週の未充足需要が後の週に持ち越されることは許されない。

続いて、$D_{ta}$を用いて血液需要を定義する。これは、時刻$t$において属性$a$を持つ患者に必要とされる血液の単位数であり、$D_t = (D_{ta})_{a\in\Acal}$を満たす。

状態変数は次式で与えられる。

決定変数

血液資源に対する行動は決定$d$によって与えられる。これは決定の種類であり、属性$a\in\Acal$を持つ患者に血液を与える決定や、何もせず血液を保持する決定を含み、後者は$d^\phi$で表す。また$\Dcal$はすべての可能な決定の集合であり、$\Dcal = \Acal \cup d^\phi$である。

続いて$x_{tbd}$を、時刻$t$において決定種類$d$で行動する対象となる属性$b$の血液単位数とし、$x_t = (x_{tbd})_{b\in\Bcal,d\in\Dcal}$を満たすとする。

実行可能領域$\Xcal_t$は以下の制約によって定義される。

外生情報

決定を下した後に到着する情報は献血によって与えられ、これを$\Rhat_{t+1,b}$を用いて表す。これは$t$から$t+1$の間に献血された新しい$b$型血液の単位数であり、$\Rhat_{t+1} = (\Rhat_{t+1,b})_{b\in\Bcal}$を満たす。

新たな血液需要は$\Dhat_{t+1,a}$を用いてモデル化される。これは$t$から$t+1$の間に発生した属性$a$を持つ需要の単位数であり、$\Dhat_{t+1} = (\Dhat_{t+1,a})_{a\in\Acal}$を満たす。

外生情報変数は以下のようになる。

遷移関数

保持された血液は単に1週間分だけ経過するが、年齢は6週間に限定される。需要を満たすために割り当てられた血液は、血液型シンク――おそらく$b_{t,1} = \phi$(null血液型)を用いて表される――に移動したものとしてモデル化できる。血液属性遷移関数$b^M(b_t,d_t)$は次式で与えられる。

遷移関数を表すために、次のように定義すると便利である。

そして$\Delta$を、行$b’$・列$(b,d)$に$\delta_{b’}(b,d)$を持つ行列とする。

属性遷移関数は決定論的であることに注意する。ランダムな要素が生じる例としては、血液の検査により、6週間未満であっても期限切れと判定される場合が挙げられる。資源遷移関数は次のように書くことができる。

行列形式では、これらは次のように書かれる。

需要$D_{t+1}$は、新たな需要$\Dhat_{t+1}$から単に観測されるものであるため、次のように記述する。

図13.1は週$t$に生じている遷移を示している。需要を満たすためにどの型の血液を使用するかを決めるか(図13.1a)、あるいは翌週まで血液を保持するかのいずれかである。血液を需要充足のために使用する場合、それはシステムから失われるものとみなされる。血液を翌週まで保持する場合、その血液は1週間分年齢を重ねた血液に変換される。6週間経過した血液はいかなる需要も満たすために使用できないため、6週間経過した血液のバケツは使用不可能な血液のシンクと見なすことができる(この血液の価値はゼロとなる)。なお、献血は年齢0で到着すると仮定される。

図13.1で表されるモデルは、資源配分問題にとって非常に有用である。我々はこのモデルを、流通センター間の製造製品の配分の最適化や、貨物輸送におけるトラック、貨車、機関車の配分の最適化に非常に成功裏に利用してきた。価値関数近似を推定する際には注意が必要であるが、いったん推定されれば、その利用によって図に示されているような非常に小さなネットワーク問題の連続が生成される。

目的関数

ある型の血液を別の型の需要に割り当てることに実質的な「コスト」は存在しない(追加の献血を促すための資金支出や、ある病院から別の病院への在庫の輸送といった手段は考慮していない)。その代わり、貢献関数を用いて医師の選好を捉える。代替を行わない方が一般に望ましいこと、そして緊急の需要を満たすことは選択的な需要よりも重要であるという自然な選好を捉えたい。

例えば、表13.2に記載されている貢献を用いることができる。したがって、$A+$型血液を必要とする選択的患者の需要を満たすために$O-$型血液を使用する場合、血液代替に対する-＄10の貢献(負であるためペナルティ)、$O-$型血液の使用に対する+＄5の貢献(病院が奨励したいもの)、そして選択的需要を満たすことに対する+＄20の貢献を受け取り、合計+＄15の貢献となる。

総貢献(時刻$t$における)は最終的に次式で与えられる。

これまでと同様に、$X^\pi_t(S_t)$を、$S_t$が与えられたときに$x_t\in\Xcal_t$を決定するある種の決定規則である方策とする。以下を解くことで最良の方策を求めたい。

ここで$S_{t+1} = S^M(S_t,X^\pi(S_t),W_{t+1})$である。

不確実性のモデリング

この問題における不確実性の発生源は、献血、および血液を必要とする新たな手術の発生である。この不確実性をモデル化する際に考慮すべきいくつかの問題は以下の通りである。

• 献血される単位数にランダム性があるだけでなく、血液型にもランダム性がある。
• 献血には曜日パターンと季節パターンの両方があり、また呼びかけに対する反応もある。これはもちろん決定を表すものである。
• 新たな手術の発生は、天候や暴力事件により急増することがある。
• 献血する人々の型と手術を必要とする人々の型との間には一貫した不一致があり、これは血液型の分布の違いとして現れる。
• 大きな課題は血液型の代替を管理することである。$O-$型血液を誰にでも使用できることには多くの注意が払われているが、すべての血液型に対して異なる種類の代替が存在する。

方策の設計

まず基本的な近視眼的方策から始め、その後、将来の血液在庫の価値を近似することに依拠する方策へと移行する。

近視眼的方策

この問題を解く最も明白な方法は、単純な近視眼的方策であり、各時点での貢献を最大化する一方で、将来に対する決定の影響を考慮しない。1期間の貢献を調整することで、近視眼的方策の族を得ることができる。

例えば、（表13.2において）$O-$血液を使用することに対する＄5のボーナスは、実際にはある種の近視眼的方策である。$O-$血液は他の血液型より一般に入手しやすいため、その使用を促している。このボーナスを変化させることで、集合$\Pi^M$で表される異なる種類の近視眼的方策を得ることができ、$\pi\in\Pi^M$に対して、我々の決定関数は次式で与えられる。

$\eqref{eq:bloodmyopic}$の最適化問題は単純な線形計画問題である。式$\eqref{eq:bloodobjective}$で与えられる最適化問題における方策の探索とは、$O-$血液を使用することに対するボーナスの異なる値を探索することを意味する。

VFA方策

伝統的な動的計画法として捉えると、式$\eqref{eq:bloodobjective}$で提示された最適化問題は非常に手強い。状態変数$S_t$は$\vert \Acal\vert + \vert \Bcal\vert = 8 \times 6 + 8 \times 2 \times 2 = 80$次元を持つ。確率変数$\Rhat$と$\Dhat$も合わせて80次元を持つ。決定ベクトル$x_t$は$27 + 8 = 35$次元を持つ。

価値関数近似を用いて、以下の式によって配分ベクトル$x_t$を決定するのは自然なことである。

ここで$R^x_t = R^M(R_t,x_t)$は式$\eqref{eq:bloodresourcetransition1}$で与えられ、$\Xcal^n_t$は制約$\eqref{eq:blood1}$～$\eqref{eq:blood3}$によって定義される。鍵となる制約は$\eqref{eq:blood1}$であり、これは各血液型の供給の可用性を制限する。

我々が直面する最初の（そして最も重要な）課題は、$\Vbar^{x,n-1}_t(R^x_t)$に対する適切な近似戦略を特定することである。単純かつ効果的な近似は、分離可能な区分線形近似を用いることであり、すなわち

ここで$\Vbar^x_{tb}(R^x_{tb})$は、各血液型$b$についての決定後在庫$R^x_{tb}$に関するスカラーの区分線形関数である。

価値関数が凹（かつ区分線形）であることは容易に示せるので、各$\Vbar^x_{tb}(R^x_{tb})$も凹であるはずである。一般性を失うことなく、$R^x_{tb} = 0$に対して$\Vbar^x_{tb}(R^x_{tb}) = 0$と仮定でき、これは関数がその傾きの集合によって完全に特徴づけられることを意味する。この関数は次式を用いて書くことができる。

ここで$\lfloor R \rfloor$は$R$以下の最大整数である。見てわかるように、この関数は$r = 0, 1, \ldots, R^{max}$に対する傾きの集合$(\vbar^{n-1}_{tb}(r))$によって決まり、$R^{max}$は特定の種類の資源数の上限である。

$\Vbar_t(R_t)$における傾きを推定する方法は、時刻$t$における問題に対する目的関数を作成することである。

この線形計画問題を解くと、$R^n_{ta}$で与えられる、$a$型の血液1単位を追加した場合の限界価値の推定値が得られる。この値を$\vhat^n_{ta}$と呼び、これは任意の線形計画法パッケージから即座に得られる（そして、すべての血液型$a$について同時に得られる）。

あるいは、摂動を加えた資源ベクトル$R^{n+}_{ta} = R^n_{ta} +1$を作成することで、限界価値をより正確に計算することもできる。$\Xcal^{n+}_t(a)$を（式$\eqref{eq:blood1}$～$\eqref{eq:blood3}$からなる）実行可能領域とし、単一の属性$a$について$R^n_{ta}$の代わりに$R^{n+}_{ta}$を用いるものとする。また、$\Vtilde^+_{ta}(S_t)$を$\Vtilde_t(S_t)$と同じものとするが、実行可能領域$\Xcal^{n+}_{ta}$については$R^n_{ta}$の代わりに摂動を加えた資源$R^{n+}_{ta}$を用いる。すると、限界価値$\vhat^n_{ta}$は次式を用いて求めることができる。

各$a$について$\Vtilde^+_{ta}(S_t)$を計算しなければならないことに注意されたい（一方、双対変数を用いれば、限界価値の集合全体を一度に得ることができる）。

そして、$\vhat^n_{ta}$を用いて、直前の決定後価値関数近似$\vbar^{x,n}_{t-1,a}$を更新するが、これは次式で行われる。

傾き$\vbar^{x,n}_{ta}(R^{x,n}_{ta})$は$R^{x,n}_{ta}$が増加するにつれて減少することが示せるので、これを維持しておくと役立つ。これはCAVEアルゴリズムやLevelingアルゴリズムなどの手法を用いて行うことができる（Reinforcement Learning and Stochastic Optimization、18.3節を参照）。

この関数を推定できると仮定すると、解かなければならない最適化問題（式$\eqref{eq:adpblood}$）は、図13.2に示すようなかなり控えめな線形計画問題である。図13.1と同様に、異なる種類の血液を異なる種類の需要に割り当てることと、血液を保有する決定の両方を考慮しなければならない。

図を簡略化するため、異なる需要タイプのネットワークを、需要$\Dhat_t$を持つ単一の集約ボックスにまとめている。このネットワークは実際には図13.1aのネットワークとまったく同じように見えるだろう。血液を保有する決定は、（年齢を含む）ある種類の血液の将来における価値を考慮しなければならず、我々はこれを分離可能な区分線形価値関数を用いて近似している。

ここでは、分離可能な区分線形価値関数近似を、$R^x_t$の各要素を表すノードからスーパーシンクへの一連の並列リンクに変換する、標準的なモデリングのテクニックを用いる。区分線形関数は解くのが容易である（線形計画法ソルバーへのアクセスさえあればよい）だけでなく、推定するのも容易である。さらに、多くの（すべてではないが）問題クラスにおいて、高品質な解とともに非常に高速な収束をもたらすことがわかっている。

この決定関数を用いて、近似価値反復と呼ばれる手法を使用する。これは、時間期間$t=0, \ldots, T$を通じて反復的に前方シミュレーションを行うものである。$n = 1, \ldots, N$を反復カウンタとし、外生情報$W^n_t,~t=0, \ldots, T$の標本経路（これらは履歴から抽出されるか、分布からサンプリングされる場合がある）に従うものとする。時刻$t$、反復$n$において、状態$S^n_t$にあるとき、式$\eqref{eq:adpblood}$を用いて決定$x^n_t$を行う。そして$W^n_{t+1}$を観測し、遷移関数（式$\eqref{eq:bloodresourcetransition1}$～$\eqref{eq:bloodresourcetransition2}$）を用いて$R^n_t$から$R^n_{t+1}$への遷移を行う。状態$S^n_t = (R^n_t, \Dhat^n_t)$にあるとき、式$\eqref{eq:adpblood}$のVFA方策を用いて$x^n_t$を計算し、続いて$\vhat^n_t$を計算して傾き$\vbar^{x,n}_{t-1}$を更新する。それから$W^n_{t+1}$（$\Dhat^n_{t+1}$を含む）を観測して、状態$S^n_{t+1}$へ遷移する。

ほとんどの運用上の応用では、この問題は有限の計画期間（例えば10週間）にわたって解かれ、今すぐ何をすべきかについての推奨が得られる。価値関数近似$\Vbar^x_t(R^x_t)$を用いて方策を何度もシミュレーションすることができ、これを用いて将来の在庫についての確率的予測の一形態を生成することができる。

拡張

これは豊かで複雑な資源配分問題であり、いくつかの方法で拡張することができる。以下にいくつかの例を示す。

1) 時刻$t$に満たされない需要はすべて失われると仮定している。満たさなければならない緊急手術と、後の時間期間に延期できる待機手術があると想像してみよう。この新しい問題の状態変数を書き出しなさい。

2) 待機手術を延期できると仮定する。血液在庫について区分線形かつ分離可能な価値関数近似（これが上で提案したVFAである）を使用することに加えて、保留された需要量（血液型別）についても区分線形かつ分離可能なVFAを使用することを考える。血液在庫に対する双対変数を用いて、血液供給に対するVFAを更新する。保留された需要に対するVFAはどのように更新すればよいだろうか？

3) 冷凍された血液の存在と、血液を冷凍する決定を含め、使用されなかった冷凍血液は廃棄しなければならないものとする。これは、手術に必要な血液量が手術前には未知であり、血液を解凍する決定を下さなければならないことを認識する必要があることを意味する。

4) 病院は、系統的な不足を補うために、地域血液銀行からの毎週の血液配送を必要とするかもしれない。毎週固定量（例えば100単位）の血液が到着するが、各型・各年齢（血液はすでに数週間在庫として保有されていた可能性がある）の血液の量はランダムであるかもしれないと想像してみよう。

5) 我々は単一の病院における血液在庫のみに焦点を当てたモデルを提示した。位置属性を単に追加し、（コストをかけて）ある場所から別の場所へ血液を移動させる決定を設けることで、複数の病院と配送センターを扱うことができる。

このモデルは、異なる種類の製品と異なる種類の需要が存在し、どの種類の製品をどの種類の需要に割り当てるかを選択できる限り、任意の多製品在庫問題にも適用できる。また、製品は再利用不可能であり、一度需要に割り当てられた製品はシステムから失われると仮定している。

何を学んだか

• 極めて大きな状態空間を持つが、価値関数の近似において活用できる凹性という構造を提供する、多次元資源配分問題を導入した。
• 多属性資源配分問題をモデル化する方法を示し、これにより追加の属性を導入することがかなり容易になる。
• 現在下した決定の下流への影響を無視する基本的な近視眼的方策を例示した。
• 続いて、問題が本来持つ凹性を活用して、分離可能な区分線形価値関数近似に基づく近似を提案するVFA方策を説明した。
• 我々のVFA方策はローリングベースで実装しなければならないため、我々の方策は実際には確率的DLAであり、先読み方策としてVFA方策を用いている。これは、第6章における確率的・動的最短経路問題の近似を表す決定論的最短経路問題を解くために動的計画法を使用したことと類似している。

演習問題

復習問題

1. 状態変数$S_t$の次元は何か？
2. 決定ベクトル$x_t$の次元は何か？
3. 不確実性の源は何か？
4. 目的関数におけるコストの性質を説明せよ。これらはどこから来るのか？
5. 純粋な近視眼的方策の限界は何か？より優れた方策からどのような振る舞いを期待するか？
6. 価値関数の使用は解をどのように改善するか？

問題解決演習

1. 血液管理 - パートI：モデリング - 血液管理問題を考えるが、血液の種類は1種類のみと仮定する。ただし、依然として加齢過程をモデル化し、血液は0～5週間の古さになり得るものとする。保有されている5週間経過した血液は廃棄しなければならない。本文と同様に、患者には緊急と待機の2種類がある。以下を定義する。

   $R_{t\tau}$	時刻$t$において$\tau$時間期間保有されている手持ちの血液の単位数、$\tau = 0, \ldots, 5$。
   $\Rhat_t$	$t-1$と$t$の間に到着する新しい献血、ここで$\Rhat_t$はスカラーである。
   $\Dhat^{urgent}_t$	時刻$t$に到着する新しい緊急需要。
   $\Dhat^{elective}_t$	時刻$t$に到着する新しい待機需要。

   時刻$t$において、以下を決定しなければならない。

   $x^{urgent}_t$	緊急患者に割り当てられる血液量。
   $x^{elective}_t$	待機患者に割り当てられる血液量。
   $x^{hold}_t$	保有される血液量。
   $x_t$	$(x^{urgent}_t,x^{elective}_t,x^{hold}_t)$。

   需要は必ずしも満たされる必要はないが、本当の問題は、（すべての緊急需要を満たすのに十分な血液があると仮定した上で）今、待機需要を満たすか、それとも将来の潜在的な緊急需要のために血液を保有しておくかである。これまでと同様に、満たされない需要はシステムから離脱すると仮定する。

あなたの目標は、緊急患者を1人カバーするごとに10、待機患者を1人カバーするごとに5の得点を与える効用関数を最大化することです。

1. この問題の状態変数は何ですか?
2. 決定変数と外生情報は何ですか?
3. 遷移関数は何ですか?
4. 目的関数は何ですか?方策をシミュレータ内でシミュレートできると仮定してください。
5. 各決定に対して以下のコストを割り当てる、パラメータ化されたコスト関数近似を作成してください:$c^{urgent}$は緊急患者をカバーしなかったことへのペナルティ、$c^{elective}$は待機患者をカバーしなかったことへのペナルティ、$c^{discard}$は5週間の日齢を超えた血液を廃棄することへのペナルティです。 方策として、各時間period(時間ステップ)においてこれらのコストを最小化すると仮定してください。ベクトル$c=(c^{urgent},c^{elective},c^{discard})$を調整可能なパラメータの集合として扱ってください。確率的勾配アルゴリズムを用いてベクトル$c$を最適化する方法を説明してください。確率的勾配を計算するための式を必ず示してください。

</li>

</ol>

プログラミング演習

これらの演習問題では、tinyurl.com/sdagithubにあるPythonモジュール BloodManagement を使用します。

1. 我々の目標は、異なる血液型を異なる患者へ割り当てることを管理することです。患者はまず自身の血液型によって、次に手術が緊急であるか待機であるかによって特徴づけられます。

   この演習問題では、2種類の方策クラスを扱います:近視眼的なパラメータ化コスト関数近似と、価値関数近似に基づく方策です。

   まず、異なる血液型を異なる需要に単純に一致させると仮定することから始めます。血液は血液型(8種類あります)と日齢によって記述され、日齢は0週から2週の範囲です(3週齢の血液は廃棄されます)。患者は血液型と、手術が緊急か待機かによって記述されます。割り当てを導くための様々なボーナスとペナルティがあります。例えば、緊急患者をカバーすることには正のボーナスがあります(これが最も高い)。また、血液型が完全に一致した場合(例えば、A型陽性の血液をA型陽性の患者に使う場合)にもボーナスがあり、血液が古くなりすぎて廃棄される場合にはペナルティがあります。

   もし今の決定が将来に与える影響を無視すれば、これらのボーナスによって与えられるコストを用いて供給と需要を一致させる単純な線形計画問題になります。問題は、今の決定が将来に与える影響を無視することで、最善を尽くせていない可能性があるということです。1つの問題は、待機手術に今血液を使ってしまうと、後で緊急手術用の血液が不足した場合に備えて保持しておく価値を無視してしまうことです。あるいは、将来他の血液型が不足するかもしれない場合に備えて保持しておくのではなく、今O型陰性の血液を使ってしまうかもしれません。

   $R_{ta}$を、週$t$における属性$a$を持つ血液の供給とし、$R_t = (R_{ta})_{a\in\Acal}$とします。ここで$\Acal$は、すべての異なる血液属性(血液型と日齢)の集合です。同様に、$D_{tb}$を患者の属性とし、$b$が血液型と手術が緊急か待機かを捉えるとし、$D_t = (D_{tb})_{b\in\Bcal}$とします。システムの状態は$S_t = (R_t,D_t)$です。

   次に、$\Rhat_{t+1,a}$を、週$t$から週$t+1$の間に献血された、属性$a$を持つ血液の単位数とします。同様に、$\Dhat_{t+1,b}$を、属性$b$を持つ新規患者到着数とします。以下のように書くことができます

   $$ W_{t+1} = (\Rhat_{t+1,a},\Dhat_{t+1,b}). $$

   最後に、$\omega$を、$T$週間の計画期間にわたる献血および新規患者のサンプルパス$W_1(\omega), \ldots, W_T(\omega)$を表すものとします。$W_t$のシミュレーション群を作成済みであると仮定し、$\Omega=(\omega_1, \ldots, \omega_N)$をこのサンプル実現値の集合とします。

   1. 状態変数$S_t$はいくつの次元を持ちますか?
   2. $X^\pi(S_t\vert \theta)$を、状態$S_t$が与えられたときに線形計画問題を解いた結果とし、$\theta$を、様々な割り当てに対するすべてのボーナスとペナルティのベクトルとします。$D^{urgent}_t(x_t)$を、決定ベクトル$x_t$が与えられたときにカバーされた緊急患者数とし、$D^{elective}_t(x_t)$をカバーされた待機患者数とします。$\Omega$内のサンプルパスに対する平均として、通常の期待値の代わりに書くことで、$\theta$の最良値を見つける問題を最適化問題として書いてください。
   3. 需要が時折急増する確率があるデータセットを検討します。この確率はスプレッドシート内で設定できます。この急増確率を50パーセントに設定してください。緊急手術のために血液を保持しておくよう近視眼的モデルを促すため、待機手術に血液を使うことへの特別なペナルティがあります。20回のテスト反復を実行した後、集合$\lbrace -4,-9,-14,-19,-24\rbrace $の中からこのペナルティの最良値を見つけてください。
   4. 追加の数値作業を行わずに、O型陰性血液へのペナルティが季節変動を扱うために週ごとに変化する必要があると想像してください。15週間をシミュレートしているので、15次元のベクトルを最適化する方法を記述してください(前の課題で2つの中心的な戦略を説明しました - どちらかを選択するか、新しい方法を考案してください)。

2. 次に、VFAベースの方策に切り替えます。ここでは、将来のために保持される各血液型(と日齢)の限界価値を使用します。これは、上記のVFA方策の節で説明した適応学習アルゴリズムを用いて行われます(決定がベクトルである問題に対して行っているという点を除けば、最短経路問題に対する我々のADP戦略と非常によく似ています)。

   待機手術に血液を使うことへのペナルティを0に設定してください。VFAベースの方策を使う場合、VFAは供給を超える緊急用血液が将来必要になり得ることを学習するはずです。VFA方策を使用する際には、価値関数を推定するために20回の訓練反復を実行する必要があります。これらが推定された後、方策の質を評価するために20回のテスト反復を実行します。

   需要が時折急増する確率があるデータセットに対して、我々の方策をテストします。この確率はスプレッドシート内で設定できます。まず、この急増確率を0.7に設定してください。

   1. 適応学習アルゴリズムでは、各血液型の限界価値を推定する必要があります。$\vhat^n_{ta}$を、サンプルパス$\omega^n$をシミュレートしている間の、週$t$における血液型$a$の限界価値の推定値とします。 $\Vbar^{n-1}_t(R_{ta})$を、$n-1$回の反復後の、$t$週の終わりにおける$r$番目の単位の血液($r = R^x_{ta}$である)の限界価値の推定値とします(これが我々の「事後決定」状態変数です)。前の事後決定状態変数の周りで価値関数近似を更新するために$\vhat^n_{ta}$を使用することを思い出してください。この更新過程を以下のように書きます $$ \Vbar^n_{t-1,a}(R^{x,n}_{t-1,a}) = (1-\alpha) \Vbar^{n-1}_{t-1,a}(R^{x,n}_{t-1,a}) + \alpha \vhat^n_{ta}. $$ 我々の最初の課題は$\alpha$を調整することです。$\alpha \in \lbrace 0, 0.05, 0.1, 0.2, 0.3\rbrace $について、近似動的計画法アルゴリズムを20回反復実行し(スプレッドシートはこのように設定されています)、結果を報告してください。ステップサイズ$\alpha = 0$を使うことは、価値関数近似をゼロに保つこと(言い換えれば近視眼的方策)と同じであることに注意してください。$\alpha = 0$の場合、VFAを訓練する必要はなく、方策を評価するために20回のテスト反復を実行するだけで済みます。 VFA方策は、近視眼的方策($\alpha = 0$に対応する)と比べてどの程度うまく機能しますか?
   2. 次に、急増確率をゼロに切り替え、ステップサイズ$\alpha = 0.2$を用いて近視眼的方策とVFA方策を比較してください。これらはどのように比較されますか?このデータセットにおける挙動と、急増があった場合の挙動との違いを説明できますか?