3.1 Monte Carlo Learning

前置知识

2.3 Value Iteration and Policy Iteration (值迭代)

2.4 Value Iteration and Policy Iteration (策略迭代与truncated iteration)

引例

• 对于抛硬币，通过不断重复实验，可以得到哪一面朝上的概率，进而得到其对应的面朝上的期望

  \(\mathbb{E}[X]=\sum_{x \in \mathcal{X}} p(x) x\).

  \(\mathbb{E}[X] \approx \bar{x}=\frac{1}{n} \sum_{j=1}^n x_j\).

  重复次数越多，得到的结果就越接近真实值，其依据就是大数定律, 证明见Proof: Law of Larg numbers.

我理解的，为什么要使用Monte Carlo方法呢，因为它可以允许我们不需要知道，在当前状态采取某个动作时会导致的下个状态的概率，从而求得某个return。

Policy iteration to Model-free

策略迭代过程中分2步完成：

第一步，给定一个初始state value，迭代求得真实的state value： \(v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k} v_{\pi_k}\)

第二步，求得了 state value 后，进行策略提升 \(\pi_{k+1}=\arg \max _\pi\left(r_\pi+\gamma P_\pi v_{\pi_k}\right)\)，而这一步其实是利用state value 来找到每一个状态中 action value 最大的 action 来替换原来策略中的 action，即：

\(\begin{aligned} \pi_{k+1}(s) & =\arg \max _\pi \sum_a \pi(a \mid s)\left[\sum_r p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_{\pi_k}\left(s^{\prime}\right)\right] \\ & =\arg \max _\pi \sum_a \pi(a \mid s) q_{\pi_k}(s, a), \quad s \in \mathcal{S}\end{aligned}\)

可以看到在这个过程中最重要的还是要找到最大的 action value \(q_{\pi_{k}}(s,a)\)。

这个值有两种求法，第一个是依赖模型，利用state value来求，即：\(q_{\pi_k}(s, a)=\sum_r p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_{\pi_k}\left(s^{\prime}\right)\)

第二个是依赖定义，它是一个期望，即：

\(\begin{aligned} q_{\pi_k}(s, a) & =\mathbb{E}\left[G_t \mid S_t=s, A_t=a\right] \\ & =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\ldots \mid S_t=s, A_t=a\right],\end{aligned}\)

这个期望的求法即是可以通过采样来完成，不需要模型参与。

Monte Carlo 方法来估计 action value:

• 对某个状态的某个action (s,a),根据当前策略，生成一个episode

• 这个episode的return \(g(s,a)\) 即为当下的一个采样，即：

  \(q_{\pi_k}(s, a)=\mathbb{E}\left[G_t \mid S_t=s, A_t=a\right]\)

• 如果我有很多个这样的采样，即可以用于估计它的actio value,即：

  \(q_{\pi_k}(s, a)=\mathbb{E}\left[G_t \mid S_t=s, A_t=a\right] \approx \frac{1}{N} \sum_{i=1}^N g^{(i)}(s, a)\).

MC basic algorithm

1. 利用初始策略，采用抽样方法，求得每个状态的action value,

2. 利用所有求得的action value，更新当下的策略（使用状态值最大的action替换原策略的action）, 在原来的策略迭代算法中，action value是利用state value及模型来求得的，而在这里是利用多次采样的结果估计的，这就是最本质的区别。正式算法截个图如下：

   

本部分总结： 本部分介绍了使用抽样方法来替代模型的根本原理，虽然这个方法其实效率很低，但是却是model free方法最核心的部分