使用 Rcpp 的多臂强盗

Question

我正在翻译 here 的多臂强盗的 epsilon-greedy 算法。这是对 Rcpp 强大而优雅的一个很好的展示。但是，此版本的结果与上面 link 中提到的结果不一致。我知道这可能是一个非常小众的问题，但没有其他地方可以 post 这个！

代码总结如下。基本上，我们有一组手臂，每只手臂都以预定义的概率支付奖励，我们的工作是表明，通过随机抽取手臂，同时间歇性地抽取具有最佳奖励的手臂，最终可以让我们收敛在最好的手臂上。 John Myles White 提供了对该算法的一个很好的解释。

现在，到代码：

#include <Rcpp.h>

using namespace Rcpp;

// [[Rcpp::depends(RcppArmadillo)]]
// [[Rcpp::plugins(cpp11)]]

struct EpsilonGreedy {
  double epsilon;
  std::vector<int> counts;
  std::vector<double> values;
};

int index_max(std::vector<double>& v) {
  return std::distance(v.begin(), std::max_element(v.begin(), v.end()));
}

int index_rand(std::vector<double>& v) {
  return R::runif(0, v.size()-1);
}

int select_arm(EpsilonGreedy& algo) {
  if (R::runif(0, 1) > algo.epsilon) {
    return index_max(algo.values);
  } else {
    return index_rand(algo.values);
  }
}

void update(EpsilonGreedy& algo, int chosen_arm, double reward) {
  algo.counts[chosen_arm] += 1;

  int n = algo.counts[chosen_arm];
  double value = algo.values[chosen_arm];

  algo.values[chosen_arm] = ((n-1)/n) * value + (1/n) * reward;
}

struct BernoulliArm {
  double p;
};

int draw(BernoulliArm arm) {
  if (R::runif(0, 1) > arm.p) {
    return 0;
  } else {
    return 1;
  }
}

// [[Rcpp::export]]
DataFrame test_algorithm(double epsilon, std::vector<double>& means, int n_sims, int horizon) {

  std::vector<BernoulliArm> arms;

  for (auto& mu : means) {
    BernoulliArm b = {mu};
    arms.push_back(b);
  }

  std::vector<int> sim_num, time, chosen_arms;
  std::vector<double> rewards;

  for (int sim = 1; sim <= n_sims; ++sim) {

    std::vector<int> counts(means.size(), 0);
    std::vector<double> values(means.size(), 0.0); 

    EpsilonGreedy algo = {epsilon, counts, values};

    for (int t = 1; t <= horizon; ++t) {
      int chosen_arm = select_arm(algo);
      double reward = draw(arms[chosen_arm]);
      update(algo, chosen_arm, reward);

      sim_num.push_back(sim);
      time.push_back(t);
      chosen_arms.push_back(chosen_arm);
      rewards.push_back(reward);
    }
  }

  DataFrame results = DataFrame::create(Named("sim_num") = sim_num,
                                        Named("time") = time,
                                        Named("chosen_arm") = chosen_arms,
                                        Named("reward") = rewards);

  return results;
}

/***R

means <- c(0.1, 0.1, 0.1, 0.1, 0.9)
results <- test_algorithm(0.1, means, 5000, 250) 

p2 <- ggplot(results) + geom_bar(aes(x = chosen_arm)) + theme_bw()
*/

模拟过程中选择的手臂图（即上面的图p2）如下：

显然，尽管奖励很低，但第一只手臂的选择比例偏高！这是怎么回事？

Answer 1

我不知道 bandits 应该如何工作，但一些标准调试（即：查看生成的值）表明您生成了很多零。

修复一些基本错误后（让你的 C/C++ 循环 for (i=0; i<N; ++) 即从零开始并与 less-than 进行比较）我们留下了其他不太细微的错误，例如 runif(1,N) 强制转换为 int 不会为您提供 N 个值的相等范围（提示：添加 0.5 并四舍五入并强制转换，或者从 1..N 整数集合中采样一个整数）。

但罪魁祸首似乎是您的第一个参数 epsilon。只需将其设置为 0.9 即可得到如下图表，其中您仍然存在最后一个 'half' 单元丢失的问题。

使用 Rcpp 的多臂强盗

Multi-armed bandits with Rcpp

std

rcpp

rcpp11