Consider a stochastic n-armed bandit, n 2, in which the arms give 0-1 (Bernoulli) rewards....

Transcribed Image Text:

Consider a stochastic n-armed bandit, n ≥ 2, in which the arms give 0-1 (Bernoulli) rewards. We restrict our attention to instances I in which the means of the arms all lie in (0,1), and moreover, no two arms have the same mean. In any such instance I, let a2 be the arm with the second highest mean, and let u be a random variable denoting the number of pulls of a2 over a horizon T > 1. Describe a deterministic algorithm L, which, for every qualifying bandit instance I, achieves ELI [UT] T In other words, the number of pulls of arms other than a2 under L must be a vanishing fraction of the horizon. Provide a proof sketch that L satisfies this property; no need for a detailed mathe- matical working. [4 marks] lim T→∞ 1. Consider a stochastic n-armed bandit, n ≥ 2, in which the arms give 0-1 (Bernoulli) rewards. We restrict our attention to instances I in which the means of the arms all lie in (0,1), and moreover, no two arms have the same mean. In any such instance I, let a2 be the arm with the second highest mean, and let u be a random variable denoting the number of pulls of a2 over a horizon T > 1. Describe a deterministic algorithm L, which, for every qualifying bandit instance I, achieves ELI [UT] T In other words, the number of pulls of arms other than a2 under L must be a vanishing fraction of the horizon. Provide a proof sketch that L satisfies this property; no need for a detailed mathe- matical working. [4 marks] lim T→∞ 1.

Answer rating: 100% (QA)

The detailed ... View the full answer