Skip to main content
Journal cover image

Multi-armed bandits with metric switching costs

Publication ,  Conference
Guha, S; Munagala, K
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
November 12, 2009

In this paper we consider the stochastic multi-armed bandit with metric switching costs. Given a set of locations (arms) in a metric space and prior information about the reward available at these locations, cost of getting a sample/play at every location and rules to update the prior based on samples/plays, the task is to maximize a certain objective function constrained to a distance cost of L and cost of plays C. This fundamental and well-studied problem models several optimization problems in robot navigation, sensor networks, labor economics, etc. In this paper we develop a general duality-based framework to provide the first O(1) approximation for metric switching costs; the actual constants being quite small. Since these problems are Max-SNP hard, this result is the best possible. The overall technique and the ensuing structural results are independently of interest in the context of bandit problems with complicated side-constraints. Our techniques also improve the approximation ratio of the budgeted learning problem from 4 to 3∈+∈ε. © 2009 Springer Berlin Heidelberg.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783642029295

Publication Date

November 12, 2009

Volume

5556 LNCS

Issue

PART 2

Start / End Page

496 / 507

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Guha, S., & Munagala, K. (2009). Multi-armed bandits with metric switching costs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5556 LNCS, pp. 496–507). https://doi.org/10.1007/978-3-642-02930-1_41
Guha, S., and K. Munagala. “Multi-armed bandits with metric switching costs.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5556 LNCS:496–507, 2009. https://doi.org/10.1007/978-3-642-02930-1_41.
Guha S, Munagala K. Multi-armed bandits with metric switching costs. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009. p. 496–507.
Guha, S., and K. Munagala. “Multi-armed bandits with metric switching costs.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5556 LNCS, no. PART 2, 2009, pp. 496–507. Scopus, doi:10.1007/978-3-642-02930-1_41.
Guha S, Munagala K. Multi-armed bandits with metric switching costs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009. p. 496–507.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783642029295

Publication Date

November 12, 2009

Volume

5556 LNCS

Issue

PART 2

Start / End Page

496 / 507

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences