Revenue Maximization 的 learning curves：為何 PAC 最壞情況不是全部故事

2天前
讀畢需時 6 分鐘

已更新：7小时前

在 auction design 與 pricing 問題入面，機器學習常被用來從歷史 valuation data 學一個能最大化 revenue 的價格。傳統理論多數問：在最壞分佈下，需要幾多 samples 才能保證 revenue 接近最佳？這是 PAC-style 的 distribution-free 問法。

Hanneke、Kalavasis、Moran 與 Velegkas 的 On the Learning Curves of Revenue Maximization（arXiv:2604.26922v1）換了一個角度：如果固定一個 valuation distribution，隨着 sample size 增加，某個 learning algorithm 的 expected revenue gap 會如何下降？換句話說，他們研究的是 revenue maximization 的 learning curves。

這個轉向看似細微，其實很關鍵。PAC framework 看的是所有分佈 learning curves 的 upper envelope；learning-curve framework 則問每一條固定分佈上的曲線本身長甚麼樣。結果顯示，這兩個視角可以得出非常不同的 learnability 圖像。

本文重點

這篇 paper 聚焦最基本的 posted-price setting：一個 seller、一個 buyer、一件 item。Buyer valuation 來自未知分佈 D，seller 只看到 i.i.d. samples，然後要選一個 price p。若 valuation 大於等於 p，交易成功，revenue 是 p；否則 revenue 是 0。

作者的主要貢獻，是近乎完整刻劃這個 setting 下 learning curves 的收斂速率。最驚喜的地方是：某些在 PAC 框架下看似困難的情況，對固定分佈而言可以學得很快；但另一些情況即使最優 revenue 有限，也可能只能任意慢地收斂。

一、PAC 看 upper envelope，learning curve 看固定分佈

對一個 learning algorithm t_n，給定 n 個 samples 後，它輸出一個 price。對固定分佈 D，作者把 learning curve 定義為 expected revenue gap：

epsilon_n(t_n, D) = opt_D - E[Rev_D(t_n)]

其中 opt_D 是該分佈下所有 prices 可達到的最佳 expected revenue。

PAC learning 會要求存在一組 distribution-independent constants，令所有分佈在所有 n 上都被同一條 rate bound 控制。這等於看所有 learning curves 的最壞 upper envelope。

Universal learning rate 則放寬一點：對每個固定分佈 D，可以有自己的 constants，但同一個 algorithm 要對整個分佈類都有效。這保留了「每個分佈都要學到」的要求，但不再要求最壞分佈在每個 sample size 都用同一個 uniform bound 壓住。

這個 quantifier order 的差別，是整篇 paper 的核心。

二、第一個好消息：所有分佈都有 Bayes-consistent learner

作者先證明一個基本正面結果：對所有 R+ 上的 valuation distributions，都存在 Bayes-consistent learning algorithm。

這裏的演算法很直觀。對 sample size n，只在價格區間 [0, log n] 內做 empirical revenue maximization。隨着 n 增加，搜尋區間慢慢擴大；同時又避免一開始被極端 tail sample 誘導到過大的 price。

這個結果說明：即使 valuation distribution 沒有任何 regularity、bounded support 或 MHR 假設，至少在極限上仍然可以把 expected revenue 推向最佳值。若最優 revenue 是無限大，演算法 revenue 亦會趨向無限大。

但這只是 consistency，沒有給出速度。

三、只有 finite optimal revenue 還不夠：可能任意慢

接着作者給出第一個強烈負面結果：如果唯一假設只是 opt_D < infinity，那麼沒有任何 universal rate 可以保證。

更精確地說，對任何 learning algorithm 和任何你指定的收斂 rate，都存在一個固定的 hard distribution，令該 algorithm 的 learning curve 在無限多個 sample sizes 上不會比這個 rate 更快。

這個結果的關鍵在於，hard distribution 的 optimal revenue 是一個 supremum，但不是由任何 finite price 真正達成。直覺上，最佳價格永遠在更遠的 tail；algorithm 看見有限 samples 時，很難知道應該追到多遠。

這提醒我們：在 revenue maximization 中，「最佳 revenue 有限」不等於「最佳 price 存在」。這個細節會徹底改變可學速率。

四、若最優價格存在：接近 1/sqrt(n)

如果排除上述 pathological 情況，假設 optimal revenue 由某個 finite price p*_D 達成，情況就穩定很多。

作者證明，在 arbitrary support 下，optimal universal rate 接近 1/sqrt(n)。更準確地說，任何略慢於 1/sqrt(n) 的 rate 都可達到；而任何比 1/sqrt(n) 快太多的 rate 都不可普遍保證。

上界演算法是 Capped Empirical Revenue Maximization。它不是在所有 observed prices 上無限制 ERM，而是只在 [0, g(n)] 這個隨 n 慢慢增長的區間內最大化 empirical revenue。只要 g(n) 最終超過真正的 optimal price，就能學到；但在早期它又能避免被過大的 tail values 影響。

這個設計與前面的 Bayes-consistent algorithm 一脈相承：探索的 price range 要逐步擴大，但不能一開始毫無節制。

五、bounded support：可快過 1/sqrt(n)

若 valuation distribution 的 support 是 bounded，作者得到更強結果：存在 optimal o(1/sqrt(n)) universal rate。

這裏的意思不是所有分佈共享同一條具體 rate，而是對每個固定 bounded-support distribution，algorithm 可以用某個分佈相關的 rate，比 1/sqrt(n) 更快收斂；同時這個結果在 universal lower-bound 意義下也是 optimal。

有趣的是，在 bounded support setting，普通 Empirical Revenue Maximization（ERM） 是 optimal learner。作者的分析使用較 local 的 concentration argument，而不是只用粗糙的 uniform worst-case bound。

這也說明 learning-curve framework 的好處：它能看見固定分佈附近的局部結構，而不只看最壞 envelope。

六、離散支撐：幾乎 exponential，有限支撐則 exponential

最引人注目的結果出現在 discrete support。

若每個 valuation distribution 的 support 是 closed and discrete，且 optimal revenue 由某個 price 達成，作者證明存在幾乎 exponential 的 universal learning rate：e^{-o(n)}。這比 1/sqrt(n) 快得多，也不是 PAC framework 通常能表現出的現象。

若 support 是 finite，結果更乾淨：optimal universal rate 是真正 exponential，約為 e^{-n} 等級。此時 ERM 也是 optimal。

這與傳統 PAC 下的困難結果形成強烈對比。PAC lower bounds 可以在每個 sample size 換一個兩點分佈作為 hard instance；但對每個固定 finite-support distribution，learning curve 其實可以 exponential decay。困難並不是來自每個固定分佈本身，而是來自 PAC adversary 可以隨 n 改變分佈。

七、ERM 不是萬能：離散無界支撐會失敗

這篇 paper 另一個重要訊息，是普通 ERM 在某些 closed discrete unbounded support 上甚至不是 Bayes-consistent。

作者構造一個分佈，support 類似 {1, 4^k}。真正 optimal monopoly price 是 1，且 revenue 是 1；但極大的 tail values 偶爾會在 sample 中出現兩次，使得 empirical revenue 看起來比 price 1 更好。ERM 會被這些 tail events 反覆誤導，在無限多個 sample sizes 上以常數概率選錯，導致 revenue gap 不收斂到 0。

解法是 structured ERM：它仍然基於 empirical revenue，但加入對小價格的 bias，並讓這個 bias 隨 sample size 逐步減弱。直覺上，它既要防止被罕見 tail 事件騙走，又不能永遠困在低 price。

這是 paper 中很有實務味道的一點：有時候「最大化 empirical objective」太天真，適度 regularization 或 structural bias 是必要的。

八、技術難點：固定一個 hard distribution

在 PAC lower bound 中，常見做法是對每個 n 設計一個 hard distribution D_n。這比較靈活，因為 adversary 可以隨 sample size 改變。

但 learning-curve lower bound 要困難得多：必須找到一個固定分佈 D，讓任何 algorithm 在無限多個 n 上都表現不好。這類結果接近 strong minimax lower bound。

作者為 bounded-support lower bound 建構了 uncountably many hard distributions，可想像成一棵 infinite binary tree。每條 path 對應一個 distribution，algorithm 若想在某些 sample sizes 上學得太快，就等於要猜中 path 往左還是往右延伸；作者再用隨機選 path 與反向 Fatou lemma 的想法，把「每層難猜」轉化成「無限多層都會失敗」。

這部分技術相當重，但高層訊息清楚：universal lower bounds 不是 PAC lower bounds 的簡單改寫，它需要完全不同的 hard-instance 思維。

九、實務含意

這篇 paper 雖然是理論工作，但對資料驅動 pricing 與 auction design 有幾個實務提醒。

第一，平均學習曲線和 worst-case sample complexity 是不同問題。若你面對的是一個固定市場或固定 buyer population，PAC lower bound 可能過於悲觀。

第二，support geometry 很重要。bounded、finite、closed discrete、unbounded tail，對 learning rate 的影響可以非常大。

第三，是否存在真正 optimal price 是關鍵。如果最優 revenue 只是被一串越來越大的價格逼近，學習速度可能任意慢。

第四，ERM 需要小心使用。當 valuation distribution 有無界離散 tail，純粹追逐 empirical revenue 可能被偶然的高價樣本誤導；合適的 truncation、regularization 或 structured ERM 可能更可靠。

十、小結

On the Learning Curves of Revenue Maximization 把 revenue maximization from samples 的評估方式，從 PAC worst-case envelope 推向 per-distribution learning curves。這讓我們看見更細緻的圖像：一般分佈可一致學習但可能任意慢；最優價格存在時接近 1/sqrt(n)；bounded support 更快；discrete / finite support 可接近或達到 exponential；普通 ERM 則在某些離散無界分佈上會失敗。

對做 mechanism design、pricing、ad auctions 或 learning theory 的人來說，這篇文的價值在於提出一個更貼近「固定市場長期學習」的問題框架。它不是取代 PAC，而是補上 PAC 沒有描述好的部分：單一分佈上的 learning curve 到底如何下降。

Reference

Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas. On the Learning Curves of Revenue Maximization. arXiv:2604.26922v1 [cs.LG], 29 Apr 2026. https://arxiv.org/abs/2604.26922
Richard Cole and Tim Roughgarden. The Sample Complexity of Revenue Maximization. STOC 2014.
Nikhil R. Devanur, Zhiyi Huang, et al. Work on sample complexity and revenue maximization for structured valuation distributions, as discussed in the paper.
Luc Devroye, László Györfi, Gábor Lugosi, and related work on universal learning rates and learning curves, as referenced in the paper.