Многорукий бандит — это ряд игровых автоматов (рук) с неизвестными выплатами. Эпсилон-жадная стратегия балансирует исследование и использование: с вероятностью 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: По одной строке на шаг с наградой, которую каждая рука выплатила бы на этом шаге.
epsilon: Вероятность исследования.
random_values: По одному случайному числу в [0, 1) на шаг.
random_arms: Рука, которую нужно дёрнуть на каждом шаге при исследовании.
Выходные данные
Верните итоговые оценки Q, по одной на руку.
Ограничения
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
На каждом шаге выбирайте либо принудительно случайную руку, либо текущую лучшую по оценке.
Подсказка 2
Обновляйте значение каждой руки через бегущее среднее, чтобы старые награды влияли меньше по мере роста числа выборов.
Подсказка 3
При равенстве выбирайте руку с меньшим индексом и помните, что на каждом шаге меняется только выбранная рука.
Ожидаемая сложность
время O(steps * arms), доп. память O(arms)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.