Source-linked AI summary
Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards
Yi Gai, Bhaskar Krishnamachari, Rahul Jain
TL;DR
The paper addresses the scalability limits of arm-based bandit policies for dependent arms and proposes policies for rewards that are linear in unknown variables. These policies achieve logarithmic regret in time, polynomial dependence on the number of unknown variables, and linear storage, while applying to tractable combinatorial network optimization.
Problem
Arm-based policies do not scale to large dependent-arm problems because storage, computation, and regret can grow with the number of arms, which may be exponential.
Method
The paper models actions as feasible vectors producing linear rewards from observed unknown variables and bases LLR storage and decisions on those variables directly.
Results
The policies achieve regret logarithmic in time and polynomial in the number of unknown variables, while requiring storage linear in that number.
Takeaways & Limitations
The framework applies to tractable combinatorial network problems including maximum weight matching, shortest path, and minimum spanning tree computation.
Abstract
from arXiv · showhide
In the classic multi-armed bandits problem, the goal is to have a policy for dynamically operating arms that each yield stochastic rewards with unknown means. The key metric of interest is regret, defined as the gap between the expected total reward accumulated by an omniscient player that knows the reward means for each arm, and the expected total reward accumulated by the given policy. The policies presented in prior work have storage, computation and regret all growing linearly with the number of arms, which is not scalable when the number of arms is large. We consider in this work a broad class of multi-armed bandits with dependent arms that yield rewards as a linear combination of a set of unknown parameters. For this general framework, we present efficient policies that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown parameters (even though the number of dependent arms may grow exponentially). Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. We show that this generalization is broadly applicable and useful for many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weight matching, shortest path, and minimum spanning tree computations.
I. INTRODUCTION
The paper generalizes multi-armed bandits to dependent arms whose rewards are linear in unknown variables, enabling scalable policies for combinatorial optimization. Its LLR policies target logarithmic-time regret with storage and computation governed by the unknown variables rather than potentially exponential arm sets.
- Independent-arm bandit policies are inadequate when practical problems contain exponentially many arms and dependencies that should be exploited.
- Each action selects a vector from a finite feasible set, observes variables corresponding to nonzero components, and receives the linear reward aT X.
- LLR stores and computes estimates for unknown variables directly, reducing storage, computation, and regret relative to arm-based approaches.
- O(N) storage and O(N^4 ln n) regret are stated for the single-arm LLR policy, with n denoting the time index.
- The paper also extends the single-arm policy to selecting K ≥1 different actions per time and provides regret analysis for that formulation.
- The framework covers maximum weight matching, shortest path, and minimum spanning tree problems with unknown random coefficients when their deterministic optimization is tractable.
III. PROBLEM FORMULATION
The paper formulates bandits with dependent, linear-reward arms and explains why arm-independent UCB1 scaling is unsuitable when the action set is exponentially large.
- III. PROBLEM FORMULATION: The model uses N bounded random processes with unknown means, allowing dependence across variables while assuming i.i.d. evolution over time.
- III. PROBLEM FORMULATION: Each finite-set action is an N-dimensional nonnegative vector, and selecting it reveals the variables corresponding to its nonzero components.
- III. PROBLEM FORMULATION: The reward is evaluated through regret against a genie that selects an optimal arm at every time.
- III. PROBLEM FORMULATION: The optimal-arm index is denoted by ∗, with any one optimal arm selected when multiple optimal arms exist.
- III. PROBLEM FORMULATION: The number of arms |F| may be exponential in N, making sublinear regret important for vanishing time-averaged regret.
- A. A Naive Approach: UCB1 selects arms using each arm’s empirical reward and play count, thereby ignoring dependencies and storing observations independently.
- A. A Naive Approach: UCB1 has a regret bound inherited from prior work, while requiring storage linear in the number of arms.
- A. A Naive Approach: When the arm count grows exponentially with the number of unknown variables, UCB1’s storage and regret scaling are highly unsatisfactory.
B. A new policy
LLR learns unknown variable means directly rather than maintaining arm-specific statistics, then uses those estimates in a deterministic linear optimization step.
- B. A new policy: LLR is the paper’s proposed Learning with Linear Rewards policy.
- B. A new policy: The algorithm’s main loop repeatedly plays an arm solving a maximization problem over the feasible action set.
- B. A new policy: The policy initializes and updates one sample-mean vector and one observation-count vector for the N unknown variables.
- B. A new policy: After playing an arm, LLR updates statistics only for variables observed through that arm.
- B. A new policy: LLR treats coefficient vectors as arms and operates over the feasible action set F.
- B. A new policy: Previous time-indexed matrices need not be stored while running the algorithm.
- B. A new policy: LLR requires storage linear in N, while its per-step computation is polynomial when the embedded deterministic optimization is polynomial-time solvable.
- B. A new policy: The optimization subproblem may be NP-hard for arbitrary F, although practical special cases admit polynomial computation.
V. ANALYSIS OF REGRET
The regret analysis avoids summing separately over potentially exponentially many suboptimal arms by charging non-optimal selections to under-observed variables.
- V. ANALYSIS OF REGRET: Arm-by-arm regret analysis can be loose because the number of arms may grow faster than polynomially.
- V. ANALYSIS OF REGRET: Theorem 2 gives an upper bound on expected regret under LLR.
- V. ANALYSIS OF REGRET: The proof uses a Chernoff-Hoeffding bound for bounded variables with conditional mean θ_i.
- V. ANALYSIS OF REGRET: After initialization, an optimal arm leaves the variable counters unchanged, whereas a non-optimal arm increments a counter associated with a least-observed variable.
- V. ANALYSIS OF REGRET: Each non-optimal arm selection increments exactly one variable counter, equating total non-optimal plays with the sum of those counters.
- V. ANALYSIS OF REGRET: The proof bounds counter increments through indicator variables and probability inequalities involving the observed-variable counts.
- V. ANALYSIS OF REGRET: The resulting bound includes a term proportional to N ln n rather than the number of dependent arms.
- V. ANALYSIS OF REGRET: The highlighted final bound scales with 4a^2 maxL^2(L + 1)N ln n.
VI. APPLICATIONS
The paper introduces applications and extensions of LLR for graph-based combinatorial network optimization with unknown edge weights.
- VI. APPLICATIONS: The applications and extensions concern combinatorial network optimization in graphs whose edge weights are unknown random variables.
A. Maximum Weighted Matching
Maximum weighted matching can be treated as a linear-reward bandit whose matching arms may be exponentially numerous, while learning uses linear storage and polynomial computation.
- A. Maximum Weighted Matching: In cognitive-radio channel allocation, unknown user-channel throughputs make sequential learning necessary, and optimal allocations are one-to-one matchings when channels exceed users.
- A. Maximum Weighted Matching: Each matching is an arm, with reward equal to the sum-throughput from user-channel assignments.
- A. Maximum Weighted Matching: The problem has M × Q unknown variables but P(Q, M) possible arms, which can grow exponentially in the number of variables.
- A. Maximum Weighted Matching: LLR stores sample means and observation counts in two M by Q matrices, giving storage linear in the number of unknown variables.
- A. Maximum Weighted Matching: The policy's deterministic step is a maximum weighted bipartite matching solvable in polynomial computation time, such as with the Hungarian algorithm.
- A. Maximum Weighted Matching: The regret is O(min{M, Q}^3MQ log n), because L = min{M, Q} is smaller than M × Q.
B. Shortest Path
The shortest-path formulation maps unknown edge costs to a linear-cost bandit, using a cost-minimization version of LLR called LLC.
- B. Shortest Path: A path from source s to destination d minimizes the sum of nonnegative edge costs D_i,j.
- B. Shortest Path: For shortest path, Dijkstra's and Bellman-Ford algorithms can solve the deterministic optimization used by LLC in polynomial computation time.
- B. Shortest Path: When edge costs are bounded-support random variables with unknown means and are i.i.d. over time, dynamic learning is required.
- B. Shortest Path: LLC is obtained by changing LLR's linear-objective maximization into minimization over a finite constraint set F.
2: // MAIN LOOP
The main loop selects an arm by solving the current linear minimization problem, yielding an efficient shortest-path learning policy with logarithmic-time regret growth.
- 2: // MAIN LOOP: At each iteration, the policy plays an arm that solves the linear cost minimization problem.
- 2: // MAIN LOOP: LLC applies to any constraint set with linear costs and inherits Theorem 2's regret analysis from LLR.
- 2: // MAIN LOOP: For shortest path, each s-to-t path is an arm, with |E| unknown variables even though the number of paths may be exponential.
- 2: // MAIN LOOP: Dijkstra's and Bellman-Ford algorithms provide polynomial-time solvers for the optimization step, giving LLC linear storage and polynomial computation time.
- 2: // MAIN LOOP: Regret is O(|E|^4 log n).
C. Minimum Spanning Tree
Minimum spanning tree is presented as another combinatorial bandit application: spanning trees are arms, and LLC retains polynomial-scale regret dependence with logarithmic time growth.
- C. Minimum Spanning Tree: Minimum spanning tree has polynomial-time solution methods, including Prim's and Kruskal's algorithms.
- C. Minimum Spanning Tree: The feasible set F consists of all spanning trees in the graph.
- C. Minimum Spanning Tree: With LLC, each spanning tree is treated as an arm and L = |E|.
- C. Minimum Spanning Tree: Regret bound also grows as O(|E|^4 log n).
- VII. NUMERICAL SIMULATION RESULTS: For Q = 7 and M = 4, P(7, 4) = 840 versus 7 × 4 = 28, making naive-policy storage 30 times larger.
- VII. NUMERICAL SIMULATION RESULTS: For Q = 9 and M = 5, P(9, 5) = 15120 versus 9 × 5 = 45, about 336 times higher, and naive-policy regret grows faster.
- VII. NUMERICAL SIMULATION RESULTS: The simulations compare LLR with a naive policy for cognitive-radio channel allocation under i.i.d. Bernoulli throughputs with unknown means.
VIII. K SIMULTANEOUS ACTIONS
The LLR policy extends to selecting K arms simultaneously, maximizing total reward while preserving a logarithmic-in-time regret bound.
- VIII. K SIMULTANEOUS ACTIONS: The reward-maximizing LLR policy and cost-minimizing LLC policy both extend to playing K arms per time slot.The cost-minimization extension is described as straightforward.
- VIII. K SIMULTANEOUS ACTIONS: LLR-K selects the K arms with the largest expected rewards under the simultaneous-action setting.The optimal set is defined as A* = {a*,k, 1 ≤ k ≤ K}.
- VIII. K SIMULTANEOUS ACTIONS: Theorem 3 bounds expected regret under LLR-K by 4a^2 maxL^2(L + 1)N ln n.This bound is presented for the extended policy with K-arm selection.
- VIII. K SIMULTANEOUS ACTIONS: Because K arms are played at each time, a random variable may be observed up to Kt times, modifying the single-arm analysis.The proof otherwise follows the structure of the single-arm theorem.
IX. CONCLUSION
The paper applies linear-reward bandit policies to combinatorial optimization with many dependent arms and identifies several open problems for extending the framework.
- IX. CONCLUSION: LLR and LLC use the underlying unknown variables rather than individual arms for storage and decision-making.This addresses the poor scaling of arm-based policies when the arm set is exponentially large.
- IX. CONCLUSION: The paper demonstrates applicability to linear combinatorial optimization with unknown-mean random coefficients.The conclusion characterizes these applications as providing useful insights into real-world problems.
- IX. CONCLUSION: A rigorous lower bound on achievable regret remains open, including whether an upper bound better than O(N^4 log n) is possible.The authors conjecture a lower bound of Ω(N log n), but state that it remains unproved.
- IX. CONCLUSION: Distributed policies in which users independently select different action-vector elements remain an open problem.The conclusion connects this question to distributed channel-access policies in cognitive radio networks.
- IX. CONCLUSION: Extending the framework to tractable structured nonlinear rewards, such as convex functions, is left for future work.The paper specifically identifies nonlinear reward functions as a direction for further study.