[學習筆記] CS229 Part XIII Reinforcement Learning and Control + AlphaGo

04-29

在機器人領域，很難使用supervised learning因為沒有一個合理的結果需要預測，而往往是基於其行為對其評價，然後根據不同行為導致的不同結果來調整之後的行為。這大致就是Reinforcement learning。其使用reward function來評價learning agent的action是好是壞。因此將問題轉化為，訓練得出最優action策略。RL已經成功應用於自動直升機飛行，機器腿運動，手機網路routing，營銷策略選擇，工廠控制和網頁indexing以及AlphaGo。模型的基礎知識是Markov decision processes(MDP)

感覺只要是連鎖的state都叫Markov，以往學到的與Markov有關的都涉及到probability conditional on certain previous states, if not all of them。

Finite-state MDP（以直升機為例）

主要參數： $(S,A,{P_{sa}},gamma,R)$ ，S是set of states（直升機所有可能位置的集合），A是actions（可運行方向的集合），Psa是state transition probabilities，提供了給定當前state和action後心得state的概率分布（也就是take action後到達的新state是不確定的）。 $gamma$ 是discount factor，R是關於S和A到實數的mapping，reward function，不過reward通常是根據所在的state定的，所以一般寫作S的函數。

Total payoff of a sequence of action = $R(s_0)+gamma R(s_1)+gamma^2R(s_2)+cdot cdot cdot$ ，model的目標是最大化E[payoff]。 $gamma$ 一般小於1，所以要最大化E，需要在前面的步驟獲得好的reward。策略（policy） $pi$ 是S到A的映射，就是如果在某state就採取指定action。因此，一個policy和starting state可以決定total reward - value function。

$egin{align*}& V^pi(s)=E[R(s_0)+gamma R(s_1)+gamma^2 R(s_2)+cdotcdotcdot|s_0=s,pi] \& =R(s)+gamma E[R(s_1)+gamma R(s_2)+gamma^2 R(s_3)+cdotcdotcdot ] \& =R(s)+gamma Eleft {R(s_1)+E[gamma R(s_2)+gamma^2 R(s_3)+cdotcdotcdot|s_1] ight} \& =R(s)+gamma E[V(s_1)] \& =R(s)+gamma sum_{sin S}P_{sa(s)}(s)V^pi(s)end{align*}$

假設，每一個state之後take的action根據相同的policy，那麼對於所有initial state，optimal policy都是同一個。

Algo:

Value Iteration: used more in practice,

for each state s, initialize V(s):=0
Repeat until converge{ For every state, update $V(s)=R(s)+max_{ain A}gammasum_{s}P_{sa}(s)V(s)$ }

Policy Iteration

initialize $pi$ randomly.
repeat until converge{

let $V=V^pi$
for each state s, let $pi(s)=argmax_{ain A}sum_{s}P_{sa}(s)V(s)$ }

Learning a model for MDP

一般S，A和 $gamma$ 是知道的，但 $P_{sa}$ 和R需要用model來predict。 $P_sa{s}=frac{#times we took action a in state s and got to s}{#times we took action a in state s}$

Initialize $pi$ randomly
Repeat {

Execute $pi$ in the MDP for some number of trials
using the accumulated experience in the MDP, update out estimate for $P_{sa}$ ,and R
apply value iteration with the estimated state transition probabilities and rewards to get a new estimated value function V
update $pi$ to be the greedy policy with respect to V

}

Continuous state MDP

例如自動行駛的車就是infinite state MDP。

Discretization：用grid表示所有state。缺點是，grid間隔要很小才能有好的model效果，以及多維空間的話，grid的維數也很大。通常對1d或2d問題比較有效
Value function approximation：execute m trials, each for T timesteps. 然後得到m個state sequence，用model來預測st，at與st+1的關係。

可以是線性模型比如 $s_{t+1}=As_t+Ba_t$ ，或者stochastic model比如 $s_{t+1}=As_t+Ba_t+epsilon_t$
fitted value iteration: to approximate the value function as a function of the state: $V(s)= heta^Tphi(s)$ ， $phi$ is a known (linear or nonlinear )feature mapping of state, and $heta$ is what we need to model by first calculate sample approximation of the value function $V(s)=R(s)+gamma max_aint_{s}P_{sa}(s)V(s)ds$

randomly sample m states $s^{(1)},s^{(2)},...,s^{(m)}in S$
Initialize $heta=0$
Repeat {

for i = 1,...,m{

for each action $ain A$ {

sample $s_1,...s_ksim P_{s^{(i)}a}$ (using a model of the MDP)

Set $q(a)=frac{1}{k}sum_{j=1}^kR(s^{(i)})+gamma V(s_j)$ // if the model of MDP is deterministic, then k = 1, because from st and at there is only one specific s(t+1)

} Set $y^{(i)}=max_aq(a)$ //so that $y^{(i)}$ is an estimate of $R(s)+gamma max_aint_{s}P_{sa}(s)V(s)ds$

} set $heta = arg min_ heta frac{1}{2}sum_{i=1}^{m}( heta^Tphi(s^{(i)}-y^{(i)})^2$

---------------------------------------------------------------------------------------------------------------------------

看完了筆記，立刻就想到了十分火熱的alphago，因為自己曾經在初中學過兩年圍棋，所以能裝的逼一定要裝一下，特此學習一下介紹AlphaGo的paper：Mastering the game of Go with deep neural networks and tree search

---------------------------------------------------------------------------------------------------------------------------

縮寫：SL - Supervised Learning，RL - Reinforcement Learning

摘要

主要運用的技術：運用value network來評估棋盤位置（圍棋術語：金角銀邊草肚皮），以及policy networks來選擇走哪一步。模型訓練結合了真人實戰的監督學習以及self-play的reinforcement learning。在self-play中使用最新的Monte Carlo tree search

Intro

遊戲的寬度b代表可以走哪，深度d代表可以走的步數。圍棋的b大約是250，d大約是150，所以exhaustive search很難。可以通過評估不同棋盤位置的價值，比如邊緣的兩排至少在布局和中盤階段價值很小，以及別人的"眼"（除非能提子）。來減少search space。以往的圍棋軟體是基於Monte Carlo tree search(MCTS)，預測search tree中每一個狀態的價值，通過不斷地simulate，tree不斷變大，通過選取最大的子分支，可以得到最優value function。但是以往的policy和value function模型都是簡單的線性模型。我們效仿了時下比較時髦的deep convolutional neural networks。用卷積層將輸入的19*19 image（棋盤有19*19個點可以落子）提取feature map從而減小search tree的b和d。第一步是通過真人的實際走步進行監督學習policy network $p_sigma$ 。同時，訓練了另一個policy $p_pi$ 可以在Monte Carlo的rollout中快速sample actions。然後，訓練一個reinforcement learning(RL)的policy network $p_ ho$ ，通過最優化self play的結果來優化監督學習的policy network。最後，訓練一個value network $v_ heta$ 來預測RL policy在self play中的勝利方。AlphaGo combine policy and value networks with MCTS。AlphaGo貢獻：第一次構造出有效的move selection和position evaluation function。模型使用DNN並且運用監督學習和reinforcement learning進行訓練。還首次結合了NNevaluation和MC rollout。

a. 用真實對局的數據來訓練一個可以快速sample action的rollout policy $p_pi$ ，以及一個SL policy network $p_sigma$ ，訓練的目標是基於已有的落子預測下一個。之後，將訓練得出的SL policy network $p_sigma$ 作為RL policy network $p_ ho$ 的初始值，然後用梯度訓練來improve $p_ ho$ 以最大化結果（相對之前的policy network取得更多勝利）。接著，用 $p_ ho$ 進行self-play獲得新的數據集。最後，基於新的數據集通過回歸來訓練一個value network $v_ heta$ 來預測self play的expected勝利方。

b. 圖像表述模型想要達到的效果，input image（當前state）通過許多層卷積，weight為 $sigma$ ( $p_sigma$ )或 $ho$ （ $p_ ho$ ），計算當前state下，棋盤上所有legal move的條件概率， $p_sigma(a|s) or p_ ho(a|s)$ 。value network類似地，也是用很多參數為 $heta$ 的卷積層計算當前state下的預期outcome（勝利方）

Monte Carlo tree search(MCTS)一種在遊戲中經常使用的decision process。就是通過隨機sample之後的moves然後看哪個sample的結果最好就選這個sample作為下一步。
Rollout: 最早源自於對backgammon雙陸棋的分析。A rollout consists of playing the same position many times (with different dice rolls) and recording the results. The balance of wins and losses is used to evaluate the equity of the position.就是隨機重複

簡述流程：具體方法介紹後文有

一. 監督學習Policy network $p_sigma$

第一步監督學習這一part，是根據很多前人對預測高手落子的監督學習研究。監督學習PN $p_sigma(a|s)$ 在weight為 $sigma$ 的卷積層和非線性Rectifier activation function之間不斷轉換，最後用一個softmax層輸出所有legal action $a$ 的概率分布。input s是對棋盤狀態的一個簡單描述（包括棋子顏色、單位平面、零平面、回合數、臨近空白位、可提子數、被提子數等）

weight的訓練是使用隨機採樣的state-action組，用隨機梯度上升法最大化在state s真人會選擇action a的likelihood $p_sigma(a|s)$ 。 $、sigma proptofrac{partial log p_sigma(a|s)}{partial sigma}$

我們的SL policy network有13個層級，訓練數據來自KGS GO Server，有3000萬個位置數據。預測的步數準確率已經有57%。

二. Reinforcement Learning of policy networks

一開始的RL policy network和原SL得出的一樣（結構和參數），然後通過與random sample的過往iteration的 policy network下很多局棋獲得新數據。用數據來反向計算outcome函數 $z_t$ (當前state視角下的遊戲最終reward，很像martingale)：贏了為+1，輸了為-1。然後要最大化outcome就是要最大化函數： $、 ho propto frac{partial log p_ ho(a|s)}{partial ho}z_t$ 。最大化的方法是隨機梯度上升。

Performance：與SL policy network，能贏80%。與當前最強的Go軟體Pachi下，贏了85%。Pachi的基礎是Monte Carlo search，棋力在KGS里能排到業餘二段，每一步需要做10萬次模擬。之前最厲害的只應用監督學習的卷積網路只能贏11%。

三. RL of value networks

目標是：value function用於預測在某state s，兩方都用policy p，expected最終outcome $v^p(s)=E[z_t|s_t=s,a_{t...T}sim p]$ 。理想狀態下，我們是想要預測採用最優策略時的value function $v^*(s)$ ;但在實際訓練中，我們其實是在預測我們自己RL policy network訓練的最強policy network $p_ ho$ 產生的value function $v^{p_ ho}$ ，而預測的方法就是用一個含參數 $heta$ 的模型 $v_ heta(s)$ 通過回歸得出 $heta$ 使得 $v_ heta(s)approx v^{p_ ho}(s)approx v^*(s)$ 。目標error function是MSE： $frac{1}{2}left(z-v_ heta(s) ight)^2$ ，z是用RL policy network走出來的最終outcome，用SGD最小化該方程， $、 heta propto frac{partial v_ heta(s)}{partial heta}(z-v_ heta(s))$

四. Search with policy and value networks (MCTS)

AlphaGo在MCTS演算法中結合了policy和value network，通過前向模擬選擇下一個action。通過simulation遍歷search tree。每一個edge（s，a）儲存三個value作決策：action value Q（s,a), visit count N(s,a), prior probability P(s,a)。在每一次模擬的每個時刻t，所做的action $a_t=argmax_a(Q(s_t,a)+u(s_t,a))$ ，是為了最大化action value加上一個bonus $u(s,a)propto frac{P(s,a)}{1+N(s,a)}$ ，bonus隨著visit count的增多而減少，所以鼓勵多explore新的position。在step L時，simulation到達一個leaf node（當然可以expand），在這個position $s_L$ 使用SL policy network $p_sigma$ 計算 $p_sigma(a|s)$ 作為P（s,a)。而 $s_L$ 的value function是fast rollout policy $p_pi$ 的結果 $z_L$ 和我們模型的value function $v_ heta$ 的結合： $V(s_L)=(1-lambda)v_ heta(s_L)+lambda z_L$ 。完成n次simulation後，所有遍歷的edges上存儲的action value 和visit count要進行更新。

$N(s,a)=sum_{i=1}^n1(s,a,i)$

$Q(s,a)=frac{1}{N(s,a)}sum_{i=1}^n1(s,a,i)V(s_L^i)$

$1(s,a,i)$ 表示第i次simu有經過這個edge（s，a）。注意這裡計算prior probability用的是SL的network而不是RL的，是因為，SL表現更好。因為，人類棋手在下棋時一般是選擇一組最優落子，而RL則是尋找一個最佳落子。但是RL的value function表現更好，因為更像人類思維過程。

另外，並行運算加強了效率，最終土豪版AlphaGo使用40個線程，1202個CPU，176個GPU。

與深藍的比較：這個比較是不可避免的，AlphaGo在實際下棋中評估的盤面比深藍少數千倍。另外，深藍的評估函數是專門為國際象棋設計調整的，而AlphaGo的訓練是在下棋過程中使用general-purpose監督學習和reinforcement learning方法，更具普遍性。

Method！！

Problem setting.棋類遊戲可以歸類為Alternating Markov games，基於MDP，所要解決的問題就是最大化value function

前人研究：最優value function可以用minimax search計算，不過對於圍棋還是很難算。RL可以從self-play中直接近似value function。過去的研究都是用線性方程with weight heta用temporal-difference learning或線性回歸來訓練。除了minimax，還有一個方法就是MCTS search。通過simulation approximate value function。search tree會不斷加深，模擬的policy也會通過不斷精確的統計量而優化，具體的search algo可以使用UCT。AlphaGo使用的是truncated的MCTS，在遊戲結束前就停止rollout，然後用value function來計算terminal reward。AlphaGo的position評估很像Temporal difference演算法；而且，與以往研究不同的是AG使用了一種慢一些，但很強大的representation of policy and value network - deep NN。傳統方法用rollout policy 進行position evaluationg經常出現不打得偏差，AlphaGo用簡單的rollout，而position eva就交給value network解決。

Search algo：（感覺有點複雜，很難再大腦中構造出具體的選擇model，只有一個比較general的想法，需要先弄懂MCTS的基本原理，以及像UCT這樣的search algo）採用asynchronous policy and value MCTS algo (APV-MCTS)。Tree building：每一個node s包含edges (s,a)就是桿兒，用於連接下一個node。edge存儲六個統計量： ${P(s,a),N_v(s,a),N_r(s,a),W_v(s,a),W_r(s,a),Q(s,a)}$ 。角標v代表value function，r代表rollout，W是Monte Carlo估計的total action value，通過匯總N個leaf evaluations和rollout reward。Q是兩者結合後的平均action value for the edge。Search分為四個步驟：

假設：tree的depth為L，即 $s_L$ 為leaf。

Selection：其實可以說是最後一步，就是在任意timestep t<L，選擇action的標準是最大化action value + bonus的action： $a_t=argmax_a(Q(s_t,a)+u(s_t,a))$ ，search的方法是PUCT的一個變體。其中 $u(s_t,a)$ 是bonus $=c_{puct}P(s,a)frac{sqrt{sum_bN_r(s,b)}}{1+N_r(s,a)}$ ，其中c是一個常數用來決定exploration的程度。這種search control strategy一開始受bonus影響比較大，偏向於選擇大概率（P）和低訪問數；之後逐漸偏向於選擇高action value（Q）
Evaluation：在leaf處，用value network計算 $v_ heta(s_L)$ ，從leaf開始就使用rollout policy來simu action直到game over，此時可以得到 $z_t=pm r(s_T)$
Backup：就是update每個node的Q，是value function和rollout policy得到的action value的加權平均，權數是 $lambda$ 。在simu結束的時候，rollout部分的N和W的update需要添加一個量稱為virtual loss，用來提高可使用的threads數。在前述過程中，還有另外一個線程，就是在simu到達leaf的時候，要update value netword的action value。
Expansion：當對某一個edge（s，a）的visit超過一個threshold，就會expand

最後AlphaGo選擇的action是simu中擁有最多visit的action，而不是最大action value的，因為後者容易受極端值影響。

Rollout Policy $p_pi(a|s)$ ：是線性softmax，包含的feature有1）『response』：前一個落子附近的pattern，以及2）『non-response』：備選action附近的pattern以及3）一些人工選擇的圍棋常識性feature。

SL Policy network $p_sigma$ ：使用mini-batch of training data，用SGD計算參數，目標函數是預測下一個action的概率分布。總共訓練用了50個GPU，3個星期的時間。

RL Policy network $p_ ho$ ： $p_ ho$ initialized to be equal to $p_sigma$ ，然後自己和自己下棋，之後 $p_ ho$ 會和一個opponent pool里隨機抽的policy下，每過500次循環（也就是最初的500次循環都是在跟SL policy network下），就會把當前的policy加入opponent pool。一個循環中：weight的更新根據n個mini-batch的更新的平均值，一個mini-batch的每一次self-play都會下兩次，第一次下完是為了用最後輸贏計算遊戲每一回合的評分 $z_t=pm r(s_T)$ ，第二次重新下就用這個評分結合log action概率更新policy network參數，使用的演算法叫REINFORCE演算法。總共用時一天。

Value network：用value network來近似Policy network的value function。訓練用的數據來自3000萬個盤面（分別來自3000萬盤self-play，與RL的self-play不同）。self-play是通過三個步驟完成的1）在1-450中隨機取一個數作為分界點U，則這一局棋的第1至第U-1手均由SL的policy network sample出來；2）第U手下在棋盤任意legal的位置；3）從第U手下到結束都用RL policy network。每一局棋只取一個data $(s_{U+1},z_{U+1})$ 放入value network的training set里。對這個training set作回歸。training用了一個星期。

Feature for policy/value network：使用的feature都是直接使用遊戲規則（棋子顏色、棋子的氣、吃子、能否落子、回合數）。

NN Architecture：

Policy network：input to policy network是 $19 imes 19 imes 48$ ，因為input feature採用one-hot encoding，所以所有feature encoding後總共有48個plane（例如image用3個plane代表RGB color channel）。第一層用k個 $5 imes 5$ 卷積核，zero pad input，stride=1，（因為kernel是 $5 imes 5$ ，所以zero pad加了兩排0在input上所以輸出output是 $19 imes 19 imes k$ ）activation function=ReLU；之後第二至十二層，都是k個 $3 imes 3$ 的卷積核，zero pad input，stride=1, activation function=ReLU；最後一層只有1個 $1 imes 1$ 卷積核，但每一個position的bias都不同，最後用softmax計算概率分布。不同版本的AlphaGo，使用不同深度的卷積核，我們試過128，192，256和384。
Value network：input to value network是 $19 imes 19 imes 48$ ，外加一層binary feature表示當前下子的顏色。（沒說第一層，可能和policy network一樣），第二至第十一隱含層和policy network一樣，另外還有第十二層（沒說結構），以及第13層是1個 $1 imes 1$ 卷積核，stride=1。然後第14層是線性（用rectifier不知為啥還是線性？）全連接層，包含256個rectifier units。最後的output層也是一個全練接層，但只有一個tanh unit

後面寫了一些AlphaGo和樊輝的比賽。

---------------------------------------------------------------------------------------------------------------------------

讀後感：

AlphaGo其實和其他Model的構建過程差不多，都是基於前人廣泛的研究，然後通過自己對局部方法的一些創新或者結合一些已有方法，試圖獲得更好的performance，只不過他們在圍棋這個項目上竟然一下子取得了特別好的成績。AlphaGo是非常厲害的創新，但是很重要的是其內部的許多基礎工作，得益於已有的研究，比如文中提到的一些演算法，從文章到方法介紹總共有62個reference，大部分是以往對棋類遊戲的智能分析。
看完CS231n對CNN的介紹和前面的CS229的對MDP的介紹，好歹是能弄懂AlphaGo的邏輯，比如決策選擇和NN architecture。
但是，在game model這一塊基礎為0，不過也確實是一個很有意思的領域，也許以後的一些即時戰略或模擬類遊戲會更具智能，甚至可以指導現實中的一些decision過程。對文章內容比較模糊的部分主要是Search這一塊，MCTS以及應用的演算法和rollout分析等等。
做RL真的燒錢，之前看的Alex只用了兩塊兒GPU，這裡的distributed version用了上千塊兒CPU和50塊兒GPU，而且training data（真實+self-play）已然上億。這不得不讓人猜想，其他已有的演算法是否在distributed和使用更多training data後表現也會更好。不過文中也有強調過，AlphaGo的模型思路就是在關鍵的決策處採用general-purpose的方法，handcrafted程度很小，雖然訓練量大，但與其他模型的理念存在差距。

---------------------------------------------------------------------------------------------------------------------------

中間搜的一些名詞：

Markov games (see e.g., [Van Der Wal, 1981]) is an extension of game theory to MDP-like environments.
Minimax: decision rule used in decision theory, game theory,statistics and philosophy for minimizing the possible loss for a worst case (maximum loss)
Temporal Difference Learning: It has primarily been used for the reinforcement learning problem, and is said to be "a combination of Monte Carloideas and dynamic programming (DP) ideas." TD resembles a Monte Carlo method because it learns by sampling the environment according to some policy, and is related to dynamic programmingtechniques as it approximates its current estimate based on previously learned estimates (a process known as bootstrapping).
Asynchronous vs synchronous execution, what does it really mean?

Synchronous (one thread):

1 thread -> |----A-----||-----B-----------||-------C------|

Synchronous (multi-threaded):

thread A -> |----A-----| thread B ------------> ->|-----B-----------| thread C ----------------------------------> ->|-------C------|

Asynchronous (one thread):

A-Start ---------------------------------------- A-End | B-Start ----------------------------------------|--- B-End | | C-Start -------------------- C-End | | V V V V V V 1 thread-> |-A-|---B---|-C-|-A-|-C-|--A--|-B-|--C--|---A-----|--B--|

Asynchronous (multi-Threaded):

thread A -> |----A-----| thread B -----> |-----B-----------| thread C ---------> |-------C----------|
UCT：Applies the bandit algorithm UCB1(Upper Confidence Bounds)) for guiding selective sampling of actions in rollout-based planning. UCT is UCB applied to trees。作用是sample next actions for evaluation. PUCT：a multi-armed bandit problem with episode context
Exploration-Exploitation tradeoff: 淺顯的說就是在兩種選項中進行平衡1）選擇你不了解的（explore），可以學到新的東西；2）選擇你已經熟悉的（exploit），可以得到預期的結果
REINFORCE演算法：可以參考出處Simple statistical gradient-following algorithms for connectionist reinforcement learning.也可以看這裡。大致就是將一些gradient based尋找maximum reward policy的方法整合為統一的形式，以便用於backpropagation，因為AlphaGo的RL policy network是一個neural network。