该论文研究强化学习中处理稀疏回报的方法,提出了通过构造最小化覆盖时间的选项来加速探索的算法,并在多个领域实验证明其可以改善学习效率。
Mar, 2019
研究了一种随机漫步的聚合系统,其中每个个体都在有限图 G 上进行随机漫步,或者(更一般地)按照某个可逆马尔可夫链生成器 Q 进行演变,证明了所有漫步者聚合成单个群集的时间 C 的期望值最多仅为状态空间中某个元素的最大碰撞时间的常数倍,并且提出了关于仅剩下 k>1 个群集的预期时间的结果。
Sep, 2010
对有限图上的懒惰随机游走进行了新的研究,得到了有关回归概率、最大期望击中时间、会面时间引理和多个随机游走的期望完全合并时间的新结果。
Jul, 2018
本研究探讨在具有任意度数分布的随机不相关网络中的有偏随机游走过程,并推导了平稳占据概率和两个节点间的平均传输时间的精确表达式,同时探讨了循环搜索对传输时间的影响,为复杂网络上与运输相关问题的理论处理以及关键的数据包生成率的定量估计提供基础。
Sep, 2007
探究搜索者搜索未知的加权无向图的问题,证明最近邻算法的竞争比率在树中为 θ(logn),并研究参数范围内算法 Blocking 在单轮图上是 3-competitive,在仙人掌图上是 5/2+√2 约等于 3.91-competitive。
Apr, 2020
本研究探讨了因果棘手问题,针对给定的因果图和指定的一组干预方案,识别接近最优的干预方案,并通过实验显示了改进。
May, 2023
研究并比较了基于分支减枝算法在理论和实践方面的差异,证明了这些算法在现实应用中具有竞争力,以及理论研究对分支算法实际影响的作用。
Nov, 2014
该研究提出了一种强大的工具包,用于估计具有共同随机行走和混淆时间的随机游走在无向图上的汇聚时间和会合时间,并对相似类别的图形的汇聚时间和会合时间进行了完整的探索。
Nov, 2016
探索与会合问题中,我们研究了移动计算中的两个基本问题:探索和会合。通过在未知图中使用两个不同的移动代理,代理可以在所有节点上读写信息。我们展示了一个简单的深度优先搜索变体,在 $m$ 个同步时间步骤内完成了集体探索,其中 $m$ 是图的边数。同时,我们引入了一个算法,保证在不超过 $rac {3}{2} m$ 个时间步骤内实现会合,这是对所谓的 “等待妈妈” 的算法(需要 $2m$ 个时间步骤)的改进。所有的保证都是从一个更一般的异步设置中推导出来的,在该设置中,代理的速度在任何时刻都由对手控制。如果将边数 $m$ 替换为所有边长度的总和,则我们的保证也推广到加权图。
Mar, 2024
本文研究了有限图上合并随机行走的完全合并时间 C,提出了 mean meeting time 和 mixing times 的充分条件,得出了类似于大型完整图的定律。证实均场行为可在混合时间远小于 mean meeting time 的所有顶点可转移图中出现,并且扩展到非翻转游走和选民模型共识时间。
Sep, 2011