許多解決組合優化問題的傳統算法都涉及使用手工構造的啟發式算法,這些啟發式算法能夠依次地構造解決方案。這種啟發式方法是由領域專家設計的,且一般由于問題的困難性,這種方法不是最佳的。強化學習(RL)提出了一種很好的選擇,使用監督或自我監督的方式訓練 agent 來自動搜索這些啟發式方法。
在這篇調研中,我們探索了將 RL 框架應用于困難的組合問題的最新進展。我們的調研為運籌學和機器學習社區提供了必要的背景,并展示了推動領域向前發展的工作。我們將最近提出的 RL 方法并置在一起,列出了每個問題改進方法的時間線,并與傳統算法進行了比較,這表明 RL 模型可以成為解決組合問題的有希望的方向。
論文標題:Reinforcement Learning for Combinatorial Optimization: A Survey
論文作者:Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev
《強化學習和隨機優化:序列決策的統一框架》是一本新書,它提供了一個統一框架,涵蓋了所有在不確定性下進行決策的社區(見jungle.princeton.edu)。這是第一本全面介紹這些領域的書,遵循了確定性優化和機器學習(但不是隨機優化)中長期使用的風格。
第一部分提供了基礎材料,其中大部分可以略讀。第1章提供了通用建模框架的概述,該框架涵蓋了任何序列決策問題,最困難的挑戰(對于大多數問題)是策略的設計。第1章提供了跨越任何可能被設計的策略的四類策略路線圖的早期草圖。第2章總結了每個社區的規范化建模框架,這些框架使用了該字段的符號來處理某種形式的序列決策問題。對這一領域完全陌生的讀者可以略讀這一章,了解已經采用的各種方法。有深度的讀者將在這些規范問題中的一個或多個方面有一定程度的專業知識,這將有助于在該問題和我們的框架之間提供一座橋梁。最后,第三章深入探討了在線學習。本章應該略讀,然后在需要時作為參考資料使用。
第二部分-隨機搜索-這些是隨機優化問題,可以使用自適應算法解決,其中唯一的信息鏈接迭代是關于函數的信念。我們還將這些狀態獨立函數稱為狀態獨立函數,以區別于我們在第三部分中開始處理的更一般的狀態依賴函數。
第三部分-狀態相關問題-這里我們過渡到更豐富的序列問題類,其中被優化的函數是狀態相關的。
第四部分-策略搜索-這些章節描述了必須調整的策略,無論是在模擬器中還是通過經驗。
第五部分-基于前瞻近似的策略-基于前瞻近似的策略是策略搜索派生的策略的對應。
第六部分-多智能體系統和學習-最后我們展示了如何擴展我們的框架來處理多智能體系統。
目錄內容:
Chapter 1 – Introduction
Chapter 2 – Canonical models and applications .
Chapter 3 – Online learning- Revised from ADP book
Chapter 4 – Introduction to stochastic search
Chapter 5 – Derivative-based stochastic optimization
Chapter 6 – Stepsize policies
Chapter 7 – Derivative-free stochastic optimization
Chapter 8 – State-dependent problems
Chapter 9 – Modeling sequential decision problems
Chapter 10 – Uncertainty modeling
Chapter 11 – Designing policies
Chapter 12 – Policy function approximations and policy search
Chapter 13 – Cost function approximations
Chapter 14 – Discrete Markov decision processes
Chapter 15 – Backward approximate dynamic programming
Chapter 16 – Forward ADP I: The value of a policy
Chapter 17 – Forward ADP II: Policy optimization
Chapter 18 – Forward ADP III: Convex functions
Chapter 19 – Direct lookahead policies
Chapter 20 – POMDPs, two-agent systems, and multiagent RL
組合優化問題廣泛存在于國防、交通、工業、生活等各個領域, 幾十年來, 傳統運籌優化方法是解決組合優化問題的主要手段, 但隨著實際應用中問題規模的不斷擴大、求解實時性的要求越來越高, 傳統運籌優化算法面臨著很大的計算壓力, 很難實現組合優化問題的在線求解. 近年來隨著深度學習技術的迅猛發展, 深度強化學習在圍棋、機器人等領域的矚目成果顯示了其強大的學習能力與序貫決策能力. 鑒于此, 近年來涌現出了多個利用深度強化學習方法解決組合優化問題的新方法, 具有求解速度快、模型泛化能力強的優勢, 為組合優化問題的求解提供了一種全新的思路. 因此本文總結回顧近些年利用深度強化學習方法解決組合優化問題的相關理論方法與應用研究, 對其基本原理、相關方法、應用研究進行總結和綜述, 并指出未來該方向亟待解決的若干問題.
摘要
本文綜述了遷移學習在強化學習問題設置中的應用。RL已經成為序列決策問題的關鍵的解決方案。隨著RL在各個領域的快速發展。包括機器人技術和游戲,遷移學習是通過利用和遷移外部專業知識來促進學習過程來幫助RL的一項重要技術。在這篇綜述中,我們回顧了在RL領域中遷移學習的中心問題,提供了一個最先進技術的系統分類。我們分析他們的目標,方法,應用,以及在RL框架下這些遷移學習技術將是可接近的。本文從RL的角度探討了遷移學習與其他相關話題的關系,并探討了RL遷移學習的潛在挑戰和未來發展方向。
關鍵詞:遷移學習,強化學習,綜述,機器學習
介紹
強化學習(RL)被認為是解決連續決策任務的一種有效方法,在這種方法中,學習主體通過與環境相互作用,通過[1]來提高其性能。源于控制論并在計算機科學領域蓬勃發展的RL已被廣泛應用于學術界和工業界,以解決以前難以解決的任務。此外,隨著深度學習的快速發展,應用深度學習服務于學習任務的集成框架在近年來得到了廣泛的研究和發展。DL和RL的組合結構稱為深度強化學習[2](Deep Reinforcement Learning, DRL)。
DRL在機器人控制[3]、[4]、玩[5]游戲等領域取得了巨大的成功。在醫療保健系統[6]、電網[7]、智能交通系統[8]、[9]等領域也具有廣闊的應用前景。
在這些快速發展的同時,DRL也面臨著挑戰。在許多強化學習應用中,環境模型通常是未知的,只有收集到足夠的交互經驗,agent才能利用其對環境的知識來改進其性能。由于環境反饋的部分可觀察性、稀疏性或延遲性以及高維觀察和/或行動空間等問題,學習主體在沒有利用任何先驗知識的情況下尋找好的策略是非常耗時的。因此,遷移學習作為一種利用外部專業知識來加速學習過程的技術,在強化學習中成為一個重要的課題。
在監督學習(SL)領域[10]中,TL得到了廣泛的研究。與SL場景相比,由于MDP環境中涉及的組件更多,RL中的TL(尤其是DRL中的TL)通常更復雜。MDP的組件(知識來自何處)可能與知識轉移到何處不同。此外,專家知識也可以采取不同的形式,以不同的方式轉移,特別是在深度神經網絡的幫助下。隨著DRL的快速發展,以前總結用于RL的TL方法的努力沒有包括DRL的最新發展。注意到所有這些不同的角度和可能性,我們全面總結了在深度強化學習(TL in DRL)領域遷移學習的最新進展。我們將把它們分成不同的子主題,回顧每個主題的理論和應用,并找出它們之間的聯系。
本綜述的其余部分組織如下:在第2節中,我們介紹了強化學習的背景,關鍵的DRL算法,并帶來了這篇綜述中使用的重要術語。我們還簡要介紹了與TL不同但又緊密相關的相關研究領域(第2.3節)。
在第3節中,我們采用多種視角來評價TL方法,提供了對這些方法進行分類的不同方法(第3.1節),討論了遷移源和目標之間的潛在差異(第3.2節),并總結了評價TL有效性的常用指標(第3.3節)。
第4節詳細說明了DRL領域中最新的TL方法。特別是,所討論的內容主要是按照遷移知識的形式組織的,如成型的獎勵(4.1節)、先前的演示(4.2節)、專家策略(4.3節),或者按照轉移發生的方式組織的,如任務間映射(4.4節)、學習可轉移表示(4.5節和4.6節)等。我們在第5節討論了TL在DRL中的應用,并在第6節提供了一些值得研究的未來展望。
神經網絡在諸多應用領域展現了巨大的潛力,成為當前最熱門的研究方向之一。神經網絡的訓練主要通過求解一個優化問題來完成,但這是一個困難的非線性優化問題,傳統的優化理論難以直接應用。在神經網絡和優化的交叉領域,長期以來研究人員積累了大量的理論研究知識,不過這些研究或過于理論而不被大部分實踐者所了解,或過于偏工程而不被理論學者所理解和欣賞。本文的目的是總結目前對于神經網絡優化基本理論和算法的現狀,架起理論和實踐、優化和機器學習界之間的橋梁。
對苦于調參常感到困惑的工程師而言,本文可以提供一些已有的理論理解以供參考,并提供一些思考的方式。對理論學者而言,本文力圖解釋其作為數學問題的困難之所在以及目前的理論進展,以期吸引更多研究者投身神經網絡優化理論和算法研究。
本文概述了神經網絡的算法和優化理論。首先,我們討論梯度爆炸/消失問題和更一般的譜控制問題,然后討論實際中常用的解決方案,包括初始化方法和歸一化方法。其次,我們回顧用于訓練神經網絡的一般優化方法,如SGD、自適應梯度方法和大規模分布式訓練方法,以及這些算法的現有理論結果。第三,我們回顧了最近關于神經網絡訓練的全局問題的研究,包括局部極值、模式連接、彩票假設和無限寬度分析等方面的結果。
圖在許多應用中被廣泛用于表示復雜數據,如電子商務、社交網絡和生物信息學。高效、有效地分析圖數據對于基于圖的應用程序非常重要。然而,大多數圖分析任務是組合優化(CO)問題,這是NP困難。最近的研究集中在使用機器學習(ML)解決基于圖CO問題的潛力上。使用基于ML的CO方法,一個圖必須用數值向量表示,這被稱為圖嵌入。在這個調查中,我們提供了一個全面的概述,最近的圖嵌入方法已經被用來解決CO問題。大多數圖嵌入方法有兩個階段:圖預處理和ML模型學習。本文從圖預處理任務和ML模型的角度對圖嵌入工作進行分類。此外,本文還總結了利用圖嵌入的基于圖的CO方法。特別是,圖嵌入可以被用作分類技術的一部分,也可以與搜索方法相結合來尋找CO問題的解決方案。最后對未來的研究方向做了一些評論。
低秩稀疏矩陣優化問題是一類帶有組合性質的非凸非光滑優化問題. 由于零模與秩函數 的重要性和特殊性, 這類 NP-難矩陣優化問題的模型與算法研究在過去?幾年里取得了長足發 展. 本文從稀疏矩陣優化問題、低秩矩陣優化問題、低秩加稀疏矩陣優化問題、以及低秩張量 優化問題四個方面來綜述其研究現狀; 其中, 對稀疏矩陣優化問題, 主要以稀疏逆協方差矩陣估 計和列稀疏矩陣優化問題為典例進行概述, 而對低秩矩陣優化問題, 主要從凸松弛和因子分解 法兩個角度來概述秩約束優化和秩 (正則) 極小化問題的模型與算法研究. 最后,總結了低秩 稀疏矩陣優化研究中的一些關鍵與挑戰問題, 并提出了一些可以探討的問題。
深度強化學習(deep reinforcement learning, DRL)方法在經濟學中的普及度呈指數級增長。DRL通過從增強學習(RL)到深度學習(DL)的廣泛功能,為處理復雜的動態業務環境提供了巨大的機會。DRL的特點是可擴展性,有可能應用于高維問題,并結合經濟數據的噪聲和非線性模式。本文首先對DL、RL和深度RL方法在經濟學中不同應用的簡要回顧,提供了對現有技術的深入了解。此外,為了突出DRL的復雜性、魯棒性、準確性、性能、計算任務、風險約束和盈利能力,還研究了DRL在經濟應用中的體系結構。調查結果表明,與傳統算法相比,DRL在面臨風險參數和不確定性不斷增加的現實經濟問題時,可以提供更好的性能和更高的精度。
【簡介】隨著深度表示學習的發展,強化學習(RL)已經成為了一個強大的學習框架,其可以在高維度空間中學習復雜的規則。這篇綜述總結了深度強化學習(DRL)算法,提供了采用強化學習的自動駕駛任務的分類方法,重點介紹了算法上的關鍵挑戰和在現實世界中將強化學習部署在自動駕駛方面的作用,以及最終評估,測試和加強強化學習和模仿學習健壯性的現有解決方案。
論文鏈接: //arxiv.org/abs/2002.00444
介紹:
自動駕駛(AD)系統由多個感知級任務組成,由于采用了深度學習架構,這些任務現在已經達到了很高的精度。除了感知任務之外,自主駕駛系統還包含多個其他任務,傳統的監督學習方法已經不再適用。首先,當對agent行為的預測發生變化時,從自動駕駛agent所處的環境中接收到的未來傳感器觀察到的結果,例如獲取市區最佳駕駛速度的任務。其次,監督信號(如碰撞時間(TTC),相對于agent最佳軌跡的側向誤差)表示agent的動態變化以及環境中的不確定性。這些問題都需要定義隨機損失函數來使其最大化。最后,agent需要學習當前環境新的配置參數,預測其所處的環境中每一時刻的最優決策。這表明在觀察agent和其所處環境的情況下,一個高維度的空間能夠給出大量唯一的配置參數。在這些場景中,我們的目標是解決一個連續決策的問題。在這篇綜述中,我們將介紹強化學習的概念,強化學習是一種很有前景的解決方案和任務分類方法,特別是在驅動策略、預測感知、路徑規劃以及低層控制器設計等領域。我們還重點回顧了強化學習在自動駕駛領域當中各種現實的應用。最后,我們通過闡述應用當前諸如模仿學習和Q學習等強化學習算法時所面臨的算力挑戰和風險來激勵使用者對強化學習作出改進。
章節目錄:
section2: 介紹一個典型的自動駕駛系統及其各個組件。
section3: 對深度強化學習進行介紹,并簡要討論關鍵概念。
section4: 探討在強化學習基本框架上對其進行更深層次,更加復雜的擴展。
section5: 對強化學習用于自動駕駛領域的所面臨的問題提供一個概述。
section6: 介紹將強化學習部署到真實世界自動駕駛系統中所面臨的挑戰。
section7: 總結