Q-learning учится только на опыте, насколько хорошо каждое действие в каждом состоянии, Q(s, a). После действия a в состоянии s, получения reward и перехода в состояние s':
- target = reward, если эпизод закончился (
done= 1) - target = reward + gamma × максимум по a' от Q(s', a'), иначе
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Начните со всех значений Q, равных 0, и применяйте переходы по порядку.
Реализуйте q_learning(num_states, num_actions, transitions, alpha, gamma).
Входные данные
num_states, num_actions: Размер таблицы.
transitions: По одной строке [state, action, reward, next_state, done] на шаг.
alpha: Скорость обучения.
gamma: Коэффициент дисконтирования.
Выходные данные
Верните таблицу Q в виде матрицы с одной строкой на состояние и одним столбцом на действие.
Ограничения
1 ≤ num_states, num_actions ≤ 100, 0 ≤ число переходов ≤ 10 000
-100 ≤ reward ≤ 100, done равно 0 или 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Примеры
Ввод:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Ожидаемый вывод:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Ввод:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{0, 1, 0, 1, 0},
{1, 0, 10, 0, 1}
};
Ожидаемый вывод:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Ввод:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {0, 1, 0, 1, 0},
new long[] {1, 0, 10, 0, 1}
};
Ожидаемый вывод:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Пояснение
На первом шаге награды ещё нет: target = 0 + 0.9 × max(Q[1]) = 0, поэтому Q[0][1] остаётся 0. Второй шаг завершает эпизод с наградой 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5.
Ввод:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Ожидаемый вывод:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Ввод:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{1, 0, 10, 0, 1},
{0, 1, 0, 1, 0}
};
Ожидаемый вывод:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Ввод:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {1, 0, 10, 0, 1},
new long[] {0, 1, 0, 1, 0}
};
Ожидаемый вывод:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Пояснение
Те же шаги в обратном порядке. Q[1][0] сначала становится 5, поэтому шаг из состояния 0 его видит: target = 0 + 0.9 × 5 = 4.5 и Q[0][1] = 0.5 × 4.5 = 2.25. Награда распространилась на одно состояние назад.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Каждый переход обновляет одну ячейку таблицы, используя только её текущее значение и лучшую оценку из следующего состояния.
Подсказка 2
Инициализируйте Q-таблицу нулями, затем обрабатывайте переходы по порядку и сразу обновляйте после каждого.
Подсказка 3
Если эпизод закончился, будущего значения нет, и максимум по следующему состоянию не используется.
Ожидаемая сложность
время O(T * A), доп. память O(S * A)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.