??在開始說值函數(shù)近似方法之前光督，我們先回顧一下強化學(xué)習(xí)算法。強化學(xué)習(xí)算法主要有兩大類Model-based 的方法和Model-free的方法，model based 的方法也可以叫做 dynamic programming ：
- Model-based dynamic programming
??在model-based的動態(tài)規(guī)劃算法中舍杜，核心概念是值迭代和策略迭代妙色。在值迭代算法中是通過對未來狀態(tài)的價值估計和及時獎勵來估計當(dāng)前狀態(tài)的價值桅滋；在策略迭代算法中，主要是通過貪婪策略進行迭代燎斩，而要使得貪婪策略能夠進行下去虱歪，依然還是會需要對狀態(tài)的估計，也就是需要值迭代栅表，但是可以不用值迭代收斂才進行策略改進笋鄙，這樣能夠使得算法收斂地快一些。其核心公式如下所示：
-
Value iteration：
怪瓶。
-
Policy iteration：
- Model-free reinforcement learning
??在model-free的強化學(xué)習(xí)算法中萧落，主要是通過蒙特卡洛的方法和TD的方法來估計state value。在TD算法中又分為On policy的sarsa算法和off-policy的q-learning算法洗贰。
-
On-Policy MC：
找岖。
-
On-Policy TD：
。
- On-policy TD SARSA ：
- Off-policy TD Q-learning ：
處理大規(guī)模狀態(tài)敛滋、動作空間
??In all previous models, we have created a lookup table to maintain a variable for each state or
for each state-action许布。
??當(dāng)state or state-action space 太大的話，或者state or action is continuous就沒辦法created the lookup table绎晃。
??解決上述問題主要有兩種方式蜜唾，一種就是將大的連續(xù)的狀態(tài)空間或者動作空間離散化，變成一塊一塊地庶艾，這種做法控制效果不會太好袁余，另外一種辦法呢，就是建立一個參數(shù)化的值函數(shù)來近似咱揍，后面這種方法也是比較常見的颖榜。
Discretization Continuous MDP
??對于連續(xù)狀態(tài)下的MDP問題，我們可以將狀態(tài)離散化為概率煤裙，比如在這個狀態(tài)下采取什么動作會以多大的概率轉(zhuǎn)移到下一個狀態(tài)掩完，進而可以離散化為一個表格的形式。這種方法非常地繁瑣硼砰。
??這里要注意的就是state transition需要對連續(xù)量積分且蓬，離散化。
Bucketize Large Discrete MDP
??對于大規(guī)模的離散化狀態(tài)空間夺刑，我們可以通過domain knowledge將相似的離散state聚合在一起缅疟。上述操作不管怎么離散聚合都會存在誤差分别。因此現(xiàn)在的主流方法還是值函數(shù)近似算法。
Parametric Value Function Approximation
- Create parametric (thus learnable) functions to approximate the value function
?? is the parameters of the approximation function, which can be updated by reinforcement learning存淫。
??這種做法一方面解決了維度災(zāi)難的問題耘斩，另一方面可以Generalize from seen states to unseen states，這也是整個machine learning最強大桅咆，最具有魅力的地方括授。
Many function approximations
- (Generalized) linear model
- Neural network
- Decision tree
- Nearest neighbor
- Fourier / wavelet bases
??上述算法都可以做 function approximations 但是決策樹、隨機森林的靈活性沒有那么強岩饼，因為強化學(xué)習(xí)算法中參數(shù)經(jīng)常會被用來更新荚虚。因此我們很多時候用Differentiable functions 像(Generalized) linear model 、Neural network來做籍茧。
??We assume the model is suitable to be trained for nonstationary, non-iid data
Value Function Approx. by SGD
-
Goal: find parameter vector
minimizing mean-squared error between approximate value function
and true value
版述。
- Gradient to minimize the error
- Stochastic gradient descent on one sample
Linear Value Function Approximation
??舉個實際的例子：
- Represent value function by a linear combination of features
- Objective function is quadratic in parameters
- Thus stochastic gradient descent converges on global optimum
??那上述公式中的是怎么求的呢？
Monte-Carlo with Value Function Approx
??如果不知道真正的value是多少就無法更新寞冯，之前的方法就可以拿過來用了渴析。
??For each data instance ：
??可以證明MC evaluation at least converges to a local optimum 吮龄，如果環(huán)境本身是In linear case it converges to a global optimum俭茧。
TD Learning with Value Function Approx
??現(xiàn)在就是在找這個target learning用什么東西來替代它，在TD Learning中For each data instance ：
??Linear TD converges (close) to global optimum漓帚。
Action-Value Function Approximation
- Approximate the action-value function：
- Minimize mean squared error：
- Stochastic gradient descent on one sample：
Linear Action-Value Function Approx
- Represent state-action pair by a feature vector
??這里就需要從state-action pair上面去抽取 fearure母债。
- Parametric Q function, e.g., the linear case
- Stochastic gradient descent update
TD Learning with Value Function Approx.
- For MC, the target is the return
：
- For TD，the target is
：
Control with Value Function Approx
??上圖中無法達到上界的原因是由于值函數(shù)近似逼近無法趨近于真實 所導(dǎo)致的尝抖。
- Policy evaluation: approximatelypolicy evaluation
毡们。
- Policy improvement:
-greedy policy improvement。
NOTE of TD Update
For TD(0), the TD target is
- State value
- Action value
??Although is in the TD target, we don’t calculate gradient from the target. Think about why.
??對上述問題主要有兩方面的理解：1. 更新方程中是用后面的估值更新前面的牵署，而不需要去更新后面的漏隐，這也是馬爾可夫性所決定的大體思想(在無近似值函數(shù)的算法中也是這么做的)喧半；2. 在做神經(jīng)網(wǎng)絡(luò)的時候奴迅，可以更新后面的那一項都不去做更新，因為會使得算法更新不穩(wěn)定挺据。
Deep Q-Network (DQN)
??在2013年年底的時候DeepMind就基于深度學(xué)習(xí)和強化學(xué)習(xí)做出來了直接估計像素狀態(tài)值函數(shù)的深度強化學(xué)習(xí)算法取具。
??看似比較簡單的更新的trick，在深度強化學(xué)習(xí)里面往往是比較重要的method扁耐，原因是因為當(dāng)你神經(jīng)網(wǎng)絡(luò)變得復(fù)雜的時候暇检，很多以前經(jīng)典的算法都會不那么work，而如果能真正理解深度神經(jīng)網(wǎng)絡(luò)婉称，而應(yīng)用在強化學(xué)習(xí)里面块仆，這些看起來像一些trick的東西构蹬，往往會是深度強化學(xué)習(xí)里面最重要的算法。
- VolodymyrMnih, KorayKavukcuoglu, David Silver et al. Playing Atari with Deep Reinforcement Learning. NIPS 2013 workshop.
- VolodymyrMnih, KorayKavukcuoglu, David Silver et al. Human-level control through deep reinforcement learning. Nature 2015.
我的微信公眾號名稱：深度學(xué)習(xí)與先進智能決策
微信公眾號ID：MultiAgent1024
公眾號介紹：主要研究分享深度學(xué)習(xí)悔据、機器博弈庄敛、強化學(xué)習(xí)等相關(guān)內(nèi)容！期待您的關(guān)注科汗，歡迎一起學(xué)習(xí)交流進步藻烤！
