基于多搖臂賭博機的產品定價算法

畢文杰，郭樂薇

中南大學 商學院，長沙410083

據Internet Retailer的數據顯示，在線零售商的規模2018年增至18.84萬億美元，相比去年增長3.3%，而實體零售商的規模僅增長了1.0%。2018年在線零售份額占全球零售總額的15.2%，兩年內提高了34.5%，貢獻了零售增長總額的3/4。與傳統零售商相比，在線零售商實時觀測到消費者的購買決策并能以微不足道的成本動態調整價格。在線零售商同時銷售多種產品，并不確切知道產品的需求函數，因此需要在不完全需求信息下決定大量產品的實時價格[1]。本文研究產品需求分布函數也未知的情形，目標是最大化收益同時也是最小化后悔值[2]。

現有的不完全需求信息下的產品定價方法主要分為兩類：參數方法和非參數方法[3]。參數方法一般假設需求分布函數已知但具體參數值未知[4]。如Chen等人[5]假設產品的需求分布函數來自一個參數值未知的分布族，并在有限的價格變動次數約束下提出了相應的定價算法。非參數方法研究的是產品的需求分布函數完全未知的情形。Ferreira等人[6]研究了在線零售商如何利用歷史銷售數據優化產品定價的問題，建立了非參數結構需求預測模型，同時設計了線性規劃約束算法來獲取最優定價。Cheung等人[7]利用歷史交易數據生成一組需求函數作為其所提出的定價算法的輸入，在有限次價格變動的約束下進行價格實驗以最大化收益，在電商平臺Groupon上的現場實驗結果證明了該定價算法的有效性。

參數方法的局限性在于假定了未知參數的先驗概率分布，后續根據貝葉斯法則更新未知參數的值都與此概率分布有關，而事先給定的未知參數的概率分布不一定符合真實的情況。非參數方法中大多數文獻是先進行需求學習后進行定價優化[8-11]，本文將兩者同時進行來研究產品需求分布函數完全未知情形下的單產品定價問題。同時進行需求學習和定價優化的關鍵在于均衡“探索”與“利用”之間的關系，這也是多搖臂賭博機（Multi-Armed Bandit，MAB）問題的關鍵所在。

MAB問題可以形象地看作是賭場中有一臺多個手柄的賭博機，每個手柄有不同的中獎概率，玩家需要在一定時期內多次選擇拉哪個手柄，且根據輸贏的情況來估計手柄的性能，用來決定下一次選擇拉的手柄，目的是最大化贏錢的總數[12]。MAB模型的建立是為了找到均衡探索與利用的決策方法。MAB模型缺乏先驗知識，只依賴于決策體與環境交互得到的有限反饋。同樣在線零售商不知道產品的需求分布函數，只能通過銷售結果來推測需求信息。在線零售商需要權衡即時收益與長期收益的關系，這與MAB問題中探索與利用之間的平衡目標一致。探索與利用的權衡在MAB問題中得到了廣泛的研究[13]，置信區間上界法（Upper Confidence Bound，UCB）是解決此問題的經典算法，因其有較強的理論支撐而受到學者的認可。Auer等人[14]最早提出了UCB1算法，并對其后悔值進行了分析。UCB算法定義不同的置信上界指標從而產生了一系列的衍生算法[12]。

在動態定價的文獻中，MAB模型通常被應用到標價（posted price）問題中，此種情形下買家選擇接受或者放棄賣家的報價。Singla等人[15]利用采購拍賣與MAB問題之間的聯系，提出了一種預算可行，激勵相容的標價機制。Amin等人[16]考慮了一個賣家反復與有著策略行為的買家進行交互的情形，引入策略后悔值的定義，并給出了相應的定價算法。Trovo等人[17]對UCB1算法的上界進行了改進，提出了UCB1-O和UCB1-P定價算法。在此基礎上，針對需求分布未知但發生改變情形下的單產品定價問題，Trovo等人[18]結合滑動窗口法提出了SW-UCB-M定價算法。Xu等人[19]將UCB1算法應用到隱私數據的定價問題中，結合上下文信息提出了VarLinUCB定價算法。Misra等人[20]在UCB1算法的基礎上加入消費者類別部分識別信息提出了UCB-PIUntuned定價算法。

大多數不完全需求信息下的產品定價研究采用的都是參數方法[21]，知道需求函數的形式便于進行理論分析，但在實踐中決策者往往不具備這樣的信息。Besbes等人[8]表明錯誤地指定需求函數的形式會導致獲得的收益遠遠偏離于最大值。在這種情形下，非參數方法是較優的選擇。非參數方法的難點在于其可操作性和有效性。已有的采用非參數方法的研究一般是以先學習再利用的方式，也有部分學者在MAB問題背景下對此進行研究，采取邊學習邊利用的方式。在收益管理文獻中，對需求的最基本的假設有產品需求隨價格遞減[22]，因此在定價問題中采用UCB1算法來定價其置信上界指標有很大的改進空間。本文利用需求曲線的單調遞減性來提升UCB1算法在定價場景中的性能，并結合消費者的類別信息對消費者的保留價格進行分析，進而得到消費者購買概率，然后將不完全需求信息下的產品定價問題建模為MAB模型，改進置信上界指標，并給出定價策略，為在線零售商的定價問題提供解決方案。

1 不完全需求信息下定價模型的建立

1.1 問題描述

假設在線零售商銷售一款新的數字產品，沒有任何此產品的歷史銷售數據可供統計分析。在線零售商每期從K個價格中選擇一個價格對產品定價，目標是最大化收益。同時，將產品的成本歸一化為零。市場上消費者的總量是有限的，且對產品的偏好存在差異，當消費者的保留價格低于產品的價格時才會選擇購買產品。消費者做出購買決定后即刻退出市場，不考慮消費者的策略行為。在線零售商可以觀測到消費者的特征信息，如人口統計信息和歷史購買行為，并依此將消費者劃分為若干個類別。同一類別消費者具有相似的偏好，不同類別消費者的偏好相互獨立。在線零售商知曉前來購物的消費者所屬的類別和各個類別消費者數量占消費者總量的比例，但不知道各個類別消費者的偏好取值。

1.2 模型建立

1.2.1 參數說明及假設

本文的參數說明及表示如下：k表示價格序號，k∈{1,2,…,K}；i表示消費者序號，i∈{1,2,…,T}；s表示消費者所屬類別的序號，s∈{1,2,…,S}；t表示銷售期序號，t∈{1,2,…,T}；{p1,p2,…,pK}表示可選的價格集合，其中p1

在實際的定價場景中，消費者對產品的保留價格一般是未知的。不同的消費者對產品的偏好不同，故其保留價格不同。消費者的偏好在短期內不會發生改變，故價格越高愿意購買產品的消費者數量越少，即產品需求率越低。在線零售商擁有傳統零售商所不具備的優勢，可根據消費者的人口統計信息和購買記錄來對消費者進行分類，如谷歌向其廣告商提供超過1 000個的細分市場[20]。針對上述具體情況，建立如下相關假設：假設產品的需求函數是常規的（與Gallego等人[22]的假設類似），當價格p1λ2>…>λK，且產品需求率在整個銷售過程中不發生改變；在線零售商將消費者劃分為若干個類別，s類別消費者i對產品的保留價格為vis∈[vs-δs,vs+δs],?s，在線零售商不知道vs和δs的真實取值；產品對消費者i的效用為ui=vi-p，當ui≥0時，消費者購買一單位產品；市場上消費者的數量有限，每個銷售期到達一位消費者，消費者做出購買決策后退出市場。

1.2.2 消費者保留價格分析

根據問題的描述可知，在線零售商在定價的過程中可以逐步學習到每個類別消費者保留價格的取值范圍。如果一個消費者愿意以價格p1購買產品，那么他將愿意以價格pk購買產品，pk≤p1；如果一個消費者不愿意以價格p2購買產品，那么他將不愿意以價格pk購買產品，pk≥p2。

定義消費者保留價格的集合為Θ:={θ1,θ2,…,θK}，θk滿足θk-pk≥0，θk-pk+1<0。s類別消費者在價格為pk時的產品需求率λk,s存在以下三種情形：

（1）λk,s=0，表明s類別消費者的保留價格vis屬于集合{θ1,θ2,…,θk-1}，當價格為pk時，s類別消費者不會購買產品。

（2）λk,s=1，表明s類別消費者的保留價格vis屬于集合{θk,…,θK}，當價格為pk時，s類別消費者肯定會購買產品。

（3）λk,s∈(0,1)，表明s類別消費者的保留價格vis屬于集合{θ1,θ2,…,θK}，當價格為pk時，部分s類別消費者購買產品，部分s類別消費者不會購買產品。

在線零售商可識別出消費者所屬的類別，因此在定價的過程中可以估計s類別消費者保留價格vis的取值范圍。假設在線零售商可選的價格為{1,2,…,6}，在交易的過程中得到A類別消費者的以下購買信息：

（1）當p≤1時，所有消費者購買產品。

（2）當p≤2時，所有消費者購買產品。

（3）當p≥3時，部分消費者購買產品。

（4）當p≥4時，部分消費者購買產品。

（5）當p≥5時，所有消費者都不購買產品。

（6）當p≥6時，所有消費者都不購買產品。

則根據以上購買記錄可得到A類別消費者保留價格的取值范圍：viA∈[2,5]。

在線零售商在t期交易結束后得到各類別消費者保留價格波動估計值的集合為：。最大的保留價格波動估計值為：

前文對δs做出了保守的估計：所有類別消費者保留價格的波動都取值為，故有。則δ)=1。Handel等人[23]證實了對真實的δ值提供了可靠的估計，且消費者的數量越多，得到的δ估計值越準確，成立的前提是價格要有足夠多次數的變化。

1.2.3 消費者購買概率

由于每期僅到達一位消費者且消費者最多購買一單位產品，因此產品的需求率與消費者購買概率相等。對于每一個價格pk，產品的需求率為所有類別消費者群體中vis≥pk的消費者數量總和占總消費者數量的比率，則其購買概率為：

其中，Fs(pk)表示s類別消費者保留價格的累計分布函數，在線零售商并不知道Fs(pk)的真實形式，但可以從上節對各類別消費者保留價格的分析來推斷Fs(pk)的取值。當時，有；當時，有；當，有。

假設市場上共有A、B兩類消費者，ψA=0.4，ψB=0.6；可選的價格集合為{1,2,…,6}，t期時得到的消費者保留價格的取值范圍為viA∈[2,4]，viB∈[3,5]。則分析得到各個價格購買概率的取值范圍為：

（1）當p≤2時，A、B兩個類別的消費者都會購買產品，因此，其中k≤2。

（2）當p∈(2,3]時，A類別消費者可能會購買產品，所有B類別消費者會購買產品，因此，其中2

（3）當p∈(3,4]時，A、B兩個類別的消費者可能會購買或不購買產品，因此，其中3

（4）當p∈(4,5]時，A類別消費者肯定不會購買產品，B類別消費者可能會購買產品，因此，其中4

（5）當p>6時，A、B兩個類別的消費者都不會購買產品，因此，其中k>5。

則有價格為pk時產品購買概率估計值的取值范圍為，其中：

價格為pk時產品的收益率：πk=pkλk，相應的產品收益率估計值的取值范圍為，其中：

2 基于UCB1的定價算法

2.1 UCB1算法

假設一個老虎機共有K個手柄，每次拉手柄給與的獎勵用xk,Nk,t表示，取值為0或者1，其中k∈{1,2,…,K}，Nk,t表示t期時拉動手柄k的總次數，為t期時手柄k的樣本平均獎勵。各個手柄的平均獎勵相互獨立，手柄的平均獎勵等于中獎概率，屬于[0,1]。玩家每期拉動一次手柄，總時隙為T。則UCB1算法[9]的具體步驟如下：

步驟1初始化K、T，令t=1，Nk,t=0。

步驟2選擇第t個手柄，記錄下觀測值xt,1，令Nt,t=1。

步驟3令t←t+1，若t≤K，轉到步驟2；否則轉到步驟4。

步驟4計算，選擇第個手柄，記錄下觀測到的值，令。

步驟5令t←t+1，若t≤T，轉到步驟4；否則算法結束。

2.2 定價策略

由上節可知t期時價格為pk時的產品收益率估計值的取值范圍為。假設有兩個價格p1、p2，當的上界小于的下界時，則沒有再定價格p1的必要。令lt、mt分別為t期時滿足的最小和最大價格序號，在線零售商基于歷史交易記錄ht-1={p1,X1,…,pt,Xt-1}根據策略Ψ從{plt,…,pmt}中選擇一個價格對產品進行定價pk=Ψ(ht-1)。到達市場的消費者觀察到此時的價格pk后做出購買決策，并得到價格為pk時交易結果Xk,Nk,t的一個觀測值xk,Nk,t，計算得到價格為pk時的購買概率估計值：

定理1給定l≤j≤k≤m，令其中，則有λjk≥λk。

證明由定義可知：，則λjk為λj,…,λk購買概率的凸組合。價格pj≤pk，因此產品需求率λj≥λk，由凸集的性質易知λjk≥λk。

t期時λjk的估計值：，其中Njk,t=，根據霍夫丁不等式[24]有：

由上述分析得到t期時在線零售商的定價策略，其中為：

2.3 算法設計

建立了在線零售商的定價模型后，進一步將此問題建模為MAB模型。待選的價格為離散的區間{plt,…,pmt}，價格視作MAB問題中的手柄。當t≤K時，選擇價格pt作為當期的定價，當t≥K+1時，依據策略Ψ來對產品定價，每期交易結束后知曉當期銷售出的產品數量，即MAB模型中的獎勵值。

在MAB模型中，期望累計后悔值用來衡量算法的性能，即實際選取的手柄與一直選擇最優手柄獲得的累計收益差值的期望，表示由于沒有選取最優手柄所造成的損失。MAB模型的目標為最小化累計后悔值，即相當于最大化累計收益值。在不完全需求信息下的定價問題中，t期時的后悔值為：

本文提出包含消費者保留價格分析和利用需求曲線單調性的UCB1-PI-M定價算法，具體算法步驟如下：

步驟1初始化可選的價格集合{p1,p2,…,pK}，消費者類別S，各類別消費者群體占總體的比例ψs，銷售期T，令t=1，，Nk,t=0。

步驟2將產品定價為pt，記錄下觀測值xt,1，，，令Nt,t=1。

步驟3令t←t+1，若t≤K，轉到步驟2；否則轉到步驟4。

步驟4根據式（1）～（10）計算與的取值，令plt與pmt分別為滿足的最小價格和最大價格。

步驟5根據式（11）～（13）計算得到的值，令。

步驟6將產品定價為，記錄下觀測值，，令。

步驟7令t←t+1，若t≤T，轉到步驟4；否則算法結束。

分析UCB1-PI-M定價算法的理論性能，重點在于式（16）中的期望累計后悔值的收斂速率?？紤]不存在消費者類別信息的情形，每期可選的價格集合為{p1,p2,…,pK}，Trovo等人[18]分析了此種情形下的期望累計后悔值。本文將消費者類別信息考慮進來后，每期可選的價格集合{plt,…,pmt}是價格集合{p1,p2,…,pK}的子集，故小于Trovo等人[18]提出的UCB1-M定價算法的期望累計后悔值。由Trovo等人[18]提出的定理1得到UCB1-PI-M定價算法的期望累計后悔值：

其中，Δk=pk*λk*-pkλk，?k∈{1,2,…,K}。式（17）保證了UCB1-PI-M定價算法可以速率O(logT)收斂到最優價格，對比Misra等人[20]對UCB-PI-Untuned定價算法后悔值的分析，可知加入消費者類別信息后算法的時間復雜度并沒有變化。

3 仿真實驗

為模擬在線零售商的定價場景，首先需要生成每個消費者的保留價格。本文采用Misra等人[20]同樣的數據生成方式。假設市場上的消費者類別總數S=1 000，各個類別消費者占總體消費者的比例均為，消費者保留價格的中值vs服從某一分布，考慮vs服從以下四種分布的情形：

（1）vs服從右偏貝塔分布：vs～β(2,9)。

（2）vs服從對稱貝塔分布：vs～β(2,2)。

（3）vs服從左偏貝塔分布：vs～β(9,2)。

（4）vs服從雙峰貝塔分布：vs～β(0.2,0.3)。

上述的參數設置是為了模擬真實世界中一系列不同的消費者保留價格分布，從而得到不同的需求曲線和利潤曲線。前三個分布都是單峰的，最后一個分布是雙峰的。本文將各個類別消費者保留價格的波動取值為δ=0.1，設置s類別消費者的保留價格vis服從[vs-0.1,vs+0.1]上的均勻分布。在線零售商可選的價格集合為{pk|pk=0.01k,k=1,2,…,K}，其中K=100。設置消費者總的數量即銷售時長為T=200 000。

為了評估UCB1-PI-M定價算法的性能，本文給出Auer等人[14]提出的UCB1算法和Misra等人[20]提出的UCB-PI-Untuned定價算法和Trovo等人[18]提出的UCB1-M定價算法作為參照。圖1顯示了當消費者保留價格中值服從β(2,9)分布時UCB1算法的價格取值情況，可以明顯看出UCB1算法不收斂于最優價格。UCB-PI-Untuned定價算法和UCB1-PI-M定價算法由于利用消費者類別信息估計了價格對應的需求率從而隨著時間的推移縮小了可選的價格集合。圖2顯示了UCB1-PI-M定價算法的價格取值情況。

圖1 vs～β(2,9)時UCB1算法的價格取值

圖2 vs～β(2,9)時UCB1-PI-M定價算法的價格取值

圖3為UCB1-PI-M定價算法當銷售期分別為0，100，1 000，5 000（陰影顏色由淺變深）時需求學習的情況，紅色虛線代表真實的需求，陰影的上下邊界為價格對應的需求上下界，可以看出UCB1-PI-M定價算法中需求率估計值的取值范圍隨時間的增大而變窄，當銷售期為5 000時需求率的估計值已經十分逼近真實需求了。

圖3 vs～β(2,9)時UCB1-PI-M定價算法的需求估計值

圖4 vs～β(2,9)時各算法的收益占事后最優收益的比值

圖5 vs～β(2,9)時各個算法的后悔值

為了進一步分析UCB1-PI-M定價算法的性能，本文計算了在線零售商在定價過程中的獲得的累計總收益和產生的累計后悔值。從圖4可知UCB1-M定價算法，UCB-PI-Untuned定價算法和UCB1-PI-M定價算法的收益隨著銷售期的增大占事后最優收益的百分比逐漸收斂到1。從收斂速度來看，本文提出的UCB1-PI-M定價算法收斂速度最快，且獲得了最高的累計收益。從圖5各個算法的后悔值來看，UCB1-PI-M定價算法的后悔值曲線最為收斂，后悔值隨時間增長得最為緩慢。同時利用需求曲線的單調性和消費者類別信息的UCB1-PI-M定價算法取得了比UCB-PI-Untuned定價算法和UCB1-M定價算法更大的累計總收益和更小的累計后悔值，收斂到最優價格的速度最快，表現出了更好的性能，體現了本文所提出算法的優越性。

接下來在消費者保留價格中值vs分別在[2,2]，[9,2]，[0.2,0.3]上服從貝塔分布的情形下進行仿真實驗。因UCB1算法在定價場景中的性能遠不及于其他算法，故此處只對UCB1-M定價算法、UCB-PI-Untuned定價算法和UCB1-PI-M定價算法同時進行實驗，計算它們產生的累計總收益和后悔值。

從表1各算法的收益值對比和表2各算法的后悔值對比可以看出當S=1 000，δ=0.1時不論消費者保留價格中值vs服從何種類型的貝塔分布，UCB1-PI-M定價算法獲得的累計總收益更大，產生的累計后悔值更小，表現最佳。

表1 S=1 000，δ=0.1時各算法收益值對比%

表2 S=1 000，δ=0.1時各算法后悔值對比

Misra等人[20]將UCB-PI-Untuned定價算法和Dubé等人[25]提出的“先學習再利用”（Learn-then-Earn）的典型方法進行了對比分析。先學習再利用方法將定價過程分為兩個階段，第一個階段為學習期，以相同的概率選擇各個價格來為產品定價；第二個階段為利用期，一直選擇學習期中期望收益最大的價格。學習期占總的銷售期的長度強烈影響到先學習再利用方法的性能，學習期過短會得到次優的價格作為利用期的定價，學習期過長雖然可以找到最優定價卻浪費了定最優價格的機會。最佳的學習期時長受到消費者保留價格和總的銷售期時長的影響，但在線零售商事前并不知道消費者保留價格的概率分布，故也不知道最佳的學習期時長。Dubé等人[25]通過嘗試不同的學習期時長找到了學習期時長的最佳值，Misra等人[20]將最佳學習期時長的先學習再利用方法與UCB-PI-Untuned定價算法進行了對比分析，多次重復實驗的結果表明UCB-PI-Untuned定價算法獲得的累計收益平均值更高，且UCB-PI-Untuned定價算法獲得的累計收益值波動范圍更窄。本文提出的UCB1-PI-M定價算法的性能優于UCB-PI-Untuned定價算法，故其獲得的累計總收益也高于先學習再利用的方法獲得的累計總收益。

為了進一步分析UCB1-PI-M定價算法的優勢，本文考慮不同δ取值的情形?？紤]一種極端情形，消費者僅被分作一類，且消費者保留價格范圍為所有可定的價格區間，則此時UCB-PI-Untuned定價算法退化成UCB1算法，UCB1-PI-M定價算法退化成UCB1-M定價算法。Trovo等人[18]證明了在定價場景中UCB1-M定價算法優于UCB1算法。UCB1-M定價算法和UCB1算法都是使用霍夫丁不等式來分析樣本購買概率的置信區間，且置信水平相同。UCB1-M定價算法利用需求曲線的單調性同時使用其他價格的樣本來計算某個價格對應的購買概率的上界，其樣本數量大于UCB1算法使用的樣本數量，故在相同置信水平下置信區間更窄，即有UCB1-M定價算法提供的上界更緊湊，由此得到的定價策略更優。同一類別消費者保留價格波動越大，UCB-PI-Untuned定價算法的性能越差，而UCB1-PI-M定價算法的性能最差也不會比UCB1-M定價算法差。故利用了需求曲線單調遞減性的UCB1-PI-M定價算法在有消費者類別信息的定價場景中的表現總是優于UCB-PI-Untuned定價算法。

4 結束語

本文在UCB1算法的基礎上，利用消費者的類別信息和需求曲線的單調性優化了在線零售商在不完全需求信息下的產品定價策略。所提出的UCB1-PI-M定價算法能夠在不同的消費者保留價格分布中識別出最優價格，同時受同一類別消費者保留價格的波動影響較小，表現出了比UCB1算法、UCB-PI-Untuned定價算法和UCB1-M定價算法更好的性能，提高了在線零售商的收益。后續的研究可以將庫存限制考慮進來，使之適用于有庫存約束的定價場景。