問題
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: 1 ステップにつき 1 行の [state, action, reward, next_state, done]。
alpha: 学習率。
gamma: 割引率。
出力
状態ごとに 1 行、行動ごとに 1 列の行列として 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 のままです。2 番目のステップは報酬 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 つ前の状態へ伝わりました。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
各遷移は、現在値と次状態の最良推定だけを使って表の1項目を更新する。
ヒント 2
Q テーブルは 0 で初期化し、遷移を順に処理して各回すぐ更新する。
ヒント 3
エピソードが終わったら未来価値は足さず、次状態の最大値も使わない。
目安の計算量
時間 O(T * A)、追加メモリ O(S * A)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。