Bandits and beyond: Index heuristics for dynamic resource allocation

该研究计划关注的是发展简单，但有效的方法，用于确定一些关键资源应如何分配随着时间的推移之间的一组实体，其中需要it.To固定一些想法，考虑的例子中描述的想象中的情况下，在文献中称为“随机多产品批量调度问题”：不同类型的产品到达一个持有站根据一些随机过程。它们被保存在那里，直到被车队中的一辆车运送到（比如说，零售商）。费用由储存在车站的物品产生。这些持有成本的性质在不同的产品类型之间可能有很大的不同。产品在运输空间要求方面也可能有所不同。在每个时间段的开始（比如每天的开始），必须决定应该派遣多少车辆以及它们的负载组成应该是什么。这样的决定可以部分地基于，比如说，当时在站处的每种产品类型的单元的数量。我们的目标是以最小化持有产品和调度车辆所产生的总成本的方式做出此类决策。用一些数学术语来说，决策者正在寻找一种动态政策，用于在一组实体（这里是产品类型）之间分配她的关键资源（即车队部署规则）。随机（随机演变）和复杂的情况。如何制定这样一项政策是极其困难的，尤其是因为评估各项决定时不仅要考虑其对费用的直接影响，而且还要考虑其对今后将产生的费用的影响。传统的方法，这样的问题，称为随机动态规划，是不可能能够很好地处理现实规模的问题。对决策者来说，最有价值的是一些有效的、但相当简单的、计算上容易处理的方法，这些方法可以根据车辆上（不同数量的）空间的相应产品类型来校准价值。然后，这种校准可用于为决策提供信息。简单的所谓基于索引的解决方案确实存在（并且非常有效），但主要是针对（土匪型）问题，这些问题对如何在实体之间分配关键资源造成了严重限制。该研究项目的目标是将这种简单的基于指数的解决方案的范围扩展到更一般的分配问题，这些问题不受这些限制。实际情况多种多样，具有上述例子的广泛特征。在研究方案期间制定的方法将产生在许多这类环境中进行资源分配的简单而有效的基于指数的办法。

The research programme is concerned with the development of simple, yet effective methods for determining how some key resource should be distributed over time among a collection of entities which require it. To fix some ideas, consider the example described in the following imagined scenario, referred to in the literature as the 'stochastic multiproduct batch dispatch problem' :Different types of products arrive at a holding station according to some random process. They are kept there until dispatched onward (to a retailer, say) by one of a fleet of vehicles. Costs are incurred by the items kept in storage at the station. The nature of these holding costs may differ markedly between product types. Products may also differ with regard to their space requirements for transportation. At the beginning of each time period (the start of each day, say), a decision has to be made regarding how many vehicles should be dispatched and what the composition of their loads should be. Such decisions may be based in part, say, on the number of units of each product type at the station at the time. The goal is to take such decisions in a way that minimises the overall costs incurred in holding the products and in dispatching the vehicles. To use some mathematical jargon, the decision-maker is looking for a dynamic policy for the allocation of her key resource (ie, a rule for the deployment of the fleet of vehicles) among a set of entities (here the product types) in a situation which is both stochastic (evolves randomly) and complex. How to develop such a policy is extremely difficult, not least because decisions must be assessed not only in terms of their immediate impact on costs but also with regard to their influence on the costs which will be incurred in the future. The conventional approach to such problems, called stochastic dynamic programming, is unlikely to be able to cope well with problems of realistic size . What would be invaluable to the decision-maker would be some effective, yet reasonably simple and computationally tractable, way of calibrating the value to the respective product types of (differing amounts of) space on the vehicles. Such calibrations could then be used to inform decision-making. Simple so-called index-based solutions do indeed exist (and are very effective), but mainly for (bandit-type) problems which impose serious limitations on how the key resource may be distributed among the entities. The goal of the research project is to extend the scope of such simple index-based solution approaches to more general allocation problems which are freed of such restrictions . There is a rich variety of practical situations which share the broad features of the above example. The methodologies developed during the research programme will yield simple and effective index-based approaches to resource allocation in many such settings.