CN106296006A - 非完备信息博弈中风险与收益均衡的最少遗憾的评估方法 - Google Patents

Abstract

本发明提供了非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，包括如下步骤：步骤1：针对每个信息集，初始化其策略、估值和每个动作的遗憾值；步骤2：使用当前的策略进行博弈，直至完成本次博弈；步骤3：在本次博弈所访问到的每个信息集上计算估值及每个动作的遗憾值；步骤4：根据遗憾匹配算法计算出新的策略；步骤5：计算新策略的风险值并综合考虑收益与风险的关系，挑选下一轮博弈中要使用的策略；步骤6：返回步骤2，直至博弈过程终止。本发明设计了一种利用经济学中风险的概念，并研究风险模型的原理，结合最少遗憾算法，应用在非完备信息机器博弈中。在利用最少遗憾算法收益占优策略的同时，兼顾策略的风险，达到更为合理的纳什均衡。

Description

非完备信息博弈中风险与收益均衡的最少遗憾的评估方法

技术领域

本发明涉及人工智能领域，尤其涉及非完备信息博弈中风险与收益均衡的最少遗憾的评估方法。

背景技术

人工智能是计算机领域的一个重要分支，它的中心任务是研究如何使计算机去做原本只能靠人的智力才能完成的工作。机器博弈作为人工智能的一个重要研究领域，是检验人工智能发展水平的一个重要手段。在机器博弈的研究中，非完备信息机器博弈是该领域研究的难点和重点之一。非完备信息博弈中的博弈方由于无法获得所有的信息，因而无法准确预知对手会采取哪些对策。这和社会中商业竞争、军事战争等的情形十分类似，它的研究对于建立现实社会的决策支持系统有很强的参考价值。

发明内容

为了解决现有技术中问题，本发明提供了非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，包括如下步骤：

步骤1：针对每个信息集，初始化其策略、估值和每个动作的遗憾值；

步骤2：使用当前的策略进行博弈，直至完成本次博弈；

步骤3：在本次博弈所访问到的每个信息集上计算估值及每个动作的遗憾值；

步骤4：根据遗憾匹配算法计算出新的策略；

步骤5：计算新策略的风险值并综合考虑收益与风险的关系，挑选下一轮博弈中要使用的策略；

步骤6：返回步骤2，直至博弈过程终止。

本发明的有益效果是：

本发明设计了一种利用经济学中风险的概念，并研究风险模型的原理，结合最少遗憾算法，应用在非完备信息机器博弈中。在利用最少遗憾算法收益占优策略的同时，兼顾策略的风险，达到更为合理的纳什均衡。

附图说明

图1是本发明流程图；

图2是非完备信息博弈过程；

图3是风险模型中I、II型风险损失示意图。

具体实施方式

下面结合附图对本发明做进一步说明。

首先介绍非完备信息博弈的模型及风险模型的基本概念。

非完备信息扩展式博弈是一个六元组＜H,H,P,f_c,{L_i}_{i＝1,2,...,N},{u_i}_{i＝1,2,...,N}＞其中N是代表玩家的有限集；H是有限动作序列的集合，空序列及每个动作序列的前缀也是H中的元素。终止序列Z是H中不是任何序列前缀的序列。对于非终止序列h∈H,A(h)＝{a:ha∈H}表示在动作序列h之后可以执行的动作的集合。函数P为非终止序列分配一个玩家，其中c代表随机事件。P(h)代表在序列h后轮到哪个玩家做动作。若P(h)＝c，则随机事件在决定序列h之后的动作。对于玩家i∈N,表示其信息分割；信息分割的元素称为信息集，每个信息集是H的子集，代表若干无法明确区分的动作序列。函数f_c为P(I)＝c的信息集提供A(h)中每一个动作a发生的概率，表示为f_c(a|I)；对于玩家i∈N,u_i:Z→R是其效用函数，在每个终止序列上获得返回值。

玩家i的策略σ_i是对每一个信息集I_i∈L_i,σ_i(I_i):A(I_i)→[0,1]是在动作集A(I_i)的概率分布函数。玩家i的策略空间用∑_i表示。一个策略组包含所有玩家的策略，用σ＝(σ₁,σ₂,...,σ_N)表示。用σ_-i表示除去玩家i，剩余的所有玩家策略组成的策略组。

给定策略组σ(当所有玩家根据策略σ选择动作)，定义动作序列h发生的概率为π^σ(h)。显然π^σ(h)可以分解为每一个玩家对动作序列h的发生所贡献的乘积，即同理，可定义对于两个不同的动作序列h和h',令π^σ(h,h')为在策略组σ下，从h到h'的转移概率，若h是h'的前缀，则π^σ(h,h')＝π^σ(h)/π^σ(h')否则，π^σ(h,h')＝0。类似的，可以定义和

图2中的集合W代表了非完备信息博弈环境I的所有可能的情况的集合，W中的每个元素w_i都代表了I的一个可能的完备信息状态，I的真实状态是W中的某一个w_i。这里引入世界的概念：一个世界是非完备信息博弈的一个可能状态。W是当前博弈状态的世界集，S是W的抽样集，完备信息蒙特卡洛抽样方法的基本过程是，采用随机方法抽样出W的子集S，对其中的每个完备信息世界s_i进行计算，统计分析每个s_i的最优解m_i,最后在M中选择最终的最优策略序列。

将机器博弈问题策略选择算法中的不确定性归结为以下两类风险损失。

I型风险损失及其计算方法：

由估值函数的对世界估值的不准确性造成的风险损失称为I型风险损失。假设世界w的最优策略序列为m，则此时m的I型风险损失计算方法如下：

在上式中，代表了估值函数对世界w下采取策略序列m的收益估值，代表真实世界采取策略序列m时的收益估值。

II型风险损失及计算方法：

由于对手最优策略判断的不准确性造成的风险损失称为II型风险损失，策略序列m的II型风险损失计算方法如下：

是估值函数对真实世界I采取策略序列m的收益估值。真实世界I下博弈双方的实际策略序列m’的收益估值。

图3展示了I、II型风险损失的区别，估值函数对世界w和真实世界I经过策略序列m的预期收益的估值差为I型风险损失，图中为L_wI，真实世界I中，策略序列m和实际策略序列m’的预期收益差为II型风险损失，图中为L_mII。由此，定义世界w下采用策略序列m的风险损失为

L_wm＝L_wI+L_mII (3)。

本发明设计了一种利用经济学中风险的概念，并研究风险模型的原理，结合最少遗憾算法，应用在非完备信息机器博弈中。在利用最少遗憾算法收益占优策略的同时，兼顾策略的风险，达到更为合理的纳什均衡。

下面结合图1就发明的各个步骤做详细阐述。基本步骤为：

步骤1：进行初始化。对于玩家i∈N，对其每个信息集I∈L_i上策略的估值v(I,σ)＝0对每一个a∈A(I)，r(I,a)＝0，其策略初始化为δ_i(I,a)＝1/|A(I)|

步骤2：博弈方按照自己的策略轮流进行动作，直到本次博弈结束，并记录各博弈方结果。

步骤3：在本次博弈所访问到的每个信息集上计算估值及每个动作的遗憾值；

信息集I处的价值：

在信息集I，不采取动作a的遗憾值：

步骤4：由上一步求出的在每个访问到的信息集上的估值根据后悔匹配算法，重新为每个信息集上的各个动作分配比重，得到新的策略。这样计算相比于直接采取后悔程度最大的动作，好处在于避免对手同样进行后悔值的计算，感知己方的策略。由此得到以收益优先的策略。

对于信息集I，通过遗憾匹配得到下一步的一个收益优先的策略：

步骤5：计算新策略的风险值并综合考虑收益与风险的关系，挑选下一轮博弈中要使用的策略。

下面考虑风险因素对博弈结果的影响：

针对非完备信息机器博弈的特点，提出一个近似化计算风险损失的方法，其基本思想是计算抽样集S中的预计收益的均值，来代替世界集W中I的真实收益。

假设博弈者对当前状态的世界集为W，元素数为n，W的抽样集为S，元素数为t，M为W的所有合法策略序列集合，元素数为k。首先给出此时的平均收益计算方法：

定义：为抽样集S的平均收益。计算方法如下：

基于(7)式，对于策略序列δ的综合风险损失近似化计算方法公式如下：

(8)式中,约等号所连接处即为使用以及抽样集S进行近似计算的过程。

基于以上方法，能够计算出新策略的风险值。

接下来是如何综合考虑收益和风险之间的关系。

假设有策略A，B。E_A和E_B分别代表博弈者对于策略A、B的预期收益。L_A和L_B代表策略A和B的风险损失。则策略A、B的优劣判断规则如下：

1：若策略A、B满足u_A-L_A>u_B,则A优于B，反之，若满足u_B-L_B>u_A,则B优于A。

2：否则，由下式：

如果R>0，则A优于B，若R<0，则B优于A，若R＝0，则AB等优，系统可做随机选择。

由以上方法，可对当前博弈者的新旧策略进行排序，排序最优的策略作为当前的风险与收益均衡的策略，也即是博弈者的最优策略。

步骤6：判断整个博弈过程是否终止，若未终止，返回步骤2继续执行。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。

Claims (5)

1.非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，其特征在于：

包括如下步骤：

步骤1：针对每个信息集，初始化其策略、估值和每个动作的遗憾值；

步骤2：使用当前的策略进行博弈，直至完成本次博弈；

步骤3：在本次博弈所访问到的每个信息集上计算估值及每个动作的遗憾值；

步骤4：根据遗憾匹配算法计算出新的策略；

步骤5：计算新策略的风险值并综合考虑收益与风险的关系，挑选下一轮博弈中要使用的策略；

步骤6：返回步骤2，直至博弈过程终止。

2.根据权利要求1所述的非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，其特征在于：步骤1中，初始化过程如下：对于玩家i∈N，对其每个信息集I∈L_i上策略的估值v(I,σ)＝0，对每一个a∈A(I)，动作a在信息集I上的遗憾值r(I,a)＝0，其策略初始化为δ_i(I,a)＝1/|A(I)|，表示起始时每个动作的概率相等，相加为1，其中：N是代表玩家的有限集，L_i表示玩家i的信息分割，I为信息集，σ为策略组，a为动作。

3.根据权利要求2所述的非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，其特征在于：步骤3中，信息集I处的价值：

$v_i(\mathrm{\&sigma;},I)=\underset{z\&Element;Z_I}{\&Sigma;}{u}_i\left(z\right){\mathrm{\&pi;}}_{-i}^{\mathrm{\&sigma;}}(z\&lsqb;I\&rsqb;){\mathrm{\&pi;}}^{\mathrm{\&sigma;}}(z\&lsqb;I\&rsqb;,z)---\left(4\right)$

在信息集I，不采取动作a的遗憾值：

$R_i^T(I,a)=\frac{1}{T}\underset{t=1}{\overset{T}{\&Sigma;}}\left(v_i\right(I,{\mathrm{\&sigma;}}_{(I\&RightArrow;a)}^t)-v_i(I,{\mathrm{\&sigma;}}^t\left)\right)---\left(5\right)$

其中，z表示终止序列集合中的一个、u(z)表示到达博弈终止状态后的实际效用值，z[I]表示终止序列z在信息集I上的显示部分，表示玩家i所有的对手到达z[I]的概率，π^σ(z[I],z)为所有玩家从历史序列z[I]到z的转移概率，表示一个与σ^t等价的策略组，除了在信息集I中，策略组总会选择动作a公式(5)计算在T轮迭代中玩家i采取动作a的平均遗憾值。

4.根据权利要求3所述的非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，其特征在于：步骤4中，由上一步求出的在每个访问到的信息集上的估值根据后悔匹配算法，重新为每个信息集上的各个动作分配比重，得到新的策略，由此得到以收益优先的策略，对于信息集I，通过遗憾匹配得到下一步的一个收益优先的策略：

其中，公式含义为：当累加的遗憾值为正时，比上总遗憾值进行归一化，成比例的更新策略，否则下一轮的迭代策略即为初始的均一化策略，其中R表示累加T轮的遗憾值，a代表动作，I代表信息集，即为下一轮(第T+1轮)在信息集I，玩家i采用动作a的概率。

5.根据权利要求4所述的非完备信息博弈中风险与收益均衡的最少遗憾的评估方法，其特征在于：步骤5中，针对非完备信息机器博弈的特点，提出一个近似化计算风险损失的方法，其基本思想是计算抽样集S中的预计收益的均值，来代替世界集W中I的真实收益；

假设博弈者对当前状态的世界集为W，元素数为n，W的抽样集为S，元素数为t，M为W的所有合法策略序列集合，元素数为k，首先给出此时的平均收益计算方法：

定义：为抽样集S的平均收益，计算方法如下：

$\stackrel{\&OverBar;}{E_s}=\frac{1}{tk}\underset{i=1}{\overset{t}{\&Sigma;}}\underset{j=1}{\overset{k}{\&Sigma;}}{E}_i^j,(i\&Element;S,j\&Element;M)---\left(7\right)$

基于(7)式，对于策略序列δ的综合风险损失近似化计算方法公式如下：

$\begin{array}{c}{L}_{W\mathrm{\&sigma;}}=\frac{1}{n}\sqrt{\underset{i=1}{\overset{n}{\&Sigma;}}{L_{w_i\mathrm{\&sigma;}}}^2}=\frac{1}{n}\sqrt{\underset{i=1}{\overset{n}{\&Sigma;}}{(L_{w_{i}I}+L_{\mathrm{\&sigma;}II})}^2}\\ =\frac{1}{n}\sqrt{\underset{i=1}{\overset{n}{\&Sigma;}}{(E_{w_i}^{\mathrm{\&sigma;}}-E_I^{\mathrm{\&sigma;}}+E_I^{\mathrm{\&sigma;}}-E_I^{\mathrm{\&sigma;}\&prime;})}^2}\\ =\frac{1}{n}\sqrt{\underset{i=1}{\overset{n}{\&Sigma;}}{(E_{w_i}^{\mathrm{\&sigma;}}-E_I^{\mathrm{\&sigma;}\&prime;})}^2}\\ \&ap;\frac{1}{t}\sqrt{\underset{i=1}{\overset{t}{\&Sigma;}}{(E_{w_i}^{\mathrm{\&sigma;}}-\stackrel{\&OverBar;}{E_s})}^2},(w_i\&Element;S)\end{array}---\left(8\right)$

(8)式中,约等号所连接处即为使用以及抽样集S进行近似计算的过程，基于以上方法，计算出新策略的风险值；

接下来是如何综合考虑收益和风险之间的关系，

假设有策略A，B，E_A和E_B分别代表博弈者对于策略A、B的预期收益，L_A和L_B代表策略A和B的风险损失，则策略A、B的优劣判断规则如下：

1：若策略A、B满足u_A-L_A>u_B,则A优于B，反之，若满足u_B-L_B>u_A,则B优于A；

2：否则，由下式：

$R=log\&lsqb;\frac{E_A-(E_B-L_B)}{E_B-(E_A-L_A)}\&rsqb;---\left(9\right)$

如果R>0，则A优于B，若R<0，则B优于A，若R＝0，则AB等优，系统可做随机选择；

由以上方法，对当前博弈者的新旧策略进行排序，排序最优的策略作为当前的风险占优策略，也即是博弈者的最优策略，其中，R代表风险，L_A和L_B代表策略A和B的风险损失，u_A和u_B代表策略A和B的实际效益值。