> For the complete documentation index, see [llms.txt](https://blog.cweihang.io/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch16.md).

# 强化学习

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