문제
멀티암드 밴딧은 지급액을 모르는 슬롯머신 (암)이 늘어선 것입니다. 엡실론-그리디는 탐험과 활용의 균형을 맞춥니다. 확률 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].
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.