因此我们重点在于状态-动作探索
**可以看作一个单步MDP模型
对于一个动作-价值是对于动作\(a\)的一个均值回报
\[q(a)=\mathbb{E}[R|A=a]
\]
对于最优价值\(v_*\)则是
\[v_*=q(a^*)=\max_{a\in\mathcal{A}}q(a)
\]
对于悔数（Regret）则是对于每一步的机会损失（opportunity loss）
\[l_t=\mathbb{E}[v_*-q(A_t)]
\]
总的悔数则是总的机会损失
\[L_t = \mathbb{E}\bigg[\sum^t_{\tau=1}v_*-q(A_\tau)\bigg]
\]
最大化累计回报\(\equiv\)最小化总悔数
对于计数\(N_t(a)\)是对于选择动作\(a\)的期望
对于间隔（gap）\(\Delta_a\)是动作\(a\)与最优动作\(a^*\)的价值之差，\(\Delta_a = v_*-q(a)\)
悔数则是与间隔与计数相关的函数
\[\begin{align}
L_t & = \mathbb{E}\bigg[\sum^t_{\tau=1}v_*-q(A_{\tau})\bigg] \\
& = \sum_{a\in\mathcal{A}}\mathbb{E}[N_t(a)](v_*-q(a)) \\
& = \sum_{a\in\mathcal{A}}\mathbb{E}[N_t(a)]\Delta_a
\end{align}
\]
对于一个性质良好的算法可以确保小计数量就可以得到大的间隔
问题在于间隔乃是未知的！
我们认定算法中存在近似关系\(Q_t(a)\approx q(a)\)
然后通过蒙特卡罗评估去估计每一次动作的价值
\[Q_t(a) = \frac{1}{N_t(a)}\sum^T_{t=1}\mathbf1(A_t=a)R_t
\]
贪心算法选择最高价值的动作
\[A_t=\mathop{\arg\max}_{a\in\mathcal{A}}Q_t(a)
\]
为此贪心算法（因为其完全不探索）使得其局限于局部最优解动作中
为此贪心算法的总悔数函数是呈线性的
将价值初始化为最大值即\(Q(a)=f_\max\)
然后运行贪心算法的行为：
\[A_t=\mathop{\arg\max}_{a\in\mathcal{A}}Q_t(a)
\]
鼓励去探索未知的价值
同样也存在一些情况会使得其无法找到最优解动作
同样最优初始化贪心算法也是线性悔数
主要思想：未知价值的动作高阶于已知价值的动作
对于\(\epsilon-Greedy\)一直保持探索状态
对于\(1-\epsilon\)的概率选择
\[A_t=\mathop{\arg\max}_{a\in\mathcal{A}}Q_t(a)
\]
对于\(\epsilon\)的概率会选择一个随机动作
但是\(\epsilon-Greedy\)同样会是线性的总悔数
跟Softmax探索差不多
我们为\(\epsilon_1,\epsilon_2\)去加入一个衰变的新方式
如下所示;
\[\begin{align}
c & > 0 \\
d & = \min_{a|\Delta_a>0}\Delta_a \\
\epsilon_t & = \min\bigg\{1,\frac{c|\mathcal{A}|}{d^2t}\bigg\}
\end{align}
\]
衰变\(\epsilon-greedy\)算法对数渐近的总悔数
不过不幸的是，这种衰变形式需要提前知道间隔
目标：找到一个在多臂老（和谐）虎（和谐）机上具有近似于线性总悔数的算法（一开始对于\(\mathcal{R}\)是一无所知的）
算法的表现主要取决于最优摇臂以及其他摇臂的差距
最复杂的问题就是相似的摇臂但是有多个均值
主要是用间隔\(\Delta_a\)以及分布的相似度（KL散度）：\(KL(\mathcal{R^a|R^(a^*)})\)
对于渐近总悔数其下界至少是与步数呈对数增长
\[\lim_{t\rightarrow\infin} L_t \ge \log t \sum_{a|\Delta > 0}\frac{\Delta_a}{KL(\mathcal{R^a|R^{a^*}})}
\]
为每个动作价值估算一个上确信界\(U_t(a)\)
例如说\(q(a)\le Q_t(a) + U_(a)\)就具有较高的概率
这主要取决于计数\(N(a)\)的取值
为此我们选择上确信界（UCB）最大的动作
\[A_t = \mathop{\arg\max}_{a\in\mathcal{A}}Q_t(a) + U_t(a)
\]
使\(X_1,\dots,X_t\)是符合\(i.i.d.\)条件的处于区间\([0,1]\)随机变量，并且使得\(\overline X_t = \frac{1}{\tau}\sum^t_{\tau=1}X_\tau\)作为采样均值。然后：
\[\mathbb{P}[\mathbb{E}[X]>\overline X_t + u]\le e^{-2tu^2}
\]
我们将会把霍夫丁不等式应用于老（和谐）虎（和谐）机问题的回报
由选择动作作为条件
\[\mathbb{P}[q(a)>Q_t(a) + U_t(a)] \le e^{-2N_t(a)U_t(a)^2}
\]
求出真实价值超出\(UCB\)的概率\(p\)
开始求解\(U_t(a)\)
\[\begin{align}
e^{-2N_t(a)U_t(a)^2} & = p \\
U_t(a) & = \sqrt{\frac{-\log p}{2N_t(a)}}
\end{align}
\]
当我们对回报的观测越多，\(p\)就会降低，例如说\(p = t^{-4}\)
确保我们在\(t\rightarrow \infin\)时每次选择最优动作
\[U_t(a) = \sqrt{\frac{2\log t}{N_t(a)}}
\]
为此引出了\(UCB1\)算法（还有很多形式可供尝试）
\[A_t = \mathop{\arg\max}_{a\in\mathcal{A}}\bigg(Q_t(a) + \sqrt{\frac{2\log t}{N_t(a)}}\bigg)
\]
为此\(UCB\)算法成功达到了对数渐近总悔数
\[\lim_{t\rightarrow\infin}L_t\le 8\log t\sum_{a|\Delta_a > 0}\Delta_a
\]
贝叶斯老（和谐）虎（和谐）机显式地利用了以往关于回报的学习，即\(p[\mathcal{R^a}]\)
我们定义一个带有参数\(\mathbf w\)关于动作-价值函数分布\(p[Q|\mathbf w]\)
贝叶斯方法在于计算后来的关于\(\mathbf w\)的分布
\[p[\mathbf w | R_1,\dots,R_t]
\]
通过后来的数据来制导探索进程
前置信息越精确，那么算法性能越好
通过贝叶斯定律计算前置\(p[\mathbf w|R_1,\dots R_{t-1}]\)
计算动作-价值的后置分布
\(p[Q(a)|R_1,\dots R_{t-1}]=p[Q(a)|\mathbf w]p[\mathbf w|R_1,\dots,R_{t-1}]\)
然后估计后置状态的上确信界，如\(U_t(a)=c\sigma(a)\)
然后选择动作以让\(Q_t(a) + c\sigma(a)\)最大化
概率匹配基于\(a\)是最优动作的概率去选择动作
\[\pi(a)=\mathbb{P}\bigg[Q(a) =\max_{a'}Q(a')|R_1,\dots,R_{t-1}\bigg]
\]
概率匹配在于未确定下方面也是充分乐观的
对于不确定性的动作有更高的可能性成为最大值
但是解析性地计算后续状态的\(\pi(a)\)比较困难
辛普森采样属于一种基于采样的概率匹配
\[\pi(a)=\mathbb{E}\bigg[\mathbf 1(Q(a)=\max_{a'}Q(a'))|R_1,\dots,R_{t-1}\bigg]
\]
然后通过贝叶斯定律去计算后续分布
\[p_\mathbf w(Q|R_1,\dots,R_{t-1})
\]
从前驱状态去采用一个动作-价值函数\(Q(a)\)
然后通过最大化采样去选择动作
\[A_t = \mathop{\arg\max}_{a\in\mathcal{A}}Q(a)
\]
对于伯努利老（和谐）虎（和谐）机，辛普森采样成功达到了黎氏与拉宾氏最低悔数下界
我们已经将老（和谐）虎（和谐）机问题视为一步决策问题了
同样也可以视为序列决策问题
每一步都存在一个信息状态\(\overline{S}\)把过去所有的信息累计起来
对于每个动作\(A\)会引出一个状态转移到达新的一个信息状态\(\overline{S'}\)（通过信息加和），基于概率\(\overline{P}^A_{\overline{S},\overline{S}'}\)
为此现在我们就拥有了一个增强信息状态空间的\(MDP\ \mathcal{\overline{M}}\)
\[\mathcal{\overline{M}}=\langle \overline{S}, \mathcal{A},\mathcal{\overline{P}},\mathcal{R},\gamma\rangle
\]
从关于回报函数\(\mathcal{R^a}\)的\(Beta(\alpha_a,\beta_a)\)开始
每一次时间选择动作\(a\)，然后更新后续的\(\mathcal{R^a}\)
如此就得以为适用于贝叶斯的MDP了一个状态转移函数\(\mathcal{\overline{P}}\)
对于所有的信息状态\((\alpha,\beta)\)代表着一个模型\(Beta(\alpha,\beta)\)
而每次状态转移则代表一个贝叶斯模型的更新
求解适用于贝叶斯的MDP需要考虑到价值信息
因为新信息的影响会作为因子影响到模型更新中
在伯努利的问题中，适用于贝叶斯的MDP可以直接通过动态规划解决
这种解法正是被称之为吉丁斯索引（Gittins index）
但是精确来说解决一个适用于贝叶斯的MDP是有点麻烦的
近来的方法已经可以做到探索大规模规划了
（例如蒙特卡罗树搜索算法）
供以构造一颗前向树然后寻找贝叶斯从最开始的学习状态的最优探索与开发权衡
\[A_t=\mathop{\arg\max}_{a\in\mathcal{A}}Q(S_t,a)+U(S_t,a)
\]
MDPs同样可以通过信息状态来增强
现在增强过的状态为\(\overline{S}=\langle S,I\rangle\)
适用于贝叶斯的方法得到了一个后继状态模型代表着每个已经被增强过的状态\(\mathbb{P}[\mathcal{P,R}|I]\)
求解适用于贝叶斯的MDP去寻找最优探索开发权衡必须关系与前驱状态
然而增强MDP一般来说都较为庞大
蒙特卡罗树形搜索在这里就被证明比较高效了（Guez等人的工作）
进阶的来说还有更多用来安排探索与开发的复杂方法
本文链接：http://task.lmcjl.com/news/12759.html
