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

Ruan, Yufei

Permalink

https://hdl.handle.net/2142/108641 Copy

Description

Title

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

Author(s)

Ruan, Yufei

Issue Date

2020-07-24

Director of Research (if dissertation) or Advisor (if thesis)

Etesami, Rasoul Seyed

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Dynamic games
• online learning

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

Graduation Semester

2020-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2020 Yufei Ruan

Owning Collections