受限制策略下多臂Bandit过程的理论与应用研究

Multi-armed bandit processes (abbreviated as MAB), which are dated back to 1950s, belong to the framework of dynamic stochastic optimizaitons. They are a type of particular dynamic stochastic control models that are concerned with the problems of optimally allocating scareced resources to certain competitive projects. In mathematical language, an MAB constitutes of a set of parallel controllable stochastic processes, each of which has two options: evolution and freezen. Whenever a process evolves, it gives out a flow of rewards. MAB models aim at finding out the rules of evolution and freezen on each controllabel member stochastic processes (time allocation schemes) such that at any calander time t the sum of the time allocated to each projects is not more than t itself, so as to maximize the expected total rewards. The objective of this pproposal is to introduce the concept of restricted policies into the MAB community so as to characterize the restrictions on policies in the real life practice, e.g., freezing is prohibted if the process enters certain particular states, and accordingly develop the optimality theory of MAB under restricted policies, as well as explore the applications of that new theory in related areas including particularly the area of stochastic scheduling.

多臂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最优策略的研究和应用场景。