强化学习

第16章强化学习(reinforcement learning)

Page371: MDP
在概率论和统计学中，马可夫决策过程（英语：Markov Decision Processes，缩写为 MDPs）提供了一个数学架构模型，用于面对部份随机，部份可由决策者控制的状态下，如何进行决策，以俄罗斯数学家安德雷·马尔可夫的名字命名。在经由动态规划与强化学习以解决最佳化问题的研究领域中，马可夫决策过程是一个有用的工具。
Page371: 奖赏(reward)
奖励函数定义了强化学习 Agent 的目标，它将环境的状态映射为一个数字（奖励），表现了该状态的内在愿望。Agent 的目标是最大限度地提高长期收益。
Page371: 马尔科夫决策过程(Markov Decision Process)
Markov Decision Process，通常用来描述强化学习任务：机器处于环境 $E$ 中，状态空间为 $X$ ，其中每个状态 $x \in X$ 是机器感知到的环境的描述；机器能采取的动作构成了动作空间 $A$ ；若某个动作 $a \in A$ 作用在当前状态 $x$ 上，则潜在的转移函数 $P$ 将使得环境从当前状态按某种概率转移到另一个状态；在转移到另一个状态的同时，环境会根据潜在的『奖赏』函数 $R$ 反馈给机器一个奖赏。
Page371: 强化学习(reinforcement learning)
强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。强化学习任务对应了四元组 $E = \langle \mathit{X,A,P,R} \rangle$ ，其中 $P: X \times A \times X \to \mathbb{R}$ 指定了状态转移概率， $R: X \times A \times X \to \mathbb{R}$ 指定了奖赏；在有的应用中，奖赏函数可能仅与状态转移有关，即 $R: X \times X \to \mathbb{R}$ 。
Page371: 再励学习
强化学习，亦称再励学习。
Page372: 策略(policy)
在环境中状态的转移、奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。机器要做的是通过在环境中不断地尝试而学得一个『策略』（policy） $\pi$ ，根据这个策略，在状态 $x$ 下就能得知要执行的动作 $a = \pi(x)$ 。简单来说，policy 是 Agent 的决策功能，规定了在 Agent 可能遇到的任何情况下应采取的行动。这是 Agent 的核心。策略有两种表示方法：一种是将策略表示为函数 $\pi: X \to A$ ，确定性策略常用这种表示；另一种是概率表示 $\pi: X \times A \to \mathbb{R}$ ，随机性策略常用这种表示， $\pi(x,a)$ 为状态 $x$ 下选择动作 $a$ 的概率，这里必须有 $\sum_a \pi(x,a) = 1$ 。在强化学习任务中，学习的目的就是要找到能使长期累积奖赏最大化的策略。
Page373: K-摇臂赌博机(K-armed bandit)
单步强化学习对应的理论模型，K-摇臂赌博机（K-armed bandit）有 K 个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。
Page374: ϵ-贪心
强化学习面临「探索-利用窘境」， $\epsilon$ -贪心法基于一个概率来对探索和利用进行折中：每次尝试时，以 $\epsilon$ 的概率进行探索，即以均匀概率随机选取一个摇臂；以 $1 - \epsilon$ 的概率进行利用，即选择当前平均奖赏最高的摇臂（若有多个，则最随机选择一个）。
Page374: 探索-利用窘境(Exploration-Exploitation dilemma)
若获知每个摇臂的期望奖赏，可采用「仅探索」法：将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。若执行奖赏最大的动作，则可采用「仅利用」法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。「探索」（即估计摇臂的优劣）和「利用」（即选择当前最优摇臂）这两者是矛盾的，因为尝试次数（即总投币数）有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的「探索-利用窘境」（Exploration-Exploitation dilemma）。
Page375: Softmax
Softmax 算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。若个摇臂的平均奖赏想当，则选取个摇臂的概率也相当；若某些摇臂的平均奖赏高于其他摇臂，则它们被选取的概率也明显更高。 Softmax 算法中摇臂概率的分配是基于 Boltzmann 分布： $P(k) = \frac {e^{\frac {Q(k)}{\tau}}}{\sum_{i=1}^K e^{\frac {Q(i)}{\tau}}}$ ，其中， $Q(i)$ 记录当前摇臂的平均奖赏； $\tau > 0$ 称为「温度」， $\tau$ 越小则平均奖赏高的摇臂被选取的概率越高。 $\tau$ 趋于 0 时 Softmax 将趋于「仅利用」， $\tau$ 趋于无穷大时 Softmax 则将趋于「仅探索」。
Page377: 有模型学习(model-based learning)
在已知模型的环境中学习称为「有模型学习」，即机器已对环境进行了建模，能在机器内部模拟出与环境相同或近似的情况。
Page377: 状态-动作值函数(state-action value function)
在模型已知时，对任意策略 $\pi$ 能估计出该策略带来的期望累积奖赏。令函数 $V^{\pi}(x)$ 表示从状态 $x$ 出发，使用策略 $\pi$ 所带来的累积奖赏；函数 $Q^{\pi}(x,a)$ 表示从状态 $x$ 出发，执行动作 $a$ 后再使用策略 $\pi$ 带来的累积奖赏。这里的 $V(\cdot)$ 称为「状态值函数」（state value function）， $Q(\cdot)$ 称为「状态-动作值函数」（state-action value function），分别表示指定「状态」上以及指定「状态-动作」上的累积奖赏。
Page377: 状态值函数(state value function)
见「状态-动作值函数」。
Page380: Bellman 等式
对于状态值函数，由于 MDP 具有马尔科夫性质，即系统下一时刻的状态仅由当前时刻的状态决定，不依赖于以往任何状态，于是值函数有很简单的递归形式。对于 $T$ 步累积奖赏有： $V_T^{\pi}(x) = \sum_{a \in A} \pi (x, a) \sum_{x' \in X} P_{x \to x'}^a \lgroup \frac {1}{T} R_{x \to x'}^a + \frac {T-1}{T} V_{T-1}^{\pi} (x') \rgroup$ ，这样的递归等式称为 Bellman 等式。
Page381: 策略迭代(policy iteration)
一种求解最优解的方法。从一个初始策略（通常是随机策略）出发，先进性策略评估，然后改进策略，评估改进的策略，再进一步改进策略，……不断迭代进行策略评估和改进，直到策略收敛、不再改进为止。这样的做法称为「策略迭代」（policy iteration）。
Page382: 值迭代(value iteration)
策略迭代算法在每次改进策略后都需重新进行策略评估，这通常比较耗时。由于策略改进和值函数的改进是一致的，因此可将策略改进视为值函数的改善。这种改善值函数的算法就称为值迭代（value iteration）算法。
Page382: 免模型学习(model-free learning)
在现实的强化学习任务中，环境的转移概率、奖赏函数往往很难得知，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境建模，则称为「免模型学习」（model-free learning）。
Page386: TD(Temporal Difference) 学习(393)
由于蒙特卡洛强化学习算法没有充分利用强化学习任务的 MDP 结构，因此效率要低很多。时序差分（Temporal Difference，简称 TD）学习则结合了动态规划与蒙特卡洛方法的思想，能做到更高效的免模型学习。
Page386: 时序差分学习(393)
同 TD 学习。
Page387: Sarsa 算法(390)
该算法每次更新值函数需前一步的状态（state）、前一步的动作（action）、奖赏值（reward）、当前状态（state）、将要执行的动作（action），因此得名 Sarsa 算法。Sarsa 让系统按照策略指引进行探索，在探索每一步都进行状态价值的更新，更新公式如下： $Q^\pi_{t+1} (x,a) = Q^\pi_t (x,a) + \alpha \lgroup R^\alpha_{x \to x'} + \gamma Q^\pi_t(x',a') - Q^\pi_t(x,a) \rgroup$ ，其中， $x'$ 是前一次在状态 $x$ 执行动作 $a$ 后转移到的状态， $a'$ 是策略 $\pi$ 在 $x'$ 上选择的动作。 Sarsa 是一个同策略（on-policy）算法，算法中的评估（上式）和执行（ $a' = \pi^\epsilon(x')$ ）的均为 $\epsilon$ -贪心策略。
Page387: Q-学习(393)(Q-learning)
将 Sarsa 修改为异策略（off-policy）算法，即动作值函数更新（评估）不同于选取动作（执行）时遵循的策略，就得到 Q-学习算法，Q-学习的动作值函数更新公式如下： $Q^\pi_{t+1} (x,a) = Q^\pi_t (x,a) + \alpha \lgroup R^\alpha_{x \to x'} + \gamma max_{a} Q^\pi_t(x',a) - Q^\pi_t(x,a) \rgroup$
Page388: 表格值函数(tabular value function)
如果我们假定强化学习任务是在有限状态空间上进行，每个状态可以用一个编号来指代；值函数就是关于有限状态的「表格值函数」（tabular value），也就是说值函数能表示为一个数组，输入 $i$ 对应的函数值就是数组元素 $i$ 的值，且更改一个状态上的值不影响其他状态上的值。
Page388: 值函数近似(value function approximation)
实际强化学习任务所面临的状态空间往往是连续的，有无穷多个状态。我们假定状态空间为 $n$ 维实数空间 $X = \mathbb{R}^n$ ，此时显然无法用表格值函数来记录状态值。但考虑简单情形，即值函数能表达为状态的线性函数： $V_\theta(x) = \theta^Tx$ ，其中 $x$ 为状态向量， $\theta$ 为参数向量。由于此时的值函数难以像有限状态那样精确记录每个状态的值，因此这样的值函数求解被称为值函数近似（value function approximation）。
Page390: 模仿学习(imitation learning)
在强化学习的经典任务设置中，机器所能获得的反馈信息仅有多步决策后的累计奖赏，但在现实任务中，往往能得到人类专家的决策过程范例。从这样的范例中学习，称为「模仿学习」（imitation learning）。
Page391: 逆强化学习(inverse reinforcement learning)
在很多任务中，设计奖赏函数往往相当困难，从人类专家提供的范例数据中反推出奖赏函数有助于解决该问题，这就是「逆强化学习」（inverse reinforcement learning）。逆强化学习的基本思想是：欲使机器做出与范例一致的行为，等价于在某个奖赏函数的环境中求解最优策略，该最优策略所产生的轨迹与范例数据一致。换言之，我们要寻找某种奖赏函数使得范例数据是最优的，然后即可使用这个奖赏函数来训练强化学习策略。
Page393: 近似动态规划(approximate dynamic programming)
强化学习在运筹学与控制论领域的研究被称为「近似动态规划」（approximate dynamic programming）。

最后更新于5年前

第16章强化学习(reinforcement learning)

Page371: MDP

在概率论和统计学中，马可夫决策过程（英语：Markov Decision Processes，缩写为 MDPs）提供了一个数学架构模型，用于面对部份随机，部份可由决策者控制的状态下，如何进行决策，以俄罗斯数学家安德雷·马尔可夫的名字命名。在经由动态规划与强化学习以解决最佳化问题的研究领域中，马可夫决策过程是一个有用的工具。

Page371: 奖赏(reward)

奖励函数定义了强化学习 Agent 的目标，它将环境的状态映射为一个数字（奖励），表现了该状态的内在愿望。Agent 的目标是最大限度地提高长期收益。

Page371: 马尔科夫决策过程(Markov Decision Process)

Markov Decision Process，通常用来描述强化学习任务：机器处于环境 $E$ 中，状态空间为 $X$ ，其中每个状态 $x \in X$ 是机器感知到的环境的描述；机器能采取的动作构成了动作空间 $A$ ；若某个动作 $a \in A$ 作用在当前状态 $x$ 上，则潜在的转移函数 $P$ 将使得环境从当前状态按某种概率转移到另一个状态；在转移到另一个状态的同时，环境会根据潜在的『奖赏』函数 $R$ 反馈给机器一个奖赏。

Page371: 强化学习(reinforcement learning)

强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。强化学习任务对应了四元组 $E = \langle \mathit{X,A,P,R} \rangle$ ，其中 $P: X \times A \times X \to \mathbb{R}$ 指定了状态转移概率， $R: X \times A \times X \to \mathbb{R}$ 指定了奖赏；在有的应用中，奖赏函数可能仅与状态转移有关，即 $R: X \times X \to \mathbb{R}$ 。

Page371: 再励学习

强化学习，亦称再励学习。

Page372: 策略(policy)

在环境中状态的转移、奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。机器要做的是通过在环境中不断地尝试而学得一个『策略』（policy） $\pi$ ，根据这个策略，在状态 $x$ 下就能得知要执行的动作 $a = \pi(x)$ 。简单来说，policy 是 Agent 的决策功能，规定了在 Agent 可能遇到的任何情况下应采取的行动。这是 Agent 的核心。策略有两种表示方法：一种是将策略表示为函数 $\pi: X \to A$ ，确定性策略常用这种表示；另一种是概率表示 $\pi: X \times A \to \mathbb{R}$ ，随机性策略常用这种表示， $\pi(x,a)$ 为状态 $x$ 下选择动作 $a$ 的概率，这里必须有 $\sum_a \pi(x,a) = 1$ 。在强化学习任务中，学习的目的就是要找到能使长期累积奖赏最大化的策略。

Page373: K-摇臂赌博机(K-armed bandit)

单步强化学习对应的理论模型，K-摇臂赌博机（K-armed bandit）有 K 个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

Page374: ϵ-贪心

强化学习面临「探索-利用窘境」， $\epsilon$ -贪心法基于一个概率来对探索和利用进行折中：每次尝试时，以 $\epsilon$ 的概率进行探索，即以均匀概率随机选取一个摇臂；以 $1 - \epsilon$ 的概率进行利用，即选择当前平均奖赏最高的摇臂（若有多个，则最随机选择一个）。

Page374: 探索-利用窘境(Exploration-Exploitation dilemma)

若获知每个摇臂的期望奖赏，可采用「仅探索」法：将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。若执行奖赏最大的动作，则可采用「仅利用」法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。「探索」（即估计摇臂的优劣）和「利用」（即选择当前最优摇臂）这两者是矛盾的，因为尝试次数（即总投币数）有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的「探索-利用窘境」（Exploration-Exploitation dilemma）。

Page375: Softmax

Softmax 算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。若个摇臂的平均奖赏想当，则选取个摇臂的概率也相当；若某些摇臂的平均奖赏高于其他摇臂，则它们被选取的概率也明显更高。 Softmax 算法中摇臂概率的分配是基于 Boltzmann 分布： $P(k) = \frac {e^{\frac {Q(k)}{\tau}}}{\sum_{i=1}^K e^{\frac {Q(i)}{\tau}}}$ ，其中， $Q(i)$ 记录当前摇臂的平均奖赏； $\tau > 0$ 称为「温度」， $\tau$ 越小则平均奖赏高的摇臂被选取的概率越高。 $\tau$ 趋于 0 时 Softmax 将趋于「仅利用」， $\tau$ 趋于无穷大时 Softmax 则将趋于「仅探索」。

Page377: 有模型学习(model-based learning)

在已知模型的环境中学习称为「有模型学习」，即机器已对环境进行了建模，能在机器内部模拟出与环境相同或近似的情况。

Page377: 状态-动作值函数(state-action value function)

在模型已知时，对任意策略 $\pi$ 能估计出该策略带来的期望累积奖赏。令函数 $V^{\pi}(x)$ 表示从状态 $x$ 出发，使用策略 $\pi$ 所带来的累积奖赏；函数 $Q^{\pi}(x,a)$ 表示从状态 $x$ 出发，执行动作 $a$ 后再使用策略 $\pi$ 带来的累积奖赏。这里的 $V(\cdot)$ 称为「状态值函数」（state value function）， $Q(\cdot)$ 称为「状态-动作值函数」（state-action value function），分别表示指定「状态」上以及指定「状态-动作」上的累积奖赏。

Page377: 状态值函数(state value function)

见「状态-动作值函数」。

Page380: Bellman 等式

对于状态值函数，由于 MDP 具有马尔科夫性质，即系统下一时刻的状态仅由当前时刻的状态决定，不依赖于以往任何状态，于是值函数有很简单的递归形式。对于 $T$ 步累积奖赏有： $V_T^{\pi}(x) = \sum_{a \in A} \pi (x, a) \sum_{x' \in X} P_{x \to x'}^a \lgroup \frac {1}{T} R_{x \to x'}^a + \frac {T-1}{T} V_{T-1}^{\pi} (x') \rgroup$ ，这样的递归等式称为 Bellman 等式。

Page381: 策略迭代(policy iteration)

一种求解最优解的方法。从一个初始策略（通常是随机策略）出发，先进性策略评估，然后改进策略，评估改进的策略，再进一步改进策略，……不断迭代进行策略评估和改进，直到策略收敛、不再改进为止。这样的做法称为「策略迭代」（policy iteration）。

Page382: 值迭代(value iteration)

策略迭代算法在每次改进策略后都需重新进行策略评估，这通常比较耗时。由于策略改进和值函数的改进是一致的，因此可将策略改进视为值函数的改善。这种改善值函数的算法就称为值迭代（value iteration）算法。

Page382: 免模型学习(model-free learning)

在现实的强化学习任务中，环境的转移概率、奖赏函数往往很难得知，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境建模，则称为「免模型学习」（model-free learning）。

Page386: TD(Temporal Difference) 学习(393)

由于蒙特卡洛强化学习算法没有充分利用强化学习任务的 MDP 结构，因此效率要低很多。时序差分（Temporal Difference，简称 TD）学习则结合了动态规划与蒙特卡洛方法的思想，能做到更高效的免模型学习。

Page386: 时序差分学习(393)

同 TD 学习。

Page387: Sarsa 算法(390)

该算法每次更新值函数需前一步的状态（state）、前一步的动作（action）、奖赏值（reward）、当前状态（state）、将要执行的动作（action），因此得名 Sarsa 算法。Sarsa 让系统按照策略指引进行探索，在探索每一步都进行状态价值的更新，更新公式如下： $Q^\pi_{t+1} (x,a) = Q^\pi_t (x,a) + \alpha \lgroup R^\alpha_{x \to x'} + \gamma Q^\pi_t(x',a') - Q^\pi_t(x,a) \rgroup$ ，其中， $x'$ 是前一次在状态 $x$ 执行动作 $a$ 后转移到的状态， $a'$ 是策略 $\pi$ 在 $x'$ 上选择的动作。 Sarsa 是一个同策略（on-policy）算法，算法中的评估（上式）和执行（ $a' = \pi^\epsilon(x')$ ）的均为 $\epsilon$ -贪心策略。

Page387: Q-学习(393)(Q-learning)

将 Sarsa 修改为异策略（off-policy）算法，即动作值函数更新（评估）不同于选取动作（执行）时遵循的策略，就得到 Q-学习算法，Q-学习的动作值函数更新公式如下： $Q^\pi_{t+1} (x,a) = Q^\pi_t (x,a) + \alpha \lgroup R^\alpha_{x \to x'} + \gamma max_{a} Q^\pi_t(x',a) - Q^\pi_t(x,a) \rgroup$

Page388: 表格值函数(tabular value function)

如果我们假定强化学习任务是在有限状态空间上进行，每个状态可以用一个编号来指代；值函数就是关于有限状态的「表格值函数」（tabular value），也就是说值函数能表示为一个数组，输入 $i$ 对应的函数值就是数组元素 $i$ 的值，且更改一个状态上的值不影响其他状态上的值。

Page388: 值函数近似(value function approximation)

实际强化学习任务所面临的状态空间往往是连续的，有无穷多个状态。我们假定状态空间为 $n$ 维实数空间 $X = \mathbb{R}^n$ ，此时显然无法用表格值函数来记录状态值。但考虑简单情形，即值函数能表达为状态的线性函数： $V_\theta(x) = \theta^Tx$ ，其中 $x$ 为状态向量， $\theta$ 为参数向量。由于此时的值函数难以像有限状态那样精确记录每个状态的值，因此这样的值函数求解被称为值函数近似（value function approximation）。

Page390: 模仿学习(imitation learning)

在强化学习的经典任务设置中，机器所能获得的反馈信息仅有多步决策后的累计奖赏，但在现实任务中，往往能得到人类专家的决策过程范例。从这样的范例中学习，称为「模仿学习」（imitation learning）。

Page391: 逆强化学习(inverse reinforcement learning)

在很多任务中，设计奖赏函数往往相当困难，从人类专家提供的范例数据中反推出奖赏函数有助于解决该问题，这就是「逆强化学习」（inverse reinforcement learning）。逆强化学习的基本思想是：欲使机器做出与范例一致的行为，等价于在某个奖赏函数的环境中求解最优策略，该最优策略所产生的轨迹与范例数据一致。换言之，我们要寻找某种奖赏函数使得范例数据是最优的，然后即可使用这个奖赏函数来训练强化学习策略。

Page393: 近似动态规划(approximate dynamic programming)

强化学习在运筹学与控制论领域的研究被称为「近似动态规划」（approximate dynamic programming）。

第16章 强化学习(reinforcement learning)

第16章 强化学习(reinforcement learning)

第16章强化学习(reinforcement learning)

第16章强化学习(reinforcement learning)