Policy Stability Check
Problem Statement
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:
policy_stable([0, 1, 1], [0, 1, 1])
True
- We begin by identifying the two deterministic policies provided in the input: the old policy is the list [0,1,1] and the new policy is the list [0,1,1].
- To check for stability, we compare the actions at each state index i from 0 to 2 to ensure the old and new policies are identical.
- At index 0, we compare the first elements: 0=0, which matches.
- At index 1, we compare the second elements: 1=1, which matches.
- At index 2, we compare the third elements: 1=1, which matches.
- Since all corresponding elements are equal, the policies are identical, indicating the policy has converged; the final output is True
Constraints:
len(old) == len(new).- Return a Python bool.
1. Background Knowledge
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
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.