MC epsilon-greedy

Monte-Carlo with epsilon-greedy

Soft Policy

• deterministic policy: greedy policy(only choose the max q action, other unconsidered action probability is just 0)
• stochastic policy: soft policy(the probability to take any action is positive, sample action from probability)
• with soft policy, sufficiently long episodes can guarantee that all state-action pairs are visited
• then we do not need to have a large number of episodes starting from every state-action pair(remove the exploring starts condition)

$\epsilon$-greedy Policy

Greedy policy:

$$\pi (a|s)\leftarrow \{\begin{array}{ll}1,& \text{if }a=\arg {\max }_{a}q(s,a)\\ 0,& \text{otherwise}\end{array}$$

$\epsilon$-greedy policy:

$$\pi (a|s)\leftarrow \{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|},& \text{if }a=\arg {\max }_{a}q(s,a)\\ \frac{\epsilon }{|\mathcal{A}(s)|},& \text{otherwise}\end{array}$$

where:

• $\epsilon \in [0,1]$ is a small positive number
• $\mathcal{A}(s)$ is the set of all possible actions in state $s$
• $|\mathcal{A}(s)|$ is the number of actions in $\mathcal{A}(s)$.

Core Idea

hard to soft这里的idea很简单，就是从greedy action的概率1中挖了一块$\epsilon$出来分给所有的action（包括greedy action，q最大的那个action），从而让所有action都有概率被选上。

• $\epsilon \to 0$ 很显然就会变得更greedy，更倾向于选择q最大的action
  • p_greedy → 1, p_others → 0
  • more exploitation less exploration
• $\epsilon \to 1$ 就会变得更random，因为被挖出来分配到所有action的概率越来越平均
  • p_greedy → 1/|A|, p_others → 1/|A|
  • more exploration less exploitation

利用和探索其实自己的理解又加深了一点

• $\underset{\text{greedy}}{\underbrace{\text{exploitation}}}$就是倾向在已知的最好的action中选择
• $\underset{\text{random}}{\underbrace{\text{exploration}}}$就是倾向在所有的action中随机选择

上一章所提及到的确保每个$(s,a)$都能被访问到的exploring-starts现在也不需要用了，因为我们自带了exploring的功能，不是100%greedy，而是带了$\epsilon$的random exploration在里面，所以就确保了只要次数够多（一个step足够多的episode），每个$(s,a)$都能被访问到。

Algorithm

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{MC }\epsilon \text{-Greedy (a variant of MC Exploring Starts)}\\ & \text{Initialization: }\text{Initial policy }{\pi }_0(a|s)\text{, value }q(s,a)\text{ for all }(s,a).\text{Returns}(s,a)\leftarrow 0,\text{Num}(s,a)\leftarrow 0.\\ & \text{For each episode, do:}\\ & \text{Select starting }(s_0,a_0)\\ & \text{Generate episode }{s}_0,a_0,r_1,s_1,\dots ,s_{T-1},a_{T-1},r_T\text{ following current policy }\pi .\\ & g\leftarrow 0\\ & \text{For }t=T-1,T-2,\dots ,0:\\ & g\leftarrow \gamma g+r_{t+1}\\ & \text{Returns}(s_t,a_t)\leftarrow \text{Returns}(s_t,a_t)+g\\ & \text{Num}(s_t,a_t)\leftarrow \text{Num}(s_t,a_t)+1\\ & q(s_t,a_t)\leftarrow \frac{\text{Returns}(s_t,a_t)}{\text{Num}(s_t,a_t)}\text{(Policy evaluation)}\\ & \pi (a|s_t)\leftarrow \{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{if }a=\arg {\max }_{a}q(s_t,a)\\ \frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{otherwise}\end{array}\text{(Policy improvement)}\end{array}}$$

• simple modify of MC Exploring Starts
  1. just remove the line of selecting starting $(s_0,a_0)$ under exploring-starts condition
  2. change the policy improvement formula to $\epsilon$-greedy policy

Optimality vs exploration

1. 牺牲了$\epsilon$的最优性来保证探索率，实际上只要$\epsilon$足够小还是可以趋近于最优的
2. 也可以用decay的方法，一开始设置一个较大的$\epsilon$，然后随着episode的增加逐渐减小$\epsilon$，这样可以在开始的时候更多的探索，然后在后面逐渐趋近于最优
3. 可以唯一确定的是只要$\epsilon$不为零，那么最终的state value肯定不是最优的，因为总是有一部分action的概率是随机的(总可能进入forbidden的区域获得惩罚)，如果太大state value甚至会变成负数（比如环境中陷阱要多于安全的区域，总是乱走那么就会变成负数）
4. 在$\epsilon$-greedy学习完之后我们希望直接取greedy的最大值进行决策（也叫optimal $\epsilon$-greedy），相当于就是不希望再带着随机性去探索，而是希望转成对应的greedy policy，并且这个策略和最优策略是相同的(consistent)，赵老师举了一个例子就是当$\epsilon \ge 0.2$时转换后的策略和最优策略怎么都等价不了了，这个告诉我们如果要用$\epsilon$-greedy的话$\epsilon$要尽量小，但是又不能为0，所以这个是一个trade-off的问题