Seminar Series in Management Science and Quantitative Economics

Monotone Policies and Indexability for Bi-directional restless Bandits

Dr. Christopher Kirkbride
Lancaster University

8th of April, 2011 from 1200 to 1330
Seminars Theatre (Room 12), Serrano Anguita 8, 2nd Floor.

Motivated by a wide range of applications, we consider a development of Whittle's restless bandit model in which project activation requires a state-dependent amount of a key resource, which is assumed to be available at a constant rate.  As many projects may be activated at each decision epoch as resource availability allows. We seek a policy for project activation within resource constraints which minimises an aggregate cost rate for the system.

Project indices derived from a Lagrangian relaxation of the original problem exist provided the structural requirement of indexability is met. Verification of this property and derivation of the related indices is greatly simplified when the solution of the Lagrangian relaxation has a state monotone structure for each constituent project. We demonstrate that this is indeed the case for a wide range of bi-directional projects in which the project state tends to move in a different direction when it is activated from that in which it moves when passive. This is natural in many application domains in which activation of a project ameliorates its condition, which otherwise tends to deteriorate or deplete. In some cases the state monotonicity required is related to the structure of state transitions while in others it is also related to the nature of costs.

On occasion we are able to demonstrate a limited form of indexability which is nevertheless adequate for the purpose of policy design. Two numerical studies demonstrate the value of the ideas for the construction of policies for dynamic resource allocation, most especially in contexts which involve a large number of projects.

Christopher Kirkbride, PhD in Statistics, Newcastle University, UK. Chris is currently a Research Fellow at the Department of Management Science at Lancaster University. His main research fields are queueing theory, dynamic allocation models and heuristic solutions for stochastic decision problems.

 

To confirm your attendance and for any questions related to the seminar, please contact Prof. Dídac Ruiz-Hernández (d.ruiz@cunef.du).