一个强化学习的入门者，仅用于自己学习的记录

强化学习

• OpenAI出品的强化学习 (RL) 入门教程，Spinning Up

Q-learining 算法

• Q-learining 算法 不错的教程

Pytorch 强化学习算法实现

https://github.com/p-christ/Deep-Reinforcement-Learning-Algorithms-with-PyTorch

# 讲的很详细, 循序渐进，含有代码，很适合入门

• 动手学系强化学习

DQN算法

• 很详细的DQN算法

一些概念

• 当前累计奖励增量更新：
  

• 占用度量： 归一化的占用度量用于衡量在一个智能体决策与一个动态环境的交互过程中，采样到一个具体的状态动作对（state-action pair）的概率分布

  给定两个策略及其与一个动态环境交互得到的两个占用度量，那么当且仅当这个两个占用度量相同时，这两个策略相同。

• 策略： 指的是智能体在不同的状态下如何选择动作。 强化学习的策略在训练过程中不断的更新， 一个策略对应的价值就是一个占用度量下对应的奖励的期望。 因此寻找平最优策略就是寻找最优占用度量。

• 强化学习最终的目标就是寻找最优策略，使智能体和环境交互中的价值最大化。

马尔可夫过程

• 状态之间的转移， 用元祖表示，其中 表示状态的集合， 表示状态转移的概率矩阵
• 给定一个马尔可夫的过程， 我们可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤叫做采样(sampling)

马尔可夫奖励

• 在马尔可夫过程中加入奖励因子和折扣因子, 就得到马尔可夫奖励过程（MRP）。
• 在一个马尔可夫奖励过程中，从时刻的状态开始直到终止状态时，所有奖励的衰减之和称为回报。
  
  其中表示时刻获取的奖励。

这里我的理解是，因为从某个状态开始， 按照概率转移矩阵就可以获取下一个状态，假设可以走到终止状态。这时候形成的序列中，有些状态会出现多次，有些出现一次，有些甚至不出现。假设采样了一个的状态序列为, 那么在第时刻（本质上就是采样的顺序）的期望回报就是按照上面的公式计算整个序列，序列中也可能会包含同样的状态, 比如第时刻的。

价值函数

• 在马尔科夫奖励中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望），称为这个状态的价值。 所有状态的价值就组成了价值函数，价值函数的输入为某个状态，输出为这个状态的价值：
  

• 利用状态转移矩阵，可得到贝尔曼方程计算状态价值函数：
  
  是 状态获取的即时奖励。

• 将上式子写成矩阵的方式：
  

马尔可夫决策

• 在马尔科夫奖励过程中加上动作，就称为马尔可夫决策过程。

• 智能体的策略用表示，策略函数 表示输入状态为时，采用动作的概率。

• 基于策略的状态价值函数为：
  

• 动作价值函数表示马尔可夫决策过程遵循决策时， 对当前状态执行动作得到的期望回报：
  

• 状态价值函数和动作价值函数的关系：
  

综上得到状态价值函数和动作价值函数的贝尔曼期望方程：

• 马尔可夫决策中状态的奖励，通过动作边缘化：
  
• 马尔可夫决策中状态的转移概率，通过动作边缘化：
  
• 这是马尔卡夫决策过程就转换为马尔可夫奖励

蒙特卡洛方法（要先完成序列采样）

• 使用蒙特卡洛方法来估计一个策略在一个马尔可夫奖励过程中的状态价值函数：
  
• 根据上述公式，当计算一个状态的期望回报时，可以使用策略在MDP上采样很多条序列，计算从这个状态出发的回报再求期望。
• 简单的说，就是不断的进行序列采样，计算采样到状态的累计奖励。

1. 使用策略 采样若干条序列:

2. 对每一条序列中的每一时间步 的状态 进行以下操作:

• 更新状态 的计数器 ;
• 更新状态 的总回报 ;

3. 每一个状态的价值被估计为回报的平均值 。

• 状态在序列中出现一次，就计算一次期望回报，当采样很多次序列时，假设状态出现了次，求均值就行。
  根据大数定律，当 ，有 。计算回报的期望时，除了可以把所有的回报加起来除以次数，还有一种增量更新的方法。对于每个状态 和对应回报 ，进行如下计算:

  • 
  • 

• 核心代码 （在这里是按照逆序列更新的）

def MC(episodes, V, N, gamma):
    # episodes 采样的序列列表【[s0---> s2--->s4--->....s_结束], [s0---> s3--->s8--->....s_结束],...】
    for episode in episodes:
    # episode  一个序列[s0---> s2--->s4--->....s_结束]
        G = 0
        for i in range(len(episode) - 1, -1, -1):  #一个序列从后往前计算
            (s, a, r, s_next) = episode[i]
            # 即使奖励+折扣回报
            G = r + gamma * G
            # 计数器
            N[s] = N[s] + 1
            # 更新状态s的价值
            V[s] = V[s] + (G - V[s]) / N[s]

• 不同策略访问到的状态的概率分布是不同的，因此策略的状态价值函数是不同的。

动态规划（必须知道转移概率矩阵）

策略迭代

• 策略评估: 使用贝尔曼期望方程来得到一个策略的状态价值函数， 当我们知道奖励函数和状态转移函数，根据下一个状态的价值来计算当前状态。根据动态规划的思想，把计算下一个可能状态的价值当做一个子问题， 把计算当前状态的价值看作当前问题。 在得知子问题的解后，就可以求解当前问题。更一般的，考虑所有的状态，就变成了用上一轮的状态价值函数来计算当前这一轮的状态价值函数，即
  当 ，. 由于不断需要做贝尔曼期望方程的迭代，策略评估需要很大的计算代价，实际中，某轮的值非常小，则可以结束。

• 这里完全没看懂。。。很模糊。贝尔曼方程是根据下一个状态计算当前状态，怎么就成了使用上一轮状态计算当前这一轮的了？ 代表的是每一轮。

• 虽然看懂代码的过程了，但是还不明白为啥这么算？ 代码的过程是，每轮遍历所有的状态和动作，然后利用上一轮计算的状态价值，使用贝尔曼来更新当前这一轮的状态价值，然后执行很多轮。。。也就是不断使用贝尔曼方程计算状态价值，一直到收敛。
• 突然又想明白了，在计算当前状态时，无法知道下一个状态的值，因此，就是用上一轮获取的下一个状态的值来计算。 另一个问题是，为何要一轮一轮的计算？ 每一轮代表的是什么?

• 策略提升： 假设智能体在某一个状态采取动作之后的动作依旧遵循策略, 此时得到的期望回报就是动作价值， 如果有， 说明在该状态下存在一个更好的策略回报更高。现在假设存在一个策略， 在任意一个状态下，都满足 , 则任意状态下有：

• 我们可以直接贪心地在每一个状态选择动作价值最大的动作，也就是在状态中，选择动作价值最大的那些：
  

• 策略迭代和价值迭代通常只用于有限的马尔科夫决策，即状态空间和动作空间是离散的。

策略迭代是 策略评估和策略提升不断循环交替，直至最后得带最优策略的过程。 对当前测策略进行策略评估，得到其状态价值函数，然后根据该状态价值函数进行策略提升得到一个更好的新策略，持续进行。。。直到收敛。

价值迭代 ： 使用贝尔曼最优方程进行动态规划，得到最终的最优状态价值

• 如果只在策略评估中进行一轮价值更新，然后直接根据更新后的价值进行策略提升，这样是否可以呢？答案是肯定的

为啥是肯定的？

• 价值迭代的更新方式， 就是始终选择最大的动作价值：
  

• 在策略迭代中：策略评估---策略提升---策略评估---策略提升---策略评估---策略提升---策略评估。。。。一直进行下午，直到收敛, 这时就可以获取策略了， 其中策略评估需要很多轮
• 在价值迭代在中： 价值评估----获取策略， 就结束了, 其中价值评估也是很多轮（明显少于策略评估的轮数）。
• 我的理解是，价值评估中， 每次选择的都是最优价值进行评估，加快了收敛速度

时序差分

• 无模型的强化学习（model-free reinforcement learning）：马尔可夫决策过程的状态转移矩矩阵无法直接获取，也不知道奖励函数，智能体只能和环境交互采样数据进行学习。
• 在线策略学习： 使用在当前策略采样得到的样本进行学习， 一旦策略更新，样本被抛弃
• 离线策略学习： 使用经验回放池将之前采样得到的样本手机起来再次利用
• 蒙塔卡洛的价值增量更新为： 。 需要采样很多序列，序列中每个状态可能出现很多次，按照顺序记为时刻，表示第时刻的状态。蒙特卡洛需要采样整个序列结束后计算回报。
• 时序差分，用当前获取的奖励加上下一个状态的奖励的价值估计来作为当前状态的回报：
  ,
  其中被称为时序差分, 是更新步长。本质上， 。

Sarsas算法， 在线策略

• 在不知道奖励函数和状态转移函数的情况下，如何进行策略提升？使用时序差分来估计动作价值函数
  

• Sarsa 的具体算法如下：

  
  
  Saras
• 核心代码

class Sarsa:
    """ Sarsa算法 """
    def __init__(self, ncol, nrow, epsilon, alpha, gamma, n_action=4):
        self.Q_table = np.zeros([nrow * ncol, n_action])  # 初始化Q(s,a)表格
        self.n_action = n_action  # 动作个数
        self.alpha = alpha  # 学习率
        self.gamma = gamma  # 折扣因子
        self.epsilon = epsilon  # epsilon-贪婪策略中的参数

    def take_action(self, state):  # 选取下一步的操作,具体实现为epsilon-贪婪
        if np.random.random() < self.epsilon:
            action = np.random.randint(self.n_action)
        else:
            action = np.argmax(self.Q_table[state])
        return action

    def update(self, s0, a0, r, s1, a1):
        td_error = r + self.gamma * self.Q_table[s1, a1] - self.Q_table[s0, a0]
        self.Q_table[s0, a0] += self.alpha * td_error

• 训练核心

            # 根据state先拿到action 
            action = agent.take_action(state)
            done = False
            while not done:
              # 根据当前的action,拿到下一个状态和即时奖励
                next_state, reward, done = env.step(action)
                # 采样下一个action
                next_action = agent.take_action(next_state)
                episode_return += reward  # 这里回报的计算不进行折扣因子衰减
                agent.update(state, action, reward, next_state, next_action, done)
                state = next_state
                action = next_action

Q-learning 算法 ，离线策略

• Q-learning的价值更新：
  

• 具体流程;

  
  
  Q-learning
• 核心代码

class QLearning:
    """ Q-learning算法 """
    def __init__(self, ncol, nrow, epsilon, alpha, gamma, n_action=4):
        self.Q_table = np.zeros([nrow * ncol, n_action])  # 初始化Q(s,a)表格
        self.n_action = n_action  # 动作个数
        self.alpha = alpha  # 学习率
        self.gamma = gamma  # 折扣因子
        self.epsilon = epsilon  # epsilon-贪婪策略中的参数

    def take_action(self, state):  #选取下一步的操作
        if np.random.random() < self.epsilon:
            action = np.random.randint(self.n_action)
        else:
            action = np.argmax(self.Q_table[state])
        return action

    def update(self, s0, a0, r, s1):
        td_error = r + self.gamma * self.Q_table[s1].max() - self.Q_table[s0, a0]
        self.Q_table[s0, a0] += self.alpha * td_error

• 训练核心

         while not done:
                # 直接根据state获取action
                action = agent.take_action(state)
                # 根据action 获取下一个状态和即时奖励
                next_state, reward, done = env.step(action)
                episode_return += reward  # 这里回报的计算不进行折扣因子衰减
                agent.update(state, action, reward, next_state)
                state = next_state

离线和在线策略的差异

• 我们称采样数据的策略为行为策略， 用这些数据来更新的策略为目标策略
• 在线策略（on-policy）算法表示行为策略和目标策略是同一个策略
• 离线策略（off-policy）算法表示行为策略和目标策略不是同一个策略
• Sarsa 是典型的在线策略算法，而 Q-learning 是典型的离线策略算法。判断二者类别的一个重要手段是看计算时序差分的价值目标的数据是否来自当前的策略
• 对于Sarsa , 更新涉及的五元组 来自当前策略的采样
• 对于Q-learning , 更新用到的四元组 ， 其中 和 是给定的， 和 不一定来自于当前策略。
  
  Sarsa 和 Q-learning 的对比

DQN算法（使用神经网络实现Q-learning算法）

• 写的很好
• Q-learning 需要维护状态-动作表，因此只适用有限状态-动作。
• 因此，使用神经网络来学习一个拟合函数，输入为状态, 输出每一个动作的值，也就是输出一个向量, 其中每个值代表了状态下执行动作的值。

现在最大的问题是，如何训练Q网络？ 神经网络需要损失函数来提供信号进行参数更新，如何设置损失？也就是如何为Q网络提供 有标签的样本训练网络？

• 由于Q-learning的更新过程为：
  
  它的目标就是使不断逼近
  因此，损失函数定义为（为神经网络的参数）：
  

经验回放

• 维护经验回放池， 将每个采样的的四元组数据（状态、动作、奖励、下一状态）存储到回放缓冲区中，训练 Q 网络的时候再从回放缓冲区中随机采样若干数据来进行训练。

1. 使样本满足独立假设。
2. 提高样本效率。

目标网络

• 更新目标时， 不断的逼近，由于时序差分的误差目标本身就包含神经网络的输出，因此，网络参数的变化导致目标也不短变化。 因此DQN使用了目标网络： 在训练中暂时将时序差分目标中的Q网络固定。因此，DQN使用两套Q网络：
  （1） 训练网络计算
  （2）目标网络计算

训练网络正常更新，每隔个step就将训练网络的参数同步到目标网络。

DDQN(Double DQN)

• 出现的原因： Q-learning会对高估。

Dueling DQN

• 当 比较大时， 是因为比较好还是比较好？ 所以定义一个优势函数
  可以理解为： 对于中某一步行动的改变（做出了动作）， 所带来的变化。简单理解，就是在一个状态上进行了一个所带来的变化。
• 由于
  我们不难推出:

状态价值来自于所有动作的动作价值函数的期望。

策略梯度算法

又看不懂了。。。。