One-Step Bellman Expectation Backup

mediumPROMarkov Decision Processes and Bellman EquationsReinforcement LearningRL 1: Foundations

Problem Statement

Perform a single Bellman expectation backup for one state-action pair, given the current value estimates of the next states:

$Q(s,a) = R(s,a) + \gamma \sum_{s'} P(s'\mid s,a)\, V(s')$

Implement bellman_backup(reward, gamma, probs, values) where probs and values are aligned lists over next states.

Example

Input

bellman_backup(1.0, 0.9, [0.5, 0.5], [10.0, 0.0])

Output

5.5

Reasoning

Compute the expected value of the next states by taking the dot product of the transition probabilities and the corresponding state values: $0.5 \times 10.0 + 0.5 \times 0.0 = 5.0$ .
Scale this expectation by the discount factor $\gamma$ to account for the reduced importance of future rewards: $0.9 \times 5.0 = 4.5$ .
Add the immediate reward to the discounted future value to obtain the total Q-value: $1.0 + 4.5 = 5.5$ .
The final output is 5.5

Constraints

len(probs) == len(values), probs sums to 1.
Return a float.

Learn this in

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 Reinforcement Learning, an agent interacts with an environment modeled as a Markov Decision Process (MDP). The goal is to learn a policy that maximizes expected cumulative reward. Central to this is the Bellman Expectation Equation, which decomposes the value of a state-action pair into two parts: the immediate reward and the discounted expected value of future states.

The Q-function $Q(s,a)$ represents the expected return starting from state $s$ , taking action $a$ , and thereafter following a policy. The V-function $V(s)$ represents the expected return starting from state $s$ and following the policy thereafter. The relationship between them is defined by the Bellman expectation backup:

Q(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) \, V(s')

Here, $R(s,a)$ is the immediate reward, $\gamma \in [0,1]$ is the discount factor (balancing immediate vs. future rewards), $P(s' \mid s,a)$ is the transition probability to next state $s'$ , and $V(s')$ is the current value estimate of that next state. This equation is the foundation of value iteration, policy iteration, and Q-learning.

A Bellman backup is a single update step: given current estimates of $V(s')$ for all possible next states, compute a new (or updated) estimate of $Q(s,a)$ . This is distinct from a Bellman optimality backup, which would take the $\max$ over actions. Here, we are performing an expectation backup—averaging over the distribution of next states weighted by their transition probabilities.

2. Algorithm Approach

The problem reduces to computing a weighted sum (expectation) over the next states, then adding the immediate reward and discounting appropriately.

The core operation is:

Compute the expected next-state value: $\sum_{i} P_i \cdot V_i$ , where $P_i$ and $V_i$ are the $i$ -th elements of probs and values.
Multiply by the discount factor $\gamma$ .
Add the immediate reward $R(s,a)$ .

This is essentially a dot product between the probability vector and the value vector, scaled by $\gamma$ , plus the reward. No iterative or recursive computation is needed—this is a single, closed-form update.

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