在之前的UCB / greedy等算法中，我们实际上关注的是 “upper bound”， 也即“算法最坏也不会比$\sqrt{nk}$ 差“（以UCB 为例）。但很自然的会有一个问题是：$\sqrt{nk}$ 足够好了么？ 会不会有regret为常数的算法？
lower bound analysis 解决的就是这一问题，我们通过证明问题的lower bound 来展示我们的算法足够优秀
主要介绍$\epsilon$-greedy算法和UCB算法以及他们的regret 证明。非常重要的是介绍了一个很普适的证明框架(UCB 分析1)
Explore Then Commit (ETC) Algorithm
The goal of this chapter is to formally introduce stochastic bandits. The model introduced here provides the foundation for the remaining chapters that treat stochastic bandits.
开坑online learning and bandits，一直想着系统地学习下，利用2022 summer争取拿下。🤤🤤🤤
|
The furies are at home in the mirror;
it is their address. Even the clearest water, if deep enough can drown.
Never think to surprise them.
Your face approaching ever so friendly is the white flag they ignore. There is no truce with the furies.
A mirror’s temperature is always at zero.
It is ice in the veins. Its camera is an X-ray.
It is a chalice held out to you in silent communion,
where gaspingly you partake of a shifting identity never your own. |
复仇女神们的居处，
就在家家户户的镜中。 即使世间至清的水， 那深潭亦会带来灭顶之灾。
他们不会吃惊，
容颜永恒。 他们无视白旗的友好， 怒火永不熄灭。
镜子凝在零度，
它是血中之冰，是X光片。 它在沉默的圣飨向你递来圣杯
在那里，你喘着粗气
扮演着一个不断变化的 始终不属于你的身份。 |
KKT已经成为了几乎所有的CS 、MAT学生都绕不开的知识、工具。浅写一下自己在几年的学习中对KKT和CQ的一些理解，方便自己日后复习。
最大流与最小割问题常用于matching问题、clustering问题等等…
**最小割问题：**在一个带权重的图中找出一个将所有顶点分为两类的分割方法，切分割的边权重合最小（实际上就是一种对于边的cut）。
**最大流问题：**在一个带权有向图中，找出可能的最大流量从 S->T。
对于给定的两个字符串 S1 和 S2 将2个字符串进行匹配解决：S2是否是S1 的子字符串？S2和S1 如何进行“对齐”使得2个字符串最接近？等问题
最直接以及常见的使用场景例如：查询 DNA上是否含有某个基因，2个DNA是否有相似的片段（可能是相似的基因）
昨夜如梦，像流星划过，忘了他，忘了那双手所干过的一切
我再也不会像从前那样玩世不恭，再也不会像从前那样爱你，
突然有一天我醒了，看着外面一片白云，火车低低地飞过，一片叶子掉下来，
我感觉到一切在生长，一切又在衰老，一切就像你，一切就像我，一切只是一场梦，我再也找不到那些时光。
杀死他，再给他一刀，
开枪吧，
杀了他，干了他，
我就还不信了，还不信呢，杀了他！嘿！