# 强化学习

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch16.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.