日B视频因产,亚洲精品第三页

視頻學習：
莫凡視頻教程
 李宏毅2018強化學習視頻教程
 馬爾科夫決策過程
 https://github.com/wangshusen/DeepLearning
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
An Introduction to Deep Reinforcement Learning

術(shù)語

注：所有小寫字母表示已觀測到的值，大寫字母表示未觀測到的（隨機變量）

state 當前的場景、狀態(tài)
action 動作
agent 做動作的主體、可翻譯成智能體
policy $\pi$ 狀態(tài)s下，各種動作的概率密度函數(shù)
reward 獎勵 $R_i$ 和 $S_i, A_i$ 有關(guān)
狀態(tài)轉(zhuǎn)移 state i → state i+1通常是隨機的

條件概率密度函數(shù)

強化學習的隨機性來源主要有兩個

action是隨機的 $P[A=a|S=s] = \pi(a|s)$
狀態(tài)轉(zhuǎn)移（新狀態(tài)）是隨機的 $P[S'=s'|S=s, A=a]=p(s'|s,a)$

強化學習狀態(tài)軌跡：
$[(state, action, reward)]$ $(s_1,a_1,r_1), ..., (s_T,a_T,r_T)$

Return 回報，未來的累計獎勵
$U_t = R_t+R_{t+1}+R_{t+2} +...$
Discounted Return折扣回報， $\gamma$ 是折扣率
$U_t = R_t+ \gamma R_{t+1}+ \gamma^2 R_{t+2}+...$
顯然在給定的 $s_t$ 下 $U_t$ 依賴于 $A_t,A_{t+1},...S_{t+1},S_{t+2},...$
Action-Value Function 動作價值函數(shù) $Q(s,a)$

U_t的條件期望

含義：如果用policy函數(shù)

\pi

，在s_t狀態(tài)下做動作

a_t

的好壞，是否明智

求期望就是對

A_{t+1},A_{t+2},...S_{t+1},S_{t+2},...

求積分

最優(yōu)動作價值函數(shù) $Q^{*}(s_t,a_t)=\max_{\pi}Q_{\pi}(s_t,a_t)$
含義：在s_t狀態(tài)下做動作 $a_t$ 好不好，給每個action打分。就像一個先知，能告訴你每個action的平均回報

State-Value Function狀態(tài)價值函數(shù) $V(s)$
$V_{\pi}(s_t)=\mathbb{E}_{A}[Q_{\pi}(s_t,A)]$
對A求積分，含義：當前局勢好不好。 $\pi$ 越好，勝算越大。

強化學習的目標是學習 $\pi$ 或者 $Q^*$

強化學習的幾種思路

Value-based learning
用神經(jīng)網(wǎng)絡（DQN）近似 $Q^*$ ，參數(shù)學習利用了temporal different (TD) 算法
Policy-based learning
用神經(jīng)網(wǎng)絡（DQN）近似 $\pi$ ，參數(shù)學習利用了policy gradient梯度上升
Actor-critic method
以上兩種的結(jié)合

Value-based learning

如果我們知道 $Q^*(s,a)$ ，就能當前最好的action
$a^* = \argmax_{a}Q^*(s,a)$

本質(zhì)：用神經(jīng)網(wǎng)絡 $Q(s,a;w)$ 近似 $Q^*(s,a)$

神經(jīng)網(wǎng)絡的輸入是s，輸出是很多數(shù)值，表示對所有可能動作的打分，根據(jù)觀測到的獎勵來更新參數(shù)

TD算法
如何訓練DQN？實際場景中，完成任務需要很多步的action，如果全部action都結(jié)束了，再來更新模型，效果一定很差，那么如何走一步更新一下呢？
TD target : 實際已經(jīng)得到的獎勵和模型預測未來的獎勵之和。
越接近結(jié)束，TD target越準
用TD target(y)和全部都是模型預測的獎勵Q(w)計算loss
$L=\frac{1}{2}(Q(w)-y)^2$
其中 $Q(w)-y$ 被稱為TD Error，換個角度，去掉相同的部分，其實就是實際獎勵和預測獎勵的誤差。
最后用梯度下降更新模型參數(shù)，不需要打完游戲再來更新參數(shù)。

$Q(s_t,a_t;w) \approx r_t+\gamma \cdot Q(s_{t+1},a_{t+1};w)$
$t$ 時刻未來獎勵總和的期望約等于 $t$ 時刻的獎勵加上 $t+1$ 時刻未來獎勵總和的期望

Policy-based learning

本質(zhì)：用神經(jīng)網(wǎng)絡 $\pi(a|s;\theta)$ 近似策略函數(shù) $\pi(a|s)$

比如超級瑪麗，輸入是當前狀態(tài)，輸出是每個操作的概率分布

$V_{\pi}(s_t)=\mathbb{E}_{A}[Q_{\pi}(s_t,A)]=\sum_{a}\pi(a|s_t)\cdot Q_{\pi}(s_t,a)$

狀態(tài)價值函數(shù) $V(s_t;\theta) = \sum_{a}\pi(a|s_t;\theta)\cdot Q_{\pi}(s_t,a)$

給定狀態(tài) $s_t$ ，策略網(wǎng)絡越好， $V$ 的值越大
目標函數(shù) $J(\theta)=\mathbb{E}_S[V(S;\theta)]$ 越大越好，利用policy gradient ascent更新參數(shù)

Policy Gradient Ascent

觀測到狀態(tài)s，計算策略梯度 $\frac{\partial V(s;\theta))}{\partial \theta}$ ，更新模型參數(shù)
$\theta \leftarrow \theta+\beta \cdot \frac{\partial V(s;\theta))}{\partial \theta}$

如何求策略梯度？

第三步是用蒙特卡洛（抽樣）方法對策略梯度做近似。

整個算法過程：

Actor-Critic Methods

$V_{\pi}(s)=\sum_{a}\pi(a|s)\cdot Q_{\pi}(s,a)\approx \sum_{a}\pi(a|s;\theta)\cdot q_{\pi}(s,a;w)$
Actor是策略網(wǎng)絡，可以看成是運動員。用神經(jīng)網(wǎng)絡 $\pi(a|s;\theta)$ 近似策略函數(shù) $\pi(a|s)$
Critic是價值網(wǎng)絡，可以看成裁判員，給運動員打分。用神經(jīng)網(wǎng)絡 $q(s,a;w)$ 近似價值函數(shù) $Q_{\pi}(s,a)$

策略網(wǎng)絡

價值網(wǎng)絡

訓練過程

觀測當前狀態(tài) $s_t$
根據(jù)策略網(wǎng)絡得到當前action $a_t$
實施 $a_t$ ，然后觀察 $s_{t+1}$ 和 $r_{t}$
用TD算法更新價值網(wǎng)絡參數(shù) $w$
用策略梯度更新策略網(wǎng)絡參數(shù) $\theta$

總結(jié)：(重點，多看幾遍理解一下)

AlphaGo

主要設(shè)計思路

棋譜大小19x19，一共361個點，所以action的數(shù)量一共是361個?？梢杂?code>19x19x2的矩陣代表黑白棋子的狀態(tài)state

策略網(wǎng)絡

狀態(tài)矩陣：1表示有棋子，0表示沒有，黑白棋子分別記錄最近8個狀態(tài)，所以一共是16，還有一個表示當前是黑棋下還是白棋下（全0或者全1）

策略網(wǎng)絡

訓練三步走

Behavior cloning 通過對人類棋譜有監(jiān)督的學習（16w局）是一個分類任務，初步學習策略網(wǎng)絡（這一步可有可無）
- 網(wǎng)絡只會對見過的state表現(xiàn)比較好，所以想要戰(zhàn)勝它，只需要做一些出乎尋常的操作就行了

強化學習進一步學習這個網(wǎng)絡，自我博弈（利用策略梯度）
- 一個模型參數(shù)需要更新的策略網(wǎng)絡作為player，上一個策略網(wǎng)絡作為opponent
- 進行一局比賽得到 $s_1,a_1,s_2,a_2, ..., s_T, a_T$
- 獎勵 $u_1=u_2=...=u_T$ , 贏了全為1，否則全為-1
- 計算策略梯度 $g_\theta = \sum_{t=1}^{T} \frac{\partial \log \pi (a_t|s_t, \theta)}{\partial \theta } \cdot u_t$
- 更新策略網(wǎng)絡 $\theta \leftarrow \theta+\beta \cdot g_\theta$
利用策略網(wǎng)絡訓練一個價值網(wǎng)絡
- 用神經(jīng)網(wǎng)絡 $v(s;w)$ 近似 $V_\pi(s)$
  
  兩個網(wǎng)絡共享卷積層
- 進行一場比賽
- 獎勵 $u_1=u_2=...=u_T$ , 贏了全為1，否則全為-1
- 計算Loss: $L = \sum_{t=1}^{T} \frac{1}{2} [v(s_t;w)-u_t]^2$
- 更新模型參數(shù)

執(zhí)行的時候用的是Monto Carlo Tree Search (MCTS),利用策略網(wǎng)絡和價值網(wǎng)絡指導搜索（人類高手在下棋的時候會往前看好幾步）
- 搜索的主要思想
  1. 根據(jù)策略網(wǎng)絡，在分數(shù)高的action中隨機選擇一個
  2. 自我博弈，根據(jù)勝負和價值函數(shù)給該動作打分
  3. 選擇打分最高的那個action

1.Selection	2.Expansion	3.Evaluation	4.Backup
$score(a)=Q(a) + \eta \cdot \frac {\pi (a\|s_t; \theta)}{1+N(a)}$		$V(s_{t+1}) = \frac{1}{2}(v(s_{t+1};w)+r_(T))$	$Q(a_t)=mean(Records)$ $a_t=\argmax_{a}N(a)$
其中 $Q(a)$ 是動作價值，初始值都為0，N(a)表示動作 $a$ 已經(jīng)被選擇的次數(shù)	$s_{t+1}$ 是根據(jù)策略函數(shù)隨機采樣模擬動作之后的狀態(tài) 后面就是自我博弈，根據(jù)最終的勝負計算獎勵 $r_{T}$	綜合考慮獎勵和價值函數(shù)，對狀態(tài) $s_{t+1}$ 打分Record，分數(shù)越高勝算越大	計算動作的Q值，循環(huán)很多次之后選擇被選中次數(shù)最多的動作

蒙特卡洛

一種數(shù)值算法，靠隨機樣本對目標做近似
待補充

TD Learning 之 Sarsa算法

用來學習動作價值函數(shù) $Q_\pi (s,a)$
TD target: $y_t=r_t+\gamma \cdot Q_\pi (s_{t+1},a_{t+1})$
Sarsa方法來更新價值網(wǎng)絡（critic）

TD Leaning 之 Q-Learning

用來學習 $Q^*(s,a)$
TD target: $y_t=r_t+\gamma \max_{a} Q^*(s_{t+1},a)$

Multi-Step TD Target

多個action之后再更新參數(shù)，相當于有累計多次獎勵
m-step TD target for Sarsa
$y_t=\sum_{i=0}^{m-1} \gamma ^i \cdot r_{t+i}+\gamma ^m \cdot Q_\pi (s_{t+m},a_{t+m})$

Experience Replay

經(jīng)驗回放

定義：

A transition： $(s_t,a_t,r_t,s_{t+1}), \delta_t$
Experience: 所有的transition

之前訓練方式的缺點：

每個 $r_t$ 只是用了一次，相當于對經(jīng)驗的浪費
$s_t$ 和 $s_{t+1}$ 之間的相關(guān)性太強，理論上打亂順序更好

replay buffer: 最近n個transition，訓練的時候每個batch從replay buffer中隨機選k個transition 做隨機梯度下降

一種對經(jīng)驗回放的改進Prioritized Experience Replay:用非均勻抽樣代替均勻抽樣

用TD error $\delta_t$ 判斷transition的重要性
用不同的學習率 $(np_t)^{-\beta}$ 抵消不同樣本抽樣頻率的不用，其中 $p_t$ 是抽樣概率， $\beta \in [0,1]$ ，實戰(zhàn)中先比較小，然后慢慢變大。

Target Network 和 Double DQN

TD target: $y_t=r_t+\gamma \cdot \max_aQ(s_{t+1},a;w)$
TD error : $\delta_t = Q(s_t,a_t;w)-y_t$
SGD: $w \leftarrow w - \alpha \cdot \delta_t \cdot \frac{\partial Q(s_t,a_t;w)}{\partial w} = w - \alpha \cdot ( Q(s_t,a_t;w) - y_t) \cdot \frac{\partial Q(s_t,a_t;w)}{\partial w}$
我們發(fā)現(xiàn)在t時刻更新參數(shù)的時候，計算梯度的時候用到了 $y_t$ ，而 $y_t$ 又包含了對t+1時刻的預測，就出現(xiàn)了bootstapping的問題，自己把自己舉起來了

DQN的高估問題

原因一：計算TD target的時候會最大化價值函數(shù)
原因二：上面提到的bootstrapping

結(jié)論：DQN對價值的高估是非均勻的，非常有害

解決方案：

用target network來計算TD targets
DQN： $Q(s,a;w)$ ，用來控制agent
target network: $Q(s,a,w^-)$ 用來計算TD targets $y_t=r_t+\gamma \cdot \max_aQ(s_{t+1},a;w^-)$
結(jié)構(gòu)一樣，參數(shù)不一樣
用double DQN 緩解高估的問題

selection: $a^* = \argmax_{a}Q^*(s_{t+1},a;w)$
evaluation: $y_t=r_t+\gamma \cdot Q(s_{t+1},a^*;w^-)$

compute TD target	selection	evaluation
naive	DQN	DQN
using target network	Target Network	Target Network
Double DQN	DQN	Target Network

Dueling Network

Optimal advantage function
$A^*(s,a) = Q^*(s,a) - V^*(s)$
以最優(yōu)狀態(tài)函數(shù)為基準，最優(yōu)動作價值函數(shù)的優(yōu)勢
Dueling Network
$Q^*(s,a) = V^*(s) + A^*(s,a) - \max_{a}A^*(s,a)$

Dueling Network

實際實驗中發(fā)現(xiàn)把max換成mean效果更好
$Q^*(s,a;w) = V(s;w^V) + A(s,a;w^A) - mean_{a}A(s,a;w^A)$

數(shù)學原理待補充

Multi-Agent 強化學習

四種設(shè)定

合作關(guān)系 共同的目標，獎勵一致，如多個工業(yè)機器人協(xié)同裝配汽車
競爭關(guān)系 一方的收益是另外一方的損失，如零和博弈，拳擊比賽
合作競爭混合 足球比賽，星際爭霸
利己主義 股票自動交易系統(tǒng)，無人車

假設(shè)有n個agent， $S$ 是狀態(tài)， $A^i$ 第i個agent的動作，
那么狀態(tài)轉(zhuǎn)移方程為（條件概率密度函數(shù)）： $p(s'|s,a^1,...,a^n)=\mathbb{P}(S'=s'|S=s,A^1=a1,...,A^n=a^n)$

假設(shè) $R^i$ 表示第i個agent的獎勵（Reward），那么
合作關(guān)系 $R^1=R^2=···=R^n$
競爭關(guān)系 $R^1 \propto -R_2$

假設(shè) $R_{t}^{i}$ 表示第i個agent在t時刻的獎勵（reward）
那么回報（return） $U_t^i = R_{t}^i + R_{t+1}^i + R_{t+2}^i + ···$
折扣回報 $U_t^i = R_{t}^i + \gamma R_{t+1}^i + \gamma ^2 R_{t+2}^i + ···$

每個agent有自己的策略網(wǎng)絡 $\pi(a^i|s;\theta^i)$ ，不同agent的參數(shù) $\theta^i$ 可以相同（比如自動駕駛）也可以不相同（比如機器人足球隊）

狀態(tài)價值函數(shù) $V^i(s_t;\theta^1,···,\theta^n)=\mathbb{E}[U_t^i|S_t=s_t]$ ，依賴于所有策略網(wǎng)絡

部分可觀測

multi-agent通常假設(shè)agent只能看到狀態(tài) $s$ 的一部分 $o^i$ ， $o^i \neq s$

納什均衡 `Nash Equilibrium`

納什均衡用來判斷多個agent的策略網(wǎng)絡收斂的標準。
當其他所有agent的策略保持不變，單獨優(yōu)化某一個agent的策略不會得到更好的回報

Multi-Agent 學習的難點

如果直接把single-agent學習的方法直接用到multi-agent上的話，收斂會很困難
原因是一個agent的策略更新會導致其他所有agent策略網(wǎng)絡的目標函數(shù) $J$ 發(fā)生變化
所以在訓練一個agent策略網(wǎng)絡的時候最好能拿到其他agent的信息 (通信)

中心化`centralized`與去中心化`decentralized`通信方式

Fully decentralized
agent之間完全沒用通信，其實就是上文說的
每個agent都是一個actor-critic，一個策略網(wǎng)絡和一個價值網(wǎng)絡
Fully centralized
所有agent把所有信息（observation, actions, rewards）發(fā)送給中央控制器central controller，由中央控制器來決定每個agent的action
agent沒有策略網(wǎng)絡和價值網(wǎng)絡，中央控制器學習n個策略網(wǎng)絡、n個價值網(wǎng)絡
主要的問題是執(zhí)行速度慢，不能實時做決策

Centralized training and decentralized execution
- 中央控制器幫助訓練策略網(wǎng)絡，運行的時候直接由agent決定action
- 每個agent有自己的策略網(wǎng)絡（actor） $\pi(a^i|o^i;\theta^i)$ ，中央控制器有n個價值網(wǎng)絡（critic） $q(\textbf {o} | \textbf {a} ;w^i)$