基于深度強化學習的自動協商研究綜述

唐 詩，楊 陽，陳鍶奇*

(1.西南大學附屬中學,重慶 400700；2.天津大學 智能與計算學部，天津 300072)

0 引言

在現如今的生活中，協商無處不在，小到去市場購物，大到影響人類命運共同體的協商，如全球碳排放協議。協商是一種強有力的解決雙方矛盾、沖突和爭議的機制。參與協商的各方在追求自己的需求，或者自己所代表的某個組織的需求時，通過交換提議共同尋找雙方都能接受的共同方案，目前被廣泛應用于經濟[1]、人工智能[2-3]、商業[4-6]等領域，有非常重要的社會價值。但是由于協商談判的代價高昂，學者試圖去尋找一種更有效的協商方式。

深度強化學習(Deep Reinforcement Learning,DRL)集成了深度學習對復雜環境的感知能力，以及強化學習對復雜場景的決策能力，實現了端到端的學習模式。深度強化學習的出現使得強化學習技術真正走向實用，解決現實場景中的復雜問題，其在人工智能領域(如無人駕駛[7-8]、智能交通系統[9]、機器人系統[10-11]、游戲[12]等)取得的成功推動它應用于包括協商[13]在內的復雜人類問題。運用到自動協商領域的基于深度強化學習方法訓練的自動協商智能體可以在較短時間內用較小的成本系統地考慮所有可能的結果。因此，協商智能體可以減少達成協議所需的時間和精力，同時增加達成更好的雙贏協議的機會。自動協商智能體在電子商務和供應鏈管理方面取得了巨大的成功。

本文將以基于強化學習的自動協商任務為核心展開綜述，首先介紹自動協商概述，然后綜述強化學習在自動協商任務中的應用并分析各模型特點，最后總結全文并分析深度強化學習技術與自動協商任務相結合的研究趨勢及應用前景。

1 自動協商概述

1.1 自動協商框架

自動協商是兩個自動智能體之間的協商，這些協商智能體被稱為協商者。在一個自動協商框架中包含協商目標、協商協議和協商策略三個內容。協商目標確定了參與協商的雙方所要協商討論的議題。協商協議定義了參與協商的雙方都需遵循的協商規則，指定了每個協商者在任何給定時刻可以執行的動作。本文協商者的協商策略是接受策略和投標策略的結合。

1.1.1 協商目標

協商目標是指參與協商的智能體所要進行協商討論的議題，協商的目的在于使參與協商的雙方對這些協商議題上的取值能都達到一致。若協商討論的議題只有一個，稱為單議題協商。然而，在復雜的現實生活中，在協商過程中考慮的常常不是單一的議題，在正常條件下協商議題是多樣化的，常常還要對大小、數量、質量等議題進行協商，這就是多議題協商。

1.1.2 協商協議

協商協議是指參與協商的雙方都需遵循的協商規則。此處介紹較常使用的交替報價協議(Altermating Offers Protocol,AOP)[14]。該協議在進行雙邊多議題自動協商時，由協商雙方輪流報價。通過多個協商回合的交流，AOP協議能使參與協商的智能體慢慢靠近尋找最優協商解。

在AOP協議下，協商環節由連續回合組成，每個參與協商的智能體可以提出報價、接受報價，或退出協商。如果雙方達成了共同協議，或者到了最后期限，那么一局協商就結束了。截止日期可以用最大回合數或實際交替提議次數來衡量。協商是不重復的，即每個協商環節都是獨立進行的，一個協商環節不能影響其他協商環節。

在多回合的協商中，每個參與協商的智能體都有對手的協商歷史信息，可以通過判斷對手協商歷史信息來學習對手的協商態度，從而實現選用合適的協商策略讓協商達到雙贏。

AOP協商流程如圖1所示。

圖1 AOP協商流程

1.1.3 協商策略

協商策略，即智能體在協商過程中憑借所處的環境，利用何種決策在自己全部協商提議中挑選最利于自己的提議給對方智能體，即為可以讓協商智能體做出判斷的函數。協商策略包括兩部分：

其一是評估提議模塊，即接受策略。接收策略的核心問題是何時給出報價，是否接受或等待未來可能更好的報價。然而，如果智能體未能在截止日期之前接受，就會發生交易沖突，兩個參與協商的智能體都不會得到任何回報。給定一個折扣率和讓步因子，從他們先前的報價中推斷出接受報價的最佳時機，因此接受策略可以看作是一個最優停止問題，接受策略的作用是在一個回合中評估對方智能體的協商提議，隨即判斷決定是否可以接受該提議。

其二是產生提議模塊，即報價策略，報價策略的作用是產生最有利于自身的還價提議。協商策略的好環是判斷所采用協商框架效率高低的主要標準。

為了設計一種可以從過往協商經驗中自適應學習協商策略并和未知對手進行并行雙邊協商的智能體，本文研究了先前提出的策略學習方法，并發現它們在實際應用中均存在一些問題，如：

啟發策略通過啟發策略訓練的智能體適應環境變化的能力不強，不同的雙邊協商通過一個協調智能體或者通過多個內部對話策略來管理，但這種策略不支持學習，即不能適應變化的對手和環境，對預先設定的對手和環境依賴性強，一旦變化，可能會無法使用。

遺傳算法通過遺傳算法學習訓練需要大量的試驗才能獲得好的策略，這意味著它們不能在線設置。

強化學習基于強化學習的協商模型通常采用Q-Learning[15]，但它不支持連續的行動，這也是設定中的重要限制，因為想知道要讓步多少，譬如在出售物品的價格上，這自然是一個連續的行動空間。

所以，現在學者通常使用了深度強化學習算法來訓練針對每個對手(如基于時間策略的對手和基于行為策略的對手)的協商策略。

1.1.4 協商模型

(1)

根據Rubinstein[21]提出的協商回合的概念，每個智能體依次以提議的形式提出報價，以表達自己的要求，他們可以為了自己的利益自由離開協商場景。通常，將協商輪數稱為雙方交換報價的次數。協商持續進行，直到一方接受另一方的提議，或一方中斷，或由于超時而沒有提議被接受。如果最終沒有達成協議，則提供的分歧解決方案生效，各方獲得各自的保留值(θ)，這也適用于一方提前退出協商的情況。

此外，定義一個折現因子δ(δ∈[0,1])來捕捉協商中的折現效應，如下所示：

(2)

式中，Dδ(U,t)表示t時刻的折現效用，U為(初始)效用，t為標準化時間(t∈[0,1])。由式(2)可知，智能體達成協議所花的時間越長，他們所能獲得的效用就越低。

1.2 基準協商策略

協商的目的是在進行交易時獲得最大的效用，因此，智能體需要采取恰當的協商策略。在信息完全的情況下，可以確定最優報價策略。然而，如前所述，在協商中不太可能獲得完全的信息，因為參與協商的智能體由于害怕被剝削利用而不愿透露他們的偏好，這推動了不完全信息下協商策略的發展。根據將狀態映射到目標效用的決策函數，這些協商策略可以大致分為基于時間的協商策略和基于對手行為的協商策略。

1.2.1 基于時間的協商策略

時間因素在智能體自動協商中起著舉足輕重的作用，若參與協商的雙方可用的協商時間較短時，可能會導致兩種結果：其一，參與協商的雙方在時間不夠充足的條件下，由于迫切希望達成共識來完成協商任務，會使考慮不夠充分，導致其協商解的效用值較低，協商雙方會丟失一些潛在的效益；其二，由于時間不夠，雙方在達成一致前退出協商，而讓原本可以達成一致的協商被迫失敗。若協商雙方可用的協商時間較為寬裕，協商對手之間能夠實現充分地討價還價，在協商過程中深入了解對方的喜好，從而利于找到能使雙方都認可且能夠達到最大價值的協商解。

基于時間的協商策略是指僅基于時間產生報價的功能。在每一輪協商中，智能體計算他們的決策效用，決定他們是否接受報價。對于基于時間的智能體，其決策效用是：

(3)

式中，Pmax、Pmin∈[0，1]，從而參數化報價范圍。通常，F(t)被參數化為指數函數：

(4)

式中，c為讓步因子，反映了讓步幅度。為簡單起見，k通常設置為0。在輪流出價的讓步協商中，根據讓步因子的不同，基于時間的協商策略基本可以分為以下3種類型：

① 0

②c≥ 1，在協商初始階段，智能體讓步幅度較大，隨著時間的推移漸漸縮小讓步幅度，即智能體迅速讓步并提供其保留值，因此被稱為Conceder讓步型；

③c= 1，是智能體隨協商時間推移均勻讓步的時間策略函數，意味著智能體的決策效用線性下降，稱為均勻線型。

3種類型不同讓步因子的基于時間策略智能體的決策效用如圖2所示。

圖2 不同讓步因子下的基于時間策略的智能體的決策效用

1.2.2 基于對手行為的協商策略

基于對手行為的協商策略通過觀察對手的行為來決定自己的行為，譬如是出價還是接受，可以理解為模仿對手的行為，即對方對我如何，我就對對方如何。智能體在進行輪流出價的自動協商中，參與協商的雙方都有自己的偏好和保留值等信息，且在討價還價的協商中，智能體害怕被利用，這些信息是不為對手所知的，這推動了非完全信息下協商策略的發展。所以智能體在自動協商過程中通過輪流出價的提議來了解對方的偏好，并學著投其所好。

在智能體的自動協商過程中，協商雙方會有協商的歷史信息，基于對手行為的協商策略是觀察對手在協商歷史中所表現出的行為來確定自己的協商行為，以確定自己的讓步幅度，并根據它提出新的提議。這種通過模仿對手行為的協商策略可以在一定程度上有效避免協商過程中的利用、欺騙等情況。

目前最廣為人知的基于對手行為的協商策略是tit-for-tat針鋒相對，通過互惠產生合作。它的3個中心原則是：

① 永遠不要首先背叛：即不會在協商初始時就選擇主動背叛對手或者采取作弊行為，而是選擇友好的互惠互利合作模式。

② 如果受到背叛就采取報復行動：即在協商過程中若對手有背叛己方的行動，可以快速識別出背叛行為，同時利用背叛的行動來報復對手。

③ 報復后可以原諒：是指不會因為對手的一次背叛而進行不可原諒的多次報復，若對手在背叛后選擇悔改，重新進入合作模式，則會寬容地原諒對手，繼續恢復到友好的互惠互利合作模式。

相對針鋒相對(TFT)策略，通過提供與對手在δ回合之前的讓步，成比例地讓步來進行報價：

(5)

2 深度強化學習在自動協商中的應用

2.1 強化學習概述

除了監督學習和非監督學習之外，強化學習是機器學習家族中必不可少的一類。強化學習讓機器學習如何在環境中表現良好，獲得高分。強化學習是一類算法，最初什么都不知道的機器，在經歷過多次的嘗試后，能夠不斷學習吸收經驗，進而發現規律，最終達成目的，這便是強化學習的過程。

如圖3所示，強化學習的組成有智能體(Agent)和環境(Environment)兩部分。強化學習所研究的問題就是智能體如何于某一不確定的復雜環境中使其所能夠得到的獎勵最大化。

圖3 強化學習示意圖

強化學習的整個過程中，智能體一直與環境發生交互。智能體會在環境中獲得狀態，它能夠用該狀態給一個輸出動作(action)，即決策。隨后將該決策置于環境中，環境會依據智能體使用的決策，給出該決策獲得的獎勵，同時給出下一個狀態。智能體的目的是在環境中獲得盡可能多的獎勵。

沒有監督數據，這是強化學習與監督學習相異的一個方面，因此強化學習得到的模型能夠產生超過人類的表現。監督學習獲得的監督數據是由人來標注的，譬如ImageNet的圖片全部由人標注，則能夠確定人類的表現是此算法的上限，人類的標注結果決定了它永遠不可能超越人類。而強化學習與它不同，能夠自行在環境中探索，因此具備很大的潛力，能夠擁有超過人類能力范圍的表現，如著名AlphaGo這樣一個強化學習的算法在圍棋場上擊敗了最強的人類圍棋大師。

2.2 深度強化學習

深度學習與強化學習各有優劣：深度學習的感知能力較強而決策能力較欠缺；強化學習決策能力較強，卻難以處理感知問題。將深度學習和強化學習相結合，能夠產生新的解決思路，用于處理應對復雜系統的感知決策問題。

近年來，學術界已將強化學習與深度學習成功結合并使用，利用深度神經網絡來逼近價值函數，其突破在于策略梯度方法。強化學習算法在傳統上是動作—價值方法：在學習動作—價值之后，算法根據估計的動作-價值選擇動作。相比之下，策略梯度方法學習參數策略，而不是價值函數。本文所說的策略是指智能體策略——它在給定的狀態和時間所采取的行動。

深度強化學習是一種具有較強通用性的端到端感知控制系統，DRL學習過程描述如下：

① 智能體與環境交互時，可以獲得每一時刻的高維觀測，同時，利用深度學習方法對觀測結果進行感知，獲得具體的狀態特征表示；

② 基于根據預期效用評估每個行動的價值函數，并通過某種策略將當前狀態映射到相應的行動；

③ 環境在動作的基礎上做出反應，能夠獲得下一步的觀察。這樣就可以不斷重復上述過程，最終得到達到目標的最優策略。

DRL原理框架如圖4所示。由于概率可以分布在離散或連續的行動空間上，接受或拒絕報價的決定是離散的，而投標是在連續的空間上，所以DRL是一個有效的協商控制框架。

圖4 DRL原理框架圖

2.3 協商領域基于深度強化學習的經典算法

在Soft Actor-critic (SAC)[23]算法提出之前，主流的Model-Free強化學習方法在實際應用時均存在以下幾點問題：

采樣效率較低主要是信任區域策略優化算法(Trust Region Policy Optimization,TRPO)[24]、近端策略優化算法(Proximal Policy Optimization,PPO)[25]等On-Policy方法的不足。每一次策略更新都需要舍棄之前采樣的數據，并在當前策略下重新采樣足夠多的樣本數量，這需要很高的樣本復雜性和樣本數量才能保證其最終收斂。

對超參數十分敏感主要為深度確定性策略梯度算法(Deep Deterministic Policy Gradient,DDPG)[26]、分布式深度確定性策略梯度算法(Distributed Distributional Deterministic Policy Gradients,D4PG)[27]等Off-Policy方法的缺陷。由于這些策略與Q-value相互耦合，使其雖然通過Replay Buffer解決了采樣效率的問題，但它們還是容易受超參數的影響，使其算法性能不穩定。

脆弱的收斂性質與極高的樣本復雜度使Model-Free強化學習算法需要進行精細的超參數調整，這嚴重限制了以上這些算法在錯綜復雜的現實世界的適用性。SAC深度強化學習算法整合了Actor-Critic、Off-Policy、Maximum Entropy Model三大框架，極大程度地解決了以上算法的缺陷。

SAC是一種基于最大熵強化學習的Off-Policy算法，其目的是使預期回報和策略熵最大化。熵值越高的策略隨機性越大，這意味著最大熵強化學習的策略隨機性越大，其回報也越高，也就是說，在完成任務的同時盡可能隨機地行動。普通的強化學習算法只嘗試最大化最終回報，而SAC算法在最大化最終回報的同時也最大化策略熵，這可以提高算法對超參數的魯棒性和樣本效率。在自動協商中，這種策略隨機性可以降低對手預測智能體的行為及利用其行為信息的能力。

(6)

式中，r為獎勵函數，H為策略π的熵，α> 0被稱為熱度參數用以控制熵正則化的系數。st和at分別表示時間步t時的狀態和動作。現在，對應狀態s和動作a的動作-價值函數Qπ(s，a)可以表示為：

(7)

SAC同時學習一個策略π和兩個Q值函數。其中熵正則化參數α也是一個可訓練參數[28]，如式(8)所示，這可以通過近似雙重梯度下降來實現。

(8)

軟Q值函數的參數通過最小化軟貝爾曼殘差進行訓練，其中價值函數可以使用隨機梯度對其進行優化。

(9)

(10)

SAC算法利用兩個軟Q值函數來減小策略改進步驟中的正偏差，這會降低基于價值方法的性能。特別是，參數化了兩個軟Q值函數，參數為θi，并獨立培訓它們以優化JQ(θi)。兩個軟Q值函數顯著加快了訓練速度，這在較艱巨的任務上表現得尤為明顯。

3 基于強化學習的自動協商

在先前的研究中，包括貝葉斯學習和遺傳算法在內的許多計算方法已經被用于自動協商中開發和評估協商策略。在過去的幾十年中，已經有了一些研究強化學習算法，如Q-learning[15,29-32]和REINFORCE[33]在自動協商中的應用。

最近，深度強化學習被用于學習目標效用值、接受策略或報價和接受策略。Ho-Chun Herbert Chang[34]研究了深度強化學習在協商領域的應用，評價了其開發、適應和合作的能力。兩個Actor-Critic網絡針對基于時間策略的智能體、基于對手行為策略的智能體，以及通過自我演練被訓練為報價和接受策略。該文揭示了4個關鍵發現：① 神經智能體學會利用基于時間策略的智能體，實現決策值的清晰轉換，主要的障礙是邊際效用(二階導數)的變化和協商期限導致的懸崖行走；② 由于柯西分布的尖峰中心和沉重的尾部，柯西分布適合抽樣報價；③ 神經智能體證明適應性行為與基于對手行為策略的智能體不同；④ 神經智能體在自我演練過程中學習合作。智能體學習不可信的威脅，類似于進化博弈論文獻中基于聲譽的策略。此外，Pallavi Bagga[35]等人也展示了深度強化學習在并行雙邊協商中的應用。

3.1 RLBOA模型

2019年，Jasper Bakker[36]等人提出了一個模塊化的框架RLBOA，使用強化學習來促進自主協商智能體的創建。該框架可以創建能夠在許多不同協商環境中進行有效協商的智能體。為了能夠應對大規模的狀態和行動空間以及協商策略設置的多樣性，利用了將協商策略分為投標策略、對手模型和接受策略這種模塊化的BOA框架，這是一個通用的強化學習接口，其中非重復的多議題交替報價協商可以以一種可擴展的方式應用。通過實現一個智能體來證明RLBOA框架的價值，該智能體在壓縮的狀態和動作空間上使用表格Q-learning算法來學習報價策略。其方法是將效用空間離散化，并使用對手模型從一組提議中選擇下一個提議，其中每個時間步驟的提議集合取決于所采取的行動。這種方法的局限性是因效用空間的離散化導致的信息損失，這將導致進一步依賴對手建模來選擇下一個提議。RLBOA框架如圖5所示[36]。

圖5 RLBOA框架

3.2 ANEGMA模型

2020年，Pallavi Bagga等人[35]提出了一個新的協商模型ANEGMA，該模型允許智能體學習如何在未知和動態的電子市場中進行雙邊協商。該智能體使用一個Modle-Free強化學習的Actor-Critic架構來學習一個深度神經網絡的策略。該方法基于深度確定性策略梯度算法(DDPG)，以支持連續控制，為買方生成確定性動作選擇策略。通過監督綜合的市場數據來預培訓策略，從而減少了協商過程中學習所需要的探索時間，因此，可以為雙邊協商構建不需要預先編程即可適應不同的電子市場設置的自動智能體。這項工作的缺點是它只解決單一問題，其RL智能體的狀態和動作是特定的值，所以它僅限于特定的協商場景，不能在其他的協商場景中發揮作用。ANEGMA框架如圖6所示[35]。

圖6 ANEGMA框架

3.3 基于強化學習策略和自適應策略切換機制的智能體自動協商框架

2021年，Ayan Sengupta等人[37]提出了一個基于強化學習策略和自適應策略切換機制的智能體自動協商框架，如圖7所示[37]。

圖7 基于強化學習策略和自適應策略切換機制的智能體自動協商框架框架

這個框架包含4個部分：negotiator-strategy pairs、對手分類器、策略切換機制以及reviewer機制。此框架允許對對手的行為進行實時分類，并提供了在單個協商過程中選擇、切換或組合策略的機制，即自適應地改變策略以達到更好的協議。此外還提出了一種以算法方式更新基策略的機制，以提高自動協商整體性能。用SAC算法來訓練競價策略，其輸入和輸出都是效用值，因此，可以用于不同的協商領域。這項工作的缺點是沒有考慮對手的偏好。

3.4 Deep BPR+agent

2021年，Leling Wu等人[38]提出了一個通用的協商框架——Deep BPR+協商智能體框架，包括兩個關鍵部分：一個是學習機制，當遇到使用以前未見過的策略的對手時，學習新的應對策略；另一個是策略重用機制，支持從觀察到的信號中準確地檢測對手的策略并從策略庫中選擇最佳應對策略。

它利用貝葉斯策略重用(BPR)機制，通過在智能體可用的若干策略中進行選擇來應對未知對手。BPR對一組已知策略的對手使用一個概率分布(貝葉斯信念)，以捕捉它們與智能體正在面對的新對手的相似性。貝葉斯信念隨著觀察到的信號而更新，這些信號可以是與策略性能相關的任何信息。在這項工作中，信號包括協議效用、協商回合數和從對手的提議收到的效用值的標準偏差。當一個未知的對手策略出現時，像BPR+那樣通過移動平均獎勵來識別，它就會切換到學習階段，并開始使用深度強化學習算法來學習最佳響應策略，該算法通過在每一步選擇適當的目標效用，以時間軸和提議交換歷史為條件來學習實現有效的協議。這項工作之后將加速在線新策略學習速度并將這一框架擴展到其他協商環境，如并發協商或多邊協商進行研究。

3.5 MCAN agent

2021年，Xiaoyang Gao等人[39]提出了一個新的基于DRL的協商框架——多渠道自動協商(MCAN)，利用參數化深度Q網絡(P-DQN)來學習一個綜合的協商策略，同時整合語言交流技能和報價策略。結合深度Q網絡(DQN)和深度確定策略梯度(DDPG)的優勢，P-DQN適合于這個雙重優化問題，它學習了每種語言溝通技能的最佳競價策略，然后選擇共同優化的策略。與其他分別學習語言溝通技能和報價策略的算法不同，P-DQN同時學習這兩種技能，這使得語言溝通技能學習和競價策略學習能夠共享所有信息，而不需要像兩個獨立的網絡那樣交換信息。MCAN智能體將對手的提議(如cheaptalk和offer)作為輸入，并將其發送給提議解析器。在更新狀態后，DRL策略輸出一個動作給提議生成器，指導最佳提議。根據用戶研究，其根據如何贏得朋友以及效用指標來評估MCAN智能體和基于規則的智能體。與人類協商的實驗結果表明，MCAN智能體學會了一種綜合語言交際技巧和報價策略的協商策略。這項工作之后將探索如何學習更復雜的語言溝通技能，并將其應用于自然語言處理，以實現更面向應用的架構。

3.6 通過個性建模改進協商對話模型

2021年，Runzhe Yang等人[40]將心智理論(Theory of Mind,ToM)[41]建模融入面向任務的對話系統中，提供了一種建模和推斷對手性格，預測對手心智狀態變化的模型，同時利用這種模型去調整智能體高級的語言動作策略。以當前狀態和自己所說的自然語言為輸入，輸出對手的假想反饋。這個假想的反饋能夠幫助智能體選擇更加合理的動作。為了預測對手的反饋，將對手的性格建模為一個能夠根據對話歷史得到的隱變量z，利用這個隱變量z、歷史的狀態和當前所有可能采取的動作來計算對手反饋的分布，進而可以計算出對于每個動作，它所能得到的長期收益，最終選出當前最合適的動作。這項工作在克雷格(CRAIGSLISTBARGAIN)[42]數據集上進行了方法測試，結果表明所提的方法使用ToM作推斷，相較基線能提升20%以上的交易成交率。此外，模型在面對不同類型的對手時，能夠展現出多樣性的協商行為。這項工作之后的方向包括開發有效的方案來逼近未來狀態的值計算，探索更高階的ToM，以及將ToM更緊密地整合到話語生成和處理中。協商系統的心智理論框架如圖8所示[40]。

圖8 協商系統的心智理論框架

4 結束語

本文對現有的基于深度強化學習的自動協商任務進行了綜述，從提出的背景、基本概念、算法的思想及模型優缺點等方面進行了詳細的分析。強化學習和自動協商任務相結合的研究備受關注，推動了利用強化學習方法進行自動協商的研究和發展，且已取得了一定的成果，但該結合研究仍存在問題和挑戰亟需解決。深度強化學習領域的算法依然存在著其自身問題，例如訓練不穩定、需要人為設計獎勵函數等。因此，如何提高生成模型的性能是深度強化學習能在自動協商任務中得以廣泛應用的重要研究方向。同時，目前利用強化學習算法及思想解決自動協商任務，僅局限在經典的強化學習算法。深度強化學習發展至今有許多改進算法及新的模型，因此如何將更適合的強化學習算法有效地應用于自動協商任務，也是另一個亟待探索的研究方向。