“思想总是走在行动的前面，正如闪电总是走在雷鸣之前。” — — 海涅

第三节 马尔科夫决策过程

随机过程和马尔科夫过程

与多臂老虎机问题不同，马尔可夫决策过程包含状态信息以及状态之间的转移机制。如果要用强化学习去解决一个实际问题，第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程，也就是明确马尔可夫决策过程的各个组成要素。

随机过程（stochastic process）是概率论的“动力学”部分。概率论的研究对象是静态的随机现象，而随机过程的研究对象是随时间演变的随机现象（例如天气随时间的变化、城市交通随时间的变化）。当前 T 时刻的状态用 STS_T 表示，所有可能的状态集合表示为 SS。在某时刻 tt 的状态 STS_T 通常取决于 tt 时刻之前的状态，可以表示为：

ST+1∼P(⋅ ∣ S1,...,ST)S_{T+1} \sim P(· ~|~S_1,...,S_T )

当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被称为具有马尔可夫性质（Markov property）。马尔可夫过程（Markov process）指具有马尔可夫性质的随机过程，也被称为马尔可夫链（Markov chain）。我们用 <S,P><S,P> 描述这个马尔科夫过程，其中 PP 是状态转移概率矩阵。

下图是一个具有 6 个状态的马尔可夫过程的简单例子。其中每个绿色圆圈表示一个状态，每个状态都有一定概率（包括概率为 0）转移到其他状态，其中通常被称为终止状态（terminal state），因为它不会再转移到其他状态，可以理解为它永远以概率 1 转移到自己。

给定一个马尔可夫过程，我们就可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。例如，从 s1s_1 出发，可以生成序列s1→s2→s3→s6s_1\to s_2\to s_3\to s_6等。

马尔可夫奖励过程

在马尔可夫过程的基础上加入奖励函数 r 和折扣因子 γ，就可以得到马尔可夫奖励过程（Markov reward process）。一个马尔可夫奖励过程由 (S,P,r,γ)(S,P,r,γ) 构成，各个组成元素的含义如下所示：

  • S 是有限状态的集合。
  • P 是状态转移矩阵。
  • r 是奖励函数，某个状态ss的奖励 r(ss)指转移到该状态时可以获得奖励的期望。
  • γγ 是折扣因子（discount factor），γ的取值范围为 [0,1)。引入折扣因子的理由为**远期利益具有一定不确定性，有时我们更希望能够尽快获得一些奖励，所以需要对远期利益打一些折扣。**接近 1 的 γ 更关注长期的累计奖励，接近 0 的 γ 更考虑短期奖励。

回报

在一个马尔可夫奖励过程中，从第 tt 时刻状态 StS_t 开始，直到终止状态时，所有奖励的衰减之和称为回报 GtG_t（Return），公式如下:

Gt=Rt+γRt+1+γ2Rt+2+⋯=∑k=0∞γkRt+kG_{t}= R_{t} + \gamma R_{t+1} + \gamma^{2}R_{t+2}+ \cdots = \sum_{k=0}^{\infty} \gamma^{k} R_{t+k}

其中，Rt 表示在时刻 t 获得的奖励。γ\gamma 是某种回报衰减，表示我们更关心有限步长以内的回报，这样也可以帮助强化学习算法进行收敛。这个 γ\gamma 也相当于对“绕远路”的行为做了一次惩罚。


价值函数

在马尔可夫奖励过程中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值(value)。所有状态的价值就组成了价值函数（value function），价值函数的输入为某个状态，输出为这个状态的价值。

我们将价值函数写成 V(s)=E[Gt∣St=s]V(s)=\mathbb{E}[G_t|S_t=s] 展开为：

V(s)=E[Gt∣St=s]=E[Rt+γRt+1+γ2Rt+2+…∣St=s]=E[Rt+γ(Rt+1+γRt+2+…)∣St=s]=E[Rt+γGt+1∣St=s]=E[Rt+γV(St+1)∣St=s]\begin{aligned} V(s) &=\mathbb{E}[G_t|S_t=s]\\ &=\mathbb{E}[R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\ldots |S_t=s]\\ &=\mathbb{E}[R_t+\gamma(R_{t+1}+\gamma R_{t+2}+\ldots)|S_t=s]\\ &=\mathbb{E}[R_t+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}[R_t+\gamma V(S_{t+1})|S_t=s] \end{aligned}

在上式的最后一个等号中，一方面，即时奖励的期望正是奖励函数的输出，即 E[Rt∣St=s]=r(s)\mathbb{E}[R_t|S_t=s]=r(s)；另一方面，等式中剩余部分 E[γV(St+1)∣St=s]\mathbb{E}[\gamma V(S_{t+1})|S_t=s] 可以根据从状态 ss 出发的转移概率得到，即：

V(s)=r(s)+γ∑s′∈Sp(s′∣s)V(s′)V(s)=r(s)+\gamma\sum_{s'\in S}p(s'|s)V(s')

上式就是马尔可夫奖励过程中非常有名的贝尔曼方程（Bellman equation），对每一个状态都成立。若一个马尔可夫奖励过程一共有 nn 个状态，即 S={s1,s2,…,sn}S=\{s_1,s_2,…,s_n\}，我们将所有状态的价值表示成一个列向量 ν=[V(s1),V(s2),…,V(sn)]T\nu=[V(s_1),V(s_2),…,V(s_n)]^T，同理，将奖励函数写成一个列向量 R=[r(s1),r(s2),…,r(sn)]TR=[r(s_1),r(s_2),…,r(s_n)]^T。于是我们可以将贝尔方程写成矩阵的形式：$$\nu=R+\gamma P\nu$$。

我们可以直接根据矩阵运算求解，得到以下解析解：$$\nu=(I-\gamma P)^{-1}R$$ ，以上解析解的计算复杂度是 O(n3)O(n^3)，其中nn是状态个数，因此这种方法只适用很小的马尔可夫奖励过程。求解较大规模的马尔可夫奖励过程中的价值函数时，使用动态规划、蒙特卡洛方法和时序差分，这些方法将在之后的章节介绍。

马尔科夫决策过程

马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程；而如果有一个外界的“刺激”来共同改变这个随机过程，就有了马尔可夫决策过程（Markov decision process, MDP）。我们将这个来自外界的刺激称为智能体（agent）的动作，在马尔可夫奖励过程（MRP）的基础上加入动作，就得到了马尔可夫决策过程（MDP）。马尔可夫决策过程由元组(S,A,P,r,γ)(S,A,P,r,\gamma) 构成，其中：

  • S 是状态的集合；
  • A 是动作的集合；
  • γ\gamma 是折扣因子；
  • r(s,a)r(s,a) 是奖励函数，此时奖励可以同时取决于状态 s 和动作 a；
  • P(s′∣s,a)P(s'|s,a) 是状态转移函数，表示在状态 s 执行动作 a 之后到达状态 s′s' 的概率。

MDP 中的状态转移函数和奖励函数都比 MRP 多了动作 aa 作为自变量。注意，在上面 MDP 的定义中，我们不再使用类似 MRP 定义中的状态转移矩阵方式，而是**直接表示成了状态转移函数。**这样做，一是因为此时状态转移与动作也有关，变成了一个三维数组，而不再是一个矩阵；二是因为状态转移函数更具有一般意义，例如，如果状态集合不是有限的，就无法用数组表示，但仍然可以用状态转移函数表示。

在马尔可夫决策过程中，通常存在一个智能体来执行动作。例如，一艘小船在大海中随着水流自由飘荡的过程就是一个马尔可夫奖励过程，它如果凭借运气漂到了一个目的地，就能获得比较大的奖励；如果有个水手在控制着这条船往哪个方向前进，就可以主动选择前往目的地获得比较大的奖励。

马尔可夫决策过程是一个与时间相关的，在智能体和环境 MDP 之间不断交互的过程。一般而言，它们之间的交互是如下图的循环过程：智能体根据当前状态StS_t选择动作AtA_t；MDP 根据奖励函数和状态转移函数得到St+1S_{t+1}和RtR_t反馈给智能体。智能体的目标是最大化得到的累计奖励。智能体根据当前状态从动作的集合AA中选择一个动作的函数，被称为策略。

rl-process.723b4a67.png


策略

智能体的策略（Policy）通常用字母π\pi表示。策略π(a∣s)=P(At=a∣St=s)\pi(a|s)=P(A_t=a|S_t=s)表示在输入状态情况下采取动作的概率。

当一个策略是确定性策略（deterministic policy）时，它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；当一个策略是随机性策略（stochastic policy）时，它在每个状态输出的是关于动作的概率分布，然后根据该分布采样就可以得到一个动作。

在 MDP 中，由于马尔可夫性质的存在，策略只需要与当前状态有关，不需要考虑历史状态。

总言而之，原来马尔科夫过程只基于状态，现在同时基于状态和动作了，我们称其为基于策略。

我们用Vπ(s)V^\pi(s)表示在 MDP 中基于策略的状态价值函数（state-value function），定义为从状态ss出发遵循策略π\pi能获得的期望回报。由于动作的存在，我们额外定义一个动作价值函数（action-value function）。我们用Qπ(s,a)Q^\pi(s,a)表示在 MDP 遵循策略时，对当前状态ss执行动作aa得到的期望回报。

不难看出，这两个函数存在以下关系：在使用策略中，状态ss的价值等于在该状态下基于策略π\pi采取所有动作的概率与相应的价值相乘再求和的结果：

Vπ(s)=∑π(a∣s)⋅Qπ(s,a)V^\pi(s) = \sum \pi(a|s)·Q^\pi(s,a)

另一方面，使用策略ππ时，状态ss下采取动作aa的价值，等于 即时奖励 加上 经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积：

Qπ(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)Q^{\pi}(s,a) = r(s,a) + \gamma \sum_{s'\in S}P(s'|s,a)V^{\pi}(s')

综上，通过简单推导可以分别得到两个价值函数的贝尔曼期望方程：

  • 状态价值函数的贝尔曼方程：

Vπ(s)=∑π(a∣s)⋅Qπ(s,a)=∑a∈Aπ(a∣s)(r(s,a)+γ∑s′∈Sp(s′∣s,a)Vπ(s′))\begin{aligned} V^{\pi}(s) &= \sum \pi(a|s)·Q^\pi(s,a) \\ &= \sum_{a \in A} \pi(a|s)\left(r(s,a)+\gamma \sum_{s'\in S} p(s'|s,a)V^{\pi}(s')\right) \\ \end{aligned}

  • 也可以写成期望的表示方式：

\begin{aligned} V^{\pi}(s) &= \mathbb{E}[r(S_0,A_0)+\gamma· r(S_1,A_1)+ \gamma^2·r(S_2,A_2)+... | S_0=s, \pi] \\ &=\mathbb{E}_{a\sim \pi(s)}~\left[r(s,a)+\gamma \sum_{s'\in S} \\ p(s'|s,a)V^{\pi}(s')\right] \\ &= \mathbb{E}_{a\sim \pi(s)}~\left [Q^\pi(s,a)\right ] \\ \end{aligned}

  • 动作价值函数的贝尔曼方程：

Qπ(s,a)=E[r(S0,A0)+γ⋅r(S1,A1)+γ2⋅r(S2,A2)+...∣S0=s,A0=a,π]=r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)=r(s,a)+γ∑s′∈Sp(s′∣s,a)∑a′∈Aπ(a′∣s′)Qπ(s′,a′)\begin{aligned} Q^{\pi}(s,a) &= \mathbb{E}[r(S_0,A_0)+\gamma· r(S_1,A_1)+ \gamma^2·r(S_2,A_2)+... | S_0=s, A_0=a, \pi] \\ &= r(s,a) + \gamma \sum_{s'\in S}P(s'|s,a)V^{\pi}(s') \\ &=r(s,a)+\gamma \sum_{s'\in S}p(s'|s,a)\sum_{a' \in A}\pi(a'|s')Q^{\pi}(s',a') \end{aligned}

接下来我们想要计算该 MDP 下，一个策略π\pi的状态价值函数。我们可以用蒙特卡洛方法来近似估计这个价值函数，好处在于我们不需要知道 MDP 的状态转移函数和奖励函数，它可以得到一个近似值，并且采样数越多越准确。

下图是一个马尔可夫决策过程的简单例子，每个浅色小圆圈旁的数字代表在某个状态下采取某个动作能获得的奖励。虚线箭头代表采取动作后可能转移到的状态，箭头边上的数字代表转移概率，如果没有数字则表示转移概率为 1。

mdp.aaacb46a.png (400×324)


占用度量

在强化学习中，**占用度量（Occupancy Measure）**是指在一个策略下，某个状态和动作的组合在长期内被访问的频率（数据分布）。它告诉我们，某个状态-动作对在整个策略执行过程中“出现”的概率有多大。

我们可以用一个例子来说明：

假设你是一只老鼠，在一个迷宫里寻找奶酪。迷宫有不同的房间（状态），你可以在每个房间做出选择，比如向左或向右走（动作）。你有一套策略来指导你在每个房间的行动，可能是根据闻到奶酪味道的强弱来做出选择。

占用度量就是在长期探索中，你按照这个策略走了很多次迷宫后，统计在每个房间采取某个动作的频率。例如，你可能发现自己有80%的时间在某个特定的房间里选择向右走，而在另一个房间里只有20%的时间选择向左走。

这个度量在强化学习中很有用，本质上就是某个策略πθ\pi_\theta和环境交互时得到的数据分布本身。它能帮助我们理解策略的行为模式，以及在改进策略时，哪些状态和动作的组合最常使用，从而帮助我们优化策略。

占用度量的公式表达为：ρπ(s,a)=∑γtP(St=s,At=a∣s0,π)\rho^\pi(s,a) = \sum \gamma^tP(S_t=s,A_t=a|s_0,\pi)，对于某一策略的累计奖励为：

\begin{align*} V(\pi) & = \mathbb{E}[r(S_0,A_0) + \gamma r(S_1,A_1) + \gamma^2 r(S_2,A_2) + \cdots \mid s_0,\pi] \\ & = \sum_{s,a} \sum_{t=0}^{T} \gamma^t P(S_t=s, A_t=a \mid s_0,\pi)· r(s,a) \\ & = \sum_{s,a} \rho^\pi(s,a)· r(s,a) = \mathbb{E}_\pi [r(s,a)] \end{align*}

这样，我们也可从另一角度去解读：“为什么占用度量和策略是一一对应的关系”。由于 ρπ\rho^\pi 的累和是 1/1-γ，我可以通过乘上一个 1-γ 使其变为分布。则有：(1−γ)ρπ(s,a)=Pπ(s)⋅π(a∣s)(1-\gamma)\rho^\pi(s,a) = P^\pi(s)·\pi(a|s) ，相当于我是在某个状态下，基于某种策略 π\pi 选择了一个行动 aa.

因此，如果有两个占用度量的分布是一样的，那么在任何状态下，他们采取的行动都是一样的，则他们的策略也必然相同。


贝尔曼最优方程

强化学习的目标通常是找到一个策略，使得智能体从初始状态出发能获得最多的期望回报。我们首先定义策略之间的偏序关系：当且仅当对于任意的状态ss都有Vπ(s)≥Vπ′V^\pi(s)\ge V^{\pi^\prime} ，记为π>π′\pi>\pi^\prime 。我们称这个策略为最优策略。

因此定义了最优状态价值和最优动作价值，同时也得到了贝尔曼最优方程。

V∗(s)=max⁡a∈A{r(s,a)+γ∑s′∈Sp(s′∣s,a)V∗(s′)}Q∗(s,a)=r(s,a)+γ∑s′∈Sp(s′∣s,a)max⁡a′∈AQ∗(s′,a′)V^{*}(s) = \max_{a\in A}\{r(s,a)+\gamma \sum_{s'\in S} p(s'|s,a)V^{*}(s')\} \\ Q^{*}(s,a) =r(s,a)+\gamma \sum_{s'\in S}p(s'|s,a)\max_{a' \in A}Q^{*}(s',a')

之后，我们将使用动态规划算法求解最优策略。

image-20241109120532476


动态规划算法

序言听上去挺装B的，本质意思就是：“策略迭代是 策略评估和策略提升不断循环交替 ，直至最后得到最优策略的过程。”

先回顾一下状态价值的贝尔曼方程：

Vπ(s)=∑π(a∣s)⋅Qπ(s,a)=∑a∈Aπ(a∣s)(r(s,a)+γ∑s′∈Sp(s′∣s,a)Vπ(s′))\begin{aligned} V^{\pi}(s) &= \sum \pi(a|s)·Q^\pi(s,a) \\ &= \sum_{a \in A} \pi(a|s)\left(r(s,a)+\gamma \sum_{s'\in S} p(s'|s,a)V^{\pi}(s')\right) \\ \end{aligned}

也可以写成期望的表示方式：

\begin{aligned} V^{\pi}(s) &= \mathbb{E}[r(S_0,A_0)+\gamma· r(S_1,A_1)+ \gamma^2·r(S_2,A_2)+... | S_0=s, \pi] \\ &=\mathbb{E}_{a\sim \pi(s)}~\left[r(s,a)+\gamma \sum_{s'\in S} \\ p(s'|s,a)V^{\pi}(s')\right] \\ &= \mathbb{E}_{a\sim \pi(s)}~\left [Q^\pi(s,a)\right ] \\ \end{aligned}

动作价值的贝尔曼方程：

Qπ(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)=r(s,a)+γ∑s′∈Sp(s′∣s,a)∑a′∈Aπ(a′∣s′)Qπ(s′,a′)\begin{aligned} Q^{\pi}(s,a) &= r(s,a) + \gamma \sum_{s'\in S}P(s'|s,a)V^{\pi}(s') \\ &=r(s,a)+\gamma \sum_{s'\in S}p(s'|s,a)\sum_{a' \in A}\pi(a'|s')Q^{\pi}(s',a') \end{aligned}

策略评估

策略评估这一过程用来计算一个策略的状态价值函数。由上式状态价值函数的贝尔曼方程可知，已知奖励函数和状态转移函数时，我们可以根据下一个状态的价值来计算当前状态的价值。因此，根据动态规划的思想，可以把计算下一个可能状态的价值当成一个子问题，把计算当前状态的价值看作当前问题。

更一般地考虑所有的状态，就变成了用上一轮的状态价值函数来计算当前这一轮的状态价值函数，即：

Vk+1(s)=∑a∈Aπ(a∣s)(r(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′))V^{k+1}(s) = \sum_{a \in A} \pi(a|s)\left(r(s,a)+\gamma \sum_{s'\in S} P(s'|s,a)V^{k}(s')\right)

我们可以选定任意初始值 V0V_0。根据贝尔曼方程，可以得知 Vk=VπV^{k}=V^{\pi} 是贝尔曼公式的不动点（fixed point）。由 Contraction Mapping Theorem 可知，这个不动点是存在且唯一的。然而，由于需要不断做期望方程的迭代，策略评估其实会耗费很大的计算代价。在实际的实现过程中，如果某一轮的提升非常小，可以提前结束策略评估。


策略提升

假设此时对于策略 π\pi，我们已经知道其价值 VπV^\pi，也就是知道了在该策略下从每一个状态出发最终得到的期望回报。

我们要如何改变策略来获得在状态下更高的期望回报呢？假设智能体在状态ss下采取动作aa，之后的动作依旧遵循策略π\pi，此时得到的期望回报其实就是动作价值Q(s,a)Q(s,a)。如果我们有Q(s,a)>Vπ(s)Q(s,a)>V^\pi(s)，则说明在当前状态下我们找到了一个更好的策略 π′\pi^{'} —— 该策略只替换在状态ss下的策略，其余状态和π\pi保持一致。

策略迭代算法

那么我们就可以很自然地说：对于某一个策略$\pi^\prime $，在任意状态下满足 Qπ′(s,a)≥Vπ(s)Q^{\pi^\prime}(s,a)\ge V^\pi(s)，则有 Vπ′(s)>Vπ(s)V^{\pi^\prime}(s)>V^\pi(s). 这便是策略提升定理（policy improvement theorem）， 他保证我们可以直接贪心地在每一个状态选择动作价值最大的动作，以得到更好的策略。

证明用到了之前提及的贝尔曼最优公式 ，用一个例子就可以很好理解。

image-20241031185616773


策略迭代算法的过程如下：对当前的策略进行策略评估，得到其状态价值函数，然后根据该状态价值函数进行策略提升以得到一个更好的新策略，接着继续评估新策略、提升策略……直至最后收敛到最优策略。

image-20241029150315555


价值迭代算法

策略迭代中的策略评估需要进行很多轮才能收敛得到某一策略的状态函数，这需要很大的计算量。价值迭代算法就是一种在策略评估时只进行了一轮更新的策略迭代算法。我们将其看做动态规划问题，随机初始化 V0(s)V^0(s) ，则转移方程可以表示为：

Vk+1(s)=max⁡a∈A{r(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′)}V^{k+1}(s) = \max_{a \in A} \{ r(s,a)+\gamma \sum_{s'\in S} P(s'|s,a)V^{k}(s') \}

等到 Vk+1V^{k+1} 和 VkV^k 相同时，它就是贝尔曼最优方程的不动点。最后我们利用 π(s)=arg⁡max⁡a{r(s,a)+γ∑s′∈SP(s′∣s,a)V(s′)}\pi(s)=\arg\max_a\{r(s,a)+\gamma \sum_{s'\in S} P(s'|s,a)V(s')\}，从中恢复出最优策略即可。

image-20241029165110522


蒙特卡洛方法（Monte-Carlo methods）

MC Basic: What’s Model-Free

蒙特卡洛方法是一种基于概率统计的数值计算方法，相较于动态规划算法，他是 model-free 的，不依赖于模型，即对应的概率分布。运用蒙特卡洛方法时，我们通常使用重复随机抽样，然后运用概率统计方法来从抽样结果中归纳出我们想求的目标的数值估计。一个简单的例子是用蒙特卡洛方法来计算圆的面积。

回忆一下，一个状态的价值是它的期望回报，那么一个很直观的想法就是用策略在 MDP 上采样很多条序列，计算从这个状态出发的回报再求其期望就可以了，即：

Vπ(s)=Eπ[Gt∣St=s]≈1N∑Gt(i)V^\pi(s)=E_\pi[G_t|S_t=s]\approx \frac1N\sum G_t^{(i)}

简单来讲，假设我们现在用策略π\pi从状态ss开始采样序列，据此来计算状态价值。我们为每一个状态维护一个计数器和总回报，计算状态价值的具体过程如下所示。

(1) 使用策略ππ采样若干条序列：

s0(i)→a0(i)r0(i),s1(i)→a1(i)r1(i),s2(i)→a2(i)…→aT−1(i)rT−1(i),sT(i)s_0^{(i)}\xrightarrow{a_0^{(i)}}r_0^{(i)},s_1^{(i)}\xrightarrow{a_1^{(i)}}r_1^{(i)},s_2^{(i)}\xrightarrow{a_2^{(i)}}\ldots\xrightarrow{a_{T-1}^{(i)}}r_{T-1}^{(i)},s_T^{(i)}

(2) 对每一条序列中的每一时间步的状态sis_i进行以下操作:

更新状态sis_i的计数器N(s)←N(s)+1N(s)←N(s)+1；

更新状态sis_i的总回报G(s)←G(s)+gtG(s)←G(s)+g_t；

(3) 每一个状态的值被估计为回报的平均值 V(s)=G(s)/N(s)V(s)=G(s)/N(s)。

“当你没有模型的时候，你得有数据。” 根据大数定律,当 N(s)→∞N(s)\rightarrow\infty，有V(s)→Vπ(s)V(s)\rightarrow V^\pi(s)。计算回报的期望时,除了可以把所有的回报加起来除以次数,还有一种增量更新的方法。对于每个状态ss和对应回报GG,进行如下增量式计算：

N(s)←N(s)+1; V(s)←V(s)+1N(s)(G−V(S))N(s)\leftarrow N(s)+1;~V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(S))


MC Exploring Starts & ϵ−\epsilon-Greedy

s0(i)→a1(i)s1(i)→a2(i)s2(i)→a3(i)s3(i)→a4(i)…→aT−1(i)sT−1(i)→aT(i)sT(i)s_0^{(i)}\xrightarrow{a_1^{(i)}} s_1^{(i)}\xrightarrow{a_2^{(i)}}s_2^{(i)}\xrightarrow{a_3^{(i)}}s_3^{(i)}\xrightarrow{a_4^{(i)}}\ldots\xrightarrow{a_{T-1}^{(i)}}s_{T-1}^{(i)}\xrightarrow{a_T^{(i)}}s_T^{(i)}

对于 MC basic 的思想，我们采样出一条序列（我称其为轨迹）后，只计算起始的state-action 对的回报，这对于这条轨迹的利用率显然是极低的；一个很自然的想法就是我们计算这条轨迹上每一对 state-action 的回报，然后更新我们的策略。

然而，为了保证每一个 state-action 都至少被采样一次，Exploring Starts 算法要求从所有 pair 为起点均采过一次样，这样显然不易于操作。所以就会想：啊，要是能在某条轨迹中采样到对应的 state-action 就好了。

因此我们提出了 ϵ−Greedy\epsilon-Greedy，这个策略在多臂老虎机那块儿也提到过。具体来讲，我们在原来的 MC 算法中最终会通过完全贪心的方式更新策略，此时我们替换成 ϵ−Greedy\epsilon-Greedy，其他没啥变化。这样只要我们采样的轨迹足够长，就能保证他一定能访问到所有 state-action 了。