Use this resource - and many more! - in *your* textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match *your* way.

**Not an educator**but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

# On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards

## By: Mingyan Liu; Krishnamachari, B.; Yi Gai;

2011 / IEEE / 978-1-4244-9268-8

### Description

This item was taken from the IEEE Conference ' On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards ' We consider a combinatorial generalization of the classical multi-armed bandit problem that is defined as follows. There is a given bipartite graph of M users and N¡YM resources. For each user-resource pair (i,j), there is an associated state that evolves as an aperiodic irreducible finite-state Markov chain with unknown parameters, with transitions occurring each time the particular user i is allocated resource j. The user i receives a reward that depends on the corresponding state each time it is allocated the resource j. The system objective is to learn the best matching of users to resources so that the long-term sum of the rewards received by all users is maximized. This corresponds to minimizing regret, defined here as the gap between the expected total reward that can be obtained by the best-possible static matching and the expected total reward that can be achieved by a given algorithm. We present a polynomial-storage and polynomial-complexity-per-step matching-learning algorithm for this problem. We show that this algorithm can achieve a regret that is uniformly arbitrarily close to logarithmic in time and polynomial in the number of users and resources. This formulation is broadly applicable to scheduling and switching problems in communication networks including cognitive radio networks and significantly extends prior results in the area.

**Related Topics**

Graph Theory

Learning (artificial Intelligence)

Markov Processes

Resource Allocation

Scheduling

Telecommunication Computing

Cognitive Radio Networks

Combinatorial Multiarmed Bandit Problem

Markovian Rewards

Combinatorial Generalization

Classical Multiarmed Bandit Problem

Bipartite Graph

Aperiodic Irreducible Finite-state Markov Chain

Unknown Parameters

Resource Allocation

System Objective

Long-term Sum

Best-possible Static Matching

Polynomial-storage

Polynomial-complexity-per-step Matching-learning Algorithm

Scheduling

Switching Problems

Communication Networks

Markov Processes

Upper Bound

Polynomials

Eigenvalues And Eigenfunctions

Ieee Communications Society

Algorithm Design And Analysis

Cognitive Radio

Computational Complexity

Cognitive Radio

Telecommunication Switching

Engineering

User-resource Pair