强化学习

第16章 强化学习(reinforcement learning)

  • Page371: MDP

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

  • Page371: 奖赏(reward)

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

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

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

  • Page371: 强化学习(reinforcement learning)

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

  • Page371: 再励学习

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

  • Page372: 策略(policy)

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

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

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

  • Page374: ϵ-贪心

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

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

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

  • Page375: Softmax

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

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

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

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

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

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

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

  • Page380: Bellman 等式

    对于状态值函数,由于 MDP 具有马尔科夫性质,即系统下一时刻的状态仅由当前时刻的状态决定,不依赖于以往任何状态,于是值函数有很简单的递归形式。对于 TT 步累积奖赏有: VTπ(x)=aAπ(x,a)xXPxxa1TRxxa+T1TVT1π(x)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 让系统按照策略指引进行探索,在探索每一步都进行状态价值的更新,更新公式如下: Qt+1π(x,a)=Qtπ(x,a)+αRxxα+γQtπ(x,a)Qtπ(x,a)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, 其中,xx' 是前一次在状态 xx 执行动作 aa 后转移到的状态,aa' 是策略 π\pixx' 上选择的动作。 Sarsa 是一个同策略(on-policy)算法,算法中的评估(上式)和执行(a=πϵ(x)a' = \pi^\epsilon(x'))的均为 ϵ\epsilon-贪心策略。

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

    将 Sarsa 修改为异策略(off-policy)算法,即动作值函数更新(评估)不同于选取动作(执行)时遵循的策略,就得到 Q-学习算法,Q-学习的动作值函数更新公式如下: Qt+1π(x,a)=Qtπ(x,a)+αRxxα+γmaxaQtπ(x,a)Qtπ(x,a)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),也就是说值函数能表示为一个数组,输入 ii 对应的函数值就是数组元素 ii 的值,且更改一个状态上的值不影响其他状态上的值。

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

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

  • Page390: 模仿学习(imitation learning)

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

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

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

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

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