문제
가치 반복은 마르코프 결정 과정을 풉니다. 상태 s에서 시작해 얻을 수 있는 최선의 할인된 보상 합 V(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]) )의 최댓값
단, 다음 상태가 -1이면 gamma × V 항은 0입니다.
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].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
매 스윕은 같은 패스에서 앞서 갱신한 값이 아니라, 이전 스윕의 값만 사용합니다.
힌트 2
각 상태에서 즉시 보상과 할인된 다음 상태 값을 합쳐 모든 행동을 비교하세요.
힌트 3
종단 행동은 다음 상태가 없으면 즉시 보상만 기여하도록 처리하세요.
예상 복잡도
시간 O(iterations * total_actions), 추가 공간 O(states)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.