問題
多腕バンディットは、払い戻しのわからないスロットマシン (アーム) の列です。ε-greedy は探索と活用のバランスを取ります。確率 epsilon でランダムなアームを引き、それ以外は推定価値が最も高いアームを引きます。
テストできるように、乱数は与えられます。すべてのアームについて推定値 Q = 0、回数 N = 0 から始めます。各ステップ t で:
random_values[t]< epsilon なら探索: arm =random_arms[t]。そうでなければ活用: arm = Q が最も高いアーム (同点なら最も小さいインデックス)。- reward =
rewards[t][arm]を受け取ります。 - N[arm] ← N[arm] + 1、Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm] (逐次平均)。
epsilon_greedy(rewards, epsilon, random_values, random_arms) を実装してください。
入力
rewards: 1 ステップにつき 1 行で、そのステップに各アームが払う報酬。
epsilon: 探索する確率。
random_values: ステップごとの [0, 1) の乱数。
random_arms: 探索する場合に各ステップで引くアーム。
出力
最終的な推定値 Q をアームごとに 1 つずつ返します。
制約
1 ≤ ステップ数 ≤ 10,000、1 ≤ アーム数 ≤ 100
0 ≤ epsilon ≤ 1、-100 ≤ 各報酬 ≤ 100
例
入力：
epsilon = 0.1
rewards = [
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0]
]
random_arms = [0, 1, 0, 0]
random_values = [0.5, 0.05, 0.7, 0.9]
期待される出力：
expected = [1.0, 3.0]入力：
double epsilon = 0.1;
std::vector<std::vector<double>> rewards = {
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0}
};
std::vector<long long> random_arms = {0, 1, 0, 0};
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
期待される出力：
std::vector<double> expected = {1.0, 3.0};入力：
double epsilon = 0.1;
double[][] rewards = new double[][] {
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0}
};
long[] random_arms = new long[] {0, 1, 0, 0};
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
期待される出力：
double[] expected = new double[] {1.0, 3.0};解説
ステップ 0 は活用します。Q はどちらも 0 なのでアーム 0 を引き、Q = [1, 0]。ステップ 1 は探索 (0.05 < 0.1) でアーム 1 を試し、Q = [1, 3]。ステップ 2 と 3 はより良いアーム 1 を活用します。結果: [1, 3]。
入力：
epsilon = 0.0
rewards = [
[2.0, 5.0],
[4.0, 5.0],
[0.0, 5.0]
]
random_arms = [1, 1, 1]
random_values = [0.5, 0.5, 0.5]
期待される出力：
expected = [2.0, 0.0]入力：
double epsilon = 0.0;
std::vector<std::vector<double>> rewards = {
{2.0, 5.0},
{4.0, 5.0},
{0.0, 5.0}
};
std::vector<long long> random_arms = {1, 1, 1};
std::vector<double> random_values = {0.5, 0.5, 0.5};
期待される出力：
std::vector<double> expected = {2.0, 0.0};入力：
double epsilon = 0.0;
double[][] rewards = new double[][] {
new double[] {2.0, 5.0},
new double[] {4.0, 5.0},
new double[] {0.0, 5.0}
};
long[] random_arms = new long[] {1, 1, 1};
double[] random_values = new double[] {0.5, 0.5, 0.5};
期待される出力：
double[] expected = new double[] {2.0, 0.0};解説
epsilon = 0 ではエージェントは決して探索しません。アーム 0 を引き続け、平均は 2 → 3 → 2 と変わり、アーム 1 が 5 を払うことに気づきません。結果: [2, 0]。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
各 step で、強制ランダムな arm か、今いちばん良い推定の arm を選ぶ。
ヒント 2
各 arm の値は running average で更新し、試行回数が増えるほど古い報酬の影響を弱める。
ヒント 3
同値なら index が最小の arm を選び、各 step で変わるのは選ばれた arm だけだと覚えておく。
目安の計算量
時間 O(steps * arms)、追加メモリ O(arms)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。