接下来我总共花了将近四天时间才将论文《Towards Long-term Fairness in Recommendation》^[1]理解透彻。因为该论文用到了强化学习(Reinforcement Learning)，而强化学习不像之前的生成对抗网络(GAN)一样简洁明了，涉及的数学知识非常多。
在看论文之前我花费了很所时间去补强化学习的基础，其中牵涉到的知识点还包括随机过程、数值优化等，因此我在掌握文章背景上就耗费了很多时间和精力。
不过当我将强化学习的背景搞清楚后，整片文章读起来的速度就大大加快了，因为该文章本质上就是在强化学习的策略优化算法(论文采用的的是经典的置信域优化算法)的基础上加一个公平性约束而已。我我自身理解的基础上，对该论文的结构和核心思想进行了模块化地详细地梳理，而这篇日志也就是我记录的梳理论文思想的心路历程。

论文创新点

该论文有三个要点：
其一是视角独到，在基于强化学习的推荐系统框架上建模，可以保证长期的公平性问题，而不是像大多数论文一样只保证短期的公平性；
其二是将公平性约束做为强化学习中著名的置信域优化算法的一个约束项来处理，简洁明了；
其三是公平性约束是线性的，对于模型的参数优化能求得解析解，这样可以大大降低算法的时间复杂度。

背景知识储备

首先，我通过阅读强化学习的经典著作《Reinforcement learning: An introduction》^[2]对强化学习中的许多基本概念有了初步的认知。强化学习的关键思想是马尔可夫决策过程(Markov Decision Processes, MDPs)。一个MDP可以用一个元组\(M=(\mathcal{S}, \mathcal{A},\mathcal{P}, \mathcal{R}, \mu , \gamma )\)来表示，这\(\mathcal{S}\)表示\(n\)个状态\(s\)的集合。\(A\)表示\(m\)个动作\(a\)的集合，\(\mathcal{P}: \mathcal{S}\times \mathcal{A} \times \mathcal{S} \to [0,1]\)表示状态转移函数。对于在经过动作\(a_{t}\)后，由状态\(s_{t}\)转移为状态\(s_{t+1}\)的概率我们可以表示为\(P(s_{t+1}|s_{t}, a_{t})\)。\(\mathcal{R}:\mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}\)。我们将做出动作\(a_{t}\)后，由状态\(s_{t}\)转移到状态\(s_{t+1}\)而触发的奖励记作\(r(s_{t}, a_{t}, s_{t+1})\)，\(\mu: \mathcal{S} \to [0, 1]\)是一个初始状态分布。\(\gamma \in [0, 1)\)是折扣因子。一个固定的策略\(\pi: \mathcal{S} \to \mathcal{P}(\mathcal{A})\)是一个从状态到动作概率分布的映射，\(\pi(a|s)\)表示在状态\(s\)下选择动作\(a\)的概率，我们将所有策略的集合记作\(\prod\)。在强化学习中，我们目标是学习一个策略\(\pi\)，它能够最大化无穷时间步的折扣总回报\(J(\pi)\)

\[J(\pi) = \mathop{\mathbb{E}}_{\tau \sim \pi}[\sum_{t=0}^{\infty}\gamma^{T}R(s_{t}, a_{t}, s_{t+1})] \tag{1} \]

这里\(\tau\)表示一个轨迹(trajectory)，例如\(\tau=(s_{0}, a_{0}, s_{1}, a_{1}, ...)\)，且\(\tau \sim \pi\)是一个简略记法，表示轨迹的分布依靠于\(\pi:s_{0} \sim \mu , a_{t} \sim \pi(\cdot |s_{t}), s_{t+1} \sim P(\cdot | s_{t}, a_{t})\),使\(R(\tau)\)表示从当前\(t\)时刻到回合结束的折扣回报（累计折扣奖励)。
我们将动作价值函数表示为\(Q^{\pi}(s, a)=\mathop{\mathbb{E}}_{\tau \sim \pi}[R(\tau)|s_{0}=s, a_{0}=a]\)，状态价值函数表示为\(V_{\pi}(s)= \mathop{\mathbb{E}}_{a_{t}\sim \pi(\cdot|s_{t})}[Q^{\pi}(s, a)] = \mathop{\mathbb{E}}_{\tau \sim \pi}[R(\tau)|s_{0}=s]\),优势函数表示为\(A^{\pi}(s, a)=Q^{\pi}(s, a)-V^{\pi}(s)\)。

论文理解

而本篇论文采用了在MDP之上改造的受限马尔可夫决策过程(Constrained Markov Decision Process, CMDP)。CMDP在MDP的基础上添加了一些约束，这些约束限制了MDP所允许的策略。具体而言，MDP被一些辅助的代价函数\(C_{1}, ..., C_{m}\)约束，相应的限制为\(\textbf{d}_{1},..., \textbf{d}_{m}\)，这意味着在代价函数上的折扣总代价需要以\(\textbf{d}_{i}\)为上界。类似于传统MDP中的奖励，每个函数\(C_{i}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to R\)将状态转换元组(即\((s_{t}, a_{t}, s_{t+1})\))映射到代价。论文中用\(J_{C_{i}}(\pi)\)表示策略\(\pi\)关于代价函数\(C_{i}\)的折扣总代价:

\[ J_{C_{i}}(\pi) = \mathop{\mathbb{E}}_{\tau \sim \pi}[\sum_{t=0}^{\infty}\gamma^{T}C_{i}(s_{t}, a_{t}, s_{t+1})] \tag{2} \]

一个CMDP的策略集合是\(\prod_{C} = \{\pi \in \prod: \forall i, J_{C_{i}}(\pi) \leqslant \textbf{d}_{i}\}\)，且强化学习在CMDP中的一个任务是找到\(\pi^{*} = \arg\max_{\pi \in \prod_{C}}J(\pi)\)，这里\(J(\pi)\)是一个按照等式\((1)\)定义折扣总回报。我们用\(V_{C_{i}}^{\pi}, Q_{C_{i}}^{\pi}\)和\(A_{C_{i}}^{\pi}\)来类比地替代\(V_{\pi}, Q_{\pi}, A_{\pi}\)，其中分别用代价函数\(C_{i}\)替代原本的奖励函数\(R\)。
而对于优化策略，论文中采用类似于置信域优化方法的“受限策略优化”(Constrained Policy Optimization, CPO)。CPO中的策略迭代形式如下：

\[\begin{matrix} \pi_{k+1} = \mathop{\arg\max}_{\pi \in \prod_{\theta}}\mathop{\mathbb{E}}_{s\sim d^{\pi_{k}}, a\sim \pi}[A^{\pi_{k}}(s, a)],\\ s.t. \quad J_{C_{i}}(\pi_{k}) + \frac{1}{1-\gamma} \mathop{\mathbb{E}}_{s\sim d^{\pi_{k}}, a\sim \pi}[A_{C_{i}}^{\pi_{k}}(s, a)] \leqslant \textbf{d}_{i}, \forall i \\ \overline{D}_{KL}(\pi || \pi_{k}) \leqslant \delta \end{matrix} \tag{3} \]

这里\(\prod_{\theta} \subset \prod\)是一个参数为\(\theta\)的参数化策略的集合(比如有着固定架构的神经网络)。\(d^{\pi_{k}}\) 是一个在策略\(\pi_{k}\)下的状态分布。\(\overline{D}_{KL}\)表示平均KL散度，这里\(\delta>0\)是步长(置信域半径)。集合\(\{\pi_{\theta} \in \prod_{\theta}: D_{KL}(\pi || \pi_{k}) \leqslant \delta\}\)被称为置信域。特别地，对于只有一个线性约束的问题，只存在一个解析解。我们将式子\((3)\)中的目标函数的梯度表示为\(g\)，约束的梯度表示为\(b\)，KL散度的Hessian矩阵表示为\(H\)，并定义\(c=J_{C}(\pi_{k})-d\)，则对式\((3)\)的近似为

\[\begin{matrix} \theta_{k+1} = \mathop{\arg\max}_{\theta}g^{T}(\theta-\theta_{k}) \\ s.t. \quad c+b^{T}(\theta - \theta_{k}) \leqslant 0 \\ \frac{1}{2}(\theta - \theta_{k})^{T}H(\theta-\theta_{k}) \leqslant \delta \end{matrix} \tag{4} \]

就这样，论文通过迭代算法对策略的参数\(\theta\)进行优化。
接下来论文阐述了CMDP在实际推荐中运用的具体细节。在每个时间步\((t_{1}, t_{2}, t_{3}, t_{4}, t_{5})\)，用户向推荐系统发送请求，推荐智能体\(G\)会将当前用户的特征表示和候选物品\(\mathcal{I}\)做为输入，并生成推荐物品列表\(L \in \mathcal{I}^{K}\)，这里 \(K \geqslant 1\)。用户\(u\)收到了推荐的物品清单\(L\)后会以点击物品的方式给出他(或者她)的反馈\(B\)。因此，状态\(s\)可以用户的特征来表示(比如用户最近的点击历史)，动作\(a\)用\(L\)中的物品表示奖励馈\(r\)是在目前状态采取动作\(a\)的即时反馈(比如用户是否点击\(L\)中的物品)。代价\(c\)是即时代价(比如推荐的物品是否来自敏感群组)。这样，我们可以将强化学习中的各元素和推荐系统中的元素联系起来：
\(\bullet \quad 状态 \mathcal{S}\): 状态\(s_{t}\)是用户最近和推荐系统的正交互历史\(H_{t}\)的表示，以及他(或她)的人口结构信息（如果存在的话）。
\(\bullet \quad 动作 \mathcal{A}\): 动作\(a_{t}=\{a_{t}^{1}, ..., a_{t}^{K}\}\)是一个推荐列表，包括在\(t\)时刻和状态\(s_{t}\)下给用户\(u\)推荐\(K\)个物品的推荐列表。
\(\bullet \quad 奖励 \mathcal{R}\): 给定基于动作\(a_{t}\)和用户状态\(s_{t}\)的推荐，用户会提供他(或者她)的反馈，比如点击、跳过或购买等，推荐系统会依据用户的反馈接收到即时奖励\(R(s_{t}, a_{t})\)。
\(\bullet \quad 代价 \mathcal{C}\): 给定基于动作\(a_{t}\)的推荐，环境给出了基于特定问题的代价函数值(比如推荐列表中来自敏感群组的物品数量)，并将该即时代价\(C(s_{t}, a_{t})\)发给推荐系统。
\(\bullet \quad 折扣率 \gamma_{r} 和 \gamma_{c}\): \(\gamma_{r} \in [0, 1]\)是一个用于权衡长期奖励值的因子，\(\gamma_{c} \in [0, 1]\)是另一个权衡长期代价值的因子。

论文中算法的目的是学习最优策略，以最大化在一定的公平性约束下的累计奖励。论文将奖励函数和代价函数定义如下:

\[ R(s_{t}, a_{t}, s_{t+1}) = \sum _{l=1}^{K} \mathbb{I} (a_{t}^{l} \text{得到用户的正面反馈}) \tag{5} \]

\[ C(s_{t}, a_{t}, s_{t+1}) = \sum _{l=1}^{K} \mathbb{I} (a_{t}^{l} \text{在敏感群组里}) \tag{6} \]

这里\(a_{t} = \{a_{t}^{1},\cdots , a_{t}^{K}\}\)代表了包括了\(K\)个物品ID的推荐列表，这些物品由当前策略在时间点\(t\)处选择。在论文中代价函数的表示方式如式\((6)\)所示，表示在时间\(t\)，暴露给用户的敏感群组物品总数。根据论文中的描述，我们有

\[ C(s_{t}, a_{t}, s_{t+1}) \leqslant \frac{\alpha}{1+\alpha}K = \alpha^{'}K \tag{7} \]

使\(C\leqslant \alpha^{'}K\)这个约束在每一轮迭代的时候得到满足，我们能得到折扣后的总代价

\[ J_{C}(\pi) = \mathop{\mathbb{E}}_{\tau \sim \pi}[ \sum_{t=0}^{T} \gamma_{c}^{T} C(s_{t}, a_{t}, s_{t+1})] \leqslant \sum_{t=0}^{T}\gamma_{c}^{t}\alpha^{'}K \tag{8} \]

这里\(T\)是推荐系统轨迹的长度，等式\((8)\)是我们优化问题的群组公平性约束，论文中将不公平性约束的上界\(d\)表示如下

\[ \textbf{d} = \sum_{t=1}^{T}\gamma_{c}^{t} \alpha^{'}K \tag{9} \]

就这样，一旦定义好用于推荐的CMDP及特定的奖励函数（如式\((5)\)所示），代价函数（如式\((6)\)所示)和约束上界\(d\)，我们就可以将它们都带入等式\((4)\)建立公平性限制的策略优化框架。值得注意的是论文中的模型仅仅只包括线性公平性约束。因此，正如之前提到的，求解式\((4)\)我们能得出解析解（如果问题是可解的）。具体求解框架的细节可以参见论文。

参考文献

• [1] Ge Y, Liu S, Gao R, et al. Towards Long-term Fairness in Recommendation[C]//Proceedings of the 14th ACM International Conference on Web Search and Data Mining. 2021: 445-453.
• [2] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. MIT press, 2018.
• [3] Singh A, Joachims T. Fairness of exposure in rankings[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 2219-2228.