문제
Q-러닝은 각 상태에서 각 행동이 얼마나 좋은지, 즉 Q(s, a)를 경험만으로 학습합니다. 상태 s에서 행동 a를 하고 reward를 받은 뒤 상태 s'에 도착하면:
- 에피소드가 끝났다면 (
done= 1) target = reward - 그렇지 않으면 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 테이블은 0으로 초기화하고, 전이를 순서대로 처리하며 매번 즉시 업데이트하세요.
힌트 3
에피소드가 끝나면 더할 미래 값이 없으므로, 다음 상태의 최대값은 쓰지 않습니다.
예상 복잡도
시간 O(T * A), 추가 공간 O(S * A)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.