社区探索:从离线优化到在线学习
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
利用机器学习预测作为辅助,通过引入预测算法结合最近邻算法,探索未知环境的学习增加变种基于线上图探索问题的研究,证明当预测精度高时算法显著优于其他线上算法,并在预测较差时保持良好保证,提供了与预测误差平稳退化的理论最坏情况下的绑定,并通过计算实验证实了结果,同时还扩展了该概念到鲁棒算法的一般框架,通过在给定算法与最近邻算法之间进行谨慎插值,证明了新的性能边界,既利用特定输入的良好性能,又确立了对任意输入的鲁棒性。
Dec, 2021
研究异步在线学习设置和代理人网络,探讨了代理人自网络结构中获取信息的效果对后悔程度的影响。当激活是随机时,研究了代理人无需了解网络结构即可达到最优后悔。当激活是对抗性的时候,研究了代理人可以基于网络结构的信息来减少后悔的上界。
Jan, 2019
本研究中,我们针对社交网络中的影响最大化问题进行研究。通过利用社区结构,我们设计了一种简单的启发式算法,在实践中有效地克服了该问题。尽管我们的算法在一般情况下的近似保证无法界定,但我们对其性能进行了实验,并在通过随机块模型生成的图中证明算法获得了常量近似保证。
Jan, 2018
本文提出了一种从初始节点开始探索,一旦选择邻居节点,新节点变得可见和可选择的新模型,称为 NetExp,并给出了基于底层网络结构属性与理论边界的性能分析,此方法在各种模拟问题实例和社会问答系统中得到了评价。
Apr, 2015
该论文提出了一种新的 “元” 算法,可以在在线学习环境中实现算法的快速适应,该算法对于同样时间复杂度的其他算法而言具有更好的强适应性后悔边界,并且在专家建议的学习及度量学习方面表现优异。
Nov, 2017
介绍了一种基于 Lagrangian hedging 的在线算法(包括 regret-matching 和 hedge),通过引入 optimism 和 adaptive step size 对非对抗性问题进行了优化,并给出了相应的性能界限。
Jan, 2021
本文提出了一种简单的方法,可以将两个具有不同遗憾保证的无参数在线学习算法结合起来得到一个新的算法,其遗憾值是两个算法中的最小值。此外,作者还提出了一种基于该方法的黑盒子算法,可以生成乐观的在线学习算法,并提供无拘束设定下的第一个乐观遗憾保证。
Feb, 2019
本研究中,我们采用了三种 Deep Q-Networks 算法,分别使用了智能采样策略来解决 URRLC 消息的发送问题,证明了方差和最大熵探索的效率比标准的贪婪探索方法更高。
Apr, 2023