深度增强学习David Silver（九）——Exploration and Exploitation

本课主要内容：

• multi-armed bandits
• contextual bandits
• MDPs

multi-armed bandit是多臂赌博机，有元组$langle cal{A},cal{R} rangle$，目标是最大化奖励。
行动价值函数是一个行动所获得的平均奖励：$Q(a)=mathop{mathbb{E}[r|a]}$
最优价值为$V^*=Q(a*)=max_{a in cal{A}}Q(a)$
regret指每一步的损失：$l_t=mathbb{E}[V^*-Q(a_t)]$
total regret为：$L_t=mathbb{E}[sum_{tau=1}^tV^*-Q(a_tau)]$
最大化总奖励就是最小化total regret。
$L_t$又可以表示为：
$L_t=sum_{a in cal{A}}mathbb{E}[N_t(a)](V^*-Q(a))=sum_{a in cal{A}}mathbb{E}[N_t(a)]Delta_a$
$Delta_a$称为gap，是行动a和最优行动a*之间的价值上的差值。
用$hat{Q}_t(a)$估计$Q(a)$，使用Monte-Carlo估计：$hat{Q}_t(a)=frac{1}{N_t(a)}sum_{t=1}^Tr_t1(a_t=a)$
greedy算法总是选择使$hat{Q}_t(a)$最高的行动，这样容易陷入次最优行动中，而且total regret呈线性。
$epsilon$-greedy保证了最小的regret：$l_t ge frac{epsilon}{cal{A}}sum_{ain cal{A}}Delta_a$
但它也是线性的。
因此选择让$epsilon$逐渐衰减，
$c>0,d=mathop{min}_{a|Delta_a>0}Delta_i,epsilon_t=min{1,frac{c|cal{A}|}{d^2t}}$
衰减的$epsilon_t$-greedy的total regret呈对数。

以上是exploitation方面的方法，接下来从exploration方面进行考虑，在不确定面前，要多探索未知位置。对每个行动价值函数设置一个置信上界$hat{U}_t(a)$。比如$Q(a)le hat{Q}_t(a)+hat{U}_t(a)$具有很高的概率。当经过的次数$N_t(a)$较少时，$hat{U}_t(a)$就要比较大，让它多经过几次。
选择最大化置信上界（Upper Confidence Bound, UCB）的行动：
$a_t=mathop{argmax}_{aincal{A}}hat{Q}_t(a)+hat{U}_t(a)$
根据Hoeffding不等式推导得出$U_t(a)=sqrt{frac{2logt}{N_t(a)}}$

目前为止我们还没有做关于奖励R分布的假设。设给定历史$h_t=a_1,r_1,...,a_{t-1},r_{t-1}$下，奖励R的后验分布为$p(cal{R}|h_t)$。
使用后验概率引导exploration：

• Upper confidence bounds (Bayesian UCB)
• Probability matching (Thompson sampling)
• Better performance if prior knowledge is accurate

假设奖励分布为高斯分布$R_a(r)=cal{N}(r;mu_a,sigma_a^2)$，根据贝叶斯公式计算高斯后验概率：
$p[mu_a,sigma_a^2|h_t]propto p[mu_a,sigma_a^2]mathop{Pi}_{t|a_t=a}cal{N}(r_t;mu_a,sigma_a^2)$
选择使Q(a)的标准差最大的行动。
$a_t=mathop{argmax}_{ain cal{A}}mu_a+csigma_a/sqrt{N(a)}$

probability matching根据a是最优行动的概率选择行动。Thompson sampling实现probability matching。
$pi(a|h_t)=mathbb{P}[Q(a)>Q(a'),forall a' neq a|h_t]=mathbb{E}_{cal{R}|h_t}[1(a=mathop{argmax}_{a in cal{A}}Q(a))]$

如果我们知道信息的价值，那么能更好的权衡exploration和exploitation。刚才我们将bandit看做一步的decision-marking问题。它也可以作为序列决策问题。在每一步，都有一个信息状态$hat{s}$，定义MDP $hat{M}=langle hat{S},A,hat{P},R,gamma rangle$

感觉这章偏应用。。看不下去了，第十章也是偏应用，就不讲了，就这样吧。。

最后

以上就是平淡橘子最近收集整理的关于深度增强学习David Silver（九）——Exploration and Exploitation的全部内容，更多相关深度增强学习David内容请搜索靠谱客的其他文章。