No-regret learning experiments

Explore-Then-Commit

Start with a demonstration of the ETC algorithm. Choose the number of times each arm is explored, denoted by $m$. Run the algorithm when ready. Observe the empirical average of each arm after being tested $m$ times. The algorithm picks the arm with the highest empirical average and plays it until the horizon is reached.

We now focus on the setting with two arms. Let us experiment with how the number of exploration rounds affects the expected total regret at the horizon. If we don't spend enough time exploring, then we pick the wrong arm, leading to large regret. At some point, we should be confident enough to commit to our arm choice. Beyond this point, the negative impact of further exploration outweighs its benefit of confidence.

We can choose to explore each arm the following number of times.$$m=max\{1,\lceil \frac{4{𝜎}^2}{{𝛥}^2}ln\frac{T{𝛥}^2}{4{𝜎}^2}\rceil \}$$Notice that for a Bernoulli experiment, $T=512$, and $𝛥=0.2$, we would choose $m=76$. This doesn't match our empirical data, but is exactly where our regret upper bound is minimized.

Three key quantities that affect our choice of $m$ and our regret guarantees are the optimality gap, horizon, and the distributions of the rewards. The experiment below uses a Gaussian bandit with two arms to explore the effect of the optimality gap.

Returning to the Bernoulli bandit, we can experiment with the effect of the horizon on regret. Here, each trial uses a fresh run of our algorithm. Recall that $m$ varies based on the horizon.