Research Article
Optimal Index Rules for Single Resource Allocation to Stochastic Dynamic Competitors
@INPROCEEDINGS{10.4108/icst.valuetools.2011.245797, author={Peter Jacko}, title={Optimal Index Rules for Single Resource Allocation to Stochastic Dynamic Competitors}, proceedings={5th International ICST Workshop on Tools for solving Structured Markov Chains}, publisher={ACM}, proceedings_a={SMCTOOLS}, year={2012}, month={6}, keywords={optimality index rules gittins index whittle index lagrangian relaxation markov decision processes dynamic programming resource allocation restless bandits}, doi={10.4108/icst.valuetools.2011.245797} }
- Peter Jacko
Year: 2012
Optimal Index Rules for Single Resource Allocation to Stochastic Dynamic Competitors
SMCTOOLS
ICST
DOI: 10.4108/icst.valuetools.2011.245797
Abstract
In this paper we present a generic Markov decision process model of optimal single resource allocation to a collection of stochastic dynamic competitors. The main goal is to identify sufficient conditions under which this problem is optimally solved by an index rule. The main focus is on the frozen-if-not-allocated assumption, which is notoriously found in problems including the multi-armed bandit problem, tax problem, Klimov network, job sequencing, object search and detection. The problem is approached by a Lagrangian relaxation and decomposed into a collection of normalized parametric single-competitor subproblems, which are then optimally solved by the well-known Gittins index. We show that the problem is equivalent to solving a time sequence of its Lagrangian relaxations. We further show that our approach gives insights on sufficient conditions for optimality of index rules in restless problems (in which the frozen-if-not-allocated assumption is dropped) with single resource; this paper is the first to prove such conditions.