# Agnostic query learning for DFAs

Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $$n$$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?

Here's the formal setting. We have a target concept $$f^\star$$ and distribution $$D$$ over $$\Sigma^*$$. A membership query $$MQ:\Sigma^*\to\{0,1\}$$ returns the value of $$f^\star(x)$$. An "accuracy query" $$AQ$$ takes a DFA $$f$$ as input and returns $$\mathrm{err}(f):=\sum_{x\in\Sigma^*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$ a output.

The goal is to efficiently produce a small (up to $$n$$-states) DFA $$f$$ with small (or minimum) $$\mathrm{err}(f)$$ using the oracles $$MQ$$ and $$AQ$$. [A trivial solution is to brute-force search over all $$n$$-state DFAs.]

Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?

Edit: It was pointed out off-line that for parity-type concepts, $$\mathrm{err}(f)$$ might be close to $$1/2$$. So to clarify: the question seeks not a bound on the worst-case $$\mathrm{err}(f)$$, but rather an efficient procedure of attaining it via an $$n$$-state DFA.

• So, if you allow an extra slack of say $\\varepsilon$ (and high probability of success only, instead of probability one), you can always cheaply estimate $\mathrm{err}(f)$ by sampling, and this becomes equivalent to proper PAC-learning DFAs with membership queries, isn't it? – Clement C. May 28 '19 at 17:52
• Yes, exactly right. I haven't yet figured out if this question and answer have any relevance cstheory.stackexchange.com/questions/153/… – Aryeh May 28 '19 at 17:55
• For the agnostic case, where $f^\ast$ may not itself be a DFA, this looks relevant (if I parse the abstract correctly: MQ are not very useful): jmlr.org/papers/volume10/feldman09a/feldman09a.pdf – Clement C. May 28 '19 at 17:56
• Hmm, you may be right. If you turn this into a full answer, I'll accept. – Aryeh May 28 '19 at 18:00
• That still leaves the non-agnostic case open, though (not sure how much of your original motivation that is). – Clement C. May 28 '19 at 18:01

As mentioned in the comments, if you allow some extra additive slack of $$\varepsilon\in(0,1]$$ (an input parameter) in the error guarantee, and relax the success probability from one to $$1-\delta$$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $$\mathcal{C}_n$$ of $$n$$-state DFAs with membership queries.
Indeed, while you do not have accuracy queries $$\mathrm{AQ}$$, those can be easily simulated by sampling in the PAC setting (leading to the $$\pm\varepsilon$$ and $$1-\delta$$ relaxation).
In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of $$n$$-state DFAs.