通过快速不精确的预言加速拟阵优化
内容提要
该文综述拟阵约束下的赌博与子模最大化研究，涵盖Best-Basis纯勘探、matroid bandits的OMM算法、k-次模函数逼近、公平性子模最大化、动态维护4+ε近似、匹配约束优化及预算半强盗遗憾改进，兼顾质量、公平与效率。
延伸解读
拟阵约束下的赌博与子模优化概览
文章综述了拟阵约束下的赌博与子模最大化研究，涵盖Best-Basis纯勘探、matroid bandits的OMM算法、k-次模函数逼近、公平性子模最大化、动态维护4+ε近似、匹配约束优化及预算半强盗遗憾改进。这些工作共同关注在拟阵约束下平衡质量、公平与效率，为相关领域提供了算法基础。
关键算法与理论保证
Best-Basis纯勘探算法达到几乎最优样本复杂度，用于确定拟阵的基并最大化总权重。OMM算法针对matroid bandits，提供gap-dependent和gap-free上界，时间复杂度亚线性。动态算法维护4+ε近似子系统，查找复杂度与序列长度无关。预算半强盗的遗憾改进将无间隙遗憾界限提高了sqrt(m)/log m倍。
应用场景与权衡
这些研究应用于流式与离线设置、动态插入删除、匹配约束等场景。公平性子模最大化在质量、公平性和广泛性之间提供不同权衡，并给出不可能性结果。k-次模函数逼近涵盖单调与非单调情况，并提供总大小约束的快速算法。匹配约束优化具有高精度和时间效率。
Q&A
拟阵约束下的纯勘探问题（Best-Basis）主要研究什么？
研究在随机多臂赌博游戏中受拟阵约束的纯勘探问题，目标是提供几乎最优样本复杂度的算法，以确定拟阵的基并达到最大总权重。
matroid bandits中的OMM算法是什么？它有什么特点？
OMM（乐观matroid最大化）是一种组合赌博算法，用于在matroid中最大化一个随机的初始未知的模块化函数。它证明了gap-dependent和gap-free两个上界，时间复杂度为亚线性，与其他相关量最多线性相关，并在三个实际问题上验证了有效性。
如何最大化满足拟阵约束的k-次模函数？
应用阈值减小算法来最大化满足matroid约束的k-次模函数，提出了逼近算法来处理单调和非单调k-次模函数，并提供了时间复杂度结果，还介绍了针对总大小约束的快速算法。
在拟阵约束的子模最大化中，公平性是如何考虑的？
针对更一般的matroid约束问题，提出了各种算法和不可能性结果，在质量、公平性和广泛性之间提供了不同的权衡。此前公平性研究仅限于基数约束或流式设置下的单调目标。
动态子模最大化算法如何维护近似解？
提出了一种动态算法，对于给定序列的插入和删除操作，维护一个在任一时间点具有4+ε近似度的子系统，参数化为matroid约束的秩k，且查找复杂度与序列长度无关。还探讨了基于基数约束的动态算法。
在预算组合半强盗中，如何改进遗憾界限？
通过将实现优化为特定的子模最大化，并设计适应的近似程序，提供了首个可以依赖奖励结构来改善遗憾界限的有效算法。这一改进将state-of-the-art的无间隙遗憾界限显著提高了sqrt(m)/log m倍，并转化为更普遍的预算组合半强盗。
