本文研究了基于多项式逻辑模型（MNL）的多臂老虎机问题，其中卖家从 n 个商品中选取至多 K 个组成推荐组合，顾客根据商品的效用参数进行随机选择，目标是最大化累计期望收益。静态问题在已知模型参数时可高效求解；动态问题中效用未知，传统方法遗憾界差。文章提出一种基于周期的 UCB 算法：通过持续推荐同一组合直至顾客不购买，利用几何分布性质获得效用无偏估计，并构造置信区间。算法在每周期选取置信上界最大的组合，最终实现遗憾上界为 $\widetilde{O}(\sqrt{nT})$，匹配理论下界，显著优于直接应用 UCB 的组合数指数依赖结果。

多项式逻辑模型（MNL）多臂老虎机

商品组合选择

商品池：$[n] = {1,2,3,\dots,n}$，$r_i$：销售商品 $i$ 的收益（$r_i \in [0,1]$）

选择模型 $p_a(S)$：当向顾客提供商品组合 $S \subseteq [n]$ 时，顾客购买商品 $a \in S$ 的概率

多项式逻辑模型（MNL）选择模型

效用参数：每个商品 $i \in [n]$ 对应的 $u_i \in [0,1]$。

$p_a(S) \triangleq \frac{u_a}{1 + \sum_{i \in S} u_i}$：购买概率与效用成正比。

$1$ 表示“不购买”

组合优化目标

选择 $S \subseteq [n]$，满足 $|S| \le K$（容量约束）
以最大化 $R(S) = \sum_{a \in S} r_a \cdot p_a(S) \overset{\text{在 MNL 模型中}}{=} \frac{\sum_{i \in S} r_i u_i}{1 + \sum_{i \in S} u_i}$，即提供组合 $S$ 的期望收益

静态问题

假设我们已知模型的所有信息（所有 $r_i$ 和 $u_i$）。如何高效计算最优的 $S$？

决策版本

给定 $\beta \in [0,1]$，判断是否存在 $S \subseteq [n]$，使得 $|S| \le K$ 且 $R(S) = \frac{\sum_{i \in S} r_i u_i}{1 + \sum_{i \in S} u_i} \ge \beta$。

（若能高效解决决策版本，则可通过二分搜索在 $O(\log \frac{1}{\varepsilon})$ 次迭代内以精度 $\varepsilon$ 求得最优收益 $\beta^\ast$。）

分析

注意：$R(S) \ge \beta \iff \sum_{i \in S} r_i u_i \ge \beta + \sum_{i \in S} \beta \cdot u_i \iff \sum_{i \in S} (r_i - \beta) \cdot u_i \ge \beta$

因此，$\exists S \subseteq [n], |S| \le K, R(S) \ge \beta \iff \max_{S \subseteq [n], |S| \le K} \sum_{i \in S} (r_i - \beta) \cdot u_i \ge \beta$。

为最大化左侧，我们按 $(r_i - \beta) \cdot u_i$ 的值选取前 $K$ 个商品（仅当其值 $\ge 0$ 时）。

引理

我们可以在时间 $O(n \log n \cdot \log \frac{1}{\varepsilon})$ 内找到一个组合 $S$：$|S| \le K$，使得 $R(S) \ge R(S^\ast) - \varepsilon$（其中 $S^\ast$ 为最优组合）。

注记

静态优化问题也存在强多项式时间算法，即时间复杂度为 $\text{poly}(n)$：不依赖于精度参数 $\varepsilon$，甚至不以对数形式依赖。

动态问题

效用参数（$u_i$）对卖家未知。给定时间长度 $T$，卖家依次进行 $T$ 次商品组合推荐 $S_1, S_2, S_3, \dots, S_T$（可基于先前可观察的顾客选择进行自适应），以最小化 $\text{Reg}T = \sum{t=1}^{T} \left( R(S^\ast) - \mathbb{E} R(S_t) \right)$。

简单方法

将每个可能的组合 $S \in \binom{[n]}{\le K}$ 视为一个臂，其平均收益为 $R(S) \in [0,1]$，直接应用 UCB 算法，得到 $\text{Reg}_T \le O(1) \cdot \sqrt{\binom{n}{\le K} \cdot T \log T}$：对 $n$ 和 $K$ 的依赖较差。

目标

设计一个算法，使得 $\text{Reg}_T \le \widetilde{O}(\sqrt{nT})$（匹配 $\Omega(\sqrt{nT})$ 的下界）。

问题

假设我们已进行了 $t$ 次推荐：$S_1, S_2, S_3, \dots, S_t$，并观察到顾客选择。如何估计效用参数？

“通用解法”：最大似然估计（MLE）。问题：无闭式解，分析困难。

基于周期的推荐

当我们选择一个组合 $S$ 时，不是只推荐一次，而是持续推荐“一个周期”。更精确地说，在一个周期内，持续提供 $S$，直到顾客不购买（或达到时间上限 $T$）。

分析

在第 $\ell$ 个周期中，推荐组合 $S_\ell$。对每个 $i \in S_\ell$，令 $T_{\ell,i} =$ 顾客购买商品 $i$ 的次数。令 $E_\ell$ 为第 $\ell$ 个周期的长度。

当 $\ell$ 不是最后一个周期时，对每个 $i \in S_\ell$：$\Pr[T_{\ell,i} = 0] = \frac{1}{1 + \sum_{j \in S_\ell} u_j} + \frac{(\sum_{j \in S_\ell} u_j) - u_i}{1 + \sum_{j \in S_\ell} u_j} \cdot \Pr[T_{\ell,i} = 0]$ $\Rightarrow \Pr[T_{\ell,i} = 0] = \frac{1}{1 + u_i}$

对每个 $\alpha = 1,2,3,\dots$，$\Pr[T_{\ell,i} = \alpha] = \frac{u_i}{1 + \sum_{j \in S_\ell} u_j} \cdot \Pr[T_{\ell,i} = \alpha - 1] + \frac{(\sum_{j \in S_\ell} u_j) - u_i}{1 + \sum_{j \in S_\ell} u_j} \cdot \Pr[T_{\ell,i} = \alpha]$ $\Rightarrow \Pr[T_{\ell,i} = \alpha] = \frac{u_i}{1 + u_i} \Pr[T_{\ell,i} = \alpha - 1] = \frac{u_i^\alpha}{(1 + u_i)^{\alpha + 1}}$。

因此，我们有

断言

$T_{\ell,i} \sim \text{Geometric}\left(\frac{1}{1+u_i}\right)$（失败模型）

更重要的是，$\mathbb{E}[T_{\ell,i}] = u_i$：$u_i$ 的无偏估计量。

经过 $\ell$ 个周期后，令 $N_{\ell,i} = \#\{S_{\ell’} \ni i : \ell’ \in \{1,2,\dots,\ell\}\}$，$\widehat{u}_{\ell,i} = \frac{\sum_{\ell’ : S_{\ell’} \ni i} T_{\ell’,i}}{N_{\ell,i}}$

置信区间：独立同分布几何随机变量之和的集中性

引理

设 $X_1, X_2, \dots, X_n \overset{\text{i.i.d.}}{\sim} \text{Geometric}(p)$，$X = \sum_{i=1}^{n} X_i$，$\mu = \frac{1-p}{p} = \mathbb{E}X_i$。定义 $H(\lambda) \triangleq \mu \lambda \cdot \ln \lambda - (1 + \mu \lambda) \ln \frac{1 + \mu \lambda}{1 + \mu}$，则

1. $\forall \lambda \ge 1$，$\Pr[X \ge \lambda \cdot n \mu] \le \exp(-n \cdot H(\lambda))$。

2. $\forall \lambda \in [0,1]$，$\Pr[X \le \lambda \cdot n \mu] \le \exp(-n \cdot H(\lambda))$。

便利形式

对于 $\mu \in [0,1]$，

1. $\forall \Delta \in [0,1]$，$\Pr[X \ge n \mu \cdot (1+\Delta)] \le \exp\left(-\frac{n \mu \Delta^2}{8}\right)$，$\Pr[X \le n \mu \cdot (1-\Delta)] \le \exp\left(-\frac{n \mu \Delta^2}{8}\right)$。

2. $\forall \Delta > 1$，$\Pr[X \ge n \mu \cdot (1+\Delta)] \le \exp\left(-\frac{n \mu \Delta}{8}\right)$。

因此，$\begin{cases} \Pr\left[\left|\frac{X}{n} - \mu\right| \ge \sqrt{\frac{16 \mu \cdot \ln \Delta^{-1}}{n}}\right] \le 2\Delta^2 & \text{（当 } \sqrt{\frac{16 \mu \ln \Delta^{-1}}{n}} \le \mu\text{）}
\Pr\left[\frac{X}{n} - \mu \ge \frac{16 \ln \Delta^{-1}}{n}\right] \le \Delta^2 & \text{（否则）} \end{cases}$

断言

在固定 $i$ 和固定 $N_{\ell,i}$ 的条件下，以概率 $1 - O(\frac{1}{(Tn)^2})$，我们有 \(\begin{cases} \widehat{u}_{\ell,i} \le u_i + \sqrt{\frac{16 u_i \ln(Tn)}{N_{\ell,i}}} + \frac{16 \ln(Tn)}{N_{\ell,i}} & (\ast\ast) \\ \widehat{u}_{\ell,i} \ge \max\left\{ u_i - \sqrt{\frac{16 u_i \ln(Tn)}{N_{\ell,i}}}, 0 \right\} \end{cases}\)

\[(\ast\ast) \Rightarrow |\widehat{u}_{\ell,i} - u_i| \le \sqrt{\frac{32 \widehat{u}_{\ell,i} \ln(Tn)}{N_{\ell,i}}} + \frac{80 \ln(Tn)}{N_{\ell,i}} \quad (\ast)\]

对所有可能的 $i$ 和 $N_{\ell,i}$ 应用联合界，我们有 $(\ast)$ 和 $(\ast\ast)$ 在所有 $\ell$ 和 $i$ 上以概率 $\ge 1 - \frac{1}{T}$ 一致成立。

UCB 算法

1. $\ell \leftarrow 0$

2. WHILE 时间上限 $T$ 未达到 DO

   1. 对每个 $i$，设置 $\overline{u}{\ell,i} = \min{1, \widehat{u}{\ell,i} + CI_{\ell,i}}$。

   2. 选择 $S_{\ell+1} = \underset{S \subseteq [n], |S| \le K}{\arg\max} \left\{ \frac{\sum_{i \in S} \overline{u}_{\ell,i} r_i}{1 + \sum_{i \in S} \overline{u}_{\ell,i}} \right\}$（多项式时间可解）

   3. $\ell \leftarrow \ell + 1$，将 $S_\ell$ 推荐一个周期（达到时间上限 $T$ 时终止）

分析

假设 $(\ast)$ 和 $(\ast\ast)$ 一致成立。令 $\overline{R}_\ell(S) = \frac{(\sum_{i \in S} \overline{u}_{\ell,i} \cdot r_i)}{(1 + \sum_{i \in S} \overline{u}_{\ell,i})}$。

断言 1

$\overline{R}_\ell(S_{\ell+1}) \ge R(S^\ast)$

证明

设 $R(S^\ast) = \beta$，如前所述：$\sum_{i \in S^\ast} (r_i - \beta) \cdot u_i \ge \beta$（实际上等号成立）。

事实上，对所有 $i \in S^\ast$，有 $r_i - \beta \ge 0$（否则可从 $S^\ast$ 中剔除 $i$ 得到更优组合）。因此，$\overline{R}_\ell(S_{\ell+1}) \ge \overline{R}_\ell(S^\ast) \ge \beta = R(S^\ast)$，因为 $\sum_{i \in S^\ast} (r_i - \beta) \overline{u}_{\ell,i} \ge \sum_{i \in S^\ast} (r_i - \beta) u_i \ge \beta$。

为便于分析，假设我们运行算法时不设时间上限，则有：

断言 2

对每个周期 $\ell$，$(\mathbb{E} E_\ell) \cdot R(S_\ell) \ge (\mathbb{E} E_\ell) \cdot \overline{R}_{\ell-1}(S_\ell) - 2 \sum_{i \in S_\ell} CI_{\ell-1,i}$。
（以头 $(\ell-1)$ 个周期为条件）第 $\ell$ 个周期的期望收益。

证明

$\begin{aligned} (\mathbb{E} E_\ell) \cdot R(S_\ell) &= \left( \sum_{i \in S_\ell} u_i + 1 \right) \cdot \frac{\sum_{i \in S_\ell} u_i r_i}{1 + \sum_{i \in S_\ell} u_i} = \sum_{i \in S_\ell} u_i r_i
&\ge \sum_{i \in S_\ell} \left( \overline{u}_{\ell-1,i} - 2 CI_{\ell-1,i} \right) r_i \ge \sum_{i \in S_\ell} \overline{u}_{\ell-1,i} \cdot r_i - 2 \sum_{i \in S_\ell} CI_{\ell-1,i} \end{aligned}$

另一方面，$\overline{R}_{\ell-1}(S_\ell) \cdot (\mathbb{E} E_\ell) = \frac{\sum_{i \in S_\ell} \overline{u}_{\ell-1,i} \cdot r_i}{1 + \sum_{i \in S_\ell} \overline{u}_{\ell-1,i}} \cdot \left(1 + \sum_{i \in S_\ell} u_i\right) \le \sum_{i \in S_\ell} \overline{u}_{\ell-1,i} \cdot r_i$。

引理

以头 $(\ell-1)$ 个周期为条件，第 $\ell$ 个周期的期望遗憾为 \(\begin{aligned} (\mathbb{E} E_\ell) \left( R(S^\ast) - R(S_\ell) \right) &\le (\mathbb{E} E_\ell) \left( \overline{R}_{\ell-1}(S_\ell) - R(S_\ell) \right) \quad \text{（由断言 1）} \\ &\le 2 \sum_{i \in S_\ell} CI_{\ell-1,i} \quad \text{（由断言 2）} \\ &= O(1) \cdot \sum_{i \in S_\ell} \left( \sqrt{\frac{\widehat{u}_{\ell-1,i} \ln(Tn)}{N_{\ell-1,i}}} + \frac{\ln(Tn)}{N_{\ell-1,i}} \right) \\ &\le O(1) \cdot \sum_{i \in S_\ell} \left( \sqrt{\frac{u_i \ln(Tn)}{N_{\ell-1,i}}} + \frac{\ln(Tn)}{N_{\ell-1,i}} \right) \quad \text{（由 $(\ast\ast)$）} \end{aligned}\)

令 $\ell^\ast$ 为包含时间 $T$ 的周期，前 $T$ 个时间步的期望遗憾为： \(\begin{aligned} &\le O(1) \mathbb{E} \sum_{\ell=1}^{\ell^\ast-1} \sum_{i \in S_\ell} \left( \sqrt{\frac{u_i \ln(Tn)}{N_{\ell-1,i}}} + \frac{\ln(Tn)}{N_{\ell-1,i}} \right) + \mathbb{E} E_{\ell^\ast} \\ &\quad \underbrace{\downarrow}_{L \to \le n} \\ &\le \mathbb{E} \sum_{i \in [n]} \sum_{\ell \in N_i} \left( \sqrt{\frac{u_i \ln(Tn)}{N_{\ell-1,i}}} + \frac{\ln(Tn)}{N_{\ell-1,i}} \right) \\ &\quad \underbrace{\downarrow}_{\text{在 } \ell^\ast \text{ 之前推荐 } i \text{ 的周期集合}} \\ &\le O(1) \cdot \mathbb{E} \sum_{i \in [n]} \left( \sqrt{u_i \ln(Tn) \cdot |N_i|} + \ln(Tn) \cdot \ln(|N_i|) \right) \\ &\le O(1) \left( \mathbb{E} \sum_{i \in [n]} \sqrt{u_i \ln(Tn) \cdot |N_i|} + n \ln(Tn) \cdot \ln T \right) \\ &\quad \underbrace{\downarrow}_{\le \sqrt{\ln(Tn)} \cdot \mathbb{E} \sqrt{n} \cdot \sqrt{\sum_{i \in [n]} u_i |N_i|}} \\ &\le \sqrt{n \ln(Tn)} \cdot \sqrt{\mathbb{E} \sum_{i \in [n]} u_i |N_i|} \le \sqrt{n \ln(Tn)} \cdot \sqrt{\mathbb{E} \sum_{\ell=1}^{\ell^\ast-1} E_\ell} \le \sqrt{n T \ln(Tn)} \end{aligned}\)

综上，我们有：

定理

MNL-UCB 的遗憾至多为 $O(\sqrt{nT \ln(nT)} + n \ln(nT) \ln T)$。