一、強(qiáng)化學(xué)習(xí)概述

1.強(qiáng)化學(xué)習(xí)簡(jiǎn)介

（1）強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)中的一個(gè)領(lǐng)域，強(qiáng)調(diào)如何基于環(huán)境而行動(dòng)，以取得最大化的預(yù)期利益。其靈感來(lái)源于心理學(xué)中的行為主義理論，即有機(jī)體如何在環(huán)境給予的獎(jiǎng)勵(lì)或懲罰的刺激下，逐步形成對(duì)刺激的預(yù)期，產(chǎn)生能獲得最大利益的習(xí)慣性行為。

（2）強(qiáng)化學(xué)習(xí)最早可以追溯到巴甫洛夫的條件反射實(shí)驗(yàn)，它從動(dòng)物行為研究和優(yōu)化控制兩個(gè)領(lǐng)域獨(dú)立發(fā)展，最終經(jīng)Bellman之手將其抽象為馬爾可夫決策過(guò)程?(Markov Decision Process，MDP)

2.發(fā)展歷程：

1956年Bellman提出了動(dòng)態(tài)規(guī)劃方法。

1977年Werbos提出只適應(yīng)動(dòng)態(tài)規(guī)劃算法。

1988年sutton提出時(shí)間差分算法。

1992年Watkins?提出Q-learning?算法。

1994年rummery?提出Saras算法。

1996年Bersekas提出解決隨機(jī)過(guò)程中優(yōu)化控制的神經(jīng)動(dòng)態(tài)規(guī)劃方法。

2006年Kocsis提出了置信上限樹(shù)算法。

2009年kewis提出反饋控制只適應(yīng)動(dòng)態(tài)規(guī)劃算法。

2014年silver提出確定性策略梯度（Policy?Gradients）算法。

2015年Google-deepmind?提出Deep-Q-Network算法。

可見(jiàn)，強(qiáng)化學(xué)習(xí)已經(jīng)發(fā)展了幾十年，并不是一門(mén)新的技術(shù)。在2016年，AlphaGo擊敗李世石之后，融合了深度學(xué)習(xí)的強(qiáng)化學(xué)習(xí)技術(shù)大放異彩，成為這兩年最火的技術(shù)之一。總結(jié)來(lái)說(shuō)，強(qiáng)化學(xué)習(xí)就是一個(gè)古老而又時(shí)尚的技術(shù)。

3.MDP（馬兒可夫決策過(guò)程）

S:?表示狀態(tài)集(states)，有s∈S，si表示第i步的狀態(tài)。

A:表示一組動(dòng)作(actions)，有a∈A，ai表示第i步的動(dòng)作。

?sa:?表示狀態(tài)轉(zhuǎn)移概率。?s??表示的是在當(dāng)前s ∈ S狀態(tài)下，經(jīng)過(guò)a ∈ A作用后，會(huì)轉(zhuǎn)移到的其他狀態(tài)的概率分布情況。比如，在狀態(tài)s下執(zhí)行動(dòng)作a，轉(zhuǎn)移到s'的概率可以表示為p(s'|s,a)。

R: S×A???，R是回報(bào)函數(shù)(reward function)。有些回報(bào)函數(shù)狀態(tài)S的函數(shù)，可以簡(jiǎn)化為R: S??。如果一組(s,a)轉(zhuǎn)移到了下個(gè)狀態(tài)s'，那么回報(bào)函數(shù)可記為r(s'|s, a)。如果(s,a)對(duì)應(yīng)的下個(gè)狀態(tài)s'是唯一的，那么回報(bào)函數(shù)也可以記為r(s,a)。

γ:折現(xiàn)因子

4.why RL？

強(qiáng)化學(xué)習(xí)所解決的問(wèn)題的特點(diǎn)：

• 
  

• 智能體和環(huán)境之間不斷進(jìn)行交互

• 
  

• 搜索和試錯(cuò)

• 
  

• 延遲獎(jiǎng)勵(lì)（當(dāng)前所做的動(dòng)作可能很多步之后才會(huì)產(chǎn)生相應(yīng)的結(jié)果）

目標(biāo)：

• 
  

• 獲取更多的累積獎(jiǎng)勵(lì)

• 
  

• 獲得更可靠的估計(jì)

強(qiáng)化學(xué)習(xí)?(Reinforcement Learning)?是一個(gè)機(jī)器學(xué)習(xí)大家族中的分支,?由于近些年來(lái)的技術(shù)突破,?和深度學(xué)習(xí)?(Deep Learning)?的整合,?使得強(qiáng)化學(xué)習(xí)有了進(jìn)一步的運(yùn)用。比如讓計(jì)算機(jī)學(xué)著玩游戲,?AlphaGo?挑戰(zhàn)世界圍棋高手,?都是強(qiáng)化學(xué)習(xí)在行的事。強(qiáng)化學(xué)習(xí)也是讓你的程序從對(duì)當(dāng)前環(huán)境完全陌生,?成長(zhǎng)為一個(gè)在環(huán)境中游刃有余的高手。

5.總結(jié)：

深度強(qiáng)化學(xué)習(xí)全稱(chēng)是?Deep Reinforcement Learning（DRL），其所帶來(lái)的推理能力 是智能的一個(gè)關(guān)鍵特征衡量，真正的讓機(jī)器有了自我學(xué)習(xí)、自我思考的能力。

深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement?Learning，DRL)本質(zhì)上屬于采用神經(jīng)網(wǎng)絡(luò)作為值函數(shù)估計(jì)器的一類(lèi)方法，其主要優(yōu)勢(shì)在于它能夠利用深度神經(jīng)網(wǎng)絡(luò)對(duì)狀態(tài)特征進(jìn)行自動(dòng)抽取，避免了人工 定義狀態(tài)特征帶來(lái)的不準(zhǔn)確性，使得Agent能夠在更原始的狀態(tài)上進(jìn)行學(xué)習(xí)。

二、強(qiáng)化學(xué)習(xí)求解方法

1.動(dòng)態(tài)規(guī)劃方法

基石：貝爾曼方程

（1）貝爾曼方程：

貝爾曼最優(yōu)方程：

如何求解貝爾曼方程呢？

本質(zhì)上就是個(gè)線性規(guī)劃問(wèn)題，多個(gè)方程，多個(gè)未知數(shù)，進(jìn)行求解，如下，假設(shè)每一步的即使獎(jiǎng)勵(lì)是-0.2，有三個(gè)未知狀態(tài)V(0,1),V(1,1),V(1,0),損失因子是1，則在如下的策略下，得到的貝爾曼方程如下：

但是當(dāng)未知變量不斷增大，線性規(guī)劃則很難求解，這時(shí)需要使用動(dòng)態(tài)規(guī)劃進(jìn)行不斷迭代，讓其狀態(tài)值收斂。

（2）值迭代

In Value Iteration, you start with a?randon?value function and then find a new (improved) value function in a iterative process, until reaching the optimal value function. Notice that you can derive easily the optimal policy from the optimal value function. This process is based on the Optimality Bellman operator.?

（3）策略迭代

In Policy Iteration algorithms, you start with a random policy, then find the value function of that policy (policy evaluation step), then find an new (improved) policy based on the previous value function, and so on. In this process, each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). Given a policy, its value function can be obtained using the Bellman operator.

（4）算法詳細(xì)對(duì)比：

• 
  

• 根據(jù)策略迭代算法，每一次迭代都要進(jìn)行策略評(píng)估和策略提升，直到二者都收斂。可我們的目標(biāo)是選出最優(yōu)的策略，那么有沒(méi)有可能在策略評(píng)估值沒(méi)有收斂的情況下，最優(yōu)策略已經(jīng)收斂了呢？答案是有這個(gè)可能

• 
  

• 策略迭代的收斂速度更快一些，在狀態(tài)空間較小時(shí)，最好選用策略迭代方法。當(dāng)狀態(tài)空間較大時(shí)，值迭代的計(jì)算量更小一些

（5）GridWorld舉例（分別用策略迭代和值迭代進(jìn)行求解）

策略迭代過(guò)程：

值迭代過(guò)程：

2.蒙特卡洛方法

上面的動(dòng)態(tài)規(guī)劃方法，是一種較為理想的狀態(tài)，即所有的參數(shù)都提前知道，比如狀態(tài)轉(zhuǎn)移概率，及獎(jiǎng)勵(lì)等等。然而顯示情況是未知的，這時(shí)候有一種手段是采用蒙特卡洛采樣，基于大數(shù)定律，基于統(tǒng)計(jì)計(jì)算出轉(zhuǎn)移概率值；比如當(dāng)你拋硬幣的次數(shù)足夠多，那么正面和反面的概率將會(huì)越來(lái)越接近真實(shí)情況。

3.時(shí)間差分方法

基于動(dòng)態(tài)規(guī)劃和蒙特卡洛

三、強(qiáng)化學(xué)習(xí)算法分類(lèi)

1.分類(lèi)一：

基于理不理解所處環(huán)境來(lái)進(jìn)行分類(lèi)：

Model-free:環(huán)境給了我們什么就是什么.?我們就把這種方法叫做?model-free,?這里的?model?就是用模型來(lái)表示環(huán)境

Model-based:那理解了環(huán)境也就是學(xué)會(huì)了用一個(gè)模型來(lái)代表環(huán)境,?所以這種就是?model-based?方法

2.分類(lèi)二：

一類(lèi)是直接輸出各個(gè)動(dòng)作概率，另一個(gè)是輸出每個(gè)動(dòng)作的價(jià)值；前者適用于連續(xù)動(dòng)作情況，后者無(wú)法表示連續(xù)動(dòng)作的價(jià)值。

3.分類(lèi)三：

4.分類(lèi)四：

判斷on-policy和off-policy的關(guān)鍵在于，你所估計(jì)的policy或者value-function和你生成樣本時(shí)所采用的policy是不是一樣。如果一樣，那就是on-policy的，否則是off-policy的。

總結(jié)各常用算法的分類(lèi)：

四、代表性算法

1.Q-learning

（1）四個(gè)基本組成成分：

• 
  

• Q表：Q(s,a),狀態(tài)s下執(zhí)行動(dòng)作a的累積價(jià)值

• 
  

• 定義動(dòng)作：選擇動(dòng)作

• 
  

• 環(huán)境反饋：做出行為后，環(huán)境的反饋

• 
  

• 環(huán)境更新

（2）算法公式：

（3）算法決策：

（4）算法更新：

（5）代碼實(shí)現(xiàn)框架：

2.Sarsa:

與Q-learning基本類(lèi)似，唯一的區(qū)別是更新方式不一樣

（1）算法公式：

（2）與Q-learning的區(qū)別：Sarsa是on-policy的，Q-learning是off-policy的

（3）更新過(guò)程：

前者是Sarsa，后者是Q-learning

（4）代碼中展現(xiàn)不同：

Sarsa:

Q-learning:

（5）代碼實(shí)現(xiàn)框架：

3.大名鼎鼎的DQN

Deepmind就是因?yàn)镈QN這篇論文，被谷歌收購(gòu)

（1）由來(lái)：

• 
  

• 
  

  DQN（Deep?Q?Network）是一種融合了神經(jīng)網(wǎng)絡(luò)和Q?learning的方法.

  
  

• 
  

• 
  

  有些問(wèn)題太復(fù)雜，Q表無(wú)法存儲(chǔ)，即使可以存儲(chǔ)，搜索也很麻煩。故而，將Q表用神經(jīng)網(wǎng)絡(luò)進(jìn)行替代。

  
  

（2）增加了兩個(gè)新特性：

Experience?replay：每次DQN更新的時(shí)候，隨機(jī)抽取一些之前的經(jīng)歷進(jìn)行學(xué)習(xí)。隨機(jī)抽取這種打亂了經(jīng)歷之間的相關(guān)性，使得神經(jīng)網(wǎng)絡(luò)更新更有效率。

Fixed Q-targets：使用兩個(gè)結(jié)構(gòu)相同但參數(shù)不同的神經(jīng)網(wǎng)絡(luò)，預(yù)測(cè)Q估計(jì)的神經(jīng)網(wǎng)絡(luò)具備最新的參數(shù)，而預(yù)測(cè)Q現(xiàn)實(shí)的神經(jīng)網(wǎng)絡(luò)使用的參數(shù)則是很久以前的。

（3）算法公式：

paper地址：Playing?Atari with?Deep?Reinforcement?Learning

（4）DQN代碼實(shí)現(xiàn)框架：

可以看到基本上Q-learning一模一樣，只是有一處不一樣，就是多了存儲(chǔ)記憶，并且批量進(jìn)行學(xué)習(xí)。

clear; warning off all; format compact; load shujv.mat; train_y=(train_y-1)*2+1; test_y=(test_y-1)*2+1; assert(isfloat(train_x), 'train_x must be a float'); assert(all(train_x(:)>=0) && all(train_x(:)<=1), 'all data in train_x must be in [0:1]'); assert(isfloat(test_x), 'test_x must be a float'); assert(all(test_x(:)>=0) && all(test_x(:)<=1), 'all data in test_x must be in [0:1]'); %%%%%%%%%%%%%%%%%%%%This is the model of broad learning system for%%%%%% ?這是用于 m2+m3 增強(qiáng)節(jié)點(diǎn)和 m1 特征節(jié)點(diǎn)的增量的寬度學(xué)習(xí)系統(tǒng)模型 %%%%%%%%%%%%%%%%%%%%increment of m2+m3 enhancement nodes and m1 feature nodes %%%%%%%%%%%%%%%%%%%%%%%% C = 2^-30; ? ? ? ? s = 0.7 ; %the l2 regularization parameter and the shrinkage scale of the enhancement nodes l2正則化參數(shù)和增強(qiáng)節(jié)點(diǎn)的縮小比例 N11=20; %feature nodes ?per window 每個(gè)窗口的特征映射節(jié)點(diǎn)數(shù) N2=30; % number of windows of feature nodes 特征節(jié)點(diǎn)的窗口數(shù) N33=550; % number of enhancement nodes ?增強(qiáng)節(jié)點(diǎn)數(shù) epochs=1;% number of epochs ?epochs的周期數(shù) m1=20;%number of feature nodes per increment step ?每個(gè)增量步長(zhǎng)中特征節(jié)點(diǎn)數(shù) m2=80;%number of enhancement nodes related to the incremental feature nodes per increment step ?每個(gè)增量步長(zhǎng)中，與增量特征節(jié)點(diǎn)相關(guān)的增強(qiáng)節(jié)點(diǎn)的數(shù)量 m3=200;%number of enhancement nodes in each incremental learning ?每次增量學(xué)習(xí)中增強(qiáng)節(jié)點(diǎn)的數(shù)量 l=1;% steps of incremental learning ?增量學(xué)習(xí)的步長(zhǎng) train_err_t=zeros(epochs,l);test_err_t=zeros(epochs,l);train_time_t=zeros(epochs,l);test_time_t=zeros(epochs,l); Testing_time_t=zeros(epochs,1);Training_time_t=zeros(epochs,1); % rand('state',67797325) ? % 12000 %%%%% The random seed recommended by the % reference HELM [10]. ?參考HELM [10]生成的隨機(jī)數(shù) N1=N11; N3=N33; ? for i=1:epochs ? ? ? ? ?[train_err,test_err,train_time,test_time,Testing_time,Training_time] = bls_train_enhancefeature(train_x,train_y,test_x,test_y,s,C,N1,N2,N3,m1,m2,m3,l); ? ?train_err_t(i,:)=train_err;test_err_t(i,:)=test_err;train_time_t(i,:)=train_time;test_time_t(i,:)=test_time; ? ?Testing_time_t(i)=Testing_time;Training_time_t(i)=Training_time; end save ( [ 'cwt_result_enhancefeature'], 'train_err_t', 'test_err_t', 'train_time_t', 'test_time_t','Testing_time_t','Training_time_t');

?

?