Back to activities
ISS Informal Systems Seminar

Restless bandits: Indexability, Whittle index computation and learning

iCalendar

Jul 9, 2021   10:15 AM — 11:15 AM

Nima Akbarzadeh McGill University, Canada

Nima Akbarzadeh is a Ph.D. candidate in electrical and computer engineering at McGill University. He received the B.Sc. degree in electrical and computer engineering from Shiraz University, Iran, in 2014, the M.Sc. in electrical and electronics engineering from Bilkent University, Turkey, in 2017. He is a recipient of 2020 FRQNT PhD Scholarship. His research interests include stochastic control, reinforcement learning and multi-armed bandits.

Nima Akbarzadeh

Webinar link
Nº du webinaire : 910 7928 6959
Code secret : VISS

Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among several alternative processes where the evolution of the process depends on the resource allocated to them. In 1988, Whittle proposed an index heuristic for restless bandit problems which has emerged as a popular solution approach due to its simplicity and strong empirical performance. The Whittle index heuristic is applicable if the model satisfies a technical condition known as indexability. We present two general sufficient conditions for indexability and identify simpler to verify refinements of these conditions for fully-observable models and a class of indexable models for the partially-observable ones. We show that a generalization of the adaptive greedy algorithm computes the Whittle index for all indexable restless bandits. Finally, we discuss a learning problem in restless bandits when the dynamics of all processes are unknown initially. The learning algorithm uses a Thompson sampling approach to estimate the unknown parameters and uses estimated Whittle index to choose actions. We provide an upper-bound on the regret with respect to an oracle who knows the true parameters.

Peter E. Caines organizer
Aditya Mahajan organizer
Shuang Gao organizer
Rinel Foguen Tchuendom organizer
Yaroslav Salii organizer

Location

Online meeting
Zoom
Montréal Québec
Canada

Associated organization

Centre for intelligent machines (CIM)

Research Axes

Research application