Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits

Zongqi Wan; Jialin Zhang; Wei Chen; Xiaoming Sun; Zhijie Zhang

Source-linked AI summary

Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits

Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, Zhijie Zhang

arXiv:2305.12402v1May 21, 2023cs.LGcs.AI

TL;DR

The paper addresses adversarial bandit learning for monotone multi-linear DR-submodular functions and constrained submodular maximization. It introduces BanditMLSM and feasible-action continuous extensions, achieving eO(T 2/3) (1 −1/e)-regret for the core problem and the two targeted combinatorial applications.

Problem
Existing submodular bandit reductions do not provide the desired guarantees for general partition matroid constraints and sequential submodular maximization, while classical continuous extensions require infeasible-set information.
Method
The paper proposes BanditMLSM for monotone multi-linear DR-submodular functions and reduces combinatorial bandits through continuous multi-linear DR-submodular extensions using only feasible-action information.
Results
eO(T 2/3) (1 −1/e)-regret is obtained for BanditMLSM, partition-matroid submodular bandits, and bandit sequential submodular maximization.
Takeaways & Limitations
The continuous reduction yields the first sublinear-regret algorithm for submodular bandits with partition matroid constraints and improves the sequential problem’s approximation ratio to 1 −1/e.
Takeaways & Limitations
The general DR-submodular result assumes ft(0) = 0, while the partition-matroid development assumes a dummy ground-set element with zero marginal gain.

Abstract

from arXiv · show

We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm $\mathtt{BanditMLSM}$ that attains $O(T^{2/3}\log T)$ of $(1-1/e)$-regret. Then we reduce submodular bandit with partition matroid constraint and bandit sequential monotone maximization to the online bandit learning of the monotone multi-linear DR-submodular functions, attaining $O(T^{2/3}\log T)$ of $(1-1/e)$-regret in both problems, which improve the existing results. To the best of our knowledge, we are the first to give a sublinear regret algorithm for the submodular bandit with partition matroid constraint. A special case of this problem is studied by Streeter et al.(2009). They prove a $O(T^{4/5})$ $(1-1/e)$-regret upper bound. For the bandit sequential submodular maximization, the existing work proves an $O(T^{2/3})$ regret with a suboptimal $1/2$ approximation ratio (Niazadeh et al. 2021).

1. Introduction

The paper studies adversarial submodular bandits through continuous multi-linear DR-submodular optimization, addressing limitations of prior reductions and improving regret or approximation guarantees across several settings.

1.1. Bandit Optimization Model: The adversarial model uses bandit feedback, with reward functions selected obliviously before play and the optimizer observing only the played action’s reward.The action set may be finite or infinite, while the optimization model distinguishes finite action sets from structured continuous sets.
1.2. Our Results: eO(T 2/3) (1 −1/e)-regret is achieved for monotone multi-linear DR-submodular bandit maximization by BanditMLSM.The bound hides a log T factor.
1.2. Our Results: BanditDRSM improves general monotone DR-submodular bandit maximization to eO(T 3/4) (1 −1/e)-regret by exploiting smoothness.This result assumes ft(0) = 0 but does not require a downward-closed constraint set.
1.2. Our Results: A continuous multi-linear DR-submodular extension uses only feasible-action information, overcoming the classical extension’s need for values outside the constraint.The classical multi-linear extension cannot provide unbiased estimates under nontrivial constraints because infeasible sets cannot be queried.
1.2. Our Results: Submodular bandit with a partition matroid constraint receives the first sublinear (1 −1/e)-regret algorithm, improving the special assignment case studied by Streeter et al. (2009).The paper also reproduces an eO(T 2/3) (1 −1/e)-regret bound for cardinality constraints.
1.2. Our Results: Bandit Sequential Submodular Maximization improves the prior O(T 2/3) 1/2-regret result to eO(T 2/3) (1 −1/e)-regret.The paper describes 1 −1/e as the tight approximation ratio.

2. Preliminary

The preliminary section introduces self-concordant-barrier RFTL, ellipsoid gradient estimation, and non-oblivious auxiliary functions as tools for bandit DR-submodular optimization.

2.1. Regularized Follow the Leader and Self-Concordant Functions: The local norm induced by the barrier's Hessian is the quantity used to bound estimator-dependent regret.
2.1. Regularized Follow the Leader and Self-Concordant Functions: RFTL with a self-concordant barrier converts unbiased gradient estimates into low-regret decisions over a convex set.
2.2. Ellipsoid Gradient Estimator: An H-smoothed function averages f over an H-transformed unit ball, while the ellipsoid estimator obtains an unbiased gradient estimate from one value query.
2.2. Ellipsoid Gradient Estimator: Choosing H=(∇^2Φ(x))^-1/2 places exploration in a Dikin ellipsoid contained within the feasible set.
2.3. Non-oblivious Techniques for Monotone DR-Submodular Maximization: Non-oblivious optimization replaces the original objective with an auxiliary function whose local optima can have a higher approximation ratio.

3. Bandit Monotone Multi-linear DR-Submodular Maximization

BanditMLSM combines block-based exploitation, self-concordant-barrier RFTL, and ellipsoid estimation to optimize monotone multi-linear DR-submodular functions under bandit feedback.

BanditMLSM uses blocks so it can explore in one round while exploiting the RFTL decision during most remaining rounds.This separation is needed because the exploration sample must be far from the current decision.
The algorithm runs RFTL on auxiliary-function gradients and estimates each block's gradient using one queried function value.
When the sampling scale zq is small, the estimator can become unbounded, so the algorithm modifies the estimator to keep regret controllable.
The block estimator is conditionally unbiased, satisfying E[elq(Hqvq) | Hq−1,vq]=lq(Hqvq).
With η=d^-4T^-2/3 and L=d^-2T^1/3, Theorem 3.3 gives the expected (1−1/e)-regret bound for Algorithm 1.

4. Bandit DR-submodular Maximization

The paper extends its continuous bandit approach beyond multi-linear objectives to general monotone DR-submodular reward functions.

RFTL with a self-concordant barrier and a non-oblivious technique yields an algorithm for general bandit DR-submodular maximization.The online reward functions need not be multi-linear.
Theorem 4.1 states a regret upper bound for any (K,FDS)-bandit instance when K admits a ν-self-concordant barrier.

5. A Continuous Approach for Submodular Full-Bandit

The continuous approach reduces feasible combinatorial full-bandit problems to bandit multi-linear DR-submodular maximization through extension mappings that preserve feasibility and unbiased feedback.

5.1. Reduction Framework: The classical multi-linear extension fails under strict full-bandit feedback because it requires values from infeasible subsets.The paper avoids the relaxed model that permits querying infeasible actions.
5.1. Reduction Framework: The framework maps product-simplex points to distributions over feasible actions, so sampled rewards provide unbiased estimates of the continuous extension.
5.1. Reduction Framework: Under the extension conditions in Lemma 5.1, MLSMWrapper attains expected (1−1/e)-regret.
5.2. Bandit Monotone Submodular Maximization with Partition Matroid Constraint: For partition matroids, EXTPM independently samples simplex coordinates, maps them through ρ, and produces feasible subsets while satisfying Lemma 5.1.
5.3. Bandit Sequential Submodular Maximization: For sequential maximization, EXTSS treats each list position as an independent distribution and induces a distribution over ordered lists.
5.3. Bandit Sequential Submodular Maximization: The sequential extension satisfies the framework conditions, is M|G|-Lipschitz, and supports an expected (1−1/e)-regret algorithm.

6. Conclusion

The paper proposes BanditMLSM and BanditDRSM, then reduces two combinatorial full-bandit problems to multilinear DR-submodular bandits. Technical lemmas establish that averaged and smoothed functions preserve key regularity and DR-submodularity properties.

6. Conclusion: BanditMLSM and BanditDRSM target monotone multilinear and general monotone DR-submodular bandit maximization, respectively.
6. Conclusion: The paper reduces two combinatorial full-bandit submodular maximization problems to multilinear DR-submodular bandits.
6. Conclusion: The paper leaves open whether eO(T^2/3)-type regret is optimal and whether sublinear regret extends beyond partition matroid constraints.The authors conjecture that sublinear regret may not hold for all matroid constraints.
A. Technical Lemmas: Averaged block functions retain Lipschitzness, smoothness, monotonicity, and DR-submodularity under the stated assumptions.
A. Technical Lemmas: H-smoothed functions preserve monotone DR-submodularity and retain the original Lipschitz and smoothness parameters.

B. Missing Proofs in Section 3

This section develops the multilinear estimator and proves the resulting regret bound for BanditMLSM. The analysis uses multilinearity, unbiased estimation, block averaging, and tuned algorithm parameters.

Multilinearity makes each coordinate linear when the others are fixed, enabling the key estimator identity.
The estimator is conditionally unbiased after averaging over the sampled exploration round and auxiliary randomness.
The proof combines the estimator lemmas with the linearity of the auxiliary functions to control regret over blocks.
Theorem 3.3 bounds BanditMLSM’s expected (1−1/e)-regret using η=d^-4T^-2/3, L=d^-2T^1/3, and Q=d^2T^2/3.
The algorithm uses blockwise random exploration with one sampled round per block, random directions, and perturbed plays.

C. Bandit DR-submodular Maximization

BanditDRSM extends the approach to general monotone DR-submodular functions using ellipsoid smoothing, self-concordant regularization, and an improved gradient estimator. Under an added normalization assumption, it achieves a eO(T^3/4) (1−1/e)-regret bound.

The algorithm applies RFTL with a self-concordant regularizer to gradients of ellipsoid-smoothed auxiliary functions.
The ellipsoid perturbation remains feasible through the Dikin ellipsoid and convexity of K.
The smoothed gradient estimator is unbiased and has a bounded dual local norm under the stated Lipschitz and normalization assumptions.
Compared with earlier FKM-based methods, the estimator yields an O(δ^2) additive term instead of the larger O(δ) boundary term.The earlier methods compete with a point in an interior set Kδ, whereas this approach uses the ellipsoid estimator.
BanditDRSM achieves eO(T^3/4) (1−1/e)-regret under the theorem’s parameter settings and barrier assumptions.

D. Self-Concordant Barrier of Product Simplexes

The paper constructs a self-concordant barrier for products of simplexes and supplies missing algorithmic proof material. The barrier’s parameter depends on the dimensions of the component simplexes.

D. Self-Concordant Barrier of Product Simplexes: For a product of n simplexes with dimensions d1,…,dn, the constructed Φ is a Σ_i=1^n(d_i+1)-self-concordant barrier.
D. Self-Concordant Barrier of Product Simplexes: The product-simplex representation concatenates each simplex vector xi=(xi,1,…,xi,di) into the full decision vector.
D. Self-Concordant Barrier of Product Simplexes: The proof verifies differentiability, boundary divergence, convexity, and the self-concordance inequalities for the product-simplex barrier.
D. Self-Concordant Barrier of Product Simplexes: The appendix includes blockwise exploration and feedback steps for the product-simplex algorithm.
E. Missing Proofs in Section 5: The BanditMLSM4PS pseudocode differs from BanditMLSM specifically in lines 9 through 17.

E.1. Proof of Lemma 5.1

Lemma 5.1 establishes that MLSMWrapper can use an unbiased estimator within the extension framework to obtain a (1 −1/e)-regret guarantee.

Estimator construction: The estimator l′q(Hqvq) is unbiased for lq(Hqvq), enabling MLSMWrapper to replace the unavailable function value with observed feedback.The proof explicitly identifies the estimator as unbiased and uses it in the BanditMLSM analysis.
Framework conditions: The extension framework requires K to be a product of standard simplexes and each induced function to be multi-linear, monotone, DR-submodular, Lipschitz, and zero at the origin.These are the structural conditions imposed in Lemma 5.1.
Regret analysis: The cited passages state that MLSMWrapper attains expected (1 − 1/e)-regret while introducing and bounding a new estimator for lq(Hqvq) within the proof.
Comparator correspondence: The reduction maps a comparator x* satisfying EXT(x*) = 1S* to the corresponding discrete reward, so ft(x*) = gt(S*).This connects continuous optimization regret to the original discrete decision problem.

E.2. Proof of Lemma 5.3 and Corollary 5.4

This section verifies that the partition-matroid extension satisfies Lemma 5.1 and therefore yields a continuous reduction with the claimed regret guarantee.

Partition matroid extension: The partition-matroid extension satisfies the conditions of Lemma 5.1, placing its domain K in a dimension d = Σk rk|Gk| space.The extension can represent every feasible set by assigning probability one within selected simplex components.
Multi-linearity: The induced extension is multi-linear because each outcome probability is multi-linear in x, and the expected reward is their linear combination.The proof writes the distribution probability as a product of coordinate terms before taking expectations.
DR-submodularity: The extension is DR-submodular because its mixed partial derivatives are nonpositive, relying on monotone submodularity of the discrete function.The key discrete inequality is the diminishing-returns relation in Lemma E.2.
Regret consequence: Corollary 5.4 transfers Lemma 5.1 to an algorithm for any (SPM, GMS)-bandit with expected (1 −1/e)-regret.The corollary follows directly from the extension properties and the dimension bound.

E.3. Proof of Lemma 5.5 and Corollary 5.6

The sequential extension is shown to satisfy the same structural requirements, allowing the generic reduction to provide a regret guarantee for sequential submodular bandits.

Sequential extension: The sequential extension EXTSS satisfies Lemma 5.1 and uses a |G|2 −|G| dimensional space with an M|G|-Lipschitz induced function.Lemma 5.5 supplies the structural and Lipschitz properties needed for the generic reduction.
Multi-linearity: The induced function is multi-linear because each ordered-list outcome probability is multi-linear in the coordinates x_i,s.The expected reward is expressed as a linear combination of these multi-linear outcome probabilities.
Structural properties: The construction preserves the zero baseline and establishes monotonicity and DR-submodularity through coordinate-wise replacement mappings.The proof analyzes second derivatives across cases involving one or two changed positions.
Regret consequence: Corollary 5.6 gives an algorithm attaining the expected (1 −1/e)-regret on any (SOL, GSS)-bandit.This is obtained by applying Lemma 5.1 to EXTSS.

F. Remark on the Stochastic Submodular Bandit

The adversarial reduction also applies to a stochastic cardinality-constrained model by treating the expected reward function as the online function and using stochastic rewards as unbiased feedback.

Stochastic model: The stochastic model draws reward functions from an unknown distribution and restricts each selected subset to cardinality at most k.The expected function g = E[g′t] is assumed monotone submodular, while individual draws need not be.
Reduction: Cardinality constraints are handled as a special case of partition matroid constraints, with gt = g = E[g′t] treated as the online reward function.This lets the adversarial algorithm be applied to the stochastic setting.
Unbiased feedback: Observed stochastic feedback remains unbiased because E[g′t(St)] = gt(St), so replacing adversarial feedback preserves the gradient-estimator analysis.Independence between action randomness and function randomness is used in the argument.
Regret consequence: The resulting stochastic algorithm has the same regret bound as the adversarial submodular bandit with partition matroid constraint.The section states that the same regret bound follows after substituting the unbiased stochastic observations.