# Learning Hidden Markov Models Using Conditional Samples

arXiv: https://arxiv.org/abs/2302.14753 · HTML: https://mlsanity.com/paper/2302.14753/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 28 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [A Survey of Active Learning for Natural Language Processing](https://mlsanity.com/paper/2210.10109/) (2022)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Learning and Testing Junta Distributions with Subcube Conditioning](https://mlsanity.com/paper/2004.12496/) (2020)
- [Learning Overcomplete HMMs](https://mlsanity.com/paper/1711.02309/) (2017)
- [Minimal Realization Problems for Hidden Markov Models](https://mlsanity.com/paper/1411.3698/) (2014)
- [On learning parametric-output HMMs](https://mlsanity.com/paper/1302.6009/) (2013)
- [Learning Parametric-Output HMMs with Two Aliased States](https://mlsanity.com/paper/1502.02158/) (2015)

## Built on by (most cited first, 12 of 12)

- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [Sequences of Logits Reveal the Low Rank Structure of Language Models](https://mlsanity.com/paper/2510.24966/) (2025)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [Causal Learning in Biomedical Applications: Krebs Cycle as a Benchmark](https://mlsanity.com/paper/2406.15189/) (2024)
- [Opportunities and Challenges of Natural Language Processing for Low-Resource Senegalese Languages in Social Science Research](https://mlsanity.com/paper/2601.09716/) (2025)
- [The Role of Generator Access in Autoregressive Post-Training](https://mlsanity.com/paper/2604.04855/) (2026)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)

## Abstract (arXiv)

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.