這算是一篇綜述性文章，講的不深，但是可以了解做planning都有哪些方法。這篇文章里全部使用了Q的說法，因為實現上可能是網絡DQN，也可以是經典的Table。

Models and Planning

Models指的是Environment Models，可以分為兩大類：

當前狀態和采取的動作作為輸入，輸出下一個所有可能狀態和獎勵的分布

當前狀態和采取的動作作為輸入，輸出下一個狀態和獎勵

Planning則是指對模型的合理使用，指定使用模型的"策略"(跟policy區分開，使用策略的意思)，用最低的成本收斂到價值函數。

Dyna-Q: Integrating Planning, Acting, and Learning

如果能有完美的環境模型，就可以使用類似動態規劃那樣的planning方法來更快更好地收斂Q，但是實際上由于各種各樣的原因，我們手上的模型可能沒有那么完美。

于是乎，是不是可以先學出個差不多的環境模型，然后使用這個環境模型來學習Q？這當然可以，而且學到的Q也能用于優化策略從而生成更好的樣本，然后更新環境模型和Q，這樣持續的迭代下去。這樣我們就有了兩種更新Q的方式：

通過真實經驗學到的環境模型生成的模擬樣本更新

直接通過真實經驗更新

這個過程可以描述為：

Tabular Dyna-Q

$1:InitializeQ(s,a)$ and $Model(s,a)$ for all $s\in S$ and $a\in A(s)$
$2:Doforever$:
$3:(a)S\leftarrow$ current (nonterminal) state
$4:(b)A\leftarrow ?$-greedy $(S,Q)$
$5:(c)Execute$ action $A$, observe resultant reward $R$ and next state $S^{\prime }$
$6:(d)Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma ma{x}_{a}Q(S^{\prime },a)?Q(S,A)]$
$7:(e)Model(S,A)\leftarrow R,S^{\prime }$(assuming deterministic environment)
$8:(f)Repeatn$ times:
$9:S\leftarrow$ random previously observed state
$10:A\leftarrow$random action previously taken in $S$
$11:R,S^{\prime }\leftarrow Model(S,A)$
$12:Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma ma{x}_{a}Q(S^{\prime },a)?Q(S,A)]$

算法里寫的$A$指代整個動作集合，實際運作時只會執行$a$，$S$和$S^{\prime }$同理。原算法這樣給的，我也不敢隨便改。

算法里plannaing步驟中，

算法可以使用下面這張圖描述：

Prioritized Sweeping

前面的Planning搜索是隨機的，見算法$Dyna?Q$第9行，第10行。下面要講的優先掃除算法加入了優先隊列，每次把變化最大的臨近4個(可以單步直接到達)加進去，與廣度優先搜索求最短路徑有相似地方。

我覺得其實是貪心算法+beam search，維持search窗口大小為4，窗口大小對結果肯定有影響，所以實際做的時候可以嘗試改變這個4.

Prioritized sweeping for a deterministic environment

$1:InitializeQ(s,a),Model(s,a)$, for all $s,a$ and $PQueue$ to empty
$2:Doforever:$:
$3:(a)S\leftarrow$ current (nonterminal) state
$4:(b)A\leftarrow policy$(S,Q)
$5:(c)Execute$ action $A$; observe resultant reward, $R$, and state, $S^{\prime }$
$6:(d)Model(S,A)\leftarrow R,S^{\prime }$
$7:(e)P\leftarrow |R+\gamma ma{x}_{a}Q(S^{\prime },a)?Q(S,A)|.$
$8:(f)ifP>\theta ,then$ insert $S,A$ into PQueue with priority $P$
$9:(g)Repeatn$ times, while PQueue is not empty:
$10:S,A\leftarrow$ from $PQueue$ with top priority
$11:R,S^{\prime }\leftarrow Model(S,A)$
$12:Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma ma{x}_{a}Q(S^{\prime },a)?Q(S,A)]$
$13:Repeat,forall\overline{S},\overline{A}$ predicted to lead S:
$14:\overline{R}\leftarrow$ predicted reward for $\overline{S}$,$\overline{A}$,$S$
$15:P\leftarrow |\overline{R}+\gamma ma{x}_{a}Q(S,a)?Q(\overline{S},\overline{A})|.$
$16:ifP>\theta then$ insert $\overline{S}$, $\overline{A}$ into $PQueue$ with priority $P$

Trajectory Sampling

動態規劃中不計算所有的節點，而是選擇重要的進行更新。

Heuristic Search

在選擇action時，通過一定深度的搜索得到最好的路徑。這種方法在Model準確但是Q不準確的條件下可用。

Rollout Algorithms

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)。通過在大量從任何一個可能的動作上開始然后遵循策略的模擬跡上取平均來評估一個給定策略的動作價值。當動作-價值估計被認為是足夠準確的時候，最高估計值的動作(或者動作集中的一個)被執行，然后在下一個狀態重復該過程。

Monte Carlo Tree Search

蒙特·卡羅爾樹搜索(MCTS)是一個最近的并且特別成功的決策時planning的例子。

蒙特·卡羅爾樹搜索和Rollout算法類似，但是不是隨機搜索而是有"指導"的搜索，目的是為了更大概率地獲得更好的路徑。

MCTS也是Alpha Go核心技術之一，同時不局限于棋類搜索，所有的可以進行不高效模擬的問題都可以使用這個方法。

MCTS并不是每次都從當前狀態開始搜索，而是會利用以前搜索到的以當前狀態為開始狀態的高分路徑作為候選。

MCTS可以分為如下圖所示的四個步驟：

有三個注意點：

• backup之后，rollout的路徑不更新價值函數，只更新selection和expansion的路徑
• 上面四個步驟將按序循環執行，直到時間耗盡或者找不到新的狀態
• 并不是每次搜索都從當前節點開始，而是會服用出現過的當前節點的樹結構

總結

以上是生活随笔為你收集整理的Planning and Learning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。