针对对抗性线性情境赌博机的高效稳健算法
提出了一种基于oracle的算法来应对敌对情境下的赌博问题,该算法在访问离线优化Oracle并且享有$O((KT)^{\frac{2}{3}}(\log N)^{\frac{1}{3}})$的遗憾度的情况下是计算有效的,其中K是操作的数量,T是迭代次数,N是基线策略的数量。
Jun, 2016
本文使用代理损失函数导出了新的后悔界限和新的算法,其中借助于坡道损失函数,我们导出了新的边界界限。同时也根据标准顺序复杂度度量了回归函数的基准类,使用铰链损失函数,导出了一种有效的算法,并且其中包含了一个以$d$维度回归器引出的基准方针。在实现假设下,本研究的结果也可以得出经典的后悔边界。
Jun, 2018
研究了随机线性赌博机问题,考虑了对抗攻击,提出了两种Robust Phased Elimination算法,证明了在非污染情况下可以获得近似最优的收益,并得出针对这些算法的相对近似最优的加性项。同时,在具有多样化情境的情况下,表明一种简单的贪婪算法是稳健的,近似最优的加性遗憾项,尽管不进行明确的探索并且不知道C。
Jul, 2020
考虑对抗性线性上下文赌博机设置,文中给出了一种新的算法,通过利用与不需要上下文设置的线性赌博机的新联系,利用连续指数权重算法在概率单形上的一个截断版本来获得结果,并证明了其结果优于最坏情况下的后悔,特别的当环境相对温和时,考虑了上下文的密度是对数凹的情况,给出了一种同时优于二阶和一阶损失的方法。
May, 2023
通过实现无需模拟器的多项式时间算法,我们在拥有线性上界误差的情况下,提高了对抗性线性上下文赌博问题的表现,实现了近乎优化的后悔度,同时保持了计算效率。
Sep, 2023
通过将属于再现核希尔伯特空间的损失函数纳入到对手性线性背景乐队的在线学习问题的研究中,我们提出了一种计算有效的算法,该算法利用一种新的对损失函数进行乐观偏差估计的方法,在对底层内核进行的各种特征值衰减假设下实现接近最佳的后悔保证。
Oct, 2023
我们提出了一种对抗情境下上下文弛豫的方法,其中上下文是从已知分布中顺序独立抽取的,并且成本序列由在线对手选择。我们的算法在每一轮最多对离线优化预言机进行O(K)次调用,有一个遗憾界限为O(T^(2/3)(Klog(|Pi|))^(1/3)),这是首次改进了Syrgkanis等人在2016年NeurIPS会议上获得的 O((TK)^(2/3)(log(|Pi|))^(1/3)) 最佳界限,也是第一次与Langford和Zhang在2007年NeurIPS会议上为随机情况获得的原始界限相匹配。
Oct, 2023