Agnostic query learning for DFAs

Question

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.

Answer 1

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).

However, this paper by Vitaly Feldman [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:

[...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.

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.

---

[Feldman09] Vitaly Feldman. On The Power of Membership Queries in Agnostic Learning. Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.