化學(xué)習(xí)：算法設(shè)計(jì)與理論極限解析)
如果你在讀論文推送時(shí)看到這樣一條標(biāo)題2025_NIPS_Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits——大概率會直接劃過。我第一眼也差不多但在這個(gè)圈子里待久了反而養(yǎng)成了一個(gè)習(xí)慣越是帶這種硬核詞綴的標(biāo)題越要先拆清楚它在說什么因?yàn)樗馕吨粋€(gè)新方向、或者一個(gè)還沒被充分占領(lǐng)的問題。這個(gè)標(biāo)題里三個(gè)關(guān)鍵片段分別是Outcome-Based基于結(jié)果、Online Reinforcement Learning在線強(qiáng)化學(xué)習(xí)、Algorithms and Fundamental Limits算法與理論下界。把它們翻譯成人話就是在只能觀察到最終結(jié)果、而非每一步都有即時(shí)獎勵(lì)的強(qiáng)化學(xué)習(xí)任務(wù)里我們要設(shè)計(jì)算法讓智能體在與環(huán)境交互的過程中不斷學(xué)習(xí)同時(shí)弄清楚這類問題的最優(yōu)效率邊界在哪里。這篇內(nèi)容不會去復(fù)述某個(gè)具體論文的公式細(xì)節(jié)而是分享一套我自己看這類RL理論工作時(shí)用的拆解框架。無論你是正在復(fù)現(xiàn)相關(guān)實(shí)驗(yàn)的研究生還是想了解為什么這類文章越來越重要的工程師讀完應(yīng)該都能建立一張比較完整的地圖。1. 先把標(biāo)題拆開三個(gè)關(guān)鍵詞其實(shí)在回答三個(gè)問題1.1 一個(gè)看起來很勸退的前綴老實(shí)說Outcome-Based Online Reinforcement Learning這個(gè)組合在圈內(nèi)并不是一個(gè)像 off-policy、model-based 那樣統(tǒng)一且公認(rèn)的范式門類。它更多是研究者為了強(qiáng)調(diào)自己問題設(shè)定而拼出來的一個(gè)描述性前綴。也正是因?yàn)闆]有固定模板看到這個(gè)標(biāo)題反而要多問幾句它說的 outcome 到底是什么它限定的 online 又是在什么尺度上的在標(biāo)準(zhǔn)強(qiáng)化學(xué)習(xí)里一個(gè)有監(jiān)督式的學(xué)習(xí)循環(huán)通常是智能體觀察狀態(tài)選擇動作環(huán)境返回下一個(gè)狀態(tài)和獎勵(lì)。獎勵(lì)一旦在每個(gè)時(shí)刻都給出算法的學(xué)習(xí)信號就非常密集。但 Outcome-Based 這個(gè)偏移一開始就把獎勵(lì)壓縮了你只在回合結(jié)束、或者某個(gè)關(guān)鍵節(jié)點(diǎn)到來時(shí)才知道這一整條軌跡到底產(chǎn)出什么結(jié)果。這個(gè)結(jié)果可能是一個(gè)成功/失敗標(biāo)簽可能是最終收益也可能是一段很長的延遲反饋。這種設(shè)計(jì)變化不是文字游戲它會直接影響整個(gè)算法的優(yōu)化目標(biāo)、方差大小、甚至理論分析中要用到的概率工具。我通常把這個(gè)前綴理解為三個(gè)問題第一可觀測信號是什么第二信號之間相隔多長第三最優(yōu)策略的定義是否仍然是最大化長期回報(bào)。把這三個(gè)問題想清楚這個(gè)方向的骨架其實(shí)就出來了。1.2 結(jié)果驅(qū)動不等于每步都給獎勵(lì)很多剛接觸強(qiáng)化學(xué)習(xí)的同學(xué)會下意識覺得RL 本來就靠獎勵(lì)學(xué)習(xí)Outcome-Based 能有多大差別。這里我舉個(gè)最直觀的類比考試只看期末總成績和每次作業(yè)、隨堂測驗(yàn)、課堂表現(xiàn)全部計(jì)入平時(shí)分看起來只是一個(gè)打分方式變化但對你該怎么分配復(fù)習(xí)時(shí)間這件事的影響是天翻地覆的。如果老師每節(jié)課都打分你立刻就能知道哪些知識點(diǎn)掌握得不好下一周就可以針對調(diào)整。但如果只有一張期末試卷你只有等到考完才能發(fā)現(xiàn)自己的薄弱環(huán)節(jié)而且你根本無法確定到底是哪個(gè)章節(jié)、哪種題型拖累了總分。這就是 credit assignment信用分配問題在只有最終結(jié)果的時(shí)候中間每一環(huán)的貢獻(xiàn)都被混在一起算法很難把功勞和責(zé)任準(zhǔn)確地拆給某個(gè)狀態(tài)-動作對。在這種設(shè)定下先前那些建立在每步都有 reward 反饋之上的技巧也會失效比如時(shí)間差分學(xué)習(xí)中的時(shí)序誤差更新就缺少了一個(gè)穩(wěn)定的局部監(jiān)督信號。于是大量方案會退化成蒙特卡洛式的經(jīng)驗(yàn)積累從終局結(jié)果出發(fā)把整條軌跡上的狀態(tài)-動作統(tǒng)一賦上回報(bào)值。理解了這個(gè)關(guān)鍵差異才算真正讀懂了標(biāo)題里的 Outcome-Based。1.3 一個(gè)Online就讓它和離線學(xué)習(xí)區(qū)分開標(biāo)題里另一個(gè)容易忽略的詞是 Online。它意味著智能體必須一邊和環(huán)境交互、一邊更新策略而不是拿到一批離線數(shù)據(jù)之后慢慢訓(xùn)練。這個(gè)區(qū)別遠(yuǎn)比表面上看起來更嚴(yán)重。在線學(xué)習(xí)會帶來兩個(gè)離線式方法不太會遇到的問題。第一個(gè)是非平穩(wěn)數(shù)據(jù)流你用當(dāng)前策略收集的數(shù)據(jù)反過來更新當(dāng)前策略策略一變下一輪數(shù)據(jù)的分布又會變。這就像一個(gè)在不斷改變出題方向的考試系統(tǒng)剛復(fù)習(xí)完上一版考點(diǎn)下一版又換了。第二個(gè)是探索與利用的成本要實(shí)時(shí)兌現(xiàn)任何一次嘗試新動作都可能造成真實(shí)收益損失算法必須精確地控制探索頻率。對比之下離線強(qiáng)化學(xué)習(xí)面對的是一個(gè)固定數(shù)據(jù)集核心難點(diǎn)在于處理好分布外動作的價(jià)值估計(jì)而在線強(qiáng)化學(xué)習(xí)真正難在如何設(shè)計(jì)一個(gè)有原則的探索機(jī)制。標(biāo)題里同時(shí)出現(xiàn) Online 和 Fundamental Limits基本就是在暗示這篇文章大概率會拿遺憾界regret作為標(biāo)尺因?yàn)檫z憾恰恰是量化在線探索代價(jià)最自然的方式。對比維度在線 RL離線 RL / 批處理傳統(tǒng)監(jiān)督式學(xué)習(xí)數(shù)據(jù)來源策略實(shí)時(shí)交互生成固定歷史數(shù)據(jù)集獨(dú)立同分布樣本策略更新邊交互邊更新訓(xùn)練后再部署訓(xùn)練后固定探索代價(jià)直接計(jì)入遺憾無需考慮無需考慮主要難點(diǎn)探索-利用權(quán)衡、非平穩(wěn)分布分布外估計(jì)、數(shù)據(jù)覆蓋度泛化與過擬合2. 什么場景會逼你用只認(rèn)結(jié)果的在線學(xué)習(xí)2.1 只有最終結(jié)果的現(xiàn)實(shí)任務(wù)單看問題設(shè)定可能覺得這是理論家在自娛自樂。但落到真實(shí)世界大量任務(wù)就是只給你一個(gè)最終結(jié)果沒有過程獎勵(lì)。最典型的是推薦系統(tǒng)。平臺給用戶推了一系列內(nèi)容你不會在每個(gè)內(nèi)容上直接得到用戶真正喜歡嗎的反饋你只會在幾天后看到轉(zhuǎn)化率、留存率或者總收入這類結(jié)果指標(biāo)。中間哪些內(nèi)容起了正作用、哪些起了反作用其實(shí)沒有一個(gè)可靠的即時(shí)標(biāo)簽。另一個(gè)例子是自適應(yīng)臨床試驗(yàn)醫(yī)生分批對患者施加治療方案只有在試驗(yàn)結(jié)束時(shí)才能看到治愈率這類終局指標(biāo)。如果過程中藥物有階段性的生理指標(biāo)變化這些變化也只是弱信號未必能代表最終結(jié)果。機(jī)器人操控也是一樣。一個(gè)機(jī)械臂嘗試抓取物體最常見的反饋是抓沒抓起來軌跡中間的每一步都沒有明確獎勵(lì)。這類少樣本、稀疏反饋、單回合成敗的場景幾乎就是 Outcome-Based 在線 RL 的原生土壤。2.2 探索-利用權(quán)衡在這里被放大了多臂老虎機(jī)問題里有一個(gè)經(jīng)典直覺你要在多試試幾家餐廳和一直去最喜歡的那家之間權(quán)衡。放到只有最終結(jié)果的場景里這個(gè)權(quán)衡被放大了好幾倍。原因很簡單如果每一步都有獎勵(lì)算法在探索過程中還能不斷獲得局部信號來修正判斷探索的性價(jià)比很高。但如果只有終局結(jié)果一次探索的代價(jià)是整條軌跡的機(jī)會成本而且如果失敗你不知道失敗來自探索動作本身還是來自軌跡上更早的一個(gè)決定。我見過不少同學(xué)在復(fù)現(xiàn)這類算法時(shí)會把探索參數(shù)調(diào)得很激進(jìn)覺得稀疏獎勵(lì)環(huán)境下不多探索怎么行。結(jié)果 regret 曲線反而直線上升因?yàn)槊恳淮蔚唾|(zhì)量探索都積累了一整段低價(jià)值軌跡更新時(shí)又把錯(cuò)誤信號傳播給了所有狀態(tài)。多試了 Deep Q-Network 的 epsilon 衰減策略也收效一般關(guān)鍵問題在于探索不僅是換個(gè)動作還要考慮換哪個(gè)狀態(tài)下去換動作。2.3 為什么這類論文非要談Fundamental Limits部分讀者可能不太理解為什么一篇研究論文要去證明某些事情做不到這不是給自己唱衰嗎其實(shí)理論下界才是這類工作的價(jià)值錨點(diǎn)。一個(gè)算法的 regret 上界告訴你我把效率做到了多少量級但你可能還想知道還有沒有更快的算法。如果沒有下界你永遠(yuǎn)不知道當(dāng)前的上界是不是最優(yōu)結(jié)果。Fundamental Limits 說的是不管你怎么設(shè)計(jì)你的遺憾都不可能低于某個(gè)量級。這就像賽跑選手想知道人類百米極限到底是多少——不是用來打擊熱情而是用來校準(zhǔn)訓(xùn)練目標(biāo)。在下界證明中研究者通常會構(gòu)造兩個(gè)或多個(gè)統(tǒng)計(jì)上難以區(qū)分的環(huán)境它們的最優(yōu)策略差別很大但觀測到的結(jié)果分布卻極為接近。任何算法想要區(qū)分它們都必須積累足夠的樣本量。如果某個(gè)問題在 T 步交互內(nèi)需要的樣本量有硬性下限那么對應(yīng)遺憾量級也就有了下界。這是我在讀這類文章時(shí)最佩服的環(huán)節(jié)也是Algorithms and Fundamental Limits這個(gè)標(biāo)題中更有分量的那一半。3. 算法側(cè)樂觀估計(jì)、函數(shù)逼近與一個(gè)最小可復(fù)現(xiàn)框架3.1 樂觀估計(jì)從老虎機(jī)到大規(guī)模MDP現(xiàn)代在線 RL 算法里最常見的設(shè)計(jì)原則叫面對不確定性的樂觀optimism in the face of uncertainty它的思想源頭非常簡單直觀如果你不知道某個(gè)選擇的真實(shí)價(jià)值那就先相信它比目前看上去要好一點(diǎn)于是你會更愿意嘗試它。這個(gè)原則在多臂老虎機(jī)中的應(yīng)用就是 UCB每個(gè)臂的估計(jì)獎勵(lì)之外疊加一個(gè)置信區(qū)間上界然后選擇上界最高的臂。置信區(qū)間越寬說明歷史數(shù)據(jù)越少越需要探索。把這個(gè)想法從選擇臂擴(kuò)展到馬爾可夫決策過程中的價(jià)值函數(shù)時(shí)就成了優(yōu)化算法的基礎(chǔ)底盤每一步都對狀態(tài)-動作價(jià)值估計(jì)加上一個(gè)探索附加項(xiàng)讓算法在拿不準(zhǔn)的狀態(tài)更愿意試探。我接觸這類方法時(shí)最大的感悟是樂觀不是一種盲目賭運(yùn)氣的心態(tài)而是一個(gè)經(jīng)過精心量化的機(jī)制。附加項(xiàng)到底加多大直接決定了算法是過度保守還是過度魯莽。理論工作往往給出附加項(xiàng)與訪問次數(shù)或函數(shù)類復(fù)雜度之間的精確關(guān)系工程復(fù)現(xiàn)時(shí)即使簡化也最好不要把探索項(xiàng)調(diào)沒了否則你會得到一堆確定性但次優(yōu)的策略。3.2 函數(shù)逼近部署回歸目標(biāo)與探索Bonus當(dāng)狀態(tài)空間不是幾個(gè)離散格子時(shí)我們必須用參數(shù)化的價(jià)值函數(shù)來泛化。于是 Outcome-Based 場景下的算法結(jié)構(gòu)會演變成這樣維護(hù)一個(gè)價(jià)值網(wǎng)絡(luò)每次完成一個(gè)回合后用終局結(jié)果作為整條軌跡的返回估計(jì)然后執(zhí)行回歸更新。這里最要命的是回歸目標(biāo)不穩(wěn)定。在監(jiān)督學(xué)習(xí)里標(biāo)簽是外部給定、不會變的但在這種在線 RL 里價(jià)值網(wǎng)絡(luò)的更新目標(biāo)來自自身預(yù)測加上終局返回。隨著策略不斷變化同一個(gè)狀態(tài)在不同階段看到的返回分布會完全不同。如果直接把所有歷史放進(jìn)一個(gè)大規(guī)模經(jīng)驗(yàn)池網(wǎng)絡(luò)可能會被互相矛盾的舊目標(biāo)拖累但如果完全只使用最近的數(shù)據(jù)樣本量又不夠方差極大。實(shí)用的折中做法是分復(fù)雜度處理小規(guī)模離散環(huán)境可以直接保存每個(gè)狀態(tài)-動作對的訪問次數(shù)和累計(jì)返回按表格方式查表更新大規(guī)模連續(xù)環(huán)境才上神經(jīng)網(wǎng)絡(luò)并配一個(gè)很小的經(jīng)驗(yàn)池或者定期重新擬合。很多時(shí)候我建議初學(xué)者先跑通表格版本的 UCB-H 型算法再切入函數(shù)逼近否則會陷在網(wǎng)絡(luò)到底該擬合什么的泥潭里。3.3 一個(gè)最小可行的框架偽代碼為了把上面的思路串起來我寫一個(gè)非常抽象的框架它捕捉了 Outcome-Based Online RL 算法的共性骨架。不同論文的差異主要在于如何構(gòu)造樂觀策略和如何更新價(jià)值估計(jì)這兩步。def outcome_based_online_rl(env, total_episodes): # value_fn: progress 估計(jì) Q(s, a) 的函數(shù) # count: 記錄 s,a 訪問次數(shù)用于置信區(qū)間 value_fn init_value_net() count init_counter() dataset [] for ep in range(total_episodes): # 1. 用樂觀估計(jì)生成當(dāng)前策略 policy optimistic_policy(value_fn, count) # 2. 和真實(shí)環(huán)境交互收集一條軌跡 s env.reset() trajectory [] while not env.is_terminal(s): a policy.choose_action(s) s_next env.step(s, a) trajectory.append((s, a, s_next)) s s_next # 3. 只有回合結(jié)束時(shí)才拿到最終結(jié)果 outcome env.final_outcome() # 4. 把整條軌跡上的狀態(tài)-動作對統(tǒng)一標(biāo)記為該結(jié)果 for (s, a, s_next) in trajectory: dataset.append((s, a, outcome)) # 5. 重新擬合價(jià)值函數(shù) value_fn fit_value(value_fn, dataset) # 6. 更新訪問計(jì)數(shù)探索缺失會反映在置信區(qū)間上 update_count(count, trajectory) return value_fn實(shí)際工作里第 4 步不一定把 outcome 直接賦給每個(gè) (s, a)需要按折扣因子折算當(dāng)前時(shí)刻的返回。這個(gè)折算是 Outcome-Based 場景里最微妙的地方折扣因子選大了遠(yuǎn)期信用被過度關(guān)注方差爆炸選小了終端結(jié)果對早期狀態(tài)的影響被削弱學(xué)習(xí)會很慢。傳統(tǒng) MDP 里的折扣主要是個(gè)數(shù)學(xué)便利在這里它反而是學(xué)習(xí)效率的開關(guān)。我強(qiáng)烈建議你在理解一個(gè)具體論文時(shí)先把它對應(yīng)的偽代碼親手寫出來把樂觀策略怎么定義和價(jià)值函數(shù)怎么更新這兩行盯清楚其余推導(dǎo)基本都能順藤摸瓜。4. 理論極限遺憾、下界與不可能更快的證明直覺4.1 先統(tǒng)一理解遺憾到底在衡量什么在線學(xué)習(xí)里的遺憾regret定義非常直白每一輪的「最優(yōu)策略收益」和「當(dāng)前策略收益」之差的累計(jì)。如果每一輪里你用的是策略 π_t那么總遺憾可以寫成[ R(T)\sum_{t1}^{T}\mathbb{E}[V^*-V^{\pi_t}] ]其中 (V^*) 是最優(yōu)策略的期望總收益 (V^{\pi_t}) 是當(dāng)前策略的期望總收益。如果一個(gè)算法幾乎沒有遺憾說明它從頭到尾都貼近最優(yōu)策略浪費(fèi)極少。反過來如果算法前期探索太猛或者后期還在胡亂嘗試遺憾就會線性增長。一個(gè)效率高的算法要讓遺憾盡可能小而平緩即 sublinear 增長比如 (O(\sqrt{T})) 或更好。在 Outcome-Based 設(shè)定下由于每回合只有一個(gè)結(jié)果信號最優(yōu)策略的期望總收益通常就等于該回合結(jié)果的期望。這也讓遺憾的計(jì)算變得更加結(jié)果導(dǎo)向過程如何不重要最終總能拿回多少才是關(guān)鍵。理解這一點(diǎn)后你會發(fā)現(xiàn)理論推導(dǎo)和算法設(shè)計(jì)其實(shí)都圍繞同一個(gè)目標(biāo)盡可能少地在探索時(shí)輸?shù)艚K局。4.2 下界證明的通用思路構(gòu)造兩個(gè)無法分辨的世界理論 paper 里下界定理往往最勸退因?yàn)榇罅扛怕什坏仁胶洼o助假設(shè)堆在一起。但如果你只抓骨架會發(fā)現(xiàn)所有下界證明幾乎都遵循同一個(gè)套路找一個(gè)硬樣本讓最優(yōu)算法也分不清自己到底在哪一個(gè)環(huán)境里。具體來說研究者會構(gòu)造兩個(gè) MDP記為 M1 和 M2。它們之間的最優(yōu)策略完全不同比如 M1 里應(yīng)該選動作 AM2 里應(yīng)該選動作 B。但算法得到的結(jié)果信號在分布上極其接近以至于必須積累很大的樣本量才能以高概率區(qū)分出到底是 M1 還是 M2。信息論里區(qū)分兩個(gè)分布的難度可以用 KL 散度描述如果兩個(gè)分布在 KL 意義上非常近那即使是最優(yōu)算法也需要很多次觀測才能確認(rèn)。把這個(gè)邏輯反推過來如果在 T 次交互內(nèi)要區(qū)分 M1 和 M2 至少需要某個(gè)數(shù)量的樣本那么任何算法都必然在前期犯很多次選錯(cuò)最優(yōu)動作的錯(cuò)。把這些錯(cuò)誤累計(jì)起來就得到了遺憾下界。讀下界證明時(shí)你可以直接跳過繁瑣的常數(shù)計(jì)算重點(diǎn)看這三件事它構(gòu)造了兩個(gè)什么樣的環(huán)境這兩個(gè)環(huán)境在統(tǒng)計(jì)上有多接近它們要求的最優(yōu)策略差異有多大。這三點(diǎn)明白之后下界的直覺就有了。4.3 一張表看懂不同設(shè)定下的遺憾量級這類工作的理論貢獻(xiàn)通常會在表格中體現(xiàn)得最清楚。不同假設(shè)強(qiáng)度下算法的遺憾上界和下界都有各自的特征。我這里給出一個(gè)非常粗略的典型量級圖景可以幫助你建立基線判斷設(shè)定假設(shè)典型遺憾量級上界量級含義表格型 MDP有限狀態(tài)動作(\tilde{O}(\sqrt{HSAT})) 附近隨狀態(tài)動作數(shù)、回合長度開根號增長線性函數(shù)逼近特征維度 d與 (d)、(T) 相關(guān)的 (\tilde{O}(d\sqrt{T})) 量級維度越高探索代價(jià)越大一般非線性函數(shù)類往往依賴某種復(fù)雜度度量覆蓋數(shù)、eluder維數(shù)復(fù)雜度度量越小遺憾上界越緊如果你第一次看到 (\tilde{O}) 這個(gè)符號不用慌它只是省略了 (\log) 因子。表格只是幫你建立不同假設(shè)會帶來不同遺憾量級的認(rèn)知。上下界是否匹配其實(shí)是這類文章最值得關(guān)注的看點(diǎn)。一個(gè)算法如果上界正好等于已知下界就說明它在理論上達(dá)到了不可改進(jìn)的級別。這在 Online RL 里通常意味著問題被徹底認(rèn)識了。但另一方面匹配的上下界往往來自相對簡單的設(shè)定一旦把函數(shù)逼近類擴(kuò)大到普遍情形下界會變得非?？量趟惴ㄒ@得好表現(xiàn)也會困難得多。讀這類推導(dǎo)時(shí)我的習(xí)慣是先把表格抄下來再比對作者在定理里到底用了哪些額外假設(shè)比如獎勵(lì)上界、混合時(shí)間、特征范數(shù)約束。這些假設(shè)在真實(shí)環(huán)境下常常并不滿足卻是理論能成立的前提。5. 復(fù)現(xiàn)這個(gè)方向的實(shí)驗(yàn)時(shí)我繞過的那些坑5.1 只有最終結(jié)果帶來的信用分配陷阱第一次親手復(fù)現(xiàn) Outcome-Based 在線算法時(shí)我踩過一個(gè)典型坑當(dāng)回合結(jié)束時(shí)只有一個(gè) outcome比如成功1、失敗0我就很自然地把這個(gè)值當(dāng)作整條軌跡所有狀態(tài)-動作對的回歸目標(biāo)。直覺上是既然結(jié)果是好的所有步驟都算貢獻(xiàn)但這樣做忽略了回報(bào)在不同時(shí)間點(diǎn)的權(quán)重差異。在帶折扣因子 (\gamma) 的設(shè)定下終局結(jié)果 G 折算到第 t 步目標(biāo)時(shí)應(yīng)該是 (\gamma^{L-t}G)其中 L 是回合長度。很多簡化實(shí)現(xiàn)直接用了 G結(jié)果在早期狀態(tài)上過度放大遠(yuǎn)期結(jié)果導(dǎo)致價(jià)值估計(jì)偏差巨大。而如果 (\gamma) 太小早期狀態(tài)幾乎什么都沒學(xué)到。我的改進(jìn)方案是在生成訓(xùn)練目標(biāo)時(shí)嚴(yán)格按時(shí)間衰減重新計(jì)算每一步的返回估計(jì)同時(shí)給軌跡末段的狀態(tài)更高置信權(quán)值。另一個(gè)更直覺的辦法是只讓靠近成功時(shí)刻的最后幾步參與強(qiáng)更新前期狀態(tài)用弱一點(diǎn)的學(xué)習(xí)率。這其實(shí)不是花哨技巧而是對稀疏返回的一種方差控制越靠近結(jié)果信用越明確學(xué)習(xí)信號越可靠。5.2 在線評估指標(biāo)別只看最終遺憾復(fù)現(xiàn)在線 RL 實(shí)驗(yàn)時(shí)最讓我頭疼的不是訓(xùn)練不穩(wěn)而是怎么評價(jià)算法到底有沒有在學(xué)。很多論文的圖表只畫累計(jì)遺憾看起來平滑規(guī)律可一旦你換隨機(jī)種子或者換環(huán)境曲線就會非常振蕩。因?yàn)槊炕睾现挥幸粋€(gè)終局結(jié)果單回合 return 的方差本來就大直接看單回合曲線基本看不出趨勢。我建議在實(shí)驗(yàn)里同時(shí)記錄三個(gè)指標(biāo)累計(jì)遺憾的滾動平均、最近 100 個(gè)回合的平均 outcome、以及策略在差評環(huán)境下的最差表現(xiàn)。第三點(diǎn)最容易被忽略。由于在線學(xué)習(xí)會隨機(jī)訪問不同狀態(tài)某一輪的壞結(jié)果會把策略推向錯(cuò)誤方向之后可能好幾輪都緩不過來。記錄最差表現(xiàn)能幫你捕捉這類災(zāi)難性忘記現(xiàn)象它的出現(xiàn)往往說明學(xué)習(xí)率或探索系數(shù)需要調(diào)整。如果要和別人的 baseline 對比務(wù)必統(tǒng)一環(huán)境、統(tǒng)一回合長度、統(tǒng)一隨機(jī)種子。稀疏反饋算法對種子極其敏感同一個(gè)參數(shù)在不同隨機(jī)種子下可能產(chǎn)生完全不同的 regret 曲線。我會直接跑至少 5 個(gè)種子畫中位數(shù)和四分位區(qū)間而不是只畫一條單次運(yùn)行曲線。5.3 一個(gè)快速驗(yàn)證思路從大狀態(tài)空間退回小環(huán)境我認(rèn)識不少同學(xué)直接上來就在連續(xù)控制環(huán)境里復(fù)現(xiàn)價(jià)值函數(shù)逼近類算法結(jié)果一調(diào)就是幾周。其實(shí)這兩類問題的結(jié)論差距非常大因?yàn)檫B續(xù)狀態(tài)空間會立刻引入泛化誤差這個(gè)額外變量使算法設(shè)計(jì)中的理論邏輯被噪聲掩蓋。所以如果只是想驗(yàn)證我對算法的理解對不對我會先選一個(gè)離散狀態(tài)空間足夠小但又不是 trivial 的環(huán)境比如十幾個(gè)狀態(tài)、兩三個(gè)動作的網(wǎng)格類任務(wù)。在這個(gè)環(huán)境里表格型 UCB 和帶函數(shù)逼近的方法可以得到幾乎一致的結(jié)論。如果在這個(gè) toy 環(huán)境里策略收斂不了一定是算法邏輯有 bug而不是環(huán)境太難。真正要跑 Large-Scale 實(shí)驗(yàn)前先在小環(huán)境上把樂觀項(xiàng)大小、學(xué)習(xí)率、折扣因子過一遍至少能砍掉一半調(diào)試時(shí)間。我還有一個(gè)習(xí)慣在小環(huán)境里把每個(gè)狀態(tài)的訪問計(jì)數(shù)打印成熱力圖。如果某個(gè)區(qū)域完全白色說明算法從未正式探索過那里這會直接反映在策略空洞區(qū)。這種診斷信息在連續(xù)環(huán)境里很難獲得但在小環(huán)境里卻一針見血。6. 一點(diǎn)個(gè)人閱讀與實(shí)踐后的體會到現(xiàn)在為止我還記得第一次讀這類標(biāo)題時(shí)被大量符號勸退的經(jīng)歷。后來我養(yǎng)成一個(gè)三步分析法幾乎可以用在任何帶 Algorithms and Fundamental Limits 后綴的 RL 文章上第一步找出它定義的價(jià)值信號到底是什么是每回合 terminal outcome還是某個(gè)延遲但非稀疏的獎勵(lì)第二步找出它的算法用了哪種探索機(jī)制是樂觀估計(jì)、隨機(jī)擾動還是熵正則這一決定直接告訴你實(shí)驗(yàn)里什么參數(shù)最敏感第三步找出它證明的下界對應(yīng)哪種信息缺口這能幫你理解為什么算法長成那樣。這三步做完標(biāo)題里的信息就被消化得差不多了。合上論文后我會問自己一個(gè)問題如果換一個(gè)真實(shí)業(yè)務(wù)場景我還需要額外補(bǔ)充哪些工程性假設(shè)這個(gè)問題往往比論文本身更鍛煉判斷力因?yàn)槔碚撛O(shè)定終究是理想化的而現(xiàn)實(shí)永遠(yuǎn)是混雜、多噪聲、部分可觀測的。希望這篇拆解也能幫你少走一些我走過的彎路遇到同類標(biāo)題時(shí)至少能一眼看出它到底在打哪一局。 Outcome-Based在線強(qiáng)化學(xué)習(xí)：算法設(shè)計(jì)與理論極限解析
如果你在讀論文推送時(shí)看到這樣一條標(biāo)題2025_NIPS_Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits——大概率會直接劃過。我第一眼也差不多但在這個(gè)圈子里待久了反而養(yǎng)成了一個(gè)習(xí)慣越是帶這種硬核詞綴的標(biāo)題越要先拆清楚它在說什么因?yàn)樗馕吨粋€(gè)新方向、或者一個(gè)還沒被充分占領(lǐng)的問題。這個(gè)標(biāo)題里三個(gè)關(guān)鍵片段分別是Outcome-Based基于結(jié)果、Online Reinforcement Learning在線強(qiáng)化學(xué)習(xí)、Algorithms and Fundamental Limits算法與理論下界。把它們翻譯成人話就是在只能觀察到最終結(jié)果、而非每一步都有即時(shí)獎勵(lì)的強(qiáng)化學(xué)習(xí)任務(wù)里我們要設(shè)計(jì)算法讓智能體在與環(huán)境交互的過程中不斷學(xué)習(xí)同時(shí)弄清楚這類問題的最優(yōu)效率邊界在哪里。這篇內(nèi)容不會去復(fù)述某個(gè)具體論文的公式細(xì)節(jié)而是分享一套我自己看這類RL理論工作時(shí)用的拆解框架。無論你是正在復(fù)現(xiàn)相關(guān)實(shí)驗(yàn)的研究生還是想了解為什么這類文章越來越重要的工程師讀完應(yīng)該都能建立一張比較完整的地圖。1. 先把標(biāo)題拆開三個(gè)關(guān)鍵詞其實(shí)在回答三個(gè)問題1.1 一個(gè)看起來很勸退的前綴老實(shí)說Outcome-Based Online Reinforcement Learning這個(gè)組合在圈內(nèi)并不是一個(gè)像 off-policy、model-based 那樣統(tǒng)一且公認(rèn)的范式門類。它更多是研究者為了強(qiáng)調(diào)自己問題設(shè)定而拼出來的一個(gè)描述性前綴。也正是因?yàn)闆]有固定模板看到這個(gè)標(biāo)題反而要多問幾句它說的 outcome 到底是什么它限定的 online 又是在什么尺度上的在標(biāo)準(zhǔn)強(qiáng)化學(xué)習(xí)里一個(gè)有監(jiān)督式的學(xué)習(xí)循環(huán)通常是智能體觀察狀態(tài)選擇動作環(huán)境返回下一個(gè)狀態(tài)和獎勵(lì)。獎勵(lì)一旦在每個(gè)時(shí)刻都給出算法的學(xué)習(xí)信號就非常密集。但 Outcome-Based 這個(gè)偏移一開始就把獎勵(lì)壓縮了你只在回合結(jié)束、或者某個(gè)關(guān)鍵節(jié)點(diǎn)到來時(shí)才知道這一整條軌跡到底產(chǎn)出什么結(jié)果。這個(gè)結(jié)果可能是一個(gè)成功/失敗標(biāo)簽可能是最終收益也可能是一段很長的延遲反饋。這種設(shè)計(jì)變化不是文字游戲它會直接影響整個(gè)算法的優(yōu)化目標(biāo)、方差大小、甚至理論分析中要用到的概率工具。我通常把這個(gè)前綴理解為三個(gè)問題第一可觀測信號是什么第二信號之間相隔多長第三最優(yōu)策略的定義是否仍然是最大化長期回報(bào)。把這三個(gè)問題想清楚這個(gè)方向的骨架其實(shí)就出來了。1.2 結(jié)果驅(qū)動不等于每步都給獎勵(lì)很多剛接觸強(qiáng)化學(xué)習(xí)的同學(xué)會下意識覺得RL 本來就靠獎勵(lì)學(xué)習(xí)Outcome-Based 能有多大差別。這里我舉個(gè)最直觀的類比考試只看期末總成績和每次作業(yè)、隨堂測驗(yàn)、課堂表現(xiàn)全部計(jì)入平時(shí)分看起來只是一個(gè)打分方式變化但對你該怎么分配復(fù)習(xí)時(shí)間這件事的影響是天翻地覆的。如果老師每節(jié)課都打分你立刻就能知道哪些知識點(diǎn)掌握得不好下一周就可以針對調(diào)整。但如果只有一張期末試卷你只有等到考完才能發(fā)現(xiàn)自己的薄弱環(huán)節(jié)而且你根本無法確定到底是哪個(gè)章節(jié)、哪種題型拖累了總分。這就是 credit assignment信用分配問題在只有最終結(jié)果的時(shí)候中間每一環(huán)的貢獻(xiàn)都被混在一起算法很難把功勞和責(zé)任準(zhǔn)確地拆給某個(gè)狀態(tài)-動作對。在這種設(shè)定下先前那些建立在每步都有 reward 反饋之上的技巧也會失效比如時(shí)間差分學(xué)習(xí)中的時(shí)序誤差更新就缺少了一個(gè)穩(wěn)定的局部監(jiān)督信號。于是大量方案會退化成蒙特卡洛式的經(jīng)驗(yàn)積累從終局結(jié)果出發(fā)把整條軌跡上的狀態(tài)-動作統(tǒng)一賦上回報(bào)值。理解了這個(gè)關(guān)鍵差異才算真正讀懂了標(biāo)題里的 Outcome-Based。1.3 一個(gè)Online就讓它和離線學(xué)習(xí)區(qū)分開標(biāo)題里另一個(gè)容易忽略的詞是 Online。它意味著智能體必須一邊和環(huán)境交互、一邊更新策略而不是拿到一批離線數(shù)據(jù)之后慢慢訓(xùn)練。這個(gè)區(qū)別遠(yuǎn)比表面上看起來更嚴(yán)重。在線學(xué)習(xí)會帶來兩個(gè)離線式方法不太會遇到的問題。第一個(gè)是非平穩(wěn)數(shù)據(jù)流你用當(dāng)前策略收集的數(shù)據(jù)反過來更新當(dāng)前策略策略一變下一輪數(shù)據(jù)的分布又會變。這就像一個(gè)在不斷改變出題方向的考試系統(tǒng)剛復(fù)習(xí)完上一版考點(diǎn)下一版又換了。第二個(gè)是探索與利用的成本要實(shí)時(shí)兌現(xiàn)任何一次嘗試新動作都可能造成真實(shí)收益損失算法必須精確地控制探索頻率。對比之下離線強(qiáng)化學(xué)習(xí)面對的是一個(gè)固定數(shù)據(jù)集核心難點(diǎn)在于處理好分布外動作的價(jià)值估計(jì)而在線強(qiáng)化學(xué)習(xí)真正難在如何設(shè)計(jì)一個(gè)有原則的探索機(jī)制。標(biāo)題里同時(shí)出現(xiàn) Online 和 Fundamental Limits基本就是在暗示這篇文章大概率會拿遺憾界regret作為標(biāo)尺因?yàn)檫z憾恰恰是量化在線探索代價(jià)最自然的方式。對比維度在線 RL離線 RL / 批處理傳統(tǒng)監(jiān)督式學(xué)習(xí)數(shù)據(jù)來源策略實(shí)時(shí)交互生成固定歷史數(shù)據(jù)集獨(dú)立同分布樣本策略更新邊交互邊更新訓(xùn)練后再部署訓(xùn)練后固定探索代價(jià)直接計(jì)入遺憾無需考慮無需考慮主要難點(diǎn)探索-利用權(quán)衡、非平穩(wěn)分布分布外估計(jì)、數(shù)據(jù)覆蓋度泛化與過擬合2. 什么場景會逼你用只認(rèn)結(jié)果的在線學(xué)習(xí)2.1 只有最終結(jié)果的現(xiàn)實(shí)任務(wù)單看問題設(shè)定可能覺得這是理論家在自娛自樂。但落到真實(shí)世界大量任務(wù)就是只給你一個(gè)最終結(jié)果沒有過程獎勵(lì)。最典型的是推薦系統(tǒng)。平臺給用戶推了一系列內(nèi)容你不會在每個(gè)內(nèi)容上直接得到用戶真正喜歡嗎的反饋你只會在幾天后看到轉(zhuǎn)化率、留存率或者總收入這類結(jié)果指標(biāo)。中間哪些內(nèi)容起了正作用、哪些起了反作用其實(shí)沒有一個(gè)可靠的即時(shí)標(biāo)簽。另一個(gè)例子是自適應(yīng)臨床試驗(yàn)醫(yī)生分批對患者施加治療方案只有在試驗(yàn)結(jié)束時(shí)才能看到治愈率這類終局指標(biāo)。如果過程中藥物有階段性的生理指標(biāo)變化這些變化也只是弱信號未必能代表最終結(jié)果。機(jī)器人操控也是一樣。一個(gè)機(jī)械臂嘗試抓取物體最常見的反饋是抓沒抓起來軌跡中間的每一步都沒有明確獎勵(lì)。這類少樣本、稀疏反饋、單回合成敗的場景幾乎就是 Outcome-Based 在線 RL 的原生土壤。2.2 探索-利用權(quán)衡在這里被放大了多臂老虎機(jī)問題里有一個(gè)經(jīng)典直覺你要在多試試幾家餐廳和一直去最喜歡的那家之間權(quán)衡。放到只有最終結(jié)果的場景里這個(gè)權(quán)衡被放大了好幾倍。原因很簡單如果每一步都有獎勵(lì)算法在探索過程中還能不斷獲得局部信號來修正判斷探索的性價(jià)比很高。但如果只有終局結(jié)果一次探索的代價(jià)是整條軌跡的機(jī)會成本而且如果失敗你不知道失敗來自探索動作本身還是來自軌跡上更早的一個(gè)決定。我見過不少同學(xué)在復(fù)現(xiàn)這類算法時(shí)會把探索參數(shù)調(diào)得很激進(jìn)覺得稀疏獎勵(lì)環(huán)境下不多探索怎么行。結(jié)果 regret 曲線反而直線上升因?yàn)槊恳淮蔚唾|(zhì)量探索都積累了一整段低價(jià)值軌跡更新時(shí)又把錯(cuò)誤信號傳播給了所有狀態(tài)。多試了 Deep Q-Network 的 epsilon 衰減策略也收效一般關(guān)鍵問題在于探索不僅是換個(gè)動作還要考慮換哪個(gè)狀態(tài)下去換動作。2.3 為什么這類論文非要談Fundamental Limits部分讀者可能不太理解為什么一篇研究論文要去證明某些事情做不到這不是給自己唱衰嗎其實(shí)理論下界才是這類工作的價(jià)值錨點(diǎn)。一個(gè)算法的 regret 上界告訴你我把效率做到了多少量級但你可能還想知道還有沒有更快的算法。如果沒有下界你永遠(yuǎn)不知道當(dāng)前的上界是不是最優(yōu)結(jié)果。Fundamental Limits 說的是不管你怎么設(shè)計(jì)你的遺憾都不可能低于某個(gè)量級。這就像賽跑選手想知道人類百米極限到底是多少——不是用來打擊熱情而是用來校準(zhǔn)訓(xùn)練目標(biāo)。在下界證明中研究者通常會構(gòu)造兩個(gè)或多個(gè)統(tǒng)計(jì)上難以區(qū)分的環(huán)境它們的最優(yōu)策略差別很大但觀測到的結(jié)果分布卻極為接近。任何算法想要區(qū)分它們都必須積累足夠的樣本量。如果某個(gè)問題在 T 步交互內(nèi)需要的樣本量有硬性下限那么對應(yīng)遺憾量級也就有了下界。這是我在讀這類文章時(shí)最佩服的環(huán)節(jié)也是Algorithms and Fundamental Limits這個(gè)標(biāo)題中更有分量的那一半。3. 算法側(cè)樂觀估計(jì)、函數(shù)逼近與一個(gè)最小可復(fù)現(xiàn)框架3.1 樂觀估計(jì)從老虎機(jī)到大規(guī)模MDP現(xiàn)代在線 RL 算法里最常見的設(shè)計(jì)原則叫面對不確定性的樂觀optimism in the face of uncertainty它的思想源頭非常簡單直觀如果你不知道某個(gè)選擇的真實(shí)價(jià)值那就先相信它比目前看上去要好一點(diǎn)于是你會更愿意嘗試它。這個(gè)原則在多臂老虎機(jī)中的應(yīng)用就是 UCB每個(gè)臂的估計(jì)獎勵(lì)之外疊加一個(gè)置信區(qū)間上界然后選擇上界最高的臂。置信區(qū)間越寬說明歷史數(shù)據(jù)越少越需要探索。把這個(gè)想法從選擇臂擴(kuò)展到馬爾可夫決策過程中的價(jià)值函數(shù)時(shí)就成了優(yōu)化算法的基礎(chǔ)底盤每一步都對狀態(tài)-動作價(jià)值估計(jì)加上一個(gè)探索附加項(xiàng)讓算法在拿不準(zhǔn)的狀態(tài)更愿意試探。我接觸這類方法時(shí)最大的感悟是樂觀不是一種盲目賭運(yùn)氣的心態(tài)而是一個(gè)經(jīng)過精心量化的機(jī)制。附加項(xiàng)到底加多大直接決定了算法是過度保守還是過度魯莽。理論工作往往給出附加項(xiàng)與訪問次數(shù)或函數(shù)類復(fù)雜度之間的精確關(guān)系工程復(fù)現(xiàn)時(shí)即使簡化也最好不要把探索項(xiàng)調(diào)沒了否則你會得到一堆確定性但次優(yōu)的策略。3.2 函數(shù)逼近部署回歸目標(biāo)與探索Bonus當(dāng)狀態(tài)空間不是幾個(gè)離散格子時(shí)我們必須用參數(shù)化的價(jià)值函數(shù)來泛化。于是 Outcome-Based 場景下的算法結(jié)構(gòu)會演變成這樣維護(hù)一個(gè)價(jià)值網(wǎng)絡(luò)每次完成一個(gè)回合后用終局結(jié)果作為整條軌跡的返回估計(jì)然后執(zhí)行回歸更新。這里最要命的是回歸目標(biāo)不穩(wěn)定。在監(jiān)督學(xué)習(xí)里標(biāo)簽是外部給定、不會變的但在這種在線 RL 里價(jià)值網(wǎng)絡(luò)的更新目標(biāo)來自自身預(yù)測加上終局返回。隨著策略不斷變化同一個(gè)狀態(tài)在不同階段看到的返回分布會完全不同。如果直接把所有歷史放進(jìn)一個(gè)大規(guī)模經(jīng)驗(yàn)池網(wǎng)絡(luò)可能會被互相矛盾的舊目標(biāo)拖累但如果完全只使用最近的數(shù)據(jù)樣本量又不夠方差極大。實(shí)用的折中做法是分復(fù)雜度處理小規(guī)模離散環(huán)境可以直接保存每個(gè)狀態(tài)-動作對的訪問次數(shù)和累計(jì)返回按表格方式查表更新大規(guī)模連續(xù)環(huán)境才上神經(jīng)網(wǎng)絡(luò)并配一個(gè)很小的經(jīng)驗(yàn)池或者定期重新擬合。很多時(shí)候我建議初學(xué)者先跑通表格版本的 UCB-H 型算法再切入函數(shù)逼近否則會陷在網(wǎng)絡(luò)到底該擬合什么的泥潭里。3.3 一個(gè)最小可行的框架偽代碼為了把上面的思路串起來我寫一個(gè)非常抽象的框架它捕捉了 Outcome-Based Online RL 算法的共性骨架。不同論文的差異主要在于如何構(gòu)造樂觀策略和如何更新價(jià)值估計(jì)這兩步。def outcome_based_online_rl(env, total_episodes): # value_fn: progress 估計(jì) Q(s, a) 的函數(shù) # count: 記錄 s,a 訪問次數(shù)用于置信區(qū)間 value_fn init_value_net() count init_counter() dataset [] for ep in range(total_episodes): # 1. 用樂觀估計(jì)生成當(dāng)前策略 policy optimistic_policy(value_fn, count) # 2. 和真實(shí)環(huán)境交互收集一條軌跡 s env.reset() trajectory [] while not env.is_terminal(s): a policy.choose_action(s) s_next env.step(s, a) trajectory.append((s, a, s_next)) s s_next # 3. 只有回合結(jié)束時(shí)才拿到最終結(jié)果 outcome env.final_outcome() # 4. 把整條軌跡上的狀態(tài)-動作對統(tǒng)一標(biāo)記為該結(jié)果 for (s, a, s_next) in trajectory: dataset.append((s, a, outcome)) # 5. 重新擬合價(jià)值函數(shù) value_fn fit_value(value_fn, dataset) # 6. 更新訪問計(jì)數(shù)探索缺失會反映在置信區(qū)間上 update_count(count, trajectory) return value_fn實(shí)際工作里第 4 步不一定把 outcome 直接賦給每個(gè) (s, a)需要按折扣因子折算當(dāng)前時(shí)刻的返回。這個(gè)折算是 Outcome-Based 場景里最微妙的地方折扣因子選大了遠(yuǎn)期信用被過度關(guān)注方差爆炸選小了終端結(jié)果對早期狀態(tài)的影響被削弱學(xué)習(xí)會很慢。傳統(tǒng) MDP 里的折扣主要是個(gè)數(shù)學(xué)便利在這里它反而是學(xué)習(xí)效率的開關(guān)。我強(qiáng)烈建議你在理解一個(gè)具體論文時(shí)先把它對應(yīng)的偽代碼親手寫出來把樂觀策略怎么定義和價(jià)值函數(shù)怎么更新這兩行盯清楚其余推導(dǎo)基本都能順藤摸瓜。4. 理論極限遺憾、下界與不可能更快的證明直覺4.1 先統(tǒng)一理解遺憾到底在衡量什么在線學(xué)習(xí)里的遺憾regret定義非常直白每一輪的「最優(yōu)策略收益」和「當(dāng)前策略收益」之差的累計(jì)。如果每一輪里你用的是策略 π_t那么總遺憾可以寫成[ R(T)\sum_{t1}^{T}\mathbb{E}[V^*-V^{\pi_t}] ]其中 (V^*) 是最優(yōu)策略的期望總收益 (V^{\pi_t}) 是當(dāng)前策略的期望總收益。如果一個(gè)算法幾乎沒有遺憾說明它從頭到尾都貼近最優(yōu)策略浪費(fèi)極少。反過來如果算法前期探索太猛或者后期還在胡亂嘗試遺憾就會線性增長。一個(gè)效率高的算法要讓遺憾盡可能小而平緩即 sublinear 增長比如 (O(\sqrt{T})) 或更好。在 Outcome-Based 設(shè)定下由于每回合只有一個(gè)結(jié)果信號最優(yōu)策略的期望總收益通常就等于該回合結(jié)果的期望。這也讓遺憾的計(jì)算變得更加結(jié)果導(dǎo)向過程如何不重要最終總能拿回多少才是關(guān)鍵。理解這一點(diǎn)后你會發(fā)現(xiàn)理論推導(dǎo)和算法設(shè)計(jì)其實(shí)都圍繞同一個(gè)目標(biāo)盡可能少地在探索時(shí)輸?shù)艚K局。4.2 下界證明的通用思路構(gòu)造兩個(gè)無法分辨的世界理論 paper 里下界定理往往最勸退因?yàn)榇罅扛怕什坏仁胶洼o助假設(shè)堆在一起。但如果你只抓骨架會發(fā)現(xiàn)所有下界證明幾乎都遵循同一個(gè)套路找一個(gè)硬樣本讓最優(yōu)算法也分不清自己到底在哪一個(gè)環(huán)境里。具體來說研究者會構(gòu)造兩個(gè) MDP記為 M1 和 M2。它們之間的最優(yōu)策略完全不同比如 M1 里應(yīng)該選動作 AM2 里應(yīng)該選動作 B。但算法得到的結(jié)果信號在分布上極其接近以至于必須積累很大的樣本量才能以高概率區(qū)分出到底是 M1 還是 M2。信息論里區(qū)分兩個(gè)分布的難度可以用 KL 散度描述如果兩個(gè)分布在 KL 意義上非常近那即使是最優(yōu)算法也需要很多次觀測才能確認(rèn)。把這個(gè)邏輯反推過來如果在 T 次交互內(nèi)要區(qū)分 M1 和 M2 至少需要某個(gè)數(shù)量的樣本那么任何算法都必然在前期犯很多次選錯(cuò)最優(yōu)動作的錯(cuò)。把這些錯(cuò)誤累計(jì)起來就得到了遺憾下界。讀下界證明時(shí)你可以直接跳過繁瑣的常數(shù)計(jì)算重點(diǎn)看這三件事它構(gòu)造了兩個(gè)什么樣的環(huán)境這兩個(gè)環(huán)境在統(tǒng)計(jì)上有多接近它們要求的最優(yōu)策略差異有多大。這三點(diǎn)明白之后下界的直覺就有了。4.3 一張表看懂不同設(shè)定下的遺憾量級這類工作的理論貢獻(xiàn)通常會在表格中體現(xiàn)得最清楚。不同假設(shè)強(qiáng)度下算法的遺憾上界和下界都有各自的特征。我這里給出一個(gè)非常粗略的典型量級圖景可以幫助你建立基線判斷設(shè)定假設(shè)典型遺憾量級上界量級含義表格型 MDP有限狀態(tài)動作(\tilde{O}(\sqrt{HSAT})) 附近隨狀態(tài)動作數(shù)、回合長度開根號增長線性函數(shù)逼近特征維度 d與 (d)、(T) 相關(guān)的 (\tilde{O}(d\sqrt{T})) 量級維度越高探索代價(jià)越大一般非線性函數(shù)類往往依賴某種復(fù)雜度度量覆蓋數(shù)、eluder維數(shù)復(fù)雜度度量越小遺憾上界越緊如果你第一次看到 (\tilde{O}) 這個(gè)符號不用慌它只是省略了 (\log) 因子。表格只是幫你建立不同假設(shè)會帶來不同遺憾量級的認(rèn)知。上下界是否匹配其實(shí)是這類文章最值得關(guān)注的看點(diǎn)。一個(gè)算法如果上界正好等于已知下界就說明它在理論上達(dá)到了不可改進(jìn)的級別。這在 Online RL 里通常意味著問題被徹底認(rèn)識了。但另一方面匹配的上下界往往來自相對簡單的設(shè)定一旦把函數(shù)逼近類擴(kuò)大到普遍情形下界會變得非?？量趟惴ㄒ@得好表現(xiàn)也會困難得多。讀這類推導(dǎo)時(shí)我的習(xí)慣是先把表格抄下來再比對作者在定理里到底用了哪些額外假設(shè)比如獎勵(lì)上界、混合時(shí)間、特征范數(shù)約束。這些假設(shè)在真實(shí)環(huán)境下常常并不滿足卻是理論能成立的前提。5. 復(fù)現(xiàn)這個(gè)方向的實(shí)驗(yàn)時(shí)我繞過的那些坑5.1 只有最終結(jié)果帶來的信用分配陷阱第一次親手復(fù)現(xiàn) Outcome-Based 在線算法時(shí)我踩過一個(gè)典型坑當(dāng)回合結(jié)束時(shí)只有一個(gè) outcome比如成功1、失敗0我就很自然地把這個(gè)值當(dāng)作整條軌跡所有狀態(tài)-動作對的回歸目標(biāo)。直覺上是既然結(jié)果是好的所有步驟都算貢獻(xiàn)但這樣做忽略了回報(bào)在不同時(shí)間點(diǎn)的權(quán)重差異。在帶折扣因子 (\gamma) 的設(shè)定下終局結(jié)果 G 折算到第 t 步目標(biāo)時(shí)應(yīng)該是 (\gamma^{L-t}G)其中 L 是回合長度。很多簡化實(shí)現(xiàn)直接用了 G結(jié)果在早期狀態(tài)上過度放大遠(yuǎn)期結(jié)果導(dǎo)致價(jià)值估計(jì)偏差巨大。而如果 (\gamma) 太小早期狀態(tài)幾乎什么都沒學(xué)到。我的改進(jìn)方案是在生成訓(xùn)練目標(biāo)時(shí)嚴(yán)格按時(shí)間衰減重新計(jì)算每一步的返回估計(jì)同時(shí)給軌跡末段的狀態(tài)更高置信權(quán)值。另一個(gè)更直覺的辦法是只讓靠近成功時(shí)刻的最后幾步參與強(qiáng)更新前期狀態(tài)用弱一點(diǎn)的學(xué)習(xí)率。這其實(shí)不是花哨技巧而是對稀疏返回的一種方差控制越靠近結(jié)果信用越明確學(xué)習(xí)信號越可靠。5.2 在線評估指標(biāo)別只看最終遺憾復(fù)現(xiàn)在線 RL 實(shí)驗(yàn)時(shí)最讓我頭疼的不是訓(xùn)練不穩(wěn)而是怎么評價(jià)算法到底有沒有在學(xué)。很多論文的圖表只畫累計(jì)遺憾看起來平滑規(guī)律可一旦你換隨機(jī)種子或者換環(huán)境曲線就會非常振蕩。因?yàn)槊炕睾现挥幸粋€(gè)終局結(jié)果單回合 return 的方差本來就大直接看單回合曲線基本看不出趨勢。我建議在實(shí)驗(yàn)里同時(shí)記錄三個(gè)指標(biāo)累計(jì)遺憾的滾動平均、最近 100 個(gè)回合的平均 outcome、以及策略在差評環(huán)境下的最差表現(xiàn)。第三點(diǎn)最容易被忽略。由于在線學(xué)習(xí)會隨機(jī)訪問不同狀態(tài)某一輪的壞結(jié)果會把策略推向錯(cuò)誤方向之后可能好幾輪都緩不過來。記錄最差表現(xiàn)能幫你捕捉這類災(zāi)難性忘記現(xiàn)象它的出現(xiàn)往往說明學(xué)習(xí)率或探索系數(shù)需要調(diào)整。如果要和別人的 baseline 對比務(wù)必統(tǒng)一環(huán)境、統(tǒng)一回合長度、統(tǒng)一隨機(jī)種子。稀疏反饋算法對種子極其敏感同一個(gè)參數(shù)在不同隨機(jī)種子下可能產(chǎn)生完全不同的 regret 曲線。我會直接跑至少 5 個(gè)種子畫中位數(shù)和四分位區(qū)間而不是只畫一條單次運(yùn)行曲線。5.3 一個(gè)快速驗(yàn)證思路從大狀態(tài)空間退回小環(huán)境我認(rèn)識不少同學(xué)直接上來就在連續(xù)控制環(huán)境里復(fù)現(xiàn)價(jià)值函數(shù)逼近類算法結(jié)果一調(diào)就是幾周。其實(shí)這兩類問題的結(jié)論差距非常大因?yàn)檫B續(xù)狀態(tài)空間會立刻引入泛化誤差這個(gè)額外變量使算法設(shè)計(jì)中的理論邏輯被噪聲掩蓋。所以如果只是想驗(yàn)證我對算法的理解對不對我會先選一個(gè)離散狀態(tài)空間足夠小但又不是 trivial 的環(huán)境比如十幾個(gè)狀態(tài)、兩三個(gè)動作的網(wǎng)格類任務(wù)。在這個(gè)環(huán)境里表格型 UCB 和帶函數(shù)逼近的方法可以得到幾乎一致的結(jié)論。如果在這個(gè) toy 環(huán)境里策略收斂不了一定是算法邏輯有 bug而不是環(huán)境太難。真正要跑 Large-Scale 實(shí)驗(yàn)前先在小環(huán)境上把樂觀項(xiàng)大小、學(xué)習(xí)率、折扣因子過一遍至少能砍掉一半調(diào)試時(shí)間。我還有一個(gè)習(xí)慣在小環(huán)境里把每個(gè)狀態(tài)的訪問計(jì)數(shù)打印成熱力圖。如果某個(gè)區(qū)域完全白色說明算法從未正式探索過那里這會直接反映在策略空洞區(qū)。這種診斷信息在連續(xù)環(huán)境里很難獲得但在小環(huán)境里卻一針見血。6. 一點(diǎn)個(gè)人閱讀與實(shí)踐后的體會到現(xiàn)在為止我還記得第一次讀這類標(biāo)題時(shí)被大量符號勸退的經(jīng)歷。后來我養(yǎng)成一個(gè)三步分析法幾乎可以用在任何帶 Algorithms and Fundamental Limits 后綴的 RL 文章上第一步找出它定義的價(jià)值信號到底是什么是每回合 terminal outcome還是某個(gè)延遲但非稀疏的獎勵(lì)第二步找出它的算法用了哪種探索機(jī)制是樂觀估計(jì)、隨機(jī)擾動還是熵正則這一決定直接告訴你實(shí)驗(yàn)里什么參數(shù)最敏感第三步找出它證明的下界對應(yīng)哪種信息缺口這能幫你理解為什么算法長成那樣。這三步做完標(biāo)題里的信息就被消化得差不多了。合上論文后我會問自己一個(gè)問題如果換一個(gè)真實(shí)業(yè)務(wù)場景我還需要額外補(bǔ)充哪些工程性假設(shè)這個(gè)問題往往比論文本身更鍛煉判斷力因?yàn)槔碚撛O(shè)定終究是理想化的而現(xiàn)實(shí)永遠(yuǎn)是混雜、多噪聲、部分可觀測的。希望這篇拆解也能幫你少走一些我走過的彎路遇到同類標(biāo)題時(shí)至少能一眼看出它到底在打哪一局。