无模型的强化学习方法
前面所介绍的策略迭代、值迭代的方法属于基于模型的方法，它需要通过学习 $\mathcal P$ 和 $\mathcal R$，来得到MDP问题的解。
无模型的强化学习方法在没有 $\mathcal P$ 和 $\mathcal R$ 的情况下学习策略，有蒙特卡洛方法和时序差分方法。本节主要介绍其中的蒙特卡洛方法，它分为两步：
- 无模型预测：利用蒙特卡洛方法对未知MDP的值函数进行估计；
- 无模型控制：利用蒙特卡洛方法对未知MDP的值函数进行优化。
蒙特卡洛强化学习（Monte-Carlo RL）
蒙特卡洛方法定义在Episode Task（在有限时间内可到达终止状态并获得回报的任务）上，通过对经验（训练样本）的学习，来估计在状态 $s$ 下遵循策略 $\pi$ 的期望回报。
蒙特卡洛预测
回顾回报 $G_t$ 与值函数 $v_\pi(s)$ 的定义如下：
$G_t=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_{T},$
$v_\pi(s)=\mathbb E_\pi(G_t\mid S_t=s).$
蒙特卡洛策略评估利用多个回合回报的样本均值来代替计算状态的价值函数，即
$v_\pi(s)=\mathbb E_\pi(G_t\mid S_t=s)\approx\dfrac{\sum_{i:S_t^i=s}^NG_t^i}{N}.$
根据大数定律，当 $N\rightarrow\infty$ 时，我们可以得到确切的函数期望值。
由于在同一个回合中，同一个状态可能会被访问多次，因此具体来说会有两种方案：
- 首次访问蒙特卡洛策略评估：仅当该状态第一次出现在回合中时列入计算；
- 每次访问蒙特卡洛策略评估：该状态每次出现在回合中时都列入计算。
不过这两种方案计算得到的价值函数的估计最终都会收敛到真值。
从计算机实现的角度来讲，由于
$\displaystyle\mu_k=\frac{1}{k}(x_k+(k-1)\mu_{k-1})=\mu_{k-1}+\frac{1}{k}(x_k-\mu_{k-1}).$
所以计算均值应当采用如下增量的计算方式：
$\begin{array}{rl}
N(S_t)\leftarrow&\!\!\!\! N(S_t)+1\\
v(S_t)\leftarrow&\!\!\!\! v(S_t)+\dfrac{1}{N(S_t)}(G_t-v(S_t))
\end{array}$
因此，不需要存储所有的回报，只需要上一个回合的均值，就可以实时更新回报均值。
有了这种思想之后，我们可以考虑更加一般的更新，即
$v(S_t)\leftarrow v(S_t)+\alpha(G_t-v(S_t)),$
其中 $\alpha\in(0,1)$ 是一个参数，在非平稳的问题（不稳定环境）中比较适用。
蒙特卡洛控制
根据最优策略与状态值函数和行动值函数的关系可知，利用状态值函数改进策略需要知道MDP模型，而利用行动值函数则不需要，因此在蒙特卡洛策略迭代时采用行动值函数 $q(s,a)$，即
$q(S_t,A_t)\leftarrow q(S_t,A_t)+\alpha(G_t^a-q(S_t,A_t)).$
这种迭代的收敛需要如下的假设：
- 策略估计过程中有无限个回合，以收敛到回报的期望；
- 能够保证状态集合 $\cal S$ 中所有状态都可能被选中为每个回合的初始状态。
但这两个假设在实际中并不容易实现，为去掉两个假设，在实际中有两种方法：
- On-policy Method：智能体的行为策略与目标策略是同一个策略，并且这个策略是一种软（soft）策略，即 $\pi(a\mid s)>0,~\forall s\in\mathcal S,a\in\mathcal A$。
- Off-policy Method：智能体的行为策略与目标策略不是同一个策略，其中行为策略 $\mu$ 是一个具有探索性的策略，它专门用于产生回合积累经验；目标策略 $\pi$ 是用来学习成为最优策略的。这里的 $\pi$ 和 $\mu$ 要求对所有满足 $\pi(a\mid s)>0$ 的 $(s,a)$ 均有 $\mu(a\mid s)>0$。
On-Policy
采用 $\varepsilon$-贪婪策略搜索方法，它通过控制 $\varepsilon$ 将初始的软策略通过不断优化得到最优策略：
- 以 $1-\varepsilon$ 的概率选择当前认为最好的行为；
- 以 $\varepsilon$ 的概率在所有可能的 $m$ 个行为中选择。
用公式表达为
$\pi(a\mid s)=\left\{\begin{array}{l}
\dfrac{\varepsilon}{m}+1-\varepsilon, & \text{if}~a^\star=\underset{a\in\cal A}{\arg\max}~Q(s,a),\\
\dfrac{\varepsilon}{m}, & \text{otherwise}.
\end{array}\right.$
定理. 对任一 $\varepsilon$-贪婪策略，基于 $q_\pi$ 的 $\varepsilon$-贪婪策略 $\pi’$ 是一个改进，即 $v_{\pi’}(s)\geq v_\pi(s)$。
证明. 注意到
$\begin{array}{rl}
q_\pi(s,\pi'(s)) =&\!\!\!\! \displaystyle\sum_{a\in\cal A}\pi'(a\mid s)q_\pi(s,a)\\
=&\!\!\!\! \displaystyle\frac{\varepsilon}{m}\sum_{a\in\cal A}q_\pi(s,a)+(1-\varepsilon)\max_{a\in\cal A}q_\pi(s,a)\\
\geq&\!\!\!\! \displaystyle\frac{\varepsilon}{m}\sum_{a\in\cal A}q_\pi(s,a)+(1-\varepsilon)\sum_{a\in\cal A}\frac{\pi(a\mid s)-\varepsilon/m}{1-\varepsilon}q_\pi(s,a)\\
=&\!\!\!\! \displaystyle\sum_{a\in\cal A}\pi(a\mid s)q_\pi(s,a)=v_\pi(s),
\end{array}$
因此，我们有 $v_{\pi’}(s)\geq v_\pi(s)$。
另一种软策略改进的方法是UCB（Upper Confidence Bound），用公式表达为
$a_t=\underset{a\in\cal A}{\arg\max}\left(q_t(a)+c\sqrt{\dfrac{\ln t}{N_t(a)}}\right),$
这里 $N_t(a)$ 在时间 $t$ 之前行动 $a$ 被选择的次数，而 $c$ 为控制探索程度的参数。
Off-Policy
采用重要性采样（Importance Sampling）来对行为策略进行采样。重要性采样的原理如下：对于 $X\sim p(x)$ 的随机变量，基于
$\displaystyle\mathbb E[f(X)]=\int_{\mathscr{X}}p(x)f(x){\rm d}x=\int_{\mathscr{X}}q(x)\frac{p(x)}{q(x)}f(x){\rm d}x,$
定义重要性权重 $\omega_n=\dfrac{p(x^n)}{q(x^n)}$，则普通的重要性采样结果为
$\displaystyle\mathbb E[f(X)]\approx\frac{1}{N}\sum_n\omega_nf(x^n).$
注意，一般情形下，$q(\cdot)$ 是容易采样的概率分布。
在Off-Policy预测问题中，给定初始状态 $S_t$，轨迹 $A_t,S_{t+1},A_{t+1},\dots,S_T$ 在策略 $\pi$ 下发生的概率为
$\prod_{k=t}^{T-1}\pi(A_k\mid S_k)\mathcal P_{S_k,S_{k+1}}^{A_k}.$
因此，轨迹在目标策略和行为策略下发生的相关概率（即重要性权重）为
$\displaystyle\rho_{t:T-1}=\dfrac{\prod_{k=t}^{T-1}\pi(A_k\mid S_k)\mathcal P_{S_k,S_{k+1}}^{A_k}}{\prod_{k=t}^{T-1}\mu(A_k\mid S_k)\mathcal P_{S_k,S_{k+1}}^{A_k}}=\prod_{k=t}^{T-1}\dfrac{\pi(A_k\mid S_k)}{\mu(A_k\mid S_k)}.$
由此可以看到，$\rho_{t:T-1}$ 与MDP没有关系，仅仅与两个策略有关。
一般地，假设我们得到了一系列回报 $G_1,G_2,\dots,G_{t-1}$，设每个回报的权重为 $W_k$，则
$v_t=\dfrac{\sum_{k=1}^{t-1}W_kG_k}{\sum_{k=1}^{t-1}W_k},$
它的增量表示为
$\begin{array}{rl}
v_{t+1}=\dfrac{\sum_{k=1}^{t}W_kG_k}{\sum_{k=1}^{t}W_k}=&\!\!\!\!\dfrac{\sum_{k=1}^{t-1}W_kG_k+W_tG_t}{\sum_{k=1}^{t-1}W_k}\cdot\dfrac{\sum_{k=1}^{t-1}W_k}{\sum_{k=1}^{t}W_k}\\
=&\!\!\!\! v_t\dfrac{C_{t-1}}{C_t}+W_t\dfrac{G_t}{C_t}=v_t+\dfrac{W_tG_t-v_tW_t}{C_t}\\
=&\!\!\!\! v_t+\dfrac{W_t}{C_t}(G_t-v_t).
\end{array}$
因此对该问题的迭代公式如下：
$v_{t+1}=v_t+\dfrac{W_t}{C_t}(G_t-v_t),$
$C_{t+1}=C_t+W_{t+1}.$
下面两张图给出了基于行动值函数的预测和控制流程图。
后记
本文内容来自中国科学技术大学《强化学习》（2022Fall）课件。
如对本文内容有任何疑问，请联系 watthu@mail.ustc.edu.cn。
