# Efficient Online Submodular Maximization with Bandit Feedback

DevFeed: [Efficient Online Submodular Maximization with Bandit Feedback](<https://devfeed.tech/articles/efficient-online-submodular-maximization-with-bandit-feedback-125452.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.11808>)

Author: Iasonas Nikolaou, Evimaria Terzi

Published: 2026-11-10T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [thompson sampling](<https://devfeed.tech/topics/thompson-sampling.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approach](<https://devfeed.tech/tags/approach.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [bandit](<https://devfeed.tech/tags/bandit.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [constraint](<https://devfeed.tech/tags/constraint.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [develop](<https://devfeed.tech/tags/develop.md>), [elements](<https://devfeed.tech/tags/elements.md>), [feedback](<https://devfeed.tech/tags/feedback.md>), [first](<https://devfeed.tech/tags/first.md>), [functions](<https://devfeed.tech/tags/functions.md>), [horizon](<https://devfeed.tech/tags/horizon.md>), [knowledge](<https://devfeed.tech/tags/knowledge.md>), [learner](<https://devfeed.tech/tags/learner.md>), [linear](<https://devfeed.tech/tags/linear.md>), [log](<https://devfeed.tech/tags/log.md>), [online](<https://devfeed.tech/tags/online.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [with](<https://devfeed.tech/tags/with.md>)

## AI overview

The proposed algorithm achieves expected (1−1/e)-regret of O(k√(nT log(n/k))) for online monotone submodular maximization with a cardinality limit and bandit feedback: each round, it selects at most k of n elements and sees only the chosen set's value. The authors describe it as efficient and polynomial-time, with √T dependence on the horizon, and, to their knowledge, the first such guarantee for arbitrary monotone submodular functions in this setting. Their method uses randomized sampling and a potential function to reduce the problem to online linear optimization over the probability simplex.

## Source excerpt

arXiv:2611.11808v1 Announce Type: new Abstract: We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most $k$ elements from a ground set of size $n$ and observes only the value of the selected set. We develop an efficient algorithm achieving $O\!\left(k\sqrt{nT\log(n/k)}\right)$ expected $(1-1/e)$-regret over $T$ rounds. To our knowledge, this is the first polynomial-time algorithm with $\sqrt{T}$ dependence on the horizon for arbitrary monotone submodular functions in the bandit setting. Our approach uses randomized sampling and a carefully constructed potential to reduce online submodular maximization to online linear optimization over the probability simplex.