A Structured Multiarmed Bandit Problem and the Greedy Policy

Adam J. Mersereau · Paat Rusmevichientong · John N. Tsitsiklis

93 citations0/0 files storedIEEE Transactions on Automatic Control

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

We consider a multiarmed bandit problem where the expected reward of each arm is a linear function of an unknown scalar with a prior distribution. The objective is to choose a sequence of arms that maximizes the expected total (or discounted total) reward. We demonstrate the effectiveness of a greedy policy that takes advantage of the known statistical correlation structure among the arms. In the infinite horizon discounted reward setting, we show that the greedy and optimal policies eventually coincide, and both settle on the best arm. This is in contrast with the Incomplete Learning Theorem for the case of independent arms. In the total reward setting, we show that the cumulative Bayes risk afterTperiods under the greedy policy is at mostO(logT), which is smaller than the lower bound of ¿(log2T) established by Lai for a general, but different, class of bandit problems. We also establish the tightness of our bounds. Theoretical and numerical results show that the performance of our policy scales independently of the number of arms.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 93 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 2002The Nonstochastic Multiarmed Bandit Problem 1952Some aspects of the sequential design of experiments 1974A two-armed bandit theory of market pricing 2004Online convex optimization in the bandit setting: gradient descent without a gradient 1987Bandit Problems, Sequential Allocation of Experiments.1995Sample mean based index policies byO(logn) regret for the multi-armed bandit problem 1980Multi-Armed Bandits and the Gittins Index

Cited by

2014Bounded Regret for Finite-Armed Structured Bandits 2013A linear response bandit problem 2013Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats 2015Robust Multiarmed Bandit Problems 2013Bayesian Dynamic Pricing in Queueing Systems with Unknown Delay Cost Characteristics 2013OM Forum—Operations Management Challenges for Some “Cleantech” Firms

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.