我正在从这里翻译多臂强盗的 epsilon-greedy 算法。这是对 Rcpp 的强大和优雅的一个很好的展示。但是，此版本的结果与上面链接中提到的结果不符。我知道这可能是一个非常小众的问题，但没有其他地方可以发布这个！
代码摘要如下。基本上，我们有一组手臂，每个手臂都以预定义的概率支付奖励，我们的工作是证明，通过从手臂中随机抽取，同时间歇性地抽取具有最佳奖励的手臂，最终可以让我们收敛到最好的手臂上。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）如下：
显然，尽管奖励很低，但第一只手臂的选择不成比例！到底是怎么回事？
