Policy Evaluation by Linear Solve

1. Background Knowledge

In a Markov Decision Process (MDP), the value function $V(s)$ under a fixed policy $\pi$ represents the expected sum of discounted future rewards starting from state $s$. For a finite MDP with $n$ states, this value function satisfies the Bellman equation: $V(s) = r(s) + \gamma \sum_{s'} P(s, s') V(s')$, where $r(s)$ is the immediate expected reward, $\gamma \in [0, 1)$ is the discount factor, and $P$ is the transition probability matrix induced by the policy.

When written in vector form, the Bellman equation becomes the linear system $V = r + \gamma P V$. By rearranging terms, we get $(I - \gamma P) V = r$, where $I$ is the $n \times n$ identity matrix. Since $\gamma < 1$ and $P$ is a stochastic matrix (rows sum to 1), the matrix $(I - \gamma P)$ is always invertible. This guarantees a unique solution given by $V = (I - \gamma P)^{-1} r$. This exact solution contrasts with iterative methods like policy iteration or value iteration, which approximate $V$ through successive updates.

The key insight is that for a fixed policy, the value function is not a fixed-point iteration problem but a straightforward linear algebra problem. The matrix $(I - \gamma P)$ captures the "effective" transition dynamics after accounting for discounting, and solving the linear system yields the exact value function in one step.

2. Algorithm Approach

The approach is direct linear system solving using NumPy:

1. Construct the coefficient matrix $A = I - \gamma P$.
2. Solve $A V = r$ for $V$ using a numerically stable linear solver.
3. Return $V$ as a list of floats.

The preferred method is numpy.linalg.solve(A, r) rather than explicitly computing the inverse, as it is more numerically stable and computationally efficient. Direct inversion via numpy.linalg.inv(A) @ r is discouraged in practice due to accumulated floating-point errors.

3. Step-by-Step Strategy

• Validate inputs: Ensure P is a 2D array of shape $(n, n)$, r is a 1D array of length $n$, and $0 \leq \gamma < 1$.
• Construct the identity matrix: Use np.eye(n) to create $I$.
• Form the coefficient matrix: Compute $A = I - \gamma \cdot P$ using element-wise multiplication and subtraction.
• Solve the linear system: Call np.linalg.solve(A, r) to obtain $V$.
• Convert to list: Use V.tolist() to return a plain Python list of floats, as required by the problem signature.

import numpy as np

def policy_eval_exact(P, r, gamma):
 n = len(r)
 I = np.eye(n)
 A = I - gamma * P
 V = np.linalg.solve(A, r)
 return V.tolist()

4. Common Pitfalls

• Using matrix inverse instead of solve: Computing np.linalg.inv(A) @ r introduces unnecessary numerical error and is slower. Always prefer np.linalg.solve.
• Shape mismatches: Ensure P is a 2D array and r is a 1D array. If r is passed as a column vector (shape $(n, 1)$), np.linalg.solve will return a 2D result, breaking .tolist() expectations.
• Gamma equal to 1: If $\gamma = 1$, the matrix $(I - P)$ may be singular for recurrent MDPs, causing np.linalg.solve to raise a LinAlgError. The problem guarantees $\gamma < 1$, but defensive checks are wise.
• Integer dtype issues: If P or r are integer arrays, the multiplication gamma * P may produce float results, but explicit casting to float avoids subtle type promotion bugs.
• **Forgetting **.tolist()****: Returning a NumPy array instead of a Python list will fail test cases that check type equality.

5. Time & Space Complexity

• Time Complexity: Constructing $A$ takes $O(n^2)$ for the element-wise operations. Solving the linear system via np.linalg.solve uses LU decomposition, which costs $O(n^3)$ floating-point operations. Overall complexity is $O(n^3)$.
• Space Complexity: Storing the $n \times n$ matrix $A$ requires $O(n^2)$ space. The LU decomposition in-place does not significantly increase this. The solution vector $V$ uses $O(n)$ space. Total space is $O(n^2)$.

For typical MDP sizes in coding problems ($n \leq 10^3$), this is perfectly tractable. For very large sparse systems, iterative methods like Gauss-Seidel or conjugate gradient would be preferable, but the problem explicitly asks for the exact linear solve.