我们提出了一种新颖的组合性随机贪婪的赌博算法 (SGB)，用于组合多臂赌博问题。该算法在没有额外信息的情况下，仅观察到每个时间步 t∈[T] 时选择的一组 n 个臂的联合奖励。SGB 采用了一种优化的随机探索再确认的方法，并且专门设计用于具有大量基本臂的情景。与现有方法在每个选择步骤中都会探索整个未选择基本臂集不同，我们的 SGB 算法仅对未选择的臂进行优化比例的抽样，并从该子集中选择行动。我们证明了对于单调随机次模性奖励，我们的算法实现了 (1-1/e) 的遗憾边界，其复杂度为 O (n^(1/3) k^(2/3) T^(2/3) log (T)^(2/3))，在基数约束 k 方面优于最先进的方法。此外，我们在在线受限社交影响最大化的背景下对我们的算法进行实证评估。我们的结果表明，我们提出的方法始终优于其他算法，并且随着 k 的增长，性能差距也增大。

Dec, 2023

利用随机 bandit 反馈在无序集合函数最大化问题中建立了首个极小极大下界，并提出了一个能够匹配下界的算法。

Oct, 2023

本文提出了三种在线算法，分别用于子模最大化问题中的函数渐变计算优化、带赌博的子模最大化问题和响应式带乘积集约束的带乘积子模问题。三个算法在达到 $(1-1/e)$ -regret bound 的前提下，分别取得了复杂度为 $O (T^{4/5})$、$O (T^{8/9})$ 以及 $O (T^{8/9})$ 的折损。

Oct, 2019

本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。

Jul, 2020

本文提出了一种线性时间算法 STOCHASTIC-GREEDY 用于求解一般性单调子模函数最大化问题，旨在实现对数据的概括，比传统算法 lazy greedy 更快且表现基本一致。

Sep, 2014

研究在线赌徒学习中的单调多线性 DR - 子模函数设计算法 BanditMLSM，可以获得（1-1/e）遗憾的 O（T ^ {2/3} log T）；将子模随机带入分割拟阵约束和赌徒顺序单调最大化，可以在两个问题中获得 O（T ^ {2/3} log T）的（1-1 /e）遗憾，这比现有结果更好。给出第一个关于具有分割拟阵约束的子模赌徒的次线性遗憾算法。

May, 2023

在带有赌博反馈的子模函数优化中，考虑使用逼近算法来最大化线性结构的子模客观函数，通过模拟算法和实证研究检验了样本效率与线性结构的关系。

Jul, 2024

本文研究了具有随机次模（期望上）奖励和完全 bandit 延迟反馈的组合多臂老虎机问题，其中假定延迟反馈是组合匿名的，同时研究了有界择逊、随机独立和随机条件独立三种延迟反馈模型，给出了每种延迟模型的后悔界限，忽略问题相关参数，证明所有延迟模型的后悔界限为 $ ilde {O}(T^{2/3} + T^{1/3} u)$，其中 $T$ 为时间跨度，$ u$ 根据三种情况有不同的定义，因此在所有三种延迟模型中表明了延迟对后悔的添加项，该算法被证明优于具有延迟复合匿名反馈的其他全 bandit 方法。

Mar, 2023

在线决策问题、子模函数、求和 - 最大函数、强化学习以及后悔上界是该研究论文的主要关键词和内容。

Nov, 2023

本研究探讨了组合多臂赌博的后悔下界，并证明了在所有光滑奖励函数下，这种下界都是合理的，并且根据 Merlis 和 Mannor（2019）提出的 Gini 加权平滑度参数确定单调奖励函数的下界。

Feb, 2020