基于模型的學(xué)習(xí)vs無模型學(xué)習(xí)

聽到“強(qiáng)化學(xué)習(xí)”，你首先想到的是什么？最常見的反應(yīng)是有太多數(shù)學(xué)知識(shí)、非常復(fù)雜。但是我認(rèn)為這是一個(gè)非常迷人的研究領(lǐng)域，在今天的文章中，我會(huì)把其中的技術(shù)分解成多種易于理解的概念。

你一定聽說過OpenAI和DeepMind，這兩家機(jī)構(gòu)在強(qiáng)化學(xué)習(xí)領(lǐng)域都作出了重要進(jìn)步。OpenAI的強(qiáng)化學(xué)習(xí)智能體可以在Dota 2中擊敗人類對(duì)手。

你是否認(rèn)為我們用動(dòng)態(tài)編程可以打造一個(gè)像Dota 2一樣復(fù)雜的機(jī)器人呢？

很不幸，答案是否定的。因?yàn)镈ota 2中的狀態(tài)有很多，要收集所有具體狀態(tài)幾乎不可能。所以我們開始采用強(qiáng)化學(xué)習(xí)或者更具體的無模型學(xué)習(xí)。

在這篇文章中，我們要試著理解蒙特卡羅學(xué)習(xí)的基本概念。當(dāng)沒有有關(guān)環(huán)境的先驗(yàn)信息時(shí)，所有的信息都從經(jīng)驗(yàn)中獲取，此時(shí)就要用到蒙特卡羅學(xué)習(xí)方法。在這一過程中，我們會(huì)用到OpenAI Gym工具包，并且用Python實(shí)現(xiàn)這一方法。

基于模型的學(xué)習(xí) vs 無模型學(xué)習(xí)

我們知道，動(dòng)態(tài)編程適用于解決已知環(huán)境基礎(chǔ)模型的問題（更準(zhǔn)確地說是基于模型的學(xué)習(xí)）。強(qiáng)化學(xué)習(xí)指的是從玩游戲的經(jīng)驗(yàn)中學(xué)習(xí)，但是，我們卻從未在動(dòng)態(tài)編程中玩過游戲，或者體驗(yàn)環(huán)境。我們有關(guān)于環(huán)境的完全模型，其中包含了所有狀態(tài)轉(zhuǎn)換的可能。

但是，在大多數(shù)現(xiàn)實(shí)生活情境中，從一種狀態(tài)轉(zhuǎn)換到另一種狀態(tài)的可能性是無法提前預(yù)知的。

假設(shè)我們想訓(xùn)練一個(gè)機(jī)器人學(xué)習(xí)下象棋，將棋盤環(huán)境的變化看作是馬爾科夫決策過程（MDP）。

現(xiàn)在根據(jù)棋子的位置，環(huán)境可以有很多種狀態(tài)（超過1050），另外還會(huì)有許多可能做出的動(dòng)作。這種環(huán)境下的模型幾乎無法設(shè)計(jì)出來。

一種可能的解決方法是重復(fù)地下棋，接收到可以獲勝的積極獎(jiǎng)勵(lì)以及會(huì)輸?shù)舯荣惖南麡O獎(jiǎng)勵(lì)。這就是從經(jīng)驗(yàn)中學(xué)習(xí)的過程。

蒙特卡羅方法案例

通過生成合適的隨機(jī)數(shù)，并觀察數(shù)字遵循一定特征的，這種方法都可以看作是蒙特卡羅方法。

在下面的案例中，我們?cè)囍霉P和紙找到π的值。首先畫一個(gè)正方形，然后以原點(diǎn)為圓心，正方形邊長為半徑畫圓?，F(xiàn)在我們用C3PO機(jī)器人在正方形內(nèi)隨機(jī)畫點(diǎn)，一共有3000個(gè)點(diǎn)，結(jié)果如下：

所以，π的值用以下公式計(jì)算：

其中N是紅點(diǎn)落入圓圈中的次數(shù)。可以看到，我們通過計(jì)算隨機(jī)點(diǎn)的比例估算出了π的值。

蒙特卡羅強(qiáng)化學(xué)習(xí)

用于強(qiáng)化學(xué)習(xí)的蒙特卡羅方法是直接從經(jīng)驗(yàn)中學(xué)習(xí)，沒有先驗(yàn)知識(shí)。這里的隨機(jī)因素就是返回結(jié)果或獎(jiǎng)勵(lì)。

需要注意的是，這種方法只能應(yīng)用于偶爾發(fā)生的馬爾科夫決策過程。原因是在計(jì)算任意返回之前，這一episode就要停止。我們并不在每次動(dòng)作結(jié)束后就更新，而是在每個(gè)episode結(jié)束后更新。它的方法很簡單，即取每個(gè)狀態(tài)所有采樣軌跡的平均回報(bào)。

和動(dòng)態(tài)編程類似，這里有一種策略評(píng)估和策略改進(jìn)方法，我們將在下面兩個(gè)部分進(jìn)行講解。

蒙特卡羅方法評(píng)估

這里的目標(biāo)是學(xué)習(xí)在策略pi的訓(xùn)練下得到的價(jià)值函數(shù)vpi(s)。返回的值是總體折扣獎(jiǎng)勵(lì)：

同時(shí)價(jià)值函數(shù)是預(yù)期回報(bào)：

我們可以通過添加樣本并除以總樣本數(shù)來估計(jì)預(yù)期值：

其中i表示episode指數(shù)，s表示狀態(tài)指數(shù)。

問題時(shí)我們要如何得到這些樣本的返回值？為了做到這一點(diǎn)，我們需要運(yùn)行多個(gè)episode來生成它們。

對(duì)每次運(yùn)行的episode，我們會(huì)有一系列狀態(tài)和獎(jiǎng)勵(lì)。對(duì)于獎(jiǎng)勵(lì)，我們可以用定義計(jì)算返回值，是左右未來獎(jiǎng)勵(lì)的總和。

以下是算法每一步的內(nèi)容：

對(duì)策略、價(jià)值函數(shù)進(jìn)行初始化

根據(jù)當(dāng)前策略生成一次episode并跟蹤這一過程中遇到的狀態(tài)

從上一步中選擇一種狀態(tài)。

當(dāng)這一狀態(tài)第一次出現(xiàn)時(shí)，將接收到的返回值添加到列表中

對(duì)所有返回值進(jìn)行平均

計(jì)算平均值時(shí)設(shè)定狀態(tài)的值

4. 重復(fù)步驟3

這里我們重點(diǎn)講解步驟3.1，“添加收到的返回值到列表中”。

用一個(gè)簡單例子理解這一概念，假設(shè)這里有一種環(huán)境，其中包含了兩種狀態(tài)A和B。以下是兩次樣本的episode：

A+3=＞A表示從狀態(tài)A轉(zhuǎn)移到狀態(tài)A需要獎(jiǎng)勵(lì)+3.

蒙特卡羅控制

和動(dòng)態(tài)編程類似，一旦我們有了隨機(jī)策略中的價(jià)值函數(shù)，重要的任務(wù)就是用蒙特卡羅尋找優(yōu)化策略。

用模型改進(jìn)策略所需的公式如下：

該公式通過尋找可以將獎(jiǎng)勵(lì)最大化的動(dòng)作，對(duì)策略進(jìn)行了優(yōu)化。但是，這里的重點(diǎn)是用了遷移概率，這在無模型學(xué)習(xí)中是無法獲取的。

因?yàn)槲覀儾恢罓顟B(tài)遷移概率p(s’,r/s,a)，我們不能提前進(jìn)行搜索。于是，所有信息都是通過玩游戲或環(huán)境探索得來的。

策略的改進(jìn)是根據(jù)當(dāng)前價(jià)值函數(shù)讓策略變得貪婪，在這種情況下，我們有了一個(gè)動(dòng)作-價(jià)值函數(shù)，所以在建立貪婪策略時(shí)不需要模型。

如果大多數(shù)動(dòng)作并沒有得到具體研究，一種貪婪策略只會(huì)支持一個(gè)特定動(dòng)作。解決方法有兩種：

Exploring starts

在這種算法中，所有狀態(tài)的動(dòng)作對(duì)是不可能成為起始對(duì)的，這就保證了每個(gè)episode都會(huì)帶領(lǐng)智能體到新狀態(tài)中，所以智能體會(huì)對(duì)環(huán)境有更多了解和探索。

epsilon-Soft

如果環(huán)境中只有一個(gè)起始點(diǎn)該怎么辦（例如棋盤類游戲）？這個(gè)時(shí)候探索起始點(diǎn)就沒有意義了，這里就要用到?-貪婪方法。

想保證探索繼續(xù)進(jìn)行，最簡單的方法就是以非零概率嘗試所有動(dòng)作。?選擇的動(dòng)作可以將價(jià)值函數(shù)最大化，并且隨機(jī)選擇動(dòng)作。

現(xiàn)在我們理解了基礎(chǔ)的蒙特卡羅控制和預(yù)測，接下來就用Python實(shí)現(xiàn)這些算法吧。我們會(huì)導(dǎo)入OpenAI Gym中的冰凍湖環(huán)境進(jìn)行演示。

用Python實(shí)現(xiàn)蒙特卡羅方法

智能體控制人物在網(wǎng)格中的移動(dòng)，其中一些是可以移動(dòng)的，另一些可能會(huì)讓智能體掉入水中。另外，智能體的移動(dòng)方向是不確定的，如果智能體找到正確的路就能獲得獎(jiǎng)勵(lì)。

S：起始點(diǎn)，安全；F：冰凍湖面，安全；H：洞，危險(xiǎn)；G：目標(biāo)點(diǎn)

游戲的任務(wù)就是讓智能體從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)，不要掉進(jìn)洞里。這里附上OpenAI Gym的安裝細(xì)節(jié)和文件：gym.openai.com/docs/，下面就開始用Python實(shí)現(xiàn)吧！

首先，我們要定義集中函數(shù)設(shè)置蒙特卡羅算法。

創(chuàng)建環(huán)境

import gym

import numpy as np

importoperator

fromIPython.display import clear_output

from time import sleep

import random

import itertools

import tqdm

tqdm.monitor_interval = 0

隨機(jī)策略函數(shù)

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

存儲(chǔ)狀態(tài)動(dòng)作值的詞典

def create_state_action_dictionary(env, policy):

Q = {}

for key in policy.keys():

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

return Q

運(yùn)行episode的函數(shù)

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

env.reset()

episode = []

finished = False

whilenot 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

測試策略和計(jì)算獲勝概率的函數(shù)

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

首次蒙特卡羅預(yù)測和控制

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

ifnot 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

ifnot 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 policy

完成后運(yùn)行算法并檢查獎(jiǎng)勵(lì)：

結(jié)語

蒙特卡羅學(xué)習(xí)到此并未結(jié)束，除此之外還有另一類稱為“離線蒙特卡羅”的方法，這種方法用另一種策略生成的返回值學(xué)習(xí)優(yōu)化策略。

本文提到的是在線方法，類似在做中學(xué)，而離線方法更強(qiáng)調(diào)的是看別人的示范從中學(xué)習(xí)。