7.6.2 上下文动态定价问题
在传统的动态定价问题中，我们一般假定买家对物品的估值服从一个概率分布。然而，在某些场景下，买家对物品的估值也可能与某些特征有关，即，𝑣𝑡 = 𝑤 · 𝑥𝑡 + 𝜃0。其中，𝑥𝑡是特征，𝜃0是噪声。这类问题也被称为上下文动态定价问题。针对在这类重复拍卖中卖家的最大化收益的问题，有大量研究提出了不同的算法，这些算法通常是统计估计过程和在线学习技术的组合。 Kareem Amin, Afshin Rostamizadeh 和Umar Syed 第一次考虑了重复的上下文拍卖问题[8] 。他们分别考虑了在重复的上下文拍卖中诚实的买家和盈余最大化的
买家这两种情况。前者是只聚焦于当前轮次的收益，而后者可能放弃短期盈余，通过一个策略性的出价来诱导卖家的算法在未来设定更低的保留价格以获得长期收益。针对这两种买家，作者提出了一种 LEAP 算法， 并分别给出了针对不同买家这个算法的界。这个算法把卖家的策略分成了两个阶段。在第一个阶段，卖家在买家对物品估值的分布的支撑内随机报价，根据买家是否购买物品来估计𝑤。在第二个阶段， 卖家根据第一个
阶段估计的𝑤来确定保留价。随后， 对于诚实的买家， 作者证
2
明了这个算法的遗憾界是𝑂(𝑇3 √𝑙𝑜𝑔 (𝑇 𝑙𝑜𝑔 (𝑇)))。对于盈余
最大化的买方，作者对 LEAP 算法进行了微调，并证明了该算
2
法能获得次线性𝑂̃(𝑇3)的遗憾。这也是在上下文环境下第一个
2
获得𝑂̃(𝑇3)的遗憾的算法。但这个研究并没有针对噪声𝜃0进行建
模，后续的许多研究开始针对𝜃0进行建模以获得更好的遗憾界。
Javanmard 和 Nazerzadeh 考虑了一个保留价定价问题[9] 。同样是与上一篇研究相同的场景。在一个只有一个买家和一个卖家的重复的拍卖中，卖家每一轮给买家设置一个保留价，买家决定是否购买物品。如果购买，则需要支付保留价。买家对物品的估值𝑣𝑡 = 𝑤 · 𝑥𝑡 + 𝜃0。在这个模型下，卖家的预期收入表示为
𝑝 × 𝑃(𝑣𝑡 ≥ 𝑝) = 𝑝(1 − 𝐹(𝑝 − 𝑤𝑡 ⋅ 𝑥𝑡))，其中𝑝表示卖家设置的保
留价， 𝐹(𝑝 − 𝜃0 ⋅ 𝑥𝑡)则表示买家对物品的估值小于卖家设置的保留价的概率。卖家想要确定最优的保留价只需要最大化预期收入。为此，作者提出了一个基于正则极大似然估计的最大化卖家收入的算法—— RMLP。该算法与 Kareem Amin, Afshin Rostamizadeh 和 Umar Syed 所提出的算法类似，依然是分为两个阶段。在第一个阶段，卖家随机报价并利用正则极大似然估计来估计𝑤.第二个阶段，根据估计出来的𝑤，卖家设置保留价。与 LEAP 算法不同的是，RMLP 将 T 轮分成了 K 个阶段，在每个阶段分别运行上述
两个过程。RMLP 算法假设市场噪声分布是已知的，并基于该知识形成对数似然函数。随后，对于一个事先知道选择模型参数的透视者，作者分析了 RMLP 政策的遗憾，并证明了它达到了𝑂(𝑠0𝑙𝑜𝑔𝑑 · 𝑙𝑜𝑔𝑇)的遗憾。其中，𝑠0表示𝑤的非零坐标数，𝑑表示𝑥_𝑡的维数。值得注意的是，这个模型需要假设了解随机噪音的分布，这在某些实际生活中的场景下是难以实现的。为此，Yiyun Luo, Will Wei Sun 和 Yufeng Liu提出了一个DIP 模型来解决这个问题[10] 。他们考虑了一个重复拍卖的模型。在 Javanmard 和 Nazerzadeh 提出的模型的基础上，作者进一步假设卖家不知道随机噪声的概率分布。与 Javanmard 和 Nazerzadeh 的模型相似， 作者依然是通过最大化𝑝(1 − 𝐹(𝑝 −
𝑤𝑡 ⋅ 𝑥𝑡))来获得最优的保留价。但是，在这个模型里面，作者是将买家能否获得产品看作了一个二元分类问题， 即𝑦𝑡 = 1𝑣𝑡≥ 𝑝𝑡。在在线学习中，总时间跨度𝑇通常是未知的。为了解决这个问题，作者采用了在线学习和多臂赌博机算法中广泛使用的加倍技巧，将时间跨度切割成若干阶段。从第二个阶段开始，
作者将下一阶段的长度设定为当前阶段的两倍，直到重复拍卖结束。在每个阶段，卖家运行两个算法。第一个算法是使用逻辑回归来估计𝑤的值。第二个阶段是使用改进的 UCB 算法来确
定当前阶段的保留价。最后， 作者证明了该算法的遗憾界是
2
1
𝑂𝑑 (𝑇3 + ||𝜃 − 𝜃0|| 𝑇)。在此之后，Jianqing Fan, Yongyi Guo 和
Mengxin Yu 引入了非参数方法来解决上下文重复拍卖的问题
[11] 。他们的模型与 Yiyun Luo, Will Wei Sun 和 Yufeng Liu 的模型相同，依然是考虑了线性函数的估值、未知的随机噪声的概率分布、最大化𝑝(1 − 𝐹(𝑝 − 𝑤𝑡 ⋅ 𝑥𝑡))来获得最优的保留价𝑝、使用在线学习和多臂赌博机算法中广泛使用的加倍技巧来划分总时间跨度和先估计 w 后根据 w 设置保留价。与 Yiyun Luo 等人所使用的逻辑回归的技术不同的是，Fan Jianqing 等人直接使用非参
数统计中常用的 Nadaraya-Watson 核回归方法给出了𝜃0的累积分布函数 F 和 F 的一阶导数𝐹′ 的估计。 然后， 再通过最 大 化
𝑝(1 − 𝐹(𝑝 − 𝑤𝑡 ⋅ 𝑥𝑡))来估计𝑤。同样，作者给出了这个算法的
2𝑚+1
遗憾界𝑂̃((𝑇𝑑)4𝑚−1)。这样做与 Javanmard 等人以及 Yiyun Luo 所
提出的方法相比，能用更少的假设来实现更好的遗憾界。与其他非参数方法的相比，这个方法能够很好的适用当维数𝑑很大的时候的场景。与一些基于bandit 的算法相比，这个的算法也很容易实现。