Reinforcement Learning

计算 \(V_k(s)\) 时，为了避免存储所有的回报，可以把它改写为“增量更新”的形式，推导如下：
\[\begin{align*} V_{k+1}(s) & = \frac{G_1(s) + G_2(s) + \cdots + G_{k+1}(s)}{k+1} \\ & = \frac{ k V_k(s) + G_{k+1}(s)}{k+1} \\ & = \frac{1}{k+1} \left[ (k+1) V_k(s) - V_k(s) + G_{k+1}(s) \right] \\ & = V_k(s) + \frac{1}{k+1} \left[ G_{k+1}(s) - V_k(s) \right] \end{align*}\]

由上式知，计算 \(V_{k+1}(s)\) 时只需要记下 \(V_{k}(s)\) 和 \(k\) ，不再需要记录 \(G_1(s), G_2(s), \cdots, G_k(s)\) 了。更进一步，我们可以连 \(k\) 都不用记录：

\begin{equation} \underbrace{V_{k+1}(s)}_{\substack{\text{“状态-值函数”的} \\ \text{新估计值}}} = \underbrace{V_{k}(s)}_{\substack{\text{“状态-值函数”的} \\ \text{旧估计值}}} + \alpha [\underbrace{G_{k+1}(s)}_{\substack{\text{根据当前Episode计算} \\ \text{的状态折扣回报}}} - \underbrace{V_{k}(s)}_{\substack{\text{“状态-值函数”的} \\ \text{旧估计值}}} ] \tag{“蒙特卡罗”增量更新公式} \end{equation}

其中， \(\alpha\) 为正数，它随着采样数 \(k\) 的增加而不断变小。 \(G_{k+1}(s) - V_k(s)\) 可以看作是估计误差。

在一次 episode 过程中，同一个状态可能出现多次。假设在第 3 次 episode 时出现下面序列：
\[s_0, +0, s_4, +0, s_2, +4, s_6, +1, s_4, +1, s_5, +2, s_7\]

上面出现了两次状态 \(s_4\) ，那么这第一个和第二个状态 \(s_4\) 的折扣回报分别为：

\begin{align*} \\ G_{31}(s_4) &= 0 + 1 \times 4 + 1^2 \times 1 + 1^3 \times 1 + 1^4 \times 2 = 8 \\ G_{32}(s_4) &= 1 + 1 \times 2 = 3 \end{align*}

First Visit 的含义是在计算状态 \(s\) 处的值函数时，只利用每次实验(episode)中第一次访问到状态 \(s\) 时返回的值，如前面例子中计算 \(V(s_4)\) 时只使用 \(G_{31}(s_4)\) 。
Every Visit 的含义是在计算状态 \(s\) 处的值函数时，利用所有访问到状态 \(s\) 时的回报返回值。如前面例子中计算 \(V(s_4)\) 时同时使用 \(G_{31}(s_4)\) 和 \(G_{32}(s_4)\) 。

Monte Carlo Methods have below advantages:

• Zero bias
  
• Good convergence properties (even with function approximation)
  
• Not very sensitive to initial value
  
• Very simple to understand and use
  

But it has below limitations as well:

• MC must wait until end of episode before return is known
  
• MC has high variance
  
• MC can only learn from complete sequences
  
• MC only works for episodic (terminating) environments
  

参考：https://towardsdatascience.com/monte-carlo-learning-b83f75233f92

有了“状态-值函数”，为什么需要定义 Q 函数（“行为-值函数”）呢？

However, we must note that knowing the exact value of all states is not enough to determine what to do. If the agent does not know which action results in reaching any particular state, i.e. if the agent does not have a model of the transition function, knowing V does not help it determine its policy. This is why similar algorithms based on state-action pairs and computing the action-value function Q were developed.

摘自：Markov Decision Processes in Artificial Intelligence, 2.5. Temporal difference methods

我们知道，策略 \(\pi\) 下，在状态 \(s\) 处的累积回报的期望值被定义为值函数（或者称为“状态-值函数”），常常用 \(V\) 表示。相应的，策略 \(\pi\) 下，在状态 \(s\) 处执行动作 \(a\) 后的累积回报的期望值被定义为“行为-值函数”，常常用 \(Q\) 表示。

“行为-值函数”的计算公式（也可称为定义）为：

\begin{equation} Q^{\pi}(s,a) = r(s, a) + \gamma \sum_{s' \in S}p(s' \mid s, a)V^{\pi}(s') \tag{Definition of action-value function} \end{equation}

式中， \(r(s, a)\) 表示从状态 \(s\) 处执行动作 \(a\) 后得到的回报， \(p(s' \mid s, a)\) 表示当在状态 \(s\) 中完成行动 \(a\) 时，到达状态 \(s'\) 的概率。

它们显然有关系（ \(\pi^*\) 为最优策略）：
\[V^{\pi^*}(s) = \max_a Q^{\pi^*}(s, a)\]

SARSA 算法的更新公式和 TD(0) 算法是一样的，只是把“状态-值函数”换成了“行为-值函数”。

SARSA 算法的更新公式：

\begin{equation} 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)] \tag{SARSA update equation} \end{equation}

使用更新公式时需要的信息为 \(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\) ，这也是 SARSA 名称的由来。

SARSA 算法的描述如图 2 所示。

摘自：Reinforcement Learning - An Introduction, Chapter 6 Temporal-Difference Learning

Q-Learning 算法的更新公式和 SARSA 算法是一样的，只是把 \(Q(s_{t+1}, a_{t+1})\) 换成了 \(\max_b Q(s_{t+1}, b)\) （注：行动 \(b\) 是使得 \(Q(s_{t+1}, b)\) 取得最大值的行动，在图 3 中行动 \(b\) 写为了 \(a\) ，它可以写为任何其它符号）。

Q-Learning 算法的更新公式：

\begin{equation} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_{t+1} + \gamma \max_b Q(s_{t+1}, b) - Q(s_t, a_t)] \tag{Q-Learning update equation} \end{equation}

Q-Learning 算法的描述如图 3 所示。

参考：
http://mnemstudio.org/path-finding-q-learning-tutorial.htm
https://zhuanlan.zhihu.com/p/46850008

SARSA 和 Q-Learning 的区别如图 4 所示。

参考：
https://www.oreilly.com/library/view/hands-on-reinforcement-learning/9781788836524/20659243-cadb-46f0-b5c3-3acadd590d67.xhtml

在 Markov Decision Processes in Artificial Intelligence 一书中采用了记法一。这种记法下“状态-值函数”和“行为-值函数”分别定义如下。

策略 \(\pi\) 下，状态 \(s\) 处的累积回报的期望值被定义为值函数，即“状态-值函数”为：

\begin{align*} V^{\pi}(s) &= E[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \mid \pi, s_0 = s] \\ &= E \left[\sum_{t=0}^{\infty} \gamma^t R(s_t) \mid \pi, s_0 = s \right] \\ \end{align*}

策略 \(\pi\) 下，状态 \(s\) 进行行动 \(a\) 的价值，即“行为-值函数”为：

\begin{align*} Q^{\pi}(s, a) &= E[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \mid \pi, s_0 = s, \pi(s_0) = a] \\ &= E \left[\sum_{t=0}^{\infty} \gamma^t R(s_t) \mid \pi, s_0 = s, \pi(s_0) = a \right] \\ \end{align*}

在 Reinforcement Learning - An Introduction 一书中采用了记法二。这种记法下“状态-值函数”和“行为-值函数”分别定义如下。

假设采样轨迹为：
\[S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \cdots\]
状态 \(S_t\) 后的回报为 \(R_{t+1}, R_{t+2}, \cdots\) ，这个序列的折扣回报为：
\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\]

策略 \(\pi\) 下，状态 \(s\) 处的累积回报的期望值被定义为值函数，即“状态-值函数”为：

\begin{align*} V^{\pi}(s) &= E [G_t \mid S_t = s] \\ &= E \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \mid S_t = s \right] \\ \end{align*}

策略 \(\pi\) 下，状态 \(s\) 进行行动 \(a\) 的价值，即“行为-值函数”为：

\begin{align*} Q^{\pi}(s, a) &= E [G_t \mid S_t = s, A_t = a] \\ &= E \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \mid S_t = s, A_t = a \right] \\ \end{align*}