One-Step Bellman Expectation Backup
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)+γ∑s′P(s′∣s,a)V(s′)
Implement bellman_backup(reward, gamma, probs, values) where probs and values are aligned lists over next states.
Example:
bellman_backup(1.0, 0.9, [0.5, 0.5], [10.0, 0.0])
5.5
- Compute the expected value of the next states by taking the dot product of the transition probabilities and the corresponding state values: 0.5×10.0+0.5×0.0=5.0.
- Scale this expectation by the discount factor γ to account for the reduced importance of future rewards: 0.9×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.
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)+γs′∑P(s′∣s,a)V(s′)Here, R(s,a) is the immediate reward, γ∈[0,1] is the discount factor (balancing immediate vs. future rewards), P(s′∣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: ∑iPi⋅Vi, where Pi and Vi are the i-th elements of probs and values.
- Multiply by the discount factor γ.
- Add the immediate reward R(s,a).
This is essentially a dot product between the probability vector and the value vector, scaled by γ, plus the reward. No iterative or recursive computation is needed—this is a single, closed-form update.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.