9 Multi Armed Bandit

Page 1

9 Multi-Armed Bandit In this exercise session we will consider the UCB1 and the TS algorithms as examples of frequentist and Bayesian MAB algorithms, respectively, for the solutions of the stochas- tic MAB problem. 9.1 Practical Session Let us instantiate a stochastic MAB environment with 5 arms with Bernoulli distribu- tion: 1 R = [0.2 0.3 0.7 0.5]; 2 n_arms = length(R); 3 4 for ii = 1:n_arms 5 mathcal_R(ii) = makedist('Binomial','p',R(ii)); 6 labels{ii} = ['a_' num2str(ii)]; 7 end where a Bernoulli distribution is here defined with a Binomial distribution with n = 1. To get a reward at each round from these distributions we resort to the function random() which returns a random sample from the distribution. Consider the following scheme for sequential learning over a time horizon ofT = 1000 rounds: 1 T = 1000; 2 3 N = zeros(1,n_arms); %number of pull for each arm 4 cum_r = zeros(1,n_arms); %cumulated regret for each arm 5 6 %History 7 ind = zeros(T,1); %index of the chosen arm at each step t 8 rewards = zeros(T,1); %rewards gained at each step t 9 10 for tt = 1:T 11 %Arm decision 1 9 Multi-Armed Bandit 12 13 %Reward collection 14 15 %Statistics update 16 17 end and let us implement the UCB1 algorithm and the Thompson Sampling one as specific instance of this scheme. 9.1.1 UCB1 Following the proposed pipeline we need also to store somewhere: • An upper bound for each arm U • The cumulative reward to estimate the empirical mean cum_r In the firstn_arms rounds we need to use a different strategy than the one in the main algorithm, since for the definition of the uncertainty bounds, if we have not pulled an arm its bound is +∞. Here we resort to a round robin initialization, where each arm is pulled in turns. The resulting code is: 1 N = zeros(1,n_arms); 2 U =…