[RL Notes] epsilson 软性策略
在真实环境中，并不是总能满足试探性出发的假设，例如在某些任务中的状态和动作太多，或者实验的成本很大，无法确保智能体能够以所有可能的“状态-动作”二元组作为起始状态。
$\varepsilon$-贪心方法是一种 $\varepsilon$-贪心策略，即在绝大多数情况下选择获得最大动作价值估计的动作，同时而以一个较小的概率 $\varepsilon$ 随机选择一个动作。所有非贪心动作都有 $\frac{\varepsilon}{|\mathcal{A}(s)|}$ 的概率被选中，贪心动作被选中的概率为 $1 – \varepsilon+ \frac{\varepsilon}{|\mathcal{A}(s)|}$。
更一般地，$\varepsilon$-软性策略指的是对于某个 $\varepsilon > 0$，所有状态和动作的概率都有 $\pi(a|s) \geq \frac{\varepsilon}{|\mathcal{A}(s)|}$。由此可见 $\varepsilon$-软性策略是一个随机性策略，区别于确定性策略从一个状态映射到一个动作，随机性策略指定了每个状态下选择各个动作的概率。$\varepsilon$-贪心策略和均匀随机策略都是 $\varepsilon$-软性策略的一种。$\varepsilon$-软性策略强制智能体不断地进行试探，就不需要满足试探性出发的要求。
由于 $\varepsilon$-软性策略会不断地进行试探，它无法像试探性出发那样收敛到最优策略，而是会收敛到 $\varepsilon$ 最优策略，$\varepsilon$ 最优策略下每个状态的价值都高于任何其他 $\varepsilon$-软性策略。虽然无法达到最优策略，$\varepsilon$-软性策略仍可以获得足够好的策略，且不需要满足试探性出发的假设。
$\varepsilon$-软性策略的控制算法如下所示。
同轨策略的首次访问型 MC 控制算法（对于 $\varepsilon$-软性策略），用于估计 $\pi \approx \pi_*$
算法参数：很小的 $\varepsilon > 0$
初始化：
$\pi \leftarrow $ 一个任意的 $\varepsilon$-软性策略
对所有 $s \in \mathcal S$，$a \in \mathcal A(s)$，任意初始化 $Q(s, a) \in \mathbb R$
对所有 $s \in \mathcal S$，$a \in \mathcal A(s)$，$Returns(s, a) \leftarrow 空列表$
无限循环（对每幕）：
根据 $\pi$ 生成一幕序列 $S_0, A_0, R_1, \cdots, S_{T-1}, A_{T-1}, R_T$
$G \leftarrow 0$
对每幕中的每一步循环，$t = T-1, T-2, \cdots, 0$：
$G \leftarrow \gamma G + R_{t+1}$
如果二元组 $S_t, A_t$ 在 $S_0, A_0, S_1, A_1, \cdots, S_{t-1}, A_{t-1}$ 中没有出现过：
把 $G$ 加入 $Returns(S_t, A_t)$
$Q_t(S_t, A_t) \leftarrow \mathrm{average}(Returns(S_t, A_t))$
$A^* \leftarrow \underset{a}{\arg\max} \; Q_t(S_t, a)$
对于所有 $a \in \mathcal{A}(S_t)$：
$\pi(a|S_t) \leftarrow
\begin{cases}
1 – \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|} & \mathrm{if} \; a = A^* \\
\varepsilon / |\mathcal{A}(s)| & \mathrm{if} \; a \neq A^*
\end{cases}$