增強學習入門1——基本概念

本文收錄在無痛的機器學習第二季目錄。

前言

這個系列是我和InfoQ合作的《無痛的增強學習入門》系列，現轉載到知乎專欄中。首發地址在：無痛的增強學習入門：基本概念篇，歡迎圍觀。

作為機器學習中十分重要的一支，增強學習在這些年取得了十分令人驚喜的成績，這也使得越來越多的人加入到學習增強學習的隊伍當中。增強學習的知識和內容與經典監督學習、非監督學習相比並不容易，而且可解釋的小例子比較少，本系列將向各位讀者簡單介紹其中的基本知識，並以一個小例子貫穿其中。

作為一個85後（暴露年齡），在年幼的時候我曾經接觸一種遊戲，這種遊戲是一種棋類遊戲，有一個棋盤，棋盤上有許多小格子，還有幾個棋子和一個骰子。棋盤的樣子大概是這樣的：

圖1 蛇棋的棋盤

這種棋被稱為蛇棋，他的玩法大概是這樣的：

1. 幾個小夥伴一起玩，每個人有一個棋子，大家一開始把棋子放在圖中標為「1」的格子中；
2. 每個人依次擲骰子，根據骰子的點數將自己的棋子向前行進相應的步數。如果現在我的棋子在「1」處，並且投擲出了「4」，那麼我的棋子就可以到達「5」的位置；
3. 棋盤上有一些梯子，這些梯子十分重要，它的兩邊將棋盤上的兩個格子相連，這樣如果棋子落在其中的一個各自上時，就會自動走到梯子對應的另一個格子中。對於上面的例子，如果我的棋子在「1」處，並且投擲出2，那麼我的棋子將到達「3」，由於「3」的位置有梯子，我將直接前進到梯子的另一段——「20」；
4. 最終的目標是到達「100」這個格子，如果在到達時投擲的數字超過了100，那麼棋子將首先到達100，剩餘的步數將反向前進。比方說我的棋子在「99」這個位置，如果我投擲出了「3」，那麼我將先前進1步到達100，然後再後退2步，這樣就到達了「98」。悲劇的是「98」處還有一個梯子，於是我的棋子將順著梯子到達「81」。

從現在的角度來看，這個遊戲的可玩性其實比較有限，遊戲中也沒有那麼多跌宕起伏的情節，但是它確實是那一代人的一大娛樂。由此引出的一系列遊戲棋——尤其是大富翁系列的遊戲棋，真的影響了很多人。

說了那麼多遊戲規則和情懷的事情，下面就將來到正題：這東西和增強學習有什麼關係？

蛇棋的遊戲定義

實際上這個遊戲就是增強學習的一個小案例。我們先不介紹增強學習的一些抽象概念，但從這個遊戲入手。蛇棋中的棋盤和遊戲規則是既定的，勝利規則也是既定的，這些內容幫助玩家建立對這個遊戲的世界觀，以及遊戲的目標。

那麼遊戲的參與形式呢？就是擲骰子。實際上擲骰子這個問題是一個值得大書特書的問題，君不見，有些人擲骰子的時候要氣沉丹田，有的要大喝一聲，有的小心翼翼……尤其一個賭局上，每個人擲骰子的模樣都不相同。對於這些不同的擲骰子方式，我們顯然可以認為不同方式下骰子各個面出現的概率是不同的。為什麼？這個就不用細談了吧……

所以遊戲中唯一決定玩家命運的操作出現了——擲骰子的手法。這裡我們運用一點抽象，讓玩家的手法暫時變成2種手法：一種可以均勻投擲出1～6這6個數字，另一種可以均勻投擲出1～3這3個數字。這樣玩家相當於有了兩個選擇。

接下來看看遊戲的最終獲勝條件。一般來說遊戲是多人一起玩的（一個人玩是什麼鬼……），那麼誰先到達「100」，誰就獲得了勝利。換句話說，用最少的投擲次數到達「100」是每一個玩家的目標。為了達到這個目標，玩家最好能儘可能地「乘坐」更多的梯子上升，這樣可以快速到達終點。一般來說遊戲喜歡用一些數字或得分的形式記錄玩家的表現，我們這裡做一個約定，玩家每走一步，將獲得-1分，也就是扣一分，到達重點後，將得到100分。這樣先到達重點的玩家一定會有最高分，也就相當於TA獲得勝利。

聽完了上面的描述，「精通」開發的你一定忍不住想把上面的描述變成代碼，於是我們就有了下面的這段代碼：

import numpy as npclass Snake: def __init__(self, ladder_num, dice_ranges): self.ladder_num = ladder_num self.dice_ranges = dice_ranges self.ladders = dict(np.random.randint(1, 100, size=(ladder_num, 2))) reverse_ladders = [(v, k)for k,v in self.ladders.items()] for item in reverse_ladders: self.ladders[item[0]] = item[1] print ladders info: print self.ladders print dice ranges: print dice_ranges def start(self): self.pos = 1 def action(self, act): step = np.random.randint(1, self.dice_ranges[act] + 1) self.pos += step if self.pos == 100: return 100, -1 elif self.pos > 100: self.pos = 200 - self.pos if self.pos in self.ladders: self.pos = self.ladders[self.pos] return -1, self.posif __name__ == "__main__": env = Snake(10, [3,6]) env.start() while Ture: reward, state = env.action(1) print reward, state if state == -1: break

這個代碼主要定義了一個蛇棋類，其中包含3個函數：

• 構造函數：需要傳人兩個參數——梯子數量和骰子數量。我們用一個dict存儲梯子相連的兩個格子的關係，用一個list保存可能的骰子的可投擲最大值。
• start()：將pos設置為「1」，也就是開始遊戲
• action()：完成一次投擲，參數act表示玩家將採用何種手法。完成位置的更新後，函數將返回這一輪玩家的得分（-1或100）和玩家的最新位置

代碼中的main函數用於展示一個蛇棋的遊戲過程，運行如下所示：

ladders info:{2: 99, 67: 73, 54: 82, 73: 67, 10: 58, 43: 86, 45: 95, 93: 23, 50: 59, 17: 92, 82: 54, 99: 2, 86: 43, 23: 93, 26: 73, 59: 50, 92: 17, 58: 10, 95: 45}dice ranges:[3, 6]-1 7-1 9-1 15-1 19…………(以下省略若干中間結果)-1 73-1 77-1 83-1 88-1 90-1 96-1 97100 -1

最終玩家完成了一次遊戲，在這次遊戲中，玩家共進行了294次投擲才到達重點，最終得分-193分。從上面的梯子情況可以看出，有些梯子真的容易讓人絕望：

99: 295: 4592: 17

玩家多次掉入這種陷阱，才導致遊戲進行了這麼長時間。

作為好勝心很強的我們，肯定在想，剛才的遊戲中，玩家只使用了一種手法啊，要是兩種手法並用，甚至更多的手法並用，一定能提前完成遊戲的。這就要涉及要一些策略了。

增強學習的概念

在經典的增強學習中，玩家作為Agent，要和環境Environment做一系列的交互。在每一個時刻，環境將給出一個當前的狀態，玩家將根據狀態做出決策，這個決策會影響環境，使得環境發生一定的改變，改變後的環境會反饋給玩家一個「獎勵」Reward，這個獎勵可以是正向的，也可以是負向的，它用於反饋用戶當前的表現。環境同時還會反饋下一時刻的狀態給玩家，這樣玩家就可以做新一輪的決策了。這個過程由圖2所示。

圖2 增強學習的過程表示

看過了蛇棋，相信大家很容易就把蛇棋的遊戲過程套用到上面流程中，這裡就不重複一遍了，只是將圖2中的關鍵實體做一個對應：

• Agent：玩家
• policy：策略，簡單來說就選擇哪種投擲手法
• action：策略最終決定的行動，具體的投擲手法
• Environment：棋盤，遊戲規則，獲勝策略等一籃子內容
• state transition：玩家投擲完骰子後，棋子的位置將發生變化，也就是狀態的變化
• state，reward：棋盤變化後，新的棋子位置將發送給玩家，同時包含一個獎勵：-1或者100

看到這裡，我們可以把最終目標進行重新定義：如何確保在遊戲結束前獲得的reward總和最大。如果用表示t時刻的獎勵，遊戲將在第T輪結束，那麼遊戲的目標就是最大化下面的公式：表示t時刻的獎勵，遊戲將在第T輪結束，那麼遊戲的目標就是最大化下面的公式：

那麼該如何最大化呢？我們能否求出最優的「策略」來？下次我們將繼續介紹。

廣告時間

《深度學習輕鬆學：核心演算法與視覺實踐》，感謝支持！

我愛機器學習13群：550972653，歡迎加入～