問題
価値反復法はマルコフ決定過程を解きます。状態 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 つずつ返します。
制約
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用に調整されています。上記の説明と制約に従ってください。