8 ms·
I know about the Gittins index to solve Multi-armed bandit problems, from 1979. http://en.wikipedia.org/wiki/Gittins_index http://en.wikipedia.org/wiki/Gittins
by cschmidt 15y ago
I know about the Gittins index to solve Multi-armed bandit problems, from 1979.
http://en.wikipedia.org/wiki/Gittins_index http://en.wikipedia.org/wiki/Gittins_index
I thought that was supposed to be optimal in some sense. How does the paper cited in this post improve on that?
- noelwelsh 15y agoThe kind of optimality we're talking about is the up-to-constant factors / Big-O kind. The Gittins index has better constant factors than UCB-1. However, UCB-1 can be computed easily whereas Gittins indices are very expensive to compute.