M.Sc Thesis


M.Sc StudentGlassner Yonatan
SubjectEfficient Resource Allocation using Multi Armed Bandit
Variation
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Yacov Crammer


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.