|M.Sc Student||Yonatan Glassner|
|Subject||Efficient Resource Allocation using Multi Armed Bandit|
|Department||Department of Electrical Engineering||Supervisor||Professor Crammer Yacov|
|Full Thesis text|
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.