快速增長的現實世界網絡，擁有數十億個頂點，需要可擴展的、快速的和高效的圖算法。幸運的是，商業化的多核、多處理器和多機環境可以處理如此大量的數據。不幸的是，盡管有這樣的資源，許多目前的圖算法并沒有充分利用這些并行和分布式環境，或者有非最佳的理論保證，在實踐中轉化為更慢和更不有效的算法。本論文的目的是在理論上改進現代機器中以前的圖算法。我們通過實驗證明，這種理論上的改進也會轉化為實際的收益。

為了實現這一目標，本論文采取了雙管齊下的方法。首先，我們在模仿大規模數據處理環境的計算模型中制定算法。這種模型中的算法利用了機器集群和一個機器的多個核和處理器的優勢。第二，我們在設計算法時使用了現實世界網絡的特殊屬性。退化就是這樣一個特性；雖然一個網絡可能有數十億個頂點，但其退化可能只有幾百個。

本論文由三部分組成。

第一部分介紹了靜態圖算法。我們首先介紹了一套新的編輯算法，該框架通過將圖編輯成所需的結構化類別，針對難以解決的優化問題來逼近其解決方案。然后，我們提出了新的小子圖計數算法，在大規模并行計算模型中具有更好的理論空間和回合保證；我們的實驗證實了我們的理論成果，并顯示在現實世界的圖中，與以前的最先進的算法相比，回合數和近似系數都有所改善。在這一部分的最后，我們提出了一個近乎線性的時間調度算法，用于在具有通信延遲的相同機器上進行調度，其中優先權受限的工作被建模為有向無環圖。

第二部分主要討論動態圖算法。我們首先展示了一個??(1)的攤銷時間，高概率的(?+1)-頂點著色的動態算法。然后，我們為批量動態更新下的??核分解問題提供了一個新的并行級數據結構（其中動態邊緣更新是分批進行的）。我們表明，我們的數據結構可以證明對每個頂點的核心性提供了(2+??)的近似值，改進了以前已知的(4+??)的最佳約束。最后，我們提出了新的三角形和團計數的并行、高效批處理動態算法。我們對批處理動態算法的廣泛實驗，結果表明，在現實世界的網絡中，我們的性能比以前最好的多核算法實現了數量級的提高。

最后一部分是關于下限的結論。我們通過硬實例展示了在外部存儲器模型中，在有向無環計算圖上獲得最優計算時間表的困難性。然后，我們證明這種圖可以用來構建靜態-內存-硬哈希函數，使用磁盤內存來阻止大規模密碼破解攻擊。

摘要

強化學習是一種為需要做出一系列決定的任務制定最佳策略的方法。以平衡短期和長期結果的方式做出決定的能力，使強化學習成為醫療機構中規劃治療的潛在強大工具。不幸的是，傳統的強化學習算法需要對環境進行隨機實驗，這在醫療衛生領域通常是不可能的。然而，強化學習提供了從觀察數據中評估策略的工具，這是一個被稱為離策略評估的子項目。

在這項工作中，我們討論了離策略評估在應用于醫療數據時變得如此困難的主要挑戰，并設計了一些算法來改進目前執行離策略評估的方法。我們描述了幾種改進現有方法的準確性和統計能力的算法，最后介紹了一種新的方法，通過開發一種將專家臨床醫生及其知識納入評價過程的評價技術來提高離策略評估方法的可靠性。

簡介

強化學習(RL)是機器學習(ML)中的一個子領域，它為學習需要平衡短期和長期結果的任務中的連續決策策略提供了一個框架。RL的關鍵范式是將學習算法視為一個與環境互動的智能體，采取行動并觀察環境對這些行動的變化。通過與環境的不斷互動和實驗，智能體學會了實現預期目標的最佳策略。這個強大的想法促進了RL算法在廣泛的應用中的成功，如游戲和機器人。

然而，在這些應用中，與環境的隨機互動--使RL如此強大的關鍵特性--是不可能的。例如，在醫療保健中，隨機治療病人并觀察其反應是不道德的。

從批量觀察數據中評估RL決策的任務被稱為離策略評估（OPE），這個術語用來表示用于收集數據的策略與我們希望評估的策略不同。OPE只關注評估一個特定的策略，而不是學習一個最優的onc，這是大多數RL應用的目標。

這項工作的動力來自于這樣的認識：盡管在OPE方面取得了重大的理論突破，但目前的方法仍然遠遠不夠可靠，無法證明其在實際應用中的使用和部署。這些限制在醫療保健領域尤為突出，因為那里的數據非常嘈雜，而且錯誤的代價很高。 我們首先強調了使OPE在觀察性醫療環境中如此困難的關鍵因素，并展示了這些算法可能失敗的主要方式。然后，我們描述了幾種改善OPE算法性能的方法。這些方法可以應用于所有RL領域，但我們在醫療數據中經常遇到的具體特征是其強大的動力。

雖然這項工作中所描述的方法有助于提高OPE方法的性能，但它們基本上都試圖從數據中提取出更多的統計能力。不幸的是，僅從數據中提取出的知識是有限的，而且往往我們所能做的最好的也是不夠好。 然而，試圖僅從原始數據中獲得知識，卻忽視了臨床醫生和其他醫療專家所擁有的大量知識和專長。在這項工作的最后一部分，我們將論證，為了使OPE的性能足夠好，使其能夠被信任并用于醫療領域，領域專家必須被納入評估過程。為了能夠在OPE中使用領域專家，必須開發新的方法，使幾乎總是不熟悉RL和OPE技術細節的臨床醫生能夠有效地提供對OPE過程有用的意見。我們將在這個方向上邁出一步，描述一種方法，使臨床醫生能夠隨意地識別OPE方法何時可能給出不可靠的結果，并討論發展這一研究途徑的未來方向。

總而言之，這項工作應該概述了OPE在醫療領域的狀況，以及將其引入現實世界所必須做出的努力--從詳細說明當前方法可能失敗的方式和解決這些問題的可能方法，到描述臨床醫生可以被納入評估過程的方式。本論文的其余部分的結構如下：本章的其余部分介紹了本論文將使用的基本符號，并涵蓋了相關文獻。 第三章繼續討論基于模型的OPE，并介紹了一種建立模型的方法，該方法的訓練強調從評估策略下可能出現的例子中學習，并沿用了Liu等人的工作。最后，在第四章中，我們討論了如何利用臨床醫生的輸入來調試和驗證OPE的結果，沿用了Gottesman等人的方法。

** Oleksandr Shchur**

柏林AWS AI的一名應用科學家，我在那里研究AutoGluon。目前我的研究方向是時間序列預測和AutoML。 我在慕尼黑工業大學(Technical University of Munich)攻讀機器學習博士學位，導師是Stephan Günnemann。在讀博士期間，我主要研究時間點過程(TPPs)——連續時間事件序列的概率模型，如社交媒體上的用戶活動或地震學中的地震序列。

Modeling Continuous-time Event Data with Neural Temporal Point Processes

事件數據是機器學習許多高影響力應用的核心。電子健康記錄中的醫院訪問，地震學中的地震目錄，以及神經科學中的高峰列車——所有這些都可以用連續時間中可變長度的事件序列來表示。時間點流程(TPPs)為此類數據建模提供了一個自然的框架。然而，傳統的TPP模型缺乏捕捉現實事件數據中呈現的復雜模式的能力。神經TPP旨在通過將神經網絡與點過程文獻中的基本思想相結合來解決這一限制。本論文的兩個主要主題是(1) 設計靈活、可處理和高效的神經TPP模型，(2)它們在現實問題中的應用。我們的第一個貢獻是TPP和神經密度估計領域之間的聯系。這使得我們能夠開發第一個神經TPP模型，其中的可能性計算、采樣和預測都可以以封閉的形式有效地完成。接下來，我們提出了TriTPP——一種新的表達性TPP模型，與現有方法不同，該模型中所有操作都可以并行完成。快速平行采樣為TPP模式開啟了新的應用。我們通過推導連續時間離散狀態系統的變分推斷方案來證明這一點。最后，我們將擬合優度測試方法與神經TPP模型相結合，建立了一種簡單有效的事件序列異常檢測方法。

金融交易、在線交流、神經突列、地震——各種人為和自然現象都可以用連續時間的事件序列來表示。這種事件數據的概率模型被稱為時間點過程(TPP)，可以用來進行預測，找到模式，并更好地理解各自的現實世界系統。TPPs理論是在20世紀Feller [56,58]， Cox [35,38]， Lewis [105,106]， Hawkes[79]和Ogata[133,134]的開創性著作中發展起來的。由于事件數據的普遍性，TPPs被廣泛應用于地震[82,135]和神經科學[46,68]等科學領域，以及金融[9,80]和醫療[3,56]等行業。

在過去的幾十年里，在實際應用中遇到的事件數據的規模和復雜性都出現了爆炸式增長。地震學的新技術能夠收集數以百萬計的地震的豐富多樣的數據集[126,192]。像Twitter和Facebook這樣的在線服務以前所未有的規模捕捉社交互動，而AWS這樣的托管提供商每天產生PB級的數據[165]。分析這些數據可以釋放出巨大的價值。然而，傳統的TPP模型，如泊松過程或自激過程，無法捕捉這些數據中呈現的復雜模式。此外，事件序列通常伴隨著與預測任務相關的附加屬性(例如，位置)，但將它們納入傳統的TPP需要繁瑣的特征工程。處理這些問題需要開發新的TPP模型，該模型具有表示復雜模式的靈活性，并具有足夠的可擴展性，以處理大型多樣化的數據集。

近年來，被稱為神經TPPs的一類新模型出現，以應對上述挑戰[170]。神經TPP將點過程理論的基本思想與深度學習方法相結合。深度學習方法基于神經網絡——通過可微變換組合定義的表達函數逼近器[72]。基于神經網絡的方法大大提高了計算機視覺[101,186]、自然語言處理[23,48]、圖機器學習[212]和許多其他領域的性能。在本文中，我們研究了深度學習在連續時間事件數據中的應用。

在神經TPPs環境中，神經網絡的靈活性允許我們從數據中自動學習事件發生的不同模式，而不是像傳統模型那樣手動指定它們。例如，在一個自激過程中，觀察到的事件只能增加未來事件的到達率——這是一個相當有限的假設，在許多現實世界的事件數據集中不成立(例如，大腦中的抑制性神經元降低了放電率[46])。相比之下，神經TPP模型可以通過純數據驅動的方式自動學習不同事件類型的抑制和興奮效應。2016年，Du等人[52]和Mei & Eisner[119]的開創性工作首次展示了TPP與神經網絡相結合帶來的新可能性。隨后，許多論文提出了神經TPP的新模型架構和參數估計算法[95,108,181,198-200]。然而，基于深度學習的TPP模式的設計和應用仍存在許多懸而未決的問題。

神經跨TPP模型應該滿足許多要求，以成功地應用于現實世界的任務。此類模型的表達性、可處理性、高效訓練和推理往往相互矛盾，現有的神經TPP架構在這些屬性之間做出了次優權衡。在論文的第一部分，我們關注了TPP模式設計的這些方面，并將其作為我們的第一個研究問題:

研究問題1:我們如何定義靈活的神經TPP模型，同時可處理和高效?

我們首先回顧了概率建模和深度學習的基礎知識，并在第2章中從機器學習的角度對TPP進行了獨立的介紹。在第三章中，我們討論了現有神經TPP模型的局限性，并引入了一類新的模型來解決這些缺點。通過與神經密度估計領域的聯系，我們構建了靈活的神經TPP，其中似然計算和采樣都可以解析地完成。與現有的方法相比，這是一個重大的改進，沒有一種方法同時滿足所有這些標準。接下來，在第4章中，我們將采取不同的路徑，并展示如何通過三角形地圖的視角來看待所有的TPP。基于這一見解，我們提出了TriTPP——一種基于可逆變換組成的靈活高效的TPP參數化方法。現代的TPP架構通常使用自回歸神經網絡(例如，rnn和變壓器)，因此具有內在的順序性。相比之下，在TriTPP中，采樣和訓練可以并行進行，這大大提高了效率。此外，重新參數化的高效采樣為TPP提供了新的應用。這就直接引出了我們的第二個研究問題:

研究問題2: 我們如何應用神經TPP來解決現實世界的問題?

在第5章中，我們展示了重新參數化技巧如何讓我們有效地訓練基于抽樣損失的TPP模型。TPP的這種損失函數通常是不連續的，這使得用基于梯度的方法對其進行優化是不可能的。為了解決這一挑戰，我們引入了一個可微松弛的損失，包括變長事件序列。為了展示這種方法的實用性，我們開發了一個連續時間離散狀態系統的變分推斷方案，如馬爾可夫跳躍過程。最后，在第6章中，我們用TPPs處理事件序列的異常檢測。我們演示了如何使用生成模型的擬合優度測試來解決異常檢測問題——針對任意數據類型，而不僅僅是事件序列。我們將該框架與第三章的神經TPP模型相結合，得到了一種簡單有效的異常檢測方法。

現代深度強化學習(RL)算法，盡管處于人工智能能力的最前沿，但通常需要大量的訓練樣本才能達到與人類相當的性能水平。這種嚴重的數據效率低下是深度RL實際應用的主要障礙:在沒有模擬器的情況下，深度RL幾乎不可能應用于任何領域。為了解決這種關鍵數據效率低下的問題，在本論文中，我們致力于設計能夠快速適應新環境的元學習智能體。與標準的強化學習相比，元學習在特定的環境分布上進行學習，從這些環境中采樣特定的任務，并直接優化元學習器，以提高策略改進的速度。通過利用與感興趣任務具有共同子結構的任務分布，元學習器可以調整自己的歸納偏見，使其能夠在測試時快速適應。

本論文的重點是設計元學習算法，利用記憶作為驅動快速適應新環境的主要機制。具有情景間記憶的元學習是一類元學習方法，利用基于特定環境的整個交互歷史的記憶架構來產生策略。因此，在特定任務中驅動策略改進的學習動態被包含在序列模型的計算過程中，本質上把學習算法的設計交給了體系結構。雖然概念簡單，但使用情景間記憶的元學習非常有效，仍然是最先進的方法。我們提出并討論了幾種通過記憶進行元學習的技術。

論文的第一部分集中在“具身”類環境，其中一個主體在一個類似自然世界的環境中有物理表現。我們利用這種高度結構化的環境集來設計具有快速記憶、規劃和狀態推斷能力的整體嵌入式代理體系結構。在論文的第二部分，我們將重點放在沒有強公共子結構的一般環境中應用的方法。首先，我們重新檢查元學習代理與環境的交互模式:提出用一個并行執行框架來取代典型的順序處理交互歷史，其中多個智能體并行地在環境中行動。接下來，我們討論了一個通用的和強大的序列模型的使用片段間存儲器，門控transformer，展示了性能和數據效率的巨大改進。最后，我們開發了一種方法，可以顯著降低(元)強化學習設置中transformer模型的訓練成本和作用延遲，目的是(1)使它們在研究社區中更廣泛地使用，(2)解鎖它們在實時和延遲受限的應用中使用，如機器人。

//www.ml.cmu.edu/research/phd-dissertation-pdfs/eparisot_phd_mld_2021.pdf

摘要

推薦系統已經被廣泛應用于不同的現實生活場景，幫助我們找到有用的信息。近年來，基于強化學習(RL)的推薦系統已經成為一個新興的研究課題。由于其交互性和自主學習能力，它常常超過傳統的推薦模型，甚至是最基于深度學習的方法。然而，在推薦系統中應用RL還面臨著各種挑戰。為此，我們首先對五種典型推薦場景的RL方法進行了全面的概述、比較和總結，以下是三個主要的RL類別: 價值函數、策略搜索和演員-評論員(Actor-Critic)。然后，在現有文獻的基礎上，系統分析了面臨的挑戰和相應的解決方案。最后，通過對RL研究中存在的問題和局限性的討論，指出了該領域潛在的研究方向。

//arxiv.org/abs/2109.10665

引言

個性化推薦系統能夠提供符合用戶喜好的有趣信息，從而有助于緩解信息過載問題。在過去的二十年中，人們對推薦系統進行了廣泛的研究，開發了許多推薦方法。這些方法通常根據用戶的喜好、商品特征和用戶與商品的交互來進行個性化的推薦。一些推薦方法還利用其他附加信息，如用戶之間的社會關系(例如，社會推薦)、時間數據(例如，順序推薦)和位置感知信息(例如，POI(“興趣點”的縮寫)推薦。

推薦技術通常利用各種信息為用戶提供潛在的項目。在現實場景中，推薦系統根據用戶與商品的交互歷史進行商品推薦，然后接收用戶反饋進行進一步推薦。也就是說，推薦系統的目的是通過交互獲取用戶的偏好，并推薦用戶可能感興趣的項目。為此，早期的推薦研究主要集中在開發基于內容和基于協同過濾的方法[2]，[3]。矩陣分解是傳統推薦方法中最具代表性的方法之一。近年來，由于深度學習的快速發展，各種神經推薦方法被開發出來[4]。然而，現有的推薦方法往往忽略了用戶與推薦模型之間的交互。它們不能有效地捕捉到用戶的及時反饋來更新推薦模型，往往導致推薦結果不理想。

一般來說，推薦任務可以建模為這樣一個交互過程——用戶被推薦一個商品，然后為推薦模型提供反饋(例如，跳過、點擊或購買)。在下一次交互中，推薦模型從用戶的顯式/隱式反饋中學習，并向用戶推薦一個新項目。從用戶的角度來看，高效的交互意味著幫助用戶盡快找到準確的商品。從模型的角度看，有必要在推薦的多輪中平衡新穎性、相關性和多樣性。交互式推薦方法已成功應用于現實世界的推薦任務中。然而，該方法經常遇到一些問題，如冷啟動[5]和數據稀疏[6]，以及挑戰，如可解釋性[7]和安全性[8]。

作為一個機器學習領域，強化學習(RL)專注于智能代理如何與環境交互，提供了潛在的解決方案來模擬用戶和代理之間的交互。最近RL的成功推動了人工智能[9]，[10]的研究。特別是，深度強化學習(DRL)[11]具有強大的表示學習和函數逼近特性，可以解決人工智能的挑戰。它已被應用于各個領域，如游戲[12]，機器人[13]，網絡[14]。近年來，應用RL解決推薦問題已成為推薦研究的一個新趨勢。具體來說，RL使推薦代理能夠不斷地與環境(例如，用戶和/或記錄的數據)交互，以學習最佳推薦策略。在實踐中，基于RL的推薦系統已經被應用到許多特定的場景中，如電子商務[18]、電子學習[19]、電影推薦[20]、音樂推薦[21]、新聞推薦[22]、工作技能推薦[23]、醫療保健[24]、能量優化[25]等。

為促進基于RL的推薦系統的研究，本文總結了現有的推薦問題的相關解決方案，系統分析了在推薦方法中應用RL所面臨的挑戰，并探討了未來潛在的研究方向。本文從理論研究的角度，回顧了已有的研究工作，包括環境構建、先驗知識、獎勵函數定義、學習偏差和任務構建。環境建設可以緩解勘探開發的取舍。先驗知識和獎勵定義是進行推薦決策的關鍵。此外，任務結構化可以很好地解決維度的詛咒。從應用的角度，我們還提供了基于RL的推薦系統的全面調研，分別遵循價值函數、策略搜索和演員評論。值得注意[26]的是還提供了對基于RL和drl的推薦算法的回顧，并在推薦列表、架構、可解釋性和評估方面提出了幾個研究方向。[27]主要從基于模型的方法和無模型的算法兩方面對基于drl的推薦系統進行了概述，并重點介紹了基于drl的推薦中一些有待解決的問題和新興的課題。與[26]和[27]不同的是，我們根據其他分類算法(即價值函數、策略搜索和角色-評論)概述了現有的(D)RL推薦方法，并分析了在推薦系統中應用(D)RL的挑戰。

本工作的主要貢獻如下:

• 我們全面回顧了為五種典型推薦方案開發的RL方法。對于每個推薦場景，我們提供了有代表性的模型的詳細描述，總結了文獻中使用的具體RL算法，并進行了必要的比較。

• 我們系統地分析了在推薦系統中應用RL所面臨的挑戰，包括環境構建、先驗知識、獎勵函數定義、學習偏差和任務構建。

• 我們還討論了RL的開放問題，分析了該領域的實際挑戰，并提出了未來可能的研究和應用方向。

本文的其余部分結構如下。第2節介紹了RL的背景，定義了相關的概念，列出了常用的方法。第三節給出了基于rl的推薦方法的標準定義。第4節全面回顧了為推薦系統開發的RL算法。第五部分討論了在推薦系統中應用RL所面臨的挑戰和相應的解決方案。接下來，第6節討論了基于rl的推薦系統的各種限制和潛在的研究方向。最后，第7節總結了本研究。

智能需要記憶。沒有記憶，人類就無法完成各種重要的任務，比如讀小說、玩游戲或解決數學問題。機器學習的最終目標是開發出像人類一樣自動學習和行動的智能系統，因此機器的記憶構建是必然的。人工神經網絡通過權值將計算單元連接起來，對大腦中的神經元和突觸進行建模，這是一種典型的類似于記憶結構的機器學習算法。他們的后代擁有更復雜的建模技術(即深度學習)，已經成功地應用于許多實際問題，并證明了記憶在機器系統學習過程中的重要性。近年來，深度學習中記憶建模的研究主要圍繞外部記憶結構展開，受到計算圖靈模型和生物神經元系統的啟發。注意力機制的產生是為了支持外部記憶的獲取和保留操作。盡管缺乏理論基礎，這些方法已經顯示出幫助機器系統達到更高智能水平的希望。本文的目的是提高對深度學習中記憶和注意力的認識。它的貢獻包括: (i) 呈現記憶分類的集合，(ii)構建支持多個控制和記憶單元的新的記憶增強神經網絡(MANN)， (iii)通過序列生成模型中的記憶引入可變性，(iv)在基于槽的記憶網絡中尋找最佳的寫操作以最大限度地提高記憶能力;(v)通過神經網絡的一種新型外部存儲器——神經存儲程序存儲器來模擬通用圖靈機。

目錄內容： 1 Introduction 2 Taxonomy for Memory in RNNs 3 Memory-augmented Neural Networks 4 Memory Models for Multiple Processes 5 Variational Memory in Generative Models 6 Optimal Writing Memory 7 Neural Stored-Program Memory 8 Conclusions

在這篇論文中，我們介紹了神經網絡的幾種記憶類型，特別是遞歸神經網絡(RNNs)。我們強調記憶作為RNN的外部存儲的概念，其中rnn可以學習讀寫外部記憶，以支持其工作記憶(第2章)。我們回顧了解決訓練RNN困難的進展，如門控和注意機制，特別是基于槽的MANN，這是本文第三章提出的新模型的主要內容。我們的主要貢獻有四方面。首先, 我們MANN作為一個多進程多視點模型來處理復雜的問題,如sequence-to-sequence映射和多視角序列學習(第四章)。我們進一步擴展MANNs作為離散序列的模型生成會話數據可變性和一致性要求(第5章)。我們也解釋到內存中最后，我們介紹了一類新的MANN，它遵循存儲程序存儲原理，可以通過切換控制器的程序來執行不同的功能。

許多解決組合優化問題的傳統算法都涉及使用手工構造的啟發式算法，這些啟發式算法能夠依次地構造解決方案。這種啟發式方法是由領域專家設計的，且一般由于問題的困難性，這種方法不是最佳的。強化學習（RL）提出了一種很好的選擇，使用監督或自我監督的方式訓練 agent 來自動搜索這些啟發式方法。

在這篇調研中，我們探索了將 RL 框架應用于困難的組合問題的最新進展。我們的調研為運籌學和機器學習社區提供了必要的背景，并展示了推動領域向前發展的工作。我們將最近提出的 RL 方法并置在一起，列出了每個問題改進方法的時間線，并與傳統算法進行了比較，這表明 RL 模型可以成為解決組合問題的有希望的方向。

論文標題：Reinforcement Learning for Combinatorial Optimization: A Survey

論文作者：Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev

與經典的監督學習不同，強化學習(RL)從根本上是交互式的: 一個自主的智能體必須學習如何在一個未知的、不確定的、可能是對抗的環境中表現，通過與環境的積極互動來收集有用的反饋，以提高其序列決策能力。RL代理還將干預環境: 代理做出決策，進而影響環境的進一步演化。

由于它的普遍性——大多數機器學習問題可以看作是特殊情況——RL很難。由于沒有直接的監督，RL的一個主要挑戰是如何探索未知的環境并有效地收集有用的反饋。在最近的RL成功案例中(如視頻游戲中的超人表現[Mnih et al.， 2015])，我們注意到它們大多依賴于隨機探索策略，如“貪婪”。同樣的，策略梯度法如REINFORCE [Williams, 1992]，通過向動作空間注入隨機性進行探索，希望隨機性能導致良好的動作序列，從而獲得高總回報。理論RL文獻已經開發出了更復雜的算法來進行有效的探索(例如，[Azar等人，2017])，然而，這些接近最優算法的樣本復雜度必須根據底層系統的關鍵參數(如狀態和動作空間的維數)呈指數級增長。這種指數依賴性阻礙了這些理論上優雅的RL算法在大規模應用中的直接應用。總之，如果沒有進一步的假設，無論在實踐上還是在理論上，RL都是困難的。

在本文中，我們試圖通過引入額外的假設和信息源來獲得對RL問題的支持。本文的第一個貢獻是通過模仿學習來提高RL樣本的復雜度。通過利用專家的示范，模仿學習極大地簡化了探索的任務。在本論文中，我們考慮了兩種設置:一種是交互式模仿學習設置，即在訓練期間專家可以進行查詢;另一種是僅通過觀察進行模仿學習的設置，在這種設置中，我們只有一組由對專家狀態的觀察組成的演示(沒有記錄專家行為)。我們在理論和實踐中研究如何模仿專家，以減少樣本的復雜性相比，純RL方法。第二個貢獻來自于無模型的強化學習。具體來說，我們通過構建一個從策略評估到無后悔在線學習的總體約簡來研究策略評估，無后悔在線學習是一個活躍的研究領域，具有良好的理論基礎。這樣的約減創造了一個新的算法族，可以在生成過程的非常弱的假設下證明正確的策略評估。在此基礎上，對行動空間和參數空間兩種無模型勘探策略進行了理論和實證研究。這項工作的第三個貢獻來自基于模型的強化學習。我們提供了基于模型的RL方法和一般無模型的RL方法之間的第一個指數樣本復度分離。然后，我們提供了基于PAC模型的RL算法，可以同時實現對許多有趣的MDPs的采樣效率，如表列MDPs、因子MDPs、Lipschitz連續MDPs、低秩MDPs和線性二次控制。通過將最優控制、模型學習和模仿學習結合在一起，我們還提供了一個更實用的基于模型的RL框架，稱為雙重策略迭代(DPI)。此外，我們給出了一個通用的收斂分析，將現有的近似策略迭代理論推廣到DPI。DPI對最近成功的實用RL算法如ExIt和AlphaGo Zero進行了概括和提供了第一個理論基礎[Anthony et al.， 2017, Silver et al.， 2017]，并為統一基于模型的RL方法和無模型的RL方法提供了一種理論健全和實踐高效的方法。

//www.ri.cmu.edu/publications/towards-generalization-and-efficiency-in-reinforcement-learning/