Bounded Regret for Finite-Armed Structured Bandits

By Tor Lattimore, R´emi Munos. 2014

70 citations recorded by the source corpus.

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.

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

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

1. Sergey Levine
2. Chelsea Finn
3. Pieter Abbeel
4. Yuxi Li
5. Matthew Botvinick
6. Yoshua Bengio
7. Ruslan Salakhutdinov
8. Charles Blundell

In Computer Networks and Communications

1. R´emi Munos
2. Charles Blundell
3. Matthew Botvinick
4. Csaba Szepesvari
5. Aadirupa Saha
6. Tor Lattimore

In Management Science and Operations Research

1. Matthew Botvinick
2. R´emi Munos
3. Charles Blundell
4. Dhruva Tirumala
5. Joel Z. Leibo
6. Hubert Soyer
7. Zeb Kurth-Nelson
8. Marc G. Bellemare

Citations in the corpus

• Learning to reinforcement learn (2016, background): “We report the performance (average over bandit environments drawn from the test distribution) either in terms of the cumulative regret:”