Source-linked AI summary
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Zongqi Wan, Zhijie Zhang
TL;DR
The paper studies adversarial bandit maximization of monotone submodular functions under general matroid constraints, where only one feasible set value is observed per round. It learns exchange policies through the Poisson base walk and compresses their mixture into balanced fractional exchanges, yielding a polynomial-time algorithm with expected (1-1/e)-regret \widetilde O(n^{1/3}k^{2/3}T^{2/3}).
Problem
Adversarial bandit submodular maximization under general matroid constraints lacks a sublinear-regret algorithm using only one feasible value query per round.
Method
The paper views the problem as learning state-dependent exchange policies for the Poisson base walk and compresses their exponentially large mixture into a fractional base using balanced fractional exchanges.
Results
\widetilde O(n^{1/3}k^{2/3}T^{2/3}) expected (1-1/e)-regret is achieved by a randomized oracle-polynomial algorithm making exactly one feasible value query per round.
Takeaways & Limitations
Balanced fractional exchanges retain the exchange marginals needed for the Poisson analysis while avoiding the exponential time and space required to learn all policies directly.
Takeaways & Limitations
The analysis assumes an oblivious adversary and conditions on each round's reward function being fixed before fresh learner randomization while remaining unobserved.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses adversarial bandit maximization of monotone submodular functions when every queried set must satisfy a general matroid constraint. It develops a polynomial-time approach based on learning and compressing exchange policies for a Poisson base walk, obtaining sublinear (1 −1/e)-regret.
- Motivation: General matroid constraints create a strict feasible-query obstacle because exploratory sets used for estimation must also be independent.Existing offline methods may query infeasible auxiliary subsets, but the bandit action is precisely the queried set.
- Motivation: The paper asks whether polynomial-time bandit algorithms can achieve sublinear (1 −1/e)-regret under general matroid constraints.It answers affirmatively and thereby disproves the conjecture of Wan et al. (2023).
- Approach: The online formulation treats the current Poisson-walk base as context, a feasible exchange as action, and each comparator base as a state-dependent exchange policy.Directly learning the exponentially many policies gives only an information-theoretic guarantee because it requires exponential time and space.
- Approach: Balanced fractional exchanges compress the policy mixture into a fractional base while preserving the exchange marginals needed by the Poisson analysis.This produces a polynomial-time algorithm for arbitrary monotone submodular objectives and arbitrary matroids without a product decomposition or concave-relaxation assumption.
- Main result: The main theorem gives a randomized oracle-polynomial algorithm using exactly one feasible value query per round and achieving expected sublinear (1 −1/e)-regret.The paper identifies this as the first polynomial-time sublinear (1 −1/e)-regret guarantee in the strict feasible-query model for general matroids.
- Approach: The Poisson-process method maintains feasibility through single-element exchanges, making it suitable for the strict feasible-query setting.Its local improvement conditions yield a differential inequality whose integration gives the 1−1/e approximation guarantee.
2 Preliminaries
This section defines the submodular, matroid, multilinear-extension, and Poisson-walk preliminaries used later. The bandit protocol restricts each played set to feasible independent sets and reveals only its scalar reward.
- Submodular functions: A normalized monotone function has diminishing returns when adding an element to a larger set yields no greater marginal value.The section formalizes monotonicity and submodularity for set functions on a finite ground set.
- Matroids: A rank-k matroid consists of independent sets whose bases support feasible single-element exchanges.For a base A, E(A) contains pairs (i,j) such that A − i + j remains a base, including self-loops.
- Matroids: Brualdi’s theorem supplies a bijection between any two bases that maps each element of one base to a feasible exchange target in the other.The bijection can fix every element shared by the two bases.
- Bandit protocol: In the strict feasible-query bandit protocol, the learner chooses an independent set before observing the reward function and then sees only its scalar value.Because rewards are monotone and every independent set extends to a base, the protocol can focus on feasible bases.
- Multilinear extension: The multilinear extension evaluates a set function on independently sampled elements, enabling continuous analysis of submodular objectives.Its derivatives are independent of their own coordinates and nonincreasing in the other coordinates.
- Poisson base walk: The Poisson base walk samples event times with intensity λ(s) = k/s and applies feasible exchanges from a current base.The algorithm input includes a matroid, starting base, starting time, and exchange distributions supported on feasible exchanges.
3 Poisson Base Walk with General Exchange Distribution
The generalized Poisson base walk evolves a feasible base through random single-element exchanges, while its analysis expresses terminal approximation through cumulative discounted exchange deficits. This formulation isolates the loss caused when online exchanges cannot depend on the current objective.
- Bandit limitation: The bandit learner cannot generally satisfy the local exchange condition because it selects exchanges before observing the current reward function.The analysis therefore bounds terminal value when expected exchange gain falls below the ideal condition.
- Poisson base walk: The Poisson base walk runs a nonhomogeneous process of intensity k/s and updates the current base using exchange distributions supported on feasible exchanges.Each event samples one feasible exchange and updates the simulated base trajectory.
- Poisson base walk: Every state remains a base, so the walk requires no rounding and has expected exchange count k log(1/ε).The event count can be sampled directly conditional on the total number of events.
- Objective-dependent exchange rule: The GKSS specialization chooses exchanges from a maximum-weight base using a Brualdi bijection and satisfies the exchange condition at every event.This objective-dependent rule is crucial for obtaining the 1 − 1/e approximation factor.
- Deficit analysis: Theorem 3.5 represents the approximation loss through a cumulative sum of discounted deficits associated with the Poisson events.The event-sum identity converts the expected jump contribution into an integral by canceling the factor s with the intensity k/s.
- Deficit analysis: When the exchange rule satisfies the objective-dependent condition, the cumulative deficit is nonpositive; general exchange distributions retain it explicitly as the source of approximation degradation.As ε decreases to zero, the ideal coefficient tends to 1 − 1/e.
4 Balanced Fractional Exchanges
Balanced fractional exchanges compress a mixture of comparator-specific exchange policies into a fractional base while preserving the marginals required by the Poisson analysis. They exist for every base and fractional base and admit an oracle-polynomial transportation implementation.
- Motivation: The Poisson analysis needs only uniform deletion and fractional insertion marginals, not the identities of the exponentially many comparator policies.These marginals can be represented by a single point in the matroid base polytope.
- Definition: A balanced fractional exchange is a nonnegative exchange matrix from a base A whose row sums are uniform and whose column sums equal a fractional base x.Its support is restricted to feasible exchanges.
- Exchange distribution: The exchange matrix induces a feasible-exchange distribution because its row and column sums both have total mass k.The resulting distribution has the prescribed deletion and insertion marginals.
- Existence: For every base A and fractional base x, a balanced fractional exchange exists.The proof decomposes x into bases and combines Brualdi bijections for those bases.
- Polynomial implementation: A transportation flow computes the balanced exchange using a bipartite graph with k + n nonterminal vertices and at most kn edges.The support graph requires at most kn independence-oracle calls.
- Compression: Comparator vertices recover exact Brualdi identities, while arbitrary fractional bases interpolate them without explicitly representing a distribution over bases.This exposes a polynomial-dimensional decision variable while preserving the same local benchmark.
5 The Balanced-Exchange Bandit Algorithm
The algorithm runs a Poisson base walk using balanced exchange distributions induced by a fractional base, estimates linearized insertion losses with one feasible query, and updates via entropy projection. Its analysis controls Poisson deficits and estimator variance while preserving feasibility and coordinate positivity.
- Algorithm: The algorithm runs a Poisson base walk using the balanced exchange distribution induced by the current fractional base x_t.The balanced matrix converts x_t into feasible exchanges whose deleted element is uniform on the current base and whose inserted-element marginal is x_t/k.
- Algorithm: Balanced exchanges linearize the expected Poisson exchange gain as a linear loss over the matroid base polytope.The resulting loss vector is indexed by inserted elements and its inner product with x_t − 1_O controls the local deficit relative to comparator base O.
- Online update: The shrinkage set K_δ keeps every coordinate at least δ/n, enabling bounded importance weights and a feasible comparator representative.The algorithm contracts the base polytope toward a strictly positive point and uses negative-entropy mirror descent with exact projection back to K_δ.
- Online update: Entropy’s stability analysis exploits cancellation between the insertion marginal x_t,j/k and the estimator’s inverse probability, yielding variance dependence on n/k.The projection simultaneously restores the matroid base constraints and uniform positivity after each update.
- Bandit feedback: The bandit estimator uses one feasible query and is conditionally unbiased for the local loss while remaining bounded and having controlled weighted second moment.A leave-one-out feasible set and a fair coin produce observations with conditional mean 1 − I_f(A,τ;i,j); the estimator is nonnegative and bounded by two.
- Guarantees: Theorem 5.11 analyzes the capped implementation under ε = 1/T and μ = k log T when n(μ^2 + μ) log(en) < T, while Lemma 5.6 establishes conditional unbiasedness.The cap makes the number of transportation flows worst-case polynomial; overflow analysis bounds the discrepancy from the uncapped Poisson trajectory.
A Sampling the Nonhomogeneous Poisson Process
The appendix samples a nonhomogeneous Poisson process with intensity k/s by first sampling its event count and then sampling event times conditionally as order statistics. A transformed uniform variable provides the required event-time density.
- Process law: The process has intensity λ(s) = k/s on [ε,1], so its integrated intensity over [a,b] is k log(b/a).The total count on [ε,1] is therefore Poisson with mean k log(1/ε).
- Conditional sampling: Conditional on M = m, the unordered event times are independent with density proportional to λ/μ, and the ordered times are their order statistics.This conditional representation is the sampling rule used for the event times.
- Conditional sampling: If U is uniform on [0,1], the transformation S = ε^(1−U) has the appendix’s event-time density.Differentiation gives density 1/(s log(1/ε)).
- Derivation: The joint density of exactly m ordered events is derived by partitioning the interval into small cells around event times and taking a limiting product of Poisson probabilities.Integrating this density over the ordered simplex gives the count probability and supports the conditional event-time law.