📘 Explanation: The Client's Tip

To solve the singular matrix problem, we need to identify the terminal states. For this case, the client has provided us with a crucial piece of information. We have a new helper function, `get_terminal_states(env)`, which returns a reliable list of the ID numbers for all states where the episode ends. We can use this list to implement a smarter version of our Bellman solver. ---

**Food for thought #1:** In this case, we were lucky to get a tip. But what if you were dealing with a true black box? How could you design an **empirical** experiment to discover the terminal states yourself, just by running simulations?

Click to see one possible method

You could run thousands of rollouts with a random policy. Every time the `terminated` flag from `env.step()` becomes `True`, you would record the state. The set of all unique states found this way would be your empirically-discovered list of terminal states.

**Food for thought #2 (Advanced):** Could you find the terminal states using a **theoretical** approach? We know the `LinAlgError` happens when $\gamma = 1$. What if you set $\gamma = 0.99$ to get the solver to run, and then assume that any state $s$ where the calculated $V(s) = 0$ must be a terminal state? Would this be a reliable method?

Click to see the analysis

Unfortunately, this is **not a reliable method**. While all true terminal states will have a value of 0, it's possible for a **non-terminal state** to also have a value of 0. Imagine a "crossroads" state where a random policy has an equal chance of leading to a large positive reward (like the Goal) or an equally large negative reward (like a Hole). The expected return from this state—its value—would be 0, but it is not a terminal state. Therefore, this method can produce "false positives."