PaperlayerView exact revision on arXiv

Source-linked AI summary

Sum-max Submodular Bandits

Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicolò Cesa-Bianchi

arXiv:2311.05975v1cs.LG

TL;DR

The paper addresses nonstochastic online maximization of submodular rewards when decisions are subsets and feedback reveals only the selected subset’s reward. It introduces sum-max functions and an efficient algorithm based on pseudo-concavity and unbiased gradient estimates, obtaining improved regret guarantees for this class.

  • Problem

    The paper studies sequential subset decisions with monotone submodular rewards under bandit feedback, where only the reward of the chosen subset is observed.

  • Method

    The paper introduces sum-max reward functions and uses pseudo-concavity, expected-reward objectives, and unbiased gradient estimates with online exponentiated gradient ascent.

  • Results

    The efficient MSE3 algorithm achieves the paper’s stated regret guarantee for sum-max functions, with the approximation relationship supplied by submodularity.

  • Takeaways & Limitations

    The approach applies to a broad class of bandit subset-selection problems, including multichannel advertising and facility location, and also handles nonnegative arm costs.

  • Takeaways & Limitations

    The analysis is scoped to sum-max functions and relies on pseudo-concavity; extending comparable guarantees to all monotone submodular functions remains open.

Abstract

from arXiv · show

Many online decision-making problems correspond to maximizing a sequence of submodular functions. In this work, we introduce sum-max functions, a subclass of monotone submodular functions capturing several interesting problems, including best-of-$K$-bandits, combinatorial bandits, and the bandit versions on facility location, $M$-medians, and hitting sets. We show that all functions in this class satisfy a key property that we call pseudo-concavity. This allows us to prove $\big(1 - \frac{1}{e}\big)$-regret bounds for bandit feedback in the nonstochastic setting of the order of $\sqrt{MKT}$ (ignoring log factors), where $T$ is the time horizon and $M$ is a cardinality constraint. This bound, attained by a simple and efficient algorithm, significantly improves on the $\widetilde{O}\big(T^{2/3}\big)$ regret bound for online monotone submodular maximization with bandit feedback.

1 INTRODUCTION

The paper studies nonstochastic online subset decisions with bandit feedback and introduces an efficient algorithm for sum-max reward functions, leveraging pseudo-concavity to obtain improved regret guarantees.

  • 1 INTRODUCTION: Sum-max functions form a subclass of monotone submodular functions covering multichannel advertising, facility location, and related subset-selection problems.They are defined by summing, across matrix rows, the maximum selected entry in each row; symmetric square matrices recover non-metric facility location.
  • 1 INTRODUCTION: Bandit feedback reveals only the reward of the selected subset, while cardinality constraints require each decision to contain at most M elements.When M = 1, the setting reduces to adversarial K-armed bandits.
  • 1 INTRODUCTION: The algorithm extends to nonnegative per-arm costs, where Ψ_t lower-bounds expected profit and captures the trade-off between reward and selecting too many arms.The cost-aware objective differs from Φ_r by a linear function, allowing the preceding methodology to extend to this setting.
  • 1 INTRODUCTION: MSE3 uses repeated draws from a distribution over K arms, unbiased reward-gradient estimates, and online exponentiated gradient ascent.For M = 1 and zero costs, its reward estimator reduces to the standard Exp3 estimator.
  • 1 INTRODUCTION: Pseudo-concavity of the reward function ensures concavity of the expected-reward objective, enabling exponentiated gradient ascent under bandit feedback.The expected reward is represented by Φ_r, and the algorithm competes with any distribution in the simplex.
  • 1 INTRODUCTION: For a uniform distribution over a set S, submodularity yields Φ_r(S) ≥ (1 − α^M)r(S), where α = (|S| − 1)/|S|.This inequality supplies the approximation factor connecting the distributional objective to set-based decisions.

2 SUM-MAX FUNCTIONS

Sum-max functions are matrix-defined monotone submodular objectives that capture several bandit problems. Their pseudo-concavity enables bandit learning and is strictly stronger than monotone submodularity.

  • Definition: Sum-max functions sum, across matrix rows, the maximum entry selected from each row by a subset of columns.They are defined by a nonnegative matrix with K columns and any number of rows.
  • Structure: Sum-max functions are monotone submodular because they are sums of monotone submodular functions.The learner may face a cardinality constraint |A_t| ≤ M when costs are absent.
  • Applications: The class captures multichannel advertising, hitting sets, combinatorial bandits, facility location, and k-medians under bandit feedback.These examples differ in their matrix interpretations and observed reward structure.
  • Pseudo-concavity: Pseudo-concavity requires x^T U_{r,S}x ≤ 0 for zero-sum vectors, where U_{r,S} records pairwise augmented-set rewards.This property is used to analyze learning with bandit feedback.
  • Pseudo-concavity: Every sum-max function is pseudo-concave, while some monotone submodular functions are not, making sum-max a proper subclass.The proof decomposes the function into positive sums of pseudo-concave components.

3 ADDITIONAL RELATED WORK

The paper contrasts its bandit-feedback approach with prior facility-location and linear-submodular work, while distinguishing its multichannel model from stochastic click models.

  • Comparison with prior work: Compared with Pasteris et al. [2021], the paper handles bandit feedback, uses an unbiased gradient estimator, and achieves per-trial O(MK) time with a reward oracle.The prior methodology would require per-trial time exponential in K for general sum-max functions.
  • Comparison with prior work: The algorithm applies to a broader class than sum-max functions and obtains tighter approximation ratios, including optimality for multichannel campaigns.These comparisons are stated relative to the cited facility-location work.
  • Related formulations: Sum-max functions are special cases of linear submodular functions, whose prior study used stochastic assumptions, known component functions, and more informative feedback.The paper instead considers adversarial rewards with bandit feedback.
  • Related formulations: Click-model formulations [Lattimore and Szepesvári, 2020, Lattimore et al., 2018, Kveton et al., 2015] differ because items are ordered and click probabilities depend on position.The multichannel campaign problem does not use that ordered-list structure.

4 MAIN RESULT

The main result develops an efficient bandit algorithm for pseudo-concave, pseudo-submodular rewards under cardinality and cost settings. It provides approximation-regret guarantees while identifying computational limits for improving the factor.

  • Algorithm and setting: MSE3 maintains a probability vector over arms and operates with bandit reward feedback plus observed costs for selected arms.The learner chooses sets of size at most M and observes r_t(A_t) and c_{t,i} for i in A_t.
  • Algorithm and setting: The analysis assumes known reward-range bounds and permits shifting rewards by trial-dependent constants through centered rewards.Rewards are normalized to [−1, 0] after scaling and shifting when necessary.
  • Computational limitation: Improving the approximation factor for multichannel advertising below the stated threshold would yield an efficient randomized set-cover approximation better than ln K.The reduction connects such an improvement to the hardness result of Dinur and Steurer, 2014.
  • Computational limitation: The set-cover consequence is formalized through a polynomial-time reduction with parameters d, s, γ, and a sufficiently large B.The theorem states the resulting algorithm succeeds with a specified probability, though the supplied passage truncates that value.

5 BANDIT FACILITY LOCATION

The facility-location application maximizes sum-max rewards minus positive linear costs without restricting the chosen arm set. The algorithm tunes the subset size and uses dummy arms to control the cost approximation.

  • The facility-location objective is r(A) − γ(A), combining a sum-max reward with a linear, positive cost function and no restriction on A.
  • Choosing a larger M improves the reward approximation ratio but also increases the cost approximation ratio.
  • FLE3 addresses this trade-off by borrowing dummy arms and M tuning from Pasteris et al. [2021].
  • The analysis applies Theorem 4.2 because the facility-location rewards are sum-max and therefore pseudo-concave and submodular.
  • The resulting profit bound combines the dummy-arm contribution with the choice of M.

6 ANALYSIS

The analysis constructs a differentiable expected-reward objective for randomized subset selection, proves concavity under pseudo-concavity, and uses unbiased gradients with exponentiated gradient ascent to bound regret.

  • MSE3 samples M arms independently with replacement from p_t and forms the played set from the sampled sequence.
  • The function Φ_r(q) represents the expected reward of the random set B(q), with a unique subset decomposition supporting its construction.
  • An unbiased gradient estimate can be constructed from the observed reward, enabling online exponentiated gradient ascent on Φ_{r_t}.
  • Pseudo-concavity of r_t is sufficient for Φ_{r_t} to be concave on the simplex, which supports the exponentiated-gradient analysis.
  • Concavity and unbiased gradients relate the update term to expected reward differences, allowing regret comparison with a comparator distribution p_S.
  • With nonzero costs, the analysis replaces Φ_{r_t} with a concave surrogate Ψ_t that lower-bounds expected profit and has an unbiased gradient estimate.

7 EXPERIMENTS

Experiments compare the method with CascadeBandit and Comband across stochastic, corrupted, and adversarial synthetic environments. The method is strongest in the adversarial setting and competitive in the stochastic settings while requiring only M samples per prediction.

  • Experimental setup: The experiments compare against CascadeBandit and Comband for M-sized subsets.
  • Experimental setup: Figure 1 reports cumulative reward over time with 95% confidence intervals computed from 35 runs.
  • Experimental setup: The synthetic environments vary K, M, T, and the probabilities of optimal and suboptimal arms; Figure 1 uses T = 10^5, K = 20, and M = 3.
  • Environments: The stochastic environment assigns reward probability 0.3 to M good actions and 0.1 to the remaining arms.
  • Results: The method outperformed established baselines in the adversarial environment and was on par with them in the two stochastic environments.
  • Results: The approach is described as efficient because each prediction samples M times from a distribution over K actions.

8 FUTURE WORK

The future-work discussion asks whether the regret guarantee extends beyond the identified pseudo-concave subclass and whether pseudo-concavity can be characterized for additional submodular functions.

  • A central open question is whether the reported regret bound can hold for all monotone submodular set functions.
  • The discussion asks whether other classes of submodular functions are pseudo-concave, including budget-additive functions.
  • The standard adversarial bandit problem is identified as a special case, supplying a lower-bound perspective on achievable regret.

A.9 Theorem 4.2

Theorem 4.2 derives the stated guarantee when each r_t is pseudo-concave and pseudo-submodular. Its proof combines concavity of Ψ_t with a sequence of lemmas and substitutions, concluding via η = ln(K)/R.

  • Theorem 4.2 applies when r_t is pseudo-concave and pseudo-submodular for every t ∈ [T].
  • Proof: The proof uses concavity of Ψ_t over Δ_K and Lemma 6.13 to establish the key intermediate inequality.
  • Proof: Conditional expectation rewrites the gain difference as E[(p_S − p_t) · g_t | p_t] = (p_S − p_t) · E[g_t | p_t].
  • Proof: The remaining bound follows by substituting equations (13)–(16) into the preceding inequalities and setting η = ln(K)/R.

B PROOF OF THEOREM 4.3

Theorem 4.3 gives a reduction from a sufficiently strong learner for multichannel advertising to an approximation algorithm for set cover. The construction yields a randomized polynomial-time algorithm achieving approximation ratio at least (1 − ε) ln(B) with probability at least 1/2.

  • Theorem 4.3: With the theorem’s learner assumptions, the reduction produces a randomized polynomial-time set-cover algorithm with approximation ratio at least (1 − ε) ln(B).The guarantee holds with probability at least 1/2 under the stated conditions on B and ε.
  • Reduction: The construction chooses ρ ∈ (1/γ, 1), requires B > 4^1/(ργ−1), and sets M ≥ ρ ln(B)|S|.
  • Reduction: For each trial, β_t is drawn uniformly from [B], and D_t is defined from the set collection so that selected sets intersect D_t.

C SUBMODULAR MONOTONE NON-PSEUDOCONCAVE FUNCTIONS

This section constructs a monotone submodular function that is not pseudo-concave, showing that pseudo-concavity is not implied by monotonicity and submodularity. The construction verifies these properties through controlled marginal gains and an explicit violating vector.

  • The constructed function r is monotone submodular but non-pseudo-concave, providing the claimed counterexample.
  • Construction: For K = 8, the construction defines r over P = 2^[K], beginning with prescribed values for selected subsets and extending them by cardinality.
  • Non-pseudo-concavity: Non-pseudo-concavity is certified using x = (1, 1, 1, 1, −1, −1, −1, −1)^⊤ with ⟨x, 1⟩ = 0 and x^⊤U_r,Sx = 17 − 24α positive for the stated α range.
  • Construction: The extension preserves submodularity because the minimum gain at cardinality i is at least the maximum gain at cardinality i + 1.
  • Construction: The assigned values maintain monotonicity across subset sizes, including the explicitly defined values for cardinalities three through eight.

D EFFICIENT IMPLEMENTATION OF COMBAND

The ComBand implementation samples a fixed-size subset with probability proportional to the product of its positive weights. Dynamic programming computes the required marginal and conditional probabilities, enabling linear-time sampling in m · d under the stated arithmetic assumption.

  • The sampling method selects an m-sized subset with probability proportional to the product of its contained positive numbers.
  • Complexity: The running time is linear in m · d under the assumption that multiplying two numbers takes constant time.
  • Sampling procedure: Dynamic programming computes the needed probabilities and samples indices u_m, u_{m−1}, …, u_1 in reverse order.
  • Dynamic programming: The recurrence derives all required values from the base cases z_1,j = q_j, allowing the conditional probabilities to be computed efficiently.
Loading 2311.05975v1…