Policy iteration stops when the policy no longer changes. Given two deterministic policies old and new (lists of action indices), return True if they are identical (policy is stable), else False.
Implement policy_stable(old, new).
Example
Input
policy_stable([0, 1, 1], [0, 1, 1])
Output
True
Reasoning
Inputs: each list is a deterministic policy π over 3 states. Position s holds the action chosen in state s, so old=[0,1,1] means πold(0)=0, πold(1)=1, πold(2)=1.
Stability condition: policy iteration has converged when improvement changed nothing, i.e. πnew(s)=πold(s) for every state s.
Sample: state 0: 0=0; state 1: 1=1; state 2: 1=1. All three states keep their action, so the result is True.
Output: a single Python bool, not a per-state list of matches.
Notice: one disagreement is enough to break stability. With new=[0,0,1], state 1 switches from action 1 to action 0, so the answer becomes False and iteration must continue.
In Reinforcement Learning, a policyπ maps each state to an action. For a finite state space with n states, a deterministic policy can be represented as a list (or array) of length n, where the i-th element is the action index chosen in state i. Policy Iteration is a core algorithm that alternates between two phases: policy evaluation (computing the value function for the current policy) and policy improvement (updating the policy to be greedy with respect to the new value function).
The algorithm terminates when the policy becomes stable, meaning that after a policy improvement step, the resulting policy is identical to the previous one. This is the convergence criterion for policy iteration. Because the number of distinct deterministic policies is finite (bounded by ∣A∣n), policy iteration is guaranteed to converge in a finite number of iterations, though the worst-case bound is exponential.
In practice, checking stability is straightforward: compare the old and new policy arrays element by element. If every state maps to the same action in both policies, the policy has stabilized and the algorithm can halt. This is a simple but critical check that prevents unnecessary additional iterations.
2. Algorithm Approach
This problem is a direct array comparison task. The general approach is:
Verify that both policies have the same length (a sanity check).
Iterate through each index and compare the corresponding action indices.
If any mismatch is found, the policy is not stable; return False.
If all elements match, the policy is stable; return True.
In Python, this can be done with a simple loop or by leveraging the built-in list equality operator, which performs exactly this element-wise comparison under the hood.
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.