5. 表格法& Bellman方程

5.1 价值、状态、优化

强化学习中，价值value、状态state、优化optimality，这三个元素非常重要。强化学习中我们要优化实现的目标是最佳的行动action路径。

可以简单设想一下，我们人在做选择的时候，如果有plan A和plan B，我们会去比较两者中间哪一个方案给我们带来的“效用”最高。尽管这里也是个主观的效用估计判断，大概率不准，但他是我们经常做选择的依据。而这里对于效用的主观判断，我们在机器人的世界里，假设机器也有类似的自己对于不同方案的效用评判标准，我们也就将其定义为RL中的价值（value）。

而状态则是回答“在哪儿？”的问题。对于当前所处环境变量的一个抽象表述。就好比汽车到了红绿灯路口，决定是否通过，要依赖于红绿灯颜色这个环境变量一样。所有的行动选择应该基于选择时所处的状态。

优化行动选择就更直接，类似在回答“去哪儿”的问题。当我们看到红灯的时候，优化的选择是停下来等红灯变绿。

状态价值的表达和内涵

其实脱离行动方案谈某个状态的价值是没有意义的。举个简单的例子，场景如下：

初始状态为，如果agent在状态面临两种行为选择，一种是向右移动到达状态，并获得回报，行动终止；一种是向左移动到达状态，获得回报，行动终止。

在这个场景中，如何评判状态的价值呢？其实在不知道具体的行动方案（policy）的情况下，的结果有很多种。

• policy 1: 总是向右移动，
• policy 2: 总是向左移动，
• policy 3: 以一定概率向左移动，

从这个例子可以看出最佳的方案肯定是policy 2。在状态始终保持向左移动。

上面是个单步的例子，如果多步呢？

现实中，我们很多时候做出的决策不是一锤子买卖。不仅要考虑当前行为带来的“即时回报”，还要考虑后续的回报。比如在上面的场景中做一点调整。假定从出发在第一步到达状态之后，并不是终点。状态之后还有唯一个去处状态，到达后终止。状态到状态将发生回报损失

此时最佳行动方案就会发生变化。显然，总是在状态时向右移动为最佳policy。因为多步来看，在状态向左移动，后续损失会更多。

5.2 Bellman方程

做个简单的设想，在时刻的价值假设为，那么的高低，既取决于当前选择行为之后的即期回报，也取决于未来的价值。因此有：

可以看出，当行动方案policy有了，其实计算状态行为价值其实就是个递归迭代。结合优化，我们递归的过程想实现一个最大化价值的结果。通俗点说，我们每步决策都想选择最有利的行动方案，那么我们可以感谢Richard Bellman了。大佬帮我们证明过了，每步最佳，连续的结果也是最佳。所以，我们实践中上面那个式子其实下面这样表达：

为可选择的行动集合。

上述为确定性场景，但也很容易扩展应用至随机场景。

这里的随机场景简单的理解就是当做出行为选择后，下一步的状态可能存在不确定性。就好比我们在这个十字路口等了红灯，并不知道下个十字路口将会遇到什么颜色的交通灯。这种扩展到随机场景也很简单，不就是把下一步每种可能性都遍历一遍，求个期望价值么？所以通常我们会把前面大家看到的式子进一步写成下面这种形式：

表示时刻状态下的价值等于选择最佳那个行动之后的即时回报加上以各种可能到达的新的状态时的价值折现。

也许有人会有疑问？这个递归的迭代式怎么计算，未来的情况并不知道。尤其是无终止状态的场景。有终止状态的可以利用Bellman方程从后往前算。这里就涉及到我们用来做表格强化学习的核心了。在算法领域经常可能会遇到这种方法。假定已知，不断根据新的信息来修改，期望它向我们真实想要求的那个结果收敛。

由前文可知，对于i时刻的状态价值本身的计算若不考虑行动方案，可以有多个结果。所以单独谈状态价值是没有意义的。通常我们谈的状态价值，其实是这个状态下可以获得的最大化的那个价值。所以一般情况未特别说明的时候，。

我们实践中设计迭代算法为了方便，把对应状态，可以获得的最大化那个价值就表达为。所以大家经常听到Q-learning这个说法。Q-learning就是寻找使得每步价值都最大化的过程，同时还能得到使得价值最大化所应该选择的行为路径。

1: 初始化所有状态行为的Q(s, a)=0.0
2: 观察当前状态s
3: 选择行为a = argmax(Q(s, a))
4: 执行a后，观察状态s → s'
5: 获得即期回报r(s → s', a)
6: Q(s, a)=Q(s, a)+alpha*(r(s → s', a)+gamma*Q(s', a)-Q(s, a))
7: 返回2，直至收敛。

表格法的迭代方法很简单，如上。这个迭代其实已经是Q-learning了。如果是value迭代怎么做呢? 其实理解了状态的value是max之后的那一个，那么value iteration与表格法的Q-learning并没有本质的区别。

价值迭代

表格法实现价值迭代，下面的例子中用到三张表。

• 回报表（reward table）：这个表用来记录回报值。注意这里需要用复合键值的字典。因为每一个回报共同决定。即状态下选择行为并过渡到状态所获得的回报。
• 状态转移表（transitions table）：由于随机场景中，在状态下执行行为并不能确定转移到某个状态。于是，我们可以在不断尝试的过程中记录状态下执行行为之后到达不同状态的次数，进而来表达状态下执行行为到其他状态的转移概率。
• 状态价值表（value table）：用来记录不同状态的价值数据（再次提醒一下，状态价值离不开行动方案，单纯的说状态价值，指的是在该状态选择优化行为maximized的那个价值）。

#!/usr/bin/env python3
import gym
import collections
from tensorboardX import SummaryWriter
# 以上导入相关的package


ENV_NAME = "FrozenLake-v0"
GAMMA = 0.9
TEST_EPISODES = 20
# 全局参数设定，例子用的gym提供的FrozenLake场景
# gamma 为计算远期价值的折现因子参数
# 测试的回合数为20

class Agent:
    def __init__(self):  # 智能体的初始化
        self.env = gym.make(ENV_NAME)  # 初始化的同时定义环境为FrozenLake
        self.state = self.env.reset()  # 初始化的同时给出行动的初始状态
        
        # 创建回报表、状态转移表、状态价值表
        # 全部为符合键值类型
        self.rewards = collections.defaultdict(float) 
        self.transits = collections.defaultdict(collections.Counter)
        self.values = collections.defaultdict(float)

    def play_n_random_steps(self, count):
        # 产生随机的count大小的步数，收集回报、状态转移信息
        for _ in range(count):
            # 从env提供的可选行为中随机抽取行为，注意和未来要讲的贪婪行为区分
            # 这里非greedy选行为，完全就是各种试错
            # 错了没关系，会累积错的经验
            action = self.env.action_space.sample()
            # env.step环境向前推进一步，获取执行action后的下一步状态、回报、是否结束等信息
            new_state, reward, is_done, _ = self.env.step(action)
            # 更新回报表、状态转移表
            self.rewards[(self.state, action, new_state)] = reward
            self.transits[(self.state, action)][new_state] += 1
            # 如果回合没有结束，循环。如果结束则重置状态进行下一个episode。
            # 直到步数到达count
            self.state = self.env.reset() if is_done else new_state

    def calc_action_value(self, state, action):  # 计算状态行动价值
        # 先计算state时，选择action的次数总和
        target_counts = self.transits[(state, action)]
        total = sum(target_counts.values())
        # 初始化行动价值为0.0
        action_value = 0.0
        # 由于state下选择action可能到达很多不同的状态
        # 因此根据不同可能到达的状态分别计算回报
        # 最后按照count/total到达不同状态的次数占比进行加权得到
        # state时选择action的value
        for tgt_state, count in target_counts.items():
            reward = self.rewards[(state, action, tgt_state)]
            action_value += (count / total) * (reward + GAMMA * self.values[tgt_state])
        return action_value

    def select_action(self, state):  # 选择行为
        # best_action和best_value用来记录当前信息下的最佳行为和价值
        best_action, best_value = None, None
        for action in range(self.env.action_space.n): # 遍历环境提供的行为集
            # 逐一计算action_value
            action_value = self.calc_action_value(state, action)
            if best_value is None or best_value < action_value:
                best_value = action_value
                best_action = action
        return best_action

    def play_episode(self, env):  # 注意这里和前面随机步数尝试的区别
        # play_episode中用到了选择最佳行为的方法
        # 因此使用play_episode时，agent已经具有greedy属性了
        # 注意这里调用一次，只执行完一个回合episode
        total_reward = 0.0
        state = env.reset()
        while True:
            action = self.select_action(state)
            new_state, reward, is_done, _ = env.step(action)
            self.rewards[(state, action, new_state)] = reward
            self.transits[(state, action)][new_state] += 1
            total_reward += reward
            if is_done:
                break
            state = new_state
        return total_reward

    def value_iteration(self):  # 这里就是把状态行动价值最大的找出来作为状态价值
        for state in range(self.env.observation_space.n):
            state_values = [self.calc_action_value(state, action)
                            for action in range(self.env.action_space.n)]
            self.values[state] = max(state_values)

Agent的各项功能定义完毕之后就是训练Agent的过程。代码如下：

if __name__ == "__main__":
    test_env = gym.make(ENV_NAME)
    agent = Agent()
    writer = SummaryWriter(comment="-v-iteration")

    iter_no = 0
    best_reward = 0.0
    while True:
        iter_no += 1
        agent.play_n_random_steps(100)
        agent.value_iteration()

        reward = 0.0
        # 注意这里测试价值迭代效果的时候也对三张表进行了更新
        for _ in range(TEST_EPISODES):
            reward += agent.play_episode(test_env)
        reward /= TEST_EPISODES
        writer.add_scalar("reward", reward, iter_no)
        if reward > best_reward:
            print("Best reward updated %.3f -> %.3f" % (best_reward, reward))
            best_reward = reward
        if reward > 0.80:
            print("Solved in %d iterations!" % iter_no)
            break
    writer.close()

运行结果如下：

从tensorboard输出结果可以看到，Agent通过价值迭代实现了回报的提升，在解决FrozenLake的问题上表现越来越好。

Q-learning

Q-learning与前面价值迭代本质是一致的。细节的区别主要体现在select_action和value_iteration这两个方法上。

由于Q-learning把(state, action)组合在一起考虑，因此在选择行为的时候只需要把self.values中以（state，action）为键值对应的最大的value找出来即可。由于state和action组合在一起考虑，self.values的存储结构和价值迭代里不一样。这个在value_iteration()方法中体现。关键的一行代码：self.values[(state, action)] = action_value

    def select_action(self, state):
        best_action, best_value = None, None
        for action in range(self.env.action_space.n):
            action_value = self.values[(state, action)]
            if best_value is None or best_value < action_value:
                best_value = action_value
                best_action = action
        return best_action

    def value_iteration(self):
        for state in range(self.env.observation_space.n):
            for action in range(self.env.action_space.n):
                action_value = 0.0
                target_counts = self.transits[(state, action)]
                total = sum(target_counts.values())
                for tgt_state, count in target_counts.items():
                    reward = self.rewards[(state, action, tgt_state)]
                    best_action = self.select_action(tgt_state)
                    action_value += (count / total) * (reward + GAMMA * self.values[(tgt_state, best_action)])
                self.values[(state, action)] = action_value