Shu Wang

Silence maks big money

(强化学习) – 基本概念

介绍

大二下学期学习强化学习(虽然我连机器学习都了解不深),假期也阅读了一些论文,有懂得和不懂的东西。网上的资源实在是太多,所以为了综合书本和网上的资料,我就打算写下我的理解。

化学习的定义是:

Reinforcement learning is learning what to do ----how to map situations to actions ---- so as to maximize a numerical reward signal.

也就是说增强学习关注的是智能体如何在环境中采取一系列行为,从而获得最大的累积回报。通过增强学习,一个智能体应该知道在什么状态下应该采取什么行为。RL是从环境状态到动作的映射的学习,我们把这个映射称为策略

强化学习是一个试错的过程。在 Flappy Bird 游戏中,我们并没有鸟运动的动力学模型,也不需要去了解他的模型。所以机器想要学习如何去玩耍,我们就需要设计一个算法。这个算法不断地去尝试,从环境中交互的得到数据,例如撞到了柱子回报是 -1,越过去是 1。通过不断地学习,鸟儿知道在什么样的状态小采取什么行动。

关键概念

RL 来自于人类学习的过程

我们认为 agent 与环境$\mathcal{E}$交互. 环境对于采取一个行动(action)采取什么反应(即转移到的状态)依赖于模型(model), 他可以已知也可未知. agent 在所处的状态(state, $s\in\mathcal{S}$)采取由转移概率$P$决定的行动$a\in\mathcal{A}$, 转移到任何一种状态, 环境返回(deliver)一个回报(reward)作为反馈.

  • 已知模型: 基于模型的方法, 例如 DP, 可以用来求最优的解决方案
  • 未知模型: 使用不完整的信息, 即 model-free 形式的 RL.

策略(policy)$\pi(s)$通过概率分布的形式告诉了在状态$s$采取什么行为是最优的, 这个最优的目标就是最大化累积的回报. 与状态$s$相关的函数$V(s)$反映了这个状态有多好, 换句话说就是在遵循一个特定的状态时, 在这个状态$s$会获得的未来的回报的预计.

Reward Signal: 定义了 agent 学习的目标. agent 每次和环境交互, 环境返回一个 数值型(numerical) reward, 高速 agent 刚刚的 action 是好是坏, 可以理解为对 agent 的奖励或者惩罚. agent 与环境交流的序列/轨迹(episode/trajectory)为:

$$\tau=s_0,a_0,r_1,s_1,a_1,r_2,\cdots,s_{n-1},a_{n-1},r_n$$

其中$s_{i-1},a_{i-1},r_i$被认为是在同一时间的一组交互的数据, 分别为 state, action 和 reward, $s_n$是终止状态.

每一个 episode 都会在一个名为终止状态(terminal state)下结束. 采用 episodes 形式的 task 被认为是 episodic tasks. 每个 episode 都会以终止状态结束, 不同点就是每个 episode 的结果是不同的. 同时新的 episode 与前面结束的 episode 都无关. 在 episodic tasks 中, 将所有非终止状态记为$\mathcal{S}$, 包含终止状态的所有状态集合记为$\mathcal{S}^+$

如果是是连续性任务(continuing tasks), 即不会自然结束持续的任务.

下一个状态由当前的状态$s_t$和$a_t$共同决定的:

$$
s_{t+1}=f\left(s_{t}, a_{t}\right)
$$

和随机策略:

$$
s_{t+1} \sim P\left(\cdot | s_{t}, a_{t}\right)
$$

它的别名有 episodes 和 rollouts.

由于马尔可夫性, 下一个状态仅仅和当前的状态和行为决定:

$$
p(s_{t+1}|s_t,a_t,\cdots,s_0,a_0)=p(s_{t+1}|s_t,a_t)
$$

因此这个轨迹出现的概率可以记为:

$$
\begin{aligned}
p(\tau)&=p\left(s_{0}, a_{0}, s_{1}, a_{1}, \dots, s_{T-1}, a_{T}, s_T, r_T\right)\\
&=p(s_0)\prod_{t=0}^{T-1}\pi(a_t|s_t)p(s_{t+1}|s_t,a_t)
\end{aligned}
$$

Model: 状态转移和回报

模型主要的两个部分: 状态转移概率函数$P$和回报函数$R$

一次状态转移可以用元组$(s,a,s',r)$表示. 函数$P$记录了采取行动$a$且返回回报为$r$转移到$s'$的概率, 使用$\mathcal{P}$表示概率:

$$P(s', r \vert s, a) = \mathbb{P} [s_{t+1} = s', r_{t+1} = r \vert s_t = s, a_t = a]$$

基于状态的转移概率在关于$\mathcal{R}$求和即可:

$$
P_{ss'}^a = P(s' \vert s, a) = \mathbb{P} [s_{t+1} = s' \vert s_t = s, a_t = a] = \sum_{r \in \mathcal{R}} P(s', r \vert s, a)
$$

回报函数$R$采取行动的回报:

$$R(s, a) = \mathbb{E} [r_{t+1} \vert s_t = s, a_t = a] = \sum_{r\in\mathcal{R}} r \sum_{s' \in \mathcal{S}} P(s', r \vert s, a)$$

状态$s$是一个关于 agent 关于当前环境的完整描述, 观察$o$是部分观察, 可能丢失了一些信息. 在 DRL 中, 观察可以是 agent 的RGB输入, 状态就是 agent 关节的角度和速度. 在一般的 RL 记法中, 行为取决与当前状态$P(a_i|s_t)$, 严格来说, 应该更适合记为$P(a_i|o_t)$. 但是, 在实际中, agent 无法获取到状态, 只能利用观察代替.

策略(Policy)

如果策略是随机的, policy 根据在状态$s$的动作概率$\pi(a|s)$选择动作; 如果策略是确定的, policy 直接根据状态$s$选择动作$a=\pi(s)$. 他们都需要满足:

  • 随机策略(stochastic policy): $\sum\pi(a|s)=1$
  • 确定性策略(deterministic policy): $\pi(s)=P[a_t=a|s_t=t]:S\rightarrow{A}$.

确定性策略和随机(stochastic)策略都可以由$\theta$或$\phi$参数化为可以计算的策略:

$$
\begin{array}{l}{a_{t}=\mu_{\theta}\left(s_{t}\right)} \\ {a_{t} \sim \pi_{\theta}\left(\cdot | s_{t}\right)}\end{array}
$$

但是, 策略不能代替 agent, 比如说策略就是最大化 reward.

  • 确定性策略: 一般用在连续行为空间中,
  • 随机策略: 常用的两种随机策略: categoricaldiagonal Gaussian. 后者多用于连续空间. 这两种随机策略在行为的选择(sample from policy)和计算对数似然中有不同的计算方式. 在代码中, 他们都是使用 logits 作为输入的. 具体计算方式可见stochastic-policies

Rewards 和 Return

reward 函数$R$用于产生参数立即回报:

$$
r_t=R(s_t,a_t,s_{t+1})
$$

或者$r_t=R(s_t,a_t)$.

不同的问题可以定义不同的 Return:

  1. 折扣回报(infinite-horizon discounted return): $R(\tau)=\sum_{t=0}^{\infty} \gamma^{t} r_{t}$适用于连续任务(即终止时间不定)
  2. finite-horizon undiscounted return: $R(\tau)=\sum_{t=0}^{T} r_{t}$用于步长确定的任务.

$0\leq\gamma\leq{1}$是折扣率(discount rate), 它嗲表未来第$k$步的 reward 的价值只是在当前获得这个 reward 的 $\gamma^{k-1}$倍. 若$\gamma{<1}$, 上面的公式就会从在本发散的和变为前提为序列$\left\{r_k\right\}$的前提下转变为一个有限的值;若$\gamma=0$, agent变得目光短浅(myopic), 仅仅选择最大化$r_{t+1}$的动作;若$\gamma\rightarrow{1}$, 这个 agent 变得很"有远见". 这么做的目的:

  • 未来的回报有很高的不确定性.
  • 未来回报对现在没有即时的好处: 今天的幸福比五年后的幸福要好
  • 求和会收敛.
  • 不用担心状态转换图中的无限循环.

在其他的文献中, return 记为$G(\tau)$, 且默认以$t=0$ 为开始时刻且最终的时刻为$T$, 其定义为:

$$
G(\tau)=\sum_{t=0}^{T-1} \gamma^{t} r_{t+1}
$$

这个和$R(\tau)$略有不同

值函数(Value Function)

值函数用于测量(measure)一个状态或者在某个状态采取一个行动的价值(Value function measures the goodness of a state or how rewarding a state or an action is by a prediction of future reward.)一共有四种类型的值函数(注意样本序列依据$\tau\sim\pi$产生): $Q^\pi$和$Q_\pi$是等价的记法.

  1. 定义$\pi$的On-Policy Value Function $v_\pi$ 表示以从$t$开始的以$s$为起始状态的 return 的期望:

$$
\begin{equation}
V^{\pi}(s)=\underset{\tau \sim \pi}{\mathrm{E}}\left[R(\tau) | s_{0}=s\right]
\label{v_func}
\end{equation}
$$

  1. 定义$\pi$的On-Policy Action-Value Function, $Q_\pi(s,a)$, 这里的$a$可能并不是根据策略$\pi$产生的, 但是接下来永远基于策略$\pi$:

$$
\begin{equation}
Q^{\pi}(s, a)=\underset{\tau \sim \pi}{\mathrm{E}}\left[R(\tau) | s_{0}=s, a_{0}=a\right]
\label{q_func}
\end{equation}
$$

  1. 最优的值函数(Optimal Value Function)以最大化 return 为目标:

$$
V^{*}(s)=\max _{\pi} \underset{\tau \sim \pi}{\mathrm{E}}\left[R(\tau) | s_{0}=s\right]
$$

  1. 最优行为-值函数(Optimal Action-Value Function): 以$s$为起始状态采取一个任意的行为$a$并永远执行最优策略:

$$
Q^{*}(s, a)=\max _{\pi} \underset{\tau \sim \pi}{\mathrm{E}}\left[R(\tau) | s_{0}=s, a_{0}=a\right]
$$
$Q_\pi$和$V_\pi$之间的差值就是 advantage function(A值):$$A_{\pi}(s, a) = Q_{\pi}(s, a) - V_{\pi}(s)$$

值函数和行为-值函数的关联:

$$
V^{\pi}(s)=\underset{a \sim \pi}{E}\left[Q^{\pi}(s, a)\right]
$$

$$
V^{*}(s)=\max _{a} Q^{*}(s, a)
$$

The Optimal Q-Function and the Optimal Action

最优的行为-值函数($Q^*(s,a)$)给出了以$s$为起点状态, 采取一个任意一个行为$a$并以后永远根据最优策略$\pi$执行的 return 的期望.

在状态$s$的最优策略就是选择一个能够最大化以$s$为起始的 return 的期望的最优的行为:

$$
a^{*}(s)=\arg \max _{a} Q^{*}(s, a)
$$

最优行为可以有很多个, 但是总有一个策略确定性地选择一个行为.

优化的目标

将基于策略$\pi$期望的回报可以分解为:
$$
\begin{equation}
\begin{split}
\mathbb{E}_{\tau \sim p(\tau)}[G(\tau)]&=E_{s \sim p\left(s_{0}\right)}\left[\mathbb{E}_{\tau \sim p(\tau)}\left[\sum_{t=0}^{T-1} \gamma^{t} r_{t+1} | \tau_{s_{0}}=s\right]\right]\\
&=\mathbb{E}_{s \sim p\left(s_{0}\right)}\left[V^{\pi}(s)\right]\quad\text{带入}\eqref{v_func}
\end{split}
\label{obj_func}
\end{equation}
$$
这个函数$\eqref{obj_func}$就是我们需要优化的目标.

马尔可夫决策过程(MDP)

马尔可夫性: 指系统的下一个状态 $S_{t+1}$ 仅与当前状态 $S_t$ 有关,而与之前的状态无关。定义为 $P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t]$。可以看出当前状态 $S_t$ 蕴含了历史信息。

agent 与环境在 MDP 交互过程:

马尔可夫决策过程由元组$\mathcal{M} = <\mathcal{S}, \mathcal{A}, P, R, \gamma>$ 表示。

  • $\mathcal{S}$ 是有限的状态集
  • $\mathcal{A}$ 是有限的动作集
  • $P$ 是状态转移概率矩阵
  • $R$ 是回报函数
  • $\gamma$ 是折扣因子,用来对 return 进行折扣操作

贝尔曼方程(Bellman Equation)

记$\tau_{0:T}=s_0,a_0,s_1,\cdots,s_T$, 则$\tau_{0:T}=s_0,a_0,\tau_{1:T}$

V的离散的贝尔曼方程可以写为:

$$
\begin{aligned}
V^\pi(s) &= \mathbb{E}[R(\tau) \vert s_0 = s] \\
&=\mathbb{E}_{\tau_{0:T}\sim{p(\tau)}}[r_0+\gamma r_1+\gamma^2r_2+\cdots\vert \tau_{s_0} = s]\\
&=\mathbb{E}_{a\sim\pi(a|s)}\mathbb{E}_{s'\sim{p(s'|s,a)}}\mathbb{E}_{\tau_{1:T}\sim{p(\tau)}}[r(s_0,a,s')+\gamma\sum_{t=1}^{\infty}\gamma^{t-1}r_t\vert \tau_{s_1}=s']\\
&=\mathbb{E}_{a\sim\pi(a|s)}\mathbb{E}_{s'\sim{p(s'|s,a)}}\left[r(s,a,s')+\gamma\mathbb{E}_{\tau_{1:T}\sim{p(\tau)}}\left[\sum_{t=1}^\infty\gamma^{t-1}r_t\vert\tau_{s_1}=s'\right]\right]&\scriptstyle\text{;r为常数}\\
&=\mathbb{E}_{a\sim\pi(a|s)}\color{red}{\mathbb{E}_{s'\sim{p(s'|s,a)}}[r(s,a,s')+\gamma V^\pi(s')]}
\end{aligned}
$$

红色部分就是$\eqref{q_func}$, 状态值函数(V)就是Q关于动作$a$的期望:

$$
V^\pi(s)=\mathbb{E}_{a\sim\pi(a|s)}[Q^\pi(s,a)]
$$

结合上面两个公式, 得到Q的贝尔曼方程:

$$
Q^\pi(s,a)=\mathbb{E}_{s'\sim{p(s'|s,a)}}\left[r(s,a,s')+\gamma\mathbb{E}_{a'\sim\pi(a'|s')}[Q^\pi(s',a')]\right]
$$

贝尔曼期望方程

递归地更新过程之后可以被分解为关于 state-value 和 action-value 的方程. 下图展示了贝尔曼期望方程如何更新 state-value 和 action-value 函数:

$$\begin{aligned}
V_{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a \vert s) Q_{\pi}(s, a) \\
Q_{\pi}(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_{\pi} (s') \\
V_{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a \vert s) \big( R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_{\pi} (s') \big) \\
Q_{\pi}(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a \sum_{a' \in \mathcal{A}} \pi(a' \vert s') Q_{\pi} (s', a')
\end{aligned}$$

具体细节可参考, (强化学习)- 马尔可夫过程中的 MDP 部分.

贝尔曼最优方程

我们只关心最优值而不是计算特定策略的期望. 我们可以直接跳转到期望的最大值而不使用策略, 最优值$V_*$和$Q_*$:

$$\begin{aligned}
V_*(s) &= \max_{a \in \mathcal{A}} Q_*(s,a)\\
Q_*(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_*(s') \\
V_*(s) &= \max_{a \in \mathcal{A}} \big( R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a V_*(s') \big) \\
Q_*(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a \max_{a' \in \mathcal{A}} Q_*(s', a')
\end{aligned}$$

如果知道了模型, 也就是知道了$P^a_{ss'}$和$R(s,a)$这个问题就变成了规划问题. 大多数情况下还是不知道模型, 所以无法直接通过贝尔曼方程去求解. 但是贝尔曼方程是许多 RL 算法的基础.

通用方法

DP

相关的描述参见(强化学习)- 动态规划寻找最优策略和不基于模型的学习. 简略介绍 DP 三个部分:

策略评估(Policy Evaluation)

在给定策略$\pi$计算状态价值:

$$V_{t+1}(s)
= \mathbb{E}_\pi [r + \gamma V_t(s) | S_t = s]
= \sum_a \pi(a \vert s) \sum_{s', r} P(s', r \vert s, a) (r + \gamma V_k(s'))$$

策略改善(Policy Improvement)

生成一个比策略$\pi$更好的策略$\pi'\geq\pi$, 这个和类似于贪心的性质:

$$Q_\pi(s, a)
= \mathbb{E} [R_{t+1} + \gamma V_\pi(S_{t+1}) \vert S_t=s, A_t=a]
= \sum_{s', r} P(s', r \vert s, a) (r + \gamma V_\pi(s'))$$

策略迭代(Policy Iteration)

通用的策略迭代(Generalized Policy Iteration, GPI)算法指在策略评估和改进的情况下通过迭代的程序来改进策略.

$$\pi_0 \xrightarrow[]{\text{evaluation}} V_{\pi_0} \xrightarrow[]{\text{improve}}
\pi_1 \xrightarrow[]{\text{evaluation}} V_{\pi_1} \xrightarrow[]{\text{improve}}
\pi_2 \xrightarrow[]{\text{evaluation}} \dots \xrightarrow[]{\text{improve}}
\pi_* \xrightarrow[]{\text{evaluation}} V_*$$

在 GPI 算法中, 值函数会随着逼近真实值同时策略也会达到最优. 策略迭代总是会收敛到最优: 因为改进后的策略$\pi'$是基于贪心地采取行动的策略, 即$\pi'(s)=\arg\max_{a\in\mathcal{A}}Q_\pi(s,a)$. 改进策略$\pi'$一定会更好:

$$
\begin{aligned}
Q_\pi(s, \pi'(s))
&= Q_\pi(s, \arg\max_{a \in \mathcal{A}} Q_\pi(s, a)) \\
&= \max_{a \in \mathcal{A}} Q_\pi(s, a) \geq Q_\pi(s, \pi(s)) = V_\pi(s)
\end{aligned}$$

Monte-Carlo 方法

值函数$V(s)=\mathbb{E}[G_t|S_t=s]$. MC 方法地思想: 从一个完整的 episode 中学习到不需要知道环境(without modeling the environmental dynamics)的经验, 根据学习到的经验来计算平均 return 作为期望 return. 为了计算经验平均(empirical mean) return $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$, MC 方法使用完整的 episode $S_1, A_1, R_2, \dots, S_T$, episode 会在时间$T$停止.

在状态$s$的经验平均的 return:

$$V(s) = \frac{\sum_{t=1}^T \mathbb{I}[S_t = s] G_t}{\sum_{t=1}^T \mathbb{I}[S_t = s]}$$

其中$\mathbb{I}[S_t = s]$是0-1指示函数(indicator function). 计算状态$s$访问次数的方式包括:

  • every-visit 每次都记录每个 episode 中状态$s$
  • first-visit 记录(record)在一次 episode 中状态$s$的第一次访问

同样地, MC 方法也可以扩展到关于 action-value 元组$(s,a)$:

$$Q(s, a) = \frac{\sum_{t=1}^T \mathbb{I}[S_t = s, A_t = a] G_t}{\sum_{t=1}^T \mathbb{I}[S_t = s, A_t = a]}$$

Monte-Carlo 控制

通过 MC 的方法学习到最优策略, 类似于 GPI, 我们可以通过以下的办法改进策略:

  1. 利用当前的值函数$\pi(s) = \arg\max_{a \in \mathcal{A}} Q(s, a)$贪心地更新策略
  2. 使用新的策略$\pi$(例如$\epsilon-\text{greedy}$来进行探索-利用的平衡)生成一个新的 episode.
  3. 使用新的 episode 估计新的 Q值: $q_\pi(s, a) = \frac{\sum_{t=1}^T \big( \mathbb{I}[S_t = s, A_t = a] \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1} \big)}{\sum_{t=1}^T \mathbb{I}[S_t = s, A_t = a]}$

First-visit 的 MC 方法:

时间差分学习(Temporal-Difference Learning)

与 MC 方法相似, TD 学习也是 model-free 的, 但是不需要像 MC 方法一样从完整的 episodes 学习, 即从不完整的 episodes 学习.

自助法(Bootstrapping)

TD 学习估计当前状态的价值使用了其他状态的价值.What exactly is bootstrapping in reinforcement learning?

值估计(Value Estimation)

TD 学习的关键思想是使用估计的 return: $R_{t+1}+\gamma{V}(S_{t+1})$, 即 TD 目标(TD target)来更新值函数$V(S_t)$. 参数$\alpha$用来更新值函数更新的步幅:

$$
\begin{aligned}
V(S_t) &\leftarrow (1- \alpha) V(S_t) + \alpha G_t \\
V(S_t) &\leftarrow V(S_t) + \alpha (G_t - V(S_t)) \\
V(S_t) &\leftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))
\end{aligned}$$

同样地, action-value 估计:

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

知道了估计值函数, 既可以通过下面的方法学习最优的策略(即 TD 控制, 关于更多的 TD 控制可以参考: (强化学习)- 不基于模型的控制)

SARSA: On-policy TD 控制

SARSA 可以指的是用于更新Q-值的序列: $\dots, S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}, \dots$. 与 GPI算法相似:

  1. 在时间$t$, 从状态$S_t$开始, 根据 Q-值选择行为$A_t=\arg\max_{a\in\mathcal{A}}Q(S_t,a)$; 通常可用 $\epsilon-\text{greddy}$策略.
  2. 采取动作$A_t$, 收到即时回报$R_{t+1}$和下一个状态$S_{t+1}$
  3. 按照同样的策略选择下一个动作: $A_{t+1} = \arg\max_{a \in \mathcal{A}} Q(S_{t+1}, a)$
  4. 更新 action-value 函数值: $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t))$
  5. $t=t+1$ 回到步骤1

在每次更新 SARSA 中, 都需要选择使用当前一样的的策略两次来选择行为.

具体的算法:

Q-Learning: Off-policy TD 控制

论文可以参考(Watkins & Dayan, 1992) 算法流程:

  1. 在时间$t$, 从状态$S_t$开始, 根据 Q-值选择行为$A_t=\arg\max_{a\in\mathcal{A}}Q(S_t,a)$; 通常可用 $\epsilon-\text{greddy}$策略.
  2. 采取动作$A_t$, 收到即时回报$R_{t+1}$和下一个状态$S_{t+1}$
  3. 更新 action-value 函数值: $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t))$
  4. $t=t+1$ 回到步骤1
  5. 详细算法步骤:

与 SARSA 不同的是, Q-leanring 并不继续使用当前的策略选择下一个动作. 而是使用估计得到的最优Q-值$Q_*$

Q-leaning 的 backup 方式与 SARSA 不同:

Deep Q-Network(DQN)

参考: (强化学习)- DQN

TD 和 MC 结合的学习

前面介绍在 TD 学习中的值函数估计方法. 目前在计算 TD 目标的时候, 我们仅仅追踪了(trace)下一个动作. 为了方便拓展, 可以考虑最总更多的时间步(steps)来估计 return.

记最多n时间步的 return 为: $G_t^{(n)}, n=1, \dots, \infty$, 则有:

n $G_t$ 备注
$n=1$ $G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$ TD 学习
$n=2$ $G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})$
$\cdots$
$n=n$ $G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$
$\cdots$
$n=\infty$ $G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T + \gamma^{T-t} V(S_T)$ MC 估计

通用的n-step TD 学习与之前更新值函数的公式形式一样:

$$V(S_t) \leftarrow V(S_t) + \alpha (G_t^{(n)} - V(S_t))$$

问题是如何确定最好的$n$, 哪一个$G_t^{(n)}$是好的 return 的逼近. 一个通用的方法是应用(apply)加权后的关于所有可能的 n-step TD 目标的和来选择最好的 n. 加权操作的系数$\lambda^{n-1}$, 这个和 return 使用 discount factor 的原因一样: 越远的感觉对于当前来说的可信度(confident)越低. 为了让权重的和加起来为1(在过程$n\rightarrow\infty$), 需要给每个权重乘以$(1-\lambda)$, 因为:

$$\begin{aligned}
\text{let } S &= 1 + \lambda + \lambda^2 + \dots \\
S &= 1 + \lambda(1 + \lambda + \lambda^2 + \dots) \\
S &= 1 + \lambda S \\
S &= 1 / (1-\lambda)
\end{aligned}$$

这个加权后的许多 n-step 的 returns 被称为$\lambda-\text{return}$, 即$G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$. TD 学习在值函数更新时采用$\lambda-\text{return}$作为对 return 的估计称为TD(λ). 之前所讨论的为TD(0).

关于三种不同的学习方法 Monte-Carlo, TD 学习和 DP 在 state-value 函数的 backup 过程:

策略梯度

参考: (强化学习)- 策略梯度(强化学习)- 深入策略梯度

Evolution Strategies

未完待续

存在的问题

Exploration-Exploitation Dilemma

参考: (强化学习)- 多摇臂赌博机问题和解决方案

Deadly Triad Issue

TD 方法中为了提到效率和灵活性引入了 bootstrapping. 然而当使用 off-policy 的时, 非线性函数估计(神经网络)的引入或造成训练变得不稳定(unstable)和难以收敛(converge). 这个问题就被称为deadly triad. 许多使用了 DL 的结构提出了解决方案: DQN 使用了经验回放(experience replay)和冻结目标网络(occasionally frozen target network)

摘自

添加评论