These computations are tractable for HMMs, since the distribution q(t) = p θ (t | w) that is optimal at the E-step (which makes the inequality tight) can be represented as a lattice (a certain kind of weighted DFA), and this makes the M-step tractable via the forward-backward algorithm.
there are many extensions such as factorial HMMs and Bayesian HMMs in which an expectation under p θ (t | w) involves an intractable sum.