如何使用强化学习玩21点?

2020-08-04 11:34:13 浏览数 (1)

本文将比较分析Monte-Carlo控制算法与时域差分控制算法在解21点(Blackjack)博弈中的应用。

我们注意到很少有文章详细解释Monte-Carlo方法,而只是直接跳到深度Q-learning应用程序。

在本文中,您将了解强化学习中无模型算法背后的动机和内部工作原理,同时应用它们来解决Blackjack。

在正式开始之前,我们假设您对强化学习的基本概念有所了解,如果你没接触过相关内容,也没关系,这里有一个简短的概述:

  • 在通常的强化学习设置中,代理在环境中执行操作,并从环境中获得观察结果和奖励。
  • 代理执行的这些任务可以是情景性的,也可以是持续性的。21点是情景性的游戏,也就是说,它以你是赢是输告终。
  • 代理期望最大化其累积的回报,也就是所谓的“预期回报”。相比将来可能获得的奖励,可以立刻获得的奖励显得更加重要。例如Gt = Rt 1 γRt 2 …
  • 我们假设我们的环境具有马尔可夫性质,即在给定当前状态的情况下,未来状态或奖励独立于过去状态,即P(St 1|St) = P(St 1|S1,S2,S3,…St)。

代理采取的策略,可以看做是从感知到的环境状态到该状态下的行动的一种映射。

  • 我们定义状态对V (s)对应于一个策略π:当agent在某一状态运行并遵循策略π时,它就会获得预期的回报。记得V(s)总是对应于某些政策略π。
  • 我们还定义了行为函数Q(s,a),其值代表在状态s下遵循策略π,并采取行动'a'。
  • V(s) = E [Gt | St = s], Q(s,a) = E [Gt | St = s, At=a],也可以如下图所示。这种形式在计算V(s)和Q(s,a)时会更有用。

Pss '是环境的属性,在Sutton和Barto的书中也被称为P(s ', r|s, a)

动态规划等各种基于模型的方法使用Bellman方程(V(St)和V(St 1)之间的递归关系),通过迭代寻找最优值函数和Q函数。

无模型(Model-free)方法

要使用基于模型的方法,我们需要对环境有完整的了解,即我们需要知道Pss':

如果agent处于状态St=1,并且在At=a处采取行动,那么我们最终会得到状态St 1=s '的转换概率。例如,如果一个机器人选择向前移动,它可能会侧身移动,以防它下面的地板很滑。在像21点这样的游戏中,我们的行动空间是有限的,因为我们可以选择“打”或“坚持”,但我们可以在任何一种可能的状态结束!在21点状态下,由你、庄家以及你是否有可用的ace决定,如下:

代码语言:javascript复制
env = gym.make('Blackjack-v0')
print(env.observation_space)
print(env.action_space)

当我们没有环境模型时该怎么办?你通过一次又一次地与它们交互来获取样本,并从它们那里估计这些信息。无模型基本上是一种反复试验的方法,不需要对环境或任意两种状态之间的转移概率有明确的了解。

因此,我们看到无模型系统甚至不能考虑它们的环境将如何响应某个特定的动作而发生变化。这样,相对于构建一个足够精确的环境模型,其真正瓶颈是构建更复杂的方法,同时具有合理的优势。(例如,我们不可能开始列出在21点的每一种状态下,发卡人抽到下一张牌的概率。)

了解了无模型方法背后的动机之后,让我们来看看一些算法!

蒙特卡罗预测算法

为了构建更好的策略,我们首先需要能够评估任何策略。如果一个agent对多个事件遵循一个策略,使用蒙特卡罗预测,我们可以根据这些事件的结果构建Q表(即“估计”行为价值函数)。

我们可以从一个随机策略开始,比如" stick "如果sum大于18,概率是80%因为我们不想超过21。否则,如果sum小于18,我们将以80%的概率“命中”。以下代码使用以下策略生成剧集,然后我们将对该策略进行评估:

代码语言:javascript复制
def generate_episode_from_limit_stochastic(bj_env):
    episode = []
    state = bj_env.reset() #here, bj_env is the env instance
    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

现在,我们想要得到给定策略的Q函数,它需要直接从经验中学习价值函数。请注意,在蒙特卡洛方法中,我们将在一集的最后获得奖励。

集= S1 A1 R1, S2 A2 R2, S3 A3 R3……ST(直至终止状态的步骤序列)

我们将从MDP的示例返回中学习值函数,回顾一下:

什么是样本回报?假设我们使用一个策略玩了10次,当我们10次访问相同的状态‘S’时,我们得到了2,6,5,7的奖励,那么样本返回值就是(2 6 5 7)/4 = 20/4 = 5 ~V(S)。因此,样本回报是每一集的平均回报(回报)。我们访问状态的顺序在这里并不重要,每个值的估计值都是独立计算的!

这样我们既可以建立一个V表,也可以建立一个Q表。为了创建一个Q表,我们需要跟踪每访问一个(状态,动作)对所获得的奖励,同时也要记录我们访问这个状态的次数,比如n个表。这取决于在估计q值时所选择的返回值。

  • 第一次访问MC: 在一次迭代中,我们平均只访问第一次(s,a)的回报。从统计学上来说,这是一种不偏不倚的方法。
  • 每一次访问MC: 在一次迭代中,我们只对每一次访问(s,a)进行平均回报。这在统计学上是有偏见的。

例如:在一个情节,S1 A1 R1, R2 S2 A2, S3 A3 R3, S1 A1 R4→结束。然后第一次访问MC会考虑奖励直到R3计算回报,而每次访问MC会考虑所有的奖励直到剧集结束。

在这里,在21点,它不太影响我们是否使用首次访问或每次访问MC。这是首次访问MC预测算法:

但我们将实现每次访问MC预测如下所示:

代码语言:javascript复制
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):
        # Let us monitor our progress :)
        if i_episode % 1000 == 0:
            print("rEpisode {}/{}.".format(i_episode, num_episodes), end="")


        # Generating an episode using our 80-20 policy we defined above:
        episode = generate_episode(env)
        # obtain the states, actions, and rewards
        states, actions, rewards = zip(*episode)
        '''
        This discounts array is the amount by which we wanna discount each consequent reward ie.
        discounts = [1,gamma, gamma^2, gamma^3.....] 
        then we compute the total return Gt= Rt 1 *1   Rt 2 * gamma   Rt 3 * gamma^2  ...
        '''
        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): #ever-visit
            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]]
            #Just taking the mean of all the returns got by taking this action when we were in this state.
    return Q

我们首先初始化一个Q表和N表,以保持对每个状态-行为对的访问。

然后在生成集函数中,我们使用前面讨论过的80-20随机策略。

代码语言:javascript复制
sum(rewards[i:]*discounts[:-(1 i)]) #is used to calculate Gt

这将估计用于生成剧集的任何策略的Q表!

一旦我们有了Q值,得到效用是相当容易的V(s)= Q(s,π(s))。让我们画出状态值V(s)!

绘制出32*10*2个状态下的V(s),每个V(s)的值都在[-1,1]之间,因为对于赢、平和输,

我们得到的奖励是 1,0,-1

现在我们知道如何估计政策的行为价值函数,我们如何改进它?

蒙特卡罗控制算法

这是一个简单的计划。我们从一个随机策略开始,使用MC预测计算Q表。所以我们现在知道了哪些行为,哪些状态比其他状态更好,也就是说它们的Q值更大。所以我们可以改进现有的策略,根据我们的知识贪婪地选择每个状态下的最佳操作,即Q表,然后重新计算Q表,贪婪地选择下一个策略,以此类推!听起来不错吗?

  • 增量平均值:还记得我们在MC预测中是如何用所有收益的平均值来估计Q值的吗?但现在不同于MC Pred,在MC Control中,我们的策略正在经历每一个周期的变化!我们可以用之前的Q值来表示同样的方程,如果你看到N(St, at) * Q(St, at)是Gt,你自己也可以得到同样的方程,因此Gt-Q(St, at)是增量变化。
  • 常数阿尔法:现在随着N(St,At)的增加,也就是我们在交互中多次访问同一个状态-动作对,增量变化项减少,这意味着我们的后一种体验对初始状态的影响会越来越小。为了解决这个我们可以用一个常数α取代(1/N)项,即超参数,供我们选择。

了解了这些重要的实际变化的想法,只是采样返回,这是算法的首次访问MC控制!

我们将实现每次访问MC控件,因为它稍微容易一些。

代码语言:javascript复制
def get_probs(Q_s, epsilon, nA): #nA is no. of actions in the action space
    # 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

''' 
Now we will use this get_probs func in generating the episode. 
Note that we are no longer using the stochastic policy we started with, instead building upon it in an epsilon greedy way.
'''
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

''' 
Finally Q values are approximated by taking average of corresponding returns.
But instead we can write it using incremental mean and constant alpha.
As we are using constant alpha we need not keep a track of N-table, ie how many times we visited that state.
''' 

def update_Q(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

我们只使用了3个函数使代码看起来更整洁。要像预测MC那样生成剧集,我们需要一个策略。

update_Q函数用增量均值和常数更新q值。最后我们调用MC控件中的所有这些函数和ta-da!

代码语言:javascript复制
def mc_control(env, num_episodes, alpha, gamma=1.0, eps_start=1.0, eps_decay=.99995, eps_min=0.01):
    nA = env.action_space.n
    # initialize empty dictionary of arrays
    Q = defaultdict(lambda: np.zeros(nA))
    epsilon = eps_start
    # 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 = max(epsilon*eps_decay, eps_min)
        # 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(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

最后我们有了一个学习玩21点的算法,至少是一个稍微简化的版本。让我们将学习到的策略与Sutton和Barto在RL书中提到的最优策略进行比较。

!好了,我们的AI在玩21点的时候赢了很多次!

时间差分(TD)方法

21点并不是学习TD方法优点的最佳环境,因为21点是一种情景博弈,蒙特卡罗方法假设情景环境。在MC控制中,在每一集结束时,我们更新Q表并更新我们的策略。因此我们无法找出是哪个错误的举动导致了失败,但这在像21点这样的短时间游戏中并不重要。

如果它是一个更长的像国际象棋游戏,它将更有意义使用TD控制方法,因为他们辅助程序,这意味着它不会等到最后一集更新预期未来回报评估(V),它只会等到下一个时间步长更新值估计。

TD方法的独特之处在于,它是由相同数量的时间连续估计值之间的差异驱动的。关于时间差异学习的起源更多的是在动物心理学中,特别是在二次强化的概念中。二级强化物是与一级强化物配对的刺激物(来自环境本身的简单奖励)因此二级强化物具有类似的性质。

例如,在MC控件中:

但是在TD控制中:

就像动态规划一样,TD在每一步都使用Bellman方程来更新。

下图可以帮助解释DP、MC和TD方法之间的区别。

因此我们能想到的增量意味着以不同的方式好像Gt的目标或期望返回代理会有,而是返回了Q(St,At)所以意义推动Q值由αGt * (Gt-Q(St,At))。

同样在TD方法的情况下,瞬时TD目标是Rt 1 γQ(St 1,At 1)和TD误差误(Rt 1 γQ(St 1,At 1)- Q(St,At))。

根据不同的TD目标和略有不同的实现,3种TD控制方法分别是:

  • SARSA或SARSA(o)

在python中是这样实现的:

代码语言:javascript复制
def update_Q_sarsa(alpha, gamma, Q, state, action, reward, next_state=None, next_action=None):
    """Returns updated Q-value for the most recent experience."""
    current = Q[state][action]  # estimate in Q-table (for current state, action pair)
    # get value of state, action pair at next time step
    Qsa_next = Q[next_state][next_action] if next_state is not None else 0    
    target = reward   (gamma * Qsa_next)               # construct TD target
    new_value = current   (alpha * (target - current)) # get updated value
    return new_value
  • SARSAMAX or Q-learning

在python中是这样实现的:

代码语言:javascript复制
def update_Q_sarsamax(alpha, gamma, Q, state, action, reward, next_state=None):
    """Returns updated Q-value for the most recent experience."""
    current = Q[state][action]  # estimate in Q-table (for current state, action pair)
    Qsa_next = np.max(Q[next_state]) if next_state is not None else 0  # value of next state 
    target = reward   (gamma * Qsa_next)               # construct TD target
    new_value = current   (alpha * (target - current)) # get updated value 
    return new_value
  • Expected SARSA

在python中是这样实现的:

代码语言:javascript复制
def update_Q_expsarsa(alpha, gamma, nA, eps, Q, state, action, reward, next_state=None):
    """Returns updated Q-value for the most recent experience."""
    current = Q[state][action]         # estimate in Q-table (for current state, action pair)
    policy_s = np.ones(nA) * eps / nA  # current policy (for next state S')
    policy_s[np.argmax(Q[next_state])] = 1 - eps   (eps / nA) # greedy action
    Qsa_next = np.dot(Q[next_state], policy_s)         # get value of state at next time step
    target = reward   (gamma * Qsa_next)               # construct target
    new_value = current   (alpha * (target - current)) # get updated value 
    return new_value

注意,TD控制方法中的Q表在每次迭代的每一个时间步长中都会更新,而MC控制在每一集结束时都会更新。

这里没有像MC方法那样深入地解释TD方法,而是以一种比较的方式进行分析,但是对于那些感兴趣的人来说,这3种方法都是在notebook中实现的。

0 人点赞