在网络优化问题中，公平性(fairness)是一个重要的考虑指标。随着越来越多的设备接入网络中，网络中的资源分配、任务调度等需要充分考虑设备之间的公平性，在系统效率与用户公平性之间达到一种平衡。近年来，强化学习被成功应用于网络优化问题的在线决策中，然而大部分算法聚焦于最大化所有agent的长期收益，很少考虑公平性。在这样的背景下，作者提出了一种fairness Actor-Critic algorithm，该算法将公平性融入到AC算法的设计中，旨在优化整体公平效用函数。具体做法为，设计了一种适应性奖励，在原奖励的基础上乘以一个权重，该权重与效用函数和过去的奖励有关。实验部分，作者将算法用于求解网络调度问题（convex)与视频流QoE优化问题(non-convex)，说明了算法的有效性。

Problem Formulation

考虑一个网络效用优化问题，网络建模为环境，用户是agents，agent与环境进行交互，学习策略来优化rewards（如数据率等）。假设有K个agents，使用随机策略(stochastic policy) $\pi$(a|s)表示状态s下选择动作a的概率。$x_{\pi ,k}$代表agent k在策略$\pi$下的平均奖励

在本文中，使用$\alpha$-fiar 效用函数，该函数广泛应用于网络优化领域。对于任意的$\alpha$ >= 0，有

Learning Algorithm

假定在任何策略下的马尔科夫链都是不可还原/非周期性的。

Learning with Multiplicative-Adjusted Rewards

为了优化公平效用，在算法中需要追踪历史reward。为什么能使用过去历史reward来实现公平呢？
假设这样一个场景，两个agent分别有自己的reward，在某个策略下，如果截至到epoch t时agent 1比agent 2获得了更多的累积奖励，那么我们需要偏好使用策略梯度更新agent 2而不是agent 1。因此过去历史reward能够用于优化公平性。
使用$h_{\pi ,t}$表示截止epoch t从采样路径中获得的数据，使用一个一致连续函数( uniformly-continuous function) $\varphi (h_{\pi ,t})$计算奖励的乘子。一致连续函数本身是“公平性”的体现。定义适应性奖励(adjust rewards)为

使用$\widehat{{\rho }_{\pi }}$表示MDP下平均单步适应性奖励，定义状态价值函数和动作价值函数如下：

可以看到，V和Q都是有边界的。定义一个增强函数

因为适应性奖励依赖于过去的历史h，所以标准RL的策略梯度理论不再适用适应性奖励。重新分析MDP。

当策略参数发生微小改变，平均奖励的改变如上式。
证明：定义新的状态$z_t=[s_t,h_{\pi ,t}]$，新的马尔可夫过程为状态$z_t$、动作$a_t$和奖励$\widehat{r_{k,t}}$的链。使用$p_{z{z}^{\prime }}^a$表示状态转移概率，$V_{\pi }(z)$和$Q_{\pi }(z,a)$为状态-值函数、动作-值函数。用$P^{\pi }(z|s)$表示对于给定的状态s发生z的有限概率。Q函数与V函数表示如下

定义一个辅助函数

其中$A_{\pi }(z,a)=Q_{\pi }(z,a)-V_{\pi }(z,a)$。则有

因为${\sum }_a\pi (a|s)Q_{\pi }(z,a)=V_{\pi }(z)$, 所以根据推导，有$G_{\theta +ϵ,\theta +ϵ,\theta +ϵ}$ = 0 。上述推导的最后一步中，第一项和第三项能够消掉，最后得到

当策略参数发生的改变$\varphi$十分微小，策略${\pi }_{\theta }$的相应改变可以用$ϵ\nabla {\pi }_{\theta }(a|s)+O(||ϵ|{|}_2^2)$来bound。那么有


以上的梯度和较小的学习率能够使得算法收敛到一个平稳点。
策略梯度算法如下：（类似于REINFORCE算法）

Solving Fairness Utility Optimization

Lemma 2说明了新的策略梯度算法能收敛到适应性MDP的平稳点。定义最优策略的参数为${\theta }^{\ast }$，那么初始奖励的单步平均值为

我们需要证明${\theta }^{\ast }$也是优化问题${\sum }_{k}U(x_{{\pi }_{\theta },k})$的平稳点。
对于一致连续函数$\varphi$，设定为效用函数U的一阶导数。该函数是符合Lipschitz连续的，有$|U^{\prime }(x)-U^{\prime }(y)|<=L|x-y|$, 对于L > 0。那么适应性奖励可以表示为


理论1：策略梯度算法能够收敛至公平效用函数的平稳点。
证明：由上已知，${\theta }^{\ast }$是适应性MDP的平稳点，即${\nabla }_{\theta }\widehat{{\rho }_{{\pi }_{\theta }}}{|}_{\theta ={\theta }^{\ast }}=0$，需要证明${\theta }^{\ast }$也是$\alpha$-fair 效用函数${\sum }_{k}U(x_{{\pi }_{\theta },k})$的平稳点，也即${\nabla }_{\theta }[{\sum }_{k}U(x_{{\pi }_{\theta },k})]{|}_{\theta ={\theta }^{\ast }}=0$。
所以我们需要分析单步平均适应性奖励$\widehat{{\rho }_{{\pi }_{\theta }}}$和单步平均奖励$x_{{\pi }_{\theta },k}$的关系

根据公式(17)，有

在policy ${\pi }_{\theta }$下，对于任意的$ϵ$ > 0 存在一个足够大的T使得，$|1/T{\sum }_{t=1}^T{r}_{k,t}-x_{{\pi }_{\theta },k}|<ϵ$，结合U’的Lipschitz continuity有

其中C1是$|U^{\prime }(x_{{\pi }_{\theta },k})|$的边界，C2是$|1/T{\sum }_{t=1}^T{r}_{k,t}|$的边界。当T足够大，有
$\widehat{{\rho }_{{\pi }_{\theta }}}={\sum }_k{x}_{{\pi }_{\theta },k}{U}^{\prime }(x_{{\pi }_{\theta },k})$
由于${\theta }^{\ast }$是适应性MDP的平衡点，有 ${\nabla }_{\theta }[x_{{\pi }_{\theta },k}{U}^{\prime }(x_{{\pi }_{\theta },k})]{|}_{\theta ={\theta }^{\ast }}=0$，也即${\nabla }_{\theta }\widehat{{\rho }_{{\pi }_{\theta }}}{|}_{\theta ={\theta }^{\ast }}=0$。

上述证明结果可以形成一个新的actor-critic算法，使用$\widehat{V_w}(s_t)$作为神经网络近似state-value function，使用TD误差来训练$\widehat{V_w}(s_t)$。

Evaluations

两个场景：无线网络调度和QoE优化
结果都表明FAC算法的优势：能够优化全局的效用、收敛速度快。

————————————————————————————
参考文献：
【1】J. Chen, Y. Wang and T. Lan, “Bringing Fairness to Actor-Critic Reinforcement Learning for Network Utility Optimization,” IEEE INFOCOM 2021 - IEEE Conference on Computer Communications, Vancouver, BC, Canada, 2021, pp. 1-10