Design of optimal investment policy for influence systems and online learning for job scheduling

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 ).

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Ruan, Yufei

Contributors dc:contributor

• Etesami, Rasoul Seyed

• Dynamic games
• online learning

Statement dc:rights

• Copyright 2020 Yufei Ruan

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/108641

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/108641