{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106342"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106342","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On upper confidence bound algorithms for piecewise-stationary stochastic multi-armed bandits and the variants","abstract":"In recent years, multi-armed bandit (MAB) problems have received much attention, as they model many real-world applications such as online recommendation, web search and crowdsourcing tasks. The core of MAB algorithms is addressing the exploration versus exploitation dilemma, and finding the right balance between them. Several simple yet effective algorithms (e.g., upper confidence bound (UCB) and Thompson sampling (TS)) have been proposed in the literature, which are order optimal compared with the lower bound. Original MAB problems are considered in a stationary environment, where the reward distributions do not evolve over time. Many real-world applications, however, have a non-stationary nature that cannot be fully characterized by the stationary settings. In this thesis, we mainly study the UCB-based algorithms for MAB problems and the variants under the scenario where the reward distributions can change in a piecewise-stationary manner. The variants considered in this thesis are combinatorial MAB (CMAB) and cascading bandit (CB) problems. In the first part of this thesis (Chapters 2, 3 and 4), we propose algorithms, \\texttt{GLR-UCB}, \\texttt{GLR-CUCB} and \\texttt{GLR-CascadeUCB1}, for piecewise-stationary MAB, CMAB and CB problems, respectively. The key idea behind the proposed algorithms is incorporating an almost parameter-free change-point detector, the generalized likelihood ratio (GLR) change-point detector, within the classical \\texttt{UCB1} algorithm and its variants (e.g., \\texttt{CUCB} and \\texttt{CascadeUCB1}). Gap-dependent regret upper bounds of the proposed algorithms are derived and all on the order of $\\mathcal{O}(\\sqrt{NLT\\log{T}})$, where $N$ is the number of piecewise-stationary segments, $L$ is the number of arms in MAB, base arms in CMAB, or items in CB. We also present numerical experiments on both synthetic and real-world datasets to show that our proposed algorithms outperform other state-of-the-art algorithms in the literature. Next, in the second part (Chapter 5), we also derive a nearly matching regret lower bound on the order of $\\Omega(\\sqrt{NLT})$ for MAB problems, which improves the current best lower bound $\\Omega(\\sqrt{T})$ by adding the dependence on $L$ and $N$. Since CMAB and CB are variants of MAB, this lower bound also holds for CMAB and CB.","abstract_html":"In recent years, multi-armed bandit (MAB) problems have received much attention, as they model many real-world applications such as online recommendation, web search and crowdsourcing tasks. The core of MAB algorithms is addressing the exploration versus exploitation dilemma, and finding the right balance between them. Several simple yet effective algorithms (e.g., upper confidence bound (UCB) and Thompson sampling (TS)) have been proposed in the literature, which are order optimal compared with the lower bound. Original MAB problems are considered in a stationary environment, where the reward distributions do not evolve over time. Many real-world applications, however, have a non-stationary nature that cannot be fully characterized by the stationary settings. In this thesis, we mainly study the UCB-based algorithms for MAB problems and the variants under the scenario where the reward distributions can change in a piecewise-stationary manner. The variants considered in this thesis are combinatorial MAB (CMAB) and cascading bandit (CB) problems. In the first part of this thesis (Chapters 2, 3 and 4), we propose algorithms, \\texttt{GLR-UCB}, \\texttt{GLR-CUCB} and \\texttt{GLR-CascadeUCB1}, for piecewise-stationary MAB, CMAB and CB problems, respectively. The key idea behind the proposed algorithms is incorporating an almost parameter-free change-point detector, the generalized likelihood ratio (GLR) change-point detector, within the classical \\texttt{UCB1} algorithm and its variants (e.g., \\texttt{CUCB} and \\texttt{CascadeUCB1}). Gap-dependent regret upper bounds of the proposed algorithms are derived and all on the order of $\\mathcal{O}(\\sqrt{NLT\\log{T}})$, where $N$ is the number of piecewise-stationary segments, $L$ is the number of arms in MAB, base arms in CMAB, or items in CB. We also present numerical experiments on both synthetic and real-world datasets to show that our proposed algorithms outperform other state-of-the-art algorithms in the literature. Next, in the second part (Chapter 5), we also derive a nearly matching regret lower bound on the order of $\\Omega(\\sqrt{NLT})$ for MAB problems, which improves the current best lower bound $\\Omega(\\sqrt{T})$ by adding the dependence on $L$ and $N$. Since CMAB and CB are variants of MAB, this lower bound also holds for CMAB and CB.","abstract_has_math":true,"creators":["Wang, Lingda"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Zhao, Zhizhen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T22:12:17Z","date_published":"2020-03-02T22:12:17Z","updated_at":"2026-07-22T22:24:45Z","subjects":["Multi-Armed Bandits","Non-stationary Environments","Change-Point Detection"],"languages":["en"],"rights":["Copyright 2019 Lingda Wang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106342","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Zhao, Zhizhen"]},{"key":"dc:creator","label":"Author","values":["Wang, Lingda"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T22:12:17Z","2022-03-03T10:15:08Z","2019-11-12","2019-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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 Bandits","Non-stationary Environments","Change-Point Detection"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Lingda Wang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106342"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In recent years, multi-armed bandit (MAB) problems have received much attention, as they model many real-world applications such as online recommendation, web search and crowdsourcing tasks. The core of MAB algorithms is addressing the exploration versus exploitation dilemma, and finding the right balance between them. Several simple yet effective algorithms (e.g., upper confidence bound (UCB) and Thompson sampling (TS)) have been proposed in the literature, which are order optimal compared with the lower bound. Original MAB problems are considered in a stationary environment, where the reward distributions do not evolve over time. Many real-world applications, however, have a non-stationary nature that cannot be fully characterized by the stationary settings. In this thesis, we mainly study the UCB-based algorithms for MAB problems and the variants under the scenario where the reward distributions can change in a piecewise-stationary manner. The variants considered in this thesis are combinatorial MAB (CMAB) and cascading bandit (CB) problems. In the first part of this thesis (Chapters 2, 3 and 4), we propose algorithms, \\texttt{GLR-UCB}, \\texttt{GLR-CUCB} and \\texttt{GLR-CascadeUCB1}, for piecewise-stationary MAB, CMAB and CB problems, respectively. The key idea behind the proposed algorithms is incorporating an almost parameter-free change-point detector, the generalized likelihood ratio (GLR) change-point detector, within the classical \\texttt{UCB1} algorithm and its variants (e.g., \\texttt{CUCB} and \\texttt{CascadeUCB1}). Gap-dependent regret upper bounds of the proposed algorithms are derived and all on the order of $\\mathcal{O}(\\sqrt{NLT\\log{T}})$, where $N$ is the number of piecewise-stationary segments, $L$ is the number of arms in MAB, base arms in CMAB, or items in CB. We also present numerical experiments on both synthetic and real-world datasets to show that our proposed algorithms outperform other state-of-the-art algorithms in the literature. Next, in the second part (Chapter 5), we also derive a nearly matching regret lower bound on the order of $\\Omega(\\sqrt{NLT})$ for MAB problems, which improves the current best lower bound $\\Omega(\\sqrt{T})$ by adding the dependence on $L$ and $N$. Since CMAB and CB are variants of MAB, this lower bound also holds for CMAB and CB.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2021-12-01","The student, Lingda Wang, accepted the attached license on 2019-11-12 at 10:07.","The student, Lingda Wang, submitted this Thesis for approval on 2019-11-12 at 10:09.","This Thesis was approved for publication on 2019-11-12 at 13:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14543 on 2020-02-28 at 17:22:04","Made available in DSpace on 2020-03-02T22:12:17Z (GMT). No. of bitstreams: 2 WANG-THESIS-2019.pdf: 1031544 bytes, checksum: b82c6cfa2dd2819ffabba3fde87ee4e7 (MD5) LICENSE.txt: 4208 bytes, checksum: f18d275b9bc777e4ede0bb5e78110e0f (MD5) Previous issue date: 2019-11-12","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:12:26Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:15:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:18:25Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 113883 on 2022-03-03T10:15:08Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On upper confidence bound algorithms for piecewise-stationary stochastic multi-armed bandits and the variants"]}]}],"canonical_facts":{"dc:contributor":["Zhao, Zhizhen"],"dc:creator":["Wang, Lingda"],"dc:date":["2020-03-02T22:12:17Z","2022-03-03T10:15:08Z","2019-11-12","2019-12"],"dc:description":["In recent years, multi-armed bandit (MAB) problems have received much attention, as they model many real-world applications such as online recommendation, web search and crowdsourcing tasks. The core of MAB algorithms is addressing the exploration versus exploitation dilemma, and finding the right balance between them. Several simple yet effective algorithms (e.g., upper confidence bound (UCB) and Thompson sampling (TS)) have been proposed in the literature, which are order optimal compared with the lower bound. Original MAB problems are considered in a stationary environment, where the reward distributions do not evolve over time. Many real-world applications, however, have a non-stationary nature that cannot be fully characterized by the stationary settings. In this thesis, we mainly study the UCB-based algorithms for MAB problems and the variants under the scenario where the reward distributions can change in a piecewise-stationary manner. The variants considered in this thesis are combinatorial MAB (CMAB) and cascading bandit (CB) problems. In the first part of this thesis (Chapters 2, 3 and 4), we propose algorithms, \\texttt{GLR-UCB}, \\texttt{GLR-CUCB} and \\texttt{GLR-CascadeUCB1}, for piecewise-stationary MAB, CMAB and CB problems, respectively. The key idea behind the proposed algorithms is incorporating an almost parameter-free change-point detector, the generalized likelihood ratio (GLR) change-point detector, within the classical \\texttt{UCB1} algorithm and its variants (e.g., \\texttt{CUCB} and \\texttt{CascadeUCB1}). Gap-dependent regret upper bounds of the proposed algorithms are derived and all on the order of $\\mathcal{O}(\\sqrt{NLT\\log{T}})$, where $N$ is the number of piecewise-stationary segments, $L$ is the number of arms in MAB, base arms in CMAB, or items in CB. We also present numerical experiments on both synthetic and real-world datasets to show that our proposed algorithms outperform other state-of-the-art algorithms in the literature. Next, in the second part (Chapter 5), we also derive a nearly matching regret lower bound on the order of $\\Omega(\\sqrt{NLT})$ for MAB problems, which improves the current best lower bound $\\Omega(\\sqrt{T})$ by adding the dependence on $L$ and $N$. Since CMAB and CB are variants of MAB, this lower bound also holds for CMAB and CB.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2021-12-01","The student, Lingda Wang, accepted the attached license on 2019-11-12 at 10:07.","The student, Lingda Wang, submitted this Thesis for approval on 2019-11-12 at 10:09.","This Thesis was approved for publication on 2019-11-12 at 13:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14543 on 2020-02-28 at 17:22:04","Made available in DSpace on 2020-03-02T22:12:17Z (GMT). No. of bitstreams: 2 WANG-THESIS-2019.pdf: 1031544 bytes, checksum: b82c6cfa2dd2819ffabba3fde87ee4e7 (MD5) LICENSE.txt: 4208 bytes, checksum: f18d275b9bc777e4ede0bb5e78110e0f (MD5) Previous issue date: 2019-11-12","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:12:26Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:15:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 113883 Lift date: 2022-03-02T22:18:25Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 113883 on 2022-03-03T10:15:08Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106342"],"dc:language":["en"],"dc:rights":["Copyright 2019 Lingda Wang"],"dc:subject":["Multi-Armed Bandits","Non-stationary Environments","Change-Point Detection"],"dc:title":["On upper confidence bound algorithms for piecewise-stationary stochastic multi-armed bandits and the variants"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:45Z"}