模和子模函数的top-k优化问题一直是策略优化问题的重点和难点。近年来,随着人工智能的兴起,模函数和子模函数被用到了越来越多的实际应用建模中。在建模实际应用中,为了适用更多的应用场景,研究者们都希望在更普适的模型下研究模函数和子模函数top-k优化问题。基于以上背景,本文选择了模函数优化中最受关注的多臂赌博机问题,和子模函数优化中最受关注的影响力最大化问题展开了研究。本文立足于更普适的模型下研究这些优化问题,特别地,在模函数优化问题中,本文研究了 top-k臂在轮次模型下的优化算法。在子模函数优化问题中,本文研究了更一般的框架下的影响力最大化问题。具体而言,本文的研究内容和贡献如下。首先,在轮次模型下研究了 top-k臂选择问题。在轮次模型里,toP-kk臂选择问题允许一个轮次里面采样多个臂,这些臂的采样结果会在下一轮的报告中给出。在轮次模型里,对于top-k选择问题,算法设计者不仅要优化样本数,同时要优化轮次数。这无疑增大了问题的难度。现有的方法要么是轮次复杂度没有达到最优,要么是在很强的假设下可以达到轮次最优。显然这都不是问题最好的解决方案。针对这一问题,本文同时研究了概率精确的(PAC)和精确的(Exact)top-kk臂选择问题。综合来看,贡献如下1)对于PAC top-kk臂选择问题,本文在实现最优的查询复杂度的同时只用了 O(logk/δ*(n))轮次。进一步地,本文证明了提出的算法的轮次复杂度也达到了下界。另δ 一方面其它的前人工作最优的轮次复杂度是O(log n/k2)对于Exact top-kk臂选择问题,本文实现了在接近最优的查询复杂度的同时将轮次复杂度的一项从O(logn/k)提升到了 O(logk/δ*(n))。3)在实验中,本文验证了所提出的算法在使用了更少的轮次的同时,在查询需要的样本上有着数量级的提升。其次,在影响力最大化问题中,本文立足于建模更符合现实应用场景的信息接受度传播模型。经典的影响力最大化问题将激活节点视为了信息接受节点。但实际上激活(信息传播)和接受是两个不同的行为。为此,本文提出了信息接受度最大化问题,该问题的目标函数既考虑了激活节点,也考虑了其邻居的感知节点。本文用一个抽象函数描述了这两种节点对信息接受的贡献。并证明了传统的影响力最大化和信息覆盖度最大化问题都是该模型的特例。为了深人理解信息接受度的传播过程,本文全面分析了信息接受度函数的性质,证明了该问题的计算复杂度。算法方面,本文以贪心算法为基础,设计了反向抛币算法,给出了算法的复杂度和正确性证明。最后本文在四个真实数据集上验证了算法的正确性和效率。本文实验结果还证实了不同目标函数得到问题的解是有差别的,说明了信息接受度建模的必要性。