PaperlayerView exact revision on arXiv

Source-linked AI summary

Combinatorial Multi-Armed Bandit with General Reward Functions

Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, Pinyan Lu

arXiv:1610.06603v4cs.LGcs.DSstat.ML

TL;DR

The paper addresses CMAB problems where expected rewards depend on full outcome distributions rather than only means. It proposes SDCB for distributional learning, obtains logarithmic distribution-dependent and near-square-root distribution-independent regret, and applies the framework to K-MAX and EUM.

  • Problem

    Existing CMAB methods mainly estimate arm means, but nonlinear rewards such as max() and utility functions can depend on entire outcome distributions.

  • Method

    SDCB estimates arm outcome distributions through cumulative distribution functions and uses stochastically dominant confidence bounds, with offline optimization supplied through an oracle.

  • Results

    The framework achieves O(log T) distribution-dependent regret and ˜O(√T) distribution-independent regret, and provides a first PTAS for offline K-MAX.

  • Takeaways & Limitations

    The framework extends online combinatorial bandit learning to arbitrary bounded outcome distributions and supports K-MAX and expected utility maximization applications.

  • Takeaways & Limitations

    The main SDCB implementation can require Θ(T) space and Θ(T^2) running time over T rounds, excluding the offline computation oracle.

Abstract

from arXiv · show

In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the $\max()$ function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve $O(\log{T})$ distribution-dependent regret and $\tilde{O}(\sqrt{T})$ distribution-independent regret, where $T$ is the time horizon. We apply our results to the $K$-MAX problem and expected utility maximization problems. In particular, for $K$-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first $\tilde{O}(\sqrt T)$ bound on the $(1-ε)$-approximation regret of its online problem, for any $ε>0$.

1 Introduction

The paper extends CMAB to reward functions whose expected value depends on full outcome distributions, then develops SDCB and applies it to K-MAX and EUM.

  • Motivation: CMAB applications select combinatorial super arms and observe selected-arm outcomes, but common methods mainly address linear rewards or rewards determined by arm means.This leaves distribution-dependent objectives outside the usual framework.
  • General framework: The paper generalizes CMAB to arbitrary outcome distributions and reward functions whose expectations may depend on entire input distributions.The framework targets nonlinear rewards such as max() and utility functions.
  • Method: SDCB estimates each arm’s cumulative distribution function and constructs stochastically dominant confidence bounds for learning.The method replaces mean-only estimation with distributional estimation.
  • Algorithms: Lazy-SDCB improves computational efficiency by discretizing the problem before applying SDCB while retaining ˜O(√T) distribution-independent regret bounds.The Lipschitz-continuity assumption is specific to Lazy-SDCB.
  • Applications: The applications include EUM problems and a first PTAS for offline K-MAX, which maximizes expected maximum reward under a cardinality constraint.The framework can integrate an offline stochastic optimization algorithm as an oracle.

2 Setup and Notation

The paper formalizes CMAB instances with stochastic base-arm outcomes, feasible super arms, and general rewards, while removing the restriction that expected rewards depend only on means.

  • Problem Formulation: A CMAB instance consists of base arms, feasible super arms, an outcome distribution, and a reward function over outcomes and selected super arms.The maximum super-arm size is denoted K.
  • Interaction model: Each round selects a super arm, reveals outcomes from its constituent arms, and receives the corresponding reward; expected reward is defined by averaging over the outcome distribution.The reward for a super arm depends only on its revealed outcomes.
  • Objectives: The learning objective is to maximize expected cumulative reward over T rounds, with regret measured against repeatedly choosing the optimal super arm when the distribution is known.Approximation regret is used when exact optimization is computationally hard.
  • Motivation: The paper removes the usual assumption that expected super-arm rewards depend only on the vector of arm means.This enables general nonlinear reward functions and distribution-sensitive objectives.
  • Assumptions: The analysis assumes mutually independent arm outcomes, bounded rewards, and monotone reward functions.An α-approximation computation oracle is required for finite-support distributions.

3 SDCB Algorithm

SDCB estimates each arm’s outcome distribution and constructs a stochastically dominant confidence bound, then uses an approximation oracle to select super arms. Under the stated assumptions, it achieves logarithmic distribution-dependent and near-square-root distribution-independent regret.

  • Algorithm: SDCB maintains empirical distributions for observed arm outcomes and uses their CDFs to construct distribution-level confidence bounds.The algorithm initializes arm observations, updates empirical distributions after each played super arm, and lowers empirical CDFs to obtain optimistic distributions.
  • Algorithm: The algorithm calls an α-approximation oracle on the constructed optimistic distribution and then observes and updates every arm in the selected super arm.This combines optimistic distribution estimation with offline approximate optimization.
  • Optimism: With high probability, the constructed distributions stochastically dominate the true arm distributions, yielding optimistic expected rewards through reward monotonicity.The analysis uses first-order stochastic dominance and the monotonicity assumption on the reward function.
  • Regret Bounds: SDCB achieves O(log T) distribution-dependent and O(√(T log T)) distribution-independent regret bounds.The proof reduces the general-reward analysis to a summation-reward analysis and uses the Dvoretzky–Kiefer–Wolfowitz inequality for uniform empirical-CDF concentration.
  • Relation to CUCB: When expected rewards depend only on arm means, SDCB achieves the same regret bounds as CUCB without requiring the three assumptions used for nonlinear rewards.Its confidence-bound expectations lie within the same interval length as CUCB with high probability.

4 Improved SDCB Algorithm by Discretization

The section improves SDCB by discretizing continuous outcomes, reducing computational overhead while preserving distribution-independent regret guarantees under a Lipschitz reward assumption.

  • Motivation: Θ(T) space and Θ(T^2) time make original SDCB costly when empirical CDFs contain many distinct observations.This occurs, for example, when an arm’s outcome distribution is continuous.
  • Improved SDCB Algorithm by Discretization: O(s) per-round operations from discretization reduce Lazy-SDCB’s total time and space usage to the stated subquadratic bounds.Lazy-SDCB replaces arbitrary outcomes with counts over an equally spaced support before applying SDCB.
  • Assumptions: The discretized method requires bounded, monotone, Lipschitz-continuous rewards, with Lipschitz continuity used specifically by Lazy-SDCB.The discretization error is bounded through the Lipschitz condition.
  • Discretization: The horizon-dependent discretization uses s equally spaced support values and can be made horizon-free through the doubling trick.Algorithm 3 invokes the known-horizon procedure over geometrically increasing horizons.
  • Regret Bounds: O(√(T log T)) distribution-independent regret bounds hold for both known-horizon and doubling-trick variants.The known-horizon algorithm uses discretization, while the horizon-free version uses the doubling trick.

5 Applications

The framework applies to K-MAX and expected utility maximization, yielding a PTAS for offline K-MAX and improved online regret guarantees for K-MAX.

  • K-MAX: K-MAX combines at most K selected arms with a maximum-outcome reward, satisfying the framework’s stated reward assumptions with M = C = 1.The offline problem is computationally hard to solve exactly, motivating approximation algorithms.
  • K-MAX: A polynomial-time (1 − ε)-approximation algorithm exists for offline K-MAX for every constant ε > 0.The result applies to selecting at most K independent arms under the cardinality constraint.
  • K-MAX: SDCB gives K-MAX O(log T) distribution-dependent and tilde-O(√T) distribution-independent regret bounds, while Lazy-SDCB gives the corresponding discretized guarantees.The PTAS also enables a tilde-O(√T) bound for (1 − ε)-approximation regret for any constant ε > 0.
  • Expected Utility Maximization: Expected utility maximization uses rewards of the form u(product of selected outcomes), where nonlinear utility may depend on full distributions rather than arm means.Nonlinear utility functions model risk-averse or risk-prone behavior, while linear utility corresponds to risk neutrality.
  • Expected Utility Maximization: The framework can incorporate offline stochastic optimization algorithms as approximation oracles for online applications.Prior PTAS results for several utility functions and feasibility constraints provide examples of such offline components.

A.1 Proof of Theorem 1

The proof establishes technical properties of distribution-based confidence bounds using L1 distance, stochastic dominance, and the DKW inequality. These tools support the regret analysis of SDCB.

  • A.1. Proof of Theorem 1: The proof combines L1-distance properties, DKW concentration, and technical lemmas to establish Theorem 1.The proof is organized into four steps: reviewing L1 distance, stating DKW concentration, proving technical lemmas, and completing the theorem.
  • A.1. Proof of Theorem 1: CDF confidence errors are controlled uniformly over x using the DKW inequality, enabling high-probability bounds on the confidence-adjusted distributions.The analysis separates accurate and inaccurate empirical-CDF events and bounds their contributions to regret.
  • A.1. Proof of Theorem 1: Stochastic dominance implies that increasing an arm distribution increases expected reward under the reward function’s monotonicity assumption.The proof first establishes rP′(S) ≥ rP(S) under coordinatewise stochastic dominance, then bounds the effect of CDF deviations.
  • A.1. Proof of Theorem 1: SDCB estimates each arm’s distribution with an empirical CDF and uses confidence-adjusted distributions as oracle inputs.The algorithm maintains observation counts and empirical distributions, then constructs stochastically dominant confidence bounds.

A.1.4 Finishing the Proof of Theorem 1

The proof finishes Theorem 1 by counting rounds in which SDCB selects substantially suboptimal super arms. It derives both distribution-dependent and distribution-independent regret bounds.

  • A.1.4 Finishing the Proof of Theorem 1: The proof defines decreasing confidence and counting sequences to control how often insufficiently observed arms can influence SDCB’s choices.The sequences αk and βk determine the auxiliary events used in the counting argument.
  • A.1.4 Finishing the Proof of Theorem 1: The distribution-dependent regret proof is completed by combining the event-based regret lemma with the counting argument.Lemma 5 links a regret-causing event Ht to one of the auxiliary events Gk,t, after which the bad-arm counts are bounded.
  • A.1.4 Finishing the Proof of Theorem 1: The distribution-independent bound follows by decomposing regret at a threshold ε and applying the same bad-event analysis only when the gap exceeds ε.The proof combines this decomposition with Lemma 4 to conclude the distribution-independent result.
  • A.1.4 Finishing the Proof of Theorem 1: The comparison algorithm CUCB estimates means and passes their upper confidence bounds to an offline oracle, whereas SDCB maintains distributional information.The CUCB description provides the mean-based baseline used for contrast in the proof and algorithm analysis.

A.2 Analysis of Our Algorithm in the Previous CMAB Framework

In the mean-dependent CMAB setting, SDCB’s distributional confidence construction also yields a valid mean upper confidence bound. Consequently, the existing CUCB regret analysis applies unchanged.

  • A.2 Analysis of Our Algorithm in the Previous CMAB Framework: The analysis does not require independence among all arm outcome distributions in this previous CMAB framework.The arm-specific distributions are treated as marginals of the joint distribution when independence is absent.
  • A.2 Analysis of Our Algorithm in the Previous CMAB Framework: CUCB maintains empirical means and counts, constructs a UCB vector, and sends that vector to the offline computation oracle.SDCB can be viewed as supplying analogous mean inputs through confidence-adjusted distributions.
  • A.2 Analysis of Our Algorithm in the Previous CMAB Framework: The proof uses DKW concentration and stochastic-dominance properties to show that SDCB’s oracle input upper-bounds the true arm means with high probability.The argument compares the empirical-CDF confidence distribution with the true distribution and then applies the mean consequences of stochastic dominance.
  • A.2 Analysis of Our Algorithm in the Previous CMAB Framework: SDCB achieves exactly the same regret bounds as CUCB when expected rewards depend only on arm means.The proof shows that the mean of each confidence-adjusted distribution is a UCB for the corresponding arm mean with the same confidence level.

B Missing Proofs from Section 4

These proofs bound discretization error for Lipschitz reward functions and analyze the offline K-MAX approximation. The K-MAX reward is computable in polynomial time and admits a (1 − 1/e)-approximate greedy solution.

  • Missing proofs from Section 4: Lipschitz continuity bounds the error from replacing continuous arm distributions with discretized finite-support distributions.The proof applies the one-dimensional discretization bound inductively across coordinates and then to the reward function.
  • Missing proofs from Section 4: The discretized distribution assigns each arm’s mass in interval Ij to the representative value j/s.This construction converts arbitrary distributions into finite-support distributions suitable for the finite-support analysis.
  • Missing proofs from Section 4: Theorem 2’s regret analysis combines the discretization-error bound with Theorem 1’s distribution-independent regret bound.The proof compares the optimal super arms under the original and discretized distributions before applying the online bound.
  • Missing proofs from Section 4: For K-MAX, the expected maximum of any selected subset can be computed in polynomial time from the independent arm distributions.The calculation enumerates possible maximum values and uses independence to compute their probabilities.

C.1 (1 −1/e)-Approximation

The paper establishes a (1 −1/e)-approximation for K-MAX through monotone submodularity, then builds a discretization-and-signature framework toward a PTAS.

  • C.1 (1 −1/e)-Approximation: A greedy algorithm achieves a (1 −1/e)-approximation because the expected maximum reward is monotone and submodular.The argument shows each fixed-outcome maximum function is monotone and submodular, and their convex combination preserves both properties.
  • C.1 (1 −1/e)-Approximation: The K-MAX PTAS first discretizes each random variable onto a support of size O(1/ε^2), then represents the discretized variables through Bernoulli decompositions.The discretization uses the greedy solution to define W and rounds or truncates Bernoulli components relative to W/ε.
  • C.1 (1 −1/e)-Approximation: Signatures aggregate discretized Bernoulli probabilities, and sets with identical signatures have objective values differing by at most O(ε)W.This lets the algorithm compare sets through a finite signature representation rather than their full distributions.
  • C.1 (1 −1/e)-Approximation: The algorithm enumerates polynomially many signatures and selects the best feasible cardinality-K set, yielding a polynomial-time approximation scheme for fixed ε.The stated running time is polynomial for fixed ε, with feasibility checked through dynamic programming.

C.2.3 Enumerating Signatures

The signature-enumeration algorithm searches a polynomial-size signature space, uses dynamic programming to test feasibility, and inherits the PTAS guarantee from the signature approximation bound.

  • C.2.3 Enumerating Signatures: The algorithm enumerates every signature vector, finds feasible size-K sets matching each signature, and returns the candidate with maximum expected reward.Feasibility is tested by a dynamic program over variables, selected-set size, and dominated signature vectors.
  • C.2.3 Enumerating Signatures: The optimal set’s signature is included in the enumeration, so the returned solution achieves at least (1 −O(ε))OPT.The argument combines the signature-value approximation with the greedy lower bound W ≥ (1 −1/e)OPT.
  • C.2.3 Enumerating Signatures: For fixed ε, the number of signatures and the dynamic-programming work per signature are polynomial, establishing the PTAS running-time claim.The result applies when signature-feasibility checking can be performed in polynomial time.

D Empirical Comparison between the SDCB Algorithm and Online Submodular Maximization on the K-MAX Problem

Experiments compare SDCB or Lazy-SDCB with an online submodular maximization algorithm on four K-MAX distributions. The proposed algorithms achieve much lower regret in all examples.

  • D Empirical Comparison between the SDCB Algorithm and Online Submodular Maximization on the K-MAX Problem: The baseline Algorithm 8 uses K copies of Exp3 and has an O(K√(mT log m)) upper bound on (1 −1/e)-approximation regret for K-MAX.The experiment compares SDCB/Lazy-SDCB against this online submodular maximization method.
  • D Empirical Comparison between the SDCB Algorithm and Online Submodular Maximization on the K-MAX Problem: The setup uses m = 9 arms, selects at most K = 3 arms per round, and evaluates four distributions whose difficulty varies with the separation of arm distributions.Distribution 2 is described as hard because suboptimal-arm distributions are close to those of the optimal arms.
  • D Empirical Comparison between the SDCB Algorithm and Online Submodular Maximization on the K-MAX Problem: The proposed algorithms achieve much lower regret than online submodular maximization in all four K-MAX examples.Figure 1 reports regrets averaged over 20 independent runs.
  • D Empirical Comparison between the SDCB Algorithm and Online Submodular Maximization on the K-MAX Problem: SDCB is used for distributions 1–3, while Lazy-SDCB with known time horizon is used for distribution 4.The plotted metric is 1-approximation regret rather than (1 −1/e)-approximation regret because the greedy oracle usually performs better than its guarantee.
Loading 1610.06603v4…