Particle Thompson sampling

Zhou, Zeyu

Permalink

https://hdl.handle.net/2142/113061 Copy

Description

Title

Particle Thompson sampling

Author(s)

Zhou, Zeyu

Issue Date

2021-07-16

Director of Research (if dissertation) or Advisor (if thesis)

Hajek, Bruce

Doctoral Committee Chair(s)

Hajek, Bruce

Committee Member(s)

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

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2021 Zeyu Zhou

Owning Collections