Description
Bandit algorithms [100 points] For this assignment, you will carry out some experimentation with bandit algorithms, in order to help you understand what we discussed in class, and to get used to the way in which we will run experiments for other assignments as well. You should submit a notebook with your code, results and explanations. 1. [5 points] Write a small simulator for a Bernoulli bandit with k arms. The probability of success pi for each arm i ∈ {1, …k} should be provided as an input. The bandit should have a function called ”sample” which takes as input the index of an action and provides a reward sample. Recall that a Bernoulli bandit outputs either 1 or 0, drawn from a binomial distribution of parameter pk. Test your code with 3 arms of parameters q∗ = [0.5, , 0.5 − δ, 0.5 − 2δ, with δ = 0.1. Generate and save a set of 50 samples for each action. For the test, plot one graph for each action, containing the reward values obtained over the 100 draws, the empirical mean of the values, and the true q∗ for each arm. Each graph will have an x-axis that goes to 50, two horizontal lines (true value and estimated value) and a set of points of value 0 and 1. 2. [5 points] Code the rule for estimating action values discussed in lecture 2, with a fixed learning rate α, in a function called update, and using the incremental computation of the mean presented in lecture 2, in a function called updateAvg. Using the previous data, plot for each action a graph showing the estimated q value as a function of the number of samples, using averaging as well as α = 0.01 and α = 0.1, and the true value. Each graph should have two curves and a horizontal line. 3. [10 points] Repeat the above experiment 100 times, starting with action value estimates of 0. Each run will still contain 100 samples for each action. Plot the same graph as above, but where the curves have the average and standard error over the 100 runs. Explain in 1-2 sentences what you observe. Which of the α values is better? How do they compare to averaging? If you wanted to optimize further, in what range of α would you look for better values? 4. [20 points] Code the -greedy algorithm discussed in class, with averaging updates, with provided as an input. You will run 100 independent runs, each consisting of 1000 time steps. Plot the following graphs: (a) The reward received over time, averaged at each time step over the 100 independent runs (with no smoothing over the time steps), and the standard error over the 100 runs (b) The fraction of runs (out of 100) in which the first action (which truly is best) is also estimated best based on the action values 1 (c) The instantaneous regret lt (as discussed in lecture 3) (averaged over the 100 runs) (d) The total regret Lt up to time step t (as discussed in lecture 3) (averaged over the 100 runs) Generate this set of graphs, for the following values of : 0, 1/8, 1/4, 1/2, 1. Explain what you observe in the graphs and discuss the effect of you observe. 5. [5 points] For = 1/4 and = 1/8, plot the same graphs for α = 0.1, α = 0.01, α = 0.001 and averaging. Explain in 2 sentences what you observe. 6. [20 points] Write a function that implements the UCB algorithm discussed in lecture 2. Set c = 2. Plot the same graphs as above for α = 0.1, α = 0.01, α = 0.001 and averaging. Explain briefly the behavior you observe. 7. [20 points] Write a function that implements the Thompson sampling to be discussed in lecture 4. Plot the same graphs as above for α = 0.1, α = 0.01, α = 0.001 and averaging. Explain briefly the behavior you observe. 8. [5 points] For each of the algorithms, pick the best hyper-parameter combination you have observed (explain how you decided what ”best” means). Plot together the curves for this setting. Comment on the relative behavior of the different algorithms. 9. [10 points] Let us now consider a non-stationary problem. Let δ = 0.1 and imagine that after 500 time steps, the parameter of actions 2 and 3 become 0.5 + δ and 0.5 + 2δ respectively. Run for each of the three algorithms a fixed value of α = 0.1 and the averaging value estimation. For use values 1/4 and 1/8. Using these values, plot only the reward graph as above (you should have 2 lines for -greedy, one for UCB and one for Thompson sampling, for each learning rate setting). Explain what you see in the graph. Based on these results, which algorithm is best suited to cope with non-stationarity? 2
