Model-free prediction & control

请先阅读书本的Chapter 5和Chapter 6


  • Model-free prediction: Estimate value function of an unknown MDP
  • Model-free control: Optimize value function of an unknown MDP

  Policy iteration和value iteration都是假设可以直接接触环境的动态过程和奖励的。然而在很多实际问题中,MDP模型可能是未知的或者过大而无法利用。

Model-free RL: learning by iteration

  • 无模型的RL可以在与环境交互的过程中解决问题
  • 不再能够直接访问已知的转移动态过程和奖励函数
  • trajectory/episodes是在agent与环境交互的过程中收集的
  • 每个trajectory/episode包含\(\{S_1, A_1, R_1, S_2, A_2, R_2, \ldots, S_T, A_T, R_T\}\)
补充

强化学习中”episode(事件)”指的是agent在环境里面根据某个策略从开始到结束这一过程,”trajectory”是一段状态动作序列。

Model-free prediction: policy evaluation without the access to the model

在无法接触MDP模型时,估计某个策略下的期望return

  • Monte Carlo policy iteration
  • Temporal Difference (TD) learning

3.1 Monte-Carlo Methods

  • Return:\(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\) 在策略\(\pi\)下
  • \(v^{\pi}(s) = \mathbb{E}_{\tau \sim \pi} [G_t \vert S_t = s]\),按策略\(\pi\)生成的trajectory\(\tau\)的期望
  • MC simulation:对很多trajectory进行简单采样,计算所有轨迹的实际return,然后取平均
  • MC policy iteration使用经验平均return替代期望return
  • MC不需要MDP的动态过程/奖励,没有bootstrapping(在之前估计的基础上估计),也无需假设状态是马尔可夫的
  • 只能应用于由一系列独立事件组成的MDPs(每个episode都会终止)

  假设经验被划分为episodes,并且无论选择什么动作,所有episodes最终都会结束。只有在一个episodes完成时,价值估计和策略才会改变。因此,Monte-Carlo方法可以在"episode-by-episode"意义上是增量的,而不是在step-by-step(在线)意义上。这里的"Monte-Carlo"特指基于averaging complete return的方法。

3.1.1 MC policy iteration

  Monte-Carlo预测法可以在episode-by-episode的基础上进行增量实现。

评估状态\(v(s)\):

  1. 在一个随机事件中访问状态\(s\)的每个时间步长\(t\)
  2. 增量计数 \(N(s) \leftarrow N(s) + 1\)
  3. 增量总return \(S(s) \leftarrow S(s) + G_t\)
  4. 值的评估根据平均return \(v(s) = S(s) / N(s)\)

根据大数定律,当\(N(s) \rightarrow \infty\)时,\(v(s) \rightarrow v^{\pi}(s)\)。

Incremental mean:来自样本\(x_1, x_2, \ldots\)的平均值

\[\begin{aligned} \mu_t & = \frac{1}{t} \sum_{j = 1}^t x_j \\ & = \frac{1}{t} \left(x_t + \sum_{j = 1}^{t-1} x_j\right) \\ & = \frac{1}{t} (x_t + (t - 1) \mu_{t - 1}) \\ & = \mu_{t - 1} + \frac{1}{t} (x_t - \mu_{t - 1}) \end{aligned}\]

Incremental MC Updates

  1. 收集一次episode \((S_1, A_1, R_1, \ldots, S_t)\)
  2. 对于每个有\(G_t\)(计算所得的return)的状态\(S_t\)
     \(N(S_t) \leftarrow N(S_t) + 1\)
     \(v(S_t) \leftarrow v(S_t) + \frac{1}{N(S_t)} (G_t - v(S_t))\)
  3. 或者使用一个更新的均值(旧事件的影响会逐渐减小),适合解决非静态问题(\(\alpha\)可以理解为学习率
     \(v(S_t) \leftarrow v(S_t) + \alpha (G_t - v(S_t))\)

3.1.2 DP vs. MC 策略评估

  动态规划(DP)通过价值估计\(v_{i-1}\)引导其余的期望回报的方法计算\(v_i\)。根据Bellman expectation backup迭代:

\[v_i(s) = \sum_{a \in A} \pi(a \vert s) \bigg[R(s,a) + \gamma \sum_{s' \in S} P(s' \vert s,a) v_{i-1}(s')\bigg]\]

  MC用一次采样episode来更新经验平均return

\[v(S_t) \leftarrow v(S_t) + \alpha (G_{i,t} - v(S_t))\]

MC与DP的区别

  1. MC根据样本经验进行操作,因此可以在没有模型的情况下直接学习。
  2. MC不会在其他价值估计的基础上更新其价值估计。
    (这两个不同点并没有紧密联系,可以分开。)

MC相较于DP的优势

  1. MC可以用于环境未知的情况。
  2. 即使是环境动态特性完全已知的情况下,使用采样episode仍有很大的优势,e.g. 转移概率难以计算的情况。
  3. 估计某个单一的状态的值与全部状态无关。所以可从感兴趣的状态开始采样,然后再取return的平均。

3.2 Temporal-Difference Learning

  • TD法是直接从episodes的经验学习
  • TD是无模型的:MDP的转移特性/奖励
  • TD从不完整的episodes中学习,通过bootstrapping的方式。

3.2.1 one-step TD

  • 目标:根据策略\(\pi\)下的经验在轨学习\(v(\pi)\)
  • 最简的TD算法:TD(0)
      向估计return \(R_{t+1} + \gamma v(S_{t+1})\)方向更新\(v(S_t)\)
        \(v(S_t) \leftarrow v(S_t) + \alpha(R_{t+1} + \gamma v(S_{t+1}) - v(S_t))\)
  • TD target:\(\color{green}{R_{t+1} + \gamma v(S_{t+1})}\)
  • TD error:\(\color{green}{\delta = R_{t+1} + \gamma v(S_{t+1}) - v(S_t)}\)
  • 与incremental Monte-Carlo相比
      给定episode \(i\),用实际return \(G_t\)更新\(v(S_t)\)
        \(v(S_t) \leftarrow v(S_t) + \alpha(G_{i,t} - v(S_t))\)

3.2.2 TD vs. MC

  1. TD可以在每步后在轨学习
    MC必须等到episode结束才能知道return
  2. TD可以从不完全序列中学习
    MC只能从完全序列中学习
  3. TD能用在连续的(non-terminating)环境中
    MC只能用在episodic(terminating)环境中
  4. TD利用马尔可夫性,在马尔可夫环境中更有效
    MC没有利用马尔可夫性,在非马尔可夫环境中更有效
补充

TD方法介于MC和DP之间,既使用了采样的方法,又采用了bootstrapping的方法。

3.2.3 n-step TD

  • n-step TD法是one-step TD和MC的一般情况
  • 可以根据需要平滑地从一个方法转移到另一个,以满足特定任务的需求。

  考虑以下n(\(n = 1, 2, \infty\))步的return

\[\begin{aligned} n = 1 (TD) \quad & G_t^{(1)} = R_{t+1} + \gamma v(S_{t+1}) \\ n = 2 \quad \quad \quad \ & G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 v(S_{t+2}) \\ & \vdots \\ n = \infty (MC) \quad & G_t^{\infty} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1} R_T \\ \end{aligned}\]

因此,n-step return被定义为

\[G_t = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n v(S_{t+n})\]

n-step TD:\(v(S_t) \leftarrow v(S_t) + \alpha (G_t^n - v(S_t))\)

Summary for Model-free Prediction

补充

Bootstrapping:更新时涉及估计
DP自助,MC不自助,TD自助
Sampling:更新时对期望采样
DP不采样,MC采样,TD采样

1. Dynamic Programming Backup

\[v(S_t) \leftarrow \mathbb{E}_{\pi} [R_{t+1} + \gamma v(S_{t+1})]\]

2. Monte-Carlo Backup

\[v(S_t) \leftarrow v(S_t) + \alpha (G_t - v(S_t))\]

3. Temporal-Difference Backup

\[\text{TD(0): } v(S_t) \leftarrow v(S_t) + \alpha(R_{t+1} + \gamma v(S_{t+1}) - v(S_t))\]

4. Reinforcement Learning

3.3 Monte-Carlo Control

提示

一般涉及到采样时,将策略迭代称为控制。

策略迭代,迭代以下两个步骤:

  1. 策略评估(给定当前的\(\pi\),计算\(v\))
  2. 策略改进(通过对\(v^{\pi}\)采取贪心行为 \(\pi' = \text{greedy}(v^{\pi})\))

已知MDP的策略迭代过程:

  1. 计算策略\(\pi\)下的状态-动作价值:\(q_{\pi_i}(s,a) = R(s,a) + \gamma \sum_{s' \in S} P(s' \vert s,a) v_{\pi_i}(s')\)
  2. 对于所有的\(s \in S\)计算新策略\(\pi_{i+1}\):\(\pi_{i+1}(s) = \text{arg} \max_a q_{\pi_i}(s,a)\) (根据策略改进定理可知,\(\pi_{i+1}\)优于\(\pi_i\))

问题:如果\(R(s,a)\)和\(P(s' \vert s,a)\)都不可知或不可得怎么办呢?
—利用动作价值函数的广义策略迭代(Generalized Policy Iteration, GPI

MC控制

  1. 策略评估:Monte Carlo策略评估 \(Q = q_{\pi}\)
    (采样的两个假设:Ⅰ无限幕 Ⅱ试探性出发假设 )
  2. 策略改进:贪心策略改进? \(\pi(s) = \text{arg}\max_a q(s,a)\)

3.3.1 Monte Carlo ES

首次访问型 MC预测,\(v \approx v_{\pi}\)

  • 保证策略迭代收敛的假设:episode有exploring starts
  • Exploring starts可以确保无限频繁地选择所有动作

3.3.2 MC with ϵ-greedy exploration

  • exploration与exploitation的权衡(这部分内容将在后面的课程中详细讨论)
  • ϵ-贪心探索:确保持续探索
\[\pi'(s \vert a) = \begin{cases} \epsilon / |A| + 1 - \epsilon \quad & \text{if } a^* = \text{arg}\max_{a \in A} Q(s,a) \\ \epsilon / |A| & \text{otherwise} \end{cases}\]

所有的动作的概率都是非零的,有\(1 - \epsilon\)的概率选择贪心动作,有\(\epsilon\)的概率随机选择一个动作。

Policy improvement theorem:对于任意的ϵ-贪心策略\(\pi\),关于\(q_{\pi}\)的ϵ-贪心策略\(\pi\)都是一次改进,\(v_{\pi '}(s) \ge v_{\pi}(s)\)。(证明见书p101式(5.2))

3.4.3 MC vs. TD 预测与控制

时序差分学习相较于蒙特卡洛有以下优势:

  1. 较小的方差
  2. 在线
  3. 不完全序列

所以可以在控制回路中用TD代替MC

  • 将TD用于\(Q(S,A)\)
  • 用ϵ-贪心策略改进
  • 在每个时间步长更新,而不是等到一次episode结束

3.4 TD Control

首先,回顾一下TD预测:

  一次episode由交替的状态序列和状态-动作对组成

估计价值函数的TD(0)法:
  \(A_t \leftarrow\)由\(\pi\)给出的\(S\)的动作
  采取动作\(A_t\),观察\(R_{t+1}\)和\(S_{t+1}\)
  \(v(S_t) \leftarrow v(S_t) + \alpha(R_{t+1} + \gamma v(S_{t+1}) - v(S_t))\)

那么,如何估计动作价值函数\(Q(S, A)\)呢?

3.4.1 On-policy vs. Off-policy

On-policy learning:从\(\pi\)中收集的经验来学习策略\(\pi\)
  按非最优的方式行动,以此探索所有动作,然后减少探索,e.g. ϵ-贪心。

另一种重要方法是off-policy learning,使用两个不同的策略
  一个是正在被学习并成为最优策略的策略
  另一个更具探索性,用于生成轨迹

Off-policy learning:从另一个策略\(\mu\)中采样的经验来学习策略\(\pi\)
  \(\color{green}{\pi}\):target policy
  \(\color{green}{\mu}\):behavior policy

3.4.2 Sarsa: On-policy

  一次episode是由交替的状态序列和状态-动作对组成的。

  One-setp Sarsa: 一步ϵ-贪心策略,然后bootstrap状态价值函数:

\[Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \big]\]

每次从非终止状态\(S_t\)转换后完成更新。

  TD target \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\)

n-step Sarsa

  考虑以下n(\(n = 1, 2, \infty\))步的Q-returns

\[\begin{aligned} n = 1 (Sarsa) \quad & q_t^{(1)} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) \\ n = 2 \quad \quad \quad \ & q_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 Q(S_{t+2}, A_{t+2}) \\ & \vdots \\ n = \infty (MC) \quad & q_t^{\infty} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1} R_T \\ \end{aligned}\]

因此,n-step Q-return被定义为

\[q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})\]

n-step Sarsa用n-step Q-return更新\(Q(s,a)\):\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (q_t^{(n)} - Q(S_t, A_t))\)

Expected Sarsa

\[Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma \mathbb{E}_{\pi}[Q(S_{t+1}, a \vert S_{t+1})] - Q(S_t, A_t))\]
  1. 默认情况下\(\pi = \mu\),同轨。
  2. 若\(\pi\)是贪心策略,即\(\pi = \text{arg} \max_a Q(S_{t+1}, a) = a^*\),此时期望Sarsa为离轨策略,会退化成Q-learning。

3.4.3 Q-learning: Off-policy

Off-policy control遵循以下行为策略\(\mu(a \vert s)\)来收集数据
  \(S_1, A_1, R_2, \ldots, S_T \sim \mu\)
  用\(S_1, A_1, R_2, \ldots, S_T\)更新\(\pi\)

离轨学习的好处:

  1. 在遵循探索性策略的同时学习最优策略
  2. 通过观察人或其它agents来学习
  3. 重用由旧策略\(\pi_1, \pi_2, \ldots, \pi_{t-1}\)生成的经验

Off-policy control with Q-learning:

  • 行为价值\(Q(s, a)\)的离轨学习
  • 无需重要性采样
  • TD目标中的下一个动作是从备选动作\(A' \sim \pi(. \vert S_t)\)中选择的
  • 将\(Q(S_t, A_t)\)更新为备选动作的值
    \(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S_t, A_t))\)

  Q-learning中行为策略和目标策略都是允许改进的。目标策略\(\color{blue}{\pi}\)\(\color{blue}{Q(s, a)}\)贪心

\[\pi(S_{t+1}) = \text{arg}\max_{a'} Q(S_{t+1}, a')\]

其中,行为策略\(\color{blue}{\mu}\)可以是完全随机的,但是我们让它随着\(\color{blue}{Q(s, a)}\)的ϵ-贪心而改进

  因此,Q-learning的目标为

\[\begin{aligned} R_{t+1} + \gamma Q(S_{t+1}, A') & = R_{t+1} + \gamma Q(S_{t+1}, \text{arg}\max_{a'} Q(S_{t+1}, a')) \\ & = R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') \end{aligned}\]

Q-learning的更新过程为

\[Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) \big]\]

3.4.4 Sarsa vs. Q-learning

Sarsa: on-policy TD control
  按ϵ-贪心,用从\(Q\)派生的策略从\(S_t\)选择动作\(A_t\)
  采取行为\(A_t\),观察\(R_{t+1}\)和\(S_{t+1}\)
  按ϵ-贪心,用从\(Q\)派生的策略从\(S_{t+1}\)选择动作\(A_{t+1}\)
  \(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \big]\)

Q-learning: off-policy TD control
  按ϵ-贪心,用从\(Q\)派生的策略从\(S_t\)选择动作\(A_t\)
  采取行为\(A_t\),观察\(R_{t+1}\)和\(S_{t+1}\)
  然后将\(A_{t+1}\)"想象"为更新目标中的\(\text{arg}\max_{a'} Q(S_{t+1}, a')\)
  \(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t)\big]\)

Sarsa和Q-learning的回溯图

  在Sarsa中,\(A\)和\(A'\)都是从同一个策略中采样得到的,所以它是on-policy的;在Q-learning中,\(A\)和\(A'\)是从不同的策略中得到的,\(A\)更具探索性而\(A'\)是直接通过取最大值的操作得到的。

例:Cliff Walk(书 Example 6.6)
  Sarsa和Q-learning的例子

3.4.5 DP vs. TD

Summary

无模型预测

  • 在不知道MDP模型的情况下,只通过与环境交互来评估状态价值

MDP的无模型控制

  • 无模型控制:优化一个未知MDP的价值函数
  • 利用MC和TD的广义策略迭代

Supplement:Importance Sampling

  估计一个函数的期望为\(E_{x \sim P}[f(x)] = \int{f(x) P(x) dx} \approx \frac{1}{n} \sum_i f(x_i)\),但是有时很难从\(P(x)\)中采样\(x\),可以从另一个分布\(Q(x)\)中对\(x\)采样,然后修改权重

\[\begin{aligned} \mathbb{E}_{x \sim P}[f(x)] & = \int{P(x) f(x) dx} \\ & = \int{Q(x) \frac{P(x)}{Q(x)} f(x) dx} \\ & = \mathbb{E}_{x \sim Q} \bigg[\frac{P(x)}{Q(x)} f(x)\bigg] \approx \frac{1}{n} \sum_i \frac{P(x_i)}{Q(x_i)} f(x_i) \end{aligned}\]

  离轨RL的重要性采样:用从另一个策略(行为策略)采样的轨迹来估计回报的期望

\[\begin{aligned} \mathbb{E}_{T \sim \pi}[g(T)] & = \int{P(T) g(T) dT} \\ & = \int{Q(T) \frac{P(T)}{Q(T)} g(T) dT} \\ & = \mathbb{E}_{T \sim \mu} \bigg[\frac{P(T)}{Q(T)} g(T)\bigg] \approx \frac{1}{n} \sum_i \frac{P(T_i)}{Q(T_i)} g(T_i) \end{aligned}\]

离轨MC的重要性采样

  1. 根据行为策略\(\mu\)生成episode,并计算生成的return \(G(t)\),即\(S_1, A_1, R_2, \ldots, S_T \ \sim \ \mu\)。
  2. 根据策略之间的相似性返回权重\(G_t\),在整个情节中乘以重要性采样校正
    \(G_t^{\pi / \mu} = \frac{\pi (A_t \vert S_t)}{\mu (A_t \vert S_t)} \frac{\pi (A_{t+1} \vert S_{t+1})}{\mu (A_{t+1} \vert S_{t+1})} \cdots \frac{\pi (A_T \vert S_T)}{\mu (A_T \vert S_T)} G_t\)
  3. 用矫正后的return更新价值函数 \(V(S_t) \leftarrow V(S_t) + \alpha (G_t^{\pi / \mu} - V(S_t))\)

离线TD的重要性采样

  1. 根据行为策略\(\mu\)生成的TD目标来评估\(\pi\)
  2. 根据重要性采样来加权TD目标\(R + \lambda V(S')\)
  3. 只需要一次重要性采样校正
    \(V(S_t) \leftarrow V(S_t) + \alpha \left(\frac{\pi (A_t \vert S_t)}{\mu (A_t \vert S_t)} (R_{t+1} + \lambda V(S_{t+1})) - V(S_t)\right)\)
  4. 策略只要在一个步骤中是相似的即可
补充

为什么不对Q-learning使用重要性采样?
— 简单来说是因为Q-learning不对策略分布进行期望值估计。

  价值迭代中的贝尔曼最优性回溯为\(Q(s, a)= R(s, a) + \gamma \sum_{s' \in S} {P(s' \vert s,a) \max_{a'} {Q(s', a')}}\)。Q-learning可以被认为是价值迭代的基于采样的版本,使用从环境中收集的样本而不是使用过渡动态的期望值

\[Q(s, a) = r + \gamma \max_{a'} {Q(s', a')}\]

Q-learning是在转换分布上,而不是在策略分布上,因此不需要修正不同的策略分布。