網易公開課，第16課
notes，12
前面的supervised learning，對于一個指定的x可以明确告訴你，正确的y是什麼
但某些sequential decision making問題，比如下棋或直升機自動駕駛
無法确切知道，下一步怎麼樣是正确的，因為這是一個連續和序列化的決策，比如直到最終直升機crash或下棋輸了，你才知道之前的選擇是不好的，但中間那麼多步決策，到底是哪部分出了問題，可見這是個比較複雜的問題
強化學習，基本思路就是，既然不知道怎樣是正确的，那就随便try，然後根據回報好壞來，逐漸強化得到正确結果的行為
挺有意思的，想想人學習的過程，
比如大家都學過自行車，這個不是别人和你說下步怎麼做，你就能會的，開始你也不知道如何騎
隻能試，如果摔倒了，潛意識的就會改變步驟，如果可以騎起來了，就會強化剛才的步驟，慢慢身體就學會了騎車，這就是典型的強化學習
markov decision processes
馬爾可夫決策過程，可以表示成5元組
s，set of states. 狀态集合，對于直升機駕駛，就是目前的位置和方向
a，set of actions. 行為集合，對于直升機駕駛，就是下一步采取的操控，上，下，左右，前後等
比如，你讓直升機像右移動，但是比如因為風或其他noise，它移動到右前方向，或右後方，或前方，都是有可能的，是以要用機率來表示。
大家可以想象，markov決策過程應該就是如圖這個過程
表達的意思，越早的決策越重要，是不是比較合理
即，
那麼我們強化學習的目标就是，maximize the expected value of the total payoff
這個不難了解，reward function的值越大，表示越正确
比如看ng的例子，12格，其中一格為障礙，最終到達+1格（4，3）為成功，到達-1格（4，2）為失敗
假設起始點為圖中的（3，1），采取的action為n，即朝北走，圖中就是上方，有
朝上走，
到達（3，2）的機率最大，0.8
作為擾動noise，也有0.1的機率會到達（4，1），或（2，1）
到達其他格的機率為0
看看如何設定reward function的值？
到達（4，3），即成功，reward function為1
（4，2）為失敗，reward function為-1
其他格的reward function都設定為-0.02
這是一個技巧，把剩餘的格都設為很小的負面獎勵，對于導航或機器人，每多走一步意味着耗費更多的電或能源
如果要reward function和最大，必須盡量最小step數
bellman equations
那麼顯然我們的目的，就是找到使total payoff最大的那個policy函數
上面這個式子，可以寫成下面這種遞歸的形式，
這就稱為bellman equation
分為兩部分，
其中r(s)，為immediate reward，即刻回報
而用bellman等式，可以為每個s列出這樣一個等式，
還是看上面的例子，
下圖表示一個policy，可以看到畫出每一格上，選擇移動的方向，即action
現在為狀态（3，1）列出bellman等式，其中畫框的都是變量
當為每個狀态都列出上面這樣的等式時，就可以通過解方程組，解出變量值
好，繼續定義
即，因為r(s)是常數，是以得到bellman等式的另一種表示
這就是我們要找的最佳的policy
value iteration and policy iteration
那麼現在介紹算法來求解上面的最優問題，介紹的算法隻針對有限的狀态和actions的mdps
value iteration
算法挺簡單，就是用bellman等式不斷去更新v，可以證明v是會收斂于v*的
在得到v*後，用
如圖，還是上面的例子在（3，1），如何定policy？根據上面的式子分别算出往w或往n的值，發現往w是更優的policy
其中更新v的有異步和同步兩種，
同步是把所有s的新的v都算出來後，一次性更新所有的v
異步是算一個更新一個，那麼後面s的v的計算就會用到前面更新的v
policy iteration
這兩個算法都是會收斂的，
是以對于比較大的狀态集的mdp，往往使用，value iteration
learning a model for an mdp
前面的算法都是基于一個假設，即，state transition probabilities and rewards function是已知的
但是很多情況下，它們是未知的，是以我們需要去estimate出它們
其中rewards function一般也是已知的，因為這個是你提供的，你應該知道，除了些特例
是以下面就特别看下state transition probabilities是如何預估的，
其實很簡單，多試幾次，然後根據實際情況統計即可，
并且這個p應該可以線上不斷更新，會更為準确
并且對于0/0的case，用1/|s|替代
using a similar procedure, if r is unknown, we can also pick our estimate of the expected immediate reward r(s) in state s to be the average reward
observed in state s.
如果r未知，也可以用實驗中觀察到的均值來作為估計值，我不太明白，實驗中怎麼能觀察到reward function的值？
本文章摘自部落格園，原文釋出日期：2014-08-21