機(jī)器學(xué)習(xí)一共有三個(gè)分支澜共，有監(jiān)督學(xué)習(xí)型凳、無監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)心俗。強(qiáng)化學(xué)習(xí)是系統(tǒng)從環(huán)境學(xué)習(xí)以使得獎(jiǎng)勵(lì)最大的機(jī)器學(xué)習(xí)单绑。強(qiáng)化學(xué)習(xí)和有監(jiān)督學(xué)習(xí)的不同在于教師信號(hào)回官。強(qiáng)化學(xué)習(xí)的教師信號(hào)是動(dòng)作的獎(jiǎng)勵(lì)，有監(jiān)督學(xué)習(xí)的教師信號(hào)是正確的動(dòng)作搂橙。

1. 馬爾科夫決策過程

要說強(qiáng)化學(xué)習(xí)歉提，就必須說說馬爾科夫決策過程 (Markov Decision Processes, MDP)。馬爾可夫決策過程是基于馬爾可夫過程理論的隨機(jī)動(dòng)態(tài)系統(tǒng)的決策過程，其分五個(gè)部分：

和一般的馬爾科夫過程不同苔巨，馬爾科夫決策過程考慮了動(dòng)作版扩，即系統(tǒng)下個(gè)狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān)，也和當(dāng)前采取的動(dòng)作有關(guān)侄泽。還是舉下棋的例子礁芦，當(dāng)我們在某個(gè)局面（狀態(tài)s）走了一步 (動(dòng)作 a )。這時(shí)對手的選擇（導(dǎo)致下個(gè)狀態(tài) s’ ）我們是不能確定的蔬顾，但是他的選擇只和 s 和 a 有關(guān)宴偿，而不用考慮更早之前的狀態(tài)和動(dòng)作，即 s’ 是根據(jù) s 和 a 隨機(jī)生成的诀豁。
下圖是一個(gè)機(jī)器人從任意一個(gè)狀態(tài)出發(fā)尋找金幣的例子窄刘。找到金幣則獲得獎(jiǎng)勵(lì) 1，碰到海盜則損失 1舷胜。找到金幣或者碰到海盜則機(jī)器人停止娩践。

我們可以把這個(gè)問題建模成馬爾科夫決策過程。圖中不同位置為狀態(tài)烹骨，因此 S = {1,...,8}翻伺。機(jī)器人采取動(dòng)作是向東南西北四個(gè)方向走，因此A={'n','e','s','w'}沮焕。轉(zhuǎn)移概率方面吨岭，當(dāng)機(jī)器人碰到墻壁，則會(huì)停在原來的位置峦树；當(dāng)機(jī)器人找到金幣時(shí)獲得獎(jiǎng)勵(lì) 1辣辫，當(dāng)碰到海盜則損失 1, 其他情況不獎(jiǎng)勵(lì)也不懲罰。因此除了 R1,s=?1 , R3,s=1 魁巩， R5,s=?1 之外急灭，其他情況 R?,?=0 。衰減因子 γ 在后面介紹谷遂。寫成代碼下面所示：

    class Mdp():
        def __init__(self):
            self.states = [1, 2, 3, 4, 5, 6, 7, 8]

            self.terminal_states = dict()
            self.terminal_states[6] = 1
            self.terminal_states[7] = 1
            self.terminal_states[8] = 1

            self.actions = ['e', 'w', 's', 'n']

            self.rewards = dict()
            self.rewards['1_s'] = -1.0
            self.rewards['3_s'] = 1.0
            self.rewards['5_s'] = -1.0

            self.t = dict()
            self.t['1_s'] = 6
            self.t['1_e'] = 2
            self.t['2_w'] = 1
            self.t['2_e'] = 3
            self.t['3_s'] = 7
            self.t['3_w'] = 2
            self.t['3_e'] = 4
            self.t['4_w'] = 3
            self.t['4_e'] = 5
            self.t['5_s'] = 8
            self.t['5_w'] = 4

            self.gamma = 0.8

    def transform(self,state,action):
        if state in self.terminal_states:
            return True, state, 0

        key = '%d_%s'%(state,action)
        if key in self.t:
            next_state = self.t[key]
        else:
            next_state = state
        is_terminal = False
        if next_state in self.terminal_states:
            is_terminal = True

        if key not in self.rewards:
            r = 0.0
        else:
            r = self.rewards[key]
        print(is_terminal,next_state,r)
        return is_terminal, next_state, r

import random

demo = Mdp()
is_terminal=False
init_state = 1

while(is_terminal==False):
    action = random.randint(0,3)
    is_terminal,state,r = demo.transform(init_state,demo.actions[action])

馬爾科夫決策過程是強(qiáng)化學(xué)習(xí)的理論基礎(chǔ)葬馋。不管我們是將強(qiáng)化學(xué)習(xí)應(yīng)用于五子棋游戲、星際爭霸還是機(jī)器人行走肾扰，我們都假設(shè)背后存在了一個(gè)馬爾科夫決策過程畴嘶。只不過有的時(shí)候我們知道馬爾科夫決策過程所有信息(狀態(tài)集合，動(dòng)作集合集晚，轉(zhuǎn)移概率和獎(jiǎng)勵(lì))掠廓，有的時(shí)候我們只知道部分信息 (狀態(tài)集合和動(dòng)作集合)，還有些時(shí)候馬爾科夫決策過程的信息太大無法全部存儲(chǔ) (比如圍棋的狀態(tài)集合總數(shù)為 319×19 )甩恼。強(qiáng)化學(xué)習(xí)算法按照上述不同情況可以分為兩種: 基于模型 (Model-based) 和非基于模型 (Model-free)。基于模型的強(qiáng)化學(xué)習(xí)算法是知道并可以存儲(chǔ)所有馬爾科夫決策過程信息条摸，非基于模型的強(qiáng)化學(xué)習(xí)算法則需要自己探索未知的馬爾科夫過程悦污。

2、策略和價(jià)值

強(qiáng)化學(xué)習(xí)技術(shù)是要學(xué)習(xí)一個(gè)策略 (Policy)钉蒲。這個(gè)策略其實(shí)是一個(gè)函數(shù)切端，輸入當(dāng)前的狀態(tài) s，輸出采取動(dòng)作 a 的概率 π(s,a) 顷啼。有監(jiān)督學(xué)習(xí)希望分類器正確地對實(shí)例分類踏枣，那么強(qiáng)化學(xué)習(xí)的目標(biāo)是什么呢？強(qiáng)化學(xué)習(xí)希望把策略訓(xùn)練什么樣呢钙蒙？ 假設(shè)我們的系統(tǒng)在一個(gè)狀態(tài) s 中茵瀑，我們不會(huì)選擇當(dāng)前獎(jiǎng)勵(lì) Rs,a 最大的動(dòng)作 a。因此這個(gè)動(dòng)作可能導(dǎo)致系統(tǒng)進(jìn)入死胡同躬厌，即系統(tǒng)之后會(huì)受到很大的處罰马昨。為了避免這種情況，策略要考慮到后續(xù)的影響扛施。因此我們最大化遞減獎(jiǎng)勵(lì)的期望：

其中 γ 是馬爾科夫決策過程的第五個(gè)部分：衰減因子鸿捧。 γ 用于平衡當(dāng)前獎(jiǎng)勵(lì)和遠(yuǎn)期獎(jiǎng)勵(lì)的重要性，也是用來避免計(jì)算結(jié)果無窮疙渣。 Rk 是系統(tǒng)在當(dāng)前策略下第 k 步之后獲得的獎(jiǎng)勵(lì)匙奴。這種目標(biāo)既考慮了當(dāng)前獎(jiǎng)勵(lì)又考慮了遠(yuǎn)期獎(jiǎng)勵(lì)，避免了下一個(gè)狀態(tài)是死胡同的問題妄荔。
根據(jù)上面的目標(biāo)泼菌，人們提出了價(jià)值的概念。一個(gè)策略下的一個(gè)狀態(tài)的價(jià)值定義：這個(gè)狀態(tài)下懦冰，按照這個(gè)策略灶轰，系統(tǒng)能夠獲得的遞減獎(jiǎng)勵(lì)期望。

上面機(jī)器人找金幣的例子中刷钢，設(shè)定衰減因子 γ
等于 0.5笋颤。如果策略是一直往西走碰壁之后立馬向南，那么狀態(tài) 2 的價(jià)值 v(2)=0+0.5??1.0=?0.5
内地。如果策略是隨機(jī)一個(gè)方向伴澄，那么所有狀態(tài)的價(jià)值如下圖所示。

3荆针、最優(yōu)策略存在性和貝爾曼等式

根據(jù)上面的介紹敞嗡，我們發(fā)現(xiàn)強(qiáng)化學(xué)習(xí)的目標(biāo)是找到一個(gè)策略 π , 使得這個(gè)策略下每個(gè)狀態(tài)的價(jià)值最大颁糟。但是這里有一個(gè)問題啊。對于兩個(gè)策略喉悴，有可能出現(xiàn)：策略 π1 狀態(tài) a 的價(jià)值大于策略 π2 狀態(tài) b 的價(jià)值棱貌，但策略 π2 狀態(tài) c 的價(jià)值大于策略 π1 狀態(tài) d 的價(jià)值。因此我們不確定箕肃，是否存在一個(gè)策略 pi 的所有狀態(tài)價(jià)值大等于其他策略的狀態(tài)價(jià)值婚脱。如果不存在這么一個(gè)策略，我們的目標(biāo)是迷茫的勺像。
但是萬幸啊障贸，下面的定理保證了這么一個(gè)策略存在。這么一個(gè)所有狀態(tài)價(jià)值大等于其他所有的狀態(tài)價(jià)值吟宦，我們可以稱之為最優(yōu)策略篮洁。強(qiáng)化學(xué)習(xí)算法的目標(biāo)就是找到最優(yōu)策略。

另外一個(gè)重要的點(diǎn)是貝爾曼等式督函。貝爾曼登等式表明了當(dāng)前狀態(tài)的值函數(shù)與下個(gè)狀態(tài)的值函數(shù)的關(guān)系嘀粱，具有很簡明的形式。

關(guān)于貝爾曼等式中的各個(gè)部分辰狡，可以看下面的解釋：