Epsilon Greedy 在少量武器上表现优于 UCB

Question

我正在使用各种算法实现强盗问题。我面临的问题是 epsilon-greedy 对于 5arms 的性能优于 UCB，对于 epsilon 值为 0.95 的 horizon 2000。我知道 epsilon-greedy 在 horizon 与许多武器相当时确实表现更好。但由于我的手臂明显小于 horizon，UCB 应该表现更好。知道为什么会这样吗？我附上了我的 UCB 实现。

else if(algorithm.compare("UCB") == 0){

if(pulls == 0){
  armpullfrequency = new int[numArms];
  armRewards = new float[numArms];
  armmean = new double[numArms];
  UCB = new double[numArms];

  for(int i=0; i<numArms; i++){
    armpullfrequency[i] = 0;
    armRewards[i] = 0.0;
    armmean[i] = (double)0;
    UCB[i] = (double)0;
  }
}

else{

  armpullfrequency[pulled_arm] = armpullfrequency[pulled_arm] + 1;
  armRewards[pulled_arm] = armRewards[pulled_arm] + reward;
}
int selected_arm = 0;
//int randint = (rand() % 100);
if(pulls<=6){
  for(int i=0;i<numArms;i++){
    if(armpullfrequency[i]==0){
      selected_arm = i;
      return selected_arm;
    }
  }
}

for(int i=0;i<numArms;i++){
    int freq = armpullfrequency[i];
    float prize = armRewards[i];
    double mean = eval_mean(freq, prize);
    armmean[i] = mean;
  }

for(int i=0; i<numArms;i++){
  int freq = armpullfrequency[i];
  double mean = armmean[i];
  double UCBval = UCBUpdate(mean, freq, pulls);
  UCB[i] = UCBval;
}

selected_arm = LargestElementIndex(UCB, numArms);
return(selected_arm);

我的 UCB 和 LargestElementIndex 函数是：-

int LargestElementIndex(double arr[], int size){
  int max = 0;
  for(int i=0;i<size; i++){
    if(arr[i]>max){
     max = arr[i];
    }
  }
  return max;
}

int UCBUpdate(double mean, int freq, int pulls){
  double result = mean + sqrt((double)2.0 *(log(pulls))/(double)freq);
  return result;
}

UCB 的结果是：- maxMean 0.5805 numTotalPulls 2000 cumulativeReward 716.308 遗憾 = 444.692

Epsilon Greedy 的结果是：- max 表示 0.5805 numTotalPulls 2000 cumulativeReward 823.948 遗憾=337.052

Answer 1

我怀疑错误在以下代码中：

int LargestElementIndex(double arr[], int size){
  int max = 0;
  for(int i=0;i<size; i++){
    if(arr[i]>max){
     max = arr[i];
    }
  }
  return max;
}

这不是 return 具有最大 UCB 值的手臂的索引（这可能是您想要的）。在将其转换为 int 之后，此代码只是 return 数组本身中最大的 UCB 值。这可能会被修复如下：

int LargestElementIndex(double arr[], int size){
  double max_val = -1000.0;
  int max_idx = -1;
  for(int i=0;i<size; i++){
    if(arr[i]>max_val){
     max_val = arr[i];
     max_idx = i;
    }
  }
  return max_idx;
}

Epsilon Greedy 在少量武器上表现优于 UCB

Epsilon Greedy Performing better than UCB for small number of arms

c++

artificial-intelligence

machine-learning

reinforcement-learning