Policy iteration和value iteration都是假设可以直接接触环境的动态过程和奖励的。然而在很多实际问题中,MDP模型可能是未知的或者过大而无法利用。
Model-free RL: learning by iteration
强化学习中”episode(事件)”指的是agent在环境里面根据某个策略从开始到结束这一过程,”trajectory”是一段状态动作序列。
Model-free prediction: policy evaluation without the access to the model
在无法接触MDP模型时,估计某个策略下的期望return
假设经验被划分为episodes,并且无论选择什么动作,所有episodes最终都会结束。只有在一个episodes完成时,价值估计和策略才会改变。因此,Monte-Carlo方法可以在"episode-by-episode"意义上是增量的,而不是在step-by-step(在线)意义上。这里的"Monte-Carlo"特指基于averaging complete return的方法。
Monte-Carlo预测法可以在episode-by-episode的基础上进行增量实现。
评估状态\(v(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:
动态规划(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的区别:
MC相较于DP的优势:
TD方法介于MC和DP之间,既使用了采样的方法,又采用了bootstrapping的方法。
考虑以下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))\)
Bootstrapping:更新时涉及估计
DP自助,MC不自助,TD自助
Sampling:更新时对期望采样
DP不采样,MC采样,TD采样
一般涉及到采样时,将策略迭代称为控制。
策略迭代,迭代以下两个步骤:
已知MDP的策略迭代过程:
问题:如果\(R(s,a)\)和\(P(s' \vert s,a)\)都不可知或不可得怎么办呢?
—利用动作价值函数的广义策略迭代(Generalized Policy Iteration, GPI)
MC控制:
首次访问型 MC预测,\(v \approx v_{\pi}\)
所有的动作的概率都是非零的,有\(1 - \epsilon\)的概率选择贪心动作,有\(\epsilon\)的概率随机选择一个动作。
Policy improvement theorem:对于任意的ϵ-贪心策略\(\pi\),关于\(q_{\pi}\)的ϵ-贪心策略\(\pi\)都是一次改进,\(v_{\pi '}(s) \ge v_{\pi}(s)\)。(证明见书p101式(5.2))
时序差分学习相较于蒙特卡洛有以下优势:
所以可以在控制回路中用TD代替MC
首先,回顾一下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)\)呢?
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
一次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(\(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))\)
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\)
离轨学习的好处:
Off-policy control with Q-learning:
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]\]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中,\(A\)和\(A'\)都是从同一个策略中采样得到的,所以它是on-policy的;在Q-learning中,\(A\)和\(A'\)是从不同的策略中得到的,\(A\)更具探索性而\(A'\)是直接通过取最大值的操作得到的。
例:Cliff Walk(书 Example 6.6)
Sarsa和Q-learning的例子
无模型预测
MDP的无模型控制
估计一个函数的期望为\(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}\]为什么不对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是在转换分布上,而不是在策略分布上,因此不需要修正不同的策略分布。