{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/18352"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/18352","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parametrized Stochastic Multi-armed Bandits with Binary Rewards","abstract":"In this thesis, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across arms and across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any $f \\in \\omega(\\log(T))$, the total regret can be made to be $O(f(T))$, independent of the number of arms.","abstract_html":"In this thesis, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across arms and across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any <span class=\"etd-inline-math\">f \\in &omega;(\\log(T))</span>, the total regret can be made to be $O(f(T))$, independent of the number of arms.","abstract_has_math":true,"creators":["Jiang, Chong"],"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":["Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-01-14T22:47:13Z","date_published":"2011-01-14T22:47:13Z","updated_at":"2026-07-22T22:25:11Z","subjects":["machine learning","multi-armed bandits"],"languages":["en"],"rights":["Copyright 2010 Chong Jiang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/18352","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Jiang, Chong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-01-14T22:47:13Z","2010-12"]},{"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":["machine learning","multi-armed bandits"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Chong Jiang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/18352"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across arms and across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any $f \\in \\omega(\\log(T))$, the total regret can be made to be $O(f(T))$, independent of the number of arms.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-12-09T18:39:12Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jiang_Chong.pdf: 325450 bytes, checksum: 9f6372630df4d279f19fca565c89d472 (MD5)","Made available in DSpace on 2011-01-14T22:47:13Z (GMT). No. of bitstreams: 2 Jiang_Chong.pdf: 325450 bytes, checksum: 9f6372630df4d279f19fca565c89d472 (MD5) license.txt: 4060 bytes, checksum: 9148706d902e93953c049052831ab198 (MD5)"]},{"key":"dc:title","label":"Title","values":["Parametrized Stochastic Multi-armed Bandits with Binary Rewards"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam"],"dc:creator":["Jiang, Chong"],"dc:date":["2011-01-14T22:47:13Z","2010-12"],"dc:description":["In this thesis, we consider the problem of multi-armed bandits with a large number of correlated arms. We assume that the arms have Bernoulli distributed rewards, independent across arms and across time, where the probabilities of success are parametrized by known attribute vectors for each arm, as well as an unknown preference vector. For this model, we seek an algorithm with a total regret that is sub-linear in time and independent of the number of arms. We present such an algorithm, which we call the Three-phase Algorithm, and analyze its performance. We show an upper bound on the total regret which applies uniformly in time. The asymptotics of this bound show that for any $f \\in \\omega(\\log(T))$, the total regret can be made to be $O(f(T))$, independent of the number of arms.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-12-09T18:39:12Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jiang_Chong.pdf: 325450 bytes, checksum: 9f6372630df4d279f19fca565c89d472 (MD5)","Made available in DSpace on 2011-01-14T22:47:13Z (GMT). No. of bitstreams: 2 Jiang_Chong.pdf: 325450 bytes, checksum: 9f6372630df4d279f19fca565c89d472 (MD5) license.txt: 4060 bytes, checksum: 9148706d902e93953c049052831ab198 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/18352"],"dc:language":["en"],"dc:rights":["Copyright 2010 Chong Jiang"],"dc:subject":["machine learning","multi-armed bandits"],"dc:title":["Parametrized Stochastic Multi-armed Bandits with Binary Rewards"],"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:25:11Z"}