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

Question

我正在使用各种算法实现强盗问题。我面临的问题是 epsilon-greedy 在 5 个臂和 2000 年的 epsilon 值为 0.95 时比 UCB 表现更好。我知道本地平线与许多武器相当时，epsilon-greedy 确实表现得更好。但由于我的 ARM 明显小于地平线，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;
}

这不会返回具有最大 UCB 值的 ARM 的索引(这可能是您想要的)。此代码在将其转换为 int 后，简单地返回数组本身中的最大 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;
}