第3章：適応的市場計画
章の概要
本章では、いわゆる「新聞売り子問題」として広く知られる問題を表すために「適応的市場計画」という用語を用いる。この問題では、未知の市場需要を満たすために販売する資源(「新聞」)の量を選択しなければならず、使われなかった資源は販売期間の終わりに廃棄される。つまり、異なる時間期間は物理的につながっていない。
まず、この問題を用いて、最適な量に収束することが知られている基本的な確率的勾配アルゴリズムを説明する。このアプローチは、割り当てが少なすぎる場合に実際の需要を観測できず、代わりに販売できた量(利用可能にした在庫によって制限される)しか観測できないという問題を克服する。
確率的勾配アルゴリズムは、勾配にアクセスできる不確実性下での最適化において広く用いられている。確率的勾配アルゴリズムは1951年に初めて導入され、よく理解された収束特性を持つ。しかし、あまり知られていないのは、確率的勾配アルゴリズム自体が一つの逐次決定問題であり、その「決定」がアルゴリズムで使用されるステップサイズであるという考え方である。
確率的勾配アルゴリズムに関する古典的な文献は、極限においてこれらが単一期間問題の最適解(すなわち割り当てるべき最適な量)を生成するという性質に焦点を当てている。ほぼ完全に見過ごされているのは、これが実地の設定、すなわち結果が起こるにつれてそれを経験する設定で行われる場合、目的として累積報酬、すなわち時間にわたる報酬の合計を最大化するという課題を用いなければならないということである。
拡張の部分では、文献で見過ごされているひねりも導入する。実際には、需要が分からないだけでなく、需要の分布さえも分からない。各時間期間において、どれだけ売れたか(利用可能にした資源の量によって制限される)を観測し、この経験から学習して、次の時間期間にどれだけ割り当てるかを決定する前に需要分布についての信念を更新する。これにより、時間期間同士を結びつける信念状態が導入され、これはちょうど、残った在庫を次の時間期間に持ち越す場合に起こることと同様である。これは新聞売り子問題の古典的な扱いに欠けているもう一つの視点である。
これらの論点は、依然としてかなり単純で洗練された逐次決定問題に、かなりの豊かさを与えている。
問題の枠組み
3つの枠組み設定の質問に対する答えは以下の通りである:
- 指標: 計画期間にわたり、需要を満たすことから得られる期待収益から製品の購入コストを差し引いたものを最大化する。
- 決定: 各時間期間にどれだけの製品を購入するか。
- 不確実性: 各時間期間における製品への需要。
ナラティブ
不確実な(そして時には観測不可能な)需要を満たすために何らかの資源を割り当てることを含む問題群は幅広く存在する。例としては次のようなものがある:
- 生鮮在庫(例えば鮮魚)を確保して需要を満たすが、残った在庫は将来のために保持できない場合。
- 高度技術製造(例えばジェットエンジン)向けの部品を確保する場合で、既知の需要を満たすために部品を注文する必要があるが、部品が必要な仕様を満たさず廃棄しなければならない場合がある。したがって、5個の需要を満たすために、いくつかの部品が必要な工学仕様を満たさない可能性があるため、8個の部品を注文する必要があるかもしれない。
- タスクを完了するために時間を割り当てなければならない場合(職場への通勤やプロジェクト完了のための時間割り当てなど)。
- マーケティングなどの活動のために年次予算を割り当てなければならない場合。余った資金は会社に返還される。
最も単純な問題は、既知の分布を持つ不確実な需要を満たすためにこれらの決定を行うことを含むが、最も一般的な応用は未知で学習する必要がある分布を伴う。需要予測の利用可能性のような他の情報や、鮮魚の市場価格(資源決定が行われる前に既知か未知かもしれない)のような動的情報が存在することもある。
この問題は1950年代以来広く研究されており、当初は「単一期間在庫問題」として知られていたが、現在では主に「新聞売り子問題」として認識されている。これは不確実性下の最適化における標準的な問題として広く用いられている。
新聞売り子問題は典型的には次のように定式化される
\[\begin{align} \max_x \E F(x,W) = \E \big(p\min\{x,W\} - cx\big), \label{eq:newsvendorasymptotic} \end{align}\]ここで、$x$は需要を満たすための資源の量を決定する我々の決定変数であり、$W$は資源に対する不確実な需要である。我々は単位コスト$c$で資源を「購入」し、$x$と$W$のうち小さい方を価格$p$(これは$c$より大きいと仮定する)で販売すると仮定する。式$\eqref{eq:newsvendorasymptotic}$で与えられる目的関数は新聞売り子問題の漸近形式と呼ばれる。
新聞売り子問題には2つの重要な変種がある:
- 確率変数$W$の分布が既知である場合。
- $W$の分布が未知である場合。
未知の場合が実務においてより頻繁に生じるものであり、これは$x$を選択し、次に$x$と$W$のうち小さい方を観測するという反復を行うたびに、$W$の分布について何かを学習するという次元を導入する。
もし$W$が確定的であれば(そして$p > c$であれば)、解は容易に$x = W$であることが検証できる。次に、$W$が確率分布$f^W(w)$($W$は離散でも連続でもよい)を持つ確率変数であると想像しよう。$F^W(w) = Prob[W \leq w]$を$W$の累積分布とする。もし$W$が連続であり、$F(x) = \E F(x,W)$を計算できるならば、最適解$x^\ast $は次を満たすであろう
\[\left.\frac{d F(x)}{dx}\right\vert _{x=x^\ast } = 0.\]次に、$F(x,W)$の導関数を、$W$を知っていると仮定して取る、いわゆる確率的勾配を考えよう。これは次で与えられる
\[\begin{align} \frac{d F(x,W)}{dx} = \begin{cases} p-c & x \leq W, \\ -c & x > W. \end{cases} \label{eq:newsvendorstochasticgradient} \end{align}\]これは、確率変数$W$が与えられたときの$F(x,W)$の勾配(すなわち導関数)であり、これが「確率的」であるのは、我々が$x$を選択した後にのみ明らかになる確率変数$W$に依存するためである。これが、式$\eqref{eq:newsvendorstochasticgradient}$における$d F(x,W)/dx$が「確率的勾配」と呼ばれる理由である。
$\eqref{eq:newsvendorstochasticgradient}$の両辺の期待値を取ると
\[\begin{align*} \E \frac{d F(x,W)}{dx} &= (p-c) Prob[x \leq W] - c Prob[x > W] \\ &= (p-c) (1-F^W(x)) - c F^W(x) \\ &= (p-c) - pF^W(x) \\ &= 0 \quad \text{for } x = x^\ast . \end{align*}\]が得られる。これで$F^W(x^\ast )$について解くと
\[F^W(x^\ast ) = \frac{p-c}{p}.\]が得られる。したがって、$c$が0に減少するにつれて、確率1で需要を満たすような量$x^\ast $を注文したいことになる。$c$が$p$に近づくにつれて、最適注文量は確率が0に近づく形で需要を満たすことになる。
これは、0と1の間の数である$(p-c)/p$を計算し、次に、ランダムな需要が$x^\ast $未満である確率が$(p-c)/p$に等しくなるような注文量に対応する量$x^\ast $を見つけることを意味する。
我々はちょうど、注文量を正確に見つけられる2つの状況を見てきた:$W$を事前に知っている場合(これを完全予測と呼ぶことができる)、あるいは$W$の分布を知っている場合である。この結果は1950年代から知られており、観測データから$W$の分布を推定するための多数の論文や、$x < W$のとき$W$を直接観測できない状況(すなわち、需要ではなく販売数のみを観測する状況で、「打ち切り需要」として知られる)を扱う多数の論文を生み出した。
我々は需要分布が未知である問題に取り組もうとしている。我々のアプローチは、次で与えられる逐次探索アルゴリズムを用いることである
\[\begin{align} x^{n+1} = \max\left\{0,x^n + \alpha_n \left.\frac{d F(x,W^{n+1})}{dx}\right\vert _{x=x^n} \right\}, \label{eq:stochasticgradientalgorithm} \end{align}\]ここで、$\alpha_n$はステップサイズとして知られている。我々の課題は、各反復で$\alpha_n$を選択することである。
基本モデル
状態変数
状態変数は、方策および外生情報と共に、時刻$n+1$における状態を計算するために必要な時刻$n$における情報を捉える。式$\eqref{eq:stochasticgradientalgorithm}$の我々の探索手続きについて、我々の状態変数は次で与えられる
\[S^n = (x^n).\]決定変数
この問題の巧妙な点は、決定変数を認識することである。$x^n$が決定であると考えたくなるが、このアルゴリズムの文脈では、真の決定はステップサイズ$\alpha_n$である。我々のすべての逐次決定問題と同様に、決定(すなわちステップサイズ)は典型的にはステップサイズ則と呼ばれるものによって決定されるが、時にはステップサイズ方策とも呼ばれ、これを$\alpha^\pi(S^n)$と表記する。
通常、我々は方策を後で導入するが、モデルの理解を助けるために、調和ステップサイズ則と呼ばれる基本的なステップサイズ方策から始めることにする。これは次で与えられる
\[\alpha^{harmonic}(S^n\vert \theta^{step}) = \frac{\theta^{step}}{\theta^{step}+n-1}.\]これは単純な決定論的ステップサイズ則であり、これは$n$が分かれば、ステップサイズ$\alpha_n$が事前に分かることを意味する。以下では、より豊かな状態変数を必要とする、より興味深い確率的ステップサイズ方策を導入する。
また、$\alpha^\pi(S^n)$というステップサイズ方策によって決定される$x^n$の値を$X^\pi(S^n)$とする。
外生情報
外生情報は、我々が供給$x^n$で満たそうとしている資源(製品、時間、または資金)に対するランダムな需要$W^{n+1}$である。$W^{n+1}$を直接観測すると仮定してもよいし、あるいは単に$x^n \leq W^{n+1}$か$x^n > W^{n+1}$かのみを観測すると仮定してもよい。
遷移関数
$x$が制約されない設定に対する遷移方程式は、次で与えられる
\[\begin{align} x^{n+1} = x^n + \alpha_n \left.\frac{d F(x,W^{n+1})}{dx}\right\vert _{x=x^n}. \label{eq:stochasticgradientaltransition1} \end{align}\]式$\eqref{eq:stochasticgradientaltransition1}$が値$x^{n+1} < 0$を生成する可能性があることに注意すべきであり、これは実装できない。ここでの修正は単純で、単に$x^{n+1} = 0$と設定すればよい。
目的関数
各反復で、我々は次で与えられる純便益を受け取る
\[F(x^n,W^{n+1}) = p\min\{x^n,W^{n+1}\} - cx^n.\]さて、最良の方策を見つけるための目的関数を構築しなければならない。この問題設定には2つの方法でアプローチできる。1つ目では、実地で学習しなければならないと仮定し、2つ目では、方策を学習するためのシミュレータにアクセスできると仮定する。
実地での最適化
もし我々が実地で決定を経験しているならば、ある期間にわたる累積報酬を最大化したい。これは、次を解くことによって最良の方策(この設定では最良のステップサイズ則を意味する)を見つける必要があることを意味する
\[\begin{align} \max_\pi \E \left\{\sum_{n=0}^{N-1} F(X^\pi(S^n\vert \theta),W^{n+1})\vert S^0\right\}. \label{eq:newsvendorobjectivecumulativereward} \end{align}\]ここで、$S^{n+1} = S^M(S^n,X^\pi(S^n),W^{n+1})$はアルゴリズムの進化を表す(例えば式$\eqref{eq:stochasticgradientaltransition1}$で与えられる遷移関数)。ここで、$\pi$はステップサイズ則の種類(以下でいくつか検討する)、および任意の調整可能なパラメータ($\theta^{step}$など)を指す。
奇妙なことに、新聞売り子問題の背景にある話は常に実地での学習を含むにもかかわらず、式$\eqref{eq:newsvendorobjectivecumulativereward}$の累積報酬が目的関数として使われることは決してない。我々はこれを、「新聞売り子問題」について文献検索を行う読者のために言及する。
シミュレータを用いた最適化
あるいは、$N$回の反復のために探索を実行し、$x^N$で終わるシミュレータを使用しているかもしれない。我々は、ステップサイズ方策$\alpha^\pi(S^n)$への依存性を表現するために、この最終解を$x^{\pi,N}$と改名する。
我々の最終解$x^{\pi,N}$は、系列$W^1, \ldots, W^n$に依存するため確率変数である。以前と同様に、我々は$\omega$を$W^1(\omega), \ldots, W^n(\omega)$のサンプル実現として表し、我々の解を$x^{\pi,N}(\omega)$と書いて、これがサンプルパス$\omega$を使用したときに得られた解であることを示す。
我々はシミュレータを使用しているため、最終解の性能(最終報酬とも呼ばれる)にのみ関心があり、これを次のように書く
\[\begin{align} F(x^{\pi,N},\What) = p\min\{x^{\pi,N},\What\} - cx^{\pi,N}, \label{eq:newsvendorxpiNobjective} \end{align}\]ここで、$\What$は$x^{\pi,N}$の性能をテストするために使用する確率変数である。
これは、$\eqref{eq:newsvendorxpiNobjective}$で与えられる我々の目的関数に2つの確率変数があることを意味する。$W^1(\omega), \ldots, W^n(\omega)$の1つの実現の集合に対して、解$x^{\pi,N}(\omega)$が得られる。次に、$\psi$を$\What$のサンプル実現とする。したがって、解$x^{\pi,N}(\omega)$のサンプル実現と、我々のテスト変数$\What(\psi)$のサンプル実現があれば、我々の性能は
\[\begin{align} F(x^{\pi,N}(\omega),\What(\psi)) = p\min\{x^{\pi,N}(\omega),\What(\psi)\} - cx^{\pi,N}(\omega). \label{eq:newsvendorxpiNobjectivesample} \end{align}\]となる。我々が本当にやりたいのは、$x^{\pi,N}(\omega)$と$\What(\psi)$の両方の可能な実現にわたる平均を取ることであり、これは次を用いて書くことができる
\[\begin{align} \Fbar^\pi = \frac{1}{N} \frac{1}{M} \sum_{\omega=1}^N \sum_{\psi=1}^M \left(p\min\{x^{\pi,N}(\omega^n),\What(\psi^m)\} - cx^{\pi,N}(\omega^n)\right). \label{eq:newsvendorxpiNobjectivesampleaverage} \end{align}\]推定値$\Fbar^\pi$は、系列$W^1(\omega), \ldots, W^n(\omega)$の$N$個のサンプル、およびテスト変数$\What(\psi)$の$M$個のサンプルにわたる平均を表す。
不確実性のモデリング
$W$の分布を$f^W(w)$とする(これは離散でも連続でもよい)。累積分布関数は$F^W(w) = Prob[W \leq w]$である。分布は既知だが未知のパラメータを持つと仮定してもよい。例えば、$W$が平均$\mu$のポアソン分布に従うと想像すると、次で与えられる
\[f^W(w) = \frac{\mu^w e^{-\mu}}{w!}, \quad w=0, 1, 2, \ldots.\]$\mu$が既知であると仮定してもよく、その場合、本章冒頭で示した解析解を用いてこの問題を解くことができる。代わりに、$\mu$は未知であるが、既知の分布$p^\mu_k = Prob[\mu=\mu_k]$を持つと仮定しよう。この分布$p^\mu = (p^\mu_k)_{k=1}^K$は、初期状態$S^0$の中でモデル化されることになる点に注意されたい。
方策の設計
我々はすでに、他の箇所で方策を記述する際のスタイルに倣って$\alpha^\pi(S^n)$と書く2種類のステップサイズ方策を導入している。
文献では非常に多様なステップサイズ方策（しばしばステップサイズ則と呼ばれる）が提案されてきた。最も単純で人気のあるものの一つが、次式で与えられる調和ステップサイズ方策である。
\[\alpha^{harmonic}(S^n\vert \theta^{step}) = \frac{\theta^{step}}{\theta^{step}+n-1}.\]図3.1は、$\theta^{step}$の様々な値に対する調和ステップサイズ則の挙動を示している。
調和ステップサイズ方策は決定論的方策とも呼ばれる。なぜなら、与えられた$n$に対するその値を事前に知ることができるからである。決定論的方策における課題は、データに対して適応することが許されない点である。このため、確率的な規則を用いることがしばしば有用となる。最も初期の単純な例の一つがKestenの規則である。
\[\alpha^{kesten}(S^n\vert \theta^{step}) = \frac{\theta^{step}}{\theta^{step}+K^n-1},\]ここで$K^n$は、勾配が何回方向を変えたかを数えるカウンタである。これは、積（あるいは$x$がベクトルである場合は内積）$(\nabla_x F(x^n,W^{n+1}))^T \nabla_x F(x^{n-1},W^n) < 0$を問うことで判定する。勾配が方向を変えているということは、我々が最適点の近傍にいて、それを飛び越えるようにステップしていることを意味するため、ステップサイズを減少させる必要がある。この式は次のように書かれる。
\[\begin{align} K^{n+1} = \begin{cases} K^n + 1 & \text{if } (\nabla_x F(x^n,W^{n+1}))^T \nabla_x F(x^{n-1},W^n) < 0, \\ K^n & \text{otherwise,} \end{cases} \label{eq:kestenupdate} \end{align}\]ここで$\nabla_x F(x^n,W^{n+1}) = \frac{d F(x,W^{n+1})}{dx}$である。
これで、確率変数$K^n$に依存するステップサイズが得られたことになり、これを確率的ステップサイズ則と呼ぶ理由である。Kestenの規則を用いる場合、状態変数を修正して$K^n$を含める必要があり、次のようになる。
\[S^n = (x^n,K^n).\]また、遷移関数に式$\eqref{eq:kestenupdate}$を追加する必要がある。
AdaGradとして知られる別のステップサイズ則は、$x$が要素$x_i,~i=1, \ldots, I$を持つベクトルである場合に特に適している。表記を少し簡略化するため、要素$x_i$に関する確率的勾配を次式で与えることとする。
\[g^n_{i} = \nabla_{x_i} F(x^{n-1}, W^n).\]ここで、$(i,i)$番目の要素$G^n_{ii}$が次式で与えられる$I \times I$対角行列$G^n$を作る。
\[G^n_{ii} = \sum_{m=1}^n (g^n_{i})^2.\]そして、$i$番目の次元に対するステップサイズを次式を用いて設定する。
\[\begin{align} \alpha_{ni} = \frac{\theta}{(G^n_{ii})^2 + \epsilon}, \label{eq:adagrad} \end{align}\]ここで$\theta$は（調和ステップサイズ式の$\theta^{step}$に相当する）調整可能なパラメータであり、$\epsilon$はゼロ除算の可能性を避けるための小さな数（例えば$10^{-8}$）である。
図3.2は、反復回数の関数として$F(x^n,W^{n+1})$を示すことで、異なるステップサイズ則に対する収束速度の違いを示している。もし我々が$\eqref{eq:newsvendorxpiNobjectivesampleaverage}$における最終報酬を最適化しているのであれば、予算$N$に依存する、最も高い位置にある線を選べばよいことになる。もし我々が式$\eqref{eq:newsvendorobjectivecumulativereward}$における累積報酬を最適化しているのであれば、曲線の下側の面積に着目する必要があり、これは急速な初期収束を優遇することになる。
拡張
1) $\mu$を我々が知らないと想像してみよう。ただし、$\mu$は値$(\mu_1, \mu_2, \ldots, \mu_K)$のいずれかを取り得るとする。$n$番目の実験までの観測履歴を$H^n$とし、$H^0$を初期の空の履歴とする。我々は、次のように書く$\mu$に関する初期の事前確率から出発すると仮定する。
\[p^0_k = Prob[\mu = \mu_k\vert H^0].\]$W^1, \ldots, W^n$を観測した後、我々は更新後の分布を次のように書くことになる。
\[p^n_k = Prob[\mu = \mu_k\vert H^n].\]ベイズの定理を用いて$p^n = (p^n_k)_{k=1}^K$を更新することができる。
\[\begin{align} p^{n+1}_k &= Prob[\mu=\mu_k\vert W^{n+1}=w,H^n] \\ &= \frac{Prob[W^{n+1}=w\vert \mu=\mu_k,H^n]Prob[\mu=\mu_k\vert H^n]}{Prob[W^{n+1}=w\vert H^n]}\\ &= \frac{Prob[W^{n+1}=w\vert \mu=\mu_k]p^n_k}{Prob[W^{n+1}=w\vert H^n]}, \end{align}\]ここで
\[Prob[W^{n+1}=w\vert H^n] = \sum_{k=1}^K Prob[W^{n+1}=w\vert \mu=\mu_k]p^n_k.\]この基本モデルへの拡張により、我々は2つの確率分布——真の平均$\mu$に関する信念と、$\mu$のもとでのランダムな需要$W$——を持つことになる。この拡張を組み込むためには、$p^n$を状態変数に挿入する必要があり、次のように書くことになる。
\[S^n = (x^n, p^n).\]2) 我々の問題が、月$n$に商品（石油や天然ガスなど）を購入し、それを月$n+1$の間に使用するというものであると想像してみよう。我々は単価$c$でその商品を購入し、未知の需要$D^{n+1}$まで未知の価格$p^{n+1}$で販売する。この問題の目的関数を次のように書くことになる。
\[\begin{align} F^n(x^n,W^{n+1}) = p^{n+1} \min(x^n,D^{n+1})-cx^n. \label{eq:newsvendorextension1} \end{align}\]何を学んだか
- 我々は、逐次決定問題として確率的勾配アルゴリズムを説明するために、newsvendor問題という文脈を用いた。第1章で紹介した逐次決定問題の5つの要素を用いて、確率的勾配アルゴリズムをどのようにモデル化するかを示した。
- ステップサイズを選択するためのPFA方策のいくつかの例を紹介した。
- newsvendor問題は古典的には、最終的に選んだ$x$の性能のみに関心がある最良の解を探索する静的な問題として述べられる。本章では、2つの目的――現場でのオンライン学習（最適化）のための累積報酬と、最良の学習方策を設計するためにシミュレータを使用する場合の最終報酬――を導入した。
- 製品に対するランダムな需要のために確率分布（この場合はポアソン分布）を用いるという考え方を導入した。ここでポアソン分布の平均自体が確率変数となっている。
- ポアソン分布の平均に関する確率分布を適応的に学習するという拡張を導入した。
- また、決定$x_t$を、価格$p_t$のような他の状態変数に依存させるという問題も導入した。これは、状態$S_t$が（この設定においては）価格$p_t$に依存する方策$X^\pi(S_t)$を作ることと同じである。これはnewsvendor問題についての考え方における大きな転換であるが、我々の逐次決定問題すべてと同じクラスに属するものである。
演習問題
復習問題
- 我々の逐次探索アルゴリズムの決定変数は何か。
- 方策のクラスを探索する例を（2つ）挙げ、それぞれの方策クラスの調整可能なパラメータを示せ。
- *累積報酬*目的関数と*最終報酬*目的関数が何を意味するかを書き出せ。
- 調和ステップサイズ則の調整可能パラメータ$\theta^{step}$を探索する場合、累積報酬を用いて得られる$\theta^{step}$の最適値は、最終報酬を用いた場合の最適値とどのように比較されると考えられるか。
- 需要$W$の分布が分からないと仮定した場合、シミュレータにおいて最適な$x^\ast $を見つけることが意味をなさない理由を論じよ。これを踏まえると、シミュレータを学習方策の最適化のために使う方が理にかなっている。シミュレータを用いて学習方策を最適化する場合、この学習演習にはどのような目的関数が適切か。
問題解決演習
- ある大手産業ガス会社は、「テイク・オア・ペイ」契約を用いて、1か月前に電力の契約を購入しなければならない。もし会社が月$t+1$のために$x_t$メガワット時を購入する契約を結んだ場合、それが必要かどうかにかかわらず価格$p_t$を支払う。しかし、月$t+1$の負荷（需要）$L_{t+1}$が$x_t$を超える場合、会社はスポット価格$p^{spot}_{t+1}$で送電網から電力を購入しなければならない。月$t+1$の負荷を満たすコストは次のようになる。
$$
C(S_t,W_{t+1}) = p_t x_t + p^{spot}_{t+1} \max\{0, L_{t+1}-x_t\}.
$$
我々は異なる価格と負荷を観測することができるが、その確率分布は分からない。我々の目標は、1年間のコストを最小化することである。
$x_t$は値$x_1, \ldots, x_M$を取る離散変数であると仮定する。$(\mubar_{tx}, \beta_{tx})$を、$\E C(S_t,W_{t+1})$の推定値の平均と精度とし、*区間推定*と呼ばれる方策$X^{IE}(S_t\vert \theta)$を用いて$x_t$を選択すると仮定する。
$$
X^{IE}(S_t\vert \theta^{IE}) = \argmin_x \left(\mubar_{tx} - \theta^{IE} \sqrt{\frac{1}{\beta_{tx}}}\right).
$$
- 状態変数$S_t$と外生情報$W_{t+1}$を与えよ。
- 1年間の累積コストを最小化する$\theta^{IE}$を見つけるための目的関数を書け。期待値演算子の下付き添字として確率変数を書くことで（$\E_Y$のように）、各確率変数にわたる期待値を示せ。そして、各確率変数について$K$個のサンプルがあると仮定した場合に、期待値をシミュレーションとしてどのように書くかを示せ。
- 数値微分を用いて(b)の目的関数の勾配を求める公式を与え、$N$回の反復以内で$\theta$の良い値を見つけるための確率的勾配アルゴリズムを書き出せ。
- ここで、価格が$p_{t+1} = \eta_0 p_t + \eta_1 p_{t-1} + \eta_2 p_{t-2}$に従って推移すると仮定する。この場合、状態変数は何になるか、また状態変数に次元を追加することは、上記の最適な$\eta$を見つける問題をどのように複雑にするか。
- 上記の拡張2を考える。ここで価格$p$は反復に伴って変化するようになり、時刻$n$に受け取る価格は時刻$n$では知られていないため、これを$p^{n+1}$と表記する。ここでは、$p^{n+1}$は$p^n$と独立であり、$D^{n+1}$は$D^n$と独立であると仮定する。
- 式$\eqref{eq:newsvendorextension1}$のモデルについて、状態変数$S^n$と外生情報変数$W^n$を与えよ。
- この問題に対する確率的勾配アルゴリズムを示し、それが価格が一定であった場合のものと基本的に同じであることを示せ。
- 演習7を拡張するが、今度は価格が次式に従って推移すると仮定する。
$$
p^{n+1} = \eta_0 p^n + \eta_1 p^{n-1} + \eta_2 p^{n-2} + \varepsilon^{n+1}
$$
ここで$\varepsilon^{n+1}$は、価格過程とは独立な平均0の雑音項である。
- 式$\eqref{eq:newsvendorextension1}$のモデルについて、状態変数$S^n$と外生情報変数$W^n$を与えよ。
- この問題に対する確率的勾配アルゴリズムを与えよ。
- 次に、我々の目的が次式を最適化することであると仮定する。
$$
\begin{align}
F^n(x^n,W^{n+1}) = p^n \min(x^n,D^{n+1})-cx^n. \label{eq:newsvendorextension2}
\end{align}
$$
式$\eqref{eq:newsvendorextension2}$と$\eqref{eq:newsvendorextension1}$との唯一の違いは、今度は決定$x^n$を選ぶ*前に*価格$p^n$を見ることができるという点である。これは、価格がどのように添字付けされているかによって分かる。
- 式$\eqref{eq:newsvendorextension2}$のモデルについて、状態変数$S^n$と外生情報変数$W^n$を与えよ。
- この問題に対する確率的勾配アルゴリズムを与えよ。前の問題と異なり、この勾配は$p^n$の関数となる。
- 価格が発注決定の後にのみ明らかになる式$\eqref{eq:newsvendorextension1}$の目的関数に戻るが、今度は$p^{n+1}$が次のように履歴に依存するとする。 $$ p^{n+1} = p^n + \varepsilon^{n+1}. $$ 上で示した内容を踏まえて、この問題にどのようにアプローチするかを議論せよ。
- 演習問題10を繰り返すが、今度は次を仮定する。 $$ p^{n+1} = 0.5 p^n + 0.5 p^{n-1} + \varepsilon^{n+1}. $$
- 演習問題10を繰り返すが、今度は数量$x^n$が次の制約$0 \leq x \leq R^n$の下で選択されるとする。ただし $$ R^{n+1} = \max\{0, R^n + x^n - W^{n+1}\}, $$ であり、価格$p=p^n$は決定を下す前に明らかになる。この変更により、我々の問題は伝統的な在庫問題となる。
- フレキシブル・スペンディング・アカウント（FSA）は、人々が医療費を賄うために税引き前の資金を積み立てることを可能にする会計制度である。年$t$の終わりに、年$t+1$において利用可能にしたい金額を割り当てなければならない。課題は、口座に入れすぎると、残った分を失ってしまうことである。
年$t+1$における医療費を$M_{t+1}$とし、年$t$の終わりに年$t+1$に使うために割り当てる金額を$x_t$とする。限界税率を$r$とし、ただし$0 < r < 1$とする。年$t+1$における総支出は次で与えられる。
$$
C(x_t,M_{t+1}) = x_t + \frac{1}{1-r}\max\{0,M_{t+1} - x_t\}.
$$
次の形式の確率的勾配アルゴリズムを使用したいとする。
$$
x_{t+1} = x_t + \alpha_t \gbar_{t+1},
$$
ここで
$$
\gbar_{t+1} = (1-\eta)\gbar_t + \eta \frac{dC(x_t,M_{t+1})}{dx_t}
$$
であり、$0 < \eta < 1$は平滑化係数である。ステップサイズについては、次を使用する。
$$
\alpha_t = \frac{\theta^{step}}{\theta^{step} + K_t -1},
$$
ここで$K_t$は、コスト関数の導関数が符号を変えた回数を数える。すなわち
$$
K_{t+1} = \begin{cases} K_t +1 & \text{if } \frac{dC(x_t,M_{t+1})}{dx_t} \frac{dC(x_{t-1},M_t)}{dx_{t-1}} < 0. \\ K_t & \text{otherwise.} \end{cases}
$$
ここでの課題は、この問題を逐次決定問題として定式化することにより、ステップサイズパラメータ$\theta^{step}$と平滑化パラメータ$\eta$を決定することである。ステップサイズ則の性能を評価するためのシミュレータが利用できると仮定せよ。
まず、$M_{t+1}$の分布が既知であると仮定して、最適解を求めることから始める。
- $\frac{dC(x_t,M_{t+1})}{dx_t}$とは何か。これは$M_{t+1}$が既知になった後に計算されることを思い出そう。
- （a）の導関数をゼロと等置し、$x^\ast $について解くことにより、最適な静的解を求めよ。累積分布関数$F^M(m) = Prob(M_{t+1} \leq m)$は既知であると仮定せよ。
- この動的システムの状態変数は何か。
- 決定変数は何か。
- 外生情報は何か。
- 遷移関数は何か。状態変数の各要素について式が必要であることを思い出そう。
- 目的関数は何か。何について最適化しているのか。
- 私たちが販売するガスの価格は月ごとに変化すると仮定する。月間利益関数は次で与えられる。
$$
F_t(x_t,W_{t+1}) = p_{t+1} \min(x_t,W_{t+1}) - cx_t,
$$
ここで$D_{t+1}$は月$t + 1$における電力（メガワット時単位）の需要である。
簡単のため、価格プロセスは次のように推移すると仮定する。
$$
p_{t+1} = \begin{cases} p_t - 1 & \text{with probability 0.2,} \\ p_t & \text{with probability 0.6,} \\ p_t + 1 & \text{with probability 0.1.} \end{cases}
$$
- 演習問題15の（a）で最初に示したモデルの5つの要素を書き直せ。$x_t$を探す代わりに、今度は$x_t(p_t)$を探していることに注意せよ。これは、スカラーを探す代わりに、今度は関数を探していることを意味する。
- まず、$x_t(p_t)$をルックアップテーブル関数として表現することから始める。これは、$p_t$を離散価格の集合$(0, 1, 2, \ldots, 50)$に離散化することを意味する。コーディングを行わずに、関数$x_t(p_t)$を推定するために使用する手法の手順を説明せよ（あなたの説明は、それをもとに誰かがコードを書けるほど注意深いものでなければならない）。この問題の複雑さを基本モデルと比較せよ。
- （b）を繰り返すが、$x_t(p_t)$のルックアップテーブルの代わりに、次を用いて方策の関数形式を近似せよ。 $$ x_t(p_t\vert \theta) = \theta_0 + \theta_1 p_t + \theta_2 \ln{p_t} + \theta_3 \exp{\{\theta_4 p_t\}}. $$ 再び、$\theta$を見つけるための適応アルゴリズムの手順を説明せよ。
プログラミング演習
これらの演習問題は、tinyurl.com/sdagithubにあるPythonモジュール AdaptiveMarketPlanning を使用する。
- 空気を液体酸素および液体窒素に変換する大手産業ガス会社は、電力生産のために天然ガスの契約を結ばなければならない。契約は、1か月前に署名され、翌月分のガスの数量を提供する。月$t+1$における電力（メガワット時単位）の需要を$W_{t+1}$とし、月$t$の初めに決定され、月$t + 1$に購入されるガスの数量を$x_t$とする（これを$x_{t,t+1}$と添字付けすることもできただろう）。
私たちは（通常は百万btu単位で測定される）ガスを、同等のメガワット時（mwh）当たり20ドルの価格で購入し、同等のmwh当たり26ドルの価格で販売すると仮定する（後ほど、これらの価格に不確実性を導入する）。
簡単のため、確率変数$W_1,W_2, \ldots, W_t,$は定常であり、すべて同じ分布に従うが、その分布は未知であると仮定する。月$t$における利益は次で与えられる。
$$
F_t(x_t,W_{t+1}) = p \min\{x_t,W_{t+1}\} - cx_t.
$$
さらに、次で与えられる、発注数量$x_t$を求めるための確率的勾配アルゴリズムを使用すると仮定する。
$$
x_{t+1} = x_t + \alpha_t \nabla F_t(x_t,W_{t+1}).
$$
最後に、ステップサイズは次で与えられると仮定する。
$$
\alpha_t = \frac{\theta^{step}}{\theta^{step} + N_t - 1},
$$
ここで$N_t$は勾配が符号を変えた回数を数える。$N_t$の更新式を次を用いて書く。
$$
N_{t+1} = \begin{cases} N_t + 1 & \text{if } \nabla F_{t-1}(x_{t-1},W_t)\nabla F_t(x_t,W_{t+1}) < 0, \\ N_t & \text{otherwise.} \end{cases}
$$
- この問題のモデルの5つの要素を書き出せ。目的関数については、$T = 24$か月の期間にわたる天然ガスの売買から得られる総利益を最大化する最良の方策（これはアルゴリズムとなる）を見つけたい。方策の探索とは、$\theta^{step}$の最良値を見つけることを指すことに注意せよ。
- tinyurl.com/sdagithubにあるPythonパッケージ *AdaptiveMarketPlanning* を使用して、（a）のモデルについて$\theta^{step} = (2,5,10,20,50)$を評価せよ。
- 累積報酬ではなく終端報酬を最適化する場合、目的関数はどのように変化するか。$W$に関する期待値を取る場合は$\E_W$のような記法を用いて、期待値をその入れ子形式で書き出すこと。
- （同じ値を用いて）最良の$\theta^{step}$の探索を繰り返すが、今度は（c）で示した最終報酬の定式化を用いよ。
- 今度は、目的関数が次で与えられると仮定する。 $$ F_t(x_t,W_{t+1}) = p_{t+1} \min(x_t,W_{t+1}) - cx_t. $$ ここでは、私たちが市場に販売する電力に対して受け取る価格を知ることなく、数量$x_t$の契約を結ばなければならないと仮定する。その代わり、価格$p_{t+1}$は月$t + 1$の間に明らかになる。この変更は、あなたのモデルと解法戦略にどのような影響を与えるか。