2
\$\begingroup\$

I am learning about reinforcement learning and came across the first and simplest form of reinforcement learning system called multi-armed reinforcement learning (also called as n-armed bandit). I have read Sutton's book and an outlace.com tutorial regarding this learning. Outlace.com has written a nice Python implementation of this learning which I rewrote as an R program.

#multi/n-armed bandit algorithm with greedy search
#original code http://outlace.com/Reinforcement-Learning-Part-1/

iter=500
n=10
arms=runif(n)
eps=0.1
av=rep.int(1,n)
counts=rep.int(0,n)

#reward function
reward<-function(prob){
  reward=0
  for (i in 1:100){
    if(runif(1)<prob){
      reward=reward+1
    }
    return(reward)
  }
}

bestArm<-function(a){
  return(max(a))
}

runMean=NULL
for (i in 1:iter){
  if(runif(1) > eps){    
    # exploitation!(use best arm)
    choice=bestArm(av)
    counts[choice]=counts[choice]+1
    k = counts[choice]
    #reward for n arms
    rwd =  reward(arms[choice])    
    old_avg = av[choice]
    new_avg = old_avg + (1/k)*(rwd - old_avg) #update running avg
    av[choice] = new_avg

  }else{
    # exploration!(test all arm)
    # choose a random lever 10% of the time.  

    #randomly chose an arm
    choice=sample(arms,1)    
    counts[choice]=counts[choice]+1
    old_avg = av[choice]
    new_avg = old_avg + (1/k)*(rwd - old_avg) #update running avg
    av[choice] = new_avg
  }
  runMean[i]=mean(av)  
}
plot(runMean)

I don't know whether the output is correct because I don't understand some parts of the code and just copy pasted it.

Python

choice = bestArm(av)
counts[choice] += 1
k = counts[choice]
rwd =  reward(arms[choice])
old_avg = av[choice]
new_avg = old_avg + (1/k)*(rwd - old_avg) #update running avg
av[choice] = new_avg

R

choice=bestArm(av)
counts[choice]=counts[choice]+1
k = counts[choice]
#reward for n arms
rwd =  reward(arms[choice])    
old_avg = av[choice]
new_avg = old_avg + (1/k)*(rwd - old_avg) #update running avg
av[choice] = new_avg

It runs and doesn't show any errors even after using most of the original Python code.

\$\endgroup\$
2
\$\begingroup\$

There were quite a few things wrong with your implementation:

  • In both the if and else parts, choice ended up being a numeric (a non-integer, e.g. 0.6532) when it should be an integer. The problem was that a) you where using max instead of which.max inside bestArm and b) randomly picking a value from arms instead of its index.
  • Inside the else part, you were using k and rwd without setting them.
  • your computation of the running mean was not using weights as the python implementation does
  • This won't have a significant impact, but I think the python implementation had an issue: the observed mean rewards av should be initialized to zero, not one.

Here are other improvements I would suggest:

  • The if/else should be limited to the picking of the choice index. Everything else should be moved after the if/else as to not repeat code. This was a problem from the original python implementation you pointed to.
  • Instead of writing a script, you should write a function. It is a good way to isolate the inputs and outputs of your program, it gives you an easy way to test with different input parameters, to share your code, etc.
  • use spaces to make your code easier on the eyes. Spaces also avoid ambiguous situations for people who are not experts in R's syntax rules; for example, when someone sees a<-b, is it assigning b to a, or is it asking if a is less than -b? Maybe another way to convince you is to make you notice that R's compiled code does contain spaces (run print(lapply) for example); it shows that R's authors agreed that code readability was more important than compactness.
  • If you are slowly building a vector (runMean) and know in advance its final length, initialize it with that exact length: runMean <- rep(NA, iter). Otherwise, at each iteration R will have to create a longer object and this will significantly slow down your code for any large number of iterations.

So the code could look like this:

n.armed.bandit.sim <- function(iter = 500, n = 10, eps = 0.1, max.reward = 100) {

  arms <- runif(n)
  av <- rep(0, n)
  counts <- rep(0L, n)

  reward  <- function(prob) sum(runif(max.reward) < prob)
  bestArm <- which.max

  runMean <- rep(NA, iter)
  for (i in seq_len(iter)) {
    choice <- if(runif(1) > eps) bestArm(av) else sample(n, 1) 
    counts[choice] <- counts[choice] + 1L
    k <- counts[choice]
    rwd <- reward(arms[choice])    
    old_avg <- av[choice]
    new_avg <- old_avg + (1 / k) * (rwd - old_avg)
    av[choice] <- new_avg
    runMean[i] <- weighted.mean(av, counts / sum(counts))
  }
  plot(runMean)
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.