Bandits and beyond: Index heuristics for dynamic resource allocation

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

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.