提出新算法，在矩阵约束下高效优化随机子模函数。
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
- 通过压缩交换策略，将指数级复杂度降为多项式时间。
- 在n个元素、秩k的约束下，达到近似(1-1/e)的收益保证。
- 适合做资源分配、推荐系统等需要高效决策的场景。
研究在矩阵约束下的对抗性带通优化单调子模函数问题。对于包含n个元素、秩为k的矩阵，我们提出一种随机多项式时间算法，每轮仅需一次可行值查询，期望(1-1/e)- regret 为 ×(n^{1/3}k^{2/3}T^{2/3})。这是首个在一般矩阵约束下实现次线性后悔率的对抗性带通子模最大化算法。技术上，我们将问题视为学习泊松基行走的交换策略，将其与上下文带通问题关联，获得信息论意义上的次线性后悔保证；但直接学习指数级策略需指数时间和空间。为此，我们引入平衡分数交换机制，将策略混合压缩为单一分数基，同时保留泊松分析所需的交换信息，从而得到具有相同后悔界且多项式时间的算法。
原文摘要 · Abstract (English)
We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-$k$ matroid on $n$ elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected $(1-1/e)$-regret $\widetilde O(n^{1/3}k^{2/3}T^{2/3})$. This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce \emph{balanced fractional exchanges}, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。