Learning Proportionally Fair Allocations with Low Regret

This paper addresses a generic sequential resource allocation problem, where in each round a decision maker selects an allocation of resources (servers) to a set of tasks consisting of a large number of jobs. A job of task i assigned to server j is successfully treated with probability θ_ij in a round, and the decision maker is informed on whether this job is completed at the end of the round. The probabilities θᵢj's are initially unknown and have to be learned. The objective of the decision maker is to sequentially assign jobs of various tasks to servers so that it rapidly learns and converges to the Proportionally Fair (PF) allocation (or other similar allocations achieving an appropriate trade-off between efficiency and fairness). We formulate the problem as a multi-armed bandit (MAB) optimization problem, and devise sequential assignment algorithms with low regret (defined as the difference in utility achieved by an oracle algorithm aware of the θ_ij $'s and by the proposed algorithm over a given number of slots). We first provide the properties of the so-called Restricted-PF (RPF) allocation, obtained by assuming that each task can only use a single server, and in particular show that it is very close to the PF allocation. We devise ES-RPF, an algorithm that learns the RPF allocation with regret no greater than O (m³øver θₘin Δₘin łog(T)) after T slots, where m , θ_min , and Δₘin represent the number of tasks, the minimum success rate minᵢ,j θᵢj, and an appropriately defined notion of gap, respectively. We further provide regret lower bounds satisfied by any algorithm targeting the RPF allocation. Finally, we present ES-PF, an algorithm directly learning the PF allocation, and prove that its regret does not exceed O (²s θₘin łog(T)) after T slots, where s denotes the number of servers.