Particle Thompson sampling

Thompson sampling is an effective Bayesian heuristic for solving stochastic bandit problems. But it is hard to implement in practice due to the intractability of maintaining a continuous posterior distribution. Particle Thompson sampling (PTS) is an approximation of Thompson sampling based on the simple idea of replacing the continuous distribution by a discrete distribution supported at a set of particles. It is very flexible and easy to implement. This dissertation aims to analyze, improve and apply PTS. Firstly, we provide a thorough analysis of PTS for the two-arm Bernoulli bandit problem and a preliminary analysis of PTS for general stochastic bandit problems. Our main findings are that, fit particles survive, unfit particles decay, and most particles eventually decay. Secondly, we propose regenerative particles Thompson sampling (RPTS), an attempt to improve PTS based on the heuristic: delete the decaying unfit particles and regenerate new particles in the vicinity of fit surviving particles. Empirical evidence shows that RPTS outperforms PTS for a set of representative bandit problems. Finally, we apply PTS and RPTS to network slicing, a 5G communication network problem, to demonstrate the flexibility and efficacy of the algorithms.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Zhou, Zeyu

Contributors dc:contributor

• Hajek, Bruce
• Srikant, Rayadurgam
• Veeravalli, Venugopal V.
• Milenkovic, Olgica
• Mehta, Prashant

• multi-armed bandit
• stochastic bandit
• Thompson sampling
• particle Thompson sampling
• network slicing

Statement dc:rights

• Copyright 2021 Zeyu Zhou

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113061

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113061