机器学习工程师 – Udacity 强化学习 Part Four

五、蒙特卡洛方法

1.状态值

如果你想详细了解首次经历和所有经历 MC 方法之间的区别，建议你阅读此论文的第 3 部分。结果在第 3.6 部分进行了总结。作者指出：

• 所有经历 MC 存在偏差，而首次经历 MC 不存在偏差（请参阅 Theorems 6 和 7）。
• 一开始，所有经历 MC 具有更低的均方误差 (MSE)，但是随着经历更多的阶段，首次经历 MC 的均方误差更低（请参阅 Corollary 9a 和 10a，以及图 4）。

当每个状态的经历次数接近无穷大时，首次经历和所有经历方法都保证会收敛于真值函数。（换句话说，只要智能体在每个状态获取足够的经验，值函数估值将非常接近真值。）对于首次经历 MC，收敛性遵守大数定律，详情请参阅该教科书的第 5.1 部分。

2.动作值

当每个状态动作对的经历次数接近无穷大时，首次经历和所有经历方法都保证会收敛于真值函数。（换句话说，只要智能体在每个状态动作对获取足够的经验，值函数估值将非常接近真值。）

我们不会使用 MC 预测估算确定性策略对应的动作值；这是因为很多状态动作对从未经历过（因为确定性策略在每个状态始终选择相同的动作）。因此为了收敛，我们仅估算在每个状态中每个动作被选中的概率非零的策略对应的动作值函数。

3.广义策略迭代
旨在解决控制问题的算法会通过与环境互动确定最优策略 π_∗。
广义策略迭代 (GPI) 是指通过交替地进行策略评估和和改进步骤搜索最优策略的广义方法。

4.增量均值
一般情况下，智能体需要猜测大概 5000 次，以便很好地估算值函数，这样的话，在完善策略之前，似乎花费了太长的时间来评估策略。或许在每次猜测之后都完善策略更合理。在这种情况下，我们可以将每个状态动作对的值初始猜测设为 0 并获得起始策略，然后使用该策略生成一个阶段，当该阶段结束时，我们可以更新值函数，并使用该值函数完善策略，然后使用该新策略生成下个阶段，等等。
增量均值可以不断估算一系列数字 (x₁,x₂,…,x_n) 的均值。该算法按顺序查看每个数字，并连续地更新均值 μ。

import numpy as np

def running_mean(x):
    mu = 0
    mean_values = []
    for k in np.arange(0, len(x)):
        mu = mu + (1.0/(k+1))*(x[k] - mu)
        mean_values.append(mu)
    return mean_values

5.策略改进
如果对于每个状态 s∈S，它保证会选择满足 a=arg max a∈A(s)Q(s,a) 的动作 a∈A(s)，则策略相对于动作值函数估值 Q 来说是贪婪策略。（通常将所选动作称之为贪婪动作。）
如果对于每个状态 s∈S，策略相对于动作值函数估值 Q 是 ϵ 贪婪策略：
概率为 1−ϵ 时，智能体选择贪婪动作，以及
概率为 ϵ 时，智能体随机（均匀地）选择一个动作。
为了构建一个相对于当前动作值函数估值 Q 为 ϵ 贪婪策略的策略 π，我们只需设置

6.探索-利用困境
所有强化学习智能体都面临探索-利用困境，即智能体必须在根据当前信息采取最优动作（利用）和需要获取信息以做出更好的判断（探索）之间找到平衡。
一开始倾向于探索环境而不是利用已有的经验，然后逐渐倾向于利用已有的经验而不是探索环境可以证明是最优策略。

7.有限状态下的无限探索贪婪算法 (GLIE)
为了保证 MC 控制会收敛于最优策略 π_∗ ，我们需要确保满足两个条件。我们将这些条件称之为有限状态下的无限探索贪婪算法 (GLIE)。尤其是，如果：
1)每个状态动作对 s,a（针对所有 s∈S 和 a∈A(s)）被经历无限次
2)策略收敛相对于动作值函数估算 Q 来说贪婪的策略。

8.常量 α
在增量均值中，我们完成了一种算法，该算法可以不断估算一系列数字 (x₁,x₂,…,x_n) 的均值。当我们在策略评估中针对蒙特卡洛控制调整该算法时，序列 (x₁,x₂,…,x_n) 对应的是经历相同状态动作对后获得的回报。
但是，（相同状态动作对）的抽样回报可能对应于很多不同的策略。因为控制算法是由一系列的评估和改进步骤组成，在每个互动阶段后，策略被改进。尤其是，我们提到后续时间步抽取的回报很可能对应的策略更优化。
因此，有必要修改策略评估步骤并改为使用常量步长。这样会确保智能体在估算动作值时主要考虑最近抽样的回报，并逐渐忘记很久之前的回报。

 

请在该教科书的第 5.1 个示例中详细了解二十一点游戏。

完成后，请查看相应的 GitHub 文件，并阅读 BlackjackEnv 类的注释部分。

21点规则简介

二十一点是一种扑克牌游戏，目标是尽量使手中牌的总点数达到 21 点，或是接近 21 点，但不能超过，然后与庄家的点数进行比较。人头牌（J、Q、K）的点数是 10。王牌可以是 11 点或 1 点，11 点时“可用”。这种游戏的整副牌是有限的（或者可以替换）。游戏开始时，每个玩家和庄家的一张牌朝上，另一张牌朝下。玩家可以请求更多的牌 (hit=1) 并决定何时停止请求牌(stick=0) 或者超过 21 点（爆牌）。玩家停止请求牌后，庄家翻开扣着的牌，并抽牌，直到所有点数之和是 17 点或大于 17 点。如果庄家爆牌，玩家获胜。
如果玩家或庄家都没爆牌，结果（输赢或持平）由谁的点数更接近 21 点来确定。赢了的奖励是 +1，平局的奖励是 0，输了的奖励是 -1。
包含以下三种状态：玩家的当前点数之和，庄家显示的一张牌（1-10，其中王牌是 1），以及玩家是否拥有可使用的王牌（0 或 1）。
此规则对应于《强化学习引论》（作者：Sutton 和 Barto，1998 年）第 5.1 个示例中介绍的二十一点问题。
http://incompleteideas.net/book/the-book.html

第 0 部分：探索 BlackjackEnv

请使用以下代码单元格创建 Blackjack 环境的实例。

import gym
env = gym.make('Blackjack-v0')

每个状态都是包含以下三个元素的 3 元组：

• 玩家的当前点数之和 ∈{0,1,…,31}，
• 庄家朝上的牌点数之和 ∈{1,…,10}，及
• 玩家是否有能使用的王牌（no =1）。

智能体可以执行两个潜在动作：

STICK = 0
HIT = 1

通过运行以下代码单元格进行验证。

print(env.observation_space)
print(env.action_space)

Tuple(Discrete(32), Discrete(11), Discrete(2))
Discrete(2)

执行以下代码单元格以按照随机策略玩二十一点。

（代码当前会玩三次二十一点——你可以随意修改该数字，或者多次运行该单元格。该单元格旨在让你体验当智能体与环境互动时返回的输出结果。）

for i_episode in range(3):
    state = env.reset()
    while True:
        print(state)
        action = env.action_space.sample()
        state, reward, done, info = env.step(action)
        if done:
            print('End game! Reward: ', reward)
            print('You won :)\n') if reward > 0 else print('You lost :(\n')
            break

(9, 10, False)
End game! Reward:  -1.0
You lost :(

(11, 3, False)
(12, 3, False)
(19, 3, False)
End game! Reward:  1.0
You won :)

(12, 10, False)
(13, 10, False)
(21, 10, False)
End game! Reward:  -1
You lost :(

第 1 部分：MC 预测 - 状态值

在此部分，你将自己编写 MC 预测的实现（用于估算状态值函数）。

我们首先将研究以下策略：如果点数之和超过 18，玩家将始终停止出牌。函数generate_episode_from_limit 会根据该策略抽取一个阶段。

该函数会接收以下输入：

• bj_env：这是 OpenAI Gym 的 Blackjack 环境的实例。

它会返回以下输出：

• episode：这是一个（状态、动作、奖励）元组列表，对应的是 R_i+1。

def generate_episode_from_limit(bj_env):
    episode = []
    state = bj_env.reset()
    while True:
        action = 0 if state[0] > 18 else 1
        next_state, reward, done, info = bj_env.step(action)
        episode.append((state, action, reward))
        state = next_state
        if done:
            break
    return episode

执行以下代码单元格以按照该策略玩二十一点。

（代码当前会玩三次二十一点——你可以随意修改该数字，或者多次运行该单元格。该单元格旨在让你熟悉 generate_episode_from_limit 函数的输出结果。）

for i in range(3):
    print(generate_episode_from_limit(env))

[((14, 6, False), 1, 0), ((15, 6, False), 1, 0), ((19, 6, False), 0, -1.0)]
[((14, 6, False), 1, 0), ((17, 6, False), 1, 0), ((18, 6, False), 1, -1)]
[((16, 10, False), 1, -1)]

现在你已经准备好自己编写 MC 预测的实现了。你可以选择实现首次经历或所有经历 MC 预测；对于 Blackjack 环境，这两种技巧是对等的。

你的算法将有三个参数：

• env：这是 OpenAI Gym 环境的实例。
• num_episodes：这是通过智能体-环境互动生成的阶段次数。
• generate_episode：这是返回互动阶段的函数。
• gamma：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：1。

该算法会返回以下输出结果：

• V：这是一个字典，其中 V[s] 是状态 s 的估算值。例如，如果代码返回以下输出结果：

{(4, 7, False): -0.38775510204081631, (18, 6, False): -0.58434296365330851, (13, 2, False): -0.43409090909090908, (6, 7, False): -0.3783783783783784, ...

则状态 (4, 7, False) 的值估算为 -0.38775510204081631。

如果你不知道如何在 Python 中使用 defaultdict，建议查看此源代码。

from collections import defaultdict
import numpy as np
import sys
​
def mc_prediction_v(env, num_episodes, generate_episode, gamma=1.0):
    # initialize empty dictionary of lists
    returns = defaultdict(list)
    # loop over episodes
    for i_episode in range(1, num_episodes+1):
        # monitor progress
        if i_episode % 1000 == 0:
            print("\rEpisode {}/{}.".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        # generate an episode
        episode = generate_episode(env)
        # obtain the states, actions, and rewards
        states, actions, rewards = zip(*episode)
        # prepare for discounting
        discounts = np.array([gamma**i for i in range(len(rewards)+1)])
        # calculate and store the return for each visit in the episode
        for i, state in enumerate(states):
            returns[state].append(sum(rewards[i:]*discounts[:-(1+i)]))
    # calculate the state-value function estimate
    V = {k: np.mean(v) for k, v in returns.items()}
    return V

使用以下单元格计算并绘制状态值函数估算值。 (用于绘制值函数的代码来自此源代码，并且稍作了修改。）

要检查你的实现是否正确，应将以下图与解决方案 notebook Monte_Carlo_Solution.ipynb 中的对应图进行比较。

from plot_utils import plot_blackjack_values
​
# obtain the value function
V = mc_prediction_v(env, 500000, generate_episode_from_limit)
​
# plot the value function
plot_blackjack_values(V)

Episode 500000/500000.

第 2 部分：MC 预测 - 动作值

在此部分，你将自己编写 MC 预测的实现（用于估算动作值函数）。

我们首先将研究以下策略：如果点数之和超过 18，玩家将几乎始终停止出牌。具体而言，如果点数之和大于 18，她选择动作 STICK 的概率是 80%；如果点数之和不大于 18，她选择动作 HIT 的概率是 80%。函数 generate_episode_from_limit_stochastic 会根据该策略抽取一个阶段。

该函数会接收以下输入：

• bj_env：这是 OpenAI Gym 的 Blackjack 环境的实例。

该算法会返回以下输出结果：

• episode: 这是一个（状态、动作、奖励）元组列表，对应的是 R_i+1。

def generate_episode_from_limit_stochastic(bj_env):
    episode = []
    state = bj_env.reset()
    while True:
        probs = [0.8, 0.2] if state[0] > 18 else [0.2, 0.8]
        action = np.random.choice(np.arange(2), p=probs)
        next_state, reward, done, info = bj_env.step(action)
        episode.append((state, action, reward))
        state = next_state
        if done:
            break
    return episode

现在你已经准备好自己编写 MC 预测的实现了。你可以选择实现首次经历或所有经历 MC 预测；对于 Blackjack 环境，这两种技巧是对等的。

你的算法将有三个参数：

• env: 这是 OpenAI Gym 环境的实例。
• num_episodes：这是通过智能体-环境互动生成的阶段次数。
• generate_episode：这是返回互动阶段的函数。
• gamma：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：1。

该算法会返回以下输出结果：

• Q：这是一个字典（一维数组），其中 Q[s][a] 是状态 s 和动作 a 对应的估算动作值。

def mc_prediction_q(env, num_episodes, generate_episode, gamma=1.0):
    # initialize empty dictionaries of arrays
    returns_sum = defaultdict(lambda: np.zeros(env.action_space.n))
    N = defaultdict(lambda: np.zeros(env.action_space.n))
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    # loop over episodes
    for i_episode in range(1, num_episodes+1):
        # monitor progress
        if i_episode % 1000 == 0:
            print("\rEpisode {}/{}.".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        # generate an episode
        episode = generate_episode(env)
        # obtain the states, actions, and rewards
        states, actions, rewards = zip(*episode)
        # prepare for discounting
        discounts = np.array([gamma**i for i in range(len(rewards)+1)])
        # update the sum of the returns, number of visits, and action-value 
        # function estimates for each state-action pair in the episode
        for i, state in enumerate(states):
            returns_sum[state][actions[i]] += sum(rewards[i:]*discounts[:-(1+i)])
            N[state][actions[i]] += 1.0
            Q[state][actions[i]] = returns_sum[state][actions[i]] / N[state][actions[i]]
    return Q

请使用以下单元格获取动作值函数估值 Q。我们还绘制了相应的状态值函数。

要检查你的实现是否正确，应将以下图与解决方案 notebook Monte_Carlo_Solution.ipynb 中的对应图进行比较。

# obtain the action-value function
Q = mc_prediction_q(env, 500000, generate_episode_from_limit_stochastic)
​
# obtain the state-value function
V_to_plot = dict((k,(k[0]>18)*(np.dot([0.8, 0.2],v)) + (k[0]<=18)*(np.dot([0.2, 0.8],v))) \
         for k, v in Q.items())
​
# plot the state-value function
plot_blackjack_values(V_to_plot)

Episode 500000/500000.

第 3 部分：MC 控制 - GLIE

在此部分，你将自己编写常量-α MC 控制的实现。

你的算法将有三个参数：

• env: 这是 OpenAI Gym 环境的实例。
• num_episodes：这是通过智能体-环境互动生成的阶段次数。
• generate_episode：这是返回互动阶段的函数。
• gamma：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：1。

该算法会返回以下输出结果：

• Q：这是一个字典（一维数组），其中 Q[s][a] 是状态 s 和动作 a 对应的估算动作值。
• policy：这是一个字典，其中 policy[s] 会返回智能体在观察状态 s 之后选择的动作。

（你可以随意定义其他函数，以帮助你整理代码。）

def generate_episode_from_Q(env, Q, epsilon, nA):
    """ generates an episode from following the epsilon-greedy policy """
    episode = []
    state = env.reset()
    while True:
        action = np.random.choice(np.arange(nA), p=get_probs(Q[state], epsilon, nA)) \
                                    if state in Q else env.action_space.sample()
        next_state, reward, done, info = env.step(action)
        episode.append((state, action, reward))
        state = next_state
        if done:
            break
    return episode
​
def get_probs(Q_s, epsilon, nA):
    """ obtains the action probabilities corresponding to epsilon-greedy policy """
    policy_s = np.ones(nA) * epsilon / nA
    best_a = np.argmax(Q_s)
    policy_s[best_a] = 1 - epsilon + (epsilon / nA)
    return policy_s
​
def update_Q_GLIE(env, episode, Q, N, gamma):
    """ updates the action-value function estimate using the most recent episode """
    states, actions, rewards = zip(*episode)
    # prepare for discounting
    discounts = np.array([gamma**i for i in range(len(rewards)+1)])
    for i, state in enumerate(states):
        old_Q = Q[state][actions[i]] 
        old_N = N[state][actions[i]]
        Q[state][actions[i]] = old_Q + (sum(rewards[i:]*discounts[:-(1+i)]) - old_Q)/(old_N+1)
        N[state][actions[i]] += 1
    return Q, N

def mc_control_GLIE(env, num_episodes, gamma=1.0):
    nA = env.action_space.n
    # initialize empty dictionaries of arrays
    Q = defaultdict(lambda: np.zeros(nA))
    N = defaultdict(lambda: np.zeros(nA))
    # loop over episodes
    for i_episode in range(1, num_episodes+1):
        # monitor progress
        if i_episode % 1000 == 0:
            print("\rEpisode {}/{}.".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        # set the value of epsilon
        epsilon = 1.0/((i_episode/8000)+1)
        # generate an episode by following epsilon-greedy policy
        episode = generate_episode_from_Q(env, Q, epsilon, nA)
        # update the action-value function estimate using the episode
        Q, N = update_Q_GLIE(env, episode, Q, N, gamma)
    # determine the policy corresponding to the final action-value function estimate
    policy = dict((k,np.argmax(v)) for k, v in Q.items())
    return policy, Q

通过以下单元格获取估算的最优策略和动作值函数。

# obtain the estimated optimal policy and action-value function
policy_glie, Q_glie = mc_control_GLIE(env, 500000)

Episode 500000/500000.

接着，我们将绘制相应的状态值函数。

# obtain the state-value function
V_glie = dict((k,np.max(v)) for k, v in Q_glie.items())
​
# plot the state-value function
plot_blackjack_values(V_glie)

最后，我们将可视化估算为最优策略的策略。

from plot_utils import plot_policy
​
# plot the policy
plot_policy(policy_glie)

真最优策略 ϵ 的衰减率和/或使该算法运行更多个阶段，以获得更好的结果。

α

在此部分，你将自己编写常量-α MC 控制的实现。

你的算法将有三个参数：

• env: 这是 OpenAI Gym 环境的实例。
• num_episodes：这是通过智能体-环境互动生成的阶段次数。
• generate_episode：这是返回互动阶段的函数。
• alpha：这是更新步骤的步长参数。
• gamma：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：1。

该算法会返回以下输出结果：

• Q：这是一个字典（一维数组），其中 Q[s][a] 是状态 s 和动作 a 对应的估算动作值。
• policy：这是一个字典，其中 policy[s] 会返回智能体在观察状态 s 之后选择的动作。

（你可以随意定义其他函数，以帮助你整理代码。）

def update_Q_alpha(env, episode, Q, alpha, gamma):
    """ updates the action-value function estimate using the most recent episode """
    states, actions, rewards = zip(*episode)
    # prepare for discounting
    discounts = np.array([gamma**i for i in range(len(rewards)+1)])
    for i, state in enumerate(states):
        old_Q = Q[state][actions[i]] 
        Q[state][actions[i]] = old_Q + alpha*(sum(rewards[i:]*discounts[:-(1+i)]) - old_Q)
    return Q

def mc_control_alpha(env, num_episodes, alpha, gamma=1.0):
    nA = env.action_space.n
    # initialize empty dictionary of arrays
    Q = defaultdict(lambda: np.zeros(nA))
    # loop over episodes
    for i_episode in range(1, num_episodes+1):
        # monitor progress
        if i_episode % 1000 == 0:
            print("\rEpisode {}/{}.".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        # set the value of epsilon
        epsilon = 1.0/((i_episode/8000)+1)
        # generate an episode by following epsilon-greedy policy
        episode = generate_episode_from_Q(env, Q, epsilon, nA)
        # update the action-value function estimate using the episode
        Q = update_Q_alpha(env, episode, Q, alpha, gamma)
    # determine the policy corresponding to the final action-value function estimate
    policy = dict((k,np.argmax(v)) for k, v in Q.items())
    return policy, Q

通过以下单元格获得估算的最优策略和动作值函数。

# obtain the estimated optimal policy and action-value function
policy_alpha, Q_alpha = mc_control_alpha(env, 500000, 0.02)

Episode 500000/500000.

接着，我们将绘制相应的状态值函数。

# obtain the state-value function
V_alpha = dict((k,np.max(v)) for k, v in Q_alpha.items())
​
# plot the state-value function
plot_blackjack_values(V_alpha)

最后，我们将可视化估算为最优策略的策略。

# plot the policy
plot_policy(policy_alpha)

真最优策略 ϵ 的衰减率和/或使该算法运行更多个阶段，以获得更好的结果。