Approximations of the Restless Bandit Problem

Add to your list(s) Download to your calendar using vCal

• Azadeh Khaleghi (Lancaster)
• Friday 23 February 2018, 16:00-17:00
• MR12.

If you have a question about this talk, please contact Quentin Berthet.

The multi-armed restless bandit problem is studied in the case where the pay-off distributions are jointly stationary ϕ-mixing. This version of the problem provides a more realistic model for most real-world applications, but cannot be optimally solved in practice. Our objective is to characterize a sub-class of the problem where good approximate solutions can be found using tractable approaches. Specifically, it is shown that under some conditions on the ϕ-mixing coefficients, a modified version of UCB can prove 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, ϕ-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 in this paper can be more generally used in the context of online sampling under dependence. Proposed algorithms are accompanied by corresponding regret analysis.

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.