Bellman Optimality Backup

mediumPROMarkov Decision Processes and Bellman EquationsReinforcement LearningRL 1: Foundations

Problem Statement

The Bellman optimality backup takes a max over actions instead of a policy average:

$V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'\mid s,a)\, V(s') \right]$

You are given, for one state, a list of actions. Each action is a dict {"reward": r, "probs": [...], "values": [...]}. Return the optimal state value. Implement bellman_optimality(actions, gamma).

Example

Input

bellman_optimality([{"reward":1.0,"probs":[1.0],"values":[0.0]},{"reward":0.0,"probs":[1.0],"values":[10.0]}], 0.9)

Output

9.0

Reasoning

Evaluate the first action by combining its immediate reward with the discounted expected value of the next state: $Q_1 = 1.0 + 0.9 \times (1.0 \times 0.0) = 1.0$ .
Evaluate the second action similarly, noting that it has no immediate reward but leads to a high-value state with certainty: $Q_2 = 0.0 + 0.9 \times (1.0 \times 10.0) = 9.0$ .
Apply the optimality principle by selecting the maximum Q-value among all available actions to determine the optimal state value: $\max(1.0, 9.0) = 9.0$ .
The final output is 9.0

Constraints

1 <= len(actions) <= 1000
Each action's probs sum to 1 and align with values.
Return the max backed-up value (a float).

Learn this in

Reinforcement LearningML Study Plan Markov Decision ProcessesReinforcement Learning Dynamic ProgrammingReinforcement Learning

More from RL 1: Foundations

GAE Over a Full Trajectoryhard PPO Clipped Objective (Single Sample)medium TD Residuals for GAEmedium Return Standardization Baselinemedium REINFORCE Loss Termmedium

Concept primerPREVIEW

1. Background Knowledge

In Markov Decision Processes (MDPs), the value of a state represents the expected cumulative reward an agent can achieve starting from that state. While a fixed policy $\pi$ defines how actions are chosen, the optimal value function $V^*(s)$ assumes the agent always picks the best possible action at every step. This leads to the Bellman optimality equation, which expresses $V^*(s)$ as the maximum over all actions of the immediate reward plus the discounted expected value of successor states.

The key distinction from the standard Bellman expectation backup is the use of $\max_a$ instead of a weighted average over actions. For each action $a$ , you compute the expected next-state value as $\sum_{s'} P(s' \mid s,a) \, V(s')$ , add the immediate reward $R(s,a)$ , discount by $\gamma$ , and then take the maximum across all actions. This "backup" operation is fundamental in dynamic programming algorithms like value iteration, where it is applied repeatedly until convergence.

The parameter $\gamma \in [0, 1)$ is the discount factor, which controls how much future rewards are valued relative to immediate ones. When $\gamma = 0$ , only the immediate reward matters; as $\gamma \to 1$ , the agent becomes more long-term focused. The probabilities in probs must sum to 1 for each action, and the values array contains the known value estimates for each possible successor state.

2. Algorithm Approach

This problem follows a straightforward evaluate-and-maximize pattern:

For each action in the list, compute the expected next-state value by taking the dot product of the probability distribution and the successor state values.
Add the immediate reward and apply the discount factor to the expected value.
Track the maximum Q-value across all actions.
Return that maximum as the optimal state value.

No iterative solving is needed here because the successor state values are already provided — this is a single backup step, not a full value iteration loop.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results