附代碼!一文看懂強化學習中的蒙特卡羅學習法

當聽到“強化學習”這個詞時,你的第一反應是什麼呢?大多數人認為它涉及過多的數學內容所以過於複雜,但強化學習其實是一個極有魅力的學習領域。這篇文章把強化學習相關的技術拆分為了幾個概念,便於大家理解。

你一定聽過OpenAI和DeepMind這兩大行業領先的AI公司,它們在AI研究領域取得了重大成果。在一款極受歡迎且操作複雜的戰鬥競技類遊戲——Dota2中,一隊OpenAI的電腦玩家擊敗了遊戲中的業餘玩家。


附代碼!一文看懂強化學習中的蒙特卡羅學習法


所以有人猜想:運用動態規劃編寫一個電腦機器人來應對像Dota2一樣複雜的工作是否可行呢?

很遺憾,答案是不可行。遊戲中有成百上億種狀態,要想收集所有有關Dota2的細節是不可能的。這時候就需要進入強化學習或更具體地來說——無模型學習領域。

蒙特卡羅學習法的基本原理是一個重要概念:當你缺乏對環境的先驗信息,基本上只能靠經驗收集信息時,就可以用到蒙特卡洛學習法。本文將通過使用Python中的OpenAI Gym工具包來實現這一方法。

TIPS:如果你剛剛接觸到這個領域或者需要快速地瞭解一些關於強化學習的術語,強烈推薦閱讀以下資料,有助於你在本篇文章中儘可能地學到更多東西。

1. Simple Beginner’s guide to Reinforcement Learning & its implementation

2. Nuts & Bolts of Reinforcement Learning: Model Based Planning using Dynamic Programming

3. Reinforcement Learning Guide: Solving the Multi-Armed Bandit Problem from Scratch in Python

附代碼!一文看懂強化學習中的蒙特卡羅學習法


1.有模型學習vs無模型學習


動態規劃(或更準確的說法,有模型學習)是用於解決事先已知潛藏環境的問題,強化學習則是從遊戲經驗中學習。然而在所有的動態規劃的算法中,我們都沒有真正地玩過這個遊戲或者體驗過這個環境,因為我們擁有一個完整的環境模型,它包括了所有狀態轉換的概率。

但是在現實生活中,大多數情況下,一個狀態到另一個狀態的轉換率(或者所謂的環境模型)都是未知的,它甚至不一定遵循馬可夫性質。


附代碼!一文看懂強化學習中的蒙特卡羅學習法



比方說,我們想訓練一個電腦機器人學會國際象棋,需要將國際象棋環境轉換為MDP(馬可夫決策過程)。

根據每個棋子不同的位置,這個環境存在超過1050 種不同的狀態以及成千上萬種棋子下一步的可能性。這個環境模型幾乎是不可能被設計出來的。

有一種潛在的解決方法是不停地進行國際象棋的對局,每局比賽結束後,獲得勝利和失敗相應的回報(reward),這就是所說的從經驗中學習。

附代碼!一文看懂強化學習中的蒙特卡羅學習法


2.蒙特卡羅方法使用的實例


任何通過生成隨機數並觀察數據是否服從某個性質或某些性質的方法都可以被歸為蒙特卡洛方法。

讓我們來做一個有趣的實驗:嘗試用筆和紙來計算出π的值。首先,先繪製一個單位長度的正方形和四分之一個以單位長度為半徑的圓。現在一個機器人助手C3PO幫助我們,它的任務是儘可能地在正方形上隨機點3000下並得到如下表格:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



C3PO將計算在圓形中的點的總和,那麼π的值通過如下計算得到:

N是圖形圈中點的總數,我們要做的只是計算隨機落在圓形中的點然後通過它和N的比值就計算出了π的近似值。

附代碼!一文看懂強化學習中的蒙特卡羅學習法


3.蒙特卡羅強化學習


使用蒙特卡洛方法的強化學習可以直接從經驗中學習,不需要任何MDP轉化率的先驗信息。其中隨機的要素是return或reward。(return是reward總和的平均數。)

TIPS:蒙特卡洛強化學習只能用於情節性的MDP,原因則是在我們計算回報之前任務必須終止。我們並不是在每個動作結束以後進行數據的更新,而是在每個情節(episode)結束以後進行更新。它採用的是最簡單的概念——所得的值來自於每個狀態所有樣本軌跡的平均回報(mean return)。

每一個狀態都是一個獨立的多臂老虎機問題,蒙特卡羅強化學習的想法就是讓所有的多臂老虎機以最佳狀態同時運行。

和動態規劃類似,蒙特卡洛強化學習也有策略估計(為隨機的策略確定值函數)和策略改進(找到最佳策略)的功能。那麼,如何使用這兩個方法呢?

3.1 蒙特卡羅估計


這個方法的目的是在π策略下從階段性經驗中學習值函數。回想之前提到的,return是所有狀態平均reward的總和:

S1, A1, R2, ….Sk ~ pi


同樣,之前提到值函數是預計的累積return:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



我們可以簡單地通過樣本的相加除以樣本的總數來估計任何期望值:

  • i – Episode index
  • s – Index of state


問題是如何得到那些樣本return?對於這點,需要先進行一組episode併產出結果。

運行完每一個episode,我們都會得到一系列的狀態和reward。然後從這些reward中,我們可以通過定義來計算return,而這正是未來所有reward的總和。

蒙特卡羅的第一次遍歷: 平均returns 是指第一次在episode出現的狀態。

下面是這個算法的具體步驟:

  1. 將策略與狀態值函數初始化
  2. 根據現有策略開始運行episode
  3. 1.記錄實驗中遇到的所有狀態
  4. 在 2.1中選取一個狀態
  5. 1.記錄此狀態第一次出現後的return
  6. 2.算出所有return的平均值
  7. 3.將所得return平均數設為狀態的值
  8. 重複第三步
  9. 重複2-4步直到得到滿意的結果


全遍歷蒙特卡羅方法: 將每一次s – Index of state在episode中遍歷,都取回報的平均數:

對於這個算法,我們只需將步驟3.1改為“將每次該狀態出現的return記錄下來”。

下面我們來看一個樣本實例來更好地理解這個概念。假設一個環境擁有兩種狀態——A和B。讓我們觀察這兩個樣本實驗:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



A+3=>A表示從狀態A到狀態A的轉換附帶的reward是3。讓我們同時用這兩種方法確定值函數:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



增量式平均數

這個方法使得將平均return轉換為增量式更新變得非常方便,這樣平均值就可以隨著實驗的狀態return更新,讓我們可以掌控每次實驗得到的進展。我們已經知道這個方法可以幫助我們解決多臂老虎機的問題。

將v(s)在每個實驗結束後逐漸增加,每個狀態St帶著return Gt:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



在非平穩問題中,這個方法可以用作記錄連續的平均數,比如:

V(St) ← V(St) + α (Gt − V(St))

3.2 蒙特卡羅控制


蒙特卡羅控制和動態規劃類似,只要我們確定一個隨機策略的值函數,關鍵的任務就只剩下運用蒙特卡羅方法找到最佳策略。

回想一下DP(Date Processing 數據處理)中策略改進的公式,它需要下列所示的環境模型:


附代碼!一文看懂強化學習中的蒙特卡羅學習法



這個等式通過找到能夠最大化reward的行動來確定最佳策略。然而在這裡要注意一下:它採用的狀態轉換率在無模型學習中是未知的。

既然我們不知道狀態轉換率p(s’,r/s,a),我們就不能像DP一樣做預測搜索,因此所有的信息都是通過運行episode的經驗或探索環境得來的。

策略改進就是儘可能地使策略與現存的值函數接近。這樣我們就可以得到一個行動值函數,我們就不需要模型來構建一個貪心策略了。


附代碼!一文看懂強化學習中的蒙特卡羅學習法


如果大多數行動並沒有被充分地發掘的話,一個貪心策略(就像剛才提到的)總會傾向於某些行動。以下有兩個解決方案:

蒙特卡羅探索起點

在該算法中,所有狀態動作的起始對概率都大於零。這就保證了所做的每個episode都會將主體帶到新的狀態,然後實現對環境的更多的探索。


附代碼!一文看懂強化學習中的蒙特卡羅學習法


蒙特卡羅epsilon-Soft

那如果一個環境是單一的起點呢(如國際象棋)?探索起點在這種情況下並不適用。回想我們剛剛提到的多臂老虎機的問題,我們講過epsilon-greedy approach。

為了能夠持續地探索,所有行為都要和概率大於0緊密相連——epsilon可能會選擇能夠得到最大行動值的行動或隨機選擇一個行動。


附代碼!一文看懂強化學習中的蒙特卡羅學習法


現在我們瞭解了蒙特卡羅控制和估計的基礎,讓我們將算法運用到Python中。我們將從OpenAI Gym 工具包中導入冰湖環境。

附代碼!一文看懂強化學習中的蒙特卡羅學習法


4.蒙特卡羅在Python中的實際運用

冰湖環境


玩家會控制一個人物在網格里的移動。網格里一些格子是可行走的,而其他格子則導致玩家落入水中。此外,玩家的移動方向是不確定的,只是部分取決於所選擇的方向。玩家找到到達目的地的路徑就能獲得獎勵。

這個遊戲表面是由如下格子構成的:

(S:起點,安全),(F: 冰凍區域,安全),(H: 洞, 摔死), (G: 目的地)

這個遊戲的規則就是,從起點開始避開所有的洞,只走冰凍的格子然後到達終點。

首先,我們先定義一些輔助函數來設置蒙特卡羅算法。

創建環境

import gym

import numpy as np

import operator

from IPython.display import clear_output

from time import sleep

import random

import itertools

import tqdm

tqdm.monitor_interval = 0


隨機策略函數

def create_random_policy(env):

policy = {}

for key in range(0, env.observation_space.n):

current_end = 0

p = {}

for action in range(0, env.action_space.n):

p[action] = 1 / env.action_space.n

policy[key] = p

return policy


狀態行動值儲存庫

def create_state_action_dictionary(env, policy):

Q = {}

for key in policy.keys():

Q[key] = {a: 0.0 for a in range(0, env.action_space.n)}

return Q


遊戲運行函數

def run_game(env, policy, display=True):

env.reset()

episode = []

finished = False

while not finished:

s = env.env.s

if display:

clear_output(True)

env.render()

sleep(1)

timestep = []

timestep.append(s)

n = random.uniform(0, sum(policy[s].values()))

top_range = 0

for prob in policy[s].items():

top_range += prob[1]

if n < top_range:

action = prob[0]

break

state, reward, finished, info = env.step(action)

timestep.append(action)

timestep.append(reward)

episode.append(timestep)

if display:

clear_output(True)

env.render()

sleep(1)

return episode


測試策略並顯示勝利百分比的函數


def test_policy(policy, env):

wins = 0

r = 100

for i in range(r):

w = run_game(env, policy, display=False)[-1][-1]

if w == 1:

wins += 1

return wins / r


蒙特卡羅估計和控制第一遍歷

def monte_carlo_e_soft(env, episodes=100, policy=None, epsilon=0.01):

if not policy:

policy = create_random_policy(env) # Create an empty dictionary to store state action values

Q = create_state_action_dictionary(env, policy) # Empty dictionary for storing rewards for each state-action pair

returns = {} # 3.

for _ in range(episodes): # Looping through episodes

G = 0 # Store cumulative reward in G (initialized at 0)

episode = run_game(env=env, policy=policy, display=False) # Store state, action and value respectively

# for loop through reversed indices of episode array.

# The logic behind it being reversed is that the eventual reward would be at the end.

# So we have to go back from the last timestep to the first one propagating result from the future.

for i in reversed(range(0, len(episode))):

s_t, a_t, r_t = episode[i]

state_action = (s_t, a_t)

G += r_t # Increment total reward by reward on current timestep

if not state_action in [(x[0], x[1]) for x in episode[0:i]]: #

if returns.get(state_action):

returns[state_action].append(G)

else:

returns[state_action] = [G]

Q[s_t][a_t] = sum(returns[state_action]) / len(returns[state_action]) # Average reward across episodes

Q_list = list(map(lambda x: x[1], Q[s_t].items())) # Finding the action with maximum value

indices = [i for i, x in enumerate(Q_list) if x == max(Q_list)]

max_Q = random.choice(indices)

A_star = max_Q # 14.

for a in policy[s_t].items(): # Update action probability for s_t in policy

if a[0] == A_star:

policy[s_t][a[0]] = 1 - epsilon + (epsilon / abs(sum(policy[s_t].values())))

else:

policy[s_t][a[0]] = (epsilon / abs(sum(policy[s_t].values())))


return 策略

現在使用下列算法解決一個8x8的冰湖環境問題然後查看獎勵。


附代碼!一文看懂強化學習中的蒙特卡羅學習法



運行這個遊戲50000次,我們可以得到0.9分,如果運行更多次,最終我們可以得到最佳方案。

附代碼!一文看懂強化學習中的蒙特卡羅學習法


5.總結

蒙特卡羅學習的內容還有很多,此外還有另一套算法稱為無策略蒙特卡羅方法。無策略方法是通過使用另一個策略中的return來嘗試找出最佳策略。

在本文中討論的方法都是基於策略的,就如同一邊工作一邊學習一樣。相反,無策略方法就像通過看著別人做從而學習。

附代碼!一文看懂強化學習中的蒙特卡羅學習法



編譯組:何卿妍、韋振琛

相關鏈接:

https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/

如需轉載,請後臺留言,遵守轉載規範

相關推薦

推薦中...