出租车调度-Q learning & SARSA
- 案例分析
- 实验环境使用
- 同策时序差分学习调度
- 异策时序差分调度
- 资格迹学习调度
- 结论
代码链接
案例分析
本节考虑Gym库里出租车调度问题（Taxi-v2）：在一个5×5方格表示的地图上，有4个出租车停靠点。在每个回合开始时，有一个乘客会随机出现在4个出租车停靠点中的一个，并想在任意一个出租车停靠点下车。出租车会随机出现在25个位置的任意一个位置。出租车需要通过移动自己的位置，到达乘客所在的位置，并将乘客接上车，然后移动到乘客想下车的位置，再让乘客下车。出租车只能在地图范围内上下左右移动一格，并且在有竖线阻拦地方不能横向移动。出租车完成一次任务可以得到20个奖励，每次试图移动得到-1个奖励，不合理地邀请乘客上车（例如目前车和乘客不在同一位置，或乘客已经上车）或让乘客下车（例如车不在目的地，或车上没有乘客）得到-10个奖励。希望调度出租车让总奖励的期望最大。
实验环境使用
Gym库的Taxi-v2环境实现了出租车调度问题的环境。导入环境后，可以用env.reset()来初始化环境，用env.step()来执行一步，用env.render()来显示当前局势。env.render()会打印出的局势图，其中乘客的位置、目的地会用彩色字母显示，出租车的位置会高亮显示。具体而言，如果乘客不在车上，乘客等待地点（位置）的字母会显示为蓝色。目的地所在的字母会显示为洋红色。如果乘客不在车上，出租车所在的位置会用黄色高亮；如果乘客在车上，出租车所在的位置会用绿色高亮。
这个环境中的观测是一个范围为[0,500)的int型数值。这个数值实际上唯一表示了整个环境的状态。我们可以用env.decode()函数将这个int数值转化为长度为4的元组
(taxirow,taxicol,passloc,desti dx)，其各元素含义如下：
·taxirow和taxicol是取值为{0,1,2,3,4}的int型变量，表示当前出租车的位置；
·passloc是取值为{0,1,2,3,4}的int型数值，表示乘客的位置，其中0～3表示乘客在表1中对应的位置等待，4表示乘客在车上；
·destidx是取值为{0,1,2,3}的int型数值，表示目的地，目的地的位置由表5-1给出。全部的状态总数为(5×5)×5×4=500。
这个问题中的动作是取自{0,1,2,3,4,5}的int型数值，其含义下表所示。表中还给出了对应的env.render()函数给出的文字提示以及执行动作后可能得到的奖励值。
代码清单给出了初始化环境并玩一步的代码。初始化后，借助env.decode()获得了出租车、乘客和目的地的位置，并将地图显示出来，接着试图玩了一步。
import gym
env = gym.make('Taxi-v2')
state = env.reset()
taxirow, taxicol, passloc, destidx = env.unwrapped.decode(state)
print(taxirow, taxicol, passloc, destidx)
print('出租车位置 = {}'.format((taxirow, taxicol)))
print('乘客位置 = {}'.format(env.unwrapped.locs[passloc]))
print('目标位置 = {}'.format(env.unwrapped.locs[destidx]))
env.render()
env.step(1)至此，我们已经会使用这个环境了。
同策时序差分学习调度
本节我们使用SARSA算法和期望SARSA算法来学习策略。
首先我们来看SARSA算法。以下代码中的SARSAAgent类play_sarsa()函数共同实现了SARSA算法。其中，SARSAAgent类包括了智能体的学习逻辑和判决逻辑，是智能体类；play_sarsa()函数实现了智能体和环境交互的逻辑。play_sarsa()函数有两个bool类型的参数，参数train表示是否对智能体进行训练，参数render表示是否用对人类友好的方式显示当前环境。这里把SARSA算法拆分成一个智能体类和一个描述智能体和环境交互的函数，是为了能够更加清晰地将智能体的学习和决策过程隔离开来。智能体和环境的交互过程可以为许多类似的智能体重复使用。例如，play_sarsa()函数不仅在SARSA算法中被使用，还会被本章后续的SARSA(λ)算法使用，甚至被后续章节使用。
class SARSAAgent:
def __init__(self, env, gamma=0.9, learning_rate=0.2, epsilon=.01):
self.gamma = gamma
self.learning_rate = learning_rate
self.epsilon = epsilon
self.action_n = env.action_space.n
self.q = np.zeros((env.observation_space.n, env.action_space.n))
def decide(self, state):
if np.random.uniform() > self.epsilon:
action = self.q[state].argmax()
else:
action = np.random.randint(self.action_n)
return action
def learn(self, state, action, reward, next_state, done, next_action):
u = reward + self.gamma * \
self.q[next_state, next_action] * (1. - done)
td_error = u - self.q[state, action]
self.q[state, action] += self.learning_rate * td_errorSARSA智能体与环境交互一回合
def play_sarsa(env, agent, train=False, render=False):
episode_reward = 0
observation = env.reset()
action = agent.decide(observation)
while True:
if render:
env.render()
next_observation, reward, done, _ = env.step(action)
episode_reward += reward
next_action = agent.decide(next_observation) # 终止状态时此步无意义
if train:
agent.learn(observation, action, reward, next_observation,
done, next_action)
if done:
break
observation, action = next_observation, next_action
return episode_reward智能体在初始化时，先根据状态空间和动作空间的大小初始化q ( s , a ) , s ∈ S , a ∈ A q(s,a),s∈\mathcal{S},a∈\mathcal{A}q(s,a),s∈S,a∈A。在判决时，使用了ε贪心策略。下面给出了训练SARSA算法的代码。该代码调用play_sarsa()函数5000次，运行了5000回合的环境进行训练。
# 训练
episodes = 3000
episode_rewards = []
for episode in range(episodes):
episode_reward = play_sarsa(env, agent, train=True)
episode_rewards.append(episode_reward)
plt.plot(episode_rewards)
# 测试
agent.epsilon = 0. # 取消探索
episode_rewards = [play_sarsa(env, agent) for _ in range(100)]
print('平均回合奖励 = {} / {} = {}'.format(sum(episode_rewards),
len(episode_rewards), np.mean(episode_rewards)))
测试结果平均总奖励数值一般在6～8.5之间。增加迭代次数往往能进一步提高性能。
agent.epsilon = 0. # 取消探索
episode_rewards = [play_sarsa(env, agent) for _ in range(100)]
print('平均回合奖励 = {} / {} = {}'.format(sum(episode_rewards),
len(episode_rewards), np.mean(episode_rewards)))如果我们要显示最优价值估计，可以使用以下语句：
pd.DataFrame(agent.q)
如果显示最优策略估计，可以使用以下语句：
policy = np.eye(agent.action_n)[agent.q.argmax(axis=-1)]
pd.DataFrame(policy)
接下来使用期望SARSA算法求解最优策略。ExpectedSARSAAgent类实现了期望SARSA智能体类。
class ExpectedSARSAAgent:
def __init__(self, env, gamma=0.9, learning_rate=0.1, epsilon=.01):
self.gamma = gamma
self.learning_rate = learning_rate
self.epsilon = epsilon
self.q = np.zeros((env.observation_space.n, env.action_space.n))
self.action_n = env.action_space.n
def decide(self, state):
if np.random.uniform() > self.epsilon:
action = self.q[state].argmax()
else:
action = np.random.randint(self.action_n)
return action
def learn(self, state, action, reward, next_state, done):
v = (self.q[next_state].mean() * self.epsilon + \
self.q[next_state].max() * (1. - self.epsilon))
u = reward + self.gamma * v * (1. - done)
td_error = u - self.q[state, action]
self.q[state, action] += self.learning_rate * td_errorplay_qlearning()函数实现了期望SARSA智能体与环境的交互。这里的交互函数命名为play_qlearning，是因为期望SARSA智能体的交互函数和后续Q学习的交互函数相同。
def play_qlearning(env, agent, train=False, render=False):
episode_reward = 0
observation = env.reset()
while True:
if render:
env.render()
action = agent.decide(observation)
next_observation, reward, done, _ = env.step(action)
episode_reward += reward
if train:
agent.learn(observation, action, reward, next_observation,
done)
if done:
break
observation = next_observation
return episode_reward实现了期望SARSA算法后，下面是训练和测试期望SARSA算法的代码。期望SARSA算法在这个问题中的性能往往比SARSA算法要好一些。
episodes = 5000
episode_rewards = []
for episode in range(episodes):
episode_reward = play_qlearning(env, agent, train=True)
episode_rewards.append(episode_reward)
plt.plot(episode_rewards);
agent.epsilon = 0. # 取消探索
episode_rewards = [play_qlearning(env, agent) for _ in range(100)]
print('平均回合奖励 = {} / {} = {}'.format(sum(episode_rewards),
len(episode_rewards), np.mean(episode_rewards)))
异策时序差分调度
本节我们使用Q学习和双重Q学习来学习最优策略。
首先来看Q学习算法。QLearningAgent智能体类和play_qlearning()函数一起实现了Q学习算法。QLearningAgent类和ExpectedSARSAAgent类的区别在于learn()函数内自益的方法不同。
class QLearningAgent:
def __init__(self, env, gamma=0.9, learning_rate=0.1, epsilon=.01):
self.gamma = gamma
self.learning_rate = learning_rate
self.epsilon = epsilon
self.action_n = env.action_space.n
self.q = np.zeros((env.observation_space.n, env.action_space.n))
def decide(self, state):
if np.random.uniform() > self.epsilon:
action = self.q[state].argmax()
else:
action = np.random.randint(self.action_n)
return action
def learn(self, state, action, reward, next_state, done):
u = reward + self.gamma * self.q[next_state].max() * (1. - done)
td_error = u - self.q[state, action]
self.q[state, action] += self.learning_rate * td_error接下来看双重Q学习算法。DoubleQLearningAgent类和play_qlearning()函数一起实现了双重Q学习算法。双重Q学习涉及两组动作价值估计，DoubleQLearnignAgent类和QLearningAgent类在构造函数、decide()函数和learn()函数都有区别。在该问题中，最大化偏差并不明显，所以双重Q学习往往不能得到好处。
class DoubleQLearningAgent:
def __init__(self, env, gamma=0.9, learning_rate=0.1, epsilon=.01):
self.gamma = gamma
self.learning_rate = learning_rate
self.epsilon = epsilon
self.action_n = env.action_space.n
self.q0 = np.zeros((env.observation_space.n, env.action_space.n))
self.q1 = np.zeros((env.observation_space.n, env.action_space.n))
def decide(self, state):
if np.random.uniform() > self.epsilon:
action = (self.q0 + self.q1)[state].argmax()
else:
action = np.random.randint(self.action_n)
return action
def learn(self, state, action, reward, next_state, done):
if np.random.randint(2):
self.q0, self.q1 = self.q1, self.q0
a = self.q0[next_state].argmax()
u = reward + self.gamma * self.q1[next_state, a] * (1. - done)
td_error = u - self.q0[state, action]
self.q0[state, action] += self.learning_rate * td_error
资格迹学习调度
class SARSALambdaAgent(SARSAAgent):
def __init__(self, env, lambd=0.6, beta=1.,
gamma=0.9, learning_rate=0.1, epsilon=.01):
super().__init__(env, gamma=gamma, learning_rate=learning_rate,
epsilon=epsilon)
self.lambd = lambd
self.beta = beta
self.e = np.zeros((env.observation_space.n, env.action_space.n))
def learn(self, state, action, reward, next_state, done, next_action):
# 更新资格迹
self.e *= (self.lambd * self.gamma)
self.e[state, action] = 1. + self.beta * self.e[state, action]
# 更新价值
u = reward + self.gamma * \
self.q[next_state, next_action] * (1. - done)
td_error = u - self.q[state, action]
self.q += self.learning_rate * self.e * td_error
if done:
self.e *= 0.本节使用SARSA(λ)算法来学习策略。代码实现了SARSA(λ)算法智能体类SARSALambdaAgent类，它由代码清单5-2中的SARSAAgent类派生而来。与SARSAAgent类相比，它多了需要控制衰减速度的参数lambd和控制资格迹增加的参数beta。值得一提的是，lambda是Python的关键字，所以这里不用lambda作为变量名，而是用去掉最后一个字母的lambd作为变量名。由于引入了资格迹，所以SARSA(λ)算法的性能往往比单步SARSA算法要好。
在这一节中，我们尝试了很多算法，有些算法的性能相对另外一些较好。其中的原因比较复杂，可能是算法本身的问题，也可能是参数选择的问题。没有一个算法是对所有的任务都有效的。可能对于这个任务，这个算法效果好；换了一个任务后，另外一个算法效果好。
结论
无模型时序差分更新方法，包括了同策时序差分算法SARSA算法和期望SARSA算法，以及异策时序差分算法Q学习和双重Q学习算法。各种算法的主要区别在于更新目标Ut具有
不同的表达式。最后还介绍了历史上具有重大影响力的资格迹算法。
