טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYonatan Glassner
SubjectEfficient Resource Allocation using Multi Armed Bandit
Variation
DepartmentDepartment of Electrical Engineering
Supervisor Professor Crammer Yacov
Full Thesis textFull thesis text - English Version


Abstract

In this thesis, we examine an online resource allocation problem, where a resource manager simultaneously allocates resources, learns the impact on the different consumers and improves the allocation towards optimal performance. This resource allocation problem involves the inherent exploration-exploitation trade-off, where the allocator should strike a balance between the consumers' identifi0cation (exploration) and an optimal allocation approach (exploitation).

We build on the rich framework of multi-armed bandits (MAB) and present online and offline algorithms. The algorithms are built on a behavior model of the consumers' gain as a function of their given resources. We analyze these algorithms in the worst case regret-bound models.

We perform extensive experiments with both synthetic data and real-world cache allocation to threads. In this cache allocation task, we consider a dividable cache, which can be separately divided among the different cores. We show that such a cache architecture is better than a uniformly divided cache, and present an algorithm to learn the optimal division from the running threads. The different experiments show the merits and properties of our algorithms.