{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/99200"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/99200","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Low-complexity, low-regret link rate selection in rapidly varying wireless channels","abstract":"We consider the problem of transmitting at the optimal rate over a rapidly varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mmWave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.","abstract_html":"We consider the problem of transmitting at the optimal rate over a rapidly varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mmWave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.","abstract_has_math":false,"creators":["Gupta, Harsh"],"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":2018,"date_issued":"2018-03-13T15:21:07Z","date_published":"2018-03-13T15:21:07Z","updated_at":"2026-07-22T22:24:37Z","subjects":["Link rate selection","Thompson sampling","Regret minimization","Computational complexity"],"languages":["en"],"rights":["Copyright 2017 Harsh Gupta"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/99200","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":["Gupta, Harsh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-03-13T15:21:07Z","2020-03-14T09:15:08Z","2017-11-10","2017-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":["Link rate selection","Thompson sampling","Regret minimization","Computational complexity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Harsh Gupta"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/99200"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider the problem of transmitting at the optimal rate over a rapidly varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mmWave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-12-01","The student, Harsh Gupta, accepted the attached license on 2017-11-10 at 13:35.","The student, Harsh Gupta, submitted this Thesis for approval on 2017-11-10 at 13:38.","This Thesis was approved for publication on 2017-11-10 at 14:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11731 on 2018-03-13 at 09:55:44","Made available in DSpace on 2018-03-13T15:21:07Z (GMT). No. of bitstreams: 2 GUPTA-THESIS-2017.pdf: 537746 bytes, checksum: 4ccb993d6ef1edf24b636d8b87de5e85 (MD5) LICENSE.txt: 4208 bytes, checksum: 8f78f5b5a8a6494d8be414226238774c (MD5) Previous issue date: 2017-11-10","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:21:19Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:25:40Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:28:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105162 on 2020-03-14T09:15:08Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Low-complexity, low-regret link rate selection in rapidly varying wireless channels"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam"],"dc:creator":["Gupta, Harsh"],"dc:date":["2018-03-13T15:21:07Z","2020-03-14T09:15:08Z","2017-11-10","2017-12"],"dc:description":["We consider the problem of transmitting at the optimal rate over a rapidly varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mmWave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-12-01","The student, Harsh Gupta, accepted the attached license on 2017-11-10 at 13:35.","The student, Harsh Gupta, submitted this Thesis for approval on 2017-11-10 at 13:38.","This Thesis was approved for publication on 2017-11-10 at 14:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11731 on 2018-03-13 at 09:55:44","Made available in DSpace on 2018-03-13T15:21:07Z (GMT). No. of bitstreams: 2 GUPTA-THESIS-2017.pdf: 537746 bytes, checksum: 4ccb993d6ef1edf24b636d8b87de5e85 (MD5) LICENSE.txt: 4208 bytes, checksum: 8f78f5b5a8a6494d8be414226238774c (MD5) Previous issue date: 2017-11-10","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:21:19Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:25:40Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105162 Lift date: 2020-03-13T15:28:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105162 on 2020-03-14T09:15:08Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/99200"],"dc:language":["en"],"dc:rights":["Copyright 2017 Harsh Gupta"],"dc:subject":["Link rate selection","Thompson sampling","Regret minimization","Computational complexity"],"dc:title":["Low-complexity, low-regret link rate selection in rapidly varying wireless channels"],"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:37Z"}