Hmm... so the following events need to successively introduce necessary concepts. Not sure when you want to incorporate 'do' operations; I'd guess a good bit later, once inference is well established (but I could also envision basic ones sooner). You might teach the player to navigate larger networks next, and introduce some simple decisions.

Maybe have a case where the node of interest is the majority vote of three nodes (N1, N2, N3). N1 is observable for cost 3, and is itself the majority vote of three nodes that are observable with cost 2. N2 is observable with cost 3, and is the deterministic is child of an observable node of cost 2. N3 is hidden. You have 5 actions.

ETA: Also want more complicated examples incorporating the collision-inference stuff from the expects-an-answer-or-is-looking-at-a-monster scenario.