One Sweep of Iterative Policy Evaluation
Problem Statement
Perform one synchronous sweep of iterative policy evaluation over all states, given the induced transition matrix P (P[s][s']) and reward vector r:
Vk+1​(s)=r(s)+γ∑s′​P(s′∣s)Vk​(s′)
Given the current values V, return the updated values after one sweep (use the old V for all right-hand sides — synchronous). Implement policy_eval_sweep(P, r, gamma, V).
Example:
policy_eval_sweep([[1.0]], [1.0], 0.9, [0.0])
[1.0]
- Identify the single state s=0 and retrieve its parameters: transition probability P[0][0]=1.0, reward r[0]=1.0, discount factor γ=0.9, and current value V[0]=0.0.
- Calculate the expected value of the next state by summing the products of transition probabilities and current values: E[Vnext​]=P[0][0]×V[0]=1.0×0.0=0.0.
- Apply the Bellman update equation to compute the new value for state 0: Vnew​(0)=r[0]+γ×E[Vnext​]=1.0+0.9×0.0=1.0.
- The final output is [1.0]
Constraints:
Pisn x n(rows sum to 1),randVlengthn.- Synchronous update: every state uses the same input
V. - Return a list of
nfloats.
1. Background Knowledge
Iterative Policy Evaluation is a core algorithm in reinforcement learning used to estimate the value function Vπ(s) for a fixed policy π. The value function represents the expected cumulative discounted return starting from state s and following policy π thereafter. The relationship between values of consecutive states is governed by the Bellman equation, which expresses the value of a state as the immediate reward plus the discounted expected value of successor states.
The update rule provided in the problem is a single application of the Bellman operator. In a synchronous sweep, every state's value is updated simultaneously using the old values from the previous iteration k. This contrasts with an asynchronous (or Gauss-Seidel) update, where newly computed values are immediately used for subsequent states in the same sweep. Synchronous updates are mathematically cleaner and easier to parallelize, though they may converge slightly slower in practice. The discount factor γ∈[0,1) ensures the series of future rewards converges, preventing infinite accumulation in episodic or continuing tasks.
The transition matrix P encodes the environment dynamics: P[s][s′] is the probability of transitioning to state s′ from state s under the current policy. The reward vector r provides the immediate scalar reward for each state. Together, these define the Markov Decision Process (MDP) that the value function is being evaluated for.
2. Algorithm Approach
The problem requires implementing a vectorized Bellman backup. The general approach is:
- Initialize a new array V_new of the same size as V.
- For each state s, compute the expected value of successor states by taking the dot product of the transition probabilities P[s] and the old value vector V.
- Add the immediate reward r[s] and the discount factor γ to this expected value.
- Store the result in V_new[s].
- Return V_new.
This is essentially a matrix-vector multiplication followed by element-wise addition and scaling. In NumPy, this can be expressed compactly as r + gamma * (P @ V), where @ denotes matrix multiplication. The key insight is that P @ V computes ∑s′​P(s′∣s)V(s′) for all s simultaneously, leveraging optimized linear algebra libraries for efficiency.
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.