Abstract
We study the placement of virtual functions aimed at minimizing the cost. Wepropose a novel algorithm, using ideas based on multi-armed bandits. We provethat these algorithms learn the optimal placement policy rapidly, and theirregret grows at a rate at most $O( N M \sqrt{T\ln T} )$ while respecting thefeasibility constraints with high probability, where $T$ is total time slots,$M$ is the number of classes of function and $N$ is the number of computationnodes. We show through numerical experiments that the proposed algorithm bothhas good practical performance and modest computational complexity. We proposean acceleration technique that allows the algorithm to achieve good performancealso in large networks where computational power is limited. Our experimentsare fully reproducible, and the code is publicly available.