Information that is of relevance for decision-making is often distributed, and held by self-interested agents. Decision markets are well-suited mechanisms to elicit such information and aggregate it into conditional forecasts that can be used for decision-making. However, for incentive-compatible elicitation, decision markets rely on stochastic decision rules which entails that sometimes actions have to be taken that have been predicted to be sub-optimal. In this work, we propose three closely related mechanisms that elicit and aggregate information similar to a decision market, but are incentive compatible despite using a deterministic decision rule. Following ideas from peer prediction mechanisms, proxies rather than observed future outcomes are used to score predictions. The first mechanism requires the principal to have her own signal, which is then used as a proxy to elicit information from a group of self-interested agents. The principal then deterministically maps the aggregated forecasts and the proxy to the best possible decision. The second and third mechanisms expand the first to cover a scenario where the principal does not have access to her own signal. The principal offers a partial profit to align the interest of one agent and retrieve its signal as a proxy; or alternatively uses a proper peer prediction mechanism to elicit signals from two agents. Aggregation and decision-making then follow the first mechanism. We evaluate our first mechanism using a multi-agent bandit learning system. The result suggests that the mechanism can train agents to achieve a performance similar to a Bayesian inference model with access to all information held by the agents.
做出決定是很難的! 值得慶幸的是,人類已經開發了許多概念框架,如決策理論、運籌學、倫理理論、統計學、博弈論和強化學習,以幫助解決這個過程。這些框架中的每一個都可以通過它們將決策的哪些方面放在前面和中心,哪些方面被忽略來描述。
本論文涉及統計學、博弈論和強化學習的交叉領域的課題。廣義上講,這些領域可以有以下特點。
統計學是關于不確定性的量化:給定一些產生數據的過程,統計學提供了正式的工具,將數據轉換為關于該過程的陳述,這些陳述是根據數據所傳達的證據量來校準的。在一個典型的統計問題中,科學家對一個系統進行干預,并在每次干預后收集系統的數字測量。統計學家的任務是利用這些數據來提供(i)干預措施效果的估計值,以及(ii)這些估計值中不確定性的一些原則性量化。如何處理這些估計值的問題完全由科學家(或其他領域的專家)來決定。
博弈論是關于戰略的,即在有其他決策者存在的情況下的決策考慮。它把有關相互作用的決策者或智能體之間的沖突、合作和激勵的問題放在最前面和中心。一個典型的博弈論問題是:給定一組智能體可用的選項和智能體對結果的偏好,什么樣的智能體行為分配是穩定的,以至于沒有智能體會有動力改變他們的行為?博弈論想當然地認為,智能體確切地知道他們的偏好(用數字表示),并且通常假設,一旦考慮到其他智能體行動的不確定性,就可以確定地知道行動的后果。
強化學習是關于從經驗中學習。在強化學習中,決策者通過采取行動和觀察與所采取行動的質量相關的數字 "獎勵 "信號來與系統互動。學習問題是更新決策規則以獲得更大的獎勵。這些更新可能會影響到收集到的數據的分布,從而引入統計方面的挑戰。在這種情況下,決策者面臨著基本的權衡,如是否采取行動以收集更多的信息,或是否采取行動以獲得更大的獎勵(所謂的探索-利用權衡)。強化學習的一個典型問題是反復玩有限數量的老虎機,保持對其報酬分布的估計,目的是獲得最大的累積報酬。鑒于其對行為和行為引起的獎勵的強調,強化學習(狹義上的解釋)不關注不確定性的量化,也不關注其他決策者的存在。
上述每個框架都提供了一個獨特的視角來分析決策問題,并提供了強大的工具來進行分析。每個框架也都有其局限性。例如,傳統的統計學可以被認為是一種完全的描述性工作,適用于分析者不與之互動的系統:它沒有明確地納入決策,并經常假設數據是以一種方便的方式取樣的,例如,作為獨立和相同的人口抽樣。這就排除了分析本身可能會改變產生的數據。在光譜的另一端,經典博弈論幾乎沒有試圖進行描述,而是相當規范,詳細說明了 "理性 "智能體必須采取行動的方式,并規定了這些智能體的理論上穩定的配置。博弈論是抽象的,它假設了許多不確定性的來源,如環境中的不確定性或自己對結果的偏好。
寬泛地說,強化學習在純粹的描述性或規范性之間做出了妥協:它的工具可以用來分析現實世界的智能體所產生的數據,或者為智能體推薦或規定行動。它的研究重點通常是制造理想的行為,這使得它更適合作為一門工程學科(如控制理論),而不是用于對不確定性進行仔細量化的數據稀缺環境,或對其他智能體的考慮至關重要的現實世界環境。
鑒于它們的優點和缺點,這些框架中的每一個都有一些強大的東西可以提供給其他的框架。正是這種觀察激勵了本論文的工作,它試圖以各種方式將這些框架融合在一起,以提供更好的工具,在復雜的世界中做出決策。下面,我們概述了三種不同的框架融合方式的動機和結果,每一種都構成了本論文的一個章節。
鑒于其規范性方向,博弈論并沒有提供數據驅動的分析工具,因為它們是由人或算法進行的游戲。這種類型的分析是很重要的。視頻游戲是全世界范圍內大規模流行的娛樂形式,為了創造或平衡它們,游戲設計師必須了解它們是如何被玩的。例如:某些策略是否對游戲的結果產生了不良影響?隨機性是否發揮了過大的作用?除了游戲設計之外,在美國和全世界的許多司法管轄區,在游戲上賭博的合法性取決于在決定該游戲的結果時是技巧還是機會 "占優勢"。這個概念并沒有一個既定的正式說法。因此,在游戲設計和賭博法中,都需要有統計工具來描述各方面對游戲結果的影響。
在第二章(廣義形式游戲的方差分解)中,我們采用了一種常見的統計工具,并為廣義形式游戲開發了一個版本,廣義形式游戲是一種具有離散步驟和部分可觀察性的游戲的一般模型,包括國際象棋和撲克這些特殊情況。這個工具就是方差分解,它在統計學中被用來量化感興趣的結果中的變化來源。游戲的方差分解允許用戶將游戲結果的變化歸因于不同的玩家和機會,使分析游戲的新方法可能對賭博法或游戲設計產生影響。具體來說,我們推導出一個封閉式表達式,并估算出可歸因于單一玩家或機會的廣義游戲結果的方差。我們分析了撲克牌,發現發牌的隨機性對每一手牌的結果的影響小得令人吃驚。我們簡要地評論了這一想法的延伸,它可以用來測量游戲的其他有趣的屬性。本章是Cloud和Laber(2021)的翻版,稍作修改。
在過去的五年里,機器學習方法在決策方面有了快速的發展,特別是在復雜的、大規模的、多人游戲中,如國際象棋、圍棋、Dota II、星際爭霸和戰略游戲。學習玩這些游戲的一個明顯的困難是弄清楚如何采取行動,以便在復雜的環境中實現某些變化。這正是強化學習所要解決的問題。然而,還有一個重要的困難,在文獻中得到了很好的理解,但也許并不普遍:在有多個智能體的情況下學習。在上述所有的游戲中,機器學習算法必須學會以尊重游戲的隱含動態性的方式行事:通過游戲環境,智能體可能面臨許多不同種類的對手。這些對手可能會利用曾對其他智能體產生有利結果的行為。例如,應用于 "剪刀石頭布 "游戲的天真強化學習算法,在對 "布"的對手進行訓練后,將產生一個 "剪刀 "智能體,在對其訓練對手時獲得高額獎勵,但被 "石頭 "智能體嚴重懲罰。對這些多智能體動態的考慮存在于博弈論的領域。因此,為了定義合適的收斂概念和設計達到收斂的算法,多智能體強化學習問題必須將博弈論引入其中。
在第三章(預期的虛構游戲)中,我們研究了一種經典的博弈論算法,這種算法之前已經被成功地擴展到多智能體強化學習中。該算法被稱為 "虛構游戲",用于在雙人競爭游戲中尋找平衡點。然而,正如我們在理論上和經驗上所顯示的,它在一些感興趣的游戲中收斂得很慢。為了解決這一缺陷,我們提出了一種新的虛構游戲的變體,稱為預期性虛構游戲。預測性虛構游戲被證明是收斂的,被證明具有優越的經驗性能,并被擴展到多智能體強化學習的環境中。在此過程中,我們提供了一種易于實現的多智能體強化學習算法,其性能優于由虛構游戲驅動的算法。本章是Cloud等人(2022)的復制品,做了些許修改,仿真結果也不那么廣泛。
在許多數據驅動的決策問題中,對其他智能體的考慮并不重要,因此,不需要博弈論。例如,在臨床試驗、推薦系統或其他許多獨立個體與系統互動的環境中,通常把問題當作病人或網站用戶是可以互換的、獨立的和固定的。這是合理的,因為,例如,給一個病人提供治療,不太可能導致另一個病人后來對同一治療有不同的反應。使用數據為臨床試驗中的個人定制治療方法,或向網絡用戶推薦媒體,是一個強化學習問題。然而,在需要 "安全 "概念的環境中,強化學習的天真應用不可能是合適的。如果一個決策系統要可靠地遵守對其行動效果的約束,就必須能夠量化其行動效果的不確定性。進行這種不確定性的量化是統計推理的一個問題。
在第四章(上下文強盜中的安全約束在線學習)中,我們提出并研究了一個受約束的強化學習問題,除了獎勵最大化之外,決策者還必須根據對其 "安全性 "的約束來選擇行動。約束滿足,就像潛在的獎勵信號一樣,是由噪聲數據估計的,因此需要仔細處理不確定性。我們提出了一個新的算法框架,它采用了樣本分割,以便比現有的安全算法更有效地利用數據。我們框架的通用性意味著它有可能被應用于各種現實世界中的安全關鍵決策問題,包括那些使用人工神經網絡等難以分析的函數近似器的問題。然而,我們在更有限的線性背景下研究了我們的框架,以便得出理論結果,暗示該方法的實際安全性和實用性。我們證明,在適當的條件下,我們的算法保證在極限情況下產生最佳的安全行為,甚至在小樣本環境下也是近似安全的。在各種模擬中,我們驗證了該理論,并證明了卓越的經驗性能。通過這種方式,我們提供了一種可靠的算法,可用于現實世界的安全關鍵數據驅動的決策問題。本章是Cloud, Laber和Kosorok(即將出版)的論文的預印本。
本文考慮圖遺忘學習問題,將圖神經網絡模型訓練到指定的準確度,然后部署圖神經網絡模型,同時一系列請求到達,從模型中刪除圖元素(節點、邊)。隨著GNN模型在現實世界中的應用,解決這個問題變得越來越重要——例如,當用戶試圖隱藏他們在社交圖中與其他人的聯系時,或者當知識圖譜中的關系變得不相關或不再真實時。
要從經過訓練的GNN中刪除信息,必須從模型中刪除其對GNN模型權重以及對圖中鄰居表示的影響。然而,現有的通過再訓練和權重修改的方法要么降低了所有節點共享的模型權重,要么由于刪除的邊對局部圖鄰域的強依賴性而失效。認識到這些陷阱,本文以刪除邊一致性和鄰域影響的形式形式化了圖遺忘學習所需的屬性,并開發了GNNDelete,一種與模型無關的逐層算子,為遺忘學習任務優化這兩個屬性。 GNNDelete更新潛在表示,從模型中刪除節點和邊,同時保持學到的其余知識的完整性。在6個真實世界和2個知識圖譜上的實驗表明,與現有的圖忘記模型相比,GNNDelete在鏈路預測任務上的AUC最高可達36.9%,在區分刪除邊和未刪除邊的AUC最高可達22.5%。GNNDelete高效——例如,與在大型知識圖譜上從頭開始訓練相比,它需要的時間減少12.3倍,空間減少9.3倍。
圖神經網絡(GNN)在現實世界中的應用越來越多,在大多數部署的GNN中,底層圖會隨著時間的推移而變化。傳統的機器學習方法通常是離線工作的,其中模型使用完整的訓練數據集進行一次訓練,然后鎖定用于推理,對模型進行少量更新。相比之下,在線訓練可以在新的訓練數據點可用時使用它們更新模型。然而,離線和在線學習都無法處理數據刪除——即在不犧牲模型性能的情況下從模型中刪除數據點的所有痕跡的任務。當需要從模型中刪除數據時,模型必須進行相應的更新。例如,GNN必須實施保護個人隱私的隱私條款(如加州消費者隱私法(CCPA)和通用數據保護條例(GDPR)),這意味著賦予GNN數據刪除能力是重要的,但在文獻中研究較少。 然而,設計圖遺忘學習方法是具有挑戰性的。僅刪除數據不足以滿足最近對增加數據隱私的要求,因為在原始數據上訓練的模型可能仍然包含有關其模式和特征的信息。一種簡單的方法是刪除數據并從頭開始重新訓練模型。然而,這可能非常昂貴,特別是在大型數據集上。 本文提出GNNDelete,一種用于圖遺忘的通用方法。我們形式化了兩個關鍵的GNN刪除屬性: * 刪除邊的一致性:未學習模型刪除邊的預測概率應該與不存在邊的預測概率相似。該屬性強制GNNDelete刪除被刪除的邊偽裝成未連接的節點等信息。 * 鄰域影響:在圖的刪除和Granger因果關系之間建立聯系,以確保刪除后的局部子圖不受影響,從而保持原始的預測依賴關系。然而,現有的圖刪除方法沒有考慮這一本質屬性,即沒有考慮局部連通性的影響,導致次優刪除。
利用這兩個屬性,我們開發了GNNDelete,一個逐層刪除操作符來更新節點表示。當接收刪除請求時,GNNDelete凍結模型并學習在所有節點中共享的額外的小門控權重矩陣。與現有方法不同,現有方法試圖從頭開始重新訓練幾個小型模型或直接更新模型權重,這可能是低效和次優的,GNNDelete使用小型可學習矩陣進行推理,而不改變GNN模型權重,實現了效率和可擴展性。為了優化GNNDelete,指定了一個新的目標函數,滿足刪除邊的一致性和鄰域影響,產生強的整體刪除。
從教育到招聘,社會中的重要決策越來越依賴于數據驅動的算法。然而,算法決策的長期影響在很大程度上沒有得到充分理解,在理論和實踐中,確保公平利益存在嚴重挑戰。在本文中,我從兩個角度考察了機器學習算法的社會動力學:(I)算法決策的長期公平性,以及(ii)匹配市場的長期穩定性。
在計算機科學中,算法公平這個主題受到了廣泛的關注,但最近才認識到算法可以通過各種動態機制對種群產生不同的影響。我們通過提出機器學習算法和感興趣群體的動態交互的兩種不同模型來促進這一不斷發展的理解。首先,我們引入了延遲影響的概念——決策結果被觀察后,決策算法對人口的福利影響,其動機是,例如,在應用新的貸款批準算法后,平均信用分數的變化。我們證明了研究界提出的公平機器學習的幾個統計標準,如果應用于決策約束,可能會對弱勢群體的福利造成損害。t,我們考慮一個動態的環境,在這個環境中,個人投資于一個基于算法決策規則的預期回報的積極結果。我們表明,不良的長期結果是由于群體間的異質性和缺乏可實現性而產生的,并研究了干預措施的有效性,如按群體“脫鉤”決策規則和提供補貼。
除了長期公平的問題,利用機器學習為社會造福面臨的另一個挑戰是社會選擇。在市場中,個人學習目標(通常是構想出來的)可能與實現有效市場結果的長期社會目標相沖突。受在線市場和平臺中重復匹配問題的激勵,我們研究了雙邊匹配市場,參與者重復匹配,并通過匹配獲得關于其偏好的不完全信息。由于競爭,一個參與者試圖了解自己的偏好可能會影響其他參與者的效用。我們為市場平臺設計了一種機器學習算法,使市場作為一個整體能夠足夠有效地學習他們的偏好,從而快速獲得稱為穩定的市場公平概念。此外,我們研究了上述問題的分散化版本,并設計了參與者的學習算法,以在給定過去數據的情況下戰略性地避免競爭,從而消除了對中央平臺的需要。我們還研究了具有獨立行動誘惑的策略參與者是否仍應遵循算法的建議,結果顯示了算法的激勵兼容性方面的幾個積極結果。
//www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-41.pdf
摘 要
人工智能體在我們的世界中的流行提高了確保它們能夠處理環境的顯著屬性的需求,以便計劃或學習如何解決特定任務。
第一個重要方面是現實世界的問題不限于一個智能體,并且通常涉及在同一環境中行動的多個智能體。此類設置已被證明難以解決,其中一些示例包括交通系統、電網或倉庫管理。此外,盡管許多問題域固有地涉及多個目標,但這些多智能體系統實現中的大多數旨在優化智能體相對于單個目標的行為。通過對決策問題采取多目標視角,可以管理復雜的權衡;例如,供應鏈管理涉及一個復雜的協調過程,用于優化供應鏈所有組件之間的信息和物質流。
在這項工作中,我們關注這些突出的方面,并討論當涉及多個智能體時,如何將人工智能體的決策和學習過程形式化,并且在該過程中需要考慮多個目標。為了分析這些問題,我們采用了基于效用的觀點,主張在相互競爭的目標之間做出妥協,應該基于這些妥協對用戶的效用,換句話說,它應該取決于結果的可取性。
我們對多目標多智能體決策 (MOMADM) 領域的分析表明,迄今為止該領域已經相當分散。因此,對于如何識別和處理這些設置還沒有統一的看法。作為第一個貢獻,我們開發了一種新的分類法來對 MOMADM 設置進行分類。這使我們能夠提供該領域的結構化視圖,清楚地描述當前多目標多智能體決策方法的最新技術,并確定未來研究的有希望的方向。
在多目標多智能體系統的學習過程中,智能體接收一個值列表,每個分量代表不同目標的性能。在自利智能體人的情況下(即,每個人都可能對目標有不同的偏好),在相互沖突的利益之間尋找權衡變得非常簡單。作為第二個貢獻,我們繼續分析和研究不同多目標優化標準下的博弈論均衡,并提供有關在這些場景中獲得此類解決方案的存在和條件的理論結果。我們還表明,在某些多目標多智能體設置中,納什均衡可能不存在。
當決策過程中的每個參與者都有不同的效用時,智能體了解其他人的行為就變得至關重要。作為最后的貢獻,我們首次研究了對手建模對多目標多智能體交互的影響。我們提供了新穎的學習算法,以及將對手行為建模和學習與對手學習意識相結合的擴展(即,在預測一個人對對手學習步驟的影響的同時進行學習)。實證結果表明,對手的學習意識和建模可以極大地改變學習動態。當存在納什均衡時,對手建模可以為實現它的智能體帶來顯著的好處。當沒有納什均衡時,對手學習意識和建模允許智能體仍然收斂到有意義的解決方案。
提 綱
1 引言
1.1 多智能體與多目標 1.2 激勵示例 1.3 研究目標和貢獻 1.3.1 貢獻 1.4 論文結構
2 多目標多智能體系統
2.1 強化學習 2.1.1 基于價值的方法 2.1.2 策略梯度和演員評論家 2.2 多智能體決策理論 2.2.1 標準形式博弈與均衡 2.3 單智能體多目標決策 2.3.1 工具函數 2.3.2 多目標優化標準 2.3.3 應用案例場景 2.4 多智能體多目標決策 2.4.1 多目標隨機博弈 2.4.2 特殊案例模型 2.4.3 多目標標準博弈 2.4.4 MONFG優化標準 2.5 總結
3 構建多目標多智能體決策域
3.1 執行階段 3.1.1 團隊獎勵 3.1.2 個體獎勵 3.2 解決方案概念 3.2.1 策略 3.2.2 覆蓋集合 3.2.3 均衡 3.2.4 ε近似納什均衡 3.2.5 聯盟形式與穩定概念 3.2.6 社會福利與機制設計 3.2.7 其他解決方案的概念 3.3 總結
4 多目標多智能體場景均衡
4.1 MONFG計算均衡 4.1.1 定義 4.1.2 理論分析 4.1.3 用于SER分析的附加博弈 4.2 實驗 4.2.1 Game 1 - The (Im)balancing Act Game 4.2.2 Game 2 - The (Im)balancing Act Game without action M 4.2.3 Game 3 - A 3-action MONFG with pure NE 4.3 總結
5 多目標多智能體場景中的對手建模
5.1 背景 5.1.1 對手建模 5.2 MONFG中的對手建模 5.2.1 對手學習意識和建模使用高斯過程 5.2.2 MONFG評價器 5.2.3 MONFG策略梯度方法 5.3 實驗設置與結果 5.3.1 完整信息設置 - MO-LOLA vs. MO-LOLA 5.3.2 無信息設置 5.4 總結
6 結論
6.1 討論 6.2 未來研究方向
6.2.1 優化標準和解決方案概念 6.2.2 ESR計劃、強化學習與SER博弈論 6.2.3 對手建模和建模對手效用 6.2.4 互動研究方法 6.2.5 深度多目標多智能體決策 6.2.6 更廣泛的適用性
我們為什么在這里?我們大多數人來到這里的原因很簡單:我們想解決人工智能問題。那么,人工智能和這本書的書名有什么關系呢?人工智能的現代定義之一是對理性代理的研究和設計[RN09]。從這個意義上說,我們將一個系統描述為智能的,當它最大化某些預期的性能概念時。機器學習的子領域處理的是問題和算法的子集,其中代理可以獲得經驗(通常以某種形式的數據),可以利用這些經驗來改進性能的概念[MRT12]。大多數情況下,性能是由代理人在新的和看不見的情況下如何行動來衡量的,這些情況不構成其訓練經驗的一部分。例如,可以訓練一名代理人將英文翻譯成法文,其訓練經驗包括大量翻譯的聯合國文件。然而,在評估時,它可能會在與它所見過的文件不同的聯合國新文件上進行測試。很自然地,代理在它所看到的訓練經驗和它所評估的新情況下的表現之間存在著差距。代理泛化的能力是通過性能上的差距有多小來衡量的。
希望前面的段落已經解釋了在機器學習的背景下,以及在更大的AI背景下,什么是泛化。那么,標題中還保留著哪些“分布外”詞呢?如前所述,泛化是指減少一個agent在已知訓練情境下的表現與同一agent在未知測試情境下的表現之間的差距。然而,有許多不同類型的未知。統計學習通常處理的一類泛化是分布的:當從訓練示例生成的數據與測試示例生成的數據無法區分時。根據定義,非分布內的泛化問題稱為分布外泛化問題,這是本書的主題。
這項工作的目標很簡單。我們想要回顧,分布外泛化的知識。因此,這項工作的很大一部分將致力于理解(有時是微妙的)不同方法和假設之間的差異和相似性,通常以一種孤立的方式呈現。重點將放在與人工智能或現代大規模機器學習應用等想法上。此外,我們將特別注意研究不同方法的缺點,以及下一步可能是重要的。
在第二章中,我們首先討論如何量化分布外泛化。通過幾個例子,我們研究了分布外泛化與處理不同分布外任務的幾種常用方法之間的關系。本文將特別強調這些方法背后的假設,并說明這些方法何時有效,何時無效。
在第三章中,我們將關注一個特定的分布外任務類。在這些預測任務中,就像在許多實際問題中一樣,在分布之外泛化的困難在于找出數據中的哪些相關性是假的和不可靠的,以及哪些相關性代表感興趣的現象。
在第四章中,我們討論了不同應用領域在實踐中出現的分布外任務的類型,以及這些領域在過去是如何處理這些問題的。
在第五章中,我們為分布外泛化和人工智能背景下的新研究領域奠定了基礎。在本章中,我們將關注在探索或強化學習環境中與世界交互的agent,以及它們如何從分布外泛化中獲益。
我們考慮這樣一個問題:你如何為對比學習抽取好的負樣本例子?我們認為,與度量學習一樣,學習對比表示法受益于硬負樣本(即,點很難與錨點區分)。使用硬負樣本的關鍵挑戰是對比方法必須保持無監督,使得采用現有的使用標簽信息的負樣本抽樣策略不可行。作為回應,我們開發了一種新的無監督的方法來選擇硬負樣本,在那里用戶可以控制硬負樣本的數量。這種抽樣的極限情況會導致對每個類進行緊密聚類的表示,并將不同的類推到盡可能遠的地方。該方法提高了跨模態的下游性能,只需要少量的額外代碼來實現,并且沒有引入計算開銷。