Value Iteration Step
Value Iteration Step
Value iteration is a dynamic programming algorithm that computes the optimal value function for a Markov Decision Process (MDP). Each step applies the Bellman optimality equation: for every state, consider all possible actions, compute the expected value of each action using the transition probabilities, and take the maximum.
Given the current value estimates, transition probabilities, rewards, and a discount factor, perform one step of value iteration and return the updated values.
Algorithm
For each state s, compute:
V′(s)=amax[R(s,a)+γs′∑T(s,a,s′)⋅V(s′)]Where:
- R(s, a) is the immediate reward for taking action a in state s
- T(s, a, s') is the probability of transitioning to state s' given state s and action a
- V(s') is the current value estimate for state s'
Examples
Input:
values = [0, 0], transitions = [[[0.8, 0.2], [0.3, 0.7]], [[0.5, 0.5], [0.1, 0.9]]], rewards = [[1, 2], [-1, 0]], gamma = 0.9
Output:
[2.0, 0.0]
State 0: Q(0,a0) = 1 + 0.9*(0.80 + 0.20) = 1, Q(0,a1) = 2 + 0.9*(0.30 + 0.70) = 2. V'(0) = max(1, 2) = 2. State 1: Q(1,a0) = -1 + 0 = -1, Q(1,a1) = 0 + 0 = 0. V'(1) = max(-1, 0) = 0.
Input:
values = [0, 0, 0], transitions = [[[0,1,0],[0,0,1]], [[1,0,0],[0,0,1]], [[0,1,0],[1,0,0]]], rewards = [[1,2],[3,0],[-1,5]], gamma = 0.9
Output:
[2.0, 3.0, 5.0]
With all values at 0, the future value terms vanish and V'(s) = max over immediate rewards. State 0: max(1, 2) = 2. State 1: max(3, 0) = 3. State 2: max(-1, 5) = 5.
Hint 1
Use three nested loops: outer loop over states s, middle loop over actions a, inner loop over next states s_next. For each (s, a), compute q = rewards[s][a] + gamma * sum(transitions[s][a][s_next] * values[s_next] for all s_next). Track the max q across actions.
Hint 2
Initialize best = negative infinity for each state before looping over actions. After the action loop, append best to the new values list.
Requirements
- For each state, compute Q(s, a) = R(s, a) + gamma * sum over s' of T(s, a, s') * V(s')
- Take the max over all actions to get the new value
- Return a list of updated values with the same length as the input values
Constraints
- values has at least one element
- transitions[s][a][s'] gives the transition probability (rows sum to 1)
- rewards[s][a] gives the immediate reward
- 0 <= gamma <= 1
- Return a list of floats with the same length as values
- Time limit: 300 ms
Try Similar Problems
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array
Accepts: number
Value Iteration Step
Value Iteration Step
Value iteration is a dynamic programming algorithm that computes the optimal value function for a Markov Decision Process (MDP). Each step applies the Bellman optimality equation: for every state, consider all possible actions, compute the expected value of each action using the transition probabilities, and take the maximum.
Given the current value estimates, transition probabilities, rewards, and a discount factor, perform one step of value iteration and return the updated values.
Algorithm
For each state s, compute:
V′(s)=amax[R(s,a)+γs′∑T(s,a,s′)⋅V(s′)]Where:
- R(s, a) is the immediate reward for taking action a in state s
- T(s, a, s') is the probability of transitioning to state s' given state s and action a
- V(s') is the current value estimate for state s'
Examples
Input:
values = [0, 0], transitions = [[[0.8, 0.2], [0.3, 0.7]], [[0.5, 0.5], [0.1, 0.9]]], rewards = [[1, 2], [-1, 0]], gamma = 0.9
Output:
[2.0, 0.0]
State 0: Q(0,a0) = 1 + 0.9*(0.80 + 0.20) = 1, Q(0,a1) = 2 + 0.9*(0.30 + 0.70) = 2. V'(0) = max(1, 2) = 2. State 1: Q(1,a0) = -1 + 0 = -1, Q(1,a1) = 0 + 0 = 0. V'(1) = max(-1, 0) = 0.
Input:
values = [0, 0, 0], transitions = [[[0,1,0],[0,0,1]], [[1,0,0],[0,0,1]], [[0,1,0],[1,0,0]]], rewards = [[1,2],[3,0],[-1,5]], gamma = 0.9
Output:
[2.0, 3.0, 5.0]
With all values at 0, the future value terms vanish and V'(s) = max over immediate rewards. State 0: max(1, 2) = 2. State 1: max(3, 0) = 3. State 2: max(-1, 5) = 5.
Hint 1
Use three nested loops: outer loop over states s, middle loop over actions a, inner loop over next states s_next. For each (s, a), compute q = rewards[s][a] + gamma * sum(transitions[s][a][s_next] * values[s_next] for all s_next). Track the max q across actions.
Hint 2
Initialize best = negative infinity for each state before looping over actions. After the action loop, append best to the new values list.
Requirements
- For each state, compute Q(s, a) = R(s, a) + gamma * sum over s' of T(s, a, s') * V(s')
- Take the max over all actions to get the new value
- Return a list of updated values with the same length as the input values
Constraints
- values has at least one element
- transitions[s][a][s'] gives the transition probability (rows sum to 1)
- rewards[s][a] gives the immediate reward
- 0 <= gamma <= 1
- Return a list of floats with the same length as values
- Time limit: 300 ms
Try Similar Problems
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array
Accepts: number