基于模型的學習vs無模型學習

聽到“強化學習”，你首先想到的是什么？最常見的反應是有太多數學知識、非常復雜。但是我認為這是一個非常迷人的研究領域，在今天的文章中，我會把其中的技術分解成多種易于理解的概念。

你一定聽說過OpenAI和DeepMind，這兩家機構在強化學習領域都作出了重要進步。OpenAI的強化學習智能體可以在Dota 2中擊敗人類對手。

你是否認為我們用動態(tài)編程可以打造一個像Dota 2一樣復雜的機器人呢？

很不幸，答案是否定的。因為Dota 2中的狀態(tài)有很多，要收集所有具體狀態(tài)幾乎不可能。所以我們開始采用強化學習或者更具體的無模型學習。

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

基于模型的學習 vs 無模型學習

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

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

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

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

一種可能的解決方法是重復地下棋，接收到可以獲勝的積極獎勵以及會輸掉比賽的消極獎勵。這就是從經驗中學習的過程。

蒙特卡羅方法案例

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

在下面的案例中，我們試著用筆和紙找到π的值。首先畫一個正方形，然后以原點為圓心，正方形邊長為半徑畫圓?，F在我們用C3PO機器人在正方形內隨機畫點，一共有3000個點，結果如下：

所以，π的值用以下公式計算：

其中N是紅點落入圓圈中的次數。可以看到，我們通過計算隨機點的比例估算出了π的值。

蒙特卡羅強化學習

用于強化學習的蒙特卡羅方法是直接從經驗中學習，沒有先驗知識。這里的隨機因素就是返回結果或獎勵。

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

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

蒙特卡羅方法評估

這里的目標是學習在策略pi的訓練下得到的價值函數vpi(s)。返回的值是總體折扣獎勵：

同時價值函數是預期回報：

我們可以通過添加樣本并除以總樣本數來估計預期值：

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

問題時我們要如何得到這些樣本的返回值？為了做到這一點，我們需要運行多個episode來生成它們。

對每次運行的episode，我們會有一系列狀態(tài)和獎勵。對于獎勵，我們可以用定義計算返回值，是左右未來獎勵的總和。

以下是算法每一步的內容：

對策略、價值函數進行初始化

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

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

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

對所有返回值進行平均

計算平均值時設定狀態(tài)的值

4. 重復步驟3

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

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

A+3=＞A表示從狀態(tài)A轉移到狀態(tài)A需要獎勵+3.

蒙特卡羅控制

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

用模型改進策略所需的公式如下：

該公式通過尋找可以將獎勵最大化的動作，對策略進行了優(yōu)化。但是，這里的重點是用了遷移概率，這在無模型學習中是無法獲取的。

因為我們不知道狀態(tài)遷移概率p(s’,r/s,a)，我們不能提前進行搜索。于是，所有信息都是通過玩游戲或環(huán)境探索得來的。

策略的改進是根據當前價值函數讓策略變得貪婪，在這種情況下，我們有了一個動作-價值函數，所以在建立貪婪策略時不需要模型。

如果大多數動作并沒有得到具體研究，一種貪婪策略只會支持一個特定動作。解決方法有兩種：

Exploring starts

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

epsilon-Soft

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

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

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

用Python實現蒙特卡羅方法

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

S：起始點，安全；F：冰凍湖面，安全；H：洞，危險；G：目標點

游戲的任務就是讓智能體從起始點到達目標點，不要掉進洞里。這里附上OpenAI Gym的安裝細節(jié)和文件：gym.openai.com/docs/，下面就開始用Python實現吧！

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

創(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

隨機策略函數

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

存儲狀態(tài)動作值的詞典

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

運行episode的函數

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

測試策略和計算獲勝概率的函數

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):

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ōu)化策略。

本文提到的是在線方法，類似在做中學，而離線方法更強調的是看別人的示范從中學習。