受限制策略下多臂Bandit過程的理論與套用研究

《受限制策略下多臂Bandit過程的理論與套用研究》是依託華東師範大學，由吳賢毅擔任項目負責人的面上項目。

基本介紹

• 中文名：受限制策略下多臂Bandit過程的理論與套用研究
• 項目類別：面上項目
• 項目負責人：吳賢毅
• 依託單位：華東師範大學

項目摘要

多臂Bandit過程模型（Multi-armed Bandit Processes,簡稱為MAB）起源於1950年代，屬於動態隨機最最佳化的範疇，是一種特殊類型的動態隨機控制模型，用於處理如何最優地進行稀缺資源的分配。從數學上來說，MAB由一組平行的可控隨機過程組成，每個隨機過程有兩個選項：演進和停止，一旦向前演進，該過程的信息會隨時更新，同時給出一個報酬流；一旦被停止，則其信息流和報酬都不會發生更新。MAB模型的目標是確定各個隨機過程演進和停止的規則（時間分配規則），滿足條件：在時間t，各個隨機過程進程時間之和不大於總時間t，並且使得期望折扣總報酬達到最大。本項目旨在MAB模型中引入受限策略的概念，以便刻畫現實中對策略的技術限制（比如在某個隨機過程達到一定的狀態時，不允許被停止），相應發展一套受限策略下MAB最優策略的新理論、新方法，並探索其在相關領域比如隨機調度領域的套用。

結題摘要

經典 bandit process 研究主要分為三類:連續時間、離散時間以及半馬氏類 過程(或者跳過程)上的 bandit process 最優決策問題,該框架對加工機器在各 個臂(arms)之間的切換不加任何約束。但是在實際問題中,往往會碰到加工機器 不能在各個臂之間自由切換的情形。 本項目研究帶約束 bandit process 的最優調度的理論及相關問題, 重要的結果包括三個部分:一是作為研究基礎的帶約束最優停時問題, 其中,可行的停時集合併不包括所有的停時,而是帶有一定約束的停時;二是以帶約束的最優停時理論作為基本工具, 獲得了帶約束 bandit process 的Gittins index的定義，並證明了基於Gittins index的策略在期望折扣報酬調度下的最有性; 三是帶約束bandit process調度理論套用於機器加工調度問題以及醫療調度的問題，得到了相應問題的最優解。 本研究本研究提出的模型涵蓋了幾乎所有的經典bandit process的模型，其結果從理論上拓廣了經典bandit process最優策略的研究和套用場景。