【文件属性】：
文件名称：ＵＣＴ和ＲＡＶＥ结合-云原生安全技术预研报告
文件大小：2.45MB
文件格式：PDF
更新时间：2021-06-08 12:48:43
不围棋 UCT
１．２ ＲＡＶＥ介绍
ＲＡＶＥ （ｒａｐｉｄ ａｃｔｉｏｎ ｖａｌｕｅ ｅｓｔｉｍａｔｉｏｎ）［１１］是基于值 （ｖａｌｕｅ－
ｂａｓｅｄ）函数的强化学习思想在ＵＣＴ方法中的应用。ＲＡＶＥ收
集并评价ＵＣＴ搜索中产生的状态动作对，并在下一次ＵＣＴ搜
索时加以引导，使ＵＣＴ能够更多的搜索更好的分支。
强化学习是一种无监督的机器学习方法，它被称之为
“和批评者一起学习”。批评者 （ｃｒｉｔｉｃ）并不反馈应该做什
么，而仅仅反馈之前所做的怎么样［１２］。最典型的强化学习
算法是 Ｑ 学习算法，可以看作是马尔可夫决策 过 程
（Ｍａｒｋｏｖ ｄｅｃｉｓｉｏｎ ｐｒｏｃｅｓｓｅｓ）的一种变化形式。
马尔可夫决策过程是强化学习的数学模型，它是由四
元组组成：＜Ｓ，Ａ，Ｒ，Ｔ＞，其中Ｓ是离散的状态集，Ａ
是离散的动作集，Ｒ：Ｓ×Ａ→Ｒ是奖励函数，Ｔ：Ｓ×Ａ→
ＰＤ （Ｓ）是状态转移函数，ＰＤ （Ｓ）是状态集Ｓ上的概率
分布函数。
典型的基于折扣报酬的强化学习问题通常可以描述为给
定＜Ｓ，Ａ，Ｒ，Ｔ＞，寻找策略π使得期望折扣报酬总和最大
π（ｓ）＝ａｒｇｍａｘ
π
Ｖπ（ｓ）
式中：Ｖπ （ｓ）———折算累积回报，上式可以改写为
π（ｓ）＝ａｒｇｍａｘ
π
［ｒ（ｓ，ａ）＋γＶπ（δ（ｓ，ａ））］
式中：ｒ （ｓ，ａ）———ｓ状态下执行ａ所得的报酬值，γ是折
扣因子。
定义Ｑ （ｓ，ａ）为从状态ｓ开始并使用ａ作为第一个动
作时的最大折算累积回报，换言之，Ｑ的值为从状态ｓ执
行动作ａ的立即回报加上以后遵循最优策略的值
Ｑ（ｓ，ａ）＝ｒ（ｓ，ａ）＋γＶπ（δ（ｓ，ａ））
则
π（ｓ）＝ａｒｇｍａｘ
π
Ｑ（ｓ，ａ）
动态规划理论保证至少存在一个策略π＊ 使得对任意
ｓ∈Ｓ有
π＊（ｓ）＝ａｒｇｍａｘ
π
Ｑ（ｓ，ａ）
值函数 Ｑ （ｓ，ａ）的估计有很多种算法，比如 ＴＤ
（λ）［１３］。如果环境模型是已知的或是可学习的，那么基于值
函数的强化学习算法可用于基于样本的搜索。可从模型中
抽样来获得模拟场景，通过模拟经验来更新值函数。
ＲＡＶＥ是基于值函数Ｑ （ｓ，ａ）的强化学习方法，通过
基于样本的搜索树来动态更新值函数。为了与 ＵＣＴ相结
合，ＲＡＶＥ的收益公式定义为
ＱＲＡＶＥ（ｓ，ａ）＝ＱＲＡＶＥ（ｓ，ａ）＋ｃ
ｌｏｇｍ（ｓ）
ｍ（ｓ，ａ槡 ）
式中：ｍ （ｓ，ａ）———ｓ状态下ａ 动作被选择的次数，ｍ
（ｓ）———ｓ状态被访问的次数。
１．３ ＵＣＴ和ＲＡＶＥ结合
ＵＣＴ需要对每个ｓ∈Ｓ状态下可供选择的动作进行抽
样，以便比较各分支的收益情况并做出路径选择。如果动
作空间巨大，可供选择的分支数就很多，要用足够多的模
拟次数来区分分支的好坏［１４－１５］，而巨大的模拟次数将影响
算法的性能。为减少模拟次数，ＵＣＴ中加入在线学习知识
ＲＡＶＥ，将ＲＡＶＥ值作为分支选择的另一参考，以提高分
支选择的准确性。引入线性因子β （ｓ，ａ）把ＱＵＣＴ和ＱＲＡＶＥ
线性组合到一起
β（ｓ，ａ）＝
ｋ
３ｎ（ｓ）＋槡 ｋ
·７３１１·