ギッティンズ指数

ギッティンズ指数は、特定の特性を持つ特定の確率過程を通じて達成できる報酬の尺度です。つまり、過程には最終的な終了状態があり、各中間状態で終了するオプションを備えて進化します。特定の状態で終了すると、達成される報酬は、実際の終了状態から最終的な終了状態までのすべての状態に関連付けられた確率的期待報酬の合計です。指数は実数 スカラーです。

この理論を説明するために、発展途上の分野から、風力発電と波力発電という発電技術の2つの例を挙げることができます。2つの技術が両方ともアイデアとして提案されたときに、どちらが長期的に優れているかを言うことはできません。なぜなら、判断の根拠となるデータがまだないからです。^[1]長い浮体式発電機を作り、それを海まで曳いて必要なケーブルを敷設するよりも、多くの風力タービンを設置する方が簡単そうに思えるので、波力発電は開発が困難すぎると言うのは簡単です。

開発の初期段階で判断を下すと、一方の技術は棚上げにされ、もう一方の技術は開発され運用されることになるかもしれません。両方の技術を開発すれば、3か月ごとなどの一定の間隔で各技術の進捗状況を比較することで、それぞれの判断を下すことができます。次の段階への投資に関する決定は、その結果に基づいて行われます。^[1]

1979 年の論文「バンディット プロセスと動的割り当てインデックス」で、 ジョン C. ギッティンズはこのような問題の解決策を提案しています。彼は「スケジューリング問題」と「多腕バンディット」問題^{[2]という 2 つの基本機能を取り上げ、これらの問題を}動的割り当てインデックスを使用して解決する方法を示しています。彼はまず「スケジューリング問題」を取り上げ、それを、ジョブを実行する必要があり、各ジョブを完了するための一定の期間 (たとえば 1 時間ごとまたは 1 日ごと) を持つマシンに縮小します。マシンには、期間内に完了するかどうかに基づいて報酬値が与えられ、各ジョブが終了するかどうかの確率値が計算されます。問題は、「各段階で次にどのジョブを処理するかを決めて、期待される総報酬を最大化すること」です^[1]。次に彼は「多腕バンディット問題」に移り、「片腕バンディット」レバーを引くたびに、成功した引きに対しては報酬関数が割り当てられ、失敗した引きに対しては報酬がゼロになります。成功のシーケンスはベルヌーイ過程を形成し、成功の確率は不明です。複数の「盗賊」が存在し、成功したプルの分布は計算され、各マシンごとに異なります。ギッティンズは、ここでの問題は「無限のプルシーケンスから予想される総報酬を最大化するために、各段階で次にどのアームを引くかを決定すること」であると述べています。^[1]

ギッティンズは、「上記の問題は両方とも、それぞれが前のものよりも多くの情報に基づいた一連の決定を伴うものであり、これらの問題は両方とも動的割り当てインデックスによって解決できる可能性がある」と述べています。^[2]

応用数学において、「ギッティンズ指数」は、報酬関数と終了確率を持つ確率過程の状態に関連付けられた実数 スカラー値です。これは、将来終了する確率の下で、その状態から進化する過程によって達成できる報酬の尺度です。ギッティンズ指数によって誘導される「指数ポリシー」は、現在最も高いギッティンズ指数を持つ確率過程をいつでも選択することから成り、動的割り当ての問題などのいくつかの停止問題の解決策です。動的割り当てでは、意思決定者は、それぞれが確率的報酬を返す多数の競合プロジェクトに限られた労力を配分することにより、総報酬を最大化する必要があります。プロジェクトが互いに独立しており、一度に 1 つのプロジェクトのみが進化する場合、問題は多腕バンディット(確率的スケジューリング問題の一種) と呼ばれ、ギッティンズ指数ポリシーは最適です。複数のプロジェクトが進化する可能性がある場合、この問題はRestless banditと呼ばれ、Gittins インデックス ポリシーは既知の優れたヒューリスティックですが、一般に最適なソリューションは存在しません。実際、一般にこの問題はNP 完全であり、実行可能なソリューションが見つからないことは広く認められています。

臨床試験の文脈における最適な中止ポリシーに関する疑問は 1940 年代から存在し、1960 年代には数人の著者が最適なインデックス ポリシーにつながる単純なモデルを分析しました^[3]。しかし、一般的なケースの最適解は、各プロジェクトのすべての状態について、単一プロジェクトのダイナミクスの関数として「動的割り当てインデックス」が原理的に計算可能なインデックス ポリシーであることを、マルコフの枠組みでギッティンズと彼の協力者が実証したのは 1970 年代になってからでした [2]。[ ^{4 ]}ギッティンズと並行して、マーティン ワイツマンも経済学の文献で同じ結果を確立しました^{[5] 。}

Gittinsの独創的な論文のすぐ後、Peter Whittle ^[6]は、リタイアメントプロセスと呼ばれる問題の動的計画法による定式化から、 インデックスがラグランジュ乗数として現れることを実証し、同じインデックスが、より一般的な設定であるRestless banditでも優れたヒューリスティックになると推測しました。マルコフ連鎖のインデックスを実際に計算する方法という問題は、Varaiyaと彼の協力者^[7]によって、最大のインデックスから最小のインデックスまで計算するアルゴリズムで最初に取り組まれ、ChenとKatehakis ^[8]によって、標準のLPを使用して、より高いインデックス値を持つすべての状態を計算する必要なく、状態のインデックスを計算できることが示されました。LCM Kallenberg ^[9]は 、マルコフ連鎖のすべての状態のインデックスを計算するためのパラメトリックLP実装を提供しました。さらに、Katehakis と Veinott ^{[10] は}、インデックスはマルコフ連鎖上に構築されRestart in Stateとして知られるマルコフ決定プロセスの期待報酬であり、ポリシー反復アルゴリズムでその問題を解くことによって正確に計算できるか、または値反復アルゴリズムで近似的に計算できることを実証しました。このアプローチには、すべての大きなインデックスを計算することなく 1 つの特定の状態のインデックスを計算できるという利点もあり、より一般的な状態空間条件下で有効です。すべてのインデックスを計算するより高速なアルゴリズムは、マルコフ連鎖の最適停止のための消去アルゴリズムの結果として、 2004 年に Sonin ^[11]によって得られました。このアルゴリズムでは、プロセスの終了確率は、固定係数ではなく、現在の状態に依存する場合があります。2007 年に Niño-Mora ^{[12]によって、パラメトリック単体の構造を利用してピボット ステップの計算量を削減し、}ガウス消去アルゴリズムと同じ複雑さを実現する、より高速なアルゴリズムが提案されました。 Cowan, W. と Katehakis (2014) ^{[13] は}、潜在的に非マルコフ的で、無数の状態空間報酬プロセスを伴う問題の解決策を提示している。その枠組みでは、割引率が非均一で時間の経過とともに変化するか、各バンディットの活性化期間が固定でも均一でもなく、代わりに別のバンディットへの変更が許可されるまでの活性化の確率的な期間が条件となる。この解決策は、一般化された状態再開インデックスに基づいている。

Gittins らによる古典的な定義は次のとおりです。

${\displaystyle \nu (i)=\sup _{\tau >0}{\frac {\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]\right\rangle _{Z(0)=i}}{\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}\right\rangle _{Z(0)=i}}}}$

ここで、 は確率過程、は離散状態 に関連付けられた効用（報酬とも呼ばれる）、 は確率過程が終了しない確率、 はcが与えられた場合の条件付き期待値演算子です 。 ${\displaystyle Z(\cdot )}$${\displaystyle R(i)}$${\displaystyle i}$${\displaystyle \beta <1}$${\displaystyle \langle \cdot \rangle _{c}}$

${\displaystyle \langle X\rangle _{c}\doteq \sum _{x\in \chi }xP\{X=x|c\}}$

はXの 定義域である。 ${\displaystyle \chi}$

Whittle によって示された退職プロセスに関する動的計画法の定式化は次のとおりです。

${\displaystyle w(i)=\inf\{k:v(i,k)=k\}}$

価値関数はどこにありますか${\displaystyle v(i,k)}$

${\displaystyle v(i,k)=\sup _{\tau >0}\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z(t)]+\beta ^{t}k\right\rangle _{Z(0)=i}}$

上記と同じ表記で、

${\displaystyle \nu (i)=(1-\beta )w(i).}$

が報酬付きマルコフ連鎖である場合、 KatehakisとVeinott（1987）の解釈では、すべての状態に1つの任意の状態から再開するアクションが関連付けられ、それによってマルコフ決定プロセスが構築されます。 ${\displaystyle Z(\cdot )}$${\displaystyle i}$${\displaystyle M_{i}}$

その状態の Gittins 指数は、その状態から継続するか再開するかを常に選択できる場合に達成できる最高の総報酬です。 ${\displaystyle i}$${\displaystyle M_{i}}$${\displaystyle i}$

${\displaystyle h(i)=\sup _{\pi }\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z^{\pi }(t)]\right\rangle _{Z(0)=i}}$

ここで は上の政策を表す。 ${\displaystyle \pi}$${\displaystyle M_{i}}$

${\displaystyle h(i)=w(i)}$。

生存確率が状態に依存する場合、Sonin ^[11] (2008)によって導入された一般化では、Gittins 指数を終了の可能性あたりの最大割引総報酬として定義します。 ${\displaystyle \beta (i)}$${\displaystyle i}$${\displaystyle \alpha (i)}$

${\displaystyle \alpha (i)=\sup _{\tau >0}{\frac {R^{\tau }(i)}{Q^{\tau }(i)}}}$

どこ

${\displaystyle R^{\tau }(i)=\left\langle \sum _{t=0}^{\tau -1}R[Z(t)]\right\rangle _{Z(0)=i}}$

${\displaystyle Q^{\tau }(i)=\left\langle 1-\prod _{t=0}^{\tau -1}\beta [Z(t)]\right\rangle _{Z(0)=i}}$

、およびの定義においてが に置き換えられると、 ${\displaystyle \beta^{t}}$${\displaystyle \prod _{j=0}^{t-1}\beta [Z(j)]}$${\displaystyle \nu (i)}$${\displaystyle w(i)}$${\displaystyle h(i)}$

${\displaystyle \alpha (i)=h(i)=w(i)}$

${\displaystyle \alpha (i)\neq k\nu (i),\forall k}$

この観察から、ソニン^[11]は、それがギッティンズ指数の「真の意味」で はないと結論付けている。${\displaystyle \alpha (i)}$${\displaystyle \nu (i)}$

待ち行列理論では、ギッティンズ指数は、例えばM/G/1待ち行列におけるジョブの最適なスケジュールを決定するために使用されます。ギッティンズ指数スケジュールにおけるジョブの平均完了時間は、SOAPアプローチを使用して決定できます。^[14]待ち行列のダイナミクスは本質的にマルコフ的であり、確率性は到着プロセスとサービスプロセスに起因することに注意してください。これは、確率性がノイズ項を通じて明示的に説明されている学習文献のほとんどの研究とは対照的です。

従来の Gittins インデックスは報酬の発生を最適化するポリシーを誘導しますが、一般的な問題設定は、発生した報酬の比率を最適化することです。たとえば、これは、時間の経過に伴うデータで構成される帯域幅を最大化したり、時間の経過に伴うエネルギーで構成される電力消費を最小化したりするシステムの場合です。

このクラスの問題は、セミマルコフ報酬プロセスの最適化とは異なります。セミマルコフ報酬プロセスでは、より高い報酬を得るためだけに、滞在時間が不均衡な状態を選択する可能性があるからです。代わりに、これは線形分数マルコフ報酬最適化問題のクラスに対応します。

しかし、このような比率最適化の欠点は、ある状態で達成された比率が高くなると、終了確率が高いため、比率が低くなる状態が最適化によって選択される可能性があることです。そのため、比率が大幅に低下する前にプロセスが終了する可能性があります。このような早期終了を防ぐための問題設定は、各状態で見られる将来の比率の最大化として最適化を定義することです。この問題にはインデックス化が存在すると推測され、既存の状態再開アルゴリズムまたは状態除去アルゴリズムの単純なバリエーションとして計算可能であり、実際にうまく機能することが評価されています。^[15]

• Scully, Ziv、Harchol-Balter, Mor、Scheller-Wolf, Alan (2018)。「SOAP: すべての年齢ベースのスケジューリング ポリシーの 1 つのクリーンな分析」。コンピューティングシステムの測定と分析に関する ACM の議事録。2 (1)。ACM: 16。doi : 10.1145/3179419。S2CID  216145213。{{cite journal}}: CS1 maint: multiple names: authors list (link)
• ベリー、ドナルド A.、フリストット、バート (1985)。バンディット問題: 実験の順次割り当て。統計と応用確率に関するモノグラフ。ロンドン: チャップマン & ホール。ISBN 978-0-412-24810-8。{{cite book}}: CS1 maint: multiple names: authors list (link)
• Gittins, JC (1989)。マルチアームバンディットアロケーションインデックス。Wiley-Interscience Series in Systems and Optimization。序文：Peter Whittle。チチェスター：John Wiley & Sons, Ltd. ISBN 978-0-471-92059-5。
• Weber, RR (1992 年11月)。「多腕バンディットの Gittins 指数について」。応用確率年報。2 (4): 1024–1033。doi : 10.1214/ aoap /1177005588。JSTOR  2959678。
• Katehakis, Michael N. ; Veinott, Arthur F. Jr. (1987). 「多腕バンディット問題: 分解と計算」.オペレーションズリサーチの数学. 12 (2): 262–268. doi :10.1287/moor.12.2.262. JSTOR  3689689. S2CID  656323.
• Cowan, W. およびMN Katehakis ( 2014)。「一般的な減価償却とコミットメントの下でのマルチアームバンディット」。工学と情報科学における確率。29 : 51–76。doi : 10.1017/S0269964814000217。

• [1] インデックス計算アルゴリズムのMatlab/Octave実装
• コーワン、ロビン(1991)。 「ウサギとカメ: メリットの不明なテクノロジーの選択」。経済ジャーナル。101 (407): 801–814。doi :10.2307/2233856。JSTOR  2233856。