ICMLMay, 2023

具有强鲁棒性保证的边加权在线二分匹配学习

PDF
TL;DR本研究提出了一种基于强化学习的新型边权重在线二分图匹配方法（LOMAR），以实现良好的平均情况和最坏情况下的性能，其中，关键新颖的操作是根据谨慎的条件决定是否跟随专家的决策还是 RL 决策。
online bipartite matchingreinforcement learningedge-weightedrobustness guaranteesempirical experiments
发现论文，激发创造
  • 在线二分匹配的深度策略：一种强化学习方法

    本文提出了一个端到端的强化学习框架，基于历史数据的试错，通过设置神经网络架构和设计特征表示，对在线匹配问题进行更好的匹配决策。在两个在线匹配问题中，我们的模型表现得比传统算法更好，提高了匹配质量约 3-10％，代码可在给出的 URL 中公开获得。

    Sep, 2021

  • 在线优化的具有记忆成本的强化学习

    提出一种新的 Expert-Robustified Learning (ERL) 方法，即利用专家在线算法进行投影运算实现对机器学习行为（即 Online Optimization with Memory Costs）的强度鲁棒性，并通过递归神经网络模型进行传递专家在线算法的平均性能训练，从而在内存成本上提高行为竞争性能和稳健性。

    May, 2023

  • 在线带有有限指导的二部图匹配

    研究在线非加权二分图匹配中的问题，其中有 n 个离线顶点和 n 个在线顶点，并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率，但我们表明在对抗性到达模型中，没有学习增强方法既可以是 1 - 一致的又可以比 1/2 - 健壮。同时，在随机到达模型下，我们展示了如何利用分布测试方法设计出一种算法，该算法接受关于在线顶点的外部建议，并在竞争比率上从不需要建议的方法和最优比率 1 之间插值，这取决于建议的质量。

    May, 2024

  • 在线 3D 装箱的可调鲁棒强化学习

    在线 3D 装箱问题（3D-BPP）的有效政策设计一直是一个长期的挑战，本文提出了可调整鲁棒性强化学习（AR2L）框架，通过调整鲁棒性权重实现策略在平均情况和最坏情况下的平衡，以提升策略的鲁棒性同时保持较高的性能水平。

    Oct, 2023

  • 基于配对损失函数的在线学习

    本文研究了在线学习算法中带有成对损失函数的泛化性能，并提出了一种数据依赖性较小的界限来衡量在线学习算法的平均风险产生的序列的模型偏差，同时针对常见的机器学习问题，如基于排名和监督度量学习提出了实际应用案例。

    Jan, 2013

  • 元学习对抗性赌博机

    本文研究了跨多任务的在线学习问题，设计了一个统一的元算法，旨在优化平均性能。该算法在多臂老虎机和乐观线性优化两个重要情境下提供了特定保证，通过任务平均后悔的降低来提高性能。

    May, 2022

  • 在线随机匹配：新算法和界限

    本文提出了一些基本的算法变体和改进，旨在提高已知 IID 模型和具有随机奖励延伸的模型的竞争比率，另外提出了加强型线性规划基准来提高非加权边的概率的情况。

    Jun, 2016

  • 通过子模性在在线二分匹配中平衡相关度和多样性

    本文介绍了在线子模二分图匹配问题（Online Submodular Bipartite Matching）的概念和算法，该问题旨在在考虑到多样性和相关性的情况下，通过优化子模函数 $f$ 来匹配边的集合以得到最佳匹配。

    Nov, 2018

  • 元学习对抗强盗算法

    该论文研究了具有 bandit feedback 的在线元学习，目的是通过某种自然的相似性度量改善类似的多个任务的性能。

    Jul, 2023

  • 在线随机匹配：超越 1-1/e

    本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。

    May, 2009