譚友鈺，陳蕾，周明拓，王昆侖，楊旸，張武雄

(1 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050； 2 國網(wǎng)浙江省電力有限公司， 杭州 310007；3 中國科學(xué)院大學(xué)， 北京 100049； 4 上?？萍即髮W(xué)， 上海 201210； 5 上海霧計算實驗室， 上海 201210)

隨著智能物聯(lián)網(wǎng)、5G與人工智能等技術(shù)的興起與發(fā)展，處理海量且多樣性的數(shù)據(jù)、滿足超低的服務(wù)時延需求，成為越來越亟待解決的問題[1]。傳統(tǒng)的基于集中式的云計算架構(gòu)由于終端設(shè)備與云服務(wù)器的遙遠(yuǎn)距離而產(chǎn)生較大時延，已難以滿足時延敏感性服務(wù)的需求；同時，基于集中式的管理也難以支撐海量設(shè)備的接入。在這種情況下，霧計算(fog computing)[2]應(yīng)運而生。霧計算技術(shù)將通信、計算、控制和存儲等能力從云端推向網(wǎng)絡(luò)邊緣(如(小)基站、無線接入點及其他有計算能力的終端設(shè)備)[3]，通過資源共享機制和協(xié)同服務(wù)架構(gòu)幫助資源有限的移動設(shè)備執(zhí)行具有超低延遲限制的計算密集型應(yīng)用程序，從而有效提升用戶體驗或者生產(chǎn)效率，有望成為支撐未來智能物聯(lián)網(wǎng)、5G和人工智能應(yīng)用的關(guān)鍵技術(shù)[4-5]，受到廣泛的關(guān)注與研究。

任務(wù)卸載(task offloading)是霧計算的主要技術(shù)之一，計算資源有限的節(jié)點在難以獨立支持應(yīng)用服務(wù)時，可將計算任務(wù)卸載到網(wǎng)絡(luò)中資源充足的節(jié)點幫助計算。需要進(jìn)行任務(wù)卸載的節(jié)點叫做任務(wù)節(jié)點(task node)，提供計算幫助的節(jié)點叫做幫助節(jié)點(help node)。時延和能耗是任務(wù)卸載過程中兩個重要的指標(biāo)，有大量學(xué)者對其進(jìn)行了研究[2-11]，本文主要考慮時延。

一方面，目前大多數(shù)學(xué)者考慮的都是靜態(tài)網(wǎng)絡(luò)里的任務(wù)卸載，即在任務(wù)卸載過程中，網(wǎng)絡(luò)中的移動設(shè)備處于靜止?fàn)顟B(tài)，且?guī)椭?jié)點所提供的計算資源保持不變[6-7]。在文獻(xiàn)[6]的研究模型里，終端設(shè)備可以通過基站將任務(wù)卸載給附近的云，為多設(shè)備的任務(wù)卸載場景提出一種基于博弈論的任務(wù)卸載算法。Dinh等[7]通過聯(lián)合優(yōu)化任務(wù)分配和節(jié)點的計算頻率，最小化時延和能量總消耗。然而在實際中，任務(wù)節(jié)點和幫助節(jié)點往往都不是靜止的，而是處在移動狀態(tài)，經(jīng)歷著多變的無線信道；并且，幫助節(jié)點可提供的計算資源也可能發(fā)生變化。

另一方面，現(xiàn)有的研究大都假設(shè)系統(tǒng)中的節(jié)點狀態(tài)信息已知，或者這些信息可以實時廣播到網(wǎng)絡(luò)中[8-9]。由于任務(wù)的卸載決策通常需要幫助節(jié)點狀態(tài)相關(guān)信息，比如任務(wù)隊列長度、可共享資源大小等，因此任務(wù)卸載過程本身便可看作典型的隨機決策過程。對此，許多研究工作利用李亞普諾夫優(yōu)化(Lyapunov optimization)等方法解決這種隨機決策問題，從而實現(xiàn)任務(wù)或計算資源的近似最優(yōu)分配[8-9]。不停在網(wǎng)絡(luò)中廣播及監(jiān)聽節(jié)點的狀態(tài)信息會產(chǎn)生大量的能量開銷，影響設(shè)備使用時長，在未來超大規(guī)模體系中，節(jié)點個數(shù)倍數(shù)增加的場景下，這個問題將更加突出。

為減少由于多次溝通信息導(dǎo)致的能量損耗，基于學(xué)習(xí) (learning) 的方法被提出[10]。文獻(xiàn)[10]使用馬爾可夫決策方法動態(tài)地進(jìn)行服務(wù)資源的配置和卸載決策。Tan等[11]為霧計算網(wǎng)絡(luò)設(shè)計基于學(xué)習(xí)的任務(wù)卸載算法，但未建模考慮任務(wù)的排隊情況，此外，該工作也未考慮任務(wù)本身的時延需求，可能過多地導(dǎo)致任務(wù)不滿足時延需求。

在實際情況中，節(jié)點會動態(tài)出入網(wǎng)絡(luò)，幫助節(jié)點可共享的計算資源也會隨情況發(fā)生變化；同時，實時在網(wǎng)絡(luò)中傳輸或廣播節(jié)點狀態(tài)信息又會造成大量的能量開銷。這樣一個最貼近實際需求又有待解決的問題，卻鮮有學(xué)者研究。本文旨在為這樣的動態(tài)霧計算網(wǎng)絡(luò)設(shè)計任務(wù)卸載算法，最優(yōu)化設(shè)備的任務(wù)卸載時延，同時盡量滿足其任務(wù)時延需求，任務(wù)節(jié)點無需實時請求網(wǎng)絡(luò)中幫助節(jié)點的狀態(tài)信息，如隊列信息及計算資源信息等，而是以很小的計算代價根據(jù)自己的歷史卸載經(jīng)驗學(xué)習(xí)和判斷得來。本文動態(tài)霧計算網(wǎng)絡(luò)中的“動態(tài)”有3個含義：1)網(wǎng)絡(luò)中的節(jié)點運動狀態(tài)可變；2)網(wǎng)絡(luò)大小可變：節(jié)點可自由出入網(wǎng)絡(luò)；3)幫助節(jié)點可提供的計算資源可變。

本文首先為穩(wěn)定狀態(tài)下的動態(tài)網(wǎng)絡(luò)提出任務(wù)卸載算法TOD(online learning-based task offloading algorithm for the dynamic fog networks under stationary status)。在穩(wěn)定狀態(tài)里，網(wǎng)絡(luò)中節(jié)點的參數(shù)達(dá)到穩(wěn)定。穩(wěn)定狀態(tài)一般適用于以下場景：節(jié)點靜止或緩慢移動，可自由出入網(wǎng)絡(luò)，幫助節(jié)點可提供穩(wěn)定的計算資源。接著，擴(kuò)展TOD算法到非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下，提出TOD-N算法(online learning-based task offloading algorithm for the dynamic fog networks under non-stationary status)，以動態(tài)追蹤網(wǎng)絡(luò)中變化的最優(yōu)資源和節(jié)點。在非穩(wěn)定環(huán)境中，系統(tǒng)參數(shù)會隨著時間而變化。非穩(wěn)定狀態(tài)可能包含有以下場景：節(jié)點(快速)移動，可自由出入網(wǎng)絡(luò)，信道環(huán)境變化較大，幫助節(jié)點可提供計算資源隨時間改變。然后，針對所提出的兩個算法進(jìn)行詳細(xì)的性能分析，包括算法與理想算法的近似情況、算法復(fù)雜度分析以及存儲空間占用分析等。仿真結(jié)果表明，本文算法所能達(dá)到的卸載時延與理想情況下的最優(yōu)卸載時延十分相近，且任務(wù)卸載服務(wù)的時延滿足率顯著提升；此外，TOD-N算法在非穩(wěn)定的網(wǎng)絡(luò)狀態(tài)下能夠追蹤計算資源與環(huán)境的變化，與貪心 (Greedy) 算法相比，性能顯著提升。

1 系統(tǒng)模型與問題建模

1.1 系統(tǒng)模型與目標(biāo)

本文考慮單對多(單個任務(wù)節(jié)點，多個幫助節(jié)點)任務(wù)卸載，且任務(wù)不可拆分的情況，即一個任務(wù)節(jié)點可從多個幫助節(jié)點中選擇一個來卸載任務(wù)。將時間劃分為若干個時隙，假設(shè)從時隙t=0開始，UE在每個時隙的開始產(chǎn)生一個卸載請求Rt，表示為Rt={xt,Δt}，其中xt為Rt任務(wù)大小，Δt表示任務(wù)Rt可容忍的最大時延。通常，由于返回的結(jié)果很小(幾到幾十個比特)，結(jié)果的返回時延可忽略不計[3]。每當(dāng)有卸載請求時，UE從愿意共享計算資源的候選幫助節(jié)點里選擇一個來完成任務(wù)卸載。將t時隙里UE的候選節(jié)點表示為集合H(t)，H(t)={H1,H2,…,Hh(t)}，其中h(t)=|H(t)|。由于UE不能實時掌握或請求網(wǎng)絡(luò)中幫助節(jié)點的節(jié)點狀態(tài)信息，因此，UE需要根據(jù)自己的歷史卸載數(shù)據(jù)等對當(dāng)前幫助節(jié)點Hk∈H(t)進(jìn)行學(xué)習(xí)，以便找到優(yōu)秀的幫助節(jié)點進(jìn)行任務(wù)卸載。如圖1所示，UE選擇H2卸載任務(wù)Rt。

圖1 t時隙下的動態(tài)霧網(wǎng)絡(luò)圖示Fig.1 Illustration of the dynamic fog network at time t

本文以最小化平均任務(wù)卸載時延、提高任務(wù)卸載成功率為目標(biāo)設(shè)計任務(wù)卸載算法。任務(wù)的卸載時延包含3個部分[3]：傳輸時延、等待時延和計算時延。

(1)

式中rk(t)為UE到Hk的傳輸速率，根據(jù)香農(nóng)公式可得

(2)

(3)

(4)

最終，UE將Rt卸載到Hk的卸載服務(wù)時延可表示為

(5)

令Π表示在從t=1到t=T所有可能的卸載策略，則直到t=T為止，UE的任務(wù)平均卸載時延為

(6)

1.2 將原模型建模為MAB問題

(7)

與傳統(tǒng)的MAB問題相比，本文的研究問題有如下挑戰(zhàn)：1) 傳統(tǒng)的MAB問題動作空間恒定，本文由于節(jié)點移動出入網(wǎng)絡(luò)或是否愿意繼續(xù)共享資源，使問題具有動態(tài)變化的動作空間，更加復(fù)雜。2) 傳統(tǒng)MAB問題中通常系統(tǒng)參數(shù)穩(wěn)定，如某個動作的平均收益穩(wěn)定，本文中節(jié)點的自由移動、信道環(huán)境變化，以及共享計算資源的變化，可能導(dǎo)致系統(tǒng)參數(shù)實時發(fā)生變化。

2 基于UCB的在線任務(wù)卸載算法

本文考慮任務(wù)本身的時延需求，在上節(jié)所述的2個挑戰(zhàn)下，基于UCB(upper confidence bound)[13]提出在線任務(wù)卸載算法解決問題P1。首先提出TOD算法，適用于節(jié)點的參數(shù)穩(wěn)定，處在穩(wěn)定狀態(tài)下的霧計算網(wǎng)絡(luò)。由于幫助節(jié)點可共享的計算資源可能隨著時間發(fā)生變化，節(jié)點的任務(wù)隊列信息也可能會發(fā)生一系列改變，在這種情況下，節(jié)點處理單位任務(wù)的時延會相應(yīng)發(fā)生變化。為應(yīng)對和處理這些情況，將算法TOD進(jìn)行擴(kuò)展，為處在非穩(wěn)定狀態(tài)的霧計算網(wǎng)絡(luò)提出TOD-N算法。值得注意的是，TOD算法與TOD-N算法并不對系統(tǒng)參數(shù)分布做出限制。

2.1 穩(wěn)定網(wǎng)絡(luò)狀態(tài)下的任務(wù)卸載算法

算法1 穩(wěn)定霧計算網(wǎng)絡(luò)狀態(tài)下基于在線學(xué)習(xí)的任務(wù)卸載算法TOD初始化:輸入?yún)?shù)ζ,初始化t=1 WHILEUE有任務(wù)卸載請求 DO更新候選幫助節(jié)點集合H(t)IF ?Hk∈H(t)是未選擇過的幫助節(jié)點 THEN向Hk請求信息Xqk(t), Xek(t)初始化uek=Xek(t), Qk=Xqk(t), Nk(t)=1, Γak(t)=1ELSE?Hk∈H(t),根據(jù)式(8)計算決策索引值u⌒k(t)選擇節(jié)點?(t)=argminHk∈Η(t)u⌒k(t)卸載Rt,收到反饋Xq?(t)(t)與Xe?(t)(t),卸載服務(wù)完成后收到返回結(jié)果?Hk∈H(t),Nk(t)=Nk(t-1)+1,Γak(t)=Γak(t-1)+1t=t+1END IF END WHILE

(8)

(9)

(10)

(11)

2.2 非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下的任務(wù)卸載算法

(12)

(13)

(14)

(15)

(16)

TOD-N算法的偽代碼如算法2所示。

算法2 非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下基于在線學(xué)習(xí)的任務(wù)卸載算法TOD-N初始化:輸入?yún)?shù): ζ, γ, Δmax,初始化t=0 WHILEUE有任務(wù)卸載請求 DO更新候選幫助節(jié)點集合H(t)IF?Hk∈H(t)是未選擇過的幫助節(jié)點 THEN向Hk請求初始信息Xqk(t),Xek(t)初始化uek(t,γ)=Xek(t),Qk(t,γ)=Xqk(t),Nnk(t,γ)=γ,Γnk(t,γ)=γELSE?Hk∈H(t),據(jù)式(12)計算決策索引值u⌒nk(t,γ)選擇節(jié)點?(t)=argminHk∈Η(t)u⌒k(t,γ)卸載Rt,收到即時反饋Xq?(t)(t),Xe?(t)(t),卸載服務(wù)完成后收到返回結(jié)果?Hk∈H(t),Γnk(t,γ)=Γnk(t-1,γ)γ+γ,?Hk∈H(t),根據(jù)式(15)更新Nnk(t,γ)END IF END WHILE

3 算法性能分析

本節(jié)將對TOD算法、TOD-N算法進(jìn)行性能分析，包括算法的最優(yōu)近似情況、算法的計算復(fù)雜度以及內(nèi)存占用情況。

(17)

3.1 算法的Regret分析

3.1.1 TOD算法的Regret分析

令Δmax=maxtΔt，則當(dāng)φ=TOD時,有如下結(jié)論：

結(jié)論1若動態(tài)調(diào)整Δ+和Δ-，使得?t，τ(Rt)=1，則

3.1.2 TOD-N算法的Regret分析

證明見附錄B。

(18)

結(jié)論3當(dāng)φ=TOD-N，存在常數(shù)C′,使得下式成立

(19)

證明見附錄C。

3.2 算法復(fù)雜度及內(nèi)存占用情況分析

(20)

(21)

(22)

4 仿真結(jié)果與分析

本節(jié)對TOD算法以及TOD-N算法進(jìn)行性能仿真驗證。主要考察采用所提出算法后的任務(wù)卸載的時延情況、任務(wù)卸載成功率以及算法的學(xué)習(xí)性能。

4.1 TOD算法仿真結(jié)果

圖2 穩(wěn)定網(wǎng)絡(luò)狀態(tài)下不同算法的任務(wù)卸載成功情況Fig.2 Task offloading success ratios for different algorithms under stationary status

圖2中RR算法為輪詢調(diào)度(round-robin)算法，輪流選擇幫助節(jié)點進(jìn)行任務(wù)卸載。Oracle算法表示理想算法，UE實時地對幫助節(jié)點處的排隊情況、計算資源情況以及信道環(huán)境情況了如指掌，這在實際中是不現(xiàn)實的。當(dāng)調(diào)節(jié)Δ+和Δ-使τ(Rt)始終為1的時候，TOD就變成TOD0算法，注意到此時相當(dāng)于TOD0算法未考慮任務(wù)本身的時延需求。從圖2可以看出，相比RL算法與TOD0算法，TOD算法能夠有效地提升任務(wù)卸載的成功率，所達(dá)到的累計概率和Oracle算法十分接近，且隨著任務(wù)卸載次數(shù)增加，卸載成功率也會越來越靠近理想狀態(tài)下的任務(wù)卸載成功率。

圖3所示為TOD算法在網(wǎng)絡(luò)中有節(jié)點自由出入時的性能表現(xiàn)。時隙長度為20 ms。?t，xt=x，圖3中有兩種輸入任務(wù)大小，分別為x=0.5 Mbit和x=0.8 Mbit。?k,rk=48 Mbit/s。仿真過程中有3個等長時段：T1，T2和T3，長度分別為5 s。節(jié)點在網(wǎng)絡(luò)中的存在情況如表1所示，此時，ue，a和b分別為：ue=[0.08, 0.2, 0.2, 0.4, 0.5, 0.5, 0.7, 0.8]，a=[3.1, 1.6, 0.6, 0.4, 0.25, 0.007, 0.06, 0.015]，b=[2.9, 1.4, 0.4, 0.2, 0.15, 0.005, 0.05, 0.005]。

圖3 TOD算法在穩(wěn)定狀態(tài)下的時延表現(xiàn)Fig.3 Average offloading delays under stationary status by TOD algorithm

表1 TOD算法候選幫助節(jié)點Table 1 Candidate help nodes by TOD algorithm

從圖3可以看出，在網(wǎng)絡(luò)動態(tài)變化后，TOD算法能快速找到新的最優(yōu)幫助節(jié)點，且采用TOD算法的時延與理想算法的時延十分接近。進(jìn)一步對比時段1與時段2發(fā)現(xiàn)，兩種大小的任務(wù)平均時延差距變小，這是因為幫助節(jié)點的隊列長度不同，因此當(dāng)任務(wù)大小不同時，相應(yīng)的最優(yōu)節(jié)點可能不同。

4.2 TOD-N算法仿真結(jié)果

接下來檢驗算法在非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下的表現(xiàn)。仿真過程中共出現(xiàn)過6個幫助節(jié)點，各個幫助節(jié)點可提供的共享計算資源隨時間改變，如圖4(a)所示。時隙長度為20 ms。仿真過程可分為兩個時段：T1和T2，長度各為5 s，各節(jié)點在各時段的存在情況如表2所示。?t，xt=0.6 Mbit。參考文獻(xiàn)[7]，任務(wù)的計算密度設(shè)置為330 Cycls/bit。?k，?t，Qk(t)(單位：Mbit)有：Qk(t)～U(0.25，0.35)，且Δt(單位：s)有：Δt/xt～U(1.3e-6,1.5e-6)，Δ+=6e-6，Δ-=0。此外，為了體現(xiàn)出算法對網(wǎng)絡(luò)中節(jié)點計算資源的學(xué)習(xí)情況，需要盡量減少傳輸試驗帶來的影響，因此假設(shè)?k,rk=72 Mbit/s。本節(jié)將TOD-N算法與Greedy算法和理想Oracle算法進(jìn)行對比。Greedy算法每次決策時均選擇目前的最優(yōu)節(jié)點，Oracle算法則依然實時地對所有幫助節(jié)點的排隊情況、計算資源情況等了如指掌。同時，為進(jìn)一步分析γ參數(shù)對算法性能的影響，本節(jié)給出TOD-N算法在不同γ值下的性能表現(xiàn)。根據(jù)圖4(a)，最優(yōu)節(jié)點和次優(yōu)節(jié)點不可分的時隙個數(shù)在T1和T2時段分別為1和2，根據(jù)式(18)可得，相應(yīng)的參數(shù)γ分別為0.999 5和0.999 3。實驗中另外給出的實驗數(shù)據(jù)值分別為γ=1，0.999，0.99，0.9。TOD-N算法在非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下的性能表現(xiàn)如圖4～圖6所示。

圖4 不同算法對網(wǎng)絡(luò)中最優(yōu)計算資源的追蹤情況Fig.4 Learning performance on computing resource for different algorithms

圖5 不同算法下的卸載時延及學(xué)習(xí)RegretFig.5 Average offloading delays and learning regrets for different algorithms

圖6 非穩(wěn)定網(wǎng)絡(luò)狀態(tài)下不同算法的任務(wù)卸載成功情況Fig.6 Task offloading success ratios for different algorithms under non-stationary status

表2 TOD-N算法候選幫助節(jié)點Table 2 Candidate help nodes by TOD-N algorithm

圖4(b)為TOD-N算法對網(wǎng)絡(luò)中計算資源的學(xué)習(xí)追蹤與利用情況，結(jié)合圖4(a)、4(b)可以看出，當(dāng)γ=0.999 5和0.999 3時，TOD-N算法均能較好地追蹤學(xué)習(xí)到最佳CPU資源，Greedy算法則無法做到。進(jìn)一步地，可發(fā)現(xiàn)，當(dāng)γ=1和0.999時，TOD-N總體表現(xiàn)比前兩個值要遜色一些，但在某些局部時段里表現(xiàn)卻要好一些。例如，在剛開始的一段時間里γ=1要比γ=0.999 3時性能好一些，在最后一段時間里γ=0.999要比γ=0.999 5稍微好一點。這是因為剛開始網(wǎng)絡(luò)狀態(tài)相對較穩(wěn)定，因此γ選擇大一些；在最后一段時間里，網(wǎng)絡(luò)狀態(tài)變化相對較快，因此γ選擇可相對減小一些。以上結(jié)論與3.1.2節(jié)分析的結(jié)論一致。但當(dāng)γ=0.99，甚至γ=0.9，TOD-N算法無法很好地適應(yīng)非穩(wěn)定網(wǎng)絡(luò)狀態(tài)，同時，圖5(b)也同時表明，此時Regret增長很快，算法表現(xiàn)較差。這是因為γ值選擇過小的話，算法基本丟掉了歷史有用的數(shù)據(jù)信息，而過于依賴當(dāng)前的數(shù)據(jù)。根據(jù)以上分析發(fā)現(xiàn)，參數(shù)γ的選擇確實會對TOD-N算法性能造成影響，具體選擇可參考式(18)。但是在實際情況中，很難提前知道網(wǎng)絡(luò)情況，因此很難實時地對γ做出最優(yōu)判斷，但是如圖4～圖6所示，根據(jù)實驗結(jié)果與分析，本文建議選用γ∈(0.99,1)，在這個范圍內(nèi)，均可有較為良好的結(jié)果，具體值可結(jié)合實際情況做出調(diào)整。

圖5(a)表明，當(dāng)合理選擇γ，TOD-N在非穩(wěn)定狀態(tài)下可達(dá)到的時延和理想最優(yōu)時延十分接近，可達(dá)5 ms以內(nèi)，同時從圖6可知，此時任務(wù)卸載成功率也明顯比貪心算法高，且與最優(yōu)成功率之差在1%以內(nèi)。

5 總結(jié)

本文將動態(tài)霧計算網(wǎng)絡(luò)中的任務(wù)卸載問題建模為具有動態(tài)動作空間的MAB問題，并為穩(wěn)定狀態(tài)霧網(wǎng)絡(luò)提出基于在線學(xué)習(xí)的任務(wù)卸載算法TOD，該算法能夠最優(yōu)化平均卸載時延，并提高任務(wù)卸載成功率。再將TOD擴(kuò)展到非穩(wěn)定網(wǎng)絡(luò)狀態(tài)情況，提出TOD-N算法，TOD-N算法能動態(tài)追蹤到網(wǎng)絡(luò)中節(jié)點的計算資源。接著對TOD算法和TOD-N算法進(jìn)行詳細(xì)的性能分析。并同時對TOD-N中的參數(shù)γ進(jìn)行一定討論和實驗。仿真結(jié)果驗證了所提出算法的優(yōu)異性能。未來將進(jìn)一步考慮任務(wù)可拆分以及節(jié)點之間可協(xié)作的場景。

附錄A

根據(jù)式(17)的定義，當(dāng)φ=TOD，RTOD(T)可寫作

當(dāng)單位任務(wù)容忍時延一定時，即?t，Δt/xt=Δ0，令Δ+=Δ0，Δ-=0，則?t，τ(Rt)=1。根據(jù)文獻(xiàn)[11]的定理1以及文獻(xiàn)[15]的引理1可得

顯然Γk≤ts≤T，結(jié)合式(A.1)(A.3)(A.4)則可得到結(jié)論1。

附錄B

式(B.2)中事件{φ(t)=k≠k*(t)}意味著下式成立：

對{φ(t)=k≠k*(t)}有

此時，可得

附錄C

TOD-N在時段ps的學(xué)習(xí)Regret可表示為

則存在C′，使得下式成立：