Almost optimal policies for stochastic systemswhich almost satisfy conservation laws
Almost optimal policies for stochastic systemswhich almost satisfy conservation laws
复制标题
几乎满足守恒定律的随机系统的近最优策略
DOI：
--
复制
发表时间：
1999
影响因子：
4.8
通讯作者：
R. Garbe
中科院分区：
文献类型：
--
作者：
K. Glazebrook;R. Garbe
当受控随机系统的性能满足广义守恒律（GCL）时，利用agittin指数策略对性能为线性的目标进行优化。我们开发了系统不能满足gcl的程度的度量，并根据这些度量得出了合适的索引策略的次优性界限。除其他外，这些界限被用于探索多类G/G/1排队系统的cm‐类型规则在偏离指数服务时间假设时的性能鲁棒性。我们还研究了经典未折现和折现多臂盗匪问题的并行处理版本的Gittins索引策略。在未贴现的情况下，索引策略的成本在最优成本的常数范围内-该常数与提交调度的项目数量无关。在折现情况下，在相当温和的条件下，Gittins指数策略在O(1)数量的最优性范围内，因此当折现率足够小时是平均奖励最优的。
When controlled stochastic systems have performances which satisfy generalisedconservation laws (GCL), an objective which is linear in the performance is optimised by aGittins index policy. We develop measures of the extent to which a system fails to satisfyGCL and derive suboptimality bounds for suitable index policies in terms of such measures.These bounds are used, inter alia, to explore the robustness in performance of cm‐typerules for a multiclass G/G/1 queueing system to departures from an assumption of exponentialservice times. We also study Gittins index policies for parallel processor versions of theclassical undiscounted and discounted multi‐armed bandit problems. In the undiscountedcase, the cost of an index policy comes within a constant of the optimal cost ‐ thisconstant being independent of the number of projects submitted for scheduling. In thediscounted case, under fairly mild conditions, Gittins index policies come within an O(1) quantity ofoptimality and are hence average reward optimal when the discount rate is small enough.