反事實遺憾

概述

反事實遺憾（CFR）是博弈論和人工智能領域的一個重要概念。它由Martin Zinkevich等人於2008年提出，用於解決不完全信息遊戲中的策略優化問題。在德州撲克等遊戲中，CFR是遺憾最小化算法的核心組成部分，已被廣泛用於構建高級AI，例如Libratus和Pluribus。

原理

反事實遺憾衡量的是，在給定特定信息集（玩家當前知道的所有信息）的情況下，如果玩家選擇了不同的行動而不是實際採取的行動，他們會獲得的收益差異。具體來說，對於每個信息集和每個可能的行動，算法計算該行動的「反事實遺憾值」：假設玩家在所有其他決策點遵循當前策略，僅在此節點更改行動，遺憾值等於新行動的預期收益減去當前策略的預期收益。

每輪遊戲結束後，算法根據實際結果更新每個信息集下行動的遺憾值。隨著迭代次數增加，遺憾累積並用於調整策略：遺憾較低（即較少後悔）的行動被分配較高的概率。最終，當所有信息集下的平均遺憾接近零時，策略收斂到納什均衡。

在德州撲克中的應用

CFR特別適合於像德州撲克這樣包含隱藏信息、隨機性和多輪決策的遊戲。由於完整的遊戲樹過大，實際應用中通常使用抽象技術（如狀態聚類和動作抽象）來降低複雜性。通過數萬億次的自對弈模擬，CFR可以生成接近最優的策略，並已在單挑無限注德州撲克中擊敗頂級人類玩家。

與相關術語的關係

• 遺憾最小化（RM）：CFR是RM在多玩家、不完全信息場景中的擴展，共享相同的核心思想。
• 納什均衡：CFR的目標是找到混合策略納什均衡，其中任何玩家都不能通過單方面改變策略而獲益。
• 策略迭代：CFR通過重複迭代更新策略，不同於傳統的值迭代或策略梯度方法。