PaperlayerView exact revision on arXiv

Source-linked AI summary

Combinatorial Sleeping Bandits with Fairness Constraints

Fengjiao Li, Jia Liu, Bo Ji

arXiv:1901.04891v3cs.LGcs.PFstat.ML

TL;DR

The paper asks how bandits can jointly support combinatorial play, sleeping arms, and per-arm fairness under unknown rewards. It proposes CSMAB-F and the LFG algorithm, combining UCB with virtual queues. LFG is proved feasibility-optimal with a stated regret upper bound, while simulations show that tuning η trades lower regret against slower fairness convergence.

  • Problem

    Basic MAB omits simultaneous arm selection and sleeping arms, while practical systems also require minimum selection fractions for individual-arm fairness.

  • Method

    The paper combines an extended UCB method for exploration–exploitation with virtual queues to enforce fairness in the CSMAB-F model.

  • Results

    LFG is proved feasibility-optimal with a time-average regret upper bound, and simulations show effective fairness and good regret performance.

  • Takeaways & Limitations

    The simulations identify a tunable tradeoff: larger η lowers regret but slows convergence toward satisfying the fairness constraints.

Abstract

from arXiv · show

The multi-armed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many real-world applications, where multiple arms can be simultaneously played and an arm could sometimes be "sleeping". Besides, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMAB-F, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, UCB, to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by $\frac{N}{2η}+\frac{β_1\sqrt{mNT\log{T}}+β_2 N}{T}$, where N is the total number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, $β_1$ and $β_2$ are constants, and $η$ is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.

I. INTRODUCTION

The paper introduces CSMAB-F, a unified bandit model combining simultaneous arm selection, random arm unavailability, and minimum selection-fraction fairness constraints. It develops LFG by integrating UCB exploration with virtual queues, proving feasibility-optimality and a regret upper bound, while simulations expose a regret–fairness-convergence tradeoff.

  • Model and motivation: The framework addresses a gap left by basic MAB models, which select one action per round and omit simultaneous actions, unavailability, and fairness.The paper identifies this combination as previously unified in no prior work, to the authors’ knowledge.
  • Model and motivation: CSMAB-F models multiple simultaneously playable arms, sleeping arms whose availability is revealed each round, and minimum selection fractions for individual arms.The player selects at most m available arms and receives a weighted compound reward.
  • Model and motivation: Fairness creates a second decision dilemma alongside exploration versus exploitation: maximizing reward while satisfying each arm’s long-term selection requirement.The paper notes that standard MAB algorithms handle exploration–exploitation but were not designed for these fairness constraints.
  • Algorithm and analysis: LFG combines an extended UCB algorithm for learning and exploration with virtual queues for handling fairness constraints.The algorithm is designed for the CSMAB-F problem.
  • Algorithm and analysis: LFG is proved feasibility-optimal and is given a time-average regret upper bound involving N, m, T, constants β1 and β2, and tunable parameter η.The supplied passage introduces the bound but does not contain its complete displayed expression.
  • Evaluation: Simulations find that LFG can satisfy fairness with good regret, while tuning η controls a tradeoff between regret and convergence speed.Larger η reduces regret in the reported experiments, but convergence to the fairness requirement slows as η increases.

IV. THE LFG ALGORITHM

LFG integrates UCB-based exploration with virtual queues to maximize reward while satisfying per-arm fairness constraints in the CSMAB-F setting. Its tunable parameter η controls the balance between reward priority and fairness convergence, while linear rewards enable efficient super-arm selection.

  • Algorithm design: LFG combines an extended UCB policy with virtual queues to jointly address unknown rewards and per-arm fairness constraints.UCB handles the exploitation–exploration tradeoff, while virtual queues track each arm’s selection debt.
  • Algorithm design: The UCB estimate uses observed sample means and an exploration bonus, is capped at 1, and equals 1 for arms never previously played.The cap reflects rewards bounded in [0, 1].
  • Algorithm design: Each virtual queue records an arm’s fairness debt: debt increases by its minimum selection fraction and decreases when the arm is selected.Queue lengths are initialized at zero and updated using prior decisions and feedback.
  • Action selection: At each round, LFG observes available arms and selects a super arm using a linear combination of UCB estimates and virtual-queue lengths.Although the super-arm action space can be exponential in m, linear compound rewards permit iterative selection of the best individual arms.
  • Parameter tradeoff: η tunes the reward–fairness tradeoff: larger values prioritize estimated reward, whereas smaller values prioritize arms with larger fairness debt.Simulations show that this choice trades off regret against the speed of convergence to fairness.
  • Scope: The approach relies on linear rewards; with more general nonlinear rewards such as submodular rewards, the known-reward offline problem may become NP-hard and efficient fair learning remains unclear.The paper leaves this nonlinear-reward setting for future work.

V. MAIN RESULTS

The paper analyzes LFG’s performance for CSMAB-F by establishing feasibility-optimality and deriving a finite-horizon upper bound on time-average regret.

  • Main results: The performance analysis proves that LFG is feasibility-optimal and derives an upper bound on time-average regret.The two results are developed in separate subsections covering fairness feasibility and regret.

A. Feasibility Optimality

LFG satisfies feasible long-term per-arm fairness requirements and admits a finite-horizon regret bound. The bound separates fairness and learning costs, exposing a tunable regret–convergence tradeoff.

  • Feasibility Optimality: LFG is feasibility-optimal: it satisfies any minimum selection fraction vector strictly inside the maximal feasibility region C.The proof uses strong stability of the virtual queue system, which implies mean-rate stability and therefore fairness feasibility.
  • Feasibility Optimality: The virtual queue system is strongly stable under LFG whenever the required minimum selection fractions are strictly inside C.Strong stability is the sufficient condition used to establish long-term satisfaction of the fairness constraints.
  • Comparison: Unlike prior minimum-guarantee work cited by the authors, LFG satisfies feasible long-term per-arm fairness constraints rather than permitting violations bounded by O(T^5/6).The cited prior work concerns total rewards and does not consider sleeping bandits.
  • Upper Bound on Regret: Theorem 2 gives a time-average regret upper bound uniformly for every finite horizon T, rather than only asymptotically.The bound is stated for the regret defined in the paper’s formulation.
  • Upper Bound on Regret: The regret bound separates the fairness-constraint impact from the uncertainty-driven learning and exploration cost.The first term reflects fairness, while the second term corresponds to typical MAB learning regret and is instance-independent.
  • Upper Bound on Regret: A smaller η increases the fairness-related regret term but accelerates fairness convergence, whereas a larger η lowers that term but delays convergence.The same tradeoff appears in the simulation results.

VI. APPLICATIONS

CSMAB-F is illustrated through real-time traffic scheduling, online ad placement, and crowdsourcing task assignment, each combining unknown rewards with application-specific availability or fairness requirements. Simulations compare algorithm performance using regret and arm-selection fractions.

  • Scheduling of real-time traffic: CSMAB-F models real-time traffic scheduling with unavailable clients, at most one transmission per slot, and minimum delivery-ratio guarantees.The AP maximizes cumulative utilities under unknown mean utilities while meeting each client's QoS requirement.
  • Ad placement in online advertising systems: Online ad placement selects no more than m ads from N candidates despite context-dependent availability and unknown click-through rates.The publisher also guarantees advertisers a minimum display frequency while maximizing cumulative revenues.
  • Task assignment in crowdsourcing platforms: Crowdsourcing task assignment allocates subtasks to no more than m workers with unknown skill levels while guaranteeing each worker a minimum assignment ratio.The fairness guarantee is associated with worker satisfaction and participation.

VII. NUMERICAL RESULTS

Simulations evaluate LFG's fairness, regret, and convergence behavior under multiple scenarios, comparing it with a fairness-oblivious baseline. The results show that tuning η creates a tradeoff between lower regret and faster fairness convergence, while the regret bound may not be tight.

  • Fairness and regret: LFG consistently satisfies the required minimum selection fraction across different η values, confirming its feasibility-optimality in simulation.The comparison uses η ∈ {1, 10, 100, 1000} over T = 2 × 10^4 rounds.
  • Fairness and regret: LLRS achieves the smallest regret, including negative regret, but violates Arm 1's fairness requirement with a 0.4 selection fraction versus the required 0.5.LLRS is explicitly oblivious to the fairness constraints, favoring higher-mean arms.
  • Fairness and regret: LFG with η ≥ 100 approaches zero regret, while larger η values produce smaller regret in the simulations.The paper explains this trend through the regret upper bound, which approaches zero as both η and T become large.
  • Convergence tradeoff: Increasing η slows convergence to the fairness requirement; with η = 1000 and T ≤ 10^4, Arm 1 remains below its required 0.5 selection fraction.Temporary constraint violations can also produce negative regret before convergence.
  • Convergence tradeoff: For the considered scenario, η = 100 appears to balance regret reduction and convergence speed effectively.The simulations use scenarios with (N, m) = (3, 2) and (10, 6), focusing discussion on the first because observations are similar.
  • Regret-bound tightness: The time-average regret appears to follow log T/T rather than the theoretical bound's dependence on T, suggesting that the upper bound is not tight.The comparison is made for T ≤ 1000 because the N/(2η) term dominates at larger T.

A. Proof of Theorem 1

The proof of Theorem 1 establishes feasibility-optimality by showing that LFG's virtual queues are strongly stable for every requirement vector strictly inside the maximal feasibility region. A Lyapunov-drift argument then yields mean rate stability and satisfaction of the fairness constraints.

  • Stability argument: Fairness requirements are satisfied when the virtual queue system is mean rate stable, so the proof targets strong stability for vectors strictly inside C.Strong stability is used because it implies mean rate stability.
  • Lyapunov analysis: The proof represents the virtual queue state as Q(t) = (Q_1(t), . . . , Q_N(t)) and analyzes it with a Lyapunov function.The conditional drift is derived from the queue-length evolution and bounded because requirements and selections lie in [0, 1].
  • Negative drift: The drift is bounded by B − ε∑_i Q_i(t), where B is constant, producing negative drift when queue lengths are sufficiently large.The constant B is obtained from bounds on weights, UCB estimates, and the maximum number m of simultaneous plays.
  • Comparison policy: For any r strictly inside C, there exists ε > 0 such that r + ε1 also lies inside C, enabling comparison with an A-only policy supporting the enlarged vector.The proof uses the all-ones vector 1 and a policy α whose decisions are independent of Q(t).
  • Conclusion: Applying the Lyapunov Drift Theorem establishes the stability result and completes the proof of feasibility-optimality.The argument concludes with equation (10).

B. Proof of Theorem 2

The proof of Theorem 2 combines regret decomposition with Lyapunov drift analysis. It bounds the resulting drift-plus-regret expression and concludes the stated time-average regret guarantee.

  • Benchmark policy: The proof introduces an optimal A-only policy α* and its action vector d*(t) as the benchmark for LFG's regret.The benchmark policy is stationary and feasible, so its selection fractions meet the requirements r_i.
  • Drift-plus-regret: The regret of LFG is rewritten using the benchmark policy, and a quantity ΔR(t) is defined to capture their expected reward gap in round t.The proof scales ΔR(t) by η and adds it to the Lyapunov drift.
  • Bounding the expression: The expected drift-plus-regret is bounded using independence between the benchmark policy's decisions and the virtual queue lengths.This independence supports replacing queue-weighted benchmark actions with products of expectations.
  • Time averaging: Summing the drift-plus-regret inequality over time and dividing by Tη yields the intermediate time-average bound.The proof uses telescoping sums over t ∈ {0, . . . , T − 1}.
  • Conclusion: Substituting the auxiliary bound into the time-average inequality and combining it with the earlier drift result yields the regret bound in Theorem 2.This final substitution completes the theorem proof.

C. Bounding C1(t)

This section bounds C1(t) by analyzing an auxiliary policy and separating learning-related costs from concentration-bound terms. Summing the resulting inequality yields the target bound.

  • An auxiliary policy π′ selects a super arm S′(t) each round to establish the bound.
  • The proof first derives an upper bound on C1(t), using the LFG selection rule and defining a second error term C2(t).
  • Summing (28) over all rounds, dividing by Tη, and substituting bounds (29) and (30) yields (25).
  • The bound in (29) contains an O(√T log T) learning/exploration term and a constant term from a Chernoff-Hoeffding bound on a bad event.
  • A corresponding bound for another error term is obtained through a second Chernoff-Hoeffding argument.

D. Bounding C2(t)

This section bounds C2(t) by tracking each arm’s play times and controlling deviations of empirical means with concentration inequalities. The resulting summation establishes bound (29).

  • For each arm i, the proof indexes the rounds t_i^a when that arm is played and relates them to its play count h_i(t).
  • The analysis decomposes the expectation of C2(t) according to events comparing the optimistic estimate μ̄_i(t) with the true mean μ_i.
  • The proof bounds deviation contributions using indicator events, sample-mean relationships, and integral comparisons.
  • Taking expectations and summing over rounds yields bound (29), while total arm selections satisfy Σ_i h_i(T−1) ≤ Tm.

E. Bounding C3(t)

This section bounds C3(t) by decomposing underestimation events for each arm and applying Chernoff-Hoeffding concentration. Summation produces bound (30).

  • The proof represents the auxiliary super arm S′(t) by an action vector and decomposes C3(t) using events where μ̄_i(t) is below μ_i.
  • The analysis separates rounds before and after an arm’s first play, using μ̄_i(t)=1 before that first play.
  • After the first play, the proof bounds the contribution K1(t) when the optimistic estimate underestimates the true mean.
  • Chernoff-Hoeffding concentration applies to the sample mean for each possible value of the random play count h_i(t−1).
  • Summing the bounds on E[K1(t)] and the resulting inequality over all rounds yields bound (30).
Loading 1901.04891v3…