Search papers, labs, and topics across Lattice.
This paper addresses the challenge of adversarial bandit maximization of monotone submodular functions constrained by a matroid, presenting a randomized oracle-polynomial algorithm that achieves expected $(1-1/e)$-regret of $\widetilde O(n^{1/3}k^{2/3}T^{2/3})$ with only one feasible value query per round. This represents the first sublinear-regret algorithm for this problem, significantly advancing the field by connecting it to contextual bandits through the learning of an exchange policy for the Poisson base walk. The authors introduce balanced fractional exchanges to efficiently compress the policy mixture, enabling polynomial time computation while preserving essential exchange information for regret analysis.
Achieving sublinear-regret in adversarial bandit submodular maximization under matroid constraints could redefine optimal strategies in complex decision-making scenarios.
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.
