  This paper is concerned with the computational complexity of learning the
Hidden Markov Model (HMM). Although HMMs are some of the most widely used tools
in sequential and time series modeling, they are cryptographically hard to
learn in the standard setting where one has access to i.i.d. samples of
observation sequences. In this paper, we depart from this setup and consider an
interactive access model, in which the algorithm can query for samples from the
conditional distributions of the HMMs. We show that interactive access to the
HMM enables computationally efficient learning algorithms, thereby bypassing
cryptographic hardness. Specifically, we obtain efficient algorithms for
learning HMMs in two settings:
  (a) An easier setting where we have query access to the exact conditional
probabilities. Here our algorithm runs in polynomial time and makes
polynomially many queries to approximate any HMM in total variation distance.
  (b) A harder setting where we can only obtain samples from the conditional
distributions. Here the performance of the algorithm depends on a new
parameter, called the fidelity of the HMM. We show that this captures
cryptographically hard instances and previously known positive results.
  We also show that these results extend to a broader class of distributions
with latent low rank structure. Our algorithms can be viewed as generalizations
and robustifications of Angluin's $L^*$ algorithm for learning deterministic
finite automata from membership queries.
