Try   HackMD

李宏毅_ATDL_Lecture_23

tags: Hung-yi Lee NTU Advance Topics in Deep Learning

課程撥放清單

A3C

課程連結

Approaches

Deep Reinforcement Learning分為兩大類:

  1. Model-free Approach
    • 適用於無法窮舉的環境
    • 兩大類:
      • Policy-based
        • 訓練一個Actor,負責執行動作。
      • Value-based
        • 訓練一個Critic,負責對目前的狀況給予評價。
      • 也可以混合使用
        • Actor + Critic
  2. Model-based Approach
    • Agent採取一個動作之後會預測接下來發生什麼事。
    • AlphaGo內就有使用到Model-based,下一步棋之後計算勝率。
    • 限制較多,使用之前要對環境先建立模型,因此可以預測環境下一步會發生的事情。
      • 如果是電玩場景,環境無法窮舉,雖然圍棋的下一步變化多端,但還是可以窮舉。

目前(2017年)較多使用的是A3C,而不是DQN。

On-policy v.s. Off-policy

On-policy,要學習的Agent跟與環境互動的Agent是同一個Agent。

Off-policy,要學習的Agent跟與環境互動的Agent並不是同一個Agent,意味著要學習的那個Agent是在一邊看著另一個Agent與環境互動,以它們互動的狀況來進行學習。使用這個方法要特別注意兩個Agent之間的差距。好比你看著Joradn空間停留三秒,但是你上場的時候根本學不起來。

Actor is a Neural network

論文連結_Asynchronous Methods for Deep Reinforcement Learning

A3C=Asynchronous Advantage Actor-Critic

Actor是一個Neural Network:

  • input:observation,可以是vector,也可以是matrix。
  • output:你有那些可以被採取的action

以遊戲來說明的話,observation就是你看到的遊戲畫面,而output的action就是機器看到observation之後決定的動作,左、右、開火等,每一個action都會有一個分數,你可以用argmax的方式看那一個機率最高就採用,或者可以用隨機選擇。

要讓Actor可以採取連續動作也是可行的,所謂的連續動作指的是,假設機器人是一個多軸訊號控制,那你要一次針對多個軸做訊號輸出,假設有十軸,那你的輸出就會是十維的向量。

Actor - Goodness of an Actor

有了Actor,就需要衡量這個Actor有多好。假設每一個Actor就是一個function-

π(s),上面已經定義它是一個nn,它的參數就是
πθ

接下來我們拿這個Actor去玩遊戲,有了一連串的操作記錄,記錄著state-

S,action-
a
,reward-
r
。遊戲的總體reward我們寫為
R=t=1Trt
,記錄每一個時間點
t
的reward。

即使拿相同的Actor去玩兩次遊戲,結果不一定會是一樣,這有兩個理由:

  1. 有時候Actor可能是隨機性的,即使相同的observation也不一定會有一樣的output。
    • 上面提到過,我們可以將output視為distribution,再從裡面sample出一個action。
  2. 即使Actor看到相同的observation有一樣的action,但是遊戲中的AI也存在著隨機性。

我們可以定義expected total reward(期望值)為

R¯θπ,也就是參數為
θπ
的情況下,我們期望得到的reward有多少。

現在,我們可以拿這個

R¯θπ來估測Actor有多好。

Actor - Policy Gradient

有了評估Actor的定義,就可以做Policy Gradient,相關推導在之前課程有,可以回頭看。

直觀說明如下:

  • θπ=θπ+ηR¯θπ
    • ηR¯θπ
      :計算
      θπ
      對expected total reward的gradient,以此更新
      θπ
      得到
      θπ
  • R¯θπ1Nn=1NR(τn)logP(τn|θπ)=1Nn=1NR(τn)t=1Tnlogp(atn|stn,θπ)=1Nn=1Nt=1TnR(τn)logp(atn|stn,θπ)

上面做的事簡單的說就是,假設在某次的遊戲記錄

τn中,Actor看到某一個state-
stn
而執行某一個action-
atn
。整個遊戲玩完之後它的reward-
R(τn)
是好的,那機器就會試著去更新參數-
θ
p(atn|stn)
出現的機率變大,反之如果最後的reward-
R(τn)
是不好的,那機器就會試著降低
p(atn|stn)
出現的機率。

要注意到一點是,我們考慮的不是單一個state-action得到的reward,而是整場遊戲所得到的reward。

Critic

Critic本身是不做事,它的角色就是給定一個actor-

π,然後衡量這個actor有多好或多不好。Critic有很多種,這次課程說明的是State value function-
Vπ(s)

  • 給定一個actor-
    π
  • 看到某一個observation(state)-
    s
    ,然後評估接下來一直到遊戲結束,我們會得到的reward有多大。
  • 這個期望值即為
    Vπ(s)
    ,為數值。

以小蜜蜂之類的遊戲來看,遊戲初始怪物多,那

Vπ(s)所得較大,而後期因為怪物殺的差不多了,因此
Vπ(s)
所得會較小。

從這邊可以發現,State value function是與actor有關,因此定義之前一定要先給定actor。

Critic

將阿光想為actor,而佐為是critic,過往阿光較弱的時候下大馬步飛那可能會有較大的機會出錯,因此是不好的,而變強之後的阿光反而應該是走大馬步飛而不是小馬步飛。

這個案例說明著不同actor即使遇到相同的state也會有不同的結果。

How to estimate
Vπ(s)

有兩種方式可以評估

Vπ(s)

  1. Monte-Carlo
    • 讓Critic觀察目前的actor-
      π
      的行為,讓actor-
      π
      與環境互動,然後統計actor-
      π
      會得到的reward
    • 舉例來說,它在看到
      sa
      之後會得到的reward-
      Ga
      ,注意到,這邊所統計的reward是一直到遊戲結束的reward總合,這樣子機器才有辦法看的長遠。
    • 因此,機器要學習的就是當看到
      sa
      的時候,其
      Vπ(s)
      要跟
      Ga
      愈接近愈好。

How to estimate
Vπ(s)

  1. Temporal-difference
    • 我們只看整個互動的其中一小段,某一個
      st
      採取什麼樣的
      at
      而得到多少的
      rt
      ..
    • 假設我們已經知道
      Vπ(st)
      ,它跟下一個時間點
      st+1
      之間差了一個
      rt
      • Vπ(st)+rt=Vπ(st+1)
    • 機器要學習的就是,
      Vπ(st)Vπ(st+1)
      要愈接近
      rt
      愈好。

這麼做的理由在於,有些情況下我們無法計算整個過程的reward,好比有一個機器人,它沒有開始與結束,就只有不斷的與環境互動,這種情況之下就無法使用Monte-Carlo來計算,只能取片段來估測而以。

MC v.s. TD

MC TD
考慮累計reward-
G
考慮單一reward-
r
variance較大 variance較小
unbiased May be biased

這非常直觀,如果每一個step的reward都加入一個noise,TD僅考慮一個step,只加一個noise,而MC是考慮整個step,加入的noise自然較大,因此會擁有較大的Variance。

MC v.s. TD

這邊案例給出兩個不同模式下的差異,假設你是一個critic,你有上表所列的8筆記錄,其中

sa僅出現1次,其reward=0。

此案例的

Vπ(sb)很直觀的就是出現8次,其reward為6,期望值為
68
,但
Vπ(sa)
就會依你所採用的方式不同而有不同的答案:

  • Monte-Carlo:這種情況下,就是統計它的期望值,僅1次且reward=0,因此
    Vπ(sa)=0
  • Temporal-difference:
    Vπ(sa)+r=Vπ(sb)
    ,因此
    Vπ(sa)=34

實際應該取決於你的真實環境,如果

sb是一個不受
sa
干擾的情況,那
sb=34
,但如果是會受干擾的話,那除非
sb
是放在互動的開頭那才會有reward。

Actor-Critic

現在我們也有Critic,利用Critic來估測Actor:

  1. 你有一個Policy-
    π
  2. 利用
    π
    與環境互動收集到很多的資料
  3. 選擇利用TD或MC的方式來學到
    Vπ(s)
  4. 依據
    Vπ(s)
    來找到新的
    π
  5. 再利用
    π
    與環境互動

Advantage Actor-Critic

θπ=θπ+ηR¯θπ

  • ηR¯θπ
    :計算
    θπ
    對expected total reward的gradient,以此更新
    θπ
    得到
    θπ

R¯θπ=1Nn=1Nt=1TnR(τn)logp(atn|stn,θπ)

  • R(τn)
    :在第
    n
    次的互動中得到多少的reward
  • 原本是讓Actor自己統計自己在整個互動中得到的reward,現在我們要改成讓Critic來幫忙算
    • 建議作法:
      rtn(Vπ(stn)Vπ(st+1n))
      • 這只是A3C論文中的其中一種作法

原本Actor是針對整個過程的reward做計算,得到

R,但如果採用A3C的話作法如下:

  • rtn(Vπ(stn)Vπ(st+1n))
    • rtn
      :在state-
      stn
      的時候採取action-
      atn
      會得到的reward-
      rtn
    • (Vπ(stn)Vπ(st+1n))
      :這個項目是根據critic估測出來的。
      • 依據目前的Policy-
        π
        ,其
        Vπ(stn)
        Vπ(st+1n))
        的accumulate value差距有多少

Advantage Actor-Critic告訴我們的就是,當Advantage function的值是正的,那就要增加採取action-

atn的機率,反之為負則減少。

Advantage Actor-Critic

實作中的小技巧:

  1. critic-
    Vπ(s)
    與actor-
    π(s)
    的參數是可以共享的
    • 如果是玩遊戲,那輸入的前幾層可能利用CNN,這部份是可以共用的
  2. 論文中提到,希望actor output的entropy是大的,以entropy來做正規化
    • 讓actor output的distribution不要過於集中,而是平滑。這麼做的好處是讓actor在與環境互動的時候能多點探索,過於集中可能就只會回應幾個固定模式。

Asynchronous

image source_Simple Reinforcement Learning with Tensorflow Part 8: Asynchronous Actor-Critic Agents (A3C)

Asynchronous的意思指,我們有一個共同參數

θ1,然後同時有很多actor(簡報上的Worker)與環境互動,每一個Worker都包含著一個actor與critic:

  1. 首先,Worker先將global parameters-
    θ1
    複製過來
  2. 利用複製過來的參數
    θ1
    與環境互動
  3. 計算更新actor與critic的參數的梯度
  4. 資訊送回global parameters更新

這個過程中其它的Worker也同時與環境做互動,其它的Worker也有它們的參數更新回傳至global parameters,因此,也許Worker回傳的global的時候它已經不是原始的

θ1而是
θ2
,雖然這麼聽起來有點怪,但實作上確實可行。這麼做的好處是可以增加訓練的速度。

Pathwise Derivative Policy Gradient

Pathwise Derivative Policy Gradient與Actor-critic的差異在於,Actor-critic只會回應好壞,但是Pathwise Derivative Policy Gradient是會有建議的。

Anthor Critic

這是一個與上面所介紹Critic不同的function,

Qπ(s,a)

  • 輸入為state與action的pair
  • 不同於
    Vπ(s)
    僅考慮state之後計算期望的reward,
    Qπ(s,a)
    考慮state與action來計算接下來可能得到的reward
  • 輸出為scalar,告讓你接下來會得到的reward有多大

如果你的action可以窮舉的話就可以讓

Qπ的輸入單純的只有state,而輸出的部份就可以帶action,每一個dimension都帶有一個action,每一個action會有多少的reward,但再次的說明,這只針對discrete action可行。

Another Way to use Critic

假設,

Qπ(s,a)的趨勢是如藍線般,很明顯的
a1
能得到的reward是低於
a2
的,這時候機器會讓
a1
出現的機率降低,而讓
a2
的機率增加。

但這會有一個問題,那就是機器對於沒有sample過的action,機器並不會知道該增加或是減少它出現的機率。圖示來看,紅線所能得到的reward是最好的,但沒有sample到的話,機器並不會知道,而且actor本身是有隨機性的,除了真的取樣取到,否則不會知道。這種問題在action是很大或者是continuous比較常見。

因此,有一種方法,基本上這個function-

Qπ(s,a)是我們所擬合出來的nn,因此我們是知道它的參數,既然知道它的參數那當然知道它的最高點在那。前提是假設這個nn的估測是準的。

當我們sample到

a的時候,只需要將它向左移得到
a
,就可以得到較大的reward,而不用苦等某年某月某一天去sample到它,這種方式稱為Q-learning。

Q-Learning

Q-learning與Actor-Critic類似:

  • 你有Policy-
    π
  • Policy-
    π
    與環境互動收集很多資料
  • 利用收集到的資料估測
    Qπ(s,a)
    • 這邊我們估測的是
      Q
      而不是
      V
      ,因為我們是借由
      Q
      來產生Policy,而不是
      V
  • 找一個比
    π
    還要好的新的
    π

註:說Policy的時候就是指Actor

Q-Learning

所謂比

π還要好的
π
的定義是:

  • 對於所有的state而言,
    Vπ(s)Vπ(s)
    • Vπ(s)
      :假設我們現在actor是
      π
      ,在state-
      s
      的時候,我們預期接下來的reward有多少
    • Vπ(s)
      :假設我們現在actor是
      π
      ,在state-
      s
      的時候,我們預期接下來的reward有多少
    • 這意昧著不管現在的state是什麼,在actor為
      π
      的情況下,它的reward都會比actor-
      π
      還要大

π(s)=argmaxQπ(s,a)

  • state為給定,為actor的input
  • 拿Q-function來看,那一個action可以給Q-function的值最大即為
    π
    的Output

兩點注意:

  1. π
    本身沒有參數,參數是在Q-function(本身為nn),要採取那一個action是由Q-function的參數決定。
  2. 不適用於action性質為continuous的情況,如果是連續函數,那代表我們需要用gradient ascent來求出最大值,每次都要計算一次,曠日費時。(後續說明)

Q-Learning

現在要證明

π(s)=argmaxQπ(s,a)可以滿足
Vπ(s)Vπ(s)
for all state-
s
這件事是對的:

  • Vπ(s)=Qπ(s,π(s))
    • Vπ(s)
      :在state-
      s
      ,用actor-
      π
      與環境互動期望得到的reward
    • Qπ(s,π(s))
      :在state-
      s
      採取action-
      π(s)
      會得到的reward,如果actor為
      π
      ,那它採取的action就是
      π(s)
  • Vπ(s)=Qπ(s,π(s))maxaQπ(s,a)
    • Q-function不變情況下,窮舉所有可能的action-
      a
      帶入
      Qπ(s,a)
      。很明顯的,
      maxQπ(s,a)
      是一個upper bound。
  • Vπ(s)=Qπ(s,π(s))maxaQπ(s,a)=Qπ(s,π(s))
    • 那一個actor會採取一個讓
      Qπ(s,a)
      的值最大,那它就是
      π
      ,即
      Qπ(s,π(s))
    • 直觀來看就是,在state-
      s
      ,用
      π(s)
      這個action來與環境互動,剩下的都用
      π
      與環境互動,其所得的reward會比沒有使用action-
      π(s)
      還要大。

將數學式展開:

  • Vπ(s)Qπ(s,π(s))
    • =Eπ[rt+1+Vπ(st+1)|st=s]
      • 假設
        s=st
        Q
        就等於
        rt+1+Vπ(st+1)
    • Eπ[rt+1+Qπ(st+1,π(st+1))|st=s]
      • 帶入上面推導出來的upper bound
    • =Eπ[rt+1+rt+2+Vπ(st+2)|st=s]
    • Eπ[rt+1+rt+2+Qπ(st+2,π(st+2))|st=s]
    • Vπ(s)

假如給我們一個Actor-

π,我們可以計算出它的Q-function,那我們就可以找到另外一個
π
,它比原來的
π
還要更好。還要更好所指的就是
Vπ(s)Vπ(s)

Estimate
Qπ(s,a)byTD

Q可以用MC,也可以用TD。

假設現在的序列為

st,at,rt,st+1

  • 我們可以計算出
    Qπ(st,at)
  • 只知道
    st+1
    ,但不知道機器會採取那一個action-
    at+1
    ,但我們可以預期機器會採取的action-
    π(st+1)
  • 兩個時步中間會有一個差距,即
    rt
  • 利用Gradient descent來求解
    • Qπ(st,at)
      rt+Qπ(st+1,π(st+1))
      愈接近愈好

實作上這兩個Q是相同的function,相同的參數,如果同時訓練會讓結果較不穩定,因此訓練的時候會將其中一個凍結,視為target,讓沒凍結的那個Q-function去擬合另一個已凍結的Q的Output,幾次迭代之後再將參數copy給另一個凍結的Q。

Double DQN

實作Q-learning的時候很容易高估Q值,假設有四個action,其

Q(st+1,a)如下圖:

因為

Q(st+1,a)是估測出來的值,因此可能存在誤差,其誤差值有大有小,有正有負,而我們每次選擇都會選擇最大的那個:

我們就發現到,當Q值有誤差的時候,我們通常都會選到高估的那個action,這時候訓練出來的結果也會是高估的。

Double DQN

論文連結_Double Q-learning
論文連結_Deep Reinforcement Learning with Double Q-learning
對於這種高估的問題有一種處理技巧-Doule DQN,這個技巧需要兩個Q-function,

Q
Q

  • 一個計算Q value(
    Q
    ),一個決定採取那一個action(
    Q
    )
    • 原始作法是用同一個Q-function來決定action,以及估測reward期望值

直觀來看,如果Q-value被高估,那代表

Q選出來的action是被估高的,但只要
Q
沒有高估
Q
選出來的action就可以了。即使
Q
高估某一個action,但只要
Q
沒有選到那個action就沒事了,兩者互相制衡。

Dueling DQN

論文連結_Dueling Network Architectures for Deep Reinforcement Learning

Dueling是決鬥的意思,與原始DQN的差異僅在Output前:

  • 最後的Output之前會分叉會兩條路,其中一條只會Output一個value-
    V(s)
    ,另一條會Output一個Vector-
    A
    ,其維度與最終輸出的action-
    a
    一致,而
    A(s,a)+V(s)=Q(s,a)
    • 論文中對於實作有另外的技巧避免
      V(s)=0
      ,這部份有興趣的話可以直接閱讀論文。
    • A(s,a)
      :在state-
      s
      採取action-
      a
      ,它比原來的Policy還要好多少。

Dueling DQN實作上比DQN的效果還要好,其中一點有趣的是它的可視化,它可以計算如何改變輸入(image)對

V(s)以及
A(s,a)
的影響最大,這樣就可以看的出什麼樣的事情是與action有關,而什麼是無關的。

Dueling DQN - Visualization

論文影片連結

影片可以看的到,左邊會一直有紅色的閃光出來,這意味著這邊的pixel改變的時候對

V(s)=0的影響最大。而右邊是顯示對
A(s,a)
(Advantage-function)影響最大的改變。

可以看的到,Advantage-function在車子出現在眼前的時候才會紅,因為車子靠近之後採取不同的action才會對結果有影響。但左邊的Value是每通過一輛車就會紅,它跟有沒有車有關,只要地平線的那端出現車子就會紅。

另一段打磚塊遊戲也是一樣的道理,左邊Value幾乎都有值,而接近下面的時候Advantage-function才會紅。

Pathwise Derivative Policy Gradient

稍早的Q-learning中提到,只要有

Q,我們就找的到
π
,不需要任何的actor。但如果現在我們有一個actor,而它的output就是我們要採取的action-
a
,那是什麼情況?

假設我們有一個actor-

π,input-
s
,output-
a
,然後要更新
π
π
,而且我們希望
Qπ(s,a)
的值愈大愈好。

實務上,如下圖所示,我們可以將整個串接起來視為一個較大的神經網路即可:

當我們在更新actor的時候,就將

Qπ的參數固定住,再用Gradient Ascent來更新actor的參數:

  • θπθπ+ηθπQπ(s,a)
    • 計算
      θπ
      對Q-function的梯度再加上
      θπ
      得到
      θπ

整個架構看起來跟GAN非常類似,但這種作法稱為Pathwise Derivative Policy Gradient

Pathwise Derivative Policy Gradient

與Q-Learning一樣有三步驟,在估測Q-function的時候與一般的DQN是一樣的,不同的地方是在估測

π的部份。原始DQN中只需要有Q-function就夠,但在Pathwise Derivative Policy Gradient中是需要一個actor(nn)來得到action,然後透過調整actor的參數讓Q-function的Output愈大愈好。

這種情況下即使action是連續的也沒有關係,因為在testing的時候我們並不需要解一個

argmax的問題,這部份是在training的時候處理掉了,testing的時候只需要input state就可以。

有一個通用的小技巧,就是Replay Buffer。意思是將過去與環境互動的所有資訊通通存下來放到一個Buffer內,訓練Q-function過程中再從這個Buffer中取值出來,並不單純只取

π與環境互動的經驗,還會包含過去其它的actor與環境互動的經驗也都在裡面,這樣訓練過程會比較穩定。

另外一個小技巧,就是對actor的output加上noise,這可以幫助actor探索不同的環境。

DDPG Alogrithm

DDPG=Deep Deterministic Policy Gradient

DDPG也是我們稍早所提到的Pathwise Derivative Policy Gradient的其中一種方式:

  • 有一個actor與critic,其初始化參數分別為critic-
    θQ
    與actor-
    θπ
  • 有一個target critic-
    θQ
    與有一個target actor-
    θπ
    • 這是估測Q-function的時候用的
  • 初始化一個replay buffer R
  • 每次的迭代
    • 用actor-
      π
      與環境互動,input-s,output-a,即
      π(s)
      ,再針對Output加上noise,即
      π(s)
      + noise來幫助actor探索環境,並收集一堆訓練資料,將它們存放到Reply buffer-R。
      • 訓練資料結構為
        {st,at,rt,st+1}
    • 從Reply buffer-R中sample出N筆資料
    • 利用取出的N筆資料訓練critic-Q
      • 調整Q的參數讓它與目標函數
        L=n(y^nQ(sn,an))2
        愈接近愈好
        • target-
          y^n=rn+Q(sn+1,π(sn+1))
          • 以target actor-
            θπ
            根據
            sn+1
            決定要採取什麼樣的action,得到
            Q
            之後加上
            rn
    • 更新actor-
      π
      的參數,讓Q-function的值增加
    • 更新target network
      • θπmθπ+(1m)θπ
      • θQmθQ+(1m)θQ
      • 理論上可以直接讓
        θπ=θπ,θQ=θQ
        ,但實務上我們會讓target networks乘上一個weight再與critic、actor做計算。
        • 這麼做的好處是,target networks的變化會比較慢,訓練上也會比較穩定。