{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108641"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108641","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Design of optimal investment policy for influence systems and online learning for job scheduling","abstract":"This thesis contains two main research thrusts, one related to the design of optimal investment policies for influence systems and the other related to online learning for job scheduling on heterogeneous machines. In Chapter 2, a continuous-time influence system on social networks is considered, where the goal is to decide on how to allocate a limited amount of budget over a finite time horizon in order to control the opinion of social entities towards a specific objective. Describing the model under continuous-time settings, it is shown that even under the simplistic case of one marketer and one social entity, the optimal strategy may not exist without any assumption on the number of investment switches. Several sufficient conditions are then developed, which guarantee the existence of an optimal policy. Subsequently, the structure of the optimal policy under some special cases are characterized. In Chapter 3, a new model for online job scheduling on heterogeneous machines is developed. In that model, the goal is to schedule a sequence of arriving jobs on a set of heterogeneous machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. However, in practice, each machine may have an unknown different power/energy budget, and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to minimize the regret, that is, the expected difference between the total quality of service (i.e., the sum of all the machines’ welfare) obtained by the algorithm and its maximum value had we known the power budgets a priori. First, it is shown that a simple Explore-then-Exploit scheduling algorithm achieves a sub-linear regret of O(T^{2/3}), where T is the total number of jobs. This result is then enhanced by providing an Upper Confidence Bound (UCB) algorithm achieving a logarithmic regret O(log T ).","abstract_html":"This thesis contains two main research thrusts, one related to the design of optimal investment policies for influence systems and the other related to online learning for job scheduling on heterogeneous machines. In Chapter 2, a continuous-time influence system on social networks is considered, where the goal is to decide on how to allocate a limited amount of budget over a finite time horizon in order to control the opinion of social entities towards a specific objective. Describing the model under continuous-time settings, it is shown that even under the simplistic case of one marketer and one social entity, the optimal strategy may not exist without any assumption on the number of investment switches. Several sufficient conditions are then developed, which guarantee the existence of an optimal policy. Subsequently, the structure of the optimal policy under some special cases are characterized. In Chapter 3, a new model for online job scheduling on heterogeneous machines is developed. In that model, the goal is to schedule a sequence of arriving jobs on a set of heterogeneous machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. However, in practice, each machine may have an unknown different power/energy budget, and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to minimize the regret, that is, the expected difference between the total quality of service (i.e., the sum of all the machines’ welfare) obtained by the algorithm and its maximum value had we known the power budgets a priori. First, it is shown that a simple Explore-then-Exploit scheduling algorithm achieves a sub-linear regret of O(T^{2/3}), where T is the total number of jobs. This result is then enhanced by providing an Upper Confidence Bound (UCB) algorithm achieving a logarithmic regret O(log T ).","abstract_has_math":false,"creators":["Ruan, Yufei"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Etesami, Rasoul Seyed"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-10-07T22:44:48Z","date_published":"2020-10-07T22:44:48Z","updated_at":"2026-07-22T22:24:48Z","subjects":["Dynamic games","online learning"],"languages":["en"],"rights":["Copyright 2020 Yufei Ruan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108641","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Etesami, Rasoul Seyed"]},{"key":"dc:creator","label":"Author","values":["Ruan, Yufei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T22:44:48Z","2022-10-07T22:44:53Z","2020-07-24","2020-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"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":["Dynamic games","online learning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Yufei Ruan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108641"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis contains two main research thrusts, one related to the design of optimal investment policies for influence systems and the other related to online learning for job scheduling on heterogeneous machines. In Chapter 2, a continuous-time influence system on social networks is considered, where the goal is to decide on how to allocate a limited amount of budget over a finite time horizon in order to control the opinion of social entities towards a specific objective. Describing the model under continuous-time settings, it is shown that even under the simplistic case of one marketer and one social entity, the optimal strategy may not exist without any assumption on the number of investment switches. Several sufficient conditions are then developed, which guarantee the existence of an optimal policy. Subsequently, the structure of the optimal policy under some special cases are characterized. In Chapter 3, a new model for online job scheduling on heterogeneous machines is developed. In that model, the goal is to schedule a sequence of arriving jobs on a set of heterogeneous machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. However, in practice, each machine may have an unknown different power/energy budget, and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to minimize the regret, that is, the expected difference between the total quality of service (i.e., the sum of all the machines’ welfare) obtained by the algorithm and its maximum value had we known the power budgets a priori. First, it is shown that a simple Explore-then-Exploit scheduling algorithm achieves a sub-linear regret of O(T^{2/3}), where T is the total number of jobs. This result is then enhanced by providing an Upper Confidence Bound (UCB) algorithm achieving a logarithmic regret O(log T ).","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-08-01","The student, Yufei Ruan, accepted the attached license on 2020-07-23 at 18:52.","The student, Yufei Ruan, submitted this Thesis for approval on 2020-07-23 at 19:12.","This Thesis was approved for publication on 2020-07-24 at 14:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15741 on 2020-10-02 at 15:34:10","Made available in DSpace on 2020-10-07T22:44:48Z (GMT). No. of bitstreams: 3 RUAN-THESIS-2020.pdf: 522109 bytes, checksum: ce871cfc5c7476298d5c63b9ff5cef88 (MD5) Yufei master thesis.zip: 3539520 bytes, checksum: e55ce38d00b60b6b6df355071f7029c6 (MD5) LICENSE.txt: 4207 bytes, checksum: a30d881b5a08b0b8bb35bf129d458821 (MD5) Previous issue date: 2020-07-24","Embargo set by: Seth Robbins for item 116268 Lift date: 2022-10-07T22:44:53Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Design of optimal investment policy for influence systems and online learning for job scheduling"]}]}],"canonical_facts":{"dc:contributor":["Etesami, Rasoul Seyed"],"dc:creator":["Ruan, Yufei"],"dc:date":["2020-10-07T22:44:48Z","2022-10-07T22:44:53Z","2020-07-24","2020-08"],"dc:description":["This thesis contains two main research thrusts, one related to the design of optimal investment policies for influence systems and the other related to online learning for job scheduling on heterogeneous machines. In Chapter 2, a continuous-time influence system on social networks is considered, where the goal is to decide on how to allocate a limited amount of budget over a finite time horizon in order to control the opinion of social entities towards a specific objective. Describing the model under continuous-time settings, it is shown that even under the simplistic case of one marketer and one social entity, the optimal strategy may not exist without any assumption on the number of investment switches. Several sufficient conditions are then developed, which guarantee the existence of an optimal policy. Subsequently, the structure of the optimal policy under some special cases are characterized. In Chapter 3, a new model for online job scheduling on heterogeneous machines is developed. In that model, the goal is to schedule a sequence of arriving jobs on a set of heterogeneous machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. However, in practice, each machine may have an unknown different power/energy budget, and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to minimize the regret, that is, the expected difference between the total quality of service (i.e., the sum of all the machines’ welfare) obtained by the algorithm and its maximum value had we known the power budgets a priori. First, it is shown that a simple Explore-then-Exploit scheduling algorithm achieves a sub-linear regret of O(T^{2/3}), where T is the total number of jobs. This result is then enhanced by providing an Upper Confidence Bound (UCB) algorithm achieving a logarithmic regret O(log T ).","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-08-01","The student, Yufei Ruan, accepted the attached license on 2020-07-23 at 18:52.","The student, Yufei Ruan, submitted this Thesis for approval on 2020-07-23 at 19:12.","This Thesis was approved for publication on 2020-07-24 at 14:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15741 on 2020-10-02 at 15:34:10","Made available in DSpace on 2020-10-07T22:44:48Z (GMT). No. of bitstreams: 3 RUAN-THESIS-2020.pdf: 522109 bytes, checksum: ce871cfc5c7476298d5c63b9ff5cef88 (MD5) Yufei master thesis.zip: 3539520 bytes, checksum: e55ce38d00b60b6b6df355071f7029c6 (MD5) LICENSE.txt: 4207 bytes, checksum: a30d881b5a08b0b8bb35bf129d458821 (MD5) Previous issue date: 2020-07-24","Embargo set by: Seth Robbins for item 116268 Lift date: 2022-10-07T22:44:53Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108641"],"dc:language":["en"],"dc:rights":["Copyright 2020 Yufei Ruan"],"dc:subject":["Dynamic games","online learning"],"dc:title":["Design of optimal investment policy for influence systems and online learning for job scheduling"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:48Z"}