针对无服务器计算中函数部署成本优化问题，提出基于多臂赌博机的在线学习算法。
Online Learning for Function Placement in Serverless Computing
- 采用多臂赌博机思想设计在线学习算法，动态优化函数部署策略。
- 理论证明算法在时间T内后悔值不超过$O(NM\sqrt{T\ln T})$，且高概率满足约束。
- 算法计算开销小，适合资源受限的大规模网络，代码开源可复现。
我们研究了旨在最小化成本的虚拟函数部署问题，提出一种基于多臂赌博机思想的新算法。理论上证明该算法能快速学习最优部署策略，其后悔值增长速率至多为$O(NM\sqrt{T\ln T})$，且在高概率下满足可行性约束，其中$T$为总时间槽数，$M$为函数类别数，$N$为计算节点数。数值实验表明，该算法兼具良好实际性能与适中计算复杂度。我们还提出一种加速技术，使算法在计算资源有限的大规模网络中仍能保持优异表现。所有实验均可复现，代码已公开。
原文摘要 · Abstract (English)
We study the placement of virtual functions aimed at minimizing the cost. We propose a novel algorithm, using ideas based on multi-armed bandits. We prove that these algorithms learn the optimal placement policy rapidly, and their regret grows at a rate at most $O( N M \sqrt{T\ln T} )$ while respecting the feasibility constraints with high probability, where $T$ is total time slots, $M$ is the number of classes of function and $N$ is the number of computation nodes. We show through numerical experiments that the proposed algorithm both has good practical performance and modest computational complexity. We propose an acceleration technique that allows the algorithm to achieve good performance also in large networks where computational power is limited. Our experiments are fully reproducible, and the code is publicly available.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。