从加权α-公平分配的角度重新审视在线学习元算法

《IEEE Transactions on Networking》：Revisiting Online Learning Meta-Algorithm From the Perspective of Weighted Alpha-Fair Allocation

MWU算法与加权alpha公平性结合，提出动态资源分配框架，在流量调度和文件缓存中验证其优于现有策略的公平性和效率。

　　

摘要：

乘性权重更新（Multiplicative Weight Update，简称MWU）是一种在线学习元算法，已被广泛应用于序列决策问题中。MWU的核心思想是维护一个分布，作为对不同行动的选择概率分配。MWU在许多研究中被独立重新发现和探讨。本文将从公平资源分配的角度重新审视MWU。具体来说，我们关注一个称为“加权阿尔法公平性”（weighted alpha-fairness）的著名公平性概念，该概念最初由Mo和Walrand在网络带宽分配问题中提出。我们首先揭示MWU在每个时间槽内本质上采用了加权阿尔法公平的概率分配机制。公平性水平等于MWU中步长参数的倒数，且分配给每个行动的权重会随着其累积成本的增加而呈指数级衰减。这一发现表明，使用适当的加权阿尔法公平分配来决定行动概率，在长期内确实可以与离线最优分配取得相同的效果。受此启发，我们进一步研究了是否可以通过为每个时间槽精心设计加权阿尔法公平分配来解决更一般的在线资源分配问题（而不局限于MWU所处理的问题）。为此，我们提出了一个加权阿尔法公平在线分配框架，该框架能够精心构建基于价值的权重和逐渐提升的公平性水平。在我们提出的框架下，每个时间槽的分配结果都满足加权阿尔法公平性原则，并且分配效果在长期内也能与离线最优结果相当。我们通过两个网络应用展示了该框架的实际运行情况：在基于流量的调度中，该框架使网络交换机能够在无需预先了解流量大小的情况下优先处理短流量并避免流量饥饿现象；在文件缓存方面，该框架的性能比几种现有的缓存策略高出多达21%...

显示更多