用于在多方策略互动中进行策略搜索的采样方案

摘要

本文公开的方法、系统和装置，包括在计算机存储介质上编码的计算机程序，用于执行反事实遗憾最小化(CRF)以在多方策略互动中进行策略搜索。所述方法之一包括：识别第一方在所述第一方的第一状态下的N1个可能动作；以第一采样概率从所述第一方在第一状态下的所述N1个可能动作中采样出可能动作；识别所述第一方在所述第一方的第二状态下的N2个可能动作，其中，所述第一方的第一状态比所述第一方的第二状态更接近IIG的开始状态；以第二采样概率从所述第一方在第二状态下的所述N2个可能动作中采样出可能动作，其中，所述第一采样概率小于所述第二采样概率。

说明书

技术领域

本文涉及在两方或更多方之间的策略互动中进行策略搜索。

背景技术

两方或更多方之间的策略互动可以通过涉及两方或更多方(也称为玩家)的博弈来建模。在涉及两个或更多个玩家的不完美信息博弈(imperfect information games，IIG)中，玩家在做出决策之前只能部分地了解其对手。这类似于现实场景，例如贸易、流量交通路线规划和公开拍卖。许多现实生活场景可以表示为IIG，例如不同公司之间的商业竞争、拍卖场景中的竞标关系、欺诈方和反欺诈方之间的博弈关系。

求解IIG的方法具有很大的经济和社会效益。由于信息隐藏，因此玩家必须在对其对手信息不确定的情况下进行推理，并且玩家还需要采取行动以利用其对手对其自己的信息的不确定的优势。

发明内容

本文的实施方式包括计算机实现的用于在多方策略互动中进行策略搜索的方法。更具体地，本文描述了用于在求解不完美信息博弈(IIG)时执行反事实遗憾最小化(CRF)算法的采样方案的示例，该方法可以降低计算的复杂度和方差同时提高CRF算法的收敛速度。本文还描述了用神经网络执行反事实遗憾最小化(CRF)的技术，由于神经网络的泛化能力，它可以节省存储空间并提供更快的收敛。

本文中描述的在特定实施例中实现的主题实现了以下技术效果和优势中的一个或多个。在一些实施例中，所描述的采样技术可以以更有效的方式帮助寻找例如资源分配、产品/服务推荐、网络攻击预测和/或预防、流量交通路线规划、欺诈管理等的现实场景的更好策略，这些现实场景可被建模或表示为多方策略互动、例如涉及两方或更多方的IIG。在一些实施例中，所描述的技术可以提高反事实遗憾最小化(CRF)算法在寻找由IIG建模的现实场景的最佳策略时的计算效率并降低计算负荷。在一些实施例中，所描述的采样技术可以提供比结果采样更低的方差，同时比外部采样具有更高的存储效率。在一些实施例中，所描述的技术可以提高CRF算法在寻找纳什(Nash)均衡以求解代表一个或多个现实场景的博弈时的收敛速度。在一些实施例中，所描述的技术提供表示IIG的博弈树的更平衡和全面的信息，使得CRF算法可以具有更小的方差和更快的收敛速度。在一些实施例中，所描述的技术通过使用神经网络结合CRF算法，节省了存储空间并提供了更快的收敛。在一些实施例中，所描述的技术可以仅需要少量存储空间用于CRF算法的每次迭代。

本文还提供了耦接一个或多个处理器并且其上存储有指令的一个或多个非暂时性计算机可读存储介质，所述指令当由所述一个或多个处理器执行时，促使所述一个或多个处理器按照本文提供的方法的实施例执行操作。

本文还提供了用于实施本文提供的所述方法的系统。所述系统包括一个或多个处理器以及耦接到所述一个或多个处理器并且其上存储有指令的计算机可读存储介质，所述指令当由所述一个或多个处理器执行时，促使所述一个或多个处理器按照本文提供的方法的实施例执行操作。

应了解，依据本文的方法可以包括本文描述的方面和特征的任意组合。也就是说，根据本文的方法不限于本文具体描述的方面和特征的组合，还包括所提供的方面和特征的任意组合。

以下在附图和描述中阐述了本文的一个或多个实施例的细节。根据说明书和附图以及权利要求，本文的其他特征和优点将显现。

附图说明

图1是根据本文的实施例示出的单牌扑克中的部分博弈树的示例的图。

图2是根据本文的实施例示出的不同采样方案的示例的图。

图3是根据本文的实施例的鲁棒采样蒙特卡罗CFR(MCCFR)的示例的伪代码。

图4是根据本文的实施例示出的应用于博弈树的双神经CFR算法的示例的图。

图5是根据本文的实施例的双神经CFR算法的示例的伪代码。

图6是根据本文的实施例的用于优化与双神经CFR算法相关的神经网络的算法的示例的伪代码。

图7是根据本文的实施例的小批量MCCFR算法的示例的伪代码。

图8是根据本文的实施例示出的用于执行MCCFR的采样处理的示例的流程图。

图9是根据本文的实施例示出的双神经CFR算法的示例的流程图。

图10描绘了根据本文的实施例示出的计算机实现的用于提供与所描述的算法、方法、功能、处理、流程和程序相关联的计算功能的系统的示例的框图。

图11描绘了根据本文的实施例的装置的模块的示例。

图12描绘了根据本文的实施例的另一装置的模块的示例。

各附图中相同的附图标记和名称表示相同的元件。

具体实施方式

本文的实施方式包括计算机实现的例如通过求解不完美信息博弈(IIG)在多方策略互动中进行策略搜索的方法。IIG可以代表例如资源分配、产品/服务推荐、网络攻击预测和/或预防、流量交通路线规划、欺诈管理等一个或多个现实场景，其中，涉及两方或更多方(也称为玩家)，且每方可以具有关于他方的决策的不完全或不完美信息。更具体地，本文描述了用于在求解IIG时执行反事实遗憾最小化(counterfactual regret minimization，CRF)算法的采样方案的示例，可以降低计算的复杂度和方差同时提高CRF算法的收敛速度。本文还描述了用神经网络执行反事实遗憾最小化(CRF)的技术，由于神经网络的泛化能力，它可以节省存储空间并提供更快的收敛。

纳什均衡是涉及两个或更多个玩家的IIG的典型解法。反事实遗憾最小化(CRF)是一种旨在近似找到大型博弈的纳什均衡的算法。CRF试图最小化整体的反事实遗憾。事实证明，所有迭代中的多个策略的平均值会收敛到纳什均衡。在求解博弈时，原始形式的CRF(也称为原始CRF、标准CRF、普通CFR或简称CRF)在每次迭代中遍历整个博弈树。因此，原始CFR需要大容量存储器处理大型零和扩展式博弈，例如单挑无限注德州扑克。在某些情况下，原始CFR可能无法用有限存储器处理大型博弈。

引入蒙特卡洛CFR(Monte Carlo CFR，MCCFR)以使反事实遗憾最小化。MCCFR可以计算反事实值(counterfactual value)的无偏估计，并避免遍历整个博弈树。由于在每次迭代中仅访问所有信息集的子集，因此MCCFR所需的存储空间比原始CFR少。

可以使用结果采样(outcome sampling)算法或外部采样(external sampling)算法来执行MCCFR。MCCFR中的结果采样算法的方差大，并且难以在较少的迭代步骤中收敛到近似纳什均衡解。MCCFR中的外部采样算法的方差比结果采样算法的方差小，但该方法的缺点类似于CFR的缺点。当博弈树很大时，它需要非常大的存储空间，并且不能扩展到复杂的大规模IIG。

本文公开了一种鲁棒采样(robust sampling)方案。在所述鲁棒采样方案中，每个玩家在当前决策点使用均匀采样(uniform sampling)方法进行采样，而他方根据相应的策略进行采样。对应于不同迭代的到达概率可以是固定的。可以证明，该鲁棒采样方案的方差比MCCFR中的结果采样方案的方差小，同时比外部采样的存储效率高。在一些实施例中，该鲁棒采样方案可以使MCCFR以更快的收敛求解纳什均衡。

本文公开了一种深度依赖采样方案。所述深度依赖采样方案可以将更高的采样概率分配给更接近终点(terminal)状态的状态，而不是与终点状态更远(或更接近初始状态或开始状态)的另一状态。在一些实施例中，所述深度依赖采样方案可以允许更接近终点状态的状态更多地被采样，从而提供IIG的更全面(well-around)信息，因此与现有采样方案相比提高了MCCFR的收敛速率。

本文还公开了双神经CFR算法。现有的CFR方法，如CFR和MCCFR，使用两个基于表格的大容量存储器来记录所有信息集的累积遗憾和平均策略。这种表格表示形式使得这些方法难以以有限的时间和空间应用于大型扩展式的博弈。

相比之下，双神经CFR算法使用两个神经网络来计算IIG的近似纳什均衡。例如，其中一个神经网络可用于学习累积遗憾，另一个神经网络可用于学习平均策略分布(strategy profile)的累积分子。在这两个网络的帮助下，双神经CFR算法不需要使用基于表格的两个大容量存储器。基于该紧凑神经网络的泛化能力，累积遗憾和平均策略可以被学习和生成。所公开的双神经CFR算法可以保持MCCFR需要较少的计算负荷的益处还不需要两个大容量表格式存储器。即使存在存储器限制，所公开的双神经CFR算法也可用于大型博弈中。在一些实施例中，相比于现有技术，双神经方法可以以更少的迭代实现更低的可利用性。另外，在一些实施例中，在从不良表格策略初始化之后，双神经CFR还可以持续改进。

在一些实施例中，所描述的技术可以用于例如AI扑克、推荐平台和许多其他AI和机器学习的应用。所描述的技术使用蒙特卡罗方法，并且不需要针对整个博弈树的变量。

在一些实施例中，具有玩家有限集合N＝{0,1,...,n-1}的扩展式博弈可以表示如下。定义h

历史{h∈H:P(h)＝i}的I

图1是根据本文的实施例示出的单牌扑克中的部分博弈树102和部分博弈树104的示例的图100。单牌扑克是双玩家IIG扑克。单牌扑克是扩展式博弈的示例。

博弈树是有向图。博弈树的节点表示博弈中的位置(或玩家状态)，并且博弈树表示的节点可以表示博弈的玩家的行动或动作。在图1中，z

在第一部分树102中，两个玩家(玩家0和玩家1)被发牌(Q,J)，如左子树中的“0:Q1:J”和(Q,J)，如右子树中所示的“0:Q 1:K”。

从根节点到每个节点的轨迹是动作的历史。动作由博弈树的边(用箭头表示)旁边的字母(例如，F、C、P和B)或表达式(例如，“0:Q 1:J”)表示。

在扩展式博弈中，h

在该IIG中，玩家1的私人牌对于玩家0是不可见的，因此对于玩家0来说h

通常，任何I

策略分布σ＝{σ

对于玩家i，策略分布σ的预期博弈效用被表示为

策略σ

对于诸如CFR的迭代方法，σ

信息集I

在大型零和IIG中，CFR被证明是用于计算纳什均衡的有效方法。可以证明，一个玩家的状态到达概率与对手的隐藏变量的后验概率成比例，即，

对于玩家i和策略分布σ，状态h下的反事实值(CFV)v

其中

类似地，信息集I

然后，可以根据式(2)计算动作a在T次迭代之后的累积遗憾:

其中R

从迭代1到T的平均策略

其中，

在迭代t中定义

其中S

在求解博弈时，原始CFR在每次迭代中遍历整个博弈树。因此，原始CFR可能无法用有限的存储器处理大型博弈。引入蒙特卡洛CFR(MCCFR)以使反事实遗憾最小化。MCCFR可以计算反事实值的无偏估计并避免遍历整个博弈树。由于在每次迭代中仅访问所有信息集的子集，因此MCCFR所需的存储空间比原始CFR少。

例如，定义Q＝{Q

图2是根据本文的实施例示出的不同采样方案的示例的图200。具体地，子图A示出了博弈树的外部采样方案202的示例；子图B示出了博弈树的结果采样方案204的示例，子图C示出了博弈树的鲁棒采样方案206的示例。

如图2中所示，圆圈表示玩家0节点，矩形表示玩家1节点，三角形表示机会节点。实线边或箭头表示被采样的动作，而虚线边或箭头表示未被采样的动作。阴影节点表示被采样的节点，而空白节点表示未被采样的节点。

以玩家0的更新为例，用如子图A所示的外部采样方案202，玩家0节点遍历玩家0节点的所有分支，非玩家0节点(例如，玩家1节点和机会节点)根据相应采样策略对分支进行随机采样。

结果采样方案不区分不同玩家。如子图B所示，结果采样方案204根据相应采样策略随机地针对所有玩家对一个分支进行采样。因此，在结果采样方案下只会对一个轨迹进行采样。

如子图C所示，鲁棒采样方案206根据玩家0的均匀分布随机选择k个分支，并根据相应采样策略对非玩家0节点的一个分支进行随机采样。通过改变k的值，鲁棒采样方案可以对多个路径或单个路径进行采样，例如，取决于实际存储器需求或系统规范。与外部采样方案不同，鲁棒采样方案不需要每次都了解在当前玩家i的决策点的所有可能动作和变量。

在一些实施例中，在外部采样和结果采样方案中，每个块Q

在结果采样方案中，将仅对一个轨迹进行采样，使得

证明了MCCFR中的采样反事实值是CFR中实际反事实值的无偏估计：

定义σ

其中

对于鲁棒采样，可以将采样简档定义为

在一些实施例中，如果玩家i根据在信息集I

并且在给定采样简档σ

为简化符号，令k＝max表示k＝max

如果k＝1且

如果在状态h没有对动作a进行采样，即

如果k＝1，且玩家i根据信息集I

对于a∈A

如果在状态h没有对动作a进行采样，即

图3是根据本文的实施例的鲁棒采样MCCFR的示例的伪代码300。如伪代码300的第1-5行所示，整体鲁棒采样MCCFR是输入为总迭代次数t的迭代算法。在每次迭代t内，针对玩家0和玩家1调用鲁棒采样MCCFR(RS-MCCFR)函数(如第3和第4行所示)，以更新累积遗憾R

具体地，函数RS-MCCFR根据如上结合图2所述的鲁棒采样方案对多个动作进行采样。如伪码300的第16行所示，可以根据鲁棒采样策略

在一些实施例中，可以使用深度依赖采样方案来提供由博弈树表示的博弈的更平衡或全面的信息。例如，采样策略

在一些实施例中，深度依赖采样方案可以与鲁棒采样、结果采样、外部采样或任何其他合适的采样算法结合使用。例如，深度依赖采样方案可以进一步改善鲁棒采样、结果采样和外部采样中任一项的方差和收敛速度，因为后三种采样方案更多地关注于玩家状态博弈树的不同动作之间的水平采样(例如，表示为博弈树的一个节点的不同分支)。

图4是根据本文的实施例示出的应用于博弈树410的双神经CFR算法的示例400的图。双神经CFR算法400使用两个神经网络420和430来计算IIG，例如由博弈树410表示，的近似纳什均衡。如图4中所示，一个神经网络420用于获得累积遗憾并且被称为RegretSumNetwork(RSN)。另一神经网络430用于获得平均策略，并且被称为AveStrategyNetwork(ASN)。

在一些实施例中，CFR算法的迭代更新维持两种策略：当前策略σ

根据公式(3)，可以通过累积遗憾R

如图4所示，存储器

根据式(4)，近似纳什均衡是T次迭代中所有先前策略的加权平均。类似于累积遗憾，被表示为

在一些实施例中，在每次迭代中，

在一些实施例中，如果大容量存储器可用于在多次迭代内汇总并保存

在一些实施例中，在每次迭代中，仅对信息集的小的子集进行采样，这可能导致神经网络RSN 420和ASN 430忘记那些未观察到的或未采样的信息集的值。为了解决这个问题，来自先前迭代的神经网络参数可以用作当前迭代的初始值，为更新提供了在线学习/适应特色。此外，由于神经网络的泛化能力，即使来自信息集的少量样本也可用于更新新神经网络，并且新更新的神经网络可以为累积遗憾和平均策略产生良好的值。

在一些实施例中，随着迭代次数t增加，R

其中R^

在一些实施例中，例如，由于存储器

在一些实施例中，为了用有限存储器但无限迭代来持续改进平均策略和/或进一步减轻对存储器容量的要求，可以使用利用两个贮存器(reservoir)M

在一些实施例中，可以根据重写公式(2)的公式(10)获得T次迭代之后的平均累积遗憾：

类似地，平均策略可以是累积策略的归一化，如公式(4)所示，是由其到达概率

在一些实施例中，两个一样的贮存器M

请注意，双增量CFR算法和双贮存器CFR算法均采用在线学习的思想，并分别使用两个神经网络来学习更新遗憾和平均策略。在一些实施例中，不需要在每次迭代中更新ASN，而在蒙特卡洛采样之后可能需要对RSN进行优化以产生新的行为策略。例如，当使用新的行为策略遍历博弈树时，可能需要在每次迭代时更新RSN。另一方面，ASN可以用作最终的近似纳什均衡，其是行为策略的加权平均。ASN可以用作双神经CFR算法的输出。如果有足够大的数据存储设备来保存所有样本，则只需要在最后一步优化平均策略。实际上，对于大型博弈，大容量数据存储设备可能非常昂贵。这样，如果数据存储设备(例如，贮存器

双神经CFR算法和双贮存器CFR算法具有不同的样本集。对于双增量CFR，基于新增的多个样本对神经网络进行优化。对于双贮存器CFR，基于固定大小的贮存器中的多个样本对神经网络进行优化。另外，在双贮存器法中，平均策略可以通过最大对数似然而不是最小均方误差来优化。

图5是根据本文的实施例的双神经CFR算法的示例的伪代码500。该双神经CFR算法的示例包括使用双神经CFR算法或双贮存器CFR算法的选项。

伪代码500的第3-7行显示了第一次迭代中初始化策略的示例。例如，如果系统根据现有CFR方法(例如基于表格的CFR或MCCFR方法或该双神经CFR方法)热启动，则可以根据现有策略分布初始化神经网络以克隆累积遗憾和策略。如果没有热启动初始化，则双神经CFR算法可以在迭代t＝1时通过随机初始化RSN和ASN中的参数来启动。

在一些实施例中，如果使用双增量CFR算法，如伪代码500的第8行所示，则可以使用采样方法来返回该迭代中被采样信息集的反事实遗憾和平均策略分子。该迭代中被采样信息集的反事实遗憾和平均策略分子可以分别保存在存储器

在一些实施例中，如果使用双贮存器CFR算法，则该迭代中被采样信息集的反事实遗憾和平均策略分子(例如在双增量CFR算法中保存在存储器

如伪代码500的第13-15行所示，该迭代中被采样信息集的这些反事实遗憾和平均策略分子可以由图6所示的NeuralAgent算法使用，以优化两个神经网络RSN和ASN，并返回RSN和ASN(例如，

图6是根据本文的实施例的用于优化与双神经CFR算法相关的神经网络的算法的示例的伪代码600。该算法的示例称为NeuralAgent算法。所描述的双神经CFR算法可以使用其他算法来优化在双神经CFR算法中使用的一个或两个神经网络。

将β

在一些实施例中，现有的优化器可能因潜在的鞍点或局部最小值而不会返回足够低的损失。为了获得相对较高的精度和较低的优化损失，专门设计了一种调度器，以在损失已停止减少时降低学习率。具体地，调度器读取度量值量，例如均方误差，并且如果若干回合内没有看到改善，则学习率被降低了一个因子。另外，一旦损失在β

在实验中，可以如下设置神经网络的超参数。例如，对于RSN，神经批量大小(batchsize)为256，学习率β

对于ASN，提前停止标准的损失可以设置为10

图7是根据本文的实施例的小批量MCCFR算法的示例的伪代码700。小批量MCCFR算法(表示为Mini-Batch-MCCFR-NN)包括用于获取博弈的被采样信息集的反事实遗憾和平均策略分子的采样算法。与仅在一次迭代中对一个块进行采样并提供一个原始CFV的无偏估计量的传统的结果采样和外部采样不同，小批量采样技术可以在一次迭代中随机采样b个块。伪代码700中所示的小批量MCCFR算法的示例基于上述鲁棒采样。在一些实施例中，小批量MCCFR算法可以与诸如深度依赖采样方案的其他采样方案结合使用。请注意，小批量MCCFR算法是用于获取博弈的被采样信息集的反事实遗憾和平均策略分子的算法的示例。双神经CFR算法可以使用其他算法来获取博弈的被采样信息集的反事实遗憾和平均策略分子。

令Q

此外，可以表明v～

同样，动作a的累积小批量遗憾是

其中R～

注意，小批量MCCFR使用遗憾匹配算法来更新累积小批量遗憾R

其中，(x)

如伪代码700的第1-6行所示，Mini-Batch-MCCFR-NN是输入为总迭代次数t的迭代算法。在每次迭代中，MCCFR-NN函数分别被调用用于玩家0和玩家1(如第4和5行所示)，并且该迭代中的被采样信息集的反事实遗憾和平均策略分子分别被返回并被保存在存储器

函数MCCFR-NN可以定义为如伪代码700的第8-33行所示的。函数MCCFR-NN像表格MCCFR一样遍历博弈树，它从根历史

图8是根据本文的实施例的用于执行MCCFR的采样处理800的示例的流程图。采样处理800可以是上述用于执行反事实遗憾最小化(CRF)以在两方或更多方之间的策略互动中进行策略搜索的深度依赖采样方案的示例。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。IIG可以代表涉及两方或更多方的一个或多个现实场景，例如资源分配、产品/服务推荐、网络攻击预测和/或预防、流量交通路线规划、欺诈管理等，其中，每方可以具有关于他方的决策的不完全或不完美信息。作为示例，IIG可以表示至少涉及第一玩家和第二玩家的合作产品/服务的推荐服务。第一玩家可以是，例如，具有客户(或用户)信息、产品和服务信息、客户的购买历史等的在线零售商。第二玩家可以是，例如，具有该客户的社交网络数据的社交网络平台、具有该客户的财务信息的银行或其他金融机构、汽车经销商或在预测和向该客户推荐产品和服务时具有关于该客户的偏好、需求、财务状况、位置等客户信息的任何其他方。第一玩家和第二玩家可能各自具有不希望与他人共享的专有数据。第二玩家可以在不同时间向第一玩家仅提供部分信息。这样，第一玩家对第二玩家的信息只有有限访问权。为方便起见，处理800将被描述为数据处理装置，如，位于一个或多个位置并根据本文被适当地编程的一个或多个计算机的系统。例如，被适当地编程的图10的计算机系统1000可以执行处理800。

在810处，数据处理装置识别第一玩家在第一玩家的第一状态下的N1个可能动作。在一些实施例中，IIG可以由博弈树(例如，博弈树102、104、202、204或206)表示。第一玩家的第一状态可以由博弈树的第一节点(例如，博弈树102中的玩家0的节点h1)表示，并且N1个可能动作可以是博弈树的第一节点的边或分支(例如，博弈树102中玩家0的节点h1的P和B边)。在合作产品/服务的推荐服务的示例中，第一玩家的第一状态包括第二玩家所提供信息的历史，并且第一玩家的N1个可能动作包括响应于第二玩家所提供信息的历史的N1个可能动作，以向客户提供产品/服务推荐。第一玩家的第一状态和可能动作可以包括由IIG建模的其他现实场景中的其他特征。

在820处，数据处理装置以第一采样概率从第一玩家在第一状态下的N1个可能动作中采样出可能动作。在一些实施例中，数据处理装置可以从第一玩家在第一状态下的N1个可能动作中采样出k1个可能动作，其中，k1个可能动作中的每个动作都以相同的第一采样概率被采样。

在830处，数据处理装置识别第一玩家在第一玩家的第二状态下的N2个可能动作，其中，第一玩家的第一状态比第一玩家的第二状态更接近IIG的开始状态。在博弈树102的示例中，第一玩家的第二状态可以是例如h7节点，其比第一玩家的第一状态(例如，博弈树102中的玩家0的节点h1)距离博弈树102的开始状态(例如，h0节点)更远。

在840处，数据处理装置以第二采样概率从第一玩家在第二状态下的N2个可能动作中采样出可能动作，其中，第一采样概率小于第二采样概率。在一些实施例中，数据处理装置从第一玩家在第二状态下的N2个可能动作中采样出k2个可能动作，其中，k2个可能动作中的每个动作都以相同的第二采样概率被采样。

在850处，数据处理装置基于从第一玩家在第一状态下的N1个可能动作中采样出的可能动作和从第一玩家在第二状态下的N2个可能动作中的采样出可能动作执行CRF。在一些实施例中，可以根据相对于图3和/或图7描述的示例性技术来执行CRF。

在一些实施例中，输出是通过求解IIG产生的第一玩家的策略。该策略可以包括由IIG建模的现实场景中第一玩家的一系列动作。例如，在合作产品/服务的推荐场景中，通过求解IIG产生的第一玩家的策略可以包括，如，响应于第二玩家提供的信息的一系列动作、基于第一玩家的信息给客户的相应产品/服务的推荐、以及由第二玩家提供的信息。通过求解IIG产生的第一玩家的输出策略可以包括由IIG建模的其他现实场景中的其他信息。

在一些实施例中，基于从第一玩家在第一状态下的N1个可能动作中采样出的可能动作和从第一玩家在第二状态下的N2个可能动作中采样出的可能动作执行CRF，包括：计算从第一玩家在第一状态下的N1个可能动作中采样出的可能动作的遗憾值(例如，根据公式(1a)和/或公式(2))；计算从第一玩家在第二状态下的N2个可能动作中采样出的可能动作的遗憾值(例如，根据公式(1a)和/或公式(2))；基于N1个可能动作中采样出的可能动作的该遗憾值更新第一玩家在第一状态下的第一策略(例如，根据公式(3))；以及基于N2个可能动作中采样出的可能动作的该遗憾值更新第一玩家在第二状态下的第二策略(例如，根据公式(3))。

在一些实施例中，数据处理装置基于从第一玩家在第一状态下的N1个可能动作中采样出的k1个可能动作和从第一玩家在第二状态下的N2个可能动作中采样出的k2个可能动作执行CRF。

在一些实施例中，可以结合深度依赖采样进行鲁棒采样。例如，第一采样概率是k1/N1，第二采样概率是k2/N2。这样，根据均匀分布该可能动作被采样。

在一些实施例中，2<＝k1<＝N1且2<＝k2<＝N2，以便玩家的每个状态都会有一个以上的可能动作被使用。

在一些实施例中，k1＝k2，因此在第一玩家的第一状态和第二状态下选择或访问相等数量的样本。

类似地，可以结合第二玩家进行深度依赖采样。例如，数据处理装置识别第二玩家在第二玩家的第一状态下的M1个可能动作。数据处理装置以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作。数据处理装置识别第二玩家在第二玩家的第二状态下的M2个可能动作，其中，第二玩家的第一状态比第二玩家的第二状态更接近IIG的开始状态。数据处理装置以第四采样概率从第一玩家在第二状态下的M2个可能动作中采样出可能动作，其中，第三采样概率小于第四采样概率。

在一些实施例中，可以结合第一玩家和第二玩家两者进行深度依赖采样。在一些实施例中，数据处理装置识别第二玩家在第二玩家的第一状态下的M1个可能动作，其中，第一玩家的第一状态(例如，博弈树102中的玩家0的状态h1)比第二玩家的第一状态(例如，博弈树102中的玩家1的状态h4)更接近IIG的开始状态(例如，h0状态)。数据处理装置以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作，其中，第三采样概率大于第一采样概率。

图9是根据本文的实施例的用于执行MCCFR的双神经CFR算法900的示例的流程图。采样处理900可以是如上针对图4至图7描述的用于执行反事实遗憾最小化(CRF)以在两个或更多个玩家之间的策略互动中进行策略搜索的双贮存器CFR算法的示例。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。IIG可以代表涉及两方或更多方的一个或多个现实场景，例如资源分配、产品/服务推荐、网络攻击预测和/或预防、流量交通路线规划、欺诈管理等，其中，每方可以具有关于他方的决策的不完全或不完美信息。作为示例，IIG可以表示至少涉及第一玩家和第二玩家的合作产品/服务的推荐服务。第一玩家可以是，例如，具有客户(或用户)信息、产品和服务信息、客户的购买历史等的在线零售商。第二玩家可以是，例如，具有该客户的社交网络数据的社交网络平台、具有该客户的财务信息的银行或其他金融机构、汽车经销商或在预测和向该客户推荐产品和服务时可能具有关于该客户的偏好、需求、财务状况、位置等客户信息的任何其他方。第一玩家和第二玩家可能各自具有不希望与他人共享的专有数据。第二玩家可以在不同时间向第一玩家仅提供部分信息。这样，第一玩家对第二玩家的信息只有有限访问权。为方便起见，处理900将被描述为数据处理装置，如，位于一个或多个位置并根据本文被适当地编程的一个或多个计算机的系统。例如，被适当地编程的图10的计算机系统1000可以执行处理900。

在910处，数据处理装置初始化第一神经网络的参数和第二神经网络的参数。第一神经网络(例如，RegretSumNetwork(RSN)420)可用于预测玩家状态下的可能动作的遗憾值。在合作产品/服务的推荐服务的示例中，玩家状态包括第二玩家所提供信息的历史，并且玩家的可能动作包括响应于第二玩家所提供信息的历史的可能动作，以向客户提供产品/服务的推荐。第二神经网络(例如，AveStrategyNetwork(ASN)430)可用于预测玩家状态下的可能动作的策略值。在一些实施例中，数据处理装置根据热启动分别初始化参数，例如基于在先前迭代中或基于现有CRF算法获得的第一神经网络的参数和第二神经网络的参数分别初始化参数。在一些实施例中，数据处理装置随机地初始化第一神经网络的参数和第二神经网络的参数。

在920处，数据处理装置在第一数据存储设备(例如，贮存器M

在一些实施例中，在求解IIG的CRF算法的两次或更多次迭代的每次迭代中，数据处理装置根据采样方案从玩家在第二状态下的多个可能动作中采样出可能动作；计算玩家在第二状态下的该可能动作的反事实值(例如，根据公式(1))；基于玩家在第二状态下的该可能动作的该反事实值，计算玩家在第二状态下的该可能动作的遗憾值(例如，根据公式(1a)和/或公式(2))；根据遗憾匹配算法，基于玩家在第二状态下的该可能动作的该遗憾值，计算玩家在第二状态下的该可能动作的更新策略(例如，根据公式(3))；以及基于玩家在第二状态下的该可能动作的该更新策略，计算玩家在第二状态下的该可能动作的策略值(例如，根据公式(4)和/或公式(5))。

在一些实施例中，数据处理装置可以获得新遗憾样本(例如，通过执行MCCFR的另一次迭代)。所述数据处理装置可以根据贮存器采样算法将新遗憾样本存储到第一数据存储设备中。例如，根据贮存器采样算法将新遗憾样本存储到第一数据存储设备中，包括：确定第一数据存储设备是否已满；当确定第一数据存储设备已满，用新遗憾样本替换第一数据存储设备中的多个遗憾样本中的一个。

在930处，数据处理装置在第二数据存储设备(例如，贮存器M

在940处，例如，根据公式(7)，数据处理装置基于第一数据存储设备中的多个遗憾样本更新用于预测玩家状态下的可能动作的遗憾值的第一神经网络的参数。在一些实施例中，可以根据图6所示的NeuralAgent算法或任何其他用于优化神经网络的算法更新第一神经网络的参数。

在950处，例如，根据公式(8)，数据处理装置基于第二数据存储设备中的多个策略样本更新用于预测玩家状态下的可能动作的策略值的第二神经网络的参数。在一些实施例中，可以根据图6所示的NeuralAgent算法或任何其他用于优化神经网络的算法更新第二神经网络的参数。

在960处，数据处理装置识别玩家的第一状态以及玩家在第一状态下的第一可能动作。

在970处，数据处理装置使用第一神经网络的参数预测玩家在第一状态下的第一可能动作的第一遗憾值。在一些实施例中，玩家在第一状态下的第一可能动作的预测的第一遗憾值可以被用于CFR算法的下一次迭代中。

在980处，数据处理装置使用第二神经网络的参数预测玩家在第一状态下的第一可能动作的第一策略值。在一些实施例中，玩家在第一状态下的第一可能动作的预测的第一策略值可以被用于CFR算法的下一次迭代中。在一些实施例中，玩家在第一状态下的第一可能动作的预测的第一策略值可以被用于计算近似纳什均衡并作为CFR算法的输出。在一些实施例中，玩家在第一状态下的第一可能动作的预测的第一策略值可以包括在由IIG建模的现实场景中的第一玩家的一系列动作。例如，在合作产品/服务的推荐场景中，玩家在第一状态下的第一可能动作的预测的第一策略值可以包括，例如，响应于由第二玩家提供的信息的一系列动作、基于第一玩家的信息给客户的相应产品/服务的推荐、以及由第二玩家提供的信息。玩家在第一状态下的第一可能动作的预测的第一策略值可以包括由IIG建模的其他现实场景中的其他信息。

图10描绘了示出根据本文的实施例的计算机实现的用于提供与所描述的算法、方法、功能、处理、流程和程序相关联的计算功能的系统的示例的框图。图10是示出根据本公开的实施例的计算机实现的用于提供与所描述的算法、方法、功能、处理、流程和程序相关联的计算功能的系统1000的示例的框图。在所示的实施例中，系统1000包括计算机1002和网络1030。

所示的计算机1002旨在包含任何计算设备，例如服务器、台式计算机、膝上型计算机/笔记本计算机、无线数据端口、智能电话、个人数据助理(PDA)、平板计算机、这些设备中的一个或多个处理器、另一计算设备或计算设备的组合，包括计算设备的物理或反事实实例、或计算设备的物理或反事实实例的组合。另外，计算机1002可以包括输入设备，例如小键盘、键盘、触摸屏，另一输入设备或可以接受用户信息的输入设备的组合，以及传达与计算机1002的操作相关联的信息的输出设备，包括图形类型的用户界面(UI)(或GUI)或其他UI上的数字数据、视觉、音频、另一种类型的信息或各种类型的信息的组合。

计算机1002可以在分布式计算系统中充当客户端、网络组件、服务器、数据库的角色或另一持续性设备、另一角色或用于执行本公开中描述的主题的角色的组合。所示的计算机1002可通信地与网络1030耦接。在一些实施例中，计算机1002的一个或多个组件可以被配置为在包括基于云计算的环境、本地环境、全局环境、另一环境或环境组合的环境中操作。

在高级别上，计算机1002是可操作用于接收、发送、处理、存储或管理与所描述的主题相关联的数据和信息的电子计算设备。根据一些实施例，计算机1002还可包括服务器或与服务器可通信地耦接，包括应用服务器、电子邮件服务器、网络服务器、高速缓存服务器、流数据服务器、另一服务器或服务器的组合。

计算机1002可以通过网络1030(例如，来自另一计算机1002上执行的客户端软件应用)接收请求，并通过使用软件应用或软件应用的组合处理接收的请求来响应接收的请求。另外，还可以从内部用户(例如，从命令控制台或通过另一内部访问方法)、外部或第三方或者其他实体、个人、系统或计算机向计算机1002发送请求。

计算机1002的每个组件可以使用系统总线1003进行通信。在一些实施例中，计算机1002的任何或所有组件，包括硬件、软件或者硬件和软件的组合，可以使用应用编程接口(API)1012、服务层1013、或者API 1012和服务层1013的组合通过系统总线1003进行接口连接。API 1012可以包括用于例程、数据结构和对象类的规范。API 1012可以是独立于计算机语言的或依赖于计算机语言的，并且是指完整的接口、单个函数或甚至一组API。服务层1013向计算机1002或可通信地耦接到计算机1002的其他组件(无论是否示出)提供软件服务。使用服务层1013的所有服务客户可访问计算机1002的功能诸如由服务层1013提供的软件服务通过定义的接口提供可重用的、定义的功能。例如，该接口可以是用以JAVA、C++、另一种计算语言、或以可扩展标记语言(XML)格式、另一种格式或多种格式的组合提供数据的计算机语言的组合编写的软件。虽然示出为计算机1002的集成组件，但是替代实施例可以将API 1012或服务层1013示出为与计算机1002的其他组件有关的独立组件或可通信地耦接到计算机1002的其他组件(无论是否示出)。此外，在不脱离本公开的范围的情况下，API1012或服务层1013的任何或所有部分可以被实现为另一软件模块、企业应用或硬件模块的子模块(a child or a sub-module)。

计算机1002包括接口1004。尽管示出为单个接口1004，但是可以根据计算机1002的特定需要、期望或特定实施例使用两个或更多个接口1004。接口1004被计算机1002用来与在分布式环境中通信地链接到网络1030的另一计算系统(无论是否示出)进行通信。通常，接口1004可操作地与网络1030通信，并且包括以软件、硬件或者软件和硬件的组合编码的逻辑。更具体地说，接口1004可以包括支持与通信相关联的一个或多个通信协议的软件，以使得网络1030或接口1004的硬件可操作地在所示计算机1002之内和所示计算机1002之外通信物理信号。

计算机1002包括处理器1005。尽管示出为单个处理器1005，但是可以根据计算机1002的特定需要、期望或特定实施例使用两个或更多个处理器1005。通常，处理器1005执行指令并操纵数据以执行计算机1002的操作以及本公开中所描述的任何算法、方法、功能、处理、流程和程序。

计算机1002还包括数据库1006，该数据库1006可以保存用于计算机1002的数据、通信地链接到网络1030的另一组件(无论是否示出)的数据、或者计算机1002和另一组件的组合的数据。例如，数据库1006可以是存储与本公开一致的存储数据的内存、常规数据库或另一类型的数据库。在一些实施例中，根据计算机1002的特定需要、期望或特定实施例以及所描述的功能，数据库1006可以是两个或更多个不同数据库类型的组合(例如，混合内存和常规数据库)。尽管被示为单个数据库1006，但是可以根据计算机1002的特定需求、期望或特定实施例以及所描述的功能来使用相似或不同类型的两个或更多个数据库。尽管数据库1006被示为计算机1002的集成组件，但在替代实施例中，数据库1006可以在计算机1002的外部。作为示例，数据库1006可以包括上述存储遗憾样本1026的贮存器M

计算机1002还包括存储器1007，该存储器1007可以保存用于计算机1002的数据、通信地链接到网络1030的另一组件(无论是否示出)的数据、或者计算机1002和另一组件的组合的数据。存储器1007可以存储与本公开一致的任何数据。在一些实施例中，根据计算机1002的特定需要、期望或特定实施例以及所描述的功能，存储器1007可以是两种或更多种不同类型的存储器的组合(例如，半导体和磁存储设备的组合)。尽管被示为单个存储器1007，但是可以根据计算机1002的特定需求、期望或特定实施例以及所描述的功能来使用相似或不同类型的两个或更多个存储器1007。尽管存储器1007被示为计算机1002的集成组件，但在替代实施例中，存储器1007可以在计算机1002的外部。

应用1008是算法软件引擎，其提供根据计算机1002的特定需要、期望或特定实施例的功能，特别是关于本公开中描述的功能。例如，应用1008可以用作一个或多个组件、模块或应用。此外，尽管被示为单个应用1008，但是应用1008可以被实现为计算机1002上的多个应用1008。另外，尽管被示为与计算机1002集成，但是在替代实施例中，应用1008可以在计算机1002的外部。

计算机1002还可以包括电源1014。电源1014可包括可被配置为用户可更换的可充电电池或用户不可更换的不可充电电池。在一些实施例中，电源1014可以包括功率转换或管理电路(包括充电、备用或另一电源管理功能)。在一些实施例中，电源1014可以包括电源插头，以允许将计算机1002插入壁式插座或另一电源中，从而例如为计算机1002供电或为可充电电池充电。

可以存在与包含计算机1002的计算机系统关联或在其外部的任何数量的计算机1002，每个计算机1002通过网络1030进行通信。此外，在不脱离本公开的范围的情况下，术语“客户端”、“用户”或其他适当的术语可以适当地互换使用。此外，本公开预期许多用户可以使用一个计算机1002，或者一个用户可以使用多个计算机1002。

图11是根据本文的实施例的装置1100的模块的示例的图。装置1100可以是数据处理装置的示例性实施例，该数据处理装置用于执行反事实遗憾最小化(CRF)以在两个或更多个玩家之间的策略互动中进行策略搜索。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。作为示例，IIG表示至少涉及第一玩家和第二玩家的合作产品服务推荐服务，第一玩家对第二玩家的信息具有有限访问权。装置1100可以对应于上述实施例，并且装置1100包括：第一识别模块1101，用于识别第一玩家在第一玩家的第一状态下的N1个可能动作；第一采样模块1102，用于以第一采样概率从第一玩家在第一状态下的N1个可能动作中采样出可能动作；第二识别模块1103，用于识别第一玩家在第一玩家的第二状态下的N2个可能动作，其中，第一玩家的第一状态比第一玩家的第二状态更接近IIG的开始状态；第二采样模块1104，以第二采样概率从所述第一玩家在第二状态下的N2个可能动作中采样出可能动作，其中，所述第一采样概率小于所述第二采样概率；处理模块1105，用于基于第一玩家在第一状态下的N1个可能动作中的可能动作和第一玩家在第二状态下的N2个可能动作中的可能动作执行CRF。在一些实施例中，第一玩家的第一状态包括第二玩家所提供信息的历史，并且第一玩家的N1个可能动作包括响应于第二玩家所提供信息的历史的N1个可能动作，以向客户提供产品服务推荐。

在可选实施例中，处理模块包括：第一计算模块，用于计算第一玩家在第一状态下的N1个可能动作中的可能动作的遗憾值；第二计算模块，用于计算所述第一玩家在第二状态下的所述N2个可能动作中的可能动作的遗憾值；第一更新模块，用于基于所述N1个可能动作中的可能动作的遗憾值更新所述第一玩家在所述第一状态下的第一策略；第二更新模块，用于基于所述N2个可能动作中的可能动作的遗憾值更新第一玩家在第二状态下的第二策略。

在可选实施例中，第一采样模块从第一玩家在第一状态下的N1个可能动作中采样k1个可能动作，其中，k1个可能动作中的每个可能动作都以相同的第一采样概率被采样。第二采样模块从第一玩家在第二状态下的N2个可能动作中采样出k2个可能动作，其中，k2个可能动作中的每个可能动作以相同的第二采样概率被采样。

在可选实施例中，处理模块基于第一玩家在第一状态下的N1个可能动作中的k1个可能动作和第一玩家在第二状态下的N2个可能动作中的k2个可能动作执行CRF。

在可选实施例中，第一采样概率为k1/N1，第二采样概率为k2/N2。

在一个可选的实施例中，2<＝k1<＝N1和2<＝k2<＝N2。

在可选的实施例中，k1＝k2。

在可选实施例中，装置1100还包括：第三识别模块，用于识别第二玩家在第二玩家的第一状态下的M1个可能动作；第三采样模块，用于以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作；第四识别模块，用于识别第二玩家在第二玩家的第二状态下的M2个可能动作，其中，第二玩家的第一状态比第二玩家的第二状态更接近IIG的开始状态；第四采样模块，用于以第四采样概率从第一玩家在第二状态下的M2个可能动作中采样出可能动作，其中，第三采样概率小于第四采样概率。

在可选实施例中，装置1100还包括：第五识别模块，用于识别第二玩家在第二玩家的第一状态下的M1个可能动作，其中，第一玩家的第一状态比第二玩家的第一状态更接近IIG的开始状态；第五采样模块，用于以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作，其中，第三采样概率大于第一采样概率。

在先前实施例中示出的系统、装置、模块或单元可以通过使用计算机芯片或实体来实现，或者可以通过使用具有特定功能的产品来实现。典型的实施设备是计算机，计算机可以是个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件收发设备、游戏控制台、平板计算机、可穿戴设备或这些设备的任意组合。

对于装置中每个模块的功能和角色的实施过程，可以参考前一方法中相应步骤的实施过程。为简单起见，这里省略了细节。

由于装置实施基本上对应于方法实施，对于相关部分，可以参考方法实施中的相关描述。先前描述的装置实施仅是示例。被描述为单独部分的模块可以是或不是物理上分离的，并且显示为模块的部分可以是或不是物理模块，可以位于一个位置，或者可以分布在多个网络模块上。可以基于实际需求来选择一些或所有模块，以实现本文方案的目标。本领域普通技术人员无需付出创造性劳动就能理解和实现本申请的实施方式。

再次参考图11，可以将其解释为示出了内部功能模块和数据处理装置的结构，该数据处理装置用于执行反事实遗憾最小化(CRF)以在两方或更多方之间的策略互动中进行策略搜索。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。执行主体本质上可以是电子设备，并且所述电子设备包括：一个或多个处理器；被配置为存储一个或多个处理器的可执行指令的存储器。

所述一个或多个处理器被配置为识别第一玩家在第一玩家的第一状态下的N1个可能动作；以第一采样概率从第一玩家在第一状态下的N1个可能动作中采样出可能动作；识别第一玩家在第一玩家的第二状态下的N2个可能动作，其中，第一玩家的第一状态比第一玩家的第二状态更接近IIG的开始状态；以第二采样概率从第一玩家在第二状态下的N2个可能动作中采样出可能动作，其中，第一采样概率小于第二采样概率；并基于第一玩家在第一状态下的N1个可能动作中的可能动作和第一玩家在第二状态下的N2个可能动作中的可能动作执行CRF。

可选地，所述一个或多个处理器被配置用于计算所述第一玩家在第一状态下的N1个可能动作中的可能动作的遗憾值；计算第一玩家在第二状态下的N2个可能动作中的可能动作的遗憾值；基于N1个可能动作中的可能动作的遗憾值更新第一玩家在第一状态下的第一策略；并基于N2个可能动作中的可能动作的遗憾值更新第一玩家在第二状态下的第二策略。

可选地，所述一个或多个处理器被配置用于从第一玩家在第一状态下的N1个可能动作中采样出k1个可能动作，其中，k1个可能动作中的每个可能动作以相同的第一采样概率被采样；从第一玩家在第二状态下的N2个可能动作中采样出k2个可能动作，其中，k2个可能动作中的每个可能动作以相同的第二采样概率被采样。

可选地，一个或多个处理器被配置为基于第一玩家在第一状态下的N1个可能动作中的k1个可能动作和第一玩家在第二状态下的N2个可能动作中的k2个动作执行CRF。

可选地，第一采样概率是k1/N1，第二采样概率是k2/N2。

可选地，2<＝k1<＝N1和2<＝k2<＝N2。

可选地，k1＝k2。

可选地，一个或多个处理器被配置为识别第二玩家在第二玩家的第一状态下的M1个可能动作；以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作；识别第二玩家在第二玩家的第二状态下的M2个可能动作，其中，第二玩家的第一状态比第二玩家的第二状态更接近IIG的开始状态；并以第四采样概率从第一玩家在第二状态下的M2个可能动作中采样出可能动作，其中，第三采样概率小于第四采样概率。

可选地，一个或多个处理器被配置为识别第二玩家在第二玩家的第一状态下的M1个可能动作，其中，第一玩家的第一状态比第二个玩家的第一状态更接近IIG的开始状态；并以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作，其中，第三采样概率大于第一采样概率。

图12是根据本文的实施例的另一装置1200的模块的示例的图。装置1200可以是数据处理装置的示例性实施例，该数据处理装置用于执行反事实遗憾最小化(CRF)以在两个或更多个玩家之间的策略互动中进行策略搜索。装置1200可以对应于上述实施例，并且装置1200包括以下：第一存储模块1201，用于将多个遗憾样本存储在第一数据存储设备中，其中，多个遗憾样本各自包括玩家状态和玩家状态下的可能动作的遗憾值，其中，多个遗憾样本是在玩家与至少另一玩家之间的策略互动中进行策略搜索时，通过反事实遗憾最小化(CRF)算法的两次或更多次迭代获得的；第二存储模块1202，用于将多个策略样本存储在第二数据存储设备中，其中，多个策略样本各自包括玩家状态和玩家状态下的可能动作的策略值；第一更新模块1203，用于基于第一数据存储设备中的多个遗憾样本，更新用于预测玩家状态下的可能动作的遗憾值的第一神经网络的参数；第二更新模块1204，用于基于第二数据存储设备中的多个策略样本更新用于预测玩家状态下的可能动作的策略值的第二神经网络的参数。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。作为示例，IIG表示至少涉及玩家和第二玩家的合作产品服务推荐服务，所述玩家对第二玩家的信息具有有限的访问权，其中，玩家状态包括第二玩家所提供信息的历史，其中，玩家的可能动作包括响应于第二玩家所提供信息的历史的可能动作以向顾客提供产品服务推荐。

前述和其他描述的实施例可以各自可选地包括以下特征中的一个或多个：

在可选的实施例中，装置1200还包括：识别模块，用于识别玩家的第一状态和玩家在第一状态下的第一可能动作；第一预测模块，用于使用第一神经网络的参数预测玩家在第一状态下的第一可能动作的第一遗憾值；第二预测模块，用于使用第二神经网络的参数预测玩家在第一状态下的第一可能动作的第一策略值。

在可选的实施例中，其中，所述第一存储模块能够获取新遗憾样本；并且根据贮存器采样算法将所述新遗憾样本存储到第一数据存储设备中。

在可选的实施例中，其中，根据贮存器采样算法将新遗憾样本存储到第一数据存储设备中，包括：确定第一数据存储设备是否已满；并响应于确定第一数据存储设备已满，用新遗憾样本替换第一数据存储设备中的多个遗憾样本中的一个。

在可选的实施例中，其中，CRF算法包括鲁棒采样CRF算法。

在可选的实施例中，其中，玩家状态下的可能动作的策略值包括平均策略分子。

在可选的实施例中，其中，玩家状态下的可能动作的遗憾值包括基于玩家状态下的可能动作的反事实值计算出的玩家状态下的可能动作的反事实遗憾值。

在可选的实施例中，装置1200还包括：在玩家与至少另一玩家之间的策略互动中进行策略搜索时，在反事实遗憾最小化(CRF)算法的两次或更多次迭代的每次迭代中，采样模块，用于根据采样方案从玩家在第二状态下的多个可能动作中采样出可能动作；第一计算模块，用于计算玩家在第二状态下的可能动作的反事实值；第二计算模块，用于基于玩家在第二状态下的可能动作的反事实值计算玩家在第二状态下的可能动作的遗憾值；第三计算模块，用于根据遗憾匹配算法基于玩家在第二状态下的可能动作的遗憾值计算玩家在第二状态下的可能动作的更新策略；第四计算模块，用于基于玩家在第二状态下的可能动作的更新策略计算玩家在第二状态下的可能动作的策略值。

在可选的实施例中，装置1200还包括：第一初始化模块，用于基于先前迭代中的第一神经网络的参数对第一神经网络的参数进行初始化；第二初始化模块，用于基于先前迭代中的第二神经网络的参数对第二神经网络的参数进行初始化。

在先前实施例中示出的系统、装置、模块可以通过使用计算机芯片或实体来实现，或者可以通过使用具有特定功能的产品来实现。典型的实施设备是计算机，计算机可以是个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件收发设备、游戏控制台、平板计算机、可穿戴设备或这些设备的任意组合。

对于装置中每个模块的功能和角色的实施过程，可以参考前一方法中相应步骤的实施过程。为简单起见，这里省略了细节。

由于装置实施基本上对应于方法实施，对于相关部分，可以参考方法实施中的相关描述。先前描述的装置实施仅是示例。被描述为单独部分的模块可以是或不是物理上分离的，并且显示为模块的部分可以是或不是物理模块，可以位于一个位置，或者可以分布在多个网络模块上。可以基于实际需求来选择一些或所有模块，以实现本文方案的目标。本领域普通技术人员无需付出创造性劳动就能理解和实现本申请的实施方式。

再次参考图12，可以将其解释为示出了内部功能模块和数据处理装置的结构，该数据处理装置用于执行反事实遗憾最小化(CRF)以在两方或更多方之间的策略互动中进行策略搜索。本质上，执行主体可以是电子设备，电子设备包括：一个或多个处理器；被配置为存储一个或多个处理器的可执行指令的存储器。

所述一个或多个处理器被配置为将多个遗憾样本存储在第一数据存储设备中，其中，多个遗憾样本各自包括玩家状态和玩家状态下的可能动作的遗憾值，其中，多个遗憾样本是在玩家与至少一个其他玩家之间的策略互动中进行策略搜索时，通过反事实遗憾最小化(CRF)算法的两次或更多次迭代获得的；将多个策略样本存储在第二数据存储设备中，其中，所述多个策略样本各自包括玩家状态和玩家状态下的可能动作的策略值；基于第一数据存储设备中的多个遗憾样本更新用于预测玩家状态下的可能动作的遗憾值的第一神经网络的参数；基于第二数据存储设备中的多个策略样本更新用于预测玩家状态下的可能动作的策略值的第二神经网络的参数。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。作为示例，IIG表示至少涉及玩家和第二玩家的合作产品服务推荐服务，所述玩家对第二玩家的信息具有有限的访问权，其中，玩家状态包括第二玩家所提供信息的历史，其中，玩家的可能动作包括响应于第二玩家所提供信息的历史的可能动作以向顾客提供产品服务推荐。

可选地，所述一个或多个处理器被配置为识别玩家的第一状态以及玩家在第一状态下的第一可能动作；使用第一神经网络的参数预测玩家在第一状态下的第一可能动作的第一遗憾值；并使用第二神经网络的参数预测玩家在第一状态下的第一可能动作的第一策略值。

可选地，所述一个或多个处理器被配置为：获得新遗憾样本；以及根据贮存器采样算法将新遗憾样本存储到第一数据存储设备中。

可选地，一个或多个处理器被配置为：确定第一数据存储器是否已满；并响应于确定第一数据存储设备已满，用新遗憾样本替换第一数据存储设备中的多个遗憾样本中的一个。

可选地，CRF算法包括鲁棒采样CRF算法。

可选地，玩家状态下的可能动作的策略值包括平均策略分子。

可选地，玩家状态下的可能动作的遗憾值包括基于玩家状态下的可能动作的反事实值计算出的玩家状态下的可能动作的反事实遗憾值。

可选地，所述一个或多个处理器被配置为：在玩家与至少另一玩家之间的策略互动中进行策略搜索时，在反事实遗憾最小化(CRF)算法的两次或更多次迭代的每次迭代中，根据采样方案从玩家在第二状态下的多个可能动作中采样出可能动作；计算玩家在第二状态下的可能动作的反事实值；基于玩家在第二状态下的可能动作的反事实值计算玩家在第二状态下的可能动作的遗憾值；根据遗憾匹配算法基于玩家在第二状态下的可能动作的遗憾值计算玩家在第二状态下的可能动作的更新策略；并基于玩家在第二状态下的可能动作的更新策略计算玩家在第二状态下的可能动作的策略值。

可选地，所述一个或多个处理器被配置为基于先前迭代中的第一神经网络的参数对第一神经网络的参数进行初始化；并基于先前迭代中的第二神经网络的参数对第二神经网络的参数进行初始化。

所描述的主题的实施例可以包括单独或组合的一个或多个特征。例如，在第一实施例中，一种计算机实现的用于执行反事实遗憾最小化(CRF)以在两方或更多方之间的策略互动中进行策略搜索的方法。所述方法包括识别第一玩家在第一玩家的第一状态下的N1个可能动作；以第一采样概率从第一玩家在第一状态下的N1个可能动作中采样出可能动作；识别第一玩家在第一玩家的第二状态下的N2个可能动作，其中，第一玩家的第一状态比第一玩家的第二状态更接近IIG的开始状态；以第二采样概率从第一玩家在第二状态下的N2个可能动作中采样出可能动作，其中，第一采样概率小于第二采样概率；并基于第一玩家在第一状态下的N1个可能动作中的可能动作和第一玩家在第二状态下的N2个可能动作中的可能动作执行CRF。在一些实施例中，两个或更多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。作为示例，IIG表示指示涉及第一玩家和第二玩家的合作产品服务推荐服务，所述第一玩家对第二玩家的信息具有有限的访问权，其中，第一玩家状态包括由第二玩家提供的信息的历史，其中，第一玩家的N1个可能动作包括响应于由第二玩家提供的信息的历史的N1个可能动作以向顾客提供产品服务推荐。

前述和其他描述的实施例可以各自可选地包括以下特征中的一个或多个：

第一特性，可与以下任何特性组合，其中，基于第一玩家在第一状态下的N1可能动作中的可能动作和第一玩家在第二状态下的N2个可能动作中的可能动作执行CRF包括：计算所述第一玩家在第一状态下的N1个可能动作中的可能动作的遗憾值；计算第一玩家在第二状态下的N2个可能动作中的可能动作的遗憾值；基于N1个可能动作中的可能动作的遗憾值，更新第一玩家在第一状态下的第一策略；并基于N2个可能动作中的可能动作的遗憾值更新第一玩家在第二状态下的第二策略。

第二特征，可与以下任何特征组合，进一步包括：从第一玩家在第一状态下的N1个可能动作中采样出k1个可能动作，其中，k1个可能动作中的每个可能动作以相同的第一采样概率被采样；从第一玩家在第二状态下的N2个可能动作中采样出k2个可能动作，其中，k2个可能动作中的每个可能动作以相同的第二采样概率被采样。

第三特征，可与以下任何特征组合，进一步包括：基于第一玩家在第一状态下的N1个可能动作中的k1个可能动作和在第一玩家在第二状态下的N2个可能动作中的k2个可能动作执行CRF。

第四特征，可与以下任何特征组合，其中，第一采样概率是k1/N1，第二采样概率是k2/N2。

第五特征，可与以下任何特征组合，其中，2<＝k1<＝N1并且2<＝k2<＝N2。

第六特征，可与以下任何特征组合，其中，k1＝k2。

第七特征，可与以下任何特征组合，进一步包括：识别第二玩家在第二玩家的第一状态下的M1个可能动作；以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作；识别第二玩家在第二玩家的第二状态下的M2个可能动作，其中，第二玩家的第一状态比第二玩家的第二状态更接近IIG的开始状态；并以第四采样概率从第一玩家在第二状态下的M2个可能动作中采样出可能动作，其中，第三采样概率小于第四采样概率。

第八特征，可与以下任何特征组合，进一步包括：识别第二玩家在第二玩家的第一状态下的M1个可能动作，其中，第一玩家的第一状态比第二个玩家的第一状态更接近IIG的开始状态；并以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作，其中，第三采样概率大于第一采样概率。

在第二实施例中，一种系统，包括：一个或多个处理器；一个或多个计算机可读存储器，其耦接到所述一个或多个处理器并其上存储有指令，所述指令可由所述一个或多个处理器执行以执行第一实施例中的任一方法及其如上所述一个或多个特征的可选组合。

在第三实施例中，一种用于执行反事实遗憾最小化CFR以在两方或更多方之间的策略互动中进行策略搜索的装置。所述装置包括：第一识别模块，用于识别第一玩家在第一玩家的第一状态下的N1个可能动作；第一采样模块，用于以第一采样概率从第一玩家在第一状态下的N1个可能动作中采样出可能动作；第二识别模块，用于识别第一玩家在第一玩家的第二状态下的N2个可能动作，其中，第一玩家的第一状态比第一玩家的第二状态更接近IIG的开始状态；第二采样模块，以第二采样概率从所述第一玩家在第二状态下的N2个可能动作中采样出可能动作，其中，所述第一采样概率小于所述第二采样概率；处理模块，用于基于第一玩家在第一状态下的N1个可能动作中的可能动作和第一玩家在第二状态下的N2个可能动作中的可能动作执行CRF。在一些实施例中，两个或多个玩家之间的策略互动可以通过涉及两个或更多个玩家的不完美信息博弈(IIG)来建模。作为示例，IIG表示至少涉及第一玩家和第二玩家的合作产品服务推荐服务，所述第一玩家对第二玩家的信息具有有限的访问权，其中，第一玩家的第一状态包括由第二玩家提供的信息的历史，其中第一玩家的N1个可能动作包括响应于由第二玩家提供的信息的历史的N1个可能动作以向顾客提供产品服务推荐。

前述和其他描述的实施例可以各自可选地包括以下特征中的一个或多个：

第一特性，可与以下任何特性组合，其中，所述处理模块包括：第一计算模块，用于计算第一玩家在第一状态下的N1个可能动作中的可能动作的遗憾值；第二计算模块，用于计算所述第一玩家在第二状态下的所述N2个可能动作中的可能动作的遗憾值；第一更新模块，用于基于所述N1个可能动作中的可能动作的遗憾值更新所述第一玩家在所述第一状态下的第一策略；第二更新模块，用于基于所述N2个可能动作中的可能动作的遗憾值更新第一玩家在第二状态下的第二策略。

第二特征，可与以下任何特征组合，其中，第一采样模块从第一玩家在第一状态下的N1个可能动作中采样出k1个可能动作，其中，k1个可能动作中的每个可能动作以相同的第一采样概率被采样；以及第二采样模块从第一玩家在第二状态下的N2个可能动作中采样出k2个可能动作，其中，k2个可能动作中的每个可能动作以相同的第二采样概率被采样。

第三特征，可与以下任何特征组合，其中，所述处理模块基于第一玩家在第一状态下的N1个可能动作中的k1个可能动作和第一玩家在第二状态下的N2个可能动作中的k2个可能动作执行CRF。

第四特征，可与以下任何特征组合，其中，第一采样概率是k1/N1，第二采样概率是k2/N2。

第五特征，可与以下任何特征组合，其中，2<＝k1<＝N1并且2<＝k2<＝N2。

第六特征，可与以下任何特征组合，其中，k1＝k2。

第七特性，可与以下任何特性组合，进一步包括：第三识别模块，用于识别第二玩家在第二玩家的第一状态下的M1个可能动作；第三采样模块，用于以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作；第四识别模块，用于识别第二玩家在第二玩家的第二状态下的M2个可能动作，其中，第二玩家的第一状态比第二玩家的第二状态更接近IIG的开始状态；第四采样模块，用于以第四采样概率从第一玩家在第二状态下的M2个可能动作中采样出可能动作，其中，第三采样概率小于第四采样概率。

第八特征，可与以下任何特征组合，进一步包括：第五识别模块，用于识别第二玩家在第二玩家的第一状态下的M1个可能动作，其中，第一玩家的第一状态比第二个玩家的第一状态更接近IIG的开始状态；和第五采样模块，用于以第三采样概率从第二玩家在第一状态下的M1个可能动作中采样出可能动作，其中，第三采样概率大于第一采样概率。

本文中描述的主题、动作和操作的实施例可以在数字电子电路、有形体现的计算机软件或固件、计算机硬件中实现，包括本文中公开的结构及其结构等同物，或者它们中的一个或多个的组合。本文中描述的主题的实施可以实现为一个或多个计算机程序，例如，编码在计算机程序载体上的一个或多个计算机程序指令模块，用于由数据处理执行或控制数据处理装置的操作。例如，计算机程序载体可以包括一个或多个计算机可读存储介质，其具有编码或存储在其上的指令。载体可以是有形的非暂态计算机可读介质，例如磁盘、磁光盘或光盘、固态驱动器、随机存取存储器(RAM)、只读存储器(ROM)或其他介质类型。替代地或另外地，载体可以是人工生成的传播信号，例如，机器生成的电、光或电磁信号，其被生成以编码信息以便传输到合适的接收器装置以供数据处理装置执行。计算机存储介质可以是或部分是机器可读存储设备、机器可读存储基板、随机或串行存取存储器设备或它们中的一个或多个的组合。计算机存储介质不是传播信号。

计算机程序，也可以被称为或描述为程序、软件、软件应用、app、模块、软件模块、引擎、脚本或代码，可以以任何形式的编程语言编写，包括编译或解释性语言、说明或程序性语言；它可以配置为任何形式，包括作为独立程序，或者作为模块、组件、引擎、子程序或适合在计算环境中执行的其他单元，该环境可包括由通信数据网络互联的在一个或多个位置上的一个或多个计算机。

计算机程序可以但非必须对应于文件系统中的文件。计算机程序可以存储在：文件保存其他程序或数据的文件的一部分中，例如，存储在标记语言文档中的一个或多个脚本；专用于所讨论的程序的单个文件；或者多个协调文件，例如，存储一个或多个模块、子程序或代码部分的多个文件。

举例来说，用于执行计算机程序的处理器包括通用和专用微处理器，以及任何类型的数字计算机的任何一个或多个处理器。通常，处理器将从耦接到处理器的非暂态计算机可读介质接收用于执行的计算机程序的指令以及数据。

术语“数据处理装置”包括用于处理数据的所有类型的装置、设备和机器，包括例如可编程处理器、计算机或者多处理器或计算机。数据处理装置可以包括专用逻辑电路，例如FPGA(现场可编程门阵列)、ASIC(专用集成电路)或GPU(图形处理单元)。除了硬件，该装置还可以包括为计算机程序创建执行环境的代码，例如，构成处理器固件、协议栈、数据库管理系统、操作系统或者它们中的一个或多个的组合的代码。

本文中描述的处理和逻辑流程可以由执行一个或多个计算机程序的一个或多个计算机或处理器执行，以通过对输入数据进行运算并生成输出来执行操作。处理和逻辑流程也可以由例如FPGA、ASIC或GPU的专用逻辑电路或专用逻辑电路与一个或多个编程计算机的组合来执行。

适合于执行计算机程序的计算机可以基于通用和/或专用微处理器，或任何其他种类的中央处理单元。通常，中央处理单元将从只读存储器和/或随机存取存储器接收指令和数据。计算机的元件可包括用于执行指令的中央处理单元以及用于存储指令和数据的一个或多个存储器设备。中央处理单元和存储器可以补充有专用逻辑电路或集成在专用逻辑电路中。

通常，计算机还将包括或可操作地耦接至一个或多个大容量存储设备，以从一个或多个存储设备接收数据或将数据传输到一个或多个大容量存储设备。存储设备可以是，例如，磁盘、磁光或光盘，固态驱动器或任何其他类型的非暂态计算机可读介质。但是，计算机不需要具有这样的设备。因此，计算机可以耦接到例如本地和/或远程的一个或多个存储器的一个或多个存储器设备。例如，计算机可以包括作为计算机的整体部件的一个或多个本地存储器，或者计算机可以耦接到云网络中的一个或多个远程存储器。此外，计算机可以嵌入到另一个设备中，例如移动电话、个人数字助理(PDA)、移动音频或视频播放器、游戏控制台、全球定位系统(GPS)接收器或例如通用串行总线(USB)闪存驱动器的便携式存储设备，仅举几例。

组件可以通过例如直接地或经由一个或多个中间组件彼此电连接或光连接而可交换地彼此“耦接”。如果其中一个组件集成到另一个组件中，则组件也可以彼此“耦接”。例如，集成到处理器中的存储组件(例如，L2高速缓存组件)被“耦接到”处理器。

为了提供与用户的交互，本文中描述的主题的实施例可以在计算机上实现或配置为与该计算机通信，该计算机具有：显示设备(例如，LCD(液晶显示器)监视器)，用于向用户显示信息；以及输入设备，用户可以通过该输入设备向该计算机提供输入，例如键盘和例如鼠标、轨迹球或触摸板等的指针设备。其他类型的设备也可用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感觉反馈，例如视觉反馈、听觉反馈或触觉反馈；并且可以接收来自用户的任何形式的输入，包括声音、语音或触觉输入。另外，计算机可以通过向用户使用的设备发送文档和从用户使用的设备接收文档来与用户交互；例如，通过响应于从用户设备上的web浏览器接收的请求将网页发送到用户设备上的web浏览器，或者通过与在例如智能电话或电子平板电脑等的用户设备上运行的应用(app)交互。此外，计算机可以通过向个人设备(例如，运行消息应用的智能手机)轮流发送文本消息或其他形式的消息来并接收来自用户的响应消息来与用户交互。

本文使用与系统、装置和计算机程序组件有关的术语“配置为”。对于被配置为执行特定操作或动作的一个或多个计算机的系统，意味着系统已经在其上安装了在运行中促使该系统执行所述操作或动作的软件、固件、硬件或它们的组合。对于被配置为执行特定操作或动作的一个或多个计算机程序，意味着一个或多个程序包括当被数据处理装置执行时促使该装置执行所述操作或动作的指令。对于被配置为执行特定操作或动作的专用逻辑电路，意味着该电路具有执行所述操作或动作的电子逻辑。

尽管本文包含许多具体实施细节，但这些不应被解释为由权利要求本身限定的对要求保护的范围的限制，而是作为对特定实施例的具体特征的描述。在本文单独实施例的上下文中描述的某些特征也可以在单个实施例中组合实现。相反，在单个实施例的上下文中描述的各种特征也可以单独地或以任何合适的子组合在多个实施例中实现。此外，尽管上面的特征可以描述为以某些组合起作用并且甚至最初如此要求保护，但是在一些情况下，可以从要求保护的组合中删除来自该组合的一个或多个特征，并且可以要求保护指向子组合或子组合的变体。

类似地，虽然以特定顺序在附图中描绘了操作并且在权利要求中叙述了操作，但是这不应该被理解为：为了达到期望的效果，要求以所示的特定顺序或依次执行这些操作，或者要求执行所有示出的操作。在某些情况下，多任务和并行处理可能是有利的。此外，上述实施例中的各种系统模块和组件的划分不应被理解为所有实施例中都要求如此划分，而应当理解，所描述的程序组件和系统通常可以一起集成在单个软件产品中或打包成多个软件产品。

已经描述了主题的特定实施例。其他实施例在以下权利要求的范围内。例如，权利要求中记载的动作可以以不同的顺序执行并且仍然实现期望的结果。作为一个示例，附图中描绘的处理无需要求所示的特定顺序或次序来实现期望的结果。在某些情况下，多任务和并行处理可能是有利的。