深度強(qiáng)化學(xué)習(xí)（理論篇）—— 從 Critic-only、Actor-only 到 Actor-Critic

來(lái)源于 Tangowl 的系列文章 https://blog.csdn.net/lipengcn/article/details/81253033

自己第一篇 paper 就是用 MDP 解決資源優(yōu)化問(wèn)題，想來(lái)那時(shí)寫(xiě)個(gè)東西真是艱難啊竿音。彼時(shí)倒沒(méi)想到這個(gè)數(shù)學(xué)工具，如今會(huì)這么火，還衍生了新的領(lǐng)域——強(qiáng)化學(xué)習(xí)谎砾。當(dāng)然現(xiàn)在研究的內(nèi)容已有了很大拓展。
這段時(shí)間會(huì)做個(gè)深度強(qiáng)化學(xué)習(xí)的專(zhuān)題捧颅，包括基礎(chǔ)理論景图、最新文獻(xiàn)和實(shí)踐三大部分。

1 概述

1.1 強(qiáng)化學(xué)習(xí) v.s. 監(jiān)督學(xué)習(xí)

強(qiáng)化學(xué)習(xí)碉哑，與監(jiān)督學(xué)習(xí)挚币、無(wú)監(jiān)督學(xué)習(xí)并列，作為機(jī)器學(xué)習(xí)的三大類(lèi)扣典。強(qiáng)化學(xué)習(xí)妆毕，研究的是 agent 從與 environment 交互過(guò)程進(jìn)行學(xué)習(xí)，學(xué)習(xí)如何作用于 environment贮尖，從而可以從 environment 得到最優(yōu)的激勵(lì)笛粘。這個(gè)過(guò)程可以描述如下：
[圖片上傳失敗...(image-ae3406-1535181350541)]
即，agent 從 environment 處觀察到 state，從而基于某種 policy 做出 action薪前，environment 繼而對(duì)這種 action 做出反饋 reward 并轉(zhuǎn)移到新的 state润努，agent 面對(duì)新的 state 和之前 policy 得到的 reward，再次給出 action序六，周而復(fù)始任连，目標(biāo)就是 reward 某種長(zhǎng)期指標(biāo)最大化。

可見(jiàn)例诀，強(qiáng)化學(xué)習(xí)的理論框架和監(jiān)督學(xué)習(xí)有一定相似性随抠，學(xué)習(xí)改進(jìn)的過(guò)程，都有一種評(píng)價(jià)指標(biāo)繁涂，監(jiān)督學(xué)習(xí)中是 label拱她，強(qiáng)化學(xué)習(xí)中是 reward，用來(lái)指引 model 的學(xué)習(xí)扔罪，也都有訓(xùn)練樣本秉沼。
但區(qū)別也是巨大的，基本可以概括為：

SL 中樣本 x 通常要求 IID矿酵，而 RL 中顯然序列交互過(guò)程產(chǎn)生的樣本 (s,a) 不滿足 IID
SL 中 label 是隨 x 一起準(zhǔn)備好的唬复，而 RL 中的“標(biāo)簽” reward 的產(chǎn)生是滯后于（s,a）的。這就使得 RL 的學(xué)習(xí)必然是一個(gè)序列多步?jīng)Q策問(wèn)題全肮，同時(shí) action 會(huì)影響下一步的 state 和 reward敞咧，從而表明目標(biāo)應(yīng)是長(zhǎng)期激勵(lì)，這都顯著區(qū)別于 SL辜腺。此外休建，這個(gè) reward 不像 label 一樣能直接指導(dǎo)選擇什么樣的 action。
SL 中樣本的產(chǎn)生和訓(xùn)練是個(gè)open-loop评疗，準(zhǔn)備好樣本测砂，完成訓(xùn)練。RL 中樣本的產(chǎn)生和訓(xùn)練是個(gè) closed-loop百匆，樣本產(chǎn)生砌些，用于訓(xùn)練，應(yīng)用模型加匈，得到新的樣本寄症，繼續(xù)訓(xùn)練。這就使得 RL 的訓(xùn)練對(duì)樣本準(zhǔn)備要求低了很多矩动。

1.2 強(qiáng)化學(xué)習(xí) v.s. 深度學(xué)習(xí)

前面提到 SL 的缺陷：

樣本服從 IID，而很多問(wèn)題要處理的序列交互過(guò)程并不滿足 IID 假設(shè)
強(qiáng)監(jiān)督需要的標(biāo)注樣本释漆，是昂貴而稀缺的

RL 恰恰能處理這些缺陷悲没，但也要考慮到 DL 強(qiáng)大的表征能力，因此，DRL 的提出即融合 RL 和 DL 的優(yōu)勢(shì)：

DL learns the representation
RL learns the model

1.3 強(qiáng)化學(xué)習(xí)

RL 本身也有一些監(jiān)督學(xué)習(xí)示姿、無(wú)監(jiān)督學(xué)習(xí)所沒(méi)有的特點(diǎn)：

exploration-exploitation dilemma甜橱，為獲得長(zhǎng)期激勵(lì)，要選用已知的好的 action栈戳，還要嘗試未知的也許更好的 action岂傲，這種博弈在其他 ML 方法中未涉及
直接嘗試解決目標(biāo)明確的 agent 與未知的 environment 交互的這個(gè)“大”問(wèn)題，而不是分解為多個(gè)子問(wèn)題

一個(gè) RL 系統(tǒng)可以由四個(gè)基本元素描述：a policy, a reward signal, a value function, and, optionally, a model of the environment.

RL 研究的是序列多步?jīng)Q策問(wèn)題子檀，通常形式建模為 MDP（當(dāng)然早期也有 multi-bandit）镊掖。但凡適合解決 MDP 的算法，都可以稱(chēng)為 RL 算法褂痰。了解 Finite MDP 的理論亩进，可以理解現(xiàn)代 RL 的90%。下面主要介紹 MDP 模型缩歪，及其幾類(lèi)求解方法归薛。

2 MDP

2.1 Formulation

markov 模型家族有不少熟知角色，可以概括如下：

Markov models	無(wú) action	有 action
state 可見(jiàn)	MC	MDP
state 不可見(jiàn)	HMM	POMDP

MDP 建立在 markov chain 之上匪蝙，自然 state transition 僅與上一個(gè) state（可包含 action）有關(guān)主籍。

MDP 模型形式化為五元組（T，S逛球，A千元，P，R）需忿，即 epoch诅炉，state，action屋厘，transition probability涕烧， reward。當(dāng)然汗洒，有些教材會(huì)把 T 省略议纯，但考慮到 MDP 建模的序列多步?jīng)Q策，而且 T 的不同選擇對(duì) S 的定義也有影響溢谤，所以習(xí)慣上瞻凤，這里加上 T。此外世杀，還有基于五元組阀参，衍生的幾個(gè)概念：

（1）Policy，π瞻坝，建模了 agent 的 behavior蛛壳，可分為兩類(lèi)

stochastic policy，π：p(a|s) = π(s,a)
deterministic policy，π：a = π(s)

（2) Return衙荐，g捞挥，一個(gè) reward 序列的函數(shù)，用來(lái)衡量從當(dāng)前到未來(lái)的長(zhǎng)期激勵(lì)忧吟。
通常有兩種形式： ${g_t} = \mathop {\lim }\limits_{K \to \infty } {1 \over K}\sum\limits_{k = 0}^{K - 1} {{r_{t + k + 1}}}$ 和 $g_t = \sum\limits_{k = 0}^\infty {{\lambda ^k}{r_{t+k+1}}}$ 砌函，其中 $0 \le \lambda \le 1$ 。第二種長(zhǎng)期折扣總回報(bào)用的更多溜族，一是有一定現(xiàn)實(shí)意義讹俊，二是便于很多數(shù)學(xué)證明。

MDP 的優(yōu)化目標(biāo)是得到一個(gè) π斩祭，使得這個(gè) MDP 過(guò)程的期望 return 最大劣像，即形式化為：
$\max J\left( \pi \right) = \max {\rm E}\left\{ {g|\pi } \right\}$ 利用長(zhǎng)期折扣總回報(bào)，可以進(jìn)一步將 MDP 的目標(biāo)寫(xiě)為：
$J\left( \pi \right) = E\left\{ {\sum\limits_{t = 0}^\infty {{\lambda ^t}{r_t}} \left| {{s_0},{a_0},\pi } \right.} \right\}$

這里有些概念需進(jìn)一步闡述：

state 信號(hào)通常由預(yù)處理系統(tǒng)給出摧玫，其構(gòu)建耳奕、學(xué)習(xí)不在 MDP 算法討論范圍內(nèi)。其次诬像，不能期望 state 告知 agent 關(guān)于 environment 的一切信息屋群，甚至可以做出 action-decision 的一切信息。
environment 的 Markov 性坏挠，即 state 的 Markov 性芍躏，表示聯(lián)合概率分布 $p\left( {{s_{t + 1}},{r_{t + 1}}|{s_t},{a_t}} \right) = p\left( {{s_{t + 1}},{r_{t + 1}}|{s_0},{a_0},{s_1},{a_1}, \cdots ,{s_t},{a_t}} \right)$
[2] 認(rèn)為 $r_{t+1}$ 和 $s_t$ 、 $a_t$ 有關(guān)降狠，亦可和 $s_{t+1}$ 有關(guān)对竣，但不可和 $a_{t+1}$ 有關(guān)，一些其他材料也持這種觀點(diǎn)榜配。但 [1] 建模 $r_{t+1}$ 僅與 $s_t$ 否纬、 $a_t$ 有關(guān)，通常交互序列為 ${s_0},{a_0},{r_1},{s_1},{a_1},{r_2}, \cdots ,{r_t},{s_t},{a_t}$ 蛋褥，這種描述方式更簡(jiǎn)單临燃。下面不刻意區(qū)分 $r\left( {s,a,s'} \right)$ 與 $r\left( {s,a} \right)$ 。
policy 是由每個(gè) epoch 上的 decision rule 組成烙心，每個(gè) decision rule 決定了該 epoch 時(shí) $s$ 到 $a$ 的映射膜廊。decision rule 的 stochastic 還是 deterministic 決定了 policy 的性質(zhì)。當(dāng)所有 epoch 上都選用同一個(gè) decision rule 時(shí)也稱(chēng) policy 為 stationary 的淫茵，即通常接觸的 MDP （infinite horizon MDP）的研究對(duì)象爪瓜。通常稱(chēng) stationary deterministic policy 為 pure policy，屬于最特殊的 policy 匙瘪。
定理表明钥勋，在追求期望 return 最大化情況下炬转，最優(yōu)的 policy 一定是 deterministic 的，因此不必考慮 stochastic policy算灸。
下面基本假設(shè) S 和 A 是有限的，即 finite MDP驻啤，以避免積分表示菲驴。

2.2 Value function

為了期望 return 最大化，這里構(gòu)造了值函數(shù)骑冗，用來(lái)評(píng)估（預(yù)測(cè)）在當(dāng)前 state（以及 action）情況下遵循該 π赊瞬，能獲得的期望 return 是多少。即值函數(shù)中 policy 確定贼涩， $J\left( \pi \right)$ 則以 policy π為變量巧涧。以折扣總回報(bào)形式的 return 為例，值函數(shù)形式化為：

state 值函數(shù) ： ${V^\pi }\left( s \right) = \mathop E\limits_{\pi} \left\{ {\sum\limits_{k = 0}^\infty {{\lambda ^k}{r_{t + k + 1}}} \left| {{s_t} = s} \right.} \right\}$
state-action 值函數(shù) ： ${Q^\pi }\left( {s,a} \right) = \mathop E\limits_{\pi} \left\{ {\sum\limits_{k = 0}^\infty {{\lambda ^k}{r_{t + k + 1}}} \left| {{s_t} = s,{a_t} = a } \right.} \right\}$

顯然兩者存在簡(jiǎn)單的轉(zhuǎn)化關(guān)系：
${Q^\pi }\left( {s,a} \right) = \sum\limits_{s'} {p\left( {s'|s,a} \right)\left( {r\left( {s,a,s'} \right) + {V^\pi }\left( {s'} \right)} \right)}$ ${V^\pi }\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right){Q^\pi }\left( {s,a} \right)}$

值函數(shù)可以利用 experiences 進(jìn)行估計(jì)遥倦，也可以利用參數(shù)化的方式來(lái)進(jìn)行參數(shù)估計(jì)谤绳。后面會(huì)具體介紹。
利用值函數(shù)內(nèi)含的迭代關(guān)系袒哥，可以構(gòu)造為下列形式缩筛，即 Bellman 方程組：
${V^\pi }\left( s \right) = \mathop E\limits_{\pi}\left\{ {r\left( {s,a,s'} \right) + \lambda {V^\pi }\left( {s'} \right)} \right\} = \sum\limits_a {\pi \left( {a|s} \right)} \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V^\pi }\left( {s'} \right)} \right\}}$ ${Q^\pi }\left( {s,a} \right) = \mathop E\limits_{\pi}\left\{ {r\left( {s,a,s'} \right) + \lambda {Q^\pi }\left( {s',a'} \right)} \right\} = \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V^\pi }\left( {s'} \right)} \right\}}$

2.3 Optimal policy

值函數(shù)定義了各種 policy 的偏序，即 $\pi \ge \pi '$ 當(dāng)且僅當(dāng)對(duì)于任意 state 有 ${V^\pi }\left( s \right) \ge {V^{\pi '}}\left( s \right)$ 堡称。因此瞎抛，最優(yōu) policy 即對(duì)應(yīng)讓該 policy 的值函數(shù)最大的 policy。

利用上面 Bellman 方程組却紧，很容易得到 optimal value func：
${V^*}\left( s \right) = \mathop {\max }\limits_\pi {V^\pi }\left( s \right) = \mathop {\max }\limits_a \mathop {{\rm{ }}E}\limits_{s'} \left\{ {r\left( {s,a,s'} \right) + \lambda {V^*}\left( {s'} \right)} \right\} = \mathop {\max }\limits_a \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V^*}\left( {s'} \right)} \right\}}$ ${Q^*}\left( {s,a} \right) = \mathop {\max }\limits_\pi {Q^\pi }\left( {s,a} \right) = \mathop {{\rm{ }}E}\limits_{s'} \left\{ {r\left( {s,a,s'} \right) + \mathop {\max }\limits_{a'} \lambda {Q^*}\left( {s',a'} \right)} \right\} = \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \mathop {\max }\limits_{a'} \lambda {Q^*}\left( {s',a'} \right)} \right\}}$ 下面是一個(gè)比較直觀的示意圖
[圖片上傳失敗...(image-5cfe92-1535181350541)]

一旦有了最優(yōu)值函數(shù)桐臊，就很簡(jiǎn)單確定 optimal policy 了，即對(duì)于任意 state晓殊，選使得值函數(shù)最大的 action 即可断凶。任何關(guān)于最優(yōu)值函數(shù)的貪心 policy 都算最優(yōu) policy。

貌似挺物，只要顯式解決了 Bellman Optimality Equation 就找到了 optimal policy懒浮。但這個(gè)方法僅僅是理論，基本行不通识藤，除非至少滿足以下假設(shè)：

能對(duì) environment 精確建模
足夠的巨大計(jì)算資源
滿足 Markov 性

顯然砚著，實(shí)際中，這三個(gè)假設(shè)很難滿足痴昧，通常不可能直接解上述 Bellman Optimality Equation 來(lái)得到 optimal policy稽穆，都是用一些近似方法來(lái)求解 Bellman Optimality Equation。

2.4 MDP 優(yōu)化方法

利用 MDP 對(duì)問(wèn)題建完模赶撰，求解 $J\left( \pi \right)$ 的最優(yōu)化舌镶，直觀思路是直接從 $J\left( \pi \right)$ 下手柱彻，將其看成普通的參數(shù)優(yōu)化問(wèn)題，利用 SGD 類(lèi)方法求解餐胀；或者從上面引導(dǎo)出的 Bellman Optimality Equation 入手哟楷，不停迭代逼近最優(yōu)值函數(shù)。根據(jù)這兩種不同思路否灾，可以將解決方法歸類(lèi)為三種：

critic-only 類(lèi)卖擅，學(xué)習(xí) value func，不涉及參數(shù)化的 policy
actor-only 類(lèi)墨技，學(xué)習(xí)參數(shù)化的 policy惩阶，不涉及 value func
actor-critic 類(lèi)，將 value func 與參數(shù)化 policy 結(jié)合

where ‘a(chǎn)ctor’ is a reference to the learned policy, and ‘critic’ refers to the learned value function, usually a state value function.

3 Critic-only 類(lèi)方法

該類(lèi)方法的思路基本都是扣汪，先想辦法評(píng)估當(dāng)前值函數(shù)断楷，然后針對(duì)當(dāng)前值函數(shù)遍歷 action 得到當(dāng)前最優(yōu) policy，然后繼續(xù)估計(jì)采用該最優(yōu) policy 的值函數(shù)崭别，循環(huán)往復(fù)冬筒。
該類(lèi)方法還可以分為 model-based 類(lèi)和 model-free 類(lèi)：

前一種利用 model 的 P 和 R 來(lái)計(jì)算值函數(shù)，以 DP-based 類(lèi)方法紊遵，RMax 方法為主
后一種處理現(xiàn)實(shí)中往往 P 和 R 未知的情況账千，并不對(duì) model 進(jìn)行建模學(xué)習(xí)，包括 MC-based 方法和 TD-based 方法

prediction v.s. control

Prediction or evaluation problem, is that of estimating the value function for a given policy π.
Control problem , is that of finding an optimal policy.

無(wú)論是否基于 model暗膜，critic-only 類(lèi)方法都可以看作以下范式：先進(jìn)行 Prediction匀奏，然后進(jìn)行 Control。
主要區(qū)別在于處理 prediction problem 的方法学搜。而 Control problem 都是采用 greedy-search 方法娃善。

3.1 DP-based methods

該類(lèi)方法屬于 model-based 類(lèi)，即已知 P 和 R 可以用來(lái)計(jì)算 value func瑞佩，主要依靠 Bellman optimality equations聚磺。

policy iteration

第一種思路是，首先根據(jù)當(dāng)前 policy炬丸，計(jì)算 value func 來(lái)對(duì)當(dāng)前 policy 進(jìn)行評(píng)估瘫寝，然后基于這個(gè) value func 來(lái) greedy search 最好的 action 從而更新 policy，循環(huán)往復(fù)稠炬』腊ⅲ總結(jié)為兩步：

predict：這里稱(chēng) policy evaluation，根據(jù) policy 計(jì)算 value func
${V^\pi }\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)} \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V^\pi }\left( {s'} \right)} \right\}}$ 只要 λ<1 或者在π下存在最終結(jié)束狀態(tài)首启，那么 ${V^\pi }\left( s \right)$ 就存在且唯一暮屡。上面實(shí)際是 |S| 個(gè)聯(lián)立的方程，不存在時(shí)序概念毅桃。通常值函數(shù)的計(jì)算利用迭代逼近褒纲，即 iterative policy evaluation ${V_{k+1}^\pi }\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)} \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V_k^\pi }\left( {s'} \right)} \right\}}$
control：這里稱(chēng) policy improvment准夷，針對(duì) state-action value func 遍歷 action 得到當(dāng)前最優(yōu) policy 來(lái)更新 policy （由 Bellman optimality equations，知道 ${V^*}\left( s \right) = \mathop {\max }\limits_a {{Q^*}\left( s,a \right)}$ ）莺掠，自然下面更新也是對(duì) |S| 個(gè) state 都進(jìn)行
$\pi '\left( s \right) = \mathop {\arg \max }\limits_a {Q^\pi }\left( {s,a} \right)$
循環(huán)往復(fù)衫嵌，直至 value func 收斂

該思路稱(chēng)為 policy iteration 算法，算法效率還算高汁蝶，除非已經(jīng)收斂到最優(yōu) policy渐扮，否則 policy 的每次 improvement 都是嚴(yán)格提升的。

value iteration

第二種思路是掖棉，上面 policy evaluation 過(guò)程由于迭代計(jì)算值函數(shù)，每次都要掃描 S膀估，迭代過(guò)程理論上趨于無(wú)窮才收斂幔亥，如果等到 policy evaluation 收斂才進(jìn)行 policy improvement，顯然是很耗時(shí)的察纯。事實(shí)上帕棉，policy iteration 中的 policy evaluation 進(jìn)行裁剪（減少迭代計(jì)算次數(shù)）并不會(huì)影響算法的收斂性，極端情況就是 policy evaluation 時(shí)僅進(jìn)行一次迭代計(jì)算饼记，就進(jìn)行 policy improvement香伴，這種方式稱(chēng)為 value iteration 算法：
${V_{k+1}^{\pi}}\left( s \right) = \mathop {\max }\limits_a \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \lambda {V_{k}^{\pi} }\left( {s'} \right)} \right\}}$ 或者 ${Q_{k+1}^{\pi}}\left( {s,a} \right) = \sum\limits_{s'} {p\left( {s'|s,a} \right)\left\{ {r\left( {s,a,s'} \right) + \mathop {\max }\limits_{a'} \lambda {Q_{k}^{\pi}}\left( {s',a'} \right)} \right\}}$

generalized policy iteration

對(duì)比上面兩種算法，可見(jiàn) Policy iteration 多次迭代 Bellman equation 直到收斂具则，而 Value iteration 僅僅迭代一次 Bellman equation（實(shí)際上利用的 Bellman optimality equation 作為更新規(guī)則）區(qū)別主要在于 policy evaluation 和 policy improvement 兩個(gè)環(huán)節(jié)的交織方式即纲。
兩者本質(zhì)上的區(qū)別是數(shù)值分析中的 explicit method 和 implicit method 的區(qū)別，explicit 方法收斂慢博肋、穩(wěn)定性差低斋，但 implicit method 要解方程。如果方程沒(méi)有解析解匪凡，解這個(gè)方程本身又要用數(shù)值迭代方式膊畴。

介于兩者之間的就是 generalized policy iteration，即多次迭代來(lái)進(jìn)行 policy evaluation 然后 policy improvement病游。這種闡述方式基本是大多 RL 算法的范式唇跨。
有趣的是，policy evaluation 然后 policy improvement 兩個(gè)環(huán)節(jié)可以看做既競(jìng)爭(zhēng)又合作衬衬。競(jìng)爭(zhēng)說(shuō)的是买猖，它們引導(dǎo)的方向相反。policy improvement 中的 greedy-search 會(huì)讓 value func 偏離新的 policy佣耐，而 policy evaluation 中追求 value func 與 policy 一致會(huì)使得 policy 對(duì)于 value func 不再 greedy政勃。但從長(zhǎng)期來(lái)看，這兩個(gè)環(huán)節(jié)會(huì)交錯(cuò)合作來(lái)找到那個(gè)唯一的聯(lián)合解兼砖，即最優(yōu) policy 和最優(yōu) value func奸远。

維度災(zāi)難

該類(lèi)方法很大一個(gè)局限就是算法的復(fù)雜度既棺，尋找到最優(yōu) policy 的復(fù)雜度是 $O\left( {\left| S \right|\left| A \right|} \right)$ ，看著只是 S 和 A 個(gè)數(shù)的線性關(guān)系懒叛，但通常我們談?wù)摰乃惴◤?fù)雜度不是用狀態(tài)空間的中值的個(gè)數(shù)而是狀態(tài)空間的維數(shù)丸冕，那么上面的復(fù)雜度實(shí)際應(yīng)該是狀態(tài)空間和動(dòng)作空間的指數(shù)階，這就是 Bellman 提出的維度災(zāi)難薛窥。
但 DP-based methods 要比窮搜和線性規(guī)劃好上不少胖烛，在當(dāng)前計(jì)算力下，解決擁有百萬(wàn)狀態(tài)的 MDP诅迷，DP-based methods 也是沒(méi)問(wèn)題的佩番。

3.2 RMax method

針對(duì)無(wú)模型情況，有兩種思路罢杉，一種是想辦法還原出 P 和 R 即還原出 MDP model趟畏，然后再在這個(gè) model 上進(jìn)行策略優(yōu)化，這還是屬于 model-based 思路滩租；另一種是不還原直接優(yōu)化赋秀，即 model-free 思路。
RMax 即屬于前一種思路律想，MC-based 和 TD-based 屬于后一種猎莲。

RMax 方法，利用隨機(jī)游走技即，通過(guò)計(jì)數(shù)這個(gè)簡(jiǎn)單的回歸模型來(lái)還原 MDP著洼。但僅還原 MDP 的抽樣復(fù)雜度就是 $O\left( {\left| S \right|^2\left| A \right|} \right)$ 級(jí)別，所以人們通常關(guān)注 model-free 類(lèi)方法姥份。這里就不介紹 RMax 了郭脂。

3.3 MC-based method

model-free 類(lèi)方法驰唬，整體流程和前面 DP-based 類(lèi)似鳄袍，也是先進(jìn)行 predict，然后利用 greedy-search 來(lái)解決 control畅卓。

MC-based 方法不需要前面 DP-based 類(lèi)方法中 P 和 R 的先驗(yàn)埃难，僅需要 experiences —— agent 與 env 的交互序列（s,a,r）莹弊，即不需知道 model 的真實(shí)分布，只需要 model 的真實(shí)分布的采樣涡尘。
算法思路也很簡(jiǎn)單忍弛，利用采樣平均值來(lái)替代 value func 中的期望值，實(shí)質(zhì)就是使用統(tǒng)計(jì)學(xué)的方法來(lái)取代 Bellman 方法考抄。計(jì)算方法還是分兩步：

predict：從初始 state-action 出發(fā)细疚，以某種 policy 進(jìn)行采樣，執(zhí)行該 policy 進(jìn)行 T 步得到對(duì)應(yīng)軌跡川梅，針對(duì)軌跡中每一對(duì) $(s_t, a_t)$ 疯兼，記錄其后的總回報(bào)作為對(duì)應(yīng) state-action 的一次采樣值然遏，多次采樣得到多條軌跡后將每對(duì) $(s_t, a_t)$ 的所有 value func 進(jìn)行 mean 即為該 $(s_t, a_t)$ 值函數(shù)的估計(jì)值。
control：仍用 greedy-search 法吧彪。

這里寫(xiě)圖片描述

注意上面 Q 和 V 不再像 DP-based methods 中那樣通用待侵。在有 model 時(shí)，即使只有 V 也可以利用下一個(gè)狀態(tài)的信息得到 Q 從而決定 policy姨裸，但當(dāng)沒(méi)有 model 時(shí)秧倾，僅 V 不足夠得到 Q 從而沒(méi)法指導(dǎo) policy 更新。因此傀缩，MC-based 中 predict 的是 Q 而非 V那先。

MC-based 方法中 $(s_t, a_t)$ 的估計(jì)是獨(dú)立于其他 $(s_t, a_t)$ 的，因此有一個(gè)好處就是可以僅關(guān)注感興趣的 $(s_t, a_t)$ 赡艰，即僅產(chǎn)生從 $(s_t, a_t)$ 出發(fā)的軌跡胃榕。

first-visit v.s. every-visit

記對(duì)（s,a）的一次 visit 為一條軌跡中（s,a）的一次出現(xiàn)。first-visit MC-based method 即在 policy evaluation 時(shí)僅利用軌跡中第一次出現(xiàn)（s,a）后的總回報(bào)為采樣值瞄摊，而 first-visit MC-based method 即在 policy evaluation 時(shí)利用軌跡中每次出現(xiàn)（s,a）后的總回報(bào)為采樣值。
前者更經(jīng)典些苦掘，研究的更多些换帜，后者則比較好拓展到后面要介紹的 function approximation 和 eligibility traces。
無(wú)論哪種鹤啡，隨著軌跡中對(duì)（s,a）的 visit 趨于無(wú)窮惯驼，MC-based policy evaluation 都會(huì)收斂到估計(jì)的值函數(shù)。

Incremental mean 原理

上面算法中倒數(shù)第五行所在的 for 循環(huán)實(shí)現(xiàn)了值函數(shù)的 batch update递瑰，類(lèi)似于（加了 one-visit） ${Q^\pi }\left( {s,a} \right) = {1 \over m}\sum\limits_{i = 1}^m {r\left( {trajector{y_i}} \right)}$ 祟牲。
利用 Incremental mean 原理： ${\mu _k} = {1 \over k}\sum\limits_{i = 1}^k {{x_i}} = {1 \over k}\left( {{x_k} + \sum\limits_{i = 1}^{k - 1} {{x_i}} } \right) = {1 \over k}\left( {{x_k} + \left( {k - 1} \right){\mu _{k - 1}}} \right) = {\mu _{k - 1}} + {1 \over k}\left( {{x_k} - {\mu _{k - 1}}} \right)$ ，可以將其變成 incremental update 形式抖部， ${Q^\pi }\left( {s,a} \right) \leftarrow {Q^\pi }\left( {s,a} \right) + \alpha \left( {R - {Q^\pi }\left( {s,a} \right)} \right)$ 说贝，其中 ${R - {Q^\pi }\left( {s,a} \right)}$ 部分稱(chēng)為 MC error。注意 R 不是 r慎颗。則算法流程如
[圖片上傳失敗...(image-346a0e-1535181350541)]

exploration-exploitation dilemma

有個(gè)問(wèn)題需要思考下乡恕，可能很多（s,a）都不會(huì)出現(xiàn)在軌跡中從而沒(méi)法估計(jì)其值函數(shù)，尤其當(dāng) greedy-search 得到了 deterministic policy俯萎，那么豈不是每次軌跡都是一樣的傲宜？
這就涉及一個(gè)經(jīng)典問(wèn)題，exploration-exploitation dilemma夫啊。常用的處理方法是采用 ε-greedy search函卒，即在 control/探索時(shí)，以 1-ε 選擇當(dāng)下最好的 policy 實(shí)現(xiàn) exploitation撇眯，以 ε 進(jìn)行隨機(jī)選擇實(shí)現(xiàn) exploration报嵌。

on/off policy

引入一個(gè)概念虱咧，在探索和學(xué)習(xí)階段，如果采用同一個(gè) policy沪蓬，即為 on policy彤钟，不同則為 off policy。

上面 MC-based method 就是為了探索所以 behave π-ε跷叉，但在學(xué)習(xí)時(shí)也使用 π-ε逸雹，而實(shí)際上我們要學(xué)習(xí)的應(yīng)是不帶探索的 π，即探索用 π-ε云挟，學(xué)習(xí)用 π梆砸，即 off policy。
通常把 off policy 中用來(lái)探索空間（生成軌跡）的 policy 稱(chēng)為 behavior policy园欣，把用來(lái)學(xué)習(xí)（evaluation & improvement）為了達(dá)到最優(yōu)的 policy 稱(chēng)為 target policy帖世。事實(shí)上，這種思路不僅用在 MC-based method 中沸枯。
由于 behaviour policy 和 target policy 不相關(guān)日矫，這種方法方差也較大，比較不容易收斂绑榴。但是 off-policy 更強(qiáng)大哪轿，更通用。比如翔怎，可以使用 off-policy 從人類(lèi)專(zhuān)家或者傳統(tǒng)的控制算法來(lái)學(xué)習(xí)一個(gè)增強(qiáng)學(xué)習(xí)模型窃诉。

Importance Sampling

回到 MC-based method 的 off policy 機(jī)制，這里面臨一個(gè)問(wèn)題赤套，從 π-ε 中采樣和 π 是有區(qū)別的飘痛，一個(gè)需要滿足的基本假設(shè)是 coverage assumption，即 every action taken under π is also taken, at least occasionally, under π-ε容握。
幾乎所有的 off policy 都使用 Importance Sampling 技術(shù)宣脉，從而可以根據(jù)某分布（behaviour policy）的樣本來(lái)估計(jì)另一分布（target policy）的某個(gè)期望值（Q）。

比如我們想獲得 p 分布中 f 的均值唯沮，但 p 分布的樣本 x 并不好生成脖旱，利用 Importance Sampling，可以引入另一個(gè)更方便生成樣本的分布 q介蛉，從而將問(wèn)題轉(zhuǎn)化為求 $g(x) = f(x){{p(x)} \over {q(x)}} = f(x)w(x)$ 在 $q(x)$ 分布下的期望萌庆，其中 $w(x) = {{p(x)} \over {q(x)}}$ 稱(chēng)為 importance weight，具體如下式：
[圖片上傳失敗...(image-1b9dcc-1535181350541)]
具體到 MC-based method币旧，π 對(duì)應(yīng)分布 p践险，π-ε 對(duì)應(yīng)分布 q，因此在計(jì)算 R 時(shí)每個(gè)來(lái)自 π-ε 的樣本都要乘上一個(gè) importance weight，其構(gòu)造方式多樣巍虫，通常為軌跡在 target policy 和 behavior policy 下的相對(duì)概率彭则。算法流程如下
[圖片上傳失敗...(image-983152-1535181350541)]

3.4 TD-based methods

TD-based methods 結(jié)合了 DP-based 方法和 MC-based 方法的思想，即像 MC-based 一樣不需要建恼家＃可以從 experiences 中直接學(xué)習(xí)俯抖，也像 DP-based 一樣基于其他已經(jīng)學(xué)習(xí)到的估計(jì)來(lái)更新估計(jì)（即 bootstrap）。通常認(rèn)為瓦胎，TD-based methods 是 RL 的精華與核心芬萍。

MC-based method 好理解，但有個(gè)嚴(yán)重缺陷搔啊，就是一定要跑完所有 epoches 得到整個(gè)軌跡以后柬祠，才能更新模型，效率很低负芋。即在 MC-based 的 evaluation 過(guò)程中漫蛔， ${Q^\pi }\left( {s_t, a_t} \right) \leftarrow {Q^\pi }\left( {s_t,a_t} \right) + \alpha \left( {R_t - {Q^\pi }\left( {s_t,a_t} \right)} \right)$ ，必須要等到這個(gè) trajectory 結(jié)束旧蛾，才能得到 $R_t$ 莽龟，才能對(duì) Q 進(jìn)行 incremental upgrade。
考慮到 ${R_t} = \sum\limits_{k = 0}^\infty {{\lambda ^k}{r_{t + k + 1}}} = {r_{t + 1}} + \lambda \sum\limits_{k = 0}^\infty {{\lambda ^k}{r_{t + k + 2}}} = {r_{t + 1}} + \lambda Q\left( {{s_{t + 1},a_{t+1}}} \right)$ 锨天，可見(jiàn) TD-based 可以只等一個(gè) epoch轧房，在下一個(gè)時(shí)刻就利用觀察到的 r 和估計(jì)的值函數(shù)進(jìn)行一次有效更新，即
${Q^\pi }\left( {{s_t,a_t}} \right) \leftarrow {Q^\pi }\left( {{s_t,a_t}} \right) + \alpha \left( {{r_{t + 1}} + \lambda {Q^\pi }\left( {{s_{t + 1},a_{t + 1}}} \right) - {Q^\pi }\left( {{s_t,a_t}} \right)} \right)$

可見(jiàn)绍绘，MC-based 更新的目標(biāo)是 $R_t$ ，而 TD-based 更新的目標(biāo)是 ${{r_{t + 1}} + \lambda {Q^\pi }\left( {{s_{t + 1},a_{t + 1}}} \right)}$ 迟赃。TD error 雖然是 t 時(shí)刻 V 的誤差陪拘，但由于依賴 t+1 時(shí)刻的 reward 和 state-action pair，所以在 t+1 時(shí)刻才可用纤壁。

由于每個(gè) epoch 即可更新一次左刽，所以 TD-based 方法很大一個(gè)好處就是可以 on-line 執(zhí)行。
雖然目前沒(méi)有理論證明酌媒，但實(shí)踐表明 TD-based 相較 MC-based 收斂的更快一些欠痴。

SARSA v.s. Q-learning

把上面 TD-based 的估計(jì)方式應(yīng)用起來(lái)，就能得到具體的 RL 算法秒咨，下面介紹的 SARSA 就是 on-policy TD-based method喇辽，Q-learning 就是 off-policy TD-based method。
[圖片上傳失敗...(image-54c566-1535181350541)]
[圖片上傳失敗...(image-8df92e-1535181350541)]
仔細(xì)觀察雨席，可以發(fā)現(xiàn) Q-learning 中 evaluation 的更新也可以寫(xiě)作：
$Q\left( {{s_t},{a_t}} \right) \leftarrow Q\left( {{s_t},{a_t}} \right) + \alpha \left( {{r_{t + 1}} + \lambda \mathop {\max }\limits_{{a_{t + 1}}} Q\left( {{s_{t + 1}},{a_{t + 1}}} \right) - Q\left( {{s_t},{a_t}} \right)} \right)$ 菩咨，即相當(dāng)于把 policy iteration 改為 value iteration。

n-step return

之前列出的算法稱(chēng)為 one-step TD-based method。也可以取 TD-based method 和 MC-based method 兩者之間抽米，即利用 n epoches 信息來(lái)更新對(duì)值函數(shù)的估計(jì)特占，對(duì)于 n-step return 有
$R_t^n = \sum\limits_{i = 0}^n {{\lambda ^{k - 1}}{r_{t + i}}} + {\lambda ^n}Q\left( {{s_{t + n},a_{t + n}}} \right)$

很簡(jiǎn)單，有 n-step TD-based methods：
${Q^\pi }\left( {{s_t},a_t} \right) \leftarrow {Q^\pi }\left( {{s_t,a_t}} \right) + \alpha \left( {R_t^n - {Q^\pi }\left( {{s_t,a_t}} \right)} \right)$

eligibility trace

幾乎所有 TD-based methods 都可以結(jié)合 eligibility trace 機(jī)制云茸，從而更高效地實(shí)現(xiàn)是目。

（該節(jié)待補(bǔ)充）

雖然利用 n-step return，也統(tǒng)一了 TD-based 和 MC-based标捺，但相對(duì)原始懊纳。當(dāng) TD-based 結(jié)合了 eligibility trace，相當(dāng)于將原來(lái)的方法拓展到一個(gè)頻譜上宜岛，一端是 one-step TD-based（λ=0）长踊，一端是 MC-based（λ=1），更完美的統(tǒng)一了 TD-based 和 MC-based萍倡。

3.5 Value function approximation

上面所有提到的算法都屬于 tabular representation身弊，即值函數(shù)是通過(guò)一個(gè) lookup table 來(lái)表示的，如每個(gè) state 都有對(duì)應(yīng)的 V(s)列敲，每個(gè) state-action 都有對(duì)應(yīng)的 Q(s,a)阱佛。這種表示自然有難以回避的問(wèn)題：對(duì)于大規(guī)模問(wèn)題（state 空間巨大，state-action 空間巨大）的內(nèi)存耗費(fèi)難以接受戴而，學(xué)習(xí)所有的值函數(shù)速度也難以接受凑术。

在有限計(jì)算資源情況下，處理大規(guī)模 MDP 問(wèn)題所意，就需要這里要講的 approximation solution淮逊。準(zhǔn)確來(lái)說(shuō)，就是使用監(jiān)督學(xué)習(xí)的思想扶踊，構(gòu)建一個(gè)函數(shù)逼近模型泄鹏，在已經(jīng)見(jiàn)過(guò)的那部分 state or state-action 空間上構(gòu)建一個(gè)函數(shù)逼近的值函數(shù)，然后泛化到未知的數(shù)據(jù)秧耗。可以表達(dá)為： $\hat V\left( {s,\theta } \right) \approx {V^\pi }\left( s \right)$ or $\hat Q\left( {s,a,\theta } \right) \approx {Q^\pi }\left( {s,a} \right)$ 备籽。
函數(shù) $\hat V$ 是參數(shù) θ 的可微函數(shù)，可以用線性函數(shù)分井、MLP车猬、決策樹(shù)，就像監(jiān)督學(xué)習(xí)中尺锚，參數(shù) θ 的維度遠(yuǎn)遠(yuǎn)小于狀態(tài)的數(shù)量珠闰，因此改變參數(shù)的一個(gè)權(quán)重可以改變很多 state 的估值，從而一個(gè) state 更新后瘫辩，其帶來(lái)的變化會(huì)影響很多其他 state 的估值铸磅，即產(chǎn)生了泛化赡矢。關(guān)于訓(xùn)練方法則需要一種適合于不穩(wěn)定、不獨(dú)立分布數(shù)據(jù)的阅仔。

假設(shè)用 $\hat V\left( {s,\theta } \right)$ 來(lái)逼近 ${V^\pi }\left( {s} \right)$ 吹散，記均方誤差為 $J\left( \theta \right) = {E_{s \sim \pi }}\left[ {{{\left( {{V^\pi }\left( {s} \right) - \hat V\left( {s,\theta } \right)} \right)}^2}} \right]$ ，很容易得到 SGD 的更新公式為： $\Delta {\theta _t} = \alpha \left( {{V^\pi }\left( {s} \right) - \hat V\left( {s,\theta } \right)} \right){\nabla _\theta }\hat V\left( {s,\theta } \right)$

會(huì)像前面提到 MC-based 和 TD-based evaluation 時(shí)更新公式分別為：
${V^\pi }\left( {s_t} \right) \leftarrow {V^\pi }\left( {s_t} \right) + \alpha \left( {R_t - {V^\pi }\left( {s_t} \right)} \right)$ ${V^\pi }\left( {{s_t}} \right) \leftarrow {V^\pi }\left( {{s_t}} \right) + \alpha \left( {{r_{t + 1}} + \lambda {V^\pi }\left( {{s_{t + 1}}} \right) - {V^\pi }\left( {{s_t}} \right)} \right)$
可以認(rèn)為 $R_t$ 和 ${r_{t + 1}} + \lambda {V^\pi }\left( {{s_{t + 1}}} \right)$ 分別為 target八酒， {V^\pi } 即 model空民。
因此，MC-based 和 TD-based 在利用函數(shù)逼近時(shí)的更新公式分別變?yōu)?br> $\Delta {\theta _t} = \alpha \left( {R_t - \hat V\left( {s,\theta } \right)} \right){\nabla _\theta }\hat V\left( {s,\theta } \right)$ $\Delta {\theta _t} = \alpha \left( {{r_{t + 1}} + \lambda {V^\pi }\left( {{s_{t + 1}}} \right) - \hat V\left( {s,\theta } \right)} \right){\nabla _\theta }\hat V\left( {s,\theta } \right)$

總結(jié)下利用函數(shù)逼近的大致流程就是：

先隨機(jī)初始化一個(gè) policy羞迷，然后使用MC-based or TD-based 的方法來(lái)調(diào)整 θ 得到 approximation 的值函數(shù)界轩；
基于該 approximation 的值函數(shù)，進(jìn)行 policy improvement衔瓮；
然后循環(huán)迭代浊猾。

即，value function approximation 只做 policy evaluation(predict) 部分热鞍，policy improvement(control) 部分還需要單獨(dú)的策略葫慎，比如 ε-greedy。

4 Actor-only 類(lèi)方法

前面介紹到的 Critic-only 類(lèi)方法薇宠，從 DP/MC/TD 到 Value function approximation偷办，關(guān)注的是 state 空間的 scaling 問(wèn)題，那么 action 空間如何 scaling 呢澄港？面對(duì)高維或者連續(xù)的 action 空間椒涯，critic-only 以來(lái)的 greedy-search 方法自然是難以應(yīng)付了。
此外回梧，基于值函數(shù)的方法废岂，存在 policy degradation 現(xiàn)象，這就表明對(duì)于次優(yōu)的 policy 來(lái)說(shuō)狱意，更好的值函數(shù)并不對(duì)應(yīng)更好的 policy泪喊，因此，前面這種利用優(yōu)化值函數(shù)間接優(yōu)化 policy 的思路并不完美髓涯。

Actor-only 類(lèi)方法，即直接通過(guò)參數(shù)化的 policy 學(xué)習(xí) $\max J\left( \pi_\theta \right)$ 哈扮。 $\pi_\theta$ 的學(xué)習(xí)過(guò)程可能仍涉及到值函數(shù)纬纪，但值函數(shù)并不是再用來(lái)選擇 action 的。這就是個(gè)典型的優(yōu)化問(wèn)題了滑肉，許多數(shù)學(xué)工具可以應(yīng)用包各。
先看下梯度上升 ${\theta _{k + 1}} = {\theta _k} + \alpha {\nabla _\theta }J\left( {{\theta _k}} \right)$ ，需要 policy gradient ${\nabla _\theta }J\left( \theta \right) = {{\partial J} \over {\partial {\pi _\theta }}}{{\partial {\pi _\theta }} \over {\partial \theta }}$ 靶庙。那么如何計(jì)算 policy gradient 呢问畅？通常有兩個(gè)方向：

Finite-difference methods
Likelihood ratio methods

4.1 Finite-difference methods

非常簡(jiǎn)單粗糙，就是對(duì)參數(shù)產(chǎn)生小的擾動(dòng)，用 $J\left( \pi_\theta \right)$ 的變化率來(lái)估計(jì)其導(dǎo)數(shù)护姆，如下 ${{\partial J\left( \theta \right)} \over {\partial {\theta _i}}} \approx {{J\left( {\theta + \varepsilon {\mu _k}} \right) - J\left( \theta \right)} \over \varepsilon }$

方法雖然很簡(jiǎn)單矾端，但可以用，即使 policy 是不可導(dǎo)的卵皂。但顯然噪聲太大秩铆，效率也較低。

4.2 Likelihood ratio methods

顯然上面的方法并不常用灯变，這里介紹 Likelihood ratio methods殴玛，也稱(chēng)為 REINFORCE 算法。

policy gradient theorem

很重要一個(gè)定理添祸，也稱(chēng)為 stochastic policy gradient 公式滚粟，后面會(huì)提到 deterministic policy gradient公式。
$\nabla_\theta J\left( \theta \right) = \mathop E\limits_{s \sim {\rho ^\pi },a \sim {\pi _\theta }} \left[ {{Q^\pi }\left( {s,a} \right){\nabla _\theta }\pi \left( {a|s,\theta } \right)} \right]$
這里加個(gè) logarithm trick刃泌，即可將 SPG 公式變?yōu)椋?br> $\nabla_\theta J\left( \theta \right) = \mathop {{\rm{ }}E}\limits_{s\sim {\rho ^\pi },a\sim {\pi _\theta }} \left[ {{Q^\pi }\left( {s,a} \right){\nabla _\theta }\log \left( {\pi \left( {a|s,\theta } \right)} \right)} \right]$

下面問(wèn)題就是如何得到上面 SPG凡壤，這里仍然使用了抽樣平均逼近期望的方式，即 MC-based 方式蔬咬。
從軌跡產(chǎn)生的角度鲤遥，利用 likelihood ratios 計(jì)算 policy gradient 為：
${\nabla _\theta }J\left( \theta \right) = \mathop E\limits_{trajectory} \left[ {{J^{traj}}\sum\limits_{t = 0}^T {{\nabla _\theta }\log \left( {\pi \left( {{a_t}|{s_t},\theta } \right)} \right)} } \right]$
可以直接將上面的 trajectory return 換為值函數(shù)，即為
${\nabla _\theta }J\left( \theta \right) = \mathop E\limits_{trajectory} \left[ {\sum\limits_{t = 0}^T {{Q^\pi }\left( {{s_t},{a_t}} \right){\nabla _\theta }\log \left( {\pi \left( {{a_t}|{s_t},\theta } \right)} \right)} } \right]$

baseline

再來(lái)看下上面用到的 SPG 公式林艘，其表征當(dāng)值函數(shù)越大的 action 越努力提高它出現(xiàn)的概率盖奈。但有時(shí)某個(gè) state 對(duì)應(yīng)的每個(gè) action 的值函數(shù)都為正，即所有的 PG 都為正狐援，此時(shí)每個(gè) action 出現(xiàn)的概率都會(huì)提高钢坦，這會(huì)大幅減緩學(xué)習(xí)速度，并增大 PG 的方差啥酱，因此需要對(duì) SPG 公式中的值函數(shù)進(jìn)行某種標(biāo)準(zhǔn)化來(lái)降低方差爹凹。

通常，實(shí)踐中镶殷，會(huì)在 $J^{traj}$ 或者 ${Q^\pi }\left( {{s_t},{a_t}} \right)$ 中減去一個(gè) baseline禾酱，用來(lái)降低方差，加快學(xué)習(xí)绘趋。
以值函數(shù)為例颤陶，baseline 用來(lái)給值函數(shù)作比較用，可以使不隨 action 變化的任意函數(shù)陷遮，即
${\nabla _\theta }J\left( \theta \right) = \mathop {{\rm{ }}E}\limits_{trajectory} \left[ {\sum\limits_{t = 0}^T {\left( {{Q^\pi }\left( {{s_t},{a_t}} \right) - b\left( {{s_t}} \right)} \right){\nabla _\theta }\log \left( {\pi \left( {{a_t}|{s_t},\theta } \right)} \right)} } \right]$
此時(shí)滓走，更新參數(shù)時(shí)，值函數(shù)超過(guò) baseline 的 action 對(duì)應(yīng)的概率才會(huì)提高帽馋，理論證明這可以降低 PG 的方差搅方。
實(shí)踐中比吭，通常選取值函數(shù)的一個(gè)期望估計(jì)作為 baseline。

實(shí)際上姨涡，這種思路已經(jīng)類(lèi)似 Actor-Critic 體系了衩藤。

5 Actor-Critic 類(lèi)方法

首先來(lái)回顧下前面介紹到的 Critic-only 類(lèi)方法、Actor-only 類(lèi)方法：

critic-only 雖然方差低绣溜，但無(wú)法處理連續(xù) A 域
actor-only 能處理連續(xù) A 域慷彤，但高方差

AC 類(lèi)方法，旨在結(jié)合兩者優(yōu)點(diǎn)怖喻，使用參數(shù)化的 actor 來(lái)產(chǎn)生 action底哗，使用 critic 的低方差的梯度估計(jì)來(lái)支撐 actor。
簡(jiǎn)答來(lái)說(shuō)锚沸，policy 網(wǎng)絡(luò)是 actor跋选，進(jìn)行action-selection，value 網(wǎng)絡(luò)是 critic哗蜈，通過(guò)值函數(shù)來(lái)評(píng)價(jià) actor 網(wǎng)絡(luò)所選動(dòng)作的好壞
[圖片上傳失敗...(image-d2b749-1535181350541)]
如此以來(lái)前标，critic 利用值函數(shù)方法來(lái)更好地評(píng)估策略，能給 actor 一個(gè)更好的梯度估計(jì)值距潘，能改善局部?jī)?yōu)化的問(wèn)題炼列。 actor 則避免了值函數(shù)中低效的值估計(jì)過(guò)程，同時(shí)也能應(yīng)對(duì)連續(xù) A 域音比。

bootstrap

這里用到的 bootstrap俭尖，指 DP-based、TD-based 中洞翩，用某個(gè)估計(jì)值來(lái)更新估計(jì)值的思想稽犁。DP-based 中，用下一個(gè)狀態(tài)的值函數(shù)估計(jì)值來(lái)估計(jì)這個(gè)狀態(tài)的值函數(shù)骚亿。TD-based 中已亥，部分基于其他狀態(tài)的估計(jì)來(lái)更新估計(jì)值。而 MC-based 關(guān)于各個(gè)值函數(shù)的估計(jì)是獨(dú)立的来屠，換言之虑椎，該狀態(tài)的值函數(shù)估計(jì)并不依賴于其他狀態(tài)的估計(jì)，因此俱笛，沒(méi)有利用 bootstrap捆姜。
通過(guò) bootstrap，可以引入偏差嫂粟，以及對(duì)函數(shù)逼近效果的漸進(jìn)依賴。這可以降低方差墨缘、加快學(xué)習(xí)速度星虹。

那么就可以看出零抬，雖然 REINFORCE + baseline 方法通過(guò) policy 和值函數(shù)來(lái)一起學(xué)習(xí)，但并不能稱(chēng)為 AC 類(lèi)宽涌，因?yàn)橹岛瘮?shù)只在那里用作 baseline 來(lái)更新?tīng)顟B(tài)平夜，而非用作 bootstrap。如此以來(lái)卸亮，REINFORCE + baseline 是無(wú)偏的忽妒，并將漸進(jìn)收斂于局部最小值，但又會(huì)像所有的 MC-based method 那樣兼贸，由于高方差而學(xué)習(xí)很慢段直，且難以在線運(yùn)行。
所以 AC 架構(gòu)中溶诞，actor 通常選用 TD-based methods鸯檬。

具體的算法，這里就不介紹了螺垢，在下一篇的文獻(xiàn)篇會(huì)具體介紹喧务，簡(jiǎn)單的比如 REINFORCE + baseline 中用對(duì)抗函數(shù)做 baseline 即可。

6 references

[1] Reinforcement Learning: An Introduction, second edition, Richard S. Sutton, Andrew G. Barto, Francis Bach.
[2] Markov Decision Processes: Discrete Stochastic Dynamic Programming, Martin L. Puterman.
[3] Introduction to Deep Reinforcement Learning From Theory to Applications, Siyi LI. (slides)
[4] 強(qiáng)化學(xué)習(xí), 俞揚(yáng). (slides)
[5] 難以一一列舉的博客

最后編輯于：2018.09.02 14:37:41

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末枉圃，一起剝皮案震驚了整個(gè)濱河市功茴，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌孽亲，老刑警劉巖坎穿，帶你破解...
沈念sama閱讀 206,602評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異墨林，居然都是意外死亡赁酝，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,442評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)旭等，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)酌呆，“玉大人，你說(shuō)我怎么就攤上這事搔耕∠对” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 152,878評(píng)論 0贊 344
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵弃榨，是天一觀的道長(zhǎng)菩收。經(jīng)常有香客問(wèn)我，道長(zhǎng)鲸睛，這世上最難降的妖魔是什么娜饵？我笑而不...
開(kāi)封第一講書(shū)人閱讀 55,306評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮官辈，結(jié)果婚禮上箱舞，老公的妹妹穿的比我還像新娘遍坟。我一直安慰自己，他們只是感情好晴股，可當(dāng)我...
茶點(diǎn)故事閱讀 64,330評(píng)論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布愿伴。她就那樣靜靜地躺著，像睡著了一般电湘。火紅的嫁衣襯著肌膚如雪隔节。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 49,071評(píng)論 1贊 285
城市分裂傳說(shuō)
那天寂呛，我揣著相機(jī)與錄音怎诫，去河邊找鬼。笑死昧谊，一個(gè)胖子當(dāng)著我的面吹牛刽虹，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播呢诬，決...
沈念sama閱讀 38,382評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼涌哲，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了尚镰？” 一聲冷哼從身側(cè)響起阀圾，我...
開(kāi)封第一講書(shū)人閱讀 37,006評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎狗唉，沒(méi)想到半個(gè)月后初烘，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,512評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡分俯，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,965評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年肾筐，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片缸剪。...
茶點(diǎn)故事閱讀 38,094評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡吗铐，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出杏节，到底是詐尸還是另有隱情唬渗，我是刑警寧澤，帶...
沈念sama閱讀 33,732評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布奋渔，位于F島的核電站镊逝，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏嫉鲸。R本人自食惡果不足惜撑蒜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,283評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧座菠，春花似錦染突、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,286評(píng)論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)也榄。三九已至巡莹，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間甜紫，已是汗流浹背降宅。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,512評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留囚霸，地道東北人腰根。一個(gè)月前我還...
沈念sama閱讀 45,536評(píng)論 2贊 354
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像拓型，于是被迫代替她去往敵國(guó)和親额嘿。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,828評(píng)論 2贊 345