Online Bidding for Contextual First-Price Auctions with Budgets under One-Sided Information Feedback

Each language version is independently generated for its own context, not a direct translation.

这篇文章讲的是如何在网络广告竞价中，像一个聪明的“老练买家”一样，在不知道对手出多少价、不知道广告价值、且手里钱（预算）有限的情况下，如何一步步学会出价，从而赚到最多的钱。

为了让你更容易理解，我们可以把整个场景想象成一场**“盲盒拍卖会”**。

1. 场景设定：一场特殊的拍卖会

想象你是一家广告公司的“采购员”，你的任务是每天在成千上万个**“盲盒”**（也就是网络广告位）里挑选最好的买下来。

盲盒（广告位）： 每个盲盒里都藏着一个“用户”，有的用户很有钱（价值高），有的普通。
你的预算： 你手里只有一笔固定的钱（比如 500 元），花完了就不能再买了。
对手（其他买家）： 还有无数其他采购员也在抢这些盲盒。
规则变了（第一价格拍卖）： 以前是“谁出价高谁赢，但只付第二高价”（像拍卖古董，很公平）。现在变成了**“谁出价高谁赢，直接付你出的那个价”（像买股票，你出多少就付多少）。这意味着你不能乱喊高价，必须“压价”**（Bid Shading），否则就亏了。
最大的难点（单向反馈）：
- 如果你赢了，你只知道你赢了，付了多少钱，赚了多少钱。
- 如果你输了，你完全不知道对手出了多少钱！你只知道“对手比我高”，但高多少？不知道。
- 这就像你玩猜拳，输了只知道“对手赢了”，但不知道他出了“石头”还是“剪刀”。

2. 核心挑战：如何在“瞎猜”中变聪明？

以前的研究假设对手出价的规律是固定的（比如对手总是出 5 元），或者假设你能看到所有对手的价格。但现实是：

对手很狡猾： 对手的价格不是固定的，而是根据**“盲盒的特征”**（比如这个用户是年轻人还是老年人，是晚上还是早上）变化的。
信息太少： 你只能在你输掉的时候，隐约感觉到对手的价格（因为对手赢了，说明对手价格 > 你的价格），但你赢的时候，对手的价格就彻底消失了。
钱要省着花： 你不能一开始就乱花钱去试探，否则钱花光了，后面再好的机会也买不起了。

3. 作者的解决方案：三个“独门秘籍”

作者提出了一套算法，就像给采购员装上了三个“超能力”：

秘籍一：用“幸存者偏差”来反推对手（鲁棒回归法）

比喻： 想象你在玩一个游戏，你每次出 5 元，如果输了，你就知道对手出了 6 元或更多。如果你出 10 元，输了，对手可能出了 11 元。
做法： 作者发明了一种**“分而治之”的统计方法。他们把盲盒分成两堆（比如“年轻人”和“老年人”）。虽然你看不到具体的对手价格，但通过观察在“年轻人”堆里你输了多少次，在“老年人”堆里输了多少次，利用数学上的“分位数不变性”**（Quantile Invariance），可以像拼图一样，把对手价格随特征变化的规律（那个未知的参数 $\alpha$ ）给“算”出来。
简单说： 即使你看不到对手的底牌，但通过长期观察“我在什么情况下会输”，就能猜出对手大概的出牌习惯。

秘籍二：像“双管齐下”的侦探（分阶段学习）

比喻： 你不能一边开车一边换轮胎。作者把时间分成了“探索期”和“利用期”。
做法：
- 探索期（A 阶段）： 专门用来“试错”。这时候出价策略比较激进，目的是收集数据，用上面的“秘籍一”算出对手的价格规律。
- 利用期（B 阶段）： 拿着算出来的规律，开始精准出价，尽量多赚钱。
- 交替进行： 随着时间推移，他们不断交替这两个阶段，让估算越来越准，出价越来越精。

秘籍三：给钱包加个“智能阀门”（对偶更新）

比喻： 你的预算就像水龙头里的水。如果水放得太快，后面就没了；放得太慢，前面的机会就错过了。
做法： 算法里有一个虚拟的“价格标签”（ $\lambda$ $λ$ ）。
- 如果钱花得太快，这个标签就会变高，告诉算法：“现在的广告太贵了，要更保守一点，或者只买特别便宜的”。
- 如果钱花得太慢，标签变低，告诉算法：“可以大胆一点，多买几个”。
- 这个机制自动调节你的出价策略，确保在 T 天结束时，钱刚好花得差不多，不多不少。

4. 结果如何？

作者证明了，用这套方法：

学得很快： 随着时间推移，你的总收益和“如果上帝视角知道所有秘密的最优策略”之间的差距（遗憾值），会以 $\sqrt{T}$ 的速度增长。
这意味着什么？ 在数学上，这已经是**“最优”**的速度了。也就是说，在这么困难（对手价格未知、信息不全、有预算限制）的情况下，人类能做到的最好程度，就是这个算法达到了。

5. 总结：这篇论文解决了什么？

这就好比在迷雾中开车：

以前： 要么假设路是直的（对手价格固定），要么假设你能看清所有车（全信息反馈）。
现在： 路是弯的（对手价格随环境变），而且大雾弥漫（只能看到输赢，看不到对手具体速度），还要保证油（预算）能撑到终点。
这篇论文： 发明了一套**“盲开导航系统”**。它通过观察“什么时候会撞车（输）”来反推路况，通过“油门和刹车的自动调节”来省油，最终证明这套系统能开得和“老司机”一样好。

一句话总结：
这是一篇关于如何在信息不全、对手多变、预算有限的复杂网络拍卖中，通过聪明的统计推断和动态策略调整，实现**“花最少的钱，赚最多的钱”**的数学指南。

Each language version is independently generated for its own context, not a direct translation.

1. 问题背景与定义 (Problem Formulation)

核心场景：
论文研究的是在**重复一价拍卖（First-Price Auctions, FPA）中，带有预算约束（Budget Constraints）**的在线竞价问题。随着数字广告市场从二价拍卖（Vickrey）向一价拍卖的范式转变，竞价者不再能简单地报出真实估值，而必须策略性地“压低”出价（Bid Shading）以获取剩余价值。

关键挑战：

上下文相关竞争（Contextual Competitors）：竞争对手的最高出价 $d_t$ 不仅随机，还依赖于当前的广告展示上下文 $x_t$ （如用户画像）。模型假设为线性关系： $d_t = \alpha x_t + z_t$ ，其中 $\alpha$ 未知， $z_t$ 服从未知分布 $G$ 。
单侧信息反馈（One-Sided Information Feedback）：这是本文最独特的设定。竞价者仅在输掉拍卖时（即 $b_t < d_t$ ）才能观察到竞争对手的最高出价 $d_t$ ；如果赢了（ $b_t > d_t$ ），竞价者只知道 $d_t < b_t$ ，但不知道 $d_t$ 的具体数值。这种“删失（Censored）”数据使得参数估计极其困难。
预算约束：竞价者在整个时间跨度 $T$ 内必须遵守总预算 $B$ 的限制，不能无限制地参与高成本拍卖。

目标：
设计一个在线算法，在未知 $\alpha$ 和 $G$ 的情况下，通过不断学习，最大化总期望收益，同时满足预算约束。性能指标为后悔值（Regret），即最优策略收益与算法实际收益之差。

2. 方法论 (Methodology)

为了解决上述挑战，作者提出了一套结合鲁棒回归估计与**对偶更新（Dual Update）**的算法框架。

2.1 核心难点：参数估计

由于单侧反馈，传统的回归方法（如最小二乘法）失效，因为观测到的 $d_t$ 是有偏的（只观测到较大的值，或者完全观测不到）。

创新点：作者提出了一种基于**条件分位数不变性（Conditional Quantile Invariance）**的鲁棒回归方法（Algorithm 1）。
原理：
- 利用残差 $R_i(\alpha) = d_i - \alpha x_i$ 。
- 将样本根据上下文 $x_t$ 的中位数分为两组。
- 在特定分位数水平 $p$ 下，如果 $\alpha$ 估计正确，两组残差的分位数差值应趋近于 0。
- 通过最小化两组条件分位数的差值 $|q_1(\alpha) - q_2(\alpha)|$ 来估计 $\alpha$ 。
- 鲁棒性：该方法将未观测到的（输掉的）数据视为 $-\infty$ ，从而在计算分位数时自动忽略这些删失数据，仅利用可观测的“输掉”数据中的有效部分进行估计。

2.2 算法设计 (Algorithm 2)

算法采用**分阶段（Phase-based）**学习策略，结合在线梯度下降（Online Gradient Descent）处理预算约束：

探索阶段（Exploration）：
- 初始阶段（ $T_0$ ）：以 $b_t=0$ 出价，收集数据以获取 $\alpha$ 的初步估计。
- 后续阶段：将时间划分为多个阶段 $A_i$ 和 $B_i$ 。
参数更新：
- 在 $A_i$ 阶段：利用该阶段收集的“输掉”数据，使用上述分位数估计器更新 $\alpha$ 的估计值 $\hat{\alpha}_i$ 。
- 在 $B_i$ 阶段：利用更新后的 $\hat{\alpha}_i$ 和观测数据，估计收益函数 $r(v, b)$ 和成本函数 $c(v, b)$ 。
竞价策略：
- 引入拉格朗日乘子 $\lambda_t$ 来松弛预算约束。
- 在每一轮，计算缩放后的价值 $v_t / (1+\lambda_t)$ 。
- 在离散化的出价集合中，选择对应于该缩放价值的最小可行出价（利用最优出价随价值单调递增的性质进行剪枝，缩小搜索空间）。
- 根据实际支出更新对偶变量 $\lambda_t$ （在线梯度下降）。

2.3 多维扩展 (Multi-dimensional Extension)

论文进一步将方法扩展到多维上下文（ $x_t \in \mathbb{R}^d$ ）。通过分量式估计（Component-wise Estimation）（Algorithm 3），将多维问题分解为 $d$ 个一维问题分别求解，保持了算法的效率和理论保证。

3. 主要贡献 (Key Contributions)

首个综合框架：这是第一篇同时处理预算约束、上下文竞争者和单侧信息反馈的重复一价拍卖学习问题。
去除了分布假设：不同于以往假设噪声分布 $G$ 已知的研究，本文在 $\alpha$ 和 $G$ 均未知的情况下实现了最优后悔界。
新型估计技术：提出了基于条件分位数不变性的鲁棒回归方法，有效解决了由竞价策略导致的非随机删失数据（Bid-dependent Censoring）估计难题。
理论最优性：证明了算法的后悔值为 $\tilde{O}(\sqrt{T})$ ，这在单侧反馈设置下是阶最优的（Order-optimal）。

4. 理论结果 (Results)

单维情况（Theorem 2）：
在假设 1-4（超线性增长、Lipschitz 连续性、有界性、可识别性）下，算法 2 的累积后悔值满足：
$\text{Regret}(\pi) \leq \tilde{O}(\sqrt{T})$
该结果以高概率成立，且对数因子 $\ln T$ 被包含在 $\tilde{O}$ 中。
多维情况（Theorem 3）：
在 $d$ 维上下文设置下，算法 4 的后悔值为：
$\text{Regret}(\pi) = \tilde{O}(\sqrt{dT})$
这表明算法在维度增加时具有良好的扩展性。
估计误差：
提出的分位数估计器（Algorithm 1）的参数估计误差为 $\tilde{O}(1/\sqrt{n})$ ，这与标准回归在完整数据下的收敛速度一致，证明了在删失数据下依然能高效学习。

5. 数值实验 (Numerical Experiments)

设置：时间跨度 $T=5000$ ，预算 $B=500$ 。竞争对手出价遵循线性模型 $d_t = 0.8 x_t + z_t$ 。
噪声分布：测试了正态分布、对数正态分布和均匀分布三种噪声，验证算法的鲁棒性。
对比：将提出的上下文算法（Alg1）与非上下文算法（Alg2，即 Wang et al. 2023 的算法）进行对比。
结果：
- 如图 1 所示，提出的算法在平均奖励（Average Reward）上显著优于非上下文算法。
- 随着时间推移，Alg1 的后悔值增长更慢，证明了利用上下文信息（Contextual Information）对于优化竞价策略至关重要。

6. 意义与总结 (Significance)

理论意义：填补了在线学习在“一价拍卖 + 预算 + 上下文 + 单侧反馈”这一复杂组合下的理论空白。证明了即使在信息极度受限（仅知道输赢和输时的对手出价）且数据存在严重删失的情况下，依然可以实现最优的收敛速度。
实际应用：直接服务于现代数字广告生态系统（如 Google Ad Manager, OpenX 等），这些平台已全面转向一价拍卖并提供有限的透明度。算法帮助广告主在预算有限的前提下，更智能地应对动态变化的竞争环境。
方法论推广：提出的基于分位数不变性的鲁棒估计方法，不仅适用于拍卖，也可能推广到其他存在删失数据（Censored Data）和选择偏差（Selection Bias）的在线决策问题中。

总结：该论文通过巧妙的统计估计创新（分位数不变性）和标准的在线优化技术（对偶梯度下降）的结合，成功解决了一个极具挑战性的在线拍卖学习问题，为现代数字广告竞价提供了坚实的理论基础和高效的算法工具。