强化学习|[强化学习实战]出租车调度-Q learning & SARSA 算法|python|强化学习

出租车调度-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 actiondef 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_error

SARSA智能体与环境交互一回合

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.ndef decide(self, state): if np.random.uniform() > self.epsilon: action = self.q[state].argmax() else: action = np.random.randint(self.action_n) return actiondef 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_error

play_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 actiondef 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 actiondef 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

资格迹学习调度本节使用SARSA(λ)算法来学习策略。代码实现了SARSA(λ)算法智能体类SARSALambdaAgent类，它由代码清单5-2中的SARSAAgent类派生而来。与SARSAAgent类相比，它多了需要控制衰减速度的参数lambd和控制资格迹增加的参数beta。值得一提的是，lambda是Python的关键字，所以这里不用lambda作为变量名，而是用去掉最后一个字母的lambd作为变量名。由于引入了资格迹，所以SARSA(λ)算法的性能往往比单步SARSA算法要好。

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.

在这一节中，我们尝试了很多算法，有些算法的性能相对另外一些较好。其中的原因比较复杂，可能是算法本身的问题，也可能是参数选择的问题。没有一个算法是对所有的任务都有效的。可能对于这个任务，这个算法效果好；换了一个任务后，另外一个算法效果好。
结论 【强化学习|[强化学习实战]出租车调度-Q learning & SARSA】无模型时序差分更新方法，包括了同策时序差分算法SARSA算法和期望SARSA算法，以及异策时序差分算法Q学习和双重Q学习算法。各种算法的主要区别在于更新目标Ut具有不同的表达式。最后还介绍了历史上具有重大影响力的资格迹算法。