If you enjoy this sort of thing, you might like to work out what the exact optimal algorithm is.
I guess this is a joke. From wikipedia: “Originally considered by Allied scientists in World War II, it proved so intractable that, according to Peter Whittle, it was proposed the problem be dropped over Germany so that German scientists could also waste their time on it.[10]” (note that your wikipedia-link is broken)
Multi-armed bandit problems were intractable during WWII probably mainly because computers weren’t available yet. In many cases, the best approach is brute force simulation. That’s the way I would approach the “blue box” problem (because I’m lazy).
But exact approaches have also been found: “Burnetas AN and Katehakis MN (1996) also provided an explicit solution for the important case in which the distributions of outcomes follow arbitrary (i.e., nonparametric) discrete, univariate distributions.” The blue box problem is within that class.
I guess this is a joke. From wikipedia: “Originally considered by Allied scientists in World War II, it proved so intractable that, according to Peter Whittle, it was proposed the problem be dropped over Germany so that German scientists could also waste their time on it.[10]” (note that your wikipedia-link is broken)
Thank you very much—link fixed!
That’s a really funny quote!
Multi-armed bandit problems were intractable during WWII probably mainly because computers weren’t available yet. In many cases, the best approach is brute force simulation. That’s the way I would approach the “blue box” problem (because I’m lazy).
But exact approaches have also been found: “Burnetas AN and Katehakis MN (1996) also provided an explicit solution for the important case in which the distributions of outcomes follow arbitrary (i.e., nonparametric) discrete, univariate distributions.” The blue box problem is within that class.
Yeah, but that was 60 years ago, and the single-armed bandit problem is easier than the multi-armed bandit.