Events
CRiSM Seminar
2nd Feb - 3pm - 4pm A1.01 - Azadeh Khaleghi (Lancaster Univeristy)
Title: Approximations of the Restless Bandit Problem
Abstract: In this talk I will discuss our recent paper on the multi-armed restless bandit problem. My focus will be on an instance of the bandit problem where the pay-off distributions are stationary $\phi$-mixing. This version of the problem provides a more realistic model for most real-world applications, but cannot be optimally solved in practice since it is known to be PSPACE-hard. The objective is to characterize a sub-class of the problem where good approximate solutions can be found using tractable approaches. I show that under some conditions on the $\phi$-mixing coefficients, a modified version of the UCB algorithm proves effective. The main challenge is that, unlike in the i.i.d. setting, the distributions of the sampled pay-offs may not have the same characteristics as those of the original bandit arms.
In particular, the $\phi$-mixing property does not necessarily carry over. This is overcome by carefully controlling the effect of a sampling policy on the pay-off distributions. Some of the proof techniques developed can be more generally used in the context of online sampling under dependence. Proposed algorithms are accompanied with corresponding regret analysis. I will ensure to make the talk accessible to non-experts.