马尔可夫决策-悬崖寻路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最优方程往往难以获得或难以求解。