?姚班2018級本科生周潤龍作為共同第一作者完成的論文《Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret》被2021年神經信息處理系統進展大會（NeurIPS 2021）接收并評為焦點（Spotlight）論文。本年度大會上獲得該榮譽的論文占總提交論文數不足3%。該論文研究了理論強化學習中最為根本的問題——馬爾科夫決策過程隨機最短路問題（SSP-MDP），并得出了理論最優的算法。
//www.zhuanzhi.ai/paper/616680d5758b82a133a4ce3dc4e540b9
由于其普適性，馬爾科夫決策過程是理論強化學習領域中最受關注的問題模型。在這類問題中，人工智能可以將其所在的環境抽象成一個馬爾科夫鏈，即用狀態、操作、轉移狀態、回報刻畫。在不知道每個操作的轉移狀態和回報的情況下，人工智能需要在K輪學習后最優化某個特定目標。理論研究最為深入的MDP通常假設人工智能一輪只能走固定、有限的步數，或者假設回報隨著步數增長呈指數衰減，這樣的假設過于強大，以至于生活中的另一些基本問題不能被很好地表示。隨機最短路（SSP）問題則沒有上述假設，而采用了一個較弱的假設，即假設按照最優策略執行的人工智能，其一輪的期望總代價不超過一個特定值B*，同時期望步數不超過另一個特定值T*。同時，SSP的目標為搜尋到一個特定狀態的最小總代價，這也與人們以目標為導向的行為方式更加吻合。采用遺憾刻畫算法的優劣，即前K輪所花的實際代價減去K倍最優代價。
????該論文提出了SSP問題的三點要求：(1)最小化最劣情況下的遺憾，由信息論推知下界為Ω(B√(SAK))，依照理論強化學習慣例，可以忽略對數項和與K無關的項；(2)算法的執行不需要事先知道參數B和T*，實際情況中人工智能也是不可能知道這兩個參數的；(3)忽略對數項后，遺憾與T無關，因為T可能會比B大任意多倍。該論文與另一篇同時投稿的論文分別獨立提出了滿足要求(1)的不同算法，而該論文的獨有貢獻在于提出了滿足要求(2)的通用算法。最后，該論文中的算法還能以犧牲要求(2)中的T換取要求(3)，而同時滿足三點要求的算法是否存在目前仍是開放性問題。
????對于要求(1)，該論文提出的算法基于樂觀估計、值迭代的有限時間近似收斂來保證運行效率和遺憾上界。樂觀估計部分用到了上確信界的思路，通過引入統計量方差來獲得較同領域前作更精細的分析方式。該論文通過構造一個新式的貝爾曼算子來保證值迭代的單調、收斂。基于這兩點，該論文將遺憾分解為貝爾曼誤差和統計誤差，并通過遞歸（推）的方式得到方差總和的上界，從而證明遺憾上界。對于要求(2)，該論文的通用算法核心對于B的估計。只要給定一個滿足要求(1)的算法，通用算法可以通過定期比較其實際總代價與估計B的遺憾上界來自適應調整B的估計值。對于遺憾上界的估計需要精細構造常數以及對數項。由于零代價環的存在，需要對對代價增加微小擾動來保證算法的執行效率，而代價就是會在小項上引入T。如果事先知道關于T*的階的正確估計，那么就可以精細地計算擾動值來滿足要求(3)。
付費5元查看完整內容
相關內容
Setting the Variance of Multi-Agent Policy Gradients
策略梯度方法是常見的強化學習方法之一，其中基線函數通常用于減少梯度估計的方差。在多智能體強化學習中，雖然策略梯度定理可直接被擴展使用，但隨著梯度估計的方差隨著智能體數量的增加而迅速增加，多智能體策略梯度方法的性能會逐漸惡化。本文中，我們首先通過量化智能體數量及各智能體探索對多智能體策略梯度估計方差的貢獻，對策略梯度方法進行了嚴格的分析。基于此分析，可獲得實現最小方差的最佳基線函數。進而我們測量了現有多智能體強化學習算法如vanilla MAPG和COMA的過量方差。考慮到現有方法大多使用深度神經網絡，為此我們提出了可以直接與現有多智能體強化學習策略梯度方法相兼容的代理最優基線函數。在多智能體MuJoCo和星際爭霸基線任務上，所提方法有效地穩定了訓練過程，并顯著提高了MAPPO和COMA算法的性能。
付費5元查看完整內容
元學習理論的一個關鍵問題是如何理解任務分布對遷移風險的影響，即從未知任務分布中得出的元學習器對新任務的預期錯誤。本文針對高斯噪聲和高斯任務(或參數)分布的固定設計線性回歸問題，給出了任意算法的分布相關的遷移風險下界，同時給出了一種新的，所謂的偏置正則化回歸方法的加權版本能夠將這些下界匹配到一個固定的常數因子。值得注意的是，權重是由高斯任務分布的協方差得到的。總之，我們的結果提供了在這種高斯設置下元學習的困難的精確表征。雖然這個問題設置可能看起來很簡單，但我們證明它足夠豐富，可以統一元學習的“參數共享”和“表示學習”流; 特別地，表示學習是作為任務分布的協方差矩陣未知的特殊情況得到的。在這種情況下，我們提出采用EM方法，這在我們的情況下顯示了有效的更新。本文通過對EM的實證研究完成，實驗結果表明，EM算法可以隨著任務數量的增加而達到下界，同時在表示學習環境中，該算法也能成功地與其他算法相媲美。
付費5元查看完整內容
對抗訓練是提高模型對抗擾動魯棒性的最有效技術之一。然而，這種方法對模型的全部影響還沒有被很好地理解。例如，雖然對抗訓練可以減少對抗風險(針對對手的預測錯誤)，但它有時會增加標準風險(沒有對手時的泛化錯誤)。在本文中，我們關注于分布擾動對手框架，其中對手可以改變訓練數據分布的鄰域內的測試分布。鄰域是通過分布之間的Wasserstein距離定義的，鄰域的半徑是對手操縱能力的度量。我們研究了標準風險和對抗風險之間的權衡，并推導了在特征維數不變的無限數據限制下，在特定類型的模型上可實現的Pareto最優權衡。我們考慮了三種學習設置:1) 線性模型類的回歸; 2) 二元分類下的高斯混合數據模型，用線性分類器分類; 3)用一類隨機特征模型進行回歸(可等效表示為第一層權值為隨機的兩層神經網絡)。我們表明，標準風險和對抗性風險之間的權衡在所有三種情況下都得到了體現。我們進一步描述了Pareto最優權衡曲線，并討論了各種因素，如特征相關性、對手的力量或兩層神經網絡的寬度會如何影響這種權衡。
付費5元查看完整內容
深度學習的成功依賴大規模的標記數據，然而人工標注數據的代價巨大。域自適應（Domain Adaptation）意圖利用已有源領域標記數據的有效信息學習得到一個可以泛化到目標領域無標記數據上的模型。因此域自適應方法是解決上述問題的方案之一。回歸問題作為一個具有廣泛應用的機器學習范式，和分類問題具備同等的重要性。然而，當前的研究缺乏一個針對回歸問題的深度無監督域自適應方法：（1）已有很多基于實例加權和域不變表征學習的淺層域自適應回歸方法，但他們沒有辦法利用深度網絡的表征學習能力，因此不具備處理現實世界多種復雜結構數據的能力。同時，他們往往依賴目標領域中的少量有標數據才能取得理想的性能，即只能做成半監督域自適應方法；（2）已有很多基于深度表征學習的域自適應分類方法，在分類基準數據集上取得了突破性進展，但他們在回歸數據集上的表現往往不夠理想。因此，本文意在利用深度網絡的表征能力，考慮回歸問題的本質特點，提出一種適用于回歸問題的無監督可遷移域自適應方法。
付費5元查看完整內容
多智能體學習
·
探索 - 利用（exploration-exploitation）是多智能體學習（MAL）中強大而實用的工具，但其效果遠未得到理解。為了探索這個目標，這篇論文研究了 Q 學習的平滑模擬。首先，研究者認為其學習模型是學習「探索 - 利用」的最佳模型，并提供了強大的理論依據。具體而言，該研究證明了平滑的 Q 學習在任意博弈中對于成本模型有 bounded regret，該成本模型能夠明確捕獲博弈和探索成本之間的平衡，并且始終收斂至量化響應均衡（QRE）集，即有限理性下博弈的標準解概念，適用于具有異構學習智能體的加權潛在博弈。
該研究的主要任務轉向衡量「探索」對集體系統性能的影響。研究者在低維 MAL 系統中表征 QRE 表面的幾何形狀，并將該研究的發現與突變（分歧）理論聯系起來。具體而言，隨著探索超參數隨著時間的演化，系統會經歷相變。在此過程中，給定探索參數的無窮小變化，均衡的數量和穩定性可能會發生劇烈變化。在此基礎上，該研究提供了一種形式理論處理方法，即如何調整探索參數能夠可驗證地產生均衡選擇，同時對系統性能帶來積極和消極（以及可能無限）的影響。
//www.zhuanzhi.ai/paper/58dfd45f8af99a926fb48199e1447e9a
付費5元查看完整內容
最佳論文獎
1. No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
地址： //www.zhuanzhi.ai/paper/1cede84d4fe70b6f36d5df9acb3076e7
獲獎理由：
人們的決定會影響到他人。為了保證合理的行事方式，我們需要通過這種「相互依賴」達到經濟學家所說的「均衡」（equilibrium）。創建能夠找出均衡點的自動程序是非常困難的任務。這篇論文提供了首個解決方法——利用學習方法為通用交互尋找「相關均衡」（correlated equilibria，CE）。
相關均衡要求一個受信任的外部調停者為決策者提供決策建議，典型案例就是紅綠燈，紅綠燈告訴車輛前進這一行為是否安全。即使在相關法律缺失的情況下，我們仍然應該遵循紅綠燈的推薦結果，因為我們知道每個人都可以推斷出這是最好的選擇，闖紅燈是危險的行為。
這篇論文表明，此類均衡可以通過完全獨立執行的學習算法來實現，無需外部交通工程師，甚至在決策涉及多個步驟、決策者對于世界的狀態一知半解時也是如此。也就是說，存在此類 regret-minimizing 算法使 CE 在更廣泛的博弈類別中實現收斂，即擴展形式的博弈。這一結果解決了博弈論、計算機科學和經濟學領域中長期存在的開放性問題，并對涉及調停者的博弈產生顯著影響，如通過導航 app 高效制定交通路線。
2. Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method
獲獎理由：
從大型矩陣中選擇小規模且具代表性的列向量子集是一個困難的組合問題，基于基數約束行列式點過程的方法可以給出實用的近似解。這篇論文推導出近似解近似因子的新型上下界。由于這些近似方法在機器學習領域中廣泛應用，因此這篇論文可能帶來巨大影響，并為核方法、特征選擇和神經網絡的雙下降現象提供新的理解方式。
隨著更多大型數據集變得可用，人們越來越依賴以簡明扼要的形式總結復雜數據。數據總結（data summarization）是識別數據中重要的樣例及屬性以高效表示數據的過程。它能夠用于從遺傳學數據集中選擇具有代表性的基因變體子集，也可用于從文本數據庫中選擇最具信息量的文檔。
此前的研究表明，數據總結是一個棘手的問題，對于有些數據集，不存在能夠在合理的時間范圍內很好地總結數據的算法。而這篇論文表明，這些分析過于悲觀。實際上，對于現實世界中的數據而言，生成可解釋總結的成本要低得多。該研究表明，未來的系統將能夠創建準確、可解釋且高效生成的數據總結，從而極大地提高我們吸收和處理復雜數據集的能力。
3. Language Models are Few-Shot Learners
獲獎理由：
用于估計序列中下一個詞概率的人工智能系統叫做「語言模型」。語言模型首次出現在 1950 年代，是連接自然語言與當時的新領域——信息論的理論構架。OpenAI 的這篇論文提出了 GPT-3——有史以來最大也最復雜的語言模型。這項研究表明，如果你使用史無前例的大量算力和數據讓語言模型獲得足夠的準確率，它也就獲得了無需額外訓練，僅使用簡單的自然語言提示即可解決大量任務的能力。比如回答簡單的問題、生成文章、確定電影評論是否積極，以及英法互譯等。
論文作者表明，GPT-3 在一些任務中的能力勝過其他模型，并用大量篇幅探討這項技術的優缺點。論文作者還考慮了這項技術的潛在有害影響，如低成本生成難以檢測的假新聞，模型因訓練數據偏見在種族、性別和宗教等敏感話題上產生傾向性。
付費5元查看完整內容
機器學習中部分非凸和隨機優化算法研究
機器學習是一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、算 法復雜度理論等多門學科。算法理論與應用是機器學習中最為重要的核心之一。其中一階優化算法因其簡單有效性，而被廣泛研究與應用。另一方面由于近年來 數據規模的不斷增大，數據集的規模使得二階或更高階的算法應用受阻。這使得 一階算法進一步成為機器學習的研究重點。隨著機器學習中問題模型的不斷擴張， 例如深度學習，非凸問題和模型也激發了學者們廣泛的研究興趣。這使得研究非 凸算法顯得更加急迫。而且由于數據集的龐大性，確定算法難以逃出鞍點，因此 隨機算法受到了史無前例的關注。本文主要結果可以歸納如下：
一、研究了三種 ADMM 算法。第一個 ADMM 的工作是關于一般的 ADMM 收 斂性分析統一框架。在此框架下，很多現有的 ADMM 收斂性分析可以歸納進該 框架。除了現有的 ADMM 算法，根據統一框架還能夠設計出新的 ADMM 算法。第二個和第三個 ADMM 都是針對結構非凸優化問題提出的：一個是針對泛 ?q 正 則化約束優化問題，而另一個是針對 ?1?2 正則化約束優化。給出了后面兩種非凸 ADMM 算法的收斂性分析，所得到的結果可以指導用戶選擇合適的超參數。
二、研究了兩種一階優化領域常用的非精確算法。第一種是非精確的加速算 法。相較于之前的研究，該算法的假設更為真實。而且還囊括了一大類隨機噪聲 的情況，使得算法更為實用。而機器學習中的一階催化劑算法由于是該加速算法 帶上了隨機噪聲，因此可以看做本算法的特例。在第二部分給出了非精確非凸算 法的收斂性框架理論。可以被廣泛應用到各種一階非凸算法。
三、證明了在有界和無界延遲以及隨機和確定性塊選擇下異步并行梯度下降法 的收斂結果。這些結果不需要迄今為止絕大多數其他工作中出現的獨立性假設。這是由于本文使用了 Lyapunov 函數技術，可直接處理延遲，而不是像之前的工作 一樣僅僅將它們建模為噪聲。
四、分析了馬爾可夫鏈隨機梯度下降法，其中樣本采用了某個馬爾可夫鏈的軌跡。主要貢獻之一是給出了馬爾可夫鏈隨機梯度下降法的在凸情況下的非遍歷收 斂分析。結果然后擴展到不精確的格式。這種分析使得能夠建立不可逆有限狀態 馬爾可夫鏈和非凸最小化問題的收斂性。這樣的結果適用于不知道具體的概率分 布，但可以通過馬爾可夫鏈進行采樣的情形。
付費5元查看完整內容
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191