AI Research Portal

This paper introduces Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing (MSB-PRS), a new variant of multi-play stochastic bandits designed for resource allocation problems in applications like LLM and edge intelligence. The core idea is to model resource sharing where arms have stochastic capacities and plays have priority weights, influencing capacity allocation. The paper proposes MSB-PRS-OffOpt, an algorithm to find the optimal play allocation policy with polynomial computational complexity, and an approximate UCB-based algorithm (MSB-PRS-APUCB) for efficient learning. Empirically, MSB-PRS-APUCB demonstrates sub-linear regret and consistently achieves the smallest regret compared to two baselines in synthetic experiments.

The paper addresses several bottlenecks in existing multi-play multi-armed bandit (MP-MAB) frameworks when applied to resource allocation:

Nonlinear Combinatorial Utility Structure: The prioritized resource sharing mechanism and movement costs impose a nonlinear combinatorial structure on the utility function, making it difficult to locate the optimal play allocation policy.

Model Formulation: Formulates MSB-PRS, a model that captures prioritized resource sharing in resource allocation problems.
Fundamental Learning Limits: Proves instance independent and instance dependent regret lower bounds of Ω(α₁σ√KMT) and Ω(α₁σ² ln T), respectively, revealing the impact of model parameters on learning hardness.
Computational Efficiency: Designs MSB-PRS-OffOpt, an algorithm to locate the optimal play allocation policy with a polynomial computational complexity of O(MK³) by formulating a priority ranking aware bipartite graph.
Sample Efficiency: Develops an approximate UCB-based algorithm (MSB-PRS-APUCB) that uses MSB-PRS-OffOpt as a subroutine, achieving per-round computational complexity of O(MK³) and sublinear instance independent and instance dependent regret upper bounds matching the corresponding lower bounds up to acceptable factors (√K ln KT and α₁K² respectively).

The proposed method, MSB-PRS, involves a decision maker assigning K plays to M arms over T rounds to maximize cumulative utility.

Arm Model: Each arm m ∈ [M] has a stochastic number of capacities Dm and a per-unit capacity reward Rm. Dm is drawn from a support subset of [dmax], and Rm is drawn from a support subset of R, with mean µm. Play and Priority Model: Each play k ∈ [K] has a movement cost vector ck (with entries ck,m for assigning to arm m) and a priority weight αk. Larger αk implies higher priority, with α₁ ≥ α₂ ≥ ... ≥ αK > 0. Prioritized Capacity Sharing: When multiple plays are assigned to an arm, capacity is allocated in a larger priority weight first manner. Only top-min{N_m^(t), D_m^(t)} plays assigned to arm m receive capacity. Rewards and Feedback: If play k gets a unit of capacity on arm m, it receives a reward X_k^(t) = α_k R_m,l_k^(t), where l_k^(t) is its rank. Otherwise, it receives null. The decision maker observes rewards for each arm and the number of capacity units D_m^(t) if at least one play is assigned to arm m. Objective: Maximize the total utility U(a(t); μ, P) = Σm∈[M] Um(a(t); µm, Pm) over T rounds, where Um(a(t); µm, Pm) = Rm(a(t); µm, Pm) - Σk∈[K] Ck,m1{a(t)=m}. The optimal action profile a* = arg max_α∈A U(α; μ, P) is unknown due to unknown parameters μ and P.

Efficient Computation Oracle (MSB-PRS-OffOpt):

Bipartite Graph Formulation: A complete weighted bipartite graph G = (U ∪ V, U × V, W) is constructed. U = {u₁, ..., uK} represents plays, and V = ∪m∈[M] Vm, where Vm = {um,1, ..., um,K} represents arm m's capacity units, capturing prioritized sharing.
Weight Function: The weight of an edge (uk, um,j) is W(uk, um,j) = Am(k, j) if j ≤ θk, otherwise -∞, where Am(k,l) = αkµmPm,l - Ck,m is the marginal utility contribution of play k when ranked l-th on arm m, and θk is the number of plays with priority weight ≥ αk.
Optimal Action Profile: Locating the optimal action profile is equivalent to finding a U-saturated, V-monotone, and priority compatible matching with maximum total weights. If a maximum weighted matching does not have these properties, it can be adjusted.
Algorithm 1 (MSB-PRS-OffOpt): Takes μ and P as input, constructs the graph G, finds the MaximumWeightedMatching(G), adjusts it if necessary, and returns the optimal action profile a(M).

Efficient Learning Algorithm (MSB-PRS-APUCB):

Approximate UCB: An approximate UCB-based algorithm is designed, which uses MSB-PRS-OffOpt as a subroutine.
Estimators: It estimates the complementary cumulative probability matrix P^(t) and the reward mean vector μ^(t) from historical feedback Ht.
UCB Index: The approximate UCB index is defined as UCB(t)(a)=U (α, μ(t)+ε(t), P(t)+λ(t)), where ε(t) and λ(t) are confidence bands derived from Lemma 6.
Action Selection: In each round t, the algorithm selects the action profile a(t) = arg max_α∈A UCB(t-1)(a) using MSB-PRS-OffOpt with the estimated parameters and confidence bands.

Model Parameters:
- M ∈ N+ arms, K ∈ N+ plays, T ∈ N+ decision rounds.
- Arm m capacity Dm: stochastic, support subset of [dmax].
- Arm m reward Rm: stochastic, support subset of R, mean µm = E[Rm]. Assumed µm > 0, ∀m ∈ [M]. Rm is σ-subgaussian, σ ∈ R+.
- Play k movement cost ck: vector [ck,m : ∀m ∈ [M]], ck,m ∈ R+ ∪ {+∞}.
- Play k priority weight αk: αk ∈ R+, with α₁ ≥ α₂ ≥ ... ≥ αK > 0.
Key Equations:
- Expected total reward from arm m: Rm(a(t); µm, Pm) = µm Σk∈[K] 1{a(t)=m}αkPm,lk(t).
- Expected utility from arm m: Um(a(t); µm, Pm) = Rm(a(t); µm, Pm) - Σk∈[K] Ck,m1{a(t)=m}.
- Aggregate utility: U(a(t); μ, P) = Σm∈[M] Um(a(t); µm, Pm).
- Marginal utility contribution: Am(k,l) = αkµmPm,l - Ck,m.
- Weight function for bipartite graph: W(uk, Um,j) = Am(k, j) if j ≤ θk, otherwise -∞.
- Estimated complementary cumulative probability: P_m,d^(t) = (Σs=1^t 1{D_m^(s) ≥ d} 1{N_m^(s) > 0}) / (Σs=1^t 1{N_m^(s) > 0}).
- Estimated mean reward: μ_m^(t) = (Σs=1^t Σk=1^K 1{X_k^(s) ≠ null} 1{a_k^(s)=m} X_k^(s)/α_k) / (Σs=1^t Σk=1^K 1{X_k^(s) ≠ null} 1{a_k^(s)=m}).
- Approximate UCB index: UCB(t)(a)=U (α, μ(t)+ε(t), P(t)+(t)).
Optimization: MSB-PRS-OffOpt uses a maximum weighted matching algorithm (e.g., Crouse et al. (Crouse 2016)) as its core.
Computational Complexity:
- MSB-PRS-OffOpt: O(MK³).
- Approximate UCB-based algorithm (MSB-PRS-APUCB) per round: O(MK³).
Regret Bounds:
- Instance independent regret lower bound: RegT ≥ Ω(α₁σ√KMT).
- Instance dependent regret lower bound: lim inf_(T→∞) RegT / ln T ≥ α₁σ² M / Δ.
- Instance independent regret upper bound: RegT ≤ 2M(1+dmax)Kµmax + 3601(µmax + 1)(2σ + 1)√MKT/K ln KT.
- Instance dependent regret upper bound: RegT < 96MK²α₁²(2σ + 1)² ln KT / Δ + 2M(1+dmax)Kµmax.

Datasets: Synthetic experiments.
Metrics: Regret.
Baselines:
- OnlinActPrf (Chen and Xie 2022): Considers homogeneous plays and expert feedback on capacity, without priority capacity sharing.
- OnlinActPrf-v: A variant of OnlinActPrf enabling UCB on capacity distribution estimation.
Numeric Results:
- Parameter Settings: Default parameters: T = 10⁴, δ = 1/T, K = 10 plays, M = 5 arms, η = 1, σ = 0.2. Half of plays have weight 3, other half have weight 1.
- Impact of Number of Arms (M):
  - MSB-PRS-APUCB regret curves (for M=5, 10, 15) initially exhibit a sharp increase before plateauing, indicating sub-linear regret.
  - The convergence rate of MSB-PRS-APUCB regret gradually decreases with an increase in M.
  - MSB-PRS-APUCB consistently yields the smallest regret compared to OnlinActPrf and OnlinActPrf-v, which show a linear regret trend.
- Impact of Number of Plays (K):
  - MSB-PRS-APUCB regret curves (for K=10, 15, 20) also show an initial sharp increase before plateauing, indicating sub-linear regret.
  - MSB-PRS-APUCB consistently yields the smallest regret compared to OnlinActPrf and OnlinActPrf-v, which show a linear regret trend.

Regret Gap: Closing the regret gap between the derived lower and upper bounds is an open problem, as MSB-PRS is neither a standard MP-MAB model nor a standard combinatorial bandit model.

Method evidence: "Formally, we proposed MSB-PRS (Multiple-play Stochastic Bandits with Prioritized Resource Sharing). The MSB-PRS is composed of K∈ N+ plays and M∈ N+ arms. Each play has a priority weight and movement costs. Each arm has a stochastic number of units of capacities. Plays share the capacity in a high priority weight first manner." (section: 1 Introduction)
Result evidence: "This observation confirms that MSB-PRS-APUCB yields the smallest regret compared to the two baseline algorithms. This trend persists even when K = 15 and 20, as shown in Fig. 2c and 2d, respectively." (section: 6 Synthetic Experiments)
Limitation evidence: "Closing the regret gap is an open problem, since MSB-PRS is neither a standard MP-MAB model nor a standard combinatorial bandit model." (section: 5.2 Efficient Learning Algorithm)

Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures