第1章:逐次決定問題のモデル化

コンピュータ上で物理的な問題（特に逐次決定問題）を解決するプロセスには、図 1.1 に示すように数理モデルの構築が必要である。何十年もの間、研究コミュニティは、すべてのデータが事前に判明している決定問題（決定論的最適化と呼ばれる）に対して標準的な数学的枠組みを使用してきた。決定論的最適化問題の単純なバージョンである線形計画問題は、次のように書くことができる。

ここで$x$は、通常次のように書かれる一連の制約条件を満たさなければならない要素のベクトルである。

式$\eqref{eq:linearprogram1}$–$\eqref{eq:linearprogram3}$を理解する必要は必ずしもない（それには線形代数の基本的な素養が必要となる）が、毎年何千人もの学生がこの表記法を学び、また幅広い物理的問題をこの表記法に変換する方法を学ぶ課程を卒業している。そして、この形式で表現された問題を解に変換するソフトウェアパッケージが存在する。最も重要な点は、この表記法という言語が世界中で通用しているということである。統計モデリング／機械学習についても同じことが言え、こちらは今日、式$\eqref{eq:linearprogram1}$–$\eqref{eq:linearprogram3}$を理解する人々よりもはるかに大きなコミュニティとなっている。

しかし、逐次決定問題については同じことは言えない。この問題クラスは、少なくとも15の異なるコミュニティによって、8つの根本的に異なる表記スタイルを用いて研究されており、しばしば高度な訓練を要する数学が使われている。本書では、実例を通して教えるスタイルを用い、私たちが逐次決定問題と呼ぶ、驚くほど豊かな問題クラスをどのようにモデル化するかを示す。比較的単純な問題に焦点を当てるが、私たちの枠組みはあらゆる逐次決定問題をモデル化するために使うことができる。さらに、結果として得られるモデルは直接ソフトウェアに変換することができる。

本書の分析的基盤は、方法論を中心とした大学院レベルのテキストである『Reinforcement Learning and Stochastic Optimization: A unified framework for sequential decisions』（RLSO）に含まれている。より深い内容に興味を持つ読者のために、時折この本の内容を参照することがあり、技術的な素養のある読者にはRLSOを参考文献として利用することを勧める。しかし、それは必須ではない。本書は、たとえコードを一行も書くことがないとしても、読者が逐次決定問題について明確かつ精密に考えられるようにする一連の例という形で、文脈的背景を提供するように設計されている。

本書は、確率・統計の講義を受講したことのある学部生または修士課程の学生を対象としている（線形計画法の知識は必要ないが、線形計画問題を解く必要がある例が一つある）。全ての章は特定の例を中心に構成されているが、例外として第1章はモデリング枠組み全体の概観を提供し、第7章では最初の6つの章を用いていくつかの重要な原則を説明するために立ち止まって考察する。

この説明には、確率・統計の最初の講座で期待される以上の数学は必要ないはずである。とはいえ、本書は、コンピュータソフトウェアの基礎となり得るほど精密な表記法を用いて逐次決定問題を記述する方法を示すことを中心に据えている。

ほとんどの章にはPythonモジュールが付属しており、これらのモジュールは本書全体を貫くモデリング枠組みに基づいて書かれている。同時に、どのように解かれるかにかかわらず、逐次決定問題をシミュレートするあらゆるソフトウェアパッケージは、私たちが用いるモデリング枠組みに直接変換することができる。このため、読者にはコンピュータプログラム中の変数として、あらゆる表記法を捉えることを勧める。

はじめに

逐次決定問題は常に次のように書くことができる。

決定を下すたびに、私たちはコストを負担するか、貢献または報酬を受け取る（性能を測定する方法は数多くある）。決定は、私たちが方策と呼ぶことになる方法によって下される。本書全体を通じて中心的な焦点となる大きな目標は、まだ到着していない情報の不確実性が存在する中で、時間をかけてうまく機能する効果的な方策を設計することである。

逐次決定問題はどこにでも存在し、事実上あらゆる人間の過程において生じる。表 1.1 は、生じうる決定のいくつかの例とともに、分野の一覧を示している。これらの分野のほとんどは、資産をいつ売却するか、あるいは新しいウェブデザインを採用するかといったことから、最適な薬、材料、または施設を設計するために何を選ぶか、さらには複雑なサプライチェーンの管理やトラック車両群のディスパッチに至るまで、複雑さの異なる多種多様な決定を持っているだろう。

あらゆる種類の決定を列挙することよりもさらに難しいのは、多くの応用分野で生じる不確実性の様々な源を特定することである。人間の行動、市場、物理的過程、輸送ネットワーク、エネルギーシステム、そして健康分野に生じる幅広い不確実性は、不確実性の源の多様性を示唆している。

本書が執筆されている現在、人類はCOVID-19の変異株の蔓延と格闘している。このパンデミックへの対処は「気が遠くなるほど複雑」（USA Today, 2020年9月8日）と評されているが、これは実際には問題を構造的に考えることができなかったことの副産物にすぎない。私たちは、問題を実践的な解決策につながる一連の基本的な構成要素に分解する方法を読者に示す。

私たちのアプローチは、性能指標、決定、不確実性の源といった中核となる要素を特定することから始まり、それが問題の数理モデルの作成につながる。次の段階は通常（必ずしもそうとは限らないが）、モデルをコンピュータ上に実装することであるが、コンピュータモデルの構築というプロセスが、様々な理由により非現実的な問題も数多く存在するだろう。このため、私たちは現場でアイデアを試験し評価しなければならない問題も検討する。性能を改善するためには、まず時間をかけて良い決定を下す方法を学ぶ必要がある（これがシステムを制御する方法である）。それから、システムの設計へと目を向ける。

現時点では、学術コミュニティは逐次決定問題に対する標準的なモデリング過程を採用していない。これは、1950年代以来厳格な枠組みに従ってきた静的な決定論的最適化問題の領域とは著しい対照をなしている（式$\eqref{eq:linearprogram1}$–$\eqref{eq:linearprogram3}$はこの枠組みの一例を表している）。私たちのモデリング過程はRLSOにおける説明に基づいているが、この本はコンピュータ上でのモデルの開発と実装に主に関心を持つ技術的な読者層を対象としている。

対照的に、本書は逐次決定問題について考える方法を学ぶことに何よりもまず関心を持つ、より広い読者層を対象としている。本書は実例を通して教えるスタイルを用い、最終的にコンピュータモデルを作成しなくても有用となりうると私たちが考えるモデリング過程を伝えることに焦点を当てている。私たちのアプローチの中心にあるのは、平易な英語で問題を記述する際の曖昧さを取り除く数理モデルの作成である。コンピュータモデルの開発に関心がある読者にとって、表記法はソフトウェアを書くための足がかりとなる。しかし、私たちは主に、読者がコードを一行も書くつもりがない場合であっても、問題を記述する際に明確さを生み出すために数学的表記法を使用する。

私たちの説明は次のように進む：

• 第1章は、2つの在庫問題（単純なものと、やや複雑なもの）を用いて説明する普遍的なモデリング枠組みへの軽い導入を提供し、その後に不確実性のモデリングについての簡単な議論が続く。そして、決定を下すあらゆる方法を網羅する4つの方策クラスへの導入を提供する。
• 第2章から第6章は、それぞれ実例を通して教えるスタイルを用いてモデリング枠組みを説明するために、特定の逐次決定問題を記述する。これらの応用例は、4つの方策クラスそれぞれを浮き彫りにするために選ばれた。
• 第7章は、普遍的なモデリング枠組みにより詳細に立ち返る。第2章から第6章までの例を文脈として用いながら、4つの方策クラス、そして様々なタイプの状態変数について、はるかに注意深い議論が行われる。
• 第8章から第14章は、より高度なモデリング概念を説明するために、より複雑な設定を用いた追加の例を提供する。これは不確実性のモデリング（特に第8章における電力価格のモデリング）と、より豊かな方策の集合の両方を対象とする。

応用例を扱う各章（第2章から第6章、および第8章から第14章）はすべて同じ構成に従っている。これらはどのような順序でも取り扱うことができるが、第2章から第6章の応用例はより単純であり、4つの方策クラスそれぞれを説明するために選ばれたものであることに留意されたい。特定のモデリングの話題（状態変数、不確実性のモデリング、あるいは方策の様々な例を見ることなど）に関心のある読者は、章を拾い読みし、興味のある話題に直接飛んでもよい。

各章は、次の3つの区分に分けられた一連の演習問題で締めくくられる。

• 復習問題 – これらは、章を読んで得られた基本的な理解を強化するために使える簡単な質問です。
• 問題解決演習 – これらは、問題解決スキルを必要とするモデリング上の課題を紹介します。
• プログラミング演習 – ほとんどの章には、一連のPythonモジュールを利用したプログラミング演習問題があります。当初Python 2で書かれていたPythonモジュールは、ドイツのカールスルーエ大学の教授であるDennis Djanka教授による大幅なアップグレードの恩恵を受けました。新しいライブラリはtinyurl.com/sdagithubからダウンロードできます。これらの演習問題のいくつかは、Pythonコードにプログラミング上の修正を加えることを必要とします。

では、決定とは何か

ソクラテス、アリストテレス、プラトンの時代にまで遡る2,000年以上にわたって、人々がどのように決定を下すかについての研究を記録した長い歴史があります。そして1950年代以降を中心に(それ以前にもいくつかの重要な研究がありますが)、最適な決定を下すための数学に関する膨大な文献があり、何千もの論文や書籍から構成されています。この文献が見落としているように思われるのは、次の基本的な問いです。

決定とは何か?

まず、決定とは、私たちが制御しようとしている何らかの「システム」の挙動に影響を与える情報の一形態であるという観察から始めます。このシステムには、私たちのシステムがどれだけうまく機能しているかを定量化する1つ以上の指標が暗黙のうちに含まれています。そして、私たちのシステムの何らかの側面を制御するエージェントを特定する必要があります。

この基盤を踏まえると、3つのクラスの情報を特定するのが役立ちます。

1. 知識の状態 – これは、私たちのシステムの性能に関連する、現時点で私たちが持っている情報です。
2. 私たちが制御する、知識の状態を変える情報(これには、私たちのシステムを制御するエージェントを特定する必要があります)。
3. 私たちのシステムに到着し、私たちの制御を超えて知識の状態を変える情報。

クラス2の情報を決定と呼びます。これは、Bridging Decision Problems, Volume I: Framing the Problemに基づく決定の形式的な定義を示唆しています。

定義(形式的): 決定とは、内生的に制御可能な情報クラスである。

非形式的な定義は次のようになるかもしれません。

定義(非形式的): 決定とは、私たちが制御するものである。

これらの定義は出発点を提供しますが、そこから多くを学ぶことはできません。もっと興味深いのは、決定の具体例を特定することであり、次にそれを行います。

決定の種類

私たちは、状況と最良の決定を判断するために使用しうるツールに基づいて、10種類の決定を特定しました。それらは以下の通りです。

1) 物理的および財務的決定 – これらの決定は、人材、設備、施設、製品、水、エネルギーなどの物理的資源、および現金や投資などの財務的資源の管理において生じます。決定には、資源の購入、販売、変更が含まれ、変更とは、ある場所から別の場所への移動、設備の修理、人材の訓練、ケーキを作るための材料の組み合わせなどを意味する場合があります。

2) 複雑な/戦略的決定 – これらは、システムに複数の変更(資源、パラメータ、信念の変更)をもたらす可能性のある決定であり、通常は大きな不確実性の源を伴います。これらの決定は通常一度だけ評価されますが、待って後で決定を下すという選択肢が存在する場合もあります。

3) 情報取得/観察決定 – これには、実験室での実験、フィールドテスト、コンピュータシミュレーションの実行などの決定が含まれます。市場調査の実施、専門家の雇用、大規模言語モデルへの質問なども含まれる場合があります。

4) 情報伝達/共有決定 – これらは2つの形式で現れます。

• a) メッセージング – これは、テキスト、動画、および/または音声で私たちが伝える内容を反映します。
• b) チャネルとタイミング – これは、情報を送る方法の選択、すなわちテキスト/メール、出版物(印刷またはオンライン)、ソーシャルメディア、広告チャネルを対象とします。またタイミングと頻度の選択も必要です。

5) 性能指標と目的 – これらは、収益の最大化、コストの最小化、罹患率の最小化、得票数の最大化など、私たちが達成しようとしていることを定量化するという重要な選択を表します。

6) 関数の選択 – これらは、決定を行う方法(方策)、最適化モデルの定式化、性能指標の選択、予測または推定の方法、遷移関数の設計(病気の広がり方など)である場合があります。

7) パラメータの設定 – システムの性能に影響を与えるパラメータが多数存在することがよくあります。これらは価格、統計モデルの係数、製造プロセスで使用される温度である可能性があります。性能指標に置かれる重みや、性能目標である場合もあります。

8) 推定または識別 – 人物を特定したり、需要を予測したり、病名を特定したりする必要があるかもしれません。

9) 特徴と挙動 – 製品をどのように設計するか、ソフトウェアパッケージにどのような機能を持たせるか、顧客にどのようなサービスを提供するか、あるいは学生の専攻がどのようなスキルを身につけて卒業するかを決定します。

10) 何を決定するかを決定する – この最後の決定に対して形式的な分析を用いることは一般的にありませんが、自分たちが決定を行っていることを認識し、それをデータ分析とモデリングを用いて形式的に扱いたいかどうかを認識することが重要です。

決定の特定には、その決定がシステムの性能にどのように影響するかを理解することが暗黙のうちに含まれています。物理的資源(タイプ1)の移動にはコストが伴いますが、需要を満たすことは収益をもたらします。決定は1つ以上の性能指標に即座に影響を与える場合があります(これは資源管理でよく起こります)が、多くの場合、決定は時間をかけて評価する必要があり、決定を下す時点ではまだ分かっていない情報に依存します。このため、私たちはしばしば決定そのものではなく、決定を下す方法(すなわち手法)を評価しているのです。

問題の枠組み化

決定問題に取り組む際の第一歩は、次の3つの質問に答えることです。

• 性能指標は何か?
• どのような種類の決定が下されるのか(そして誰がそれを行うのか)?
• 性能に影響を与える不確実性は何か?

これらの質問への答えは、あらゆる決定問題にとって根本的なものであることに注意してください。本書では、問題を解決するためにすでに設計したモデルの文脈でこれらの質問に答えるため、これらの質問はかなり単純に見えるでしょう。実際の応用では、性能指標、決定、不確実性のリストは非常に長くなることがあります。

問題の枠組み化がどれほど豊かなものになりうるかのヒントとして、まさにこのテーマに特化したモノグラフFraming the Problemを読者にお勧めします。このモノグラフには、これらの各質問に専念する章全体があり、十数個の異なる応用例を用いて説明されています。

枠組み化プロセスの目標は、まず性能指標から始めて、何が重要かを特定することです。単純な在庫問題でさえ、20以上の性能指標、30種類以上の決定、30種類以上の不確実性で記述できます。これらを一覧にしたスプレッドシートはtinyurl.com/PowellInventoryDecisionsにあります。これは、私たちが実際にこの複雑さをすべて備えたモデルを構築するということを意味するわけではありません。このため、本書では相互作用行列と呼ばれる仕掛けを導入しており、ドメインの専門家が指標に優先順位を付け、その後、判断を用いて最も重要な指標に最も大きな影響を与える決定と不確実性を特定します。

本書は、問題をすでに少数の指標、決定、不確実性に絞り込んだ状態であることを前提とし、これらを使って数学モデルの開発に焦点を当てます。

モデリングプロセス

モデリングは芸術ですが、コンピュータに乗せて解くことができる明確に定義された問題を得ることを保証する数学的枠組みに導かれた芸術です。これは、乱雑で不明確に定義された現実世界の問題から、たとえ最終目標がコンピュータに乗せることでなくても、コンピュータが理解できる明快さを持つものへと橋を架けることと見なすことができます。

歴史的に、決定を下そうとするモデリングの取り組みが行われる場合、人々はよく知られた決定論的最適化の枠組みに頼っていました。これは多くの場合、式$\eqref{eq:linearprogram1}$–$\eqref{eq:linearprogram3}$で与えられるモデルのように見え、決定変数$x$、目的関数$cx$、そして$\eqref{eq:linearprogram2}$–$\eqref{eq:linearprogram3}$で与えられる制約から構成されます。

この古典的なモデリング枠組みの問題点は、それが省いているものにあります。

• モデルを特徴づけるすべてのデータ(変数$A$、$b$、$c$に含まれる)が完全に既知であると仮定している。
• ほとんどの決定は時間をかけて繰り返し発生しますが、それにもかかわらずこれが認識されていません。
• システムへの情報の流れを表現する方法がありません。
• その副産物として、このモデルの最適解は、現場で$x$の性能に影響を与える事象を予期することができません。
• リスクを表現する方法がなく、これは多くの応用において主要な課題です。
• 単一の意思決定者を仮定しています。

数学モデルは、何よりもまず、問題についてどのように考えるかを教えてくれる道筋を提供すべきです。式$\eqref{eq:linearprogram1}$–$\eqref{eq:linearprogram3}$の形式に従う古典的な決定論的最適化モデルは、私たちの問題が時間とともに進展することに関連するあらゆる事柄を完全に無視しています。

本書は、ユニバーサルモデリング枠組みと呼ばれるモデリングアプローチを中心に完全に設計されています。一言で言えば、これは制御可能なシステムのあらゆる側面を表現することを目指しています。私たちのデフォルトのモデルは、新しい情報が到着するにつれて、システムが時間とともに進展すると仮定します。

この節では、ユニバーサルモデリング枠組みの非常にコンパクトなバージョンを提供します。次に、最初は非常に単純な在庫問題を使ってこの枠組みを説明し、その後、いくつかの控えめな拡張を導入します。これらの例を提示した後、ユニバーサルモデリング枠組みのより詳細な提示に戻ります。

動的モデルのコンパクトな提示

まず、以下の系列を使ってあらゆる逐次決定問題をモデル化できることを観察することから始めます。

ここで:

• $S_t$は、次のことに必要なすべてを捉える状態変数です:
  • a) 時刻$t$で決定を下す。
  • b) 時刻$t$で性能指標を計算する。
  • c) 将来の任意の時点で(a)または(b)を計算するために必要なその他の情報。

  $S_t$は、時刻$t$における情報の状態、あるいはより一般的には知識の状態と考えるのが最良です。

• $x_t$は決定変数を表し、家を売るかどうか、ネットワークを通る経路、治療のための薬の選択、製品を販売する価格、貨物を運ぶトラックの選択など、私たちが制御する要素を捉えます。

• $W_{t+1}$は、私たちが決定$x_t$を下した後に到着する情報であり、これは家の最終的な販売価格、ネットワークを通る移動時間、患者が薬にどう反応するか、ある価格での製品の販売、あるいは初期の割り当てを行った後に呼び込まれる貨物の量である可能性があります。私たちは$W_{t+1}$の情報を、私たちのシステムの外部から来るもの、すなわち私たちの制御外にあるものと見なします。このため、これを外生情報と呼びます。

  $W_{t+1}$を、現在の状態$S_t$および/または決定$x_t$に依存する関数$W_{t+1}(S_t,x_t)$として考えるのが最良である設定が多く存在します。これについては以下でより詳しく議論します。私たちはデフォルトの記法として$W_{t+1}$を使用しますが、それが状態$S_t$や決定$x_t$によって影響を受ける可能性があることを理解した上でのことです。

決定 $x_t$ は、方策 と呼ぶ何らかの方法によって決定され、これを $X^\pi(S_t)$ と表記する。表記 $\pi$ は、関数の構造に関する情報を運んでおり、これを潜在的関数の集合 $\Fcal$ 中の $f$ で表し、また関数の構造によって定義される任意の調整可能パラメータ $\theta\in\Theta^f$ についても情報を運んでいる。例えば、在庫が $\theta^{min}$ を下回ったら $\theta^{order}$ 単位を発注する、という在庫方策があり得るが、これは調整可能パラメータが $\theta = (\theta^{order}, \theta^{min})$ であることを意味する。関数の構造は、関数 $f$ の一例となる。

我々は、状態 $S_t$、決定 $x_t$、および外生情報 $W_{t+1}$ を入力として受け取り、更新後の状態 $S_{t+1}$ を与える 遷移関数 を持つと仮定する。遷移関数とは、状態変数 $S_t$ の各要素を更新する一連の方程式であり、要素はたった1つの場合もあれば、数万個(あるいはさらに多く)ある場合もある。

状態 $S_t$ に含まれる情報のもとで決定 $x_t=X^\pi(S_t)$ を行うと、貢献(あるいはコスト)$C(S_t,x_t)$ が発生する。我々の目標は、貢献 $C(S_t,x_t)$ に依存する何らかの目的を最大化する方策を見つけることであり、ここで $x_t=X^\pi(S_t)$ である。より複雑な設定では、$C(S_t,x_t)$ は実際には性能指標の集合になり得るが、その場合はどの決定 $x_t$ を選ぶかを特定するために、それらを何らかの方法で組み合わせる必要がある。

これは逐次決定問題の非常に簡潔な記述である。次に、モデリングの過程で従うべき一連のステップを説明する。

モデリング過程における各ステップ

モデリング過程全体は(我々の目的のために)7つのステップに分けることができる。これらのステップ(以下では「ステップ0」と表記)に先立ち、読者を導くためにアプリケーションの技術的な複雑さを簡潔にまとめる。

ステップ0. 章の要約 – 各章の冒頭で、その章が扱う内容の要約を示し、場合によっては他の章の内容との関連性についても述べる。この要約では、不確実性のモデリングに用いるアプローチと、使用する方策が示される。

ステップ1. ナラティブ – これは、問題についての平易な英語による記述である。ナラティブは、数理モデルを作成するために必要な情報のすべてを提供するものではなく、むしろ、モデラーが記法に迷い込むことなく全体像を把握できるようにするための最初のステップである。

ステップ2. 問題の枠組み(フレーミング) – これは以下の3つの問いに答えることから成る:

• 性能指標は何か?
• どのような種類の決定が行われているか(場合によっては、どのエージェントが決定を行っているか)?
• 性能に影響を与える不確実性の源は何か?

ステップ3. 問題の中核要素の特定。特に、逐次決定問題の3つの次元に重点を置く。これらの要素は数学を用いずに記述される:

• 我々が影響を及ぼそうとしている指標は何か? 個々の分野(サプライチェーン管理、医療、エネルギー、金融など)は、それぞれコスト、収益、利益、報酬、利得、損失、性能、リスクといった用語で表される多くの指標によって特徴づけられる。
• どのような決定が行われているか? コンピュータゲームのような多くの問題では決定を特定するのは非常に容易だが、公衆衛生プロセスへの対応、カーボンフットプリントの削減、サプライチェーンの管理といった複雑な問題に取り組む場合、すべての決定を特定することは非常に困難になり得る。
• 不確実性の異なる源は何か? 開始前に我々が不確実であるのは何についてか? どのような情報が外生的に(すなわち決定を行った後に)時間とともに到着するのか? 表 1.2 は、COVIDワクチン配布モデルにおける不確実性の異なる源を示している(12種類の不確実性クラスの提示については RLSO 第10章を参照)。

これら3つの問いに答える過程を 問題の枠組み化(フレーミング) と呼ぶ。

ステップ4. 数理モデル – ここでは、ステップ2で得られた最初の3つの要素を基盤としつつ、あらゆる逐次決定問題に当てはまる5つの次元から構成される数理モデルを構築する必要がある:

• 状態変数 $S_t$ – 状態変数は、時刻 $t$ において決定を行い(時刻 $t$)、コストや制約を計算し、必要であれば時刻 $t+1$ までシミュレートするために知っておく必要のあるすべてを捉える。状態変数には、物理的資源に関する情報(制約を通じて問題に入ってくる在庫や車両の位置など)、その他の情報(目的関数に入ってくるコストや価格など)、そして我々が完全には知らない量やパラメータに関する信念(薬に対する患者の反応の予測や推定値など)が含まれ得る。

• 決定変数 $x_t$ – これらは、我々がシステムをどのように設計・制御するかを記述する。決定は、$x_t \in \Xcal$ と書く制約を満たす必要があり、ここで $\Xcal$ は離散的な選択の集合、あるいは線形方程式の集合であり得る。決定は、我々が $X^\pi(S_t)$ と表記する関数(あるいは規則)である 方策 によって決定され、状態変数に含まれる情報を与えたときに $x_t$ を決定する。方策は非常に単純(安く買い高く売る)なものから、かなり複雑なものまであり得る。

  添字 $\pi$ は、決定を行うために用いられる関数の種類と任意の調整可能パラメータに関する情報を運ぶ。$f\in\Fcal$ を関数の構造、$\Fcal$ を可能な関数の集合、$\theta\in\Theta^f$ を関数 $f$ に対する任意の調整可能パラメータとする。すると我々の方策は $\pi = (f,\theta)$ として表される。調整可能パラメータへの依存性を示すために、方策を $X^\pi(S_t\vert \theta)$ と書くことも多い。

  この点については、本章の後半、そして本書全体を通じて、かなり詳しく取り上げる。本書で挙げられている各例は、特定の種類の方策を説明するために選ばれたものである。

• 外生情報 $W_{t+1}$ – これは、決定 $x_t$ を行った後(かつ $x_{t+1}$ を決定する前)に到着する新しい情報であり、例えば価格を設定した後にどれだけ売れるか、選択した経路を完了するまでの時間などである。時刻 $t$ において決定を行う際、$W_{t+1}$ に含まれる情報は未知であるため、$x_t$ を選ぶ際にはこれを確率変数として扱う。
• 遷移関数 $S^M(S_t,x_t,W_{t+1})$ – これは、状態変数が時間とともにどのように進化するかを記述する方程式である。多くの実際の問題において、遷移関数は問題のダイナミクスすべてを捉えるものであり、非常に複雑になり得る。場合によっては、その方程式自体が分からず、観測可能な状態変数だけに依存しなければならないこともある。状態変数 $S_t$ の進化を、遷移関数を用いて次のように書く:

ここで $S^M(\cdot)$ は状態(あるいはシステム)遷移モデルとして知られている(それゆえ上付き文字に $M$ が付く)。遷移関数は、決定 $x_t$ と外生情報 $W_{t+1}$ が与えられたときに、状態変数のすべての要素がどのように変化するかを記述する。複雑な問題では、遷移関数の実装に数千行のコードが必要になることもある。

• 目的関数 – これは、我々の性能を評価するために用いる性能指標を捉え、方策を探索するための基盤を与える。$x_t$ という決定に対する貢献(最大化する場合)あるいはコスト(最小化する場合)を $C(S_t,x_t)$ とし、これは $S_t$ に含まれる情報に依存し得る。設定によっては、単一期間の貢献関数を $C(S_t,x_t,W_{t+1})$ と書く方が自然であり、これは時間区間 $(t,t+1)$ の終わりに、$W_{t+1}$ が観測された後に評価された貢献関数である。例えば、我々は $W_{t+1}$ に含まれる不確実な需要を満たすために、即時に到着する $x_t$ を発注するかもしれない。

  我々の目的は、以下のような何らかの指標を最適化する最善の方策 $X^\pi(S_t)$ を見つけることである:

  • ある期間にわたる貢献の期待合計を最大化する。
  • 一連の実験あるいは観測を通じて学習した最終的な設計の期待性能を最大化する。
  • 最終的な設計に関連するリスクを最小化する。

  目的関数を書く最も一般的な方法は次のとおりである:

ここで「$\E$」は 期待値演算子 と呼ばれ、これは、初期状態 $S_0$ に含まれる不確実な情報や、外生情報プロセス $W_1, \ldots, W_T$ など、ランダムなものすべてにわたって平均を取ることを意味する。期待値演算子を書くことは標準的な習慣であるが、実際にはそれを計算することは決してできない。後に、一連のシミュレーションを実行して平均を取る、あるいは現場でプロセスを観測することによって、これを近似する方法を示す。

式 $\eqref{eq:baseobjectivefunction}$ において期待値演算子「$\E$」を解釈する際には注意が必要である。この演算子が文字通り意味するのは「不確実であるものすべてにわたって平均を取る」ということである。最も明白な不確実性の要素は、外生情報プロセス $W_1, W_2, \ldots, W_t, \ldots, W_T$ である。

実際の問題(ナラティブによって導かれる)から数理モデルの各要素への移行は、おそらく最も難しいステップであり、しばしば技術的でない情報源から情報を収集することを伴う。

我々は、決定をどのように行うか、つまり方策 $X^\pi(S_t)$ によって表されるものを一切指定せずに、モデル全体を提示したことに注意してほしい。我々はこれを「まずモデル化し、それから解く」と呼び、これは逐次決定問題を扱う膨大な既存文献からの大きな逸脱を表している。逐次決定問題にこのように取り組むことがいかに重要であるかは、伝えるのが難しいほどである。

ステップ5. 不確実性モデル – これは、異なる種類の不確実性をどのようにモデル化するかである。我々のモデルに不確実性を導入する方法には2つある:

1. 初期状態 $S_0$ を通じて、これは、患者が薬にどのように反応するか、あるいは市場が価格にどのように反応するかといった不確実なパラメータに対する確率分布を指定し得る。
2. 外生情報プロセス $W_1, \ldots, W_T$ を通じて。

外生情報プロセスをモデル化する方法は3つある:

• $W_1, W_2, \ldots, W_T$ の数理モデルを作成する。
• 過去の価格、売上、天候イベントなど、履歴からの観測を用いる。
• 実際にシステムを運用し、$W_t$ が発生する様子を観測する。

ステップ6. 方策の設計 – 方策は関数であるため、最善の関数を探索する必要がある。(そう、方策は最善の決定を選ぶための関数であるが、方策を選ぶこと自体も1つの決定なのである!)これを行うために、方策設計のための2つの中核戦略を特定する:

• 関数族の中を探索して、時間の経過とともに平均的に最も優れた性能を発揮するものを見つける。
• 決定 $x_t$ の直接的なコストまたは貢献を見積もり、それに将来のコストまたは貢献の近似を加え、現在と将来のコストまたは貢献の合計を最適化する選択 $x_t$ を見つけることで方策を作成する。Google マップは、ネットワーク内の次のリンクを通過するのに要する時間と、目的地に到達するまでの残り時間とを合わせて最適化することで、左折するか右折するかを決定する。在庫の決定では、注文のコストと、将来に向けて一定量の在庫を保持することの推定価値とを合わせて最適化するかもしれない。

これらの方策をどのように特定するかについて、もっと明確に説明していく。後の節では、あらゆる意思決定の方法を含む(これらはメタクラスである)4つの方策クラスについて述べる。

ステップ7. 方策の評価 – 最良の方策を見つけるということは、方策を評価してどれが最良かを判断することを意味する。方策を評価する方法は2つある。

• コンピュータシミュレータで方策をテストする。これには、状態変数 $S_t$ を更新するために必要な状態遷移モデル $S^M(S_t,x_t,W_{t+1})$ のすべての式をプログラムする必要がある。また、$W_{t+1}$ のサンプルを生成できる必要もあり、これはしばしばシミュレータの中で最も繊細な側面となる。
• 現場で方策がどのように機能するかを観察する。

シミュレータは複雑で構築が難しい場合があり、それでもなおモデル化による近似の影響を受ける。このため、実務で遭遇するほとんどの実際的な問題は、現場でのテストを伴う傾向があり、これは遅く(1日をシミュレートするのに1日かかる)、実験結果とともに生きていく必要がある。

数理モデルに親しむ唯一の方法は、身近な例を使ってそれが説明されるのを見ることである。私たちは皆、日常生活で出会う普遍的な問題、すなわち在庫管理から始めることにする。

いくつかの在庫問題

古典的な在庫問題の2つのバリエーションを使って、私たちのモデリングフレームワークを説明していく。この問題は、逐次決定問題を解くための特定の手法を説明するための応用例として広く使われている。まず、私たちのモデリングフレームワークの中核要素を伝えるシンプルな在庫例から始めるが、これにより本書の残りの部分で探求していく多くの複雑さを無視することができる。

その後、いくつかのモデリング原則を説明できる、少しだけ複雑な在庫問題へと移行する。本書を通じて、問題の基本バージョンから始め、実際の応用で生じ得る複雑さの種類を示唆する拡張を導入するという考え方も使っていく。

シンプルな在庫問題

私たちが店を訪れるたびに経験する最も馴染み深い逐次決定問題の一つが在庫問題である。上記で紹介したモデリングプロセスの6つのステップを説明するために、この問題のシンプルなバージョンを使っていく。

ステップ1: 物語 – あるピザレストランは、食品卸売業者にソーセージを何ポンド注文するかを決める必要がある。レストランは日 $t$ の終わりに決定を下さなければならず、その注文は翌朝到着し、翌日の注文に応じるために使われる。ソーセージが余った場合、翌日まで保持することができる。ソーセージのコストと、翌日に販売される価格は事前にわかっているが、需要はわからない。

ステップ2: 問題の中核要素は次の通りである。

• 評価指標 – ソーセージの販売による利益からソーセージの購入コストを差し引いたものを最大化したい。
• 決定 – ある日の終わりに、翌日の初めに到着する分の注文量を決定する必要がある。
• 不確実性の源 – このシンプルなモデルにおける唯一の不確実性の源は、翌日のソーセージの需要である。

ステップ3: 数理モデル – これは5つの要素から構成される。

1) 状態変数 $S_t$ – 初期状態変数 $S_0$ と、$t > 0$ に対する動的状態変数 $S_t$ を区別する。初期状態変数 $S_0$ は、固定パラメータと、時間とともに変化する変数の初期値から構成され、次のようになる。

初期状態を3種類の変数に分けた。

• 資源状態 $R^{inv}_0$ の初期値。
• 定数パラメータ $c$ と $p$ の値。
• 平均 $\Dbar$、標準偏差 $\sigmabar^D$ の正規分布で与えられる需要についての信念。

動的状態変数 $S_t$ は私たちの在庫であり、これを $R^{inv}_t$ と呼ぶことにする。今のところ、これが動的状態変数の唯一の要素であるため、

後で状態変数に追加の要素を導入する。

2) 決定変数 $x_t$ は、時刻 $t$ にどれだけ注文するかであり、(今のところ)それはすぐに到着すると仮定する。私たちは、後で設計する方策 $X^\pi(S_t)$ を用いて決定を下す。

3) 外生情報 は製品に対するランダムな需要であり、これを $\Dhat_{t+1}$ と表すことにする。したがって $W_{t+1} = \Dhat_{t+1}$ となる。

4) 遷移関数 は在庫 $R_t$ が時間とともにどのように変化するかを捉えたものであり、次式で与えられる。

5) 目的関数。 私たちの在庫問題では、製品 $x_t$ の購入コストと、需要 $\Dhat_{t+1}$ を満たすことによる収益を含めて貢献を計算するのが最も自然であり、これは単一期間の貢献関数が次のように書けることを意味する。

ここで $x_t = X^\pi(S_t)$ である。需要の系列 $\Dhat_1, \ldots, \Dhat_T$ が与えられたとき、方策 $\Fhat^\pi$ の価値は次のようになる。

私たちの利益 $\Fhat^\pi(S_0)$ は、ランダムな需要の特定の系列 $\Dhat_1, \ldots, \Dhat_T$ に依存するためランダムである。最後に、これらのランダムな需要について期待値を取ることで平均化する。

ここで、初期状態 $S_0$ による条件付けは、「最初にわかっていることを前提として期待値を取る」と読むことができる。$S_0$ による条件付けは、期待値を取るたびに暗黙のうちに行われるものであり、その結果として多くの著者はこれを省略している。しかし、私たちは $S_0$ による条件付けを含めることにする。これは、初期入力(信念を含む)が変化すると、方策の性能に影響を与える可能性があることを明確にするためである。

ステップ4. 不確実性モデル – 不確実性をモデル化する最もシンプルな方法は、単に過去のデータを使うことである。私たちが遭遇するかもしれない問題は、ソーセージが売り切れてしまった場合、その日の需要の全体を観測できないかもしれないということである。この失われた需要を捉えることができるのであれば、これは妥当なアプローチである。

代替案として、数理モデルを構築することもできる。需要は、ある平均 $\Dbar$ と標準偏差 $\sigmabar^D$ を持つ正規分布に従うと仮定するかもしれない。これら両方が既知であると仮定すれば、需要を次のように書くことができる。

そして、正規分布からサンプリングできるパッケージ(例えば、Excel では Norm.inv$(Rand(),\Dbar,\sigmabar)$ と呼ばれる)を利用して、平均 $\Dbar$、標準偏差 $\sigmabar$ のランダムな観測値を生成することができる。

このモデルを使って、需要の集合 $(\Dhat_1, \Dhat_2, \ldots, \Dhat_T)$ を作成できる。それから、これを $N$ 回繰り返すことで、$T$ 個の需要からなる $N$ 個の系列を作成し、方策の価値を推定するために必要な、$n=1, \ldots, N$ に対する系列 $(\Dhat^n_1, \Dhat^n_2, \ldots, \Dhat^n_T)$ が得られる(これは以下のステップ6で使用する)。

ステップ5. 方策の設計 – 次に、注文量を決定する方法を設計する必要がある。在庫問題でよく用いられる戦略は「オーダーアップトゥ」方策として知られており、次のようになる。

ここで $\theta = (\theta^{min},\theta^{max})$ は調整が必要なパラメータの集合である。これが「オーダーアップトゥ」と呼ばれるのは、在庫を上限 $\theta^{max}$ まで「引き上げる」ように注文するからである。

ステップ6. 方策の評価 – 使用できる戦略にはさまざまなものがある。実際には、式 $\eqref{eq:inventoryobjective}$ の目的関数における期待値を計算することはできないため、需要のサンプルの系列を取る。$t=1, \ldots, T$ にわたる需要の1つのサンプルを $\Dhat^n_1, \ldots, \Dhat^n_T$ とし、これらを $N$ 個生成できると仮定する。これで、$n=1, \ldots, N$ に対するサンプルを平均化することで、方策 $X^\pi(S_t)$ による期待利益を推定でき、これは次式を用いて計算される。

平たく言えば、需要のシミュレート(または過去から観測)されたサンプル $\Dhat^n_1, \ldots, \Dhat^n_T$ を使って方策 $X^\pi(S_t\vert \theta)$ を $N$ 回シミュレートし、その性能を平均化して $\Fbar^\pi(\theta\vert S_0)$ を得ているのである。次に、$\theta$ の最良値を見つけるという問題に直面する。シンプルな戦略としては、$K$ 個の可能な値 $\theta_1, \ldots, \theta_K$ を生成し、それぞれをシミュレートして各 $k$ に対する $\Fbar^\pi(\theta_k\vert S_0)$ を求め、最も良い性能を示す $\theta_k$ の値を選ぶというものである。これは最適な戦略ではないが、シンプルで実用的な出発点を提供する。

少し複雑な問題

上記のシンプルな在庫問題は、動的計画法として知られる逐次決定問題を解くための特定の手法を実演するための古典的な設定であり、これは離散的であり、かつ、あまり多くの取り得る値を持たないシンプルな状態変数を持つことに依存している。私たちの少し複雑な在庫問題では、逐次決定問題を解くためのある人気の手法にとっては深刻な複雑化を意味するが、私たちが選んだ方策には影響を与えない、3つの異なる種類の状態変数を実演していく。

ステップ1: 物語 – 再び、ソーセージを注文しなければならないピザレストランがあるが、今回はソーセージの支払い価格が日によって変動することを許す。ある日の価格は前日の価格とは独立であると仮定する。それから、明日のソーセージの需要はランダムであるものの、明日の需要の予測が与えられると仮定する。この予測は完璧ではないが、予測がないよりはましである。それ以外は、私たちのより複雑な問題に関するすべては以前と同じである。

ステップ2: 中核要素 – 次の通りである。

• 評価指標 – 日によって変動するコストのもとで、ソーセージの販売による利益からソーセージの購入コストを差し引いたものを最大化したい。
• 決定 – よりシンプルな在庫問題と同様に、ある日の終わりに、翌日の初めに到着する分の注文量を決定する必要がある。
• 不確実性の源 – 現在、不確実性の源は3つある。実際の需要と予測との差、ある日から次の日への予測の変化、そして支払うソーセージの価格である。

ステップ3: 数理モデル – 依然として同じ5つの要素を持つが、今回は問題が少し豊かになっている。

1) 状態変数を構成するには、モデルの3つの異なる部分、すなわち(1)目的関数、(2)(制約を含む)意思決定を行うための方策、(3)遷移関数で必要となる情報(具体的には、時間とともに変化する情報)を列挙する必要がある。もちろん、これらの関数はまだ何一つ導入していないため、先を読み進めて、私たちの状態変数がこれらの関数それぞれを計算するために必要なすべての情報を含んでいることを確認する必要がある。これを、必要となる情報の辞書だと考えてほしい。

固定パラメータと、時間とともに変化する量やパラメータの初期値からなる初期状態 $S_0$ から始める。これらは次の通りである。

• 初期在庫 – 初期在庫 $R_0$ から始める。
• 初期購入コスト – $c_0$。
• 価格 – 固定価格 $p$ でソーセージを販売すると仮定する。
• 初期予測 – 最初の予測 $f^D_{0,1}$ が与えられると仮定する。ここで $f^D_{0,1}$ は、時刻1における需要について時刻0でわかっている予測である。
• 需要の標準偏差の初期推定値 – $\sigmabar^D_0$。
• 予測の標準偏差の初期推定値 – $\sigmabar^f_0$。

これは、私たちの初期状態変数が次のようになることを意味する。

それから、時間とともに変化し、動的状態変数 $S_t$ を構成する情報を持つ。

• 現在の在庫 $R^{inv}_t$ – 時間区間 $(t,t+1)$ の初めにおける在庫。
• 購入コスト $c_t$ – これは時刻 $t$ に購入されたソーセージのコストであり、時刻 $t$ に私たちに与えられる。
• 需要予測 $f^D_{t,t+1}$ – これは、時刻 $t$ でわかっていることを前提とした $\Dhat_{t+1}$ の予測である。
• 需要の標準偏差の現在の推定値 – $\sigmabar^D_t$。
• 予測の標準偏差の現在の推定値 – $\sigmabar^f_t$。

我々の動的状態変数は次のように与えられる。

2) 決定変数$x_t$は時刻$t$における発注量であり、(今のところ)即座に到着すると仮定する。我々は後で設計する方策$X^\pi(S_t)$を用いて決定を行う。

3) 外生情報は次のもので構成される。

• 購入コスト$\chat_{t+1}$ – これは日$t+1$におけるソーセージの購入コストであり、外生的に指定される。
• 予測 – 各時間期間ごとに新しい予測が与えられる。$\varepsilon^f_{t+1}$を時刻$t$と$t+1$の間の予測の変化とする。
• 需要 – 最後に、実際の需要は予測からのランダムな偏差であると仮定し、次のように書ける。

我々の外生情報変数の完全な集合は次のように書くことができる。

4) 遷移関数 – これは(動的な)状態変数$S_t$のそれぞれが時間とともにどのように推移するかを規定する。我々は次式を用いて在庫を更新する。

需要は予測需要に予測からの偏差$\varepsilon^D_{t+1}$を加えたものであり、次の式が得られる。

我々は次式を用いて予測が更新されると仮定する。

次に、需要と需要予測の分散を適応的に推定する。

ここで$0 < \alpha < 1$は平滑化係数である。

最後に、コスト$c_{t+1}$を「観測されたコスト」$\chat_{t+1}$を用いて単純に次のように更新する。

式$\eqref{eq:introcomplexinventorytransition6}$は、$\eqref{eq:introcomplexinventorytransition1}$における在庫$R^{inv}_t$のように計算するのではなく、観測される状態変数の一例である。式$\eqref{eq:introcomplexinventorytransition1}$は在庫がどのように更新されるかという物理法則を反映しているため「モデルベース」と呼ばれることがあり、一方式$\eqref{eq:introcomplexinventorytransition6}$はコストの変化を生み出す基礎過程をモデル化しようとしないため「モデルフリー」と呼ばれる。

我々の遷移関数$S_{t+1} = S^M(S_t,x_t,W_{t+1})$は式$\eqref{eq:introcomplexinventorytransition1}$–$\eqref{eq:introcomplexinventorytransition6}$から構成される。

5) 最後に、単一期間の貢献関数は次のように書ける。

単純な在庫問題との唯一の違いは、コスト$c$が時間依存$c_t$になっている点である。我々は貢献を$C(S_t,x_t)$として書く慣例から離れ、需要$\Dhat_{t+1}$からの収益を含めることを許す。

我々は目的関数を形式的に次のように述べる。

最適化$\max_\pi$は、$(f,\theta)$で表されるあらゆる可能な方策を探索することを意味しており、これは文字通り、決定を行うために使用しうるあらゆる異なる関数を探索することを意味する。本書の例は、関数に対してどのように探索を行うかを示すものである。

上で述べたように、添字$\pi$は関数$f\in\Fcal$のタイプと、任意の調整可能なパラメータ$\theta\in\Theta^f$に関する情報を保持していることを思い出してほしい。実際には、関数のタイプ$f\in\Fcal$に対する探索はアドホックになりがちである(知識のある分析者が問題に対して意味のある関数を選択する)一方、$\theta\in\Theta^f$の最良の値を求める探索はコンピュータアルゴリズムが行う。

ステップ4. 不確実性モデル – 我々は、外生的な変化$\varepsilon^D_{t+1}$と$\varepsilon^f_{t+1}$が、平均0、分散$(\sigmabar^D_t)^2$と$(\sigmabar^f_t)^2$の正規分布によって記述されると仮定し、これを次のように表す。

不確実性モデルはかなり複雑になり得るが、これは例示として役立つだろう。

ステップ5. 方策の設計 – 次に、我々の発注を決定する方法を設計しなければならない。単純なモデルのオーダーアップツー方策の代わりに、調整を加えた上で明日の期待需要を満たすのに十分な量を発注するという考え方を提案する。これは次のように書ける。

もし完全な予測があれば、発注すべき量は$f^D_{t,t+1}$($\Dhat_{t+1}$の予測値)から手元在庫を差し引いたものだけになる。しかし不確実性があるため、在庫切れを避けるためのバッファを持たせるべく、調整項$\theta$を加える。

ステップ6. 方策の評価 – 今回は、系列$W_1, W_2, \ldots, W_T$内のすべての確率変数のサンプルを生成しなければならない。ここでも、系列全体の$N$個のサンプルを生成することで、次式を用いて方策の性能を推定できる。

我々は再び$\theta$の最良の値を見つけるという課題に直面するが、その課題については後で取り上げる。

汎用モデリングフレームワーク

これで、汎用モデリングフレームワーク(UMF)の要素をより詳細に説明する準備が整った。UMFはあらゆる逐次決定問題をモデル化できることに注意されたい。この、かなり広範な主張は、要素が展開されるにつれて明らかになるだろう。というのも、我々は逐次決定問題の一般的な記述に記法を適用しているに過ぎないからである。

UMFの5つの要素

UMFは次の要素から構成される。

1. 状態変数$S_t$。
2. 決定変数$x_t$。
3. 外生情報過程$W_t$。
4. 状態遷移モデル$S^M(S_t,x_t,W_{t+1})$。
5. 目的関数。

これらをより詳細に以下で説明する。

状態変数 – 時刻$t$におけるシステムの状態$S_t$は、時刻$t$以降のシステムをモデル化するために必要十分なすべての情報を持つ。より具体的には、この情報は次のもので構成される。

• a) 時刻$t$において決定を下すために必要な情報。
• b) 時刻$t$における性能指標を計算するために必要な情報。
• c) (a)と(b)を将来において計算するために今必要な情報。

$S_t$には3種類の情報がある。

• 物理状態$R_t$は、在庫、人員、利用可能な機械、施設、水、薬品、エネルギー、および(様々な形態の)資金などの物理的な量を捉える。$R_t$には、製品やサービスに対する顧客からの要求も含まれる。多くの応用において$R_t$は管理される資源を記述しており、「状態」を「物理状態」と同一視することはかなりよくある誤りである。
• 情報状態$I_t$は、(選択の余地がある場合に)使用される関数と、任意の調整可能なパラメータを含む。$I_t$は、需要をどのように予測しているか、予測を適合させるために使用されるパラメータ、さらにシステムの進展を制御するその他のパラメータを指定するかもしれない。
• 信念状態$B_t$は、完全には既知でない量やパラメータに関する推定値や信念を含む。したがって$B_t$は(上述の需要予測のように)正規分布の推定された平均と分散を捉えることができる。あるいは、時間とともに進展する確率のベクトルであるかもしれない。

物理状態$R_t$は現金口座の金額であるかもしれず、一方$I_t$は株式市場や債券市場の現在の状態であるかもしれない。動的なネットワーク上を移動している場合、$R_t$はネットワーク上の我々の位置であり、$I_t$は各リンクの所要時間について我々が知っていることであるかもしれない。経路を計画し、その後計画からの逸脱にペナルティを課したいのであれば、その計画は$I_t$を通じて状態変数に含まれることになる。

状態変数は通常、自明ではない。それらはモデリングの過程で浮かび上がってくるものであり、すぐに書き出せるようなものではない。最初に書いたからといって、状態変数の要素をすべてすぐに列挙できるとは限らない。しかし最終的には、これが時刻$t$以降のシステムをモデル化するために必要なすべての情報を保存する場所となる。

決定変数 – 異なるコミュニティは決定に対して異なる記法を用いる。例えば工学では、(典型的には離散的な)行動には$a_t$、(典型的には連続的な)制御には$u_t$が使われる。我々は、数理計画コミュニティで広く使われている$x_t$をデフォルトとして用いる。

決定変数には様々な種類がある。

• 二値(資産を売却するかどうかのモデル化、あるいは異なるウェブデザインのA/Bテストなど)。
• 離散(薬剤の選択、どの製品を宣伝するかなど)。
• 連続スカラー(価格、温度、濃度)。
• ベクトル(病院間での血液供給の配分などの、離散または連続)。
• カテゴリカル(製品広告でどの特徴を強調するかなど)。

決定変数の性質によって決定されるアルゴリズムのクラスが存在することに注意されたい。

我々は、決定が方策によって行われると仮定し、$x_t$を我々の決定として用いる場合、これを$X^\pi(S_t)$と表記するかもしれない。決定$x_t = X^\pi(S_t)$は時刻$t$において実行可能であると仮定し、これは$S_t$に依存しうる何らかの集合(または領域)$\Xcal_t$について$x_t \in \Xcal_t$を意味する。

「$\pi$」に、関数$f\in\Fcal$のタイプ(例えば、特定の説明変数を持つ線形モデル)、および任意の調整可能なパラメータ$\theta \in \Theta^f$に関する情報を持たせることにする。

外生情報 – $W_{t+1}$を、時刻$t+1$に(すなわち$t$と$t+1$の間に)初めて既知になる新しい情報とする。ここで情報の源はシステムの外部にある(そのため「外生的」である)。特定の変数をモデル化する際には、外生情報を示すために「ハット」を用いる。したがって$\Dhat_{t+1}$は$t$と$t+1$の間に生じる需要であるかもしれず、あるいは$\phat_{t+1}$を$t$と$t+1$の間の価格の変化とすることもできる。

外生情報過程は定常であるか非定常であるか、純粋に外生的であるか状態(および場合によっては行動)依存であるかもしれない(もし我々が大量の株式を売却することを決めれば、それが価格を押し下げるかもしれない)。

$\omega$をサンプルパス$W_1, \ldots, W_T$を表すものとする。これは各$W_t$の結果の系列を表す。しばしば我々は、離散的なサンプルの集合$\Omega$を作成し、各サンプルが我々の$W_t$過程の結果の特定の系列を表すものとして、これを$W_1(\omega), \ldots, W_T(\omega)$のように書くことができる。20個のサンプルパスがある場合、$\omega$を1から20までの数として考えることができ、これによりサンプルパスを検索することができる。

遷移関数 – 我々は遷移関数を次のように表す。

ここで$S^M(\cdot)$は、状態遷移モデル、システムモデル、プラントモデル、プラント方程式、状態方程式、伝達関数といった名称でも知られている。

式$\eqref{eq:transition}$は、状態$S_t$から状態$S_{t+1}$への式を与える遷移関数の古典的な形式である。式$\eqref{eq:inventoryexampleequation}$は我々の単純な在庫の例における唯一の遷移方程式であったが、式$\eqref{eq:introcomplexinventorytransition1}$–$\eqref{eq:introcomplexinventorytransition6}$は我々のより複雑な例における遷移関数を構成していた。

遷移関数は、次のいずれかの種類の更新を捉えるかもしれない。

• 在庫の追加、人員の移動、機器の変更などの物理的資源の変化。
• 価格や天候の変化などの情報の更新。
• 不確実な量やパラメータについての我々の信念の更新。

遷移関数は既知の方程式の集合であるかもしれないし、人間の行動や大気中のCO2の推移を記述する場合のように未知であるかもしれない。方程式が未知である場合、この問題はしばしば「モデルフリー」または「データ駆動」と記述され、これは物理モデルを用いる代わりに、変数の変化を観測するしかないことを意味する。$c_t$からどのように推移したかを一切知ることなく、コスト$c_{t+1} = \chat_{t+1}$を「観測する」式$\eqref{eq:introcomplexinventorytransition6}$は、モデルフリーの遷移の一例である。

遷移関数は線形、連続的な非線形、あるいはステップ関数であるかもしれない。状態$S_t$が信念状態$B_t$を含む場合、遷移関数は更新式を含まなければならない(これについては本書の後で説明する)。

方策$X^\pi(S_t)$、外生過程$W_{t+1}$、そして遷移関数が与えられれば、我々は状態、決定、情報の系列を次のように書くことができる。

目的関数 – 目的関数を書く方法は数多くある。最も一般的な方法の一つで、我々がデフォルトとして用いるものは、ある計画期間$t=0, \ldots, T$にわたる期待貢献の総和を最大化するものである。

ここで

このモデルは、初期状態$S_0$のモデルと、外生過程$W_1, W_2, \ldots$のモデルが揃った時点で完全に規定される。すべての外生情報を次のように書く。

式$\eqref{eq:objectivecumulativereward}$、$\eqref{eq:basetransition}$、$\eqref{eq:basestochasticmodel}$は逐次決定問題のモデルを構成する。

以降、簡潔さのために、関数のタイプ$f\in\Fcal$と調整可能なパラメータ$\theta\in\Theta^f$の両方に対する探索を表すために$\max_\pi$を用いることにする。

式$\eqref{eq:objectivecumulativereward}$は期待値$\E$を用いており、これは$W_1, \ldots, W_T$のあらゆる可能な結果にわたって平均を取ることを意味する。これは計算上ほぼ決して実行不可能である。代わりに、$W_1, \ldots, W_T$の系列の単一の結果を表す$\omega$を用い、これを$W_1(\omega), \ldots, W_T(\omega)$のように書くことにする。この系列の可能な結果を$N$個作成できると仮定し、$\omega^n$を$n^{th}$番目の系列をどのように添字付けするかを表すものとする。

$\omega$に従っているとすると、$\eqref{eq:basetransition}$における遷移関数を以下を用いて書き直すことになります。

我々は式$\eqref{eq:basetransition2}$のすべての変数に$\omega$という添字を付け、$W_t$の値の単一のサンプルパスに従っていることを示します。

これで、期待値に基づく目的関数を平均に置き換えることができ、次のように書けます。

多くの場合、我々は単一のサンプルパス(場合によっては履歴からのもの)のみを扱っています。この場合、この単一のサンプルパスを用いて方策の性能を近似していることになり、以下のように書けます。

$\eqref{eq:objectivecumulativereward}$のように期待値を用いて目的関数を書くときはいつでも、実際に行うのは$\eqref{eq:objectivecumulativerewardaverage}$のような平均、あるいは$\eqref{eq:objectivecumulativerewardsample}$のようなサンプルを用いることであることを覚えておいてください。

期待値はまた、初期状態$S_0$の不確実性を反映する必要がある場合もあります。これは不確実な予測に関する信念、あるいは患者の疾患状態に関する不確実な推定を捉えるものかもしれません。この場合、サンプルパス$\omega$はこれらの初期分布からのサンプルを含む必要があります。

時間ではなくカウンタ$n$を使う方が理にかなう設定もいくつかあります。この場合、$S^n$を$n$回の観測後の状態とします(これらは実験、顧客の到着、アルゴリズムの反復であってもよい)。我々は時間$t$をデフォルトの添字として使用します。

初期状態変数$S_0$

我々は初期状態$S_0$と、$t > 0$に対するそれ以降の状態$S_t$とを区別する必要があります。

• $S_0$ – 初期状態$S_0$は、i) 決して変化しない決定論的パラメータ、ii) (おそらく決定によって)変化する量やパラメータの初期値、iii) 完全にはわからない量やパラメータに関する信念(これは確率分布のパラメータであるかもしれない)、例えばワクチンに対する我々の反応や市場が価格にどう反応するかといったものを捉えます。信念は静的なまま維持されることもあれば、観測から学習するにつれて更新されることもあります。
• $S_t$ – これは、時間$t$以降のシステムをモデル化するために時間$t$から必要となる、履歴からのすべての情報です。$t > 0$に対する$S_t$には、時間とともに変化する変数のみが含まれます。つまり、時間$t$においては、$S_0$に含まれる静的な情報も同時に使用しているかもしれません。

我々は、$F^\pi(S_0)$、$\Fbar^\pi(S_0)$、$\Fhat^\pi(\omega\vert S_0)$のいずれを使う場合でも、方策の性能が初期状態$S_0$に明示的に依存することを書き表します。これは当然のことのはずですが、しばしば見落とされます。初期状態には以下のような要素が含まれます。

• 物理的または金融的資源の量の初期値$R_0$ – これは初期在庫、車両の初期位置、利用可能な機械、施設の初期集合であるかもしれません。また、輸送ネットワーク、倉庫の大きさ(変化しない)、車両群のトラック台数など、静的な値も含まれます。
• パラメータの初期値、および問題をモデル化するために使用される関数$I_0$ – これは初期価格、患者の投薬レベル、さらには予測を行うための関数や集団における疾病の進行をモデル化するための関数の選択であるかもしれません。
• 任意の量やパラメータに関する初期の信念や推定$B_0$ – これは需要予測、市場が価格にどう反応するかの推定、大統領候補の世論調査結果、あるいは製造プロセスの性能に関する信念であるかもしれません。

決して変化しない初期値と、決定または外生情報の結果として直接的に時間とともに変化する値とを分離しておくと有用であることに注意してください。決して変化しない値は$S_0$に格納されますが、$t > 0$に対する$S_t$には表現されません。この理由は、$S_t$をできるだけコンパクトに保ちたいという要望によるものです。

我々の方策$X^\pi(S_t\vert \theta)$が調整可能なパラメータを持つと仮定します。例えば、在庫システムを管理していて、おなじみの「発注点補充」方策(在庫理論の文献では$(s,S)$方策として知られる)を用いる場合を考えます。これは次式で与えられます。

ここで$\theta = (\theta^{min},\theta^{max})$です。簡単のため、発注するとすぐに到着すると仮定しましょう(実務では決して成り立たない標準的な教科書の仮定です)。これにより、物理状態$R_t$(即座に発注する直前の在庫量)の推移を次式を用いて書くことができます。

ここで$x_t = X^\pi(S_t\vert \theta)$であり、$\Dhat_{t+1}$は区間$(t,t+1)$における我々の製品に対する需要です(これが我々の外生情報$W_{t+1}$です)。最後に、$(t,t+1)$を区間$C(S_t,x_t,W_{t+1})$における純利益とします(これは今のところ重要ではありません)。

さて、我々のシステムのシミュレーションを実行できる過去の需要プロセス$W_1, W_2, \ldots, W_t, \ldots, W_T$があると想像してください。$\omega$をこの過去の需要(または任意の外生情報)の履歴系列を表すものとします。最適な発注パラメータ$\theta$の集合を見つける問題を次式を用いて書くことになります。

ここで状態変数は以下に従って推移します。

$\theta^\ast $を、$\eqref{eq:optimizingtheta}$を最適化することによって求めた$\theta$の値とします。この最適値を正しく書く方法は、$S_0$に含まれる情報に依存する関数$\theta^\ast (S_0)$としてです(これはまた、サンプルパス$\omega$にも依存します)。これは、$S_0$で表される問題への入力データを変更すると、それが我々の方策パラメータ$\theta$の最良の値に影響を及ぼしうるという現実を伝えるのに役立ちます。実際、方策の選択自体を変更しなければならないことすらあるかもしれません!

バリエーション

我々の基本的な数学モデルには2つの重要なバリエーションがあります。

• 時間$t$から反復$n$へ – 時間$t$よりもカウンタ$n$を使う方が自然な問題設定があります。反復とともに変化する変数を時間の推移とは異なる見方で捉えるため、単に$t$を$n$に変更するだけではありません。具体的には、添字$n$を上付き文字として置き、$S^n$、$x^n$、$W^{n+1}$のように書きます。

  この理由の一つは、我々が時間にわたる変数の集合$x_1, x_2, \ldots, x_t, \ldots, x_T$をベクトル$x=(x_1, x_2, \ldots, x_t, \ldots, x_T)$として捉えることです。これは決定論的な問題をモデル化する際に有用です(ベクトル$x$全体を一度に最適化するかもしれません)。それに対して、我々は$x^n$を時間とともに推移する関数として捉えます。

  より実務的には、$n$を上付き文字とすることで、反復シミュレーションを記述できるようになります。そこで、反復$n$に対する時間にわたる情報プロセスを次式を用いて書くことになります。

最良の方策を反復的に探索している場合、反復$n$に対する方策を$X^{\pi,n}(S_t)$を用いて書くことになり、これが以下を生成します。

ここで$x^n_t = X^{\pi,n}(S^n_t\vert \theta)$です。

• 最終報酬の最適化 – よくある設定は、最良の方策を探索するときに起こるような確率的探索を行っている場合です。アルゴリズムを評価する各反復は、必ずしもそうとは限りませんが、時間にわたるシミュレーションを必要とすることがあります。

  ここで、我々の決定変数がパラメータ$\theta$であり、方策$X^\pi(S_t\vert \theta)$とちょうど同じように機能するアルゴリズム$\Theta^\pi(S^{\theta,n})$があるとしましょう。ただし、$S^{\theta,n}$は$n$回目の反復におけるアルゴリズムの「状態」を捉えます。

  探索アルゴリズムはすべて逐次決定問題ですが、時間にわたるほとんどの逐次決定問題とは異なり、我々は$N$回の反復を実行したいのであり、最終的な解にのみ関心があります。「アルゴリズム」(方策)$\pi$に従いながら$N$回の反復を経た後の$\theta^n$の値を$\theta^{\pi,N}$とします。

  値$\theta^{\pi,N}$は我々の情報プロセス$W^1, \ldots, W^t, \ldots, W^N$の特定の系列に依存しますが、それを評価するには、$\What$と呼ぶことにする新しいサンプル集合を用いなければなりません。

  我々は最終報酬目的関数を用いてアルゴリズムの性能を評価します。これは次のように書きます。

簡単に言えば、$\Theta^\pi(S^{\theta,N})$と表記した$\theta$に対する学習方策を、$W^n$の観測(これは時間$t$にわたる全体のシミュレーションであるかもしれません)を用いて$N$回の反復にわたってシミュレートすることで評価します。パラメータ$\theta$の最終推定値(これを$\theta^{\pi,N}$と呼びます)を得たら、$\theta = \theta^{\pi,N}$を固定し、$m=1, \ldots, M$に対して$\What^m$と呼ぶ新しいランダム観測の集合を作成する別個のシミュレーションを用いて、この値の性能を評価します。

不確実性のモデル化

多くの複雑な問題(サプライチェーン、エネルギーシステム、公衆衛生などはほんの一例です)において、さまざまな形態の不確実性を特定してモデル化することは、豊かで複雑な作業になり得ます。ここでは生じる問題を示唆するにとどめ、この次元についての徹底的な議論は試みません。

不確実性は2つのメカニズムを通じて我々のモデルに伝えられます。すなわち、完全にはわからない量やパラメータを記述する確率分布のパラメータをモデル化する初期状態$S_0$と、外生情報プロセス$W_1, \ldots, W_T$です。

初期状態における不確実性

初期状態変数は、決定論的パラメータ、または動的に変化する量やパラメータの初期値を含むことがあります。もし初期状態に含まれるのがこれだけであれば、それは何らかの不確実性を捉えていることにはなりません。

我々がいくつかの量やパラメータについて知らないものの、確率分布のパラメータを通じて我々が知っていることを表現できる問題は数多くあります。いくつかの例を挙げます。

• 新薬に対する患者の反応。
• 価格の変化に市場がどう反応するか。
• 販売可能なレタスの在庫がどれだけあるか(不確実な数量がしおれてしまい、販売できなくなっているかもしれません)。
• 中国から以前に発注した在庫の箱が到着する時刻。
• 投資信託への預け入れ額は平均$\lambda$の周りでランダムに変動しますが、$\lambda$が何であるかはわかりません。

これらは、いくつかの入力に不確実性を持たせてモデルを初期化できる方法の例です。

初期の確率的信念は、主観的判断から、あるいは過去の観測や実験から得られることがあります。

外生情報プロセス

不確実性がモデルに入り込む2つ目の経路は、外生情報プロセスを通じてのものです。変数$W_t$は、時間period$t$まではわからない情報を含んでいます。これは、$W_{t+1}$の結果を知る前に、時間$t$において決定$x_t$を下さなければならないことを意味します。

以下は、決定$x_t$が下された後に明らかになる$W_{t+1}$の例のリストです。

• 経路を選択し、その後その経路上の移動時間を観測する。
• 薬を選択し、その後患者がどう反応するかを観測する。
• 触媒を選択し、その後それが生成する材料の強度を観測する。
• オンライン市場で宣伝する製品を選択し、その後売上を観測する。
• ウェブインターフェースのデザインを選択し、その後それが生み出すクリック数を観測する。
• 投資に資金を割り当て、その後投資の価格変化を観測する。

いずれの場合も、決定を下した後に観測される情報が、その決定の性能(そしてどの決定が最良であったか)に影響を与えます。

ここまで読んで読者はおそらく、$W_{t+1}$が通常は異なる種類の情報の集合であることに気づいたでしょう。例えば、血糖値が上昇している患者を治療していると想像してください。医師は、食事や運動、減量のための薬から、特に血糖値を標的とした投薬に至るまで、さまざまな戦略を試したいと考えています。医師が処理しなければならない情報源には以下が含まれるかもしれません。

• 患者が食事療法に取り組む意欲。
• 食事指示に対する患者の遵守度。
• 減量のための毎日の注射を受け入れる患者の意欲。
• (どのプログラムからの)実際の減量。
• 血糖値の実際の変化。

これらはそれぞれ別個の情報の流れです。我々は、時間$t$における情報プロセスの集合である集合$\Ical_t$を導入することで、これらをモデル化できます(戦略を変更するにつれて、新たな情報の流れが開かれ、この集合は変化することがあります)。これで、情報源$i\in\Ical_t$からの情報の実現値である$W_{t+1,i}$を用いて、異なる種類の情報を表現できるようになり、$W_{t+1} = (W_{t+1,i})_{i\in\Ical_t}$となります。

我々は引き続き$W_{t+1}$を用いて新たに到着する情報を表しますが、読者は、実際の応用においてはこれが通常、それぞれ独自の挙動を持つ情報源全体の集合を含むことになるということを覚えておく必要があります。

状態/決定依存プロセス

情報$W_{t+1}$が現在の状態$S_t$や決定$x_t$に依存する応用が数多くあります。いくつかの例を挙げます。

• 在庫が不足すると顧客を遠ざけ、需要が減少する可能性がある。
• 大量の株式を購入すると、その価格が上昇する可能性がある。
• ワクチンを推奨するという決定が、病気の進行に影響を与える可能性がある。
• 稼働中の発電機の数が、電力系統の価格を変化させる可能性がある。

このため、外生情報を関数$W_{t+1}(S_t,x_t)$、すなわち区間$(t,t+1)$に到着する情報を与える外生情報関数として表現するのが有用である。

例えば、大量の株式を売買しており、それが将来の価格に影響を与えるかもしれない状況を想像してほしい。そのダイナミクスは次のように書けるかもしれない。

この価格プロセスの状態は次のように書かれる。

$W_{t+1}(S_t,x_t)$で与えられる価格のランダムな変化は、価格の変化が現在の価格(価格が高ければ、将来の変化は負になりやすい)、および私たちが購入している量($x_t > 0$)や売却している量($x_t < 0$)に依存するかもしれないという私たちの信念を反映している。

もちろん、私たちは過去のデータを用いて、$S_t$と$x_t$が将来の価格に及ぼす構造的な影響を、真に外生的なノイズから切り分けたいと考えるだろう。そこで、次のようなモデルを提案するかもしれない。

ここで、次のように仮定するかもしれない。

このモデルは、$\varepsilon_{t+1}$が平均0を持ち、その分散は$x_t$の絶対値とともに増大すると仮定している。すると情報$W_{t+1}(S_t,x_t)$は平均$\theta^x x_t$を持つことになり、これは株式を購入している場合($x_t > 0$)には正となり、市場で売却している場合($x_t < 0$)には負となる。

本書では引き続き$W_{t+1}$を標準的な記法として用いるが、読者はこれが現在の状態や、状態が与えられたときに下された決定に依存する可能性があることに注意されたい。

不確実性のスタイル

情報の種類を特定することが、不確実性を理解するための第一歩である。次のステップは、不確実性の異なるスタイルを特徴づけることである。情報プロセスがとりうる挙動のうち、特に重要なものをいくつかまとめると以下のようになる。

• きめ細かい変動性 – これは秒単位(場合によっては1秒未満)、分単位、時間単位、あるいは日単位の時間スケールで生じることがある。
• シフト – プロセスのきめ細かい変動性は通常、平均値の周りでのばらつきを表すが、平均値が周期的に新たな水準へと移行することがある。これは新技術、競合他社の対応、あるいは経済の変化を反映している場合がある。
• バーストと断続的な需要 – 病気の広がりは、局地的にアウトブレイクが広がることで感染の急増を引き起こすことがある。ある顧客が製品を手に取り、それを友人に勧め、その友人がさらに別の友人に伝えるといったこともある。
• スパイク – 到来する吹雪は牛乳、卵、トイレットペーパーの需要を急増させることがあり、発電機の故障は電力価格の急騰を引き起こすことがある。
• 空間的事象 – 天候、病気、規制の変化は、地域的な性質を持つランダムな変化を引き起こすことがある。
• システミックな事象 – これらは、企業全体(国境をまたぐ場合も含む)、国全体、あるいは世界規模の影響を及ぼしうる事象である。これは通信網へのサイバー攻撃、世間の認識の変化、否定的な広告などによって生じることがある。
• まれな事象 – まれな事象は、地震、疾病の発生、テロ攻撃など様々な原因から生じうる。これらは発生頻度は非常に低い傾向があるが、いざ発生すると組織に大きな影響を及ぼしうる事象である。
• コンティンジェンシー(不測事態) – このカテゴリーは、起こりうるが過去の実績がない事象を指す。例えば、送電網の運用者は原子力発電所の故障に備えて計画を立てる。それがある国内で一度も起きたことがなくても、運用者はそれが起きた場合に備えたいと考えるかもしれない。

これらの挙動は、決定を下すための方策の選択に影響を与えうるものであり、次にこの話題を扱う。

不確実性は、企業、組織、さらには政府までもが計画を立てなければならない問題として広く認識されている。しばしば見落とされがちなのは、不確実性をモデル化する理由が、それが決定にどのような影響を与えるかを理解するためであるという点である。不確実性は常に、将来到着する情報プロセスと結びついているため、今下す決定が将来のこの情報によってどのように影響を受けるかを考えなければならない。

方策の設計

方策とは、決定を下すための手法である……いかなる手法であっても構わない。

方策とは、状態変数に含まれる情報を用いて決定を下す関数である。これは一見、明確に定義された問題のように聞こえる。何しろ、機械学習コミュニティ全体が、訓練データセットに適合する関数を見つけるという課題を中心に構築されているのだから。しかし、方策の設計はそれよりもはるかに豊かなものであり、この分野に携わるコミュニティの多様性がそれを物語っている。

図 1.2は、不確実性下での逐次決定を扱う、およそ15の異なる分野を代表する書籍の表紙を示している。これらは8種類の異なる記法体系を用いており、モデル化への取り組み方において根本的に異なるアプローチを採用している。中には、方策(埋め込まれた最適化問題を伴うもの)を目的関数と混同しているものもある。

方策の性能指標

決定論的最適化は、ある決定が別の決定よりも優れているかどうかを判断する目的関数によって特徴づけられる。逐次決定問題では、通常、式$\eqref{eq:objectivecumulativereward}$、$\eqref{eq:objectivecumulativerewardaverage}$、$\eqref{eq:objectivecumulativerewardsample}$で行ったように、方策の性能を評価する目的関数を持つことになる。

しかし実際には、方策はいくつかの競合する基準に基づいて選択される。

• 解の質 – 通常、式$\eqref{eq:objectivecumulativerewardsample}$のサンプル版の目的として表される、ある期間にわたる性能(コスト、利益、健康の成果など)に注目する。これは確率的な量であるため、平均的な性能だけでなく最悪の場合の性能も考慮しなければならない。
• 計算要件 – 運用の現場では実行時間が重要である。目的関数の場合と同様に、方策の計算にかかる時間も確率的な量であるため、平均実行時間と最悪実行時間の両方を考慮する必要がある。
• 透明性 – 決定を、誤りを含みうる入力データまで遡って追跡することがどれだけ容易かということ。
• 柔軟性・適応性 – 現実世界の問題は複雑になりうるため、複雑な状況に適応しなければならないことがしばしばある。
• 手法上の複雑さ – ある方策が(例えば)社内の分析担当グループによって実装される場合、その手法を実際に機能させられる見込みを考慮しなければならない。
• データ要件 – 方策が異なれば、必要とされるデータも異なる。

図 1.2に示された数理最適化のコミュニティは、最適方策について語ることがあるが、これは式$\eqref{eq:objectivecumulativereward}$の期待値を最適化することを意味する。しかし、これらすべての特性に注意を払うことが重要である。

方策の4つのクラス

図 1.2に掲載された書籍群は、時間の経過とともに決定を下すための様々な方法を特徴としている。実は、それらはすべて、明確に定義された方策のクラスに分類することができる。方策を作成するための根本的な戦略は2つあり、それぞれがさらに2つのクラスに分けられ、合計4つの方策クラスが生まれる。

方策検索 – これは、決定を下すための手法(関数)を横断的に探索し、その性能をシミュレーションして(式$\eqref{eq:objectivecumulativereward}$で行っているように)、長期にわたって平均的に最も良く機能する手法を見つけるというものである。これは、異なる手法のクラスにわたる探索だけでなく、ある手法に対する調整可能なパラメータの探索も含みうる。この考え方は、2つの方策クラスを生み出す。

• 1) 方策関数近似(PFA) – これらは、状態の解析的な関数であり、行動を直接指定するものである。式$\eqref{eq:introorderupto}$のオーダーアップツー方策や、式$\eqref{eq:adjustedforecastpolicy}$の調整済み予測を用いる方策がその好例である。
• 2) コスト関数近似(CFA) – これらは、通常元の問題を単純化した最適化問題を解くことを伴う方策であり、長期にわたって方策がより良く機能するよう助けるためのパラメータが導入されている。これは特に強力なアイデアであり、産業界で広く用いられている。本書の後半(第4章以降、糖尿病に対する最適な投薬を学ぶ箇所)では、CFAの事例をいくつも紹介する。

先読み方策 – ある決定の貢献(あるいはコスト)と、その決定によって将来生じる下流の貢献(あるいはコスト)の近似とを合わせて最適化することで、効果的な方策を構築することができる。ここでもまた、これを2つの方策クラスに分けることができる。

• 3) 価値関数近似(VFA) – 図 1.3に描かれたネットワークをたどり、ノード1からノード11への経路を見つけたいと想像してほしい。今、私たちがノード$S_t = i = 2$にいて、$t$がこれまでにたどったリンクの数を数えているとしよう。$V_{t+1}(S_{t+1})$を、ノード$S_{t+1}$(ノード4や5など)からノード11までの経路の価値(最大化していると仮定する)とする($V_{t+1}(S_{t+1})$をどのように得たかは気にしなくてよい)。決定$x_t$を、ノード$S_t = i$から出て通過するリンクとしよう。ノード$S_t$にいることの価値は次式で与えられる。

式$\eqref{eq:bellmangraph}$はベルマン方程式として知られている。図 1.3に描いたような決定論的なネットワークにおいて最良の経路を見つけるために用いられる場合、これは比較的容易に視覚化できる。

状態$S_t$から$S_{t+1}$への遷移が、時刻$t$の時点では既知でないランダムな情報を伴う問題は数多く存在する。私たちは、最初の在庫問題において不確実性の単純な例を見ており、2番目の在庫問題ではより複雑な例を見た。

こうしたより一般的な問題では、状態$S_t$にあり、決定$x_t$を下し、それから新たな情報$W_{t+1}$(時刻$t$の時点では既知でない)を観測すると、遷移関数に従って新たな状態$S_{t+1}$へと至ることになる。

これは、$x_t$を選ばなければならない時刻$t$において、$W_{t+1}$が確率変数であることを意味し、したがって$S_{t+1}$もまた確率変数であるということを意味する。この場合、ベルマン方程式に期待値を挿入する必要があり、式$\eqref{eq:bellmangraph}$を次のように書くことになる。

ここで、期待値$\E_{W_{t+1}}\lbrace \cdot\rbrace $を挿入したが、これは文字通り$W_{t+1}$のすべてのランダムな結果にわたって平均を取ることを意味する。

$\eqref{eq:bellmanstochastic}$における確率版のベルマン方程式は、極めて一般的なものである。状態$S_t$は単にグラフのノードを意味するのではなく、その問題に関連するあらゆる(そしてすべての)情報を捉えている。難しいのは、もはや価値関数$V_t(S_t)$を計算することができないという点であり、これはひいては、式$\eqref{eq:bellmangraph}$および$\eqref{eq:bellmanstochastic}$において既知であると仮定していた$V_{t+1}(S_{t+1})$が手に入らないということを意味する。

ベルマン方程式を適用しようとする際に研究コミュニティが用いてきた戦略は、機械学習の分野を活用して、私たちが$\Vbar_t(S_t)$と呼ぶことにする統計的近似を推定するというものである。妥当な近似$\Vbar_{t+1}(S_{t+1})$を得ることができると仮定すると、私たちの方策(決定を下すための手法)を次式を用いて書くことになる。

記法「$\argmax_x f(x)$」は、関数$f(x)$を最大化する$x$の値を意味する。添字$\pi$は、関数$f$の構造を規定する情報、および近似$\Vbar_{t+1}(S_{t+1})$に必要となる調整可能なパラメータ$\theta$を担っている。

この種類の方策は、近似動的計画法、そして最も頻繁には強化学習といった見出しの下に位置づけられる。これは強力なアイデアではあるが、適用は容易ではなく、正確な近似$\Vbar_{t+1}(S_{t+1})$を作成できるかどうかにかかっている。

価値関数を近似するための手法については非常に豊富な文献が存在するが、それは万能薬ではない。本書ではこの考え方をいくつかの箇所で示すが、読者はこのクラスの方策が使いこなすのが非常に難しいことに注意されたい。

• 4) 直接先読み近似（DLA） – 最初の3つのクラスのいずれを使っても効果的な方策を開発できない問題は数多くあり、そのような場合には直接先読み近似に頼らざるを得ない。これについては後で完全な数学的形式で記述するが、ここではひとまず、DLAとは、（通常は近似的な）モデルを用いて何らかの計画期間にわたって最適化を行いながら、現時点での決定を下すものだと説明しておく。

  よく用いられるDLAは、決定論的な近似モデルを作成することである。これは、ネットワークの各リンクに沿った移動時間が既知であると仮定して目的地までの最短経路を見つけるナビゲーションシステムを利用するときに行っていることである。一般的なルールとして、将来の厳密な確率的モデルを解くことはほぼ常に不可能であるため、本書では問題を近似するさまざまな戦略を検討していく。

我々は2つの在庫問題を用いてモデリングフレームワークを説明し、式$\eqref{eq:introorderupto}$と$\eqref{eq:adjustedforecastpolicy}$により2つの単純な方策（PFAの一形態）を提案したが、これはあくまで方策の具体例を示すために行ったものである。PFAは日々の意思決定において広く用いられているが、これらは特殊な例である。

対照的に、我々は先に概説した4つの方策クラス（PFA、CFA、VFA、DLA）が普遍的なものであり、あらゆる逐次決定問題を解くために用いうるあらゆる手法を網羅していると主張する。念のため言えば、これらはメタクラスである。つまり、ある問題が特定のクラスに適していると考えたとしても、それだけでは終わりではなく、そのクラス内で具体的な方策を設計する必要がある。とはいえ、この4つのクラスは方策設計のプロセスを導くロードマップを提供してくれると我々は考えている。

方策のテスト

方策の価値をテストするために、我々は式$\eqref{eq:objectivecumulativerewardsample}$を用いる。これは情報過程$W_t$の単一のサンプルパスにわたって方策をシミュレートするものである。方策をシミュレートする際に最も難しい部分は、通常、外生情報過程を作成することである。

$\omega$をサンプルパスとし、$W_1(\omega), \ldots, W_T(\omega)$が特定のサンプルパスを表すとする。表1.3は、$\omega^1$から$\omega^{10}$までインデックス付けされた価格の10本のサンプルパスを示している。もし$\omega^6$を選ぶならば、$W_7(\omega^6) = 44.16$となる。

問題は、表1.3に示されているような観測値のサンプルをどのように作成するかである。典型的な戦略は3つある。

• 過去のデータからサンプルを作成する。ある時点における結果は1つしか存在しないため、異なる期間の観測値を組み合わせることで複数のサンプルパスを作成できる。異なる年の価格や、異なる月の需要、異なる日に観測された移動時間などを選ぶことができる。このアプローチは、外生情報が状態$S_t$や決定$x_t$に依存する場合には使用できない。
• 数学モデルからシミュレーションする。このアプローチには、大規模なサンプルを生成して方策の性能について統計的に信頼できる推定値を得られるという利点がある。これらのモデルは非常に高度なものにすることができるが、（高度なものであっても）実際のデータの挙動を再現しないモデルを作成してしまうことは容易に起こり得る。最大の課題は、時間にわたる相関、あるいはサンプル間の相関（例えば異なる製品の需要、異なる株式の価格、異なる場所での風速など）を捉えることである。
• 実際に発生する観測値を用いて、現場でアイデアをテストすることができる。この利点は、実データを使って作業できることである（過去は将来と同じとは限らない）。欠点は、1日分の新しいデータを観測するのに1日かかることである（そして、1日分だけでなく、はるかに多くの観測が必要になる場合がある）。

もし$W_{t+1}$が状態$S_t$および／または決定$x_t$に依存する場合、我々はこの依存関係を反映する方法を考案しなければならない。数学モデルを作成すれば、コンピュータ上で多くのシミュレーションを実行することが可能になるが、情報過程のサンプルを作成するには、時間にわたる相関だけでなく、空間にわたる相関も再現する必要がある。不確実性のモデリングについてより詳しい議論は、RLSOの第10章を参照されたい。

次のステップ

本書の次の5つの章では、我々のモデリングフレームワークを5つの異なる問題に適用する。

• 第2章 – 資産売却問題
• 第3章 – 適応的市場計画
• 第4章 – 最良の糖尿病治療薬の学習
• 第5章 – 確率的最短経路問題 - 静的
• 第6章 – 確率的最短経路問題 - 動的

これらの各章は、上で2つの在庫問題を説明する際に用いたのと同じアウトラインに従う。このアウトラインは以下から構成される。

• ナラティブ – 問題の平易な英語（日本語）による説明。
• 普遍的モデル – このモデルは、逐次決定問題の5つの要素、すなわち状態変数、決定変数、外生情報変数、遷移関数、目的関数を記述するという我々の形式に従う。
• 不確実性モデル – ここでは、問題における不確実性の可能なモデルを提示する。
• 方策の設計 – 決定を下すための可能な方策を提案する。我々は、5つの応用設定が4つの方策クラスすべてを巡るツアーとなるように問題を選んでいる。ここでは、我々が選んでいる方策が4つのクラスのうちどれに該当するかを読者自身に見極めてもらうことにする。
• 拡張 – 最後に、方策の変更を必要とするかもしれない基本問題の1つ以上の可能な拡張を提案することがある。

その後、第7章で4つの方策クラスに立ち戻り、第2章から第6章までの問題を用いて様々なモデリングの考え方を説明しながら、我々の一般的なモデリングフレームワークについて議論する。

この議論の後、我々は例示による学習という章立てのパターンに戻るが、より複雑な問題を扱う。残りの章では以下の問題を扱う。

• 第8章 – エネルギー貯蔵 I
• 第9章 – エネルギー貯蔵 II
• 第10章 – サプライチェーン管理 I：2エージェント新聞売り子問題
• 第11章 – サプライチェーン管理 II：ビールゲーム
• 第12章 – 広告クリック最適化
• 第13章 – 血液管理問題
• 第14章 – 臨床試験の最適化

何を学んだか

• まず、決定とは何かを学んだ！
• あらゆる逐次決定問題に対する一般的なモデルである、普遍的モデリングフレームワークを提示した。
• 最初に、システムの状態が在庫量である古典的な在庫問題を用いてこのモデルを説明した。
• 次に、状態変数が在庫の資源状態$R_t$、価格$p_t$という形の情報状態変数、そして推定平均と分散という形での今後の需要$\Dhat_{t+1}$に関する信念状態を含む、やや複雑な在庫問題へと移行した。
• 複数の異なる情報源から到来しうる外生情報の流れをモデル化する方法を学んだ。外生情報は、状態および／または決定に依存しうる関数として表現される。
• 方策関数近似（PFA）と呼ばれる単純な方策クラスの2つの形態を例示した。
• 方策は、文脈や決定がどのように使われるかに応じて、さまざまな方法で評価できることを学んだ。
• 最後に、4つの方策クラスについて簡単な概観を示した。4つのクラスすべての例示は第2章から第6章で示され、その時点で第7章で立ち止まり、方策についてより深く議論し、第8章から第14章までのより複雑な問題への準備を整える。

演習問題

復習問題

1. 逐次決定問題の数学モデルの5つの要素とは何か？
2. 初期状態$S_0$の変数と、$t > 0$についての動的状態$S_t$の変数との違いは何か？
3. 決定と外生情報の違いは何か？
4. 方策の2つの主要なカテゴリーとは何か、そしてそれらはどのように異なるか？
5. 単純な在庫問題の状態変数を、より複雑な在庫問題の状態変数と比較せよ。

問題解決演習

1. 時間依存の挙動をどのように扱うかという観点から、2つの在庫問題に対する方策を比較せよ。例えば、我々のピザ店では、平日よりも週末の需要がはるかに高いかもしれない。調整可能なパラメータ$\theta$を時間依存（あるいは曜日依存）にすることが、解をどのように改善しうるかという観点からその価値についてコメントせよ。
2. 在庫問題においてパラメータ$\theta$をチューニングする方法を、以下の2つの場合について対比せよ。
   1. シミュレータにおいて。
   2. 現場において。
   それぞれのアプローチの長所と短所を論じよ。