• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

[强化学习实战]马尔可夫决策-悬崖寻路python实现

人工智能 柯南404 1750次浏览 0个评论

马尔可夫决策-悬崖寻路python实现

  • 案例分析
  • 要点概括
  • 环境使用
  • 求解Bellman期望方程
  • 求解Bellman最优方程
  • 总结

 

案例分析

本节考虑Gym库中的悬崖寻路问题(CliffWalking-v0)。悬崖寻路问题是这样一种回合制问题:在一个4×12的网格中,智能体最开始在左下角的网格,希望移动到右下角的网格。智能体每次可以在上、下、左、右这4个方向中移动一步,每移动一步会惩罚一个单位的奖励。但是,移动有以下限制。

在这里插入图片描述

·智能体不能移出网格。如果智能体想执行某个动作移出网格,那么就让本步智能体不移动。但是这个操作依然会惩罚一个单位的奖励。

·如果智能体将要到达最下一排网格(即开始网格和目标网格之间的10个网格),智能体会立即回到开始网格,并惩罚100个单位的奖励。这10个网格可被视为“悬崖”。当智能体移动到终点时,回合结束,回合总奖励为各步奖励之。 

要点概括

·在完全可观测的离散时间智能体/环境接口中引入概率和Markov性,可以得到Markov决策过程。

·在Markov决策过程中, S \mathcal{S}S是状态空间(包括终止状态s 终 止 的状态空间为S +), A 是动作空间, R 是奖励空间,p是动力。p ( s ′ , r ∣ s , a ) ,表示从状态s和动作

a到状态s’和奖励r的转移概率。π是策略。π(a|s)表示在状态s决定执行动作a的概率。

·回报是未来奖励的和,奖励按折扣因子γ进行折扣。

·对于一个策略π,在某个状态s下的期望回报称为状态价值v π ( s ),在某个状态动作对(s,a)下的期望回报称为动作价值q π ( s , a ) 。

·状态价值和动作价值满足Bellman期望方程:

在这里插入图片描述

·用状态价值函数可以定义策略的偏序关系。对于一个环境,如果所有策略都小于等于某个策略π*,则称π是一个最优策略。

·任何环境都存在最优策略。一个环境的所有最优策略有着相同的状态价值和动作价值,分别称为最优状态价值(记为v)和最优动作价值(记为q*)。

·最优状态价值和最优动作价值满足Bellman最优方程:

在这里插入图片描述

·可以应用下列线性规划求解最优动作价值:

在这里插入图片描述

·用Bellman最优方程求解出最优价值后,可以用

在这里插入图片描述

确定出一个确定性的最优策略。其中,对于某个s∈ S \mathcal{S}S,如果有多个动作值a使得q*(s,a)取得最大值,则任选一个动作即可。

环境使用

Gym库中的环境’CliffWalking-v0’实现了悬崖寻路的环境。

import gym
env = gym.make('CliffWalking-v0')
print('观察空间 = {}'.format(env.observation_space))
print('动作空间 = {}'.format(env.action_space))
print('状态数量 = {}, 动作数量 = {}'.format(env.nS, env.nA))
print('地图大小 = {}'.format(env.shape))

这个环境是一个离散的Markov决策过程。在这个Markov决策过程中,每个状态是取自S={0,1,…,46}的int型数值(加上终止状态则为S + ={0,1,…,46,47}),表示当前智能体在地图中对应的位置上。动作是取自A={0,1,2,3}的int型数值:0表示向上,1表示向右,2表示向下,3表示向左。奖励取自{-1,-100},遇到悬崖为-100,否则为-1。

下面给出了用给出的策略运行一个回合的代码。函数play_once()有两个参数,一个是环境对象,另外一个是策略policy,它是np.array类型的实例。

def play_once(env, policy):
    total_reward = 0
    state = env.reset()
    while True:
        loc = np.unravel_index(state, env.shape)
        print('状态 = {}, 位置 = {}'.format(state, loc), end=' ')
        action = np.random.choice(env.nA, p=policy[state])
        next_state, reward, done, _ = env.step(action)
        print('动作 = {}, 奖励 = {}'.format(action, reward))
        total_reward += reward
        if done:
            break
        state = next_state
    return total_reward

 下面代码给出了一个最优策略optimal_policy。最优策略是在开始处向上,接着一路向右,然后到最右边时向下。

actions = np.ones(env.shape, dtype=int)
actions[-1, :] = 0
actions[:, -1] = 2
optimal_policy = np.eye(4)[actions.reshape(-1)]

采用最优策略,从开始网格到目标网格一共要移动13步,回合总奖励为-13。

total_reward = play_once(env, optimal_policy)
print('总奖励 = {}'.format(total_reward))

输出为

在这里插入图片描述

 求解Bellman期望方程

接下来考虑策略评估。我们用Bellman期望方程求解给定策略的状态价值和动作价值。首先来看状态价值。用状态价值表示状态价值的Bellmn期望方程为:

在这里插入图片描述

这是一个线性方程组,其标准形式为:

在这里插入图片描述

得到标准形式后就可以调用相关函数直接求解。得到状态价值函数后,可以用状态价值表示动作价值的Bellan期望方程:

在这里插入图片描述

函数evaluate_bellman()实现了上述功能。状态价值求解部分用np.linalg.solve()函数求解标准形式的线性方程组。得到状态价值后,直接计算得到动作价值。

def evaluate_bellman(env, policy, gamma=1.):
    a, b = np.eye(env.nS), np.zeros((env.nS))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            pi = policy[state][action]
            for p, next_state, reward, done in env.P[state][action]:
                a[state, next_state] -= (pi * gamma * p)
                b[state] += (pi * reward * p)
    v = np.linalg.solve(a, b)
    q = np.zeros((env.nS, env.nA))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            for p, next_state, reward, done in env.P[state][action]:
                q[state][action] += ((reward + gamma * v[next_state]) * p)
    return v, q

 接下来我们用evaluate_bellman()函数评估给出的策略。然后用以下代码评估了一个随机策略和最优确定性策略,并输出了状态价值函数和动作价值函数。

policy = np.random.uniform(size=(env.nS, env.nA))
policy = policy / np.sum(policy, axis=1)[:, np.newaxis]

state_values, action_values = evaluate_bellman(env, policy)
print('状态价值 = {}'.format(state_values))
print('动作价值 = {}'.format(action_values))

在这里插入图片描述

optimal_state_values, optimal_action_values = evaluate_bellman(env, optimal_policy)
print(‘最优状态价值 = {}’.format(optimal_state_values))
print(‘最优动作价值 = {}’.format(optimal_action_values))

在这里插入图片描述

求解Bellman最优方程

对于悬崖寻路这样的数值环境,可以使用线性规划求解。线性规划问题的标准形式为:

在这里插入图片描述

其中目标函数中状态价值的系数已经被固定为1。也可以选择其他正实数作为系数。

 使用scipy.optimize.linprog()函数来计算这个动态规划问题。这个函数的第0个参数是目标函数中各决策变量在目标函数中的系数,本例中都取1;第1个和第2个参数是形如“Ax≤b”这样的不等式约束的A和b的值。函数optimal_bellman()刚开始就计算得到这些值。scipy.optimize.linprog()还有关键字参数bounds,指定决策变量是否为有界的。本例中,决策变量都是无界的。无界也要显式指定,不可以忽略。还有关键字参数method确定优化方法。默认的优化方法不能处理不等式约束,这里选择了能够处理不等式约束的内点法(interior-point method)。 

def optimal_bellman(env, gamma=1.):
    p = np.zeros((env.nS, env.nA, env.nS))
    r = np.zeros((env.nS, env.nA))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            for prob, next_state, reward, done in env.P[state][action]:
                p[state, action, next_state] += prob
                r[state, action] += (reward * prob)
    c = np.ones(env.nS)
    a_ub = gamma * p.reshape(-1, env.nS) - \
            np.repeat(np.eye(env.nS), env.nA, axis=0)
    b_ub = -r.reshape(-1)
    a_eq = np.zeros((0, env.nS))
    b_eq = np.zeros(0)
    bounds = [(None, None),] * env.nS
    res = scipy.optimize.linprog(c, a_ub, b_ub, bounds=bounds,
            method='interior-point')
    v = res.x
    q = r + gamma * np.dot(p, v)
    return v, q

求得最优动作价值后,可以用argmax计算出最优确定策略。

optimal_state_values, optimal_action_values = optimal_bellman(env)
print('最优状态价值 = {}'.format(optimal_state_values))
print('最优动作价值 = {}'.format(optimal_action_values))

在这里插入图片描述

总结

Markov决策模型用动力系统来描述环境,用策略来描述智能体。理论上,价值函数和最优价值函数可以通过Bellman期望方程和Bellman最优方程求解。但是在实际问题中,

Bellman期望方程和Bellman最优方程往往难以获得或难以求解。


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明[强化学习实战]马尔可夫决策-悬崖寻路python实现
喜欢 (0)

您必须 登录 才能发表评论!

加载中……