{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113061"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113061","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Particle Thompson sampling","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zhou, Zeyu"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hajek, Bruce","Srikant, Rayadurgam","Veeravalli, Venugopal V.","Milenkovic, Olgica","Mehta, Prashant"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:46:52Z","date_published":"2022-01-12T21:46:52Z","updated_at":"2026-07-22T22:24:53Z","subjects":["multi-armed bandit","stochastic bandit","Thompson sampling","particle Thompson sampling","network slicing"],"languages":["en"],"rights":["Copyright 2021 Zeyu Zhou"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113061","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce","Srikant, Rayadurgam","Veeravalli, Venugopal V.","Milenkovic, Olgica","Mehta, Prashant"]},{"key":"dc:creator","label":"Author","values":["Zhou, Zeyu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:46:52Z","2021-07-16","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["multi-armed bandit","stochastic bandit","Thompson sampling","particle Thompson sampling","network slicing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Zeyu Zhou"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113061"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Zeyu Zhou, accepted the attached license on 2021-07-15 at 23:28.","The student, Zeyu Zhou, submitted this Dissertation for approval on 2021-07-15 at 23:56.","This Dissertation was approved for publication on 2021-07-16 at 12:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16978 on 2022-01-12 at 12:46:04","Made available in DSpace on 2022-01-12T21:46:52Z (GMT). No. of bitstreams: 18 ZHOU-DISSERTATION-2021.pdf: 2156973 bytes, checksum: d9a69e4c70612304cb896215b41f3eca (MD5) IEEE_ECE.bst: 61899 bytes, checksum: 7509566d10f8075f0fad3df817415508 (MD5) ZZcommands.tex: 6440 bytes, checksum: 7236dbe023b081e19a173fb9626e427d (MD5) Zeyu_Zhou_PhD_Dissertation.tex: 6298 bytes, checksum: 70b8c4a9652a058270cc84f2a439493d (MD5) abs.tex: 1270 bytes, checksum: d16d68d544e5bd2e2332bf5db1abf2ae (MD5) ack.tex: 1217 bytes, checksum: d58f2d0fcdc302457f7e12d633637102 (MD5) appendix.tex: 13615 bytes, checksum: f498ed9024f12adfdb8cfa42c44463d6 (MD5) ch1_introduction.tex: 5869 bytes, checksum: c598deafd0f9eec49d8eca6fe23aa2b7 (MD5) ch2_related_work.tex: 7523 bytes, checksum: 5862dfa57200e69a1910fc99de4a7922 (MD5) ch3_setup_and_preliminaries.tex: 19241 bytes, checksum: 010fd2156c9f8ae699c228f5d035637e (MD5) ch4_PTS_for_2_arm_Bernoulli_bandit.tex: 93100 bytes, checksum: f667c749369d6c42ccce13b0bbd6d995 (MD5) ch5_PTS_for_general_stochastic_bandit.tex: 37510 bytes, checksum: 142b151b2cfbd318c96e8f409666ba99 (MD5) ch6_RPTS.tex: 14815 bytes, checksum: 3ae1ad2a73ecd6334155c9ad4c7ac506 (MD5) ch7_application.tex: 32772 bytes, checksum: 18bce05b6f53b0b5f759abb233af6566 (MD5) ch8_conclusions.tex: 1833 bytes, checksum: f2f730bca62d91b3a1a7b2850ff7aa58 (MD5) refs.bib: 18768 bytes, checksum: 15b6b3cbd028897a34d41de22784c496 (MD5) uiucecethesis09.cls: 22156 bytes, checksum: 0a97d8a620d90ceff5aaa113159c42b8 (MD5) LICENSE.txt: 4206 bytes, checksum: 81d959e972878fdd82e82ecbeb6f7afc (MD5) Previous issue date: 2021-07-16"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Particle Thompson sampling"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce","Srikant, Rayadurgam","Veeravalli, Venugopal V.","Milenkovic, Olgica","Mehta, Prashant"],"dc:creator":["Zhou, Zeyu"],"dc:date":["2022-01-12T21:46:52Z","2021-07-16","2021-08"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Zeyu Zhou, accepted the attached license on 2021-07-15 at 23:28.","The student, Zeyu Zhou, submitted this Dissertation for approval on 2021-07-15 at 23:56.","This Dissertation was approved for publication on 2021-07-16 at 12:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16978 on 2022-01-12 at 12:46:04","Made available in DSpace on 2022-01-12T21:46:52Z (GMT). No. of bitstreams: 18 ZHOU-DISSERTATION-2021.pdf: 2156973 bytes, checksum: d9a69e4c70612304cb896215b41f3eca (MD5) IEEE_ECE.bst: 61899 bytes, checksum: 7509566d10f8075f0fad3df817415508 (MD5) ZZcommands.tex: 6440 bytes, checksum: 7236dbe023b081e19a173fb9626e427d (MD5) Zeyu_Zhou_PhD_Dissertation.tex: 6298 bytes, checksum: 70b8c4a9652a058270cc84f2a439493d (MD5) abs.tex: 1270 bytes, checksum: d16d68d544e5bd2e2332bf5db1abf2ae (MD5) ack.tex: 1217 bytes, checksum: d58f2d0fcdc302457f7e12d633637102 (MD5) appendix.tex: 13615 bytes, checksum: f498ed9024f12adfdb8cfa42c44463d6 (MD5) ch1_introduction.tex: 5869 bytes, checksum: c598deafd0f9eec49d8eca6fe23aa2b7 (MD5) ch2_related_work.tex: 7523 bytes, checksum: 5862dfa57200e69a1910fc99de4a7922 (MD5) ch3_setup_and_preliminaries.tex: 19241 bytes, checksum: 010fd2156c9f8ae699c228f5d035637e (MD5) ch4_PTS_for_2_arm_Bernoulli_bandit.tex: 93100 bytes, checksum: f667c749369d6c42ccce13b0bbd6d995 (MD5) ch5_PTS_for_general_stochastic_bandit.tex: 37510 bytes, checksum: 142b151b2cfbd318c96e8f409666ba99 (MD5) ch6_RPTS.tex: 14815 bytes, checksum: 3ae1ad2a73ecd6334155c9ad4c7ac506 (MD5) ch7_application.tex: 32772 bytes, checksum: 18bce05b6f53b0b5f759abb233af6566 (MD5) ch8_conclusions.tex: 1833 bytes, checksum: f2f730bca62d91b3a1a7b2850ff7aa58 (MD5) refs.bib: 18768 bytes, checksum: 15b6b3cbd028897a34d41de22784c496 (MD5) uiucecethesis09.cls: 22156 bytes, checksum: 0a97d8a620d90ceff5aaa113159c42b8 (MD5) LICENSE.txt: 4206 bytes, checksum: 81d959e972878fdd82e82ecbeb6f7afc (MD5) Previous issue date: 2021-07-16"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113061"],"dc:language":["en"],"dc:rights":["Copyright 2021 Zeyu Zhou"],"dc:subject":["multi-armed bandit","stochastic bandit","Thompson sampling","particle Thompson sampling","network slicing"],"dc:title":["Particle Thompson sampling"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}