PAC and regret

论文阅读

---

这篇论文提及到，在大型的或者无限状态的MDP中，通过采样模型，一些MDP中的状态转移是可以用一些状态模型观测得到的。此时，采样复杂度就是为了达到学习目的，所需要的某种采样模式的次数。

This thesis considers various sampling models in which transitions based on the MDP can be observed by calling the sampling model.

The sample complexity can be construed to be the number of calls to the sampling model required to achieve "learning".

• 定义：Generative Model $G(M)$是一个随机算法，即输入$(s,a)$，能根据状态转移概率$s'\sim P(·|s,a)$类似于自生自灭。

• $\mu - reset model$ 这种模式可以允许agent根据$\mu$，重置当前状态到一个被采样的状态去。

2.near-optimal

文中试图用一种方式去讲解什么是near-optimal
关于phased value iteration 这个例子，作者给出了证明，证明其只要使用了采样算法（Generation model）被使用了

$$O\Big(\frac{NAT^2}{\varepsilon^2}\log\frac{NAT}{\delta}\Big)$$
即被采用并用于估计Transition这么多次，则有大于$1-\delta$得概率使得返回策略$\pi$对于所有的状态来说： $$V_\pi(s)\geq V^*(s)-\varepsilon$$
image_1d1bcv57689p1p6p1ume17f6i222d.png-66.8kB
其证明如下：
假设有如下式子成立：
$$\bigg|E_{s'\sim P(·|s,a)}\Big[\hat{V}_t(s')\Big]-E_{s'\sim \hat{P}_{t-1}(·|s,a)}\Big[\hat{V}_t(s')\Big]\bigg|<\varepsilon$$

所以：

同理，则有对于贪婪策略$\pi(s,t-1)$也有如下推导

使用迭代公式，很容易得出如下结论

因此则有如下：

$$\max_s\big|V_\pi(s)-V^*(s)\big|<2\varepsilon T$$
但是，我们希望的是得到一个
$$V_\pi(s)\geq V^*(s)-\varepsilon$$
这样的误差，所以，问题是需要提高该值的精度
$$\bigg|E_{s'\sim P(·|s,a)}\Big[\hat{V}_t(s')\Big]-E_{s'\sim \hat{P}_{t-1}(·|s,a)}\Big[\hat{V}_t(s')\Big]\bigg|<\varepsilon$$
即让当前的 $$\varepsilon \rightarrow \frac{\varepsilon}{2T}$$ 才能得到上述式子，所以此时，我们就想给出一个界限，看看m值到达多少时才会满足上述式子，这个界限设为$\delta$。从算式可以看出，这是个关于估计值和实际值差距的问题，此时借用霍夫丁不等式可以得出结论：即
$$P\Big\{\bigg|E_{s'\sim P(·|s,a)}\Big[\hat{V}_t(s')\Big]-E_{s'\sim \hat{P}_{t-1}(·|s,a)}\Big[\hat{V}_t(s')\Big]\bigg|>\frac{\varepsilon}{2T}\Big\}<\exp(-\frac{\varepsilon^2 m }{2T^2})$$
要对所有的(s,a)，都要成立，则有如下边界：
$$NAT\exp(-\frac{\varepsilon^2 m }{2T^2}) = \delta$$
推出 $$m = \frac{2T^2}{\varepsilon^2}\log{\frac{NAT}{\delta}}$$
即
$$m = O(\frac{T^2}{\varepsilon^2}\log{\frac{NAT}{\delta}})$$

此时 由霍伊夫定不等式可以得到，有$1- \delta$的概率可以让其值在满足：

$$V_\pi(s)\geq V^*(s)-\varepsilon$$
或者（个人比较喜欢下一种）
$$\varepsilon\geq V^*(s)-V_\pi(s)$$ 即两者差距的大小在$\varepsilon$中。

关于2的总结

要想达到上述目标，关键是在于其假设的估计值与期望值的差距大小，似乎是一种PAC的方式，我目前不清楚是否后文会给出详细的PAC的证明，但是现在从目前的理解来看，这个东西就有点像$(\varepsilon,\delta)-PAC$算法。即如何设置一个值来保证其在这些学习过程中，能够达到近似最优（near-optimal）