跳转至

Adaptive Maximization of Social Welfare

作者: Nicolò Cesa-Bianchi, Roberto Colomboni, Maximilian Kasy
来源: Econometrica
主题: 经济理论 / 应用
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 这个子方向研究的是在缺乏直接反馈的重复决策环境中，如何自适应地学习最优政策以最大化社会福利。其根本统计/科学问题在于：决策者（如政府）在每期选择一个政策（如税率），能观测到的是政策带来的公共收入与行为响应，但无法观测到私人效用（如个体幸福感）。社会福利是收入与私人效用的加权和，这使得目标函数本身带有不可观测的成分，必须通过间接推断与实验探索来学习响应函数，同时平衡探索（尝试新政策以学习响应）与利用（选择当前最优政策）。当前该方向处于从经典单期机制设计向在线学习/后悔最小化框架迁移的阶段，成熟度中等——已有大量拍卖与定价的在线学习结果，但针对“不可观测效用”的社会福利最大化问题，本文是首个给出完整后悔上下界的工作。

发展脉络： - 奠基工作：多臂赌博机（MAB）框架确立了在线探索-利用权衡的基本范式。Bubeck and Cesa-Bianchi (2012) 与 Lattimore and Szepesvari (2020) 系统总结了随机与对抗性设定下的后悔界，为有限策略集提供了 \(T^{1/2}\) 的基准速率。 - 主要进展（机制设计的在线学习）：一系列工作将 MAB 思想引入具体经济机制。Kleinberg and Leighton (2003) 处理了垄断定价（单边不可观测需求），Cesa-Bianchi et al. (2015) 等处理了二价拍卖的保留价学习，Han et al. (2020) 处理了一价拍卖的出价学习。这些工作共同的特征是：目标函数（收入或竞拍者效用）要么完全可观测，要么可通过机制设计还原。 - 当前 frontier（双边贸易与不可观测效用）：Cesa-Bianchi et al. (2021) 将双边贸易（买卖双方估值均私有）投入后悔框架，发现其后悔界为 \(T^{3/4}\)（部分反馈下），揭示了当福利涉及双边私有信息时学习难度陡增。Kasy (2018) 在静态设定下用机器学习（高斯过程先验）讨论最优税收，但未涉及在线后悔界。 - 本文的位置：本文填补了“单边私有信息+不可观测效用”的空白——社会福利最大化中，私人效用不可观测，但公共收入可观测。作者证明对抗性后悔界为 \(T^{2/3}\)，介于垄断定价的 \(T^{1/2}\) 与双边贸易的 \(T^{3/4}\) 之间，并给出随机凹设定下的 \(T^{1/2}\) 界。

子线索聚类： 1. 在线机制学习（可观测目标）：垄断定价、拍卖保留价、一价/二价拍卖出价学习。目标函数（收入或竞拍者效用）可从反馈中直接或间接计算，后悔界通常为 \(T^{1/2}\)。 2. 双边私有信息学习（双边贸易）：Cesa-Bianchi et al. (2021, 2023)。买卖双方估值均不可观测，福利是两者之和，部分反馈下后悔界升至 \(T^{3/4}\) 或更高。 3. 不可观测效用的政策学习（本文）：单边私有信息（私人效用不可观测），但公共收入可观测，且存在响应函数需学习。对抗性后悔界 \(T^{2/3}\)，随机凹设定 \(T^{1/2}\)。 4. 静态最优税收与充分统计量：Kasy (2018) 等。利用（准）实验证据与机器学习估计响应函数，在静态贝叶斯框架下求最优政策，不涉及在线后悔界。

这个方向在追问的核心问题： 1. 当目标函数包含不可观测成分时，在线学习的最小最大后悔速率是什么？ 已知可观测目标时为 \(T^{1/2}\)，双边不可观测时为 \(T^{3/4}\)，本文回答了单边不可观测（且需学习响应函数）时为 \(T^{2/3}\)。 2. 对抗性设定与随机设定下，后悔界是否有本质差异？ 本文表明对抗性下 \(T^{2/3}\) 是最优，而随机且凹的设定下可降至 \(T^{1/2}\)，差异源于凹性提供的结构信息。 3. 探索与利用的权衡在不可观测效用下如何实现？ 经典 MAB 的探索是为了观测目标函数值，本文的探索是为了学习响应函数（从而推断不可观测的效用），这改变了探索的代价结构。

⚠️ 作者的 framing： - 作者的说法：作者将缺口 frame 为“社会福利最大化比垄断定价难（因为效用不可观测），但比双边贸易易（因为只有单边私有信息）”，从而 \(T^{2/3}\) 是“显然的中间速率”。作者强调“响应函数需通过实验学习”是核心难点。 - 被淡化的路线：作者未深入讨论半参数效率界或因果推断中的自适应实验设计（如 Caradonna et al. 的 HOIF 框架），这些路线同样处理不可观测响应与探索-利用权衡，但侧重于估计而非后悔最小化。作者也未讨论计算复杂性约束下的后悔界（如 Daskalakis and Syrgkanis 2015 证明多项式时间无后悔算法在组合拍卖中不可行），这可能是值得研究者去查的缺口。 - 缺失的引用：因果推断中的自适应实验设计（如 Waudby-Smith et al. 的序列分配、Kasy 的自适应处理分配）与本文的在线政策学习高度相关，但 intro 中未出现。此外，半参数约束下的后悔界（如带 nuisance 参数的 MAB）也未提及，这可能是一个值得深挖的交叉点。

张力： 未见明显对立引用。各工作在不同反馈结构与目标可观测性下给出不同后悔界，形成的是难度梯度而非矛盾：垄断定价（\(T^{1/2}\)）→ 社会福利（\(T^{2/3}\)）→ 双边贸易（\(T^{3/4}\)），这恰好是目标函数不可观测成分比例的递增。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据

  • \(T\)：时间 horizon，总决策期数。
  • \(x_t \in \mathcal{X}\)：第 \(t\) 期的政策（如税率），\(\mathcal{X}\) 为政策集。本文主要考虑 \(\mathcal{X} = [-1, 1]\) 或 \([0, 1]\) 的连续区间。
  • \(R(x_t)\)：第 \(t\) 期的公共收入，是政策 \(x_t\) 的函数，可观测。
  • \(U(x_t)\)：第 \(t\) 期的私人效用，是政策 \(x_t\) 的函数，不可观测。
  • \(W(x_t) = \alpha U(x_t) + (1-\alpha) R(x_t)\)：第 \(t\) 期的社会福利，\(\alpha \in [0, 1]\) 为权重参数。这是目标 estimand，但因其包含不可观测的 \(U(x_t)\)，无法直接计算。
  • \(m(x) = E[R(x)]\)：收入的响应函数（期望收入随政策变化的曲线），未知，需学习。
  • \(u(x) = E[U(x)]\)：效用的响应函数，未知，需学习。
  • \(w(x) = \alpha u(x) + (1-\alpha) m(x)\)：期望社会福利函数，最终要最大化的对象。
  • \(x^* = \arg\max_{x \in \mathcal{X}} w(x)\)：最优政策，未知。
  • \(R_t\)：第 \(t\) 期实际观测到的收入随机变量，\(R_t = m(x_t) + \varepsilon_t\)，\(\varepsilon_t\) 为噪声。
  • 后悔：\(Regret_T = \sum_{t=1}^T [w(x^*) - w(x_t)]\)，累计社会福利损失。

模型： 数据生成机制为：每期决策者选 \(x_t\)，观测到 \(R_t = m(x_t) + \varepsilon_t\)（\(\varepsilon_t\) 为零均值噪声），但不观测 \(U_t\)。决策者需从 \(\{x_t, R_t\}_{t=1}^T\) 的历史中学习 \(m(x)\) 与 \(u(x)\)（后者需通过结构假设间接推断），以选择下一期 \(x_{t+1}\)。

可观测数据：\(\{(x_t, R_t)\}_{t=1}^T\)，即政策序列与收入序列。不可观测：\(\{U_t\}_{t=1}^T\)（私人效用）与 \(u(x), m(x)\) 的真实函数形式。

第二步：最小内核——对抗性设定下的 \(T^{2/3}\) 后悔界

最简特例：政策集 \(\mathcal{X} = \{0, 1\}\)（二值政策，如“高税率”与“低税率”），对抗性环境（响应函数可每期任意变化），\(\alpha = 1/2\)（效用与收入等权）。

在这个特例下，核心数学困难是：决策者无法观测 \(U_t\)，因此无法直接计算 \(W_t\)，从而无法知道哪个政策在历史中表现更好。经典 MAB（如 Exp3）依赖观测目标函数值来更新权重，但此处目标函数的一半（效用）是黑箱。

最小问题：在对抗性设定下，能否设计算法使得后悔 \(Regret_T = O(T^{2/3})\)，且证明任何算法的后悔至少为 \(\Omega(T^{2/3})\)？

为什么难： 1. 下界：构造对抗性环境，使得两个政策的收入响应 \(m(x)\) 相近，但效用响应 \(u(x)\) 差异大。决策者若不探索，无法区分；若探索，则必须牺牲收入（因为探索意味着选可能非最优的政策），而收入是唯一可观测的反馈。探索的代价与信息增益之间的权衡不再是 MAB 中的 \(T^{1/2}\)（观测目标值），而是 \(T^{2/3}\)（观测部分目标值+需推断另一部分）。 2. 上界：Exp3 的变体（本文算法）通过将不可观测效用替换为可观测收入的代理信号来更新权重。具体地，算法不直接用 \(W_t\) 更新，而是用 \(R_t\) 结合一个探索补贴来间接推断效用差异。这导致权重更新的方差增大，后悔界从 \(T^{1/2}\) 退化为 \(T^{2/3}\)。

证明直觉： - 下界：利用信息论约束——决策者每期只观测 \(R_t\)（含噪声），而 \(R_t\) 对 \(u(x)\) 的信息量有限（因 \(m(x)\) 可被对抗者操纵）。构造两个世界，\(u(x)\) 差异为 \(\Delta\)，但 \(m(x)\) 差异为 0。决策者需至少 \(\Omega(T^{2/3})\) 次探索才能以足够概率区分这两个世界，否则后悔线性。 - 上界：Exp3 变体以概率 \(\gamma_t \approx T^{-1/3}\) 随机探索，以概率 \(1-\gamma_t\) 利用当前权重。探索期观测 \(R_t\)，利用重要性加权（importance weighting）构造 \(W_t\) 的无偏估计（用 \(R_t\) 加上常数补贴替代 \(U_t\)）。后悔界分解为探索代价（\(\sum \gamma_t \approx T^{2/3}\)）与估计方差代价（\(\sum 1/\gamma_t \approx T^{2/3}\)），两者平衡在 \(T^{2/3}\)。

三、这篇论文做了什么

三句话： ①研究了在不可观测私人效用下重复选择政策以最大化社会福利的在线学习问题； ②核心工具是 Exp3 变体（对抗性）与二分搜索（随机凹设定），结合重要性加权与探索补贴处理不可观测效用； ③主要结论是对抗性后悔界为 \(T^{2/3}\)（匹配下界），随机凹设定下为 \(T^{1/2}\)（连续政策集）。

关键设定与假设： - 设定 1（对抗性）：响应函数 \(m_t(x), u_t(x)\) 可每期任意变化（对抗者选择），无分布假设。政策集 \(\mathcal{X}\) 为有限集或连续区间。反馈为 \(\{x_t, R_t\}\)。 - 设定 2（随机且凹）：响应函数 \(m(x), u(x)\) 固定（不随时间变化），且 \(w(x) = \alpha u(x) + (1-\alpha) m(x)\) 在 \(\mathcal{X}\) 上为凹函数。政策集 \(\mathcal{X}\) 为连续区间（如 \([0, 1]\)）。噪声 \(\varepsilon_t\) 为 i.i.d.，有界支撑或亚高斯。 - 假设 H1（Skorokhod 表示）：利用 Williams (1991) 的 Skorokhod 表示定理，将对抗性随机变量构造为 i.i.d. 均匀变量的函数，从而在对抗性设定下仍可使用概率工具（如鞅差收敛）。统计含义：将对抗性序列嵌入概率空间，使得期望与方差分析合法化。 - 假设 H2（收入与效用的结构关系）：在税收例子中，假设 \(R(x) = x \cdot Y(x)\)（收入=税率×响应收入），\(U(x) = Y(x) - R(x) - C\)（效用=响应收入-税收-常数），从而 \(W(x) = \alpha Y(x) + (1-2\alpha)x Y(x) - \alpha C\)。这提供了从 \(R(x)\) 推断 \(U(x)\) 的结构桥梁。相比已有文献（如 Kasy 2018 的静态设定），本文将此结构关系用于在线后悔界分析。 - 假设 H3（凹性）：随机设定下要求 \(w(x)\) 凹。统计含义：凹性保证全局最优可通过局部搜索（二分法）找到，避免多峰带来的探索困难。相比对抗性设定（无凹性），凹性是后悔界从 \(T^{2/3}\) 降至 \(T^{1/2}\) 的关键。

主要结果： - 定理 1（对抗性下界）：对于任何算法，存在对抗性环境使得 \(Regret_T \geq c \cdot T^{2/3}\)（\(c\) 为常数）。直觉：对抗者可操纵 \(m(x)\) 使得收入反馈对效用差异的信息量极低，决策者必须付出 \(\Omega(T^{2/3})\) 的探索代价。必要条件：政策集至少 2 个选项，\(\alpha > 0\)（效用权重非零）。 - 定理 2（对抗性上界，Exp3 变体）：本文算法（Exp3-Reserve）在对抗性下达到 \(Regret_T \leq C \cdot T^{2/3}\)。直觉：算法以 \(\gamma_t = t^{-1/3}\) 探索率随机化选择，用重要性加权构造 \(W_t\) 的无偏估计（用 \(R_t + \text{常数补贴}\) 替代不可观测 \(U_t\)），后悔界平衡探索代价与估计方差。解决的技术难点：如何在不观测 \(W_t\) 的情况下构造无偏估计，并控制方差。 - 定理 3（随机凹设定上界，二分搜索）：若 \(w(x)\) 凹且政策集为 \([0, 1]\)，二分搜索算法达到 \(Regret_T \leq C \cdot T^{1/2}\)。直觉：凹性保证 \(w(x)\) 的梯度符号可从局部观测推断，二分法每步缩小最优政策区间，后悔界与 MAB 的 \(T^{1/2}\) 相同。必要条件：\(w(x)\) 凹，噪声有界。 - 定理 4（非线性税收例子）：在非线性所得税模型中，将上述结果具体化，给出税率选择的后悔界。结构关系 \(R(x) = x Y(x)\) 允许从收入观测推断效用梯度。

证明路线与技术技巧： - 对抗性上界（定理 2）： 1. 算法设计：Exp3-Reserve。每期以概率 \(\gamma_t\) 随机选政策，以概率 \(1-\gamma_t\) 按权重选。权重更新用 \(\hat{W}_t = \frac{R_t + \text{补贴}}{\text{重要性权重}}\) 作为 \(W_t\) 的无偏估计。 2. 后悔分解：\(Regret_T = \text{探索代价} + \text{估计方差代价} + \text{利用代价}\)。探索代价为 \(\sum \gamma_t \approx T^{2/3}\)，估计方差代价为 \(\sum \frac{1}{\gamma_t} \approx T^{2/3}\)。 3. 关键跳跃点：构造 \(\hat{W}_t\) 使得 \(E[\hat{W}_t] = W_t\)（无偏），且方差可控。难点在于 \(U_t\) 不可观测，无法直接用 \(W_t\) 更新。作者用常数补贴（基于 \(R_t\) 的范围与 \(\alpha\)）替代 \(U_t\)，保证无偏性。 4. 技术技巧：重要性加权、探索补贴、鞅差分析（Azuma-Hoeffding 不等式）。 - 对抗性下界（定理 1）： 1. 构造两个世界：世界 1 中 \(u(x_1) > u(x_2)\)，世界 2 中 \(u(x_1) < u(x_2)\)，但 \(m(x_1) = m(x_2)\)（收入响应相同）。 2. 信息论约束：决策者观测 \(R_t\)，但 \(R_t\) 对区分两个世界的信息量受限于 \(\gamma_t\)（探索率）。需至少 \(\Omega(T^{2/3})\) 次探索才能以足够概率区分。 3. 关键跳跃点：利用 Bretagnolle-Huber 不等式（信息论下界工具）证明任何算法在两个世界下的后悔之和至少为 \(\Omega(T^{2/3})\)。 4. 技术技巧：Bretagnolle-Huber 不等式、KL 散度约束、Skorokhod 表示（嵌入对抗性序列到概率空间）。 - 随机凹设定上界（定理 3）： 1. 算法设计：二分搜索。每步选区间中点 \(x_t\)，观测 \(R_t\)，推断 \(w(x)\) 的梯度符号（利用 \(R(x)\) 与 \(U(x)\) 的结构关系），缩小最优政策区间。 2. 后悔分解：每步后悔为区间长度×最大值差，区间长度每步减半，总后悔为 \(\sum 2^{-t} \approx T^{1/2}\)（结合噪声影响）。 3. 关键跳跃点：从 \(R_t\) 推断 \(w(x)\) 的梯度符号。利用 \(R(x) = x Y(x)\) 与 \(U(x) = Y(x) - R(x) - C\)，可得 \(w'(x)\) 的符号与 \(Y'(x)\) 相关，而 \(Y'(x)\) 可从 \(R(x)\) 的局部变化推断。 4. 技术技巧：二分搜索、凹性利用、噪声下的梯度符号推断。

真实例子与应用： - 非线性所得税：政策 \(x\) 为税率，\(Y(x)\) 为响应收入（劳动力供给响应），\(R(x) = x Y(x)\) 为税收收入，\(U(x) = Y(x) - R(x) - C\) 为私人效用（扣除税收与常数成本）。社会福利 \(W(x) = \alpha Y(x) + (1-2\alpha) x Y(x) - \alpha C\)。本文算法在此模型下达到对抗性后悔 \(T^{2/3}\)，随机凹后悔 \(T^{1/2}\)（若 \(W(x)\) 凹）。例子说明：从税收收入观测可间接推断效用梯度，从而实现不可观测效用下的学习。 - 垄断定价对比：垄断定价中，福利=收入（\(\alpha=0\)），完全可观测，后悔 \(T^{1/2}\)。本文设定（\(\alpha>0\)）更难，因效用不可观测。 - 双边贸易对比：双边贸易中，福利=买方效用+卖方效用，两者均不可观测，后悔 \(T^{3/4}\)（部分反馈）。本文设定（单边不可观测）介于两者之间。

🔎 结论是否比证明窄： - 作者在摘要与 intro 中泛泛 claim“社会福利最大化比垄断定价难，比双边贸易易”，但严格证明仅针对有限政策集或连续区间+特定结构假设（如 \(R(x) = x Y(x)\)）。对于一般连续政策集无结构假设的对抗性设定，下界是否仍为 \(T^{2/3}\) 未严格证明（作者仅讨论了特例）。 - 随机凹设定的 \(T^{1/2}\) 界依赖 \(w(x)\) 凹，但作者未讨论凹性是否必要（即非凹随机设定下的后悔界是否仍为 \(T^{2/3}\) 或更差），仅作为“假设”引入。

四、开放问题（点到为止）

  1. 非凹随机设定下的后悔界：本文随机设定依赖 \(w(x)\) 凹达到 \(T^{1/2}\)，但若 \(w(x)\) 多峰（如非线性税收中劳动力供给响应非单调），后悔界是否退化至 \(T^{2/3}\) 或更差？扎根点：定理 3 假设 \(w(x)\) 凹，intro 未讨论非凹情形。
  2. 半参数约束下的后悔界：本文假设响应函数完全未知（非参数），若引入半参数约束（如 \(m(x)\) 为单调函数、\(u(x)\) 属于某光滑类），后悔界是否可改进？扎根点：intro 未引用半参数后悔界文献，且 Kasy (2018) 用高斯过程先验（半参数）但未分析后悔。
  3. 计算复杂性约束：本文算法（Exp3 变体、二分搜索）均为多项式时间，但未讨论是否存在统计-计算间隙（即多项式时间算法的最小最大后悔是否高于无约束算法）。扎根点：Daskalakis and Syrgkanis (2015) 证明组合拍卖中存在此类间隙，本文 intro 未提及此方向。
  4. 因果推断中的自适应实验设计交叉：本文的探索-利用权衡与因果推断中的自适应处理分配（如 Kasy 2018 的自适应实验）高度相似，但框架不同（后悔最小化 vs. 估计效率）。能否将本文的后悔界工具用于自适应因果推断的效率界？扎根点：intro 未引用自适应因果推断文献，但两者问题结构同构。

提醒：要确认某条是否真 gap，去读同子领域近期约 5 篇的 intro——若都指向“非凹设定”或“半参数后悔界”则可能是共识缺口；若互相打架（如有人 claim 非凹可解、有人 claim 不可解）则是机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论