Итерация по ценностям решает марковский процесс принятия решений: она находит V(s) — наибольшую суммарную дисконтированную награду, которую можно получить, начиная из состояния s.
Здесь переходы детерминированы. В состоянии s действие a даёт награду rewards[s][a] и ведёт в состояние next_states[s][a], где -1 означает конец эпизода. Начните с V(s) = 0 для каждого состояния и повторите iterations раз, вычисляя каждое новое значение по предыдущему проходу:
V_new(s) = максимум по a от ( rewards[s][a] + gamma × V(next_states[s][a]) )
где слагаемое gamma × V равно 0, если следующее состояние равно -1.
Реализуйте value_iteration(next_states, rewards, gamma, iterations).
Входные данные
next_states: Для каждого состояния — следующее состояние каждого из его действий (-1 завершает эпизод). У состояний может быть разное число действий.
rewards: Награда за каждое действие, той же формы, что и next_states.
gamma: Коэффициент дисконтирования.
iterations: Число проходов.
Выходные данные
Верните V после последнего прохода, по одному значению на состояние.
Ограничения
1 ≤ состояния ≤ 200, 1 ≤ действия на состояние ≤ 10, 0 ≤ iterations ≤ 1 000
-100 ≤ каждая награда ≤ 100, 0 ≤ gamma ≤ 1
Примеры
Ввод:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Ожидаемый вывод:
expected = [8.1, 9.0, 10.0]Ввод:
double gamma = 0.9;
std::vector<std::vector<double>> rewards = {
{0.0, 0.0},
{0.0, 0.0},
{10.0}
};
long long iterations = 3;
std::vector<std::vector<long long>> next_states = {
{0, 1},
{0, 2},
{-1}
};
Ожидаемый вывод:
std::vector<double> expected = {8.1, 9.0, 10.0};Ввод:
double gamma = 0.9;
double[][] rewards = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 0.0},
new double[] {10.0}
};
long iterations = 3;
long[][] next_states = new long[][] {
new long[] {0, 1},
new long[] {0, 2},
new long[] {-1}
};
Ожидаемый вывод:
double[] expected = new double[] {8.1, 9.0, 10.0};Пояснение
Проход 1: награду может получить только состояние 2, V = [0, 0, 10]. Проход 2: состояние 1 идёт вправо к нему, 0.9 × 10 = 9, V = [0, 9, 10]. Проход 3: состояние 0 получает 0.9 × 9 = 8.1. Результат: [8.1, 9, 10].
Ввод:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
Ожидаемый вывод:
expected = [2.0, 3.0]Ввод:
double gamma = 0.0;
std::vector<std::vector<double>> rewards = {
{1.0, 2.0},
{3.0, 0.0}
};
long long iterations = 5;
std::vector<std::vector<long long>> next_states = {
{1, 0},
{0, 1}
};
Ожидаемый вывод:
std::vector<double> expected = {2.0, 3.0};Ввод:
double gamma = 0.0;
double[][] rewards = new double[][] {
new double[] {1.0, 2.0},
new double[] {3.0, 0.0}
};
long iterations = 5;
long[][] next_states = new long[][] {
new long[] {1, 0},
new long[] {0, 1}
};
Ожидаемый вывод:
double[] expected = new double[] {2.0, 3.0};Пояснение
При gamma = 0 будущее не учитывается, поэтому ценность каждого состояния — просто его лучшая немедленная награда: [2, 3].
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.