西瓜书概念

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