一、無模型的強化學習

在上一節(jié)中介紹了基于模型的強化學習方法(動態(tài)規(guī)劃)，其中的前提是知道環(huán)境的狀態(tài)轉(zhuǎn)移概率，但在實際問題中，狀態(tài)轉(zhuǎn)移的信息往往無法獲知，由此需要數(shù)據(jù)驅(qū)動的無模型(model-free)的方法。

1.1、蒙特卡羅(Monte Carlo)方法

在無模型時，一種自然的想法是通過隨機采樣的經(jīng)驗平均來估計期望值，此即蒙特卡羅法。其過程可以總結如下：

1. 智能體與環(huán)境交互后得到交互序列
2. 通過序列計算出各個時刻的獎賞值
3. 將獎賞值累積到值函數(shù)中進行更新
4. 根據(jù)更新的值函數(shù)來更新策略

在動態(tài)規(guī)劃中，為保證算法的收斂性，算法會逐個掃描狀態(tài)空間中的狀態(tài)，計算值函數(shù)時用到了當前狀態(tài)的所有后繼狀態(tài)的值函數(shù)。而蒙特卡羅利用經(jīng)驗平均估計狀態(tài)的值函數(shù)，此處的經(jīng)驗是指一次試驗，而一次試驗要等到終止狀態(tài)出現(xiàn)才結束，因此學習速度慢，效率不高。下圖較直觀展示了二者的不同。

動態(tài)規(guī)劃

蒙特卡羅

在蒙特卡羅中，如果采用確定性策略，每次試驗的軌跡都是一樣的，因此無法進一步改進策略。為了使更多狀態(tài)-動作對參與到交互過程中，即平衡探索和利用，常用ε-greedy策略來產(chǎn)生動作 ，以保證每個狀態(tài)-動作對都有機會作為初始狀態(tài)，在評估狀態(tài)-動作值函數(shù)時，需要對每次試驗中所有狀態(tài)-動作對進行估計。

1.2、時序差分方法

由于蒙特卡羅需要獲得完整軌跡，才能進行策略評估并更新，效率較低。時序差分法結合了動態(tài)規(guī)劃和蒙特卡羅，即模擬一段軌跡(一步或者幾步)，然后利用貝爾曼方程進行自迭代更新，如下圖所示：

時序差分

比較三種方法估計值函數(shù)的異同點。蒙特卡羅使用的是值函數(shù)最原始的定義，即利用所有獎賞的累積和來估計值函數(shù)；動態(tài)規(guī)劃和時序差分則利用一步預測方法來計算當前狀態(tài)值函數(shù)，不同的是，動態(tài)規(guī)劃利用模型計算后繼狀態(tài)，時序差分利用實驗得到后繼狀態(tài)。

1.3、Q-Learning

Q-Learning是一種異策略(off policy)的時序差分方法，即動作策略為ε-greedy策略，目標策略為貪婪策略。在更新值函數(shù)時并不完全遵循交互序列，而是選擇來自其他策略的交互序列的子部分替換了原來的交互序列。從思想來說，它結合了子部分的最優(yōu)價值，更像是結合了價值迭代的更新算法，希望每一次都使用前面迭代積累的最優(yōu)結果進行更新。

Q-Learning 算法

Q-Learning的收斂性分析

為簡明起見，筆者在此僅做原理上的證明，更加嚴格的證明可見參考資料[2] P189-193.
根據(jù)Q-Learning的更新公式(此處“=”表達賦值含義)：
第一次迭代：
第二次迭代：
......
第n次迭代：
由于：，當n足夠大時，有，則：
仍然是最原始的貝爾曼方程的形式，說明該算法是收斂的。
下面說明收斂效果：
引理：輸出在上的隨機過程的更新過程定義為
如果下面的條件能夠滿足，那么它將依概率1 收斂到0:
（1），同時保證。
（2），同時。
（3），其中。

現(xiàn)假定值函數(shù)收斂且收斂值為，則： 令,,則上式變?yōu)椋?img class="math-block" src="https://math.jianshu.com/math?formula=%5CDelta%3D%5Cleft(1-%5Calpha%5Cright)%5CDelta%2B%5Calpha%20F" alt="\Delta=\left(1-\alpha\right)\Delta+\alpha F" mathimg="1"> 可以驗證滿足以上三個條件（驗證過程需要一定矩陣理論、概率統(tǒng)計知識，讀者可以嘗試證明），在此不再贅述。

二、函數(shù)近似與DQN

2.1、函數(shù)近似(Function Approximation)

在此之前介紹的強化學習方法(動態(tài)規(guī)劃、蒙特卡羅、時序差分)都有一個共同前提：狀態(tài)空間和動作空間是離散的且不能太大。通常值函數(shù)用表格的形式的表示，故又稱之為表格型強化學習。而在很多問題中，狀態(tài)空間維數(shù)很大，或者狀態(tài)空間是連續(xù)的，無法用表格表示，故需要函數(shù)近似的方式。
事實上，對于狀態(tài)和動作，值函數(shù)，存在這樣一個映射：，由此求解值函數(shù)的問題轉(zhuǎn)化為監(jiān)督學習的問題，而監(jiān)督學習是一種常見且易于解決的問題。線性回歸(Linear Regression) 、支持向量機(Support Vector Machine)、決策樹(Decision Tree)， 以及神經(jīng)網(wǎng)絡(Neural Network )等都可以用來解決此類問題。
下面通過在數(shù)學上說明以上過程：
假定狀態(tài)空間為維實數(shù)空間，且值函數(shù)能表達為狀態(tài)的線性函數(shù)，即： 其中為狀態(tài)向量，為參數(shù)向量。
為使學習得到的值函數(shù)盡可能近似于真實值函數(shù) ，用最小二乘來度量誤差： 其中 表示由策略采樣而得到的狀態(tài)上的期望。

為最小化誤差，采用梯度下降，對誤差求負導數(shù)：

于是得到以下更新規(guī)則： 又，用當前估計值函數(shù)代替真實值函數(shù)，則： 與Q-Learning的更新方式相同，僅僅是值函數(shù)的表達不同。

2.2、Deep Q-Network(DQN)

之前大量敘述了強化學習的基本原理，至此才開始真正的深度強化學習的部分。Deep Q-Network，簡稱DQN，來自論文 Human-level control through deep reinforcement learning。論文主要介紹了如何使用DQN 網(wǎng)絡訓練Agent 在Atari游戲平臺上盡可能獲得更多的分數(shù)。
與Q-Learning相比，DQN主要改進在以下三個方面：
（1）DQN利用深度卷積網(wǎng)絡(Convolutional Neural Networks,CNN)來逼近值函數(shù)；
（2）DQN利用經(jīng)驗回放訓練強化學習的學習過程；
（3）DQN獨立設置了目標網(wǎng)絡來單獨處理時序差分中的偏差。

DQN 結構

下面主要說明經(jīng)驗回放和目標網(wǎng)絡：
經(jīng)驗回放(Replay Buffer)
Q-Leaning 方法基于當前策略進行交互和改進，每一次模型利用交互生成的數(shù)據(jù)進行學習，學習后的樣本被直接丟棄。但如果使用機器學習模型代替表格式模型后再采用這樣的在線學習方法，就有可能遇到兩個問題，這兩個問題也都和機器學習有關。

1. 交互得到的序列存在一定的相關性。交互序列中的狀態(tài)行動存在著一定的相關性，而對于基于最大似然法的機器學習模型來說，我們有一個很重要的假設：訓練樣本是獨立且來自相同分布的，一旦這個假設不成立，模型的效果就會大打折扣。而上面提到的相關性恰好打破了獨立同分布的假設，那么學習得到的值函數(shù)模型可能存在很大的波動。
2. 交互數(shù)據(jù)的使用效率。采用梯度下降法進行模型更新時，模型訓練往往需要經(jīng)過多輪迭代才能收斂。每一次迭代都需要使用一定數(shù)量的樣本計算梯度， 如果每次計算的樣本在計算一次梯度后就被丟棄，那么我們就需要花費更多的時間與環(huán)境交互并收集樣本。

Replay Buffer 結構

DQN 算法

四、案例分析

尋寶小游戲 規(guī)則:在4×4的網(wǎng)格中，紅色方塊為尋寶者，黃色圓形為寶藏，找到寶藏獎勵為1，黑色方塊為陷阱，落入陷阱獎勵為-1，其他位置獎勵為0，通過訓練使尋寶者找到通往寶藏的路徑。

尋寶 小游戲

環(huán)境由使用Tkinter包繪制，為簡明并突出算法，在此不予介紹，感興趣的讀者可以下載源代碼加以了解。

4.1、Q-Learning實踐

1. Q-Learning算法主體
   定義一個 QLearningTable的類，首先初始化參數(shù)，其意義分別如注釋所示，其中Q值用q_table來表示。choose_action()函數(shù)定義如何決定行為，根據(jù)所在的 state, 或者是在這個 state 上的 觀測值 (observation) 來決策，采用ε-greedy策略。learn()函數(shù)決定學習過程，根據(jù)是否是 terminal state (回合終止符) 來判斷應該如何更行 q_table，其更新方式與算法描述相同。check_state_exist()函數(shù)功能就是檢測 q_table 中有沒有當前 state 的步驟了, 如果還沒有當前 state, 那我我們就插入一組全 0 數(shù)據(jù), 當做這個 state 的所有 action 初始 values。

import numpy as np
import pandas as pd

class QLearningTable:
    def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):
        self.actions = actions   # a list
        self.lr = learning_rate   # 學習率
        self.gamma = reward_decay    # 獎勵衰減
        self.epsilon = e_greedy     # 貪婪度
        self.q_table = pd.DataFrame(columns=self.actions, dtype=np.float64)    # 初始 q_table

    def choose_action(self, observation):
        self.check_state_exist(observation)   # 檢測本 state 是否在 q_table 中存在
        # action selection
        if np.random.uniform() < self.epsilon:
            # choose best action
            state_action = self.q_table.loc[observation, :]
            # some actions may have the same value, randomly choose on in these actions
            action = np.random.choice(state_action[state_action == np.max(state_action)].index)
        else:
            # choose random action
            action = np.random.choice(self.actions)
        return action

    def learn(self, s, a, r, s_):
        self.check_state_exist(s_)    # 檢測 q_table 中是否存在 s_
        q_predict = self.q_table.loc[s, a]
        if s_ != 'terminal':
            q_target = r + self.gamma * self.q_table.loc[s_, :].max()  # next state is not terminal
        else:
            q_target = r  # next state is terminal
        self.q_table.loc[s, a] += self.lr * (q_target - q_predict)  # update

    def check_state_exist(self, state):
        if state not in self.q_table.index:
            # append new state to q table
            self.q_table = self.q_table.append(
                pd.Series(
                    [0]*len(self.actions),
                    index=self.q_table.columns,
                    name=state,
                )
            )

2. 環(huán)境交互及更新過程
   該部分是整個 Q-Learning最重要的迭代更新部分，主體循環(huán)部分簡單易讀，體現(xiàn)了智能體與環(huán)境的交互和更新過程。

from maze_env import Maze
from RL_brain import QLearningTable

def update():
    for episode in range(100):
        # initial observation
        observation = env.reset()

        while True:
            # fresh env
            env.render()

            # RL choose action based on observation
            action = RL.choose_action(str(observation))

            # RL take action and get next observation and reward
            observation_, reward, done = env.step(action)

            # RL learn from this transition
            RL.learn(str(observation), action, reward, str(observation_))

            # swap observation
            observation = observation_

            # break while loop when end of this episode
            if done:
                break

    # end of game
    print('game over')
    env.destroy()

if __name__ == "__main__":
    env = Maze()
    RL = QLearningTable(actions=list(range(env.n_actions)))

    env.after(100, update)
    env.mainloop()

Q-Learning 算法實現(xiàn)的效果如下圖所示，可見尋寶者發(fā)現(xiàn)寶藏的動態(tài)過程。

Q-Learning 效果

4.2、DQN實踐

1. 神經(jīng)網(wǎng)絡的搭建
   為了使用 Tensorflow 來實現(xiàn) DQN, 比較推薦的方式是搭建兩個神經(jīng)網(wǎng)絡, target_net 用于預測 q_target 值, 他不會及時更新參數(shù),eval_net 用于預測 q_eval, 這個神經(jīng)網(wǎng)絡擁有最新的神經(jīng)網(wǎng)絡參數(shù). 不過這兩個神經(jīng)網(wǎng)絡結構是完全一樣的, 只是里面的參數(shù)不一樣。兩個神經(jīng)網(wǎng)絡是為了固定住一個神經(jīng)網(wǎng)絡 (target_net) 的參數(shù), target_net 是 eval_net 的一個歷史版本, 擁有 eval_net 很久之前的一組參數(shù), 而且這組參數(shù)被固定一段時間, 然后再被 eval_net 的新參數(shù)所替換. 而 eval_net 是不斷在被提升的, 所以是一個可以被訓練的網(wǎng)絡 trainable=True. 而 target_net 的 trainable=False。

class DeepQNetwork:
    def _build_net(self):
        # ------------------ build evaluate_net ------------------
        self.s = tf.placeholder(tf.float32, [None, self.n_features], name='s')  # input
        self.q_target = tf.placeholder(tf.float32, [None, self.n_actions], name='Q_target')  # for calculating loss
        with tf.variable_scope('eval_net'):
            # c_names(collections_names) are the collections to store variables
            c_names, n_l1, w_initializer, b_initializer = \
                ['eval_net_params', tf.GraphKeys.GLOBAL_VARIABLES], 10, \
                tf.random_normal_initializer(0., 0.3), tf.constant_initializer(0.1)  # config of layers

            # first layer. collections is used later when assign to target net
            with tf.variable_scope('l1'):
                w1 = tf.get_variable('w1', [self.n_features, n_l1], initializer=w_initializer, collections=c_names)
                b1 = tf.get_variable('b1', [1, n_l1], initializer=b_initializer, collections=c_names)
                l1 = tf.nn.relu(tf.matmul(self.s, w1) + b1)

            # second layer. collections is used later when assign to target net
            with tf.variable_scope('l2'):
                w2 = tf.get_variable('w2', [n_l1, self.n_actions], initializer=w_initializer, collections=c_names)
                b2 = tf.get_variable('b2', [1, self.n_actions], initializer=b_initializer, collections=c_names)
                self.q_eval = tf.matmul(l1, w2) + b2

        with tf.variable_scope('loss'):
            self.loss = tf.reduce_mean(tf.squared_difference(self.q_target, self.q_eval))
        with tf.variable_scope('train'):
            self._train_op = tf.train.RMSPropOptimizer(self.lr).minimize(self.loss)

        # ------------------ build target_net ------------------
        self.s_ = tf.placeholder(tf.float32, [None, self.n_features], name='s_')    # input
        with tf.variable_scope('target_net'):
            # c_names(collections_names) are the collections to store variables
            c_names = ['target_net_params', tf.GraphKeys.GLOBAL_VARIABLES]

            # first layer. collections is used later when assign to target net
            with tf.variable_scope('l1'):
                w1 = tf.get_variable('w1', [self.n_features, n_l1], initializer=w_initializer, collections=c_names)
                b1 = tf.get_variable('b1', [1, n_l1], initializer=b_initializer, collections=c_names)
                l1 = tf.nn.relu(tf.matmul(self.s_, w1) + b1)

            # second layer. collections is used later when assign to target net
            with tf.variable_scope('l2'):
                w2 = tf.get_variable('w2', [n_l1, self.n_actions], initializer=w_initializer, collections=c_names)
                b2 = tf.get_variable('b2', [1, self.n_actions], initializer=b_initializer, collections=c_names)
                self.q_next = tf.matmul(l1, w2) + b2

通過tensorboard繪制的網(wǎng)絡結構圖如下圖所示。

網(wǎng)絡結構圖

2. 思維決策的過程
   定義完上次的神經(jīng)網(wǎng)絡部分以后, 這次來定義其他部分，首先是函數(shù)值的初始化。

class DeepQNetwork:
    def __init__(
            self,
            n_actions,
            n_features,
            learning_rate=0.01,
            reward_decay=0.9,
            e_greedy=0.9,
            replace_target_iter=300,
            memory_size=500,
            batch_size=32,
            e_greedy_increment=None,
            output_graph=False,
    ):
        self.n_actions = n_actions
        self.n_features = n_features
        self.lr = learning_rate
        self.gamma = reward_decay
        self.epsilon_max = e_greedy  # epsilon 的最大值
        self.replace_target_iter = replace_target_iter    # 更換 target_net 的步數(shù)
        self.memory_size = memory_size    # 記憶上限
        self.batch_size = batch_size       # 每次更新時從 memory 里面取多少記憶出來
        self.epsilon_increment = e_greedy_increment   # epsilon 的增量
        self.epsilon = 0 if e_greedy_increment is not None else self.epsilon_max     # 是否開啟探索模式, 并逐步減少探索次數(shù)

        # total learning step
        self.learn_step_counter = 0

        # initialize zero memory [s, a, r, s_]
        self.memory = np.zeros((self.memory_size, n_features * 2 + 2))

        # consist of [target_net, evaluate_net]
        self._build_net()
        t_params = tf.get_collection('target_net_params')  # 提取 target_net 的參數(shù)
        e_params = tf.get_collection('eval_net_params')    # 提取  eval_net 的參數(shù)
        self.replace_target_op = [tf.assign(t, e) for t, e in zip(t_params, e_params)]

        self.sess = tf.Session()

        if output_graph:
            # $ tensorboard --logdir=logs
            # tf.train.SummaryWriter soon be deprecated, use following
            tf.summary.FileWriter("logs/", self.sess.graph)

        self.sess.run(tf.global_variables_initializer())
        self.cost_his = []   # 記錄所有 cost 變化, 用于最后 plot 出來觀看

記憶存儲，DQN 的精髓部分之一: 記錄下所有經(jīng)歷過的步, 這些步可以進行反復的學習, 所以是一種 off-policy 方法。

class DeepQNetwork:
    def store_transition(self, s, a, r, s_):
        if not hasattr(self, 'memory_counter'):
            self.memory_counter = 0

        transition = np.hstack((s, [a, r], s_))

        # replace the old memory with new memory
        index = self.memory_counter % self.memory_size
        self.memory[index, :] = transition

        self.memory_counter += 1

行為選擇，讓 eval_net 神經(jīng)網(wǎng)絡生成所有 action 的值, 并選擇值最大的 action；學習過程就是在 DeepQNetwork 中, 是如何學習, 更新參數(shù)的. 這里涉及了 target_net 和 eval_net 的交互使用，這是非常重要的一步。

class DeepQNetwork:
    def choose_action(self, observation):
        # to have batch dimension when feed into tf placeholder
        observation = observation[np.newaxis, :]

        if np.random.uniform() < self.epsilon:
            # forward feed the observation and get q value for every actions
            actions_value = self.sess.run(self.q_eval, feed_dict={self.s: observation})
            action = np.argmax(actions_value)
        else:
            action = np.random.randint(0, self.n_actions)
        return action

    def learn(self):
        # check to replace target parameters
        if self.learn_step_counter % self.replace_target_iter == 0:
            self.sess.run(self.replace_target_op)
            print('\ntarget_params_replaced\n')

        # sample batch memory from all memory
        if self.memory_counter > self.memory_size:
            sample_index = np.random.choice(self.memory_size, size=self.batch_size)
        else:
            sample_index = np.random.choice(self.memory_counter, size=self.batch_size)
        batch_memory = self.memory[sample_index, :]

         # 獲取 q_next (target_net 產(chǎn)生了 q) 和 q_eval(eval_net 產(chǎn)生的 q)
        q_next, q_eval = self.sess.run(
            [self.q_next, self.q_eval],
            feed_dict={
                self.s_: batch_memory[:, -self.n_features:],  # fixed params
                self.s: batch_memory[:, :self.n_features],  # newest params
            })

        # 下面這幾步十分重要. q_next, q_eval 包含所有 action 的值,
        # 而我們需要的只是已經(jīng)選擇好的 action 的值, 其他的并不需要.
        # 所以我們將其他的 action 值全變成 0, 將用到的 action 誤差值 反向傳遞回去, 作為更新憑據(jù).
        # 這是我們最終要達到的樣子, 比如 q_target - q_eval = [1, 0, 0] - [-1, 0, 0] = [2, 0, 0]
        # q_eval = [-1, 0, 0] 表示這一個記憶中有我選用過 action 0, 而 action 0 帶來的 Q(s, a0) = -1, 所以其他的 Q(s, a1) = Q(s, a2) = 0.
        # q_target = [1, 0, 0] 表示這個記憶中的 r+gamma*maxQ(s_) = 1, 而且不管在 s_ 上我們?nèi)×四膫€ action,
        # 我們都需要對應上 q_eval 中的 action 位置, 所以就將 1 放在了 action 0 的位置.

        # 下面是為了達到上面說的目的, 不過為了更方面讓程序運算, 達到目的的過程有點不同.
        # 是將 q_eval 全部賦值給 q_target, 這時 q_target-q_eval 全為 0,
        # 不過 我們再根據(jù) batch_memory 當中的 action 這個 column 來給 q_target 中的對應的 memory-action 位置來修改賦值.
        # 使新的賦值為 reward + gamma * maxQ(s_), 這樣 q_target-q_eval 就可以變成我們所需的樣子.
        # change q_target w.r.t q_eval's action
        q_target = q_eval.copy()

        batch_index = np.arange(self.batch_size, dtype=np.int32)
        eval_act_index = batch_memory[:, self.n_features].astype(int)
        reward = batch_memory[:, self.n_features + 1]

        q_target[batch_index, eval_act_index] = reward + self.gamma * np.max(q_next, axis=1)

        # train eval network
        _, self.cost = self.sess.run([self._train_op, self.loss],
                                     feed_dict={self.s: batch_memory[:, :self.n_features],
                                                self.q_target: q_target})
        self.cost_his.append(self.cost)

        # increasing epsilon
        self.epsilon = self.epsilon + self.epsilon_increment if self.epsilon < self.epsilon_max else self.epsilon_max
        self.learn_step_counter += 1

3. 交互過程
   DQN 與環(huán)境交互的過程總體與Q-Learning一致，僅僅增加了記憶存儲的過程，這與前邊提到的 “Q-Leaning 方法基于當前策略進行交互和改進，每一次模型利用交互生成的數(shù)據(jù)進行學習，學習后的樣本被直接丟棄” 是一致的。

from maze_env import Maze
from RL_brain import DeepQNetwork

def run_maze():
    step = 0
    for episode in range(1000):
        # initial observation
        observation = env.reset()

        while True:
            # fresh env
            env.render()

            # RL choose action based on observation
            action = RL.choose_action(observation)

            # RL take action and get next observation and reward
            observation_, reward, done = env.step(action)

            RL.store_transition(observation, action, reward, observation_)

            if (step > 200) and (step % 5 == 0):
                RL.learn()

            # swap observation
            observation = observation_

            # break while loop when end of this episode
            if done:
                break
            step += 1

    # end of game
    print('game over')
    env.destroy()


if __name__ == "__main__":
    # maze game
    env = Maze()
    RL = DeepQNetwork(env.n_actions, env.n_features,
                      learning_rate=0.01,
                      reward_decay=0.9,
                      e_greedy=0.9,
                      replace_target_iter=200,
                      memory_size=20000,
                      output_graph=True
                      )
    env.after(100, run_maze)
    env.mainloop()
    RL.plot_cost()

最后展示一下運行效果及代價函數(shù)值的變化情況，可以看出，整體呈下降趨勢，但仍存在明顯的波動，這是因為 DQN 中的 input 數(shù)據(jù)是一步步改變的, 而且會根據(jù)學習情況, 獲取到不同的數(shù)據(jù). 所以這并不像一般的監(jiān)督學習, DQN 的 cost 曲線就有所不同了。

DQN 效果

代價函數(shù)值

獲取完整代碼請點擊這里，感謝莫煩的貢獻。

參考資料

[1] Barto A G, Sutton R S. Reinforcement Learning: An Introduction.MIT press, 2018.
[2] 馮超著 強化學習精要：核心算法與TensorFlow實現(xiàn). ----北京：電子工業(yè)出版社 2018.
[3] 郭憲，方純勇編著 深入淺出強化學習：原理入門. ----北京：電子工業(yè)出版社 2018.
[4] 邱錫鵬著，神經(jīng)網(wǎng)絡與深度學習. https://nndl.github.io/ 2019.

人生天地間，忽如遠行客。----《古詩十九首》