异策略蒙特卡罗强化学习
几个概念：
目标策略（$Target\ Policy$）：待学习的策略，是指每次策略改进的 $\pi$
行为策略（$Behavior\ Policy$）：用于产生经验数据的策略，是指产生 $MDP$ 序列中应用的策略 $\pi$
同策略强化学习（$On-policy$）：目标策略和行为策略
相同异策略强化学习（$Off-policy$）：目标策略和行为策略
不同目标策略和行为策略区别在于生成样本的策略和参数更新时的策略是否相同
重要性采样
根据重要性，用不同的策略（分布）进行采样
$$
\begin{aligned}
\int_{a}^{b} f(x) d x &=E_{x \sim \pi(\cdot)}[f(x)] \\
&=\int_{a}^{b} \pi(x) \cdot f(x) dx \\
&=\int_{a}^{b} p(x) \cdot \frac{\pi(x)}{p(x)} f(x) dx \\
&=E_{x \sim p(\cdot)}\left[\frac{\pi(x)}{p(x)} f(x)\right] \\
& \approx \frac{b-a}{n} \sum_{i=1}^n \frac{\pi(x_i)}{p\left(x_{i}\right)} f\left(x_{i}\right)
\end{aligned}
$$
异策略蒙特卡罗策略评估
(1). 重要性权重对于目标策略 $\pi$，状态转移概率为 $P$，产生一条 $MDP$ 序列的概率为：
$$
\begin{split}
&P_{r}^{\pi}\left(s_{t}, a_{t}, \ldots, s_{T-1}, a_{T-1}, s_{T}\right) \\
~\\
&=\pi\left(a_{+} \mid s_{t}\right) P\left(s_{t+1} \mid s_{t}, a_{t}\right) \pi\left(a_{t+1} \mid s_{T+1}\right)\cdots \pi\left(a_{T-1} \mid s_{T-1}\right) P\left(s_{T} \mid s_{T-1}, a_{T-1}\right) \\
~\\
&=\prod_{k=t}^{T-1} {\pi\left(a_{k} \mid s_{k}\right) P\left(s_{k+1} \mid s_{k}, a_{k}\right)} \\
\end{split} \tag{10-1}
$$
而根据重要性采样，应用行为策略 $b$，那么产生一条 $MDP$ 序列的概率为：
$$
\begin{split}
&P_{r}^{\pi}\left(s_{t}, a_{t}, \ldots, s_{T-1}, a_{T-1}, s_{T}\right) \\
~\\
&=b\left(a_{+} \mid s_{t}\right) P\left(s_{t+1} \mid s_{t}, a_{t}\right) b\left(a_{t+1} \mid s_{T+1}\right)\cdots b\left(a_{T-1} \mid s_{T-1}\right) P\left(s_{T} \mid s_{T-1}, a_{T-1}\right) \\
~\\
&=\prod_{k=t}^{T-1} {b\left(a_{k} \mid s_{k}\right) P\left(s_{k+1} \mid s_{k}, a_{k}\right)} \\
\end{split} \tag{10-2}
$$
其中，重要性权重 $\rho$ 表示为
$$
\rho=\frac{P_{r}^{\pi}(\ldots)}{P_{r}^{b}(\cdots)}=\prod_{k=t}^{T-1} \frac{\pi\left(a_{k} \mid s_{k}\right)}{b\left(a_{k} \mid s_{k}\right)} \tag{10-3}
$$
(2). 一般重要性采样$$
\bar Q(s,a)=\frac{ \sum_{i=1}^m \rho^i(s,a) G^i(s,a)}{\sum_{i=1}^m I^i(s,a) } ,\\
~\\
\rho^i(s,a)=\prod_{k=t}^{T-1} \left( \frac{\pi\left(a_{k}^i \mid s_{k}^i\right)}{b\left(a_{k}^i \mid s_{k}^i\right)}\ \Bigg|\ s_t^i=s,a_t^i=a \right) \tag{10-4}
$$
(3). 加权重要性采样$$
\bar Q(s,a)=\frac{ \sum_{i=1}^m \rho^i(s,a) G^i(s,a)}{\sum_{i=1}^m \rho^i(s,a) } ,\\
~\\
\rho^i(s,a)=\prod_{k=t}^{T-1} \left( \frac{\pi\left(a_{k}^i \mid s_{k}^i\right)}{b\left(a_{k}^i \mid s_{k}^i\right)}\ \Bigg|\ s_t^i=s,a_t^i=a \right) \tag{10-5}
$$
(4). 异策略每次访问加权重要性蒙特卡罗策略评估算法（10-6）- 输入：环境模型 $MDP(S,A,R,\gamma)$，目标策略 $\pi$，行为策略 $b$，$MDP$ 序列数 $m$
- 初始化：累积回报 $Gsum(s,a)=0$，累计权重 $\rho sum(s,a)=0$
- 过程：
- $\qquad$ 随机抽样，根据行为策略 $b$，抽样产生 $m$ 条经历完整的 $MDP$ 序列
- $\qquad$ 循环：**$i=1 \sim m$
- $\qquad \qquad$ 循环：依次遍历第 $i$ 条 $MDP$ 序列中的所有状态动作对 $(s,a)$
- $\qquad \qquad \qquad$ $(s,a)$ 每次出现在 $MDP$ 序列中时，根据公式（8-1）计算累积折扣奖励
- $\qquad \qquad \qquad$ 根据公式（10-5）计算重要性权重 $\rho (s,a)$
- $\qquad \qquad \qquad$ 累计回报：$Gsum(s,a)\leftarrow Gsum(s,a)+\rho^i(s,a)\cdot G^i(s,a)$
- $\qquad \qquad \qquad$ 累计权重：$\rho sum(s,a)\leftarrow \rho sum(s,a)+\rho^i(s,a)\cdot G^i(s,a)$
- $\qquad$ 策略评估：根据公式（10-5）评估目标策略
- 输出：样本均值 $\bar Q_\pi$ 作为动作值的近似
增量式异策略蒙特卡罗策略评估
(1). 加权重要性采样估计的增量形式$$
\begin{split}
&\bar{Q}_\pi^{k}(s, a)=\frac{\sum_{i=1}^k \rho^{i}(s, a) G^{i}(s, a)}{\sum_{i=1}^k \rho^{i}(s, a)}\\
&=\frac{\left.\sum_{i=1}^{k-1} \rho^{i}(s, a) G^{i}(s, a)+\rho^{k}(s, a) G^{k}(s, a)\right)}{\sum_{i=1}^k \rho^{i}(s, a)}\\
&=\frac{\bar{Q}_\pi^{k-1}(s, a) \sum_{i=1}^{k-1} \rho^{ i}(s, a)+\rho^{ k}(s, a) G^{k}(s, a)}{\sum_{i=1}^k \rho^{i}(s, a)}\\
&=\frac{\bar{Q}_\pi^{k-1}(s, a) \sum_{i=1}^k \rho^{ i}(s, a)+\rho^{ k}(s, a) G^{ k}(s, a)-\rho^{ k}(s, a) \bar{Q}_\pi^{ k-1}(s, a)}{\sum_{i=1}^k \rho^{i}(s, a)}\\
&=\bar{Q}_\pi^{ k-1}(s, a)+\frac{\rho^{ k}(s, a)}{\sum_{i=1}^{k-1} \rho^{i}(s, a)+\rho^{ k}(s, a)}\left(G^{ k}(s, a) + \bar{Q}_\pi^{ k-1}(s, a)\right)
\end{split} \tag{10-7}
$$
可简写为：
$$
\begin{split}
C^k&=C^{k-1}+\rho^k \\
~\\
\bar Q^k&=\bar Q^{k-1}+ \frac{\rho^k}{C^k}\left(G^k-\bar Q^{k-1} \right)
\end{split} \tag{10-8}
$$
(2). 增量式异策略每次访问加权重要性采样蒙特卡罗策略评估算法（10-9）- 输入：环境模型 $MDP(S,A,R,\gamma)$，目标策略 $\pi$，行为策略 $b$，最大迭代局数 $m$
- 初始化：动作值 $\bar Q_\pi(s,a)=0$，回报 $G(s,a)=0$，累计重要性权重 $\rho sum(s,a)=0$，重要性权重 $\rho (s,a)=0$
- 过程：
- $\qquad$ 循环：$episode=1 \sim m$
- $\qquad \qquad$ 随机抽样：根据行为策略 $b$，抽样产生一条经历完整的 $MDP$ 序列
- $\qquad \qquad$ 循环：依次遍历第 $i$ 条 $MDP$ 序列中的所有状态动作对 $(s,a)$
- $\qquad \qquad \qquad$ 根据公式（8-1）计算累积折扣奖励 $G(s,a)$
- $\qquad \qquad \qquad$ 根据公式（10-5）计算重要性权重 $\rho (s,a)$
- $\qquad \qquad \qquad$ 累计权重：$\rho sum(s,a)\leftarrow \rho sum(s,a)+\rho(s,a)$
- $\qquad \qquad \qquad$ 策略评估：根据公式（10-8）计算 $\bar Q_\pi(s,a)$
- 输出：样本均值 $\bar Q_\pi$ 作为动作值的近似
异策略蒙特卡罗强化学习
异策略蒙特卡罗强化学习算法（10-10）- 输入：环境模型 $MDP(S,A,R,\gamma)$，最大迭代局数 $m$
- 初始化：动作值 $\bar Q_\pi(s,a)=0$，回报 $G(s,a)=0$，累计重要性权重 $\rho sum(s,a)=0$，初始化目标策略 $\pi(s) \leftarrow \arg\max_{a} Q(s,a)$
- 过程：
- $\qquad$ 循环：$episode=1 \sim m$
- $\qquad \qquad$ 生成随机行为策略 $b$
- $\qquad \qquad$ 随机抽样：根据行为策略 $b$，抽样产生一条经历完整的 $MDP$ 序列
- $\qquad \qquad$ $G \leftarrow 0$
- $\qquad \qquad$ $\rho \leftarrow 1$
- $\qquad \qquad$ 循环：自后向前遍历 $MDP$ 序列：$t=T-1,t_2,\cdots,0$
- $\qquad \qquad \qquad$ 累积折扣奖励 $G\leftarrow \gamma\cdot G+R_{t+1} $
- $\qquad \qquad \qquad$ 累计权重：$\rho sum(s,a)\leftarrow \rho sum(s_t,a_t)+\rho(s,a)$
- $\qquad \qquad \qquad$ 策略评估：$\bar{Q}\left(s_{t}, a_{t}\right) \leftarrow \bar{Q}\left(s_{t}, a_{t}\right)+\left(\rho / \rho s u m\left(s_{t}, a_{t}\right)\right)\left(G-\bar{Q}\left(s_{t}, a_{t}\right)\right)$
- $\qquad \qquad \qquad$ 策略改进：$\pi\left(s_{t}\right) \leftarrow \arg \max _{a} Q\left(s_{t}, a\right)$
- $\qquad \qquad \qquad$ 如果 $a_t\neq \pi(s_t)$ 则结束循环，进入下一条序列
- $\qquad \qquad \qquad$ 权重更新：$\rho \leftarrow \rho(\pi(s_t \mid a_t)/b(s_t\mid a_t))$
- 输出：最优动作值 $\bar Q^*(s,a)$， 最优策略 $\pi^*(s)$
说明：（1）在内层循环中，遍历一条 $MDP$ 序列的方向是自后向前而非自前向后的
（2）尾部学习效应($Learning\ on\ the\ Tail$) ，造成值不稳定
（3）权重更新公式
（4）讨论的取值
参考
