版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。undefined本文链接:https://cloud.tencent.com/developer/article/1537750
这算是一篇综述性文章,讲的不深,但是了解做planning都有哪些方法。这篇文章里全部使用了Q的说法,因为实现上可能是网络DQN,也可以是经典的Table。
Models指的是Environment Models,可以分为两大类:
Planning则是指对模型的合理使用,指定使用模型的"策略"(跟policy区分开,使用策略的意思),用最低的成本收敛到价值函数。
如果能有完美的环境模型,就可以使用类似动态规划那样的planning方法来更快更好地收敛Q,但是实际上由于各种各样的原因,我们手上的模型可能没有那么完美。
于是乎,是不是可以先学出个差不多的环境模型,然后使用这个环境模型来学习Q?这当然可以,而且学到的Q也能用于优化策略从而生成更好的样本,然后更新环境模型和Q,这样持续的迭代下去。这样我们就有了两种更新Q的方式:
这个过程可以描述为:
1: InitializeQ(s,a)1:\ Initialize Q(s,a)1: InitializeQ(s,a) and Model(s,a)Model(s,a)Model(s,a) for all s∈Ss \in Ss∈S and a∈A(s)a \in A(s)a∈A(s)
2: Do forever2:\ Do \ forever2: Do forever:
3: (a) S←3:\ \qquad (a) \ S \leftarrow3: (a) S← current (nonterminal) state
4: (b) A←ϵ4:\ \qquad (b) \ A \leftarrow \epsilon4: (b) A←ϵ-greedy (S,Q)(S,Q)(S,Q)
5: (c) Execute5:\ \qquad (c) \ Execute5: (c) Execute action AAA, observe resultant reward RRR and next state S′S'S′
6: (d) Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)6:\ \qquad (d) \ Q(S,A) \leftarrow Q(S,A) + \alphaR+\gamma max_aQ(S',a)-Q(S,A)6: (d) Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)
7: (e)Model(S,A)←R,S′7:\ \qquad (e) Model(S,A) \leftarrow R,S'7: (e)Model(S,A)←R,S′(assuming deterministic environment)
8: (f)Repeat n8:\ \qquad (f) Repeat \ n8: (f)Repeat n times:
9: S←9:\ \qquad \qquad S \leftarrow9: S← random previously observed state
10:A←10: \qquad \qquad A \leftarrow10:A←random action previously taken in SSS
11:R,S′←Model(S,A)11: \qquad \qquad R,S' \leftarrow Model(S,A)11:R,S′←Model(S,A)
12:Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)12: \qquad \qquad Q(S,A) \leftarrow Q(S,A) + \alphaR+\gamma max_aQ(S',a)-Q(S,A)12:Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)
算法里写的AAA指代整个动作集合,实际运作时只会执行aaa,SSS和S′S'S′同理。原算法这样给的,我也不敢随便改。
算法里plannaing步骤中,
算法可以使用下面这张图描述:
前面的Planning搜索是随机的,见算法Dyna−QDyna-QDyna−Q第9行,第10行。下面要讲的优先扫除算法加入了优先队列,每次把变化最大的临近4个(可以单步直接到达)加进去,与广度优先搜索求最短路径有相似地方。
我觉得其实是贪心算法+beam search,维持search窗口大小为4,窗口大小对结果肯定有影响,所以实际做的时候可以尝试改变这个4.
1: InitializeQ(s,a), Model(s,a)1:\ Initialize Q(s,a), \ Model(s,a)1: InitializeQ(s,a), Model(s,a), for all s,as,as,a and PQueuePQueuePQueue to empty
2: Do forever:2:\ Do \ forever:2: Do forever::
3: (a)S←3:\ \qquad (a) S \leftarrow3: (a)S← current (nonterminal) state
4: (b)A←policy4:\ \qquad (b) A \leftarrow policy4: (b)A←policy(S,Q)
5: (c)Execute5:\ \qquad (c) Execute5: (c)Execute action AAA; observe resultant reward, RRR, and state, S′S'S′
6: (d)Model(S,A)←R,S′6:\ \qquad (d) Model(S,A) \leftarrow R,S'6: (d)Model(S,A)←R,S′
7: (e)P←∣R+γmaxaQ(S′,a)−Q(S,A)∣.7:\ \qquad (e) P \leftarrow |R + \gamma max_a Q(S',a) - Q(S,A)|.7: (e)P←∣R+γmaxaQ(S′,a)−Q(S,A)∣.
8: (f)if P>θ, then8:\ \qquad (f) if \ P > \theta, \ then8: (f)if P>θ, then insert S,AS,AS,A into PQueue with priority PPP
9: (g) Repeat n9:\ \qquad (g) \ Repeat \ n9: (g) Repeat n times, while PQueue is not empty:
10: S,A←10:\ \qquad \qquad S,A \leftarrow10: S,A← into PQueuePQueuePQueue with priority PPP
11:R,S′←Model(S,A)11: \qquad \qquad R,S' \leftarrow Model(S,A)11:R,S′←Model(S,A)
12:Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)12: \qquad \qquad Q(S,A) \leftarrow Q(S,A) + \alphaR+\gamma max_a Q(S',a)-Q(S,A)12:Q(S,A)←Q(S,A)+αR+γmaxaQ(S′,a)−Q(S,A)
13:Repeat, for all S‾,A‾13: \qquad \qquad Repeat, \ for \ all \ \overline{S},\overline{A}13:Repeat, for all S,A predicted to lead S:
14:R‾←14: \qquad \qquad \qquad \overline{R} \leftarrow14:R← predicted reward for S‾\overline{S}S,A‾\overline{A}A,SSS
15:P←∣R‾+γmaxaQ(S,a)−Q(S‾,A‾∣.15: \qquad \qquad \qquad P \leftarrow |\overline{R} + \gamma max_a Q(S,a) - Q(\overline{S}, \overline{A}|.15:P←∣R+γmaxaQ(S,a)−Q(S,A∣.
16:if P>θ then16: \qquad \qquad \qquad if \ P > \theta \ then16:if P>θ then insert S‾\overline{S}S, A‾\overline{A}A into PQueuePQueuePQueue with priority PPP
动态规划中不计算所有的节点,而是选择重要的进行更新。
在选择action时,通过一定深度的搜索得到最好的路径。这种方法在Model准确但是Q不准确的条件下可用。
As explained by Tesauro and Galperin (1997), who experimented with rollout algorithms for playing backgammon, the term rollout “comes from estimating the value of a backgammon position by playing out, i.e., rolling out,” the position many times to the game’s end with randomly generated sequences of dice rolls, where the moves of both players are made by some xed policy.
Rollout算法是决策时规划算法,它基于Monte Carlo Control(Model-Free Control里有一个小节的介绍),应用于从当前环境状态中采样迹(trajectories)。通过在大量从任何一个可能的动作上开始然后遵循策略的模拟迹上取平均来评估一个给定策略的动作价值。当动作-价值估计被认为是足够准确的时候,最高估计值的动作(或者动作集中的一个)被执行,然后在下一个状态重复该过程。
蒙特·卡罗尔树搜索(MCTS)是一个最近的并且特别成功的决策时planning的例子。
蒙特·卡罗尔树搜索和Rollout算法类似,但是不是随机搜索而是有"指导"的搜索,目的是为了更大概率地获得更好的路径。
MCTS也是Alpha Go核心技术之一,同时不局限于棋类搜索,所有的可以进行多不高效模拟的问题都可以使用这个方法。
MCTS并不是每次都从当前状态开始搜索,而是会利用以前搜索到的以当前状态为开始状态的高分路径作为候选。
MCTS可以分为如下图所示的四个步骤:
有三个注意点: