Submodular Bandit Problem Under Multiple Constraints
Submodular Bandit Problem Under Multiple Constraints
复制标题
多重约束下的子模老虎机问题
DOI：
10.48550/arxiv.2302.01324
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Tomoko Ohkuma
中科院分区：
文献类型：
--
作者：
S. Takemori;Masahiro Sato;Takashi Sonoda;Janmajay Singh;Tomoko Ohkuma
为了同时解决推荐系统中的多样化检索和在线学习问题，提出了线性次模强盗问题。如果不存在不确定性，则该问题等价于基数约束下的子模最大化问题。然而，在某些情况下，推荐列表应该满足额外的约束，例如预算约束，而不是基数约束。因此，出于多样化的检索考虑预算约束，我们引入了一个子模块强盗问题下的交集$l$背包和$k $系统的约束。这里$k$-系统约束形成了一个非常一般的约束类，包括基数约束和$k$拟阵约束的交集。为了解决这个问题，我们提出了一个非贪婪算法，自适应地集中在一个标准的或修改后的置信上限。我们提供了一个高概率的近似遗憾的上限，其中的近似比匹配的快速离线算法。此外，我们使用合成和两个真实世界的数据集进行各种组合的约束下的实验，并证明我们提出的方法优于现有的基线。
The linear submodular bandit problem was proposed to simultaneously address diversified retrieval and online learning in a recommender system. If there is no uncertainty, this problem is equivalent to a submodular maximization problem under a cardinality constraint. However, in some situations, recommendation lists should satisfy additional constraints such as budget constraints, other than a cardinality constraint. Thus, motivated by diversified retrieval considering budget constraints, we introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. Here $k$-system constraints form a very general class of constraints including cardinality constraints and the intersection of $k$ matroid constraints. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast offline algorithm. Moreover, we perform experiments under various combinations of constraints using a synthetic and two real-world datasets and demonstrate that our proposed methods outperform the existing baselines.