Files in this item

FilesDescriptionFormat

application/pdf

application/pdfZHOU-DISSERTATION-2021.pdf (2MB)
(no description provided)PDF

Description

Title:Particle Thompson sampling
Author(s):Zhou, Zeyu
Director of Research:Hajek, Bruce
Doctoral Committee Chair(s):Hajek, Bruce
Doctoral Committee Member(s):Srikant, Rayadurgam; Veeravalli, Venugopal V.; Milenkovic, Olgica; Mehta, Prashant
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2021-07-16
Type:Thesis
URI:http://hdl.handle.net/2142/113061
Rights Information:Copyright 2021 Zeyu Zhou
Date Available in IDEALS:2022-01-12
Date Deposited:2021-08


This item appears in the following Collection(s)

Item Statistics