Problems

1 / 1

Value Iteration Step

Reinforcement Learning

Medium

Perform one value-iteration update for a Markov decision process. For every state, evaluate each action using its immediate reward and expected discounted next-state value, then keep the best action value.

V_{\mathrm{new}}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} T(s,a,s')V(s') \right]

Here:

$s$ is the current state and $s'$ is a possible next state
$a$ is an available action
$R(s,a)$ is the immediate reward
$T(s,a,s')$ is the probability of transitioning to $s'$
$V(s')$ is the current value estimate
$\gamma$ is the discount factor

Return the updated value of every state as a list of floats.

Loading visualization...

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]

Explanation: With zero current values, only immediate rewards contribute, so the best rewards are 2 and 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]

Hint 1

sum(probability * value for probability, value in zip(action_transitions, values)) computes one expected next-state value.

Hint 2

Use max() over the action values computed for each state.

Requirements

values contains one current value for every state
transitions has shape $(S, A, S)$ and rewards has shape $(S, A)$
Use the supplied transition probabilities, rewards, and discount factor without modifying them
Return a list of $S$ updated floating-point values

Constraints

The process contains at least one state and one action
Every transition-probability row sums to 1
$0 \leq \gamma \leq 1$

Try Similar Problems

Q Learning Update Sarsa Update Td Value Update Mc Policy Evaluation Discount Returns

Prev Next

Value Iteration Step

Reinforcement Learning

Medium

V_{\mathrm{new}}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} T(s,a,s')V(s') \right]

Here:

$s$ is the current state and $s'$ is a possible next state
$a$ is an available action
$R(s,a)$ is the immediate reward
$T(s,a,s')$ is the probability of transitioning to $s'$
$V(s')$ is the current value estimate
$\gamma$ is the discount factor

Return the updated value of every state as a list of floats.

Loading visualization...

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]

Explanation: With zero current values, only immediate rewards contribute, so the best rewards are 2 and 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]

Hint 1

sum(probability * value for probability, value in zip(action_transitions, values)) computes one expected next-state value.

Hint 2

Use max() over the action values computed for each state.

Requirements

values contains one current value for every state
transitions has shape $(S, A, S)$ and rewards has shape $(S, A)$
Use the supplied transition probabilities, rewards, and discount factor without modifying them
Return a list of $S$ updated floating-point values

Constraints

The process contains at least one state and one action
Every transition-probability row sums to 1
$0 \leq \gamma \leq 1$

Try Similar Problems

Q Learning Update Sarsa Update Td Value Update Mc Policy Evaluation Discount Returns

Case 1

Case 2

values =

Accepts: array

transitions =

Accepts: array

rewards =

Accepts: array

gamma =

Accepts: number