-
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）。