M.Sc Thesis

M.Sc StudentGolan Michal
SubjectBurstiness-Constrained Markov Decision Processes
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


Burstiness of a dynamic process is the behavior of anomalous changes in the process's volume or frequency of occurrence. Bursty processes are encountered, for example, in communication networks, storage systems, and cloud-computing systems.

We consider the problem of Burstiness-Constrained MDPs (BCPs): MDPs with a sample-path constraint on the burstiness of an associated cost.

Due to the burstiness constraint's form, feasible BCP policies are generally history-dependent. Thus, determining the problem's feasibility is prohibitive in its current form. Additionally, we cannot solve it with standard MDP algorithms such as backwards induction, value iteration, policy iteration and linear programming formulation.

We propose algorithms to determine the feasibility of BCPs, and to find their optimal feasible policies, in both finite and infinite time horizon settings. This is done by reformulating the burstiness constraint and posing it as a state constraint. We then characterize the conditions for feasibility of every state, action and policy, and develop procedures to determine whether these conditions are met. Next, we augment the BCP's state variable with an additional term which encompasses the past information regarding satisfaction of the burstiness constraint. The feasible policies are then Markov in the augmented state-space. Restricting the reformulated BCP to only feasible states and actions yields an unconstrained MDP with an augmented state-space, which can be treated with the aforementioned tools.