The multi-armed bandit problem (2012)

Post by moultano » Wed, May 29, 2019, 7:01 PM UTC

bhl wrote: post #67

moultano wrote: post #57

Does anyone have a reference for solving multi-armed bandit problems with a finite time horizon? I would like something that derives rules or heuristics for how your explore/exploit tradeoff changes as the horizon approaches. This seems like an obvious extension, and something that someone should have worked on given how long this problem has been around, but I've been unable to find anything on it. Any pointers?

What do you mean? Most analyses of multi-armed bandit algorithms assume a finite time horizon. And if not, they use the doubling trick for infinite time horizons.

Thank you, now I realized that I had misunderstood the notation.

Post by j2kun » Mon, Jun 10, 2019, 5:31 PM UTC

nestorD wrote: post #33

j2kun wrote: post #30

UCB1 is really not that much more complicated than epsilon-greedy. Some slightly sloppy code I wrote a few years ago, maybe 20 lines of code: https://github.com/j2kun/ucb1/blob/master/ucb1.py#L7-L35 Sure you have to read a bit more to know why it works, but if you write your code well you could plug this in without any extra trouble. It's not like you need a special optimization solver as a dependency.

And, for not much more effort (computing the variance of your samples), you can use UCB1-tuned [0] which gets rid of the 'c' parameter and tends to be even better. I personnaly think that it should replace UCB1 as a baseline when trying bandit algorithms. [0]: https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf

It's funny, I had read that paper a few times while learning about bandit learning, and I never noticed their version, which funnily enough outperforms vanilla UCB1 in all of their tests!

Re: The multi-armed bandit problem (2012)

Re: The multi-armed bandit problem (2012)