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

马尔可夫决策-悬崖寻路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))

在这里插入图片描述