समस्या
Value iteration solves a Markov decision process: it finds V(s), the best total discounted reward you can collect starting from state s.
Here the transitions are deterministic. In state s, action a gives reward rewards[s][a] and moves to state next_states[s][a], where -1 means the episode ends. Start with V(s) = 0 for every state, then repeat iterations times, computing every new value from the previous sweep:
V_new(s) = max over a of ( rewards[s][a] + gamma × V(next_states[s][a]) )
where the gamma × V term is 0 when the next state is -1.
Implement value_iteration(next_states, rewards, gamma, iterations).
Input
next_states: For each state, the next state of each of its actions (-1 ends the episode). States may have different numbers of actions.
rewards: The reward of each action, with the same shape as next_states.
gamma: The discount factor.
iterations: The number of sweeps.
Output
Return V after the last sweep, one value per state.
सीमाएँ
1 ≤ states ≤ 200, 1 ≤ actions per state ≤ 10, 0 ≤ iterations ≤ 1,000
-100 ≤ each reward ≤ 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};व्याख्या
Sweep 1: only state 2 can collect a reward, V = [0, 0, 10]. Sweep 2: state 1 moves right to it, 0.9 × 10 = 9, V = [0, 9, 10]. Sweep 3: state 0 gets 0.9 × 9 = 8.1. Result: [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};व्याख्या
With gamma = 0 the future does not count, so each state's value is just its best immediate reward: [2, 3].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Every sweep uses only the values from the previous sweep, not updates made earlier in the same pass.
संकेत 2
For each state, compare all actions by combining immediate reward with the discounted value of the next state.
संकेत 3
Handle terminal actions carefully: they contribute only their immediate reward when the next state is missing.
अपेक्षित जटिलता
O(iterations * total_actions) time, O(states) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।