Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards

By Yi Gai, Bhaskar Krishnamachari, Rahul Jain. arXiv.org, 2010

300 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a83342d7c30f17a9b0c4d377d568ca9272a58dc4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Bandit Algorithms (2020, methodology): “This procedure is explained in detail by Garivier [2013]. When the reward distributions are actually Gaussian there is a more elegant technique that avoids peeling altogether (Exercise 9.”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, methodology): “Our result significantly improves the coefficient of the leading lnn term comparing to Theorem 2 of (Gai et al., 2012) in two aspects: (a) we remove a factor of L+1; and (b) the coefficient ∑ i∈[m],∆min>0 1/∆min is likely to be much smaller than m ·∆max/(∆min)(2) in (Gai et al.”
Cascading Bandits: Learning to Rank in the Cascade Model (2015, methodology): “In this sense, the problem is similar to stochastic combinatorial bandits, which are often studied with linear rewards and semi-bandit feed-back (Gai et al., 2012; Kveton et al., 2014a;b), where the learning agent receives feedback for every selected item.”
Personalized Recommendation via Parameter-Free Contextual Bandits (2015, background): “A wide range of application-oriented problems have been modeled as the context-free multi-armed bandit problem, such as online advertising [25, 30], web search and content optimization [2, 27], network optimization [11], game playing [12], routing [6], etc.”